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

北京大学肖真教授《区块链技术与应用》公开讲座笔记

比特币数据结构章节，对应肖老师的视频：

完整系列笔记请参考：

哈希指针(Hash pointer) Markle Tree使用哈希指针代替普通指针

上图是一个简单的Markle Tree，其中A、B、C、D是数据块。可以看出A和B各有一个hash值，并且组合在一个节点中。 C和D做同样的操作。然后，分别对得到的两个节点取哈希值，得到两个新的哈希值。 ，即图的根节点。实际上，区块头中存储的是根节点的哈希（再次哈希）。

如视频中的图片：

这种数据结构的好处是你只需要记住Root Hash（根哈希值），就可以检测到对树的任何部分的修改。

例如，如果绘制的 Markle Tree 中的节点 B 发生变化，则对应的第二层第一个节点中的第二个哈希值也会发生变化，那么根节点中的第一个哈希值也会发生变化。哈希值也会发生变化，导致根哈希也发生变化。

在比特币系统中，不同的区块通过哈希值指针连接，同一区块内的多个交易（数据块）以马克尔树的形式组织在一起。块本身分为两部分（块头和块体）。区块头中有根哈希值（没有交易具体信息），区块体中有交易列表。

马克尔树的实际用途

Markle Tree 可用于提供 Markle Proof。关于 Markle 证明，首先需要了解比特币系统中的节点。比特币中的节点分为轻节点和全节点。全节点保存整个区块的所有内容，轻节点只保存区块的区块头信息。

为什么要分轻节点和全节点？

由于硬件限制。块的大小为 1MB。对于移动便携设备，如果存储块的所有内容，则所需空间太大，这是不现实的。所以轻节点只需要存储区块头信息，全节点可以存储区块的所有内容。

当需要向轻节点证明某笔交易是否已写入区块链时，需要使用 Markle proof。我们将交易到根节点的路径称为 Markle 证明。全节点将整个 Markle proof 发送给轻节点（如下图），轻节点可以根据它计算出根哈希值，并与自己保存的进行比较。验证交易是否已写入区块链。只要按照这个路径比特币创世纪区块地址，所有的hash都是正确的，说明内容没有被修改过。

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

其实这种情况是人为造成的hash冲突。正如我们在公开讲义2中看到的，由于哈希函数的抗碰撞特性，这种情况不会发生。因此，保证系统无法运行。篡改。同时，这样一个 Markle Proof 的事件复杂度是 O(log n)，非常高效【证明交易的存在】。如果要证明交易不存在，如果不指定叶子节点的排序顺序比特币创世纪区块地址，就没有有效的方法。证明不存在。

在比特币系统中，没有相应的要求，所以马克尔树在比特币系统中没有排序。

一般来说，一般的链表我们都可以用哈希指针转化成链表，但是当链表有环时，就不能再使用哈希指针了。