[Cryptography] Merkle Patricia Trie (MPT)

이민기·2022년 6월 3일
1

BlockChain & Cryptography

목록 보기
10/12
post-thumbnail

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개의 요소로 구성되어 있는 배열이며 encodedPathvalue값이 들어가 있다.

  • extension : 2개의 요소로 구성되어 있는 배열이며 encodedPathkey값이 들어가 있다.

hex Prefix Encoding

extension Node 와 leaf Node를 구별하기 위해 사용
Merkle Patricia Trie는 nibble 단위로 저장된다, nibble은 4bit 즉 0.5byte이며 hex char역시도 4bit이며 1byte로 떨어지지 않을 경우 1byte를 맞추기 위해 0을 이용하여 padding한다.

hex charnode tpyepath length
0extensioneven
1extensionodd
2terminating (leaf)even
3terminating (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이므로 encodedPathkey로만 이루어져 있다
hashC, hashG : leaf Node이므로 encodedPathvalue로만 이루어져 있다
hashD, hashF : branch Node이며 value가 존재하므로 16개의 hashing된 주소값이 들어갈 수 있는 indexvalue로 이루어져 있다.

profile
블로그를 옮기는 중입니다. https://min71.dev

0개의 댓글