ADD

本节和接下来的章节主要介绍 EVM中各个指令的具体操作、约束条件和 witness 表示，以及如何在电路设计中实现和验证相关指令。

概述

概述：加法指令，对栈中的两个值进行加法计算（256位）。

具体操作：从栈顶弹出两个值a和b，进行整数加法（mod 2^256），将结果存进栈。

trace示例：

// Example 1 
// Result 20 //0x14
PUSH1 10 //0x10
PUSH1 10 //0x10
ADD

// Example 2
// Result 0x0
PUSH32 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
PUSH1 1 //0x01
ADD

由于在evm中ADD指令会自动从栈中弹出两个操作数并将结果推入栈中，所以在trace中没有显式的POP操作。

示例具体操作流程如下：

初始状态：

• 栈内容：[a, b]
• 其中，a 和 b 是256位整数，a 在栈顶，b 在栈顶下方。

操作步骤：

• 弹出值：从栈中弹出两个值 a 和 b。此时栈变为空。
• 计算：执行加法操作：result = (a + b) % 2^256。这个操作确保结果始终保持在256位整数范围内。
• 推入结果：将计算得到的结果 result 推入栈中。

最终状态：

• 栈内容：[result]

Witness Core Row

core row中的表格设计如下：

cnt=2，vers[0]~vers[8]的位置用来存放arithmetic table lookup；

cnt=1，vers[0]~vers[7]的位置用来存放栈顶弹出的值stack_pop_a；

cnt=1，vers[8]~vers[15]的位置用来存放栈顶弹出的值stack_pop_b；

cnt=1，vers[16]~vers[23]的位置用来存进栈顶的值stack_push。

DYNA_SELECTOR 和 AUX 部分可能存储动态选择器和辅助信息，但在这个具体表格中未被使用。

其中，对于 ADD 操作，给出的算术表查找ARITH的具体值可以如下：

各个字段的含义如下：

• tag：表示算术操作的类型，如 ADD、SUB 等。
• operand_a_hi：操作数 A 的高位部分。
• operand_a_lo：操作数 A 的低位部分。
• operand_b_hi：操作数 B 的高位部分。
• operand_b_lo：操作数 B 的低位部分。
• result_hi：结果的高位部分。
• result_lo：结果的低位部分。
• unused : 没有使用的部分

这些字段可以用来存储 256 位数值的高 128 位和低 128 位。

在上面的示例中：

• 第一个条目表示 10 + 10 = 20。
• 第二个条目表示最大值加 1，结果回到 0（因为是模 2^256 运算）。

门约束

1. Auxiliary字段约束：

   这些约束用于辅助字段，如 state_stamp、stack_pointer、log_stamp 和 read_only，确保这些字段在操作期间保持一致。

2. Stack Value约束：

   这些约束用于栈的值，包括以下内容：

   • tag
   • state_stamp
   • call_id
   • stack_pointer
   • is_write

3. lookup_value约束：

   这些约束确保算术操作数和栈操作的值一致。具体来说：

   • arithmetic_operand_a = lookup_stack_pop_a
   • arithmetic_operand_b = lookup_stack_pop_b
   • arithmetic_operand_push = lookup_stack_push

   这些约束对操作数的高位 (hi) 和低位 (lo) 进行约束，并确保它们与状态查找中的值相等。

4. 当前的OPCODE=ADD

5. arithmetic tag = ADD

参考如下代码：

fn get_constraints(
    &self,
    config: &ExecutionConfig<F, NUM_STATE_HI_COL, NUM_STATE_LO_COL>,
    meta: &mut VirtualCells<F>,
) -> Vec<(String, Expression<F>)> {
    let opcode = meta.query_advice(config.opcode, Rotation::cur());
    // Auxiliary字段约束 ...

    // Stack Value约束 ...

    let mut arithmetic_operands = vec![];
    for i in 0..3 {
        let entry = config.get_state_lookup(meta, i);
        constraints.append(&mut config.get_stack_constraints(
            meta,
            entry.clone(),
            i,
            NUM_ROW,
            if i == 0 { 0 } else { -1 }.expr(),
            i == 2,
        ));
        let (_, _, value_hi, value_lo, _, _, _, _) = extract_lookup_expression!(state, entry);
        arithmetic_operands.extend([value_hi, value_lo]);
    }
    
    let (tag, arithmetic_operands_full) =
        extract_lookup_expression!(arithmetic, config.get_arithmetic_lookup(meta));
    // iterate over three operands (0..6), since we don't need constraint on the fourth
    constraints.extend((0..6).map(|i| {
        (
            format!("operand[{}] in arithmetic = in state lookup", i),
            arithmetic_operands[i].clone() - arithmetic_operands_full[i].clone(),
        )
    }));

    // 其它约束 ...
    constraints
}

LookUp约束

get_lookups

这里的四个lookup, 类型为LookupEntry::State和LookupEntry::Arithmetic, 具体可以参考Witness Core Row部分的说明。

参考代码如下:

fn get_lookups(
    &self,
    config: &ExecutionConfig<F, NUM_STATE_HI_COL, NUM_STATE_LO_COL>,
    meta: &mut ConstraintSystem<F>,
) -> Vec<(String, LookupEntry<F>)> {
    let stack_lookup_0 = query_expression(meta, |meta| config.get_state_lookup(meta, 0));
    let stack_lookup_1 = query_expression(meta, |meta| config.get_state_lookup(meta, 1));
    let stack_lookup_2 = query_expression(meta, |meta| config.get_state_lookup(meta, 2));
    let arithmetic = query_expression(meta, |meta| config.get_arithmetic_lookup(meta));
    vec![
        ("stack pop a".into(), stack_lookup_0),
        ("stack pop b".into(), stack_lookup_1),
        ("stack push".into(), stack_lookup_2),
        ("arithmetic lookup".into(), arithmetic),
    ]
}


pub(crate) fn get_arithmetic_lookup(&self, meta: &mut VirtualCells<F>) -> LookupEntry<F> {
    let (hi_0, lo_0, hi_1, lo_1, hi_2, lo_2, hi_3, lo_3, tag) = (
        meta.query_advice(self.vers[0], Rotation(-2)),
        meta.query_advice(self.vers[1], Rotation(-2)),
        meta.query_advice(self.vers[2], Rotation(-2)),
        meta.query_advice(self.vers[3], Rotation(-2)),
        meta.query_advice(self.vers[4], Rotation(-2)),
        meta.query_advice(self.vers[5], Rotation(-2)),
        meta.query_advice(self.vers[6], Rotation(-2)),
        meta.query_advice(self.vers[7], Rotation(-2)),
        meta.query_advice(self.vers[8], Rotation(-2)),
    );
    LookupEntry::Arithmetic {
        tag,
        values: [hi_0, lo_0, hi_1, lo_1, hi_2, lo_2, hi_3, lo_3],
    }
}