Skip to content

GitLab

  • Projects
  • Groups
  • Snippets
  • Help
    • Loading...
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Sign in / Register
zkevm-circuits
zkevm-circuits
  • Project overview
    • Project overview
    • Details
    • Activity
    • Releases
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
  • Issues 0
    • Issues 0
    • List
    • Boards
    • Labels
    • Service Desk
    • Milestones
  • Merge Requests 0
    • Merge Requests 0
  • CI / CD
    • CI / CD
    • Pipelines
    • Jobs
    • Schedules
  • Operations
    • Operations
    • Incidents
    • Environments
  • Packages & Registries
    • Packages & Registries
    • Package Registry
  • Analytics
    • Analytics
    • CI / CD
    • Repository
    • Value Stream
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Members
    • Members
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar

新注册的用户请输入邮箱并保存,随后登录邮箱激活账号。后续可直接使用邮箱登录!

  • zkp
  • zkevm-circuitszkevm-circuits
  • Wiki
    • Zkevm docs
    • 4 core
  • core addmod

Last edited by geruiwang 9 months ago
Page history

core addmod

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
Clone repository
  • basics
    • evm
    • halo2
  • code notes
    • binary_number_with_real_selector
    • how to use macro
    • simple_lt
    • simple_lt_word
  • Home
  • image
  • zkevm docs
    • 1 introduction
    • 10 public
    • 11 fixed
    • 12 exp
    • 13 keccak
    • 14 comparisons
    • 15 differences
View All Pages

Copyright © 2024 ChainWeaver Org. All Rights Reserved. 版权所有。

京ICP备2023035722号-3

京公网安备 11010802044225号