core gas

一、基础GAS扣费实现

1.EVM实现

code

func IntrinsicGas(data []byte, accessList types.AccessList, isContractCreation bool, isHomestead, isEIP2028, isEIP3860 bool) (uint64, error) {  
    // Set the starting gas for the raw transaction  
    var gas uint64  
    // 如果是创建合约且是homestead之后的交易  
    if isContractCreation && isHomestead {  
       gas = params.TxGasContractCreation  
    } else {  
       gas = params.TxGas  
    }  
    dataLen := uint64(len(data))  
    // Bump the required gas by the amount of transactional data  
    if dataLen > 0 {  
       // Zero and non-zero bytes are priced differently  
       // 计算非0  
       var nz uint64  
       for _, byt := range data {  
          if byt != 0 {  
             nz++  
          }  
       }  
       // Make sure we don't exceed uint64 for all data combinations  
       nonZeroGas := params.TxDataNonZeroGasFrontier  
       if isEIP2028 {  
          // 只关心这个就可以，==16  
          nonZeroGas = params.TxDataNonZeroGasEIP2028  
       }  
       // 需要： nz * nonZeroGas + gas < math.MaxUint64       if (math.MaxUint64-gas)/nonZeroGas < nz {  
          return 0, ErrGasUintOverflow  
       }  
       gas += nz * nonZeroGas  
       // zero 个数  
       z := dataLen - nz  
       if (math.MaxUint64-gas)/params.TxDataZeroGas < z {  
          return 0, ErrGasUintOverflow  
       }  
       gas += z * params.TxDataZeroGas  
  
       // 创建合约且是EIP-3860  
       if isContractCreation && isEIP3860 {  
          // 32字节对齐  
          lenWords := toWordSize(dataLen)  
          if (math.MaxUint64-gas)/params.InitCodeWordGas < lenWords {  
             return 0, ErrGasUintOverflow  
          }  
          gas += lenWords * params.InitCodeWordGas  
       }  
    }  
  
    if accessList != nil {  
       // 访问列表的长度  
       gas += uint64(len(accessList)) * params.TxAccessListAddressGas  
       // 访问列表中的所有key的个数  
       gas += uint64(accessList.StorageKeys()) * params.TxAccessListStorageKeyGas  
    }  
    return gas, nil  
}

流程

如果为创建合约且是homestead（我们默认应该是最新的）之后的交易，那么gas为53000，否则为21000.
计算data（合约调用中的input）中非零个数nz，则有gas += nz * 16.
非零个数z = codeLen - nz，则有 gas += z * 4.
如果是创建合约，gas += (dataLen + 31) / 32 * 2；
如果accessList不为空，gas += accessListLength * 2400，gas += keyNums * 1900

举例计算test_data/sstore_with_original目录下的trace。前置条件： 1.初始tx_gas = 30000. 2.input = 60fe47b1000000000000000000000000000000000000000000000000000000000000014b 计算得：0的个数为30，非0为6.（注：上述为16进制字符串，两个字符为1byte，要使用类似hex.Deocde等方法转换成[]byte结构） 3.从tx_info中accessList中获得的长度为0. 计算： 1.此trace中不是创建合约，gas = 21000； 2.gas = 21000 + 6 * 16 = 21096； 3.gas = 21096 + 30 * 4 = 21216；根据我们从hardhat curl下的tx_info和trace.json，可得30000000 - 29978784 = 21216。所以计算过程是对的。

2.设计

Begin_tx_1 gas_left填值为tx.gas，并且向Public_table中进行查询TxGasLimit；
Begin_tx_2 gas_left值同样为tx.gas，与Begin_tx_1之间的gas_left满足差值为0；
Begin_tx_3填充的是 tx.gas - intrinsic_gas。约束Begin_tx_2 gas_left - Begin_tx_3 gas_left = intrinsic_gas。

Bengin_tx_3 可以按照如下计算intrinsic_gas。

init_code_gas_cost = (calldata.len() + 31) / 32 * 2; -- 计算创建合约时可能消耗的gas费； is_create * (init_code_gas_cost + 53000) + (1-is_create) * 21000 + call_data_gas_cost()； -- 实际gas费；

call_data_gas_cost()就是查0的过程

pub fn call_data_gas_cost(&self) -> u64 {  
    self.call_data  
        .iter()  
        .fold(0, |acc, byte| acc + if *byte == 0 { 4 } else { 16 })  
}

constraints变量获取

self.is_create：bool
- 约束时需要该值进行public lookup约束，tag为TxIsCreateAndStatus;
self.call_data_gas_cost：u64
- 约束时需要进行public lookup约束，tag为TxIsCreateAndStatus;
self.call_data_length：u64
- 约束时需要进行public lookup约束，tag为TxIsCreateAndStatus;
call_data_word_length: u64
- 使用memoryExpansion算术进行计算和并进行算术电路的lookup约束；

获取上述变量后，即可按照如下方式计算基础gas：

//  select::expr() 等同于if语句
let init_code_gas_cost = select::expr(
        is_create.clone(),
        call_data_word_length * INIT_CODE_WORD_GAS.expr(),
        0.expr(),
    );

let intrinsic_gas_cost = select::expr(
    is_create.clone(),
    GasCost::CREATION_TX.expr(),
    GasCost::TX.expr(),
) + call_data_gas_cost
    + init_code_gas_cost;

layout

cnt
2	PUBLIC(0..5)	Arithmetic_tiny(7..11)
1	STATE0(0..7)	STATE(8..15)
0	DYNA_SELECTOR(0..17)	AUX(18..24)

二、STORAGE GAS实现

包含SSTORE和SLOAD，其中由于SLOAD比较简单，介绍里可能穿插带过。

1.SSTORE EVM 实现(EIP-3529)

func makeGasSStoreFunc(clearingRefund uint64) gasFunc

剩余gas要大于SstoreSentryGasEIP2200;
取值：
1. x,y：代表即将要存入的key，value；
2. slot：槽位，也就是x；
3. current：目前stateDB里存放的value，但还未commit；
4. original：已经commit的value；
if addrPresent, slotPresent := evm.StateDB.SlotInAccessList(contract.Address(), slot); !slotPresent表示这个槽位是否在访问列表里，如果不在，代表首次访问，需要添加冷加载gas费用，cost = ColdSloadCostEIP2929，并将该槽位添加到访问列表里
如果current == value。表示本次操作不改变状态，返回cost + WarmStorageReadCostEIP2929（100）；
如果original == current（表示这是一次干净的操作，状态还未改变过）：
1. 如果original为空，表示要创建一个槽位，返回cost + SstoreSetGasEIP2200（20000）;
2. 如果value为空，表示要删除一个槽位，执行addRefund(SstoreClearsScheduleRefundEIP3529（4800）)；
3. 返回 cost + (SstoreResetGasEIP2200（5000） - ColdSloadCostEIP2929（2100）)，表示准备写入一个已存在的槽位；
如果original不为空：
1. 如果current为空，表示重新创建一个槽位，执行subRefund(SstoreClearsScheduleRefundEIP3529（4800）)；
2. 如果value为空，表示要删除一个槽位，执行addRefund(SstoreClearsScheduleRefundEIP3529（4800）)；
如果original == value:
1. 如果original为空，表示重置为原来这种不存在的状态，执行addRefund(SstoreSetGasEIP2200（20000）- WarmStorageReadCostEIP2929（100）)；
2. 如果original不为空，表示重置为原来的状态，执行addRefund(SstoreResetGasEIP2200（5000）-ColdSloadCostEIP2929（2100） - WarmStorageReadCostEIP2929（100）)；
返回cost + WarmStorageReadCostEIP2929（100）;

常量值：

SstoreSentryGasEIP2200: 2300
ColdSloadCostEIP2929: 2100
WarmStorageReadCostEIP2929: 100
SstoreSetGasEIP2200: 20000
SstoreResetGasEIP2200: 5000
SstoreClearsScheduleRefundEIP3529: SstoreResetGasEIP2200 - ColdSloadCostEIP2929 + TxAccessListStorageKeyGas 4800

2.EIP-2929

在以太坊中，EIP-2929（Ethereum Improvement Proposal 2929）是一个提案，旨在增加特定操作码的气费成本，以更好地反映它们对网络资源的实际消耗。这个提案主要关注的是状态访问操作的气费，特别是 SLOAD、CALL、CALLCODE、DELEGATECALL 和 STATICCALL 操作。EIP-2929 引入了“冷”和“热”访问的概念，以区分对某个数据的首次访问（冷访问）和后续访问（热访问）。

冷装载（Cold Load）

冷装载指的是对某个数据的首次访问。在 EIP-2929 之前，访问智能合约的状态变量（例如通过 SLOAD 操作）的成本是固定的，不考虑该数据是否已经在之前被访问过。EIP-2929 引入了冷访问的概念，并为首次访问某个状态变量指定了更高的气费，反映出从 EVM 状态树中加载数据所需的更高成本。ColdSloadCostEIP2929 是指按照 EIP-2929 规定，进行一次冷装载操作的气费成本。

热存储读取（Warm Storage Read）

热存储读取指的是对已经被访问过的数据的再次访问。EIP-2929 规定，一旦某个数据在当前交易中被访问过（变“热”了），再次访问它的成本就会降低。WarmStorageReadCostEIP2929 是指进行一次热存储读取操作的气费成本。

这种区分反映了实际的资源消耗：从 EVM 的状态树中首次加载数据（冷访问）比访问已经在内存中的数据（热访问）更昂贵。

实际影响

EIP-2929 的这种改变使得智能合约开发者需要更加注意他们合约的状态访问模式，以避免不必要的冷访问，从而优化合约的气费消耗。对于那些需要频繁读取同一状态变量的合约，合理地规划状态访问顺序可以显著降低交易成本。

同时，这也是以太坊对网络拥堵和高气费问题的一种应对措施，通过调整气费成本来鼓励更高效的智能合约编写和执行，以及更合理地利用网络资源。

3.设计

预处理：

stateDB结构：

pub struct StateDB {  
   /// key is address -- is_warm (生命周期是交易级别，影响的是一笔交易内的数据)
    /// is_warm在一笔交易中初次被访问时应该false，之后会被写为true
    pub access_list: HashSet<Word>,
    /// key is (address, slot) -- is_warm (生命周期是交易级别，影响的是一笔交易内的数据)
    /// is_warm在一笔交易中初次被访问时应该false，之后会被写为true
    /// 向lot_access_list中插入新的数据时, 会同时向该address插入access_list
    pub slot_access_list: HashSet<(Word, U256)>,
    /// key is (address, slot) -- value_prev (生命周期是交易级别，影响的是一笔交易内的数据)
    /// 同一笔交易，上一次sstore opcode写入的值
    pub dirty_storage: HashMap<(Word, U256), U256>,
    /// pending key is (address, slot, tx_idx) -- committed_value in pending (生命周期是交易级别，会因为上一笔交易的改变而改变)
    /// 上一笔交易，最后一次sstore对某个key写入的值
    pub pending_storage: BTreeMap<(Word, U256, usize), U256>,
    /// original key is (address, slot) -- committed_value in original (生命周期是区块级别，对于一个区块内的所有交易都是一样的)
    /// tx_idx == 1
    /// 同一个区块，上一个区块对应key的value，即已经提交的值，对于当前区块该值不会发生变化
    pub original_storage: HashMap<(Word, U256), U256>,
}

有一系列的方法，例如get、insert等等这些。

预处理交易，核心逻辑：

/// 主要分为两部，第一步是为了找到所有交易中的第一次SLOAD，填充original_storage;
/// 第二步是获取每一笔交易的最后一次sstore的值，填充pending_storage;

每笔交易执行完后，reset_tx:

pub fn reset_tx(&mut self) {  
    self.access_list = HashSet::new();  
    self.slot_access_list = HashSet::new();  
    self.dirty_storage = HashMap::new();  
}

gas_left的状态处理：
1. 在函数 generate_trace_witness 中，current_state.gas_left 初始为 tx.gas，也即一笔交易的初始gas。
2. 在每次执行时 step 时，current_state.gas_left = step.gas - step.gas_cost。
3. 我们以前在 Aux 列的 gas_left 使用的是 trace.gas，这个值是执行状态前的 gas，目前 Aux 列 gas_left 赋值是使用的 current_state.gas_left。

layout

cnt
4	get_storage_value_write(0..11)
3	get_slot_access_list_read(0..11)	get_slot_access_list_write(12..23)
2	lt(0)	diff(1)	U64Overflow(2..6)	U64Overflow(7..11)	prev_eq_value_inv_hi(12)	prev_eq_value_inv_lo(13)	committed_eq_prev_inv_hi(14)	committed_eq_prev_inv_lo(15)	committed_value_inv(16)	value_inv(17)	value_pre_inv(18)	committed_eq_value_inv_hi(19)	committed_eq_value_inv_lo(20)	value_is_eq_prev(21)	committed_value_is_eq_prev(22)	committed_value_is_eq_value(23)	slot_gas(24)	warm_case_gas(25)	refund_part_1(26)	refund_part_2(27)	refund_part_3(28)	refund_part_4(29)	refund_part_5(30)
1	STATE1(0..7)	STATE2(8..15)	STATE3(16..23)	STATE4(24..31)
0	dynamic_selector (0..17)	AUX(18..24)

关于EIP2929的特性，我们对state电路引入了新的类型，方便我们获取is_warm的信息和某个地址（或者某个地址+某个key）对应的不同类型的value：

pub enum Tag {
    // 对应EVM里的AddressInAccessList， key是address
    AddrInAccessListStorage,
    // 对应EVM里的SlotInAccessList， key是(address, slot)
    SlotInAccessListStorage,
}

我们也设计了一个类似于EVM中的链上存储结构，取名为'stateDB':

pub struct StateDB {
    /// key is address -- is_warm (生命周期是交易级别，影响的是一笔交易内的数据)
    /// is_warm在一笔交易中初次被访问时应该false，之后会被写为true
    pub access_list: HashSet<Word>,
    /// key is (address, slot) -- is_warm (生命周期是交易级别，影响的是一笔交易内的数据)
    /// is_warm在一笔交易中初次被访问时应该false，之后会被写为true
    /// 向lot_access_list中插入新的数据时, 会同时向该address插入access_list
    pub slot_access_list: HashSet<(Word, U256)>,
    /// key is (address, slot) -- value_prev (生命周期是交易级别，影响的是一笔交易内的数据)
    /// 同一笔交易，上一次sstore opcode写入的值
    pub dirty_storage: HashMap<(Word, U256), U256>,
    /// pending key is (address, slot, tx_idx) -- committed_value in pending (生命周期是交易级别，会因为上一笔交易的改变而改变)
    /// 上一笔交易，最后一次sstore对某个key写入的值
    pub pending_storage: BTreeMap<(Word, U256, usize), U256>,
    /// original key is (address, slot) -- committed_value in original (生命周期是区块级别，对于一个区块内的所有交易都是一样的)
    /// tx_idx == 1
    /// 同一个区块，上一个区块对应key的value，即已经提交的值，对于当前区块该值不会发生变化
    pub original_storage: HashMap<(Word, U256), U256>,
}

stateDB是在witness初始化时被赋值，其值来源于链上storage结构和trace里对应结构，由于值来源有多种方式，这里可以具体参考代码，我们只介绍关于取值时的一些细节：

// 当我们需要查询是否为is_warm时，通过方法：
pub fn slot_in_access_list(&self, address: &Word, slot: &U256) -> bool {
    self.slot_access_list.contains(&(*address, *slot))
}

// 当我们需要查询该key对应的上一个值时，对应EVM取dirty value部分，此时该函数的生命周期应该为交易级别，也即同一笔交易中是否该key在上一次操作中有过值的写入，如果dirty没取到，则会继续查询committed值，也即链上值：
pub fn get_dirty_value(&self, address: &Word, key: &Word, tx_idx: usize) -> (bool, U256) {
    match self.state_db.get_dirty_storage(address, key) {
        Some(value) => (true, value),
        None => self.get_committed_value(address, key, tx_idx),
    }
}

// 当我们需要查询该key对应的committed value时，committed value对应的首先是pending值，此时该函数的生命周期应该为区块级别，也即同一个区块里，如果前面某个交易对该key写入过值，那么就会在pending_storage中存入该值，否则则为前面区块对该key写入的值，这个值存在于original_storage中；
pub fn get_committed_value(&self, address: &Word, key: &Word, tx_idx: usize) -> (bool, U256) {
    match self.state_db.get_pending_storage(address, key, tx_idx) {
        Some(value) => (true, value),
        None => match self.state_db.get_original_storage(address, key) {
            Some(value) => (true, value),
            None => (false, U256::zero()),
        },
    }
}

constraints

IS_WARM

由于我们在stateDB中已经设计好了对应结构，因此我们对于is_warm及value_prev等取值的相关操作就变得容易了很多，我们只需要把对应需要的值，通过get_storage_lookup进行约束即可。

SSTORE

由于SSTORE里涉及到多个变量的if判断以及值是否为0，因此无法一一描述，具体逻辑可参考代码中的StorageGasCost结构体，该结构体实现了gas计算的所有逻辑，由于EVM的逻辑整体比较繁琐，因此在流程上进行了一定的优化，具体思路可参考如下注释：

/// 1.warm case select:
/// if value = value_pre {
///    return WARM_ACCESS (100)
/// }else{
///     if commit_value = value_pre {
///        if commit_value = 0 {
///             return SSTORE_SET (20000)
///         }else {
///             return SSTORE_RESET (2900)
///         }
///     }else{
///         return WARM_ACCESS（100）
///     }
/// }
///
/// 2,cold case select:
/// if is_warm {
///     return warm_case_gas
/// }else{
///     return warm_case_gas + COLD_SLOAD (2100)
/// }

在上述if判断中，我们尽可能的选择了select::expr()方法进行实现。并且在我们计算的过程中，会发现我们最终的计算步骤并非是在获取了所有变量以后直接计算gas，而是拆分成了多步，这是因为我们为了优化电路所引入的一些中间变量，如下部分代码，我们在计算了set_slot_gas后，引入了slot_gas来作为中间变量：

let set_slot_gas = select::expr(
    self.committed_eq_prev.clone(),
    select::expr(
        self.committed_is_zero.clone(),
        GasCost::SSTORE_SET.expr(),
        GasCost::SSTORE_RESET.expr(),
    ),
    GasCost::WARM_ACCESS.expr(),
);

let slot_gas = meta.query_advice(
    config.vers[2 * ARITHMETIC_TINY_COLUMN_WIDTH + ARITHMETIC_TINY_START_IDX + 12],
    Rotation(-2),
);

constraints.push((
    "slot gas constraint".into(),
    set_slot_gas.clone() - slot_gas.clone(),
));

虽然目前为止我们refund相关的预处理还未完全实现，但是我们SSTORE的refund实际已经实现了对应功能，如下是对应流程，同上：

/// The refund in this round is a delta value, not the final refund
/// if current != value {
///     if commit == value_prev && value == 0 {
///         cost + SstoreClearsScheduleRefundEIP3529(4800)
///     } else {
///         if commit != 0 && value_prev == 0 {
///             cost - SstoreClearsScheduleRefundEIP3529(4800) -- refund_part_1
///         }
///         if commit != 0 && value == 0 {
///             cost + SstoreClearsScheduleRefundEIP3529(4800) -- refund_part_2
///         }
///         if commit == value && commit == 0 {
///             cost + SstoreSetGasEIP2200（20000）- WarmStorageReadCostEIP2929（100）-- refund_part_3
///         }
///         if commit == value && commit != 0 {
///             cost + SstoreResetGasEIP2200（5000）-ColdSloadCostEIP2929（2100） - WarmStorageReadCostEIP2929（100）-- refund_part_4
///         }
///     }
/// }

SLOAD

SLOAD的gas实现较为简单，我们上述实现is_warm后，仅需几行代码即可完成：

fn sload_gas_cost(&self) -> Expression<F> {
    select::expr(
        self.is_warm.clone(),
        GasCost::WARM_ACCESS.expr(),
        GasCost::COLD_SLOAD.expr(),
    )
}

其他辅助约束

begin_tx中新增两个约束，用于约束初始状态：

1. constraints.push(("init tx refund = 0".into(), refund)); 
2. ("public gas lookup".into(), public_gas_lookup),

state_circuit

// access list storage 不适用这个规则  
vec.push((  
    "is_first_access=0 & is_write=0 & not access_list_tag ==> prev_value_lo=cur_value_lo",  
    q_enable.clone()  
        * (1.expr() - is_first_access.clone())  
        * (1.expr() - access_list_storage_condition.clone())  
        * (prev_value_lo.clone() - value_lo.clone())  
        * (1.expr() - is_write.clone()),  
));  
vec.push((  
    "is_first_access=0 & is_write=0 & not access_list_tag ==> prev_value_hi=cur_value_hi",  
    q_enable.clone()  
        * (1.expr() - is_first_access.clone())  
        * (1.expr() - access_list_storage_condition.clone())  
        * (prev_value_hi.clone() - value_hi.clone())  
        * (1.expr() - is_write.clone()),  
));


// tag is access_list_storage_condition  
vec.push((  
    "is_first_access=0 & access_list_tag => value_pre_hi in cur == value_hi in prev",  
    q_enable.clone()  
        * (1.expr() - is_first_access.clone())  
        * access_list_storage_condition.clone()  
        * (value_prev_hi_in_cur.clone() - prev_value_hi.clone())  
));  
  
  
vec.push((  
    "is_first_access=0 & access_list_tag => value_pre_hi in cur == value_hi in prev",  
    q_enable.clone()  
        * (1.expr() - is_first_access.clone())  
        * access_list_storage_condition.clone()  
        * (value_prev_hi_in_cur.clone() - prev_value_hi.clone())  
));  
  
vec.push((  
    "access_list_tag => value_hi == 0",  
    q_enable.clone()  
        * access_list_storage_condition.clone()  
        * value_hi.clone()  
));  
  
vec.push((  
    "access_list_tag => value_lo is bool",  
    q_enable.clone()  
        * access_list_storage_condition.clone()  
        * (value_lo.clone() - 1.expr())  
        * value_lo.clone()  
));

三、CALL GAS实现

1.EVM（EIP2929）

call gas计算

CALL 常量Gas = 100

判断当前地址是否在access list中，如果不在，则添加进列表中，并比较gas_left >= coldcost（2600-100）;
执行call gas计算；
1. 如果是EIP158（遵循这个规则）
  1. 如果transfersValue（value不为0）且address为空，则gas += 25000;
2. 否则如果address不存在，gas += 25000 （我们暂时不考虑此分支）
3. 如果transfersValue（value不为0），gas += 9000
4. 计算memoryGas，gas += memoryGas；
  1. memsize是通过opcode的memoryFunc实现的，然后对memsize使用32对齐，计算出memorySize；
  2. 通过memorySize和当前的memsize使用memoryGasCost计算memoryGas；
5. callGas计算
  1. 如果是EIP150(gas = gas - base * 63 / 64)--（1）
    1. 执行availableGas = availableGas（执行改opcode之前的gas_left） - base（上面步骤计算出来的gas）；
    2. gas := availableGas - availableGas/64；
    3. 如果传参的callCost（调用CALL时stack里的gas值）不是Uint64，或者计算的gas < callCost，则返回gas（其实这里表达的含义就是callCost如果超过了Uint64，也就代表了gas一定小于callCost，返回gas没问题）；
  2. 如果callCost不是Uint64，就返回溢出。这里跟EIP150规则是互斥的；
  3. 返回callCost；
6. gas += callGas；
如果warm直接返回call gas，否则返回call gas + coldGas（2500）；

（1）解释：callGas部分实际计算的是base * 63 / 64这一部分，其中base就是callGas中的availableGas，而公式gas = gas - base * 63 / 64 反应的是对整体gas的计算，可以简单理解为，执行完callGas后，我们的gas_left 应该是 gas_left = gas_left - callGas计算的值。

从整体来看的话可以分为以下几个部分：

warm相关的计算：
1. 如果热访问，则gas = 100，否则gas = 2600；
2. 如果value不为0，gas += 9000，且如果stateDB(address)又为空，gas += 25000；
memoryGas部分
1. 首先需要实现call的memoryFunc（类似于memory的max对比），计算出memSize；
2. memSize进行toWordSize（x + 31 / 32） * 32 ，计算memorySize；
3. 使用memorySize，计算memoryGasCost；
callGas计算部分；
1. 执行availableGas = availableGas（执行改opcode之前的gas_left） - base（上面步骤计算出来的gas）；
2. gas := availableGas - availableGas/64；
3. 如果传参的callCost（调用CALL时stack里的gas值）不是Uint64，或者计算的gas < callCost，则返回gas（其实这里表达的含义就是callCost如果超过了Uint64，也就代表了gas一定小于callCost，返回gas没问题）；
4. 如果callCost不是Uint64，就返回溢出。这里跟EIP150规则是互斥的；
5. 返回callCost；

最终我们call的gas就是以上三部分值的和。

call gas 与下一个opcode之间的关联(opCall)

gas = interpreter.evm.callGasTemp --> callGas ；
如果value不等于0，gas += 2300；
调用interpreter.evm.Call(scope.Contract, toAddr, args, gas, &value)：
1. 如果地址不存在：
  1. 如果不是预编译且IsEIP158且value为0，返回gas；
2. 如果是预编译，调用RunPrecompiledContract(p, input, gas)（暂时忽略这个分支）
3. 否则，运行CALL的那个合约，且gas == CALL合约的gas；
4. 如果Call成功，则返回gas，否则，返回0；
scope.Contract.Gas += returnGas --> 下一步的gas；

总结流程： callOp gas cost 计算： call_op_gas_cost = is_warm * 2600 + (1 - is_warm) * 100 + has_value * (9000 + address.is_empty * 25000) + memoryGas + call_gas

传入的gas费用应该为 callGas + has_value * 2300;

~~如果地址不存在 && 不是预编译 && EIP158 && value == 0，那么下一步的gas应该为：gas_left - call_op_gas_cost + (callGas + has_value * 2300)；(不考虑EIP158的分支)~~
两种情况：
1. 按照trace分析的话，下一个opcode应该是CALL的那个合约trace的first_step，此时depth + 1，那么此时的gas应该为：callGas + has_value * 2300；
2. 当call调用合约结束后的下一个opcode的gas应该为：gas_left - call_op_gas_cost + contract_called.gas --> contract_called.gas = callGas - contractB.gas_cost

注：从以上的公式中可以推出一个结果： CALL调用的bytecode最后一个状态应该是Return之类的值，其下一个opcode应该为CALL的同depth的下一个指令，此时有个关系： next_opcode_gas - Depth_plus_1.gas = CALL_gas_left - CALL_gas_cost，具体解释可以看下示例4。

memoryGas部分

计算函数

func memoryGasCost(mem *Memory, newMemSize uint64) (uint64, error)

newMemSize > 0x1FFFFFFFE0 ((2^32 - 1) * 32) 则ErrGasUintOverflow；
newMemSizeWords = (newMemSize + 31 ) / 32；
newMemSize = newMemSizeWords * 32，此时是32位对齐后的数；
如果newMemSize > mem.Len() ，也即大于当前memory，需要扩展：
1. square := newMemSizeWords * newMemSizeWords；
2. linCoef := newMemSizeWords * params.MemoryGas(3)；
3. quadCoef := square / params.QuadCoeffDiv(512);
4. newTotalFee := linCoef + quadCoef;
5. fee := newTotalFee - mem.lastGasCost;
6. mem.lastGasCost = newTotalFee;
7. 返回fee
否则返回0；

流程解析： 主要是fee := newTotalFee - mem.lastGasCost，其中mem.lastGasCost相当于上一次计算的newTotalFee。那么应该有：

newTotalFee - oldTotalFee
= (linCoef + quadCoef) - (oldLinCoef + oldQuadCoef)

= (linCoef - oldLinCoef) + (quadCoef - oldQuadCoef)

= (params.MemoryGas * newMemSizeWords - params.MemoryGas * oldMemSizeWords)
+ (newMemSizeWords * newMemSizeWords / params.QuadCoeffDiv - oldMemSizeWords * oldMemSizeWords / params.QuadCoeffDiv)

= params.MemoryGas * (newMemSizeWords - oldMemSizeWords) 
+ (newMemSizeWords * newMemSizeWords / params.QuadCoeffDiv - oldMemSizeWords * oldMemSizeWords / params.QuadCoeffDiv)

转化后的等式，只与memSizeWord有关。

newMemSize计算

取stack中的值：

stack[5] --> retOffset
stack[6] --> retLength
stack[3] --> argsOffset
stack[4] --> argsLength

max(retOffset + retLength, argsOffset + argsLength)

2.模拟示例

命令：

./evm --code 0x7f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000017f000000000000000000000000ffffffffffffffffffffffffffffffffffffffff7f0000000000000000000000000000000000000000000000000000000000000007f1 --debug --json run --debug --json run

全部为0

此时value == 0，没有memoryGas与callGas，并且是冷启动，所以为2600。

7f PUSH32 0000000000000000000000000000000000000000000000000000000000000000  -- retLength
7f PUSH32 0000000000000000000000000000000000000000000000000000000000000000  -- retOffset
7f PUSH32 0000000000000000000000000000000000000000000000000000000000000000  -- argsLength
7f PUSH32 0000000000000000000000000000000000000000000000000000000000000000  -- argsOffset
7f PUSH32 0000000000000000000000000000000000000000000000000000000000000000  -- value
7f PUSH32 000000000000000000000000ffffffffffffffffffffffffffffffffffffffff  -- addr
7f PUSH32 0000000000000000000000000000000000000000000000000000000000000000  -- gas
1f CALL

code = 0x7f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000007f000000000000000000000000ffffffffffffffffffffffffffffffffffffffff7f0000000000000000000000000000000000000000000000000000000000000000f1

stack gas != 0 ==> call gas != 0

由于gas == 7，所以callGas可以计算出来为2607；

7f PUSH32 0000000000000000000000000000000000000000000000000000000000000000  -- retLength
7f PUSH32 0000000000000000000000000000000000000000000000000000000000000000  -- retOffset
7f PUSH32 0000000000000000000000000000000000000000000000000000000000000000  -- argsLength
7f PUSH32 0000000000000000000000000000000000000000000000000000000000000000  -- argsOffset
7f PUSH32 0000000000000000000000000000000000000000000000000000000000000000  -- value
7f PUSH32 000000000000000000000000ffffffffffffffffffffffffffffffffffffffff  -- addr
7f PUSH32 0000000000000000000000000000000000000000000000000000000000000007  -- gas
f1 CALL

code = 0x7f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000007f000000000000000000000000ffffffffffffffffffffffffffffffffffffffff7f0000000000000000000000000000000000000000000000000000000000000007f1

value != 0 , address == 0

7f PUSH32 0000000000000000000000000000000000000000000000000000000000000000  -- retLength
7f PUSH32 0000000000000000000000000000000000000000000000000000000000000000  -- retOffset
7f PUSH32 0000000000000000000000000000000000000000000000000000000000000000  -- argsLength
7f PUSH32 0000000000000000000000000000000000000000000000000000000000000000  -- argsOffset
7f PUSH32 0000000000000000000000000000000000000000000000000000000000000001  -- value
7f PUSH32 000000000000000000000000ffffffffffffffffffffffffffffffffffffffff  -- addr
7f PUSH32 0000000000000000000000000000000000000000000000000000000000000007  -- gas
f1 CALL

code = 0x7f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000007f00000000000000000000000000000000000000000000000000000000000000017f000000000000000000000000ffffffffffffffffffffffffffffffffffffffff7f0000000000000000000000000000000000000000000000000000000000000007f1

trace打印：

{"pc":0,"op":127,"gas":"0x2540be400","gasCost":"0x3","memSize":0,"stack":[],"depth":1,"refund":0,"opName":"PUSH32"}
{"pc":33,"op":127,"gas":"0x2540be3fd","gasCost":"0x3","memSize":0,"stack":["0x0"],"depth":1,"refund":0,"opName":"PUSH32"}
{"pc":66,"op":127,"gas":"0x2540be3fa","gasCost":"0x3","memSize":0,"stack":["0x0","0x0"],"depth":1,"refund":0,"opName":"PUSH32"}
{"pc":99,"op":127,"gas":"0x2540be3f7","gasCost":"0x3","memSize":0,"stack":["0x0","0x0","0x0"],"depth":1,"refund":0,"opName":"PUSH32"}
{"pc":132,"op":127,"gas":"0x2540be3f4","gasCost":"0x3","memSize":0,"stack":["0x0","0x0","0x0","0x0"],"depth":1,"refund":0,"opName":"PUSH32"}
{"pc":165,"op":127,"gas":"0x2540be3f1","gasCost":"0x3","memSize":0,"stack":["0x0","0x0","0x0","0x0","0x1"],"depth":1,"refund":0,"opName":"PUSH32"}
{"pc":198,"op":127,"gas":"0x2540be3ee","gasCost":"0x3","memSize":0,"stack":["0x0","0x0","0x0","0x0","0x1","0xffffffffffffffffffffffffffffffffffffffff"],"depth":1,"refund":0,"opName":"PUSH32"}
{"pc":231,"op":241,"gas":"0x2540be3eb","gasCost":"0x8eff","memSize":0,"stack":["0x0","0x0","0x0","0x0","0x1","0xffffffffffffffffffffffffffffffffffffffff","0x7"],"depth":1,"refund":0,"opName":"CALL"}
{"pc":232,"op":0,"gas":"0x2540b5def","gasCost":"0x0","memSize":0,"stack":["0x0"],"depth":1,"refund":0,"opName":"STOP"}
{"output":"","gasUsed":"0x8611"}

gas cost = 36607 = 0x8eff

cold access = 2600；
value != 0 -> 9000;
addr == empty && value != 0 -> 25000;
callgas -> 7;

下一步的gas = 9999999979 - 36607 + (7 + 2300) = 0x2540B5DEF

address != 0, value == 0

[
  {
    "gas": 23639,
    "failed": false,
    "invalid": false,
    "returnValue": "",
    "structLogs": [
      {"pc": 0, "op": "PUSH32", "gas": 79000, "gasCost": 3, "depth": 1, "stack": []},
      {"pc": 33, "op": "PUSH32", "gas": 78997, "gasCost": 3, "depth": 1, "stack": ["0x0"]},
      {"pc": 66, "op": "PUSH32", "gas": 78994, "gasCost": 3, "depth": 1, "stack": ["0x0", "0x0"]},
      {"pc": 99, "op": "PUSH32", "gas": 78991, "gasCost": 3, "depth": 1, "stack": ["0x0", "0x0", "0x0"]},
      {"pc": 132, "op": "PUSH32", "gas": 78988, "gasCost": 3, "depth": 1, "stack": ["0x0", "0x0", "0x0", "0x0"]},
      {"pc": 165, "op": "PUSH32", "gas": 78985, "gasCost": 3, "depth": 1, "stack": ["0x0", "0x0", "0x0", "0x0", "0x0"]},
      {"pc": 198, "op": "PUSH32", "gas": 78982, "gasCost": 3, "depth": 1, "stack": ["0x0", "0x0", "0x0", "0x0", "0x0", "0xffffffffffffffffffffffffffffffffffffffff"]},
      {"pc": 231, "op": "CALL", "gas": 78979, "gasCost": 77786, "depth": 1, "stack": ["0x0", "0x0", "0x0", "0x0", "0x0", "0xffffffffffffffffffffffffffffffffffffffff", "0x186a0"]},
      {"pc": 0, "op": "PUSH1", "gas": 75186, "gasCost": 3, "depth": 2, "stack": []},
      {"pc": 2, "op": "PUSH1", "gas": 75183, "gasCost": 3, "depth": 2, "stack": ["0x0"]},
      {"pc": 4, "op": "RETURN", "gas": 75180, "gasCost": 0, "depth": 2, "stack": ["0x0", "0x0"]},
      {"pc": 232, "op": "PUSH32", "gas": 76373, "gasCost": 3, "depth": 1, "stack": ["0x1"]},
      {"pc": 265, "op": "PUSH32", "gas": 76370, "gasCost": 3, "depth": 1, "stack": ["0x1", "0x0"]},
      {"pc": 298, "op": "PUSH32", "gas": 76367, "gasCost": 3, "depth": 1, "stack": ["0x1", "0x0", "0x0"]},
      {"pc": 331, "op": "PUSH32", "gas": 76364, "gasCost": 3, "depth": 1, "stack": ["0x1", "0x0", "0x0", "0x0"]},
      {"pc": 364, "op": "RETURN", "gas": 76361, "gasCost": 0, "depth": 1, "stack": ["0x1", "0x0", "0x0", "0x0", "0x0"]}
    ]
  }
]

scroll ：

PUSH 32, "gas": 76373 - "RETURN", "gas": 75180 = 1193 == caller_gas_left
"RETURN", "gas": 75180 == gas_refund
next_step = gas_refund + caller_gas_left = 75180+1193 = 76373

gas_cost = 77786

is_warm == false, gas += 2600;
value == 0；
memoryGas == 0；
callGas：
- availableGas = 78979 - 2600 = 76379；
- callGas = 76379 - 76379/64 = 75186;

总的gasCost = 2600 + 0 + 0 + 75186 = 77786

下一步的gas，depth + 1 = 2， PC = 0：

gas = callGas = 75186;

CALL结束后的opcode gas，如上PC = 232：

returnedGas = (75186 - 6)
78979 - 77786 + (75186 - 6) = 76373；

PC = 232 与 PC = 4(depth = 2) Return 之间的差值关系满足： (PC=232 gas)76373 - (PC=2 gas)75180 = (gas in CALL OP) 78979 - (gas_cost in CALL OP) 77786 = 1193

PC = 232 时的gas：

cur_step_gas 
= CALL_OP_GAS - CALL_OP_GAS_COST + (CALL_FUNC_GAS - CONTRACT_B_ALL_GAS)
= CALL_OP_GAS - (BASE + MEMORY_GAS + CALL_FUNC_GAS) + (CALL_FUNC_GAS - CONTRACT_B_ALL_GAS)
= 78979 - (2600 + 0 + 75186) + (75186 - 6)
= 76373

prev_step_gas 
= CALL_FUNC_GAS - CONTRACT_B_ALL_GAS 
= 75186 - 6
= 75180 

prev_step_gas - cur_step_gas
= CALL_FUNC_GAS - CONTRACT_B_ALL_GAS - (CALL_OP_GAS - (BASE + MEMORY_GAS + CALL_FUNC_GAS) + (CALL_FUNC_GAS - CONTRACT_B_ALL_GAS))
= -CALL_OP_GAS + BASE + MEMORY_GAS + CALL_FUNC_GAS
= CALL_OP_GAS_COST - CALL_OP_GAS

address != 0, value == 0, memory != 0

[
  {
    "gas": 23654,
    "failed": false,
    "invalid": false,
    "returnValue": "",
    "structLogs": [
      {"pc": 0, "op": "PUSH32", "gas": 79000, "gasCost": 3, "depth": 1, "stack": []},
      {"pc": 33, "op": "PUSH32", "gas": 78997, "gasCost": 3, "depth": 1, "stack": ["0x4"]},
      {"pc": 66, "op": "PUSH32", "gas": 78994, "gasCost": 3, "depth": 1, "stack": ["0x4", "0xa4"]},
      {"pc": 99, "op": "PUSH32", "gas": 78991, "gasCost": 3, "depth": 1, "stack": ["0x4", "0xa4", "0x0"]},
      {"pc": 132, "op": "PUSH32", "gas": 78988, "gasCost": 3, "depth": 1, "stack": ["0x4", "0xa4", "0x0", "0x0"]},
      {"pc": 165, "op": "PUSH32", "gas": 78985, "gasCost": 3, "depth": 1, "stack": ["0x4", "0xa4", "0x0", "0x0", "0x0"]},
      {"pc": 198, "op": "PUSH32", "gas": 78982, "gasCost": 3, "depth": 1, "stack": ["0x4", "0xa4", "0x0", "0x0", "0x0", "0xffffffffffffffffffffffffffffffffffffffff"]},
      {"pc": 231, "op": "CALL", "gas": 78979, "gasCost": 77786, "depth": 1, "stack": ["0x4", "0xa4", "0x0", "0x0", "0x0", "0xffffffffffffffffffffffffffffffffffffffff", "0x186a0"]},
      {"pc": 0, "op": "PUSH1", "gas": 75168, "gasCost": 3, "depth": 2, "stack": []},
      {"pc": 2, "op": "STOP", "gas": 75165, "gasCost": 0, "depth": 2, "stack": ["0x1"]},
      {"pc": 232, "op": "PUSH32", "gas": 76358, "gasCost": 3, "depth": 1, "stack": ["0x1"]},
      {"pc": 265, "op": "PUSH32", "gas": 76355, "gasCost": 3, "depth": 1, "stack": ["0x1", "0x4"]},
      {"pc": 298, "op": "PUSH32", "gas": 76352, "gasCost": 3, "depth": 1, "stack": ["0x1", "0x4", "0xa4"]},
      {"pc": 331, "op": "PUSH32", "gas": 76349, "gasCost": 3, "depth": 1, "stack": ["0x1", "0x4", "0xa4", "0x0"]},
      {"pc": 364, "op": "RETURN", "gas": 76346, "gasCost": 0, "depth": 1, "stack": ["0x1", "0x4", "0xa4", "0x0", "0x0"]}
    ]
  }
]

CALL gas：78979 gasCost：77786

is_warm == false：2600
value == 0：0
memory = 0xa4 + 04 = 168 -> (168 + 31)/32 = 6 -> 3 * 6 = 18
availableGas = 78979 - 2600 - 18 = 76361, one_64th = 76361 / 64 = 1193
callGas = 76361 - 1193 = 75168

gasCost = 75168 + 18 + 2600 = 77786 next PUSH1 gas = 75168

3.设计

规划

实现CALL的约束主要分为两个大方向：

CALL指令与下一个指令之间的约束（包含了CALL本身gas计算）；
Return与下一个指令之间的约束；

两大方向细节

CALL指令与下一个指令之间的约束（包含了CALL本身gas计算）

CALL gas_cost计算
- is_warm * 2600 + (1 - is_warm) * 100 + has_value * (9000 + address.is_empty * 25000);
- memoryGas
- call_gas
CALL与下一个状态：
- address 不为空；
- address 为空；（todo）

Return与下一个指令之间的约束

利用 CALL_gas_left - CALL_gas_cost 计算出当前的gas；

变量

1.CALL指令计算

公式：

is_warm * 2600 + (1 - is_warm) * 100 + has_value * (9000 + address.is_empty * 25000)
- is_warm：已有的设计（key是address，理论上我们需要实现所有和is_warm相关的才能保证测试没问题）；
- has_value：value =？ zero；
- address.is_empty：EVM中定义这个状态是nonce、balance、code_hash = EmptyCodeHash。在我们的Account这个结构体中目前没有用到nonce、balance，不过我们对于account有is_empty()这个类型，可以直接用。；
memoryGas部分参考如下memory gas计算部分；
callGas计算部分:
- availableGas = availableGas - base: gas_left_before_exec - (上面两步计算的gas)；
- gas := availableGas - availableGas/64: 见如下u64_div_arithmetic设计；
- gas < gas_in_stack：MinMax方法，选择一个小的；gas_in_stack 不确定大小，要用lt算术电路
- gas_in_stack range U64：如果是U64，选择上一步的结果，如果不是，选择gas。
- 优化：gas_in_stack_is_u64 * min(gas, gas_in_stack) + (1 - gas_in_stack_is_u64) * gas

2.Call gas与下一个opcode的关联

我们目前只需要考虑address不为空的情况，所以下一个opcode的gas_left == callGas；

3.在code不为空的情况下，Return与下一个opcode之间的约束

参考‘Return后与下一个opcode之间的约束’小节。

4.实现

辅助电路实现

在实现CALL指令的GAS计算之前，我们需要设计两个电路结构，u64_div是算术电路的一部分，我们需要使用lookup约束，memoryGas计算为core电路的一种，具体功能如下介绍。

u64_div arithmetic设计

公式： a/b=c余d 输入： a,b 均为U64。 b一般为一个常数，例如32、64等。

需要满足条件：

b*c+d=a
d < b
a、b、c、d u64范围

分析：保证a,b,c在U64范围内。如果余数d小于除数b，那么就不需要额外考虑余数d的U64范围。

桂忠的memory整除32的实现中，会针对32专门优化：把余数用 5 个 0,1表示，这样就不需要额外使用减法约束d < b，也不需要额外对d进行U64约束。并且由于除数是固定值32，也不需要除数的U64约束。常量除法中由于除数不是固定值，只能保证是U64的，所以上述优化思路不太适用。

但是实际过程中余数d不需要额外的U64，只需要满足d < b即可。

约束：

b*c+d=a
d < b
a、b、c u64

表格：

cnt
1	lt				c_u16s(0..3)	diff(4..7)
0	a	b	c	d	a_u16s(0..3)	b_u16s(4..7)

Memory Gas计算

计算next_word_size，根据公式next_word_size = Max(cur_memory_size, memory_size)：
1. cur_memory_size是代表当前的内存大小，这个值已经完成了32位对齐
2. memory_size通常是根据opcode来计算，例如EXTCODECOPY，memory_size为offset+length，这个值未进行32位对其；
3. 利用memory_expansion的算术电路求得next_word_size，即完成公式MAX((memory_size + 31)/32, cur_memory_size)
计算curr_quad_memory_cost.quotient() = cur_memory_word_size * cur_memory_word_size / 512 = curr_quad_memory_cost:
1. 使用u64div的算术电路可轻松求解；
计算``next_quad_memory_cost.quotient() = next_memory_word_size * next_memory_word_size / 512 = next_quad_memory_cost`同上；
计算memory gas花费，gas cost = MEMORY_EXPANSION_LINEAR_COEFF(3) * (next_word_size - cur_memory_size) + (next_quad_memory_cost.quotient() - curr_quad_memory_cost.quotient())

完整流程实现

witness阶段

CALL指令较为复杂，由于其参数也很多，所以设计时，我们将其拆分为了多个电路，其顺序如下：

call_1 -> call_2 -> .. call_7 -> end_call -> post_call_1 -> post_call_2

具体的每个步骤可以参考call op的文档，这里我们主要介绍与gas相关的几个状态：

call_4为memory gas计算；
call_5为call op整个过程需要的gas（同时会约束CALL指令与下一个opcode之间的gas）；
call_6用于写入trace中call op的gas相关的上下文；
call_7为完成call指令所需变量的上下文（与gas无关）；
post_call_1用于读取上下文中trace里的call op gas相关的数据（同时会约束return与下一个opcode之间的gas）；
post_call_2 为结束call状态的最终处理状态；

以下为相关的状态对应的layout：

CALL_4 (Memory Gas layout)

cnt
2	U64DIV(2..6)	MEMORY_EXPANSION(7..11)	MEMORY_EXPANSION(12..16)	U64DIV(17..21)	U64DIV(22..26)	args_len_inv(27)	ret_len_inv(28)
1	STATE0(0..7)	STATE1(8..15)	STATE2(16..23)	STATE3(24..31)
0	DYNAMIC(0..17)	AUX(18..24)	STATE_STAMP_INIT(24)	MEMORY_GAS(26)

CALL_5 (GAS layout)

cnt
3	STORAGE_READ(0..11)	STORAGE_WRITE(12..23)	value_inv(24)
2	U64_DIV(2..6)	U64_OVERFLOW(7..11)	U64_OVERFLOW(12..16)	memory_expansion(17..21)
1	STATE0(0..7)	STATE1(8..15)	STATE2(16..23)
0	dynamic(0..17)	AUX(18..24)

CALL_6 (call context write layout)

cnt
1	CALLCONTEXT_WRITE_0	CALLCONTEXT_WRITE_1
0	DYNA_SELECTOR	AUX	STAMP_INIT (25)

POST_CALL_1(call context read layout)

cnt
1	CALLCONTEXT_READ_0	CALLCONTEXT_READ_1
0	DYNA_SELECTOR	AUX	RETURN_SUCCESS (25)	RETURNDATA_SIZE (27)
在上述流程中，我们可以大致把整个流程划分为几个阶段，并完成对应的预处理：

CALL1-4：此时gas_left == trace.gas，这是因为call4才开始进行gas的计算，由于我们在预处理时，为了尽可能通用处理，我们将call op的gas_left设置为了下一个opcode的gas，所以在call1-4我们需要略作处理，将其恢复为trace op中的call gas_left；
CALL5-7: 此时已经完成了gas计算，我们此时gas_left为CALL OP下一个OP的gas_left，因此在约束时可以轻易设计为当前的gas_left == call_func_gas;
POST_CALL_1 - 2: POST_CALL_X状态此时gas_left为return下一个opcode，上一个END_CALL状态对应的gas_left就应该为RETURN时的gas_left；

constraints阶段

memory gas计算我们上文已经提到，因此首先为call的整体gas计算和约束，也即CALL_5，基本逻辑和EVM一样，区别为实现方式，在我们上述的前置都做好后，实现约束也变得更为简单，这里罗列几个核心代码，更为详细的，可以参考代码：

let call_gas = select::expr(
    gas_in_stack_not_overflow.expr(),
    capped_gas_left_in_table,
    all_but_one_64th_gas,
);
let base_gas = select::expr(
    is_warm,
    GasCost::WARM_ACCESS.expr(),
    GasCost::COLD_ACCOUNT_ACCESS.expr(),
) + (1.expr() - value_is_zero.expr())
    * (GasCost::CALL_WITH_VALUE.expr()
    // todo 暂时还没实现account为空的情况，用0来代替，我们目前account都不会为空
    +  0.expr() * GasCost::NEW_ACCOUNT.expr());

let memory_gas_cost = meta.query_advice(
    config.vers[NUM_STATE_HI_COL
        + NUM_STATE_LO_COL
        + NUM_AUXILIARY
        + NEW_MEMORY_SIZE_OR_GAS_COST_IDX],
    Rotation(-1 * NUM_ROW as i32),
);
let gas_cost = base_gas.clone() + memory_gas_cost.clone() + call_gas.clone();

CALL_5的GAS约束：

let delta = AuxiliaryOutcome {
    gas_left: ExpressionOutcome::To(call_gas),
    ..Default::default()
};

POST_CALL_1负责RETURN与下一个opcode之间的约束（前文提到过，我们目前实现的方案是假设子合约一定存在，因此会正常走到RETURN）

// prev_step_gas - cur_step_gas = CALL_OP_GAS_COST - CALL_OP_GAS
let gas_cost = operands[1].clone() - operands[0].clone();

// auxiliary constraints
let delta = AuxiliaryOutcome {
    gas_left: ExpressionOutcome::Delta(-gas_cost.expr()),
    ..Default::default()
};

除了上述两个状态，其余的gas_left均满足Delta(0.expr())。

四、COPY GAS实现

1.前言

基于前面memoryGas的实现之后，发现可以设置memoryGasCost作为中间状态作为计算gas的桥梁，从而避免大量重复代码。基本思路如下，CODECOPY示例：

opcode	vers_26
CODECOPY	newMemorySize
MEMORY_GAS	memory gas cost

CODECOPY在vers_26预留位置newMemorySize，MEMORY_GAS_COST计算时使用 -1 * NUM_ROW获取newMemorySize，后续计算gas时如果需要memoryGas，在vers_26取memory gas cost，其他opcode同理。注：当前memoryGas计算newMemorySize的计算是从stack里取的，也即某个opcode的input。

由于CALLDATACOPY, CODECOPY, MCOPY, EXTCODECOPY, RETURNDATACOPY 在EVM中gas计算的逻辑是一样的，区别仅在于对应opcode参数中length位置不同，所以考虑将这几个opcode一起实现和设计。

EVM中该段代码如下：

// CALLDATACOPY (stack position 2)
// CODECOPY (stack position 2)
// MCOPY (stack position 2)
// EXTCODECOPY (stack position 3)
// RETURNDATACOPY (stack position 2)
func memoryCopierGas(stackpos int) gasFunc {  
    return func(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memorySize uint64) (uint64, error) {  
       // Gas for expanding the memory  
       gas, err := memoryGasCost(mem, memorySize)  
       if err != nil {  
          return 0, err  
       }  
       // And gas for copying data, charged per word at param.CopyGas  
       words, overflow := stack.Back(stackpos).Uint64WithOverflow()  
       if overflow {  
          return 0, ErrGasUintOverflow  
       }  
  
       if words, overflow = math.SafeMul(toWordSize(words), params.CopyGas); overflow {  
          return 0, ErrGasUintOverflow  
       }  
  
       if gas, overflow = math.SafeAdd(gas, words); overflow {  
          return 0, ErrGasUintOverflow  
       }  
       return gas, nil  
    }  
}

2.设计方案

具体方案

newMemorySize的计算，这几种copy基本类似，MCOPY多了一个比较，但都比较简单，也即当只需要判断length是否为0，如果为0，则newMemorySize为0，否则为length+offset。
MEMORY_GAS_COST对post_call_memory_gas稍作改动后即可复用。
MEMORY_COPIER_GAS为 memory_gas_cost + word * copyGas，其中word：
1. word是stack(index)的32位对齐，也即不同opcode参数中的length；
2. word使用u64div计算即可，可以直接约束传参为U64；
3. 最后的gas_left使用U64Overflow进行约束。
除 gas 计算以外的其他约束：
CODECOPY 后一个状态是MEMORY_GAS。
MEMORY_GAS 需按照需求约束前后状态。
MEMORY_COPIER_GAS应该约束只由 CALLDATACOPY, CODECOPY, MCOPY, EXTCODECOPY, RETURNDATACOPY 调用，即 opcodeID 约束，并且前一个状态需要是MEMORY_GAS_COST。

MEMORY_GAS layout:

Memory
cnt
1	MEMORY_EXPANSION(2..6)	U64DIV(7..11)	U64DIV(12..16)
0	DYNAMIC(0..17)	AUX(18..24)		MEMORY_GAS(26)

MEMORY_COPIER_GAS layout：

cnt
1	U64DIV	U64OVERFLOW	is_extcodecopy (31)
0	DYNAMIC(0..17)	AUX(18..24)

Extcodecopy

Extcodecopy 在 EIP2929 之后使用了 is_warm 来计算 gas 费用，go-ethereum 代码如下：

func gasExtCodeCopyEIP2929(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memorySize uint64) (uint64, error) {  
    // memory expansion first (dynamic part of pre-2929 implementation)  
    gas, err := gasExtCodeCopy(evm, contract, stack, mem, memorySize)  
    if err != nil {  
       return 0, err  
    }  
    addr := common.Address(stack.peek().Bytes20())  
    // Check slot presence in the access list  
    if !evm.StateDB.AddressInAccessList(addr) {  
       evm.StateDB.AddAddressToAccessList(addr)  
       var overflow bool  
       // We charge (cold-warm), since 'warm' is already charged as constantGas  
       if gas, overflow = math.SafeAdd(gas, params.ColdAccountAccessCostEIP2929-params.WarmStorageReadCostEIP2929); overflow {  
          return 0, ErrGasUintOverflow  
       }  
       return gas, nil  
    }  
    return gas, nil  
}

其中 gasExtCodeCopy 部分与其他都是相同的，区别在于后续的流程。由于 is_warm 的计算和 gasExtCodeCopy 是相互独立的，因此可以考虑在 extcodecopy 这个状态时提前计算出 is_warm gas 花费，在 memory_copier_gas 时直接引用即可。

extcodecopy layout：

cnt
4	STORAGE_READ (0.. 11)	STORAGE_WRITE(12.. 23)
3	LENGTH(9)		PUB_CODE_SIZE(6)
2	COPY	ZEROCOPY	OVER_ARITH(5)	EXP_ARITH(5)
1	STATE0	STATE1	STATE2	STATE3
0	DYNA_SELECTOR	AUX	LENGTH_INV(25)	OFFSET_BOUND (26)	MEMORY_CHUNK_PREV (27)	SIZE(28)	WARM_GAS (29)

五、EXP, EXTCODESIZES GAS 实现

1.EVM 实现

EXP

exp 流程比较简单，代码如下：

func gasExpEIP158(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memorySize uint64) (uint64, error) {  
    expByteLen := uint64((stack.data[stack.len()-2].BitLen() + 7) / 8)  
  
    var (  
       gas      = expByteLen * params.ExpByteEIP158 // no overflow check required. Max is 256 * ExpByte gas  
       overflow bool  
    )  
    if gas, overflow = math.SafeAdd(gas, params.ExpGas); overflow {  
       return 0, ErrGasUintOverflow  
    }  
    return gas, nil  
}

主要是 expByteLen 的求解。

EXTCODESIZE

func gasEip2929AccountCheck(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memorySize uint64) (uint64, error) {  
    addr := common.Address(stack.peek().Bytes20())  
    // Check slot presence in the access list  
    if !evm.StateDB.AddressInAccessList(addr) {  
       // If the caller cannot afford the cost, this change will be rolled back  
       evm.StateDB.AddAddressToAccessList(addr)  
       // The warm storage read cost is already charged as constantGas  
       return params.ColdAccountAccessCostEIP2929 - params.WarmStorageReadCostEIP2929, nil  
    }  
    return 0, nil  
}

只与 is_warm 有关

2.设计

核心思想：使用 bitwise 来实现 byteLen 的求解，对于一个 U256 的数，只需要两次 bitwise 的 lookup。举例：指数：34369217034 二进制：00001000 00000000 10010000 10100010 00001010 最高有效字节数：5 以低 128 位，填充 witness，高 11 字节全为 0，后 5 个字节为有效字节。

tag	byte_0	byte_1	acc_0	acc_2	cnt	acc_2_not_zero	index
OR	zero	zero	zero		0	0	0
OR	zero	zero	zero		1	0	0
OR	zero	zero	zero		2	0	0
OR	zero	zero	zero		3	0	0
OR	zero	zero	zero		4	0	0
OR	zero	zero	zero		5	0	0
OR	zero	zero	zero		6	0	0
OR	zero	zero	zero		7	0	0
OR	zero	zero	zero		8	0	0
OR	zero	zero	zero		9	0	0
OR	zero	zero	zero	zero	10	0	0
OR	00001000	zero	00001000	00001000	11	1	5
OR	00000000	zero	00001000 00000000	00001000 00000000	12	1	5
OR	10010000	zero	10010000 00001000 00000000	10010000 00001000 00000000	13	1	5
OR	10100010	zero	10010000 00001000 00000000 10100010	10010000 00001000 00000000 10100010	14	1	5
OR	00001010	zero	10010000 00001000 00000000 10100010 00001010	10010000 00001000 00000000 10100010 00001010	15	1	5

not_is_zero ：acc_2 不为 0 时设置为 1； index：最高有效字节下标； index 计算规则（witness）：

cnt == 0：
1. not_is_zero == 0, index = 0；
2. not_is_zero == 1, index = 16 - cnt = 16;
cnt != 0，设 prev_not_is_zero = [not_is_zero, Rotation (-1)], cur_not_is_zero = [not_is_zero, Rotation (0)] :
1. 如果 prev_not_is_zero == cur_not_is_zero，则 index = prev_index;
2. 如果 prev_not_is_zero != cur_not_is_zero，则 index = 16 - cnt；

特殊的例子：如果 not_is_zero 全是 0，那么 index 一列全是 0，最高有效字节是 0，如果 not_is_zero 全是 1，那么 index 全是 16，最高有效字节全是 16。 index 约束：

/// cnt == 0时，index 只有两个选项
index = select::expr(not_is_zero, 16.expr(), 0.expr())
cnt_is_zero * (index_in_table - index);
/// cnt != 0时，cur_not_is_zero-prev_not_is_zero只会为0或1,0时相等，1时不相等
index = select::expr(cur_not_is_zero-prev_not_is_zero, 16.expr()-cnt, prev_index);
(1 - cnt_is_zero) * (index_in_table - index)

六、Return, Revert, MLoad, MStore, MStore8 GAS实现

1.EVM

在 EVM 中，这些 gas 计算都是一致的，就是调用的 memoryGasCost，相关代码：

var (  
    gasReturn  = pureMemoryGascost  
    gasRevert  = pureMemoryGascost  
    gasMLoad   = pureMemoryGascost  
    gasMStore8 = pureMemoryGascost  
    gasMStore  = pureMemoryGascost  
    gasCreate  = pureMemoryGascost  
)

func pureMemoryGascost(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memorySize uint64) (uint64, error) {  
    return memoryGasCost(mem, memorySize)  
}

Return, Revert memorySize

参数： 0. offset

length

计算：length_not_zero * (offset + length)

func memoryReturn(stack *Stack) (uint64, bool) {  
    return calcMemSize64(stack.Back(0), stack.Back(1))  
}

MLoad memorySize

参数： 0. offset

计算: offset+32

func memoryMLoad(stack *Stack) (uint64, bool) {  
    return calcMemSize64WithUint(stack.Back(0), 32)  
}

Mstore memorySize

参数： 0. offset

计算: offset+32

func memoryMStore(stack *Stack) (uint64, bool) {  
    return calcMemSize64WithUint(stack.Back(0), 32)  
}

MStore8 memorySize

参数： 0. offset

计算: offset+1

func memoryMStore8(stack *Stack) (uint64, bool) {  
    return calcMemSize64WithUint(stack.Back(0), 1)  
}

2.设计

在这之前，因为我们的 memoryGasCost 已经实现完成（在 COPY 一节已经实现），需要使用 memoryGas 以及一个通用的状态来约束最后的 gas_left。

Return，Revert 下一个状态目前是 END_CALL，所以修改后的状态顺序应该为：Return/Revert -> MemoryGas -> PureMemoryGasCost -> EndCall -> POST_CALL_1/END_TX。在 Return，Revert 中，下一个状态 PC 是不变的，对于其他指令，PC 会+1。

在 memoryGas 计算过程中需要做区分，只有 Return，Revert，MLoad，MStore， MStore8，下一个状态才是 PureMemoryGasCost。

PureMemoryGascost 主要是完成 gas_left 的约束以及与下一个 opcode 之间的约束。

七、LOG0-4 GAS实现

1.EVM

代码如下：

func makeGasLog(n uint64) gasFunc {  
    return func(evm *EVM, contract *Contract, stack *Stack, mem *Memory, memorySize uint64) (uint64, error) {  
       // 长度 length       
       requestedSize, overflow := stack.Back(1).Uint64WithOverflow()  
       if overflow {  
          return 0, ErrGasUintOverflow  
       }  
  
       // mem扩展需要的gas  
       gas, err := memoryGasCost(mem, memorySize)  
       if err != nil {  
          return 0, err  
       }  
  
       // log操作固定的gas  
       if gas, overflow = math.SafeAdd(gas, params.LogGas); overflow {  
          return 0, ErrGasUintOverflow  
       }  
       // log操作的topic数量 * topic的gas  
       if gas, overflow = math.SafeAdd(gas, n*params.LogTopicGas); overflow {  
          return 0, ErrGasUintOverflow  
       }  
  
       var memorySizeGas uint64  
       // 数据gas  
       // length * 8 U64 range check       
       if memorySizeGas, overflow = math.SafeMul(requestedSize, params.LogDataGas); overflow {  
          return 0, ErrGasUintOverflow  
       }
       if gas, overflow = math.SafeAdd(gas, memorySizeGas); overflow {  
          return 0, ErrGasUintOverflow  
       }
       return gas, nil  
    }  
}

分析：

requestedSize, overflow := stack.Back(1).Uint64WithOverflow()：stack 中的 length。
gas, err := memoryGasCost(mem, memorySize)：memorySize 还是 length_not_zero*(offset+length)，memoryGas 的计算可以使用 memoryGasCost 状态；
gas, overflow = math.SafeAdd(gas, params.LogGas)：加一个常量值；
gas, overflow = math.SafeAdd(gas, n*params.LogTopicGas)：n 是代表 LOGX，其中我们可以使用 selector 来求解这个 n 是多少；
memorySizeGas, overflow = math.SafeMul(requestedSize, params.LogDataGas)：length * 常量；
gas, overflow = math.SafeAdd(gas, memorySizeGas)：最终得到 gas + memoryGas 。

2.设计

LOG0-4 必有的状态为 LOG_BYTES, LOG_TIPIC_NUM_ADDR。

我们可以选择在这两个状态中间进行插入 MEMORY_GAS_COST, LOG_GAS 这两个状态，这样插入的好处是：

避免 stack 中的 length 不断向下传递的情况；
LOG_BYTES 时没有需要特殊处理并向下传递的值，因此插入中间状态时也不需要额外做特殊处理。

最终的执行状态：LOG_BYTES -> MEMORY_GAS -> LOG_GAS -> LOG_TIPIC_NUM_ADDR -> LOG_TOPIC ...

八、常量GAS实现

除上述特殊的GAS实现以外，其他的OPCODE几乎都是常量的GAS花费，即GAS值固定，此时我们可以通过AUX约束来完成DELTA之间的约束，即满足类似如下等式： prev_step_gas - cur_step_gas = opcode_constant_gas

core gas

一、基础GAS扣费实现

1.EVM实现

code

流程

2.设计

constraints变量获取

layout

二、STORAGE GAS实现

1.SSTORE EVM 实现(EIP-3529)

2.EIP-2929

冷装载（Cold Load）

热存储读取（Warm Storage Read）

实际影响

3.设计

预处理：

layout

constraints

其他辅助约束

三、CALL GAS实现

1.EVM（EIP2929）

call gas计算

call gas 与 下一个opcode之间的关联(opCall)

memoryGas部分

计算函数

newMemSize计算

2.模拟示例

全部为0

stack gas != 0 ==> call gas != 0

value != 0 , address == 0

address != 0, value == 0

address != 0, value == 0, memory != 0

3.设计

规划

两大方向细节

变量

4.实现

辅助电路实现

完整流程实现

四、COPY GAS实现

1.前言

2.设计方案

具体方案

Extcodecopy

五、EXP, EXTCODESIZES GAS 实现

1.EVM 实现

EXP

EXTCODESIZE

2.设计

六、Return, Revert, MLoad, MStore, MStore8 GAS实现

1.EVM

Return, Revert memorySize

MLoad memorySize

Mstore memorySize

MStore8 memorySize

2.设计

七、LOG0-4 GAS实现

1.EVM

2.设计

八、常量GAS实现

call gas 与下一个opcode之间的关联(opCall)