1-bct数据结构

简介

hash指针

一般的指针：存放的是 结构体在 内存中的起始位置；

hash 指针：除了存放结构体在 内存中的起始位置，还需要 存结构体的hash 值，以保证不被篡改。

Genesis block ：起源块

每一个区块都包括了指向前一个区块的指针。

最后一个 H() 哈希值 在系统中，这样结构。

每一个 H() 都是由前一个 区块的全部内容 算出来的 哈希值，包括 前一个区块中存放的前前一个区块的 H 哈希值。因此 我一个区块的改动就会导致 后面每一个 H 值发生改变，因此，我只需要保存最后一个 H 值，就能保证前面的值 都是没有被改变的。

很多时候，我们只保留最近几个区块，如果要用到前面的区块的内容的话，就找前面的人要，给我们以后去算一算，确认一下有没有被篡改。

full node、light node

btc链 中的结点 分 轻结点（仅仅保存 block header） 全结点（保留block header和block body）；

钱包大部分都是轻结点。

merkle tree

叶子结点保存 data数据，上面的结点 都是 保存 H 值用的。

每一个 data 其实是一个交易。

hash树是一个区块的组成部分。区块分头和体。

block header： root hash 存这里面

block body： 包括交易列表

merkle tree 用来提供 merkle proof

一个转钱的例子，你说已经把前转给我了，我只有手机上的 轻结点，我如何知道 你的操作是不是已经写入了链中？这就是 merkle proof 的过程。

**merkle proof ** ：

proof of membership、proof of inclusion

最上面蓝色的表示一个 简单的区块链。这里展开了体现了一个 区块中的一个 merkle tree。

我们的轻结点要 检验 标黄的 tx 这一笔交易是不是包含在了这个merkle tree 中。

轻结点是没有保存 merkle tree 的具体内容的，只保存了这个 root hash 值。

轻结点向某个全结点发出请求，全结点就发出 几个红色的 H 给 轻结点，有了这几个红色的H以后，轻结点就能在本地计算出 绿色的几个H值，我们可以看出来，有一红一绿两个H，就又能把上一级的H算出来，拿着上一级的绿色的H，配合上一级的红色 又能算出上上级的 绿色H… 把最后算出的 红绿H 和轻结点手中的 红绿H对比，就可以验证 黄色tx 这笔交易了。

如想要 通过 篡改 红色H ，来 实现 被篡改的黄色 tx 的配平，来让上上级的绿色H保持正确，是不可行的，因为认为调整 红色H来达到某一个值，属于认为制造 hash 碰撞，和我们在 区块链的密码学原理中说到的 collision resistance 与 hiding 性质相矛盾，所以无法实现。

proof of membership

因为是二叉树，所以，证明 tx 在里面 ，从下往上算 hash，一步一步对比，和二分法从上往下的算位置的路径是一样的。所以时间复杂度就是 二方法的 O(logN)。

proof of non-membership

为了证明 tx 不在 tree 中，只能一步一步算每一个tx看看在不在里面。时间复杂度 O(N)，当然了，如果 tx 是排序好的，那时间复杂度自然可以低很多达到 O(logN)。

btc 不要求做这样的不存在证明，所以tx实际上是没哟排序的。

只要是无环的数据结构，都可以用hash指针来代替 普通指针。

每一个指针依赖前一个区块定下来，有环的话，会出现循环依赖。