您正在查看: surou 发布的文章

以太坊状态树架构解释

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

介绍

这篇文章解释了以太坊状态树。复仇通常被称为“世态町ñ 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

Ethereum 中keccak和sha3的区别

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

VRF可验证随机函数

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