以太坊中的Merkle树 (Merkling in Ethereum)
Merkle树是使区块链运作的基础部分。尽管从理论上讲绝对可以制造没有Merkle树的区块链，但仅通过创建直接包含每个交易的巨型区块头就可以了，这样做带来了巨大的可扩展性挑战，可以说使得除了最大多数以外的所有人都无法信任地使用区块链的能力。从长远来看功能强大的计算机。多亏了Merkle树，才有可能构建以太坊节点，该节点可以在所有大小型笔记本电脑，智能手机甚至物联网设备（如Slock.it生产的设备）上运行。那么，无论现在还是将来，这些Merkle树如何精确发挥作用，并提供什么价值？
首先是基础知识。从最一般的意义上来说，Merkle树是一种将大量“块状”数据hash在一起的方法，该方法依赖于将块拆分为多个存储桶，其中每个存储桶仅包含几个存储块，然后获取每个存储桶的hash并重复相同的过程，继续这样做，直到剩余的hash总数变为一个：根hash。
Merkle树最常见，最简单的形式是二叉Merkle树，其中一个存储桶始终由两个相邻的块或hash组成。它可以描述如下：
那么，这种奇怪的hash算法有什么好处呢？为什么不将所有块连接在一起成为一个大块，并在其上使用常规的hash算法呢？答案是，它允许使用称为Merkle证明的简洁机制：
Merkle证明由块，树的根hash和“分支”组成，其中“分支”由沿从块到根的路径上的所有hash组成。读取证明的人可以验证，至少对于该分支而言，hash在整个树上一直是一致的，因此，给定的块实际上位于树中的该位置。该应用程序很简单：假设有一个大型数据库，并且数据库的全部内容存储在Merkle树中，该树的根是公开已知且受信任的（例如，它已由足够的受信方进行数字签名） ，或者有很多工作证明）。然后，想要在数据库上进行键值查找的用户（例如“告诉我位置85273中的对象”）可以请求Merkle证明，并在收到证明后验证它是正确的，因此实际接收到的值在数据库中具有该特定根的位置85273处。它允许对少量数据（例如hash）进行身份验证的机制得以扩展，以对可能无限制大小的大型数据库进行身份验证。
比特币中的Merkle证明
Merkle证明的原始应用是在比特币中，正如中本聪（Satoshi Nakamoto）在2009年描述和创建的那样。比特币区块链使用Merkle证明来将交易存储在每个区块中：
这提供的好处是Satoshi将其描述为“简化的付款验证”的概念：“轻量级客户端”只下载块头链，每个块80字节的数据块，而不是下载每个交易和每个块，只包含五件事：
- 前一个区块头的hash
- 时间戳
- 挖掘难度值
- 工作证明随机数
- Merkle树的根hash，包含该块的交易事务
如果轻量级客户想要确定交易的状态，则可以简单地索要Merkle证明，以证明特定交易在Merkle树之一中，其根在主链的块头中。
这使我们走得很远，但是比特币风格的轻客户端确实有其局限性。一个特别的限制是，尽管它们可以证明包括交易，但它们不能证明有关当前状态的任何信息（例如，数字资产持有，名称注册，金融合同的状态等）。您现在有多少个比特币？比特币轻量级客户端可以使用一种协议，该协议涉及查询多个节点并相信至少其中一个会从您的地址通知您任何特定的交易支出，这将使您在该用例中走得更远，但对于其他更复杂的应用程序这还远远不够；交易影响的确切性质可能取决于几个先前交易的影响，而这些交易本身也取决于先前交易，因此最终您将必须对整个链中的每个交易进行身份验证。为了解决这个问题，以太坊将Merkle树概念更进一步。
以太坊的Merkle证明
以太坊中的每个块头不仅包含一棵Merkle树，还包含用于三种对象的三棵树：
- 交易次数
- 收据（基本上是显示每笔交易效果的数据）
- 状态
这允许高度高级的轻客户端协议，该协议允许轻客户端轻松地对多种查询做出并获得可验证的答案：
- 该交易是否包含在特定的区块中？
- 告诉我该地址在过去30天内引发的所有X类型事件（例如达成目标的众筹合同）的所有实例
- 我帐户的当前余额是多少？
- 这个帐户存在吗？
- 假设在此合同上运行此事务。输出是什么？
第一个由事务树处理；第二个由事务树处理。第三个和第四个由状态树处理，第二个由接收树处理。前四个很容易计算。服务器简单地找到对象，获取Merkle分支（从对象到树根的hash列表），然后使用该分支答复轻客户端。
第五个也由状态树处理，但是计算它的方式更加复杂。在这里，我们需要构造所谓的Merkle状态转换证明。本质上，这是一个证明：“如果在具有根S的状态上运行事务T，结果将是具有根S’的状态，且具有日志L和输出O”（“输出”作为概念存在于以太坊，因为每个事务都是一个函数调用；从理论上讲不是必需的）。
为了计算证明，服务器在本地创建一个假块，将状态设置为S，并在应用事务时假装为轻客户端。即，如果进行交易的过程要求客户确定账户余额，则轻客进行余额查询。如果轻客户端需要检查特定合同存储中的特定项目，则轻客户端对此进行查询，依此类推。服务器正确地“响应”其自己的所有查询，但跟踪其发送回的所有数据。然后，服务器将所有这些请求的组合数据发送给客户端，以作为证明。然后，客户端将执行完全相同的过程，但使用提供的证据作为其数据库；如果其结果与服务器要求的结果相同，则客户端接受该证明。
Patricia树
上面提到过，最简单的Merkle树是二元Merkle树。但是，以太坊中使用的树更加复杂-这就是您在我们的文档中听到的"Merkle Patricia树"。本文将不涉及详细规范；尽管我将讨论基本推理，但这是本文和本文中最好的方法。
二进制Merkle树是用于验证“列表”格式信息的非常好的数据结构。本质上是一系列的块，一个接一个。对于事务树，它们也很好，因为创建树后编辑多少时间都没有关系，因为先创建树然后再将其永久冻结。
但是，对于状态树，情况更为复杂。以太坊中的状态基本上由一个键值映射组成，其中的键是地址，值是帐户声明，列出每个帐户的余额，现时，代码和存储空间（存储空间本身是一棵树）。例如，Morden测试网的生成状态如下所示：
1 | { |
但是，与交易历史记录不同，状态需要经常更新：帐户的余额和现时经常更改，此外，经常插入新帐户，并且经常插入和删除存储密钥。因此，需要一种数据结构，在该数据结构中，我们可以在执行插入，更新编辑或删除操作后快速计算新的树根，而无需重新计算整个树。还有两个非常理想的辅助属性：
- 即使攻击者故意设计事务以使树尽可能深，它的深度也是有界的。否则，攻击者可以通过将树处理得如此之深以至于每个单独的更新变得极其缓慢，从而执行拒绝服务攻击。
- 树的根仅取决于数据，而不取决于更新的顺序。以不同的顺序进行更新，甚至从头开始重新计算树都不应更改根。
简单来说，Patricia树可能是我们可以同时实现所有这些特性的最接近的树。关于其工作原理的最简单解释是，将存储值的键编码为您必须取下该树的“路径”。每个节点有16个子节点，因此路径是通过十六进制编码确定的：例如，十六进制编码的密钥狗是6 4 6 15 6 7，因此您将从根开始，沿着第6个子节点向下，然后是第4个，依此类推，直到到达终点为止。 在实践中，当树稀疏时，我们可以进行一些额外的优化以使过程效率更高，但这是基本原理。 上面提到的两篇文章更详细地描述了所有功能。