홍라이프 계산기머클 트리 크기·증명 길이 계산 쉽게 이해하기 — 개념과 원리
머클 트리는 데이터를 두 개씩 묶어 해시하고, 그 결과를 다시 두 개씩 해시하는 일을 반복해 마지막에 하나의 루트 해시를 남깁니다. 이 루트 하나가 집합 전체를 대표합니다. 이 계산기는 잎(leaf) 개수에 따른 트리 높이와, 포함 증명에 필요한 해시 개수와 바이트 수를 알려 줍니다. 블록체인, 인증서 투명성 로그, 파일 동기화처럼 전체 데이터를 보내지 않고 어떤 항목이 큰 집합에 들어 있음을 증명해야 할 때 씁니다.
계산 방법
잎이 N개인 이진 머클 트리에서 다음과 같습니다.
- 트리 높이 = ⌈log₂ N⌉, 잎 위로 쌓인 단계 수입니다.
- 증명 해시 수 = ⌈log₂ N⌉, 단계마다 형제 해시가 하나씩 필요합니다.
- 증명 크기 = ⌈log₂ N⌉ × 32바이트입니다(SHA-256처럼 32바이트 해시 기준).
⌈x⌉는 올림을 뜻합니다. 단계가 일부만 채워져도 한 단계를 온전히 거쳐야 하기 때문입니다.
원리
한 단계 올라갈 때마다 노드 수가 절반이 되므로 k단계로는 최대 2ᵏ개의 잎을 담을 수 있고, 높이는 2ᵏ ≥ N을 만족하는 가장 작은 k입니다. 어떤 잎이 포함되었음을 증명하려면 각 단계의 형제 해시를 보냅니다. 검증자는 잎과 첫 형제를 해시하고, 그 결과와 다음 형제를 해시하는 식으로 꼭대기까지 올라갑니다. 최종값이 신뢰하는 루트와 같으면 그 잎은 트리에 들어 있다고 확신할 수 있습니다. 다른 경로를 위조하려면 해시 충돌을 찾아야 하기 때문입니다.
예제 풀이
- 입력값은 잎 N = 1,000,000개입니다.
- log₂ 1,000,000 ≈ 19.93이고, 올림하면 높이는 20입니다(2²⁰ = 1,048,576 ≥ 1,000,000).
- 필요한 증명 해시는 20개입니다.
- 증명 크기는 20 × 32 = 640바이트입니다.
| 리프 수 | 트리 높이 |
|---|---|
| 250,000 | 18 |
| 500,000 | 19 |
| 750,000 | 20 |
| 1e+06 | 20 |
| 1.25e+06 | 21 |
| 1.5e+06 | 21 |
| 2e+06 | 21 |
결과 해석
잎 개수가 두 배가 되어도 증명에는 해시 하나(32바이트)만 늘어납니다. 비교하자면 100만 개의 32바이트 해시를 모두 보내면 32 MB가 듭니다. 트리 전체는 약 2N − 1개의 노드를 저장하므로 저장량은 N에 비례하지만 증명은 로그에 비례합니다.
흔한 실수
- 루트나 잎 자체를 증명 개수에 넣습니다. 증명은 형제 해시만으로 이루어집니다.
- 검증자가 각 단계에서 왼쪽·오른쪽 위치를 알아야 올바른 순서로 해시할 수 있다는 점을 잊습니다.
- 잎과 내부 노드를 같은 방식으로 해시합니다. RFC 6962 같은 표준은 접두 바이트를 달리해 위조를 막습니다.
자주 묻는 질문
머클 트리는 누가 만들었습니까?
1979년 디지털 서명 연구에서 랄프 머클이 고안했습니다.
비트코인은 왜 머클 트리를 씁니까?
경량 지갑이 블록 헤더와 짧은 증명만으로 거래가 블록에 들어 있는지 확인할 수 있게 하려는 것입니다.
출처: R. C. Merkle, "A Digital Signature Based on a Conventional Encryption Function", CRYPTO '87 · IETF RFC 6962, Certificate Transparency