머클 트리

트랜잭션 해시를 짝지어 각 쌍을 해시하고, 해시가 하나만 남을 때까지 반복합니다. 그 하나의 값이 블록 헤더에 들어가며, 어떤 트랜잭션이 그 아래에 속함을 증명하는 데는 한 경로 위의 해시만 있으면 됩니다. 2,000건의 결제를 담은 블록이라면 해시 11개, 352바이트입니다. 휴대폰 지갑이 블록을 내려받지 않고도 코인이 도착했는지 확인할 수 있는 이유가 여기에 있습니다.

작동 방식

머클 트리는 이웃끼리 해시를 묶어 한 단계씩 올라가며 해시가 하나만 남을 때까지 쌓아 올려 목록을 피라미드로 바꿉니다.

잎은 채굴업자가 배치한 순서대로 나열한 트랜잭션 ID입니다. 비트코인은 두 32바이트 값을 이어 붙이고 그 결과에 SHA-256을 두 번 적용해 각 쌍을 결합합니다. 어떤 단계의 항목 수가 홀수이면 마지막 항목은 자기 자신의 사본과 짝이 되는데, 이는 알고리즘을 단순하게 유지해 주는 한편 실제 문제를 일으킨 적이 있습니다. CVE-2012-2459로 분류된 취약점은 2012년 5월에 공개되어 같은 달에 패치되었는데, 이 중복을 악용해 기반 트랜잭션은 정상인데도 노드에는 유효하지 않은 것처럼 보이는 블록을 만들었습니다.

이득은 로그 규모입니다. 트랜잭션 수가 두 배가 되어도 단계가 하나 늘어날 뿐, 트랜잭션마다 해시가 하나씩 늘어나지는 않습니다. 1,024건의 결제가 있는 블록은 포함을 증명하는 데 해시 10개, 320바이트가 필요합니다. 4,096건이면 12개, 384바이트입니다. 증명을 검증하는 쪽은 경로를 위로 다시 계산해 그 결과를 헤더에서 이미 신뢰하는 루트와 비교하며, SHA-256을 깨지 않고는 경로를 위조할 방법이 없습니다.

이 가운데 비트코인에서 비롯된 것은 없습니다. Ralph Merkle은 US 4,309,569가 된 특허 출원에서 이 구조를 설명했으며, 그 출원은 1979년에 제출되어 1982년 1월에 등록되었습니다. 백서는 그의 업적을 인용하며 이 트리에 두 가지 용도를 부여합니다. 7절에서는 디스크 공간을 아끼기 위해 오래된 블록에서 이미 사용된 트랜잭션을 가지치기하는 데, 8절에서는 클라이언트가 헤더만 보유한 채 결제를 검증할 수 있게 하는 데 사용합니다.

확인할 수 있는 곳

머클 트리는 시스템이 큰 집합 전체를 보내지 않고도 어떤 항목이 그 집합에 속함을 증명해야 하는 곳이라면 어디에나 나타납니다.

비트코인 안에서는 모든 블록 헤더가 머클 트리의 꼭대기 값을 담고 있습니다. 노드는 받은 트랜잭션으로 트리를 다시 만들고 결과가 맞지 않으면 그 블록을 거부합니다. Bitcoin Core는 이 구조를 직접 드러냅니다. gettxoutproof는 트랜잭션이 블록에 포함되었음을 직렬화된 증명으로 만들어 내고, verifytxoutproof는 그 증명을 검사하는데, 지갑을 넘겨주지 않고도 누군가에게 결제의 증거를 건네는 실용적인 방법입니다.

비트코인의 다른 곳에서는 Taproot가 두 번째 트리를 만듭니다. Taproot 출력의 대안 지출 조건들이 트리 형태로 배치되므로, 사용한 가지를 드러내도 사용하지 않은 가지에 대해서는 아무것도 드러나지 않습니다. 비트코인 밖에서는 같은 구조가 Git 커밋 이력, 잘못 발급된 웹 인증서를 잡아내는 Certificate Transparency 로그, ZFS 파일시스템의 데이터 무결성 검사의 바탕이 됩니다.

지갑 사용자가 보는 결과는 작지만 유용합니다. 수십 메가바이트의 헤더를 보유한 경량 클라이언트는 해당 트랜잭션이 특정 블록, 특정 깊이에 있음을 확인할 수 있으며, 누군가 가짜 체인에서 유효한 작업 증명을 만들어 내지 않는 한 잘못된 답을 받지 않습니다. 그리고 그것에는 실제 비용이 듭니다.

머클 트리 vs 머클 루트

머클 트리는 작업용 구조이고, 머클 루트는 그 뒤에 남는 하나의 값입니다. 노드는 블록을 검증하는 동안 피라미드 전체를 메모리에 만들었다가 버리고, 꼭대기에 남은 32바이트만 저장합니다. 그 아래의 모든 것은 트랜잭션으로부터 다시 만들 수 있기 때문입니다. 탐색기가 머클 루트라는 이름의 항목을 보여 준다면 그것이 살아남은 값입니다. 아무도 트리를 저장하지 않으며, 저장할 필요도 없습니다.