개요
이더리움에서 비트코인에서의 바이너리 머클트리보다 효율성을 찾기위하여 도임한 내용이다.
머클 패트리샤 trie는 여러가지 이더리움에 맞게 개선한 자료구조다.
각각의 노드는 [key, value]를 가지고 있고 leaf노드 부터 부모노드를 올라가면서 계속 hash하면서
최종적으로 root node에 이르게 되어 root 해시값을 만든다.
이더리움의 모든 데이터는 머클 페트리샤 트리로 저장이 된다.
머클 패트리샤 trie는 여러가지 이더리움에 맞게 개선한 자료구조다.
각각의 노드는 [key, value]를 가지고 있고 leaf노드 부터 부모노드를 올라가면서 계속 hash하면서
최종적으로 root node에 이르게 되어 root 해시값을 만든다.
이더리움의 모든 데이터는 머클 페트리샤 트리로 저장이 된다.
해당 구조는 Radix트리와 Merkle트리를 혼합하여 최적화 시켰다.
즉 머클 패트리샤 트리를 이해하려면 Radix 트리와 Merkle트리를 이해해야한다.
개념정리
Trie
동적 셋 또는 연관배열을 저장하는데 사용되는 정렬된 트리 구조.
트리상의 노드들은 그 노드와 연관된 키를 저장하지 않는다.
그 대신, 트리상에서 위치가 현재의 키를 나타낸다.
특정노드의 모든 후손들은 그 노드에서와 동일한 prefix를 가지며, 루트노드는 빈 문자열을 갖는다.
값은 모든 노드에서 존재하지 않고 leaf node, 혹은 특정키의 내부노드에만 존재.
Radix tree
공간사용이 최적화된 trie 자료구조를 의미.
만약 특정노드의 자손이 하나만 있다면 그 노드는 자식노드와 결합된다.
때문에 모든 내부노드는 적어도 두개 이상의 자손을 갖는다.
Merkle tree
해시트리라고도 하며 해시값을 트리구조로 구성되는 데이터 구조.
leaf노드부터 해쉬한 값을 가지고 부모노드에서 합쳐서 다시 hash를 만든다.
그렇게 하여 최종적으로 루트 hash가 나온다.
장점은 데이터무결성을 효율적으로 검증이 가능하며 사용 데이터도 적다.
용어 정리
이더리움 패트리샤 트리를 설명하려면 다음 용어를 이해해야한다.
Blank node
비어있는 노드
Leaf node
[key, value] 구조로 되어있고, 실제값이 들어갑니다.
Branch node
17칸 배열로 이루어져있고, 앞의 16칸에는 자식노드를 가리키는 값.
마지막칸은 branch의 value가 들어있다.
Extension node
[key, value] 구조로 되어있으며 key값에는 공통으로 묶여진 키값,
value값에는 branch node를 해쉬한 값이 들어있다.
Nibble
4bit 즉 16진수 숫자를 의미.
key값을 나타내기 위한 단위
HP(Hex-Prefix encoding)
leaf노드인지, extension노드인지 식별
nibble의 개수를 항상 짝수로 유지시켜준다.
0: extension이면서 key값이 nibble의 갯수로 짝수
1: extension이면서 key값이 nibble의 갯수로 홀수
2: leaf면서 key값이 nibble의 갯수로 짝수
3: leaf면서 key값이 nibble의 갯수로 홀수
비어있는 노드
Leaf node
[key, value] 구조로 되어있고, 실제값이 들어갑니다.
Branch node
17칸 배열로 이루어져있고, 앞의 16칸에는 자식노드를 가리키는 값.
마지막칸은 branch의 value가 들어있다.
Extension node
[key, value] 구조로 되어있으며 key값에는 공통으로 묶여진 키값,
value값에는 branch node를 해쉬한 값이 들어있다.
Nibble
4bit 즉 16진수 숫자를 의미.
key값을 나타내기 위한 단위
HP(Hex-Prefix encoding)
leaf노드인지, extension노드인지 식별
nibble의 개수를 항상 짝수로 유지시켜준다.
0: extension이면서 key값이 nibble의 갯수로 짝수
1: extension이면서 key값이 nibble의 갯수로 홀수
2: leaf면서 key값이 nibble의 갯수로 짝수
3: leaf면서 key값이 nibble의 갯수로 홀수
예제 심화
이더리움은 key-value형태(levelDB)로 저장이 된다.
예제1
우리는 ["hello"]를 Trie에 넣어보려고 한다.
그러면 우리는 키는 b'\x01\x01\x02'
["hello"]값을 rlp한 값이 b'\xc6\x85hello'라고 하자.
Trie를 만들어 key값 010102(6 nibbles), value 값 [hello] 넣으면
Trie에서 HP encoding하여 키를 만든다.
최초 1개 노드를 추가하였기 때문에, 해당 노드가 root 노드가 된다.
그리고 leaf 노드이다.
아까 표를 이용하면 nibble의 갯수가 짝수(6개) + leaf노드이기 때문에 2가 붙는다.
Nibble은 홀수로 구성될 수 없다.
왜냐하면 바이트스트림의 최소 단위가 바이트이고, 2개의 Nibble이 1 bytes를 이루기 때문이다.
따라서 2뒤에 0을 붙여 전체 nibble의 갯수를 짝수(8개)로 만들어 준다.
결론은 HP encoding한 값은 20(HP) + 010102(원래 키) = 20010102가 된다.
예제2
우리는 "010102"에 ["hello"] (b'\x01\x01\x02', b'\xc6\x85hello'),
"010103"에 ["hellothere"] (b'\x01\x01\x03', b'\xcb\x8ahellothere')를 추가해본다.
예제1
우리는 ["hello"]를 Trie에 넣어보려고 한다.
그러면 우리는 키는 b'\x01\x01\x02'
["hello"]값을 rlp한 값이 b'\xc6\x85hello'라고 하자.
Trie를 만들어 key값 010102(6 nibbles), value 값 [hello] 넣으면
Trie에서 HP encoding하여 키를 만든다.
최초 1개 노드를 추가하였기 때문에, 해당 노드가 root 노드가 된다.
그리고 leaf 노드이다.
아까 표를 이용하면 nibble의 갯수가 짝수(6개) + leaf노드이기 때문에 2가 붙는다.
Nibble은 홀수로 구성될 수 없다.
왜냐하면 바이트스트림의 최소 단위가 바이트이고, 2개의 Nibble이 1 bytes를 이루기 때문이다.
따라서 2뒤에 0을 붙여 전체 nibble의 갯수를 짝수(8개)로 만들어 준다.
결론은 HP encoding한 값은 20(HP) + 010102(원래 키) = 20010102가 된다.
예제2
우리는 "010102"에 ["hello"] (b'\x01\x01\x02', b'\xc6\x85hello'),
"010103"에 ["hellothere"] (b'\x01\x01\x03', b'\xcb\x8ahellothere')를 추가해본다.
root 노드의 key값은 101010, value는 알수없는 hash값이 들어가있다.
해당 key값은 010102와 010103의 공통key 값은 01010이다.
그리고 공통된 key값이 있기 때문에 extension 노드가 된다.
해당key값은 홀수(5개) + extension노드이기 때문에 HP는 1값이 붙는다.
nibble은 항상 짝수여야 하기 때문에 HP encoding 한 key값은 101010이다.
value값은 extension 노드에서 갈라진 branch 노드의 hash값이다.
즉 이값을 이용하여 DB에 질의하여 branch 노드를 가져올 수 있다.
조회한 branch node를 살펴보면 17자리의 배열이 있는데,
아까 공통된 키 01010을 뺀 2, 3에 대하여 각각의 인덱스가 된다.
["", "", ["", b'\xc6\x85hello'], ["", b'\xcb\x8ahellothere'] ...]
"010102", "010103" 중 공통되지 않는부분 2,3자리에
각각의 value가 들어가있다.
그리하여 index 2에는 ["", ["hello"]] 그리고 3에는 ["", ["hellothere"]]이 위치하게 된다.
branch 노드는 16개의 leaf 노드를 저장할 수 있다.
branch 노드에 값을 저장할 때 leaf 노드의 rlp encoding한 값이 32bytes보다 작으면
값 그대로 저장되며, 32bytes보다 크다면 hash하여 저장된다.
그 해쉬를 key로하여 DB에 값을 저장된다.
예제3
"010102" 에 ["hello"] (b'\x01\x01\x02', b'\xc6\x85hello'),
"0101" 에 ["hellothere"] (b'\x01\x01', b'\xcb\x8ahellothere')를 추가해본다.
예제 2처럼 root 노드는 "0101"에 HP 0를 추가하여 000101"을 key로한 extension 노드가 되며
value값은 branch 노드 해시값을 가지고 있다.
DB에서 branch 노드를 가져와보면 다음과 같다.
[["2", b'\xc6\x85hello'], "", ......, b'\xcb\x8ahellothere']
왜 이런 결과가 나오냐면, 공통key는 0101이다.
남겨진 key는 hello는 2, hellothere는 없다.
따라서 02중 첫번째 값 0을 인덱스로 hello가 들어가고 남은 key값을 기록한다.
hellothere은 남겨진 값이 없으므로 branch 노드의 value가 된다.
예제4
"010102" 에 ["hello"] (b'\x01\x01\x02', b'\xc6\x85hello'),
"01010257" 에 ["hellothere"] (b'\x01\x01\0x2\0x57', b'\xcb\x8ahellothere')를 추가해본다.
예제 2처럼 root 노드는 "010102"에 HP 0을 추가하여 00010102를 key로한 extension node가 되며
value값은 branch 노드 해시값을 가지고 있다.
DB에서 branch 노드를 가져와보면 다음과 같다.
["", "", "", "", "", ["7", b'\xcb\x8ahellothere'], ... , b'\xc6\x85hello']
남겨진 키는 hellothere는 57, hello는 없다.
따라서 57중 첫번째 값 5를 인덱스로 hellothere이 들어가고 남은 key값을 기록한다.
hello는 남겨진 값이 없으므로 branch 노드의 value가 된다.
예제5 (마지막)
"010102" 에 ["hello"] (b'\x01\x01\x02', b'\xc6\x85hello'),
"01010255" 에 ["hellothere"] (b'\x01\x01\0x2\0x55', b'\xcb\x8ahellothere')를 추가해본다.
그 후
"01010257" 에 ["jimbojones"] (b'\x01\x01\0x2\0x57', b'\xcb\x8ajimbojones')를 추가해본다.
예제 2처럼 root 노드는 "010102"에 HP 0을 추가하여 00010102를 key로한 extension 노드가 되며
value값은 branch 노드 해시값을 가지고 있다.
DB에서 branch 노드를 가져와 보면 다음과 같다.
["", "", "", "", "", hash값, ... , b'\xc6\x85hello']
5번 인덱스에는 hellothere, jimbojones도 아니다.
바로 extension 노드가 들어가 있다.
그 extension 노드를 보면 ["5", "hash값]이 들어가 있는데
공통key값 010102에 5에 branch노드를 담겨야 하기 때문에 5를 키값으로 들어가 있다.
이곳에 있는 hash값은 실제값(hellothere, jimbojones)이 들어있는 branch 노드의 해시값이다.
DB에서 해당 branch키값으로 조회를 하면
["", "", "", "", "", ["", b'\xcb\x8ahellothere'], "", ["", b'\xcb\x8ajimbojones'], ...]
5번에는 hellothere, 7번에는 jimbojones값이 들어가 있다.
정리
공통된 키를 가진 root 노드(extension 노드)가 생기면branch 노드가 생겨 leaf 노드를 정해진 index에 넣는다.
그리고 extension 노드가 생기는데
key값은 공통된 key값이 되며 value값은 branch 노드를 해쉬한 값이다.
branch 노드는 leaf 노드뿐만 아니라 extension 노드도 저장될 수 있다.
각 노드의 key값은 HP encodeing하여 타입을 구분하고 key(nibble)을 짝수로 맞춰 bytes로 만든다.
extension 노드나 branch 노드에 있는 해시값은 DB저장에 사용하는 index역할을 한다.
정보를 찾을때는 이 해시값으로 정보를 찾는다.
해당 내용을 가지고 다음 이더리움에서 제공한 표를 참고하면 좋을 듯 하다.
