本文从翻译Vitalik Buterin 的一篇博客开始介绍三个概念:
- Merkle Tree: 默克尔树
- Merkle Patricia Tree: 默克尔帕特里夏树
- Merkle Proofs: 默克尔证明
概述
Merkle Tree是区块链的一个基础概念; 虽然可以通过构造包含所有交易的区块头的方式而不使用Merkle Tree, 但是如此笨重的设计注定让区块链无法走的更远。感谢Merkle Tree让以太坊可以运行在小型设备上:智能手机,平板电脑,甚至是slock.it即将生产的IOT设备。
Merkle Tree到底是何方神圣?下面我们娓娓道来。
最简单的Merkle Tree的形式是下图展示的这种二叉树。每个节点有两个孩子, 叶子节点是数据的哈希值。
为什么像上图这样设计呢? 因为这种结构可以提供一种叫Merkle Proofs的机制。
如上图所示, Merkle Proofs包含三部分: 待验证的块数据的哈希(如图中的9Dog:64), 根哈希(如图中的6c0a), 验证路径(图中黄色部分: 1FXq:18, ec20, 8f74)。
证明验证过程:
- 9Dog:64和1Fxq:18 求哈希。
- 上步结果和ec20求哈希。
- 上步结果和8f74求哈希。
- 上步结果和根哈希(6c0a)比对是否一致。
比特币中的Merkle Proofs
Merkle Proofs最早应用在比特币中, 如下图所示比特币用所有交易的哈希构造了一颗Merkle Tree, 而Merkle Tree的根哈希写在区块头中:
之所以这样做的目的是因为这种设计可以支持SPV(简单支付验证): 为了验证一笔交易无需下载所有区块和交易信息, 只需下载80字节的区块头就可以了。区块头包含5类数据:
- 前一个区块头的哈希
- 时间戳
- 挖矿难度
- 工作量证明nonce
- 上一段提到的所有交易组成的Merkle Tree的根哈希
如果客户端想验证一笔交易的可靠性, 只需要按照上述的Merkle Proofs过程提供交易哈希和路径, 再经过一系列哈希运算后比对根哈希就可以了。
这样客户端避免了下载所有区块数据进行交易验证的噩梦, 我们称这种客户端为轻客户端。
但是上述过程虽然可以验证一笔交易的有效性, 但是它无法提供更强大的能力。 例如它无法提供验证一个账号当前持有多少资产? 虽然轻客户端可以查询多个节点并且通过某种协议保证了至少一个可信节点返回的是真实的信息来查看账户余额, 但是这样做无疑更复杂。
所以为什么不从一开始的数据结构上就解决这类问题呢? 以太坊设计正是为此而来。
以太坊中的Merkle Proofs
以太坊中的区块头包含三颗Merkle Tree, 分别是: 交易树, 单据树, 状态树。
这种设计使得更复杂的轻客户端协议成为可能, 甚至可以处理以下问题:
- 这笔交易已经包含在一个区块了么? (交易树可以处理)
- 告诉我过去30天, 这个地址触发的所有X事件的信息(类似前一段火爆的ico的智能合约) (单据树可以处理)
- 我的账户现在有多少余额? (状态树可以处理)
- 这个账户是否存在? (状态树可以处理)
- 如果执行这笔交易会发生什么? (比较复杂, 不说明了)
帕特里夏树
最上面我们介绍了二叉的Merkle Tree形式; 对于交易树而言这种二叉的数据结构已经非常优秀了, 因为交易树是一次性计算写入后再也不会改变的,所以它对计算效率的要求并不高。
但是对于状态树情况就比较复杂了, 比如以太坊中的状态是一个key-value的map。key是账户地址, values则包含了每个账户的balance,nonce,code 和 storage。下面是测试网络上的状态数据的描述:
{
"0000000000000000000000000000000000000001": {
"balance": "1"
},
"0000000000000000000000000000000000000002": {
"balance": "1"
},
"0000000000000000000000000000000000000003": {
"balance": "1"
},
"0000000000000000000000000000000000000004": {
"balance": "1"
},
"102e61f5d8f9bc71d0ad4a084df4e65e05ce0e1c": {
"balance": "1606938044258990275541962092341162602522202993782792835301376"
}
}
不同于交易树, 状态树因为交易的发生,账户的新增等动作会频繁的进行插入,更新等操作。如何让树的插入和更新变得高效, 我们需要一种新的树形数据结构,新的数据结果需要具备两个特性:
- 树的深度有限,哪怕收到攻击使得树的深度持续增加。否则树深度过大会导致计算缓慢而无法正常服务。
- 树根哈希的计算仅依赖数据,不依赖更新的次序。无论对树更新的次序如何根哈希的结果是确定的。
帕特里夏树是最符合我们需求的了, 一句话解释什么是帕特里夏树: 每个节点有16个孩子表示路径, 分别代表了16进制的的16个字符。例如path为dog的16进制表示是: 6 4 6 15 6 7, 查找它的过程就是从根节点开始找到低6个孩子,然后进入下一层对应节点找到第4个孩子...依此类推。
后计
上面是对Vitalik Buterin(以太坊创始人)博客的翻译, 整体内容比较浅显没有涉及具体的知识点, 算是介绍性的博客。
下面列一些有价值参考资料: