详解以太坊世界状态

以太坊是由多个组成部分构成的。这篇文章旨在解构以太坊，使你能更深入理解它的数据存储层。我们将介绍区块链中“状态”的概念，并探究帕特里夏前缀树（Patricia Trie）数据结构的理论依据，利用 Google 的 leveldb 数据库来阐释以太坊中前缀树的应用。本文同时和一篇手把手学习指引相关联，它能指导你安装并配置好自己的以太坊私有网络（包括挖矿）。学习之后你将能够执行交易，并且探索以太坊的“

跨链技术践行者

14318人浏览 · 2019-05-12 09:21:15

跨链技术践行者 · 2019-05-12 09:21:15 发布

什么是区块链“状态”？

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

对 UTXO 更详尽的介绍不在本文的讨论范围内，然而在接下来的数个段落中，我们将不断提及这一概念，来指出比特币和以太坊之间基础实现上的差异。

接下来的两个比特币例子将指出比特币 UTXO 模型和以太坊世界状态概念之间的不同之处。

首先，比特币的 UTXO 不能被拆分消耗。如果一个比特币用户想要花费 0.5 个比特币（他手上只有一个价值 1 比特币的 UTXO），他必须显式地将赋予 0.5 个比特币转账地址（转给自己）作为找零。如果他们没有设置自我找零，那么 0.5 个比特币就会作为矿工打包交易的奖励转给矿工。

第二点，在一个最底层的角度来说，比特币并不保存用户的账户余额。在比特币中，用户仅仅在某一给定时间点掌握着一到多个 UTXO 的私钥。尽管数字钱包设计得好像比特币区块链能自动保存和管理用户的余额等等，但实际上不是这样的。

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

UTXO 系统在比特币网络中运行良好，某种程度上要归功于数字钱包能完成绝大多数与交易相关的工作，包括但不限于以下几点：

a) 操作 UTXO
b) 保存私钥
c) 设置交易费用
d) 提供找零地址
e) 统计 UTXO (显示可用余额、转帐中的数额以及总余额)

有趣的是，一个非确定性钱包（如上图中的比特币核心钱包）的备份仅仅提供 UTXO 的快照（在该时间点）。只要用户执行了任何交易（发送或接收），他们所生成的原始备份就过期了。

总结来说，我们知道：

比特币区块链不保存账户余额
比特币钱包保存 UTXO 的私钥
当被包含在某一条交易中时，整个 UTXO 就被使用掉了（在有些找零场景中，原来 UTXO 中的价值会被新的 UTXO 承载）

和上述比特币网络不同，以太坊世界状态已经能管理账户余额以及更多信息了。以太坊中的状态并不是一种抽象的概念，它是以太坊的基础层协议。正如黄皮书 [1] 中所提及的，以太坊是一个基于交易的“状态”机。基于所有交易的状态机概念就这样被构建出来。

让我们从头开始捋一捋，和其他区块链一样，以太坊区块链是由创世区块开始的。从这个起点开始（创世状态在 0 区块高度），诸如交易、合约以及挖矿的活动会持续不断地改变以太坊区块链的状态。在以太坊中，账户余额（存储在状态树中）随每一次交易进行所发生的改变就是这样一个例子。

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

从上图中可以注意到，存储树（所有智能合约数据存储的位置）的根节点哈希实际上指向了状态树，从而间接指向了区块链。接下来我们将深入探讨这一部分更细节的内容。

以太坊中存在两种截然不同的数据类型：永久数据和暂存数据。交易就是永久数据的一个例子。一旦一个交易被确认，它就将永久地被记录在交易树结构中，并且无法篡改。而某一个特定以太坊账户的余额则是暂存数据的例子。账户地址的余额存储在状态树中，并且每当接收到和该账户有关的交易时，该余额都会改变。将挖矿确认后的交易这样的永久数据和账户余额这样的暂存数据分开管理是有意义的。以太坊使用前缀树这种数据结构（上图所示结构）来管理数据，那么接下来我们介绍一下什么是前缀树。

前缀树

前缀树是众所周知用于存储有序字符串的一种数据结构。以太坊特别采用了一种被称为“检索用文字数字编码的信息的实用算法”（Practical algorithm to retrieve information coded in alphanumeric，缩写为 PATRICIA，下文音译“帕特里夏树”）树。帕特里夏树的主要优势在于它简缩的存储。接下来我们对比标准（传统）前缀树和帕特里夏前缀树之间工作原理的不同。

- \0 表示空指针-

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

我们跟随着所加入单词的搜索路径来看。如果我们（在搜索过程中）遇到了一个空指针，就构建一个新节点；当成功将单词加入到前缀树中后，我们再创建一个空指针（终止符）。

当需要加入一个被其他长单词所包含的短单词时，我们就直接把所有的字母放进去并加入一个空指针（终止符）。

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

我们从前缀树中搜索一个表示字符串（我们所要删除的单词）的叶子（分支末端节点）。紧接着删除从叶子末端节点开始直到根节点的所有节点。除非我们遇到了一个有超过一个子节点的节点，否则删完为止。

前缀树中搜索单词的规则

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

帕特里夏树

向帕特里夏树添加单词的规则

帕特里夏树将所有的常用字符集合为一个分支。

所有非常用字符都会成为路径上的一个新分支。当要向帕特里夏树添加一个新单词时，我们依次加入所有的字母，然后加入空指针（终止符）。

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

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

值得留意的是，当要从一个前缀树种删除时，路径上不能保留任何只有一个子节点的父节点。如果在删除过程中发生了这种情况，我们需要把合适的字符重新连接起来以解决该问题。这种例子在下图中呈现（从前缀树种删除单词 “word” ）。

-从前缀树中删除 “word” 之前-

-删除并重组前缀树之后-

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

在 Patricia 前缀树中搜索单词和标准前缀树一致。

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

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

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

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

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

使用帕特里夏树最大的优势在于存储方面。

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

使用帕特里夏树来存储总长度为“M”的字符串的空间复杂度为 O(nN+M) ，其中 “n” 是前缀树中存储字符串的数量，“N” 为可用字母表的大小。

直观来看能发现，两种树的深度显著不同（如上述两图所示）。帕特里夏树的深度更小（更浅），这归因于帕特里夏树将常用的字符组合的能力（并把空指针和叶子节点连接）更强。

以太坊前缀树的深入探究

让我们更深入地探究一下状态、存储以及交易前缀树。

状态前缀树 —— 独一无二

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

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

这个状态前缀树包含了以太坊网络中每一个账户的一组键值对。

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

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

nonce 值
余额
存储前缀树根节点哈希
代码哈希

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

-状态前缀树（用 leveldb 实现的默克尔帕特里夏树（缩写 MPT））和一个以太坊区块之间的关系-

-给定区块中存储的“stateRoot”，这是用 Keccak 256 位哈希算法计算状态前缀树根节点得到的。“stateRoot”：‘0x8c77785e3e9171715dd34117b047dffe44575c32ede59bde39fbf5dc074f2976’-

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

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

交易前缀树 —— 一个区块一个树

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

以太坊前缀树的实际示例

以太坊的各个主流客户端使用两种不同的数据库软件来存储前缀树，其中用 Rust 写成的 Parity 客户端使用 RocksDB ，而以太坊的 Go 、C++ 以及 Python 客户端使用 LevelDB 。

以太坊和 RocksDB

Rocksdb 不在本文的讨论范围之内，可能在以后我们会推出相关的文章，但是现在，让我们一起看看使用 LevelDB 的三种主流以太坊客户端吧。

以太坊和 LevelDB

LevelDB 是谷歌开源的一个键值存储库，除开其他方面，它提供了对数据的前向和后向迭代，从字符串类型键到字符串类型值的有向图，自定义比较算法以及自动压缩等功能。数据会自动地使用 “Snappy” 进行压缩，那是谷歌的一个开源压缩/解压缩库。

虽然 Snappy 并不致力于高的压缩比率，但具备极高的压缩速率。LevelDB 是管理以太坊网络状态的重要存储和检索手段。因此，LevelDB也成为了最流行的几种以太坊客户端（节点）的必要依赖环境，例如 go-ethereum, cpp-ethereum 和 pyethereum 。

虽然前缀树数据结构的生成能在硬盘上完成（使用像 levelDB 一样的数据库软件），但需要明白在前缀树中增删改和在单纯的键值对数据库中进行操作是截然不同的。

为了更深入的理解，我们必须使用合适的帕特里夏树库来在 LevelDB 中进行数据存取操作。这个练习要求我们安装以太坊。

关于安装以太坊的操作我们已经写了一篇额外的教程（和本文配套）。另一篇名为 “面向实验和测试来快速搭建一个以太坊私有网络” 的文章提供了指引你安装和配置以太坊私有网络的手把手教程。

一旦搭建好你的以太坊私有网络，你就能执行交易并探究以太坊的“状态”是如何根据交易、合约和挖矿来进行改变的。如果你并没有准备好来配置一个以太坊私有网络，也没关系，下文将提供我们的范例代码和以太坊私有网络运行时的截图。

分析以太坊数据库

正如我们上文中提到的那样，以太坊区块链中有众多的 Merkle Patricia 前缀树（在每一个区块中都有引用）：

状态前缀树
存储前缀树
交易前缀树
收据前缀树

接下来的章节中我们将假设你已经安装并配置好了你自己的以太坊私有网络，或者你愿意跟着看看我们运行代码并对以太坊 LevelDB 数据库进行的讨论。

为了找到某一个区块中特定的默克尔帕特里夏树，我们需要获得它的根哈希作为索引。下图中的三条指令分别可以使我们得到创世区块中状态前缀树、交易前缀树和收据前缀树的根哈希值。

web3.eth.getBlock(0).stateRoot
web3.eth.getBlock(0).transactionsRoot
web3.eth.getBlock(0).receiptsRoot

注意：如果你想得到最近的一个区块的根哈希值时（而不是创世区块），你可以使用如下指令。

web3.eth.getBlock(web3.eth.blockNumber).stateRoot

安装 npm、node、level 以及 ethereumjs

我们将使用 nodejs、level 以及 ehereumjs 一系列工具来探查 LevelDB 数据库的变化。下面的指令用于进一步搭建实验环境。

cd ~
sudo apt-get update
sudo apt-get upgrade
curl -sL https://deb.nodesource.com/setup_9.x | sudo -E bash - sudo apt-get install -y nodejs
sudo apt-get install nodejs
npm -v
nodejs -v
npm install levelup leveldown rlp merkle-patricia-tree --save
git clone https://github.com/ethereumjs/ethereumjs-vm.git
cd ethereumjs-vm
npm install ethereumjs-account ethereumjs-util --save

在这一步运行如下代码可以得到以太坊账户的公钥（存储于你以太坊私有网络的状态根之中）。这个代码连接了以太坊的 LevelDB 数据库，进入到了以太坊世界状态中（使用区块链中一个区块的 stateRoot 值），然后接入了以太坊私有网络中所有账户的键索引。

//Just importing the requirements
var Trie = require('merkle-patricia-tree/secure');
var levelup = require('levelup');
var leveldown = require('leveldown');
var RLP = require('rlp');
var assert = require('assert');

//Connecting to the leveldb database
var db = levelup(leveldown('/home/timothymccallum/gethDataDir/geth/chaindata'));

//Adding the "stateRoot" value from the block so that we can inspect the state root at that block height.
var root = '0x8c77785e3e9171715dd34117b047dffe44575c32ede59bde39fbf5dc074f2976';

//Creating a trie object of the merkle-patricia-tree library
var trie = new Trie(db, root);

//Creating a nodejs stream object so that we can access the data
var stream = trie.createReadStream()

//Turning on the stream (because the node js stream is set to pause by default)
stream.on('data', function (data){
  //printing out the keys of the "state trie"
  console.log(data.key);
});

有趣的是，以太坊的账户中只在（与该账户有关的）交易完成后才加入到状态前缀树中。举例来说，仅仅使用 “geth account new” 指令在本地生成一个以太坊账户并不会改变状态前缀树，即使这之后网络又挖矿验证了数个区块也不会。然而一旦一个和该账户有关的交易成功（交易执行消耗了 gas *并且*被挖矿验证）执行了，当且仅当此时这个账户会加入到状态前缀树中。这种做法机智地避免了不怀好意的攻击者通过不断制造新账户来使状态前缀树过度膨胀的后果。

解码数据

你现在应当注意到了 LevelDB 所返回的是加密后的结果。这是因为以太坊事实上使用了自己独特的 “默克尔帕特里夏树” 来与 LevelDB 进行交互。以太坊维基百科提供了改良 “默克尔帕特里夏树” 和递归长度前缀（RLP）编码的设计和实现方法。简单来说，以太坊通过上述的方法来对前缀树数据结构进行了拓展。比如说改良默克尔帕特里夏树通过使用“拓展”节点找到路径捷径（顺着前缀树）的方法。

在以太坊中，一个改良默克尔帕特里夏树节点只可能是以下的某一种：

一个空字符串（记作 NULL）
一个包含17个元素的数组（记作一个分支）
一个包含两个元素的数组（记作一个叶子节点）
一个包含两个元素的数组（记作一个拓展节点）

以太坊前缀树依循严格的规则设计并构建，而理解他们的最好方式则是通过使用计算机代码。如下的例子中用到了 ethereumjs 。ethereumjs 库的安装和使用都十分简便，是我们快速了解以太坊 LevelDB 数据库的绝佳工具。

以下代码（在有了某特定区块的 stateRoot 以及以太坊账户地址的情况下）将返回可直接阅读的账户余额。

-代码的输出结果（地址 0xccc6b46fa5606826ce8c18fece6f519064e6130b 的账户余额）-

//Mozilla Public License 2.0 
//As per https://github.com/ethereumjs/ethereumjs-vm/blob/master/LICENSE
//Requires the following packages to run as nodejs file https://gist.github.com/tpmccallum/0e58fc4ba9061a2e634b7a877e60143a

//Getting the requirements
var Trie = require('merkle-patricia-tree/secure');
var levelup = require('levelup');
var leveldown = require('leveldown');
var utils = require('ethereumjs-util');
var BN = utils.BN;
var Account = require('ethereumjs-account');

//Connecting to the leveldb database
var db = levelup(leveldown('/home/timothymccallum/gethDataDir/geth/chaindata'));

//Adding the "stateRoot" value from the block so that we can inspect the state root at that block height.
var root = '0x9369577baeb7c4e971ebe76f5d5daddba44c2aa42193248245cf686d20a73028';

//Creating a trie object of the merkle-patricia-tree library
var trie = new Trie(db, root);

var address = '0xccc6b46fa5606826ce8c18fece6f519064e6130b';
trie.get(address, function (err, raw) {
    if (err) return cb(err)
    //Using ethereumjs-account to create an instance of an account
    var account = new Account(raw)
    console.log('Account Address: ' + address);
    //Using ethereumjs-util to decode and present the account balance 
    console.log('Balance: ' + (new BN(account.balance)).toString());
})

结论

在上文中我们阐述了以太坊能够良好地管理其“状态”。这种聪明的预先设计有许多好处。

移动端亲和性

随着移动设备和物联网设备的无处不在，未来的电子商务必将依赖于安全、强健且快速的移动应用。

既然我们承认了移动性上的优势，我们也必须认识到区块链数据大小不可避免地不断增加。在每一个移动设备上存储完整的区块链网络显然是不切实际的。

高速而不降低安全性

以太坊世界状态的设计和使用改良默克尔帕特里夏树的做法在这一领域提供很多优势。在前缀树上操作的每一种函数（增删改）都有一个确定的密码学哈希，进一步来说，前缀树根节点独一无二的密码学哈希能作为证据，保证前缀树未被篡改。

举例而言，任何对前缀树进行的任何程度的改变（例如在 LevelDB 数据库种增加某一账户的余额），都将会完全颠覆根哈希。这样的密码学特性使得轻客户端（不存储整条区块链的设备）成为可能，用户可以很迅速且可信地查询区块类似某某账户 “0x … 4857” 是否有足够余额在 “5044866” 高度完成购买的问题。

“默克尔证明关于所存储的数据量大小是对数复杂的。这就意味着即使整个状态前缀树有数 Gb 大小，如果一个节点能从可信源得到状态根，那它就可以在仅仅下载数 Kb 证明数据的情况下百分百验证树上的任何信息。”[2]

限制消费

在以太坊白皮书 [3] 中提到了储蓄账户这样一种有意思的想法。在这种场景下，两个用户（也许是丈夫和妻子，或者是商业伙伴）可以每天从余额中提走 1% 的存款。这个创意仅仅在白皮书中的 “未来应用” 中被提及，但它的意义在于理论上这样的做法可以作为以太坊的基础协议层（作为第二层解决方案或是第三方钱包的必要支持方案）。你可能会想到了本文开篇中对 UTXOs 的讨论。正如我们所说 UTXOs 在区块链上是黑箱的数据，比特币区块链实际上不存储用户的账户余额。

因此比特币网络很难（也许不可能）实现任何一种限制消费的应用。