Ethereum Merkle Patricia Trie Explained

Introduction

Merkle Patricia Trie is one of the key data structures for the Ethereum’s storage layer. I wanted to understand how exactly it works. So I did a deep research on all the materials I could find and implemented the algorithm myself.

In this block post, I’ll share what I have learned. Explain how exactly Merkle Patricia Trie works, and show you a demo of how a merkle proof is generated and verified.

The source code of the algorithm and the examples used in this blog post are all open sourced.

zhangchiqing/merkle-patricia-trie

OK, let’s get started.

A basic key-value mapping

Ethereum’s Merkle Patricia Trie 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
}

An implementation of the above Trie interface should pass the following test cases:

func TestGetPut(t *testing.T) {
	t.Run("should get nothing if key does not exist", func(t *testing.T) {
		trie := NewTrie()
		_, found :=…