1703864600
1703864601
这样做的结果是，如果对手想要篡改区块链中任意地方的数据，为了保证整个内容一致，他需要篡改所有的哈希指针直至最开始的地方。他最终将碰到障碍，因为他不能篡改链表头部的指针。这样，我们便知道，仅通过记住一个哈希指针，我们就基本记住了整个链表的防篡改哈希值。因此，我们可以搭建一个包含很多区块的区块链网络，链表头部的哈希指针被称作创世区块（genesis block）。
1703864602
1703864603
你可能已经注意到了，区块链的结构与我们上一节见到的MD变换类似。的确，它们很相似，同一个安全论证对于两者都适用。
1703864604
1703864605
梅克尔树
1703864606
1703864607
另一个我们可以用哈希指针建立的有用的数据结构是二叉树。使用哈希指针的二叉树也叫作梅克尔树(Merkle trees)，以其发明者拉尔夫·梅克尔（Ralph Merkle）的名字命名。如图1.7所示，假设我们有很多包含数据的区块，这些区块就构成了树的叶子（节点）。我们将这些数据区块两两分组，然后为每一组建立一个有两个哈希指针的数据结构，每个指针对应一个区块，这些数据结构就构成了树的下一个层次。我们轮流将这些区块组两两分组，为每一组建立一个包含每个区块组哈希指针的新的数据结构。以此类推，直到我们得到一个单一区块，即树根节点。
1703864608
1703864609
1703864610
1703864611
1703864612
图1.7 梅克尔树
1703864613
1703864614
注：在梅克尔树的数据结构中，所有的数据区块都被两两分组，指向这些数据区块的指针被存储在上一层的父节点（parent node）中，而这些父节点再次被两两分组，并且指向父节点的指针被存储在上一层的父节点中，一直持续这个过程，直到最后我们到达树的根节点。
1703864615
1703864616
如上所述，我们要记住树最前面的哈希指针。我们现在可以通过哈希指针回溯到列表中的任何位置，这让我们能保证数据确实未经篡改，正如我们在区块链见过的一样，如果对手篡改了树底部的一些数据区块，会导致上一层的哈希指针不匹配，即使他继续篡改这个区块，改动数据行为将最终传递到树的顶端，而此时，他将不能篡改我们存储的哈希指针。因此，同样地仅仅通过记住顶部的哈希指针，任何企图篡改任何数据的行为都会被检测到。
1703864617
1703864618
隶属证明
1703864619
1703864620
与我们之前建立的区块链不同，梅克尔树的另一个特点是它可以实现简洁的隶属证明。假设某人想要证明某个数据区块隶属于梅克尔树。同样地，我们只记住树根节点，然后他需要展示给我们数据块信息，以及从该数据区块通向树根节点的那些区块，我们可以忽略树的其余部分，这样做是因为这些区块已经足够让我们验证通往树根节点过程中所有的哈希值。其工作原理图解参见图1.8。
1703864621
1703864622
1703864623
1703864624
1703864625
图1.8 隶属证明
1703864626
1703864627
注：为了证明某个数据区块来自一个梅克尔树，我们只需要找到该数据区块到树根节点的路径。
1703864628
1703864629
如果整棵树上有n个节点，只需要展示约log(n)个项目，因为每个步骤仅需要计算子区块的哈希值，验证过程需要时间约为log(n)。因此，即使梅克尔树包含大量的区块，我们仍可以在相对较短时间内证明隶属关系。因此，验证需要花的时间和涉及空间（树节点）与log(n)同级。
1703864630
1703864631
一个排序梅克尔树是把底层的数据通过某些排序得到的梅克尔树，这里排序规则可以是字母表排序、词典排序、数字化排序，或者其他约定的排序方式。
1703864632
1703864633
非隶属证明
1703864634
1703864635
有了排序梅克尔树，我们可以在一个对数复杂度的条件下验证某一个数据区块并非来自某梅克尔树。也就是说，我们可以证明某个特定区块不属于梅克尔树，而我们只是简单通过展示被验证区块之前的区块路径，以及被验证区块之后的区块路径，就可以达到目的。如果之前、之后两个区块在树上是连续的，那么这说明了被验证区块与该梅克尔树之间是非隶属关系。因为被验证区块确实隶属于梅克尔树，它需要在两个条目之间，而如果两个条目是连续的话，二者之间则并没有空间。
1703864636
1703864637
我们讨论过在链表及二叉树中使用哈希指针，但更广泛地说，我们可以在任何以指针为基础的数据结构中使用哈希指针，条件是数据结构不存在循环。如果数据结构中存在循环，那么我们将不能使所有哈希值得到匹配。想一下，在一个非循环的数据结构中，我们可以在靠近节点的地方开始，或者在没有指针的数据区块开始，计算其哈希值，然后从后往前进行计算。但是在一个有循环结构的网络中，并没有一个根节点，可以让我们去追溯。
1703864638
1703864639
因此，试想另一个例子，我们可以建立一个哈希指针定向的非循环图。
1703864640
1703864641
我们能够在该图中非常有效地验证隶属关系，同时也方便计算。这样的哈希指针使用方式是一个常见技巧，在分布数据结构中、在本章后面会讨论到的算法中以及本书中都会反复提到。
1703864642
1703864643
1703864644
1703864645
1703864646
区块链技术驱动金融：数字货币与智能合约技术 [:1703863909]
1703864647
区块链技术驱动金融：数字货币与智能合约技术 1.3 数字签名
1703864648
1703864649
在本节，我们将讨论数字签名（digital signatures）。数字签名是密码学中的第二个重要部分，该理论和哈希函数一起，为我们后面讨论加密货币奠定基础。数字签名被认为是对纸上手写签名的数字模拟。我们对数字签名有两个特性要求，使其与我们对手写签名的预期一致。第一，只有你可以制作你自己的签名，但任何看到它的人都可以验证其有效性；第二，我们希望签名只与某一特定文件发生联系，因此该签名不能用于表明你同意或支持另一份不同的文件。对于手写签名来说，第二条就如同确保别人不能将你的签名从一份文件上剪下来，贴到另一份文件的末尾那样。