Merkle Tree

지갑에 지급이 블록에 포함되었다는 표시가 떴다고 해 보세요. 전체 내용을 내려받지 않고 확인하려면 어떻게 해야 할까요? 여기서 Merkle Tree가 도움이 됩니다. 먼저 거래를 짧은 암호학적 지문인 해시로 나타내고, 이를 단계적으로 합쳐 하나의 공통 지문인 루트를 만듭니다. 헤더에 이 Merkle root가 담겨 블록과 거래가 연결됩니다. 루트는 모든 지급을 다시 읽어 낼 수 있는 보관함이 아니라, 제시된 데이터를 검증하는 값입니다. [1] [2]

A, B, C, D라는 네 거래를 생각해 보세요. 각각의 지문을 구한 뒤 A와 B를 이어 새 해시 AB를 계산합니다. C와 D도 같은 방식으로 CD를 만듭니다. 마지막으로 AB와 CD의 지문을 이어 루트를 계산합니다. 이 글자는 거래와 중간 결과를 표시할 뿐 실제 해시는 아닙니다. 많은 잎이 가지를 거쳐 하나의 뿌리로 모이는 거꾸로 선 나무와 비슷합니다. 거래 수가 늘면 층이 추가되지만 원리는 같습니다. [3]

B를 확인하려면 그 데이터를 가지고 지문을 계산합니다. 추가로 A의 지문, C와 D를 합친 CD의 지문, 그리고 정확한 순서만 있으면 됩니다. A와 B로 AB를 만들고, AB와 CD로 루트를 계산해 헤더의 루트와 비교합니다. 이 보조 경로를 Merkle proof라고 합니다. A, C, D의 내용은 필요하지 않습니다. 거래가 1024개인 균형 잡힌 트리라면 경로에는 형제 해시 10개가 있습니다. 따라서 블록이 커져도 증명은 전체 거래 목록보다 훨씬 느리게 커집니다. [2] [3]

증명이 루트와 일치한다고 받은 헤더를 무조건 믿을 수는 없습니다. Proof of Work, 즉 채굴 계산 결과가 요구되는 난이도를 충족하는지도 검증해야 합니다. 헤더가 적절한 체인에 연결되어 있는지도 확인합니다. 그렇게 해도 Merkle proof가 블록의 모든 거래에 대한 서명과 규칙을 전부 확인하는 것은 아닙니다. 그것은 Full Node의 역할입니다. 따라서 whitepaper에 설명된 간소화된 지급 검증 SPV는 완전 검증과 다른 보안 가정을 가집니다. 재구성으로 블록이 활성 분기에서 빠질 수도 있습니다. 내용은 여전히 증명할 수 있지만 현재 기록에서 지급의 위치는 달라질 수 있습니다. [2]

비트코인의 일반 거래 트리에서 잎은 블록의 거래 순서대로 놓인 txid이며 맨 앞에는 채굴자가 블록 보상을 받기 위해 만드는 특별한 거래인 Coinbase Transaction이 있습니다. 쌍을 바이트로 이어 SHA-256으로 두 번 해시합니다. 한 층의 마지막에 짝 없는 해시가 남으면 계산을 위해 복제합니다. 지급이 하나 더 생기는 것은 아닙니다. 거래가 하나뿐이면 그 txid가 바로 루트입니다. 이 복제 방식 때문에 구현에서는 중복을 세심하게 검사해야 합니다. 프로토콜 개선인 SegWit는 서명 같은 witness 데이터도 분리합니다. Coinbase Transaction에 기록된 또 다른 암호학적 지문이 이 데이터를 블록에 연결합니다. 이 지문을 witness commitment라고 합니다. 따라서 일반 txid 트리와 witness 트리를 혼동하면 안 됩니다. [3] [4]