稀疏Merkle树

普通列表树中，“没有看见键k”不代表k没藏在其他叶里。稀疏树先给每个键分配唯一地址：k只能在这个位置。于是证明“不存在”，就变成证明“这一个位置为空”。

逻辑树可以非常大，实际保存却不必铺开。连续的空地只需要标一句“这整片与高度j的默认空子树相同”。默认值不是任意零串，而是依照相同哈希规则递归算出的真实摘要。

三位键中的空位010 ​

取h=3，写入 001 → red 与 110 → blue，其他位置为空。证明010不存在：从空叶开始，兄弟依次是011的空叶、覆盖000与001的子树、覆盖100至111的子树。第一步010在左，第二步01子树在右，第三步0子树在左。

采用SHA-256与上述标签，当前根为：

61ca45696ba490a5073adadb861cecc97ea7afa1e8584d25c45c70d851364d6c

完整树有15个节点，稀疏字典只保存7个非默认节点：两片占用叶、两个高度1祖先、两个高度2祖先与根；另保存4个共享默认摘要。7不是普遍固定开销，依赖键的公共前缀。

插入 010 → green 后，根变为：

7bfb47ea9d196ef40ac6ee61bfc40bd70ad7f18370ca1dba801377b33400808e

旧空叶证明不能通过新根。删除010则恢复旧映射与旧根；这说明根标识内容快照，单靠根并不能证明“中间从未更新过”。版本、历史追加性及回放防护是其他接口。

空值、键压缩与未知默认值 ​

010 → 空字节串仍是占用叶：其哈希前缀为03，后接键和长度0。它与前缀02的空叶不同。下载实现用None表示缺键，用 b'' 表示存在的空值，测试覆盖两者；把二者都写成“空”会破坏非成员语义。

本页键已是h位字符串，未把任意长业务键暗中压成h位。若增加 k=HashKey(name)，两个名字可能映到同一位置，必须另外规定抗碰撞假设、冲突处理和叶内原键编码。不能直接沿用“每个业务键唯一位置”的论证。

提供者可以省略默认兄弟，但压缩格式必须声明哪些层省略、哪些层给出，并拒绝额外节点。本文下载实现始终传完整h项，免去另一层解析歧义；字典存储稀疏不等于传输格式已经压缩。

为什么空叶证明可靠 ​

固定正确根及查询键k。如果真实位置占用，伪造者却让从空叶开始的路径通过，比较真实路径与伪路径。两种叶编码分别以03与02开头，输入必然不同；若叶摘要相同，已得到碰撞。若不同而最终根相同，就在第一个汇合层得到不同内部输入的相同哈希。证明机制与认证树相同，区别在于空/占用声明的编码不再含糊。

这一论证也保护某个已存在键的值。它不证明提供者交付了业务上应有的全部数据；若发布者最初故意漏建某项，再发布那个根，密码路径会忠实认证这份漏建的映射。可信快照的来源仍是前提。

稀疏成本与迁移 ​

预计算默认值需h+1次哈希及O((h+1)n)字节。一条更新路径需1次叶哈希与h次父哈希；查字典若按期望O(1)计，更新与取证明均为O(h+1)次操作，另计值的读取。m个占用键最多贡献m条长h+1的路径，非默认存储为 $O(min\{2^{h+1}-1,m(h+1)\}n)$ 字节，键索引与字典开销另计。m=0时只需默认表；不能把256层称为渐近O(1)，除非已把键宽固定为协议常数。

终点任务：把键110删除，再证明它为空；其兄弟111默认，但更高兄弟未必全空，因为001仍在树中。另保留001与110、仅查询011，先写出三层兄弟坐标 $(0,2),(1,0),(2,1)$，再预测与010的证明何处相同。HASH-6检查器枚举全部256种三位键占用图，对每图的8个键检查存在或空叶声明，共2048项，并反向提交错误声明以检验拒绝。