머클 패트리시아 트리

블록체인의 가장 큰 장점이자 특징은 블록체인의 모든 데이터를 참여자들이 모두 공유한다는 것이다. 그러나 블록체인의 크기가 계속해서 증가한다면 공유를 위해 많은 데이터를 동기화 해야하는 것이 문제이다.

이 문제를 해결하기 위해 머클 트리를 사용했고 이더리움에서는 이를 개선하여 머클 패트리시아 트리라는 암호 해시 기반의 트리 자료구조를 사용한다.

• 트리 내의 모든 정보는 레벨DB에 저장한다.

해시 함수란?

해시 함수는 임의의 크기 값을 입력했을 때 고정 크기 값을 생성해 내는 함수다.

예를들어 “허유명”이라는 글과 “유명한 허유명”이라는 글을 sha256으로 암호화 했을때 들어간 byte값을 다르지만 64바이트 크기의 고정된 문자열 값을 생성해 낸다.

• 이더리움에서는 keccak256 암호 해시를 사용한다.

머클 트리란?

머클 트리는 암호화 함수로 데이터를 해싱한 후 이 결괏값을 다시 암호화 해시하여 상위노드로 만들어진 트리 구조의 데이터이다.

• 공간을 절약하기 위해서 만들어진 데이터 구조(?)이다.

머클 트리는 어떻게 만들어지는가?

첫번째로 구체적인 특정 값들을 해싱한다.

그 해싱한 값들을 합쳐서 다시 해싱한다.

최상위 노드 하나가 남을때까지 위 작업을 반복하면 머클 트리가 생성된다.

1. 바이너리 머클 트리

• 해싱한 값들을 2개씩 쌍으로 축약시켜서 하나로 만든다.

• 거래 데이터를 해싱해서 해시0,1,2,3을 만들고 그걸 또 해쉬하여 루트해쉬까지 만든다.
• 루트 해시만을 가지고 있는 라이트 노드가 특정 거래가 블록에 있는지 확인하려면 순서대로 재계산을 하면 확인할 수 있게 된다.
• 새로운 트랜잭션이 일어나고 상태가 변경될때 바이너리 머클 체인은 상태를 업데이트 시키지 않고 원래 있던 상태를 삭제하고 새로 바뀐 상태를 인서트 한다.

2. 상태전이 머클 트리

• 위 그림을 보면 2개의 블록이 있고 두 블록이 동일한 머클 트리를 공유하고 있다.
• 대신 블록당 트리가 한개씩 있는 것이 아니라 공통된 것은 공유하고 변경 된 것만 추가하여 사용하는 것.

패트리시아 트리란?

위 그림처럼 각 단어 전체를 저장하는 게 아니라 공통되는 부분을 공유하며 저장하는 방식이다. 이렇게 되면 데이터를 굉장히 많이 절약할 수 있게됨

머클 페트리시아 트리란?

위 그림과 같이 구성된 구조 형태이다.

이더리움 내에서 노드는 위 그림과 같이 key, value 형태로 저장이 된다.

• key = value의 hash값, 레벨DB에서 특정 노드를 검색할때 사용됨
• value = 17개 요소로 구성됨.첫 16개의 요소는 hex(16진수)값을 나타내고 마지막 17번째 요소에 노드가 가지고 있는 데이터가 저장되어있음. 트리에서 데이터를 찾는데 사용된다.

아래와 같은 key, value 데이터를 가지고있다고 하자.

{
  'cab8': 'dog',
  'cabe': 'cat',
  '39': 'chicken',
  '395': 'duck',
  '56f0': 'horse'
}

비효율적인 트리

위 트리에서 395에 해당하는 key값을 찾는 과정을 알아보자.

1. 키값 395는 3,9,5 로 분리되어 순서대로 사용된다.
2. rootHash에서 첫번째 패스인 3에 해당하는 hashA를 검색한다.
3. DB에서 hashA를 검색한후 두번째 패스인 9 인자를 검색해서 hashC를 검색한다.
4. DB에서 hashC를 검색한 후 마지막 패스인 5를 검색해서 hashD를 찾는다.
5. hashD의 value가 duck인 것을 확인한다.

이런 과정으로 395의 value 값을 찾는다.

위 과정으로 value를 검색할때 노드들이 많은 null 값을 가져서 메모리가 낭비되고 있다.

이걸 한 단계 업글시켜서 데이터의 끝까지 분기되는 경로가 없을 경우 노드 하나에 나머지 경로를 할당해서 null값을 줄이는 방법이 있다.

56f0경로를 예로 보자.

첫번째 패스인 5에 ****할당하는 hashE부터 6f0패스 끝 노드까지 빈값을 거쳐간다.

이를 6f0패스 단하나로 통일하여 기존 16개 값을 저장하는 노드에 나머지 경로 6f0만 할당하는 것이다.

아래 이미지를 참조하자.

세번째 패스까지는 겹치는 cab8, cabe는 겹치는 경로를 하나로 정의해서 데이터를 절약할 수 있다.

아래 이미지를 보면

1. 첫번째 패스인 c를 찾아 hashB를 찾는다.
2. hashB의 패스 전체를 ab로 정의하고 value값으로 hashJ를 갖는다.
3. hashJ를 검색하여 그곳에서 각자의 라스트 패스를 따라간다.

순서로 진행되는걸 알 수 있다.

나머지 노드들도 위에 나온 방법들로 정리하면 최적화된 메모리 저장 구조를 만들 수 있다.

마지막으로 HP인코딩을 통하여 리프노드와 확장노드에 prefix를 붙이게 된다.

HP인코딩까지 마친 최종 머클 패트리시아 트리는 아래와 같다.