Merkle Trees：区块链如何记住每一张 Note

来自 Annkkitaaa 的原创研究

用一个微小的指纹概括数百万个 commitment

系列： Zcash from First Principles 。第 4 篇 . Merkle Trees 读者对象： 新手。本文建立在第 3 篇（哈希与 commitment）之上。如果你知道什么是指纹、什么是 commitment，那你已经准备好了。 你将收获： 对 Merkle tree 的直观且准确的理解，了解如何在不暴露你指的是哪一项的情况下证明成员资格，以及它究竟如何成为 Zcash 的 note commitment tree。

第 0 篇描述了一个“公共公告板”，它保存着每一张曾被创建的 note，并且只会不断增长。到现在你应该能猜到上面钉着的是什么：commitment（第 3 篇），也就是那些密封的信封。但现实中的公告板会容纳数亿个这样的 commitment。网络如何存储它、验证它，并让你在不指向自己那一个的前提下证明你的信封确实在板上？答案是计算机科学中最优雅的结构之一：Merkle tree。

1. 为什么你需要关心它？

一旦你有了一张巨大的公开 commitment 列表，立刻会出现两个问题。

第一个问题：大规模完整性。 如果列表有 3 亿个条目，任何人要如何确认一个都没有被悄悄篡改？每看一次都重新检查 3 亿项，显然不现实。

第二个问题：私密成员资格。 要花费一张 note（第 0 篇），你必须证明你的 commitment 真的在这张公告板上。但如果你直接指给别人看（“它是第 4,201,337 项！”），你就等于把自己去匿名化了。你需要证明的是：“我的信封就在这张公告板上的某个地方”，而不暴露到底是哪一个。

Merkle tree 可以同时解决这两个问题。它把整张列表压缩成一个单独的指纹，并让你用一个很小、还能隐藏位置的证明来证明成员资格。

2. 直觉理解：一场指纹锦标赛

把它想象成一个淘汰赛对阵图，只不过晋级的不是选手，而是指纹被合并。

• 在最底层，每一份数据都有自己的指纹（也就是第 3 篇里的 hash）。这些是叶子。
• 把它们两两配对。每一对的两个指纹会被一起哈希成一个父指纹。
• 再把这些父节点两两配对，把每一对一起哈希。
• 持续这样做，直到顶部只剩下一个指纹。这个冠军就是Merkle root。

最重要的性质直接来自雪崩效应（第 3 篇）：

这个 root 是它下方所有内容的指纹。 只要任何一个叶子发生变化，哪怕只改动 1 bit，它的指纹就会变化，进而改变它的父节点，再改变那个父节点，一路向上传递。root 会变。 所以一个很小的 root 值，就能证明整张列表的完整性。这就解决了第一个问题。

3. 一棵真实的树，精确计算出来

我们用实际的 SHA-256 指纹，把上面这棵有四个叶子的树搭出来。叶子分别是 A, B, C, D（为便于阅读，digest 做了截断）：

hA = 559aead08264...     hB = df7e70e50215...
hC = 6b23c0d5f35d...     hD = 3f39d5c348e5...

hAB = H(hA , hB) = 63956f0ce48e...
hCD = H(hC , hD) = 98a2fbfddbc7...

ROOT = H(hAB , hCD) = 1b3faa3fcc5e...

本质上就是“先哈希单个东西，再对哈希值成对哈希”。没有比第 3 篇更奇特的东西，只是把它排成了一棵树。

4. 巧妙之处：在不暴露位置的情况下证明成员资格

现在来看第二个问题。假设你想向一个只知道root的人证明叶子 C 在这棵树里。你不会把整棵树都交给他。你只需要给出从 C 走到 root 所需的那些指纹，这叫做authentication path（或 Merkle proof）：

要证明 C 在树中，需要提供：

• 它的兄弟节点 hD，以及
• 它的叔叔节点 hAB。

验证者只知道 root，但他可以重新计算这条上升路径：

step 1:  H(hC , hD)        = hCD       (将 C 与它的兄弟节点合并)
step 2:  H(hAB , hCD)      = ROOT?     (再与叔叔节点合并)

实际算出来，这会得到 1b3faa3fcc5e...，它与 root 匹配。 于是这个叶子被证明确实在树中。

这之所以强大，有两个原因：

• 它很小。 对 4 个叶子，你只提供了 2 个 hash。对一棵有 n 个叶子的树，你只需要提供大约 log_2(n) 个 hash。对于 10 亿个叶子，大约也只是 30 个 hash，而不是 10 亿个。即使树膨胀得极大，证明也几乎不会变大。
• 它是隐私的种子。 这个证明表明你的叶子在树中的某个地方。当同样的检查是在zero-knowledge proof 内部完成时（第 5 篇），连这条路径本身也会被隐藏，所以你能证明“我的 note 在这棵树里”，同时既不暴露这张 note，也不暴露它的位置。这样就彻底解决了第二个问题。

5. 从 Merkle tree 到 Zcash 的 note commitment tree

现在我们可以精确说明第 0 篇中的“公共公告板”到底是什么：

note commitment tree 就是一棵 Merkle tree，它的叶子是 note commitments。 每当世界上任何地方创建了一张 note，它的 commitment 就会被追加为下一个叶子，而 root 也会随之更新。

再补充几个真实的细节：

• 它只会增长。 叶子只会被追加，永不删除。这叫做incremental Merkle tree。（它正好对应第 0 篇里的“公告板从不撕下任何东西”。）
• 这个 root 被称为 anchor。 当你花费时，你的交易会引用一个最近的 anchor，并以零知识方式证明你的 note commitment 位于具有该 root 的树中。
• 固定深度。 Zcash 的 shielded 树深度为 32，这意味着它们最多可以容纳 2^(32)（超过 40 亿）张 note。
• 对 ZK 友好的哈希。 这棵树并不是用 SHA-256 构建的。Sapling 用 Pedersen hashes 来对树进行哈希，Orchard 使用 Sinsemilla（两者都见第 3 篇），原因正是这样可以让成员资格路径的计算在电路内部被低成本地证明。

树不能处理的一件事：双花

这棵树能证明一张 note 存在。但仅靠它本身，不能阻止你把同一张 note 花两次。这个工作属于第 0 篇中的 nullifier set：它是一个独立的“作废令牌”集合。当你花费时，你会公布这张 note 的 nullifier，而网络会拒绝任何它之前见过的 nullifier。

所以，这两个公共结构扮演的是互补角色，而将它们分开，正是切断一张 note 的诞生与死亡之间联系的关键：

6. 一个诚实的说明

和往常一样，这里做了简化。真实的 incremental Merkle trees 会跟踪“frontier”节点，这样就能在不重建整棵树的情况下更新 root；网络保存的是一段最近的 anchor 窗口，而不只是最新那个，这样钱包就不会因为每产生一个新区块就失效；空叶子也会使用一个定义好的填充值。我们还画了整齐的、叶子数是 2 的幂的二叉树。但这些都不改变核心直觉：commitment 作为叶子，两两哈希，直到得到一个 root，并用简短的成员资格证明来验证。协议篇会回到这些精确的实现细节。

7. 总结

• Merkle tree 会先把数据哈希成叶子，然后把成对的节点向上哈希，直到只剩一个root。
• 借助雪崩效应，root 是整张列表的指纹：只要改动一个叶子，root 就会变化。一个很小的值，就能认证一个巨大的数据集。
• 成员资格证明（authentication path） 本质上只是通向 root 路径上的那些兄弟节点，大约需要 log_2(n) 个 hash，因此即使叶子达到数十亿，证明仍然很小。
• 当它在zero-knowledge proof 内部执行时，这个成员资格检查会隐藏你指的是哪个叶子，从而证明“我的 note 在这棵树里”，而不暴露这张 note 或它的位置。
• Zcash 的 note commitment tree 是一棵由 note commitments 组成的incremental Merkle tree，深度为 32，其 root 称为 anchor；Sapling 用 Pedersen 对其哈希，Orchard 用 Sinsemilla。
• 这棵树证明的是存在性；而独立的 nullifier set 用来防止双花。把它们分开，正是让一张 note 的诞生与死亡脱钩的原因。

术语表

常见问题

为什么要用树，而不是一长串 hash 列表？
平铺的列表会迫使你为了证明成员资格而暴露或处理每一个条目。树则给你对数级大小的证明，以及一个用于完整性校验的单一 root。

验证者需要整棵树吗？
不需要。验证者只需要root加上你那条简短的 authentication path。这正是重点所在。

为什么深度偏偏是 32？
因为这会把树的容量限制在大约 40 亿张 note 左右，空间非常充足，同时还能让成员资格证明（以及它在电路中的成本）保持为一个固定且可控的大小。

如果每增加一张新 note，root 都会变化，那旧证明如何继续有效？
网络会记住最近一段 root（anchors）窗口，所以即使证明是针对一个稍旧的 anchor 制作的，仍然可以通过验证。协议篇会把这件事讲精确。

测试一下你的直觉

在我们那棵 4 叶子树里，假设攻击者偷偷把叶子 C 换成了另一个值，但又让已公布的 root 保持不变。对他来说哪里会出问题？为什么他无法悄悄修复它？（答案见下方。）

接下来是什么

第 5 篇 . Zero-knowledge proofs： 渐入高潮。现在我们已经构建了 notes、commitments 和这棵树，而且一直在说“以零知识方式证明”。第 5 篇终于会解释，你如何能够证明一个陈述为真：你的 note 在树中、你的 nullifier 是正确的、资金是平衡的，同时又不泄露其中任何信息。

这是为 ZecHub 撰写的 Zcash from First Principles 系列的一部分。采用 CC BY-SA 4.0 许可。