머클 트리, 머클 경로 (= 해시 트리)

 

머클트리란 (= 해시 트리)

https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%8A%B8%EB%A6%AC

해시 트리 - 위키백과, 우리 모두의 백과사전

 

• 블록에 포함된 거래 내역의 hash값이 leaf이고, 이를 두 쌍씩 짝지어 다시 hash한게 부모 node가 되는 과정을 반복하여 완성된 이진트리.

 

블록체인에서 활용

http://wiki.hash.kr/index.php/%EB%A8%B8%ED%81%B4%ED%8A%B8%EB%A6%AC

 

• 머클트리를 이용하면 "블록에 특정 거래가 포함되어 있는지를 빠르게 검증" 할 수 있다. (블록 내에서 특정 거래의 위치를 빠르게 찾는게 아니다. 이렇게는 이용 할 수 없다.)
  • 머클경로 참고.
  • 트리 구조가 아니라 전체 거래들을 통째로 hash한 값을 root로 가지고 있다면, 검증을 위해 전체 거래들을 다 가져와야 한다.
  • 반면 머클트리 구조라면 (Hash2, Hash10, Hash14)만 알아도 Merkle Root를 계산 할 수 있어 빠른 검증이 가능하다.

• 특정 거래가 주어졌을 때, 머클트리를 이용해 블록 내에서 그 거래가 어디에 위치해있는지를 빠르게 찾는 것은 불가능하다. 
  • 주어진 input은 찾고자 하는 tx의 hash 일텐데, 특정 거래 빨리 찾는다는건 이진 탐색을 한다는거고, 이진 탐색을 하려면 left, right의 대소 비교가 의미있어야 하는데, 각 node가 hash로 구성된 이상 대소비교가 의미가 없다.
  • hash값 2개를 합쳐서 다시 hash한게 parent가 되는 방식으로 만들어가는 tree인데, 이 때 parent에 해당하는 hash가 어떤 값이 나올지는 알 수 없다. 따라서 이진 탐색이 가능하게끔 트리를 구성하는게 불가능하다.

 

분산 저장소 - 영구 장애 노드 처리에서 활용

• https://docs.datastax.com/en/dse/5.1/dse-arch/datastax_enterprise/dbArch/archAntiEntropyRepair.html
• anti-entropy 프로토콜은 사본들을 비교하여 최신 버전으로 갱신하는 과정을 포함하는데, 이 때 사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해 머클 트리를 활용한다.

• 두 머클 트리를 루트에서부터 비교해나간다. 루트가 다르므로 왼쪽 오른쪽 비교해보고, 그 아래도 왼쪽 오른쪽 비교해봐서 다른쪽을 따라가면 최종적으로 망가진 데이터가 어디에 위치해있는지 찾을 수 있다.