北京大学肖震教授公开讲座《区块链技术与应用》笔记3——比特币中的数据结构

文章目录

1.普通指针和散列指针

普通指针将结构的地址存储在内存中。如果 P 是一个结构体的指针，那么 P 中存储的就是结构体在内存中的起始位置。

哈希指针除了存储地址外，还需要存储结构的哈希值H()。好处是：从hash值的hash指针，不仅可以查到结构体的位置，还可以查到结构体的内容是否被篡改过，因为我们保存了它的hash值。

比特币中最基本的结构是区块链，它是一个由区块组成的链表。

2.区块链与普通链表的区别

①使用哈希指针代替普通指针（B区块链是使用哈希指针的链表）

区块链的第一个区块称为创世区块。最后一个块是最近的块。每个块都包含一个指向前一个块的哈希。哈希指针

如何计算一个块的hash指针：就是把前面整个块的内容，包括里面的hash指针，组合起来，得到hash值。通过这种结构，可以实现防篡改日志。如果有人改变了一个区块的内容，那么下一个区块的hash指针就会不匹配，因为后一个区块的hash指针是根据前一个区块的内容计算出来的，所以后一个区块的hash指针也是必须要改变，以此类推，我们保持的是最后一个hash值也会改变。

②一个普通的链表可以改变任何元素，对链表中的其他元素没有影响。区块链影响全身，因为只需要保存最后一个哈希值，就可以判断区块链是否发生了变化，以及发生在哪里。

所以比特币没有什么可以保留所有区块，它只能保留最近的数千个区块。如果你想使用前一个块，你可以向系统中的其他节点请求这个块。有些节点是恶意的，如何判断？这里使用哈希值，如下：

其他节点给你一个block，如何判断是否正确？计算其哈希值，并与保留块的哈希值进行比较。

3.默克尔树

比特币的另一个结构是：默克尔树。底层是数据块，上三层的内部节点是哈希指针，第一层是根节点，根节点的块也可以取哈希，称为根哈希（root hash））

这种结构的好处：只要记住根哈希，就可以检测到对树的任何部分的修改。

它们的区别：

使用哈希指针代替普通指针。

比特币中的区块通过哈希指针连接。每个区块中包含的交易以默克尔树的形式组织。数据块的底线实际上是一个块。一笔交易，每个区块分为两部分，即区块头和区块体（block header，block body）。区块头中有一个根哈希值。由每个区块中包含的所有交易组成的默克尔树的根哈希值存在于区块的区块头中。但是，区块头中并没有交易的具体内容，只有一个根哈希值。 ，在块体中有一个交易列表。

4.默克尔树的作用

提供默克尔证明

比特币中的节点分为两类：全节点（保存整个区块内容，即区块头和区块主体都有交易的具体信息）和轻节点（如比特币钱包）在手机上）（只有区块头）

这时候有一个问题：如何将轻节点发送给轻节点证明一笔交易写入区块链？

此时需要Merkle proof：找到交易的位置（最下面一行的区块之一），则该区块一直到根节点的路径称为merkle proof。

最上面一行是一个小区块链，图中是一个区块的默克尔树一个完整的比特币节点占内存多大，最下面一行是它包含的交易。假设一个轻节点想知道图片中的黄色交易是否包含在默克尔树中。轻节点不包含交易列表，没有默克尔树的具体内容，只有一个根哈希值。此时轻节点向全节点发送请求，请求黄交易包含在默克尔树中的默克尔证明。全节点收到这个请求后，只需要将图中红色标记的三个哈希值发送给轻节点即可。有了这些哈希值，轻节点就可以本地计算出图中绿色标记的三个哈希值。先计算黄色交易的hash值，即正上方的绿色hash值，再与旁边的红色hash值拼接，就可以计算出上层节点的绿色hash值。然后拼接，再计算上绿色的hash值，再拼接，就可以计算出整棵树的根hash值。轻节点将根哈希值与区块头中的根哈希值进行比较，就可以知道黄色交易是否在默克尔树中。

默克尔证明中全节点提供的哈希值是从黄色交易所在节点到树根的路径上使用的哈希值。轻节点收到这样的默克尔证明后，只要自底向上验证，一路上的哈希值都是正确的。 （验证时只能验证路径的hash值，其他路径无法验证，即图中红色的hash值无法验证）

这不安全吗？如果黄色交易被篡改，则其哈希值发生了变化。是否可以调整旁边红色的哈希值，使它们的组合哈希值保持不变？不，根据抗碰撞性，这是不可行的。

merkle proof 可以证明交易包含在 merkle 树中，所以这种证明也称为成员证明或包含证明。

对于轻节点，验证默克尔证明的复杂度是多少？假设底层有n笔交易，默克尔证明的复杂度为θ(log(n))。

如何证明默克尔树不包含交易？

非会员证明。可以将整棵树传递给轻节点，轻节点接收到后，验证树的结构是正确的，并且每一层使用的哈希值是正确的，说明里面只有这些叶子节点树，并且您正在寻找的交易是正确的。不在里面，它证明了非会员资格。问题是它的复杂度是线性的θ(n)，是一种比较笨的方法。

如果对叶子节点的顺序有一些要求，比如按照交易的hash值排序。每个叶子节点就是一个交易，交易的内容经过哈希处理，按照哈希值升序排列。要检查的交易首先计算一个哈希值，看看它应该在哪里，如果它在其中。例如，在第三和第四之间，此时提供的证明是第三和第四叶子节点必须上到根节点。如果哈希值正确，则最后一个根节点计算的哈希值没有改变，说明第四个节点三、确实是原默克尔树中的相邻点。您要查找的事务（如果存在）应该在这两个节点之间。但它没有出现一个完整的比特币节点占内存多大，所以它不存在。它的复杂性也是对数形式，以排序为代价。排序的默克尔树称为排序默克尔树。比特币中不使用这种排序的默克尔树，因为比特币不需要证明不存在。

本节讨论比特币中两个最基本的结构：区块链和默克尔树，两者都使用哈希指针构建。除了这两种之外，哈希指针还可以用其他方式来使用。

只要数据结构是非循环的（非循环链表），就可以使用哈希指针代替普通指针。环有问题，无法计算其哈希值，无法确定具有固定哈希值的区块。