머클 트리 (Merkle Tree) — 효율적 데이터 검증
머클 트리는 대량의 데이터를 하나의 해시값으로 요약하여 효율적으로 무결성을 검증할 수 있는 이진 해시 트리 구조입니다.
**머클 트리 (Merkle Tree)**는 대량의 데이터를 하나의 해시값(머클 루트)으로 요약하여 효율적으로 무결성을 검증할 수 있는 이진 해시 트리 구조입니다. 1979년 랠프 머클(Ralph Merkle)이 발명한 이 자료구조는 비트코인의 블록 구조에서 핵심적인 역할을 담당하며, 경량 클라이언트의 효율적 검증을 가능하게 합니다.
graph TD ROOT["루트 해시
Hash(H12+H34)"] H12["Hash(H1+H2)"] H34["Hash(H3+H4)"] H1["Hash(Tx1)"] H2["Hash(Tx2)"] H3["Hash(Tx3)"] H4["Hash(Tx4)"] TX1["Tx1"] TX2["Tx2"] TX3["Tx3"] TX4["Tx4"] ROOT --> H12 ROOT --> H34 H12 --> H1 H12 --> H2 H34 --> H3 H34 --> H4 H1 --> TX1 H2 --> TX2 H3 --> TX3 H4 --> TX4 style ROOT fill:#f7931a,stroke:#f7931a,color:#000 style H12 fill:#21262d,stroke:#f7931a,color:#e6edf3 style H34 fill:#21262d,stroke:#f7931a,color:#e6edf3 style H1 fill:#161b22,stroke:#30363d,color:#8b949e style H2 fill:#161b22,stroke:#30363d,color:#8b949e style H3 fill:#161b22,stroke:#30363d,color:#8b949e style H4 fill:#161b22,stroke:#30363d,color:#8b949e
이진 해시 트리의 구조
머클 트리는 최하위 리프(leaf) 노드에서 시작하여 최상위 루트까지 상향식으로 구축됩니다. 구체적인 단계는 다음과 같습니다.
1단계 - 리프 해시 생성: 블록에 포함된 각 트랜잭션의 txid를 리프 노드로 사용합니다. 비트코인에서는 SHA-256을 두 번 적용(double-SHA256)하여 각 트랜잭션의 해시를 생성합니다.
2단계 - 쌍별 결합: 인접한 두 해시를 연결(concatenate)한 뒤 다시 double-SHA256을 적용하여 부모 노드를 생성합니다. 예를 들어 H(A)와 H(B)가 인접한 리프라면, 부모 노드는 SHA256(SHA256(H(A) || H(B)))가 됩니다.
3단계 - 반복: 이 과정을 노드가 하나만 남을 때까지 반복합니다. 최종적으로 남는 단일 해시가 **머클 루트(Merkle Root)**이며, 이것이 블록 헤더의 hashMerkleRoot 필드에 기록됩니다.
트리의 깊이는 log₂(N)이므로, 1,000개의 트랜잭션이 있는 블록도 단 10단계의 해시 연산으로 머클 루트에 도달합니다. 이 로그 스케일의 효율성이 머클 트리의 핵심 가치입니다.
머클 증명(Merkle Proof)의 작동 원리
머클 증명은 특정 트랜잭션이 블록에 포함되어 있음을 증명하는 데이터 구조입니다. 전체 블록의 모든 트랜잭션을 다운로드할 필요 없이, 해당 트랜잭션에서 머클 루트까지의 경로에 있는 형제 해시들만 제공하면 됩니다.
예를 들어, 8개의 트랜잭션이 있는 블록에서 트랜잭션 D의 포함을 증명하려면: H(C), H(AB), H(EFGH) 이 세 개의 해시만 있으면 됩니다. 검증자는 H(D)를 계산하고, H(C)와 결합하여 H(CD)를 구하고, H(AB)와 결합하여 H(ABCD)를 구하고, 최종적으로 H(EFGH)와 결합하여 머클 루트를 계산합니다. 이 결과가 블록 헤더의 머클 루트와 일치하면 트랜잭션 D가 해당 블록에 포함되어 있음이 증명됩니다.
시간 복잡도는 O(log n)입니다. 블록에 4,000개의 트랜잭션이 있더라도 약 12개의 해시만으로 증명이 완료됩니다. 이는 전체 블록(수 MB)을 다운로드하는 것에 비해 극적인 효율성 향상입니다.
SPV 경량 검증에서의 활용
SPV(Simplified Payment Verification)는 사토시 나카모토의 백서 8절에 기술된 경량 검증 방식으로, 머클 증명에 전적으로 의존합니다. SPV 클라이언트는 블록 헤더(80바이트)만 다운로드하고, 관심 있는 트랜잭션에 대해 풀노드에게 머클 증명을 요청합니다.
이 방식의 장점은 저장 공간과 대역폭 요구가 극히 적다는 것입니다. 전체 블록체인 대신 블록 헤더 체인만 저장하므로 수십 MB 수준의 데이터로도 트랜잭션 검증이 가능합니다. 이러한 효율성 덕분에 모바일 지갑 등의 경량 클라이언트가 실현될 수 있었습니다. 다만 SPV는 풀노드에 의존하므로, 풀노드가 특정 트랜잭션의 존재를 숨기는 공격에는 취약합니다.
비트코인에서의 구현 세부사항
비트코인의 머클 트리 구현에는 몇 가지 특수한 규칙이 있습니다.
txid 페어링: 트랜잭션 해시들은 순서대로 페어를 이루어 결합됩니다. 첫 번째와 두 번째, 세 번째와 네 번째 식으로 페어링됩니다.
홀수 처리: 특정 레벨에서 노드 수가 홀수인 경우, 마지막 노드를 복제하여 자기 자신과 페어링합니다. 예를 들어 3개의 트랜잭션 A, B, C가 있으면 C를 복제하여 (A,B), (C,C)로 처리합니다.
코인베이스 트랜잭션: 블록의 첫 번째 트랜잭션은 항상 코인베이스(채굴 보상) 트랜잭션이며, 이것도 머클 트리의 첫 번째 리프로 포함됩니다.
CVE-2012-2459 취약점과 해결
2012년에 발견된 CVE-2012-2459는 비트코인의 머클 트리 구현에서 홀수 노드 복제 방식을 악용한 취약점이었습니다. 공격자가 동일한 머클 루트를 생성하면서도 실제 트랜잭션 목록이 다른 변조 블록을 만들 수 있었습니다. 구체적으로, 홀수 개의 트랜잭션이 있는 블록에서 마지막 트랜잭션을 복제하여 추가하면 동일한 머클 루트가 생성되는 문제였습니다.
이 취약점은 노드가 유효하지 않은 블록을 유효하다고 판단하게 만드는 것이 아니라, 유효한 블록을 무효로 거부하게 만드는 DoS(서비스 거부) 벡터로 활용될 수 있었습니다. 수정 사항은 머클 트리 계산 과정에서 동일한 해시 쌍이 발견되면 해당 블록을 무효로 처리하는 검증 로직을 추가하는 것이었습니다.
탭루트의 MAST (Merklized Abstract Syntax Trees)
MAST는 머클 트리 구조를 비트코인 스크립트에 적용한 것으로, 2021년 활성화된 탭루트(Taproot) 업그레이드의 핵심 구성 요소입니다. 기존의 비트코인 스크립트는 가능한 모든 지출 조건을 트랜잭션에 포함해야 했지만, MAST는 각 지출 조건을 머클 트리의 리프로 배치하여, 실제로 사용되는 조건의 경로만 공개합니다.
예를 들어 “3-of-5 다중서명 또는 1년 후 2-of-5 다중서명 또는 2년 후 단독 서명”이라는 복잡한 지출 조건이 있을 때, MAST를 사용하면 실제 지출 시 사용된 조건과 머클 증명만 공개하면 되므로, 다른 조건의 존재 자체가 드러나지 않습니다. 이는 프라이버시를 크게 향상시키며, 공개해야 하는 데이터양이 줄어 수수료도 절감됩니다.