Merkle多重证明

两份单叶证明可能各自携带对方已经给出的节点。一起验证时，某个兄弟能从另一目标算出来，就不该再传。只有目标路径并集外、紧贴这片路径边界的子树，需要提供根摘要。

因此缩短证明不是删除校验。验证者仍恢复同一个根，只是让几个目标共同贡献中间结果。把三个独立路径拼接后简单去掉重复字节并不稳妥：两个不同坐标可能恰好有相同摘要，证明的身份应按树中位置判断，而不是按字节值去重。

三个位置从九项降到四项 ​

继续取A至H的8叶树，目标 $S=\{1,2,6\}$，即B、C、G。逐层账本为：

要传的四个摘要对应A、D、H以及EF子树。B加A恢复AB，C加D恢复CD，G加H恢复GH；再由EF恢复EFGH，两边相合得到根。三份独立路径各含3项，共9项；共享证明只含4项，即128字节摘要。索引、值、坐标编码另计，不能把“少5个摘要”直接当作总网络包大小。

验证器计算3次叶哈希、第一层3次父哈希、第二层2次、第三层1次，共9次。三个完全独立的验证各算4次，共12次。传输量与计算量同时减少，但它们减少的数量不相同。

接收重复、额外或漏掉的内容会怎样 ​

若删除(1,2)即EF摘要，算法无法生成右半根，必须失败，不能拿全零默认值填补普通树。若多带一个已经计算出的目标叶摘要，应拒绝，而不是允许另一份同坐标数据覆盖本地计算。重复目标也不能被字典的后写覆盖静默吞掉。

这里要求全部证明条目被消费，是规范输入合同。它避免一份签名或缓存键对应多种无意义尾随表示；但不能反过来说每种接受额外字节的实现都已经产生密码伪造。有效根的可靠性与编码唯一性是相关但不同的目标。

层不变量与碰撞提取 ​

对诚实证明，第j层活跃表每一项都等于真实树的同坐标摘要。初始叶按规范编码计算；每次父节点的两孩子分别来自已证正确的活跃表或真实兄弟，所以归纳继续成立，最终得到r。

若某个目标值错误而整体通过，可沿该目标到根的重算链比较真实树。错误叶输入不同；若叶摘要已相同，得到叶碰撞，否则沿路径找到首次相同父摘要，得到内部碰撞。中间有些兄弟来自另一目标，只改变它的来源，不改变这条逐层比较。因此共享计算不会削弱抗碰撞归约。

按前沿计成本 ​

令k=|S|，B为全部缺失兄弟数，v为真正重算的内部节点数。目标叶与边界兄弟恰构成一棵压缩展开树的叶边界；每个被展开内部节点有两个孩子，故 $v=k+B-1$。验证哈希数为 $k+v=2k+B-1$，不含传输前验证者可能缓存的其他信息。本例k=3、B=4，得到v=6、总数9。所有叶都打开时B=0，仍需重建N−1个内部节点，不能说证明为空便无需计算。

有 $B\le kh$ 且 $\sum _j|A_j|\le k(h+1)$。哈希表查找按期望常数计、每层无需排序时，坐标工作为O(k(h+1)+B)，存储为O(k+B)。下载实现为了确定输出顺序逐层排序，另有 $O(\sum _j|A_j|\log (|A_j|+1))$ 比较成本；不把哈希调用界冒称整个Python运行时间。

终点任务：改成S={2,3}，第一层互为兄弟，不需各传对方；只需(1,0)与(2,1)，B=2，总哈希数5。改成全部8叶，B=0、总哈希数15。再说明为什么“稀疏多重证明”中的少数目标，不等于稀疏Merkle树理路稀疏Merkle树Sparse Merkle tree · SMT authenticated map给每个固定宽度键保留唯一叶位置，用默认子树摘要省去空区域，并把非成员声明化为该位置空叶的认证路径。中的多数空键位置。检查器枚举8叶全部255个非空目标集合，同时检查漏项、重复项与多余项。