Ralph Merkle

你想发送一条加密消息。收件人需要秘密密钥才能阅读，但如果有人监视所有通信，怎样把密钥交给他？Ralph Merkle 在 1978 年的论文中描述了一种出人意料的方法：发送者准备许多加密谜题，接收者随机选一个解开，再公开返回藏在其中的标识符。这样，双方就知道了共同密钥。窃听者也能看到标识符，却不知道它藏在哪个谜题里。在论文的模型中，窃听者的工作量随任务规模呈平方增长，参与者的工作量则呈线性增长。这是平方级差距，不是指数级差距。它是历史上的突破，并不是今天加密消息的操作建议。 [1]

理解 1978 年的论文，必须注意攻击者能做什么。他可以窃听，但论文仍假定篡改和伪造能够被发现。想象一个只读信的人，再想象一个还会改写信件、冒用你签名的人。后一种情况需要额外保护：确认你究竟在和谁通信。计算工作量的差距不能解决这个问题。因此，不能从这些谜题推导出经由主动攻击的中间人进行的任意通信都是安全的。它们的贡献在于说明：在给定假设下，即使事先没有共享秘密密钥，也有可能建立共同秘密。 [1]

Merkle Tree 解决的是另一个问题。这种认证树见于 Merkle 的 1979 年博士论文。想象一个合同档案库：你希望核验某份合同，却不想下载整个档案库。每个条目先经过哈希运算，得到一个短的数字指纹。指纹两两合并后再次哈希，直到只剩一个共同的树根。哈希并不是加密内容，而是用于检查对应关系。检查要有意义，必须先取得已经认证的树根，也就是确认属于正确档案库的指纹。如果骗子可以同时提供自己的文件和任意树根，两者匹配并不能证明它们与原始档案库有关。 [2]

以包含 8 个条目的平衡二叉树为例。验证选定的叶子需要 3 个兄弟节点哈希，也就是每一层相邻分支的指纹。从自己的叶子和这些指纹出发，逐层算出树根，再与已认证的树根比较。叶子本身和树根不计入这些辅助哈希的数量。你还必须知道树的结构和组合顺序：相邻节点应放在左边还是右边？这项节省并不是隐藏数据的魔术。档案库中较远的部分由其指纹代表，因此，这次特定检查不需要那些文件的完整内容。 [2]

Merkle Tree 证明的是条目与特定数据集之间的关系，不会让错误信息变成事实。我们的档案库也可能收录姓名写错的合同；证明可以正确确认它已被收录，却发现不了姓名错误。同样，指纹也不能证明文件作者具有相应权限。因此要分开问：条目是否对应这个树根？这个树根来自哪里？我按什么规则接受内容？这种区分有助于理解同样的技术在 Bitcoin 中能做什么，以及哪些任务必须由系统的其他部分完成。 [2]

Bitcoin 用 Merkle Tree 将交易与区块头联系起来，区块头是区块的简要记录。树根包含在区块头中；修改所收录的交易会影响它们的共同指纹。Satoshi Nakamoto 在 whitepaper 第 7 节介绍了这种结构，并将 Merkle 的工作列入参考文献。这说明技术上的影响，不说明 Merkle 是 Bitcoin 的作者。树本身不会选择有效历史，也不会代替节点检查交易签名。Bitcoin 将它与交易验证、Proof of Work 等规则结合使用，后者是计算工作量的证明。理解一个组件，比把整个系统的能力都归给它更有帮助。 [3]

whitepaper 第 8 节介绍了 SPV，即简化支付验证。轻客户端使用区块头，以及将交易连接到选定区块的树分支。这样能节省数据，但依赖关于累计工作量最大链和矿工行为的假设。仅凭收录证明，不能像 Full Node——执行完整验证的节点——那样检查全部交易规则。它也不能说明某个输出后来有没有被花掉；那需要了解后续发生的事情。初学者最需要分清的是：“这笔支付在这个区块里”，并不等于完整确认现在还有多少资金可用。 [3]

1979 年的博士论文还用认证树组织数量有限的一次性数字签名。数字签名能让人检查某条消息是否得到相应秘密密钥持有者的认可，它不是纸面签名的图片。树可以将许多验证值连接到一个已知树根。但在论文描述的构造中，签名数量有限，树根最终必须更新。这不意味着同一把一次性密钥可以无限重复使用。这部分较深入的研究体现了相同思路：用小型证明验证所需部分，同时清楚了解这种验证依赖的条件。 [2]