有几本严肃著作，由于见识和基础不够，浅尝辄止，希望明年可以读完。

另外准备看看经典影视作品。

台湾出版社 心靈工坊 有句宣传语 Reading as Healing，我很喜欢。

感染了新冠还在恢复，我半躺在窗边，回想起这几年，有种白云苍狗的感觉：人生选择，如这新冠政策般，来了个急转弯。

究其原因，外部世界不确定，内心决策却又难免非理性。人在非理性时，是该停下来思考的。

我对着路口久久思考。

也许，无论踏往何方，让人迷失的，总是另一路风景独好。可惜世间没有分身之术，能让人去探索多条小道上那迷人的未知。幸而，劈柴担水，无非妙道。这一层的精彩，在那一层看来是平常；这一时的平常，在那一刻却显得精彩。山是山，水是水。纵使百尺竿头，再进一步，山还是山，水还是水。大道三千，而又殊途同归，没有什么本质上的不同。

我也思考了终点的问题。

一段路途，如果只用精彩来定义，那么精彩过后，路途是什么？

路途结束，也还有别的事要做。可是要做的，不也仍然是平常的事？

有此疑惑，并不是说终点缥缈，因而当下得过且过；也不是说时运莫测，因而否定个人努力。恰恰相反，路只能是走出来的，道就在行之中。不努力进取，就只能在原地打转。

精彩与平常并非泾渭分明，主客观条件在起变化，它们也在转化。但是，精彩是不稳定的，只有平常才是常态。以平常心行百里，会走得更从容些。道路弯曲，却又起伏向前，每一次转弯，不正是自我成长的时机？往者已矣，来者可追，对自我的否定之否定，不正是自我完善的过程？坐而论道，不如躬身入局；骑驴觅驴，不如上下求索。此刻正当收拾精神，潜心修行。

我还思考了同行的问题。

辩证的说，人是一切社会关系的总和，人不可能摆脱社会关系而存在。吾剑未尝不利，虽有良机，不如待时。情缘未断，意犹未尽，不如归来。我知道这有些非理性了，然而性情如此，那就如此吧。眼下，我只想好好走路，体会路上的风景。

一时精彩，不足以让人迷恋；一时平常，不足以让人气短。

拍拍尘土，我又起身，迈向树林深处。

我深深记得，这首诗的结尾是：

“也许多少年后在某个地方，我将轻声叹息将往事回顾...”

今年读了一些书

陪小孩通关了两个双人游戏

代码版本：Optimism: 36efcdec48de221d402edf54b653e3403894607d

注解版本：Optimism-annotated

架构概览

图片来自 Optimistic Ethereum Introduction

角色

Optimism 中所有组件目前都由官方运行

L1

CanonicalTransactionChain

功能：

• 记录批量区块状态
• 协助中继 L1->L2 交易

事件：

• TransactionEnqueued
• SequencerBatchAppended

StateCommitmentChain

功能：

• 记录批量区块状态
• 协助 L2->L1 交易的存在性证明

事件：

• StateBatchAppended

L2

Sequencer

执行两种交易：L2->L2，L1->L2

定序器：敲定两种交易的顺序

batch-submitter

• 打包批量交易 txBatch 提交到 L1

  • TransactionBatchSubmitter
  • 出于 data availability，把交易按敲定的顺序，序列化后作为 calldata 提交到 L1

• 打包批量状态 stateBatch 提交到 L1

  • StateBatchSubmitter

参考 NOTICE: TypeScript batch submitter to be deprecated in favor of Go batch submitter #2050，目前 batch-submitter 有 TypeScript 和 Go 两种实现，其中 TypeScript 版本可能会被移除

--

Optimism 目前对交易数据的处理只是简单的序列化，没有压缩

根据文档 Optimism PBC: The Road to Sub-dollar Transactions, Part 2: Compression Edition，Optimism 正在测试使用 zlib 压缩批量交易；另外，后续会采用 EIP-4844 交易格式来降低成本

data-transport-layer

索引 L1 事件，并存储到数据库中

• TransactionEnqueued
• SequencerBatchAppended
• StateBatchAppended

对于 L1->L2 交易，还将建立引用 index <-> queueIndex

Sequencer 向它查询待执行的 L1->L2 交易

relayer

实时监控已过挑战期的 L2->L1 交易，在 L1 上调用合约完成中继

交互

1.用户在 L1 调用 CanonicalTransactionChain.enqueue()，触发事件 TransactionEnqueued

2.data-transport-layer 监听 TransactionEnqueued，解析事件并查出 calldata，写入数据库

3.Sequencer 从 data-transport-layer 同步 TransactionEnqueued 事件，转为交易并执行

4.或者，用户可通过 L2 RPC 节点，直接向 Sequencer 发送交易

56.batch-submitter 监听 L2 区块，打包 txBatch 提交到 L1 合约 CanonicalTransactionChain.appendSequencerBatch()，触发 TransactionBatchSubmitter 事件

参考 tx-batch-submitter.ts: _getSequencerBatchParams()

789.batch-submitter 监听 L2 区块，打包 stateBatch 提交到 L1 合约 StateCommitmentChain.appendStateBatch()，触发 StateBatchSubmitter 事件；对应的区块进入挑战期

参考 state-batch-submitter.ts: _generateStateCommitmentBatch()

其中，Optimism 目前正在重构第 8 步欺诈证明的实现，详见下文

欺诈证明

Optimistic Rollup 对 状态转移 的保证是在一定时间窗口内，允许挑战者提交欺诈证明，表示对某一状态存在质疑，并开始仲裁。仲裁有两种方式：

• 非交互式欺诈证明
  • 在 L1 重新执行一个区块
  • Optimism 采用
• 交互式欺诈证明
  • 在 L2 上由双方进行多轮交互后锁定某条存疑指令后在 L1 仲裁
  • Arbitrum 采用

Optimism 采用 非交互式欺诈证明，需要在 L1 重新执行一个区块，而 L1 执行成本高昂且存在 gasLimit 限制，因此要求直接指定区块内的哪一笔交易存在问题，以此在 L1 上只验证这一笔交易，而非从头执行这个区块。

在 Optimism 实现中，一个 L2 区块只包含一笔交易，使得区块的 stateRoot 实际就是这笔交易的 stateRoot；即每笔交易都会有一个对应的状态被提交到 L1，因此它可以被单独挑战

这个设计类似 Vitalik: Endgame 前期架构

--

根据 Next gen fault proofs，Optimism 目前暂停了 非交互式欺诈证明 (用户必须信任 Optimism 运行的节点没有作恶)，计划在今年转为 交互式欺诈证明

定序和时间

交易定序

两种交易的顺序，是由 Sequencer 按到达时间确定的

假设存在如下交易：

• t0: L1->L2 交易 Tx0，假设在 t3 被 data-transport-layer 索引 (经过多个 L1 区块的确认)
• t1: L2->L2 交易 Tx1
• t2: L2->L2 交易 Tx2
• t4: L2->L2 交易 Tx3

那么，这些交易在 L2 的执行时间为 [t1, t2, t3, t4]，交易顺序为 [Tx1, Tx2, Tx0, Tx3]；每笔交易为一个区块，按出块顺序记为 [B0, B1, B2, B3]

需要说明的是，区块头部中的区块时间，并非交易执行时间，而是更小些，比如 B2.header.timestamp < t3；详见后文

区块时间

相关文档

• Uniswap V3: Oracles Integrations on Layer 2 Rollups
• How should we handle timestamp in v1.0? #23

Sequencer 维护了 LatestL1Timestamp，每 timestampRefreshThreshold 更新一次 LatestL1Timestamp，且对两种交易都设置了 tx.L1Timestamp

其中，timestampRefreshThreshold 配置为 15 秒 (启动参数 ROLLUP_TIMESTAMP_REFRESH 和 浏览器)

func (s *SyncService) applyTransactionToTip(tx *types.Transaction) error {
    // The property that L1 to L2 transactions have the same timestamp as the
    // L1 block that it was included in is removed for better UX.
    ts := s.GetLatestL1Timestamp()
    bn := s.GetLatestL1BlockNumber()

    shouldMalleateTimestamp := !s.verifier && tx.QueueOrigin() == types.QueueOriginL1ToL2
    if tx.L1Timestamp() == 0 || shouldMalleateTimestamp {
        // 两种交易都会进来

        // Get the latest known timestamp
        current := time.Unix(int64(ts), 0)
        // Get the current clocktime
        now := time.Now()

        // If enough time has passed, then assign the
        // transaction to have the timestamp now. Otherwise,
        // use the current timestamp
        if now.Sub(current) > s.timestampRefreshThreshold {
            current = now
        }

        log.Info("Updating latest timestamp", "timestamp", current, "unix", current.Unix())

        // 将两种交易的 L1Timestamp 改为 LatestL1Timestamp 或 当前时间
        tx.SetL1Timestamp(uint64(current.Unix()))
    }

    // 更新 LatestL1Timestamp
    // Store the latest timestamp value
    if tx.L1Timestamp() > ts {
        s.SetLatestL1Timestamp(tx.L1Timestamp())
    }
}

--

tx.L1Timestamp 用途如下：

1.在执行交易前，构造区块头，作为区块时间

// l2geth/miner/worker.go
func (w *worker) commitNewTx(tx *types.Transaction) error {
    // 使用 l1 的区块时间
    header := &types.Header{
        ParentHash: parent.Hash(),
        Number:     new(big.Int).Add(num, common.Big1),
        GasLimit:   w.config.GasFloor,
        Extra:      w.extra,
        Time:       tx.L1Timestamp(),
    }
}

2.在交易执行时，构造 EVM 上下文，作为 opTimestamp 取值

// l2geth/core/evm.go
func NewEVMContext(msg Message, header *types.Header, chain ChainContext, author *common.Address) vm.Context {
    // 参考 [Differences between Ethereum and Optimism](https://community.optimism.io/docs/developers/build/differences/#)
    if rcfg.UsingOVM {
        // When using the OVM, we must:
        // - Set the Time to be the msg.L1Timestamp
        return vm.Context{
            // 使得 opTimestamp 取值是 L1Timestamp
            Time:          new(big.Int).SetUint64(msg.L1Timestamp()),
        }
    }
}

共识算法

Why does ethereum creates a new block,without even a single transaction?

根据上文，多笔交易可能使用相同的区块时间，又因为每一笔交易为一个区块，所以存在某个区块，其区块时间可能等于父区块的区块时间；

这在 PoW 共识算法中是不允许的：

// l2geth/consensus/ethash/consensus.go

// verifyHeader checks whether a header conforms to the consensus rules of the
// stock Ethereum ethash engine.
// See YP section 4.3.4. "Block Header Validity"
func (ethash *Ethash) verifyHeader(chain consensus.ChainReader, header, parent *types.Header, uncle bool, seal bool) error {
    if header.Time <= parent.Time {
        return errOlderBlockTime
    }

    // ...
}

根据 make-genesis.ts，Optimism 共识采用 PoA，但 PoA 对区块时间也有要求，参考 Multiple blocks with same timestamp in clique network. #21184

因此，Optimism 修改了相关代码，在 Clique 共识中跳过了区块时间的检查，比如：

// l2geth/consensus/clique/clique.go

func (c *Clique) verifyHeader(chain consensus.ChainReader, header *types.Header, parents []*types.Header) error {
    if !rcfg.UsingOVM {
        // Don't waste time checking blocks from the future
        if header.Time > uint64(time.Now().Unix()) {
            return consensus.ErrFutureBlock
        }
    }

    // ...
}

func (c *Clique) verifyCascadingFields(chain consensus.ChainReader, header *types.Header, parents []*types.Header) error {
    if !rcfg.UsingOVM {
        if parent.Time+c.config.Period > header.Time {
            return ErrInvalidTimestamp
        }
    }

    // ...
}

区块回滚

根据文档，代码和 issues， Optimism 在开发时考虑了 L1 发生区块回滚的情况，但未完全处理；比如：

// l2geth/rollup/sync_service.go

// When reorg logic is enabled, this should also call `syncBatchesToTip`
func (s *SyncService) sequence() error {
    // ...
}

// This will trigger a reorg in the future
func (s *SyncService) applyHistoricalTransaction(tx *types.Transaction) error {
    // ...
}

理解：

L1 区块回滚分两种情况：1. 用户在 L1 发起的交易被回滚；2. L2 在 L1 发起的交易被回滚

对于前者，典型操作为 L1->L2 的消息传递，data-transport-layer 会等待 L1 上 35 个区块确认 才做索引，回滚概率小

对于后者，Sequencer 和 batch-submitter 目前都是中心化的，不会存在竞争。即使 L1 回滚，此前提交的交易和状态也会被后续区块重新打包，只是 区块高度 和 区块哈希 不同，而 Optimism 不依赖于这两者

消息传递

相关文档

• Sending data between L1 and L2
• How Optimism Works #Bridging assets between layers

L1->L2

流程概览

1.用户或合约在 L1 调用 CanonicalTransactionChain.enqueue()，触发事件 TransactionEnqueued

参考 CanonicalTransactionChain.enqueue()

2.data-transport-layer 监听 TransactionEnqueued，解析后写入数据库

参考 transaction-enqueued.ts: handleEventsTransactionEnqueued

3.Sequencer 从 data-transport-layer 查询 TransactionEnqueued 事件，转为交易并执行，挖出对应区块

参考 sync_service.go: SyncService.syncQueueTransactionRange()

调用层次较深：SequencerLoop() -> ... -> syncQueueToTip() -> ... -> syncQueueTransactionRange()

交易处理

L1 合约调用

// packages/contracts/contracts/L1/rollup/CanonicalTransactionChain.sol
contract CanonicalTransactionChain {
    uint40 private _nextQueueIndex; // index of the first queue element not yet included
    Lib_OVMCodec.QueueElement[] queueElements;

    function enqueue(address _target, uint256 _gasLimit, bytes memory _data) external {
        address sender;
        if (msg.sender == tx.origin) {
            sender = msg.sender;
        } else {
            sender = AddressAliasHelper.applyL1ToL2Alias(msg.sender);
        }

        bytes32 transactionHash = keccak256(abi.encode(sender, _target, _gasLimit, _data));

        queueElements.push(
            Lib_OVMCodec.QueueElement({
                transactionHash: transactionHash,
                timestamp: uint40(block.timestamp),
                blockNumber: uint40(block.number)
            })
        );

        uint256 queueIndex = queueElements.length - 1;
        emit TransactionEnqueued(sender, _target, _gasLimit, _data, queueIndex, block.timestamp);
    }
}

用户调用 enqueue()，将导致交易被压入 queueElements 队列；其中，_nextQueueIndex 表示队列中前多少条交易已经由 Sequencer 敲定顺序

注意，如果 msg.sender 是个合约地址，会被 AddressAliasHelper 设置偏移：0x1111000000000000000000000000000000001111

L2 交易执行

// l2geth/rollup/client.go

// enqueueToTransaction turns an Enqueue into a types.Transaction
// so that it can be consumed by the SyncService
func enqueueToTransaction(enqueue *Enqueue) (*types.Transaction, error) {
    nonce := *enqueue.QueueIndex
    target := *enqueue.Target
    gasLimit := *enqueue.GasLimit
    origin := *enqueue.Origin

    blockNumber := new(big.Int).SetUint64(*enqueue.BlockNumber)
    timestamp := *enqueue.Timestamp

    data := *enqueue.Data

    // enqueue transactions have no value
    value := big.NewInt(0)
    tx := types.NewTransaction(nonce, target, value, gasLimit, big.NewInt(0), data)

    // The index does not get a check as it is allowed to be nil in the context
    // of an enqueue transaction that has yet to be included into the CTC
    txMeta := types.NewTransactionMeta(
        blockNumber,
        timestamp,
        &origin,
        types.QueueOriginL1ToL2,

        // 对于未定序的 enqueue 消息，enqueue.Index 为 nil，因此 txMeta.Index 也为 nil
        enqueue.Index,

        enqueue.QueueIndex,
        data,
    )

    tx.SetTransactionMeta(txMeta)

    return tx, nil
}

Sequencer 通过 enqueueToTransaction() 将 L1 上发起的一笔交易的事件数据 enqueue 转为 types.Transaction，各字段设置如下：

• to, gasLimit, data 设置为 L1 调用的对应字段
  • 参考 function enqueue(address _target, uint256 _gasLimit, bytes memory _data)
• value, gasPrice 设置为 0
• nonce 设置为 queueIndex
• v, r, s 未设置

注意：因为 value, gasPrice 为 0，所以中继到 L2 的交易不消耗 gas

另外，还设置了交易的 meta 字段，用途在下文描述

--

L2 Sequencer 还做了如下特殊处理：

由于 nonce 设置为 queueIndex，而 queueIndex 是全局变量，因此对同一 msg.sender 而言，nonce 可能不连续；因此在执行交易前的检查中，对来自 L1 的交易会跳过 nonce 检查

// l2geth/core/state_transition.go
func (st *StateTransition) preCheck() error {
    // Make sure this transaction's nonce is correct.

    // 如果需要检查 nonce
    if st.msg.CheckNonce() {
        if rcfg.UsingOVM {
            // 如果是 L1->L2 消息，跳过 nonce 检查，直接调用 buyGas()
            if st.msg.QueueOrigin() == types.QueueOriginL1ToL2 {
                return st.buyGas()
            }
        }

        // 正常的检查 nonce 逻辑
        nonce := st.state.GetNonce(st.msg.From())
        if nonce < st.msg.Nonce() {
            return ErrNonceTooHigh
        } else if nonce > st.msg.Nonce() {
            return ErrNonceTooLow
        }
    }
    return st.buyGas()
}

另外，由于无法通过 v, r, s 签名计算交易发起者，因此在通过 EVM 执行交易前，交易转为 Message 时，会从 meta 中取出 L1MessageSender 作为 msg.from

// l2geth/core/types/transaction.go

func (tx *Transaction) AsMessage(s Signer) (Message, error) {
    var err error
    if rcfg.UsingOVM {
        // transaction 转 Message 时，对于 L1->L2 的消息，取 meta.L1MessageSender 作为 Origin
        if tx.meta.QueueOrigin == QueueOriginL1ToL2 && tx.meta.L1MessageSender != nil {
            msg.from = *tx.meta.L1MessageSender
        } else {
            msg.from, err = Sender(s, tx)
        }
    } else {
        msg.from, err = Sender(s, tx)
    }

    return msg, err
}

--

经过上面的处理，L1->L2 消息被转换为了 L2 上的一笔交易，它将与正常交易一样被执行和打包

为什么需要 Address Alias

相关文档

• Why is address aliasing an issue?
• Differences between Ethereum and Optimism #Address Aliasing

对于 L1->L2 消息，如果 msg.sender 为合约，那么在 L2 执行时，Origin 会被加上偏移

这是出于安全考虑，举例如下：

首先，攻击者在 L2 构造一个开放源码的合约，如 Uniswap pair，并诱导用户对合约授权 (approve())

然后，攻击者在 L1 同一地址部署恶意合约，并通过该恶意合约向 L2 传递攻击消息，取出用户授权的 ERC20 token；参数如下：

• msg.sender
  • Uniswap pair (L2) / 恶意合约 (L1)
• _target
  • ERC20 地址
• _data
  • transferFrom(userAddress, attackerAddress, amount)

解决：

经过讨论：What should the value of tx.origin and msg.sender be for L1 to L2 transactions? #1480，决定参考 Arbitrum 的方案，通过 Address Alias 对msg.sender 地址做了偏移；由于哈希的抗碰撞性，攻击者无法计算相关参数 (如 Create nonce 或 Create2 salt)，因此无法将合约部署在偏移前的地址

如何实现 Censorship resistance

通过 L1->L2 消息传递，Optimism 实现了抗 Sequencer 审查某位用户

原因：Sequencer 可以忽略整个 L1->L2 消息队列，但无法跳过队列中某笔请求；因为对队列的消耗，必须遵守 FIFO 的顺序 (queueIndex 要求递增)

比较 Arbitrum

相关文档

• Inside Arbitrum: Inboxes, fast and slow
• The Sequencer and Censorship Resistance: Unhappy/Uncommon Case: Sequencer Isn’t Doing It’s Job

根据上文，Optimism Sequencer 虽然无法审查某位用户，但可以审查所有 L1->L2 交易，拒绝执行

与之相对的，Arbitrum 实现了 force inclusion 的功能，抗审查能力更强；两者比较如下：

Arbitrum 和 Optimism 一样，都有两条队列：Sequencer 定序队列，L1->L2 交易队列

• Sequencer 定序队列
  • Optimism: ChainStorageContainer-CTC-batches
  • Arbitrum: SequencerInbox (文档也称 fast Inbox)
• L1->L2 交易队列
  • Optimism: CanonicalTransactionChain.queueElements
  • Arbitrum: Inbox (文档也称 delayed Inbox)

正常而言，不管是 Optimism 还是 Arbitrum，Sequencer 都会处理 L2 发起的交易，以及消费 L1->L2 交易队列，对这两种交易定序，定序结果存储在 Sequencer 定序队列中；

区别如下：

在 Optimism 中，只存在唯一一个定序者 Sequencer，两种交易都由它确定顺序；这带来了 Sequencer 拒不处理 L1->L2 交易队列的风险

相反，在 Arbitrum 中，存在两个定序者：L2 Sequencer 和 L1 合约；如果 L1->L2 交易队列中的一笔交易L1->L2 交易经过一段时间 (目前配置为 24 小时) 未被定序，用户可以在 L1 调用合约函数 SequencerInbox.forceInclusion()，强制将它包含进 定序队列

可以预见：Arbitrum 比起 Optimism，其 Sequencer 的实现会更复杂：L1 合约定序，可能会导致后续 L2 Sequencer 回滚

L2->L1

理解如下：

根据 欺诈证明，Optimism 每笔交易都有一个 stateRoot 需要上传到 L1，如果在合约存储，需要消耗大量的 gas

为了节省成本，L1 合约将一批 stateRoot 组织成 Merkle Tree，只存储根哈希；以此支持某个 stateRoot 的存在性证明

流程概览

1. 用户或合约在 L2 调用入口函数 L2CrossDomainMessenger.sendMessage()，它进一步调用
   OVM_L2ToL1MessagePasser.passMessageToL1()，它计算消息哈希，更新合约状态

2. batch-submitter 向 L1 合约提交 txBatch 和 stateBatch

3. L1 合约计算 stateBatch 组织而成的 Merkle Tree，存储根哈希

4. relayer 监控在 L1 上经过挑战期的 L2->L1 消息，为其生成证明后，在 L1 调用合约 L1CrossDomainMessenger.relayMessage()；L1 合约验证证明后，调用目标合约

发起消息

// packages/contracts/contracts/L2/messaging/L2CrossDomainMessenger.sol
contract L2CrossDomainMessenger is IL2CrossDomainMessenger {
    function sendMessage(
        address _target,
        bytes memory _message,
        uint32 _gasLimit
    ) public {
        bytes memory xDomainCalldata = Lib_CrossDomainUtils.encodeXDomainCalldata(
            _target,
            msg.sender,
            _message,
            messageNonce
        );

        iOVM_L2ToL1MessagePasser(Lib_PredeployAddresses.L2_TO_L1_MESSAGE_PASSER).passMessageToL1(
            xDomainCalldata
        );
    }
}

// packages/contracts/contracts/L2/predeploys/OVM_L2ToL1MessagePasser.sol
contract OVM_L2ToL1MessagePasser is iOVM_L2ToL1MessagePasser {
    function passMessageToL1(bytes memory _message) public {
        // Note: although this function is public, only messages sent from the
        // L2CrossDomainMessenger will be relayed by the L1CrossDomainMessenger.
        // This is enforced by a check in L1CrossDomainMessenger._verifyStorageProof().
        sentMessages[keccak256(abi.encodePacked(_message, msg.sender))] = true;
    }
}

Sequencer 在执行 L2->L1 交易时，将修改 OVM_L2ToL1MessagePasser 状态树 (sentMessages[slot])，因而进导致 世界树 的变化，反应在 区块头部 的 stateRoot 字段。batch-submitter 将提交 stateRoot 到 L1 并等待挑战

其中，slot 的计算方式为 keccak256(_message + sender)

提交 stateBatch

// packages/contracts/contracts/L1/rollup/StateCommitmentChain.sol

contract StateCommitmentChain is IStateCommitmentChain, Lib_AddressResolver {
    function _appendBatch(bytes32[] memory _batch, bytes memory _extraData) internal {
        address sequencer = resolve("OVM_Proposer");
        (uint40 totalElements, uint40 lastSequencerTimestamp) = _getBatchExtraData();

        // 2.组织 batchHeader
        Lib_OVMCodec.ChainBatchHeader memory batchHeader = Lib_OVMCodec.ChainBatchHeader({
            batchIndex: getTotalBatches(),
            // 1. 将多笔 stateRoot 组织成一棵 Merkle Tree，得到 batchRoot；
            batchRoot: Lib_MerkleTree.getMerkleRoot(_batch),
            batchSize: _batch.length,
            prevTotalElements: totalElements,
            extraData: _extraData
        });

        // 3. 存储 batchHeader 到数组，可以方便的通过 batchIndex 索引
        batches().push(
            Lib_OVMCodec.hashBatchHeader(batchHeader),
            _makeBatchExtraData(
                uint40(batchHeader.prevTotalElements + batchHeader.batchSize),
                lastSequencerTimestamp
            )
        );
    }
}

batch-submitter 监听 L2 区块，一次批量提交多笔区块的 stateRoot 到 L1 合约

L1 合约处理如下：

1. 将多笔 stateRoot 组织成一棵 Merkle Tree，得到根哈希 batchRoot
2. 组织 meta 信息，得到 batchHeader
3. 存储 batchHeader 到数组 (可以通过 batchIndex 进行索引)

证明生成

// packages/sdk/src/cross-chain-messenger.ts
export class CrossChainMessenger implements ICrossChainMessenger {
  public async getMessageProof(
    message: MessageLike
  ): Promise<CrossChainMessageProof> {
    const resolved = await this.toCrossChainMessage(message)
    if (resolved.direction === MessageDirection.L1_TO_L2) {
      throw new Error(`can only generate proofs for L2 to L1 messages`)
    }

    // 1. 通过 txHash 向 Sequencer 请求 receipt，得到这笔交易所在区块的 stateRoot
    const stateRoot = await this.getMessageStateRoot(resolved)
    if (stateRoot === null) {
      throw new Error(`state root for message not yet published`)
    }

    // 2. 计算 slot
    const messageSlot = ethers.utils.keccak256(
      ethers.utils.keccak256(
        encodeCrossChainMessage(resolved) +
          remove0x(this.contracts.l2.L2CrossDomainMessenger.address)
      ) + '00'.repeat(32)
    )

    // 3. 通过 eth_getProof 请求 Sequencer 生成 slot 的证明
    const stateTrieProof = await makeStateTrieProof(
      this.l2Provider as any,
      resolved.blockNumber,
      this.contracts.l2.OVM_L2ToL1MessagePasser.address,
      messageSlot
    )

    return {
      stateRoot: stateRoot.stateRoot,
      stateRootBatchHeader: stateRoot.batch.header,
      stateRootProof: {
        index: stateRoot.stateRootIndexInBatch,
        // 4. 生成 stateRoot 在 stateBatch 的存在性证明
        siblings: makeMerkleTreeProof(
          stateRoot.batch.stateRoots,
          stateRoot.stateRootIndexInBatch
        ),
      },
      stateTrieWitness: stateTrieProof.accountProof,
      storageTrieWitness: stateTrieProof.storageProof,
    }
  }
}

relayer 监控已经过了挑战期的 L2->L1 交易，为其生成证明并提交到 L1；过程如下：

1. 通过 txHash 向 Sequencer 请求 receipt，得到这笔交易所在区块的 stateRoot
2. 计算消息的 slot，规则与上面合约的计算方式一致：keccak256(_message + sender)
3. 生成 消息在 合约地址 OVM_L2ToL1MessagePasser.address 的存在性的证明 (通过调用 Sequencer eth_getProof)
4. 生成 stateRoot 在此前已提交的 stateBatch 的存在性证明 (通过将 stateBatch 组织成 Merkle Tree)

根据 Should we remove the Message Relayer? #1362，relayer 用于测试环境，后续将废弃。开发者需要自己使用 Optimism SDK (开发中) 来桥接交易并承担 L1 gas 费用。

中继消息

// packages/contracts/contracts/L1/messaging/L1CrossDomainMessenger.sol

contract L1CrossDomainMessenger {
    function relayMessage(
        address _target,
        address _sender,
        bytes memory _message,
        uint256 _messageNonce,
        L2MessageInclusionProof memory _proof
    ) public nonReentrant whenNotPaused {
        bytes memory xDomainCalldata = Lib_CrossDomainUtils.encodeXDomainCalldata(
            _target,
            _sender,
            _message,
            _messageNonce
        );

        // 1. 验证 L2->L1 交易存在
        require(
            _verifyXDomainMessage(xDomainCalldata, _proof) == true,
            "Provided message could not be verified."
        );

        bytes32 xDomainCalldataHash = keccak256(xDomainCalldata);

        // 2. 检查交易未曾被中继
        require(
            successfulMessages[xDomainCalldataHash] == false,
            "Provided message has already been received."
        );

        // 3a. 调用前：修改 xDomainMsgSender 为 _sender
        xDomainMsgSender = _sender;

        // 3b. 消息调用
        (bool success, ) = _target.call(_message);

        // 3c. 调用后：重置 xDomainMsgSender
        xDomainMsgSender = Lib_DefaultValues.DEFAULT_XDOMAIN_SENDER;

        // Mark the message as received if the call was successful. Ensures that a message can be
        // relayed multiple times in the case that the call reverted.
        if (success == true) {
            // 4. 如果调用成功，设置标记
            successfulMessages[xDomainCalldataHash] = true;
            emit RelayedMessage(xDomainCalldataHash);
        } else {
            emit FailedRelayedMessage(xDomainCalldataHash);
        }
    }

    // 辅助函数：获取交易发起者的地址
    function xDomainMessageSender() public view returns (address) {
        require(
            xDomainMsgSender != Lib_DefaultValues.DEFAULT_XDOMAIN_SENDER,
            "xDomainMessageSender is not set"
        );
        return xDomainMsgSender;
    }
}

中继消息的流程如下：

1. 验证 L2->L1 交易存在，分为两步：
   1. 证明 交易 存在 stateRoot 中
   2. 证明 stateRoot 存在 batchRoot (已过挑战期的 stateBatch，参考 提交 stateBatch) 中
2. 检查消息未曾被成功中继
3. 中继消息，被调用方可以通过 xDomainMessageSender() 获取交易发起者的地址
4. 如果成功，设置标记

比较 Arbitrum

Optimism 对 L2->L1 消息传递 在 L1 的处理，与 Arbitrum 的 Retryable Ticket 设计 类似：

1. 没有权限限制，任何人可以调用 relayMessage()
2. 没有次数限制，可以多次重试直到成功
3. 没有时间限制

理解如下：用户需要自己承担消息在 L1 上的执行费用，即要求用户自己调用 relayMessage()

StandardBridge

Using the Standard Token Bridge
Adding an ERC20 token to the standard bridge
Adding a custom bridge to Optimism

StandardBridge 基于上文描述的消息传递机制，实现 ETH，ERC20 在 L1 与 L2 之间的桥接；但不支持非同质化代币 如 NFT，开发者可以自行通过通用消息传递机制来实现

在实现上，主要为 L2StandardBridge.sol 和 L2StandardBridge.sol，代码比较简单

在应用上，Optimism 基于 StandardBridge 实现了官方桥 Optimism Gateway，支持的 token 列表配置在 optimism.tokenlist.json

--

为什么账户 balance 在 Optimism 中以 ERC20 方式存在?

根据 Historical Note: How OVM_ETH works (as of Optimism v0.5.0) #84，应该是 Optimism 早对 非交互式欺诈证明的实现，是通过在 L1 构造虚拟环境 OVM 来重新执行交易 (合约代码使用修改版本的 solidity 编译器生成，原生 OPCODE 被编译为通过 OVM 获取执行上下文)，而虚拟环境将 balance 封装为 ERC20。参考 欺诈证明，Optimism 目前已暂停 非交互式欺诈证明，但为了保持兼容，在 L2 仍以 ERC20 方式存储账户的 balance

The original motivation for putting L2 ETH in an ERC20 token has to do with the 'containerized' approach behind how the old OVM worked.

EVM 特殊处理

EVM 上下文

// l2geth/core/evm.go

// NewEVMContext creates a new context for use in the EVM.
func NewEVMContext(msg Message, header *types.Header, chain ChainContext, author *common.Address) vm.Context {
    // If we don't have an explicit author (i.e. not mining), extract from the header
    var beneficiary common.Address
    if author == nil {
        beneficiary, _ = chain.Engine().Author(header) // Ignore error, we're past header validation
    } else {
        beneficiary = *author
    }

    if rcfg.UsingOVM {
        // When using the OVM, we must:
        // - Set the Time to be the msg.L1Timestamp
        return vm.Context{
            CanTransfer:   CanTransfer,
            Transfer:      Transfer,
            GetHash:       GetHashFn(header, chain),

            // 如果是 L2 -> L2 消息，则未修改
            // 如果是 L1 -> L2 消息，则可能是 msg.sender 的 alias (如果非 EOA)
            Origin:        msg.From(),

            // 收益地址固定为  0x4200....0011
            Coinbase:      dump.OvmFeeWallet, // Coinbase is the fee vault.

            BlockNumber:   new(big.Int).Set(header.Number),

            // 使得 opTimestamp 取值是 L1Timestamp
            Time:          new(big.Int).SetUint64(msg.L1Timestamp()),

            // 固定为 0
            Difficulty:    new(big.Int), // Difficulty always returns zero.

            GasLimit:      header.GasLimit,
            GasPrice:      new(big.Int).Set(msg.GasPrice()),

            // 设置 l1BlockNumber
            L1BlockNumber: msg.L1BlockNumber(),
        }
    }
}

参考 Differences between Ethereum and Optimism

go-ethereum 在将交易提交给 EVM 执行前，需要创建 vm.Context；Sequencer 做了如下特殊处理：

• Time 设置为 msg.L1Timestamp() (参考 区块时间)
• Origin 设置为 msg.From() (参考 L1->L2)
• Coinbase 设置为固定地址 OvmFeeWallet (0x4200...0011)
• Difficulty 设置为 0

另外，Sequencer 在 vm.Context 中新增了字段 L1BlockNumber；如果 L2 合约需要获取最近的 L1 区块高度，可以查询 预部署合约 Lib_PredeployAddresses.L1_BLOCK_NUMBER (0x4200...0013)

合约部署

Optimism 通过 预部署合约 管理在 L2 上部署合约的权限：OVM_DeployerWhitelist.sol (0x4200...0002)

针对 Create / Create2 两个操作码，EVM 在实际处理前，会从 白名单合约 中查询调用者的权限

// l2geth/core/vm/evm.go

// create creates a new contract using code as deployment code.
func (evm *EVM) create(caller ContractRef, codeAndHash *codeAndHash, gas uint64, value *big.Int, address common.Address) ([]byte, common.Address, uint64, error) {
    if rcfg.UsingOVM {
        if !evm.AddressWhitelisted(caller.Address()) {
            return ret, common.Address{}, gas, errExecutionReverted
        }
    }

  // ...
}

费用

相关文档

• Transaction fees on L2
• Sending data between L1 and L2 #Fees

L1->L2 交易

L2 费用

参考 L1->L2：L2 交易执行：交易在 L2 被中继时，value 和 gasPrice 字段为 0，即不消耗费用

在 How should we pay gas for deposits? #32 中，Optimism 开发团队讨论了另一种方案：在 L2 收取费用；目前没有定稿，偏向已有方案

L1 费用

参考上文，用户不需要为 L1->L2 交易 支付 L2 执行费用；这引起了下面的问题：

风险：攻击者在提交 L1->L2 交易时，将参数 _gasLimit 设置得很大，然后在 L2 合约中进行耗时操作，导致 Sequencer 性能下降

防范：Optimism 设置了阈值 enqueueL2GasPrepaid，如果提交 L1->L2 交易时，参数 _gasLimit 超过阈值，那么合约将根据 超出大小 按比例燃烧 gas；

参数：

• enqueueL2GasPrepaid
  • 配置为 1,920,000
• l2GasDiscountDivisor
  • 配置为 32

// packages/contracts/contracts/L1/rollup/CanonicalTransactionChain.sol

contract CanonicalTransactionChain is ICanonicalTransactionChain, Lib_AddressResolver {
    function enqueue(address _target, uint256 _gasLimit, bytes memory _data) external {
        // 如果 参数 超过 阈值
        if (_gasLimit > enqueueL2GasPrepaid) {
            // 根据 超出大小，计算燃烧的 gas
            uint256 gasToConsume = (_gasLimit - enqueueL2GasPrepaid) / l2GasDiscountDivisor;
            uint256 startingGas = gasleft();

            // 燃烧 gas (通过空转)
            uint256 i;
            while (startingGas - gasleft() < gasToConsume) {
                i++;
            }
        }

        // ...
    }
}

L2 交易

total_fee = l2_fee + l1_data_fee

在 L2 发起的交易，除了需要支付在 L2 本身的费用之外，还需要支付其在 L1 的上链费用。

注意：L2->L1 跨链消息的费用，与 L2->L2 交易费用一致。因为用户需要自己在 L1 调用中继消息，因此中继成本由用户承担 (参考 消息传递：比较 Arbitrum)

L2 费用

l2_fee = l2_gas_price * gas

其中：l2_gas_price 表示 L2 当前的 gasPrice

根据 Transaction fees on L2: Responding to gas price updates，l2_gas_price 会根据拥塞情况动态变化，但我未没找到实现 (Sequencer 确实实现了私有 API rollup_setL2GasPrice()，但没有调用代码)；我在 Optimism L2 链上多次查询该字段的取值，都是 1,000,000 (即 0.001 Gwei)。因此动态 gasPrice 应该是开发中..

目前，eth_gasPrice API 返回的 gasPrice 都是 0.001 Gwei

L1 费用

l1_data_fee = l1_gas_price * (tx_data_gas + fixed_overhead) * dynamic_overhead

字段：

• l1_gas_price
  • L1 平均 gasPrice
• tx_data_gas
  • count_zero_bytes(tx_data) * 4 + count_non_zero_bytes(tx_data) * 16
• fixed_overhead
  • 固定 gas，配置为 2100
• dynamic_overhead
  • 放大系数，配置为 1.24

其中，l1_gas_price 来自 gas-oracle 服务，它定期统计 L1 平均 gasPrice ，更新至 L2 预部署合约 OVM_GasPriceOracle (0x4200...000F)

计算 L1 上链费用：

// l2geth/rollup/fees/rollup_fee.go

func CalculateL1MsgFee(msg Message, state StateDB, gpo *common.Address) (*big.Int, error) {
    // 将交易序列化为 calldata
    tx := asTransaction(msg)
    raw, err := rlpEncode(tx)

    // 读取 GasPriceOracle 中的参数：L1 平均 gasPrice，固定 gas，放大系数
    l1GasPrice, overhead, scalar := readGPOStorageSlots(*gpo, state)

    // 计算 L1 费用
    l1Fee := CalculateL1Fee(raw, overhead, l1GasPrice, scalar)
    return l1Fee, nil
}

func CalculateL1Fee(data []byte, overhead, l1GasPrice *big.Int, scalar *big.Float) *big.Int {
  // 计算 L1 gas
    l1GasUsed := CalculateL1GasUsed(data, overhead)

  // 乘以 gasPrice
    l1Fee := new(big.Int).Mul(l1GasUsed, l1GasPrice)

    // 乘以放大系数 scalar (1.24)
    return mulByFloat(l1Fee, scalar)
}

func CalculateL1GasUsed(data []byte, overhead *big.Int) *big.Int {
    zeroes, ones := zeroesAndOnes(data)

    // 空字节消耗的 gas
    zeroesGas := zeroes * params.TxDataZeroGas

    // 非空字节消耗的 gas
    onesGas := (ones + 68) * params.TxDataNonZeroGasEIP2028

    // 预期 gas
    l1Gas := new(big.Int).SetUint64(zeroesGas + onesGas)

    // 加上 固定 gas
    return new(big.Int).Add(l1Gas, overhead)
}

在执行交易前预先扣除 L1 费用：

// l2geth/core/state_transition.go

func (st *StateTransition) buyGas() error {
    mgval := new(big.Int).Mul(new(big.Int).SetUint64(st.msg.Gas()), st.gasPrice)

    if rcfg.UsingOVM {
        // 如果是 L2 -> L2 消息，需要加上上链费用 l1Fee
        // Only charge the L1 fee for QueueOrigin sequencer transactions
        if st.msg.QueueOrigin() == types.QueueOriginSequencer {
            mgval = mgval.Add(mgval, st.l1Fee)
            if st.msg.CheckNonce() {
                log.Debug("Adding L1 fee", "l1-fee", st.l1Fee)
            }
        }
    }

    // ...
}

Sequencer

根据 EVM 上下文，目前 L2 上所有交易消耗的 gas，都由矿工 0x4200...0011 获得

这个地址是个非常简单的智能合约 OVM_SequencerFeeVault，它实现了一个公开函数 withdraw()：通过 StandardBridge 将 ETH 取出到 L1 上的固定地址 l1FeeWallet；L1FeeWallet 这个地址没有什么特殊逻辑

// packages/contracts/contracts/L2/predeploys/OVM_SequencerFeeVault.sol
contract OVM_SequencerFeeVault {
    function withdraw() public {
        L2StandardBridge(Lib_PredeployAddresses.L2_STANDARD_BRIDGE).withdrawTo(
            Lib_PredeployAddresses.OVM_ETH,
            l1FeeWallet,
            address(this).balance,
            0,
            bytes("")
        );
    }
}

经济模型

• Understanding rollup economics from first principles

TODO 没找到什么资料；从 Optimism 源码看不出来...

两难

Arbitrum 团队关于 Asserter 和 Checker 的思考

• The Cheater Checking Problem: Why the Verifier’s Dilemma is Harder Than You Think

  • the Asserter can cheat randomly, with probability of cheating less than C/(R+L), and a rational Checker will never check, so the Asserter will never get caught cheating.

  • Simply increasing the number of verifiers is very helpful in preventing bribery attacks; however, it has rather negative effects on solving the verifier’s laziness.

• Cheater Checking: How attention challenges solve the verifier’s dilemma

  • Attention challenges
  • The key observation is that as long as P*A > C, then checking is the best strategy, no matter what X (the probability of cheating) is.

激励

TODO

3 - 多项式承诺

有限域 \mathbb{F}_{p} \triangleq \{0, 1, 2, ... p-1\}

群 \mathbb{G} \triangleq \{g^0, g^1, g^2, ... g^{(p-1)}\}，其中 g 为 生成元

在有限域 \mathbb{F}_{p} 上的 d 阶多项式 f(x) = a_0 + a_1x + a_2x^2 + ... + a_dx^d

其中，d 远远小于 p，比如 d 为 2^{20} 而 p 为 2^{512}

--

P 拥有多项式，即他知道系数 \{a_0, a_1, a_2, ... a_d\}

V 做验证

多项式承诺

P 需要向 V 承诺他知道这个多项式，承诺过程：V 给出 在 \mathbb{F}_{p} 域内的随机值 r，P 给出多项式在这个点的取值 f(r)

但是，为了避免 P 作弊，V 不能直接给他 r 明文；而是在加密空间中交互，推导如下：

关键 对多项式 f(x) = a_0 + a_1x + a_2x^2 + ... + a_dx^d 左右求指数，即：

\begin{aligned}
g^{f(r)} =& g^{a_0 + a_1r + a_2r^2 + ... + a_dr^d} \\
=& g^{a_0} \cdot (g^r)^{a_1} \cdot (g^{r^2})^{a_2} \cdot ... \cdot (g^{r^d})^{a_d}
\end{aligned}

即：

V 给出的不是 r，而是加密空间的 \{g, g^r, g^{r^2}, ... g^{r^d}\}，称为公共参数

P 回复的承诺不是 f(r)，而是根据系数 \{a_0, a_1, a_2, ..., a_d\} 计算出的 g^{f(r)}

分析：

• 承诺拥有 binding 的性质，这是对 V 的保护
  • 因为 离散对数 不可解 (准确说法：没有 多项式时间 解法)，所以
  • P 无法通过 \{g, g^r, g^{r^2}, ... g^{r^d}\} 解出 r
  • g^{f(r)} 固定了 f(r)， 而 f(r) 进一步固定了 f
  • 换句话说，随机数 r 对 P 不可见
  • 所以 P 无法伪造承诺
  • V 可以事后要求 P 打开承诺，然后自行根据参数 \{g, g^r, g^{r^2}, ... g^{r^d}\}，计算 g'^{f(r)} 并与 g^{f(r)} 比较

补充：

离散对数 不可解：给出 g^a， 无法反解 a

-

• 承诺拥有 hiding 的性质，这是对 P 的保护
  • 因为 P 回复的承诺为 g^{f(r)}， 所以 V 无法通过它反推 \{a_0, a_1, a_2, ..., a_d\}
  • 换句话说，V 无法从 承诺 反推多项式

--

部分打开

V 给出随机数 z， P 返回多项式计算结果 s， V 表示怀疑

问题：P 如何向 V 证明 f(z) = s

转换：

证明 f(z) = s， 等于证明 f(z) - s = 0， 即 z 是多项式 f'(x) 的一个根，其中 f'(x) = f(x) - s

根据 因式定理 可知：x -z 是 多项式 f'(x) 的因子

将第二因子记为 t(x)， 则 f'(x) = t(x) \cdot (x - z)， 又因为 f'(x) = f(x) - s， 所以：

f(x) - s = t(x) \cdot (x - z)

P 可以 多项式长除法 (long division)，计算出 t(x)

我们将 t(x) 和 x - z 分别看作新的多项式，则公式右边为 两个多项式的乘法，即 二次方程组

显然，P 不能直接将 二次方程组 给 V，否则 V 可以推导出左边的原始多项式

利用：Schwartz–Zippel lemma

转换：给出一个随机点 r， 只要能承诺这个随机点 r 上 t(x) \cdot (x - z) 的取值，我们就承诺了整个 二次式

换句话说，要承诺

f(x) - s = t(x) \cdot (x - z)

只需承诺

f(r) - s = t(r) \cdot (r - z)

问题：如何做 r 在 多项式乘法 的承诺

解决：

利用椭圆曲线 pairing 的两个性质，来验证乘法关系：

(1) e(g_1, g_2) = g_T

(2) e({g_1}^a, {g_2^b}) = {g_T}^{a \cdot b}

其中，

e 是 椭圆曲线 的 pairing，是个 双线性映射公式，且这个公式公开 (参考 blocksight: 区块链中的数学（六十二）双线性映射)

G_1，G_2， G_T 是乘法循环群，g_1，g_2，g_T 分别是它们的 生成元

过程：

二次方程组 进入加密空间，应用性质 (1) 和 (2)，得到：

\begin{aligned}
& \ f(r) - s = t(r) \cdot (r - z) & \\
\Rightarrow & \ {g_T}^{f(r) - s} = {g_T}^{t(r) \cdot (r - z)} & \\
\Rightarrow & \ {e(g_1, g_2)}^{f(r) - s} = {e(g_1, g_2)}^{t(r) \cdot (r - z)} & 应用 (1)\\
\Rightarrow & \ {e(\frac{{g_1}^{f(r)}}{{g_1}^s}, g2)} = {e({g_1}^{t(r)}, \frac{{g_2}^r}{{g_2}^z})} & 应用 (2)
\end{aligned}

其中，g_1 和 g_2 是公共参数，P 和 V 都知道

V 必须有 5 个参数 {g_1}^{f(r)}，{g_1}^s，{g_1}^{t(r)}，{g_2}^r，{g_2}^z， 才能验证参数

接下来，逐个看这 5 个 参数

• {g_1}^{f(r)}，{g_1}^{t(r)}
  • r 是 setup 阶段随机数，对 P 和 V 保密
  • P 计算出来给 V
• {g_1}^s
  • P 将 s 明文发给 V，V 再计算 {g_1}^s
• {g_2}^r
  • {g_2}^r 是公共参数，对 P 和 V 都已知
  • 由于 离散对数 不可解，任何人无法知道秘密 r
• {g_2}^z
  • g_2 是公共参数，而 z 是 V 选取的随机数，所以 V 可以计算 {g_2}^z

经过上面的处理，V 最终有了这 5 个参数，所以它可以验证整个式子

其中，关键参数有：

• {g_1}^{f(r)}
  • 承诺
  • commitment
• s
  • 声明
  • f(x) 在 z 上的取值
• {g_1}^{t(r)}
  • 证明
  • witness

--

以上就是 P 如何向 V 证明：f(z) = s 的过程，

setup

概括的说，多项式承诺分为两个阶段：承诺 和 打开

在 承诺 阶段，P 向 V 返回 g^{f(r)}

在 打开 阶段，P 向 V 返回 g^{t(r)}

注意：承诺 阶段的随机数 r， 与 打开 阶段的随机数 r， 是同一个

这就引出了 setup 的概念

--

在多项式承诺系统开始前，需要 可信的第三方 通过 setup 构建任何人都不知道的随机数 r， 并通过它计算参数：

\begin{cases}
\{g_1, {g_1}^r, {g_1}^{r^2}, ... {g_1}^{r^d}\} \\
\{g_2, {g_2}^r\}
\end{cases}

这两组参数称为 公开参数 public params，对 P 和 V 都公开

其中，

P 需要 \{g_1, {g_1}^r, {g_1}^{r^2}, ... {g_1}^{r^d}\} 来计算 承诺 和 witness

V 需要的是 \{g_2, {g_2}^r\}

--

引入 可信第三方 来 setup 这些参数，而不由 V 直接选择这些参数，是因为在区块链的应用场景中，P 和 V 的角色可以是动态的，而非一成不变的；比如一个角色今天可能是 V，明天可能是 P

所以，我们要求任何人都不能知道 r， 否则可以作弊

更进一步，在 setup 构建公共参数后，第三方必须销毁随机数 r

一种方式：MPC 多方构建

--

PLONK 中 setup 是 可更新 updatable 的

首先，第三方 {P_1} 通过随机数 r_1 生成公共参数：

{P_1} : \{g_1, {g_1}^{r_1}, {g_1}^{{r_1}^2}, ... {g_1}^{{r_1}^d}\}

然后，第三方 P_2 不信任系统，它可以通过 r_2 更新公共参数：

\begin{cases}
{P_1} : \{g_1, {g_1}^{r_1}, {g_1}^{{r_1}^2}, ... {g_1}^{{r_1}^d}\} \\
{P_2} : \{g_1, {{g_1}^{r_1}}^{r_2}, {{g_1}^{{r_1}^2}}^{{r_2}^2}, ... {{g_1}^{{r_1}^d}}^{{r_2}^d}\} = \{g_1, {g_1}^{r_1 \cdot r_2}, {g_1}^{{r_1 \cdot r_2}^2}, ... {g_1}^{{r_1 \cdot r_2}^d}\}
\end{cases}

注意，{P_1} 不知道 r_2，{P_2} 不知道 r_1

因此，任何一方都可以更新公告参数，使得自己和其他人都无法知道随机数 r_1 \cdot r_2 \cdot ...

4 - SRS 与门电路

Kate 承诺：用多项式在某一个随机点上的值，来决定 f(x)

--

电路可满足问题 Circuit Satisfiability Problem

给定 x 和 y， 问是否存在 w 满足 C(x, w) = y

其中: x 已知输入，y 已知输出，w 未知输入

零知识证明：P 找到了这个解 w。他要向 V 证明自己知道这个解，但不暴露 w

例子：

现有加法电路 a_1 + b_1 = c_1， 假设 a_1 和 c_1 已知，分别为 1 和 3，问是否存在 b_1 满足这个加法电路

表达为约束方程，即：

\begin{cases}
a_1 + b_1 = c_1 \\
a_1 = 1 \\
c_1 = 3 \\
\end{cases}

可以看到，在上面的例子中，一个门存在 3 个约束

问题：如何实现一个门有且只有一个约束

解答：引入 常数门

这样使得约束方程为

\begin{cases}
a_1 + b_1 = c_1 \\
a_1 = c_0 \\
c_0 = 1 \\
\end{cases}

其中，c_0 为假想的门，它的约束为 c_0 = 1 (忽略左右输入 a_0 和 b_0 的约束)

因为引入了 常数门，系统中一共存在 5 种情况的约束：

• a + b = c 加法约束
• a \cdot b = c 乘法约束
• a = constant 已知输入 x 或 已知输出 y
• 或 b = constant -
• 或 c = constant -

这样改造后，一套电路等价于一个约束系统，每个门对应一个约束，且每个约束必然是 5 种约束之一

问题转为：如何用 一个公式 表达 上面 5 个公式

回答：

(Q_L) a+ (Q_R) b + (Q_O) c + (Q_M) ab + Q_C = 0

通过恰当地选择下面 5 个系数，公式就可以表达上面 5 种约束中的一种

• Q_L 加法门左输入系数
• Q_R 加法门右输入系数
• Q_O 输出系数
• Q_M 乘法门系数
• Q_C 常数

--

如果有 n 个门，那么存在 3n 个变量

\begin{bmatrix}
a_1 & a_2 & a_3 & ... & a_n \\
b_1 & b_2 & b_3 & ... & b_n \\
c_1 & c_2 & c_3 & ... & c_n \\
\end{bmatrix}

这些变量中，有一系列的约束方程；这些约束方程，可以分为两大类，一类是 门约束，一类是 复制约束：

门约束 可以归结为 (Q_L) a + (Q_R) b + (Q_O) c + (Q_M) ab + Q_C = 0， 每个门 有且只有 一个 门约束

复制约束 一定是形式 a_3 = c_5；即在 3n 个变量中，某一个变量等于另一个变量

5 - 置换与复制约束

门约束

zk-SNARK 电路有输入和输出，问给定 x 和 y， 问是否存在 w 满足 C(x, w) = y

这里有个反直觉的地方：为什么输出 y 是已知的，还没计算又怎么知道输出呢？

例子：已知一个图，问是否存在三色染色的解。在这个问题中，图 就是已知输出

在零知识证明中，P 求出了这个数学方程的解 w， 在不暴露 w 的情况下，向 V 证明自己求出了解

--

回忆 #4 - SRS 与门电路，我们引入 常数门 后，一个电路系统有一套约束系统，每个门有且仅有一个约束条件

假设电路有 n 个门，则他有 n 个约束条件；我们以 C 表示一个约束，则它可以表示为 C_i(a_i, b_i, c_i) = 0

每个约束条件为一个方程，共 n 个约束条件，形成方程组：

\begin{cases}
C_1(a_1, b_1, c_1) = 0 \\
C_2(a_2, b_2, c_2) = 0 \\
C_3(a_3, b_3, c_3) = 0 \\
... \\
C_n(a_n, b_n, c_n) = 0 \\
\end{cases}

注意：这个 方程组 等价于 原来的问题 C(x, w) = y

每个方程可以表达为 统一格式 (但需要正确的选择系数)：

({Q_L}_i) a_i + ({Q_R}_i) b_i + ({Q_O}_i) c_i + ({Q_M}_i) a_i b_i + {Q_C}_i = 0

所以，方程组 可以表达为：

\begin{cases}
({Q_L}_0) a_0 + ({Q_R}_0) b_0 + ({Q_O}_0) c_0 + ({Q_M}_0) a_0 b_0 + {Q_C}_0 = 0 \\
({Q_L}_1) a_1 + ({Q_R}_1) b_1 + ({Q_O}_1) c_1 + ({Q_M}_1) a_1 b_1 + {Q_C}_1 = 0 \\
({Q_L}_2) a_2 + ({Q_R}_2) b_2 + ({Q_O}_2) c_2 + ({Q_M}_2) a_2 b_2 + {Q_C}_2 = 0 \\
... \\
({Q_L}_n) a_n + ({Q_R}_n) b_n + ({Q_O}_n) c_n + ({Q_M}_n) a_n b_n + {Q_C}_n = 0 \\
\end{cases}

如果按 每个门有一个方程组 的思路，横向看待方程组，每个方程有 8 个符号：输入输出 a，b，c 加上 5 个选择系数

关键 切换视角，纵向看待 8 个符号，可以得到 8 个多项式

以 Q_L 为例，它有 n 个点，且在点 i 上的取值为 {Q_L}_i

通过 拉格朗日插值，我们可以得到这些 点 和 取值 表示的 n-1 阶的多项式

更进一步的，我们可以将这 8 个多项式，表达为：

{Q_L}(x) \cdot a(x) + {Q_R}(x) \cdot b(x) + {Q_O}(x) \cdot c(x) + {Q_M}(x) \cdot a(x) \cdot b(x) + {Q_C}(x) = 0 \\
where \quad x \in \{x_1, x_2, ..., x_n\}

注意：这个多项式只在 \{x_1, x_2, ..., x_n\} 这些点上取值为 0

问题：x 取值不是 \{1, 2, ..., n\} 吗，怎么成了 \{x_1, x_2, ..., x_n\}

理解：每个门的下标记为 \{1, 2, ..., n\} 只是为了理解方便，实际上必须是在有限域 \mathbb{F}_{p} 上，精心选择的 n 个点 \{x_1, x_2, ..., x_n\}

参考 复制约束：\{x_1, x_2, ..., x_n\} 需要满足一定的要求，实际取值为 \{\omega, \omega^2, ..., \omega^n = 1\}

关键 再次转换

转为多项式

F(x) = {Q_L}(x) \cdot a(x) + {Q_R}(x) \cdot b(x) + {Q_O}(x) \cdot c(x) + {Q_M}(x) \cdot a(x) \cdot b(x) + {Q_C}(x) = 0 \\
\quad where \quad x \in \{x_1, x_2, ..., x_n\}

注意 F(x) 只在 \{x_1, x_2, ..., x_n\} 取值为 0，所以这些点是 F(x) 的根

我们定义 Z_S(X) = (x - x_1)(x - x_2)...(x - x_n)， 那么 Z_S(x) 一定可以被 F(x) 整除，即：Z_S(x) \mid F(x)

因此，我们一定可以求得 t_g(x)， 使其满足：F(x) = t_g(x) \cdot {Z_S}(x)

注意：使用长除法的前提：知道 8 个符号的信息

反思 零知识证明 和 电路

首先，一套电路系统有 已知输入 x， 已知输出 y 和 未知输入 w；问题为：是否存在 w， 满足 C(x, w) = y

我们再看多项式：

{Q_L}(x) \cdot a(x) + {Q_R}(x) \cdot b(x) + {Q_O}(x) \cdot c(x) + {Q_M}(x) \cdot a(x) \cdot b(x) + {Q_C}(x) = 0 \\
where \quad x \in \{x_1, x_2, ..., x_n\}

其中，

关键

• 5 个 Q_x 选择系数

  • 代表一套已经构建的电路中，每个门的元信息 (每个门是加法门，还是乘法门，还是常数门，或布尔门)
  • 是已知信息

• a 和 b 和 c

  • 代表每个门的 输入和输出
  • 是否已知，取决于 P 是否已经求出 C(x, w) = y 的解
  • 如果 P 解出 w， 它就结合 已知输入 x 运算电路，得到每个门的输入和输出

复制约束

首先，把 3n 个变量看成一个集合，则 复制约束 可以看成对这个集合的 partition 划分：把一个集合拆分成若干个子集的并，且子集之间不相交；即：F = F_1 \cup F_2 \cup ... \cup F_k

然后，对每个子集 F_i 进行置换，得到 \{\sigma_1, \sigma_2, ..., \sigma_k\}；然后把所有子集的置换连乘，得到整体置换 \sigma；即：\sigma = \sigma_1 \cdot \sigma_2 \cdot ... \cdot \sigma_k

所以：

\sigma \begin{bmatrix}
a_1 & a_2 & a_3 & ... & a_n \\
b_1 & b_2 & b_3 & ... & b_n \\
c_1 & c_2 & c_3 & ... & c_n \\
\end{bmatrix}
= \begin{bmatrix}
a_x & a_x & a_x & ... & a_x \\
b_x & b_x & b_x & ... & b_x \\
c_x & c_x & c_x & ... & c_x \\
\end{bmatrix}

这个置换方程，也就覆盖了所有的 复制约束 copy constraint

TODO 没懂

\prod_{i = 1}^{N} U_i = 1

问题：怎样把 U_1 \cdot U_2 \cdot ... \cdot U_N = 1 变成 U(x) (注意不是 U(x_i)) 的方程

解答：PLONK 用 递归 来处理

定义 Z_1， Z_2， ...，Z_{N+1}， 递归如下

\begin{cases}
Z_1 = 1 \\
Z_2 = U_1 \\
Z_3 = U_1 \cdot U_2 \\
... \\
Z_N = U_1 \cdot U_2 \cdot ... \cdot U_{N-1} \\
Z_{N+1} = 1 = Z_1 \\
\end{cases}

统一表述为 Z_{i+1} = Z_i \cdot U_i

进一步，我们发现 Z(x_{i+1}) = Z(x_i) \cdot U(x_i)

这样，我们几乎得到了想要的 U(x) 的方程，除了 问号 部分：Z(?) = Z(x) \cdot U(x)

解决：在 有限域 \mathbb{F}_{p} 的 乘法群 \mathbb{F}^*_{p} 中找到带 单位根 的 n 阶子群 H：H = \{\omega, \omega^2, ..., \omega^n = 1\}

TODO '单位根'

TODO 没懂

参考 门约束，我们对门的标记不是 \{1, 2, ..., n\}， 而是 H (\{\omega, \omega^2, ..., \omega^n = 1\})

这样我们得到 问号 部分：Z(\omega \cdot x) = Z(x) \cdot U(x)

通过这个结论，我们就把一个很复杂的乘积，转成了多项式

总结

我们把一个电路的问题，完完全全翻译成一些多项式组成的方程组

准确的说，是这两种方程的形式：

\begin{cases}
\begin{aligned}
& {Q_L}(x) \cdot a(x) + {Q_R}(x) \cdot b(x) + {Q_O}(x) \cdot c(x) + {Q_M}(x) \cdot a(x) \cdot b(x) + {Q_C}(x) = 0 & where \quad x \in \{x_1, x_2, ..., x_n\} \\
& Z(\omega \cdot x) - Z(x) \cdot U(x) = 0 & where \quad x \in \{\omega, \omega^2, ..., \omega^n = 1\} \\
\end{aligned}
\end{cases}

分别对应 门约束 和 复制约束

6 - 递归证明

命题：R(x, w) = 1

P：向 V 出示 \pi， 证明自己解出 w

V：验证 V(x, \pi) = 1

递归：

V 向 V1 出示 \pi'， 证明 自己已经拿到了 P 的一个证明，即：V(x, \pi) = 1

V1：验证 V_1(x, \pi') = 1

--

问题：为什么要递归，而不是由 V 直接将 \pi 给 V1

原因：区块链 scalability

命题：存在交易 t_n， 满足状态转移方程：

\exist tn: U(\sigma_{n-1}, t_n) = \sigma_n

P 向 V 出示 \pi_n

\begin{cases}
\pi_1 \equiv \exist t_1: U(\sigma_0, t_1) = \sigma_1 \\
\pi_2 \equiv \exist t_2: U(\sigma_1, t_2) = \sigma_2 \\
\dots \\
\pi_n \equiv \exist tn: U(\sigma_{n-1}, t_n) = \sigma_n \\
\end{cases}

V 进行验证

\begin{cases}
V(\sigma_0, \sigma_1, \pi_1) = 1 \\
V(\sigma_1, \sigma_2, \pi_2) = 1 \\
V(\sigma_2, \sigma_3, \pi_3) = 1 \\
V(\sigma_3, \sigma_4, \pi_4) = 1 \\
\dots \\
V(\sigma_{n-1}, \sigma_n, \pi_n) = 1 \\
\end{cases}

接下来，两两合并：

命题：存在 \sigma_{n-1} 和 \pi_{n-1} 和 \pi_n， 使得 V(\sigma_{n-2}, \sigma_{n-1}, \pi_{n-1}) = 1 和 V(\sigma_{n-1}, \sigma_n, \pi_n) = 1 同时成立：

\exist \sigma_{n-1}, \pi_{n-1}, \pi_{n}: V(\sigma_{n-2}, \sigma_{n-1}, \pi_{n-1}) = 1 \wedge V(\sigma_{n-1}, \sigma_n, \pi_n) = 1

V 需要出示声明 \pi'_1， 证明上面式子成立；

V‘ 进行验证 V(\sigma_0, \sigma_2, \pi'_1) = 1

--

20 层递归，可以证明 2^{20} 笔交易

最后只需要一个 \pi， 就能证明 整个 状态转换 链条 合法

7 - 整体过程分析与总结

原始问题：零知识证明 R(x, w) = 1

其中，R 是个数学算法，可以检查 w 是否是 x 的解；x 是其个问题，w 是问题的解

P 和 V 都知道 R，x， 这是公开信息；

只有 P 解出 w， 这是私密信息，他向 V 证明

把 零知识证明 转为 电路问题：C(x, w) = y

其中，C 表示公开的电一套路结构，x 表示 公开的输入，y 表示 公开的输出，P 和 V 都知道

w 表示 未知输入，P 解出后要向 V 证明

把 电路问题 转为 约束系统

原来的电路系统就被表示成了约束系统，存在两种约束

(1) 门约束

i 表示门的下标，每个门有一个门约束

({Q_L}_i) a_i + ({Q_R}_i) b_i + ({Q_O}_i) c_i + ({Q_M}_i) a_i b_i + {Q_C}_i = 0

(2) 复制约束

另一个门的输出，是另一个门的输入；因此要约束 输入 等于 输出

通过置换，把整套电路系统的所有 复制约束，一起表达为方程：

\sigma \begin{bmatrix}
a_1 & a_2 & a_3 & ... & a_n \\
b_1 & b_2 & b_3 & ... & b_n \\
c_1 & c_2 & c_3 & ... & c_n \\
\end{bmatrix}
= \begin{bmatrix}
a_x & a_x & a_x & ... & a_x \\
b_x & b_x & b_x & ... & b_x \\
c_x & c_x & c_x & ... & c_x \\
\end{bmatrix}

把 门约束系统 转为 多项式

对门约束系统，把带 i 的参数，转为 i 的函数 (纵向看待 5 个选择系数 和 a，b，c)

得到多项式：

F(x) = {Q_L}(x) \cdot a(x) + {Q_R}(x) \cdot b(x) + {Q_O}(x) \cdot c(x) + {Q_M}(x) \cdot a(x) \cdot b(x) + {Q_C}(x) = 0 \\
where \quad x \in \{x_1, x_2, ..., x_n\}

再次强调：F(x) 只在 \{x_1, x_2, ..., x_n\} 取值为 0，所以这些点是 F(x) 的根

我们定义 Z_S(X) = (x - x_1)(x - x_2)...(x - x_n)， 那么 Z_S(x) 一定可以被 F(x) 整除，即：Z_S(x) \mid F(x)

因此，我们一定可以求得 t_g(x)， 使其满足：F(x) = t_g(x) \cdot {Z_S}(x)

把 复制约束系统 转为 多项式

TODO 没懂

第一步，把 置换方程 变成 代数方程

第二步，把 代数方程 换成 多项式 (把 U(x_i) 变成 U(x))

Z(\omega \cdot x) - Z(x) \cdot U(x) = 0 \\
where \quad x \in \{\omega, \omega^2, ..., \omega^n = 1\}

因为多项式 {Z(\omega \cdot x) - Z(x) \cdot U(x)} 在 \{\omega, \omega^2, ..., \omega^n = 1\} 这些点上取值为 0，所以这些点是它的根

我们定义 Z_H(X) = (x - \omega)(x - \omega^2)...(x - \omega^n)， 那么 Z_H(x) 一定可以被 {Z(\omega \cdot x) - Z(x) \cdot U(x)} 整除，即：Z_H(x) \mid Z(\omega \cdot x) - Z(x) \cdot U(x)

因此，我们一定可以求得 t_c(x)， 使其满足：Z(\omega \cdot x) - Z(x) \cdot U(x) = t_c(x) \cdot {Z_H}(x)

结合 门约束 和 复制约束

我们用 复制约束系统 中的 \{\omega, \omega^2, ..., \omega^n = 1\}， 作为 门约束系统中 \{x_1, x_2, ..., x_n\} 的取值，即：Z_S(x) \equiv Z_H(x)

那么，原始的 零知识证明 问题 可以转为：

\exist a(x), b(x), c(x), Z(x), t_g(x), t_c(x) \\
such \ that \\
\begin{cases}
{Q_L}(x) \cdot a(x) + {Q_R}(x) \cdot b(x) + {Q_O}(x) \cdot c(x) + {Q_M}(x) \cdot a(x) \cdot b(x) + {Q_C}(x) = t_g(x) \cdot {Z_H}(x)\\
Z(\omega \cdot x) - U(x) \cdot Z(x) = t_c(x) \cdot {Z_H}(x)\\
\end{cases}

P 和 V 都知道的公共信息：{Q_L}(x)，{Q_R}(x)，{Q_O}(x)，{Q_M}(x)，{Q_C}(x)，Z_H(x)

P 知道的 但 V 不知道：a(x)，b(x)，c(x)，Z(\omega \cdot x)，t_g(x)，t_c(x)

--

为了简洁，用 G 代表公共信息 {Q_L}(x)，{Q_R}(x)，{Q_O}(x)，{Q_M}(x)，{Q_C}(x)，Z_H(x)

我们可以进一步将上面两个多项式写为：

G(x, a(x), b(x), c(x), Z(\omega \cdot x), t_g(x), t_c(x)) = 0

P 需要向 V 证明，自己知道 a(x)，b(x)，c(x)，Z(\omega \cdot x)，t_g(x)，t_c(x) 满足上面的等式

之前在看 Compound 代码时，感觉存在一些疑问和改进

其中有个疑问昨天得到了回复，趁着这个机会简单整理下笔记

退出市场的资产，仍可被清算

背景

// compound-protocol/contracts/Comptroller.sol

function borrowAllowed(address cToken, address borrower, uint borrowAmount) external returns (uint) {
    if (!markets[cToken].accountMembership[borrower]) {
        // only cTokens may call borrowAllowed if borrower not in market
        require(msg.sender == cToken, "sender must be cToken");

        // attempt to add borrower to the market
        Error err = addToMarketInternal(CToken(msg.sender), borrower);
        if (err != Error.NO_ERROR) {
            return uint(err);
        }

        // it should be impossible to break the important invariant
        assert(markets[cToken].accountMembership[borrower]);
    }
}

function addToMarketInternal(CToken cToken, address borrower) internal returns (Error) {
    Market storage marketToJoin = markets[address(cToken)];

    if (!marketToJoin.isListed) {
        // market is not listed, cannot join
        return Error.MARKET_NOT_LISTED;
    }

    if (marketToJoin.accountMembership[borrower] == true) {
        // already joined
        return Error.NO_ERROR;
    }

    // survived the gauntlet, add to list
    // NOTE: we store these somewhat redundantly as a significant optimization
    //  this avoids having to iterate through the list for the most common use cases
    //  that is, only when we need to perform liquidity checks
    //  and not whenever we want to check if an account is in a particular market
    marketToJoin.accountMembership[borrower] = true;
    accountAssets[borrower].push(cToken);

    emit MarketEntered(cToken, borrower);

    return Error.NO_ERROR;
}

Compound 在借款时会通过 borrowAllowed() 检查用户是否已经进入 cToken 市场

如果未进入，会调用 addToMarketInternal() 将 cToken 添加到用户接触的资产列表 accountAssets[borrower] 中

我查了下 accountAssets[borrower]，似乎只在 存款，借款，和计算用户健康度时使用

其中前面两个操作 (存款，借款) 更多是类似声明的逻辑，没有什么疑点

// compound-protocol/contracts/Comptroller.sol

function getHypotheticalAccountLiquidityInternal(
    address account,
    CToken cTokenModify,
    uint redeemTokens,
    uint borrowAmount) internal view returns (Error, uint, uint) {
    // For each asset the account is in
    CToken[] memory assets = accountAssets[account];
    for (uint i = 0; i < assets.length; i++) {
        CToken asset = assets[i];

        // Too Long Not Listed.
        // ...
    }
}

用户健康度计算代码如上，在计算 account 健康度时，遍历的是 accountAssets[account]

如果用户此前发起退出某个资产市场的交易，如 USDC，则这个资产不在 accountAssets[account] 中

这时，计算健康度会跳过用户的 USDC 资产

清算

上面梳理了背景逻辑，即：退出市场的资产，不会参与清算时用户健康度的计算

内在含义是：该资产可以作为存款收取利息，但由于退出了市场，不会做为抵押物

而在实际清算代码时，我没有找到有关清算交易指定的资产，是否不在用户的 accountAssets 列表中的判断

即已经退出市场，不会作为抵押物的资产，可以被清算..

// compound-protocol/contracts/CToken.sol

function liquidateBorrowFresh(address liquidator, address borrower, uint repayAmount, CTokenInterface cTokenCollateral) internal returns (uint, uint) {
    /* Fail if repayBorrow fails */
    (uint repayBorrowError, uint actualRepayAmount) = repayBorrowFresh(liquidator, borrower, repayAmount);
    if (repayBorrowError != uint(Error.NO_ERROR)) {
        return (fail(Error(repayBorrowError), FailureInfo.LIQUIDATE_REPAY_BORROW_FRESH_FAILED), 0);
    }

    /* We calculate the number of collateral tokens that will be seized */
    (uint amountSeizeError, uint seizeTokens) = comptroller.liquidateCalculateSeizeTokens(address(this), address(cTokenCollateral), actualRepayAmount);
    require(amountSeizeError == uint(Error.NO_ERROR), "LIQUIDATE_COMPTROLLER_CALCULATE_AMOUNT_SEIZE_FAILED");

    /* Revert if borrower collateral token balance < seizeTokens */
    require(cTokenCollateral.balanceOf(borrower) >= seizeTokens, "LIQUIDATE_SEIZE_TOO_MUCH");

    // If this is also the collateral, run seizeInternal to avoid re-entrancy, otherwise make an external call
    uint seizeError;
    if (address(cTokenCollateral) == address(this)) {
        seizeError = seizeInternal(address(this), liquidator, borrower, seizeTokens);
    } else {
        seizeError = cTokenCollateral.seize(liquidator, borrower, seizeTokens);
    }

    return (uint(Error.NO_ERROR), actualRepayAmount);
}

测试

我担心存在理解偏差，于是在 Ropsten 网络上进行了测试：

首先用账户 A 发送 exitMarket 交易，将存入的 cETH 退出市场

然后用账户 A 发送 setUnderlyingPrice 交易，操纵预言机，模拟市场价格波动，使得账户 A 资不抵债

最后用账户 B 发送 liquidateBorrow 交易，清算账户 A 的债务，指定以 cETH 为抵押物

结论是：退出市场的 cETH 确实可以被清算

问题

问题来了：

问题一：已经退出市场的资产，是否应该被清算？

问题二：如果不应该被清算，那么进入市场和退出市场的逻辑，意义何在？

综合考虑，我个人觉得 Compound 原意应该是不允许清算已退出市场的资产；理由如下：

首先，用户在实际存款前必须单独发起进入市场的交易，考虑到 Compound 在以太坊主网运营，交易手续费不可忽视

如果可以被清算，那么进入和退出市场的逻辑没有什么实际用途，在代码中也未找到其他用途

其次，在退出市场前，Compound 提示如下

但是，从另外一个角度来说，退出市场的资产，确实应该支持被清算，否则有损于系统健康度

反馈

两个角度都有道理，我没想明白，于是向 Compound 发送了邮件，一周后收到了回复：问题已知，已退出市场的资产可以被清算；提示文本看起来是有误导

不过，我还是没明白：既然可以被清算，为什么要设计进入退出的功能，用户专门发起这两笔交易的手续费呢...

BTW，前两天 Aave V3 似乎也引入了 资产隔离 的概念..

USDC 钉住 1 美元

前面文章中有举例说明 Compound 价格预言机的流程，以 DAI 为例：首先向 USDC-WETH 交易对查询 WETH 价格，然后向 DAI-WETH 交易对查询 DAI 价格，最后将两者相乘，得到以 USDC 计价的 DAI 价格

换句话说，Compound 中大部分 token 的价格是以 USDC 计价的

这里隐藏了一个假设，USDC 价格是恒定不变的，可以作为计价单位

// https://github.com/smartcontractkit/open-oracle/blob/master/contracts/Uniswap/UniswapAnchoredView.sol

function priceInternal(TokenConfig memory config) internal view returns (uint) {
    if (config.priceSource == PriceSource.REPORTER) return prices[config.symbolHash].price;
    // config.fixedPrice holds a fixed-point number with scaling factor 10**6 for FIXED_USD
    if (config.priceSource == PriceSource.FIXED_USD) return config.fixedPrice;
    if (config.priceSource == PriceSource.FIXED_ETH) {
        uint usdPerEth = prices[ethHash].price;
        require(usdPerEth > 0, "ETH price not set, cannot convert to dollars");
        // config.fixedPrice holds a fixed-point number with scaling factor 10**18 for FIXED_ETH

        return mul(usdPerEth, config.fixedPrice) / ethBaseUnit;
    }
}

实现上，Compound 对 USDC，USDT 等做了特殊处理，其 priceSource 配置为 FIXED_USD，钉在 1 美元

在 USDC 价格波动时，可能会导致一些问题，比如 这个提案 描述的例子：

假设 USDC 因监管或其他原因不断下跌，比如市场价格为 0.5 美元，而 Compound 仍认为其价值 1 美元

由于存在价差，我们可以从外部市场低价借入 USDC，存入 Compound，将其高价抵押借出其他资产

造成的结果是，市场价格不断下跌的 USDC 涌入 Compound，而其他资产被不断借出

提案提出的问题，已经过去几个月了，没有得到官方回复..

抵押率 与 清算阈值

在比较 Compound 和 Aave 时，我发现 Compound 没有 Aave 清算阈值 (Liquidation Threshold) 的概念

在用户体验上，这可能会带来一些问题：

如果用户在 Compound 按最大抵押率借款，只要市场价格稍有波动，其抵押资产就会面临清算风险

// compound-protocol/contracts/Comptroller.sol

function getHypotheticalAccountLiquidityInternal(
    address account,
    CToken cTokenModify,
    uint redeemTokens,
    uint borrowAmount) internal view returns (Error, uint, uint) {

    AccountLiquidityLocalVars memory vars; // Holds all our calculation results
    uint oErr;

    // For each asset the account is in
    CToken[] memory assets = accountAssets[account];
    for (uint i = 0; i < assets.length; i++) {
        CToken asset = assets[i];

        vars.collateralFactor = Exp({mantissa: markets[address(asset)].collateralFactorMantissa});

        // Pre-compute a conversion factor from tokens -> ether (normalized price value)
        vars.tokensToDenom = mul_(mul_(vars.collateralFactor, vars.exchangeRate), vars.oraclePrice);

        // sumCollateral += tokensToDenom * cTokenBalance
        vars.sumCollateral = mul_ScalarTruncateAddUInt(vars.tokensToDenom, vars.cTokenBalance, vars.sumCollateral);
    }
}

其中，在计算 sumCollateral 时，使用的是抵押率 collateralFactor

--

与之相对的，在 Aave 中，贷款时按抵押率计算，而清算时健康度按清算阈值计算；因为清算阈值比抵押率大，因此留出了安全垫

引用链接中的例子：用户抵押价值 2 ETH 的资产，借出 1.575 ETH 的债务，此时健康度为 1.0476

注意例子中的债务，是按资产的最大抵押率借出的；在这种情况下，可以忍受市场价格小范围的波动

比如，市场价格短期波动，导致债务上涨 3% 时，此时健康度仍在 1 以上，用户资产不会面临清算风险

隐患

不在官方仓库中的代码

比如价格预言机，还未被合并，见 Compound 代币和价格预言

又如，官方仓库中 Comptroller，似乎也是较老的版本；而主网实际使用的合约，是修复了 9 月底 COMP 安全事件的版本

--

对于新入手 Compound 的开发者而言，要找到正确的代码，只能求助于 EtherScan 和搜索引擎，体验有点糟糕

更重要的是，会导致接下来的问题：

不同步的主网与测试网络

对于价格预言机，考虑到链下数据不好维护，为了便于测试，可以在测试网部署模拟合约作为 mock

除此之外，应该尽可能保证其他合约在主网和测试网一致，但在 Compound 中并非如此：

比如，最核心的 Unitroller，在 主网 与 测试网络 上部署的代码版本不同

又如 CErc20Immutable 是旧代码，会导致 cToken 无法支持社区治理。主网中这个合约已被废弃，但在测试中仍在使用，比如 Ropsten 中的 cUSDC

--

主网与测试网络之间的不同步，除了削弱测试网络的意义，也增加了新开发者的理解成本

要解决这个问题，首先要解决前面的问题，确保官方仓库与主网部署的合约代码一致

这也就引出了更关键的问题：

测试网络似乎没有发生作用

COMP 安全事件 暴露的问题比较严重：考虑到除了公开的测试网络之外，社区中还有不少开发者搭建着私人测试网络，而理论上，这个问题是必现的；

我们似乎可以得出一个结论：Compound 的测试网络和 测试代码，没有起到作用

那么，Compound 协议安全如何保证呢？社区成员似乎也在担心，比如最近几天出现的提案 Auditing Compound Protocol，Continuous Formal Verification

--

另外，还有代码与文档/产品之间的不同步，原始的升级模式等；限于个人视野未知全貌，某些理解可能存在局限，因此不做展开

以上，一家之言，欢迎指正～

Compound白皮书简述
Compound合约部署
Compound合约升级模式

这里补充下周边： COMP 代币 和 价格预言

COMP

投放计划

为了激励用户，用户每次存款或者借款，Compound 都会奖励 COMP 代币，可以用于治理投票

COMP 每日总产出约为 2312 枚，各市场的分布见 文档，部分市场如下

每个市场，借款和存款产出的 COMP，分别占 50%

以 USDC 市场为例，每日共产出 880.38 枚 COMP，其中通过借款的方式投放 440.19 枚 COMP，借款用户按其借款额度占总借款额度的比例分配；存款同理

配置

如上所述，根据各市场每日产出的 COMP 数量，按每 15 秒一个区块的假设，可以得到每个区块产出的 COMP 数量，记录在 ComptrollerV6Storage 中

contract ComptrollerV6Storage is ComptrollerV5Storage {
    // https://compound.finance/governance/comp

    /// @notice The rate at which comp is distributed to the corresponding borrow market (per block)
    mapping(address => uint) public compBorrowSpeeds;

    /// @notice The rate at which comp is distributed to the corresponding supply market (per block)
    mapping(address => uint) public compSupplySpeeds;
}

compBorrowSpeeds 和 comSupplySpeeds 为 cToken 到每区块产出 COMP 数量的映射

比如对 cUSDC 来说，它在两个映射表中的值都为 67000000000000000 (COMP 的精度为 {10}^{18})

\frac{2 \times 67000000000000000 \times 86400}{15} \approx 880.38 \times {10}^{18}

存款挖矿

用户每次操作，只要可能更新存款，如存款操作，会触发 mintAllowed()，它进一步

- 调用 updateCompSupplyIndex() 更新当前市场的 COMP 存款指数

- 调用 distributeSupplierComp() 分发当前用户此前未结算的存款产出的 COMP

function mintAllowed(address cToken, address minter, uint mintAmount) external returns (uint) {
    // Keep the flywheel moving
    updateCompSupplyIndex(cToken);
    distributeSupplierComp(cToken, minter);

    return uint(Error.NO_ERROR);
}

--

当前市场的 COMP 存款指数更新逻辑如下

/**
* @notice Accrue COMP to the market by updating the supply index
* @param cToken The market whose supply index to update
* @dev Index is a cumulative sum of the COMP per cToken accrued.
*/
function updateCompSupplyIndex(address cToken) internal {
    CompMarketState storage supplyState = compSupplyState[cToken];
    uint supplySpeed = compSupplySpeeds[cToken];
    uint32 blockNumber = safe32(getBlockNumber(), "block number exceeds 32 bits");
    uint deltaBlocks = sub_(uint(blockNumber), uint(supplyState.block));
    if (deltaBlocks > 0 && supplySpeed > 0) {
        uint supplyTokens = CToken(cToken).totalSupply();
        uint compAccrued = mul_(deltaBlocks, supplySpeed);

        Double memory ratio = supplyTokens > 0 ? fraction(compAccrued, supplyTokens) : Double({mantissa: 0});

        supplyState.index = safe224(add_(Double({mantissa: supplyState.index}), ratio).mantissa, "new index exceeds 224 bits");
        supplyState.block = blockNumber;
    } else if (deltaBlocks > 0) {
        supplyState.block = blockNumber;
    }
}

首先判断距离上次更新指数，经过了几个区块 deltaBlocks，另外根据 supplySpeed 判断当前市场是否产出 COMP (0x, Aave 等配置为 0，表示不产出)

条件都满足后，计算 COMP 产出数量，除以 cToken 总供给，得到这几个区块间，平均每个 cToken 对应的 COMP 产出，即代码中的 ratio

也就是说，ratio 可以理解为每持有一个 cToken ，可以得到多少 COMP

最后将 ratio 累加进 COMP 存款指数

--

当前用户此前未结算的 COMP 分发逻辑如下

/**
* @notice Calculate COMP accrued by a supplier and possibly transfer it to them
* @param cToken The market in which the supplier is interacting
* @param supplier The address of the supplier to distribute COMP to
*/
function distributeSupplierComp(address cToken, address supplier) internal {
    // TODO: Don't distribute supplier COMP if the user is not in the supplier market.
    // This check should be as gas efficient as possible as distributeSupplierComp is called in many places.
    // - We really don't want to call an external contract as that's quite expensive.

    CompMarketState storage supplyState = compSupplyState[cToken];
    uint supplyIndex = supplyState.index;
    uint supplierIndex = compSupplierIndex[cToken][supplier];

    // Update supplier's index to the current index since we are distributing accrued COMP
    compSupplierIndex[cToken][supplier] = supplyIndex;

    if (supplierIndex == 0 && supplyIndex >= compInitialIndex) {
        // Covers the case where users supplied tokens before the market's supply state index was set.
        // Rewards the user with COMP accrued from the start of when supplier rewards were first
        // set for the market.
        supplierIndex = compInitialIndex;
    }

    // Calculate change in the cumulative sum of the COMP per cToken accrued
    Double memory deltaIndex = Double({mantissa: sub_(supplyIndex, supplierIndex)});

    uint supplierTokens = CToken(cToken).balanceOf(supplier);

    // Calculate COMP accrued: cTokenAmount * accruedPerCToken
    uint supplierDelta = mul_(supplierTokens, deltaIndex);

    uint supplierAccrued = add_(compAccrued[supplier], supplierDelta);
    compAccrued[supplier] = supplierAccrued;

    emit DistributedSupplierComp(CToken(cToken), supplier, supplierDelta, supplyIndex);
}

首先获取市场最新的 COMP 存款指数，以及用户此前结算时的指数，相减得到 deltaIndex

然后乘以用户持有的 cToken 数量，得到用户这段时间应该获得的 COMP

--

需要说明的是，这里结算的是用户之前的存款，占当前总供给的百分比，不会算入用户接下来马上将改变的存款

换句话说，存款余额的修改，要在至少一个区块之后才会被用于结算 COMP，即用户操作与 COMP 结算是跨区块的

算是降低了被闪电贷攻击的风险

借款挖矿

与存款挖矿大同小异，稍微复杂一些，这里不再赘述

通胀

根据 messari，COMP 的 Inflation Rate 为 27.50%

我没找到其确切公式，不过我们可以自行计算，根据 2021-11-05 和 2022-11-04 的 流动性投放计划 ，简单相除得到通胀系数为 27.34%；和 messari 数据相比，算是大差不差了

但是，这里有个统计陷阱：Founders & team 分批 vest 且 Future team members 也未兑现，部分流动性没有进入市场，因此分母偏大了

也就是说，实际通胀率还要高出不少

不管怎样，通胀率接近甚至超过 30% 的资产，价格稳定在 $100 ~ $300；我看不懂，但我大受震撼～

安全

9月29日 Compound 发生一起安全事件，详见 [事件分析] 9月29日 Compound 62号提案 所引发的可怕Bug

其中，Robert Leshner 提到的 Reservori 合约 (地址)，就是上面投放计划中 User (借贷挖矿) 的 COMP 来源

价格预言机

Compound 同时使用 Uniswap v2 和 Chainlink v2 作为价格预言机

Chainlink 价格以 Uniswap 价格为锚，前者作为实际价格，后者作为基准价格

Chainlink 价格需要在 Uniswap 价格的某段浮动范围内，才能作为有效价格被更新到预言机

代码

compound-finance/open-oracle 中只有 Uniswap 相关代码，我找遍 branches 和 tags 都没找到 Chainlink 部分

最后在 Compound 社区找到这个关于添加 Chainlink 预言机提案的精彩讨论 Oracle Infrastructure: Chainlink Proposal

成果是 Chainlink 团队在 Compound 原有 Open Price Feed 的代码基础上，集成了 Chainlink 聚合器的报价，并进一步做了部署和测试；Compound 社区通过治理，应用了新的预言机

然而，Chainlink 提交的 PR：Oracle Improvement (Chainlink Price Feeds) #150，改动较多，还卡在审核阶段，未被合并..

因此，最新代码不在官方仓库中

审计报告见 Trail of Bits: Chainlink Open-Oracle Summary Report

以下分析基于 Chainklink fork 的仓库 smartcontractkit/open-source

实现

/**
 * @notice This is called by the reporter whenever a new price is posted on-chain
 * @dev called by AccessControlledOffchainAggregator
 * @param currentAnswer the price
 * @return valid bool
 */
function validate(uint256/* previousRoundId */,
        int256 /* previousAnswer */,
        uint256 /* currentRoundId */,
        int256 currentAnswer) external override returns (bool valid) {

    // NOTE: We don't do any access control on msg.sender here. The access control is done in getTokenConfigByReporter,
    // which will REVERT if an unauthorized address is passed.
    TokenConfig memory config = getTokenConfigByReporter(msg.sender);
    uint256 reportedPrice = convertReportedPrice(config, currentAnswer);
    uint256 anchorPrice = calculateAnchorPriceFromEthPrice(config);

    PriceData memory priceData = prices[config.symbolHash];
    if (priceData.failoverActive) {
        require(anchorPrice < 2**248, "Anchor price too large");
        prices[config.symbolHash].price = uint248(anchorPrice);
        emit PriceUpdated(config.symbolHash, anchorPrice);
    } else if (isWithinAnchor(reportedPrice, anchorPrice)) {
        require(reportedPrice < 2**248, "Reported price too large");
        prices[config.symbolHash].price = uint248(reportedPrice);
        emit PriceUpdated(config.symbolHash, reportedPrice);
        valid = true;
    } else {
        emit PriceGuarded(config.symbolHash, reportedPrice, anchorPrice);
    }
}

核心代码如上所示

validate() 由 Chainlink 调用，参数 currentAnswer 表示 Chainlink 链下统计的价格，单位由 Chainlink 控制

以 DAI 为例，假设 currentAnswer 为 100055330

为了方便处理，convertReportedPrice() 将其转为内部单位，得到 1000553

calculateAnchorPriceFromEthPrice() 通过向交易对询价得到链上 Uniswap 交易所的价格，比如为 1001190

接下来判断 failoverActive，这是由社区投票决定的一项配置，表示当前市场 (DAI) 是否忽略 Chainlink 价格，以 Uniswap 价格为准

否则，通过 isWithAnchor() 确认 Chainlink 价格在 Uniswap 价格浮动范围内 ([85%, 115%])

--

/**
 * @notice Calculate the anchor price by fetching price data from the TWAP
 * @param config TokenConfig
 * @return anchorPrice uint
 */
function calculateAnchorPriceFromEthPrice(TokenConfig memory config) internal returns (uint anchorPrice) {
    uint ethPrice = fetchEthAnchorPrice();
    require(config.priceSource == PriceSource.REPORTER, "only reporter prices get posted");
    if (config.symbolHash == ethHash) {
        anchorPrice = ethPrice;
    } else {
        anchorPrice = fetchAnchorPrice(config.symbolHash, config, ethPrice);
    }
}

/**
 * @dev Fetches the current eth/usd price from uniswap, with 6 decimals of precision.
 *  Conversion factor is 1e18 for eth/usdc market, since we decode uniswap price statically with 18 decimals.
 */
function fetchEthAnchorPrice() internal returns (uint) {
    return fetchAnchorPrice(ethHash, getTokenConfigBySymbolHash(ethHash), ethBaseUnit);
}

/**
 * @dev Fetches the current token/usd price from uniswap, with 6 decimals of precision.
 * @param conversionFactor 1e18 if seeking the ETH price, and a 6 decimal ETH-USDC price in the case of other assets
 */
function fetchAnchorPrice(bytes32 symbolHash, TokenConfig memory config, uint conversionFactor) internal virtual returns (uint) {
    (uint nowCumulativePrice, uint oldCumulativePrice, uint oldTimestamp) = pokeWindowValues(config);

    // This should be impossible, but better safe than sorry
    require(block.timestamp > oldTimestamp, "now must come after before");
    uint timeElapsed = block.timestamp - oldTimestamp;

    // Calculate uniswap time-weighted average price
    // Underflow is a property of the accumulators: https://uniswap.org/audit.html#orgc9b3190
    FixedPoint.uq112x112 memory priceAverage = FixedPoint.uq112x112(uint224((nowCumulativePrice - oldCumulativePrice) / timeElapsed));
    uint rawUniswapPriceMantissa = priceAverage.decode112with18();
    uint unscaledPriceMantissa = mul(rawUniswapPriceMantissa, conversionFactor);
    uint anchorPrice;

    // Adjust rawUniswapPrice according to the units of the non-ETH asset
    // In the case of ETH, we would have to scale by 1e6 / USDC_UNITS, but since baseUnit2 is 1e6 (USDC), it cancels

    // In the case of non-ETH tokens
    // a. pokeWindowValues already handled uniswap reversed cases, so priceAverage will always be Token/ETH TWAP price.
    // b. conversionFactor = ETH price * 1e6
    // unscaledPriceMantissa = priceAverage(token/ETH TWAP price) * expScale * conversionFactor
    // so ->
    // anchorPrice = priceAverage * tokenBaseUnit / ethBaseUnit * ETH_price * 1e6
    //             = priceAverage * conversionFactor * tokenBaseUnit / ethBaseUnit
    //             = unscaledPriceMantissa / expScale * tokenBaseUnit / ethBaseUnit
    anchorPrice = mul(unscaledPriceMantissa, config.baseUnit) / ethBaseUnit / expScale;

    emit AnchorPriceUpdated(symbolHash, anchorPrice, oldTimestamp, block.timestamp);

    return anchorPrice;
}

接下来，简单看下 Uniswap 询价逻辑

首先通过 fetchEthAnchorPrice() 从交易对 USDC-WETH 获得按 USDC 计价 (单位 10^{6}) 的 WETH 的价格，比如为 4351156768

然后通过 fetchAnchorPrice() 从交易对 DAI-WETH 获得按 WETH 计价 (单位 10^{18}) 的 DAI 的价格，比如为 230097482692738

上面两个价格相乘，得到 1001190219118269813150784

最后，转换单位，得到按 USDC 计价的 DAI 价格，即上面的 1001190

代理

UniswapAnchoredView 自身可能升级，因此会存在新旧合约实例；升级过程中，我们必须保证两个合约的价格预言同步，且经过一段时间验证后，经由社区投票，用新合约代替旧合约，以此完成升级

然而，依据 Chainlink 的设计，聚合器只能向一个合约地址发送喂价

为了解决这个问题，在 Chainlink 聚合器与 Compound 之间，引入了一层代理合约 ValidatorProxy，它将聚合器的报价同时转发给新旧 UniswapAnchoredView 合约

由于采用的是 报价 (push) 而非 询价 (pull) 的方式，更新价格的成本由 Chainlink 承担，因此 Compound 用户无须额外支付代理层带来的 gas

审计报告见 Sigma Prime: Chainlink ValidatorProxy Security Assessment Report

代码在另一个仓库中: smartcontractkit/chainlink

function validate(
    uint256 previousRoundId,
    int256 previousAnswer,
    uint256 currentRoundId,
    int256 currentAnswer
) external override returns (bool)
{
    // Send the validate call to the current validator
    ValidatorConfiguration memory currentValidator = s_currentValidator;
    address currentValidatorAddress = address(currentValidator.target);
    require(currentValidatorAddress != address(0), "No validator set");
    currentValidatorAddress.call(
        abi.encodeWithSelector(
        AggregatorValidatorInterface.validate.selector,
        previousRoundId,
        previousAnswer,
        currentRoundId,
        currentAnswer
        )
    );

    // If there is a new proposed validator, send the validate call to that validator also
    if (currentValidator.hasNewProposal) {
        address(s_proposedValidator).call(
        abi.encodeWithSelector(
            AggregatorValidatorInterface.validate.selector,
            previousRoundId,
            previousAnswer,
            currentRoundId,
            currentAnswer
        )
        );
    }
    return true;
}

逻辑非常直白了..

外部调用有好几种指令，下面以最常见的 CALL 为例

问题

讨论最多的是 CALL 指令的参数0 gas 具体的作用，比如：

问题一：参数0 是否无用，为什么 opCall() 中直接 pop 掉了？

func opCall(pc *uint64, interpreter *EVMInterpreter, scope *ScopeContext) ([]byte, error) {
    stack := scope.Stack
    // Pop gas. The actual gas in interpreter.evm.callGasTemp.
    // We can use this as a temporary value
    temp := stack.pop()
    gas := interpreter.evm.callGasTemp
    // Pop other call parameters.
    addr, value, inOffset, inSize, retOffset, retSize := stack.pop(), stack.pop(), stack.pop(), stack.pop(), stack.pop(), stack.pop()

    // Too Long Not Listed
    // ...
}

问题二：此前 Paradigm CTF 2021: BabySandbox 题解，能否稍做解释？

问题三：题解测试有效，但为什么修改原题，CALL 时 0x4000 改为 0x30000 的话，题解无效？

pragma solidity 0.7.0;

contract BabySandbox {
    function run(address code) external payable {
        assembly {
            // if we're calling ourselves, perform the privileged delegatecall
            if eq(caller(), address()) {
                switch delegatecall(gas(), code, 0x00, 0x00, 0x00, 0x00)
                    case 0 {
                        returndatacopy(0x00, 0x00, returndatasize())
                        revert(0x00, returndatasize())
                    }
                    case 1 {
                        returndatacopy(0x00, 0x00, returndatasize())
                        return(0x00, returndatasize())
                    }
            }

            // ensure enough gas
            if lt(gas(), 0xf000) {
                revert(0x00, 0x00)
            }

            // load calldata
            calldatacopy(0x00, 0x00, calldatasize())

            // run using staticcall
            // if this fails, then the code is malicious because it tried to change state
            if iszero(staticcall(0x4000, address(), 0, calldatasize(), 0, 0)) {
                revert(0x00, 0x00)
            }

            // if we got here, the code wasn't malicious
            // run without staticcall since it's safe
            switch call(0x4000, address(), 0, 0, calldatasize(), 0, 0)
                case 0 {
                    returndatacopy(0x00, 0x00, returndatasize())
                    // revert(0x00, returndatasize())
                }
                case 1 {
                    returndatacopy(0x00, 0x00, returndatasize())
                    return(0x00, returndatasize())
                }
        }
    }
}

定义

黄皮书关于 gas 机制的介绍，确实比较散乱..

要解释上面的问题，首先需要理解 CALL 的定义：

\mathbf{i} \equiv \boldsymbol{\mu}_{\mathbf{m}}[ \boldsymbol{\mu}_{\mathbf{s}}[3] \dots (\boldsymbol{\mu}_{\mathbf{s}}[3] + \boldsymbol{\mu}_{\mathbf{s}}[4] - 1) ]

\begin{aligned}
(\boldsymbol{\sigma}', g', A^+, \mathbf{o}) \equiv \begin{cases}{\Theta}(\boldsymbol{\sigma}, I_{\mathrm{a}}, I_{\mathrm{o}}, t, t, C_{\text{\tiny CALLGAS}}(\boldsymbol{\mu}), I_{\mathrm{p}}, \boldsymbol{\mu}_{\mathbf{s}}[2], \boldsymbol{\mu}_{\mathbf{s}}[2], \mathbf{i}, I_{\mathrm{e}} + 1, I_{\mathrm{w}}) & \text{if} \ \boldsymbol{\mu}_{\mathbf{s}}[2] \leqslant \boldsymbol{\sigma}[I_{\mathrm{a}}]_{\mathrm{b}} \;\wedge I_{\mathrm{e}} < 1024 \\ (\boldsymbol{\sigma}, g, \varnothing, ()) & \text{otherwise} \end{cases}
\end{aligned}

n \equiv \min(\{ \boldsymbol{\mu}_{\mathbf{s}}[6], \lVert \mathbf{o} \rVert\})

\boldsymbol{\mu}'_{\mathbf{m}}[ \boldsymbol{\mu}_{\mathbf{s}}[5] \dots (\boldsymbol{\mu}_{\mathbf{s}}[5] + n - 1) ] = \mathbf{o}[0 \dots (n - 1)]

\boldsymbol{\mu}'_{\mathbf{o}} = \mathbf{o}

\boldsymbol{\mu}'_{\mathrm{g}} \equiv \boldsymbol{\mu}_{\mathrm{g}} + g'

\boldsymbol{\mu}'_{\mathbf{s}}[0] \equiv x

A' \equiv A \Cup A^+

t \equiv \boldsymbol{\mu}_{\mathbf{s}}[1] \bmod 2^{160}

where x=0 if the code execution for this operation failed due to an {exceptional\ halting} (or for a \text{\small REVERT}) \boldsymbol{\sigma}' = \varnothing or if \boldsymbol{\mu}_{\mathbf{s}}[2] > \boldsymbol{\sigma}[I_{\mathrm{a}}]_{\mathrm{b}} (not enough funds) or I_{\mathrm{e}} = 1024 (call depth limit reached); x=1 otherwise.

\boldsymbol{\mu}'_{\mathrm{i}} \equiv M(M(\boldsymbol{\mu}_{\mathrm{i}}, \boldsymbol{\mu}_{\mathbf{s}}[3], \boldsymbol{\mu}_{\mathbf{s}}[4]), \boldsymbol{\mu}_{\mathbf{s}}[5], \boldsymbol{\mu}_{\mathbf{s}}[6])

Thus the operand order is: gas, to, value, in offset, in size, out offset, out size.

C_{\text{\tiny CALL}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) \equiv C_{\text{\tiny GASCAP}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) + C_{\text{\tiny EXTRA}}(\boldsymbol{\sigma}, \boldsymbol{\mu})

C_{\text{\tiny CALLGAS}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) \equiv \begin{cases} C_{\text{\tiny GASCAP}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) + G_{\mathrm{callstipend}} & \text{if} \quad \boldsymbol{\mu}_{\mathbf{s}}[2] \neq 0 \\ C_{\text{\tiny GASCAP}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) & \text{otherwise} \end{cases}

C_{\text{\tiny GASCAP}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) \equiv \begin{cases} \min\{ L(\boldsymbol{\mu}_{\mathrm{g}} - C_{\text{\tiny EXTRA}}(\boldsymbol{\sigma}, \boldsymbol{\mu})), \boldsymbol{\mu}_{\mathbf{s}}[0] \} & \text{if} \quad \boldsymbol{\mu}_{\mathrm{g}} \ge C_{\text{\tiny EXTRA}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) \\ \boldsymbol{\mu}_{\mathbf{s}}[0] & \text{otherwise}\end{cases}

C_{\text{\tiny EXTRA}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) \equiv G_{\mathrm{call}} + C_{\text{\tiny XFER}}(\boldsymbol{\mu}) + C_{\text{\tiny NEW}}(\boldsymbol{\sigma}, \boldsymbol{\mu})

C_{\text{\tiny XFER}}(\boldsymbol{\mu}) \equiv \begin{cases}G_{\mathrm{callvalue}} & \text{if} \quad \boldsymbol{\mu}_{\mathbf{s}}[2] \neq 0 \\0 & \text{otherwise} \end{cases}

C_{\text{\tiny NEW}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) \equiv \begin{cases} G_{\mathrm{newaccount}} & \text{if} \quad \mathtt{DEAD}(\boldsymbol{\sigma}, \boldsymbol{\mu}_{\mathbf{s}}[1] \bmod 2^{160}) \wedge \boldsymbol{\mu}_{\mathbf{s}}[2] \neq 0 \\ 0 & \text{otherwise}\end{cases}

资料

除了 CALL 自身定义外，可能还需要参考附录：

Appendix G. Fee Schedule

Appendix H. Virtual Machine Specification H.1. Gas Cost

填坑

Paradigm CTF 2021: BabySandbox 题解挖了个坑，引出上面的问题二和问题三

这里尝试用另外一个坑的方式作为例子，算是把两个坑填一填～

在 Ethernaut 第13题 Gatekeeper One 题解中，有提到对某些 OPCODE 的 GAS 存在疑惑

比如题解中的测试交易，gas 消耗状况如下

注意 [140]，在准备调用 CALL 前，堆栈和内存如下

结合 CALL 定义的相关公式和上面截图，可知此时

\boldsymbol{\mu}_{\mathbf{s}}[0] = 0x2c1e9f = 2891423

\boldsymbol{\mu}_{\mathbf{s}}[2] = 0

\boldsymbol{\mu}_{\mathrm{g}} = 2973782

问题如下：

为什么 [141] 的 Gas 为 2891423，而 [140] 的 GasCost 为 2891523，这两个数字是怎么来的？

解答

上面例子中 (\boldsymbol{\mu}_{\mathbf{s}}[3], \boldsymbol{\mu}_{\mathbf{s}}[4]) \gt (\boldsymbol{\mu}_{\mathbf{s}}[5], \boldsymbol{\mu}_{\mathbf{s}}[6])

因此没有扩展内存，即内存相关的 gas 为 0

--

推导1 C_{\text{\tiny EXTRA}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) = 100

已知公式

C_{\text{\tiny EXTRA}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) \equiv G_{\mathrm{call}} + C_{\text{\tiny XFER}}(\boldsymbol{\mu}) + C_{\text{\tiny NEW}}(\boldsymbol{\sigma}, \boldsymbol{\mu})

C_{\text{\tiny XFER}}(\boldsymbol{\mu}) \equiv \begin{cases}
G_{\mathrm{callvalue}} & \text{if} \quad \boldsymbol{\mu}_{\mathbf{s}}[2] \neq 0 \\
0 & \text{otherwise}
\end{cases}

C_{\text{\tiny NEW}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) \equiv \begin{cases}
G_{\mathrm{newaccount}} & \text{if} \quad \mathtt{DEAD}(\boldsymbol{\sigma}, \boldsymbol{\mu}_{\mathbf{s}}[1] \bmod 2^{160}) \wedge \boldsymbol{\mu}_{\mathbf{s}}[2] \neq 0 \\
0 & \text{otherwise}
\end{cases}

又有 \boldsymbol{\mu}_{\mathbf{s}}[2] 为 0

因此 C_{\text{\tiny XFER}}(\boldsymbol{\mu}) = 0 且 C_{\text{\tiny NEW}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) = 0

因此 C_{\text{\tiny EXTRA}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) = G_{\mathrm{call}} + 0 + 0

再查看编译得到的 OPCODE

GatekeeperOne(target).enter.gas(sendGas)(_gateKey);

上面代码会先通过 EXTCODESIZE 检查 target 是否存在源码，然后 CALL 时再对 target 发起消息调用。

根据 EIP-2929: Gas cost increases for state access opcodes

前面 [131] 的 EXTCODESIZE 首次对该地址操作，消耗 2600 gas；因此接下来 [141] CALL 时，只需要消耗 100 gas，即 G_{\mathrm{call}} = 100

因此 C_{\text{\tiny EXTRA}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) = G_{\mathrm{call}} + 0 + 0 = 100

// github.com/ethereum/go-ethereum@v1.10.6/params/protocol_params.go

const (
    ColdAccountAccessCostEIP2929 = uint64(2600) // COLD_ACCOUNT_ACCESS_COST
    WarmStorageReadCostEIP2929   = uint64(100)  // WARM_STORAGE_READ_COST
)

// github.com/ethereum/go-ethereum@v1.10.6/core/vm/eips.go

func enable2929(jt *JumpTable) {
    jt[CALL].constantGas = params.WarmStorageReadCostEIP2929
    jt[CALL].dynamicGas = gasCallEIP2929
}

// github.com/ethereum/go-ethereum@v1.10.6/core/vm/operations_acl.go

var (
    gasCallEIP2929         = makeCallVariantGasCallEIP2929(gasCall)
)

func makeCallVariantGasCallEIP2929(oldCalculator gasFunc) gasFunc {
    return func(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memorySize uint64) (uint64, error) {
        addr := common.Address(stack.Back(1).Bytes20())
        // Check slot presence in the access list
        warmAccess := evm.StateDB.AddressInAccessList(addr)
        // The WarmStorageReadCostEIP2929 (100) is already deducted in the form of a constant cost, so
        // the cost to charge for cold access, if any, is Cold - Warm
        coldCost := params.ColdAccountAccessCostEIP2929 - params.WarmStorageReadCostEIP2929
        if !warmAccess {
            evm.StateDB.AddAddressToAccessList(addr)
            // Charge the remaining difference here already, to correctly calculate available
            // gas for call
            if !contract.UseGas(coldCost) {
                return 0, ErrOutOfGas
            }
        }
        // Now call the old calculator, which takes into account
        // - create new account
        // - transfer value
        // - memory expansion
        // - 63/64ths rule
        gas, err := oldCalculator(evm, contract, stack, mem, memorySize)
        if warmAccess || err != nil {
            return gas, err
        }
        // In case of a cold access, we temporarily add the cold charge back, and also
        // add it to the returned gas. By adding it to the return, it will be charged
        // outside of this function, as part of the dynamic gas, and that will make it
        // also become correctly reported to tracers.
        contract.Gas += coldCost
        return gas + coldCost, nil
    }
}

--

推导2 C_{\text{\tiny GASCAP}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) = 2891423

已知公式

C_{\text{\tiny GASCAP}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) \equiv \begin{cases}
\min\{ L(\boldsymbol{\mu}_{\mathrm{g}} - C_{\text{\tiny EXTRA}}(\boldsymbol{\sigma}, \boldsymbol{\mu})), \boldsymbol{\mu}_{\mathbf{s}}[0] \} & \text{if} \quad \boldsymbol{\mu}_{\mathrm{g}} \ge C_{\text{\tiny EXTRA}}(\boldsymbol{\sigma}, \boldsymbol{\mu})\\
\boldsymbol{\mu}_{\mathbf{s}}[0] & \text{otherwise}
\end{cases}

其中

(318)

L(n) \equiv n - \lfloor n / 64 \rfloor

The Dark Side of Ethereum 1/64th CALL Gas Reduction

// github.com/ethereum/go-ethereum@v1.10.6/core/vm/gas.go

// callGas returns the actual gas cost of the call.
//
// The cost of gas was changed during the homestead price change HF.
// As part of EIP 150 (TangerineWhistle), the returned gas is gas - base * 63 / 64.
func callGas(isEip150 bool, availableGas, base uint64, callCost *uint256.Int) (uint64, error) {
    if isEip150 {
        availableGas = availableGas - base
        gas := availableGas - availableGas/64
        // If the bit length exceeds 64 bit we know that the newly calculated "gas" for EIP150
        // is smaller than the requested amount. Therefore we return the new gas instead
        // of returning an error.
        if !callCost.IsUint64() || gas < callCost.Uint64() {
            return gas, nil
        }
    }
    if !callCost.IsUint64() {
        return 0, ErrGasUintOverflow
    }

    return callCost.Uint64(), nil
}

参考截图，这里 \boldsymbol{\mu}_{\mathbf{s}}[0] 为 2891423，\boldsymbol{\mu}_{\mathrm{g}} 为 2973782，且如上所述 C_{\text{\tiny EXTRA}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) 为 100

因此 C_{\text{\tiny GASCAP}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) = \min\{ (2973782 - 100) - \lfloor (2973782 - 100) / 64 \rfloor, 2891423 \} = 2891423

又根据公式

C_{\text{\tiny CALLGAS}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) \equiv  \begin{cases}
C_{\text{\tiny GASCAP}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) + G_{\mathrm{callstipend}} & \text{if} \quad \boldsymbol{\mu}_{\mathbf{s}}[2] \neq 0 \\
C_{\text{\tiny GASCAP}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) & \text{otherwise}
\end{cases}

因此 C_{\text{\tiny CALLGAS}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) = C_{\text{\tiny GASCAP}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) = 2891423

再根据公式

\begin{aligned}
(\boldsymbol{\sigma}', g', A^+, \mathbf{o}) \equiv \begin{cases}{\Theta}(\boldsymbol{\sigma}, I_{\mathrm{a}}, I_{\mathrm{o}}, t, t, C_{\text{\tiny CALLGAS}}(\boldsymbol{\mu}), I_{\mathrm{p}}, \boldsymbol{\mu}_{\mathbf{s}}[2], \boldsymbol{\mu}_{\mathbf{s}}[2], \mathbf{i}, I_{\mathrm{e}} + 1, I_{\mathrm{w}}) & \text{if} \ \boldsymbol{\mu}_{\mathbf{s}}[2] \leqslant \boldsymbol{\sigma}[I_{\mathrm{a}}]_{\mathrm{b}} \;\wedge I_{\mathrm{e}} < 1024 \\ (\boldsymbol{\sigma}, g, \varnothing, ()) & \text{otherwise} \end{cases}
\end{aligned}

其中，{\Theta} 第6个参数为表示目标合约的 gas

因此，[141] 的 Gas 为 2891423

--

推导3 C_{\text{\tiny CALL}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) = 2891523

最后根据公式

C_{\text{\tiny CALL}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) \equiv C_{\text{\tiny GASCAP}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) + C_{\text{\tiny EXTRA}}(\boldsymbol{\sigma}, \boldsymbol{\mu})

因此，[140] 的 GasCost 为 C_{\text{\tiny CALL}}(\boldsymbol{\sigma}, \boldsymbol{\mu}) = 2891423 + 100 = 2891523

小结

理解上面的例子，应该就可以理解问题一和问题二了

至于问题三，为什么修改原题，加大 CALL 首个参数后题解无效？可以看看 C_{\text{\tiny GASCAP}} 中的 min

最后，此前的题解利用 EIP-2929: Gas cost increases for state access opcodes 的方式比较非主流，正经解答请参考官方题解~

最后的最后，可以思考下，假设当时题目首个参数确实为比较大的值，那么能否仍然利用 EIP-2929 解题呢？// 一时挖坑一时爽

最近觉得还是稍微整理发出来，抛砖引玉～

版本基于 VERSION 80085f7 – 2021-07-11

黄皮书混用了 = 和 \equiv，时而表示赋值，时而表示等价指代，注意区分

2. The Blockchain Paradigm 区块链范式

以太坊可以看作是一个交易驱动的状态机

公式 (1)

\boldsymbol{\sigma}_{t+1} \equiv \Upsilon(\boldsymbol{\sigma}_{t}, T)

其中

• \Upsilon 某次状态转移的函数
• {\sigma} 状态

挖矿

• 挖矿
  • 通过付出一定的工作量，与其他潜在区块竞争 一系列交易(一个区块) 的记账权
• 系统激励
  • 以状态转换函数的形式，给指定账户增加 ETH

公式 (2) (3) (4)

\begin{aligned}
\boldsymbol{\sigma}_{t+1} & \quad\equiv\quad {\Pi}(\boldsymbol{\sigma}_{t}, B) \\
B & \quad\equiv\quad (..., (T_0, T_1, ...), ...) \\
\Pi(\boldsymbol{\sigma}, B) & \quad\equiv\quad {\Omega}(B, {\Upsilon}(\Upsilon(\boldsymbol{\sigma}, T_0), T_1) ...)
\end{aligned}

其中

• \Omega 区块奖励状态转换函数，参考公式 (169) (170) (171) (172)
• B 表示一个区块，包含一系列交易和一些其他组成部分
• \Pi 区块状态转换函数，参考公式 (177)

2.2 Which History? 如何选择历史?

agreed-upon scheme

• blocktree 区块树
  • 去中心化
  • 每个参与者都有机会在前一个区块后，自己创建一个新的区块
  • 形成一棵树(blocktree)
• 共识
  • 如何从根节点到叶节点形成一条区块链
• 分叉
  • 无法达成共识
  • 各节点认可的 根节点到叶节点的路径(最佳区块链) 不同

(5)

\beta = 1

\beta chain ID，参考 EIP-155: Simple replay attack protection

3. Conventions 约定

符号

• \boldsymbol{\sigma} 世界状态(world-state)

• \boldsymbol{\mu} 虚拟机状态(machine-state)

• \Upsilon 状态转换函数

• C 费用，例如C_\text{SSTORE} 是执行 SSTORE 操作的费用

• \texttt{KEC} Keccak-256

• T 一笔以太坊交易

• n nonce 用于防止重放攻击

• \mathbf{o} 消息调用的输出

• \mathbb{B}_{32} 长度为32的字节序列

• \mathbb{N}_{256} 所有比 2^256 小的正整数

• \boldsymbol{\mu}_{\mathbf{s}}[0] 虚拟机栈(stack)的栈顶元素

• \boldsymbol{\mu}_{\mathbf{m}}[0..31] 虚拟机内存(memory)中的前32个条目

• \delta某个 opcode 的出栈个数

状态

熟悉下面三种表示方式，对于后文理解状态转换非常关键

• \Box 原始值/状态
• \Box' 最终值/状态
• \Box^*, \Box^{**}, ... 中间值/状态

函数

公式 (6) \ell 求序列的末尾元素

\ell(\mathbf{x}) \equiv \mathbf{x}[\lVert \mathbf{x} \rVert - 1]

4. Blocks, State and Transactions 区块，状态与交易

4.1 World Stage 世界状态

参考

• 以太坊的数据存储结构
• 以太坊MPT原理，你最值得看的一篇
• 以太坊之PMT

世界状态

• 维护 账户地址 及其 账户状态 的映射
  • a
    • 账户地址
    • 大小为160位(20字节)
  • \boldsymbol{\sigma}[a]
    • 账户状态
    • 含义
      • 编码方式 RLP
        • Recursive Length Prefix
        • 递归长度前缀编码
      • 用于序列化数据后传递到网络或存储
• 注意
  • 世界状态不直接存储在区块链上

\boldsymbol{\sigma}[a] 账户状态

• \boldsymbol{\sigma}[a]_{\mathrm{n}}
  • nonce
  • 含义
    • 如果账户是钱包地址(非合约账户)，表示由此账户发出的交易数量
    • 如果账户是智能合约，表示由此账户创建的合约数量
• \boldsymbol{\sigma}[a]_{\mathrm{b}}
  • balance
  • 余额
• \boldsymbol{\sigma}[a]_{\mathrm{s}}
  • storageRoot
  • 含义
    • 如果账户是智能合约
      • 每个账户有自己的一棵 MRT 树，存储合约的内部状态(变量)
        • MPT (Merkle Patricia Tree)
          • Merkle Tree + Patricia Tree
      • storageRoot 就是树的根节点
• \boldsymbol{\sigma}[a]_{\mathrm{c}}
  • codeHash
  • 含义
    • 账户持有的代码 bytecode 的 hash
      • 创建后不可被修改
      • 没有代码表示智能合约
  • 推导
    • 用 b 来表示 代码
    • 则 \texttt{KEC}(\mathbf{b}) = \boldsymbol{\sigma}[a]_{\mathrm{c}}

公式 (7)

\texttt{TRIE}\big(L_{\mathrm{I}}^*(\boldsymbol{\sigma}[a]_{\mathbf{s}})\big) \quad\equiv\quad \boldsymbol{\sigma}[a]_{\mathrm{s}}

其中

{\sigma}[a]_{\mathbf{s}} 表示账户的所有内部状态组成的 TRIE 树的根节点

对这棵树的所有节点做坍塌转换，即可得到根节点的 hash 值

其中 公式 (8) (9)

L_{\mathrm{I}}\big( (k, v) \big) \quad\equiv\quad \big(\texttt{KEC}(k), \texttt{RLP}(v)\big)

k \in \mathbb{B}_{32} \quad \wedge \quad v \in \mathbb{N}

(10) 世界状态坍塌函数 L_{\mathrm{S}}

L_{\mathrm{S}}(\boldsymbol{\sigma}) \quad\equiv\quad \{ p(a): \boldsymbol{\sigma}[a] \neq \varnothing \}

其中 公式 (11)

p(a) \quad\equiv\quad \big(\texttt{KEC}(a), \texttt{RLP}\big( (\boldsymbol{\sigma}[a]_{\mathrm{n}}, \boldsymbol{\sigma}[a]_{\mathrm{b}}, \boldsymbol{\sigma}[a]_{\mathrm{s}}, \boldsymbol{\sigma}[a]_{\mathrm{c}}) \big) \big)

--

函数 L_{\mathrm{S}} 和 Trie 函数一起用来提供一个世界状态的简短标识(hash)

我们假定:

公式 (12)

\forall a: \boldsymbol{\sigma}[a] = \varnothing \; \vee \; (a \in \mathbb{B}_{20} \; \wedge \; v(\boldsymbol{\sigma}[a]))

公式 (13) v 表示账户有效性的验证函数

v(x) \quad\equiv\quad x_{\mathrm{n}} \in \mathbb{N}_{256} \wedge x_{\mathrm{b}} \in \mathbb{N}_{256} \wedge x_{\mathrm{s}} \in \mathbb{B}_{32} \wedge x_{\mathrm{c}} \in \mathbb{B}_{32}

其中

• x_{\mathrm{n}} nonce
• x_{\mathrm{b}} balance
• x_{\mathrm{s}} storageRoot
• x_{\mathrm{c}} codeHash

公式 (14)

\mathtt{EMPTY}(\boldsymbol{\sigma}, a) \equiv \boldsymbol{\sigma}[a]_{\mathrm{c}} = \texttt{KEC}\big(()\big) \wedge \boldsymbol{\sigma}[a]_{\mathrm{n}} = 0 \wedge \boldsymbol{\sigma}[a]_{\mathrm{b}} = 0

EMPTY 账户

• 没有 code
• 且 nonce 为0
• 且 balance 为0

公式 (15)

\mathtt{DEAD}(\boldsymbol{\sigma}, a) \quad\equiv\quad \boldsymbol{\sigma}[a] = \varnothing \vee \mathtt{EMPTY}(\boldsymbol{\sigma}, a)

DEAD 账户

• 账户对应的状态不存在
• 或者它是 EMPTY 账户

4.2 The Transaction 交易

两种交易类型

• 消息调用 message call
• 合约创建 contract creation

共同字段

• T_{\mathrm{n}}
  • nonce
  • 由交易发送者发送的交易数量
• T_{\mathrm{p}}
  • gasPrice
  • gas 单位价格
• T_{\mathrm{g}}
  • gasLimit
  • 执行这个交易的最大 gas
• T_{\mathrm{t}}
  • to
  • 交易接收地址
• T_{\mathrm{v}}
  • value
  • 含义
    • 如果是消息调用交易
      • 转移到交易接收者的 wei 的数量
    • 如果是合约创建交易
      • 对新建合约的捐款
• T_{\mathrm{w}} , T_{\mathrm{r}} , T_{\mathrm{s}}
  • v, r, s
  • 含义
    • ECDSA 签名的3个组成部分
    • 可以从中推导交易发起者 from address

特有字段

• T_{\mathrm{i}}
  • init
  • 交易类型
    • 合约创建
  • 含义
    • 是一段 EVM-code，它将返回 body，这是这个账户每次接收到消息调用时回执行的代码
    • init 代码仅在合约创建时被执行一次，然后就被丢弃
• T_{\mathrm{d}}
  • data
  • 交易类型
    • 消息调用
  • 含义
    • 用于指定消息调用的输入数据

公式 (16)

L_{\mathrm{T}}(T) \quad\equiv\quad \begin{cases}
(T_{\mathrm{n}}, T_{\mathrm{p}}, T_{\mathrm{g}}, T_{\mathrm{t}}, T_{\mathrm{v}}, T_{\mathbf{i}}, T_{\mathrm{w}}, T_{\mathrm{r}}, T_{\mathrm{s}}) & \text{if} \; T_{\mathrm{t}} = \varnothing\\
(T_{\mathrm{n}}, T_{\mathrm{p}}, T_{\mathrm{g}}, T_{\mathrm{t}}, T_{\mathrm{v}}, T_{\mathbf{d}}, T_{\mathrm{w}}, T_{\mathrm{r}}, T_{\mathrm{s}}) & \text{otherwise}
\end{cases}

在这里，我们假设除了任意长度的字节数组 T_{\mathrm{i}} 和 T_{\mathrm{d}} 以外，所有变量都是作为整数来进行 RLP 编码

公式 (17)

\begin{aligned}
& T_{\mathrm{n}} \in \mathbb{N}_{256} & \quad\wedge\quad & T_{\mathrm{v}} \in \mathbb{N}_{256} & \quad\wedge\quad & T_{\mathrm{p}} \in \mathbb{N}_{256} \quad \wedge \\
& T_{\mathrm{g}} \in \mathbb{N}_{256} & \quad\wedge\quad & T_{\mathrm{w}} \in \mathbb{N}_{256} & \quad\wedge\quad & T_{\mathrm{r}} \in \mathbb{N}_{256} \quad \wedge \\
& T_{\mathrm{s}} \in \mathbb{N}_{256} & \quad\wedge\quad & T_{\mathbf{d}} \in \mathbb{B} & \quad\wedge\quad &  T_{\mathbf{i}} \in \mathbb{B}
\end{aligned}

其中

公式 (18)

\mathbb{N}_{\mathrm{n}} = \{ P: P \in \mathbb{N} \wedge P < 2^n \}

公式 (19)

T_{\mathbf{t}} \in \begin{cases} \mathbb{B}_{20} & \text{if} \quad T_{\mathrm{t}} \neq \varnothing \\
\mathbb{B}_{0} & \text{otherwise}\end{cases}

对于合约创建交易，T_{\mathrm{t}} 是 空字节 的 RLP

4.3 The Block 区块

Block

• H
  • 当前区块的区块头
• \mathbf{T}
  • 当前区块内的一系列交易
• \mathbf{U}
  • 当前区块内的叔块头列表

H (block header)

• H_{\mathrm{p}}
  • parentHash
  • 父区块 block header 的 hash
• H_{\mathrm{o}}
  • ommersHash
  • 当前区块的叔块列表的 hash
• H_{\mathrm{c}}
  • beneficiary
  • 因为挖到当前区块而获得奖励收益的账户地址
• H_{\mathrm{r}}
  • stateRoot
    • state trie 根节点的 hash
      • 交易被执行完且区块定稿后的状态
      • 区块内的所有交易得到的状态，组成一棵树
• H_{\mathrm{t}}
  • transactionsRoot
    • transaction trie 根节点的 hash
      • 当前区块中所有交易组成的一棵树
        H_{\mathrm{e}}
  • receiptsRoot
    • receipt trie 根节点的 has
      • 当前区块中所有交易的收据组成的一棵树
• H_{\mathrm{b}}
  • logsBloom
  • 当前区块中所有交易的收据数据中的可索引信息(产生日志的地址和日志主题)组成的 Bloom 过滤器
• H_{\mathrm{d}}
  • difficulty
  • 含义
    当前区块的难度水平
    根据前一个区块的难度水平和时间戳计算得到
• H_{\mathrm{i}}
  • number
  • 当前区块的祖先的数量
• H_{\mathrm{l}}
  • gasLimit
  • 目前每个区块的 gas 开支上限
• H_{\mathrm{g}}
  • gasUsed
  • 当前区块中所有交易所用掉的 gas 之和
• H_{\mathrm{s}}
  • timestamp
  • 当前区块初始化时的 Unix 时间戳
• H_{\mathrm{x}}
  • extraData
  • 含义
    • 与当前区块相关的任意字节数据
    • 必须在 32 字节以内
• H_{\mathrm{m}}
  • mixHash
  • 含义
    • 一个 hash 值
    • 用于与 H_{\mathrm{n}} 一起证明当前区块已经承载了足够的计算量
• H_{\mathrm{n}}
  • nonce
  • 含义
    • 一个64位的随机整数
    • 用于与 H_{\mathrm{m}} 一起证明当前区块已经承载了足够的计算量
  • 注意
    • 这里的 nonce 是个随机数，与账户下的 nonce 定义不同

公式 (20)

B \quad\equiv\quad (B_{\mathrm{H}}, B_{\mathbf{T}}, B_{\mathbf{U}})

4.3.1 Transaction Receipt 交易收据

每个交易一定会有一条对应的收据

R

• Transaction Receipt
• 含义
  • 每个交易执行过程中的特定信息，会被编码为交易收据
• 用途
  • 零知识证明
  • 索引
  • 搜索
• B_{\mathbf{R}}[i]
  • 当前区块第 i 个交易的收据

H_{\mathrm{e}}

• receiptsRoot
• 含义
  • 区块内的收据组成 receipt trie
  • 其根节点的 hash 存储在 H_{\mathrm{e}} 中

公式 (21)

R \quad\equiv\quad (R_{\mathrm{z}}, R_{\mathrm{u}}, R_{\mathrm{b}}, R_{\mathbf{l}})

R 一条收据的组成

• R_{\mathrm{u}}
  • 当前区块中，交易发生后的累积 gas 使用量
• R_{\mathrm{l}}
  • 交易过程中创建的一系列日志
• R_{\mathrm{b}}
  • 256字节大小的 hash
  • 由一系列日志构成的 Bloom 过滤器
• R_{\mathrm{z}}
  • 交易的状态码

公式 (22)

R_{\mathrm{z}} \in \mathbb{N}

公式 (23)

R_{\mathrm{u}} \in \mathbb{N} \quad \wedge \quad R_{\mathrm{b}} \in \mathbb{B}_{256}

公式 (24)

O \quad\equiv\quad (O_{\mathrm{a}}, ({O_{\mathbf{t}}}_0, {O_{\mathbf{t}}}_1, ...), O_{\mathbf{d}})

只有被调用的智能合约，自身显式调用 LOG0，LOG1，LOG2，LOG3，LOG4 才会生成日志

R_{\mathrm{l}}

• 由一系列日志组成
• (O_0,O_1,...)

O 一条日志的组成

• O_{\mathrm{a}}
  • 当前被调用的智能合约的地址 (一定不会包括 EOA 地址)
  • 跟随消息调用上下文变化
  • 例子
    • EOA -> ContracA -> ContractB -> ContractC
• O_{\mathrm{t}}
  • 一系列日志主题
• O_{\mathrm{d}}
  • 日志数据

// github.com/ethereum/go-ethereum@v1.10.6/core/vm/instructions.go

// make log instruction function
func makeLog(size int) executionFunc {
    return func(pc *uint64, interpreter *EVMInterpreter, scope *ScopeContext) ([]byte, error) {
        topics := make([]common.Hash, size)
        stack := scope.Stack
        mStart, mSize := stack.pop(), stack.pop()
        for i := 0; i < size; i++ {
            addr := stack.pop()
            topics[i] = addr.Bytes32()
        }

        d := scope.Memory.GetCopy(int64(mStart.Uint64()), int64(mSize.Uint64()))
        interpreter.evm.StateDB.AddLog(&types.Log{
            Address: scope.Contract.Address(),
            Topics:  topics,
            Data:    d,
            // This is a non-consensus field, but assigned here because
            // core/state doesn't know the current block number.
            BlockNumber: interpreter.evm.Context.BlockNumber.Uint64(),
        })

        return nil, nil
    }
}

公式 (25)

O_{\mathrm{a}} \in \mathbb{B}_{20} \quad \wedge \quad \forall x \in O_{\mathbf{t}}: x \in \mathbb{B}_{32} \quad \wedge \quad O_{\mathbf{d}} \in \mathbb{B}

公式 (26)

M 函数

• 定义
  • 计算一条日志 O 的摘要函数
• 输入
  • {x \in \{O_{\mathrm{a}}\} \cup O_{\mathbf{t}}}
    • 取并集
      • 日志地址 O_{\mathrm{a}}
        • 转成集合 \{O_{\mathrm{a}}\}
      • 一系列日志主题
        • {O_{\mathrm{t}}}
• 输出
  • 256字节的哈希

M(O) \quad\equiv\quad {\bigvee}_{x \in \{O_{\mathrm{a}}\} \cup O_{\mathbf{t}}} \big( M_{3:2048}(x) \big)

理解如下

M_{3:2048} 是个大小为256字节，共2048位的 Bloom 过滤器

• 对于输入数据，计算它的 Keccak-256 哈希值
• 取哈希值的前6个字节，两两组成一对
  • 一对字节有16个比特
  • 一共有3对
• 遍历这3对字节
  • 取低11位，得到索引，则索引范围是 [0, 2047](2^11 == 2048)
  • 设置 Bloom 过滤器对应索引的位为1
• 因此
  • 对于输入数据，会设置过滤器的随机3位

公式 (27) (28) (29) (30)

\begin{aligned}
M_{3:2048}(\mathbf{x}: \mathbf{x} \in \mathbb{B}) & \quad\equiv\quad \mathbf{y}: \mathbf{y} \in \mathbb{B}_{256} \quad \text{where:} \\
\mathbf{y} & \quad=\quad (0, 0, ..., 0) \quad \text{except:} \\
\forall i \in \{0, 2, 4\} & \quad:\quad \mathcal{B}_{m(\mathbf{x}, i)}(\mathbf{y}) = 1 \\
m(\mathbf{x}, i) & \quad\equiv\quad \mathtt{KEC}(\mathbf{x})[i, i + 1] \bmod 2048
\end{aligned}

其中

• \mathcal{B} 表示位引用函数
• \mathcal{B}_{\mathrm{j}}(\mathbf{x}) = 1 表示设置字节数组 \mathbf{x} 中的第 j 位(从0开始) 为1

如果仅看黄皮书中关于几个 LOG$ 的 opcode 说明，会误以为过滤器仅包含日志，容易对使用场景产生困惑。实际上，在 go-ethereum 实现中，会把产生日志的合约地址 log.Address 也记录在过滤器

// github.com/ethereum/go-ethereum@v1.10.6/core/types/bloom9.go

// CreateBloom creates a bloom filter out of the give Receipts (+Logs)
func CreateBloom(receipts Receipts) Bloom {
    buf := make([]byte, 6)
    var bin Bloom
    for _, receipt := range receipts {
        for _, log := range receipt.Logs {
            bin.add(log.Address.Bytes(), buf)
            for _, b := range log.Topics {
                bin.add(b[:], buf)
            }
        }
    }
    return bin
}

4.3.2 Holistic Validity 整体有效性

公式 (31)

\begin{aligned}
H_{\mathrm{r}} & \quad\equiv\quad \mathtt{TRIE}(L_S(\Pi(\boldsymbol{\sigma}, B))) & \quad\quad\wedge \\
H_{\mathrm{o}} & \quad\equiv\quad \mathtt{KEC}(\mathtt{RLP}(L_H^*(B_{\mathbf{U}}))) & \quad\quad\wedge \\
H_{\mathrm{t}} & \quad\equiv\quad \mathtt{TRIE}(\{\forall i < \lVert B_{\mathbf{T}} \rVert, i \in \mathbb{N}: p (i, L_{\mathrm{T}}(B_{\mathbf{T}}[i]))\}) & \quad\quad\wedge \\
H_{\mathrm{e}} & \quad\equiv\quad \mathtt{TRIE}(\{\forall i < \lVert B_{\mathbf{R}} \rVert, i \in \mathbb{N}: p(i, B_{\mathbf{R}}[i])\}) & \quad\quad\wedge \\
H_{\mathrm{b}} & \quad\equiv\quad {\bigvee}_{\mathbf{r} \in B_{\mathbf{R}}} \big( \mathbf{r}_{\mathrm{b}} \big)
\end{aligned}

其中

• H_{\mathrm{r}}
  • storageRoot
• H_{\mathrm{o}}
  • ommersHash
• H_{\mathrm{t}}
  • transactionsRoot
• H_{\mathrm{e}}
  • receiptsRoot
• H_{\mathrm{b}}
  • logsBloom

其中 公式 (32)

p(k, v) \quad\equiv\quad \big( \mathtt{RLP}(k), \mathtt{RLP}(v) \big)

而且 公式 (33)

\mathtt{TRIE}(L_{\mathrm{S}}(\boldsymbol{\sigma})) \quad=\quad {P(B_H)_H}_{\mathrm{r}}

其中

• P(B_H)
  • 表示区块 B 的父区块
• \Pi(\boldsymbol{\sigma}, B))
  • 参考公式 (4)
  • 参考公式 (177)
• L_S
  • 世界状态坍塌函数
  • 参考公式 (10)
• L_{\mathrm{H}}^*
  • 参考公式 (34)和(36))
• L_{\mathrm{T}}
  • 参考公式 (16)

4.3.3 Serialization 序列化

公式 (34) 定义 H 的序列化函数 L_{\mathrm{H}} 如下

L_{\mathrm{H}}(H) \quad\equiv\quad (H_{\mathrm{p}}, H_{\mathrm{o}}, H_{\mathrm{c}}, H_{\mathrm{r}}, H_{\mathrm{t}}, H_{\mathrm{e}}, H_{\mathrm{b}}, H_{\mathrm{d}}, H_{\mathrm{i}}, H_{\mathrm{l}}, H_{\mathrm{g}}, H_{\mathrm{s}}, H_{\mathrm{x}}, H_{\mathrm{m}}, H_{\mathrm{n}} \; )

公式 (35) 则 B 的序列化函数 L_{\mathrm{B}} 为

L_{\mathrm{B}}(B) \quad\equiv\quad \big( L_{\mathrm{H}}(B_{\mathrm{H}}), L_{\mathrm{T}}^*(B_{\mathbf{T}}), L_{\mathrm{H}}^*({B_{\mathbf{U}}}) \big)

公式 (36)

其中

• L_{\mathrm{T}} 参考公式 (16)
• L_{\mathrm{H}} 参考公式 (34)

L_{\mathrm{T}}^* 和 L_{\mathrm{H}}^* 分别是它们的 reduce 函数

reduce 函数定义如下: 对集合中的每一个元素，分别执行指定函数，得到的结果组成一个集合

{f^*}\big( (x_0, x_1, ...) \big) \quad\equiv\quad \big( f(x_0), f(x_1), ... \big) \quad \text{for any function} \; f

公式 (37) 值域/约束

\begin{aligned}
& {H_{\mathrm{p}}} \in \mathbb{B}_{32} & \quad\wedge\quad & H_{\mathrm{o}} \in \mathbb{B}_{32} & \quad\wedge\quad & H_{\mathrm{c}} \in \mathbb{B}_{20} & \quad\wedge\quad \\
& {H_{\mathrm{r}}} \in \mathbb{B}_{32} & \quad\wedge\quad & H_{\mathrm{t}} \in \mathbb{B}_{32} & \quad\wedge\quad & {H_{\mathrm{e}}} \in \mathbb{B}_{32} & \quad\wedge\quad \\
& {H_{\mathrm{b}}} \in \mathbb{B}_{256} & \quad\wedge\quad & H_{\mathrm{d}} \in \mathbb{N} & \quad\wedge\quad & {H_{\mathrm{i}}} \in \mathbb{N} & \quad\wedge\quad \\
& {H_{\mathrm{l}}} \in \mathbb{N} & \quad\wedge\quad & H_{\mathrm{g}} \in \mathbb{N} & \quad\wedge\quad & {H_{\mathrm{s}}} \in \mathbb{N}_{256} & \quad\wedge\quad \\
& {H_{\mathrm{x}}} \in \mathbb{B} & \quad\wedge\quad & H_{\mathrm{m}} \in \mathbb{B}_{32} & \quad\wedge\quad & {H_{\mathrm{n}}} \in \mathbb{B}_{8}
\end{aligned}

公式 (38)

\mathbb{B}_{\mathrm{n}} = \{ B: B \in \mathbb{B} \wedge \lVert B \rVert = n \}

4.3.4 Block Header Validity 区块头验证

公式 (39) 根据区块头 H 找到其父区块

P(H) \equiv B': \mathtt{KEC}(\mathtt{RLP}(B'_{\mathrm{H}})) = H_{\mathrm{p}}

公式 (40) 区块头 H 中的区块编号(block number)计算方式为

H_{\mathrm{i}} \equiv {{P(H)_{\mathrm{H}}}_{\mathrm{i}}} + 1

公式 (41) 根据区块头 H 计算权威难度值的公式

D(H) \equiv \begin{dcases}
{D_0} & \text{if} \quad H_{\mathrm{i}} = 0\\
\text{max}\!\left({D_0}, {P(H)_{\mathrm{H}}}_{\mathrm{d}} + x\times\varsigma_2 + \epsilon \right) & \text{otherwise}\\
\end{dcases}

其中

• {P(H)_{\mathrm{H}}}_{\mathrm{d}}
  • 以父块难度作为难度调整基数
• x\times\varsigma_2
  • 用于自适应难度调整，维持稳定的出块速度
• \epsilon
  • 表示设定的难度炸弹

--

注意两个函数，黄皮书与具体实现存在出入，主要是在 \epsilon 的处理上与公式 (41) 不同，实现为

D(H) \equiv \begin{dcases}
{D_0} & \text{if} \quad H_{\mathrm{i}} = 0\\
\text{max}\!\left({D_0}, {P(H)_{\mathrm{H}}}_{\mathrm{d}} + x\times\varsigma_2 \right) + \epsilon & \text{otherwise}\\
\end{dcases}

// github.com/ethereum/go-ethereum@v1.10.6/consensus/ethash/consensus.go
func makeDifficultyCalculator(bombDelay *big.Int) func(time uint64, parent *types.Header) *big.Int;

// github.com/ethereum/go-ethereum@v1.10.6/consensus/ethash/difficulty.go
func MakeDifficultyCalculatorU256(bombDelay *big.Int) func(time uint64, parent *types.Header) *big.Int;

公式 (42) 创世区块的难度值

{D_0} \equiv 131072

$2^{17} = 131072$

公式 (43) 难度值调整的单位

x \equiv \left\lfloor\frac{{P(H)_{\mathrm{H}}}_{\mathrm{d}}}{2048}\right\rfloor

公式 (44) 难度值调整的系数

\varsigma_2 \equiv \text{max}\left(y - \left\lfloor\frac{H_{\mathrm{s}} - {P(H)_{\mathrm{H}}}_{\mathrm{s}}}{9}\right\rfloor, -99 \right)

y \equiv \begin{cases}
1 & \text{if} \, \lVert P(H)_{\mathbf{U}}\rVert = 0 \\
2 & \text{otherwise}
\end{cases}

其中

• y
  • 如果父区块中包含叔父块，则难度调整会大一个单位 (从1调整为2)
  • 因为包含叔父块时发行的货币量大，需要适当提高难度以保持货币发行量稳定
• -99
  • 难度一次最多调整 -99 个单位
  • 主要是应对被黑客攻击或其他目前想不到的黑天鹅事件
• y - \left\lfloor\frac{H_{\mathrm{s}} - {P(H)_{\mathrm{H}}}_{\mathrm{s}}}{9}\right\rfloor
  • {H_{\mathrm{s}}}
    • 本区块的时间戳，以秒为单位
  • {P(H)_{\mathrm{H}}}_{\mathrm{s}}
    • 父区块的时间戳，以秒为单位
  • 规定
    • {H_{\mathrm{s}}} \gt {P(H)_{\mathrm{H}}}_{\mathrm{s}}
  • 自适应调整
    • 出块时间过短则调大难度
    • 出块时间过长则调小难度
  • 例子
    • 出块时间在 [1,8] 之间
      • 出块时间过短
      • 难度调大一个单位
    • 出块时间在 [9,17] 之间
      • 出块时间可以接受
      • 难度保持不便
    • 出块时间在 [18,26] 之间
      • 出块时间过长
      • 难度调小一个单位
    • ...

公式 (45) (46) (47) 难度炸弹

\epsilon \equiv \left\lfloor 2^{ \left\lfloor H'_{\mathrm{i}} \div 100000 \right\rfloor - 2 } \right\rfloor \\

其中

H'_{\mathrm{i}} \equiv \max(H_{\mathrm{i}} - \kappa, 0) \\

其中

\kappa \equiv \begin{cases}
  3000000 & \text{if} \quad F_{\mathrm{Byzantium}} \leqslant H_{\mathrm{i}} < F_{\mathrm{Constantinople}} \\
  5000000 & \text{if} \quad F_{\mathrm{Constantinople}} \leqslant H_{\mathrm{i}} < F_{\mathrm{Muir Glacier}} \\
  9000000 & \text{if} \quad H_{\mathrm{i}} \geqslant F_{\mathrm{Muir Glacier}} \\
\end{cases}

\begin{aligned}
F_{\mathrm{Homestead}} & \equiv 1150000 \\
F_{\mathrm{Byzantium}} & \equiv 4370000 \\
F_\mathrm{Constantinople} & \equiv 7280000 \\
F_{\mathrm{Muir Glacier}} & \equiv 9200000
\end{aligned}

为什么设置难度炸弹？

• 降低迁移到 PoS 协议时发生 fork 的风险
• 到时挖矿难度非常大，矿工将被迫迁移到 PoS 协议

参数

• \epsilon
  • 是2的指数函数，每十万个块扩大一倍
  • 后期增长非常快 ("炸弹")
• H'_{\mathrm{i}}
  • 低估了 PoS 协议的开发难度，导致一再延迟
  • 炸弹威力显现后，通过假区块号(回退区块号)来降低难度
    • 同时把区块奖励从5个 ETH 降为3个 ETH

参考 what-is-the-difficulty-bomb

公式 (48) gasLimit 约束

H_{\mathrm{l}} < {P(H)_{\mathrm{H}}}_{\mathrm{l}} + \left\lfloor\frac{{P(H)_{\mathrm{H}}}_{\mathrm{l}}}{1024}\right\rfloor \quad \wedge \\
H_{\mathrm{l}} > {P(H)_{\mathrm{H}}}_{\mathrm{l}} - \left\lfloor\frac{{P(H)_{\mathrm{H}}}_{\mathrm{l}}}{1024}\right\rfloor \quad \wedge \\
H_{\mathrm{l}} \geqslant 5000

公式 (49) timestamp 约束

H_{\mathrm{s}} > {P(H)_{\mathrm{H}}}_{\mathrm{s}}

公式 (41)难度计算公式的设计，保证了难度根据出块间隔长短的动态平衡

• 如果最近的两个区块间隔较短，则会导致难度值增加，因此需要额外的计算量，大概率会延长下个区块的出块时间
• 相反，如果最近的两个区块间隔过长，难度值和下一个区块的预期出块时间也会减少

公式 (50) nonce / mixHash 约束

必须同时满足

n \leqslant \frac {2^{256}}{H_{\mathrm{d}}} \quad \wedge \quad m = H_{\mathrm{m}} \\
with \quad (n, m) = \mathtt{PoW}(H_{\cancel{n}}, H_{\mathrm{n}}, \mathbf{d})

其中

• H_{\cancel{n}}
  • 当前区块 header H
  • 但不包含 nonce 和 mixHash components
• \mathbf{d}
  • 当前 DAG
  • 用于计算 mixHash H_{\mathrm{m}}
• \mathtt{PoW}
  • 工作量证明函数
  • 保证
    除了列举所有的可能性，没有更好的其他方法来找到一个低于要求阈值的 nonce
    攻击者必须拥有超过网络一半的算力，才能比其他人更快地找到 nonce

公式 (51)

综上所述，block header 的验证函数 V(H) 定义如下：

\begin{aligned}
V(H) \equiv\quad & n \leqslant \frac{2^{256}}{H_{\mathrm{d}}} \wedge m = H_{\mathrm{m}} \quad &\wedge \\
& H_{\mathrm{d}} = D(H) \quad &\wedge \\
& H_{\mathrm{g}} \le H_{\mathrm{l}}  \quad &\wedge \\
& H_{\mathrm{l}} < {P(H)_{\mathrm{H}}}_{\mathrm{l}} + \left\lfloor\frac{{P(H)_{\mathrm{H}}}_{\mathrm{l}}}{1024}\right\rfloor  \quad &\wedge \\
& H_{\mathrm{l}} > {P(H)_{\mathrm{H}}}_{\mathrm{l}} - \left\lfloor\frac{{P(H)_{\mathrm{H}}}_{\mathrm{l}}}{1024}\right\rfloor  \quad &\wedge \\
& H_{\mathrm{l}} \geqslant 5000  \quad &\wedge \\
& H_{\mathrm{s}} > {P(H)_{\mathrm{H}}}_{\mathrm{s}} \quad &\wedge \\
& H_{\mathrm{i}} = {P(H)_{\mathrm{H}}}_{\mathrm{i}} +1 \quad &\wedge \\
& \lVert H_{\mathrm{x}} \rVert \le 32 \\
where \quad & (n, m) = \mathtt{PoW}(H_{\cancel{n}}, H_{\mathrm{n}}, \mathbf{d})
\end{aligned}

此外，\textbf{extraData} 最多为32字节

5. Gas and Payment Gas 与支付

一般来说，用于支付交易的 gas 费用，会被发往 beneficiary 地址，这个地址由矿工设置

6. Transaction Execution 交易执行

\Upsilon 交易状态转换函数

\Upsilon 在执行前，检查如下条件:

1. 交易以 RLP 格式正确编码，且没有尾随多余的数据
2. 交易签名正确
3. nonce 有效(即等于交易发送者账户当前的 nonce)
4. gas limit 不小于 g_0 (计算公式参考(55) (56) (57))
5. 发送者账户 balance 不小于实际费用 v_0 (计算公式参考(58))

公式 (52) 交易状态转换函数

\boldsymbol{\sigma}' = \Upsilon(\boldsymbol{\sigma}, T)

其中

• \boldsymbol{\sigma}'
  • 交易完成后的世界状态
• \Upsilon^{\mathrm{g}}
  • 交易实际消耗的 gas
• \Upsilon^{\mathbf{l}}
  • 交易执行时产生的一系列日志
• \Upsilon^{\mathrm{z}}
  • 交易返回的状态码

6.1 Substrate 子状态

公式 (53) 交易执行过程中产生的子状态

A \equiv (A_{\mathbf{s}}, A_{\mathbf{l}}, A_{\mathbf{t}}, A_{\mathrm{r}})

其中

• A_{\mathbf{s}}
  • 自毁集合
    • 交易执行完成后会被销毁的账户
• A_{\mathbf{l}}
  • 一系列日志
    • 方便外界旁观者简单跟踪合约调用
• A_{\mathbf{t}}
  • 交易接触的账户
    • 其中的 EMPTY 账户会被删除
• A_{\mathbf{r}}
  • refund balance
    • 累计需要归还的 gas

公式 (54) 空的交易子状态

A^0 \equiv (\varnothing,(), \varnothing, 0)

6.2 Execution 执行

状态转换

• \boldsymbol{\sigma} 原始状态
• \boldsymbol{\sigma}_0 检查点状态
  • 发送者 balance 扣除 {T_g}{T_p}
  • 发送者 nonce 累加
• \boldsymbol{\sigma}_{\mathrm{P}} 执行交易后临时状态
  • \//
• \boldsymbol{\sigma}^* 预备最终状态
  • 剩余的 gas 返回给发送者
  • 消耗的 gas 发给 beneficiary(由打包区块的矿工指定)
• \boldsymbol{\sigma}' 最终状态
  • 删除自毁集合账户
  • 删除接触账户集合中的空账户

--

公式 (55) (56) (57) g_0 交易执行前预付的基础 gas

g_0 \equiv {}
\sum_{i \in T_{\mathbf{i}}, T_{\mathbf{d}}} \begin{cases} G_{\mathrm{txdatazero}} &\text{if} \quad i = 0 \\ G_{\mathrm{txdatanonzero}} &\text{otherwise} \end{cases}
\quad + \quad \begin{cases} G_{\mathrm{txcreate}} & \text{if} \quad T_{\mathrm{t}} = \varnothing \\ 0 & \text{otherwise} \end{cases}
\quad + \quad G_{\mathrm{transaction}}

其中

• T_{\mathbf{i}}
  • 合约创建的 initcode
• T_{\mathbf{d}}
  • 消息调用的 inputdata
• G_{\mathrm{txcreate}}
  • 如果是合约创建，需要计入成本

公式 (58) v_0 交易执行前预付的费用

v_0 \quad\equiv\quad T_{\mathrm{g}} T_{\mathrm{p}} + T_{\mathrm{v}}

公式 (59)

\begin{aligned}
S(T) & \quad\neq\quad \varnothing \quad \wedge \\
\boldsymbol{\sigma}[S(T)] & \quad\neq\quad \varnothing \quad \wedge \\
T_{\mathrm{n}} & \quad=\quad \boldsymbol{\sigma}[S(T)]_{\mathrm{n}} \quad \wedge \\
g_0 & \quad\leqslant\quad T_{\mathrm{g}} \quad \wedge \\
v_0 & \quad\leqslant\quad \boldsymbol{\sigma}[S(T)]_{\mathrm{b}} \quad \wedge \\
T_{\mathrm{g}} & \quad\leqslant\quad {B_{\mathrm{H}}}_{\mathrm{l}} - {\ell}(B_{\mathbf{R}})_{\mathrm{u}}
\end{aligned}

其中

• S(T)
  • 根据交易查找其发送者的函数
• T_{\mathrm{g}}
  • 交易的 gasLImit
• {\ell}(B_{\mathbf{R}})_{\mathrm{u}}
  • 当前区块累计已经消耗的 gas
• {B_{\mathrm{H}}}_{\mathrm{l}}
  • 当前区块的 gasLimit

公式 (60) (61) (62) 检查点状态 \boldsymbol{\sigma}_0

\begin{aligned}
\boldsymbol{\sigma}_0 & \quad\equiv\quad \boldsymbol{\sigma} \quad \text{except:} \\
\boldsymbol{\sigma}_0[S(T)]_{\mathrm{b}} & \quad\equiv\quad \boldsymbol{\sigma}[S(T)]_{\mathrm{b}} - T_{\mathrm{g}} T_{\mathrm{p}} \\
\boldsymbol{\sigma}_0[S(T)]_{\mathrm{n}} & \quad\equiv\quad \boldsymbol{\sigma}[S(T)]_{\mathrm{n}} + 1
\end{aligned}

检查点状态 \boldsymbol{\sigma}_0 预扣了 T_{\mathrm{g}} T_{\mathrm{p}}

系统会在交易执行成功后，将剩余 gas 返还发送者

--

注意 XXX

公式 (61) 计算检查点状态 balance 时，不是扣除 v_0，而是只扣了 T_{\mathrm{g}} T_{\mathrm{p}}，未扣除 T_{\mathrm{v}}

实际上，v 的处理，是在公式 (63) 执行交易时，在执行具体函数代码前，会从发送者 Transfer 到接收者

gas 与 value 分开处理，理解如下

• gas 本身与 value 语义本质量不同，不能混为一起
• 转账 value 的双方 balance 的改变应该是原子的，不应拆成前后两个上下文
• gas 一定是外部账户支付的，而 value 转账的扣款账户可以是外部账户，也可以是智能合约

// github.com/ethereum/go-ethereum@v1.10.6/core/vm/evm.go

// Call executes the contract associated with the addr with the given input as
// parameters. It also handles any necessary value transfer required and takes
// the necessary steps to create accounts and reverses the state in case of an
// execution error or failed value transfer.
func (evm *EVM) Call(caller ContractRef, addr common.Address, input []byte, gas uint64, value *big.Int) (ret []byte, leftOverGas uint64, err error) {
    evm.Context.Transfer(evm.StateDB, caller.Address(), addr, value)
    //...
}

公式 (63) 执行交易后临时状态 \boldsymbol{\sigma}_{\mathrm{P}}

(\boldsymbol{\sigma}_{\mathrm{P}}, g', A, z) \equiv \begin{cases}
\Lambda_{4}(\boldsymbol{\sigma}_0, S(T), T_{\mathrm{o}}, g, T_{\mathrm{p}}, T_{\mathrm{v}}, T_{\mathbf{i}}, 0, \varnothing, \top) & \text{if} \quad T_{\mathrm{t}} = \varnothing \\
\Theta_{4}(\boldsymbol{\sigma}_0, S(T), T_{\mathrm{o}}, T_{\mathrm{t}}, T_{\mathrm{t}}, g, T_{\mathrm{p}}, T_{\mathrm{v}}, T_{\mathrm{v}}, T_{\mathbf{d}}, 0, \top) & \text{otherwise}
\end{cases}

状态转换

• \boldsymbol{\sigma}_0 检查点状态
• \boldsymbol{\sigma}_{\mathrm{P}} 执行交易后临时状态
  操作
• 转换时需要区分交易类型
  • T_{\mathrm{t}} = \varnothing 未设置目标地址，说明是合约创建类型
  • 否则，是消息调用类型

其中

• \boldsymbol{\sigma}_{\mathrm{P}}
  • 交易执行后的临时状态
• g'
  • 剩余 gas
• A
  • 子状态
• z
  • 状态码
• T_{\mathrm{o}}
  • original transactor
  • 如果是 inner-transaction，则这里是智能合约的地址，而非 sender
• \Lambda_{4}
  • 合约创建
  • 参考 合约创建
• \Theta_{4}
  • 消息调用
  • 参考 消息调用
• \top
  • 数学符号，表示 bool 值
  • \Lambda_{4} 和 \Theta_{4} 的末尾参数
    • 含义：是否有权修改状态

--

关于 \top

// github.com/ethereum/go-ethereum@v1.10.6/core/vm/interpreter.go
func (in *EVMInterpreter) Run(contract *Contract, input []byte, readOnly bool) (ret []byte, err error) {
  // ...

  // Make sure the readOnly is only set if we aren't in readOnly yet.
  // This also makes sure that the readOnly flag isn't removed for child calls.
  if readOnly && !in.readOnly {
    in.readOnly = true
    defer func() { in.readOnly = false }()
  }

  // ...

  for {
    // ...

    op = contract.GetOp(pc)
    operation := in.cfg.JumpTable[op]
    // If the operation is valid, enforce write restrictions
    if in.readOnly && in.evm.chainRules.IsByzantium {
      // If the interpreter is operating in readonly mode, make sure no
      // state-modifying operation is performed. The 3rd stack item
      // for a call operation is the value. Transferring value from one
      // account to the others means the state is modified and should also
      // return with an error.
      if operation.writes || (op == CALL && stack.Back(2).Sign() != 0) {
        return nil, ErrWriteProtection
      }
    }

    // ...
  }
  return nil, nil
}

//

// github.com/ethereum/go-ethereum@v1.10.6/core/vm/evm.go

// StaticCall executes the contract associated with the addr with the given input
// as parameters while disallowing any modifications to the state during the call.
// Opcodes that attempt to perform such modifications will result in exceptions
// instead of performing the modifications.
func (evm *EVM) StaticCall(caller ContractRef, addr common.Address, input []byte, gas uint64) (ret []byte, leftOverGas uint64, err error) {
    // ...
    ret, err = evm.interpreter.Run(contract, input, true)
    // ...
}

func (evm *EVM) Call(caller ContractRef, addr common.Address, input []byte, gas uint64, value *big.Int) (ret []byte, leftOverGas uint64, err error) {
    // ...
    ret, err = evm.interpreter.Run(contract, input, false)
    // ...
}

func (evm *EVM) CallCode(caller ContractRef, addr common.Address, input []byte, gas uint64, value *big.Int) (ret []byte, leftOverGas uint64, err error) {
    // ...
    ret, err = evm.interpreter.Run(contract, input, false)
    // ...
}

func (evm *EVM) DelegateCall(caller ContractRef, addr common.Address, input []byte, gas uint64) (ret []byte, leftOverGas uint64, err error) {
    // ...
    ret, err = evm.interpreter.Run(contract, input, false)
    // ...
}

func (evm *EVM) create(caller ContractRef, codeAndHash *codeAndHash, gas uint64, value *big.Int, address common.Address) ([]byte, common.Address, uint64, error) {
    // ...
    ret, err = evm.interpreter.Run(contract, nil, false)
    // ...
}

--

公式 (64) 执行时最多能消耗的 gas

g \quad\equiv\quad T_{\mathrm{g}} - g_0

公式 (65) 交易执行后 refund 计数器的变化

A'_{\mathrm{r}} \quad\equiv\quad A_{\mathrm{r}} + \sum_{i \in A_{\mathbf{s}}} R_{\mathrm{selfdestruct}}

公式 (66) 交易执行后剩余的 gas

g^* \quad\equiv\quad g' + \min \left\{ \Big\lfloor \dfrac{T_{\mathrm{g}} - g'}{2} \Big\rfloor, {A'_{\mathrm{r}}} \right\}

其中

• g'
  • 交易执行后最终剩余的 gas
• T_{\mathrm{g}} - g'
  • 交易实际消耗的 gas
• g^*
  • 交易执行后最终需要返还的 gas

公式 (67) (68) (69) (70) 预备最终状态 \boldsymbol{\sigma}^*

\begin{aligned}
\boldsymbol{\sigma}^* & \quad\equiv\quad \boldsymbol{\sigma}_{\mathrm{P}} \quad \text{except} \\
\boldsymbol{\sigma}^*[S(T)]_{\mathrm{b}} & \quad\equiv\quad \boldsymbol{\sigma}_{\mathrm{P}}[S(T)]_{\mathrm{b}} + g^* T_{\mathrm{p}} \\
\boldsymbol{\sigma}^*[m]_{\mathrm{b}} & \quad\equiv\quad \boldsymbol{\sigma}_{\mathrm{P}}[m]_{\mathrm{b}} + (T_{\mathrm{g}} - g^*) T_{\mathrm{p}} \\
m & \quad\equiv\quad {B_{\mathrm{H}}}_{\mathrm{c}}
\end{aligned}

状态转换

• \boldsymbol{\sigma}_{\mathrm{P}} 执行交易后临时状态
• \boldsymbol{\sigma}^* 预备最终状态
  操作
• 剩余的 gas 返回给发送者
• 消耗的 gas 发给 {B_{\mathrm{H}}}_{\mathrm{c}} (beneficiary)

公式 (71) (72) (73) 最终状态 \boldsymbol{\sigma}'

\begin{aligned}
\boldsymbol{\sigma}' & \quad\equiv\quad \boldsymbol{\sigma}^* \quad \text{except} \\
\forall i \in A_{\mathbf{s}}: \boldsymbol{\sigma}'[i] & \quad=\quad \varnothing \\
\forall i \in A_{\mathbf{t}}: \boldsymbol{\sigma}'[i] & \quad=\quad \varnothing \quad\text{if}\quad \mathtt{DEAD}(\boldsymbol{\sigma}^*\kern -2pt, i)
\end{aligned}

状态转换

• \boldsymbol{\sigma}^* 预备最终状态
• \boldsymbol{\sigma}' 最终状态
  操作
• 删除自毁集合账户
• 删除接触账户集合中的空账户

公式 (74) (75) (76)

\begin{aligned}
\Upsilon^{\mathrm{g}}(\boldsymbol{\sigma}, T) & \quad\equiv\quad T_{\mathrm{g}} - g^* \\
\Upsilon^{\mathbf{l}}(\boldsymbol{\sigma}, T) & \quad\equiv\quad {A_{\mathbf{l}}} \\
\Upsilon^{\mathrm{z}}(\boldsymbol{\sigma}, T) & \quad\equiv\quad z
\end{aligned}

其中

• \Upsilon^{\mathrm{g}}
  • 交易一共消耗的 gas
• \Upsilon^\mathbf{l}
  • 交易生成的一系列日志
• \Upsilon^{\mathrm{z}}
  • 交易执行返回的状态码

7. Contract Creation 合约创建

两个步骤

• 合约创建
• 合约初始化
  • 调用 \mathbf{i}

公式 (77) 盐

\zeta \in \mathbb{B}_{32} \cup \mathbb{B}_{0}

如果是通过 \small{CREATE2} 创建合约，则 \zeta \neq \varnothing

公式 (78) 合约创建函数 \Lambda

(\boldsymbol{\sigma}', g', A, z, \mathbf{o}) \equiv \Lambda(\boldsymbol{\sigma}, s, o, g, p, v, \mathbf{i}, e, \zeta, w)

函数参数

• \boldsymbol{\sigma}
  • 世界状态
• s
  • 发送者 sender
• o
  • 调用者 original transactor
• g
  • available gas
• p
  • gas price
• v
  • 捐献: endowment
• \mathbf{i}
  • 用于初始化合约的 EVM 代码(二进制字符串)
• e
  • 当前消息调用/合约创建堆栈的深度
• \zeta
  • 用于计算新合约地址的盐
  • 可能不存在: \zeta = \varnothing
• w
  • 是否有权改变状态
  • 参考公式 (63)

函数输出

• \boldsymbol{\sigma}'
  • 世界状态'
• g'
  • 剩余 gas
• A
  • 子状态
  • 参考 #6.1 Substrate
• \mathbf{o}
  • 执行结果
    • 对于合约创建而言，成功的话这里得到的是合约的 body code
  • 参考公式 (145)

公式 (79) (80) (81) 新创建合约的地址 a

\begin{aligned}
a & \equiv \mathtt{ADDR}(s, \boldsymbol{\sigma}[s]_{\mathrm{n}} - 1, \zeta, \mathbf{i}) \\
\mathtt{ADDR}(s, n, \zeta, \mathbf{i}) & \equiv \mathcal{B}_{96..255}\Big(\mathtt{KEC}\big( L_{\mathrm{A}}(s, n, \zeta, \mathbf{i})\big) \Big) \\
L_{\mathrm{A}}(s, n, \zeta, \mathbf{i}) & \equiv \begin{cases}
\mathtt{RLP}\big(\;(s, n)\;\big) & \text{if}\ \zeta = \varnothing \\
(255) \cdot s \cdot \zeta \cdot \mathtt{KEC}(\mathbf{i}) & \text{otherwise}
\end{cases}
\end{aligned}

其中

• L_{\mathrm{A}}
  • 判断合约创建方式是否为 \small{CREATE2}
• \cdot
  • 拼接字节数组
• \mathcal{B}_{a..b}(X)
  • 取二进制字节数组的第 [a, b] 位
• \boldsymbol{\sigma}[x]
  • 地址 x 的世界状态
  • 不存在，则为 \varnothing

注意

• 公式(79) 中，传给合约地址计算函数 \Lambda 的参数 nonce，值是 \boldsymbol{\sigma}[s]_{\mathrm{n}} - 1
• 理解: 在调用合约创建之前，系统已经把发送者的 nonce 加一

公式 (82) (83) (84) (85) 合约创建后的世界状态 \boldsymbol{\sigma}^*

\begin{aligned}
\boldsymbol{\sigma}^* & \quad\equiv\quad \boldsymbol{\sigma} \quad \text{except:} \\
\boldsymbol{\sigma}^*[a] & \quad=\quad \big( 1, v + v', \mathtt{TRIE}(\varnothing), \mathtt{KEC}\big(()\big) \big) \\
\boldsymbol{\sigma}^*[s] & \quad=\quad \begin{cases}
\varnothing & \text{if}\ \boldsymbol{\sigma}[s] = \varnothing \ \wedge\ v = 0 \\
\mathbf{a}^* & \text{otherwise}
\end{cases} \\
\mathbf{a}^* & \quad\equiv\quad (\boldsymbol{\sigma}[s]_{\mathrm{n}}, \boldsymbol{\sigma}[s]_{\mathrm{b}} - v, \boldsymbol{\sigma}[s]_{\mathbf{s}}, \boldsymbol{\sigma}[s]_{\mathrm{c}})
\end{aligned}

公式 (86) v' 合约地址在交易前就有的余额

v' \equiv \begin{cases}
0 & \text{if} \quad \boldsymbol{\sigma}[a] = \varnothing\\
\boldsymbol{\sigma}[a]_{\mathrm{b}} & \text{otherwise}
\end{cases}

到这里，新创建合约的地址的状态已经设置好了(公式(83))

公式 (87) 调用 \Xi 函数执行代码 \mathbf{i} 来初始化合约

(\boldsymbol{\sigma}^{**}, g^{**}, A, \mathbf{o}) \quad\equiv\quad \Xi(\boldsymbol{\sigma}^*, g, I, \{s, a\}) \\

\Xi 函数的输出

• \boldsymbol{\sigma}^{**}
  • 合约初始化后的世界状态
• g^{**}
  • 剩余的可用 gas
• A
  • 累积的子状态
• \mathbf{o}
  • 新创建合约的 body code
  • 由合约初始化 \mathbf{i} 代码得到

公式 (88) (89) (90) (91) (92) (93) (94) (95) (96) 合约初始化后的世界状态 \boldsymbol{\sigma}^*

I 作为 \Xi 函数的输入参数

• 表示 执行环境的一系列变量
• 参考 #9.3 Execution Environment

\begin{aligned}
I_{\mathrm{a}} & \quad\equiv\quad a \\
I_{\mathrm{o}} & \quad\equiv\quad o \\
I_{\mathrm{p}} & \quad\equiv\quad p \\
I_{\mathbf{d}} & \quad\equiv\quad () \\
I_{\mathrm{s}} & \quad\equiv\quad s \\
I_{\mathrm{v}} & \quad\equiv\quad v \\
I_{\mathbf{b}} & \quad\equiv\quad \mathbf{i} \\
I_{\mathrm{e}} & \quad\equiv\quad e \\
I_{\mathrm{w}} & \quad\equiv\quad w
\end{aligned}

• I_{\mathrm{a}}
  • 新创建合约的地址
• I_{\mathrm{o}}
  • 调用者 original transactor
• I_{\mathrm{p}}
  • gas Price
• I_{\mathbf{d}}
  • input data
  • 在这里为空，因为对于这个初始化调用而言没有 input
• I_{\mathrm{s}}
  • 发送者 sender
• I_{\mathrm{v}}
  • 捐献: endowment
• I_{\mathbf{b}}
  • 用于初始化合约的 EVM 代码(二进制字符串)
• I_{\mathrm{e}}
  • 当前消息调用/合约创建堆栈的深度
• I_{\mathrm{w}}
  • 是否有权修改状态
  • 参考公式 (63)

公式 (97) 合约初始化需要支付的 gas

c \quad\equiv\quad G_{\mathrm{codedeposit}} \times \lVert \mathbf{o} \rVert

• 出现异常
  • 初始化代码执行过程的异常
    • 例子
      • 因可用 gas g^{**} 不够而导致 Out-Of-Gas 异常
  • 成功初始化后可用 gas 不够支付 c
    • g^{**} < c
    • 也会导致 Out-of-Gas
  • 其他场景
    • 例子 TODO
• 导致
  • 最终剩余 gas g‘ 为0
  • 使初始化提前终止
  • 合约初始化后的世界状态 \boldsymbol{\sigma}^{**} 为空，即 \varnothing
  • 最终状态与合约创建前一致

公式 (98) (99) (100) (101) 最终状态 \boldsymbol{\sigma}'

\begin{aligned}
\quad g' \quad\equiv\quad & \begin{cases}
0 & \text{if} \quad F \\
g^{**} - c & \text{otherwise} \\
\end{cases} \\
\quad \boldsymbol{\sigma}' \quad\equiv\quad & \begin{cases}
\boldsymbol{\sigma} & \text{if} \quad F \ \lor\ \boldsymbol{\sigma}^{**} = \varnothing \\
\boldsymbol{\sigma}^{**} \quad \text{except:} & \\
\quad\boldsymbol{\sigma}'[a] = \varnothing & \text{if} \quad \mathtt{DEAD}(\boldsymbol{\sigma}^{**}, a) \\
\boldsymbol{\sigma}^{**} \quad \text{except:} & \\
\quad\boldsymbol{\sigma}'[a]_{\mathrm{c}} = \texttt{KEC}(\mathbf{o}) & \text{otherwise}
\end{cases} \\
\quad z \quad\equiv\quad & \begin{cases}
0 & \text{if} \quad F \ \lor\ \boldsymbol{\sigma}^{**} = \varnothing \\
1 & \text{otherwise}
\end{cases} \\
\text{where} \\
F \quad\equiv\quad  & \big( \boldsymbol{\sigma}[a] \neq \varnothing \ \wedge\ \big(\boldsymbol{\sigma}[a]_c \neq \texttt{\small KEC}\big(()\big) \vee \boldsymbol{\sigma}[a]_n \neq 0 \big) \big) \quad \vee \\
&(\boldsymbol{\sigma}^{**} = \varnothing \ \wedge\ \mathbf{o} = \varnothing) \quad \vee \\
&g^{**} < c \quad \vee \\
&\lVert \mathbf{o} \rVert > 24576
\end{aligned}

其中

• g'
  • 最终剩余的 gas，需要返还给最初交易发起者
• \big( \boldsymbol{\sigma}[a] \neq \varnothing \ \wedge\ \big(\boldsymbol{\sigma}[a]_c \neq \texttt{\small KEC}\big(()\big) \vee \boldsymbol{\sigma}[a]_n \neq 0 \big) \big)
  • 目标地址已存在，且有 codeHash 或 nonce 不为0
• \mathbf{o}
  • 新创建合约的 body code
  • 由合约初始化 \mathbf{i} 代码得到
• \boldsymbol{\sigma}'[a]_{\mathrm{c}} = \texttt{KEC}(\mathbf{o})
  • 保存新建合约的 body code 的 hash 到 \boldsymbol{\sigma}'[a]_{\mathrm{c}}

• \boldsymbol{\sigma}^{**} = \varnothing \ \wedge\ \mathbf{o} = \varnothing

  • 含义
    • 执行 \mathbf{i} 后得到的字节码，即合约代码 \mathbf{o} 为空

  • 失败例子 Ropsten

    • \text{\small SELFDESTRUCT}
      • 结论
        • 根据执行结果，剩余 gas 有返还，所以不属于 F
      • 代码

    pragma solidity >=0.7.0 <0.9.0;
    contract Storage {
      constructor(address user) payable {
          address payable u = payable(address(user));
          selfdestruct(u);
      }
    }

    • 交易
      • 0xf06eb45dd26ec1f5a7b6e876ddf2253b0716bf50b17185f8a796d6b247d7e5d1
      • 执行细节
        • From 0xcf60d818200f23499ef4c88437e83da7a6d85ac7
        • To [Contract 0x8CAE6369489542352335f97465Ba95EBB1a2fCaF Created]
          • TRANSFER 0.01 Ether From 0x8CAE6369489542352335f97465Ba95EBB1a2fCaF To 0x6352e8a946050224b6fd9575497391af76f74a89
          • SELF DESTRUCT Contract 0x8CAE6369489542352335f97465Ba95EBB1a2fCaF
        • Value 0.01 Ether ($0.00)
        • Gas Limit 300,000
        • Gas Used by Transaction 64,402 (21.47%)
    • 合约
      • 0x8CAE6369489542352335f97465Ba95EBB1a2fCaF
        • balance: 0
        • nonce: 0
        • code: 0x

结论

• 要么带着初始捐款(endowment)成功创建合约

• 要么不会创建任何合约且不会进行转账

• REVERT

  • 参考
    • What are the Reasons for Failed Transactions?
    • Solidity Learning: Revert(), Assert(), and Require() in Solidity, and the New REVERT Opcode in the EVM
  • 注释

  // github.com/ethereum/go-ethereum@v1.10.6/core/vm/interpreter.go
  
  // It's important to note that any errors returned by the interpreter should be
  // considered a revert-and-consume-all-gas operation except for
  // ErrExecutionReverted which means revert-and-keep-gas-left.
  func (in *EVMInterpreter) Run(contract *Contract, input []byte, readOnly bool) (ret []byte, err error) {
    // ...
  }

  • 测试

    • 结论
      • 不满足 F，因此 g' = g^{**} - c
        • 剩余 gas 和 value 会被归还
      • 满足 \mathtt{DEAD}(\boldsymbol{\sigma}^{**}, a)，因此 \boldsymbol{\sigma}'[a] = \varnothing
        • 其余状态不变
    • 证明
      • 代码 (assert 和 require 都测试过，都返还了 gas，跟参考文章结论不一样)

    pragma solidity >=0.7.0 <0.9.0;
    contract Storage {
      uint256 number;
      constructor(address user, uint256 num) payable {
          require (msg.sender == user);
          number = num;
      }
    }

    • 部署
      • 发起部署的地址与构造函数的地址不同，使 require/assert 失败

    • 例子 Ropsten

      • 成功创建了合约，但初始化时 REVERTED
        • 交易
          • require
            • 0xb407a7fa764ac8ddcd556c5185357b328af8b7070babd282a49af606ea1d98ad
            • 执行细节
              • From 0xcf60d818200f23499ef4c88437e83da7a6d85ac7
              • To [Contract 0xdc1646faae75131d84b0d1213bb2bb6927d2eba5 Created]
                • Warning! Error encountered during contract execution [Reverted]
              • Value 0.01 Ether ($0.00) - [CANCELLED]
              • Gas Limit 3,000,000
            • 合约
              • 0xDC1646fAAe75131D84B0d1213Bb2BB6927D2eba5
                • balance: 0
                • nonce: 0
                • code: 0x
          • assert
            • 0x453066a33244bcf4b130e741a68032f14b536013505e0712cb99e68963e948a5
            • 合约
              • 0xE34B1dB1cbBe6ea36952076b1578995Fe85A7061
                • balance: 0
                • nonce: 0
                • code: 0x
        • 根据公式(14)，新创建的合约是个 EMPTY 账户

          const targetContract = '0xbd83EF1a5A45b54d94895C1897aF2d00154520D5';
      
          const balance = await web3.eth.getBalance(targetContract);
          const nonce = await web3.eth.getTransactionCount(targetContract);
          const code = await web3.eth.getCode(targetContract);
      
          console.log(balance: ${balance});
          console.log(nonce: ${nonce});
          console.log(code: ${code});
      
          // storageRoot
          //  无法从 web3 直接获得
          //  参考 https://github.com/medvedev1088/ethereum-merkle-patricia-trie-example

8. Message Call 消息调用 (internal Transaction)

公式 (102) 消息调用函数 \Theta

(\boldsymbol{\sigma}', g', A, z, \mathbf{o}) \equiv {\Theta}(\boldsymbol{\sigma}, s, o, r, c, g, p, v, \tilde{v}, \mathbf{d}, e, w)

函数参数

• \boldsymbol{\sigma}
  • 世界状态
• s
  • 发送者 sender
• o
  • 调用者 original transactor
• r
  • 接收者 recipient
• c
  • 消息调用执行在哪个地址上的代码，通常等于 r
  • 参考 Appendix H2. Instruction Set 的 {\small CALL}, {\small CALLCODE}
• g
  • available gas
• p
  • gas price
• v
  • 捐献: endowment
• \mathbf{d}
  • 消息调用的 input data (二进制字符串)
• e
  • 当前消息调用/合约创建堆栈的深度
• w
  • 是否有权改变状态
  • 参考公式 (63)

函数输出

• \boldsymbol{\sigma}'
  • 世界状态'
• g'
  • 剩余 gas
• A
  • 子状态
  • 参考 #6.1 Substrate
• z
  • status code
• \mathbf{o}
  • output data
  • 参考公式 (145)

注意区分

• v
  • msg.value
• \tilde{v}
  • {\small DELEGATECALL} 指令上下文的中的 value

公式 (103) 临时状态 \boldsymbol{\sigma}_1

\begin{aligned}
&\boldsymbol{\sigma}_1[r]_{\mathrm{b}} \equiv \boldsymbol{\sigma}[r]_{\mathrm{b}} + v \quad\wedge\quad \boldsymbol{\sigma}_1[s]_{\mathrm{b}} \equiv \boldsymbol{\sigma}[s]_{\mathrm{b}} - v \\
& unless s = r
\end{aligned}

意味着

公式 (104) (105) (106) (107) (108) (109) 状态转换 \boldsymbol{\sigma} -> \boldsymbol{\sigma}_1' -> \boldsymbol{\sigma}_1

%\boxed{%
\boldsymbol{\sigma}_1 \equiv \boldsymbol{\sigma}_1' \quad \text{except:}
%}%

\boldsymbol{\sigma}_1[s] \equiv \begin{cases}
\varnothing & \text{if}\ \boldsymbol{\sigma}_1'[s] = \varnothing \ \wedge\ v = 0 \\
\mathbf{a}_1 &\text{otherwise} \\
\end{cases} \\

\mathbf{a}_1 \equiv \left(\boldsymbol{\sigma}_1'[s]_{\mathrm{n}}, \boldsymbol{\sigma}_1'[s]_{\mathrm{b}} - v, \boldsymbol{\sigma}_1'[s]_{\mathbf{s}}, \boldsymbol{\sigma}_1'[s]_{\mathrm{c}}\right)

\text{and}\quad \boldsymbol{\sigma}_1' \equiv \boldsymbol{\sigma} \quad \text{except:}

\begin{cases}
\boldsymbol{\sigma}_1'[r] \equiv (0, v, \mathtt{TRIE}(\varnothing), \mathtt{KEC}(())) & \text{if} \quad \boldsymbol{\sigma}[r] = \varnothing \wedge v \neq 0 \\
\boldsymbol{\sigma}_1'[r] \equiv \varnothing & \text{if}\quad \boldsymbol{\sigma}[r] = \varnothing \wedge v = 0 \\
\boldsymbol{\sigma}_1'[r] \equiv \mathbf{a}_1' & \text{otherwise}
\end{cases}

\mathbf{a}_1' \equiv (\boldsymbol{\sigma}[r]_{\mathrm{n}}, \boldsymbol{\sigma}[r]_{\mathrm{b}} + v, \boldsymbol{\sigma}[r]_{\mathbf{s}}, \boldsymbol{\sigma}[r]_{\mathrm{c}})

执行过程参考 #9 Execution Model

公式 (110) (111) ... (123) 最终状态 \boldsymbol{\sigma}'

\begin{aligned}
\boldsymbol{\sigma}' & \quad\equiv\quad \begin{cases}
\boldsymbol{\sigma} & \text{if} \quad \boldsymbol{\sigma}^{**} = \varnothing \\
\boldsymbol{\sigma}^{**} & \text{otherwise}
\end{cases} \\
g' & \quad\equiv\quad \begin{cases}
0 & \text{if} \quad \boldsymbol{\sigma}^{**} = \varnothing \ \wedge \mathbf{o} = \varnothing \\
g^{**} & \text{otherwise}
\end{cases} \\
z & \quad\equiv\quad \begin{cases}
0 & \text{if} \quad \boldsymbol{\sigma}^{**} = \varnothing \\
1 & \text{otherwise}
\end{cases} \\
(\boldsymbol{\sigma}^{**}, g^{**},A, \mathbf{o}) & \quad\equiv\quad \Xi\\
I_{\mathrm{a}} & \quad\equiv\quad r \\
I_{\mathrm{o}} & \quad\equiv\quad o \\
I_{\mathrm{p}} & \quad\equiv\quad p \\
I_{\mathbf{d}} & \quad\equiv\quad \mathbf{d} \\
I_{\mathrm{s}} & \quad\equiv\quad s \\
I_{\mathrm{v}} & \quad\equiv\quad \tilde{v} \\
I_{\mathrm{e}} & \quad\equiv\quad e \\
I_{\mathrm{w}} & \quad\equiv\quad w \\
\mathbf{t} & \quad\equiv\quad \{s, r\} \\
where \\
\end{aligned} \\
\Xi \equiv \begin{cases}
\Xi_{\mathtt{ECREC}}(\boldsymbol{\sigma}_1, g, I, \mathbf{t}) & \text{if} \quad c = 1 \\
\Xi_{\mathtt{SHA256}}(\boldsymbol{\sigma}_1, g, I, \mathbf{t}) & \text{if} \quad c = 2 \\
\Xi_{\mathtt{RIP160}}(\boldsymbol{\sigma}_1, g, I, \mathbf{t}) & \text{if} \quad c = 3 \\
\Xi_{\mathtt{ID}}(\boldsymbol{\sigma}_1, g, I, \mathbf{t}) & \text{if} \quad c = 4 \\
\Xi_{\mathtt{EXPMOD}}(\boldsymbol{\sigma}_1, g, I, \mathbf{t}) & \text{if} \quad c = 5 \\
\Xi_{\mathtt{BN\_ADD}}(\boldsymbol{\sigma}_1, g, I, \mathbf{t}) & \text{if} \quad c = 6 \\
\Xi_{\mathtt{BN\_MUL}}(\boldsymbol{\sigma}_1, g, I, \mathbf{t}) & \text{if} \quad c = 7 \\
\Xi_{\mathtt{SNARKV}}(\boldsymbol{\sigma}_1, g, I, \mathbf{t}) & \text{if} \quad c = 8 \\
\Xi_{\mathtt{BLAKE2\_F}}(\boldsymbol{\sigma}_1, g, I, \mathbf{t}) & \text{if} \quad c = 9 \\
\Xi(\boldsymbol{\sigma}_1, g, I, \mathbf{t}) & \text{otherwise} \end{cases}

\text{Let} \; \mathtt{KEC}(I_{\mathbf{b}}) = \boldsymbol{\sigma}[c]_{\mathrm{c}}

其中

• I_{\mathrm{a}}
  • 接收者地址
• I_{\mathrm{o}}
  • 调用者 original transactor
• I_{\mathrm{p}}
  • gas Price
• I_{\mathbf{d}}
  • 消息调用的 input data (二进制字符串)
• I_{\mathrm{s}}
  • 发送者 sender
• I_{\mathrm{v}}
  • \tilde{v}
  • {\small DELEGATECALL} 指令上下文的中的 value
• I_{\mathrm{e}}
  • 当前消息调用/合约创建堆栈的深度
• I_{\mathrm{w}}
  • 是否有权改变状态
  • 参考公式 (63)

注意

• 映射
  • 客户端会存储映射 \mathtt{KEC}(I_{\mathbf{b}}) => I_{\mathbf{b}}
  • 这样可以方便根据 \boldsymbol{\sigma}[c]_{\mathrm{c}} 索引并取出目标地址的代码 I_{\mathbf{b}} 以执行
• 预编译合约
  • c 在 [1, 9] 表示预编译合约
  • 参考 # Appendix E. Precompiled Contracts

9. Execution Model 执行模型

参考 go-ethereum 源码

// github.com/ethereum/go-ethereum@v1.10.6/core/state_processor.go
func applyTransaction(msg types.Message, config *params.ChainConfig, bc ChainContext, author *common.Address, gp *GasPool, statedb *state.StateDB, blockNumber *big.Int, blockHash common.Hash, tx *types.Transaction, usedGas *uint64, evm *vm.EVM) (*types.Receipt, error);

  // github.com/ethereum/go-ethereum@v1.10.6/core/state_transition.go
  func ApplyMessage(evm *vm.EVM, msg Message, gp *GasPool) (*ExecutionResult, error);
    func (st *StateTransition) TransitionDb() (*ExecutionResult, error);

      // github.com/ethereum/go-ethereum@v1.10.6/core/vm/evm.go
      func (evm *EVM) Call(caller ContractRef, addr common.Address, input []byte, gas uint64, value *big.Int) (ret []byte, leftOverGas uint64, err error);

        // github.com/ethereum/go-ethereum@v1.10.6/core/vm/interpreter.go
        func (in *EVMInterpreter) Run(contract *Contract, input []byte, readOnly bool) (ret []byte, err error);

          // github.com/ethereum/go-ethereum@v1.10.6/core/vm/jump_table.go
          type (
            executionFunc func(pc *uint64, interpreter *EVMInterpreter, callContext *ScopeContext) ([]byte, error)
          )

          type operation struct {
            execute     executionFunc
          }

            // github.com/ethereum/go-ethereum@v1.10.6/core/vm/instructions.go

9.1 Basics 基础

9.2 Fees Overview 费用概述

• 消耗
  • 代码执行
  • 进一步的 消息调用 或 合约创建
  • 内存使用
• refund
  • 如果清除了一块存储，系统会免除这项操作的费用，且返还一定额度的 refund
  • 参考 # Appendix G. Fee Schedule
  • R_{\mathrm{sclear}}
  • R_{\mathrm{selfdestruct}}

9.3 Execution Environment 执行环境

I 执行环境

组成

• I_{\mathrm{a}}
  • 接收者地址
• I_{\mathrm{o}}
  • 调用者 original transactor
• I_{\mathrm{p}}
  • gas Price
• I_{\mathbf{d}}
  • 消息调用的 input data (二进制字符串)
• I_{\mathrm{s}}
  • 发送者 sender
• I_{\mathrm{v}}
  • value
• I_{\mathrm{b}}
  • 接收者的代码，将被执行
• I_{\mathrm{H}}
  • 当前区块的区块头
• I_{\mathrm{e}}
  • 当前消息调用/合约创建堆栈的深度
• I_{\mathrm{w}}
  • 是否有权改变状态
  • 参考公式 (63)

公式 (124) 函数 \Xi

(\boldsymbol{\sigma}', g', A, \mathbf{o}) \equiv \Xi(\boldsymbol{\sigma}, g, I)

其中

• \mathbf{o}
  • 执行结果 output

公式 (125) 累计子状态 A

A \equiv (A_{\mathbf{s}}, A_{\mathbf{l}}, A_{\mathbf{t}}, A_{\mathrm{r}})

• A_{\mathbf{s}}
  • 自毁集合
  • 交易执行完成后会被销毁的账户
• A_{\mathbf{l}}
  • 一系列日志
  • 方便外界旁观者简单跟踪合约调用
• A_{\mathbf{t}}
  • 交易接触的账户
  • 其中的 EMPTY 账户会被删除
• A_{\mathbf{r}}
  • refund balance
  • 累计需要归还的 gas

9.4 Execution Overview 执行概述

公式 (126) (127) (128) ... (137) (138) 函数 {\Xi} 的定义

\begin{aligned}
\Xi(\boldsymbol{\sigma}, g, I, T) & \quad\equiv\quad (\boldsymbol{\sigma}'\!, \boldsymbol{\mu}'_{\mathrm{g}}, A, \mathbf{o}) \\
(\boldsymbol{\sigma}', \boldsymbol{\mu}'\!, A, ..., \mathbf{o}) & \quad\equiv\quad X\big((\boldsymbol{\sigma}, \boldsymbol{\mu}, A^0\!, I)\big) \\
\boldsymbol{\mu}_{\mathrm{g}} & \quad\equiv\quad g \\
\boldsymbol{\mu}_{\mathrm{pc}} & \quad\equiv\quad 0 \\
\boldsymbol{\mu}_{\mathbf{m}} & \quad\equiv\quad (0, 0, ...) \\
\boldsymbol{\mu}_{\mathrm{i}} & \quad\equiv\quad 0 \\
\boldsymbol{\mu}_{\mathbf{s}} & \quad\equiv\quad () \\
\boldsymbol{\mu}_{\mathbf{o}} & \quad\equiv\quad ()
\end{aligned}

X\big( (\boldsymbol{\sigma}, \boldsymbol{\mu}, A, I) \big) \equiv \begin{cases}
\big(\varnothing, \boldsymbol{\mu}, A^0, I, \varnothing\big) & \text{if} \quad Z(\boldsymbol{\sigma}, \boldsymbol{\mu}, I) \\
\big(\varnothing, \boldsymbol{\mu}', A^0, I, \mathbf{o}\big) & \text{if} \quad w = \text{\small REVERT} \\
O(\boldsymbol{\sigma}, \boldsymbol{\mu}, A, I) \cdot \mathbf{o} & \text{if} \quad \mathbf{o} \neq \varnothing \\
X\big(O(\boldsymbol{\sigma}, \boldsymbol{\mu}, A, I)\big) & \text{otherwise} \\
\end{cases}

where

\begin{aligned}
\mathbf{o} & \quad\equiv\quad H(\boldsymbol{\mu}, I) \\
(a, b, c, d) \cdot e & \quad\equiv\quad (a, b, c, d, e) \\
\boldsymbol{\mu}' & \quad\equiv\quad \boldsymbol{\mu}\ \text{except:} \\
\boldsymbol{\mu}'_{\mathrm{g}} & \quad\equiv\quad \boldsymbol{\mu}_{\mathrm{g}} - C(\boldsymbol{\sigma}, \boldsymbol{\mu}, I)
\end{aligned}

其中

• X
  • 循环调用直到遇到异常或执行完成
• O
  • 单步执行当前指令 w
  • 参考 (146)
• Z
  • 检查是否异常
  • 参考 (140)
• o
  • H 的返回结果
• H
  • 检查是否正常终止
  • 返回 \varnothing 空，表示继续执行
  • 返回 () 空集，表示停止执行
  • 否则，表示有意识的停止执行并附加执行结果 o
  • 参考 (145)
• C(\boldsymbol{\sigma}, \boldsymbol{\mu}, I)
  • 参考 (314)
  • Appendix H.1. Gas Cost
• \boldsymbol{\mu}_{\mathrm{g}}
  • 剩余可用 gas
• \boldsymbol{\mu}_{\mathrm{pc}}
  • program counter
• \boldsymbol{\mu}_{\mathbf{m}}
  • memory contents
• \boldsymbol{\mu}_{\mathrm{i}}
  • active number of words in memory
• \boldsymbol{\mu}_{\mathbf{s}}
  • stack contents
• \boldsymbol{\mu}_{\mathbf{o}}
  • 执行输出 output

注意

• 公式 (146)，执行函数 \Xi 后，会丢弃 I' 并记录 \boldsymbol{\mu}'_{\mathrm{g}} 和 o

9.4.1 Machine State

机器状态 \boldsymbol{\mu} 组成为 (g, pc, \mathbf{m}, i, \mathbf{s})

(139) 当前待执行的指令 w

w \equiv \begin{cases} I_{\mathbf{b}}[\boldsymbol{\mu}_{\mathrm{pc}}] & \text{if} \quad \boldsymbol{\mu}_{\mathrm{pc}} < \lVert I_{\mathbf{b}} \rVert \\
\text{{\small STOP}} & \text{otherwise}
\end{cases}

// github.com/ethereum/go-ethereum@v1.10.6/core/vm/interpreter.go
func (in *EVMInterpreter) Run(contract *Contract, input []byte, readOnly bool) (ret []byte, err error)
  op = contract.GetOp(pc)
    operation := in.cfg.JumpTable[op]

// github.com/ethereum/go-ethereum@v1.10.6/core/vm/contract.go
// GetOp returns the n'th element in the contract's byte array
func (c *Contract) GetOp(n uint64) OpCode {
    return OpCode(c.GetByte(n))
}

// GetByte returns the n'th byte in the contract's byte array
func (c *Contract) GetByte(n uint64) byte {
    if n < uint64(len(c.Code)) {
        return c.Code[n]
    }

    return 0 // STOP
}

9.4.2 Exception Halting

公式 (140) (141) 异常检查函数 Z

\begin{aligned}
Z(\boldsymbol{\sigma}, \boldsymbol{\mu}, I) \quad\equiv\quad
& \boldsymbol{\mu}_g < C(\boldsymbol{\sigma}, \boldsymbol{\mu}, I) \quad \vee \\
& \mathbf{\delta}_w = \varnothing \quad \vee \\
& \lVert\boldsymbol{\mu}_\mathbf{s}\rVert < \mathbf{\delta}_w \quad \vee \\
& ( w = \text{\small JUMP} \; \wedge \; \boldsymbol{\mu}_\mathbf{s}[0] \notin D(I_\mathbf{b}) ) \quad \vee \\
& ( w = \text{\small JUMPI} \; \wedge \; \boldsymbol{\mu}_\mathbf{s}[1] \neq 0 \; \wedge\boldsymbol{\mu}_\mathbf{s}[0] \notin D(I_\mathbf{b}) ) \quad \vee \\
& ( w = \text{\small RETURNDATACOPY} \; \wedge \boldsymbol{\mu}_{\mathbf{s}}[1] + \boldsymbol{\mu}_{\mathbf{s}}[2] > \lVert\boldsymbol{\mu}_{\mathbf{o}}\rVert) \quad \vee \\
& \lVert\boldsymbol{\mu}_\mathbf{s}\rVert - \mathbf{\delta}_w + \mathbf{\alpha}_w > 1024 \quad \vee \\
& ( \neg I_{\mathrm{w}} \; \wedge \; W(w, \boldsymbol{\mu}) ) \quad \vee \\
& ( w = \text{\small SSTORE} \; \wedge \; \boldsymbol{\mu}_g \leqslant G_{\mathrm{callstipend}} )
\end{aligned}

where

\begin{aligned}
W(w, \boldsymbol{\mu}) \quad\equiv\quad
& w \in \{\text{\small CREATE}, \text{\small CREATE2}, \text{\small SSTORE}, \text{\small SELFDESTRUCT}\} \ \vee \\
& \text{\small LOG0} \le w \; \wedge \; w \le \text{\small LOG4} \quad \vee \\
& w = \text{\small CALL} \; \wedge \; \boldsymbol{\mu}_{\mathbf{s}}[2] \neq 0
\end{aligned}

其中

• \delta
  • 指令 w 的出栈个数
• \alpha
  • 指令 w 的入栈个数
• 栈的索引
  • 从上往下增长
  • 栈顶为0

异常情况

// github.com/ethereum/go-ethereum@v1.10.6/core/vm/errors.go

// List evm execution errors
var (
  ErrOutOfGas                 = errors.New("out of gas")
  ErrCodeStoreOutOfGas        = errors.New("contract creation code storage out of gas")
  ErrDepth                    = errors.New("max call depth exceeded")
  ErrInsufficientBalance      = errors.New("insufficient balance for transfer")
  ErrContractAddressCollision = errors.New("contract address collision")
  ErrExecutionReverted        = errors.New("execution reverted")
  ErrMaxCodeSizeExceeded      = errors.New("max code size exceeded")
  ErrInvalidJump              = errors.New("invalid jump destination")
  ErrWriteProtection          = errors.New("write protection")
  ErrReturnDataOutOfBounds    = errors.New("return data out of bounds")
  ErrGasUintOverflow          = errors.New("gas uint64 overflow")
  ErrInvalidCode              = errors.New("invalid code: must not begin with 0xef")
  ErrStackUnderflow           = errors.New(fmt.Sprintf("stack underflow (%d <=> %d)", e.stackLen, e.required))
  ErrStackOverflow            = errors.New(fmt.Sprintf("stack limit reached %d (%d)", e.stackLen, e.limit))
  ErrInvalidOpCode            = errors.New(fmt.Sprintf("invalid opcode: %s", e.opcode))
)

9.4.3 Jump Destionation Validity 跳转地址验证

公式 (142) (143) (144)

D(\mathbf{c}) \equiv D_{\mathrm{J}}(\mathbf{c}, 0)

where:

D_{\mathrm{J}}(\mathbf{c}, i) \equiv \begin{cases}
\{\} & \text{if} \quad i \geqslant \lVert \mathbf{c} \rVert  \\
\{ i \} \cup D_{\mathrm{J}}(\mathbf{c}, N(i, \mathbf{c}[i])) & \text{if} \quad \mathbf{c}[i] = \text{\small JUMPDEST} \\
D_{\mathrm{J}}(\mathbf{c}, N(i, \mathbf{c}[i])) & \text{otherwise} \\
\end{cases}

N(i, w) \equiv \begin{cases}
i + w - \text{\small PUSH1} + 2 & \text{if} \quad w \in [\text{\small PUSH1}, \text{\small PUSH32}] \\
i + 1 & \text{otherwise} \end{cases}

其中

• \mathbf{c}
  • 当前执行中的一段代码
• D TODO
  • 计算 \mathbf{c} 的有效跳转地址的集合
  • 按 {\small JUMPDEST} 指令的位置来定义
• N TODO
  • 下一有效指令在代码 \mathbf{c} 中的位置
  • 且忽略 \text{\small PUSH1} 指令的数据(如果有的话)

9.4.4 Normal Halting

(145) 正常停止检查函数 H

H(\boldsymbol{\mu}, I) \equiv \begin{cases}
H_{\text{\tiny RETURN}}(\boldsymbol{\mu}) & \text{if} \quad w \in \{\text{\small {RETURN}}, \text{\small REVERT}\} &\\
() & \text{if} \quad w \in \{ \text{\small {STOP}}, \text{\small {SELFDESTRUCT}} \} &\\
\varnothing & \text{otherwise}
\end{cases}

有3种可能的输出

其中

• H_{\text{\tiny RETURN}}
  • 表示有意识地停止执行并附加执行结果 o
  • 参考 # Appendix H. Virtual Machine Specification
  • H_{\text{\tiny RETURN}}(\boldsymbol{\mu}) \equiv \boldsymbol{\mu}_{\mathbf{m}}[ \boldsymbol{\mu}_{\mathbf{s}}[0] \dots ( \boldsymbol{\mu}_{\mathbf{s}}[0] + \boldsymbol{\mu}_{\mathbf{s}}[1] - 1 ) ]
• () 空集
  • 表示停止执行
• \varnothing 空
  • 表示继续执行

9.5 The Execution Cycle 执行循环

公式 (146) (147) (148) (149)

\begin{aligned}
O\big((\boldsymbol{\sigma}, \boldsymbol{\mu}, A, I)\big) & \quad\equiv\quad (\boldsymbol{\sigma}', \boldsymbol{\mu}', A', I) \\
\Delta & \quad\equiv\quad \mathbf{\alpha}_{w} - \mathbf{\delta}_{w} \\
\lVert\boldsymbol{\mu}'_{\mathbf{s}}\rVert & \quad\equiv\quad \lVert\boldsymbol{\mu}_{\mathbf{s}}\rVert + \Delta \\
\quad \forall x \in [\mathbf{\alpha}_{w}, \lVert\boldsymbol{\mu}'_{\mathbf{s}}\rVert): \boldsymbol{\mu}'_{\mathbf{s}}[x] & \quad\equiv\quad \boldsymbol{\mu}_{\mathbf{s}}[x-\Delta]
\end{aligned}

其中

• \delta
  • 指令 w 的出栈个数
• \alpha
  • 指令 w 的入栈个数
• \Delta
  • 栈大小的变化
• 栈的索引
  • 从上往下增长
  • 栈顶为0

公式 (150) (151)

\begin{aligned}
\boldsymbol{\mu}'_{\mathrm{g}} & \quad\equiv\quad \boldsymbol{\mu}_{\mathrm{g}} - C(\boldsymbol{\sigma}, \boldsymbol{\mu}, I) \\
\boldsymbol{\mu}'_{\mathrm{pc}} & \quad\equiv\quad \begin{cases}
{J_{\text{JUMP}}}(\boldsymbol{\mu}) & \text{if} \quad w = \text{\small JUMP} \\
{J_{\text{JUMPI}}}(\boldsymbol{\mu}) & \text{if} \quad w = \text{\small JUMPI} \\
N(\boldsymbol{\mu}_{\mathrm{pc}}, w) & \text{otherwise}
\end{cases}
\end{aligned}

其中

• N
  • 参考 (144)

公式 (152) (153) (154) (155)

\begin{aligned}
\boldsymbol{\mu}'_{\mathbf{m}} & \quad\equiv\quad \boldsymbol{\mu}_{\mathbf{m}} \\
\boldsymbol{\mu}'_{\mathrm{i}} & \quad\equiv\quad \boldsymbol{\mu}_{\mathrm{i}} \\
A' & \quad\equiv\quad A \\
\boldsymbol{\sigma}' & \quad\equiv\quad \boldsymbol{\sigma}
\end{aligned}

通常我们假定内存(\boldsymbol{\mu}'_{\mathbf{m}}, \boldsymbol{\mu}'_{\mathbf{i}})，自毁集合，世界状态不会被修改

具体参考 # Appendix H. Virtual Machine Specification

10. Blocktree to Blockchain 区块树到区块链

(156) (157) 区块难度计算函数

\begin{aligned}
B_{\mathrm{t}} & \equiv B'_{\mathrm{t}} + B_{\mathrm{d}} \\
B' & \equiv P(B_{\mathrm{H}})
\end{aligned}

其中

• B
  • 一个区块
• B'
  • 父区块
• B_{\mathrm{t}}
  • 区块总难度
• B_{\mathrm{d}}
  • 当前区块的难度

11. Block Finalization 区块定稿

区块定稿要经过 4 步验证

• 验证叔块 Ommer Validation
• 验证交易 Transaction Validation
• 奖励发放 Reward Application
• 验证状态和 nonce State & Nonce Validation

11.1 Ommer Validation 验证 Ommer

(158) (159) (160)

\lVert B_{\mathbf{U}} \rVert \leqslant 2 \bigwedge_{\mathbf{U} \in B_{\mathbf{U}}} {V({\mathbf{U}}})\; \wedge \; k({\mathbf{U}}, P(\mathbf{B}_{\mathbf{H}})_{\mathbf{H}}, 6) \\

k(U, H, n) \equiv \begin{cases} \mathit{false} & \text{if} \quad n = 0 \\
s(U, H) \vee \; k(U, P(H)_{\mathrm{H}}, n - 1) & \text{otherwise}
\end{cases}

s(U, H) \equiv (P(H) = P(U)\; \wedge \; H \neq U \; \wedge \; U \notin B(H)_{\mathbf{U}})

验证

• 当前区块头最多有2个叔块
• 叔块头列表自身有效，且表示的叔块与当前区块在6代以内

其中

• k
  • is-kin 是亲属
• s
  • is-sibling 是兄妹
• V
  • 区块头验证函数
  • 参考公式 (51)

11.2 Transaction Validation 交易验证

{B_{\mathrm{H}}}_{\mathrm{g}} = {\ell}({\mathbf{R})_{\mathrm{u}}}

其中

• {B_{\mathrm{H}}}_{\mathrm{g}}
  • 当前区块头中的累计使用 gas
• {\ell}({\mathbf{R})_{\mathrm{u}}}
  • 当前区块中最后一条收据的累计使用 gas

11.3 Reward Application 奖励发放

公式 (162) (163) (164) (165) (166) \Omega 区块奖励函数

\begin{aligned}
\Omega(B, \boldsymbol{\sigma}) & \quad\equiv\quad \boldsymbol{\sigma}': \boldsymbol{\sigma}' = \boldsymbol{\sigma} \quad \text{except:} \\
\qquad\boldsymbol{\sigma}'[{\mathbf{B}_{\mathrm{H}}}_{\mathrm{c}}]_{\mathrm{b}} & \quad=\quad \boldsymbol{\sigma}[{\mathbf{B}_{\mathrm{H}}}_{\mathrm{c}}]_{\mathrm{b}} + \left(1 + \frac{\lVert \mathbf{B}_{\mathbf{U}}\rVert}{32}\right)R_{\mathrm{block}} \\
\forall \mathbf{U} \in \mathbf{B}_{\mathbf{U}}:\quad
\boldsymbol{\sigma}'[\mathbf{U}_{\mathrm{c}}] & \quad=\quad \begin{cases}
\varnothing &\text{if}\ \boldsymbol{\sigma}[\mathbf{U}_{\mathrm{c}}] = \varnothing\ \wedge\ R = 0 \\
\mathbf{a}' &\text{otherwise}
\end{cases} \\
\mathbf{a}' & \quad\equiv\quad (\boldsymbol{\sigma}[U_{\mathrm{c}}]_{\mathrm{n}}, \boldsymbol{\sigma}[U_{\mathrm{c}}]_{\mathrm{b}} + R, \boldsymbol{\sigma}[U_{\mathrm{c}}]_{\mathbf{s}}, \boldsymbol{\sigma}[U_{\mathrm{c}}]_{\mathrm{c}}) \\
R & \quad\equiv\quad \left(1 + \frac{1}{8} (U_{\mathrm{i}} - {B_{\mathrm{H}}}_{\mathrm{i}})\right) R_{\mathrm{block}}
\end{aligned}

其中

• \mathbf{B}_{\mathbf{U}}
  • 当前区块内的叔块头列表
• {\mathbf{B}_{\mathrm{H}}}_{\mathrm{c}}
  • 当前区块头中存储的 beneficiary
  • 即当前区块收益的归属地址
• U_{\mathrm{c}}
  • 叔块收益的归属地址

(167) {R_{block}} 定义

R_{\mathrm{block}} = 10^{18} \times \begin{cases}
5 &\text{if}\ H_{\mathrm{i}} < F_{\mathrm{Byzantium}} \\
3 &\text{if}\ F_{\mathrm{Byzantium}} \leqslant H_{\mathrm{i}} < F_{\mathrm{Constantinople}} \\
2 &\text{if}\ H_{\mathrm{i}} \geqslant F_{\mathrm{Constantinople}} \\
\end{cases} \\

11.4 State & Nonce Validation 状态和 nonce 验证

(168) 映射 Block 到世界状态的函数 \Gamma

\Gamma(B) \equiv \begin{cases}
\boldsymbol{\sigma}_0 & \text{if} \quad P(B_{\mathrm{H}}) = \varnothing \\
\boldsymbol{\sigma}_{\mathrm{i}}: \mathtt{{TRIE}}(L_{\mathrm{S}}(\boldsymbol{\sigma}_{\mathrm{i}})) = {P(B_{\mathrm{H}})_{\mathrm{H}}}_{\mathrm{r}} & \text{otherwise}
\end{cases}

其中

• L_S
  • 世界状态坍塌函数
  • 参考 (10)
• \mathtt{{TRIE}}(L_{\mathrm{S}}(\boldsymbol{\sigma}_{\mathrm{i}})) = {P(B_{\mathrm{H}})_{\mathrm{H}}}_{\mathrm{r}}
  • 判断 state TRIE 根节点的内容 等于 区块头的 stateRoot
  • 理解
    • 不像 Block 存储在区块链上，TRIE 树结构是通过存储在客户端数据库中的数据构造出来的
    • 因此需要比较区块头存储中的 stateRoot hash，是否与构造 TRIE 树时层层计算出来的根节点 hash 相等

(169) (170) (171) (172) 区块级别状转换函数 \Phi

\begin{aligned}
\Phi(B) & \quad\equiv\quad B': \quad B' = B^* \quad \text{except:} \\
B'_{\mathrm{n}} & \quad=\quad n: \quad x \leqslant \frac{2^{256}}{{H_{\mathrm{d}}}} \\
B'_{\mathrm{m}} & \quad=\quad m \quad \text{with } (x, m) = \mathtt{PoW}(B^*_{{\cancel{n}}}, n, \mathbf{d}) \\
B^* & \quad\equiv\quad B \quad \text{except:} \quad {{B^*_{\mathrm{r}}}} = {r}({\Pi}(\Gamma(B), B))
\end{aligned}

\Phi 函数计算 nonce 和 mixHash 后分别设置到 B'_{\mathrm{n}} 和 B'_{\mathrm{m}}

其中

• \mathbf{d}
  • 参考 # Appendix J. EthHash
• \Pi
  • 区块级状态转换函数
  • 参考公式 (177)
• \Omega
  • 区块奖励函数

(173) 第 n 个状态 \boldsymbol{\sigma}[n]

\boldsymbol{\sigma}[n] = \begin{cases} {\Gamma}(B) & \text{if} \quad n < 0 \\ {\Upsilon}(\boldsymbol{\sigma}[n - 1], B_{\mathbf{T}}[n]) & \text{otherwise} \end{cases}

(174) (175) (176) \Upsilon^{\mathbf{u}} \Upsilon^{\mathbf{l}} \Upsilon^{\mathbf{z}} 的定义/赋值

\begin{aligned}
\mathbf{R}[n]_{\mathrm{u}} = \begin{cases} 0 & \text{if} \quad n < 0 \\
\Upsilon^g(\boldsymbol{\sigma}[n - 1], B_{\mathbf{T}}[n]) \quad + \mathbf{R}[n-1]_{\mathrm{u}} & \text{otherwise} \end{cases}
\end{aligned}

\mathbf{R}[n]_{\mathbf{l}} =
\Upsilon^{\mathbf{l}}(\boldsymbol{\sigma}[n - 1], B_{\mathbf{T}}[n])

\mathbf{R}[n]_{\mathrm{z}} =
\Upsilon^{\mathrm{z}}(\boldsymbol{\sigma}[n - 1], B_{\mathbf{T}}[n])

其中

• R_{\mathrm{u}}
  • 当前区块中，交易发生后的累积 gas 使用量
• R_{\mathrm{l}}
  • 交易过程中创建的一系列日志
• R_{\mathrm{z}}
  • 交易的状态码
• R_{\mathrm{b}}
  • 由一系列日志构成的 Bloom 过滤器
  • 参考公式 (26) (27) (28) (29) (30)

公式 (177) 区块级状态转换函数 \Pi

\Pi(\boldsymbol{\sigma}, B) \equiv {\Omega}(B, \ell(\boldsymbol{\sigma}))

对区块应用区块奖励函数 {\Omega}，可以得到最新的世界状态，即最终的区块级状态转换

Appendix B. Recursive Length Prefix

参考 eth wiki: RLP

Appendix C. Hex-Prefix Encoding

公式 (189) (190)

\begin{aligned}
\mathtt{HP}(\mathbf{x}, t): \mathbf{x} \in \mathbb{Y} \equiv \begin{cases}
(16f(t), 16\mathbf{x}[0] + \mathbf{x}[1], 16\mathbf{x}[2] + \mathbf{x}[3], ...) &
\text{if} \lVert \mathbf{x} \rVert \; \text{is even} \\
(16(f(t) + 1) + \mathbf{x}[0], 16\mathbf{x}[1] + \mathbf{x}[2], 16\mathbf{x}[3] + \mathbf{x}[4], ...) & \text{otherwise}
\end{cases} \\
\end{aligned}

\begin{aligned}
f(t) & \equiv & \begin{cases} 2 & \text{if} \quad t \neq 0 \\ 0 & \text{otherwise} \end{cases}
\end{aligned}

参考

• Data structure in Ethereum | Episode 1+: Compact (Hex-prefix) encoding.

// https://github.com/ethereum/go-ethereum/blob/master/trie/encoding.go

// https://github.com/sontuphan/debug-geth/blob/master/trie/encoding.go
// This block of code does Compact (hex-prefix) encoding as following table
// hex char    bits    |    node type partial    path length
// 0           0000    |    extension            even
// 1           0001    |    extension            odd
// 2           0010    |    terminating (leaf)   even
// 3           0011    |    terminating (leaf)   odd

func hexToCompact(hex []byte) []byte {
    terminator := byte(0)
    if hasTerm(hex) {
        terminator = 1
        hex = hex[:len(hex)-1]
    }
    buf := make([]byte, len(hex)/2+1)
    buf[0] = terminator << 5 // the flag byte
    if len(hex)&1 == 1 {
        buf[0] |= 1 << 4 // odd flag
        buf[0] |= hex[0] // first nibble is contained in the first byte
        hex = hex[1:]
    }
    decodeNibbles(hex, buf[1:])
    return buf
}

• 输入
  • hex
  • 16进制明文字符串 path
    • 每个字符占用一个字节，取值范围是 [0-9, a-f]
  • 可能在 path 尾部追加最后一个字节，值为 0x10，表示 terminator
    • 即 hex 是个叶子节点(包含 value)，而非中间节点
• 输出
  • buf (Hex-Prefix 编码得到的二进制字符串 )
  • 添加半个字节(一个hex编码)到 hex 前面，用于表示
    • hex 是否包含 terminator
    • hex 移除 terminator 后(如果有的话)，长度是奇数还是偶数
  • 确保 buf 的长度是偶数

例子

Appendix D. Modified Merkle Patricia Tree

参考

• Understanding Trie Databases in Ethereum
• Ethereum block architecture

(191) (192) 数据集合 \mathfrak{I}

\mathfrak{I} = \{ (\mathbf{k}_0 \in \mathbb{B}, \mathbf{v}_0 \in \mathbb{B}), (\mathbf{k}_1 \in \mathbb{B}, \mathbf{v}_1 \in \mathbb{B}), ... \} \\
\forall I \in \mathfrak{I}: I \equiv (I_0, I_1)

(193) (194)

任何 bytes 都可以看为半字节(nibbles 4bit)组成的序列

\begin{aligned}
y(\mathfrak{I}) & = \{ (\mathbf{k}_0' \in \mathbb{Y}, \mathbf{v}_0 \in \mathbb{B}), (\mathbf{k}_1' \in \mathbb{Y}, \mathbf{v}_1 \in \mathbb{B}), ... \} \\
\forall n: \quad \forall i < 2\lVert\mathbf{k}_{n}\rVert: \quad \mathbf{k}_{n}'[i] & \equiv
\begin{cases}
  \lfloor \mathbf{k}_{n}[i \div 2] \div 16 \rfloor & \text{if} \; i \; \text{is even} \\
  \mathbf{k}_{n}[\lfloor i \div 2 \rfloor] \bmod 16 & \text{otherwise}
\end{cases}
\end{aligned}

公式 (195) 根节点函数 \texttt{TRIE}

\texttt{TRIE}(\mathfrak{I}) \equiv \texttt{KEC}\big(\texttt{RLP} (c(\mathfrak{I}, 0))\big)

公式 (196)

n(\mathfrak{I}, i) \equiv \begin{cases}
() & \text{if} \quad \mathfrak{I} = \varnothing \\
c(\mathfrak{I}, i) & \text{if} \quad \lVert \, \texttt{RLP} \big( c(\mathfrak{I}, i) \big) \rVert < 32 \\
\texttt{KEC}\big(\texttt{RLP}( c(\mathfrak{I}, i)) \big) & \text{otherwise}
\end{cases}

公式 (197)

\begin{aligned}
c(\mathfrak{I}, i) \equiv \begin{cases}
  \big(\texttt{HP}(I_0[i .. (\lVert I_0\rVert - 1)], 1), I_1 \big) & \text{if} \ \lVert \mathfrak{I} \rVert = 1 \text{where} \ \exists I: I \in \mathfrak{I} \\
  \big(\texttt{HP}(I_0[i .. (j - 1)], 0), n(\mathfrak{I}, j) \big) & \text{if} \ i \ne j \  \text{where} \ j = \max \{ x : \exists \mathbf{l}: \lVert \mathbf{l} \rVert = x \wedge \forall I \in \mathfrak{I}: I_0[0 .. (x - 1)] = \mathbf{l} \} \\
  (u(0), u(1), ..., u(15), v) & \text{otherwise} \ \text{where} \\
  & u(j) \equiv n(\{ I : I \in \mathfrak{I} \wedge I_0[i] = j \}, i + 1) \\
  & v = \begin{cases}
    I_1 & \text{if} \ \exists I: I \in \mathfrak{I} \wedge \lVert I_0 \rVert = i \\
    () & \text{otherwise}
  \end{cases}
\end{cases}
\end{aligned}

其中

• 叶子节点 Lea
  • 包含两个字段
  • 第一个字段是剩下的 Key 的 HP 编码(HP 的第二个参数为1)
  • 第二个字段是 Value
• 扩展节点 Extension
  • 包含两个字段
  • 第一个字段是剩下的 Key 的可以至少被两个剩下节点共享的最大公共前缀((HP 的第二个参数为0)
  • 第二个字段是 n(\mathfrak{I}, j)
• 分支节点 Branch
  • 包含17个字段
  • 前16个项目对应于 [0-9,a-f]
  • 第17个字段是存储在当前结点结束的节点
    • 例如
    • 有三个key，分别是 abc，abd，ab
    • 第17个字段储存了ab节点的值

图片来源 ELI5 How does a Merkle-Patricia-trie tree work?

Appendix H. Virtual Machine Specification

注意区分单位

\boldsymbol{\mu}_{\mathbf{s}} / \boldsymbol{\sigma}[a]_{\mathbf{s}} 以 32 字节为单位

\boldsymbol{\mu}_{\mathbf{m}} 以 1 字节为单位

参考 SSTORE/SLOAD, MSTORE/MLOAD

H.2. Instruction Set

参考 Difference between CALL, CALLCODE and DELEGATECALL

DELEGATECALL was a new opcode that was a bug fix for CALLCODE which did not preserve msg.sender and msg.value. If Alice invokes Bob who does DELEGATECALL to Charlie, the msg.sender in the DELEGATECALL is Alice (whereas if CALLCODE was used the msg.sender would be Bob).

AAVE v2 - white paper
aave小组分享：白皮书解读
Dapp-Learning: AAVE

这里简单记下学习笔记

需要说明的是，个人不太适应白皮书自上而下的展开结构，所以笔记反向记录

利率 rate

当前时刻的浮动/稳定借款利率

variable/stable rate

公式

\#R_{t}^{asset} =
\begin{aligned}
\begin{cases}
\#R_{base}^{asset} + \frac{U_{t}^{asset}}{U_{optimal}} \times \#R_{slope1}^{asset} &\ if \ U_{t}^{asset} \lt U_{optimal} \\
\#R_{base}^{asset} + \#R_{slope1}^{asset} + \frac{U_{t}^{asset} - U_{optimal}}{1 - U_{optimal}} \times \#R_{slope2}^{asset} &\ if \ U_{t}^{asset} \geq U_{optimal}
\end{cases}
\end{aligned}

这里的 \# 可以为 V 或 S，代入后得到 VR_{t} 或 SR_{t}，分别表示浮动利率和稳定利率

换句话说，VR_{t} 与 SR_{t} 计算公式相同，只是系统参数不同

其中

资金利用率 等于 总债务 占 总储蓄 的比例

U_{t}^{asset} =
\begin{aligned}
\begin{cases}
0 &\ if \ L_{t}^{asset} = 0 \\
\frac{D_{t}^{asset}}{L_{t}^{asset}} &\ if \ L_{t}^{asset} \gt 0
\end{cases}
\end{aligned}

总债务 等于 浮动利率债务 与 稳定利率债务 之和

D_{t}^{asset} = VD_{t}^{asset} + SD_{t}^{asset}

综合上面三个公式，可以看到，利率 \#R_{t} 与 资金利用率 U_{t} 正相关

也就是说，借贷需求旺盛时，利率随着资金利用率上升；借贷需求萎靡时，利率随着资金利用率下降

代码

存储

library DataTypes {
  struct ReserveData {
    //the current variable borrow rate. Expressed in ray
    uint128 currentVariableBorrowRate;
    //the current stable borrow rate. Expressed in ray
    uint128 currentStableBorrowRate;
  }
}

更新

interface IReserveInterestRateStrategy {
  function calculateInterestRates(
    address reserve,
    address aToken,
    uint256 liquidityAdded,
    uint256 liquidityTaken,
    uint256 totalStableDebt,
    uint256 totalVariableDebt,
    uint256 averageStableBorrowRate,
    uint256 reserveFactor
  )
    external
    view
    returns (
      uint256 liquidityRate,
      uint256 stableBorrowRate,
      uint256 variableBorrowRate
    );
}

最新浮动借款利率

即上面的 VR_{t}

稳定借款利率

平均稳定借款利率

overall stable rate

借款 mint()

假设利率为 SR_t 时发生一笔额度为 SB_{new} 的借款，则

\overline{SR}_{t} = \frac{SD_{t} \times \overline{SR}_{t-1} + SB_{new} \times SR_{t}}{SD_{t} + SB_{new}}

SD_{t} 表示此前债务 (不含 SB_{new}) 到当前时刻累计的本金+利息（即 previousSupply）

在白皮书中没有公式，但应该是

SD_{t} = SB \times (1+\frac{\overline{SR}_{t-1}}{T_{year}})^{\Delta T}

--

用户 x 的 平均利率 (用于还款时的计算)

\overline{SR}(x) = \sum\nolimits_{i}^{}\frac{SR_{i}(x) \times SD_{i}(x)}{SD_{i}(x)}

问题：未拆开 SD_{i-1}(x) 与 SB_{new}

实际：需要拆开分别乘以不同的利率

结论：不应简单以 SD_{i}(x) 代替

结合源码，应该修正为

\overline{SR}_{t}(x) = \frac{SD_{t}(x) \times \overline{SR}_{t-1}(x) + SB_{new} \times SR_{t}}{SD_{t}(x) + SB_{new}}

其中

SD_{t}(x) = SB(x) \times (1+\frac{\overline{SR}_{t}}{T_{year}})^{\Delta T}

结合源码，应该修正为

SD_{t}(x) = SB(x) \times (1+\frac{\overline{SR}_{t-1}(x)}{T_{year}})^{\Delta T}

比较 \overline{SR}_{t} 和 \overline{SR}(x) 两个公式

• (x) 强调 用户 x 的平均利率，只受其自身操作的影响，不受其他用户影响

比较 \overline{SR}(x) 修正前后的两个公式

• 原公式不出现 t 调强 用户 x 的平均利率，自上次操作后，不受时间影响
• 修正后更好体现 rebalancing

还款 burn()

假设用户平均利率为 \overline{SR}(x) 时发生一笔额度为 SB(x) 的还款，则

\overline{SR}_{t} =
\begin{aligned}
\begin{cases}
0 &\ if \ SD - SB(x) = 0 \\
\frac{SD_{t} \times \overline{SR}_{t-1} - SB(x) \times \overline{SR}(x)}{SD_t - SB(x)} &\ if \ SD - SB(x) \gt 0
\end{cases}
\end{aligned}

代码

存储

contract StableDebtToken is IStableDebtToken, DebtTokenBase {
  uint256 internal _avgStableRate; // 池子平均利率

  mapping(address => uint40) internal _timestamps; // 用户上次借款时间
  mapping(address => uint256) internal _usersStableRate; // 用户平均利率
}

更新

StableDebtToken.mint() 更新 _avgStableRate，_timestamps[user] 和 _userStableRate[user]

StableDebtToken.burn() 更新 _avgStableRate，_timestamps[user]，如果还款金额未超过利息，则将剩余利息作为新增借款，进行 mint() 这将修改 _userStableRate[user]，也是 rebalancing

TODO 举例

function burn(address user, uint256 amount) external override onlyLendingPool {
    // Since the total supply and each single user debt accrue separately,
    // there might be accumulation errors so that the last borrower repaying
    // mght actually try to repay more than the available debt supply.
    // In this case we simply set the total supply and the avg stable rate to 0

    // For the same reason described above, when the last user is repaying it might
    // happen that user rate * user balance > avg rate * total supply. In that case,
    // we simply set the avg rate to 0
}

平均借款利率

overall borrow rate

\overline{R_{t}}^{asset} =
\begin{aligned}
\begin{cases}
0 &\ if \ D_t=0 \\
\frac{VD_t \times VR_t + SD_t \times \overline{SR}_t}{D_t} &\ if \ D_t > 0
\end{cases}
\end{aligned}

当前时刻的流动性利率

current liquidity rate

流动性利率 = 平均借款利率 X 资金利用率

LR_{t}^{asset} = \overline{R}_{t} \times U_{t}

结合 平均借款利率 和 资金利用率 的公式

\overline{R_{t}}^{asset} =
\begin{aligned}
\begin{cases}
0 &\ if \ D_t=0 \\
\frac{VD_t \times VR_t + SD_t \times \overline{SR}_t}{D_t} &\ if \ D_t > 0
\end{cases}
\end{aligned}

U_{t}^{asset} =
\begin{aligned}
\begin{cases}
0 &\ if \ L_{t}^{asset} = 0 \\
\frac{D_{t}^{asset}}{L_{t}^{asset}} &\ if \ L_{t}^{asset} \gt 0
\end{cases}
\end{aligned}

同时考虑 超额抵押 的隐藏要求

D_{t} < L_{t}

得到

LR_{t}^{asset} =
\begin{aligned}
\begin{cases}
0 &\ if \ L_{t} = 0 \ or \ D_{t} = 0\\
\frac{VD_t \times VR_t + SD_t \times \overline{SR}_t}{L_{t}} &\ if \ L_{t} \gt 0
\end{cases}
\end{aligned}

理解如下

分子 VR_{t} 与 SR_{t} 都是年化利率，所以 LR_{t} 也是年化流动性利率

分母 L_{t} 表示池子总存款本金，所以 LR_{t} 表示 每单位存款本金，产生的借款利息

指数 index

累计流动性指数

cumulated liquidity index

从池子首次发生用户操作时，累计到现在，每单位存款本金，变成多少本金（含利息收入）

cumulated liquidity index

LI_t=(LR_t \times \Delta T_{year} + 1) \times LI_{t-1} \\
LI_0=1 \times 10 ^{27} = 1 \ ray

其中

\Delta T_{year} = \frac{\Delta T}{T_{year}} = \frac{T - T_{l}}{T_{year}}

T_{l} 池子最近一次发生用户操作的的时间

T_{l} is updated every time a borrow, deposit, redeem, repay, swap or liquidation event occurs.

--

每单位存款本金，未来将变成多少本金（含利息收入）

reserve normalized income

NI_t = (LR_t \times \Delta T_{year} + 1) \times LI_{t-1}

存储

  struct ReserveData {
    //the liquidity index. Expressed in ray
    uint128 liquidityIndex;
  }

更新

  function _updateIndexes(
    DataTypes.ReserveData storage reserve,
    uint256 scaledVariableDebt,
    uint256 liquidityIndex,
    uint256 variableBorrowIndex,
    uint40 timestamp
  ) internal returns (uint256, uint256) {
    uint256 currentLiquidityRate = reserve.currentLiquidityRate;
    uint256 newLiquidityIndex = liquidityIndex;

    //only cumulating if there is any income being produced
    if (currentLiquidityRate > 0) {
      uint256 cumulatedLiquidityInterest =
        MathUtils.calculateLinearInterest(currentLiquidityRate, timestamp);

      newLiquidityIndex = cumulatedLiquidityInterest.rayMul(liquidityIndex);
      require(newLiquidityIndex <= type(uint128).max, Errors.RL_LIQUIDITY_INDEX_OVERFLOW);

      reserve.liquidityIndex = uint128(newLiquidityIndex);
    }

    reserve.lastUpdateTimestamp = uint40(block.timestamp);
  }
}

累计浮动借款指数

cumulated variable borrow index

从池子首次发生用户操作时，累计到现在，每单位借款债务，共变成多少债务

cumulated variable borrow index

VI_{t} = (1 + \frac{VR_t}{T_{year}})^{\Delta T} \times VI_{t-1}

--

每单位浮动借款债务，未来将变成多少债务

normalised variable (cumulated) debt

VN_{t} = (1 + \frac{VR_{t}}{T_{year}})^{\Delta T} \times VI_{t-1}

存储

struct ReserveData {
    uint128 variableBorrowIndex;
}

计算

// ReserveLogic.sol

/**
* @dev Returns the ongoing normalized variable debt for the reserve
* A value of 1e27 means there is no debt. As time passes, the income is accrued
* A value of 2*1e27 means that for each unit of debt, one unit worth of interest has been accumulated
* @return The normalized variable debt. expressed in ray
**/
function getNormalizedDebt(DataTypes.ReserveData storage reserve) internal view returns (uint256) {
    uint40 timestamp = reserve.lastUpdateTimestamp;

    if (timestamp == uint40(block.timestamp)) {
        return reserve.variableBorrowIndex;
    }

    uint256 cumulated =
        MathUtils.calculateCompoundedInterest(reserve.currentVariableBorrowRate, timestamp).rayMul(
        reserve.variableBorrowIndex
        );

    return cumulated;
}

更新

  function _updateIndexes(
    DataTypes.ReserveData storage reserve,
    uint256 scaledVariableDebt,
    uint256 liquidityIndex,
    uint256 variableBorrowIndex,
    uint40 timestamp
  ) internal returns (uint256, uint256) {
    uint256 currentLiquidityRate = reserve.currentLiquidityRate;

    uint256 newVariableBorrowIndex = variableBorrowIndex;

    //only cumulating if there is any income being produced
    if (currentLiquidityRate > 0) {
      //as the liquidity rate might come only from stable rate loans, we need to ensure
      //that there is actual variable debt before accumulating
      if (scaledVariableDebt != 0) {
        uint256 cumulatedVariableBorrowInterest =
          MathUtils.calculateCompoundedInterest(reserve.currentVariableBorrowRate, timestamp);
        newVariableBorrowIndex = cumulatedVariableBorrowInterest.rayMul(variableBorrowIndex);

        require(
          newVariableBorrowIndex <= type(uint128).max,
          Errors.RL_VARIABLE_BORROW_INDEX_OVERFLOW
        );

        reserve.variableBorrowIndex = uint128(newVariableBorrowIndex);
      }
    }

    reserve.lastUpdateTimestamp = uint40(block.timestamp);
    return (newLiquidityIndex, newVariableBorrowIndex);
  }

用户累计浮动借款指数

user cumulated variable borrow index

VI(x) = VI_t(x)

因为是浮动利率，所以用户每次发生借款的利率，都是当时最新的浮动借款利率

代币 token

aToken

ScB_{t}(x) 用户 x 在 t 时刻发生存款或取回操作后，在 ERC20 Token 中记录的 balance 债务

存款

ScB_{t}(x) = ScB_{t-1} + \frac{m}{NI_{t}}

取回

ScB_{t}(x) = ScB_{t-1} - \frac{m}{NI_{t}}

在当前最新的 t 时刻看，用户 x 的总余额

aB_{t}(x) = ScB_{t}(x) \times NI_{t}

Debt token

浮动借款代币

Variable debt token

ScVB_t(x) 用户 x 在 t 时刻发生借款或还款操作后，在 ERC20 Token 中记录的 balance 债务

借款

ScVB_t(x) = ScVB_{t-1}(x) + \frac{m}{VN_{t}}

还款

ScVB_t(x) = ScVB_{t-1}(x) - \frac{m}{VN_{t}}

在当前最新的 t 时刻看，用户 x 的总债务

VD(x) = ScVB(x) \times D_{t}

这里是个比较明显的 typo，应该修正为

VD(x) = ScVB(x) \times VN_{t}

稳定借款代币

Stable debt token

用户 x 此前在 t 发生操作后

SD_{t}(x) = SB(x) \times (1+\frac{\overline{SR}_{t-1}(x)}{T_{year}})^{\Delta T}

风险

借贷利率参数

Borrow Interest Rate

参考 Borrow Interest Rate

风险参数

Risk Parameters

参考 Risk Parameters

实际用的是万分比

抵押率

Loan to Value 抵押率，表示价值 1 ETH 的抵押物，能借出价值多少 ETH 的资产

最大抵押率，是用户抵押的各类资产的抵押率的加权平均值

Max LTV = \frac{ \sum{{Collateral}_i \ in \ ETH \ \times \ LTV_i}}{Total \ Collateral \ in \ ETH}

比如 用户存入价值为 1 ETH 的 DAI，和 1 ETH 的 Ethereum，那么

Max LTV = \frac{1 \times 0.75 + 1 \times 0.825}{1+1} = 0.7875

清算阈值

Liquidation Threshold

LiquidationThreshold = \frac{\sum{{Collateral}_i \ in \ ETH \ \times \ {Liquidation \ Threshold}_i}}{Total \ Collateral \ in \ ETH}

上面的例子为

LiquidationThreshold = \frac{1 \times 0.8 + 1 \times 0.85}{1 + 1} = 0.825

Loan-To-Value 与 Liquidation Threshold 之间的窗口，是借贷者的安全垫

清算奖励

Liquidation Bonus

抵押物的拍卖折扣，作为清算者的奖励

健康度

Health Factor

Hf = \frac{\sum{{Collateral}_i \ in \ ETH \ \times \ {Liquidation \ Threshold}_i}}{Total \ Borrows \ in \ ETH}

Hf < 1 说明这个用户资不抵债，应该清算 (代码中，Hf 单位为 ether)

假设用户抵押此前存入的2 ETH 资产，按最大抵押率借出价值 0.7875 \times 2 = 1.575 ETH 的债务，此时

Hf = \frac{1 \times 0.8 + 1 \times 0.85}{1.575} = 1.0476

相关代码如下

  /**
   * @dev Calculates the user data across the reserves.
   * this includes the total liquidity/collateral/borrow balances in ETH,
   * the average Loan To Value, the average Liquidation Ratio, and the Health factor.
   **/
  function calculateUserAccountData(
    address user,
    mapping(address => DataTypes.ReserveData) storage reservesData,
    DataTypes.UserConfigurationMap memory userConfig,
    mapping(uint256 => address) storage reserves,
    uint256 reservesCount,
    address oracle
  ) internal view returns (uint256, uint256, uint256, uint256, uint256){

    CalculateUserAccountDataVars memory vars;

    for (vars.i = 0; vars.i < reservesCount; vars.i++) {
      if (!userConfig.isUsingAsCollateralOrBorrowing(vars.i)) {
        continue;
      }

      vars.currentReserveAddress = reserves[vars.i];
      DataTypes.ReserveData storage currentReserve = reservesData[vars.currentReserveAddress];

      (vars.ltv, vars.liquidationThreshold, , vars.decimals, ) = currentReserve
        .configuration
        .getParams();

      vars.tokenUnit = 10**vars.decimals;
      vars.reserveUnitPrice = IPriceOracleGetter(oracle).getAssetPrice(vars.currentReserveAddress);

      if (vars.liquidationThreshold != 0 && userConfig.isUsingAsCollateral(vars.i)) {
        vars.compoundedLiquidityBalance = IERC20(currentReserve.aTokenAddress).balanceOf(user);

        uint256 liquidityBalanceETH =
          vars.reserveUnitPrice.mul(vars.compoundedLiquidityBalance).div(vars.tokenUnit);

        vars.totalCollateralInETH = vars.totalCollateralInETH.add(liquidityBalanceETH);

        vars.avgLtv = vars.avgLtv.add(liquidityBalanceETH.mul(vars.ltv));
        vars.avgLiquidationThreshold = vars.avgLiquidationThreshold.add(
          liquidityBalanceETH.mul(vars.liquidationThreshold)
        );
      }

      if (userConfig.isBorrowing(vars.i)) {
        vars.compoundedBorrowBalance = IERC20(currentReserve.stableDebtTokenAddress).balanceOf(
          user
        );
        vars.compoundedBorrowBalance = vars.compoundedBorrowBalance.add(
          IERC20(currentReserve.variableDebtTokenAddress).balanceOf(user)
        );

        vars.totalDebtInETH = vars.totalDebtInETH.add(
          vars.reserveUnitPrice.mul(vars.compoundedBorrowBalance).div(vars.tokenUnit)
        );
      }
    }

    vars.avgLtv = vars.totalCollateralInETH > 0 ? vars.avgLtv.div(vars.totalCollateralInETH) : 0;
    vars.avgLiquidationThreshold = vars.totalCollateralInETH > 0
      ? vars.avgLiquidationThreshold.div(vars.totalCollateralInETH)
      : 0;

    vars.healthFactor = calculateHealthFactorFromBalances(
      vars.totalCollateralInETH,
      vars.totalDebtInETH,
      vars.avgLiquidationThreshold
    );
    return (
      vars.totalCollateralInETH,
      vars.totalDebtInETH,
      vars.avgLtv,
      vars.avgLiquidationThreshold,
      vars.healthFactor
    );
  }

清算

继续上面的例子：用户抵押价值 2 ETH 的资产，借出 1.575 ETH 的债务，Hf 为 1.0476

经过一段时间后，市场可能出现如下清算场景

场景一：用户借出的债务从价值为 1.575 ETH，上涨为 2 ETH，此时

Hf = \frac{1 \times 0.8 + 1 \times 0.85}{2} = 0.825

场景二：用户抵押的资产 DAI，从价值为 1 ETH，下跌为 0.8 ETH，此时

Hf = \frac{0.8 \times 0.8 + 1 \times 0.85}{1.575} = 0.946

用户可能如下考虑：

假设，用户看多自己借出的债务，比如用户认为债务价值会继续上涨到 3 ETH，此时可以不做操作，任由清算

相反，用户看多自己抵押的资产，而认为债务升值无望，那么如果资产被低位清算，将得不偿失；此时用户可以追加抵押或偿还债务，避免清算

假设用户未及时操作，套利者先行一步触发清算，相关代码如下

  /**
   * @return collateralAmount: The maximum amount that is possible to liquidate given all the liquidation constraints
   *                           (user balance, close factor)
   *         debtAmountNeeded: The amount to repay with the liquidation
   **/
  function _calculateAvailableCollateralToLiquidate(
    DataTypes.ReserveData storage collateralReserve,
    DataTypes.ReserveData storage debtReserve,
    address collateralAsset,
    address debtAsset,
    uint256 debtToCover,
    uint256 userCollateralBalance
  ) internal view returns (uint256, uint256) {
    uint256 collateralAmount = 0;
    uint256 debtAmountNeeded = 0;
    IPriceOracleGetter oracle = IPriceOracleGetter(_addressesProvider.getPriceOracle());

    AvailableCollateralToLiquidateLocalVars memory vars;

    vars.collateralPrice = oracle.getAssetPrice(collateralAsset);
    vars.debtAssetPrice = oracle.getAssetPrice(debtAsset);

    (, , vars.liquidationBonus, vars.collateralDecimals, ) = collateralReserve
      .configuration
      .getParams();
    vars.debtAssetDecimals = debtReserve.configuration.getDecimals();

    // This is the maximum possible amount of the selected collateral that can be liquidated, given the
    // max amount of liquidatable debt
    vars.maxAmountCollateralToLiquidate = vars
      .debtAssetPrice
      .mul(debtToCover)
      .mul(10**vars.collateralDecimals)
      .percentMul(vars.liquidationBonus)
      .div(vars.collateralPrice.mul(10**vars.debtAssetDecimals));

    if (vars.maxAmountCollateralToLiquidate > userCollateralBalance) {
      collateralAmount = userCollateralBalance;
      debtAmountNeeded = vars
        .collateralPrice
        .mul(collateralAmount)
        .mul(10**vars.debtAssetDecimals)
        .div(vars.debtAssetPrice.mul(10**vars.collateralDecimals))
        .percentDiv(vars.liquidationBonus);
    } else {
      collateralAmount = vars.maxAmountCollateralToLiquidate;
      debtAmountNeeded = debtToCover;
    }
    return (collateralAmount, debtAmountNeeded);
  }

注意 maxAmountCollateralToLiquidate，表示可以被清算的最大的抵押资产的数量

它通过计算清算债务的价值，除以抵押资产的单位价格得到

由于清算者得到的是抵押资产，而抵押资产本身面临着市场波动风险，为了鼓励清算以降低系统风险，这里会凭空乘以 liquidationBonus

比如清算的抵押资产为 DAI，根据上面链接的数据，该资产当前的 liquidationBonus 为 10500

即清算者支付 debtAmountNeeded 的债务，可以多得到 5% 的 aDAI（或 DAI）

实际清算时，需要考虑资产的阈值与奖励各有不同；而且 Hf 是整体概念，而清算需要指定某个资产和某个债务；比如用户抵押 A 和 B 资产，借出 C 和 D 债务，清算时可以有 4 种选择

清算参数，与清算资产的多样化，使得清算策略复杂起来～

// 别跳清算套利的坑