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:
Patricia Trie: Radix trie optimized for sparse data (compressed paths)
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
Transaction Trie: Mapping index → transaction data
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