Merkle树
什么是 Merkle 树?
Merkle 数是一种特殊的hash 树,顾名思义,就是存储hash值的一棵树。Merkle树的叶子是数据块(例如,文件或者文件的集合)的hash值, 非叶节点是其对应子节点串联字符串的hash.
在比特币里, 矿工把区块内所有交易(约1-2千笔)的哈希值一字排开,让他们两两牵手,每对交易哈希牵手后再算出新哈希。矿工验证、记录和整理交易的过程称为“打包”。 下面这棵树的顶点, 就是默克尔树根(Merkle Root)
Merkle 树解决什么问题?
Bitcoin发展到今天, 全节点的区块至少已经几百G, 让每个节点下载全部的区块并不是一个好主意. 因此有人提出了一个SPV的方案.
SPV= Simple Pay Verification. 是一种即使没有完整交易记录,也能便捷、安全地验证支付的方法。 不用下载全部区块(几百G),只需下载全部区块头(约40M),就能轻松验证所有支付.
Merkle的数据结构, 允许SPV节点能够方便的验证交易.
如何解决这个问题的?
SPV有两个前提:
- 每笔交易都有标准格式:输出地址、输入地址和交易金额等,所以交易一旦发生,该交易哈希值瞬间产生(假设为HK,图3绿框)。
- 如果交易被矿工打包过,拥有全部交易数据的节点(称为“全节点”:full node)必然有整棵默克尔树。
如果想要验证这个某笔交易是否存在, 验证步骤为:
- 用户A的钱包把某笔交易(假设为$H_k$), 提交给附近的全节点
- 全节点反馈A下载下图4个蓝块的哈希值。
- 第三步:A的钱包经过4步哈希计算:
- Hash($H_k$,$H_l$)
- Hash($H_ij$, $H_kl$)
- Hash($H_ijkl$,$H_mnop$)
- Hash($H_abcdefghijklmop$) 即:沿上图的虚线框路径,用户A的钱包最终得出哈希值$H_abcdefghijklmop$
- A钱包将
$H_abcdefghijklmop$
与钱包里已经下载好的默克尔树根
对比,若一致就能确认这笔交易存在
使用了以上方案后, 即使一个区块中交易再多,十来下就能搞定验证,假设区块里有2048个交易, 最多也只需要$lg(2048)=11$次
Merkle 树有什么缺点?
Merkle树是用空间换时间, 带来的代价是全节点需要存储更多的东西, 来记录Merkle的中间节点.
在Bitcoin的Merkle树比较简单, 只能做简单的验证功能. 以太坊扩展了Bitcoin的Merkle树, 允许做更多的功能. 譬如:
- 这笔交易被包含在特定的区块中了么?
- 告诉我这个地址在过去30天中,发出X类型事件的所有实例(例如,一个众筹合约完成了它的目标)
- 目前我的账户余额是多少?
- 这个账户是否存在?
- 假如在这个合约中运行这笔交易,它的输出会是什么?