Demistifying Merkle Patricia Tries (MPTs)

one of the key data structures used by go-ethereum to save state

Merkle Patricia Trie is one of the key data structures for the Ethereum’s storage layer and is essentially a key-value mapping that provides the following standard methods:


type Trie interface {
  // methods as a basic key-value mapping
  Get(key []byte) ([]byte, bool) {
  Put(key []byte, value []byte)
  Del(key []byte, value []byte) bool
}

Essentially, the Modified Patricia Trie (MPT) integrates elements of the Patricia trie and Merkle tree, along with several optimizations tailored to Ethereum's specific needs. Consequently, a foundational grasp of both the Patricia trie and Merkle tree is mandatory before delving into the intricacies of the MPT.

Patricia Trie

The Patricia trie, also known as a Prefix tree, radix tree, or simply trie, is a data structure where keys are used as paths, allowing nodes with common prefixes to share the same path. This design excels in quickly identifying common prefixes, is straightforward to implement, and has a low memory footprint. As a result, it is widely utilized in creating routing tables and systems, particularly in devices with limited specifications, such as routers.

Merkle Tree

The Merkle tree, often referred to as a hash tree, is structured with hashes at each node. The leaf nodes hold actual data, while parent nodes store hashes that represent the combined hash values of their child nodes. In this tree, every node, except for the leaf nodes, contains a hash, which is why it's called a hash tree.

The Merkle tree offers an efficient method to determine if two nodes contain identical data. This is achieved by comparing the top hash values of the nodes. If these top hashes match, it indicates that the nodes hold the same data. For instance, in a scenario with four nodes (L1, L2, L3, L4), the equality of their top hash values would confirm their data similarity. Conversely, if the top hashes differ and there's a need to identify the distinct data, one should compare Hash 0 with Hash 1 to locate the divergent branch. This step-by-step comparison ultimately reveals the specific data that differs between the nodes.

Merkle Patricia Trie

In both the MPT and the Merkle tree, each node possesses a hash value determined by the sha3 hash of its contents. This hash also serves as the reference key for the node. In terms of storage, go-ethereum employs LevelDB and Parity utilizes RocksDB, both of which are key-value storage systems. However, the keys and values stored in these systems do not directly correspond to the key-values of the Ethereum state. Instead, the content of the MPT node is what is stored as the value, while the key is the hash of this node.

In the MPT, the key-values of the Ethereum state function as pathways. The distinguishing unit for these key values in the MPT is the nibble, allowing each node the potential to branch out into up to 16 different paths. Furthermore, as each node carries its unique value, a branch node comprises an array of 17 elements, which includes one node value and 16 branches.

A node without any child nodes is known as a leaf node. Each leaf node contains two components: its path and its value. For instance, consider that the key "0xBEA" holds the value 1000 and the key "0xBEE" holds 2000. In this scenario, there would be a branch node for the path "0xBE." Under this branch node, two leaf nodes corresponding to the paths "0xA" and "0xE" would be connected, representing the respective key values.

In the MPT, besides branch and leaf nodes, there exists another type of node known as the extension node. These extension nodes are essentially optimized versions of branch nodes. Often in the Ethereum state, there are branch nodes with only a single child node. To address this, the MPT compresses such branch nodes into extension nodes. An extension node consists of a path and the hash of its single child node, streamlining the structure where only one child is present.

Since both leaf and extension nodes in the MPT are arrays with two items, a method is needed to distinguish them. This is achieved by adding a specific prefix to the path. For a leaf node with an even number of nibbles in its path, the prefix 0x20 is added. If the path has an odd number of nibbles, the prefix becomes 0x3. For an extension node, if the path contains an even number of nibbles, the prefix used is 0x00, and for an odd number of nibbles, the prefix is 0x1. This system of prefixing ensures that a path with an odd number of nibbles gets one nibble as a prefix, while a path with an even number of nibbles receives two nibbles as a prefix, allowing every path to be uniformly expressed as a byte.

A practical implementation

A first practical use of MPTs is for data integrity. One can compute the Merkle Root Hash of the trie with the Hash function, such that if any key-value pair was updated, the Merkle root hash of the trie would be different; if two MPTs have the identical key-value pairs, they should have the same Merkle root hash.


type Trie interface {
  // compute the Merkle root hash for verifying data integrity
  Hash() []byte
}

The MPT is optimized to allows us to verify the inclusion of a key-value pair without the access to the entire set of key-value pairs. That means MPTs can provide a proof that a certain key-value pair is included in a key-value mapping that produces a certain Merkle root hash.


type Proof interface {}

type Trie interface {
  // generate a merkle proof for a key-value pair for verifying the inclusion of the key-value pair
  Prove(key []byte) (Proof, bool)
}

// verify the proof for the given key with the given merkle root hash
func VerifyProof(rootHash []byte, key []byte, proof Proof) (value []byte, err error)

This is useful in Ethereum. For instance, imagine the Ethereum world state is a key-value mapping, and the keys are each account address, and the values are the balances for each account. As a light client, which don’t have the access to the full blockchain state like full nodes do, but only the merkle root hash for certain block, how can it trust the result of its account balance returned from a full node?

The answer is, a full node can provide a merkle proof which contains the merkle root hash, the account key and its balance value, as well as other data. This merkle proof allows a light client to verify the correctness by its own without having access to the full blockchain state.

Using the APIs defined above, we can now write code to generate and verify proofs:


func TestProveAndVerifyProof(t *testing.T) {
	t.Run("should not generate proof for non-exist key", func(t *testing.T) {
		tr := NewTrie()
		tr.Put([]byte{1, 2, 3}, []byte("hello"))
		tr.Put([]byte{1, 2, 3, 4, 5}, []byte("world"))
		notExistKey := []byte{1, 2, 3, 4}
		_, ok := tr.Prove(notExistKey)
		require.False(t, ok)
	})

	t.Run("should generate a proof for an existing key, the proof can be verified with the merkle root hash", func(t *testing.T) {
		tr := NewTrie()
		tr.Put([]byte{1, 2, 3}, []byte("hello"))
		tr.Put([]byte{1, 2, 3, 4, 5}, []byte("world"))

		key := []byte{1, 2, 3}
		proof, ok := tr.Prove(key)
		require.True(t, ok)

		rootHash := tr.Hash()

		// verify the proof with the root hash, the key in question and its proof
		val, err := VerifyProof(rootHash, key, proof)
		require.NoError(t, err)

		// when the verification has passed, it should return the correct value for the key
		require.Equal(t, []byte("hello"), val)
	})

	t.Run("should fail the verification if the trie was updated", func(t *testing.T) {
		tr := NewTrie()
		tr.Put([]byte{1, 2, 3}, []byte("hello"))
		tr.Put([]byte{1, 2, 3, 4, 5}, []byte("world"))

		// the hash was taken before the trie was updated
		rootHash := tr.Hash()

		// the proof was generated after the trie was updated
		tr.Put([]byte{5, 6, 7}, []byte("trie"))
		key := []byte{1, 2, 3}
		proof, ok := tr.Prove(key)
		require.True(t, ok)

		// should fail the verification since the merkle root hash doesn't match
		_, err := VerifyProof(rootHash, key, proof)
		require.Error(t, err)
	})
}

A light client can ask for a merkle root hash of the MPT state, and use it to verify the balance of its account. If the MPT was updated, even if the updates was to other keys, then the verification would fail. And now, the light client only needs to trust the merkle root hash, which is a small piece of data, to convince themselves whether the full node returned the correct balance for its account.

Since Ethereum’s consensus mechanism is Proof of Work, and the merkle root hash for the world state is included in each block head, the computation work is the proof for verifying/trusting the merkle root hash.

Verifying Ethereum data

Ethereum has 3 Merkle Patricia Tries: Transaction Trie, Receipt Trie and State Trie. In each block header, it includes the 3 merkle root hashes: transactionRoot, receiptRoot and the stateRoot.

Since the transactionRoot is the Merkle root hash of all the transactions included in the block, we could verify our implementation by taking all the transactions, then store them in our trie, compute its merkle root hash, and in the end compare it with the transactionRoot in the block header.

I picked the block 10467135 on mainnet, and saved all the 193 transactions into a transactions.json file. Since the transaction root for block 10467135 is 0xbb345e208bda953c908027a45aa443d6cab6b8d2fd64e83ec52f1008ddeafa58. I can create a test case that adds the 193 transactions of block 10467135 to our Trie and check:

Whether the merkle root hash is bb345e208bda953c908027a45aa443d6cab6b8d2fd64e83ec52f1008ddeafa58.
Whether a merkle proof for a certain transaction generated from our trie implementation could be verified by the official implementation.

But what would be the keys and values for the list of transactions? The keys are the RLP encoding of a unsigned integer starting from index 0; the values are the RLP encoding of the corresponding transactions.

The code to perform the verification would look like this:


import (
	"github.com/ethereum/go-ethereum/common"
	"github.com/ethereum/go-ethereum/core/types"
	"github.com/ethereum/go-ethereum/trie"
)
// use the official golang implementation to check if a valid proof from our implementation can be accepted
func VerifyProof(rootHash []byte, key []byte, proof Proof) (value []byte, err error) {
	return trie.VerifyProof(common.BytesToHash(rootHash), key, proof)
}
// load transaction from json
func TransactionJSON(t *testing.T) *types.Transaction {
	jsonFile, err := os.Open("transaction.json")
	defer jsonFile.Close()
	require.NoError(t, err)
	byteValue, err := ioutil.ReadAll(jsonFile)
	require.NoError(t, err)
	var tx types.Transaction
	json.Unmarshal(byteValue, &tx)
	return &tx
}
func TestTransactionRootAndProof(t *testing.T) {
	trie := NewTrie()
	txs := TransactionsJSON(t)
	for i, tx := range txs {
		// key is the encoding of the index as the unsigned integer type
		key, err := rlp.EncodeToBytes(uint(i))
		require.NoError(t, err)
		transaction := FromEthTransaction(tx)
		// value is the RLP encoding of a transaction
		rlp, err := transaction.GetRLP()
		require.NoError(t, err)
		trie.Put(key, rlp)
	}
	// the transaction root for block 10467135
	// https://api.etherscan.io/api?module=proxy&action=eth_getBlockByNumber&tag=0x9fb73f&boolean=true&apikey=YourApiKeyToken
	transactionRoot, err := hex.DecodeString("bb345e208bda953c908027a45aa443d6cab6b8d2fd64e83ec52f1008ddeafa58")
	require.NoError(t, err)
	t.Run("merkle root hash should match with 10467135's transactionRoot", func(t *testing.T) {
		// transaction root should match with block 10467135's transactionRoot
		require.Equal(t, transactionRoot, trie.Hash())
	})
	t.Run("a merkle proof for a certain transaction can be verified by the offical trie implementation", func(t *testing.T) {
		key, err := rlp.EncodeToBytes(uint(30))
		require.NoError(t, err)
		proof, found := trie.Prove(key)
		require.Equal(t, true, found)
		txRLP, err := VerifyProof(transactionRoot, key, proof)
		require.NoError(t, err)
		// verify that if the verification passes, it returns the RLP encoded transaction
		rlp, err := FromEthTransaction(txs[30]).GetRLP()
		require.NoError(t, err)
		require.Equal(t, rlp, txRLP)
	})
}

The above test cases passed, and showed if we add all the 193 transactions of block 10467135 to our MPT, then the MPT hash is the same as the transactionRoot published in that block. And the merkle proof for the transaction with index 30, generated by our trie, is considered valid by the official golang MPT implementation.

The source code of the algorithm and the examples used in this blog post are all available in my Github repo.

For more examples on how to use MPTs to verify account balances and smart contracts, check out the articles below:

EIP 1186 Explained with Examples— the standard for Getting Account Proof

Verify Ethereum Account Balance with State Proof

Verify Ethereum Smart Contract State with Proof

Verify USDC Balance and NFT Meta Data with Proof