[비트코인 구조] 머클 트리(Merkle Tree)

미리 알아야 할 내용들

---

[비트코인 구조] 비트코인 블록 기본 규칙

[비트코인 기본 구조] 6. 머클트리와 SPV(Merkle Tree & SPV)

[비트코인 구조] 빅 엔디안(Big endian)과 리틀 엔디안(Little endian)

[비트코인 구조] 비트코인 해시 함수(sha-256, hash256, hash160)

---

머클 트리(Merkle Tree)

 

 비트코인 블록 상에는 머클 루트가 존재합니다. 여기서의 머클 루트란 트랜잭션이 이루는 머클 트리의 최상위 부모 노드(루트)입니다. 머클 루트를 구하기 위해서 먼저 머클 트리가 어떻게 구성되는지 살펴보겠습니다.

 

 기본적인 머클 트리는 다음과 같이 구성되어 있습니다.

 

 

 최하단 자식 노드인 잎 노드(leaf node)는 트랜잭션으로 구성됩니다. 그리고 모든 부모 노드는 자식 노드의 해시값으로 구성됩니다. 트랜잭션의 부모 노드를 제외한 모든 부모 노드는 자식 노드를 두 개씩 가져야 합니다. 만약 트랜잭션이 홀수개일 경우 머클 트리는 다음과 같이 구성할 수 있습니다.

 

 

 부모 노드는 자식 노드가 홀수개일 경우 자식 노드를 복제하여 사용합니다.

 

 

 지금부터는 실제 머클 트리를 구해보고 여기에서 얻은 머클 루트를 블록 헤더에 있는 머클 루트 값과 비교해보겠습니다. 머클 트리를 구하기 위해 아래 블록을 사용하겠습니다.

 

Blockchain.com Explorer | BCH | ETH | BCH

 

 위 블록은 총 3개의 트랜잭션으로 구성되어 있습니다. 각 트랜잭션의 리틀 엔디안 해시값(hash256)은 다음과 같습니다.

 

 트랜잭션 0(리틀 엔디안): 3fe4847985f3b66472e104214575421f2e2969f47cbbbe8ac02c5e9fc5cc4ad1

 트랜잭션 1(리틀 엔디안): f66e7310c31ea4273403aa759cbd5153f5cab0fa48661db8b468b735a5711d3a

 트랜잭션 2(리틀 엔디안): 3b6f5d3e54622bbf0c1d5de770ca928e75b822638efbdb9cc71d2f1e79e7a146

 

 블록 헤더에 포함된 머클 루트의 값은 다음과 같습니다.

 

 머클 루트(리틀 엔디안): 4a1cfecaeea785d2da08c8c639f9ebab87f3c8ebfc5092d7d98fa4c426335f50

 

 이제 머클 트리를 구해보겠습니다. 먼저 트랜잭션 0과 트랜잭션 1의 해시값의 부모 노드를 구해야 합니다. 트랜잭션 0과 1을 하나로 묶은 후(이어 붙인 후) 이 값의 hash256 해시 값을 구합니다.

 

 트랜잭션 0-1: 3fe4847985f3b66472e104214575421f2e2969f47cbbbe8ac02c5e9fc5cc4ad1f66e7310c31ea4273403aa759cbd5153f5cab0fa48661db8b468b735a5711d3a

 

 아래 파이썬 코드를 이용하면 쉽게 구할 수 있습니다.

import hashlib

c = '3fe4847985f3b66472e104214575421f2e2969f47cbbbe8ac02c5e9fc5cc4ad1f66e7310c31ea4273403aa759cbd5153f5cab0fa48661db8b468b735a5711d3a'
h1 = hashlib.sha256(bytes.fromhex(c))
h2 = hashlib.sha256(h1.digest())

print(h2.hexdigest())

 

 트랜잭션 0-1 해시값: b28a189a993a6900bc241ac676b39cfcfe491f87df7b306c3437f21cac488d6a

 

같은 방식으로 트랜잭션 2와 2의 해시값의 부모 노드를 구합니다. 트랜잭션이 홀수개이기 때문에 중복으로 사용하였습니다.

 

 트랜잭션 2-2: 3b6f5d3e54622bbf0c1d5de770ca928e75b822638efbdb9cc71d2f1e79e7a1463b6f5d3e54622bbf0c1d5de770ca928e75b822638efbdb9cc71d2f1e79e7a146

 

 트랜잭션 2-2 해시값: 83dc0a6275a53bd944184570b6c5c8463f2142646e5fb8bf8f27d13be1997c38

 

 마지막으로 두 해시값의 부모 노드를 구하면 이 값이 머클 루트가 됩니다.

 

 트랜잭션 01-22: b28a189a993a6900bc241ac676b39cfcfe491f87df7b306c3437f21cac488d6a83dc0a6275a53bd944184570b6c5c8463f2142646e5fb8bf8f27d13be1997c38

 

 트랜잭션 01-22의 해시값(머클 루트): 4a1cfecaeea785d2da08c8c639f9ebab87f3c8ebfc5092d7d98fa4c426335f50

 

 블록에 포함되어 있던 머클 루트와 지금 구한 머클 루트의 값이 같은 것을 알 수 있습니다. 즉, 머클 루트를 올바르게 구했음을 알 수 있습니다.

 

 지금 구한 머클 트리를 표현하면 다음과 같습니다.

 

 

 지금까지 머클 트리에 대해 알아봤습니다. 감사합니다.

 

 

이어지는 글들

---

[비트코인 구조] SPV(Simplified Payment Verification)