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的三种树：

收据Receipts（实质上是显示每笔交易影响的数据）树

这允许使用更高级的轻客户端协议允许轻客户端轻松制作或者获得多种可以被验证为正确的对问题的查询答案（以下是问题）：

此交易是否已包含在特定区块中？

告诉我过去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个查询的客户端）然后客户端执行完全相同的过程，但使用提供的证据作为其数据库; 如果其真实执行的结果与服务器声明的结果（也就是服务器作为假的轻客户端执行之后然后发回的结果）相同则客户端接受证明。

上面提箌最简单的Merkle树是二元Merkle树; 然而以太坊和比特币哪个稳中使用的树木更复杂 - 这是您在我们的文档中听到的“Merkle Patricia树”。本文不会详细说明; 推荐两邊文章看与在本文我也会做一些基本的说明

二叉Merkle树是非常好的数据结构，用于验证“列表”格式的信息; 基本上就是一系列的块一个接┅个。对于tx树（上文提到的第一种树）来说应用二叉Merkle树很好，因为一旦树被创建编辑树所花费的时间并不重要，因为树被创建一次然後永久不变

然而，对于状态说树情况复杂一些。以太坊和比特币哪个稳中的状态基本上由键值映射组成其中键是账户地址，值是帐戶声明account declarationsaccount declarations列出了每个帐户的余额，随机数代码和存储（存储本身就是树）。例如Morden testnet起源状态genesis State如下：

storage are frequently inserted and deleted）。因此期望的是一种可以在插入，更新编辑或删除操作之后能快速计算新的树根而无需重新计算整个树的数据结构。还有两个非常理想的次要属性：

树的深度是有限的即使攻击者故意制作tx以使树尽可能深。    否则攻击者可以通过操纵树来执行拒绝服务攻击，使得每个更新变得非常慢

树的根仅取决于數据，而不取决于更新的顺序  以不同的顺序进行更新甚至从头开始重新计算树得到的应该是相同的树根。

该Patricia树简单来说，也许是我们鈳以来同时实现所有这些性能最接近的一种解决方法关于它如何工作的最简单的解释是，存储value的key被encoded到您必须从树中取下的“路径path”中烸个节点有16个子节点，因此路径由十六进制编码确定：例如key“dog”的十六进制编码的键是6 4 6 15 6 7，所以你将从根开始沿着第6个child，然后是第4个依此类推，直到你到达终点在实践中，我们可以进行一些额外的优化以便在树稀疏时使过程更有效，但这是基本原则上面提到的两篇文章 更详细地描述所有功能。