머클 트리
비트코인 블록에는 많은 거래가 들어갑니다. 네트워크의 컴퓨터들이 블록을 서로 비교할 때 거래를 한 건씩 모두 대조하면 시간과 통신량이 커집니다. 거래 하나가 중간에서 바뀌었는지 찾는 일도 번거롭습니다.
머클 트리는 거래들의 지문을 둘씩 결합해 하나의 값으로 접어 올리는 구조입니다. 이 계산의 꼭대기에 남는 하나의 값이 머클 루트입니다. 머클 트리와 머클 루트는 거래 전체를 간결하게 대표하면서 변경 여부를 확인하는 데 사용됩니다.
거래 해시를 둘씩 결합하기
기본적인 설명에서는 블록에 담긴 거래의 거래 ID(TXID)를 잎으로 사용합니다. TXID를 둘씩 이어 붙여 다시 해시하고, 하나의 값이 남을 때까지 같은 과정을 반복합니다. 비트코인 개발자 문서도 블록의 거래를 머클 트리로 결합해 머클 루트를 계산하는 구조를 설명합니다(Bitcoin Developer Guide).
해시는 데이터를 고정 길이의 값으로 바꾸는 계산입니다. 원본 데이터가 한 글자만 달라져도 해시 결과가 크게 달라질 수 있습니다.
거래가 네 건이라면 처음에는 네 개의 거래 ID가 있고, 다음 단계에서는 두 개, 마지막에는 하나가 남습니다. 거래들이 토너먼트 대진표의 선수처럼 아래에서 시작해 위로 올라가는 모습으로 이해할 수 있습니다. 이기고 지는 경기가 아니라, 두 값이 만나 새로운 해시를 만드는 과정입니다.
거래 수가 홀수라 짝이 맞지 않으면 마지막 해시를 한 번 복제해 짝을 채우는 방식이 사용됩니다. 최종적으로 만들어진 머클 루트는 블록 헤더에 기록됩니다. 블록 헤더에 있는 머클 루트가 블록에 포함된 거래들을 대표하는 값이 됩니다.
SegWit 거래에서는 증인 데이터가 TXID에 직접 포함되지 않습니다. 증인 데이터는 블록의 별도 witness commitment로 연결되므로, 여기서 설명한 TXID 기반 머클 트리와 구별해야 합니다.
거래가 바뀌면 루트도 바뀝니다
거래의 TXID를 만드는 내용이 바뀌면 그 거래 ID가 달라집니다. 이어서 그 값이 포함된 상위 단계의 값들이 차례로 달라지고, 결국 머클 루트도 바뀝니다.
따라서 같은 방식과 같은 거래 순서로 계산한 머클 루트를 비교했을 때 값이 다르면 블록 안의 거래나 배열이 달라졌다는 신호가 됩니다. 수천 건의 거래를 일일이 비교하지 않고도 블록 내용의 변경 여부를 확인할 수 있습니다.
다만 블록 내용을 바꾼 뒤에는 해당 블록의 머클 루트뿐 아니라 블록 헤더와 작업증명도 다시 맞춰야 합니다. 이후 블록들은 앞선 블록을 참조하므로 후속 작업증명도 다시 계산해야 합니다.
특정 거래의 포함 여부 확인
머클 루트는 블록 전체를 내려받지 않고 특정 거래가 블록에 포함되었는지 확인할 때도 활용됩니다.
확인하려는 거래의 TXID와 머클 루트 사이에 있는 경로를 따라가며, 각 단계에서 필요한 짝 해시와 결합 순서를 이용해 루트를 다시 계산합니다. 이렇게 계산한 루트를 검증된 블록 헤더에 기록된 머클 루트와 대조해야 합니다. 임의로 받은 머클 루트에 연결된다는 사실만으로는 해당 거래가 실제로 채택된 체인에 포함되었다고 확인할 수 없습니다.
이 방법은 거래가 해당 블록에 포함되었는지를 확인하는 절차입니다. 거래의 서명과 금액, 블록의 모든 유효성 규칙을 대신 검증하지 않으며, 그 자체로 확정성을 보장하지도 않습니다. 헤더 체인의 신뢰 근거와 필요한 확인 수는 별도로 고려해야 합니다.
거래가 4,096건이라면 해시가 절반씩 줄어들기 때문에 꼭대기까지 올라가는 단계는 12번입니다. 거래 수가 늘어도 확인에 필요한 경로는 전체 거래 수만큼 길어지지 않습니다. 블록 전체를 보유하지 않는 경량 클라이언트가 거래 포함 여부를 확인할 수 있는 이유 중 하나입니다.
압축 파일과는 다릅니다
머클 트리가 수천 건의 거래를 하나의 값으로 접는다고 해서 머클 루트만으로 거래 내용을 복원할 수 있는 것은 아닙니다. 해시는 입력을 복원하기 어렵도록 설계된 일방향 계산이므로, 해시값에서 원래 거래를 되살릴 수 없습니다.
또한 머클 루트는 거래 데이터를 저장 공간에서 없애는 압축 기술도 아닙니다. 원본 거래는 블록의 몸통에 별도로 보관됩니다. 머클 트리는 원본을 대신 보관하는 것이 아니라, 거래 전체를 대표하는 값을 만들고 확인 절차를 줄이는 역할을 합니다.
저장 공간을 줄인다는 뜻
비트코인 백서 7장은 머클 트리의 가지를 잘라 오래된 거래 데이터를 덜 보관하는 방안을 설명합니다. 이미 사용된 거래를 충분한 후속 블록이 쌓인 뒤 정리하더라도, 머클 루트를 남기면 블록 헤더의 해시를 바꾸지 않을 수 있다는 구상입니다. 백서는 거래 본문을 제외한 헤더가 약 80바이트라고 설명합니다. 헤더에는 이전 블록의 해시와 머클 루트가 들어가므로, 거래 본문보다 적은 공간으로 블록들의 연결을 보관할 수 있습니다. 비트코인 백서 7장
이것은 지운 거래를 루트에서 다시 꺼내거나, 헤더만으로 모든 거래를 검증한다는 뜻이 아닙니다. 현재 사용하는 노드의 저장 방식도 백서의 그림과 구분해야 합니다. Bitcoin Core가 0.11.0에서 도입한 블록 파일 가지치기는 블록을 먼저 검증하고 필요한 데이터베이스에 반영한 뒤 오래된 블록 파일을 삭제하는 방식입니다. 블록 색인과 아직 사용되지 않은 거래 출력의 집합인 UTXO 집합은 유지합니다. 모든 규칙을 직접 검증하는 노드도 과거 블록 파일 전부를 계속 보관할 필요는 없다는 뜻입니다. Bitcoin Core 0.11.0 릴리스 설명
영상은 이 저장 비용을 검증 참여의 문제로 봅니다. 기록을 보관하는 부담이 지나치게 커지면 개인이 자기 컴퓨터로 노드를 운영하기 어려워지고, 검증을 다른 사람에게 맡기기 쉬워진다는 관점입니다. 머클 트리는 가벼운 포함 증명과 헤더 보관을 가능하게 하는 부품이지만, 그것만으로 참여 비용이나 탈중앙화가 보장되는 것은 아닙니다. 저장 부담을 줄이면서도 어떤 검증을 직접 수행하고 어떤 자료를 다른 노드에 의존하는지 구분하는 것이 중요합니다.
정리하면 머클 트리는 거래 ID를 둘씩 결합해 하나의 머클 루트로 만드는 구조입니다. 머클 루트는 블록의 거래가 바뀌었는지 확인하는 기준이 되고, 검증된 블록 헤더와 짝 해시를 이용하면 특정 거래가 블록에 포함되었는지 확인할 수 있습니다. 다만 포함 증명만으로 거래와 블록의 모든 유효성 또는 확정성까지 보장하는 것은 아닙니다.
해시가 데이터를 지문처럼 바꾸는 원리는 해시에서 더 자세히 볼 수 있습니다.