머클 패트리시아 트리

머클 패트리시아 트리를 이해하기 위해서 여러 책과 인터넷의 여러 포스팅을 찾아보았지만, 여전히 구름속에 있는 것처럼 쉽게 와닿지가 않았습니다.  이번 포스팅에서 참고로한 포스팅을 통해서 머클 패트리사의 트리의 구조가 어느정도 개념적으로 머리속에 그려지는것같아서 해당 포스팅을 참고로 머클패트리시아 트리의 개념을 정리해 보고자 합니다.

다음글은 아래의 포스팅을 참고로 하여 정리하였습니다.

Data structure in Ethereum. Episode 3: Patricia trie.

이더리움의 데이타는 머클 패트리시아 트리의 형태로 저장이 되며, 머클 패트리시아 트리는 기수(Radix)트리와 머클(Merkle)트리를 혼합하여 최적화한 트리입니다.

따라서 머클 패트리시아 트리를 이해하기 위해서는 먼저 기수트리와 머클트리의 이해가 필요합니다.

1. 기수트리(Radix trie)

먼저 다음과 같이 key:value를 가지는 데이타를 가지고 기수트리를 표현하도록 하겠습니다.

{

  do: 0,

  dog: 1,

  dax: 2,

  dogu: 3,

  dodo: 4,

  house: 5,

  houses: 6

}

위의 데이타는 기본적인 기수트리로 다음과 같이 표현할수 있습니다.

위의 예에서 dodo란 키를 통해서 값 4를 확인할수 있습니다. 하지만 위와같은 기본 기수트리로는 houses 키를 통해서 값 6을 표현하기 위해서 null 노드가 너무많이 존재하여 공간을 낭비하게 됩니다. 따라서 이러한 공간낭비를 줄이기 위해 다음과 같은 형태로 기수트리가 표현됩니다. 아래와 같이 표현할경우 houses를 표현할때 null 노드가 존재하기 않기 떄문에 공간낭비가 없어지게 됩니다. 이와같이 중간에 분기가 없는 키(경로)를 하나의 키로 합쳐서 사용하는것이 최적화 패트리시아 트리의 기본이라고 할수 있습니다.

2. 머클트리(Merkle trie)

머클트리는 데이타를 검증하는데 사용됩니다. 가장 하위노드를 해쉬하여 상위노드로 전달하고 상위노드는 하위 2개노드의 해쉬값을 더하여 다시 해쉬한후 상위로 전달합니다. 이와같은 과정을 root에 도달할때까지 진행하여 root hash를 생성합니다. 이 과정은 다음과 같이 표현할수 있습니다.

머클트리의 모든 데이타는 가장 하위의 리프노드에 저장됩니다. 만약 4번 노드의 값을 44로 변경할 경우 다음과 같이 상위노드가 모드 변경되어 root까지 업데이트가 됩니다. 따라서 root hash 값과의 비교를 통해 특정 리프노드의 값이 변경되었는지 확인을 하는데 머클트리가 사용됩니다.

3. 패트리시아 트리

패트리시아 트리를 설명하기 위해서 먼저 최적화되지않은 패트리시아 트리를 먼저 설명하고, 순서대로 최적화 과정을 통해 최종적으로 최적화된 패트리시아 트리를 구성하는 방식으로 설명을 하도록 하겠습니다.

먼저 다음과 같은 key, value 데이타를 가지고 패트리시아 트리를 구성하도록 하겠습니다.

{

  'cab8': 'dog',

  'cabe': 'cat',

  '39': 'chicken',

  '395': 'duck',

  '56f0': 'horse'

}

각 노드는 다음과 같이 표현됩니다.

이더리움에서 노드는 위와같이 key-value의 형태로 저장이 되며, key는 value의 hash 값으로 이루어져 있습니다. value는 17개의 요소로 구성되며 첫 16개의 요소는 위의 그림과 같이 hex 값을 나타내고 마지막 17번째 요소에 노드가 가지고 있는 데이타가 저장되어 있습니다. key값에 해당하는 hash 값은 "database lookup" 에 사용되는데, 이는 레벨DB로 저장되어 있는 데이타베이스에서 특정 노드를 검색하는데 사용됩니다. value는 "tree lookup"에 사용되며, 이는 기수트리에서 패스를 통해 데이타를 찾는데 사용됩니다.

이와같은 기본정보를 가지고 위에서 정의한 데이타셋의 사용하여 먼저 비효율적인 패트리시아 트리를 구성해보도록 하겠습니다.

위의 패트리시아 트리를 가지고 데이타셋에 포함되어있는 395 키에 해당하는 값을 찾는 과정을 알아보겠습니다.

이 과정은 레벨DB에서 해당노드를 검색하는 과정(TDL : Database Lookup)과 기수트리에서 검색하는 과정(TTL : Trie Lookup)으로 나눌수 있습니다.

1. 키값 395는 패스로 3,9,5 로 분리를 하여 순서대로 패스에 사용합니다.

2. rootHash에서 패스에 해당되는 연관된 rootNode를 레벨DB에서 검색합니다. (TDL)

3. rootHash에서 첫번째 경로인 3에 해당하는 값 hashA 를 검색합니다. (TTL)

4. DB에서 hashA를 검색한후에(TDL), hashA의 9번째 인자를 검색하여 hashC임을 확인합니다. (TTL)

5. DB에서 hashC를 검색한후에(TDL), hashC의 5번째 인자를 검색하여 hashD임을 확인합니다. (TTL)

5. 이 단계에서 검색경로(395)가 종료되기 떄문에 이떄 hashD 의 값이 최종 값이며, 이는 "duck"임을 알수 있습니다.

이과정에서 value를 찾기위한 경로는 기수트리(Radix trie)가 사용되고, 트리의 각 노드에서 특정 노드의 value 가 변경되면 머클트리의 특성에 따라 rootHash가 변경됩니다.

위의 과정에서 사용되는 트리는 각 노드에서 많은 null 값을 가져 많은 메모리 낭비를 발생시키고 있습니다.

그럼 이와같은 메모리 낭비를 개선하기 위해 다음과 같이 변경을 하도록 하겠습니다.

먼저 각각의 노드를 리프(leaf) 노드와 확장(extension) 노드로 구분을 합니다.

데이타의 끝까지 분기되는 경로가 없는 56f0 경로의 경우, 많은 null 노드로 인해 데이타 낭비가 발생하게 되는데, 이와같은 경우에 리프노드를 정의하여 메모리 낭비를 개선할수 있습니다. 56f0의 경우에는 데이타의 끝까지 분기되는 경로가 없기때문에 최초 rootHash에서 5에 해당하는 hashE를 검색하여 hashE를 찾은후 hashE에 나머지경로 6f0을 할당하고, 리프노드로 정의하고 데이타를 할당하여 메모리를 절약할수 있습니다. 즉 기존에 16개의 값을 저장하는 공간을 하나의 값만 저장하는 공간으로 변경하여 메모리를 줄이게 되는 것입니다. 이는 처음에 기수트리에서 메모리 낭비를 없애기 위해 분기가 발생하지않는 이어진 경로를 하나로 합쳐서 메모리를 절약하는 방법에 해당합니다.

중간에 분기되는 경로가 있는 cab8, cabe는 확장노드를 정의하여 메모리를 절약할수 있습니다.

첫번째 경로 "c" 에서 hashB를 찾고, hashB는 확장노드로 정의하고, value의 경로는 ab로 정의하고, 데이타는 hashJ로 정의합니다.

hashJ에서는 경로 "8"과 "e"를 통해 hashK와 hashL 를 알게되고, 각각의 리프노드인 hashK와 hashL의 값인 "dog", "cat"을 찾을수 있습니다.

이와같이 나머지 리프노드를 모두 재정의하여 다음과 같이 최적화된 메모리 구조를 구성할수 있습니다.

마지막으로 패트리시아 트리에서는 리프노드와 확장노드에 prefix를 붙이는 HP 엔코딩을 하여 각각 리프노드와 확장노드를 구분할수 있도록 하였습니다.

prefix는 다음과 같이 4가지 형태로 정의합니다.

Prefix	노드타입	경로길이
0	확장노드	짝수
1	확장노드	홀수
2	리프노드	짝수
3	리프노드	홀수

이와같이 HP 엔코딩을 하여 확장노드와 리프노드에 prefix를 추가한 최종 패트리시아 트리는 다음과 같습니다.

이와같은 구조를 도식화한 예는 다음과 같습니다.

하기의 예에서 "Simplified World State"의 테이블이 위 예에서의 데이타셋에 해당하는 경로와 데이타에 해당합니다.