머클 루트 (Merkle Root)

머클 루트는 머클 트리의 루트 노드로, 트리에서 해시된 모든 쌍이 최종적으로 합쳐진 값입니다. 블록 헤더는 해당 블록의 모든 트랜잭션에서 파생된 유효한 머클 루트를 포함해야 합니다. 이 하나의 해시가 블록에 담긴 트랜잭션 전체와 그 순서를 대표합니다.

만드는 방법

1. 리프: 각 트랜잭션의 해시(비트코인은 SHA-256을 두 번 적용한 TXID)를 맨 아래 층에 놓습니다.
2. 쌍 해싱: 이웃한 두 해시를 이어 붙여 다시 해시해 위층 노드를 만듭니다. 비트코인에서는 한 층의 노드 수가 홀수이면 마지막 노드를 복제해 짝을 맞춥니다.
3. 반복: 노드가 하나 남을 때까지 이 과정을 반복하며, 마지막에 남은 해시가 머클 루트입니다.

블록 헤더에서의 역할

비트코인 블록 헤더는 80바이트이며 이전 블록 해시, 머클 루트, 시각, 난이도 목표, 논스 등을 담습니다. 채굴자는 이 헤더를 해싱해 작업 증명을 찾으므로, 머클 루트를 통해 트랜잭션 목록 전체가 작업 증명에 묶입니다. 트랜잭션 하나라도 바뀌거나 순서가 달라지면 머클 루트가 달라지고, 헤더 해시와 작업 증명도 무효가 됩니다.

머클 증명과 SPV

머클 루트만 확인한다고 개별 트랜잭션이 검증되는 것은 아닙니다. 특정 트랜잭션이 블록에 포함되어 있음을 보이려면 머클 증명이 필요합니다. 머클 증명은 그 트랜잭션에서 루트까지 올라가는 경로의 형제 해시들로 이루어지며, 트랜잭션이 N개일 때 약 log₂N개의 해시면 충분합니다. 예를 들어 트랜잭션이 4,000개 정도인 블록에서도 해시 12개 정도로 포함 여부를 확인할 수 있습니다.

이 성질 덕분에 전체 블록을 내려받지 않고 블록 헤더만 보관하는 경량 지갑이 SPV(간이 결제 검증) 방식으로 자신의 트랜잭션 포함 여부를 확인할 수 있습니다. 비트코인 백서 8절이 이 방식을 설명합니다. 다만 SPV는 트랜잭션이 블록에 포함되었다는 사실만 확인할 뿐, 그 트랜잭션이 합의 규칙상 유효한지까지 스스로 검증하지는 않습니다.

알려진 취약점: CVE-2012-2459

홀수 노드를 복제하는 규칙 때문에, 마지막 트랜잭션(또는 노드)을 중복해 넣은 서로 다른 트랜잭션 목록이 같은 머클 루트를 가질 수 있습니다. 공격자는 이를 이용해 유효한 블록과 머클 루트가 같지만 중복 트랜잭션 때문에 무효인 변형 블록을 퍼뜨려, 노드가 정상 블록을 무효로 기록하게 만들 수 있었습니다. 비트코인 코어는 중복 트랜잭션이 있는 블록을 그 해시로 영구히 거부하지 않도록 처리해 이 문제를 막았습니다.

다른 쓰임

머클 트리는 블록체인 외에도 대규모 데이터 세트의 차이를 효율적으로 찾아 동기화하는 시스템, 인증서 투명성 로그, 파일 무결성 검증 등에 쓰입니다.