深入了解以太坊世界的状态

本文约4700字+，阅读（观看）需27分钟

以太坊由多个组件组成。 这篇文章旨在解构以太坊，让你更深入地了解它的数据存储层。 我们将介绍区块链中“状态”的概念，探索Patricia Trie数据结构的理论基础，并使用Google的leveldb数据库来说明前缀树在以太坊中的应用。 本文还附有分步学习指南，可以指导您安装和配置自己的以太坊私有网络（包括挖矿）。 学习后以太坊创世区块不能挖矿了，您将能够执行交易并发现以太坊的“状态”如何响应交易等活动而变化。

什么是区块链“状态”？

比特币的“状态”以网络中的全局未花费交易输出（UTXO）为特征。 比特币网络中的价值转移是通过交易进行的。 更准确地说，一个比特币用户可以使用一个或多个UTXO来创建一笔交易，所消耗的UTXO将作为交易的输入。

更详细地介绍 UTXO 超出了本文的范围，但在接下来的几段中，我们将继续引用这个概念来指出比特币和以太坊之间的基本实现差异。

接下来的两个比特币示例将指出比特币 UTXO 模型与以太坊世界状态概念之间的差异。

首先，比特币的UTXO是不能被分割消费的。 如果一个比特币用户想要花费 0.5 个比特币（他只有一个 UTXO 值 1 个比特币），他必须明确分配 0.5 个比特币的转账地址（给自己）作为找零。 如果他们不设置自找零，则将 0.5 BTC 转移给矿工作为包含交易的奖励。

第二点，在最底层，比特币不保存用户的账户余额。 在比特币中，用户在给定的时间点只持有一个或多个 UTXO 的私钥。 虽然数字钱包的设计就像比特币区块链自动保存和管理用户余额等，但事实并非如此。

用户的账户余额是比特币网络中的一个抽象概念。 实际上，一个用户的余额就是他所控制的每个UTXO（用户保管着对应的私钥）的价值总和。 用户使用的私钥可以对每个 UTXO 进行签名和消费。

UTXO 系统在比特币网络中运作良好，部分原因在于数字钱包可以完成大部分与交易相关的工作，包括但不限于以下内容：

a) 操作UTXO

b) 保存私钥

c) 设置交易费用

d) 提供更改地址

e) 统计UTXO（显示可用余额、转账金额和总余额）

有趣的是，非确定性钱包（如上图中的 Bitcoin Core 钱包）的备份仅提供 UTXO 的快照（在那个时间点）。 一旦用户执行任何交易（发送或接收），他们生成的原始备份就会过时。

总之，我们知道：

与前面提到的比特币网络不同，以太坊世界状态已经管理账户余额等。 以太坊中的状态不是一个抽象的概念，它是以太坊的基础层协议。 正如黄皮书[1]中提到的，以太坊是一个基于交易的“状态”机器。 基于所有事务的状态机的概念就是这样构建的。

让我们从头开始，像其他区块链一样，以太坊区块链从创世块开始。 从这个起点（区块高度为0的创世状态）开始，交易、合约、挖矿等活动将不断改变以太坊区块链的状态。 在以太坊中，每笔交易的账户余额变化（存储在状态树中）就是一个例子。

值得注意的是，账户余额等数据并未直接存储在以太坊区块链的区块中。 区块中只保存交易树、状态树和收据树根节点的哈希值。 其存储结构如下图所示。

从上图中可以看出，存储树（存储所有智能合约数据的地方）根节点的哈希值实际上指向状态树，因此间接指向区块链。 接下来我们将深入探讨这部分的更详细信息。

以太坊中存在两种不同类型的数据：永久数据和临时数据。 事务是持久数据的一个例子。 一笔交易一旦被确认，将永久记录在交易树结构中，不可篡改。 特定以太坊账户的余额是临时数据的一个例子。 账户地址的余额存储在状态树中以太坊创世区块不能挖矿了，并在收到与该账户相关的交易时发生变化。 将永久数据（如挖矿确认交易）与临时数据（如账户余额）分开是有意义的。 以太坊使用前缀树（如上图所示的结构）这样的数据结构来管理数据，那么我们就来介绍一下什么是前缀树。

前缀树

前缀树是众所周知的用于存储有序字符串的数据结构。 以太坊专门采用了一种所谓的“实用算法检索字母数字编码信息”（Practical algorithm to retrieve information coded in alphanumeric，缩写为PATRICIA，以下音译为“Patricia”）。 Patricia 树的主要优点是其紧凑的存储空间。 接下来我们比较标准（传统）前缀树和Patricia前缀树的工作原理。

- \0 表示空指针 -

在前缀树中添加单词的规则

让我们按照添加的单词的搜索路径。 如果我们遇到一个空指针（在搜索期间），我们构造一个新节点； 当我们成功地将单词添加到前缀树时，我们创建了一个空指针（终止符）。

当我们需要添加一个被其他长词包含的短词时，我们只需将所有字母放入并添加一个空指针（终止符）。

从前缀树中删除单词的规则

我们在前缀树中搜索表示字符串（我们要删除的单词）的叶子（分支端节点）。 然后删除从叶端节点到根节点的所有节点。 除非我们遇到一个节点有多个子节点，否则删除它直到完成。

在前缀树中搜索单词的规则

我们依次搜索搜索到的字符串中的每个字母，并停止搜索，直到得到一条完整的路径（顺序正确）。 如果在检索到字符串（检索目标）中的所有字母之前遇到空指针，则称该字符串不在前缀树中。 另一方面，如果我们随着检索到达一个叶节点（分支端节点），那么该路径就代表了目标字符串，可以认为它在前缀树中。

帕特里夏树

向 Patricia 树添加单词的规则

帕特里夏树将所有常见字符聚集到一个分支中。

所有不常见的字符都成为路径上的新分支。 在向帕特里夏树中添加新词时，我们将所有字母依次添加，然后添加空指针（终止符）。

从帕特里夏树中删除单词的规则

帕特里夏树删除单词的规则与传统的前缀树大体相同，不同的是删除节点时（从叶节点到根节点），必须保证所有父节点至少有两个子节点。 允许只包含字符和空指针的单个子节点（如上所示，每个单词的末尾都是这种情况）。 也允许一个节点只包含一个空指针（当一个短词包含在一个长词中时会发生这种情况）。 上图展示了“wood”和“wooden”在同一个前缀树中的情况。

值得注意的是，从前缀树中删除时，路径上不能保留只有一个子节点的父节点。 如果在删除过程中发生这种情况，我们需要重新连接相应的角色来解决问题。 下图显示了一个示例（从前缀树中删除了单词“word”）。

- 在从前缀树中删除“单词”之前-

-删除并重组前缀树后-

帕特里夏树中的单词搜索规则

在 Patricia 前缀树中搜索单词与标准前缀树相同。

标准前缀树和帕特里夏树之间的相似之处

假设“m”是我们要添加的字符串的长度，“N”是可用字母表的大小，将字符串添加到前缀树的时间复杂度“O”是 O(mN)

假设“m”是我们要删除的字符串的长度，“N”是可用字母表的大小，则删除前缀树中字符串的时间复杂度“O”为O(mN)

假设“m”为我们要查找的字符串的长度，则在前缀树中查找字符串的时间复杂度“O”为O(m)

标准前缀树和 Patricia 前缀树的主要区别

使用帕特里夏树的最大优势是存储。

使用标准前缀树存储总长度为“M”的字符串的空间复杂度为 O(MN)，其中“N”是可用字母表的大小。

使用 Patricia 树存储总长度为“M”的字符串的空间复杂度为 O(nN+M)，其中“n”是存储在前缀树中的字符串数，“N”是可用字母表的大小.

直观上可以发现，两棵树的深度明显不同（如上两图所示）。 Patricia 树的深度更小（更浅），这是由于 Patricia 树能够组合常用字符（并将空指针连接到叶节点）。

深入探索以太坊前缀树

让我们更深入地研究状态、存储和事务前缀树。

状态前缀树 - 唯一

以太坊中只有一棵全局状态前缀树。

这个全局状态树不断更新。

此状态前缀树包含一组用于以太坊网络中每个帐户的键值对。

这个“密钥”是一个 160 位的标识符（以太坊账户的地址）。

全局状态前缀树中的“值”是通过在以太坊账户中对以下细节进行编码得到的（使用递归长度前缀编码（RLP）方法）：

状态前缀树的根节点（整个状态树在给定时间点的哈希值）是用来保证状态前缀树安全的唯一标识符。 状态前缀树的根节点是由整个内部状态树的所有数据通过密码学手段获得的。

-状态前缀树（用leveldb实现的Merkel Patricia树（简称MPT））和一个以太坊区块的关系-

- 存储在给定块中的“stateRoot”，它是通过使用 Keccak 256 位哈希算法计算状态前缀树的根节点获得的。 “stateRoot”：'0x8c77785e3e9171715dd34117b047dffe44575c32ede59bde39fbf5dc074f2976' -

存储前缀树——智能合约数据的存储

存储前缀树是存储智能合约数据的地方。 每个以太坊账户都有自己的存储前缀树。 存储前缀树根节点的 256 位哈希 storageRoot 值保存在全局状态前缀树中（正如我们刚才讨论的）。

交易前缀树 - 每个区块一棵树

每个以太坊区块都有自己独立的交易前缀树。 一个区块往往包含多笔交易，交易的先后顺序当然是由打包交易的矿工决定的。 在交易前缀树中查找交易路径是通过（RLP 编码方法）检索区块中交易的索引来完成的。 经过挖矿验证的区块将永远不会再次更新，因此区块中的交易顺序也将固定下来。 这意味着一旦你从区块的交易前缀树中定位到某笔交易，以后你可以通过相同的路径检索它。

阿建平：账户模型可以说是以太坊设计的核心部分。 而这部分必须结合区块链本身，考虑到各方面的效率要求（存储、调用等）。 话虽如此，我听说过州树，这棵树，那棵树，现在终于弄明白它们是怎么来的了。 不过应该还有一部分没有在本文中涉及到，那就是Patricia树是如何与Merkle树结合的。