머클 트리(Merkle tree)

 

머클 트리는 대규모 데이터를 효율적으로 요약하고 검증하는 이진 트리 기반의 데이터 구조로, 블록 안에 저장된 거래 모두에 대해 디지털 지문을 만들어서 어떤 거래가 블록에 저장되어 있는지 검색할 수 있도록 해준다.

 

머클 트리를 만드는 방법?

이진 트리에 포함된 잎 노드 쌍을 연결하고, 이에 대한 해시값을 계산(SHA-256 이중 해시)하는 과정을 해시값이 하나가 될 때까지 재귀적으로 반복하면 된다. 이 과정을 거쳐 마지막에 남은 해시값이 블록 헤더의 머클 루트(Merkle Root)이다.

 

먼저 [그림 1]과 같이 각 거래의 해시값을 모은다. 예를 들면 거래 A의 해시값은 HA이다. 그 다음, 인접한 잎 노드의 해시값과 연결된 해시값을 가져와서 새로운 노드를 생성한다. 이런 과정을 반복하며 마지막에 남는 노드가 머클 루트이며 그림에서 HABCD가 된다.

그림 1. 머클 트리를 구축하는 과정

머클 트리는 이진 트리이므로 거래 수가 짝수

만약 거래 수가 홀수라면 거래를 하나 복제하여 짝수로 만들면 된다 .

[그림 1.]에서 거래 Tx D가 없는 경유를 예로 들면 [그림 1]과 같이 거래 D자리를 거래 C로 바꾸는 것과 같다.

 

 

이상포스터를 마치겠습니다.