【北大肖震-区块链技术与应用笔记】第二堂课

文章目录

【北大肖震-区块链技术与应用笔记】第二课1.哈希指针

普通指针存放的是内存中某个数据的首地址。 哈希指针不仅保存了地址，还保存了结构体的哈希值。 通过哈希指针不仅可以找到数据所在的位置，还可以检测数据是否被篡改（因为保存了哈希值）。

2. 区块链

区块链是块的链表。 与普通链表相比有一些区别。

区块链用哈希指针代替普通指针

取哈希时，将整个区块的内容（包括其存储的指向下一个区块的哈希指针）一起哈希

可以使用此数据结构实现防篡改日志

该属性意味着无论哪个区块发生变化，都会导致系统中存储的哈希值发生变化，即只要记录了哈希值，就可以检测到区块链中的任何一个位置都被篡改过。修改的。 如果前一个块发生变化，则后续块将发生变化，直到系统中的哈希指针发生变化。

这就是与普通链表的区别。 普通链表可以修改其中的任意节点，对整个链表中的其他节点没有影响。 但是，修改区块链中的一个区块将影响其后生成的所有区块。 .

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

例如，只保存下图中红线右侧较新的块。 如果你想使用圈出的块，你可以向别人索取。 保存的哈希指针可以检查给定的块是否正确比特币买了后怎么保存，只需使用保存的哈希指针来验证下一个块，然后取已验证块的哈希指针去下一个块。 验证下，如此反复就可以了。

3.默克尔树

Merkle Tree：使用哈希指针代替普通二叉树中的普通指针。 叶子节点最底层是一个数据块，它上面的几层非叶子节点存储哈希指针。

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

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

节点

在区块链中，每个区块都分为区块头和区块体两部分。 由该区块包含的所有交易组成的 Merkle Tree 的根哈希值存储在区块头中。 区块体中只存储交易列表。

比特币中的节点分为两类：全节点和轻节点

1️⃣全节点：既有区块头又有区块体的区块，存储着交易的具体信息。

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

❓ 如何向轻节点证明一笔交易被写入了区块链？比如有人将比特币转给自己，如何证明这笔交易已经在区块链中

使用 Merkle 证明：

区块中区块头中Merkle Tree的根哈希值比特币买了后怎么保存，证明某笔交易存在于该区块对应的Merkle Tree中。 简单的说，就是验证Merkle Tree中某笔交易的存在性，也称为Make proof of membership或proof of inclusion。 这涉及默克尔树中从给定交易的数据节点到根节点的路径。

轻节点需要向全节点请求图中红色标记的三个哈希值，然后只需要在本地为交易的数据节点计算并拼接哈希值，最后与根进行比较哈希值。 要知道这个交易是否真的存在于这个 Merkle Tree 中。

❓ 如何获取全节点请求：可以让转钱的人来发，因为第一课学的抗碰撞的性质，没办法伪造这些红色的部分，所以hash值交易和拼接后得到的哈希值保持不变。 ——人为制造哈希冲突是不可行的

假设有n笔交易（叶子节点）

Merkle证明验证Merkle Tree中一笔交易的存在，Merkle证明的时间复杂度为θ(log⁡n)\theta(\log n)θ(logn)

验证Merkle Tree中是否存在某笔交易：使用**sorted Merkle Tree**，排序后进行二分查找，当找到交易时，必须对其进行Merkle证明，如果没有找到交易，比较其哈希值较小的节点和哈希值较大的节点（即哈希值排序后的邻居）进行Merkle证明。

不需要证明某笔交易在比特币中不存在，所以不需要上面排序好的Merkle Tree

只要数据结构是非循环的，就可以使用散列指针代替普通指针。 环会导致保存的哈希值的循环依赖。

参考

1. 比特币和加密货币技术：综合介绍

2. 以太坊白皮书、黄皮书、源代码

3. Solidity 文档

4. 北京大学肖震老师《区块链技术与应用》公开课系列笔记

5.【区块链学习笔记】2：比特币中的数据结构