Security News
ESLint is Now Language-Agnostic: Linting JSON, Markdown, and Beyond
ESLint has added JSON and Markdown linting support with new officially-supported plugins, expanding its versatility beyond JavaScript.
merkle-patricia-tree
Advanced tools
This is an implementation of the modified merkle patricia tree as specified in Ethereum's yellow paper.
The merkle-patricia-tree npm package is a JavaScript implementation of the Ethereum modified Merkle Patricia Trie. It is used to store key-value pairs in a way that allows for efficient verification of the inclusion and integrity of data. This is particularly useful in blockchain applications where data integrity and proof of inclusion are critical.
Creating a Trie
This feature allows you to create a new instance of a Merkle Patricia Trie. The Trie can then be used to store and manage key-value pairs.
const { BaseTrie: Trie } = require('merkle-patricia-tree');
const trie = new Trie();
Inserting Data
This feature allows you to insert key-value pairs into the Trie. The keys and values are stored as Buffers.
const { BaseTrie: Trie } = require('merkle-patricia-tree');
const trie = new Trie();
trie.put(Buffer.from('key1'), Buffer.from('value1'), (err) => {
if (err) throw err;
console.log('Data inserted');
});
Retrieving Data
This feature allows you to retrieve the value associated with a given key from the Trie.
const { BaseTrie: Trie } = require('merkle-patricia-tree');
const trie = new Trie();
trie.put(Buffer.from('key1'), Buffer.from('value1'), (err) => {
if (err) throw err;
trie.get(Buffer.from('key1'), (err, value) => {
if (err) throw err;
console.log('Retrieved value:', value.toString());
});
});
Deleting Data
This feature allows you to delete a key-value pair from the Trie.
const { BaseTrie: Trie } = require('merkle-patricia-tree');
const trie = new Trie();
trie.put(Buffer.from('key1'), Buffer.from('value1'), (err) => {
if (err) throw err;
trie.del(Buffer.from('key1'), (err) => {
if (err) throw err;
console.log('Data deleted');
});
});
Proving Inclusion
This feature allows you to create a proof that a particular key-value pair is included in the Trie.
const { BaseTrie: Trie } = require('merkle-patricia-tree');
const trie = new Trie();
trie.put(Buffer.from('key1'), Buffer.from('value1'), (err) => {
if (err) throw err;
trie.createProof(Buffer.from('key1'), (err, proof) => {
if (err) throw err;
console.log('Proof:', proof);
});
});
The merkle-tree package provides a simple implementation of a Merkle Tree, which is a binary tree used for data verification. Unlike the merkle-patricia-tree, it does not support the Patricia Trie structure, which is more efficient for certain types of key-value storage and retrieval.
The merkle package is another implementation of a Merkle Tree. It is designed for general-purpose use and does not include the Patricia Trie optimizations found in merkle-patricia-tree. It is simpler but less efficient for large datasets.
The merkle-tools package provides utilities for creating and managing Merkle Trees. It includes features for creating proofs and verifying data integrity, similar to merkle-patricia-tree, but it does not implement the Patricia Trie structure.
This is an implementation of the modified merkle patricia tree 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.
The only backing store supported is LevelDB through the levelup
module.
npm install merkle-patricia-tree
There are 3 variants of the tree implemented in this library, namely: BaseTrie
, CheckpointTrie
and SecureTrie
. CheckpointTrie
adds checkpointing functionality to the BaseTrie
with the methods checkpoint
, commit
and revert
. SecureTrie
extends CheckpointTrie
and is the most suitable variant for Ethereum applications. It stores values under the keccak256
hash of their keys.
By default, trie nodes are not deleted from the underlying DB to not corrupt older trie states (as of v4.2.0
). If you are only interested in the latest state of a trie, you can switch to a delete behavior (e.g. if you want to save disk space) by using the deleteFromDB
constructor option (see related release notes in the changelog for more details).
import level from 'level'
import { BaseTrie as Trie } from 'merkle-patricia-tree'
const db = level('./testdb')
const trie = new Trie(db)
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()
The createProof
and verifyProof
functions allow you to verify that a certain value does or does not exist within a Merkle-Patricia trie with a given root.
The below code demonstrates how to construct and then verify a proof that proves that the key test
that corresponds to the value one
does exist in the given trie, so a proof of existence.
const trie = new Trie()
async function test() {
await trie.put(Buffer.from('test'), Buffer.from('one'))
const proof = await Trie.createProof(trie, Buffer.from('test'))
const value = await Trie.verifyProof(trie.root, Buffer.from('test'), proof)
console.log(value.toString()) // 'one'
}
test()
The below code demonstrates how to construct and then verify a proof that proves that the key test3
does not exist in the given trie, so a proof of non-existence.
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(trie, Buffer.from('test3'))
const value = await Trie.verifyProof(trie.root, Buffer.from('test3'), proof)
console.log(value.toString()) // null
}
test()
Note, if verifyProof
detects an invalid proof, it throws an error. While contrived, the below example demonstrates the error condition that would result if 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(trie, 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()
import level from 'level'
import { SecureTrie as Trie } from 'merkle-patricia-tree'
const db = level('YOUR_PATH_TO_THE_GETH_CHAIN_DB')
// 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, stateRootBuffer)
trie
.createReadStream()
.on('data', console.log)
.on('end', () => {
console.log('End.')
})
import level from 'level'
import { Account, BN, bufferToHex, rlp } from 'ethereumjs-util'
import { SecureTrie as Trie } from 'merkle-patricia-tree'
const stateRoot = 'STATE_ROOT_OF_A_BLOCK'
const db = level('YOUR_PATH_TO_THE_GETH_CHAINDATA_FOLDER')
const trie = new Trie(db, stateRoot)
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(rlp.decode(data.value))}`)
})
.on('end', () => {
console.log('Finished reading storage.')
})
}
test()
Additional examples with detailed explanations are available here.
npm test
There are two simple benchmarks in the benchmarks
folder:
random.ts
runs random PUT
operations on the tree.checkpointing.ts
runs checkpoints and commits between PUT
operations.A third benchmark using mainnet data to simulate real load is also under consideration.
Benchmarks can be run with:
npm run benchmarks
To run a profiler on the random.ts
benchmark and generate a flamegraph with 0x you can use:
npm run profiling
0x processes the stacks and generates a profile folder (<pid>.0x
) containing flamegraph.html
.
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 do improvements on the libraries have a look at our contribution guidelines.
FAQs
This is an implementation of the modified merkle patricia tree as specified in Ethereum's yellow paper.
The npm package merkle-patricia-tree receives a total of 134,720 weekly downloads. As such, merkle-patricia-tree popularity was classified as popular.
We found that merkle-patricia-tree demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 7 open source maintainers collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
ESLint has added JSON and Markdown linting support with new officially-supported plugins, expanding its versatility beyond JavaScript.
Security News
Members Hub is conducting large-scale campaigns to artificially boost Discord server metrics, undermining community trust and platform integrity.
Security News
NIST has failed to meet its self-imposed deadline of clearing the NVD's backlog by the end of the fiscal year. Meanwhile, CVE's awaiting analysis have increased by 33% since June.