Verkle Trees — 以太坊 Stateless 路线深度

日期: 2026-11-22 方向: 密码学 / 经典原语 阶段: Phase 4 - 经典密码学 (Day 195-208) 标签: #密码学 #Verkle #以太坊 #Stateless #EIP6800

---

今日目标

---

一、Verkle Tree 论文起源

1.1 历史脉络

• 2018: John Kuszmaul (MIT undergrad) 在论文 "Verkle Trees" 首次提出
• 2020: Vitalik 注意到 → blog post "Verkle trees" 阐述以太坊应用
• 2021-2024: PSE / EF Verkle team 设计 + 工程化
• 2025: Banderwagon 曲线选定（Pasta 系列改进）
• 2026: EIP-6800 主网激活（"The Verge"）

1.2 核心创新点

把 Merkle Tree 的"$\log n$ siblings × 32 B"换成"$\log_k n$ KZG/IPA proofs × 48 B" — 用更高分支因子 $k$（典型 256）+ vector commitment。

→ Witness size 从 ~$n^{0.5}$ 量级 → $\log_{256} n \cdot 48$ B（实测 3 MB → 200 KB，15× 缩小）。

---

二、以太坊 Verkle 路线图

2.1 当前 (Pre-Verkle) MPT 痛点

Modified Patricia Trie:

• 树高变化（基于 nibble，~8-9 levels for 全球地址空间）
• 每 leaf 需 ~6-9 节点 ÷ ~500 B / 节点 = 3 KB
• 1 block 触及 ~500 leaves → ~3 MB witness
• → Stateless client 不可行：每 block 同步 3 MB 是网络极限

2.2 Verkle 后

2.3 EIP-6800: Verkle Trie

主要更新:

1. State trie 从 MPT → Verkle
2. Account / storage 都用 32 B unified key
3. 移除 RLP encoding (节点结构改用 SSZ)
4. Block header 增 verkle root

实施: Hard fork，所有节点必须一次性迁移整个 state 到 Verkle。这是历史最大规模数据迁移（~ 1 TB）。

2.4 EIP-7864: Stateless Block Validation

Block 内含 witness（执行所需 state proof）→ 节点不需本地 state 也能验证。

→ 适合手机/RPi 节点：仅同步 block + witness ~200 KB / 12s = 17 KB/s 持续带宽。

2.5 The Verge (Vitalik's Roadmap 命名)

The Merge  - PoW → PoS (2022)
The Surge  - L2 / Sharding 扩展 (ongoing)
The Verge  - Verkle / Stateless (2026)
The Purge  - 历史数据修剪 (2027+)
The Splurge - 杂项升级

Verkle 是 The Verge 的核心。

---

三、Banderwagon 曲线

3.1 为什么不用 BLS12-381

BLS12-381 适合 pairing。Verkle 用 IPA (Halo accumulator)，不需 pairing → 用 pairing 友好曲线浪费。

需要的是:

• $\sim 254$ bit prime field (高效)
• ECDLP 安全 ~128 bit
• 标量域兼容 EVM 256-bit
• 子群清晰，无 cofactor 问题

3.2 Banderwagon = Bandersnatch + 修正

Bandersnatch (DLP twist of Jubjub on BLS12-381 scalar field):

• Field size: BLS12-381 scalar field $\approx 2^{255}$
• ECDLP 复杂度 $2^{127}$
• 但有 cofactor = 4 → 不全可靠

Banderwagon: 取 Bandersnatch 的 prime-order 子群（+ 编码规范），消除 cofactor 问题。

3.3 Verkle on Banderwagon

每节点 commitment = $\sum_{i} h_i \cdot G_i$ 在 Banderwagon 上（Pedersen vector commit）.

Open via IPA: $O(\log k)$ proof size per level.

256-ary tree 每层 IPA proof = $\log_2 256 \cdot 32 \cdot 2 = 512$ B(理论). 实测优化后 ~200 B / level.

---

四、Stateless Client 工作模式

4.1 节点角色分化

4.2 Witness 构造

Block builder:

1. 执行 block 找出所有 state read/write
2. 对触及的 leaf 提供 Verkle proof
3. 将 proof 嵌入 block

Verifier:

1. 从 witness 重建虚拟 state subtree
2. 执行 block 在该虚拟 state 上
3. 验证最终 verkle root 与 block header 一致

4.3 Witness Size 估算

平均 block 触及:

• ~150 unique leaves (account + storage)
• 每 leaf 约 1 个 Verkle inclusion proof: 4 levels × 200 B = 800 B
• 但路径共享 → 实际 ~150 × 200 B = 30 KB minimum
• • 路径节点 commitments (~50 KB)
• 总 witness: ~150-300 KB / block

---

五、Verkle 节点结构

5.1 Internal Node

class VerkleInternal:
    children_commitments: List[bytes]  # 256 banderwagon points (compressed 32 B)
    commitment: bytes  # Pedersen commit to children

commitment = Σ_{i=0..255} hash_to_field(children_commitments[i]) * G_i

5.2 Leaf Node ("Suffix tree")

实际叶子用 "stem + suffix" 优化:

• Stem: 31-byte 前缀（决定路径）
• 每 stem 下挂 256 个 32-byte values (suffix 0-255)
• 对每 stem 用 1 个 commit 含 256 个 values

class VerkleLeaf:
    stem: bytes  # 31 bytes
    values: List[bytes]  # 256 entries of 32 B
    c1: Point  # commit to values[0..127]
    c2: Point  # commit to values[128..255]
    commitment: Point  # commit to (1, stem, c1, c2)

5.3 Address Mapping

EVM address (20 B) + storage slot (32 B) → 32 B Verkle key:

key[0..30] = stem (mostly hash of account + slot prefix)
key[31] = suffix (0..255)

存放规则:

• stem || 0: nonce
• stem || 1: balance
• stem || 2: code_keccak
• stem || 3: code_size
• stem || 64-127: code chunks (31 B each)
• stem || 128-255: storage slots (paired by hash)

→ 一个 account 的所有数据集中在 1 stem，common access 路径短。

---

六、代码骨架 — 简化 Verkle

"""
verkle_demo.py - 极简 256-ary Verkle Tree 概念演示
真实 Eth 实现在 go-ethereum / verkle/go-verkle 中
"""
import hashlib
from py_ecc.bls12_381 import G1, multiply, add, curve_order

def hash_to_scalar(data: bytes) -> int:
    return int.from_bytes(hashlib.sha256(data).digest(), 'big') % curve_order

class VerkleNode:
    K = 256  # branching factor

    def __init__(self):
        self.children = {}  # idx -> VerkleNode or leaf bytes
        # generators (in real impl: from setup ceremony)
        self.gens = [multiply(G1, i + 1) for i in range(self.K)]
        self.commitment = None

    def insert(self, key: bytes, value: bytes, depth: int = 0):
        if depth == 31:  # leaf level
            # final byte selects within 256 suffixes
            self.children[key[31]] = value
        else:
            idx = key[depth]
            if idx not in self.children:
                self.children[idx] = VerkleNode()
            child = self.children[idx]
            if isinstance(child, VerkleNode):
                child.insert(key, value, depth + 1)
            else:
                # collision: turn into subtree
                pass
        self._compute_commitment()

    def _compute_commitment(self):
        c = None
        for i in range(self.K):
            child = self.children.get(i)
            if child is None:
                continue
            if isinstance(child, VerkleNode):
                h = hash_to_scalar(self._serialize_point(child.commitment))
            else:
                h = hash_to_scalar(child)
            c = add(c, multiply(self.gens[i], h))
        self.commitment = c

    def _serialize_point(self, pt) -> bytes:
        if pt is None:
            return b'\x00' * 32
        return int(pt[0]).to_bytes(48, 'big')[:32]  # toy compression

    def prove(self, key: bytes, depth: int = 0) -> list:
        """Returns list of (commitment, opening_proof) per level."""
        # in real impl: use IPA / KZG opening at idx position
        proofs = []
        if depth == 31:
            return [(self.commitment, key[31], self.children.get(key[31]))]
        idx = key[depth]
        proofs.append((self.commitment, idx, "<IPA proof opening at position idx>"))
        child = self.children.get(idx)
        if isinstance(child, VerkleNode):
            proofs.extend(child.prove(key, depth + 1))
        return proofs

# Demo
if __name__ == "__main__":
    tree = VerkleNode()
    for i in range(100):
        key = hashlib.sha256(f"key_{i}".encode()).digest()
        tree.insert(key, f"value_{i}".encode())
    print(f"Verkle root commitment: {tree._serialize_point(tree.commitment).hex()}")
    target_key = hashlib.sha256(b"key_42").digest()
    proof = tree.prove(target_key)
    print(f"Proof has {len(proof)} levels")

---

七、Verkle 工程挑战

7.1 State 迁移

现有 ~ 1 TB MPT state 需在硬分叉一次性迁成 Verkle. 选项:

• Big bang: hard fork 一夜完成（不切实可行）
• Overlay tree (主流方案): 新交易写 Verkle，老 state 后台逐步迁移，最终切换 root

EIP-7732 "Overlay-tree"（讨论中）: 区块同时含 MPT + Verkle 两 root，迁移期内并存。

7.2 EVM Gas Cost

Verkle 验证比 MPT 验证慢:

• 每 leaf 访问 ~100k gas (vs 现 ~2k)
• 影响 Smart contract 设计：随机 storage access 变贵

→ EIP-2935 (BLOCKHASH 替代) 等先行铺垫。

7.3 Witness 生成成本

Block builder:

• MPT: 简单 hash
• Verkle: 大量 EC scalar mul + IPA opening
• 预估 ~1-3 sec / block on commodity hardware

→ 专业 builder 必要 (Flashbots / Titan)；普通节点不构建 block.

7.4 客户端复杂度

每个客户端需:

• Banderwagon EC implementation
• IPA prover/verifier
• Verkle trie data structure
• State migration tooling

Geth/Reth/Erigon 实现进度:

• Geth: 实验 fork (verkle branch)
• Reth: native impl (Rust)
• Erigon: planned

---

八、Verkle 安全性

8.1 IPA Soundness

依赖 ECDLP on Banderwagon:

• 知识论证 (knowledge soundness): 攻击者可生成 "valid-looking" proof 当且仅当解 ECDLP
• 标准 Forking Lemma 论证

8.2 Cryptographic Agility

EIP-6800 设计可升级到不同 PCS（KZG / IPA / FRI）。当前选 IPA 因为:

• 无 trusted setup
• proof size $O(\log k)$ 实践上可接受
• 后期可升级 KZG 进一步缩小

8.3 Migration Risks

State 迁移期间:

• 新旧 root 并存 → 兼容性测试覆盖
• Hash 函数变更 (Keccak → Pedersen) → 完整重新计算
• 失败可能性: 低，但影响巨大 (~1 TB 数据)

---

九、协议应用 / 影响

---

十、其他链的 Verkle / VC 状态

---

十一、关键资源

• Vitalik blog: "Verkle Trees"
• John Kuszmaul 论文: "Verkle Trees" (2018)
• EIP-6800: Verkle Trees
• EIP-7864 (overlay): Stateless Witness
• Banderwagon paper (Lubarov, 2022)
• go-verkle: github.com/ethereum/go-verkle
• rust-verkle: github.com/crate-crypto/rust-verkle
• Dankrad Feist talks at EthCC / Devcon

---

十二、面试题

Q1: 为什么以太坊 Verkle 选 Banderwagon 而非 BLS12-381？ A: BLS12-381 是 pairing-friendly 但 pairing 慢且复杂。Verkle 用 IPA 而非 pairing-based commit，所以不需 pairing-friendly 曲线。Banderwagon 是 BLS12-381 scalar field 上的 elliptic curve，提供:

• 与 EVM 256-bit field 兼容
• 快速 scalar mul（无 pairing 开销）
• Prime-order group（无 cofactor 陷阱）

Q2: Verkle witness 真能从 3 MB 缩到 200 KB？ A: 是的，理论 + 实测都支持。原理:

• 分支 16 → 256 让 depth 从 ~8 → ~4
• 每层 KZG/IPA proof 替代 ~16 个 sibling hashes
• 路径共享: 多 leaf 在同子树共享上层 proof

实测 (Devnet): 平均 block witness 250 KB. Worst-case 1 MB（特殊合约扫所有 storage）。

Q3: Stateless client 真的可行吗？ A: 技术上可行，但有挑战:

• 200 KB / 12s = 17 KB/s 网络（手机/RPi 都 OK）
• 但 witness 验证 CPU 消耗 ~100 ms / block —— 占 12s 的 1%
• 主问题: block builder 中心化（必须有全 state）→ 用户运行的"verifier"无法 mempool 操作

折中: 大多数节点 stateless，少数 builder + RPC 全节点。

Q4: Verkle 后量子安全吗？ A: 否。IPA / KZG 都依赖 ECDLP / pairing，量子下 Shor 算法多项式时间破。

PQ 替代选项:

• FRI-based VC (Reed-Solomon distance)
• Hash-based commit (Merkle, but 后量子下 Grover 让 256-bit hash 变 128-bit)

Eth 长期路线: Verkle (现) → STARK-friendly state tree (PQ 时代)。

Q5: Verkle vs Plasma / state channels 对扩展的贡献区别？ A: 不同维度:

• Plasma / channels: 链下扩展 → 减少链上数据
• Verkle: 链上数据结构优化 → 减少证明大小

二者互补。Eth 现路线: L2 (Plasma 类) 处理 throughput，Verkle 处理"全节点门槛"。

---

十三、明日预告

Day 206: 后量子签名 — 切换到 PQ 世界。NIST PQC 标准 (Dilithium, Falcon, SPHINCS+) 概览，Lattice 困难问题 (LWE/SIS)、Hash-based 签名、Web3 PQ 路线。