区块链学习笔记（2）BTC数据结构

1.哈希指针（hash pointers）：一般的指针存储的是某个结构体在内存中的地址，哈希指针除了要保存结构体的地址外，还要保存这个结构体的哈希值。

通过哈希指针，我们不但可以找到结构体在内存中的位置，同时还可以检测出结构体的内容是否遭到了篡改。 因为我们记录了结构体的哈希值。
BTC中的最基本的数据结构就是区块链，即一个个区块组成的链表。
区块链与普通链表的区别：
用哈希指针代替了普通的指针。（Block chain is a linked list using hash pointers.）
如图为一个小型区块链示意图，最前面的区块区块为系统中产生的第一个区块（创世区块），最后一个为最近产生的区块。每个区块都包含指向前一个区块的哈希指针。最后一个区块也有一个hash pointer保存在系统中。

取哈希的时候是把整个区块中的内容合在一起取哈希（包括前面区块的hash pointer）。如下图所示。

通过这种数据结构可以实现tamper-evident log。只要记住最后一个哈希值，就可以检测出对区块链任意位置的修改。（多米诺骨牌效应）
BTC中的另一个数据结构是Merkle Tree。与一般的Binary Tree不同，Merkle Tree用哈希指针代替了一般的指针。

Merkle Tree数据结构的好处是只要记住了root hash，就能检测出对任一根节点的修改。
Merkle Tree可以提供Merkle Proof。
BTC中的节点分为两类，一类是全节点，一类是轻节点。全节点保存整个区块的内容，轻节点（如手机上的BTC钱包）只保存一个Block Header。
如何向一个轻节点证明某个交易写入到区块链？
假设某个轻节点想要验证蓝色的交易是否包含在此Merkle Tree中，该轻节点没有保存此Merkle Tree的具体信息，只保留了根哈希值。则其需要向全节点发出请求，全节点只需向轻节点提供下图红色部分的哈希值，轻节点便可进行验证。

Merkle Proof的时间复杂度为O(logn)。（Proof of membership/Proof of inclusion）
如何证明某个交易不在这个Merkle Tree上？Proof of non-membership：只能验证整个Merkle Tree，时间复杂度为O(n)，如果不对这个叶节点的排列顺序做任何假设的话，没有其他更高效的方法。
如果对叶节点的排列顺序做要求，对交易的内容取哈希后按从小到大排序，则存在效率更高的证明方法。

即通过验证小于该交易哈希和大于该交易哈希的两个叶子节点的路径上的所有哈希（即上图红色部分），如果完成验证，则证明该交易不在此Merkle Tree上。时间复杂度为O(logn)，但是需要提前排序。（Sorted Merkle Tree）
在BTC中不需要做不存在证明，因此BTC中不需要Sorted Merkle Tree。
只要是无环的数据结构，都可以用哈希指针来代替。

如果有环，会造成循环依赖。如上图所示。
原视频：北京大学肖臻老师《区块链技术与应用》公开课