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

在比特币中，哈希指针用来保存前一个区块头的哈希值，多个区块连成一条链，保证了区块链的不可篡改特性。比特币也使用默克尔树将交易数据保存在块体中，从最低的交易数据通过哈希指针逐层保存到根哈希，将所有的交易数据浓缩，增加了交易被篡改的难度。Merkle 树还提供了一种有效的方法来证明交易数据的成员身份和非成员身份，两者的时间复杂度均为 O(log N)。

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

发表于 2 天前

比特币技术原理与应用-1 密码学基础哈希指针H()

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

为了说明散列指针的优点，我们先来看看单链表和普通指针。

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

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

节点 0 也称为根节点。根节点是链表的初始节点，不指向任何节点，所以根节点的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 中包含的数据信息。

哈希指针 H(·) 是前一个区块的区块头的哈希值。Block Header 中的 Merkle Tree 哈希值已经包含了 Block Body 的信息，这就是为什么只需要对 Block Header 进行哈希处理。，减少了哈希函数的输入数据大小，提高了哈希运算的速度。区块 0 也称为创世区块。Block 1 中的 H() 是 Block 0 头的哈希值，Block 2 中的 H() 是 Block 1 头的哈希值... · 如果有新的区块要添加，只需计算哈希值最后一个区块头的值，并将其放入新区块的头中，从而连接成区块链。

哈希指针增加了篡改难度，防止篡改区块中的数据。假设我修改了Block 1中的数据，那么根据hash函数的抗碰撞特性，Block 1 header的hash值发生变化，那么我要修改Block 2 header中的hash指针，Block 2 header变化，同理，我还需要修改Block 3的头部……相当于链式反射。如果篡改区块链中的某个区块，则需要篡改该区块之后的所有区块，大大提高了区块的篡改能力。困难。

默克尔树

Block body 中存储交易信息的数据结构是 Merkle Tree。Merkle Tree 的根哈希反映了所有的交易信息。修改任何交易数据都会引起根哈希的变化，防止交易数据被篡改，并且可以快速验证一笔交易是属于这个区块（会员证书）还是不属于这个区域。块（非成员证明）。

与普通二叉树相比，Merkle Tree 使用哈希指针代替普通指针，增加了篡改交易的难度。Merkle Tree 最底层的叶子节点存储交易信息。H(·)是取每笔交易的hash值得到的，将相邻的两个H()拼接在一起，作为相邻的两个hash指针节点的父节点。，依次迭代，最终得到默克尔树的根节点。根节点也是通过两个子节点的哈希值拼接在一起的。根节点相当于包含了所有的交易信息。假设任何交易信息发生变化，都会层层传递，导致根节点发生变化。最后，取 Merkle Tree 根节点的哈希值，存储在区块头的 Merkle Tree Hash 字段中，以保证区块头包含所有交易信息。区块头的变化会导致区块头哈希值的变化，而区块转移会导致区块后的每个区块发生变化，从而增加了篡改交易信息的难度。

找出一笔交易是否属于默克尔树，验证一笔交易是否属于默克尔树称为会员证明，否则成为非会员证明。

附属证明

下图中，假设我们需要验证 Merkle Tree 中是否存在待处理的交易，我们只需要提供一些节点信息（下图中红圈处），经过自下而上的哈希运算后，Merkle最终计算树哈希。我们将哈希运算结果与区块头中的默克尔树哈希进行比较。如果相等，则证明待验证的交易确实存在于默克尔树中。

使用 Merkle Tree 作为交易会员证书，假设包含 N 笔交易，Merkle Tree 的高度为 O(log N)+1，验证交易的时间复杂度为 O(log N)。

非从属关系证明

如何证明一笔交易不属于默克尔树？方法是使用排序的默克尔树。与 Merkle Tree 相比，排序后的 Merkle Tree 中最低的交易数据是有序的。假设要验证的交易 X 在 Tree 中。根据有序排列的交易数据，可以计算出待验证交易之前的交易A和待验证交易之后的交易B。如果我们用成员证明中的方法来证明交易 A 和 B 都属于排序的 Merkle Tree 并且交易 A 和 B 彼此相邻（时间复杂度为 O(log N)）比特币技术原理，这意味着有树中 A 和 B 之间没有空格可以放下 证明要认证的交易 X 不隶属于默克尔树。

概括

在比特币中，哈希指针用来保存前一个区块头的哈希值，多个区块连成一条链，保证了区块链的不可篡改特性。比特币也使用默克尔树将交易数据保存在块体中，从最低的交易数据通过哈希指针逐层保存到根哈希，将所有的交易数据浓缩，增加了交易被篡改的难度。Merkle 树还提供了一种有效的方法来证明交易数据的成员身份和非成员身份，两者的时间复杂度均为 O(log N)。

参考：

北京大学肖真教授《区块链技术与应用》公开课《区块链技术驱动金融：数字货币与智能合约技术》【美国】Arvind Narayanan，Josh Bay Nu Waiting，林华，王勇，帅小译

本文参与登链社区写作激励计划，好文好收入，欢迎您的加入阅读。