Skip to content
LogoLogo

Merkle Patricia trie

MerklePatriciaTrie<H> implements Ethereum's Merkle Patricia Trie (MPT): nibble-addressed byte keys, four node types (empty, leaf, extension, branch), hex-prefix path encoding, RLP-encoded nodes, and Ethereum's inline-or-hash node references.

With Keccak256, roots match Ethereum: the implementation is tested against the official trietest.json and trieanyorder.json vectors from the Ethereum test suite.

Insert, get, remove

use merkle_variants::MerklePatriciaTrie;
use merkleforge_hash::Keccak256;
 
fn main() -> Result<(), merkle_core::error::MerkleError> {
    let mut trie = MerklePatriciaTrie::<Keccak256>::new();
 
    trie.insert(b"account:alice", b"100")?;
    trie.insert(b"account:bob", b"250")?;
    trie.insert(b"account:alice", b"90")?; // overwrite
 
    assert_eq!(trie.get(b"account:alice"), Some(b"90".as_slice()));
    assert_eq!(trie.get(b"account:carol"), None);
    assert_eq!(trie.leaf_count(), 2);
 
    // Removal collapses branches and extensions, so the root equals that of a
    // trie built from the remaining entries.
    trie.remove(b"account:bob")?;
 
    let mut fresh = MerklePatriciaTrie::<Keccak256>::new();
    fresh.insert(b"account:alice", b"90")?;
    assert_eq!(trie.root(), fresh.root());
    Ok(())
}

Unlike the sparse tree, get returns the stored value bytes. Values must be non-empty (EmptyLeafData), and removing a missing key returns UnsupportedOperation. root() is None for an empty trie.

Ethereum compatibility

The trie produces the same root as Ethereum clients for the same key-value set. This is the dogs case from Ethereum's trieanyorder.json:

use merkle_variants::MerklePatriciaTrie;
use merkleforge_hash::Keccak256;
 
fn hex32(s: &str) -> [u8; 32] {
    let s = s.trim_start_matches("0x");
    let mut out = [0_u8; 32];
    for (i, byte) in out.iter_mut().enumerate() {
        *byte = u8::from_str_radix(&s[2 * i..2 * i + 2], 16).expect("valid hex");
    }
    out
}
 
fn main() -> Result<(), merkle_core::error::MerkleError> {
    let mut trie = MerklePatriciaTrie::<Keccak256>::new();
    trie.insert(b"doe", b"reindeer")?;
    trie.insert(b"dog", b"puppy")?;
    trie.insert(b"dogglesworth", b"cat")?;
 
    let expected = hex32("0x8aad789dff2f538bca5d8ea56e8abe10f4c7ba3a5dea95fea4cd6e7c3a1168d3");
    assert_eq!(trie.root(), Some(&expected));
    Ok(())
}

Insertion order does not matter: the trie is canonical.

How compatibility works: the Keccak256 adapter overrides HashFunction::hash_encoded_node to return plain Keccak-256(rlp), with no domain prefix, exactly as Ethereum hashes nodes. RLP already distinguishes node types, so the 0x00/0x01 prefixes used by binary and sparse trees are not needed here.

Witnesses (proofs)

generate_proof(key) returns an MptProof<D>: the key, the value (or None), and the RLP-encoded nodes on the key's path, root first. It has the shape of an EIP-1186 accountProof / storageProof entry.

use merkle_variants::{MerklePatriciaTrie, MptProof};
use merkleforge_hash::Keccak256;
 
fn main() -> Result<(), merkle_core::error::MerkleError> {
    let mut trie = MerklePatriciaTrie::<Keccak256>::new();
    trie.insert(b"account:alice", b"100")?;
    trie.insert(b"account:bob", b"250")?;
    let root = *trie.root().expect("trie is not empty");
 
    // Membership
    let proof = trie.generate_proof(b"account:alice")?;
    assert!(proof.is_membership());
    assert_eq!(proof.value.as_deref(), Some(b"100".as_slice()));
    assert!(MerklePatriciaTrie::<Keccak256>::verify_proof(&root, &proof));
 
    // Non-membership: the path ends at an empty slot or a divergent node.
    let absent = trie.generate_proof(b"account:carol")?;
    assert!(absent.is_non_membership());
    assert!(MerklePatriciaTrie::<Keccak256>::verify_proof(&root, &absent));
 
    // A forged value fails verification.
    let forged: MptProof<[u8; 32]> = MptProof::new(
        proof.key.clone(),
        Some(b"1000000".to_vec()),
        proof.proof_nodes.clone(),
    );
    assert!(!MerklePatriciaTrie::<Keccak256>::verify_proof(&root, &forged));
    Ok(())
}

verify_proof checks that the first node hashes to the trusted root, then walks the key's nibble path through the witness. The verifier needs only the root and the proof, so it works for light clients and cross-chain bridges. MptProof derives Serialize / Deserialize, so you can send it over the network directly.

generate_proof on an empty trie returns MerkleError::EmptyTree.

Low-level building blocks

The merkle_variants::patricia module exposes the encoding primitives for tooling and tests:

ItemPurpose
NibblePathByte key to 4-bit nibble path (from_key, len, get, slice, common_prefix_len)
hp_encode / hp_decodeHex-prefix encoding for leaf and extension paths
rlp_encode / rlp_decodeRLP for MptNode values
MptNode<D>Empty, Leaf, Extension, Branch
NodeRef<D>Hash(D) for nodes ≥ 32 bytes of RLP, Inline(Vec<u8>) otherwise
hash_node::<H>Ethereum-style reference for a node
compute_root_hash::<H>Root digest for a root node (always hashed)
use merkle_variants::patricia::{compute_root_hash, hp_encode, MptNode, NibblePath};
use merkleforge_hash::Keccak256;
 
fn main() {
    // The empty trie root, keccak256(rlp("")), well known from Ethereum.
    let empty = compute_root_hash::<Keccak256>(&MptNode::Empty);
    assert_eq!(empty[..4], [0x56, 0xe8, 0x1f, 0x17]);
 
    let path = NibblePath::from_key(b"key");
    assert_eq!(path.len(), 6); // two nibbles per byte
 
    // Hex-prefix flag for a leaf with an even-length path is 0x20.
    assert_eq!(hp_encode(&path, true)[0], 0x20);
}

Through the generic trait

MerklePatriciaTrie implements MerkleTree<H>: leaf index i is stored under b"merkleforge:mpt:trait-leaf:" ‖ i (8 bytes, big-endian). MerkleTree::generate_proof returns UnsupportedOperation because Patricia proofs are key-addressed; call the inherent generate_proof(key) instead.

Suggest changes to this page