2.2.5 哈希指针及梅克尔树

在计算机科学理论中，指针是编程语言中的一个对象，它的值是直接指向计算机内存中的某个地址，而这个地址则是存放数据的地址，即指针的作用就是指明数据存储的位置。比如，指针Pointer的值是内存地址0xffee10，在该内存地址存放着数据1。通俗点说，指针是门牌号，通过门牌号就能找到人。如图2-43所示，信封上的地址是“江苏省南京市玄武区东南大学四牌楼校区李文正楼”，通过该地址能找到小明。

哈希指针是区块链里最常见的一类数据结构，它除了包含普通指针告诉我们的数据存储位置外，还包含所存储数据的哈希值，该哈希值是所存数据通过密码哈希函数计算得出的。如图2-44所示，用H（）表示哈希指针，以便与前面介绍的密码哈希函数H（）进行区分。

可能有人会把哈希指针理解成类似C语言里的结构体，如下所示。其实这是一个错误的理解。

实际上，哈希指针就是一串数据的哈希值。我们知道，数据的哈希值是这串数据的摘要，那么就可以用这个哈希值来指向这串数据，因为它们是一一对应的关系。

此外，我们可以运用哈希指针来构建不同的数据结构。下面我们通过哈希指针构建一个区块链模型。

如图2-45所示，用哈希指针把各个区块连接起来构成区块链。每个区块都包含有一个哈希指针，该哈希指针指向前一个区块（也称“上一个区块”或“前序区块”）并包含前一个区块的哈希值，这样通过一个个区块的连接形成了一个链状数据结构。区块在区块链中通过两个标识可以找到，一个是区块哈希值，另一个是“高度”，我们用“高度”表示当前区块与首个区块之间的距离，也称为区块号。区块哈希值和区块号之间的区别是：区块哈希值是区块唯一不变的标识，而同一个区块号可能指向两个不同的区块，比如发生分叉的两个区块在区块链里的“高度”就是一样的。区块链中的第一个区块0号区块称为创世区块，创世区块因为没有前序区块，所以它里面包含的上一个区块的哈希指针为0。

这里说明一下区块的哈希指针是如何计算的。从图2-45中可以看出，每个区块包含两部分：数据本身和“上一个区块的哈希指针”。区块的哈希值是把区块的这两部分结合在一起进行哈希计算，即当前区块包含的数据与该区块里的“上一个区块的哈希指针”合起来，作为密码哈希函数的输入，从而得到当前区块的哈希值，也即后一个区块中包含的指向当前区块的哈希指针。如图2-46所示，块2中的前序区块哈希指针h1=H（h0‖Data1）。

图2-45这样的链式结构能够防止数据被篡改，主要得益于哈希指针。无论篡改了哪个数据，通过检测该区块紧邻后序区块中的哈希指针都能被发现。这里就用到了密码哈希函数的碰撞阻力特性，可以肯定篡改数据以后的哈希值与之前的哈希值不会相同，也就是与后序区块存储的哈希指针内容不匹配。如图2-47所示，假设有3个区块连接在一起，其中h1=H（h0‖Data1），h2=H（h1‖Data2）。

如果块1里面的数据Data1被篡改为Data1′，那么块1的新哈希值为h1′=H（h0‖Data1′），而块2里存储的h1=H（h0‖Data1），因为Data1′≠Data1，所以h1′≠h1，如图2-48所示。

也许你会想到，为了保证块2里的哈希值与被篡改的块1哈希值一致，可以接着把块2里的哈希值h1篡改为h1′，但是这样又会导致后面连接的块3里的哈希值h2与块2的哈希值不一致，如图2-49所示。

当然你也可以继续篡改块3里的哈希值h2，h2′=H（h1′‖Data2）。如果整个区块链很庞大，你就必须从最初篡改数据的那个区块开始，将整条区块链之后所有区块里的哈希值全部改掉。但是如果我们把区块链最后一个区块的哈希值保护起来，那么必然能发现有人篡改了区块链。如图2-50所示，hash_end≠H（h2′‖Data3）。

因此，区块链的一个重要特性就是防篡改，从哈希指针的角度来看这个特性，就是篡改后能被发现。当然区块链的防篡改特性不止表现在这一点，还表现在全网某一个节点修改数据以后，并不影响其他节点保存的数据。

进一步延伸，前面我们学过了数字签名，那么我们是不是可以对哈希指针进行签名呢？答案是肯定的，签名了哈希指针，表示签名人认可这个哈希指针，也就表示认可该哈希指针指向的上一个区块，而上一个区块又包含指向更前一个区块的哈希指针，以此类推，可以理解为对整条区块链进行了签名。

那么区块链里每个区块包含的数据是什么呢？其实数据是任何你想挂在链上的信息，也就是你想保存的信息。在比特币系统中，区块里的数据是交易数据，简单地理解为收款地址、付款地址、交易金额等信息。每个区块只包含一笔交易数据吗？事实上不是这样的，这里涉及比特币的挖矿机制，简单地说，在挖矿期间会不断有交易产生，矿工会选取部分交易放进区块里。如图2-51所示，区块主要包含区块头部和交易信息。

这种存放交易的方式会造成每个区块过大，而且区块大小不固定，后期扩展也会遇到阻碍，所以我们需要一个全新的数据结构来存储交易数据。此时，哈希指针又大展身手了，用哈希指针建立的二叉树结构，如图2-52所示，称为梅克尔树（Merkle trees），也称为交易树。

每个交易数据单独计算哈希值，这样N个数据就生成了N个哈希值，这些哈希值构成了梅克尔树的第一层叶子节点。将这N个哈希值两两分组，将每组中两个哈希值连接起来再次进行哈希计算，其计算结果形成了上一层的叶子节点，然后将上一层的叶子节点再次两两分组，每一组的上一层是该组两个哈希值成员连接起来进行哈希计算的结果，以此类推，直到树的最上层节点，即梅克尔树的根节点，也称交易树树根节点。由此可见，梅克尔树是自底向上依次构建起来的，根在最上面，叶子在下面。交易数据本身不存储于梅克尔树上。

下面简要说明梅克尔树的生成，如图2-53所示。比特币采用双重SHA-256构造梅克尔树。假设有4笔交易数据分别经过双重SHA-256运算后得到4个32字节的哈希值：H1=SHA256（SHA256（D1）），H2=SHA256（SHA256（D2）），H3=SHA256（SHA256（D3）），H4=SHA256（SHA256（D4））。这4个哈希值构成了梅克尔树第一层叶子节点；接着，它们两两连接在一起，形成一个64字节的字符串，对该字符串再次进行双重SHA-256运算得到梅克尔树第二层叶子节点，即：H12=SHA256（SHA256（H1‖H2）），H34=SHA256（SHA256（H3‖H4））；最后，这两个哈希值结合进行双重SHA-256运算得到1个哈希值：H1234=SHA256（SHA256（H12‖H34）），H1234就是最终的梅克尔树根节点。

需要注意的是，如果交易数量是奇数怎么办？因为梅克尔树是二叉树，需要偶数个叶子节点。这种情况下我们采取的方案是把未配对的最后一个交易对应的哈希值复制一份构成偶数个叶子节点，如果上层叶子节点也是奇数，同样复制最后一份叶子节点构成偶数个叶子节点，如图2-54所示。

按照上述构造方法，我们可以构建包含任意交易数量的梅克尔树，但是最终只生成唯一一个32字节的梅克尔树根，并将其放入区块头部，作为该区块中所有交易的汇总摘要。

现在再回到梅克尔树，想一想这样的数据结构有什么好处呢？其实梅克尔树有诸多优点。

（1）梅克尔树有高效的校验作用，帮助我们很快地证明某个交易是不是隶属于该梅克尔树，即是否包含在相应的区块里。将待验证的交易通过一层层往上计算哈希值，得到最上面的树根节点的值，然后判断是否与我们存储的根节点的值相同即可。我们可以忽略树的其余部分，而只关心与这个待验证交易数据相关的、往根节点方向的层层父节点。如图2-55所示，要判断数据D3是否属于该梅克尔树，只需要将与之关联的哈希值重新计算一遍直至根节点，然后判断与根节点哈希值是否一致，如果一致则说明该交易隶属于这个梅克尔树。

需要注意的是，梅克尔树的校验是从树底层往上直至根节点来校验，但是不能从根节点开始往下来查询交易数据，原因很简单，因为密码哈希函数不能根据输出的哈希值来逆推出输入值，交易数据就是最开始的输入值。如图2-56所示。

梅克尔树之所以能高效验证交易，是因为有一条从交易到根的认证路径，即梅克尔路径，这条路径必须包含与这个待验证交易数据相关的、往根节点方向的层层父节点。如图2-57所示，要验证交易D3是否存在于区块中，节点只需要产生一条包含两个哈希值的梅克尔路径，即H4和H12。每个哈希值是32字节，那么这条路径的大小总共是64字节。因为我们要验证交易数据D3，可以根据双重SHA-256计算出D3的哈希值H3，接着将H3和H4结合就能计算出哈希值H34，然后再将H12和H34结合就能计算出根节点哈希值H1234，最后将计算出的根节点哈希值与原始的根节点哈希值进行比较，一致则说明交易数据D3是真实存在于区块的。所以，这条梅克尔路径必须包含H4和H12两个哈希值。

如果区块包含N个交易，为验证特定交易是否存在于区块里，节点只需要创建log2N个32字节的哈希值，并将它们组成梅克尔路径。如图2-57所示，总共4个交易，要验证某一个交易是否存在，只需要两个（log24=2）哈希值组成梅克尔路径。

此外，当N个交易通过层层哈希计算并最终构造一个梅克尔树，我们最多只需要进行2×log2N次运算就可以验证交易是否包含在区块里。随着N数量增大，2×log2N的增长却相对缓慢很多，这意味着即使梅克尔树包含大量的区块，仍然可以在相对较短的时间内证明隶属关系。一般1M左右的区块包含上千个交易，验证效率是很高的。

（2）因为哈希指针的存在，如果区块中的任何一个交易数据被篡改，那么其哈希值必然会发生变化，这样通过上层的哈希指针就能检测出，同样是因为密码哈希函数的碰撞阻力。你可能会问，如果我篡改了某个数据并一直修改上层相关的哈希指针直到最上层的节点，不就不能被发现了吗？事实上，区块链中树的最上层的哈希值的确可以修改，但是结合区块链结构我们就会知道，如果修改，必然能被区块链中该区块后序区块存储的哈希指针所检测到。梅克尔树防篡改如图2-58所示。

区块的数据结构主要由区块头部、梅克尔树以及交易列表三部分组成，有时也把梅克尔树和交易列表归于区块体。后序区块里的哈希指针指向当前区块头部的哈希值，所以当树根H（）变化时，整个区块头部的哈希值发生变化，这会通过后一个区块里的哈希指针检测出来。区块头部包含版本号、临时随机数nonce、时间戳、找到区块的难度（点数）、前序区块哈希值pre_H和梅克尔树根等6个部分。我们通常将区块头部的哈希值简称为区块的哈希值。

（3）梅克尔树大大地提高了区块链的运行效率和可扩展性。由图2-58可知，在区块头部数据中，只需要包含梅克尔树根，而不用将所有的交易数据都封装进区块头部，这样每个区块头部数据大小都是固定的，哈希运算可以高效地运行在智能终端上。

（4）梅克尔树支持“简单支付验证”协议。以比特币系统为例，目前区块链里所有的区块数据大小已经接近170GB且在不断增加中，而普通消费者只是为了支付消费，没必要下载完整的区块链数据。“简单支付验证”协议就是在不保存区块里全部交易数据，而仅仅保存区块头部数据的情况下，也能对交易进行验证，利用梅克尔路径判断这个交易存在于某个区块里，并得到后面区块的连续确认，则证明该交易已被验证通过了。

通过前面的介绍，我们已经了解了哈希指针和梅克尔树，下面我们来看看比特币的创世区块。中本聪在2009年1月3日创造了比特币世界的第一个区块，即创世区块，在www.blockchain.com区块链网站上可以检索到该创世区块的信息，如图2-59所示。

同样可以使用比特币标准客户端的命令行来获得创世区块信息：

值得注意的是，创世区块中包含着这样一句话：“The Times 03/Jan/2009 Chancellor on brink of second bailout for banks”（2009年1月3日，财政大臣正处于实施第二轮银行紧急援助的边缘），这句话是《泰晤士时报》当天的头版文章标题，该消息由中本聪写入创世区块中。它既是对创世区块产生时间的说明，同时告诉人们一种全新的数字货币交易体系已经诞生，随着比特币的发展，一场前所未有的世界性货币革命即将到来。

下面我们对图2-59所示网站上显示的区块中所包含的主要字段含义进行说明，如表2-4所示。需要注意，有些字段只为网站显示所用，并不包含在真正的区块数据结构中。

这里我们着重介绍一下“Timestamp”字段，该字段引出了区块链里的时间戳技术，时间戳表明了区块生成的时间，也就是交易数据写入区块的时间。在整个区块链上，各区块是按照时间先后顺序依次挂链的。有了时间的参数，我们就可以对交易数据进行存在性证明，同时也有助于形成不可篡改的区块链数据库，使得按时间来追溯历史数据成为可能。

比特币系统的第二个区块如图2-60所示，可以看出它所包含的前序区块哈希指针指向了创世区块。

比特币系统的第三个区块如图2-61所示，可以看出它所包含的前序区块哈希指针指向了第二个区块。

通过对比特币系统中区块的简单介绍，我们对区块链的区块有了大致的认识。区块作为区块链的基础组成部分，贯穿区块链技术的始终，在本书的后续章节中将频繁出现。