Nethereum.Merkle.Patricia 5.8.0

Nethereum.Merkle.Patricia

Patricia Merkle Trie implementation for Ethereum state verification, proof generation, and cryptographic validation.

Overview

Nethereum.Merkle.Patricia implements the Modified Merkle Patricia Trie, the core data structure used by Ethereum for:

• State Storage: Account balances, nonces, contract code, and storage
• Proof Verification: Validate account state, storage values, and transactions
• Light Clients: Verify data without downloading the entire blockchain
• State Roots: Compute cryptographic commitments to blockchain state

This package provides a complete implementation of the Ethereum Yellow Paper specification for Patricia tries, including proof generation and verification capabilities.

Installation

dotnet add package Nethereum.Merkle.Patricia

Dependencies

Nethereum Dependencies:

• Nethereum.Model - Account and transaction models
• Nethereum.RLP - RLP encoding/decoding for trie nodes

Key Concepts

What is a Patricia Merkle Trie?

A Patricia Merkle Trie (also called a "Merkle Patricia Tree") is a combination of:

1. Patricia Trie: Radix trie optimized for sparse data (compressed paths)
2. Merkle Tree: Cryptographic hash tree for efficient verification

Key Properties:

• Deterministic: Same data always produces same root hash
• Efficient proofs: Prove inclusion/exclusion in O(log n) space
• Optimized for sparse data: Common prefixes are compressed

Ethereum Uses

Ethereum uses three Patricia tries per block:

1. State Trie: Mapping address → account (balance, nonce, storage root, code hash)
2. Transaction Trie: Mapping index → transaction data
3. Receipt Trie: Mapping index → transaction receipt (logs, status)

Node Types

The Patricia trie uses four node types:

• EmptyNode: Represents absence of data
• LeafNode: Terminal node containing value and remaining path
• ExtensionNode: Compressed path of shared nibbles
• BranchNode: 16-way fork (one per hex digit) plus optional value

Nibbles

Keys are split into nibbles (4-bit values, 0-F hex digits):

• Byte 0x12 → Nibbles [1, 2]
• Byte 0xAB → Nibbles [A, B]

This allows efficient 16-way branching at each node.

Quick Start

using Nethereum.Merkle.Patricia;
using Nethereum.Util.ByteArrayConvertors;
using System.Text;

// Create a Patricia trie
var trie = new PatriciaTrie();

// Insert key-value pairs
trie.Put(new byte[] { 1, 2, 3, 4 }, Encoding.UTF8.GetBytes("monkey"));
trie.Put(new byte[] { 1, 2 }, Encoding.UTF8.GetBytes("giraffe"));

// Get the root hash (represents entire trie state)
var rootHash = trie.Root.GetHash().ToHex();

// Retrieve a value
var value = trie.Get(new byte[] { 1, 2 }, new InMemoryTrieStorage());
// value = "giraffe" (UTF-8 bytes)

Usage Examples

Example 1: Basic Patricia Trie Operations

using Nethereum.Merkle.Patricia;
using Nethereum.Util.ByteArrayConvertors;
using Nethereum.Hex.HexConvertors.Extensions;

// Create a trie
var trie = new PatriciaTrie();

// Insert values
trie.Put(new byte[] { 1, 2, 3, 4 }, new StringByteArrayConvertor().ConvertToByteArray("monkey"));
trie.Put(new byte[] { 1, 2 }, new StringByteArrayConvertor().ConvertToByteArray("giraffe"));

// Get root hash
var hash = trie.Root.GetHash();
// Result: "a02d89d1c0a595eecbcbee8b30c7c677be66b2314bc2661e163f1349868f45c7"

// Update an existing key
trie.Put(new byte[] { 1, 2 }, new StringByteArrayConvertor().ConvertToByteArray("elephant"));

// New root hash (changed!)
hash = trie.Root.GetHash();
// Result: "f249e880b1b8af8e788411e0cf26313cdfedb4388250f64ef10bea45ef76f9d1"

Source: PatriciaTrieTests.cs:13-34

Example 2: Generating and Verifying Proofs

using Nethereum.Merkle.Patricia;
using Nethereum.Util.ByteArrayConvertors;
using Nethereum.Util.HashProviders;
using Nethereum.Hex.HexConvertors.Extensions;

// Build a trie with multiple values
var trie = new PatriciaTrie();
trie.Put(new byte[] { 1, 2, 3 }, new StringByteArrayConvertor().ConvertToByteArray("monkey"));
trie.Put(new byte[] { 1, 2, 3, 4, 5 }, new StringByteArrayConvertor().ConvertToByteArray("giraffe"));

// Generate proof for a specific key
var key = new byte[] { 1, 2, 3 };
var proofStorage = trie.GenerateProof(key);

// Proof is a collection of RLP-encoded nodes
// Now verify the proof with just the root hash (no need for full trie)

// Create a new trie from root hash only
var rootHash = trie.Root.GetHash();
var trie2 = new PatriciaTrie(rootHash, new Sha3KeccackHashProvider());

// Retrieve value using only the proof (minimal data)
var value = trie2.Get(key, proofStorage);

// Verify we got the correct value
Assert.Equal(
    new StringByteArrayConvertor().ConvertToByteArray("monkey").ToHex(),
    value.ToHex()
);

// Verify root hashes match
Assert.Equal(trie.Root.GetHash().ToHex(), trie2.Root.GetHash().ToHex());

Source: PatriciaTrieTests.cs:38-56

Example 3: Account Proof Verification (Light Clients)

using Nethereum.Merkle.Patricia;
using Nethereum.Model;
using Nethereum.Hex.HexConvertors.Extensions;
using System.Numerics;
using System.Collections.Generic;

// Scenario: Light client wants to verify account balance without full state

// State root from block header (trustworthy via PoS/PoW consensus)
var stateRoot = "0x1234...".HexToByteArray();

// Account to verify
var accountAddress = "0x742d35Cc6634C0532925a3b844Bc9e7595f0bEb";

// Proofs received from full node (via eth_getProof RPC)
var accountProofs = new List<byte[]>
{
    "0xf90211a0...".HexToByteArray(),  // RLP-encoded trie nodes
    "0xf90211a0...".HexToByteArray(),
    "0xf8518080...".HexToByteArray()
};

// Expected account state
var account = new Account
{
    Nonce = 42,
    Balance = BigInteger.Parse("5000000000000000000"),  // 5 ETH
    StateRoot = DefaultValues.EMPTY_TRIE_HASH,
    CodeHash = DefaultValues.EMPTY_DATA_HASH
};

// Verify the proof
var isValid = AccountProofVerification.VerifyAccountProofs(
    accountAddress,
    stateRoot,
    accountProofs,
    account
);

if (isValid)
{
    // Account state is cryptographically verified!
    // We know the balance is correct without downloading entire state
    Console.WriteLine($"Account balance verified: {account.Balance} wei");
}

Source: AccountProofVerification.cs:15-36

Example 4: Storage Proof Verification (Smart Contract Storage)

using Nethereum.Merkle.Patricia;
using Nethereum.Hex.HexConvertors.Extensions;
using System.Collections.Generic;

// Scenario: Verify a specific storage slot value in a smart contract

// Storage slot key (e.g., slot 0 for a simple variable)
var storageKey = "0x0000000000000000000000000000000000000000000000000000000000000000".HexToByteArray();

// Expected value in that slot
var storageValue = "0x000000000000000000000000000000000000000000000000000000000000007B".HexToByteArray(); // 123 in hex

// Storage root from account (from account proof)
var storageRoot = "0xabcd...".HexToByteArray();

// Storage proofs from full node
var storageProofs = new List<byte[]>
{
    "0xf90211a0...".HexToByteArray(),
    "0xf87180a0...".HexToByteArray()
};

// Verify storage value
var isValid = StorageProofVerification.ValidateValueFromStorageProof(
    storageKey,
    storageValue,
    storageProofs,
    storageRoot
);

if (isValid)
{
    Console.WriteLine("Storage value verified: Contract's variable at slot 0 is 123");
}

Source: StorageProofVerification.cs:17-61

Example 5: Transaction Trie Validation

using Nethereum.Merkle.Patricia;
using Nethereum.Model;
using Nethereum.RLP;
using Nethereum.Hex.HexConvertors.Extensions;
using System.Collections.Generic;
using System.Numerics;

// Scenario: Validate that transactions in a block match the transaction root

// Transactions from a block (with indices)
var transactions = new List<IndexedSignedTransaction>
{
    new IndexedSignedTransaction
    {
        Index = 0,
        SignedTransaction = new Transaction1559(
            chainId: 1,
            nonce: 0,
            maxPriorityFeePerGas: 2_000_000_000,
            maxFeePerGas: 100_000_000_000,
            gasLimit: 21000,
            receiverAddress: "0x742d35Cc6634C0532925a3b844Bc9e7595f0bEb",
            amount: BigInteger.Parse("1000000000000000000"),
            data: "",
            accessList: null,
            signature: new Signature(rBytes, sBytes, vBytes)
        )
    },
    new IndexedSignedTransaction
    {
        Index = 1,
        SignedTransaction = new LegacyTransaction(/* ... */)
    }
    // ... more transactions
};

// Transaction root from block header
var transactionsRoot = "0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421";

// Validate
var isValid = TransactionProofVerification.ValidateTransactions(
    transactionsRoot,
    transactions
);

if (isValid)
{
    Console.WriteLine("All transactions verified against block header!");
}

Source: TransactionProofVerification.cs:10-21

Example 6: Building a Trie with Leaf Nodes

using Nethereum.Merkle.Patricia;
using Nethereum.Util.ByteArrayConvertors;
using Nethereum.Hex.HexConvertors.Extensions;

// Create trie
var trie = new PatriciaTrie();

// Insert a single key-value (creates a leaf node)
var key = new byte[] { 1, 2, 3, 4 };
var value = new StringByteArrayConvertor().ConvertToByteArray("monkey");
trie.Put(key, value);

// The root IS the leaf node at this point
// Manually create equivalent leaf node to verify structure
var leafNode = new LeafNode();
leafNode.Nibbles = key.ConvertToNibbles();  // [0, 1, 0, 2, 0, 3, 0, 4]
leafNode.Value = value;

// Verify hashes match
var trieHash = trie.Root.GetHash();
var leafNodeHash = leafNode.GetHash();

Assert.Equal(
    "f6ec9fe71a6649f422350f383ff0e2e33b42a2941b1c95599f145e1e3697b864",
    trieHash.ToHex()
);
Assert.Equal(trieHash.ToHex(), leafNodeHash.ToHex());

Source: PatriciaTrieTests.cs:59-72

Example 7: Extension and Branch Node Creation

using Nethereum.Merkle.Patricia;
using Nethereum.Util.ByteArrayConvertors;
using Nethereum.Hex.HexConvertors.Extensions;

// Start with a leaf
var trie = new PatriciaTrie();
var key1 = new byte[] { 1, 2, 3, 4 };
var value1 = new StringByteArrayConvertor().ConvertToByteArray("monkey");
trie.Put(key1, value1);

// Add a second key that shares a prefix
// This will create an ExtensionNode (shared prefix) + BranchNode (fork)
var key2 = new byte[] { 1, 2, 3 };
var value2 = new StringByteArrayConvertor().ConvertToByteArray("giraffe");
trie.Put(key2, value2);

// Resulting structure:
// ExtensionNode [0,1,0,2,0,3]
//   → BranchNode (value="giraffe")
//       → Child[0]: LeafNode [4] (value="monkey")

// Manually verify structure
var leafNode = new LeafNode
{
    Nibbles = new byte[] { 4 },  // Only the differing nibble
    Value = value1
};

var branchNode = new BranchNode();
branchNode.SetChild(0, leafNode);
branchNode.Value = value2;  // Branch can have a value!

var extendedNode = new ExtendedNode
{
    InnerNode = branchNode,
    Nibbles = key2.ConvertToNibbles()  // Shared prefix
};

// Verify structure matches
var trieHash = trie.Root.GetHash();
var extendedNodeHash = extendedNode.GetHash();

Assert.Equal(
    "3b8255bc1fb241a4e8eef2bebc2b783ad3aed8da7a5ceb06db39bda447be1531",
    trieHash.ToHex()
);
Assert.Equal(extendedNodeHash.ToHex(), trieHash.ToHex());

Source: PatriciaTrieTests.cs:75-107

Example 8: Using Hash Nodes (Lazy Loading)

using Nethereum.Merkle.Patricia;
using Nethereum.Util.HashProviders;

// Hash nodes represent nodes not yet loaded into memory
// Used for efficient trie traversal with external storage

// Create a trie and populate it
var trie = new PatriciaTrie();
trie.Put(new byte[] { 1, 2, 3 }, "value1".ToBytes());
trie.Put(new byte[] { 1, 2, 4 }, "value2".ToBytes());
trie.Put(new byte[] { 5, 6, 7 }, "value3".ToBytes());

// Get root hash
var rootHash = trie.Root.GetHash();

// Store trie nodes in external storage
var storage = new InMemoryTrieStorage();
var rlpData = trie.Root.GetRLPEncodedData();
storage.Put(rootHash, rlpData);

// Later: Create trie from hash only (doesn't load full tree)
var trie2 = new PatriciaTrie(rootHash, new Sha3KeccackHashProvider());

// Root is initially a HashNode (not yet decoded)
Assert.IsType<HashNode>(trie2.Root);

// When we query, nodes are decoded on-demand
var value = trie2.Get(new byte[] { 1, 2, 3 }, storage);
// Hash node automatically decodes inner node during traversal

Source: PatriciaTrie.cs:62-78

Example 9: Working with Nibbles

using Nethereum.Merkle.Patricia;
using Nethereum.Hex.HexConvertors.Extensions;

// Understanding nibble conversion

// Byte array to nibbles
var bytes = new byte[] { 0x12, 0xAB, 0xCD };
var nibbles = bytes.ConvertToNibbles();
// Result: [1, 2, A, B, C, D] (12 nibbles total, 2 per byte)

// Nibbles are used as the path through the trie
// Each nibble (0-F) selects one of 16 branches in a BranchNode

// Example: Storing address 0x742d35Cc... in state trie
var address = "0x742d35Cc6634C0532925a3b844Bc9e7595f0bEb".HexToByteArray();
var addressNibbles = address.ConvertToNibbles();
// addressNibbles = [7,4,2,d,3,5,C,c,6,6,3,4,C,0,5,3,2,9,2,5,a,3,b,8,4,4,B,c,9,e,7,5,9,5,f,0,b,E,b]

// Each nibble represents one step in the trie traversal

Source: NiblesBytesExtension.cs

API Reference

PatriciaTrie

Main Patricia Merkle Trie implementation.

Constructors:

PatriciaTrie()
PatriciaTrie(IHashProvider hashProvider)
PatriciaTrie(byte[] hashRoot)
PatriciaTrie(byte[] hashRoot, IHashProvider hashProvider)

Properties:

• Node Root: Root node of the trie
• IHashProvider HashProvider: Hash provider (default: Keccak-256)

Key Methods:

void Put(byte[] key, byte[] value, ITrieStorage storage = null)

• Insert or update a key-value pair
• Automatically rebuilds affected nodes
• Time complexity: O(key length)

byte[] Get(byte[] key, ITrieStorage storage)

• Retrieve value for a key
• Returns null if key doesn't exist
• Requires storage for hash node resolution

InMemoryTrieStorage GenerateProof(byte[] key)

• Generate Merkle proof for a key
• Returns storage containing all nodes needed for verification
• Proof size: O(log n) where n = number of keys

Proof Verification

Static classes for verifying proofs.

AccountProofVerification

static bool VerifyAccountProofs(string accountAddress, byte[] stateRoot, IEnumerable<byte[]> rlpProofs, Account account)

• Verify account state against state root
• Used by light clients to verify balances
• Parameters:
  • accountAddress: Ethereum address (hex string)
  • stateRoot: Block's state root hash
  • rlpProofs: RLP-encoded proof nodes (from eth_getProof)
  • account: Expected account state
• Returns: true if account state matches proof

StorageProofVerification

static bool ValidateValueFromStorageProof(byte[] key, byte[] value, IEnumerable<byte[]> proofs, byte[] stateRoot = null)

• Verify smart contract storage value
• Parameters:
  • key: Storage slot key
  • value: Expected storage value
  • proofs: RLP-encoded proof nodes
  • stateRoot: Storage root (from account)
• Returns: true if storage value matches proof

TransactionProofVerification

static bool ValidateTransactions(string transactionsRoot, List<IndexedSignedTransaction> transactions)

• Verify transactions match transaction root
• Rebuilds transaction trie and compares roots
• Parameters:
  • transactionsRoot: Transaction root from block header
  • transactions: List of indexed transactions
• Returns: true if reconstructed root matches

Node Types

All nodes inherit from abstract Node class.

Node (Abstract Base)

Properties:

• IHashProvider HashProvider: Hash provider

Methods:

• abstract byte[] GetRLPEncodedData(): RLP encoding of node
• virtual byte[] GetHash(): Keccak-256 hash of RLP data

EmptyNode

Represents absence of a node (null placeholder).

LeafNode

Terminal node containing the final value.

Properties:

• byte[] Nibbles: Remaining path (nibbles)
• byte[] Value: Stored value

ExtensionNode

Represents compressed path of shared nibbles.

Properties:

• byte[] Nibbles: Shared path prefix
• Node InnerNode: Child node (branch or leaf)

BranchNode

16-way fork (one child per hex digit 0-F).

Properties:

• Node[] Children: 16 children (indexed 0-15)
• byte[] Value: Optional value (if key ends at branch)

Methods:

• void SetChild(byte index, Node node): Set child at index (0-15)

HashNode

Placeholder for a node not yet loaded from storage.

Properties:

• byte[] Hash: Hash of the node
• Node InnerNode: Decoded node (lazy loaded)

Methods:

• void DecodeInnerNode(ITrieStorage storage, bool decodeHashNodes): Load and decode from storage

Storage Interfaces

ITrieStorage

Interface for trie node storage.

Methods:

• byte[] Get(byte[] key): Retrieve node by hash
• void Put(byte[] key, byte[] value): Store node

InMemoryTrieStorage

In-memory implementation of ITrieStorage.

Usage:

• For testing and proof generation
• For temporary trie operations
• Not suitable for large persistent tries

Utility Classes

NodeDecoder

Decodes RLP-encoded nodes.

Methods:

• Node DecodeNode(byte[] hash, bool decodeHashNodes, ITrieStorage storage): Decode node from storage

NiblesBytesExtension

Extension methods for nibble conversion.

Methods:

• byte[] ConvertToNibbles(this byte[] bytes): Convert bytes to nibbles
• byte[] FindAllTheSameBytesFromTheStart(this byte[] a, byte[] b): Find common prefix

Related Packages

Used By (Consumers)

• Nethereum.RPC - eth_getProof RPC methods return Patricia trie proofs
• Light Clients - Verify state without full blockchain
• State Verification Tools - Validate blockchain state integrity
• Archive Nodes - Serve historical state proofs

Dependencies

• Nethereum.Model - Account and transaction models for verification
• Nethereum.RLP - RLP encoding for trie nodes

Important Notes

Ethereum State Trie

The Ethereum state trie maps:

keccak256(address) → RLP([nonce, balance, storageRoot, codeHash])

Key Points:

• Keys are hashed (prevents rainbow table attacks)
• Values are RLP-encoded account objects
• Storage root points to account's storage trie

Storage Trie

Each contract has its own storage trie:

keccak256(slot) → RLP(value)

Key Points:

• Keys are hashed storage slots
• Values are RLP-encoded
• Root stored in account's stateRoot field

Transaction and Receipt Tries

RLP(index) → RLP(transaction)

Key Points:

• Keys are transaction indices (0, 1, 2, ...)
• Not hashed (sequential access pattern)
• Rebuilt from transaction list

Proof Size

Proof size depends on trie depth:

• Average depth: ~5-7 nodes
• Worst case: ~64 nodes (256-bit key / 4 bits per nibble)
• Each node: ~500-1500 bytes (RLP encoded)
• Total proof: ~2.5-100 KB typically

Security Considerations

Proof Verification:

• Always verify against a trusted root hash
• Root hash comes from block header (validated by consensus)
• Never trust client-provided roots

Hash Collisions:

• Keccak-256 provides 128-bit collision resistance
• Sufficient for all practical blockchain use cases

Denial of Service:

• Deep tries can be expensive to traverse
• Use storage limits for untrusted tries
• Consider proof size limits

Performance Optimization

For Large Tries:

• Use external storage (database) for production
• Implement ITrieStorage with persistent backend
• Cache frequently accessed nodes
• Use HashNodes for lazy loading

For Proof Generation:

• Only generate proofs for necessary keys
• Cache proofs if queried frequently
• Consider proof caching service

Memory Management:

• Use HashNodes to avoid loading entire trie
• Implement node eviction for memory-constrained environments
• Clear storage after proof verification

Common Pitfalls

1. Forgetting to Hash Keys: State trie uses keccak256(address) as keys, not raw address
2. Wrong Encoding: Keys are RLP-encoded before nibble conversion
3. Missing Storage: Get() requires storage parameter for hash node resolution
4. Null vs Empty: EmptyNode vs null value - check both
5. Nibble Confusion: Remember keys are nibbles, not bytes (2 nibbles per byte)

Differences from Standard Patricia Trie

Ethereum's Modified Merkle Patricia Trie differs from standard Patricia tries:

1. Merkle Hashing: Nodes are hashed (Merkle property)
2. RLP Encoding: All data is RLP-encoded
3. Hexary: 16-way branching instead of binary
4. Hash Nodes: Lazy loading support via hash references
5. Compact Encoding: Special encoding for nibble paths (with terminator flag)

Additional Resources

Ethereum Yellow Paper

• Section 4.1: World State - State trie specification
• Appendix D: Modified Merkle Patricia Trie - Complete trie specification

Ethereum Documentation

• Patricia Merkle Trie
• State and Storage Proofs
• eth_getProof RPC Method

Research Papers

• Merkle Patricia Trie Specification - Ethereum Wiki

Nethereum Documentation

• Nethereum Documentation
• Nethereum GitHub

Light Client Resources

• EIP-1186: RPC-Method to get Merkle Proofs
• Light Client Protocol