默克尔树的古往今来

Merkle 树是使得区块链成为可能的基本组成部分。虽然从理论上讲，打造没有 Merkle 树的区块链是可能的，简单地通过创建直接包含每个交易的巨大区块头就可以，但是这样做会带来巨大的可扩展性的挑战，可以说，在很长的时间内除了最强大的计算机之外，其他任何人都无法可靠的使用区块链。借助 Merkle 树，可以构建在所有计算机和笔记本电脑上运行的以太坊节点，这些节点可以是大型和小型智能手机，甚至是物联网设备，例如将由 Slock.it 生产的设备。那么这些 Merkle 树究竟是如何工作的，他们现在和将来会提供什么样的价值？

首先，基础知识。就一般意义上说。Merkle 树是一种将大量「数据块」散列在一起的方式，这种方式依赖于将大量的数据拆分成桶，其中每个桶只包含几个块，然后获得每个桶的散列，并重复相同的过程，直到剩余的散列总数变成一个：根散列。

Merkle 树最常见和最简单的形式是二分 Merkle 树，其中一个桶总是由两个相邻的块或散列组成 ; 它可以描述如下：

那么这种奇怪的哈希算法有什么好处呢？ 为什么不把所有块连接在一起成为一个大块，并使用常规的哈希算法呢？答案是它允许一个称为 Merkle 证明的巧妙机制存在：

Merkle 证明由一个块（树的根散列）和由沿着从块到根的路径上的所有散列组成的「分支」组成。了解此证明的人可以验证散列，至少对于那个分支来说，在树上是一直保持一致，因此给定的块实际上在树中的那个位置。该应用很简单：假设有一个大型数据库，并且数据库的全部内容都存储在 Merkle 树中，其中 Merkle 树的根是公众已知和可信的（例如，它是由足够的受信任方进行数字签名的，或者有很多工作证明）。然后，想要在数据库上执行键值查询（例如「告诉我位置 85273 中的对象」）的用户可以要求 Merkle 证明，并且在收到证明后验证它是正确的，因此实际收到的值是在具有该特定根的数据库中的 85273 处。它允许了一种验证少量数据机制的存在，例如 hash，被扩展用来对可能无限大小的大型数据库进行身份验证。

比特币中的默克尔证明

正如中本聪在 2009 年所描述和创建的那样，Merkle 证明的原始应用是在比特币中。比特币区块链使用 Merkle 证明来存储每个区块的交易：

默克尔数证明提供的好处是中本聪描述的「简化支付验证」的概念：不必下载每笔交易和每个块，「轻客户端」只需下载区块头链，80 个字节的数据区块只包含五样东西：

如果轻客户端想要确定一个交易的状态，它可以简单地要求一个 Merkle 证明，证明一个特定的交易在 Merkle 树中，该 Merkle 树的根在主链的区块头中。

这让我们相当吃惊，但比特币风格的轻客户端确实有其局限性。一个特别的限制是，尽管它们可以证明交易被包含了，但它们不能证明关于当前状态的任何信息（例如数字资产持有，名称注册，金融合同状态等）。 你现在有多少比特币？比特币轻客户端可以使用涉及查询多个节点的协议，并相信至少其中一个节点会通过您的地址通知您任何特定的交易支出，这会让您对该用例感到满意，但对于其他更复杂的应用，这还远远不够；交易影响的确切性质取决于先前几笔交易的效果，而这些交易本身依赖于以前的交易，因此最终您必须验证整个交易链中的每笔交易。为了解决这个问题，以太坊将 Merkle 树的概念进一步拓展。

以太坊中的默克尔证明

每个以太坊中的区块头包含的不仅只是一个默克尔树的数据结构，而且还分别向三个默克尔数据库结构提供不同的对象：

这允许一个非常先进的轻客户端协议，它将使得轻客户容易地创建并获得针对多种查询的可验证答案：

第一个由交易树处理 ; 第三个和第四个由状态树处理，第二个由收据树处理。 前四项计算相当简单；服务器只需找到对象，就可以获取 Merkle 分支（从对象到树根的散列列表）并将分支回复给轻客户端。

第五个也是由状态树处理的，但它的计算方式更复杂。 在这里，我们需要构建可称为 Merkle 状态转移证明的东西。从本质上讲，它是一个证明，它使得声明「如果你在具有根 S 的状态下运行交易 T，结果将是一个具有根 S' 的状态，并且具有日志 L 和输出 O」（在以太坊中，「输出」作为概念而存在，是因为每个交易都是一个函数调用 ; 这在理论上是不必要的）。

为了计算证明，服务器在本地创建一个假块，将状态设置为 S，并在应用交易时假装成为轻客户端。也就是说，如果应用交易的过程要求客户确定帐户的余额，轻客户端会进行余额查询。 如果轻客户端需要检查特定合同存储中的特定条目，则轻客户端为此进行查询，等等。服务器正确回应所有自己的查询，但会跟踪它返回的所有数据。 然后服务器向客户端发送来自所有这些请求的组合数据作为证据。然后客户端执行完全相同的程序，但是使用查询反馈所提供的证据作为其数据库 ; 如果其结果与服务器声明的结果相同，则客户端接受该证明。

Patricia 树

上面提到，最简单的默克尔树是二分默克尔树 ; 然而，以太坊使用的树更复杂 - 这就是你在我们的文档中所听说的「Merkle Patricia 树」。本文不会详细说明 ; 但是我会讨论基本的原理，这篇文章和还有这一篇对此进行了最好的解释。

二分 Merkle 树是用于验证处于「列表」格式的信息的非常好的数据结构 ; 从本质上讲，是一系列的大块数据，一个跟着一个。对于交易树，它们也是很好的，因为树一旦被创建，然后就永久冻结，所以树被创建后，编辑树需要多少时间并不重要。

但是，对于状态树，情况更为复杂。以太坊的状态基本上由一个键值映射组成，其中键是地址，值是账户声明，列出了每个账户的余额，随机数，代码和每个账户的存储（这里存储本身也是树）。例如，Morden testnet 创始状态如下所示：

{ "0000000000000000000000000000000000000001": { "balance": "1" }, "0000000000000000000000000000000000000002": { "balance": "1" }, "0000000000000000000000000000000000000003": { "balance": "1" }, "0000000000000000000000000000000000000004": { "balance": "1" }, "102e61f5d8f9bc71d0ad4a084df4e65e05ce0e1c": { "balance": "1606938044258990275541962092341162602522202993782792835301376" } }

但是，与交易历史（固化）不同的是，状态需要频繁更新：帐户的余额和随机数经常更改，而且新帐户频繁插入，并且存储中的键经常被插入和删除。因此需要一种可以在插入，更新编辑或删除操作后快速计算新的树根的数据结构，而无需重新计算整个树。 还有两个非常理想的次要属性：

简而言之，Patricia 树可能是我们可以同时实现所有这些特性中最接近的解决方案。关于它如何工作的最简单的解释是，存储值的关键字被编码到必须记录下的树的「路径」中。每个节点有 16 个子节点，所以路径是由十六进制编码决定的：例如，编码的密钥狗十六进制是 6 4 6 15 6 7，所以你可以从根开始，沿着第六个子节点，然后是第四个子节点，然后，直到你到达最后。在实践中，当树很稀疏时，我们可以做一些额外的优化来使过程更加高效，但这是基本原则。 上面提到的两篇文章更详细地描述了所有的特征。

—-

编译者/作者：NervosFans

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。