ADDMOD 指令

详细设计

概述

概述：加法取模指令，对栈中的两个值进行加法取模计算（此操作的所有中间计算不受2^256模的限制）。

具体操作：从栈顶弹出三个值a,b和n，对a，b进行整数加法再对n取模，将结果存进栈。

trace示例：

// Example 1
// Result 4  //0x4
PUSH1 8  //0x8
PUSH1 10  //0xA
PUSH1 10  //0xA
ADDMOD  //0x2

// Example 2 
// Result 1 //0x01
PUSH1 2  //0x2
PUSH1 2  //0x2
PUSH32 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
ADDMOD

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

示例具体操作流程如下：

初始状态：

• 栈内容：[a, b, n]
• 其中，a 和 b 是要进行加法的256位整数，n 是取模的值。a 在栈顶，b 在栈顶下方，n 在栈底。

操作步骤：

1. 弹出值：从栈中弹出三个值 a, b, 和 n。此时栈变为空。
2. 计算：
   • 执行加法操作：sum = a + b
   • 对结果 sum 进行取模操作：result = sum % n
   • 这个操作确保结果始终保持在 n 范围内。
3. 推入结果：将计算得到的结果 result 推入栈中。

最终状态：

• 栈内容：[result]

Witness Core Row

core row中的表格设计如下：

cnt	ver[0-7]	ver[8-15]	ver[16-23]	ver[24-31]	其他
2	ARITH	-	-	-	-
1	STATE (stack_pop_a)	STATE (stack_pop_b)	STATE (stack_pop_n)	STATE (stack_push)	-
0	DYNA_SELECTOR	AUX	-	-	-

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

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

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

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

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

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

tag	operand_a_hi	operand_a_lo	operand_b_hi	operand_b_lo	operand_n_hi	operand_n_lo	result_hi	result_lo
ADDMOD	0x00	0xA	0x00	0xA	0x00	0x08	0x00	0x04
ADDMOD	0x00	0x02	0x00	0x02	0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF	0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF	0x00	0x01

各个字段的含义如下：

• tag：表示算术操作的类型，如 ADDMOD。
• operand_a_hi：操作数 A 的高位部分。
• operand_a_lo：操作数 A 的低位部分。
• operand_b_hi：操作数 B 的高位部分。
• operand_b_lo：操作数 B 的低位部分。
• operand_n_hi：操作数 N 的高位部分。
• operand_n_lo：操作数 N 的低位部分。
• result_hi：结果的高位部分。
• result_lo：结果的低位部分。

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

在上面的示例中：

• 第一个条目表示 10 + 10 = 20，20 % 8 = 4。
• 第二个条目表示 2 + 2 = 4，4 % (2^256 - 1) = 1。

门约束

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_n = lookup_stack_pop_n
   • arithmetic_operand_push = lookup_stack_push

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

4. 当前的OPCODE=ADDMOD

5. arithmetic tag = ADDMOD

参考如下代码：

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..4 {
        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 == 3,
        ));
        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 operands (0..8)
    constraints.extend((0..8).map(|i| {
        (
            format!("operand[{}] in arithmetic = in state lookup", i),
            arithmetic_operands[i].clone() - arithmetic_operands_full[i].clone(),
        )
    }));

    // 其它约束 ...
    constraints
}

Lookup约束

get_lookups

这里的5个lookup, 类型为LookupEntry::State和LookupEntry::Arithmetic, 具体可以参考：

• 5-state
• 8-arithmetic