梅克尔树Merkle trees是什么？(以太坊）

86 阅读 0 评论 57 点赞

我是靠谱客的博主健壮硬币，最近开发中收集的这篇文章主要介绍梅克尔树Merkle trees是什么？(以太坊），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

http://www.btckan.com/news/topic/14827

梅克尔树（Merkle trees）是区块链的基本组成部分。虽说从理论上来讲，没有梅克尔树的区块链当然也是可能的，你只需创建直接包含每一笔交易的巨大区块头（block header）就可以实现，但这样做无疑会带来可扩展性方面的挑战，从长远发展来看，可能最后将只有那些最强大的计算机，才可以运行这些无需受信的区块链。正是因为有了梅克尔树，以太坊节点才可以建立运行在所有的计算机、笔记本、智能手机，甚至是那些由Slock.it生产的物联网设备之上。那么，究竟梅克尔树是如何工作的呢，它们又能够提供些什么价值呢，现在以及未来的？

上一区块头的哈希值

时间戳

挖矿难度值

工作量证明随机数（nonce）

包含该区块交易的梅克尔树的根哈希
如果一个轻客户端希望确定一笔交易的状态，它可以简单地要求一个梅克尔证明，显示出一个在梅克尔树特定的交易，其根是在主链（main chain，非分叉链）上的区块头。

交易（Transactions）

收据（Receipts，基本上，它是展示每一笔交易影响的数据条）

状态（State）

这笔交易被包含在特定的区块中了么？

告诉我这个地址在过去30天中，发出X类型事件的所有实例（例如，一个众筹合约完成了它的目标）

目前我的账户余额是多少？

这个账户是否存在？

假装在这个合约中运行这笔交易，它的输出会是什么？
第一种是由交易树（transaction tree）来处理的；第三和第四种则是由状态树（state tree）负责处理，第二种则由收据树（receipt tree）处理。计算前四个查询任务是相当简单的。服务器简单地找到对象，获取梅克尔分支，并通过分支来回复轻客户端。

树的深度是有限制的，即使考虑攻击者会故意地制造一些交易，使得这颗树尽可能地深。不然，攻击者可以通过操纵树的深度，执行拒绝服务攻击（DOS attack），使得更新变得极其缓慢。

树的根只取决于数据，和其中的更新顺序无关。换个顺序进行更新，甚至重新从头计算树，并不会改变根。
而帕特里夏树，简单地说，或许最接近的解释是，我们可以同时实现所有的这些特性。其工作原理，最为简单的解释是，一个以编码形式存储到记录树的“路径”的值。每个节点会有16个子（children），所以路径是由十六进制编码来确定的：例如，狗（dog）的键的编码为6 4 6 15 6 7，所以你会从这个根开始，下降到第六个子，然后到第四个，并依次类推，直到你达到终点。在实践中，当树稀少时也会有一些额外的优化，我们会使过程更为有效，但这是基本的原则。