1703864564
1703864565
区块链技术驱动金融：数字货币与智能合约技术 [:1703863908]
1703864566
区块链技术驱动金融：数字货币与智能合约技术 1.2 哈希指针及数据结构
1703864567
1703864568
本节将讨论哈希指针（hash pointer）及其应用。哈希指针是一种数据结构，这种数据结构在我们即将讨论的很多系统中都很有用。简单来说，哈希指针是一个指向数据存储位置及其位置数据的哈希值的指针。一个普通的指针可以告诉你数据存储的位置，哈希指针不但可以告诉你数据存储的位置，并且还可以给你一种方式，让你验证数据没有被篡改过（见图1.4）。
1703864569
1703864570
1703864571
1703864572
1703864573
图1.4 哈希指针
1703864574
1703864575
注：哈希指针是一个不但可以指向数据存储的位置，还可以明晰某个时间戳下该数据的哈希值的指针。
1703864576
1703864577
我们可以利用哈希指针构建各种各样的数据结构。为求直观，我们可以把原来用普通指针实现的数据链表和二叉查找树通过哈希指针来实现。
1703864578
1703864579
区块链
1703864580
1703864581
如图1.5所示，我们通过哈希指针构建一个链表，我们将这个数据结构称为区块链（block chain）。在普通链表中有一系列区块，每个a区块既有数据也有一个指向上一个区块的指针。而在区块链中，上一个区块指针被置换为哈希指针。因此，每个区块不仅能告诉我们上一个区块的值在哪里，还包含了该值的摘要，使我们能够验证那个值没有改变。我们存储链表头部（the head of list），即一个普通的哈希指针指向最近使用的数据区块。
1703864582
1703864583
1703864584
1703864585
1703864586
图1.5 区块链
1703864587
1703864588
注：通过哈希指针而不是普通指针构建的一个链表，我们把这个链表称为区块链。
1703864589
1703864590
区块链的一个应用就是“防篡改日志”。也就是说，我们要建立一个存储很多数据的日志数据结构，使我们能将数据附加到日志的末尾。但是如果有人篡改日志前面的数据，我们可以检测到。
1703864591
1703864592
要理解区块链如何实现这一防篡改特性，我们先看一下如果对手要篡改区块链中间的数据会发生什么。具体来说，通过这种方式，对手的目的是让只记得区块链头部哈希指针的人无法检测到篡改行为。为达到这个目标，对手会改变某区块k的数据。既然数据已经被改变，区块k+1的哈希值（即整个区块k的哈希值）将不会匹配。记住，因为哈希函数具有碰撞阻力，我们可以确定新的哈希值与改变后的内容不会匹配。因此，我们会检测到区块k中的新数据以及区块k+1中的哈希指针的不一致性。当然，对手可以继续尝试，并通过篡改下一个区块的哈希值掩盖这次篡改。他可以一直这样做，但是当他到达链表的头部时，这个策略将会失败。具体来说，只要我们将链表头部的哈希指针存储在对手无法改动的地方，对手将不能做到在不被检测到的前提下，篡改任何区块（见图1.6）。
1703864593
1703864594
1703864595
1703864596
1703864597
图1.6 防篡改日志
1703864598
1703864599
注：如果对手修改了区块链中的任意部位的数据，那么将会导致下一个数据块的哈希指针不正确。如果我们锁定区块链的头部数据，那么即使对手修改了所有哈希指针使其与修改过的数据一致，那么他也无法修改头部数据，从而我们就可以检测到篡改行为。
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