比特币技术原理与应用-2 数据结构

本系列文章： 比特币技术原理与应用-1 密码学基础 比特币技术原理与应用-2 数据结构

2天前 发表了文章

比特币技术原理与应用-1 密码学基础

哈希指针H( )

比特币中通过哈希指针将多个区块连接成一条链。 在本质上，区块链也是一个链表，只不过用哈希指针代替了普通指针。

为了说明哈希指针的优点，我们先了解一下单向链表(singly-linked list)和普通指针。

以C++为例，单向链表中的节点通常是结构体数据类型，包含节点的值val和指向下一个节点的指针next。

//单向链表节点 结构体，包含节点的值val和指向下一个节点的指针next
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

Node 0又称为根节点(root node)，根节点是链表的初始节点，没有指向任何节点，因此根节点的next指针为空(Node 0.next = NULL)。Node 1中的next指针存储了Node 0的地址(Node 1. next = Node 0_address)，指向Node 0。同理，Node 2指向Node1， Node 3指向Node 2... 如果要往链表中加入新节点，只需要新建一个节点，并将新节点的next指针指向链表的末尾节点。链表相比于数组的优势是什么？链表的可扩展性更强，一个数组中的元素在磁盘上是先申请一块空间然后连续存储的，而链表中的节点元素可以存储在不同的磁盘位置，通过指针存储下一个节点的地址，然后去磁盘上寻址找到下一个节点。如果要修改链表中的某个节点的值，我们可以寻址找到该节点，并修改节点的值val即可。

在使用普通指针的单向链表中，我们可以随意修改任意节点的值val，而不会破坏链表的完整性。如果比特币也采用普通指针连接成一个普通链表，那我们就可以任意修改区块中的交易信息，这就破坏了区块链的不可篡改特性(严格来说，是难以篡改)。相比于普通指针，哈希指针不仅能把区块连接成一条链，还能保证区块不可篡改。 一个区块(Block)的结构，包含区块头(Block Header)和区块体(Block Body)，下图简单列举了Block Header和Block Body中包含的数据信息，区块结构的具体内容我将在系列博客3-比特币协议中详细讲解。

哈希指针H( )是对上一个区块的Block Header取哈希值，Block Header中的Merkle Tree哈希值已经包含了Block Body的信息，这也是为什么只需要对Block Header 取哈希的原因，减少了哈希函数的输入数据大小从而提高哈希运算的速度。Block 0又称为创世区块(genesis block)，Block 1中的H()为Block 0 header的哈希值，Block 2中的H()为Block 1 header的哈希值······ 如果有新区块要加进来，只需把最末尾区块的header哈希值计算出来，放在新区块的header中即可，这样就连接成了一条区块链。

哈希指针提高了篡改的难度，防止篡改区块中的数据。 假设我修改了Block 1中的数据，那么根据哈希函数的碰撞阻力特性，Block 1 header的哈希值发生变化，那么我就要修改Block 2 header中的哈希指针，Block 2 header发生变化，同理我也需要修改Block 3 header······ 相当于一个连锁反映，篡改区块链中的某个区块，就需要篡改该区块之后的所有区块，大大提高了篡改区块的难度。

Merkle Tree(梅克尔树)

Block body中存储交易信息的数据结构就是Merkle Tree。Merkle Tree根哈希反映了所有的交易信息，修改任意一个交易数据都会造成根哈希的变化，防止篡改交易数据，并且能够快速验证某笔交易属于这个区块(隶属证明)或者不属于这个区块(非隶属证明)。

相比于普通的二叉树，Merkle Tree采用了哈希指针代替普通指针，提高了篡改交易的难度。Merkle Tree的最底层叶子节点存的是交易信息，对每一笔交易取哈希值得到H( )，两个相邻的H()拼接在一起作为两个相邻哈希指针节点的父节点，依次迭代，最终得到Merkle Tree的根节点。根节点也是由两个子节点的哈希值拼接在一起的，根节点相当于包含了所有的交易信息，假设任意一笔交易信息变化，都会层层传递导致根节点的变化。最终，对Merkle Tree的根节点取哈希值，存在区块头的Merkle Tree Hash字段中，从而保证区块头包含了所有的交易信息，任意一笔交易信息变化层层传递导致区块头的变化，该区块头的变化又会导致区块头取哈希值的变化，块块传递导致该区块之后每一个区块发生变化，提高了篡改交易信息的难度。

查找一笔交易是否属于Merkle Tree，验证一笔交易属于Merkle Tree称为隶属证明，反之成为非隶属证明。

隶属证明

下图中，假设我们需要验证一笔待证交易存在Merkle Tree中，只需要提供部分节点信息(下图中红圈部分)，经过自底向上的哈希运算后，最终算出Merkle Tree hash。我们将哈希运算结果与该区块头中的Merkle Tree hash作比较，如果相等则证明了待证交易确实存在这个Merkle Tree中。

使用Merkle Tree做交易的隶属证明，假设包含N笔交易，Merkle Tree的高度为O(log N)+1，则验证一笔交易的时间复杂度为O(log N)。

非隶属证明

如何证明一笔交易不属于Merkle Tree？方法是使用排序梅克尔树(sorted Merkle Tree)，相比于Merkle Tree，sorted Merkle Tree中最底层的交易数据是有序排列的。先假设待证交易X在Tree中，根据有序排列的交易数据可以推算出排在待证交易之前的交易A和排在待证交易之后的交易B，如果我们使用隶属证明中的方法证明了交易A和B都隶属于sorted Merkle Tree且交易A和B是相邻紧挨着的（时间复杂度为O(log N)），那么意味着在树中A和B之间是没有空间放下待证交易X的，从而证明了待证交易X不隶属于Merkle Tree。

小结

比特币中使用哈希指针保存前一个区块头的哈希值，将多个区块连接成一条链，保证了区块链的不可篡改特性。比特币还使用梅克尔树保存区块体中的交易数据，从最底层的交易数据通过哈希指针层层传递到根哈希，浓缩了所有的交易数据，提高了篡改交易的难度。梅克尔树还提供交易数据隶属证明和非隶属证明的高效方法，时间复杂度均为O(log N)。

参考文献：

1. 北京大学肖臻老师《区块链技术与应用》公开课
2. 《区块链 技术驱动金融：数字货币与智能合约技术》[美] 阿尔文德·纳拉亚南（Arvind Narayanan），约什·贝努 等 著，林华，王勇，帅初 等 译