跳到主要内容
ecdsa.com

Merkle 树(默克尔树)

一种二叉哈希树:每个内部节点是对其两个子节点计算的哈希,因此一个根哈希就能承诺全部叶子,成员关系或只追加增长都能用对数级大小的证明来证实。
其他写法hash treeMerkle rootinclusion proofconsistency proof

证书透明度(RFC 6962 §2.1、RFC 9162 §2.1)定义了大多数透明日志所用的哈希方式:叶子为 SHA-256(0x00 ‖ data),节点为 SHA-256(0x01 ‖ left ‖ right),这些前缀可以防止把叶子冒充为内部节点。对于一百万个条目中的某一条,包含证明大约需要 20 个哈希;一致性证明则表明较新的树是在较旧的树基础上扩展而来,没有改写历史。

CT 日志、Sigstore 的 Rekor、Go 的校验和数据库(sum.golang.org)、比特币的交易根(采用另一种双重 SHA-256 构造,并有一个已知的“重复叶子”问题)、Git 和大多数内容寻址存储,以及基于哈希的签名 XMSS、LMS 和 SLH-DSA,都以这种结构为基础。

透明日志会发布经过签名的树头(检查点,checkpoint),由见证者(witness)共同签名;这样,如果某个日志向不同的客户端展示不同的历史,就会被发现。

标准与参考资料

全部术语