Merkle树是使区块链发挥作用的基本组成部分。虽然理论上可以在没有Merkle树的情况下制作区块链（只需创建直接包含每笔交易的巨型区块），但这样做会带来巨大的可扩展性挑战，可以说大多数功能强大的电脑都没有运行这种区块链的能力。感谢Merkle树，使以太坊可以运行在所有计算机和笔记本电脑上，智能手机甚至是物联网设备也可以。那么这些Merkle树究竟是如何工作的，它们现在和未来都有什么价值呢？
首先，基础知识。从最普遍的意义上讲，Merkle树是一种将大量“数据块”哈希在一起的方法，它依赖于将数据块拆分成不同部分，其中每个部分又可以包含几个小部分，然后取每部分的哈希值并重复相同的过程，继续这样做，直到剩余的哈希总数只变为一个：根哈希。
Merkle树最常见和最简单的形式是二元Mekle树，其中一个桶总是由两个相邻的块或散列组成; 它可以描述如下：
那么这种奇怪的哈希算法有什么好处呢？为什么不将所有块连接成一个大块并使用常规哈希算法呢？答案是它允许一种称为Merkle样张 Proof的简洁机制：
Merkle证明包括一个数据块，树的根哈希，以及由从该数据块到根的路径上的所有哈希组成的“分支”。阅读证明的人可以验证哈希（至少对于该分支）在Merkle树中从该数据块一直往上到根哈希是一致的，以此证明给定的块确实原本就是在树中的那个位置。Merkle的应用很简单：假设有一个大型数据库，并且数据库的全部内容都存储在Merkle树中，其中Merkle树的根是公开的并且是可信的（例如，它由可信方进行数字签名，或者由proof of work证明）。然后，想要在数据库上进行键值查找的用户（例如“告诉我位置85273中的对象”）可以要求Merkle Proof来证明索要查找的值确实是在具有该特定根的数据库中的位置85273。它可以被用于认证的小量数据，如哈希，也可以扩展到也验证很大的数据库。
比特币中的Merkle证明
Merkle proof最开始应用是在比特币中，由Satoshi Nakamoto在2009年描述和创建。比特币区块链使用Merkle样张来存储每个块中的事务：
这提供了Nakamoto描述为“简化的支付验证”的功能：不用下载每个交易和每个区块，“轻客户端”只需下载Block Header，Block Header的80字节数据只包含五项：
前一个标题的哈希值
时间戳
采矿难度值
工作证明nonce随机数
Merkle树的根哈希，包含该块的tx。
如果轻客户端想要确定一个tx是否在链中，它可以简单地索取Merkle证明，该证明表明特定tx处于一个Merkle哈希树中，这个哈希数的根哈希位于主链的某个区块的Block Header中。
这让我们走得很远，但比特币式的轻型客户确实有其局限性。例如，虽然他们可以证明某个区块包含某个交易，但他们无法证明当前的状态（例如，数字资产持有，名称注册，金融合约的状态等）。你现在有多少比特币？比特币轻客户端可以使用一个协议，该协议涉及查询多个节点，并相信其中至少有一个会通知您地址中的任何特定交易支出，这对于该用例非常有用，但对于其他更复杂的应用程序它还不够; tx效果的确切性质可能取决于几个先前交易的影响，这些tx本身依赖于以前的tx，因此，最终您必须验证整个链中的每个tx。为了解决这个问题，以太坊将Merkle树概念向前推进了一步。
以太坊中的Merkle证明
以太坊中的每个Block Header不是仅包含一个Merkle树，而是包含三种objects的三种树：
Transaction交易 树
收据Receipts（实质上是显示每笔交易影响的数据）树
状态State 树
这允许使用更高级的轻客户端协议，允许轻客户端轻松制作或者获得多种可以被验证为正确的对问题的查询答案（以下是问题）：
此交易是否已包含在特定区块中？
告诉我过去30天内该地址发出的X类型的事件（例如，达到目标的众筹合同）的所有情况
我帐户的当前余额是多少？
这个帐户存在吗？
5、假装在此合同上运行此交易。输出会是什么？
第一个由tx树处理; 第三个和第四个由状态State树处理，第二个由收据Receipt树处理。前四个计算相当简单; 服务器只是找到对象，获取Merkle分支（从该对象到树根的哈希列表）并返回此分支给light客户端。
第五个也由状态树处理，但计算方式更复杂。在这里，我们需要构建一个可以称为Merkle状态转换证明Merkle state transition proof的东西。从本质上讲，它是一个证据，用来声明“如果您在带有Merkle根root的状态State下，运行tx T，结果将是具有root的状态S'，同时给出记录L和输出O”（“输出”作为以太坊中的概念存在，因为每个tx都是函数调用;它在理论上不是必要的）。
为了计算该证明，服务器在本地创建一个fake block假块，将状态设置为S，并假装是一个轻客户端去执行tx。也就是说，如果执行tx的过程要求客户确定某个帐户的余额，则此轻客户端会进行余额balance查询。如果轻客户端需要检查特定合约的存储中的特定项目，则此轻客户端会对其进行查询，依此类推。服务器正确地“响应”它自己的所有查询，但跟踪它发回的所有数据。然后，服务器将来自所有这些假的轻客户端请求的数据的组合作为证据发送给真的客户端（此客户端应该是提出这第5个查询的客户端）。然后客户端执行完全相同的过程，但使用提供的证据作为其数据库; 如果其真实执行的结果与服务器声明的结果（也就是服务器作为假的轻客户端执行之后然后发回的结果）相同，则客户端接受证明。
帕特里夏树Patricia Trees
上面提到最简单的Merkle树是二元Merkle树; 然而，以太坊中使用的树木更复杂 - 这是您在我们的文档中听到的“Merkle Patricia树”。本文不会详细说明; 推荐两边文章看https://github.com/ethereum/wiki/wiki/Patricia-Tree与https://easythereentropy.wordpress.com/2014/06/04/understanding-the-ethereum-trie/，在本文我也会做一些基本的说明
二叉Merkle树是非常好的数据结构，用于验证“列表”格式的信息; 基本上就是，一系列的块一个接一个。对于tx树（上文提到的第一种树）来说，应用二叉Merkle树很好，因为一旦树被创建，编辑树所花费的时间并不重要，因为树被创建一次然后永久不变。
然而，对于状态说树，情况复杂一些。以太坊中的状态基本上由键值映射组成，其中键是账户地址，值是帐户声明account declarations，account declarations列出了每个帐户的余额，随机数，代码和存储（存储本身就是树）。例如，Morden testnet起源状态genesis State如下：
{
"0000000000000000000000000000000000000001": {
"balance": "1"
},
"0000000000000000000000000000000000000002": {
"balance": "1"
},
"0000000000000000000000000000000000000003": {
"balance": "1"
},
"0000000000000000000000000000000000000004": {
"balance": "1"
},
"102e61f5d8f9bc71d0ad4a084df4e65e05ce0e1c": {
"balance": "1606938044258990275541962092341162602522202993782792835301376"
}
}
然而，与事务历史不同，状态需要经常更新：帐户的余额balance和随机数nonce经常被更改，而且经常插入新帐户，并且经常插入和删除存储的密钥（the balance and nonce of accounts is often changed, and what's more, new accounts are frequently inserted, and keys in storage are frequently inserted and deleted）。因此，期望的是一种可以在插入，更新编辑或删除操作之后能快速计算新的树根，而无需重新计算整个树的数据结构。还有两个非常理想的次要属性：
树的深度是有限的，即使攻击者故意制作tx以使树尽可能深。 否则，攻击者可以通过操纵树来执行拒绝服务攻击，使得每个更新变得非常慢。
树的根仅取决于数据，而不取决于更新的顺序。 以不同的顺序进行更新甚至从头开始重新计算树得到的应该是相同的树根。
该Patricia树，简单来说，也许是我们可以来同时实现所有这些性能最接近的一种解决方法。关于它如何工作的最简单的解释是，存储value的key被encoded到您必须从树中取下的“路径path”中。每个节点有16个子节点，因此路径由十六进制编码确定：例如，key“dog”的十六进制编码的键是6 4 6 15 6 7，所以你将从根开始，沿着第6个child，然后是第4个，依此类推，直到你到达终点。在实践中，我们可以进行一些额外的优化，以便在树稀疏时使过程更有效，但这是基本原则。上面提到的两篇文章 更详细地描述所有功能。
网友评论