Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

以太坊黄皮书公式解析(上) #53

Open
DavidCai1111 opened this issue Jan 10, 2022 · 0 comments
Open

以太坊黄皮书公式解析(上) #53

DavidCai1111 opened this issue Jan 10, 2022 · 0 comments
Labels

Comments

@DavidCai1111
Copy link
Owner

DavidCai1111 commented Jan 10, 2022

前言与版本

笔者最近在结合以太坊黄皮书以太坊源码,结合自己的理解解析下黄皮书内的公式,与大家共同学习进步,若大家在阅读以太坊黄皮书时,对公式产生理解上的困惑,可以参阅本文一起看。文章基于当前(2022/1/7)的黄皮书,版本号为 BERLIN VERSION fabef25 ,若有不准确之处,欢迎指出。由于该黄皮书内除附录外有 183 个公式,为了让文章篇幅不过长,该解析会由三部分组成一个系列,每个系列解析约 60 个公式,本文为上篇。

公式解析

(1)

  • σ 为以太坊世界状态。
  • Υ 为以太坊状态转换函数。
  • T 为一个交易。

上述公式阐述的是,以太坊是一个基于交易而改变状态的状态机。即每进来一个交易,都会改变一次以太坊的旧世界状态,从而进入一个新世界状态。

(3)

  • B 为一个区块。
  • T0, T1, ... 为一组交易。

在实际运作时,基于效率考量,以太坊是批量处理交易的,一个批次的交易,会被打包在一个区块中,这就是 (3) 公式的含义。

(2)

  • Π 表示区块层面上的状态转换函数。

上述公式即是 (1) 的批量处理版本,以太坊的世界状态通过区块(即一组交易)批量更新。

(4)

  • Ω 为区块确定性状态转换函数,会奖励挖到区块的节点。

这个公式看似有点复杂,让我们逐步解析。等式的左边 Π(σ, B) 即是公式 (2) 的 σt+1,就是以太坊的下一个世界状态。等式右边的 Υ(Υ(σ, T0), T1)... 表示的是,交易会被逐个执行,每一个交易的结束状态,都会是下一个交易的开始状态。故 Ω(B, Υ(Υ(σ, T0), T1)...) 表达的是,逐个执行完区块内的所有交易后,以太坊还会给与挖到区块的节点奖励,这就意味着,以太坊的世界状态,完成了一次基于区块的状态更新。

(5)

  • β 为以太坊的 chain_id

公式 (5) 表达的是以太坊主网的 chain_id 是 1 。目前以太坊除了使用 network_id 来区分环境外,还使用 chain_id 来区分同一环境内的不同分叉。例如,以太坊和经典以太坊的 network_id 都是 1 ,但是 chain_id 分别是 161

(6)

  • l 函数表示取一个序列内的最后一项。

公式 (6) 就是对 l 函数的定义,比较直观,直接取 l(x) 就是取 x 序列的最后一项。

(8) (9)

公式 (8) 中的 LI 函数定义一个对键值对的变换,即将键(k)进行 Keccak-256 哈希,对值进行 RLP 编码。公式 (9) 则对键值的类型和范围做了限定。由于 Keccak-256 哈希和 RLP 编码的特性,键只会是长度为 32 的字节序列,值只会是正整数(在很多文章和代码示例中我们通常看到的是其十六进制表示)。

(7)

  • σ[a]s 为以太坊账户的 storageRoot ,是一个 256 位的哈希值,表示保存该账户存储数据的 Merkle Patricia 树 的根节点哈希值。由于这种树的特性,其根节点就相当于其所有叶子数据的状态快照,任意一个叶子状态的改变,都会改变根节点的哈希值。

公式 (7) 表达的就是,以太坊的 storageRoot 值保存的是对账号数据(键值对)进行 LI 函数转换后,存入 Merkle Patricia 树之后的,根节点哈希值。

(11)

  • KEC(a) 为账号地址(公钥)。
  • σ[a]n 为账户的 nonce 值,当账户是合约账户时,该值表示该合约部署的合约数,当时外部账户时,该值表示历史交易次数。
  • σ[a]b 为账户的 balance 值,即账户余额,以 wei 为单位。1^18 wei = 1 ETH。
  • σ[a]s 为账户的 storageRoot ,上文已经阐述。
  • σ[a]c 为账户的 codeHash 值,若账户是外部账号,则该值为空,若是合约账户,则是编译后的 EVM 执行代码的 Keccak-256 哈希值。

公式 (11) 表示,一个账号在以太坊内,由一个账号地址,和 4 个状态值(存储时会被 RLP 编码)组成。

(10)

  • Ls(σ) 为以太坊世界状态函数。

公式 (10) 表示,以太坊世界状态,由所有的非空账号组成(若一个账号创建后,还未执行过交易,那么是不会被以太坊记录的)。

(13)

  • v 为以太坊的账号有效性函数。

公式 (13) 表示,一个有效的以太坊账号,nonce 和 balance 都是比 2^256 小的正整数,storageRoot 和 codeHash 都是长度为 32 的字节序列。

(12)

倒写的 “A” 此处的含义为“对于任意”,即意思是,对于在以太坊内的所有账号,要么是空账号,要么是有一个 20 字节长度地址并且符合公式 (13) 有效性函数的账号。

(14)

公式 (14) 给“空账号”下了定义,即 codeHash 为空字符串的 Keccak-256 哈希值,且 nonce 和 balance 都是 0 的账号。

(15))

公式 (15) 给“死账号”下了定义,当一个账号状态不存在或为空时,那么就是“死账号”。

(17)
(18)

  • Tn 为交易的 nonce 值,为交易发送者发出过的交易数量。
  • Tv 为交易者发送的以太币数量,以 Wei 为单位。
  • Tp 为交易的 gasPrice 值,指交易者愿意给矿工付出的 gas 单价,以 wei 为单位。
  • Tg 为执行这个交易允许消耗的最大以太币数量,以 wei 为单位。
  • Tw,Tr,Ts 是与交易者签名相关的 v,r,s 值,用于验证交易者。
  • Td 为交易的 data 字段,若交易是执行合约函数,那么 data 值里存储的就是合约函数的入参。
  • Ti 为交易的 EVM 执行码,仅交易是创建合约时,会执行一次。

公式 (17) (18) 对交易中各字段进行了约定,必须符合约定,才是合法交易。即 Tn,Tv,Tp,Tg,Tw,Tr,Ts 是比 2^256 小的正整数,Td,Ti 都是字节(bytes)类型。

(16)

公式 (16) 表示,若交易要么是一个创建合约交易,会包含 init 字段,若不是,则会包含 data 字段。

(19)

  • Tt 为交易的 to 值,即合约地址。

公式 (19) 对 to 值进行了定义,当时创建合约时,to 值为空,否则会是一个长度为 20 的字节。

(20)

  • Bu 为区块头。
  • Bt 为区块内打包的交易。
  • Bu 为叔块列表。

公式 (20) 即表示一个区块由上述三部分组成。

(21)
(22)
(23)

  • Ru 为区块中所有交易执行完后,使用的 Gas 数量。
  • Rl 为交易过程中创建的日志集合。
  • Rb 为日志信息所构成的布隆过滤器。
  • Rz 为交易的状态码,1表示成功,0表示失败。

公式 (21) 即表示一个交易收据由上述四部分组成。公式 (22) (23) 限定了这些值的类型,状态码 Rz 和 Gas 开销 Ru,需为正整数,布隆过滤器 Rb 是个长度为 256 的字节。

(24) (25)

  • O 表示一个日志。
  • Oa 为创建日志的账户。
  • O0,O1... 为具体日志。
  • Od 为相关日志数据(在 solidity 中表现为未被标注 indexed 的参数)。

公式 (24) (25) 定义了以太坊日志的结构,一个以太坊日志集合 Rl 由一系列日志项 O 组成,每一个日志项由上述三部分组成。且 Oa 为长度为 20 的字节,任意 O0,O1 ... 都是长度为 32 的字节,Od 为字节类型。

(27) (28) (29) (30)

这组公式,是一个布隆过滤器的定义,简单来说就是一种以 O(1) 时间复杂度来查询一个元素是否存在于一个集合中的方法,查询时可以保证一个元素 100% 不存在,但不可保证一个元素 100% 存在。宏观定义如公式 (27) ,以太坊的布隆过滤器,会将任意输入字节经过 Keccak-256 哈希后得到的长度为 2048 的比特经过计算获取三个数,然后将一个空的长度为 2048 的比特(256 字节)在索引为那三个数的地方,置 1 ,即结果 y。公式 (28) 表示了 y 值初始时为一个空的长度为 2048 的比特(256 字节)。公式 (29) (30) 表示,在把输入经过 Keccak-256 哈希后,取 0,2,4 这三位,并将他们分别于 1,3,5 三位求和,然后与 2048 取余,这三个数即是要将 y 这个 bit map 中置 1 的索引位置。

(26)

  • Ot 为日志主题。

公式 (26) 在宏观上定义了以太坊收据的布隆过滤器函数,查询时首先会判断日志生产者的地址,然后会根据公式 (27) 查询日志主题。

(32)

公式 (32) 定义了一个 p 函数,对于输入的键值对,分别会对其进行 RLP 编码。

(33)

  • P(BH) 为父区块的状态。
  • Hr 为当前区块最终状态标识。

公式 (33) 表达的是,当前区块的世界状态,是由父区块的状态累加上当前区块的最终状态后,储存为 Merkle Patricia 树的根节点哈希。

(34)

公式 (34) 定义了 LH 函数,用于序列化,即是取所有的区块状态字段,并且定义了顺序。

(31)

  • Hr 为当前区块最终状态标识。
  • Ho 为叔块列表。
  • Ht 为所有块内交易所组成的 Merkle Patricia 树的根节点哈希。
  • He 为所有块内交易收据所组成的 Merkle Patricia 树的根节点哈希。
  • Hb 为日志的布隆过滤器。
  • TT 为区块状态累进函数,后续公式会有详解。

公式 (31) 给出了区块最终状态标识的合法性定义:首先将当前状态与累积上区块内所有的交易修改,并将状态储存为 Merkle Patricia 树的根节点哈希(Hr);将叔块状态列表进行 RLP 编码(Ho);将区块中所有索引 i 的交易数据进行公式 (32) 编码,并将状态储存为 Merkle Patricia 树的根节点哈希(Ht);将区块中所有索引 i 的收据数据进行公式 (32) 编码,并将状态储存为 Merkle Patricia 树的根节点哈希(He);对于任意存在日志,布隆过滤器结果都为真(Hb)。

(35)

公式 (35) 定义了 LB 函数,用于序列化,并定义了顺序,LT,LH 函数上文已有阐述。

(36) (37) (38)

公式 (36) (37) (38) 定义了各种包含在 LH,LT 函数中的字段的类型限制,很直观,就不一一阐述了。

(40)

  • P(H) 为父区块。

公式 (40) 即表达了当前区块的区块号为父区块的区块号 +1 。

(39)

  • Hp 为父区块头的 Keccak-256 哈希。

公式 (39) 表述了父区块头字段 Hp 的定义,将父区块的状态进行 RLP 编码后,再进行 Keccak-256 哈希。

(41) - (48)

  • Hd 为区块的 difficulty 值。

上述公式 (41) 区块描述了 difficulty 的定义,当区块为创始块时,Hd 默认为 2^34 。若不是创始块的话,则会取 2^17 (公式(42))与 P(H)Hd + x * s2 + E 的最大值。其中 s2 为 homestead 难度参数,用于动态平衡区块间的出块时间,当前区块的 timestamp 与父区块的 timestamp 间隔很近,则该值会变调整为 -99 (公式(44))。x 为一个与父区块难度值正相关的参数(公式(43))。E 是一个每间隔十万个区块,就会指数级增长的值,故当区块越来越多时,该值会变大得越来越快,也就是俗称的“难度炸弹”,当这个值非常大时,也就进入了俗称的“冰河时期”,用于激励以太坊切换为 POS 。在 EIP-649 之后,为了减缓“冰河时期”的到来,防止链被“冻结”,让目前的区块数 Hi 减去人为定义的一个 k (公式(47))值。k 值因不同以太坊版本而不同(公式(48))。

(49)

  • Hl 为区块的 Gas Limit 值。

公式 (49) 对一个区块 Gas Limit 大小进行了范围限定,与上一个区块的 Gas Limit 相关。

(50)

公式 (50) 限制了当前区块的 timestamp 必须大于父区块的 timestamp 。

(51)

公式 (51) 限定了以太坊工作量证明函数 PoW (会于后面详细展开)的两个输出值 n,m 的范围。PoW 函数接受三个参数,第一个为不包含 nonce 和 mixHash 的新区块头状态,第二个参数为当前区块头状态,第三个参数为当前 DAG (用来计算 mixHash 的大型数据集合)。函数会输出一个数组,第一个元素即是 mixHash ,用于证明使用了正确的 DAG 。第二个元素是基于 DAG 和区块头状态的密码学伪随机数。求解时间和难度 Hd 是成正比的。

(52)

公式 (52) 定义了区块头验证函数 V(H)。当各字段同时符合条件时,验证为有效。各内部函数上文已有阐述。

(53)

  • Υ 为账户状态转移函数。
  • T 为交易。
  • σ 为账户状态。

公式 (53) 定义了账户的状态转移,即根据交易而更新状态。

(54)

  • A 为交易子状态。
  • A1 为交易日志。
  • At 交易所接触过的账户集合。
  • Ar 是交易的退还 Gas 余额。
  • Aa 是交易所访问的账户地址。
  • Ak 是交易所以访问的存储键。

公式 (54) 定义了交易子状态的组成部分。

(55)

公式 (55) 定义了交易的空子状态。π 为一个预编译地址集合(后文会详细阐述)。

(56) (57) (58)

  • Ti 是交易附带的关联数据。
  • Td 初始化的 EVM 字节码序列。

公式 (55) 定义了交易的预付 Gas 单价,会根据交易的类型不同而不同。G 的完整定义见黄皮书附录。

(59)

公式 (59) 定义了交易的预付费数量,即愿支付的 Gas 单价 * Gas 最大数量,加上转账的数量。

(60)

  • S(T) 为发送者账户。
  • B(H)l 为该区块能够使用的 Gas 上限。
  • l(BR)u 为截止到当前交易,区块内之前的交易已经使用的 Gas 数量。

公式 (60) 定义了交易合法性的验证,很直观,公式已在上文阐述。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant