概述

  • 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经过排序,则可以在对数时间内进行验证。

参考资料