머클 트리

호기심

1. 단 하나의 해시 값만으로 어떻게 4천 건의 고유한 트랜잭션이 포함되어 있음을 증명할 수 있을까요?
2. 사토시는 왜 홀로 남은 마지막 항목을 자기 자신과 짝짓도록 했으며, 그 선택은 어떤 대가를 치렀을까요?
3. 중복 짝짓기 규칙은 비트코인 초기 구현에 구체적으로 어떤 취약점을 만들었나요?

탐구

1. 랄프 머클은 1979년 이진 해시 트리에 대한 특허를 출원했습니다(1982년 등록). 이진 해시 트리는 대규모 데이터셋을 효율적으로 요약하도록 설계된 데이터 구조입니다. 비트코인에서는 이 구조를 통해 수천 개의 트랜잭션 식별자를 머클 루트라고 불리는 하나의 32바이트 값으로 줄입니다. 이 루트는 80바이트 블록 헤더에 직접 포함되어, 해당 블록 안의 모든 트랜잭션에 대한 변경 불가능한 암호학적 커밋먼트를 만들어냅니다.
2. 트리는 아래에서 위로 재귀적으로 구축됩니다. 트랜잭션 ID를 두 개씩 이어 붙인 뒤 이중 SHA-256으로 해시하여 부모 노드를 만듭니다. 이렇게 짝짓는 과정을 레벨마다 반복해 하나의 루트 해시만 남을 때까지 계속합니다. 어떤 레벨의 항목 수가 홀수이면 이진 구조를 유지하기 위해 마지막 항목을 자기 자신과 짝지으며, 이로써 모든 단계에서 트리가 올바르게 균형을 이룹니다.
3. 이 구조의 로그적 특성 덕분에 단순 지불 검증(SPV)이 가능합니다. 라이트 클라이언트는 전체 블록을 다운로드하지 않고, 대신 풀노드에 머클 브랜치를 요청합니다. 이 브랜치는 특정 트랜잭션에서 루트까지 이어지는 경로상의 형제 해시들로만 이루어집니다. 트랜잭션이 4,000건인 블록이라면 이 증명에 필요한 해시 값은 약 12개로, 전체 데이터 크기의 극히 일부에 불과합니다.
4. 라이트 클라이언트는 자신의 트랜잭션 해시를 제공받은 형제 해시들과 결합해 머클 루트를 다시 계산하고, 이를 다운로드한 블록 헤더의 값과 비교합니다. 두 값이 일치하면 체인 전체를 저장하지 않고도 트랜잭션의 포함 여부가 암호학적으로 검증됩니다. 이 메커니즘 덕분에 모바일 지갑은 저장 공간과 처리 능력이 제한된 기기에서도 안전하게 작동할 수 있습니다.
5. 2017년 8월에 활성화된 세그윗(SegWit, Segregated Witness)은 두 번째 머클 트리 구조를 도입했습니다. 기존 트리가 트랜잭션 ID에 커밋하는 반면, 위트니스 트리는 위트니스 트랜잭션 ID에 커밋합니다. 이 두 번째 트리의 루트는 헤더에 저장되지 않고 코인베이스 트랜잭션의 OP_RETURN 출력에 커밋되며, 구버전 노드는 이를 일반 데이터로 취급하므로 호환성이 유지됩니다.
6. 자기 자신과 짝짓는 규칙에는 결함(CVE-2012-2459)이 숨어 있었습니다. 홀로 남은 마지막 항목을 자기 자신과 짝짓기 때문에, 중복된 쌍으로 끝나는 트랜잭션 목록은 그 중복이 없는 목록과 동일한 머클 루트를 만들어냅니다. 공격자는 유효한 블록을 이렇게 변형한 비정상 버전을 전파할 수 있었고, 이를 거부한 노드는 진짜 블록의 해시까지 무효로 표시해 네트워크와 어긋날 수 있었습니다. 2012년의 수정으로 노드는 해당 블록을 불량으로 캐시하는 대신 이 패턴을 인식하게 되었습니다.

핵심 사실

연습 아홉, 여섯, 셋, 하나

팩트 체크

날짜, 수치 및 주장은 아래에 명시된 출처들을 통해 확인되었습니다.

• R. Merkle, US Patent 4,309,569 (1982)
• Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System (2008), sections 7-8
• BIP 141: Segregated Witness (Consensus layer)
• A. M. Antonopoulos & D. A. Harding, Mastering Bitcoin, 3rd ed. (2023), ch. 11