02 BTC-数据结构

hash pointer：不仅可以找到前区块的位置，还能防止前区块是否被篡改。

Blockchain is a linked list using hash pointers.

如果对一个区块中数据进行修改（红色区块），那么之后所有区块的中相关的哈希值都得进行修改。

好处：只要记录最后一个哈希值，就可以检测出对区块链任何部位的修改（可以进行哈希比较，判断是否修改）。

有了这个性质，有些节点就不需要保存系统的全部节点了，只需要保留最近的几千个区块就行，如果需要用到其他区块，找其它节点去要就行。

但是，因为是一个分布式的系统，有些节点可能是有恶意的（下图所示），发来错误的区块，那么我们通过区块的哈希值进行区块正确性的辨别。

hash pointer是适用于没有环的情况。

Merkle tree

Merkle tree is a binary tree.

好处：只要记录根hash值，就能检测出对树中任何部位的修改。

Merkle tree是包含在block body中的。

Merkle的另一个好处，可以提供Merkle proof。

比特币系统，包括全节点和轻节点。

全节点：保存整个区块的内容；轻节点：只保存block header；

问题：如果要告诉一个轻节点，我转给你的交易已经完成了，轻节点如何验证交易是否被已经写到区块链中？

全节点提供Merkle Proof中需要的哈希值，轻节点进行哈希值的计算（轻节点无法计算其它交易的hash），最后对比计算出来的哈希值是否等于block head中Merkle tree root的哈希值。

问题：有没有觉得些许有些不太安全？（因为Merkle proof过程中的hash是全节点传过来的）

是不可行的，因为哈希函数具有collision resistance性质的存在。这就相当于人为制造哈希碰撞。

Merkle proof可以证明Merkle tree中包含了某个交易，所以这种证明也叫做proof of membership，或者叫proof of inclusion.

Merkle tree中证明某个交易存在的时间复杂度是O(log(n))，对数级别，比较高效。

那么，能够证明Merkle tree中没有某个交易呢？proof of non-membership？

一个简单的方法，把整个Merkle tree传给轻节点，轻节点对叶子节点上的交易进行验证，说明树中没有该交易。如果这样做的话，时间复杂度是O(n)，是线性的，比较低效。

如果我们不对叶节点的排列顺序做假设的话，是没有什么更高效的办法的。

但是，如果将叶子节点中交易的顺序按照哈希值进行排序，这种方式是可行的。

如果要找的交易的block hash在两个存在的相邻交易之间，那么就证明该交易是不存在的。

排好序的Merklee tree叫做Sorted Merkle tree.