解释以太坊状态试图加深对以太坊区块链的了解。

介绍

这篇文章解释了以太坊状态树。复仇通常被称为“世态町ñ e”和使用原始数据存储到记录状态（账户）和交易。由于 state trie 是 Ethereum 的核心数据库，因此了解它以加深您对 Ethereum 的了解非常重要。我构建的内容是为了让你在逻辑上一步一步地理解。当我学习它时，很难深入理解，因为状态树有多种类型，并且每个状态树都彼此密切相关。我希望这篇文章可以帮助您轻松深入地了解 state try。本文按顺序涵盖以下主题。

• Merkle Patricia Trie
• World State Trie
• Transaction Trie
• Receipt Trie
• Account Storage Trie

Merkle Patricia Trie（基数树/帕特里夏树/前缀树）

Trie，也称为Radix Trie、Patricia Trie或Prefix Tree，是一种查找公共前缀最快、实现简单、占用内存小的数据结构。由于以太坊使用 Merkle Tree 将哈希高效地存储在块中，因此使用 Trie 作为数据存储的核心数据结构。以太坊使用“Modified Merkel Patricia Trie”，它是由 Merkle Tree、Patricia Tree(Trie) 和一些改进发明的。修改后的 Merkle Patricia Trie 作为以太坊尝试接收树、世界状态树、账户存储树和交易树中的主要数据结构。

上图显示了 Merkel Patricia Trie 的结构。它主要由三种类型的节点组成：扩展节点、分支节点和叶节点。每个节点由其内容的 sha3 散列值决定，并将散列用作键。Go-ethereum 使用 levelDB，parity 使用 RocksDB 存储状态。如果您想了解更深入的内容，请参阅“修改后的 Merkle Patricia Trie — 以太坊如何保存状态”。

状态树结构

在开始解释每个状态树之前，让我解释一下以太坊状态树的整个架构。如前所述，状态树有四种类型：世界状态树、交易树、交易收据树和账户存储树。每个状态树都是用 Merkle Patricia Trie 构建的，只有根节点（状态树的顶部节点）存储在块中以备用存储。您可以在下图中看到整个架构。

如您所见，三个主要的状态尝试：世界状态树、交易树和接收树被存储在块中。并且，账户存储树（account storage contents trie）在世界状态树中构造叶节点。

世界状态树（State Trie，全局状态树）

世界状态树是地址和帐户状态之间的映射。它可以被视为一个全局状态，通过事务执行不断更新。以太坊网络是一个分散的计算机，状态树被认为是硬盘驱动器。所有关于账户的信息都存储在世界状态树中，您可以通过查询来检索信息。世界状态树与账户存储树关系密切，因为它有“storageRoot”字段，指向账户存储树中的根节点。

帐户存储树

帐户存储树是存储与帐户关联的数据的地方。这仅与合约账户相关，所有智能合约数据都作为 32 字节整数之间的映射保存在账户存储树中。
并且，帐户状态存储有关帐户的信息，例如帐户有多少以及从帐户发送了多少交易。它有四个字段：nonce、balance、storageRoot 和 codeHash。它是世界状态树中的叶节点。

事务树

交易树记录以太坊中的交易。交易在改变状态方面起着核心作用，因为以太坊是基于交易的“状态”机器。一旦交易记录在一个区块中，就不能永久更改以证明账户余额（世界状态）。由于 Transaction Trie 是使用 Modified Merkel Patricia Trie 构建的，因此唯一的根节点存储在块中。下面的灰色框描述了交易数据字段。如果您想了解更多详细信息，请参阅以太坊交易结构说明。

nonce：交易 nonce 是从给定地址发送的交易序列号。
Gas Price：您愿意支付的价格
Gas Limit：Gas Limit 是发送方愿意为交易支付的 ETH 数量的限制
Recipient：收件人是以太坊地址的目的地。
Value：值字段表示从发送者到接收者的以太币/wei 的数量。
Data：数据字段用于合同相关活动，例如合同的部署或执行。
v,r,s：该字段是原始 EOA 的 ECDSA 数字签名的组成部分。

交易收据树（Receipt Trie）

交易收据 Trie 记录交易的收据（结果）。收据是交易成功执行的结果。收据包括交易的哈希值、区块号、使用的gas 数量和合约地址等。这是交易收据的字段。

blockHash: String, 32 Bytes - 此交易所在区块的哈希值。
blockNumber: Number - 此交易所在的区块号。
transactionHash: String, 32 Bytes - 交易的哈希值。
transactionIndex: Number - 区块中交易索引位置的整数。
from: String, 20 Bytes - 发件人的地址。
to: String, 20 Bytes - 接收者的地址。如果是合约创建交易，则为 null。
cumulativeGasUsed: Number - 在区块中执行此交易时使用的总燃料量。
gasUsed: Number - 仅此特定交易使用的 gas 量。
contractAddress: String - 20 Bytes - 创建的合约地址，如果交易是合约创建，否则为 null。
logs：数组 - 此事务生成的日志对象数组。
status : String - '0x0' 表示交易失败，'0x1' 表示交易成功。

引用：https : //ethereum.stackexchange.com/questions/6531/structure-of-a-transaction-receipt

结论

文章解释了以太坊的主要状态尝试：Merkle Patricia Trie、世界状态Trie、交易Trie、收据Trie和账户存储Trie。由于以太坊是一个世界的“状态机”，它具有原始的机制来记录和管理状态与特里数据结构。世界状态树存储帐户状态，表示帐户有多少钱。交易树记录可以更新世界状态树的交易，并且不可变地存储在区块链中以证明活动历史。Receipt trie 代表交易的结果，可以对外查询。我希望这篇文章有助于加深您对以太坊的了解。

参考

深入了解以太坊的世界状态
以太坊解释：默克尔树、世界状态、交易等
了解以太坊中的 Trie 数据库
Transaction Trie 和 Receepts Trie 之间的关系
以太坊区块架构
以太坊中的数据结构| 第 1 集：递归长度前缀 (RLP) 编码/解码。
Modified Merkle Patricia Trie——以太坊如何拯救一个状态

原文

https://medium.com/@eiki1212/ethereum-state-trie-architecture-explained-a30237009d4e

keccak应用

在以太坊中，用keccak哈希算法来计算公钥的256位哈希，再截取这256位哈希的后160位哈希作为地址值。

keccak和sha3的区别

sha3由keccak标准化而来，在很多场合下Keccak和SHA3是同义词，但在2015年8月SHA3最终完成标准化时，NIST调整了填充算法：SHA3-256(M) = KECCAK [512] (M || 01, 256)。所以标准的NIST-SHA3就和keccak计算的结果不一样。
以太坊在开发的时候sha3还在标准化中，所以采用了keccak，所以Ethereum和Solidity智能合约代码中的SHA3是指Keccak256，而不是标准的NIST-SHA3，为了避免混淆，直接在合约代码中写成Keccak256是最清晰的

为何推出sha3

推出sha3不是因为sha2出现了漏洞，只是当时学术界对于sha1被成功碰撞的担忧，但目前基于NIST的建议，sha2和sha3都是属于可以安全商用的哈希算法，sha3相当于多了一种安全选择，比特币选用的就是sha2（SHA256）。

参考

https://ethereum.stackexchange.com/questions/550/which-cryptographic-hash-function-does-ethereum-use
https://www.cnblogs.com/HachikoT/p/12792362.html

以太坊核心存储结构：Merkle-Patricia-Tree（前缀树与默克尔树的结合体），以太坊中的交易树、交易收据树、账户树以及合约存储树均使用该树索引。

该树分为三种类型节点：branch（分支，17个元素的元组）、extension（扩展，2个元素的元组）、leaf（叶子节点，2个元素的元组），因此为了区分 extension 与 leaf 节点，使用 key 的第一个 16 进制字符，其中 0000 与 0001 均代表扩展节点，0010 与 0011 均代表叶子节点，也就是说使用倒数第二位来区分 extension 与 leaf 节点。最后一位的 0、1 分别表示了该 key 原先为偶数个 16 进制字符与奇数个 16 进制字符，也就意味着为 0 时，需要填充另外的0000。

账户在以太坊中的存储

下面来看一下以太坊底层存储中是如何实现账户存储的：

目前以太坊中存在两个账户： 0xa3ac96fbe4b0dce5f6f89a715ca00934d68f6c37 0x0f5578914288da3b9a3f43ba41a2e6b4d3dd587a

通过使用编写的拉取以太坊底层存储的 python 脚本，拉取目前底层存储的账户数据（脚本的具体用法有所改变，详见这里）：

其中前一项是以太坊在底层中真正存储的 key，与账户地址的对应关系如下：

也就是说，以太坊存储账户数据的时候，会将账户地址进行一次keccak256 哈希计算

此时，账户树的形状如下：

以太坊中会对节点使用 RLP 编码来存储在底层数据 leveldb 或 rocksdb 中，存储形式为 。所以在上图的槽中，slot 1 实际存储的是 sha3(rlp(leaf1))。

合约在以太坊中的存储

下面来看一下智能合约中的数据是如何存储在以太坊中的： 智能合约中的每一个状态变量都有一个 position，以太坊中每一个 storage slot 为 32 个字节，即 256 位，solidity 编译器会尽量将变量装到同一个 storage slot 中去，对于装不下的，会重新分配 storage slot，遇到 mapping、struct 等类型的变量时，编译器会自动重新分配 storage slot。

该代码存在于账户下，该合约的地址为 0xfe5eeb229738ab87753623a81a42656bcde30a67，contract address = sha3(rlp.encode([creator address, nonce]))

该账户在底层数据库中存储的 key 为

// geth console 环境中
> web3.sha3("0xfe5eeb229738ab87753623a81a42656bcde30a67", {encoding : "hex"})
0x886f7bfb7a4887d716ec4fbb06a8bf35fc1972d2962590248ffe6271e77ac7c1

// python
In [50]: '\xed\xa8}\x9d\xeb\xa5\xbb\xc6O\xa7\'B\xf5\x84"\xaa\xf4f\x9e\xaai)\xe2\xf2_\xa60D\x8a\x0c\x7fJ'.encode("hex")
Out[50]: 'eda87d9deba5bbc64fa72742f58422aaf4669eaa6929e2f25fa630448a0c7f4a'

我们来一一分析：

我们可以看到在相应的位置上分别存储了相应的值， 对于 mapping 来说，其中元素存储的position如下：

sha3(LeftPad32(key, 0), LeftPad32(map position, 0))

所以有：

由于 mapping 中 value 为一个 struct，size 大于 256 位，因此，在存储的位置按顺位加 1，如上图所示。 来看一下，动态数组在以太坊底层存储形式：

其中，在位置 5 存储动态数组的长度，然后以位置 sha3(5) 开始顺序存放数组元素。

--- update ---

mapping中的 key 也可以是 string 形式，假设 mapping(string => string)，key = "11", value = "22", 则在 eth 底层中存储的 key 为：

// 3131 代表字符串 "11"，后面的 32 个 0 代表 map 的 position
> web3.sha3("31310000000000000000000000000000000000000000000000000000000000000000", {encoding : "hex"})
"0x756ab6158180196289fbd030ff61972bf49c0e51dbf603d0dfaf6b1d3f0e49a6"

// 0x3232...04 是 bytes(string) 在底层的存储表达形式，后面的 04 代表字符串的长度为 2， 前面的 3232 代表真正存储的字符串 "22"
> eth.getStorageAt("0xf8a7e4fb488d5e0426012592c5d66e44dffa6cb7", "0x756ab6158180196289fbd030ff61972bf49c0e51dbf603d0dfaf6b1d3f0e49a6")
"0x3232000000000000000000000000000000000000000000000000000000000004"

key = "1111111111111111111111111111111111", len(key) = 34; value = "2222222222222222222222222222222", len(value) = 31

> web3.sha3("313131313131313131313131313131313131313131313131313131313131313131310000000000000000000000000000000000000000000000000000000000000000", {encoding : "hex"})
"0xeb5b36d98f0c746023b3b0e91319a7ee8cb743f75df9f8ce513c5120487cdac3"

// 最后的 3e 代表 31 个字节长
> eth.getStorageAt("0xf8a7e4fb488d5e0426012592c5d66e44dffa6cb7", "0xeb5b36d98f0c746023b3b0e91319a7ee8cb743f75df9f8ce513c5120487cdac3")
"0x323232323232323232323232323232323232323232323232323232323232323e"

key = "1111111111111111111111111111111111", len(key) = 34; value = "22222222222222222222222222222222", len(value) = 32

// 41 代表字符串长度，为了与小于32个字节的长度区分，这里加了 1，所以算长度时：(0x41-1)/2 = 32 个字节
> eth.getStorageAt("0xf8a7e4fb488d5e0426012592c5d66e44dffa6cb7", "0xeb5b36d98f0c746023b3b0e91319a7ee8cb743f75df9f8ce513c5120487cdac3")
"0x0000000000000000000000000000000000000000000000000000000000000041"

// 对该 value 对应的 key 再次进行哈希，用于存放真正字符串
> web3.sha3("0xeb5b36d98f0c746023b3b0e91319a7ee8cb743f75df9f8ce513c5120487cdac3", {encoding : "hex"})
"0x2b3b0a6d0771d1a8fa6f89276ead655b7a0684e2a22d9290bcf4f8944f05b504"

> eth.getStorageAt("0xf8a7e4fb488d5e0426012592c5d66e44dffa6cb7", "0x2b3b0a6d0771d1a8fa6f89276ead655b7a0684e2a22d9290bcf4f8944f05b504")
"0x3232323232323232323232323232323232323232323232323232323232323232"

转载自：https://ethereum.iethpay.com/ethereum-core-storage.html

Why VRF？

场景

在区块链场景中，有的框架会用算法随机产生出块节点与验证节点（如Algorand），甚至解决分叉。按传统的随机算法，按一定的哈希规则随机轮询，选出一个节点来记账/验证。如果这个随机轮询的规则是谁都可以复现的，那么可以推测出将来的某个记账/验证节点，集中攻击它。
为了解决这个问题，就引入了VRF，只有自己能够完成这个哈希过程，而别人只能在他声明之后验证这个过程，防止有人可以提前推测出将来的记账节点。

POS中的权益研磨（Grinding）

（以下来源于以太坊Github上的《Proof of Stake FAQ》）
在任何基于区块链的权益证明算法中，都需要某种机制，来随机从当前活跃验证者集合中选择能够产生下一个区块的验证者。举个例子，如果当前活跃的验证者集合由持有40以太币的Alice，持有30以太币的Bob，持有20以太币的Charlie与持有10以太币的David组成，那么你想让Alice成为下一个区块的创建者的概率为40%，而Bob的概率为30%等（在实践中，不仅要随机选择一个验证者，而是要（随机产生）一个无限验证者序列，只有这样如果Alice不在线的时候，就可以有其他人在过段时间替代她，但是这并没有改变问题的本质）。在非基于区块链的算法中，出于不同的原因也经常需要考虑随机性。
（以下来源Ouroboros白皮书《Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol》）
基于PoS的区块链协议最基本的一个问题就是模拟领导者选举过程。为了在股东们之间的选举达到一个真正的随机性，系统中就必须要引入熵(entropy)，但引入熵的机制可能会容易被敌手操作。例如，一个控制一群股东的敌手可能会试图模拟协议的执行，尝试不同的股东参与者的顺序以此来找到对敌对股东有力的继续者。这会导致一个叫做"grinding"的致命弱点，敌对参与者可能会使用计算资源来倾斜领导者选举。

VRF的目的

VRF的目的就是要生成随机值，且无法被预测，同时还要可验证，可重放。

VRF是什么?

VRF是可验证随机函数(verifiable random function)，一方面具有伪随机性，另一方面它还具有可验证性(输出包括一个非交互零知识证明)

• 伪随机性
• 可验证性
  VRF的方式是，实现本地抽签，各个节点自己抽签，如果抽中了之后，大家可以很容易地验证这个结果确实是你生成的。

eg. 假设现在是round 10（第10 轮），节点们可能会轮流抽签，以节点自己的私钥+ 一个全网都知道的随机数（比如是这轮的轮次10）作为输入，生成了一个随机数（0-100）；设置一个条件：100 个节点轮流抽签，谁先抽出来的随机数大于10，就是这一轮的打包者。假设5 号节点抽到了11，可是只有5 号知道其他人不知道，因此他在广播这个随机的同时还需要广播一个零知识证明。通过零知识证明，全网只需要通过5 号的公钥就可以验证，接受5 号为这轮打包者。图解如下：

VRF具体的操作流程？

• 证明者生成一对密钥，PK、SK；
• 证明者计算result = VRF_Hash（SK，info），proof = VRF_Proof（SK，info）；
• 证明者把result，proof，PK递交给验证者；
• 验证者计算result = VRF_P2H（proof)，True/False = VRF_Verify(PK, info, proof)

True表示验证通过，False表示验证未通过。所谓的验证通过，就是指proof是否是通过info生成的，通过proof是否可以计算出result，从而推导出info和result是否对应匹配、证明者给出的材料是否有问题。

抽签有没有必要用VRF？

相比随机预言机

1. 普通哈希Hash(a)=b，所有人都可以重现，检验正确性；
2. VRF是Hash(SIG(sk, a))=b，别人无法复现这个过程。但是可以拿b，pk，和中间信息验证b是跟a对应的。

   相比非对称加密

3. 在密码学签名算法中，大都会引入随机性，也就是对相同信息的多次签名会得到不同的签名值，因此矿工可以不断对相同的输入SK和block，计算签名，以满足结果小于D。那么理论上任何人都会成为出块者，只要计算足够多次的签名。
4. 有些非对称加密方式得到的随机数不是均匀分布的，如RSA
5. 缺乏零知识，不管使用确定性签名还是随机性签名，都存在个安全隐患。就是一旦将自己的出块凭证公布，任何人都可以公开验证，包括攻击者。那么攻击者可以对出块节点进行攻击，使其不能出块。使用VRFs的方式，矿工只需要公布自己的R表明自己的出块权，当出完块的时候再公布P，那么攻击者就无法在出块之前知道谁具有出块权，因此也就无法实施针对性的攻击。

应用

1. Consensus：共识算法中安全性
   VRF Sortition，Smart Contracts，例如本体，Cardano，Dfinity，Algorand等，不同点在于如何产生输入以及输出怎样用。VRF的返回结果可以用来公开或私密地完成节点或节点群体的选择。eg. Dfinity利用mod操作来唯一，公开的确定一个group。Algorand，Ouroboros Praos是私密选择，即计算出哈希值后，如果哈希值小于某个阈值，节点可以私密地知道自己被选中。
   

本体-VBFT共识算法：

1. 根据VRF 从共识网络中选择备选提案节点，各个备选节点将独立提出备选区块；
2. 根据VRF 从共识网络中选择多个验证节点，每个验证节点将从网络中收集备选的区块，进行验证，然后对最高优先级的备选区块进行投票；
3. 根据VRF 从共识网络中选择多个确认节点，对上述验证节点的投票结果进行统计验证，并确定出最终的共识结果。
4. 所有节点都将接收确认节点的共识结果，并在一轮共识确认后开启新的共识。

Algorand中：

1. 先选打包者，选完打包者选委员会，委员会用BA*进行选区块。
2. 输入值由前一个随机数(最初的随机数是协议给定的)和某种代表高度，轮次的变量进行组合，然后用私钥对之进行签名(或者先签名再组合)，最后哈希一下得出最新的随机数。
3. 条件：①签名算法应当具有唯一性；②避免在生成新随机数时将当前块的数据作为随机性来源之一。

Dfinity中：

交保证金提高门槛，并降低参与节点的数量，然后选打包者，选完打包者选公证人，对区块权重进行排序，选出区块。

Cardano的共识机制-Ouroboros Praos：

在根据Random seed选举slot leader时，通过VRF确保slot leader不被事先计算出来被攻击。

1. IOST的高效分布式分配片
   使用了VRF来进行领头节点的选举，通过VRF得到随机数之后，会将结果进行广播，然后其他节点会进行统计，得到随机数值最小的作为分片领头节点。是一种交互式的选举方式。
2. Key Transparency
   密钥管理系统，使消息传递在不相信服务端的情况下做到点对点的安全上的提升。
3. DNSSEC
   DNS服务的安全性。

参考文献

1. Randao可证公平随机数白皮书
2. 《一文看懂可验证随机函数VRF》
3. Ouroboros:一个可证明安全的PoS区块链协议 白皮书
4. Proof of Stake FAQ
5. 黄祺-区块链中VRF的应用及原理解析 视频资源
6. Cardano(ADA)的共识算法Ouroboros
7. 对可验证随机函数VRF的简明解释
8. VRF wiki
9. VRF原文
10. VRF在区块链中的应用

原文链接：https://blog.csdn.net/shangsongwww/article/details/88797403

go env -w GO111MODULE=auto