《区块链技术与应用》课堂笔记（三）：区块链的数据结构

普通指针存储结构在内存中的地址。 如果P是一个指向结构体的指针，那么P中存放的就是该结构体在内存中的起始位置。 哈希指针除了存储地址外，还需要存储结构体的哈希值H()。 好处是：从哈希值的哈希指针中，不仅可以找到结构的位置，还可以检测到结构的内容是否被篡改过，因为我们保存了它的哈希值。

哈希指针

比特币中最基本的结构是区块链，它是由区块组成的链表。 区块链与普通链表的区别：

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

（Bblock链是使用哈希指针的链表）

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

防篡改日志

如何计算一个区块的哈希指针：将之前整个区块的内容，包括里面的哈希指针，组合起来得到哈希值。 通过这种结构，可以实现防篡改日志。 该属性意味着无论哪个区块发生变化，都会导致系统中存储的哈希值发生变化，即只要记录了哈希值，就可以检测到区块链中的任何一个位置都被篡改过。修改的。 因为修改某个区块的内容会导致前一个区块中保存的哈希值（与其新生成的区块相比）不一致，所以哈希值也必须改变，然后向前移动需要改变的必须被改变，就像多米诺骨牌一样。 这就是与普通链表的区别。 普通链表可以修改其中的任意节点，对整个链表中的其他节点没有影响。 但是，修改区块链中的一个区块将影响其后生成的所有区块。 .

有了这个属性，某个用户就不需要保存系统中所有的区块，只保存最近的一些区块。 如果你想使用之前生成的块，你可以问别人。

例如，只保存下图中绿线右侧的块。 这些是相对较新生成的块。 如果你想使用紫色圈出的积木，你可以问问别人。 保存的哈希指针可以检查给定的区块是否正确（取一个哈希值与保存的哈希指针的哈希值进行比较），只需使用保存的哈希指针进行下一个区块验证，然后取的哈希指针验证块然后向下验证，如此重复。

————————————————

比特币中的另一种结构是：默克尔树

其中，最底层是数据块（data blocks），上面三层的内部节点都是哈希指针，第一层是根节点比特币中节点的功能有哪些，根节点的块也可以取一个哈希，称为Genha希腊语（根哈希））

和区块链一样，在默克尔树中，只要记录了根哈希值，就可以检测到对树的任何部分的修改，即根哈希值用于保护整棵树不被篡改。 这比以前的区块链更有效率。

在比特币系统中，默克尔树的每个数据块都代表一笔交易，整棵树也在记录着比特币系统中的交易，根哈希值就是用来防止这些交易信息被篡改的。

另一个概念：二叉树。

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

它们的区别：①用散列指针代替普通指针。

比特币中的区块通过哈希指针连接在一起，每个区块中包含的交易被组织成默克尔树的形式。 最下面一行数据块其实就是一个交易，每个块又分为两部分，分别是块头和块体（block header, block body）。 区块头中有一个根哈希值，每个区块包含的所有交易组成的默克尔树的根哈希值都存在于区块头中，但是区块头中并没有交易的具体内容，只有一个root hash value ，在区块体中有一个交易列表。

Markle Tree的实际使用

默克尔树的作用：①提供默克尔证明

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

(1) 全节点

同时具有区块头和区块体的区块存储了交易的具体信息。

(2)轻节点

只保存区块头，不保存区块体。 比如手机上的比特币钱包，使用的是轻节点。

这时候就有一个问题：如何向轻节点证明某笔交易写入了区块链？

如何向轻节点证明交易已写入区块链？ 比如有人给自己转比特币，手机上的比特币钱包用的是轻节点。 轻节点没有区块体比特币中节点的功能有哪些，不存储交易列表。 它只有一个根哈希值。 如何证明这笔交易是真实的？ 在一个街区？

Merkle proof需要做的是通过区块中区块头中Merkle Tree的根哈希值来证明某个交易存在于这个区块对应的Merkle Tree中。 简单来说，就是验证Merkle Tree中是否存在某笔交易。 这也称为成员资格证明或包含证明。 这涉及默克尔树中从给定交易的数据节点到根节点的路径。

比如下图中，azure data节点就是要证明存在的事务。 这里，轻节点只有一个根哈希值是不够的。 需要向全节点请求下图中红色标记的三个哈希值，然后只需要在本地为交易的数据节点一步步计算并拼接哈希值，最后将其与根哈希值进行比较，以了解交易是否真正存在于默克尔树中。

上图：

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

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

对于一个轻节点，验证一个 merkle proof 的复杂度是多少？

假设底层有n笔交易，merkle证明的复杂度为θ(log(n))。

Merkle 证明可以证明某笔交易被包含在 merkle 树中，因此这种证明也称为成员资格证明或包含证明。

想一想：是否存在不安全的情况？ 如下图，我们要验证B，但是H(1)和H(4)都是全节点提供的。 全节点是否可以修改B，通过H(1)调整，使得修改后的H(1)和轻节点计算出的H(2)一起得到hash，仍然是H(3)？

其实这种情况是人为的哈希碰撞。 但是，从公开课的注释2中我们知道，由于hash函数的抗碰撞特性，这种情况是不会发生的。 从而保证了系统不可篡改的修改。 同时，这样的 Markle Proof 的事件复杂度是 O(log n)，非常高效【证明交易的存在】。 如果要证明交易不存在，如果不指定叶节点的排序顺序，则没有有效的方法来证明交易不存在。

在比特币系统中，没有相应的需求，所以在比特币系统中Markle Tree是没有排序的。

如何证明某笔交易不在默克尔树中？

那是非会员的证明。 您可以将整棵树传递给轻节点。 轻节点收到后，验证树的结构是否正确，每一层使用的哈希值是否正确，说明树中只有这些叶子节点。 你要找的交易里面没有，证明非会员证明。 问题是它的复杂度是线性的θ(n)，是一个比较笨的方法。

如果对叶子节点的顺序有一些要求，比如按照交易的哈希值排序。 每个叶子节点都是一笔交易，对交易的内容进行一次哈希，哈希值按升序排列。 要检查的交易先计算一个hash值，看看里面应该在什么位置。

比如第三个和第四个之间，此时提供的证明是第三个和第四个叶子节点必须上到根节点。 如果哈希值全部正确，并且根节点计算出的哈希值没有发生变化，则说明第三个和第四个节点确实是原始merkle树中的相邻点。 如果你要查找的交易存在，它应该在这两个节点之间。 但是它没有出现，所以它不存在。 它的复杂度也是以对数的形式，以排序为代价。 排序后的树称为排序默克尔树。

这种排序好的默克尔树在比特币中没有使用，因为在比特币中不需要证明不存在。

本节讲比特币中最基本的两种结构：区块链和默克尔树，它们都是用哈希指针构造的。

除了这两者之外，哈希指针还可以有另外一种用途。

只要数据结构是非循环的（非循环链表），就可以使用散列指针代替普通指针。 如果有环，则有问题。 它们的哈希值无法计算，无法确定一个固定哈希值的区块。