概述
- Blockchain
- Merkle Tree
Blockchain
本质上是链表，只不过传统的链表的指针域存储的下一个节点的地址，Blockchain 的指针域则存储上一个节点的 Hash。
结构如上图，如果从左到右第二个区块被篡改。
因此后续的节点都使用的是哈希指针，所以必然会导致右边的两个区块的哈希指针发生改变。
所以系统只需要保存最后一个区块的 Hash 就可以检验整个区块链是否被篡改。
有了这些性质后节点就没有必要保存所有的区块，当需要其它区块的时候，可以向其它节点请求，得到之后通过验证 Hash 就可以知道这个区块是否被篡改过。
Merkle Tree
Blockchain的header中只需要保存root hash即可，这样对Blockchain取哈希的时候也只需要对header取哈希就行了，也能够起到防篡改作用。
那么假如我想知道某个block是否已经写在了Merkle Tree里，则可以向其它节点请求下图中紫色的 Hash，然后通过计算 Hash 就可以验证。
理论上恶意节点可以通过篡改某个区块的内容且使其 Hash 不变的情况下来欺骗其它节点，但目前的实际应用中是不可能的，因为这是在人为制造哈希碰撞，Collision resistance 可以很好地解决这个问题。
假如我想知道某个 block 是否不存在于 Merkle Tree 里，如果对叶结点的顺序没有特殊要求则需要遍历所有 block，但是如果 block经过排序，则可以在对数时间内进行验证。