协议演进 / BIP/比特币改进提案 / BIP-98

BIP-98 快速默克尔树

定义一种快速默克尔树：叶用双 SHA256、内节点改用单次特制 IV 的 fast-SHA256，免疫 CVE-2012-2459，建树与验证约快 55%，并支持任意不平衡树。本 BIP 目前处于草案状态。

一、档案卡

二、放在哪一族

默克尔树与包含证明（inclusion proof）族。比特币区块头对交易列表的承诺用的就是中本聪设计的默克尔哈希树；BIP-98 并不改动区块里现有的那棵树，而是为新协议定义一棵修掉老毛病的新树，供今后的应用共用同一套实现。

它最直接的下游是 BIP-116（MERKLEBRANCHVERIFY）：原文 Deployment 一节写明，BIP-116 拟以软分叉新增操作码把默克尔包含证明验证带进脚本，届时本 BIP 的内容将成为共识关键部分，部署计划由 BIP-116 承载。本 BIP 档案层级标注为 Consensus (soft fork)，正源于这一预期用途；它自身单独存在时，按原文 Compatibility 一节，不造成任何向后不兼容。

三、它要解决什么

3.1 重复条目漏洞 CVE-2012-2459

中本聪的默克尔树在元素个数为奇数时把最后一个元素复制一份再配对哈希，这使不同的交易列表可能算出相同的默克尔根，构成国家漏洞数据库登记的 CVE-2012-2459。协议与实现可以绕着防，但需要刻意设计，粗心的实现容易在下游埋雷。原文主张：新协议应从一开始就避开这棵有缺陷的树。

3.2 不必要的重复哈希开销

老构造对内节点用双 SHA256（double-SHA256），压缩轮次约为严格所需的 3 倍（针对性优化实现也要 2.32 倍）。新应用若无向后兼容包袱，不必再付这份性能税。

3.3 只能是平衡树

老算法从有序列表建索引，默认所有叶子到根路径等长的平衡树；而不少应用更适合不平衡树——让更常用的元素走更短的路径。老树虽有变通办法，但依赖树的规模、并不灵活。

四、规则本身

4.1 树的定义

BIP-98 的默克尔树是任意平衡程度的二叉树：不允许只有一个子节点的节点；叶子标签是数据的双 SHA256 哈希（数据格式不在本 BIP 范围内）；内节点标签是其两个子节点标签的 fast-SHA256 哈希，最顶的内节点标签即默克尔根。两个特例：空树不被允许、也没有定义根哈希；只有一个元素的树，根哈希直接等于该叶子的哈希本身（透传，不再哈希），以便把一条证明拆成多段链式验证时可用零长度路径占位。

4.2 fast-SHA256

fast-SHA256 只定义在两个 32 字节输入上：把两者拼成 64 字节，用改过的初始化向量（IV）、不做消息填充地跑一次 SHA-256，取其中间状态（midstate）为结果。效果是：算内节点比专用优化的双 SHA256 还快 2.32 倍，比朴素通用实现快约 3 倍；整体建树与验证时间较充分优化的老构造减少约 55%。因为输入恒为定长的哈希值，双哈希与填充要防的长度扩展类攻击在此不适用。改 IV 是为了防止“同一哈希既可解释为叶、又可解释为内节点承诺”的路径长度扩展攻击。该 IV 本身的来历写得很明确：取 23（第 9 个素数）平方根小数部分的前 512 位做标准 SHA-256 后提取中间状态，是一个无隐藏常数（nothing-up-my-sleeve）式构造；选 23 是因为 2 至 19 这些素数的小数位已用作 SHA-256 自身的常数，顺延取下一个以免常数复用。

4.3 包含证明的编码

证明一个或多个哈希属于某棵树，需要：根哈希、待验证的哈希、从根到目标节点的路径结构、以及路径外被略去分支的哈希。序列化格式：先以 VarInt 写内节点个数 N；再按深度优先、从左到右的先序遍历，把每个内节点的形态用 3 位编码打包（每侧分支可为 DESCEND 继续下探、SKIP 略过并附哈希、VERIFY 待验证，三三组合共 8 种，编码 000–111；两侧皆 SKIP 的第 9 种被禁止，因为它与直接 SKIP 其父节点等价，放行只会引入证明可锻性）；最后以 VarInt 写 SKIP 哈希个数并依次附上哈希。两个计数都必须与从树结构推得的数目一致，否则证明无效。原文附了一个 6 个内节点、3 个 SKIP 哈希的完整示例，序列化为 101 字节。

4.4 Fast Merkle Lists

附录给出从列表建规范平衡树的算法：先把每个元素换成其双 SHA256；列表为空返回零哈希；反复把相邻两项用 fast-SHA256 合并，奇数个时最后一项原样保留——正是这一“不复制”修掉了 CVE-2012-2459 的成因；剩最后一项即默克尔根。

五、谁必须动

普通持币人：无任何动作。本 BIP 不改变区块、交易或地址的现有规则。

钱包与应用开发者：只有在采用这棵新树的新协议里才需要实现它——按原文构造叶子与内节点哈希、按 3 位编码生成与校验包含证明；原文给出了参考实现（含 merklebranch 与 mergemerklebranch 两个 RPC）。

全节点与矿工：现阶段无需改动。仅当 BIP-116 这类以软分叉把它引入脚本验证的提案真正部署时，节点才需升级执行新规则。

共识层：本 BIP 单独不触碰共识；原文 Compatibility 一节明言它自身不造成向后不兼容。

六、现在算不算数，以及一个常见误读

状态为 Draft（草案）：它只是一份供新协议引用的数据结构规范，未被部署进比特币共识，区块头里承诺交易的仍是中本聪的原默克尔树。它的价值在于把“修好的树”标准化，避免每个新协议各造一棵、私下再踩 CVE-2012-2459。

常见误读：“BIP-98 要替换比特币区块的默克尔树，修掉 CVE-2012-2459。”不对。原文定位是给新应用的标准构造，老树在区块中的用法原样不动——替换它既不兼容也无必要；漏洞的实际防护多年来靠的是共识层面的其他检查。

七、延伸

• 阅读版：https://bips.dev/98
• 官方原文：https://github.com/bitcoin/bips/blob/master/bip-0098.mediawiki
• 相关：BIP-116 MERKLEBRANCHVERIFY
• 仓库总目录：https://github.com/bitcoin/bips

本页内容整理自 bitcoin/bips 仓库与 bips.dev，事实已与仓库核对；解读仅供学习参考。