Ethereum에서 네트워크 부분을 빼고 보면, Ethereum은 하나의 state machine이고, transaction은 ethereum의 state를 변경시키는 것이다. 이 state는 key-value pair로 표현된다. Key-value pair를 저장하는 방법은 여러 가지 있지만, ethereum에서는 state를 저장하기 위해 Modified Merkle Patricia Trie(a.k.a. MPT)라는 특수화된 방법을 사용하도록 스펙에서 정의하고 있다.

MPT는 기본적으로 Patricia trie와 Merkle tree를 합친 것이다. 여기에 추가로 ethereum의 특성에 맞게 몇 가지 최적화를 했다. 따라서 MPT를 쉽게 이해하기 위해서는 Patricia trie와 Merkle tree를 아는 것이 좋다.

Patricia Trie

Patricia trie는 Prefix tree, radix tree, trie 등 다양한 이름으로 불리는 자료구조다. Trie는 path에 key를 집어넣어 공통된 prefix를 가지는 노드들은 같은 path를 가진다. 공통된 prefix를 찾는데 가장 빠르고, 적은 메모리로 구현할 수 있으며, 구현도 간단하다. 그래서 router 등 낮은 사양의 기계에 들어가는 routing table의 구현체로 많이 사용된다.

https://commons.wikimedia.org/wiki/File:Trie_example.svg

Merkle Tree

Merkle tree는 hash들의 tree다. Leaf 노드에는 데이터를 보관한다. Leaf의 부모는 leaf의 hash를 가지고, 그 부모는 자식들의 hash의 합을 다시 hash 한 값을 가진다. Merkle tree는 leaf 노드를 제외한 노드들은 전부 hash를 가지고 있기 때문에 hash tree라고도 불린다.

https://commons.wikimedia.org/wiki/File:Hash_Tree.svg

Merkle tree를 사용하면 서로 다른 두 노드가 같은 데이터를 가졌는지 효율적으로 비교할 수 있다. 예를 들어 위와 같은 L1, L2, L3, L4가 있을 때, 같은 Top Hash를 가졌는지만 비교하면 된다. 만약 Top Hash가 다르고, 어떤 데이터가 다른지 알고 싶으면 Hash0과 Hash1을 비교하고, 둘 중 다른 브랜치의 hash를 비교해나가면 어떤 데이터가 다른지 알 수 있다.

Merkle Patricia Trie

MPT는 Merkle tree처럼 각 노드가 hash를 가진다. 노드의 hash는 노드 내용의 sha3 hash로 결정된다. 이 hash는 노드를 지칭하는 key로도 사용된다. go-ethereum은 leveldb를, parity는 rocksdb라는 key-value storage에 state를 저장한다. 이때 스토리지에 저장되는 key와 value는 ethereum state의 key-value가 아니다. 스토리지에 저장되는 value는 MPT 노드의 내용이고, key는 이 노드의 hash다.

대신 ethereum state의 key는 MPT에서 path로 사용된다. MPT에서 key가 같은지 비교하는 단위는 nibble이기 때문에 하나의 노드에서 최대 16개의 branch를 가질 수 있다. 거기에 노드도 값을 가지기 때문에, 16개의 브랜치와 값을 합쳐 17개의 아이템을 가진 배열이 branch node가 된다.

아래로 자식이 없는 노드는 leaf node라고 불린다. Leaf node는 자신의 path와 value 두 개의 아이템으로 이루어진 배열이다. 예를 들어 "0xBEA"라는 키에 1000이 들어있고, "0xBEE"라는 키에 2000이 들어있는 경우를 생각해보자. 그렇다면 "0xBE"를 path로 가지는 branch node가 있고, 그 아래 "0xA"와 "0xE"를 path로 가지는 두 leaf node가 붙는다.

MPT에는 앞서 설명한 branch node와 leaf node 외에 extension node가 있다. Extension node는 branch node의 최적화다. Ethereum의 state에서는 하나의 branch node가 하나의 자식만 가지는 경우가 많다. 그래서 MPT는 하나의 자식만 가지는 branch node를 경로와 자식의 hash를 가지는 extension node로 압축한다.

여기서 문제가 하나 생긴다. Leaf node와 extension node는 둘 다 2개의 아이템을 가진 배열이다. 따라서 이 두 개의 node를 구분할 방법이 필요하다. MPT는 이를 위해서 경로에 prefix를 붙인다. 만약 노드가 leaf node고 경로가 짝수개의 nibble로 구성돼 있으면 0x20을 붙이고, 홀수개의 nibble로 구성돼 있으면 0x3을 붙인다. 반대로 extension node의 경우 짝수개의 nibble로 구성돼 있으면 0x00을, 홀수개의 nibble로 구성돼 있으면 0x1을 prefix로 붙인다. 홀수개의 nibble로 구성된 경로에는 한 개의 nibble을 prefix로 붙이고, 짝수개의 nibble로 구성된 경로에는 두 개의 nibble을 prefix로 붙이기 때문에 경로는 항상 byte로 표현 된다.