比特币史话·83 | 压缩(1): 默克尔树

(拉尔夫·默克尔，默克尔树发明者。图片来源于网络)

前情回顾：

正文：

在1980年4月由IEEE计算机协会举办的安全和隐私研讨会的会议论文集中，收录了SHA-256哈希函数所用的“默克尔-丹加德”构造发明者、美国计算机科学家拉尔夫·默克尔(Ralph Merkle, 1952-)的《公钥密码系统的协议》(Protocols for public key cryptosystems)一文[1]。在该论文中，拉尔夫给出了他发明的、后来以他的名字命名的一种称之为“默克尔树”(Merkle tree)的构造方法和用例。

在2008年比特币白皮书中，中本聪在第7篇参考文献的位置引用了拉尔夫的这篇论文。

默克尔树是一种使用密码学哈希函数构造的二叉树。二叉树是一种计算机中常见的数据结构，望文生义，就是从树根到树叶中间的每一层都是二分叉。1分2，2分4，4分8，如此下去。这颗二叉树还是一颗满二叉树，也就是说所有分支都是从根到叶子的完整路径，没有缺失。默克尔树的根是它直接分叉的两个枝干节点拼接起来之后求哈希值，每个枝干节点又是它直接分叉的两个下一级节点拼接后求哈希值，直到叶子节点。叶子节点是对原始数据求哈希值。

在比特币所用的默克尔树中，以上求哈希值的函数使用的是双哈希SHA-256算法。

默克尔树这种结构有一个特点，就是对原始数据的篡改会改变所在路径的默克尔值。这样，我们就可以做到在不需要原始数据的情况下，仅仅使用一条从根到叶子的、由数个哈希值组成的链条，来证明某笔交易的存在性，这种存在性证明又被称之为“默克尔证明”(Merkle proof)。

默克尔树的引入可以让我们在保持区块链不可篡改的同时，允许删除过时的交易，甚至完全删除原始交易数据，而不改变根节点的哈希值。我们只需要把当前区块打包的一笔笔交易的数据作为叶子节点，层层计算，最终算出根节点的哈希值，称为“根哈希”。把“根哈希”和其他的非交易数据，比如当前区块的工作量证明信息，放在一起，组合成为所谓的“区块头”(block header)。

在比特币白皮书的第7节“回收磁盘空间”一节中，中本聪指出，“一旦一枚硬币中的最新交易被埋在足够多的区块底下，已用完的交易就可以丢弃，以节省磁盘空间。为了在不破坏区块哈希值的情况下实现这一点，在默克尔树中对交易进行哈希处理，仅将根包含在区块哈希中。然后，可以通过砍掉树的分支来压缩旧区块。(被砍)分支内的哈希都不需要存储”[2]。

中本聪进一步仔细计算了一下实际数值。一个区块头的大小大约是80字节。按每10分钟生成一个新区块，则一年会产生80字节乘以6乘以24乘以365等于约4.2兆字节(MB)的区块头数据。“按照2008年销售的典型的计算机系统通常有2GB内存，以及摩尔定律预测当前每年将增长1.2GB，即使必须把区块头保存在内存中，存储也不应该有问题”，中本聪如此写道。

【未完待续】(公众号：刘教链)