1. 算术操作

1.1 操作指令

mul： 验证二元乘法操作，例如 $a \times b = c$，适用于简单的两输入一输出乘法。 mult： 验证多输入或复杂乘法操作，处理更高精度或特殊情况的乘法。 addcy： 验证带进位的加法操作，例如 $a + b + carry = c$，用于多字长加法或高精度计算。 slt： 验证小于比较操作 $a < b$，通常用于条件分支或逻辑判断。 lui： 验证加载高位立即数操作，将立即数加载到寄存器的高位，例如 $reg = imm << 16$。 div： 验证二元除法操作 $a \div b = c$，同时可能处理余数，确保除法合法性。 shift： 验证逻辑移位操作，包括左移或右移，例如 $a << b$ 或 $a >> b$。 sra： 验证算术右移操作，保留符号位（Sign Bit），用于有符号数处理。 lo_hi： 验证高低位分解或合并操作，例如高位 $(a >> 16)$ 和低位 $(a \& 0xFFFF)$。

1.2 运行流程

算术操作主要包括以下操作：

Step 1: 初始化算术表（Arithmetic Table）

Step 2: 生成 Trace 数据

Step 3: 验证范围检查（Range Checks）

Step 4: 验证约束条件（Constraints Evaluation）

Step 5: 电路级验证（Ext Circuit Evaluation）

1.2.1 Step 1: 初始化算术表

初始化算术表的结构，包括对列的映射（如操作数、操作类型、结果等），并将其与 CPU 表中的字段进行数据链接。

1. 定义算术操作的类型与操作码：
   • 通过 COMBINED_OPS 数组定义 26 种算术操作及其对应的列和操作码，例如：
     • columns::IS_ADD 表示加法操作，其操作码为 0b100000。
     • 操作码采用 MIPS 指令集的二进制编码。
2. 定义寄存器映射：
   • REGISTER_MAP 包含三个寄存器范围：
     • INPUT_REGISTER_0 和 INPUT_REGISTER_1 分别存储两个输入操作数。
     • OUTPUT_REGISTER 用于存储运算结果。
3. 生成过滤器：
   • 使用 Filter::new_simple 创建过滤器，标记有效的算术操作行。
   • 只有当前行属于 COMBINED_OPS 中定义的算术操作时，过滤器才会激活。
4. 链接算术表和 CPU 表：
   • 调用 cpu_arith_data_link 方法，将算术表的列（如寄存器和操作数）与 CPU 表中对应的字段链接。

代码模块：

pub fn ctl_arithmetic_rows<F: Field>() -> TableWithColumns<F> {
    const COMBINED_OPS: [(usize, u32); 26] = [
        // 映射算术操作和对应的操作码（opcode）。
        (columns::IS_ADD, 0b100000 * (1 << 6)),
        (columns::IS_ADDU, 0b100001 * (1 << 6)),
        (columns::IS_ADDI, 0b001000),
        // ... 省略部分 ...
    ];

    const REGISTER_MAP: [Range<usize>; 3] = [
        columns::INPUT_REGISTER_0, // 输入寄存器0
        columns::INPUT_REGISTER_1, // 输入寄存器1
        columns::OUTPUT_REGISTER,  // 输出寄存器
    ];

    let filter = Some(Filter::new_simple(Column::sum(
        COMBINED_OPS.iter().map(|(c, _v)| *c),
    )));

    TableWithColumns::new(
        Table::Arithmetic,
        cpu_arith_data_link(&COMBINED_OPS, &REGISTER_MAP), //将算术表链接到CPU表
        filter,
    )
}

1.2.2 Step 2: 生成 Trace 数据

根据输入的操作（Operation），逐行生成 Trace 数据，同时补充空行并执行范围检查，主要由以下几步构成。

1. 分配 Trace 行数：
   • max_rows 定义 Trace 表的最大行数：
     • 如果每个操作最多需要两行，则行数为 2 * operations.len()。
     • 范围检查需要至少 RANGE_MAX 行，因此最终行数取两者的最大值。
2. 生成操作对应的 Trace 行：
   • 对于每个 Operation 调用 to_rows 方法，将其转换为一行或两行数据。
   • 如果操作需要两行（如某些复杂的算术操作），则将第二行追加到 Trace。
3. 填充空行：
   • Trace 表的长度需要是 2 的幂次方（以便优化后续计算）。
   • 使用全零行填充至下一个 2 的幂次方长度，同时确保行数不少于 RANGE_MAX。
4. 转置为列数据：
   • Trace 的行数据转换为列数据，方便后续的验证和多项式计算。
5. 执行范围检查：
   • 调用 generate_range_checks 方法，对指定列的数据执行范围检查。

代码模块：

pub(crate) fn generate_trace(&self, operations: Vec<Operation>) -> Vec<PolynomialValues<F>> {
    let max_rows = std::cmp::max(2 * operations.len(), RANGE_MAX);
    let mut trace_rows = Vec::with_capacity(max_rows);

    for op in operations {
        let (row1, maybe_row2) = op.to_rows(); // 将操作转换为一行或两行数据。
        trace_rows.push(row1);

        if let Some(row2) = maybe_row2 { // 如果操作需要两行，添加到 Trace。
            trace_rows.push(row2);
        }
    }

    // 填充空行
    let padded_len = trace_rows.len().next_power_of_two(); // 确保行数为 2 的幂次方,以方便进行插值和FRI的commitment操作。
    for _ in trace_rows.len()..std::cmp::max(padded_len, RANGE_MAX) {
        trace_rows.push(vec![F::ZERO; columns::NUM_ARITH_COLUMNS]); // 添加全零行。
    }

    // 转置为列数据
    let mut trace_cols = transpose(&trace_rows);

    // 范围检查
    self.generate_range_checks(&mut trace_cols);

    // 转换为多项式表示
    trace_cols.into_iter().map(PolynomialValues::new).collect()
}

1.2.3 Step 3: 验证范围检查（Range Checks）

对 Trace 中的某些列进行范围检查，确保列的值在合法范围内（例如 [0, 2^16)）。

代码模块：

fn generate_range_checks(&self, cols: &mut [Vec<F>]) {
    // 初始化 RANGE_COUNTER 列，范围为 [0, 2^16)
    for i in 0..RANGE_MAX {
        cols[RANGE_COUNTER][i] = F::from_canonical_usize(i);
    }
    for i in RANGE_MAX..cols[0].len() {
        cols[RANGE_COUNTER][i] = F::from_canonical_usize(RANGE_MAX - 1);
    }

    // 对共享列（SHARED_COLS）执行频率检查
    for col in SHARED_COLS {
        for i in 0..cols[0].len() {
            let x = cols[col][i].to_canonical_u64() as usize;
            assert!(
                x < RANGE_MAX,
                "column value {} exceeds the max range value {}",
                x,
                RANGE_MAX
            );
            cols[RC_FREQUENCIES][x] += F::ONE; // 统计出现频率
        }
    }
}

1.2.4 Step 4: 验证约束条件

针对不同的算术操作验证约束条件，确保操作的输入、输出及中间状态符合定义，该模块主要在离线验证填充的值是否满足约束。

1. 初始化 RANGE_COUNTER 列：
   • 范围计数列 RANGE_COUNTER 的前 RANGE_MAX 行依次填充 [0, 2^16) 的值。
   • 如果列的行数超过 RANGE_MAX，则填充最大值 2^16-1。
2. 统计共享列的频率：
   • 遍历所有共享列（SHARED_COLS），统计每一行中的值在范围 [0, 2^16) 中的频率。
   • 如果某一行的值超出范围，将触发断言错误。

代码模块：

fn eval_packed_generic<FE, P, const D2: usize>(
    &self,
    vars: &Self::EvaluationFrame<FE, P, D2>,
    yield_constr: &mut ConstraintConsumer<P>,
) where
    FE: FieldExtension<D2, BaseField = F>,
    P: PackedField<Scalar = FE>,
{
    let lv: &[P; NUM_ARITH_COLUMNS] = vars.get_local_values().try_into().unwrap();
    let nv: &[P; NUM_ARITH_COLUMNS] = vars.get_next_values().try_into().unwrap();

    // 范围检查约束
    let rc1 = lv[RANGE_COUNTER];
    let rc2 = nv[RANGE_COUNTER];
    yield_constr.constraint_first_row(rc1); // 第一行必须为 0
    let incr = rc2 - rc1;
    yield_constr.constraint_transition(incr * incr - incr); // 范围递增约束
    let range_max = P::Scalar::from_canonical_u64((RANGE_MAX - 1) as u64);
    yield_constr.constraint_last_row(rc1 - range_max); // 最后一行为 RANGE_MAX-1

    // 调用各个算术操作的约束验证
    mul::eval_packed_generic(lv, yield_constr);
    mult::eval_packed_generic(lv, yield_constr);
    addcy::eval_packed_generic(lv, yield_constr);
    slt::eval_packed_generic(lv, yield_constr);
    lui::eval_packed_generic(lv, nv, yield_constr);
    div::eval_packed(lv, nv, yield_constr);
    shift::eval_packed_generic(lv, nv, yield_constr);
    sra::eval_packed_generic(lv, nv, yield_constr);
    lo_hi::eval_packed_generic(lv, yield_constr);
}

1.2.5 Step 5: 电路级验证（Ext Circuit Evaluation）

通过扩展电路验证算术表中的每个操作，确保满足约束条件，该模块主要通过电路约束构建 STARK 系统的证明。

代码模块：

fn eval_ext_circuit(
    &self,
    builder: &mut CircuitBuilder<F, D>,
    vars: &Self::EvaluationFrameTarget,
    yield_constr: &mut RecursiveConstraintConsumer<F, D>,
) {
    let lv: &[ExtensionTarget<D>; NUM_ARITH_COLUMNS] =
        vars.get_local_values().try_into().unwrap();
    let nv: &[ExtensionTarget<D>; NUM_ARITH_COLUMNS] =
        vars.get_next_values().try_into().unwrap();

    // 范围检查约束（电路版）
    let rc1 = lv[RANGE_COUNTER];
    let rc2 = nv[RANGE_COUNTER];
    yield_constr.constraint_first_row(builder, rc1);
    let incr = builder.sub_extension(rc2, rc1);
    let t = builder.mul_sub_extension(incr, incr, incr);
    yield_constr.constraint_transition(builder, t);
    let range_max =
        builder.constant_extension(F::Extension::from_canonical_usize(RANGE_MAX - 1));
    let t = builder.sub_extension(rc1, range_max);
    yield_constr.constraint_last_row(builder, t);

    // 调用各个算术操作的电路验证
    mul::eval_ext_circuit(builder, lv, yield_constr);
    mult::eval_ext_circuit(builder, lv, yield_constr);
    addcy::eval_ext_circuit(builder, lv, yield_constr);
    slt::eval_ext_circuit(builder, lv, yield_constr);
    lui::eval_ext_circuit(builder, lv, nv, yield_constr);
    div::eval_ext_circuit(builder, lv, nv, yield_constr);
    shift::eval_ext_circuit(builder, lv, nv, yield_constr);
    sra::eval_ext_circuit(builder, lv, nv, yield_constr);
    lo_hi::eval_ext_circuit(builder, lv, yield_constr);

2. CPU 操作

2.1 CPU模块基本介绍

CPU的执行主要分为以下部分：

1. 指令获取与解码（Decode） CPU从内存中获取指令（Fetch），并将其送入解码模块（Decode）。在这里，指令被解析成操作码（Opcode）、功能码（FuncCode）、源寄存器（Source Register）、目标寄存器（Destination Register）等字段。解码模块负责验证指令是否合法，并确定指令的类型（如算术操作、跳转指令或内存操作）。 作用：确保CPU只执行合法的指令，并为后续模块提供清晰的指令结构。 2. 跳转与分支（Jumps） 如果当前指令是跳转或分支指令，跳转模块计算目标地址并更新程序计数器（PC）。无条件跳转会直接更改PC；而条件跳转则根据条件寄存器的状态判断是否执行跳转。分支指令则需要判断具体的条件（如是否等于、大于或小于）。 作用：灵活控制程序的执行流程，实现函数调用、循环等功能。 3. 内存访问与总线操作（Membus 和 Memio） 对于需要访问内存的指令（如加载和存储指令），CPU通过内存总线模块（Membus）与内存进行交互。Membus模块会验证内存通道的状态（如是否被使用）和上下文标志（Kernel/User），确保内存访问的安全性。Memio模块则负责具体的加载（Load）和存储（Store）操作，比如从内存读取一个字（Word）、半字（Halfword）或字节（Byte），或者将数据写入内存。 作用：提供CPU与内存之间的桥梁，确保数据读写操作的正确性和安全性。 4. 算术和逻辑运算 CPU根据指令类型执行算术或逻辑运算，比如加法、减法、位移（Shift）、条件移动（CondMov）等。Shift模块负责位移操作，包括左移、右移以及循环右移；Bits模块处理特定的位操作，比如符号扩展和半字节交换；Count模块用于统计二进制数的前导零或前导一。 作用：执行指令核心逻辑，完成具体的计算任务。 5. 系统调用与特权操作（Syscall 和 Exit Kernel） 当指令为系统调用（Syscall）时，CPU切换到内核模式以处理特权操作，如内存映射、线程管理、文件操作等。Syscall模块负责验证系统调用的正确性，确保操作合法并满足系统需求。当任务完成后，CPU通过Exit Kernel模块退出内核模式，返回用户态继续执行。Exit Kernel模块会同步寄存器状态到内存，更新程序计数器，并检查内存的一致性。 作用：在用户态和内核态之间安全切换，提供系统级服务支持。 6. 结果写回与状态更新 指令执行完成后，计算结果会写入目标寄存器或存储到内存中，同时更新程序计数器（PC）以准备执行下一条指令。 作用：保存运算结果，并推进指令流的执行。

2.2 运行流程

2.2.1 Step 1: 结构定义

1. 定义了 CpuStark 结构，它是一个泛型结构，包含以下参数：
   • F：字段类型（Field type），用于支持有限域运算。
   • D：扩展度（Degree of extension），用于表示扩展字段的深度。
2. 使用了 PhantomData<F>，这是一个占位符，表明这个结构与字段类型相关联。

#[derive(Copy, Clone, Default)]
pub struct CpuStark<F, const D: usize> {
    pub f: PhantomData<F>,
}

CpuStark 是 CPU 模拟的核心结构，负责管理和操作 STARK 的具体实现，包括 trace 验证与约束生成。

2.2.2 Step 2: 本地验证方法

fn eval_packed_generic<FE, P, const D2: usize>(
    &self,
    vars: &Self::EvaluationFrame<FE, P, D2>,
    yield_constr: &mut ConstraintConsumer<P>,
) where
    FE: FieldExtension<D2, BaseField = F>,
    P: PackedField<Scalar = FE>,

1. 验证 CPU 的运行轨迹是否符合逻辑约束。
2. 使用 packed 字段进行批量验证，提高本地验证的效率。

Step 2.1: 提取 CPU 状态

1. 从输入 vars 中提取当前行（local_values）和下一行（next_values）。
2. 将其转换为 CpuColumnsView，便于访问 CPU 的各个字段。

let local_values: &[P; NUM_CPU_COLUMNS] = vars.get_local_values().try_into().unwrap();
let local_values: &CpuColumnsView<P> = local_values.borrow();
let next_values: &[P; NUM_CPU_COLUMNS] = vars.get_next_values().try_into().unwrap();
let next_values: &CpuColumnsView<P> = next_values.borrow();

• CpuColumnsView：封装了 CPU 的 trace 数据，如指令、寄存器值等。
• NUM_CPU_COLUMNS：CPU 表的总列数。

Step 2.2: 调用模块验证

bootstrap_kernel::eval_bootstrap_kernel_packed(local_values, next_values, yield_constr);
decode::eval_packed_generic(local_values, yield_constr);
jumps::eval_packed(local_values, next_values, yield_constr);
membus::eval_packed(local_values, yield_constr);
memio::eval_packed(local_values, next_values, yield_constr);
shift::eval_packed(local_values, yield_constr);
count::eval_packed(local_values, yield_constr);
syscall::eval_packed(local_values, yield_constr);
bits::eval_packed(local_values, yield_constr);
misc::eval_packed(local_values, yield_constr);
exit_kernel::eval_exit_kernel_packed(local_values, next_values, yield_constr);

• 分模块对 CPU 的不同功能进行验证。
• 每个模块对应一个具体的验证逻辑（如解码、跳转、内存操作等）。

例子： decode::eval_packed_generic

fn eval_packed_generic<P: PackedField>(
    lv: &CpuColumnsView<P>,
    yield_constr: &mut ConstraintConsumer<P>,
) {
    let filter = lv.op.decode_op; // 过滤条件，指令解码操作
    let opcode_check = lv.opcode_bits[0]; // 取操作码第一位
    yield_constr.constraint(filter * opcode_check); // 添加约束：验证操作码是否正确
}

• 作用：验证操作码是否正确。
• 过程：
  1. 检查当前行是否属于指令解码操作（通过 filter）。
  2. 验证操作码的第一位是否符合预期。

2.2.3 Step 3: 生成电路方法

fn eval_ext_circuit(
    &self,
    builder: &mut CircuitBuilder<F, D>,
    vars: &Self::EvaluationFrameTarget,
    yield_constr: &mut RecursiveConstraintConsumer<F, D>,
)

• 为 CPU 的每一步操作生成电路约束。
• 提供给 zk-STARK 证明生成器。

Step 3.1: 提取状态

let local_values: &[ExtensionTarget<D>; NUM_CPU_COLUMNS] =
    vars.get_local_values().try_into().unwrap();
let local_values: &CpuColumnsView<ExtensionTarget<D>> = local_values.borrow();
let next_values: &[ExtensionTarget<D>; NUM_CPU_COLUMNS] =
    vars.get_next_values().try_into().unwrap();
let next_values: &CpuColumnsView<ExtensionTarget<D>> = next_values.borrow();

• 提取 ExtensionTarget 数据，用于电路生成。
• 类似于 eval_packed_generic 中的状态提取。

Step 3.2: 调用模块约束生成

bootstrap_kernel::eval_bootstrap_kernel_ext_circuit(builder, local_values, next_values, yield_constr);
decode::eval_ext_circuit(builder, local_values, yield_constr);
jumps::eval_ext_circuit(builder, local_values, next_values, yield_constr);
membus::eval_ext_circuit(builder, local_values, yield_constr);
// ...
exit_kernel::eval_exit_kernel_ext_circuit(builder, local_values, next_values, yield_constr);

功能：

• 为每个模块生成对应的电路约束。
• 每个模块提供对应的 eval_ext_circuit 方法。

例子： decode::eval_ext_circuit

fn eval_ext_circuit<F: RichField + Extendable<D>, const D: usize>(
    builder: &mut CircuitBuilder<F, D>,
    lv: &CpuColumnsView<ExtensionTarget<D>>,
    yield_constr: &mut RecursiveConstraintConsumer<F, D>,
) {
    let filter = lv.op.decode_op; // 过滤条件
    let opcode_check = lv.opcode_bits[0]; // 操作码第一位
    let constr = builder.mul_extension(filter, opcode_check); // 生成约束
    yield_constr.constraint(builder, constr); // 添加到约束中
}

1. 使用 CircuitBuilder 构建乘法约束，生成指令解码的电路约束。
2. 验证操作码是否正确。

2.2.4 Step 4: 测试与验证

#[test]
fn test_stark_degree() -> Result<()> {
    const D: usize = 2;
    type C = PoseidonGoldilocksConfig;
    type F = <C as GenericConfig<D>>::F;
    type S = CpuStark<F, D>;

    let stark = S {
        f: Default::default(),
    };
    test_stark_low_degree(stark)
}

功能：

• 测试约束的多项式是否满足低阶性质（Low-degree constraints）。
• 保证 STARK 证明的有效性。

#[test]
fn test_stark_circuit() -> Result<()> {
    const D: usize = 2;
    type C = PoseidonGoldilocksConfig;
    type F = <C as GenericConfig<D>>::F;
    type S = CpuStark<F, D>;

    let stark = S {
        f: Default::default(),
    };
    test_stark_circuit_constraints::<F, C, S, D>(stark)
}

功能：

• 测试生成的电路是否符合预期的约束。
• 验证 STARK 电路生成的正确性。