머클 트리

비트코인 블록에는 많은 거래가 들어갑니다. 네트워크의 컴퓨터들이 블록을 서로 비교할 때 거래를 한 건씩 모두 대조하면 시간과 통신량이 커집니다. 거래 하나가 중간에서 바뀌었는지 찾는 일도 번거롭습니다.

머클 트리는 거래들의 지문을 둘씩 결합해 하나의 값으로 접어 올리는 구조입니다. 이 계산의 꼭대기에 남는 하나의 값이 머클 루트입니다. 머클 트리와 머클 루트는 거래 전체를 간결하게 대표하면서 변경 여부를 확인하는 데 사용됩니다.

거래 해시를 둘씩 결합하기

기본적인 설명에서는 블록에 담긴 거래의 거래 ID(TXID)를 잎으로 사용합니다. TXID를 둘씩 이어 붙여 다시 해시하고, 하나의 값이 남을 때까지 같은 과정을 반복합니다. 비트코인 개발자 문서도 블록의 거래를 머클 트리로 결합해 머클 루트를 계산하는 구조를 설명합니다(Bitcoin Developer Guide).

해시는 데이터를 고정 길이의 값으로 바꾸는 계산입니다. 원본 데이터가 한 글자만 달라져도 해시 결과가 크게 달라질 수 있습니다.

거래가 네 건이라면 처음에는 네 개의 거래 ID가 있고, 다음 단계에서는 두 개, 마지막에는 하나가 남습니다. 거래들이 토너먼트 대진표의 선수처럼 아래에서 시작해 위로 올라가는 모습으로 이해할 수 있습니다. 이기고 지는 경기가 아니라, 두 값이 만나 새로운 해시를 만드는 과정입니다.

거래 수가 홀수라 짝이 맞지 않으면 마지막 해시를 한 번 복제해 짝을 채우는 방식이 사용됩니다. 최종적으로 만들어진 머클 루트는 블록 헤더에 기록됩니다. 블록 헤더에 있는 머클 루트가 블록에 포함된 거래들을 대표하는 값이 됩니다.

SegWit 거래에서는 증인 데이터가 TXID에 직접 포함되지 않습니다. 증인 데이터는 블록의 별도 witness commitment로 연결되므로, 여기서 설명한 TXID 기반 머클 트리와 구별해야 합니다.

거래가 바뀌면 루트도 바뀝니다

거래의 TXID를 만드는 내용이 바뀌면 그 거래 ID가 달라집니다. 이어서 그 값이 포함된 상위 단계의 값들이 차례로 달라지고, 결국 머클 루트도 바뀝니다.

따라서 같은 방식과 같은 거래 순서로 계산한 머클 루트를 비교했을 때 값이 다르면 블록 안의 거래나 배열이 달라졌다는 신호가 됩니다. 수천 건의 거래를 일일이 비교하지 않고도 블록 내용의 변경 여부를 확인할 수 있습니다.

다만 블록 내용을 바꾼 뒤에는 해당 블록의 머클 루트뿐 아니라 블록 헤더와 작업증명도 다시 맞춰야 합니다. 이후 블록들은 앞선 블록을 참조하므로 후속 작업증명도 다시 계산해야 합니다.

특정 거래의 포함 여부 확인

머클 루트는 블록 전체를 내려받지 않고 특정 거래가 블록에 포함되었는지 확인할 때도 활용됩니다.

확인하려는 거래의 TXID와 머클 루트 사이에 있는 경로를 따라가며, 각 단계에서 필요한 짝 해시와 결합 순서를 이용해 루트를 다시 계산합니다. 이렇게 계산한 루트를 검증된 블록 헤더에 기록된 머클 루트와 대조해야 합니다. 임의로 받은 머클 루트에 연결된다는 사실만으로는 해당 거래가 실제로 채택된 체인에 포함되었다고 확인할 수 없습니다.

이 방법은 거래가 해당 블록에 포함되었는지를 확인하는 절차입니다. 거래의 서명과 금액, 블록의 모든 유효성 규칙을 대신 검증하지 않으며, 그 자체로 확정성을 보장하지도 않습니다. 헤더 체인의 신뢰 근거와 필요한 확인 수는 별도로 고려해야 합니다.

거래가 4,096건이라면 해시가 절반씩 줄어들기 때문에 꼭대기까지 올라가는 단계는 12번입니다. 거래 수가 늘어도 확인에 필요한 경로는 전체 거래 수만큼 길어지지 않습니다. 블록 전체를 보유하지 않는 경량 클라이언트가 거래 포함 여부를 확인할 수 있는 이유 중 하나입니다.

압축 파일과는 다릅니다

머클 트리가 수천 건의 거래를 하나의 값으로 접는다고 해서 머클 루트만으로 거래 내용을 복원할 수 있는 것은 아닙니다. 해시는 입력을 복원하기 어렵도록 설계된 일방향 계산이므로, 해시값에서 원래 거래를 되살릴 수 없습니다.

또한 머클 루트는 거래 데이터를 저장 공간에서 없애는 압축 기술도 아닙니다. 원본 거래는 블록의 몸통에 별도로 보관됩니다. 머클 트리는 원본을 대신 보관하는 것이 아니라, 거래 전체를 대표하는 값을 만들고 확인 절차를 줄이는 역할을 합니다.

정리하면 머클 트리는 거래 ID를 둘씩 결합해 하나의 머클 루트로 만드는 구조입니다. 머클 루트는 블록의 거래가 바뀌었는지 확인하는 기준이 되고, 검증된 블록 헤더와 짝 해시를 이용하면 특정 거래가 블록에 포함되었는지 확인할 수 있습니다. 다만 포함 증명만으로 거래와 블록의 모든 유효성 또는 확정성까지 보장하는 것은 아닙니다.

해시가 데이터를 지문처럼 바꾸는 원리는 해시에서 더 자세히 볼 수 있습니다.