区块链学习笔记 | 比特币中的数据结构

本文介绍了比特币中的数据结构。 就算没学好数据结构，也能看懂~

1.哈希指针

这里需要用到的一个重要概念是哈希指针（hash pointers）一般用H( )来表示。

普通指针存储的是内存中某个结构体的地址，而哈希指针不仅存储地址比特币系统架构，还存储结构体的哈希值。 这样做的好处是，通过这个哈希指针，不仅可以找到结构体的位置，还可以检测结构体的内容是否被篡改过。

2. 区块链

“区块链是一个使用哈希指针的链表”

区块链到底是什么？ 顾名思义，区块链是由区块组成的链表。 它与普通链表的区别之一是使用了哈希指针，而不是普通的指针。 图为一个小区块链：

前面的块是系统中产生的第一个块（genesis block），最后一个块是最近的块（most recent block），每个块包含一个哈希指针H指向前一个块（），最后一个块也有一个指向它的 H( ) 保存在系统中。 H(·)是对前一个块的所有内容进行哈希处理得到的，这里所说的所有内容当然包括前一个块的哈希指针。

想想这样的数据结构有什么好处？

通过这样的数据结构，可以实现防篡改日志，也就是说，如果区块链中某个区块的内容被篡改，将会导致后续所有区块的内容发生变化。

由于比特币系统是去中心化的，部分节点可能存在恶意，无法判断部分节点是否正确，这时哈希指针就派上用场了。 因为下一个区块的H(·)是对前一个区块的所有内容进行哈希处理得到的，如果某个区块的内容被篡改，就会导致最终系统中保留的最后一个H(·)发生变化。

因此，对于一条区块链，我们只需要保存指向最后一个区块的哈希指针，就可以检测整个区块的内容是否被修改过。 正是由于这种性质，比特币系统中的一些节点不需要保存整个区块链的内容。

例如：A同学只保存了Y块及后面块的信息，不保存前面块的信息。 某天他需要用到之前区块X中的信息，于是他找到了同学B让他提供了区块X的信息，那么小A如何判断小B提供的区块信息是正确的呢？

此时，他只需要对区块X中的所有信息进行哈希处理，并将结果与​​区块Y中的H(·)进行比较，如果一致，则说明区块X中的信息没有被篡改。

3.默克尔树

也许你对默克尔树这个词有点陌生，但是你对二叉树（binary tree）一定很熟悉。 你可以把默克尔树看成是一种特殊的二叉树。 Merkle 树和二叉树的一个区别是 Merkle 树使用哈希指针而不是普通指针。

让我们看一个 Merkle 树的例子：

底层是data block数据块，上层是hash指针。 每两个相邻的块取hash并放入一个块中，逐个上去得到最上面的根节点。 根节点也可以取hash——root hash

对于这样的结构，只有根散列可以用来检测树的任何部分的修改。 原理和上面第二点说的区块链最后一个哈希指针的作用是一样的。 只要数据块中某个块的数据发生变化，就会影响到上层H(·)的变化，最终影响根哈希的变化。

在比特币中，每个区块都由一个哈希指针链接在一起，每个区块中包含的交易被组织成一棵默克尔树，即默克尔树中的每个数据块对应一个交易。

区块链中的每个区块由两部分组成：区块头和区块体。 区块头包含从区块中所有交易组成的默克尔树中获取的根哈希值root hash，但不包含交易信息，交易信息存储在区块体中。

Merkle树有什么用？

一个目的是提供 Merkle 证明。 比特币有两种节点，一种是全节点，一种是轻节点。 全节点保存了整个区块的内容，而轻节点，比如手机上比特币钱包的应用，是轻节点，只包含区块头。 那么就有一个问题，如何向轻节点证明某笔交易已经写入区块链？

比如小A转了一笔钱给小C，但是小C是轻节点，因为他只能在手机上查看，那么小C怎么知道这笔交易有没有写入区块链呢？ 这里将使用 Merkle 证明。

如图，最上面的蓝色部分是一个小区块链，最下面的一行是节点包含的交易。

假设待证明的交易tx在上图所示的位置，merkle proof指的是交易tx到默克尔根的路径，即红色H(·)和绿色H(·)的路径位于。

首先我们要知道，轻节点在默克尔树中并没有具体的内容，只有一个根哈希值，因为根哈希值是保存在区块头中的。 接下来我们看一下轻节点是如何知道要证明的交易tx是否包含在区块链中的。

轻节点向全节点发送请求比特币系统架构，请求Merkle证明，证明待证明的交易tx包含在Merkle树中。 全节点收到请求后，只需要将图中红色标记的哈希值H(·)发送给轻节点即可。 节点会做。 轻节点有了这些红色哈希值后，可以在本地计算绿色部分的哈希值，最后计算出根哈希值，与区块头中的根哈希值进行比较，得到这笔交易是否存在Merkle树，从而完成验证。

说到这里，可能有同学会想，因为红色部分的H(·)不需要轻节点验证，而我想篡改待证明的交易tx，那么只需要调整红色部分的H(·)即可红色部分使其被篡改交易的H(·)生成的哈希（即上一层的哈希）是正确的，那么篡改的目的没有达到吗？ 那么，这行得通吗？

理论上似乎可行，但实际上是不可能的。 回想一下上面提到的抗碰撞的性质。 上述篡改方案实际上是人为制造哈希冲突，但这是不可行的。 对于抗碰撞性质不熟悉的可以阅读上一篇文章中的相关内容。

综上所述，默克尔证明可以实现交易是否存在于默克尔树中的证明。 此过程也称为成员资格证明或包含证明。

小珍同学