Vector Commitment — Merkle vs KZG vs Verkle 对比

日期: 2026-11-21 方向: 密码学 / 经典原语 阶段: Phase 4 - 经典密码学 (Day 195-208) 标签: #密码学 #VectorCommitment #KZG #Merkle #Verkle

---

今日目标

---

一、Vector Commitment (VC) 形式化

1.1 定义

VC 承诺一个向量 $\vec{m} = (m_1, ..., m_n)$，支持位置打开:

Commit(vec) → C
Open(vec, i) → π_i        # proof for position i
Verify(C, i, m_i, π_i) → bool

1.2 安全性质

• Position Binding: 不能在同位置 $i$ open 出两个不同 $m_i, m_i'$
• Hiding (可选): $C$ 不泄漏 $\vec{m}$
• Subvector Opening: 一个 proof 同时 open 多个位置 (size $< $ 总和)
• Updatability: 改变某 $m_i$ 后能高效更新 $C$ 和 $\pi_j$ (advanced)

1.3 用途

• Stateless clients: 区块链状态承诺，节点不存储全部状态，只验证 proof
• Database commitments: 验证查询结果属于已发布的数据库
• Authenticated data structures: Certificate Transparency 等

---

二、三类 Vector Commitment 构造

2.1 Merkle-based VC

结构: 二叉哈希树。

Commit:    C = root of Merkle tree
Open(i):   π = sibling hashes along path from leaf i to root
Verify:    re-hash from leaf along π to root, check == C

性能:

• C size: 32 B
• Proof size: $\log_2 n \cdot 32$ B (n=$2^{20}$ → 640 B)
• Verify: $\log_2 n$ hash ops
• Subvector opening (k items): $k \log n$ hashes 但有重叠优化 → $O(k \log(n/k))$
• No trusted setup ✓
• Post-quantum ✓ (仅 hash)

2.2 KZG-based VC

核心: 把向量编码为多项式 $p(X) = \sum_i m_i \cdot L_i(X)$ where $L_i$ is Lagrange basis at root of unity $\omega^i$.

Commit:    C = p(τ) g₁  (1 G1 element)
Open(i):   π = q_i(τ) g₁ where q_i(X) = (p(X) - m_i) / (X - ω^i)
Verify:    e(C - m_i G, G₂) = e(π, τG₂ - ω^i G₂)

性能:

• C size: 48 B (BLS12-381)
• Proof size: 48 B (constant!)
• Verify: 1 pairing
• Subvector opening (k items): 1 G1 with batch trick (single 48 B!)
• Trusted setup needed
• Post-quantum ✗

2.3 Verkle-based VC (vector commitment tree)

结构: 类 Merkle 树，但每个节点有 $k$ 子节点（如 256 或 1024），用 KZG / IPA 承诺 $k$ 个子节点的 hash。

节点 = VC([child_1, ..., child_k])
Open: 沿路径每层提供 1 个 KZG proof（48 B）

性能:

• C size: 48 B
• Proof size: $\log_k n \cdot 48$ B (n=$2^{20}$, k=256 → 3 层 × 48 B = 144 B)
• 比 Merkle 节省 80%+ proof size
• Verify: $\log_k n$ pairings
• Trusted setup needed (KZG variant)

---

三、KZG-VC 详细数学

3.1 Lagrange 基

设 evaluation domain ${ \omega^0, \omega^1, ..., \omega^{n-1} }$ 是 $n$-th root of unity 子群。

定义多项式 $p(X)$ 满足 $p(\omega^i) = m_i$: $$p(X) = \sum_{i=0}^{n-1} m_i \cdot L_i(X)$$ $$L_i(X) = \prod_{j \ne i} \frac{X - \omega^j}{\omega^i - \omega^j}$$

FFT 友好: 用 IFFT 从 $(m_0, ..., m_{n-1})$ 计算 monomial coeffs $O(n \log n)$.

3.2 单点 Open

要 open position $i$:

• $y = m_i = p(\omega^i)$
• $q(X) = (p(X) - m_i) / (X - \omega^i)$
• $\pi = q(\tau) g_1$ — 1 G1 element

3.3 多点 Open (subvector)

要 open positions $S = {i_1, ..., i_k}$:

• Vanishing poly $Z_S(X) = \prod_{i \in S} (X - \omega^i)$
• Interp poly $I(X)$ s.t. $I(\omega^i) = m_i$ for $i \in S$
• $q(X) = (p(X) - I(X)) / Z_S(X)$
• $\pi = q(\tau) g_1$ — 仍 1 G1 element!

Verifier: $$e(C - I(\tau) g_1, g_2) = e(\pi, Z_S(\tau) g_2)$$

但 verifier 必须自己计算 $I(\tau) g_1$ 和 $Z_S(\tau) g_2$ — 需要扩展 SRS（toxic waste 的不同元素）。

3.4 Updatability

修改 $m_i \to m_i'$: $$C' = C + (m_i' - m_i) \cdot L_i(\tau) g_1$$

需要 $L_i(\tau) g_1$ 预计算（来自 SRS）。$O(1)$ 更新。

---

四、Verkle Tree 数学

4.1 设计动机

Eth 现有 MPT (Modified Patricia Trie) 的 witness:

• Witness size: 平均 ~3 MB / block
• 阻碍 stateless client

Verkle 用 KZG vector commit 让 witness 缩小到 ~200 KB.

4.2 树结构

每节点: KZG commitment 到 256 子节点 hash (or 1024).

Root commit
  ├── 256 children, each: KZG commit to 256 grandchildren
  │     └── ...
  └── ...

depth = $\log_{256} n$. n=$2^{40}$ ≈ 1 万亿 → depth 5.

4.3 Witness 大小

每层 1 个 KZG proof ≈ 48 B + 一些辅助数据。 5 层 × ~100 B = ~500 B / leaf access.

vs MPT: 5 层 × ~500 B (含 RLP 编码) = ~2.5 KB / leaf.

5× 节省，多个 access 共享路径时节省更多 (50× 实测)。

4.4 Multi-proof Aggregation

多个 leaf 的 proof 在同 commitment 上可聚合（基于 KZG 多点 open）:

$$\pi_{\text{agg}} = q_{\text{combined}}(\tau) g_1$$

整个 block witness ≈ 1 个 KZG proof + 路径节点 hashes.

---

五、Inner Product Argument (IPA) variant

无 trusted setup 的 Verkle 风格树（"Verkle-IPA"）:

• Banderwagon / Pasta 曲线
• Proof size $O(\log n)$ (vs KZG 的 $O(1)$)
• 但 verify $O(n)$ → 实际通过 Halo accumulator 减摊

Eth 早期讨论 Verkle 用 IPA 还是 KZG，最终倾向 KZG（Eth 2024 Verkle 路线）。

---

六、对比表 — vc_compare.md 主体

# Vector Commitment 方案对比

## 1. 总体对比

| 方案 | C size | Proof size | Verify | Open | Update | Setup | PQ |
|------|--------|-----------|--------|------|--------|-------|-----|
| Merkle (binary) | 32 B | 32 log n B | log n hash | log n hash | log n hash | None | ✓ |
| Merkle (k-ary) | 32 B | 32 (k-1) log_k n B | (k-1)log_k n hash | log_k n | similar | None | ✓ |
| Verkle (KZG) | 48 B | 48 log_k n B (k=256: 3 levels × 48) | log_k n pairings | k mul | O(k) per level | Trusted | ✗ |
| Verkle (IPA) | 48 B | log n × 48 B | log n × MSM | similar | similar | None | ✗ |
| KZG flat | 48 B | 48 B (constant!) | 1 pairing | O(n log n) MSM | O(1) | Trusted | ✗ |
| Bulletproofs | 48 B | 2 log n × 48 B | O(n) MSM | O(n) | hard | None | ✗ |
| FRI flat | 32 B (Merkle) | log² n × 32 B | log² n hash | similar | hard | None | ✓ |

## 2. 实测数据 (n=2^20 = 1M items)

| 方案 | C | π single | π 100-batch | Verify single |
|------|---|---------|-------------|--------------|
| Merkle binary | 32 B | 640 B | 25 KB | 50 μs |
| Merkle 16-ary | 32 B | ~1.5 KB | ~80 KB | 100 μs |
| KZG flat | 48 B | 48 B | 48 B (single proof) | 3 ms |
| Verkle (256-ary, KZG) | 48 B | ~150 B | ~300 B (with path sharing) | ~10 ms |
| Verkle (256-ary, IPA) | 32 B | ~3 KB | ~10 KB | ~50 ms |

## 3. 应用场景决策树

需要 Vector Commitment? ├── 不接受 trusted setup │ ├── 后量子安全 → Merkle / FRI │ └── 接受 ECDLP → IPA / Bulletproofs │ ├── 接受 trusted setup │ ├── 极小 proof + 数据扁平 → KZG flat │ ├── 树形数据 + 多次 open → Verkle (KZG) │ └── ZK rollup 状态 → IPA Halo accumulator │ └── 区块链状态树 ├── 当前 (Eth) → MPT (Merkle) ├── 未来 (Eth) → Verkle (KZG-based) └── ZK rollups (zkSync, Polygon zkEVM) → MPT or SMT

## 4. KZG vs Merkle 详细比较

### Proof Size (n=$10^8$ leaves)

| 方案 | 单 leaf | 100 leaves |
|------|--------|------------|
| Merkle (binary) | 27 levels × 32 B = 864 B | 86 KB (with sharing 35 KB) |
| Merkle (16-ary) | 7 levels × 480 B = 3.4 KB | 200 KB |
| KZG flat | 48 B | 48 B (single batch proof) |
| Verkle (256-ary, KZG) | 4 levels × 48 B + ... ≈ 250 B | ~600 B |

### Verifier Cost

| 方案 | 1 query | 100 queries |
|------|--------|-------------|
| Merkle (binary) | 27 hashes ≈ 5 μs | 500 μs |
| KZG flat | 1 pairing ≈ 3 ms | 3 ms (1 batch) |
| Verkle (256, KZG) | 4 pairings ≈ 12 ms | 50 ms (with batching) |

### Prover Cost

| 方案 | Setup time | Build tree | Single open |
|------|-----------|------------|-------------|
| Merkle | 0 | $O(n)$ hash | $O(\log n)$ |
| KZG flat | $O(n)$ MSM | n/a (poly direct) | $O(n)$ MSM (FFT trick) |
| Verkle (KZG) | $O(k \cdot n/k)$ | $O(n)$ MSM | $O(k)$ per level |

## 5. 代码骨架: 多种 VC

### Merkle (已在 Day 197 实现)

```python
def merkle_open(leaves, i):
    siblings = []
    idx = i
    layer = [hash_leaf(l) for l in leaves]
    while len(layer) > 1:
        siblings.append(layer[idx ^ 1])
        idx //= 2
        layer = [hash_node(layer[2*j], layer[2*j+1]) for j in range(len(layer)//2)]
    return siblings

KZG VC

# 1. encode vector as Lagrange poly p
# 2. C = commit(p) via KZG SRS
# 3. open at ω^i for vector position i
def kzg_vc_open(p_coeffs, omega_i, srs):
    y = poly_eval(p_coeffs, omega_i)
    q = poly_div_by_X_minus_z(p_coeffs, omega_i, y)
    return y, srs.commit(q)

Verkle (256-ary)

class VerkleNode:
    children: list  # 256 children
    commitment: tuple  # KZG commit to children hashes

def verkle_open(node, path, srs):
    """Path is sequence of 256-ary indices."""
    proofs = []
    cur = node
    for p in path:
        # KZG open at the position p in this node's commitment
        proof = kzg_open(cur.commitment, ω^p, child_hash[p])
        proofs.append(proof)
        cur = cur.children[p]
    return proofs

6. 安全性论证

Merkle: 抗碰撞 hash 假设

• 攻击者要 open 不同 $m_i$ 需找哈希碰撞 → SHA-256 抗 $2^{128}$ 安全

KZG: q-SDH (q-Strong Diffie-Hellman)

• 同前一日所述
• 依赖 trusted setup τ 销毁

Verkle (KZG): 同 KZG + 树结构 binding

• 每层 KZG binding 防伪造单层 → 复合 binding

7. 何时选哪个？

选 Merkle 当:

• 需要无 trusted setup
• 后量子需求
• Proof size 不是瓶颈
• 简单实现优先 (审计友好)

选 KZG flat 当:

• 数据扁平 (vector, not tree)
• 极小 proof 关键 (链上)
• 接受 trusted setup
• 已有 ceremony (Eth 4844)

选 Verkle (KZG) 当:

• 树形数据，频繁 access
• Stateless client (Eth roadmap)
• Proof size 缩小至关重要

选 IPA (Halo2) 当:

• 不接受 trusted setup
• 用 recursive ZK 摊销 verifier 成本

---

## 七、真实事件 / 路线图

| 项目 | 状态 (2026) | 说明 |
|------|-----------|------|
| Eth Verkle EIP-6800 | 已实现，主网激活待 | "The Verge" 升级 |
| Polygon zkEVM state | 仍 MPT (Merkle) | 升级中 |
| Mina state | 用 IPA Halo accumulator | 22 KB 链全压缩 |
| Aleo | 用 KZG-based commitment | Marlin SNARK |
| Filecoin | Merkle (Sector trees) | 后量子兼容 |

---

## 八、协议应用速查

| 应用 | 推荐 VC |
|------|--------|
| Eth state (现) | MPT (Merkle) |
| Eth state (未来) | Verkle (KZG) |
| Eth blob (4844) | KZG flat |
| Optimistic rollup data | Merkle (DA-friendly) |
| ZK rollup state | KZG / IPA (depending on SNARK) |
| Stateless light client | KZG / Verkle (proof size 关键) |
| Tornado Cash anonset | Merkle (Pedersen hash) |
| zkBridge | KZG / Halo accumulator |
| L2 inclusion proofs | Merkle |

---

## 九、常见陷阱

1. **Trusted setup 长度不足** — KZG SRS 必须 ≥ vector length
2. **Lagrange ≠ Monomial** — KZG 用哪种多项式表示影响 commit 计算
3. **Domain mismatch** — root of unity 阶必须 = n
4. **Position binding 缺失** — 单纯 Pedersen vector commit 不能 open 单分量
5. **Subvector proof 实现错误** — vanishing poly $Z_S$ 计算复杂，易错
6. **Verkle 节点更新成本** — 修改一 leaf 影响 path 上所有 commitment，每层 1 个 EC op，但仍可 batch
7. **Merkle 二次原像** — domain separation 不到位
8. **Cross-chain VC mismatch** — 不同链用不同 VC 类型，桥接复杂

---

## 十、面试题

**Q1: Verkle 比 Merkle 节省多少？**
A: 主要在 proof size。256-ary Verkle 在 n=$10^8$ 时 proof ~250 B vs Merkle ~3 KB → 12× 节省。Eth witness 实测从 3 MB → 200 KB 是 15× 缩小。代价: pairing 验证比 hash 慢 10×，但 witness 减小让 stateless client 网络通信瓶颈解除（worth it）。

**Q2: KZG flat 为什么不直接用作以太坊 state？**
A: 状态约 1 万亿 leaf。KZG flat 需要 SRS 长度 ≥ n → 1 trillion G1 points × 48 B = 50 TB 的 SRS。不可行。Verkle 树形分摊每节点只需 256 长度 SRS，且 SRS 可重用。

**Q3: Verkle 影响 Geth 性能？**
A: (1) Proof verification 从 hash → pairing → 慢 10×; (2) State write 每次需 update 路径上所有 KZG commitment → 重 EC ops; (3) 但 witness 缩小让 sync 时网络/磁盘 IO 减少 → net positive 在 stateless 模式. (4) 升级前需要全网 state migration（巨大 ceremony）。

**Q4: 多次 open 同一 commitment 时 Merkle vs KZG 的优势？**
A: 
- Merkle: 多 leaf proof 共享路径，节省 ~$\log(n/k)$ 因子
- KZG: 多个位置 open 仍只 1 个 G1 (subvector batch) — 完美零开销
- 决策: 大批 open (k > log n) → KZG 完胜; 少数 open → Merkle 更简单

**Q5: 为什么 Eth 4844 选 KZG flat 而 state 选 Verkle？**
A: 用例不同。Blob 是 128 KB 的扁平数据 → flat KZG 完美 (4096 标量 → 1 commit 48 B)。State 是层级 trie → Verkle (KZG-tree) 适合，因为每节点 256 子用一个 commit 即可，proof 沿路径走。同样的 KZG 设施 (BLS12-381 ceremony) 复用。

---

## 十一、明日预告

**Day 205: Verkle Trees** — 深入以太坊 Verkle 升级路线图、stateless client 设计、EIP-6800 / EIP-7864 细节、对 Geth/Reth/Erigon 实现的影响。阅读 Verkle 论文 + Vitalik 博客深度分析。