이더리움 논문 리뷰 03 머클 트리 (해시 트리, Merkle Trees)

안녕하세요. 이번 글에서는 이더리움을 본격적으로 설명하기에 앞서 논문의 서론 부분 중 "머클 트리 (해시 트리, Merkle Trees)" 섹션을 공부해보겠습니다. 컴퓨터 자료 구조 및 알고리즘(Data Structures and Algorithms)에 대한 배경 지식이 있으신 분들은 이미 친숙한 개념이거나 쉽게 이해할 수 있을 것 같습니다.

 

이전 글
비트코인 논문 리뷰
이더리움 논문 리뷰 01 Bitcoin As A State Transition System  
이더리움 논문 리뷰 02 채굴 (마이닝, Mining)

다음 글
이더리움 논문 리뷰 04 스크립팅, 스마트 계약 (Scripting, Smart Contracts)

블록체인 네트워크에서 블록 데이터를 보다 효율적으로 관리하고 저장하기 위해 "머클 트리"라는 구조를 사용합니다. 머클 트리는 바이너리 트리(Binary Tree)의 한 종류입니다. 가장 하위 단계에 있는 leaf node들에 실제 데이터가 저장이 되며, 나머지 상위 노드들(non-leaf nodes)에는 각 노드의 children 노드에 대한 해시 값이 저장됩니다.

 

출처: 위키피디아 "해시 트리", 가장 하위 레벨의 Leaf nodes (L1, L2, L3, L4)에 블록 데이터가 저장. 상위 노드에는 children 노드의 해시 값이 저장.

 

블록 데이터를 머클 트리에 저장하는 것은 여러 부분에서 효율적입니다. 예를 들어, 블록체인을 공유하고 있는 각 컴퓨터 (사용자, 혹은 노드, 머클 트리에서의 노드와 다름)는 많은 거래 내역들을 포함하고 있는 블록 데이터 전체를 로컬에 다운로드할 필요 없이, 최소한의 "블록 헤더 (블록 해시)"만 다운로드함으로써 로컬 메모리 공간의 제약 없이 효율적으로 데이터를 저장할 수 있게 됩니다. 참고로 하나의 블록 헤더를 저장하기 위해서는 약 200 바이트면 충분하다고 논문에서 언급하고 있습니다.

 

더 나아가 어떤 두 블록의 데이터가 동일한지 비교를 하는 과정에서도 간단히 가장 상위 노드(root node)를 비교하면 되기 때문에 연산이 아주 간단해집니다. 예를 들어, 어떤 해커가 블록의 일부 거래 내역을 조작했다고 가정해 봅시다. 그러면 조작된 거래 내역이 포함된 leaf node의 해시 값이 달라질 것이고, 이 leaf node와 연결된 모든 상위 노드들의 해시 값들이 달라지게 됩니다. 결국은 가장 상위의 root node의 해시 값도 영향을 받게 되고, 블록 전체의 블록 해시 값이 바뀌게 됩니다. 

 

비트코인 논문의 섹션 7에 삽입된 그림. 한 블록의 데이터가 머클 트리의 구조로 저장된 모습.

 

레퍼런스
- 위키피디아, "해시 트리" https://ko.wikipedia.org/wiki/해시_트리
- https://rose.telecom-paristech.fr/2013/04/03/whats-a-hash-tree
-Satoshi Nakamoto, "Bitcoin: A Peer-to-Peer Electronic Cash System", URL: https://bitcoin.org/bitcoin.pdf (2008).