머클 트리

머클 트리는 데이터 조각들을 해시로 묶어 올리는 트리입니다. 맨 아래 잎에는 조각 하나하나의 해시가 놓입니다. 한 층 위의 값은 자식들의 해시를 이어 붙여 다시 해시한 것입니다. 꼭대기에 남는 값 하나를 견주면 아래에 담긴 것이 전부 같은지 알 수 있습니다.

상세

머클 트리는 데이터를 나눠 담는 트리가 아닙니다. 이미 나뉘어 있는 데이터 조각들 위에 해시를 얹어 세우는 트리입니다. 조각은 파일을 일정 크기로 자른 블록일 수도 있고, 차례로 쌓인 기록 하나하나일 수도 있습니다. 규칙은 두 줄입니다.

• 잎 노드는 데이터 조각 하나를 해시 함수에 넣은 값입니다
• 내부 노드는 두 자식의 값을 이어 붙여 해시 함수에 다시 넣은 값입니다

이 규칙을 뿌리까지 되풀이하면 값 하나가 남습니다. 그것이 트리 전체를 대표하는 뿌리 해시입니다.

이름은 Ralph C. Merkle 에게서 왔습니다. 1979년 스탠퍼드 박사논문 "Secrecy, Authentication, and Public Key Systems" 의 5장이 이 구조를 정의합니다. 논문은 그 방법을 트리 인증이라고 부릅니다. h(1,n,Y) 를 계산하는 과정이 재귀 호출의 이진 트리를 이루기 때문입니다. 논문은 함수 h(i, j, Y) 를 세웁니다. i 와 j 가 같으면 h(i, i, Y) 는 f(y_i) 입니다. 데이터 조각 y_i 를 함수 f 에 한 번 넣은 값입니다. i 와 j 가 다르면 가운데 k 를 (i+j)/2 로 잡아 h(i, j, Y) = f( h(i, k, Y), h(k+1, j, Y) ) 로 둡니다. 두 자식의 값을 f 에 넣는 것입니다. 논문은 설명을 간단히 하려고 잎 개수 n 을 2의 거듭제곱으로 제한합니다. 그리고 h(1, n, Y) 를 인증 트리의 뿌리라고 부르고 r 이라 적습니다.

잎이 여덟이면 이렇게 생깁니다. 맨 아랫줄이 데이터 조각이고, 그 바로 위가 조각마다 하나씩 놓인 잎 해시입니다. 화살표가 가리키는 쪽이 두 자식을 이어 붙여 다시 해시한 값이고, 그것이 층마다 반으로 줄며 맨 위의 뿌리 하나로 모입니다.

flowchart BT
    Y1["y1"] --> L1["h(1,1)"]
    Y2["y2"] --> L2["h(2,2)"]
    Y3["y3"] --> L3["h(3,3)"]
    Y4["y4"] --> L4["h(4,4)"]
    Y5["y5"] --> L5["h(5,5)"]
    Y6["y6"] --> L6["h(6,6)"]
    Y7["y7"] --> L7["h(7,7)"]
    Y8["y8"] --> L8["h(8,8)"]
    L1 --> N12["h(1,2)"]
    L2 --> N12
    L3 --> N34["h(3,4)"]
    L4 --> N34
    L5 --> N56["h(5,6)"]
    L6 --> N56
    L7 --> N78["h(7,8)"]
    L8 --> N78
    N12 --> N14["h(1,4)"]
    N34 --> N14
    N56 --> N58["h(5,8)"]
    N78 --> N58
    N14 --> R["뿌리 r = h(1,8)"]
    N58 --> R

여기서 두 가지 성질이 따라 나옵니다.

첫째, 잎 하나가 바뀌면 그 잎에서 뿌리까지 이어지는 노드의 값이 전부 바뀝니다. 뿌리 값 하나가 아래 전부를 대표한다는 말이 이 뜻입니다. 뒤집으면, 뿌리 값 두 개가 같은데 아래 데이터가 다르려면 해시 함수가 충돌을 내야 합니다.

둘째, 잎 하나가 트리에 들어 있다는 것을 보이는 데 트리 전체가 필요하지 않습니다. 그 잎에서 뿌리까지 올라가는 길에 매 층마다 짝이 되는 형제 노드의 값만 있으면 뿌리를 다시 계산할 수 있습니다. 논문도 잎 하나를 인증하는 데 필요한 것은 그 잎에서 뿌리까지 이어지는 h() 값들, 곧 h(i,i,Y) 부터 h(1,n,Y) 까지뿐이라고 적습니다. 인증서 투명성을 규정한 RFC(Request for Comments) 6962 는 그 값들의 목록을 감사 경로라고 부릅니다.

복잡도

두 벌의 데이터가 같은지 보는 판정이 조각을 n 번 견주는 일에서 값 하나 견주기로 줄어듭니다. 이 구조를 세우는 값어치가 그 한 줄입니다. 대신 세우는 비용과 내부 노드를 두는 공간을 각각 O(n) 만큼 먼저 치릅니다. 잎 하나가 트리에 있다는 증명은 트리 높이만큼, 곧 O(log n) 개의 값으로 끝납니다. 아래 표는 그 값들을 연산마다 하나씩 보인 것입니다.

n 은 잎의 개수, 곧 트리에 얹은 데이터 조각의 개수입니다. 비용을 정하는 것은 트리의 높이입니다. 한 층에서 노드를 둘씩 짝지어 반으로 줄이면 높이는 log2 n 입니다.

평균 칸과 최악 칸이 갈리지 않습니다. 높이를 정하는 것이 잎의 개수 하나뿐이기 때문입니다. 인증서 투명성 명세는 잎 개수가 2의 거듭제곱이 아니어도 트리 모양이 잎 개수 하나로 유일하게 정해진다고 적습니다. Merkle 의 논문이 다루는 트리는 앞서 적은 대로 잎 개수가 2의 거듭제곱인 경우입니다. 어느 쪽이든 잎 개수가 정해지면 높이가 따라 정해집니다. 뿌리 값 하나를 견주는 비교만 높이와 무관합니다.

평균과 최악을 갈라 놓고 보면 1급 출처들이 대는 값은 여기까지입니다. 머클 트리의 증명 크기나 갱신 비용을 두 경우로 나눠 서로 다른 차수를 적은 1급 문장은 자료에 없습니다.

Merkle 의 논문은 잎 개수를 2의 거듭제곱으로 제한한 경우의 수치를 적습니다. 임의의 잎 하나를 인증하는 데 log2 n 번의 전송이면 되고 한 번이 약 200비트라고 셉니다. 그리고 알고리즘을 뜯어 보면 전송의 절반이 중복이라고 덧붙입니다. 그래서 실제로 드는 것은 100 log2 n 비트입니다.

상수 자리에는 해시 함수 호출 비용이 들어옵니다. 특히 잎 해시는 데이터 조각 전체를 읽어야 하므로, 조각을 잘게 쪼갤수록 잎 개수 n 이 늘고 굵게 쪼갤수록 호출 한 번이 무거워집니다.

예시

인증서 투명성 로그의 머클 트리 해시

인증서 투명성 명세는 그 로그가 쓰는 트리 해시를 SHA-256(Secure Hash Algorithm 256, 256비트 보안 해시 알고리즘)으로 이렇게 못 박습니다.

MTH({})       = SHA-256()
MTH({d(0)})   = SHA-256(0x00 || d(0))
MTH(D[n])     = SHA-256(0x01 || MTH(D[0:k]) || MTH(D[k:n]))

|| 는 이어 붙이기입니다. 빈 목록의 해시는 빈 문자열의 해시입니다. 항목이 하나인 목록의 해시, 곧 잎 해시는 데이터 앞에 바이트 0x00 을 붙여 그 해시 함수에 넣은 값입니다. n 이 1보다 크면 n 보다 작은 2의 거듭제곱 가운데 가장 큰 값을 k 로 잡습니다. k < n <= 2k 입니다. 목록을 D[0:k] 와 D[k:n] 으로 가르고, 두 부분의 트리 해시 앞에 바이트 0x01 을 붙여 같은 해시 함수에 다시 넣습니다. 명세는 잎과 노드의 해시 계산이 다르다는 것을 괄호로 직접 짚어 둡니다.

입력 목록의 길이가 2의 거듭제곱일 필요는 없습니다. 그래서 만들어지는 머클 트리는 균형이 아닐 수 있습니다. 다만 그 모양은 잎 개수 하나로 유일하게 정해진다고 명세가 적습니다.

인증서 투명성 로그의 감사 경로

같은 명세는 잎 하나가 트리에 있다는 것을 보이는 값들의 목록을 감사 경로라고 부릅니다. 감사 경로는 그 트리의 머클 트리 해시를 계산하는 데 필요한 추가 노드들의 가장 짧은 목록입니다. 트리의 노드는 잎이거나, 바로 아래 두 노드에서 계산된 값입니다. 뿌리 쪽으로 한 층 올라갈 때마다 감사 경로의 노드 하나를 지금까지 계산한 노드와 합칩니다. 그렇게 얻은 뿌리가 진짜 뿌리와 같으면, 그 감사 경로가 잎이 트리에 있다는 증명이 됩니다.

위의 해시 규칙을 잎 넷짜리 목록에 그대로 적용하면, d3 하나를 확인하는 데 트리에서 실제로 건드리는 노드는 아래 굵은 테두리 다섯뿐입니다. 받아 오는 값은 h2 와 h01 둘이고, h3 부터 뿌리까지 셋은 검증하는 쪽이 직접 계산합니다. 나머지 절반인 d0 · d1 · h0 · h1 은 손도 대지 않습니다.

flowchart BT
    D0["d0"] --> H0["h0"]
    D1["d1"] --> H1["h1"]
    D2["d2"] --> H2["h2 · 받아 오는 값"]
    D3["d3"] --> H3["h3 · 직접 계산"]
    H0 --> H01["h01 · 받아 오는 값"]
    H1 --> H01
    H2 --> H23["h23 · 직접 계산"]
    H3 --> H23
    H01 --> R["r · 직접 계산"]
    H23 --> R
    classDef hit stroke-width:3px
    class H2,H01,H3,H23,R hit

h3 은 검증하는 쪽이 가진 d3 으로 직접 계산합니다. 그 다음은 두 걸음입니다. SHA-256(0x01 || h2 || h3) 으로 h23 을 얻고, SHA-256(0x01 || h01 || h23) 으로 뿌리를 얻습니다. h1 도 h0 도 받을 필요가 없습니다.

보장과 가정

보장 하나에 그것이 서 있는 가정이 하나씩 붙습니다.

뿌리 값 하나가 같으면 아래 잎 전부가 같습니다. 가정은 쓰는 해시 함수가 충돌을 내지 않는다는 것입니다. 서로 다른 두 입력이 같은 해시를 내면 뿌리가 같아도 아래가 다를 수 있습니다.

잎 하나가 트리에 들어 있다는 것을 형제 값 몇 개로 증명할 수 있습니다. 가정은 검증하는 쪽이 진짜 뿌리 값을 이미 알고 있다는 것입니다. 인증서 투명성 명세는 감사 경로로 계산한 뿌리가 진짜 뿌리와 같을 때 증명이 선다고 적습니다. 진짜 뿌리를 어디서 받아 오는지는 이 구조 밖의 일입니다.

뿌리 하나가 잎 목록을 하나로 정합니다. 가정은 잎의 해시와 내부 노드의 해시를 다르게 계산한다는 것입니다. 같은 명세는 잎을 SHA-256(0x00 || d) 로, 내부 노드를 SHA-256(0x01 || 왼쪽 || 오른쪽) 로 계산합니다. 그리고 잎과 노드의 해시 계산이 다르다는 것, 이 도메인 분리가 제2 원상 저항성을 주기 위해 필요하다는 것을 명세가 직접 적습니다.

세 번째 가정이 깨진 자리

Bitcoin Core 의 src/consensus/merkle.cpp 는 파일 첫머리에 경고를 남겨 두었습니다. 암호를 배우는 중이거나 머클 트리를 쓸 새 시스템을 설계하는 중이라면 다음을 염두에 두라는 경고입니다. 이 파일의 머클 트리 알고리즘에는 중복 트랜잭션 식별자와 얽힌 심각한 결함이 있습니다. 그 결함에는 CVE(Common Vulnerabilities and Exposures, 공통 취약점 식별자) 번호 CVE-2012-2459 가 붙었습니다.

원인은 짝을 맞추는 방식입니다. 어느 층에서 해시의 개수가 홀수이면 마지막 하나를 복제해 짝을 채운 뒤 다음 층을 계산합니다. 주석은 이것이 머클 트리에서는 흔치 않은 방식이라고 덧붙입니다. 그 결과 어떤 트랜잭션 목록들은 같은 머클 루트를 냅니다. 주석이 든 예가 [1,2,3,4,5,6] 과 [1,2,3,4,5,6,5,6] 입니다. 5와 6이 되풀이된 뒤쪽 목록이 앞쪽과 같은 뿌리 해시를 냅니다. (f) 를 해시한 값과 (f,f) 를 해시한 값이 같기 때문이라고 주석은 적습니다.

무너지는 것은 뿌리가 잎 목록을 하나로 정한다는 성질입니다. 주석은 그 다음에 벌어지는 일까지 적습니다. 그런 트랜잭션 목록을 가진 블록을 원본과 같은 머클 루트, 같은 블록 해시로 보낼 수 있고 그러면 검증이 실패합니다. 받는 노드가 그 블록을 영구히 무효라고 표시해 버리면, 복제되지 않은 원래 판까지 더는 받아들이지 못하게 됩니다. Bitcoin Core 는 목록 끝에서 같은 해시 둘을 합치게 되는 경우를 잡아내 그 블록의 머클 루트가 잘못된 것과 똑같이 다루는 것으로 막습니다. 이중 SHA-256(double SHA-256, 같은 값을 두 번 해시하는 것) 충돌이 없다고 가정하면 이 방법이 머클 루트를 건드리지 않고 트랜잭션을 바꾸는 알려진 모든 방식을 잡아낸다고 주석은 적습니다.

인증서 투명성 명세는 홀수 개를 복제로 채우지 않습니다. 목록을 2의 거듭제곱 자리에서 두 부분으로 가르고, 그래서 잎 개수 하나가 트리 모양을 유일하게 정합니다.

사용처

Git 의 객체 저장소. tree 객체는 항목을 하나 이상 담습니다. 각 항목은 blob 이나 하위 tree 의 SHA-1(Secure Hash Algorithm 1, 보안 해시 알고리즘) 해시에 모드와 타입과 파일명을 붙인 것입니다. commit 객체는 최상위 tree 의 해시 하나와 바로 앞선 커밋들을 가리킵니다. 이름이 곧 내용의 해시이므로 커밋 해시 하나가 그 스냅샷 전체를 덮습니다.

OpenZFS 의 풀. 풀 전체가 하나의 트리입니다. 잎은 데이터를 담고, 내부 노드인 블록 포인터는 자식이 어디에 있는지와 얼마나 큰지에 더해 자식의 체크섬을 함께 적습니다. 체크섬이 블록 옆이 아니라 부모에 저장되므로 손상된 블록이 스스로를 보증하지 못합니다. 뿌리에는 uberblock 이 있고 풀 안의 모든 것이 거기서 닿습니다. 가운데 블록은 제자리에서 고칠 수 없습니다. 새 데이터를 빈 자리에 씁니다. 새 블록을 가리키는 부모도 새로 씁니다. 부모의 체크섬이 바뀌었으므로 위로 되풀이합니다. 마지막에 새 uberblock 을 씁니다. 잎 하나 갱신이 뿌리까지의 경로 재계산이라는 성질을 저장 구조로 그대로 쓴 것입니다.

Apache Cassandra 의 안티엔트로피 repair. repair 는 노드들이 공통으로 맡은 토큰 범위의 데이터셋을 서로 견주고, 어긋난 구간만 스트리밍해 맞춥니다. 견주는 도구가 머클 트리입니다. 공식 문서는 그것을 해시의 계층이라고 적습니다. 데이터를 통째로 주고받지 않고 다른 구간만 찾아내려고 골랐습니다.

IPFS(InterPlanetary File System)의 머클 DAG(Directed Acyclic Graph, 방향 비순환 그래프). 각 노드는 식별자를 가집니다. 그 식별자는 노드가 실은 내용과 자식 식별자 목록을 SHA-256 같은 암호학적 해시 함수로 해시한 값입니다. 머클 트리와 닮았지만 균형 요건이 없고, 모든 노드가 데이터를 실을 수 있으며, 한 노드가 부모를 여럿 가질 수 있습니다. 가지가 다시 합쳐질 수 있다는 뜻입니다. 그래서 같은 식별자를 가진 두 노드는 정확히 같은 방향 비순환 그래프를 나타냅니다. 콘텐츠 주소 저장이 스스로를 검증하는 근거가 이것입니다.

관련 항목

해시 계산에 쓰는 함수

해시 함수 · SHA-256 · SHA-1 · 이중 SHA-256

보장이 딛고 선 전제

충돌 저항성 · 도메인 분리 · 제2 원상 저항성

이것이 기대는 개념과 닮은 자료구조

콘텐츠 주소 저장 · 이진 트리 · 머클 DAG

터지는 것과 그 이름

중복 트랜잭션 식별자 · CVE-2012-2459 · 블록 해시

만들어내는 증거

포함 증명 · 감사 경로

이것을 규정하거나 채택한 표준·시스템

RFC 6962 · Git · OpenZFS · Apache Cassandra · IPFS · Bitcoin Core · 인증서 투명성

이것의 부분을 시스템마다 부르는 이름

blob · tree 객체 · 커밋 · 블록 포인터 · uberblock · 머클 루트 · 트리 해시