Nethereum Merkle Patrica trie and verification
$ dotnet add package Nethereum.Merkle.PatriciaPatricia Merkle Trie implementation for Ethereum state verification, proof generation, and cryptographic validation.
Nethereum.Merkle.Patricia implements the Modified Merkle Patricia Trie, the core data structure used by Ethereum for:
This package provides a complete implementation of the Ethereum Yellow Paper specification for Patricia tries, including proof generation and verification capabilities.
dotnet add package Nethereum.Merkle.Patricia
Nethereum Dependencies:
A Patricia Merkle Trie (also called a "Merkle Patricia Tree") is a combination of:
Key Properties:
Ethereum uses three Patricia tries per block:
The Patricia trie uses four node types:
Keys are split into nibbles (4-bit values, 0-F hex digits):
0x12 → Nibbles [1, 2]0xAB → Nibbles [A, B]This allows efficient 16-way branching at each node.
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)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
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
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
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
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
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
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
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 traversalSource: PatriciaTrie.cs:62-78
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 traversalSource: NiblesBytesExtension.cs
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 trieIHashProvider HashProvider: Hash provider (default: Keccak-256)Key Methods:
void Put(byte[] key, byte[] value, ITrieStorage storage = null)
byte[] Get(byte[] key, ITrieStorage storage)
null if key doesn't existInMemoryTrieStorage GenerateProof(byte[] key)
Static classes for verifying proofs.
static bool VerifyAccountProofs(string accountAddress, byte[] stateRoot, IEnumerable<byte[]> rlpProofs, Account account)
accountAddress: Ethereum address (hex string)stateRoot: Block's state root hashrlpProofs: RLP-encoded proof nodes (from eth_getProof)account: Expected account statetrue if account state matches proofstatic bool ValidateValueFromStorageProof(byte[] key, byte[] value, IEnumerable<byte[]> proofs, byte[] stateRoot = null)
key: Storage slot keyvalue: Expected storage valueproofs: RLP-encoded proof nodesstateRoot: Storage root (from account)true if storage value matches proofstatic bool ValidateTransactions(string transactionsRoot, List<IndexedSignedTransaction> transactions)
transactionsRoot: Transaction root from block headertransactions: List of indexed transactionstrue if reconstructed root matchesAll nodes inherit from abstract Node class.
Properties:
IHashProvider HashProvider: Hash providerMethods:
abstract byte[] GetRLPEncodedData(): RLP encoding of nodevirtual byte[] GetHash(): Keccak-256 hash of RLP dataRepresents absence of a node (null placeholder).
Terminal node containing the final value.
Properties:
byte[] Nibbles: Remaining path (nibbles)byte[] Value: Stored valueRepresents compressed path of shared nibbles.
Properties:
byte[] Nibbles: Shared path prefixNode InnerNode: Child node (branch or leaf)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)Placeholder for a node not yet loaded from storage.
Properties:
byte[] Hash: Hash of the nodeNode InnerNode: Decoded node (lazy loaded)Methods:
void DecodeInnerNode(ITrieStorage storage, bool decodeHashNodes): Load and decode from storageInterface for trie node storage.
Methods:
byte[] Get(byte[] key): Retrieve node by hashvoid Put(byte[] key, byte[] value): Store nodeIn-memory implementation of ITrieStorage.
Usage:
Decodes RLP-encoded nodes.
Methods:
Node DecodeNode(byte[] hash, bool decodeHashNodes, ITrieStorage storage): Decode node from storageExtension methods for nibble conversion.
Methods:
byte[] ConvertToNibbles(this byte[] bytes): Convert bytes to nibblesbyte[] FindAllTheSameBytesFromTheStart(this byte[] a, byte[] b): Find common prefixThe Ethereum state trie maps:
keccak256(address) → RLP([nonce, balance, storageRoot, codeHash])
Key Points:
Each contract has its own storage trie:
keccak256(slot) → RLP(value)
Key Points:
stateRoot fieldRLP(index) → RLP(transaction)
Key Points:
Proof size depends on trie depth:
Proof Verification:
Hash Collisions:
Denial of Service:
For Large Tries:
ITrieStorage with persistent backendFor Proof Generation:
Memory Management:
keccak256(address) as keys, not raw addressGet() requires storage parameter for hash node resolutionEthereum's Modified Merkle Patricia Trie differs from standard Patricia tries: