머클 트리 증명 크기 계산기

트리 높이만큼, 즉 ⌈log₂n⌉개입니다. 잎이 1,000개면 10개, 100만 개면 20개입니다. 잎이 두 배가 되어도 하나만 늘어나기 때문에, 100만 개짜리 트리의 증명도 SHA-256 기준 640바이트에 그칩니다. 「전체를 보지 않고 그 안에 있다는 것만 보인다」가 이 자료구조의 존재 이유입니다.

잎을 포함해 각 층의 노드 수를 더한 값이며, 잎이 2의 거듭제곱이면 2n−1개입니다. 잎 8개면 8+4+2+1 = 15개이고 이 가운데 해시를 실제로 계산해야 하는 내부 노드는 7개입니다. 잎이 2의 거듭제곱이 아니면 층마다 ⌈이전/2⌉개가 되어 조금 달라집니다.

두 가지 방식이 있습니다. 복제는 짝이 없는 마지막 노드를 자기 자신과 묶어 올리며 비트코인이 이 방식입니다. 승격은 그대로 위로 올려 그 자리에서 형제 해시를 생략합니다. 층별 노드 «개수»는 두 방식이 같고, 갈리는 것은 증명 길이입니다 — 복제는 모든 잎이 높이와 같고, 승격은 마지막 잎일수록 짧아집니다.

있습니다. 마지막 노드를 복제하는 성질 때문에 잎 목록이 다른데도 같은 뿌리 해시가 나오는 경우를 만들 수 있으며, 비트코인에서 CVE-2012-2459로 알려진 취약점이 이것입니다. 잎 개수를 따로 커밋하거나 잎 해시와 내부 노드 해시에 다른 접두사를 붙이는 방식으로 막습니다.

자기가 가진 잎을 해시한 뒤 받은 형제 해시를 차례로 합쳐 올라가 뿌리 해시와 같은지만 봅니다. 계산 횟수는 증명 길이와 같아서, 100만 개짜리 트리도 해시 20번이면 검증이 끝납니다. 다만 형제 해시를 왼쪽에 붙일지 오른쪽에 붙일지도 증명에 함께 담겨야 하며, 이 방향 정보가 없으면 검증할 수 없습니다.

아닙니다. 여기서 세는 것은 트리의 «구조»입니다. 높이·노드 수·증명 길이·바이트 수처럼 자료의 내용과 무관하게 개수로 정해지는 값들이며, 실제 뿌리 해시를 얻으려면 잎 데이터를 직접 해시해야 합니다.

블록체인의 거래 포함 증명(SPV 지갑이 블록 전체를 받지 않고 자기 거래만 확인하는 방식), Git의 객체 트리, 인증서 투명성 로그, 분산 파일 시스템의 청크 무결성 검증, 백업 도구의 변경 감지에 두루 쓰입니다. 공통점은 「큰 자료 전체를 옮기지 않고 일부만 확인하고 싶다」는 것입니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.