머클 트리란 무엇인가
머클 트리는 대량의 데이터를 효율적으로 검증하기 위해 고안된 이진 트리 구조입니다. 이름은 고안자인 랄프 머클(Ralph Merkle)에서 따왔습니다. 가장 하위 노드(리프 노드)에는 각 데이터의 해시값이 저장되고, 상위로 올라갈수록 하위 두 노드의 해시값을 다시 합쳐서 해시한 값이 저장됩니다. 이 과정을 반복하면 최종적으로 트리 꼭대기에 단 하나의 해시값, 즉 ‘루트 해시(Merkle Root)’가 남습니다.
비유하자면 여러 명이 나눠 쓴 시험 답안지를 하나하나 채점하는 대신, 각 답안지의 요약본을 만들고 그 요약본들을 다시 요약해서 최종 요약 하나로 압축하는 것과 비슷합니다. 최종 요약값 하나만 비교해도 원본 데이터 전체가 조금이라도 바뀌었는지 즉시 알 수 있습니다.
동작 원리와 간단한 예시
예를 들어 4개의 거래 데이터 A, B, C, D가 있다고 가정해봅시다. 과정은 다음과 같습니다.
- Hash(A), Hash(B), Hash(C), Hash(D)를 각각 계산합니다.
- Hash(A)와 Hash(B)를 합쳐 Hash(AB)를 만들고, Hash(C)와 Hash(D)를 합쳐 Hash(CD)를 만듭니다.
- Hash(AB)와 Hash(CD)를 합쳐 최종 Merkle Root를 만듭니다.
만약 D 데이터가 조작되면 Hash(D)가 바뀌고, 그로 인해 Hash(CD)가 바뀌고, 결국 Merkle Root까지 달라집니다. 즉 루트 해시 하나만 비교해도 트리 어딘가의 데이터 변조 여부를 즉시 감지할 수 있습니다. 또한 특정 데이터 하나만 검증하고 싶을 때도 전체 데이터를 다 가져올 필요 없이, 해당 데이터와 짝을 이루는 ‘증명 경로(Merkle Proof)’의 해시값들만 있으면 루트까지 계산해서 맞는지 확인할 수 있습니다. 이를 Merkle Proof라고 부릅니다.
실무에서 왜 사용하는가
블록체인에서는 하나의 블록 안에 수천 개의 거래(transaction)가 담깁니다. 만약 특정 거래 하나가 블록에 포함되어 있는지 확인하려면 원래는 블록 전체 데이터를 다운로드해야 하지만, 머클 트리를 쓰면 블록 헤더에 저장된 Merkle Root와 소수의 증명 해시값만으로 검증이 가능합니다. 비트코인의 경량 노드(SPV, Simplified Payment Verification)가 바로 이 방식을 활용합니다.
분산 시스템에서도 마찬가지로 유용합니다. 여러 서버에 복제된 파일이나 데이터베이스가 서로 동일한 상태인지 확인할 때, 전체 데이터를 매번 비교하는 대신 머클 트리의 루트 해시만 비교하면 됩니다. 만약 루트 해시가 다르면 트리를 타고 내려가면서 어느 부분이 다른지만 빠르게 찾아낼 수 있습니다. 대표적으로 아마존의 다이나모DB(Dynamo)나 IPFS, Git의 커밋 구조 일부도 이와 유사한 원리를 사용합니다.
정리하면 머클 트리는 ‘전체를 다 보지 않고도 무결성을 검증할 수 있게 해주는 구조’로, 데이터 양이 많아질수록 그 효율성이 두드러지기 때문에 블록체인과 분산 시스템의 핵심 설계 요소로 널리 채택되고 있습니다.