머클 패트리샤 트리 이해하기
머클 패트리샤트리는 이더리움에서 사용하는 수정된 머클트리이며 효율적으로 정보를 관리하기 위한 자료구조입니다. 각각의 노드들은 [key, value] 값을 갖고 있고 이웃 노드와 함께 상위 노드의 해쉬값으로 올려지게 됩니다. 반복된 과정을 거치면 최상위 노드(root node)에 이르게 되고 나무와 같은 구조를 갖습니다. 이 노드의 해쉬값을 root hash이라고 합니다.
1. 머클 패트리샤 트리를 왜 사용할까?
머클 패트리샤 트리의 개념만으로는 어떤 역할을 하는 지 짐작하기 쉽지 않습니다. 블록은 이미 거래 기록을 담고 있습니다. 전파받거나 채굴한 블록에서 거래 기록을 찾으면 될 것을 왜 굳이 기존 정보를 나무 구조로 만들고 해쉬하는 걸까요?
머클 패트리샤 트리를 쓰는 이유는
1) 정보를 효율적으로 저장, 수정, 삭제, 검색 등을 할 수 있습니다. 머클 패트리샤 트리는 공통의 키 값을 따라 저장하고 그 안에서 수정, 삭제, 검색을 합니다. 정보를 저장할 때는 키값에 따라 저장하고 중복저장을 하지 않아 공간이 절약됩니다. 세부적으로는 일정 바이트를 초과하면 해싱도 합니다. 또한 전체 정보를 뒤질 필요 없이 연결된 키 값들(path)을 따라 수정,삭제,검색을 하니 처리속도도 빨라집니다.
2) 거래 정보를 검증할 수 있습니다. 해쉬함수로 인해 노드의 값이 달라지면 상위노드의 해쉬값이 달라지고 root 값도 완전히 달라집니다. 이로 인해 full node는 새로운 거래 정보를 효율적으로 검증할 수 있고, 블록헤더만 가지고 있는 light node도 root 값을 통해 거래 정보를 검증할 수 있습니다. 머클 트리가 없다면 light node는 거래 정보를 검증할 방법이 없습니다.
그래서 머클 패트리샤 트리는 이더리움의 코어 프로토콜 이외에도 이더리움 스케일링 솔루션인 샤딩, 플라즈마 등 블록체인 기술 전반에 널리 쓰이고 있습니다.
2. 머클 패트리샤 트리의 유형
이더리움의 머클 패트리샤 트리는 총 4종류이며 State Trie, Storage Trie, Transactions Trie, Receipts Trie입니다.
State Trie
State 정보가 담겨 있습니다. 여기서 key 값(path)은 항상 sha3(ethereumAddress) 이고 value 값은 항상 rlp(ethereumAccount) 이 됩니다. value 값에 쓰인 ethereumAccount은 [nonce, balance, storageRoot, codeHash] 인 배열입니다.
Storage Trie
컨트렉트 계정의 storage 정보가 담겨 있습니다. ethereumAccount 배열 안에 storageRoot에 root 값이 들어갑니다. key 값(path)은 약간의 계산 과정을 거칩니다.
https://github.com/ethereum/wiki/wiki/JSON-RPC#eth_getstorageat에 보다 상세한 설명이 있습니다.
Transactions Trie
거래 정보가 담겨 있습니다. key 값(path)은 rlp(transactionIndex) 가 되는데 transactionIndex는 블록안에 거래의 index 값입니다. 블록이 채굴된 후에는 바뀌지 않습니다.
Receipts Trie
부가적인 거래 정보 (누적 가스 사용량, 로그등) 가 담겨 있습니다. key 값(path)은 rlp(transactionIndex) 가 됩니다. 블록이 채굴된 후에는 바뀌지 않습니다.
3. 머클 패트리샤 트리의 주요 용어
1) Node
- Blank node
비어있는 노드입니다.
- Leaf node
[key,value] 구조로 되어 있으며 각각의 거래 정보를 구성하고 있습니다.
- Branch node
17칸의 배열로 이루어져 있습니다. 앞의 16칸에는 자식 노드를 가리키는 값이 들어있습니다. 마지막 칸에는 branch node의 value 값이 들어있습니다. 이더리움의 머클 패트리샤 트리는 비트코인의 머클트리(두 개의 하위 노드를 갖는)와 달리 한번에 17개의 값을 저장 할 수 있는 branch node를 추가하여 효율성을 높였습니다.
- Extension node
[key,value] 구조로 되어 있으며 key값에는 공통으로 묶여진 키값, value 값에는 branch node를 해쉬한 값이 들어 있습니다.
2) Hex-Prefix encoding(HP encoding)
- Nibble: 4 bit, 즉 반 byte를 뜻합니다. 1 nibble은 16진수 숫자 하나입니다. Nibble은
key 값을 나타내기 위한 단위입니다.
HP encoding은 hex 값을 키값앞에 붙여서 leaf node인지 extension node인지 식별하는 목적으로 쓰입니다. HP encoding은 키값의 nibble의 개수를 항상 짝수로 맞춰 바이트(8bits)를 만듭니다.
hex char bits | node type partial path length
----------------------------------------------------------
0 0000 | extension even
1 0001 | extension odd
2 0010 | terminating (leaf) even
3 0011 | terminating (leaf) odd0: extension node 이면서 key 값이 nibble의 갯수로 따졌을 때 짝수인 경우
1: extension node 이면서 key 값이 nibble의 갯수로 따졌을 때 홀수인 경우
2: leaf node 이면서 key 값이 nibble의 갯수로 따졌을 때 짝수인 경우
3: leaf node 이면서 nibble의 갯수로 따졌을 때 홀수인 경우
4. 코드 example
머클 패트리샤 트리가 어떻게 동작하는 지 이해하기 위해서 간단한 py 파일 코드 예제를 살펴보겠습니다. 설명을 위해 편의상 각 예제마다 하나의 파일을 만들겠습니다.
첫번째는 ex1.py 를 가정하고 간단한 스크립트를 짜보겠습니다.
1) Trie 클래스를 불러와 BLANK_ROOT로 초기화하고 state 변수에 담습니다.
2) Key 값 010102, value 값 hello 인 노드를 추가합니다.
3) Root hash 값을 출력합니다.
4) Root node의 key 값을 k, value 값을 v에 담습니다.
5) Root node를 출력합니다.
6) HP encoding 한 key 값을 출력합니다.
Output 을 보면
1) Root hash의 출력값입니다.
2) Root node의 출력값입니다.
3) HP encoding 한 key 값입니다.
ex1.py 를 보면 트리를 만들어 key 값 010102(6 nibbles), value 값 hello 를 넣었습니다. Output을 보면 root hash, root node, HP encoding 한 키가 나옵니다.
HP encoding한 키는 본래 키 010102 앞에 20이 더 붙어있습니다. 이 때, 2와 0을 붙이는 이유는 두 가지 때문입니다.
1) 추가된 node가 한 개이기 때문에 그 노드가 root node입니다. 그리고 leaf node입니다. 이 때 nibble의 개수가 짝수(6개)이기 때문에 2를 붙입니다.
2) Nibble은 홀수로 구성될 수 없습니다. 바이트 스트림은 최소 단위가 바이트고, 두 개의 Nibble이 1바이트를 이루기 때문입니다. 따라서 2 뒤에 0을 붙여서 전체 nibble의 개수를 짝수(8개)로 만들어 줍니다.
최종적으로 HP encoding 한 키값은 20(Hex-Prefix) + 010102(본래 키) = 20010102 가 됩니다.
또다른 스크립트 파일 ex2.py를 가정해보겠습니다. 이 예제는 value 값이 바뀜에 따라 root hash 값이 바뀌게 되는 예제입니다. 우선, ex1.py에서 만들었던 트리를 그대로 가져오겠습니다.
1) ex1.py에서 생긴 root hash값을 hex decoding해서 ex.1py의 트리와 동일한 트리를 만듭니다.
2) root node를 출력합니다.
이렇게 하면 ex1.py에서 만들었던 동일한 트리를 가져옵니다. 현재 [010102, hello] 노드가 있습니다. 여기서 value 값을 바꿔보겠습니다.
1) Key 값 010102, value 값 hellothere 를 넣습니다.
2) Root hash 값을 출력합니다.
3) Root node를 출력합니다.
Output은 다음과 같습니다.
1) Root hash의 출력값입니다.
2) Root node의 출력값입니다.
이전 root hash 값은 15da97c42b7ed2e1c0c8dab6a6d7e3d9dc0a75580bbc4f1f29c33996d1415dcc,
현재 root hash 값은 05e13d8be09601998499c89846ec5f3101a1ca09373a5f0b74021261af85d396 입니다.
이와 같이, value 값이 바뀌면 root 값은 완전히 바뀝니다.
다시 ex2.py 파일을 만든 것처럼 ex1.py에서 만든 트리를 ex2b.py 라는 파일에 동일하게 만들어 보겠습니다. 노드를 추가하여 branch node와 extension node가 만들어 지는 예제입니다.
1) Key 값 010103, value 값 hellothere 를 가진 노드를 추가합니다.
2) Root hash 값을 출력합니다.
3) 변수 k에 root node의 key 값, 변수 v에 root node의 value 값을 담습니다.
4) Root node를 출력합니다.
5) HP encoding한 key 값을 출력합니다.
Output 입니다.
1) Root hash의 출력값입니다.
2) Root node의 출력값입니다.
3) HP encoding의 출력값입니다.
Output을 보면 root node의 키 값은 101010, value 값은 암호와 같은 문자들이 있습니다. 두 노드( [010102, hello], [010103, hellothere] )의 공통된 키 값은 01010입니다. 노드는 extension node이고 공통된 키 값은 홀수이기 때문에 공통된 키 값앞에 1만 붙습니다. 즉, HP encoding 한 키값은 1(Hex-Prefix) + 01010(본래 키) = 101010 이 됩니다.
Value 값은 두 노드의 해쉬값인데 상세한 설명은 뒤에 하겠습니다.
1) Root node의 노드 타입이 extension node인지 확인하는 boolean 값을 출력합니다.
2) Root node의 key 값, value 값을 변수에 담습니다.
3) Root node의 value 값(node_hash)을 통해 local DB에서 노드의 정보를 가져오고 출력합니다.
4) Node_hash를 통해 가져온 노드 타입이 branch node 인지 확인하는 boolean 값을 출력합니다.
Output을 보겠습니다.
1) Extension node가 맞다는 True를 출력합니다.
2) Branch node의 출력값입니다.
3) Branch node가 맞다는 True를 출력합니다.
종합하면 두 개의 노드(Extension node, Branch node)가 생겼습니다. 이 extension 노드의 value 값에 branch node의 해쉬값이 있습니다. 이 해쉬값은 branch node를 가리키는 값입니다. 이 해쉬값을 통해 branch node를 local DB에 저장하고 불러옵니다.
branch node의 내용을 보면 노드들이 저장되어 있습니다. 아까 공통된 키는 01010 이었습니다. Hello의 키 값은 010102, hellothere의 키 값은 010103 이니 공통된 키 값을 제외하고 남은 키는 hello의 경우 2, hellothere의 경우 3이 됩니다. 이 값이 branch node의 index 값으로 들어가고 남은 키는 지워져서 빈칸(‘ ’)만 남게 됩니다.
Branch node는 16개의 leaf node를 저장할 수 있습니다. Branch node는 17개의 칸이 있는데 마지막 17번째에는 branch node의 value 값이 들어갑니다. Branch node에 값을 저장할 때 leaf node의 rlp encoding한 값이 32bytes 보다 작으면 위 output과 같이 그대로 저장됩니다. 만약 32bytes 보다 크면 해싱하여 저장합니다.
이번에는 ex2c.py 파일을 만들겠습니다. Branch node에 어떻게 노드가 저장되는지 알아보겠습니다. ex2.py 파일을 처음 만들었을 때처럼 ex1.py의 root 값을 가진 트리가 만들어집니다. 여기에 노드를 하나 추가 하겠습니다.
그러면 [010102, hello] 노드와 [0101, hellothere] 노드가 있으니 extension node 와 branch node 가 생길 겁니다. branch node를 보죠.
왜 이런 결과가 나올까요? 공통키는 0101 입니다. 남겨진 키는 hello는 02, hellothere는 없습니다. 그러므로 hello는 첫 번째 0이 branch node에서 hello 의 인덱스값이 되고 남은 2가 그 위치에 기록됩니다. Hellothere는 남겨진 값이 없으니 branch node의 value 값, 즉 17번째 칸에 들어가게 되는 거죠.
이번에는 ex2d.py 파일을 만들어 보겠습니다.
그러면 branch node는 다음과 같이 됩니다.
공통된 키는 010102 가되고 hellothere는 남은키 57, hello는 없습니다. 그래서 hellothere는 branch node의 5번째 인덱스, hello는 17번째에 들어가게 됩니다.
마지막으로 보다 복잡한 구조를 살펴보겠습니다. ex3.py를 만들어 보겠습니다. 노드를 추가했을 때 extension node와 branch node가 각각 2개씩 생기는 예제입니다.
1) Root hash 값을 가진 트리를 만듭니다. ex1.py에서 만들었던 것과 동일한 트리입니다.
2) Root hash 값을 출력합니다.
3) Root node를 출력합니다.
4) 공백을 출력합니다.
5) Key 값 01010255, value 값 hellothere 인 노드를 추가합니다.
6) Root hash 값을 출력합니다.
7) Root node를 출력합니다.
8) Branch node를 출력합니다. (state.root_node는 [key,value] 형식을 가진 extension node 입니다. 따라서 state.root_node[1] 는 value 값이 됩니다. 즉 branch node 입니다.)
9) 공백을 출력합니다.
아직까지는 이전 예제와 다를 것이 없습니다. 기존에 있는 hello 값을 갖고 있는 노드에 hellothere 값을 갖고 있는 노드를 추가했을 뿐입니다. 이번엔 다른 노드를 추가해 보겠습니다.
1) Key 값 01010257, value 값 jimbojones 인 노드를 추가합니다.
2) Root hash 를 출력합니다.
3) Root node 를 출력합니다.
4) Branch node 를 변수에 담습니다. (여기서 root node는 extension node로 [key, value]로 구성되어있습니다. state.root_node[1]이라는 것은 즉 value를 가리킵니다.)
5) Branch node를 출력합니다.
이렇게 하면 어떻게 될까요? 아시다시피 branch node의 5번 인덱스에는 hellothere가 담겨 있습니다. 하지만 jimbojones 도 5번에 들어가야 합니다.
1) Branch node의 index 5번(배열은 0부터 시작하므로 6번째 칸입니다.)을 next_hash 변수에 담습니다.
2) Next_hash 변수를 출력합니다.
3) 이 노드는 extension node입니다. _decode_to_node라는 함수는 이 노드의 value 값인 branch node를 출력합니다.
Output을 보겠습니다.
- key 값 01010255, value 값 hellothere 인 노드를 추가한 경우
1) Root hash의 출력값입니다.
2) Root node의 출력값입니다.
3) Branch node의 출력값입니다.
2. key 값 01010257, value 값 jimbojones 인 노드를 추가한 경우
1) Root hash의 출력값입니다.
2) Root node의 출력값입니다.
3) Branch node의 출력값입니다.
4) 다음 branch node의 해쉬값입니다.
5) 다음 branch node의 출력값입니다.
Branch node의 5번 인덱스에는 hellothere 도 jimbojones 도 담겨있지 않습니다. 어떤게 담겨 있는 걸까요? 바로 extension node가 담겨 있습니다. extension node의 path값은 0101025, key 값은 5 가 되고 value 값은 해쉬값입니다. 이 해쉬값은 무얼 가리킬까요? 바로 또다른 branch node 입니다! 그 branch node에 hellothere, jimbojones가 담겨있습니다.
수고하셨습니다! 지금까지 한것을 간단히 정리하면 공통된 키를 가진 Root node(extension node)가 생기면 branch node가 생겨 leaf node를 정해진 index에 따라 저장합니다. 그리고 extension node가 생기는데 여기서의 key 값은 공통된 키값이 되며 value 값은 branch node를 해쉬한 값입니다. 또한 branch node에는 leaf node 뿐만 아니라 다른 extension node도 저장될 수 있습니다.
각 node들의 키 값은 HP encoding하여 타입을 구분하고 키 값(nibble)을 짝수로 맞추어 바이트를 만듭니다.
Extension node나 branch node에 있는 해쉬값은 local DB에 저장할 때 쓰이는 index 역할을 합니다. 정보를 찾아올 때 이 해쉬값으로 정보를 찾아 올 수 있습니다.
코드 예제는 https://easythereentropy.wordpress.com/2014/06/04/understanding-the-ethereum-trie/ 의 포스팅 글에 있는 예제를 인용하였습니다.
참고 자료
https://easythereentropy.wordpress.com/2014/06/04/understanding-the-ethereum-trie/
