比特币 (BTC) 数据结构

哈希指针（hash pointer）

普通指针存储结构在内存中的地址。

例如：

在下图所示的结构体中，P是指向它的指针，那么P存储的是结构体在内存中的起始位置，而hash指针不仅存储地址，还存储结构体Hash值的地址比特币为什么可以交易，这与节点中的内容有关。 当节点（区块）中的内容发生变化时，哈希值也会发生变化，从而保证区块的内容不会被篡改。

下图是一个小区块链：

front block是系统中第一个产生的块比特币为什么可以交易，称为创世块；

最后一个块是最近的块；

每个块都包含一个指向前一个块的哈希指针，最后一个块在系统中存储了一个哈希点。

这种数据结构的好处：

可实现防篡改日志（tamper proof record）

例如：

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

由于这种性质，比特币中的某些节点不一定要保存整个区块链的内容，而只能保存最后几千个区块。 如果你需要之前的区块，你可以将它们发送到系统中想要的其他节点。

默克尔树（Merkle tree）

如下所示：

最底层是数据块（data block）

上面的内部节点都是哈希点（哈希指针）

这种数据结构的优点：

你只需要记住根哈希（root hash value），你就可以检测到对树的任何部分的修改。

例如：

如果默克尔树中的底层节点发生变化，则上层对应节点的哈希值也会发生变化，那么根节点的哈希值也会发生变化，从而导致根哈希值发生变化。 变了。

比特币中的区块通过哈希指针链接在一起，每个区块中包含的交易被组织成默克尔树形状。

图中每个数据块其实就是一个交易，每个块又分为块头和块体两部分。

区块头中有一个根哈希值，意思是这个区块包含的所有交易组成的Merkle Tree的根哈希值存储在这个区块的区块头中，但是第k个区块头没有具体内容的交易，只有一个根哈希值。

区块体中有一个交易列表。

梅克尔树有什么用？

Merkle Tree 可以提供 Merkle Proof。

比特币中的节点分为轻节点和全节点。

全节点保存了整个区块的所有内容（包括区块头和区块体），并拥有交易的具体信息；

轻节点（如手机中的比特币钱包应用）只保存区块头信息。

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

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

这就带来了一个问题：如果需要向轻节点证明一笔交易写入了区块链，应该如何证明呢？ （比如你让我买东西转一笔钱给我，你告诉我转账的钱已经写入区块链网络，但是我是轻节点，只能在手机上查看电话，我怎么知道这笔交易是否已经写入区块链？）

这就需要使用Merkle证明来找到交易的位置，然后从这个交易到根节点的路径就是Merkle证明，如下图所有黄色节点路径。

完整的Merkle证明图如下图所示

顶行是一个小区块链，我们展示了其中一个区块的默克尔树，底行包含交易。

假设一个轻节点想知道黄色交易是否包含在Merkle Tree中，轻节点向全节点发送请求，请求一个可以证明黄色交易包含在Merkle Tree中的交易Merkle Proof，之后全节点收到这个请求，只需要将图中红色标记的哈希值发送给轻节点即可。 轻节点利用这些哈希值在本地计算根哈希值，并与自己保存的哈希值进行比较，从而验证交易是否写入区块链。 只要该路径上的所有哈希都是正确的，内容就没有被修改。

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

其实这种情况是人为的哈希碰撞。 由于哈希函数的抗碰撞特性，这种情况不会发生，保证了系统不可篡改。 同时，这样一个Markle Proof的事件复杂度是O(log n)，非常高效。

如果要证明交易不存在，如果不对叶子节点进行排序，就没有高效的方法来证明它不存在。

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