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

前言与版本

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

公式解析

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

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

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

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

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

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

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

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

(5)
(5)
  • β 为以太坊的 chain_id

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

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

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

(8) (9)
(8) (9)

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

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

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

(11)
(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)
(10)
  • Ls(σ) 为以太坊世界状态函数。

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

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

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

(12)
(12)

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

(14)
(14)

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

(15))
(15))

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

(17)
(17)
  • 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)

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

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

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

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

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

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

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

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

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

(27) (28) (29) (30)
(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 三位拼接成 uint64,然后与 2048 取余,这三个数即是要将 y 这个 bit map 中置 1 的索引位置。

(26)
(26)
  • Ot 为日志主题。

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

(32)
(32)

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

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

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

(34)
(34)

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

(31)
(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)

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

(36) (37) (38)
(36) (37) (38)

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

(40)
(40)
  • P(H) 为父区块。

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

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

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

(41) - (48)
(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)
(49)
  • Hl 为区块的 Gas Limit 值。

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

(50)
(50)

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

(51)
(51)

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

(52)
(52)

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

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

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

(54)
(54)
  • A 为交易子状态。
  • A1 为交易日志。
  • At 交易所接触过的账户集合。
  • Ar 是交易的累计退还 Gas 余额参数,会参与最终退还 Gas 的计算。
  • Aa 是交易所访问的账户地址。
  • Ak 是交易所以访问的存储键。

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

(55)
(55)

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

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

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

(59)
(59)

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

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

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

Subscribe to DavidCai.eth
Receive the latest updates directly to your inbox.
Verification
This entry has been permanently stored onchain and signed by its creator.