@ethereumjs/trie

@ethereumjs/trie

This is an implementation of the Modified Merkle Patricia Trie as specified in the Ethereum Yellow Paper:

The modified Merkle Patricia tree (trie) provides a persistent data structure to map between arbitrary-length binary data (byte arrays). It is defined in terms of a mutable data structure to map between 256-bit binary fragments and arbitrary-length binary data. The core of the trie, and its sole requirement in terms of the protocol specification, is to provide a single 32-byte value that identifies a given set of key-value pairs.

Installation

To obtain the latest version, simply require the project using npm:

npm install @ethereumjs/trie

Upgrading

If you currently use this package in your project and plan to upgrade, please review our upgrade guide first. It will ensure you take all the necessary steps and streamline the upgrade process.

Usage

This class implements the basic Modified Merkle Patricia Trie in the Trie base class, which you can use with the useKeyHashing option set to true to create a trie which stores values under the keccak256 hash of its keys (this is the Trie flavor which is used in Ethereum production systems).

Note: Up to v4 of the Trie library the secure trie was implemented as a separate SecureTrie class, see the upgrade guide for more infos.

Checkpointing functionality to Trie through the methods checkpoint, commit and revert.

It is best to select the variant that is most appropriate for your unique use case.

Initialization and Basic Usage

import { Trie, MapDB } from '@ethereumjs/trie'

const trie = new Trie({ db: new MapDB() })

async function test() {
  await trie.put(Buffer.from('test'), Buffer.from('one'))
  const value = await trie.get(Buffer.from('test'))
  console.log(value.toString()) // 'one'
}

test()

Use with static constructor

import { Trie, MapDB } from '@ethereumjs/trie'

const trie = Trie.create()

async function test() {
  await trie.put(Buffer.from('test'), Buffer.from('one'))
  const value = await trie.get(Buffer.from('test'))
  console.log(value.toString()) // 'one'
}

test()

When the static Trie.create constructor is used without any options, the trie object is instantiated with defaults configured to match the Etheruem production spec (i.e. keys are hashed using SHA256). It also persists the state root of the tree on each write operation, ensuring that your trie remains in the state you left it when you start your application the next time.

Trie Configuration Options

Database Options

The DB opt in the TrieOpts allows you to use any database that conforms to the DB interface to store the trie data in. We provide several examples for database implementations. The level.js example is used in the ethereumjs client while lmdb.js is an alternative implementation that uses the popular LMDB as its underlying database.

If no db option is provided, an in-memory database powered by a Javascript Map will fulfill this role.

If you want to use an alternative database, you can integrate your own by writing a DB wrapper that conforms to the DB interface. The DB interface defines the methods get, put, del, batch and copy that a concrete implementation of the DB interface will need to implement.

LevelDB

As an example, to leveage LevelDB for all operations then you should create a file with the following implementation from our recipes in your project. Then instantiate your DB and trie as below:

import { Trie } from '@ethereumjs/trie'
import { Level } from 'level'

import { LevelDB } from './your-level-implementation'

const trie = new Trie({ db: new LevelDB(new Level('MY_TRIE_DB_LOCATION')) })

Node Deletion (Pruning)

By default, the deletion of trie nodes from the underlying database does not occur in order to avoid corrupting older trie states (as of v4.2.0). Should you only wish to work with the latest state of a trie, you can switch to a delete behavior (for example, if you wish to save disk space) by using the deleteFromDB constructor option (see related release notes in the changelog for further details).

Root Persistence

You can enable persistence by setting the useRootPersistence option to true when constructing a trie through the Trie.create function. As such, this value is preserved when creating copies of the trie and is incapable of being modified once a trie is instantiated.

import { Trie, MapDB } from '@ethereumjs/trie'

const trie = await Trie.create({
  db: new MapDB(),
  useRootPersistence: true,
})

Proofs

Merkle Proofs

The createProof and verifyProof functions allow you to verify that a certain value does or does not exist within a Merkle Patricia Tree with a given root.

Proof-of-Inclusion

The following code demonstrates how to construct and subsequently verify a proof that confirms the existence of the key test (which corresponds with the value one) within the given trie. This is also known as inclusion, hence the name 'Proof-of-Inclusion.'

const trie = new Trie()

async function test() {
  await trie.put(Buffer.from('test'), Buffer.from('one'))
  const proof = await trie.createProof(Buffer.from('test'))
  const value = await trie.verifyProof(trie.root(), Buffer.from('test'), proof)
  console.log(value.toString()) // 'one'
}

test()

Proof-of-Exclusion

The following code demonstrates how to construct and subsequently verify a proof that confirms that the key test3 does not exist within the given trie. This is also known as exclusion, hence the name 'Proof-of-Exclusion.'

const trie = new Trie()

async function test() {
  await trie.put(Buffer.from('test'), Buffer.from('one'))
  await trie.put(Buffer.from('test2'), Buffer.from('two'))
  const proof = await trie.createProof(Buffer.from('test3'))
  const value = await trie.verifyProof(trie.root(), Buffer.from('test3'), proof)
  console.log(value.toString()) // null
}

test()

Invalid Proofs

If verifyProof detects an invalid proof, it will throw an error. While contrived, the below example illustrates the resulting error condition in the event a prover tampers with the data in a merkle proof.

const trie = new Trie()

async function test() {
  await trie.put(Buffer.from('test'), Buffer.from('one'))
  await trie.put(Buffer.from('test2'), Buffer.from('two'))
  const proof = await trie.createProof(Buffer.from('test2'))
  proof[1].reverse()
  try {
    const value = await trie.verifyProof(trie.root(), Buffer.from('test2'), proof)
    console.log(value.toString()) // results in error
  } catch (err) {
    console.log(err) // Missing node in DB
  }
}

test()

Range Proofs

You may use the Trie.verifyRangeProof() function to confirm if the given leaf nodes and edge proof possess the capacity to prove that the given trie leaves' range matches the specific root (which is useful for snap sync, for instance).

Read Stream on Geth DB

import { Level } from 'level'
import { LevelDB, Trie } from '@ethereumjs/trie'

import { LevelDB } from './your-level-implementation'

// Set stateRoot to block #222
const stateRoot = '0xd7f8974fb5ac78d9ac099b9ad5018bedc2ce0a72dad1827a1709da30580f0544'
// Convert the state root to a Buffer (strip the 0x prefix)
const stateRootBuffer = Buffer.from(stateRoot.slice(2), 'hex')
// Initialize trie
const trie = new Trie({
  db: new LevelDB(new Level('YOUR_PATH_TO_THE_GETH_CHAIN_DB')),
  root: stateRootBuffer,
  useKeyHashing: true,
})

trie
  .createReadStream()
  .on('data', console.log)
  .on('end', () => console.log('End.'))

Read Account State Including Storage From Geth DB

import { Level } from 'level'
import { Trie, LevelDB } from '@ethereumjs/trie'
import { Account, bufferToHex } from '@ethereumjs/util'
import { RLP } from '@ethereumjs/rlp'

import { LevelDB } from './your-level-implementation'

const stateRoot = 'STATE_ROOT_OF_A_BLOCK'

const trie = new Trie({
  db: new LevelDB(new Level('YOUR_PATH_TO_THE_GETH_CHAINDATA_FOLDER')),
  root: stateRoot
  useKeyHashing: true,
})

const address = 'AN_ETHEREUM_ACCOUNT_ADDRESS'

async function test() {
  const data = await trie.get(address)
  const acc = Account.fromAccountData(data)

  console.log('-------State-------')
  console.log(`nonce: ${acc.nonce}`)
  console.log(`balance in wei: ${acc.balance}`)
  console.log(`storageRoot: ${bufferToHex(acc.stateRoot)}`)
  console.log(`codeHash: ${bufferToHex(acc.codeHash)}`)

  const storageTrie = trie.copy()
  storageTrie.root(acc.stateRoot)

  console.log('------Storage------')
  const stream = storageTrie.createReadStream()
  stream
    .on('data', (data) => {
      console.log(`key: ${bufferToHex(data.key)}`)
      console.log(`Value: ${bufferToHex(Buffer.from(RLP.decode(data.value)))}`)
    })
    .on('end', () => console.log('Finished reading storage.'))
}

test()

You can find additional examples complete with detailed explanations here.

API

Docs

Generated TypeDoc API Documentation

BigInt Support

With the 5.0.0 release, BigInt takes the place of BN.js.

BigInt is a primitive that is used to represent and manipulate primitive bigint values that the number primitive is incapable of representing as a result of their magnitude. ES2020 saw the introduction of this particular feature. Note that this version update resulted in the altering of number-related API signatures and that the minimal build target is now set to ES2020.

Testing

You may run tests for browsers and node.js using:

npm run test

You may run tests for browsers using:

npm run test:browser

Note that this requires an installation of Mozilla Firefox, otherwise the tests will fail.

You may run tests for node.js using:

npm run test:node

Benchmarking

You will find two simple benchmarks in the benchmarks folder:

• random.ts runs random PUT operations on the tree, and
• checkpointing.ts runs checkpoints and commits between PUT operations

A third benchmark using mainnet data to simulate real load is also being considered.

You may run benchmarks using:

npm run benchmarks

To run a profiler on the random.ts benchmark and generate a flamegraph with 0x, you may use:

npm run profiling

0x processes the stacks and generates a profile folder (<pid>.0x) containing flamegraph.html.

References

• Wiki
  • Ethereum Trie Specification
• Blog posts
  • Ethereum's Merkle Patricia Trees - An Interactive JavaScript Tutorial
  • Merkling in Ethereum
  • Understanding the Ethereum Trie (This is worth reading, but mind the outdated Python libraries)
• Videos
  • Trie and Patricia Trie Overview

EthereumJS

See our organizational documentation for an introduction to EthereumJS as well as information on current standards and best practices. If you want to join for work or carry out improvements on the libraries, please review our contribution guidelines first.

License

MPL-2.0