21 · 포함 증명·일관성 증명

루트 32바이트가 전체 로그를 "커밋"한다는 건 알겠습니다. 그런데 누군가 "이 레코드가 정말 그 로그에 있었나요?"라고 물으면, 로그 전체를 넘겨줘야 할까요? 수백만 건을? 머클 트리의 진짜 힘은 여기서 나옵니다 — 로그 전체 없이, 루트와 log n 개의 해시만으로 레코드의 존재를 수학적으로 증명할 수 있습니다.

포함 증명(Inclusion Proof): 로그 없이 존재를 증명

n=8 트리에서 리프 #2(R2)가 포함됐음을 증명하는 상황을 생각해 봅시다. 검증자는 루트만 알고 있습니다.

검증 절차는 이렇습니다. 검증자는 H2(리프 해시) + 증명 경로 [H3, N(01), N(4567)]를 받습니다:

1. node_hash(H2, H3) → N(23) 재계산
2. node_hash(N(01), N(23)) → N(0123) 재계산 (N(01)은 증명에 들어 있음)
3. node_hash(N(0123), N(4567)) → 루트 재계산
4. 재계산한 루트가 공개된 루트와 같으면 → H2는 분명 그 트리에 속함 ✅

n개의 리프가 있을 때 증명 경로 길이는 ⌈log₂ n⌉입니다. 백만 건이라도 증명 경로는 겨우 20개 해시, 640바이트면 됩니다.

포함 증명 코드 확인

crates/quipu-core/src/merkle.rs — inclusion_proof / verify_inclusionpub fn inclusion_proof(leaves: &[Hash], m: usize) -> Vec<Hash> {
    let n = leaves.len();
    if n == 1 { return Vec::new(); }
    let k = split(n);
    if m < k {
        let mut path = inclusion_proof(&leaves[..k], m);
        path.push(mth(&leaves[k..]));  // 오른쪽 서브트리 해시 추가
        path
    } else {
        let mut path = inclusion_proof(&leaves[k..], m - k);
        path.push(mth(&leaves[..k]));  // 왼쪽 서브트리 해시 추가
        path
    }
}

// 검증은 로그 없이 독립 실행:
pub fn verify_inclusion(
    leaf: &Hash, leaf_index: usize, tree_size: usize,
    proof: &[Hash], root: &Hash,
) -> bool { /* 증명 경로를 따라 루트를 재계산하고 비교 */ }

재귀 구조가 직관적입니다. 목표 리프가 왼쪽(m < k)이면 오른쪽 서브트리 루트를 경로에 넣고, 오른쪽이면 왼쪽 서브트리 루트를 경로에 넣습니다. 재귀가 끝나면 경로에는 "없었던 형제들의 루트"가 리프-투-루트 순서로 쌓입니다.

일관성 증명(Consistency Proof): append-only를 증명

포함 증명이 "이 레코드가 있다"를 증명한다면, 일관성 증명은 "과거 루트 R_m이 현재 루트 R_n의 접두사다 — 즉, m번째 이후로 레코드가 추가됐을 뿐, 기존 m개는 한 바이트도 안 바뀌었다"를 증명합니다.

일관성 증명의 핵심 아이디어: 두 트리의 공통 서브트리를 찾아, 그 서브트리가 두 루트 모두에 일관되게 묶인다는 것을 보입니다. 위 예에서 N(0123)는 m=4 트리의 루트이자, n=6 트리의 왼쪽 자식입니다. 이 노드 하나가 두 트리를 연결하는 증거가 됩니다.

crates/quipu-core/src/merkle_log.rs — prove_consistencypub fn prove_consistency(
    &mut self,
    first_size: u64,
) -> Result<ConsistencyProof> {
    let leaves = load(&self.path)?;
    let path = consistency_proof(&leaves, first_size as usize);
    Ok(ConsistencyProof {
        first_size,
        second_size: leaves.len() as u64,
        path,
    })
}

검증은 완전히 독립적

포함 증명과 일관성 증명 모두, 검증 함수는 로그를 전혀 보지 않습니다. verify_inclusion과 verify_consistency는 루트(들)와 증명 경로만 받아 순수하게 해시를 계산합니다:

crates/quipu-core/src/merkle.rs — verify_inclusion 서명pub fn verify_inclusion(
    leaf: &Hash,          // 검증할 레코드의 해시
    leaf_index: usize,   // 트리에서의 위치(0-based)
    tree_size: usize,    // 증명 당시 트리 크기
    proof: &[Hash],       // audit path (O(log n)개)
    root: &Hash,           // 공개·앵커된 루트 — 이것만 신뢰하면 됨
) -> bool

이 설계가 중요합니다. 외부 감사인은 Quipu-Log 서버에 접속하거나 데이터를 받을 필요 없습니다. 외부 앵커(22장)에서 루트를 가져와서, 증명 경로(서버가 생성)와 함께 이 함수를 돌리면 됩니다. RFC 6962를 구현한 어떤 언어의 코드도 호환됩니다.

MerkleLog가 노출하는 API

MerkleLog 구조체에서 증명을 요청하는 건 간단합니다:

crates/quipu-core/src/merkle_log.rs — 증명 요청 예시let mut log = MerkleLog::open(dir)?;
// 포함 증명: leaf_index #42번 레코드가 현재 트리에 있음을 증명
let p: InclusionProof = log.prove_inclusion(42)?;
assert!(verify_inclusion(&p.leaf, p.leaf_index as usize,
                         p.tree_size as usize, &p.path, &log.root()));

// 일관성 증명: first_size=1000일 때의 루트가 현재 트리의 접두사임을 증명
let c: ConsistencyProof = log.prove_consistency(1000)?;
assert!(verify_consistency(c.first_size as usize, c.second_size as usize,
                           &first_root, &log.root(), &c.path));

정리

• 포함 증명: 레코드 해시 + ⌈log₂ n⌉개 형제 해시 → 루트 재계산 → 루트 비교. 로그 전체 없이 O(log n)으로 존재 증명.
• 일관성 증명: 공통 서브트리 루트들 → 두 루트(과거/현재) 모두 재계산 → 둘 다 일치하면 append-only 증명.
• 검증 함수는 완전 독립 — 로그 없이, 루트와 증명만으로 동작. RFC 6962 표준이므로 외부 검증기 호환.
• 일관성 증명은 꼬리 절단 공격도 잡습니다.