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

比特币中的数据结构

哈希指针

比特币数据结构中使用的重要概念是哈希指针

普通指针是指结构在内存中的位置。

p是指向结构体的指针，然后p将结构体的起始位置存储在内存中。

哈希指针除了存储地址之外，还存储结构的哈希值H()。

这样做的好处是指针不仅可以有结构的位置信息提币时哈希值什么时候生成，还可以验证结构的内容没有被篡改，因为我们保存了它的hash值。

比特币中最基本的数据结构之一是区块链。什么是区块链？它是一个由块组成的链表。

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

区块链和普通链表有什么区别？

一个区别是使用哈希指针而不是普通指针。

第一个块是第一个块，创世块，最近的块是最近的块。每个块前面都有一个哈希指针。

这种数据结构有什么好处？

整个块被散列在一起。我们可以通过这样的数据结构实现防篡改日志防篡改日志。

例如，如果有人篡改了区块链中的某个内容，结果会是什么？

被篡改内容的最后一个哈希指针不匹配。所以我只保存最后一个hash，就可以保证之前的所有数据都没有被篡改过。

在一个普通的链表中，我们可以改变一个元素而不影响其他块。区块链影响整个身体。我只要保存最后一个哈希值，就可以保证整个区块链是完整的。我们只需要保存最近的几千个区块的数据，不需要保存整个区块，需要的时候向别人索取即可。

有些节点可能是恶意的，所以我们需要验证是否可以计算出给我们的区块的哈希值是否等于我们保存的哈希值。

默克尔树

比特币中的另一个数据结构是默克尔树。您可能没有听说过 Merkle 树，但您听说过二叉树。两者有什么区别？

一个区别是使用哈希指针而不是普通指针。

这是一棵默克尔树

底层是数据块

以上都是哈希指针

哈希是通过两对组合，一层一层向上推，最后根节点也取哈希，称为根哈希值root hash

只要记住给节点取散列的散列值，整个结构的值就可以得到保护。

比特币中的各个区块通过哈希指针连接起来，每个区块中包含的交易以默克尔树的形式组织起来。底层数据块的每一个区块其实就是一个交易tx（transaction）。

每个区块可以分为区块头和区块体两部分。

块头块体

默克尔树有什么用？

提供默克尔证明

比特币有两种节点，一种是全节点，一种是轻节点。

比如手机上的比特币钱包就是轻节点提币时哈希值什么时候生成，只保存区块头。那么轻节点如何知道交易是否已经存入区块链呢？这时候就用到了默克尔证明。

从交易节点回到根节点，这称为默克尔证明。

假设轻节点想知道黄色交易tx是否包含在默克尔树中，该怎么做？

先将绿色hash值与红色hash值拼接计算上一层的绿色hash值，再与红色hash值拼接，以此类推，计算出根hash值, 全节点 这可以通过将此哈希与根节点的哈希进行比较来证明。

轻节点只需要自下而上验证，只要一路上的hash值正确即可。轻节点只有区块头。检查时只能交易这条链的哈希值。只需用数据验证部分的hash值即可。

这个证明过程是不是有点不安全？

因为我们的验证过程只能验证现有链，这实际上提供了一定的修改自由度。

这里使用碰撞阻力。修改交易内容其实就是人为地做哈希冲突。

这种证明也称为成员证明，或包含证明

对于轻节点，你发给我一个默克尔证明，我要验证一下，时间复杂度是多少？

那么非会员证明的时间复杂度是多少？

它是线性时间复杂度。

我们正在寻找的交易可以出现在叶子节点的任何地方。但是如果我们把这个叶子节点的内容的哈希值，按照哈希值的大小从小到大排序，那么就有一个很好的排序方法。我要查的交易先计算hash值，然后找到这个hash值在叶子节点中的位置，统计相邻的两个叶子节点，这样所有的hash值up都是正确的，交易可以保证在原默克尔树中。

这种排序称为有序默克尔树。比特币没有使用这种默克尔树，因为比特币不需要证明不存在，也没有这种硬性要求。

除了这两种结构之外，还有什么地方可以使用散列指针呢？

那么带环的结构有什么问题？