二、区块链技术与应用-比特币的数据结构

哈希指针（hash pointer）：

        传统指针：传统指针存着一个内存位置的地址

        而哈希指针不仅保存着位置的地址 也保存着这个内存内容的哈希值 从而检测这个内容有没有被篡改

Question: 我们都知道c++ stl中也有链表 是一个个结点链起来形成了一个链式结构 那么区块链和链表有什么区别呢？

区块链里用哈希指针代替了普通指针

如上图所示 就是一个区块链的样式图 第一个区块是世界上第一个比特币的区块 叫创世纪块 之后每一个区块里的H( )就是一个哈希指针 每个哈希指针里的哈希值是基于上个区块所有的内容得出来的 一个套着一个 直到最后一个保存在自己电脑里的哈希指针指向最近产生的区块

也就是说 前一个区块的任何一点改动都会影响后面的所有区块的哈希指针 就像是多米诺骨牌效应一样，然而最终必定会影响到保存在自己电脑上的那个哈希指针

所以说 最后这个哈希指针就是用来验证前面的区块有没有被改动过 只要这个哈希指针不变 那么整个区块链就没有被篡改 所以通过这样的数据结构就可以形成tamper-evident log

有了这个性质之后 比特币中有些节点就不需要保存整条区块链里的内容了 可以只保存最近的几千个区块 如果用到之前的区块 可以向系统中其他节点索要 

Question： 然而有些节点是带有恶意的 在去中心化系统下 如何知道别人给的区块是正确的呢？

这时便用到了哈希指针 问其他节点要来的区块 只要在连接处看一下拿过来的区块的哈希值能不能与我自己哈希指针里的哈希值对应上就可以了

比特币中的另一个数据结构叫Merkle tree

或许很多人没听说过Merkle tree 但是却听说过binary tree

Merkle tree就是把binary tree里的普通指针换成了哈希指针

 最下面一行叫数据块 每一个数据块得出一个哈希值 放在第三行的哈希指针里维护 第三行的两个哈希指针的哈希值合并成一个被第二行的哈希指针维护 第二行的两个哈希指针的哈希值又合并成一个被第一行根结点中的哈希指针维护着 最后一个根哈希指针维护着根结点

只要记住根哈希值 就能检测对整个树中任意一个位置的修改 

也就是说 根哈希值保护着整棵树

Question： 我们都知道比特币中的两个数据结构区块链和Merkle tree 那么这两个数据结构有什么关系呢？在比特币中是如何体现的呢？

在大的维度上讲 区块链作为主体数据结构 而区块链中的每一个区块里的数据 也可以说是区块内部存储的一条条交易信息 是使用Merkle tree的数据结构进行维护的

每一个区块都是由两个部分组成——block header 和 block body （区块头 和 区块身）

我们再次回到Merkle tree 树中的数据块可以看作这个区块的每一笔交易 这每一笔交易最终形成的根哈希值(root hash)是存在block header 也就是区块头里的

但是block header里没有交易的具体内容 只有一个根哈希值 而block body里却是有交易的列表的

 Question：那么merkle tree这种数据结构在区块里有什么用呢？

一个作用就是提供了Merkle proof

比特币中的节点分为两类：

1.全节点：保存整个区块的内容 包含交易信息 -> 即有block header里的hash root 也有block body里的交易信息（数据块）

2.轻节点：比如手机上的比特币钱包应用 只保存block header

Question：那么在轻节点中如何知道交易的信息呢？就好比说别人给我转了钱我怎么知道已收到呢？

那么这时候就需要用到了Merkle proof 

 再来看新的这幅图 从最底下黄色的这个数据块 一直向上走（图中标注的地方） 这整一条线 就是Merkle proof

当轻节点拿到这样一个黄色的交易信息 它向要知道这个交易是不是正确的 该怎么做呢？

首先 轻节点会向全节点发出请求 拿到图中三个红色圈圈的哈希值 

然后 把拿到的需要去验证的黄色交易取哈希值 得到了第三行绿色的哈希值 与第三行请求拿来的哈希值一起得出了第二行的绿色哈希值

然后 把第二行本地得到的绿色哈希值与请求得来的红色哈希值一起得到了第一行根结点的绿色哈希值

最后 把根结点中的绿色哈希值与请求得到的红色哈希值得到了最终的root hash 也就是轻节点存储的根哈希值

这一整套的路线证明 也叫做Merkle proof 只要从下往上验证 沿途的哈希值都是正确的 最终与我block header里保存的root hash是一样的 那么就证明这条交易确实在这个区块中

也就如开头所说 只要root hash没有改变 那么就证明整个树里的内容都没有被改动过

Question：这时我们引申出一个安全性的问题，如果有人打算伪造交易信息并给出一个假的Merkle proof 这种可行吗？

答案还是理论可行 实际几乎不可能 因为这整个proof最终得到的这个root hash 是要与我轻节点本地做比较的 如果黄色的交易信息被篡改 那说明第三行的绿色哈希值就会改变 那么意味着在整一条线路中 需要伪造红色的哈希值来使得最终的root hash保持不变

我们都知道collosion resistance 这其实就是在制造人为哈希碰撞

这个难度有多大呢 还是那句话 这个概率小于地球爆炸概率

Merkle proof 也叫做

proof of membership

proof of inclusion

Question：那么在轻节点中以Merkle proof去验证交易信息数据块的效率是什么样的呢？

假设需要验证n个数据块 在树的数据结构中 其复杂度为 (log(n)) 这个是相对高效的

Question：那如果证明Merkle tree里面没有包含某个交易呢？即proof of non-membership

这个复杂度为 (n)  是线性的 不是对数级别的 是否还存在更高效的方法呢？

如果我们对叶结点的排列顺序做任何假设的话 显然是没有的 因为我们必须把所有的叶结点都遍历一遍 才能知道某个结点不属于这个范围中

这时如果我们对所有的叶结点的哈希值进行从小到大的排序 那么就存在更高效的方法：

我们先把要证明不存在的结点取哈希值 这时因为树中的叶结点已经排过序了 我们就能很轻松的定位这个要证明的结点应该出现的位置 如果这个结点存在左右两个结点 且左结点和右结点作为相邻的两个结点向上走都是正确的 最终得到的root hash也是匹配的 那么就说明这两个结点在树中确实就是两个相邻的结点 

那么这个复杂度就是(log(n)) 代价就是需要对叶结点提前进行排序

这种排好序的叫做：

Sorted Merkle tree

比特币中没有使用这种排好序的merkle tree 因为比特币中没有需求做不存在的证明

总结：

        说了这么多 其实比特币中运用的两种数据结构无异于就是把链表和二叉树中的普通指针变成了哈希指针 而哈希指针在大多数情况下都可以替代普通指针使用 除了一种情况：

也就是循环结构 因为哈希指针也包含着区块内容的信息 这导致每一块的哈希指针都依赖于前一块的内容 在循环结构中 会形成循环依赖 所以不可行 

 ⚠️备注：

        既然已经有了整体的框架 在后续的文章中 会涉及内部的具体实现