20 · 머클 히스토리 트리: 로그를 32바이트로 커밋

수백만 건의 감사 로그가 한 글자도 바뀌지 않았음을 어떻게 증명할 수 있을까요? 로그 전체를 매번 다시 읽어야 한다면 너무 느리고, 로그 각각에 해시를 붙이면 각개격파 위조가 가능합니다. 머클 트리(Merkle tree)는 이 두 문제를 한번에 해결합니다 — 수백만 건 전체를 32바이트 루트 하나로 "커밋"하고, 한 바이트만 바뀌어도 그 루트가 달라집니다.

직관 먼저: 해시를 거듭 해시한다

해시 함수의 핵심 성질(19장 SHA-256)을 떠올려 보세요 — 입력이 1비트라도 바뀌면 출력이 완전히 달라집니다. 이 성질을 재귀적으로 이용하면 어떨까요?

1. 레코드 4개 각각의 해시를 계산합니다 → H(R0), H(R1), H(R2), H(R3)
2. 인접한 둘을 묶어 다시 해시합니다 → H(H(R0)||H(R1)), H(H(R2)||H(R3))
3. 마지막으로 그 둘을 묶어 다시 해시합니다 → 루트 하나

이렇게 하면 R0를 1비트 바꿔도, H(R0)가 달라지고, 그 부모 노드가 달라지고, 루트가 달라집니다. 루트 하나만 비교하면 어딘가 바뀌었는지 알 수 있습니다.

RFC 6962 규칙: 접두사가 중요하다

Quipu-Log는 구글의 Certificate Transparency 표준인 RFC 6962 해싱 규칙을 그대로 따릅니다. 핵심은 리프와 내부 노드에 서로 다른 접두사를 씁니다:

RFC 6962 §2.1 (quipu-log/crates/quipu-core/src/merkle.rs 문서 발췌)MTH({})        = SHA-256()               // 빈 트리
leaf hash      = SHA-256(0x00 || record)  // 리프: 레코드 바이트 그대로
interior node  = SHA-256(0x01 || left || right) // 내부 노드

왜 접두사가 필요할까요? 접두사 없이 SHA-256(H0 || H1)을 쓴다고 하면, "두 리프 H0과 H1의 연결을 단일 리프로 해시한 값"과 "H0||H1이라는 데이터의 리프 해시"를 구별할 수 없습니다. 이를 second-preimage 혼동 공격이라 합니다. 리프에 0x00, 내부 노드에 0x01을 붙이면 이 경우가 절대 같아질 수 없습니다.

표준을 따르는 또 다른 이유: RFC 6962를 아는 누구나 외부 검증기를 직접 짤 수 있습니다. Quipu-Log만의 독자 규칙이 아니니, 법적 감사나 제3자 감증에 참고 문서가 있습니다.

Quipu-Log의 실제 구현: leaf_hash / node_hash / mth

RFC의 재귀 정의를 그대로 옮긴 코드를 보겠습니다:

crates/quipu-core/src/merkle.rspub fn leaf_hash(record: &[u8]) -> Hash {
    let mut h = Sha256::new();
    h.update([LEAF_PREFIX]);  // 0x00
    h.update(record);
    h.finalize().into()
}

pub fn node_hash(left: &Hash, right: &Hash) -> Hash {
    let mut h = Sha256::new();
    h.update([NODE_PREFIX]);  // 0x01
    h.update(left);
    h.update(right);
    h.finalize().into()
}

/// 재귀 정의: D[n]의 루트
pub fn mth(leaves: &[Hash]) -> Hash {
    match leaves.len() {
        0 => empty_root(),     // SHA-256()
        1 => leaves[0],          // 리프 1개면 그대로
        n => {
            let k = split(n);  // n보다 작은 2의 최대 거듭제곱 (RFC 분할점)
            node_hash(&mth(&leaves[..k]), &mth(&leaves[k..]))
        }
    }
}

split(n)이 흥미롭습니다. n=4이면 k=2, n=5이면 k=4, n=6이면 k=4입니다. RFC 6962는 항상 "n보다 작은 2의 가장 큰 거듭제곱"을 왼쪽 완전 이진 트리의 크기로 씁니다. 이 덕분에 왼쪽 서브트리는 항상 완전 이진 트리(perfect subtree)가 되고, 증분 업데이트(아래의 Roots)가 효율적으로 됩니다.

증분 루트 추적: Roots

새 레코드가 하나 추가될 때마다 전체 트리를 처음부터 다시 계산하는 건 O(n)으로 너무 느립니다. Roots 구조체는 "완전 이진 트리의 피크(peak)" 목록만 유지하여 추가를 분할상환 O(1)로 처리합니다:

crates/quipu-core/src/merkle.rs — Roots::pushpub fn push(&mut self, leaf: Hash) {
    let mut carry = (0u32, leaf);
    while let Some(&(h, _)) = self.peaks.last() {
        if h != carry.0 { break; }
        let (_, left) = self.peaks.pop().unwrap();
        carry = (carry.0 + 1, node_hash(&left, &carry.1));
    }
    self.peaks.push(carry);
    self.size += 1;
}

같은 높이의 피크 두 개를 만나면 합쳐서 한 단계 위 피크로 올립니다. 이는 이진수 덧셈의 carry 전파와 정확히 같은 원리입니다. 100만 건이 있어도 피크는 최대 20개(log₂(1,000,000) ≈ 20)만 유지됩니다.

머클 스파인 파일: 리텐션 후에도 증명 가능

세그먼트 파일은 리텐션 정책(17장 삭제와 보존)에 따라 오래된 것이 삭제됩니다. 그런데 레코드가 지워지면 해당 리프 해시도 사라질까요?

그래서 MerkleLog라는 별도의 스파인 파일(merkle.spine)이 있습니다. 각 레코드의 리프 해시(32바이트)만 따로 모아서 영속합니다. 리텐션 대상이 아니라, 레코드 페이로드가 사라져도 해시는 남아 있습니다:

crates/quipu-core/src/merkle_log.rs — 파일 포맷// [ "QMKL" magic ][ u8 version ][ leaf_0 (32B) ][ leaf_1 (32B) ] ...
// 스파인은 리텐션 대상이 아닙니다 — 해시는 페이로드를 담지 않으니
// 보관해도 기밀 유출이 없고, 덕분에 purge 후에도 inclusion/consistency
// proof를 생성할 수 있습니다.

정리

• 머클 트리: 리프(레코드 해시) → 내부 노드(두 자식 해시의 해시) → 루트(32바이트) 하나로 전체 커밋.
• RFC 6962 규칙: 리프는 SHA-256(0x00 || 레코드), 내부 노드는 SHA-256(0x01 || left || right). 접두사로 혼동 공격 차단.
• Roots는 피크만 유지해 추가를 분할상환 O(1), O(log n) 공간으로 처리.
• merkle.spine 파일에 리프 해시만 별도 보관 → 리텐션 후에도 증명 가능.