《区块链技术与应用》——数据结构

1.哈希指针

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

2、哈希指针除了存储地址外，还需要存储结构体的哈希值H()。

3、hash指针的好处：从hash值的hash指针中，不仅可以找到结构的位置，还可以检测结构的内容是否被篡改，因为我们保存了它的哈希值。

2. 区块链

在比特币中，其最基本的数据结构是由区块组成的区块链。

区块链和链表的区别1：哈希指针而不是普通指针

图为一个简单的区块链。 其中，每个区块根据自己的区块内容生成自己的哈希值。 此外，每个区块（创世区块除外）都存储前一个区块的哈希值。 需要注意的是，本块的哈希生成取决于本块的内容，本块的内容包含了前一个块的哈希值。 这确保了块内容不被篡改。

如果我们想破坏区块链的完整性。 B的内容被篡改，B的hash值保存在C中，所以C也要修改。 而C之后的block也要修改。 用户只需记住上一条区块链的哈希地址，即可检测区块​​链上的内容是否被篡改。

在实际应用中，一整条链可能会被切割并存放在多个地方。 如果用户只有其中一个，在使用前一部分区块数据时，可以直接向系统中的其他节点索取。 一致性可以判断给定的内容是否确实是区块链上的真实内容。

3.默克尔树

默克尔树（Merkle Tree）比特币创世纪区块地址，也俗称哈希树。 顾名思义，它是一棵存储哈希值的树。

Merkle树的叶子是数据块（数据块：交易数据块）的哈希值。 非叶节点是其相应子节点的串联字符串的散列。

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

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

3.1. 默克尔树的优点

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

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

3.2. merkletree的实际使用

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

为什么会有轻节点和全节点？

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

当需要向轻节点证明某个交易（标记为黄色的节点）是否已经写入区块链时，需要Merkle证明。 我们称从交易到根节点的路径为 Merkle 证明（绿色标记路径）。 全节点将整个Merkle proof发送给轻节点（如下图所示），轻节点可以据此计算根哈希值，与自己保存的比对，验证交易是否写入区块链. 只要该路径上的所有哈希都是正确的，内容就没有被修改。

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

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

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