[Structures] 202. Modified Merkle Patricia Trie

이 문서는 Blockchain 에 있는 문서와 동일합니다.

Patricia Trie

Patricia Tree (혹은 Radix Tree) 는 Prefix 를 나눠 Tree 를 구성합니다.

예 )

prefix a 를 거쳐 도달한 child 는 a 를 뜻합니다.
a 에서 다시 prefix a 를 거쳐 도달한 child 는 aa 를 뜻합니다.

Blockchain 에서 Block, Transaction, State 등에 사용되는 탐색 Key 가 Hash 라는 점에서, 16 진수 (0 - F) 를 사용하는 Patricia Tree 는 Blockchain 의 데이터를 보관하기에 적합하다고 볼 수 있습니다.

Modified Merkle Patricia Trie

Modified + Merkle Tree + Patricia Trie

Modified Merkle Patricia Trie 는 Ethereum 에서 State (및 Transaction, Receipt)를 저장하기 위한 핵심 자료구조입니다.

Ethereum 의 Merkle Patricia Trie 는 3 종류의 노드로 구성됩니다.

branch : 하위 16 child 를 연결하고, value 를 가집니다. [ v0, ..., v15, value ]
leaf : Key 에 해당하는 실제 value 를 가집니다. [ encodedPath, value ]
extension : leaf 가 공통의 prefix 를 가질 경우 사용합니다. [ encodedPath, key ]
- extension 으로, 불필요한 tree level (branch) 을 생략할 수 있습니다.

leaf 혹은 extension 의 경우, node 의 성격을 나타내는 4 bit 가 추가됩니다. 이때, byte 가 채워지지 않는다면, 4bit 만큼 0 padding 을 더 추가합니다.

4bit 가 16진수 하나를 표현할 수 있습니다. 바꿔 말하면, 16진수로 짝수 길이인 경우 padding 을 추가합니다.

char	type	length
0	extension	even
1	extension	odd
2	leaf	even
3	leaf	odd

Ethereum 은 Account 및 그 State 를 통해 Transaction 을 처리하며, 방대한 State 데이터를 가집니다.

Trie 를 구성하는 Node 는 기본적으로 불변이며, 변경이 발생하는 경우, 새 Node 가 생성됩니다.
Key 가 Hash 인 이상, 가지는 데이터가 바뀌면 Key 도 바뀝니다.

Block 1 의 Root 는 Ext 1 이고, Block 2 의 Root 는 Ext 2, Block 3 의 Root 는 Ext 3 입니다.
Block 2 시점에서, Leaf 2가 추가되며, 중간에 새 Branch 가 구성 되었습니다. 이때 Branch A를 재 사용합니다.
Block 3 시점에서, Leaf 3이 추가되며, Branch 가 갱신 되었습니다. 이때 Branch A 및 Leaf 2를 재 사용합니다.

State Trie 는 누적된 전체 데이터에 대해 하나만 존재하며, Block 의 State Root 는 그 중 하나의 Node 를 지정합니다.

이 구성을 통해 얻을 수 있는 이점은 크게 2가지를 들 수 있습니다.

중복된 데이터를 만들지 않아, Storage 를 절약할 수 있습니다.
각 Block 의 State Root 로 부터 탐색을 시작하면, 언제든지 특정 Block 시점의 State 를 조회할 수 있습니다.

Example

Ethereum Wiki 페이지의 예제인 아래 4 개의 Key/Value Pair 를 가지고 더 자세히 살펴봅시다.

('do', 'verb'), ('dog', 'puppy'), ('doge', 'coin'), ('horse', 'stallion')

(Reference : https://eth.wiki/fundamentals/patricia-tree)

각각의 Key 를 ASCII code 에 맞춰 HEX 변환을 시행하면 아래와 같습니다.

<64 6f> : 'verb'
<64 6f 67> : 'puppy'
<64 6f 67 65> : 'coin'
<68 6f 72 73 65> : 'stallion'

root (ext)     : [ <16>, hashA ]
hashA (branch) : [ <>, <>, <>, <>, hashB, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <> ]
hashB (ext)    : [ <00 6f>, hashC ]
hashC (branch) : [ <>, <>, <>, <>, <>, <>, hashD, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
hashD (ext)    : [ <17>, hashG ]
hashE (leaf)   : [ <20 6f 72 73 65>, 'stallion' ]
hashF (leaf)   : [ <35>, 'coin' ]
hashG (branch) : [ <>, <>, <>, <>, <>, <>, hashF, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ]

모든 Key 는 <6>으로 시작합니다. 따라서 Root 는 extension 이며 6인 <16> 을 가집니다.
hashE 는 hashA 의 v8 자리에 위치하고, <68> prefix 를 뜻 합니다.
- 나머지 <20 6f 72 73 65> 는 leaf 에 포함됩니다.
hashB 는 hashA 의 v4 자리에 위치하고, <64> prefix 를 뜻 합니다.
- do, dog, doge 는 <64 6f>가 공통입니다. prefix <64> 를 제외한 <6f>가 extension path 가 되지만, 짝수 길이이므로, padding 이 추가됩니다.
- <00 6F> 는 extension even 의 0 코드와 padding, 그리고 <6F> 입니다.
hashC 는 hashB 의 key 자리에 위치하고, <64 6f> prefix 를 뜻 합니다.
- <64 6f> 인 'verb' 데이터를 가집니다.
hashD 는 hashC 의 v6 자리에 위치하고, <64 6f 6> prefix 를 뜻 합니다.
- dog, doge 는 <64 6f 67>가 공통입니다. prefix <64 6f 6> 를 제외한 <7>이 extension path 가 됩니다.
- <17> 은 extension odd 의 1 코드와 <7> 입니다. 홀수 길이이므로, padding 은 없습니다.

Reference

Ethereum Wiki