从一颗种子到千片树叶——默克尔认证树2026年8月3日一个小型默克尔树Merkle Tree的实现可在指定仓库找到。那王国御玺是皇家批准标志普通人的签名就像“平价印章”其独特性源于书写时的笔压、速度等组合。但时代发展普通签名易复制粘贴要是有人伪造签名让你损失股票和投资那可就糟了。数字签名的起源不过早在1979年拉尔夫·查尔斯·默克尔提出数字签名概念并在论文中阐述。其实数字签名概念并非他首创他改进了兰波特 - 迪菲一次性签名而兰波特 - 迪菲一次性签名又是对拉宾签名的改进。兰波特 - 迪菲一次性签名是什么默克尔用爱丽丝和鲍勃的例子解释。爱丽丝持有股票想出售她购买股票时用单向函数计算并发送给鲍勃还签了含F和y但不含x的合同约定出售时透露x值因F不可逆所以可认为消息经过认证。爱丽丝想发送更长消息怎么办很多人不是一次性出售全部股票比如爱丽丝想出售11股。她要选j个私钥x并计算公钥值与鲍勃共享j表示可签名消息的比特长度。她把消息转换为二进制因j值限制只能对100位签名可通过单向函数映射和零填充处理。对消息签名时她把值为1的位对应的x_j发送给鲍勃。消息安全了吗实际上并非完全安全鲍勃可篡改消息将1改为0。为避免兰波特和迪菲建议在消息末尾附加m’m的补码这样鲍勃若篡改就需透露未获得的私钥。但这种一次性签名需大量存储空间所以拉尔夫·默克尔决定改进。默克尔如何改进兰波特 - 迪菲一次性签名默克尔的第一个解决方案是减少受保护消息的实际长度。兰波特用m的补码防止篡改使消息长度翻倍默克尔在消息m末尾添加0的数量只需⌈log₂j⌉个额外比特比兰波特方法所需比特数少。0的数量以二进制存储100位消息最多100个0需7位存储。可以存储1的数量而不是0的数量吗不行因为这样无法防止签名被篡改。鲍勃只能将1改为0不能将0改为1若存储1的数量鲍勃可轻松伪造消息。必须存储那些占用大量空间的公钥吗如果使用兰波特 - 迪菲一次性签名就得存储不然鲍勃无法确认是爱丽丝发送的密钥。但存储公钥会占大量空间所以默克尔提出“树认证”解决方案。树认证是如何工作的整个结构像二叉树叶子节点是Y_i值公钥内部节点和根节点用单向函数H归纳计算。从叶子节点开始计算再向上计算到根节点。爱丽丝想发8条签名消息先计算8个向量Y再算叶子节点、内部节点最后得到根值R这是鲍勃和爱丽丝需达成一致且鲍勃需存储的唯一公钥。爱丽丝究竟是如何签署消息的通过爱丽丝和鲍勃的对话来看8条可用消息中的第一条消息m₁的签名过程。爱丽丝依次提供相关值鲍勃进行验证若答案肯定则继续下一步若最后验证通过消息确实来自爱丽丝可按兰波特 - 迪菲方法透露私钥。爱丽丝用完8个可用签名后要更改根值R并重新计算二叉树。树认证真的解决了存储空间过大的问题吗当然。兰波特 - 迪菲一次性签名中压缩和签名的两个哈希函数产生100位输出若鲍勃收到1000条消息存储公钥需2.5MB若有1000个客户需约2.5GB。而使用默克尔的改进方法鲍勃只需存储100位的根值R差距很大。但爱丽丝仍然需要存储所有这些认证路径不是吗并非如此。认证路径删除重复项后存储内容减少且它实际上就是默克尔树只是内部节点顺序颠倒。爱丽丝在下次更改根值前可删除不再用于认证的节点如签署消息m₁、m₂和m₃后可删除四个内部节点。但爱丽丝可能仍然需要存储所有未使用的私钥X_i和公钥Y_i对吧不对。爱丽丝只需存储200位的种子密钥就能恢复所有私钥向量。私钥有两个索引通过密码C生成。没有种子密钥无法生成私钥只有爱丽丝能为消息生成有效私钥。既然能从种子密钥恢复私钥也能计算出Y_i且从种子密钥计算密钥所需时间和能量不多所以值得。这是否意味着默克尔认证树至今仍在使用是的。默克尔树是区块链的基本组成部分叶子节点包含交易的哈希值。区块链由一个个区块组成每个区块包含与前一个区块的连接和一棵默克尔树。比特币就将默克尔树作为简化支付验证的解决方案购买比特币时验证单个交易只需相关认证路径与鲍勃验证单个消息类似。那些单向函数H和F就是哈希函数默克尔树节点存储哈希值证明哈希函数可对大型结构进行认证是密码学重要一步。