Merkle Patricia Trie (MPT)
Merkle Patricia Trie란 이더리움에서 사용하는 자료구조이며 Merkle trie를 변형해서 사용한다
특징
-
각각의 노드는 sha3을 이용해서 hashing 한다
-
MPT는 key-value DB이다
↪ level DB은 Go, C++, Python client에서 사용되고, rocks DB은 Parity client에서 사용된다.
↪ key는 각 Node의 hash이고 value는 각 Node의 값을 의미한다. -
Merkle Tree처럼 하나의 Node라도 변경될 경우 Root Hash에 영향을 주게 되어 값의 안전성을 보장할 수 있다
타입
-
NULL : NULL은 빈 문자열값을 의미 한다.
-
branch : 16~17개의 요소로 구성되어 있는 배열이다 0~15번 Index는 hashing된 주소값이 들어갈 수 있으며
value가 있는경우에는 마지막 index로value의 값이 들어간다.
↪ hashing된 주소값은 index에 맞춰 들어간다 -
leaf : 2개의 요소로 구성되어 있는 배열이며
encodedPath와value값이 들어가 있다. -
extension : 2개의 요소로 구성되어 있는 배열이며
encodedPath와key값이 들어가 있다.
hex Prefix Encoding
extension Node 와 leaf Node를 구별하기 위해 사용
↪Merkle Patricia Trie는 nibble 단위로 저장된다, nibble은 4bit 즉 0.5byte이며 hex char역시도 4bit이며 1byte로 떨어지지 않을 경우 1byte를 맞추기 위해 0을 이용하여 padding한다.
| hex char | node tpye | path length |
|---|---|---|
| 0 | extension | even |
| 1 | extension | odd |
| 2 | terminating (leaf) | even |
| 3 | terminating (leaf) | odd |
📌 Example
가상의 path 예시
- <64 6f> : "Kevin"
- <64 6f 67> : "FOEN"
- <64 6f 67 65> : "David"
- <68 6f 72 73 65> : "YAYA"
가상의 key - value을 기준 trie 예시
rootHash : [ <16>, hashA ]
hashA : [<>, <>, <>, <>, hashB, <>, <>, <>, hashC, <>, <>, <>, <>, <>, <>, <>, <>]
hashB : [<00 6f>, hashD ]
hashC : [<20 6f 72 73 65>, "YAYA"]
hashD : [<>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, "Kevin"]
hashE : [<17>, hashF]
hashF : [<>, <>, <>, <>, <>, <>, hashG, <>, <>, <>, <>, <>, <>, <>, <>, <>, "FODEN"]
hashG : [<35>, "David"]
✏️ Example hash 특징
hashA : branch Node이며
value가 존재지 않기 때문에 16개의 hashing된 주소값이 들어갈 수 있는index로만 이루어져 있다
hashB, hashE : extension Node이므로encodedPath와key로만 이루어져 있다
hashC, hashG : leaf Node이므로encodedPath와value로만 이루어져 있다
hashD, hashF : branch Node이며value가 존재하므로 16개의 hashing된 주소값이 들어갈 수 있는index와value로 이루어져 있다.
