Merkle Tree

Merkle Tree

머클 트리(Merkle Tree)는 암호화된 해시 값을 기반으로 데이터 무결성을 효율적으로 검증하는 트리 구조이다.
블록체인, 분산 시스템, 파일 전송 프로토콜 등에서 널리 활용되며, 데이터 변조 탐지와 검증 효율성이 핵심 강점이다.

머클 트리는 분산 환경의 신뢰 문제를 해결하는 핵심 도구로, 블록체인의 성공을 가능케 한 기술이다.
데이터의 안전한 공유와 검증이 필요한 모든 시스템에서 그 가치를 발휘한다.

계층적 해시 구조

• Leaf Node: 원본 데이터(트랜잭션, 파일 청크 등)의 해시 값으로 구성 (예: SHA-256).
• Non-Leaf Node: 자식 노드 두 개의 해시 값을 결합한 후 다시 해시화.
• Merkle Root: 최상위 노드의 해시 값으로 전체 데이터 집합을 대표.

예시: 4개 트랜잭션(A, B, C, D)의 머클 트리 구성

1
2
3
4
5

        H(ABCD)  
       /      \  
   H(AB)      H(CD)  
  /    \     /    \  
H(A) H(B) H(C) H(D)

데이터 변조 검출 메커니즘

• 특징: 단일 데이터 변경 → 모든 상위 노드 해시 값 변경 → Merkle Root 불일치.
• 예시: 트랜잭션 B가 B’로 변조되면 H(B) → H(B’), H(AB) → H(AB’), H(ABCD) → H(AB’CD).

핵심 장점

한계 및 개선 방향

• 거대 데이터셋: 트리 높이 증가 → 검증 경로 길어짐.
• 동적 업데이트: 기존 구조는 삭제/수정에 비효율적 → Merkle Patricia Trie로 해결.
• 표준화 부족: 구현마다 해시 함수, 트리 구조 차이 (예: Bitcoin-SHA256, Ethereum-Keccak).

블록체인에서의 활용

비트코인

• 역할: 블록 헤더에 Merkle Root 저장 → 트랜잭션 집합의 무결성 보장.
• SPV(Simplified Payment Verification): 라이트 노드가 풀 노드 없이 특정 트랜잭션 검증 가능.

검증 프로세스:

1. 라이트 노드가 풀 노드에 Merkle Proof 요청 (H(C), H(D), H(AB)).
2. H(C) + H(D) → H(CD), H(AB) + H(CD) → H(ABCD) 계산.
3. 블록 헤더의 Merkle Root와 비교.

이더리움 (Merkle Patricia Tree)

• 개선점: 머클 트리 + 패트리샤 트리 → 계정 상태 효율적 관리.
• 특징:
  • 변경된 노드만 업데이트 → 저장 공간 절약.
  • 이더리움 전체 상태를 단일 Merkle Root로 표현 (State Root).

실제 구현 예시

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import hashlib

def sha256(data):
    return hashlib.sha256(data.encode()).hexdigest()

class MerkleTree:
    def __init__(self, transactions):
        self.transactions = transactions
        self.tree = self.build_tree()

    def build_tree(self):
        tree = [ [tx for tx in self.transactions] ]
        layer = 0
        while len(tree[layer]) > 1:
            layer_nodes = []
            for i in range(0, len(tree[layer]), 2):
                left = tree[layer][i]
                right = tree[layer][i+1] if i+1 < len(tree[layer]) else left
                combined = sha256(left + right)
                layer_nodes.append(combined)
            tree.append(layer_nodes)
            layer += 1
        return tree

    def get_root(self):
        return self.tree[-1][0]

# 사용 예시
transactions = ['tx1', 'tx2', 'tx3', 'tx4']
merkle_tree = MerkleTree(transactions)
print("Merkle Root:", merkle_tree.get_root())

출력:

1

Merkle Root: 1a3d4f... (64자리 해시 값)

다른 자료구조와의 비교

참고 및 출처