【zkMIPS系列】ZKM Prover—Poseidon STARK

ZKM
更新于 3天前
阅读 447

Poseidon的执行过程包括以下6个步骤：初始化、完整轮次计算、部分轮次计算、电路约束生成、生成多项式承诺、证明生成与验证。整个过程用于生成最终的零知识证明。

# 1. Poseidon哈希函数基本介绍

Poseidon在代码中的具体执行方式包括以下6步：

**1. 初始化与常量定义**
目标：定义常量矩阵（如 MDS 矩阵）、轮次常量、哈希状态。
核心操作：初始化哈希状态、轮次计数器等。

**2. 完整轮次计算**
目标：执行完整轮次计算，包括常量层、S-box 层和 MDS 层。
核心操作：
- 常量层：每轮加上特定的轮次常量。
- S-box 层：对哈希状态的每个元素进行非线性变换（如 x^3 和 x^6）。
- MDS 层：对状态进行矩阵变换以增强扩散性。

**3. 部分轮次计算**
目标：执行部分轮次的计算，部分轮次通常包括单项式 S-box 和 MDS 层。
核心操作：
- 执行 部分常量层 和 快速 MDS 层，优化计算过程。
- 将输入状态与部分常量相加，执行部分的 MDS 变换。

**4. 电路约束生成**
目标：生成电路约束，确保每个计算步骤的输出符合预期。
核心操作：
- 使用 CircuitBuilder 构建电路。
- 对每一轮计算（常量层、S-box 层、MDS 层）生成相应的约束。
- 确保电路的输出值与计算结果一致。

**5. 生成多项式承诺**
目标：将生成的trace数据转换为多项式并生成承诺。
核心操作：
- 将哈希计算过程中的trace数据行转换为多项式值。
- 使用多项式批量处理来生成承诺。

**6. 证明生成与验证**
目标：使用多项式承诺生成最终的零知识证明。
核心操作：
- 将多项式承诺与挑战结合生成最终的证明。
- 确保证明的正确性和有效性。

# 2. Poseidon 哈希的trace填充机制

在 Poseidon 哈希电路的实现中，**row** 和 **column** 是用来表示哈希计算过程中的数据和约束的结构。它们分别对应着电路中不同的输入、输出以及各个计算层的中间值。在跟踪（trace）数据的生成过程中，每一行（row）代表一次哈希计算的状态，而每一列（column）则代表哈希过程中的特定变量或计算步骤。

## 2.1 Row 和 Column 对应关系
- **Row**:
    - 每一行表示哈希计算的一个“时间步”或者计算过程中的某个阶段。例如，一行可能包含当前哈希状态（输入、输出、时间戳等）。
    - 在电路中，`row` 可以包含多个 `column`，每个 `column` 代表计算中不同的值。
- **Column**:
    - 每一列表示哈希过程中的一个特定变量，如输入数据、输出数据、中间计算结果、常量、时间戳等。
    - 例如，`reg_in(i)` 表示输入列，第 `i` 个输入，`reg_out(i)` 表示输出列，第 `i` 个输出。`FILTER` 列可以表示是否需要进行特定的筛选或操作。

## 2.2 Trace 填充

- **Trace**:
    - trace数据（trace）由多行（`row`）组成，每一行记录了哈希计算过程中的输入输出及中间状态。
    - Trace 中的每一行都包含了不同列的数据。
- **Trace 填充过程**:
    - 在生成 trace 时，每一行的各列会依次填充计算结果。具体来说，`generate_trace` 函数会根据输入数据生成对应的 trace 数据，每个 trace 行包括从输入到输出的多个数据列。

## 2.3 具体实现

`generate_trace_rows`

```rust
rust
// `generate_trace_rows` 用于生成整个过程的trace行
fn generate_trace_rows(
    &self,
    inputs_and_timestamps: Vec<([F; SPONGE_WIDTH], usize)>, // 输入数据和时间戳
    min_rows: usize, // 最小行数
) -> Vec<[F; NUM_COLUMNS]> { // 返回生成的trace数据行
    let num_rows = inputs_and_timestamps
        .len()
        .max(min_rows)
        .next_power_of_two(); // 确保行数为2的幂次

let mut rows = Vec::with_capacity(num_rows); // 初始化存储行的向量
    for input_and_timestamp in inputs_and_timestamps.iter() {
        let rows_for_perm = self.generate_trace_rows_for_perm(*input_and_timestamp, true);
        rows.push(rows_for_perm); // 为每个输入生成trace数据行
    }

let default_row = self.generate_trace_rows_for_perm(([F::ZEROS; SPONGE_WIDTH], 0), false);
    while rows.len() < num_rows {
        rows.push(default_row); // 如果行数不足，填充默认行
    }
    rows // 返回所有生成的trace数据行
}

```

- **`generate_trace_rows`**: 该函数生成一个包含多个 `row` 的 `trace`。每一行是一个包含多个列的数据数组。例如，在每一行中，可能会有输入列、输出列、时间戳列等。

`generate_trace_rows_for_perm`

```rust
rust
复制编辑
// 生成单个哈希的trace数据行，包括输入数据、输出数据以及时间戳
fn generate_trace_rows_for_perm(
    &self,
    input_and_timestamp: ([F; SPONGE_WIDTH], usize), // 输入数据和时间戳
    need_ctl: bool, // 是否需要使用CTF（Cross Table Filter）
) -> [F; NUM_COLUMNS] { // 返回生成的trace数据行
    let (hash, mut rows) = poseidon_with_witness(&input_and_timestamp.0); // 计算哈希并生成证明
    rows[FILTER] = F::from_bool(need_ctl); // 设置FILTER字段（控制标志）
    for i in 0..SPONGE_WIDTH {
        rows[reg_in(i)] = input_and_timestamp.0[i]; // 将输入数据填充到rows中的相应列
        rows[reg_out(i)] = hash[i]; // 将哈希结果填充到输出列
    }
    rows[TIMESTAMP] = F::from_canonical_usize(input_and_timestamp.1); // 设置时间戳
    rows // 返回填充后的完整trace数据行
}

```

- **`generate_trace_rows_for_perm`**: 该函数为每个输入数据生成一个完整的trace数据行。每个 `row` 包含多个 `column`，如输入列、输出列、时间戳列、以及其他计算中间结果的列。

# 3. 代码详解

接下来将重点分析一下PoseidonStark的代码结构

## 3.1 核心数据结构和常量

```rust
// PoseidonStark 结构体，使用泛型 F 和常量 D
// F: 是有限域类型，D: 是扩展域的深度
// PhantomData<F> 用来告诉 Rust 编译器该结构体与 F 类型相关，但实际不直接存储它
#[derive(Copy, Clone, Default)]
pub struct PoseidonStark<F, const D: usize> {
    pub(crate) f: PhantomData<F>, // 用 PhantomData 标明结构体与 F 关联
}

```

- **Poseidon Stark**: 这是一个结构体，目的是实现 Poseidon 哈希的 Stark 电路。`PhantomData<F>` 是为了告诉 Rust 编译器，虽然我们不直接存储 `F` 类型的值，但我们会在类型中用到它。
- **常量定义**:
代码中定义了一些常量，像 `ALL_ROUND_CONSTANTS` 和 `MDS_MATRIX_CIRC`，它们是 Poseidon 哈希计算的核心部分，涉及每一轮的常量和矩阵运算。

## 3.2 Poseidon 哈希的计算流程

### 3.2.1 `poseidon_with_witness` 函数

```rust
// `poseidon_with_witness` 计算 Poseidon 哈希，并生成与输入状态相关的“证明” witness
// 输入数据是一个长度为 SPONGE_WIDTH 的数组，输出是哈希结果和证明数据
pub fn poseidon_with_witness<F: PrimeField64>(
    input: &[F; SPONGE_WIDTH], // 输入数据
) -> ([F; SPONGE_WIDTH], [F; NUM_COLUMNS]) { // 返回计算结果和证明数据
    let mut state = *input; // 初始化哈希状态，直接使用输入数据作为初始状态
    let mut witness = [F::ZEROS; NUM_COLUMNS]; // 初始化证明数据，所有值设为零
    let mut round_ctr = 0; // 初始化轮次计数器

// 执行完整轮次的哈希计算
    full_rounds(&mut state, &mut witness, &mut round_ctr, true);
    // 执行部分轮次的哈希计算
    partial_rounds(&mut state, &mut witness, &mut round_ctr);
    // 再次执行完整轮次的哈希计算
    full_rounds(&mut state, &mut witness, &mut round_ctr, false);

// 确保轮次计数器的最终值为预期的 N_ROUNDS
    debug_assert_eq!(round_ctr, N_ROUNDS);

(state, witness) // 返回计算后的状态和证明数据
}

```

- **`poseidon_with_witness`**: 这是一个核心函数，负责执行 Poseidon 哈希的完整计算，并生成对应的证明数据（即 witness）。哈希计算分为三个阶段：完整轮次、部分轮次和再次完整轮次。

### 3.2.2 `full_rounds` 函数

```rust
// 处理完整的哈希轮次（包括常量层、S-Box层和MDS层）
fn full_rounds<F: PrimeField64>(
    state: &mut [F; SPONGE_WIDTH], // 当前哈希状态
    witness: &mut [F; NUM_COLUMNS], // 存储证明数据
    round_ctr: &mut usize, // 当前轮次
    is_first_full_round: bool, // 是否为第一次完整轮次
) {
    for r in 0..HALF_N_FULL_ROUNDS { // 完整轮次共需要 HALF_N_FULL_ROUNDS 轮
        constant_layer(state, *round_ctr); // 执行常量层
        sbox_layer(state, witness, r, is_first_full_round); // 执行S-Box层
        *state = mds_layer(state); // 执行MDS层
        *round_ctr += 1; // 轮次计数器递增
    }
}

```

- **`full_rounds`**: 处理完整的轮次，在每一轮中，哈希状态会经过常量层、S-Box 层和 MDS 层的变换，最终得到新的状态。

### 3.2.3 `partial_rounds` 函数

```rust
// 处理部分轮次的计算
fn partial_rounds<F: PrimeField64>(
    state: &mut [F; SPONGE_WIDTH], // 当前哈希状态
    witness: &mut [F; NUM_COLUMNS], // 存储证明数据
    round_ctr: &mut usize, // 当前轮次
) {
    partial_first_constant_layer(state); // 执行部分常量层
    *state = mds_partial_layer_init(state); // 初始化部分MDS层

for i in 0..N_PARTIAL_ROUNDS { // 处理每一轮部分轮次，部分轮次总共有 N_PARTIAL_ROUNDS 轮
        state[0] = sbox_monomial(state[0], witness, reg_partial_s0(i), reg_partial_s1(i)); // 执行单项式S-Box层
        unsafe {
            state[0] = state[0].add_canonical_u64(FAST_PARTIAL_ROUND_CONSTANTS[i]); // 加入常量
        }
        *state = mds_partial_layer_fast(state, i); // 执行快速MDS层
    }
    *round_ctr += N_PARTIAL_ROUNDS; // 更新轮次计数器
}

```

- **`partial_rounds`**: 处理部分轮次。在部分轮次中，首先执行常量层，然后进行 MDS 层的初始化，最后执行每一轮的单项式 S-Box 和 MDS 层。

## 3.3 生成trace数据

```rust
// `generate_trace_rows` 生成trace数据行，通常在多项式承诺系统中使用
fn generate_trace_rows(
    &self,
    inputs_and_timestamps: Vec<([F; SPONGE_WIDTH], usize)>, // 输入数据和时间戳
    min_rows: usize, // 最小行数
) -> Vec<[F; NUM_COLUMNS]> { // 返回生成的trace数据行
    let num_rows = inputs_and_timestamps
        .len()
        .max(min_rows)
        .next_power_of_two(); // 保证行数为2的幂次

let mut rows = Vec::with_capacity(num_rows); // 初始化存储行的向量
    for input_and_timestamp in inputs_and_timestamps.iter() {
        let rows_for_perm = self.generate_trace_rows_for_perm(*input_and_timestamp, true); // 为每个输入生成一行trace数据
        rows.push(rows_for_perm); // 将生成的行添加到向量中
    }

let default_row = self.generate_trace_rows_for_perm(([F::ZEROS; SPONGE_WIDTH], 0), false); // 创建一个默认行
    while rows.len() < num_rows { // 如果行数小于所需的数量
        rows.push(default_row); // 添加默认行直到行数满足要求
    }
    rows // 返回所有生成的trace数据行
}

```

- **`generate_trace_rows`**: 该函数用于生成trace数据行，这些数据行包含哈希计算的每个步骤及其输入输出。生成的行数会被调整为 2 的幂次，以适应多项式承诺的要求。

### 3.3.1 `generate_trace_rows_for_perm` 函数

```rust
// 生成单个哈希的trace数据行，包括输入数据、输出数据以及时间戳
fn generate_trace_rows_for_perm(
    &self,
    input_and_timestamp: ([F; SPONGE_WIDTH], usize), // 输入数据和时间戳
    need_ctl: bool, // 是否需要使用CTF（Cross Table Filter）
) -> [F; NUM_COLUMNS] { // 返回计算出的trace数据行
    let (hash, mut rows) = poseidon_with_witness(&input_and_timestamp.0); // 计算Poseidon哈希和生成证明
    rows[FILTER] = F::from_bool(need_ctl); // 设置FILTER字段
    for i in 0..SPONGE_WIDTH {
        rows[reg_in(i)] = input_and_timestamp.0[i]; // 将输入数据填充到rows中的相应列
    }
    rows[reg_out(0)] = hash[0]; // 将哈希结果的第一个元素存储在输出列中
    rows[reg_out(1)] = hash[1]; // 将哈希结果的第二个元素存储在输出列中
    rows // 返回生成的完整trace数据行
}

```

- **`generate_trace_rows_for_perm`**: 这个函数为每一个输入生成一行trace数据。它包含输入、输出数据以及时间戳等信息，并且可以选择是否需要Cross Table Filter（CTF）。

## 3.4 S-Box 层和 MDS 层

### 3.4.1 S-Box 层

```rust
// S-box 层：对每个输入元素进行非线性变换。
// 这个变换是通过计算 x^3 和 x^6 来实现的
fn sbox_layer<F: PrimeField64>(
    state: &mut [F; SPONGE_WIDTH], // 当前哈希状态
    witness: &mut [F; NUM_COLUMNS], // 存储证明数据
    r: usize, // 当前轮次
    is_first_full_round: bool, // 是否是第一次完整轮次
) {
    for i in 0..SPONGE_WIDTH {
        // 根据是否是第一次完整轮次，选择不同的列
        let idx0 = if is_first_full_round {
            reg_full0_s0(r, i)
        } else {
            reg_full1_s0(r, i)
        };
        let idx1 = if is_first_full_round {
            reg_full0_s1(r, i)
        } else {
            reg_full1_s1(r, i)
        };

// 对当前哈希状态的每个元素应用单项式S-Box
        state[i] = sbox_monomial(state[i], witness, idx0, idx1);
    }
}

```

- **`sbox_layer`**: 该函数是 Poseidon 哈希中的非线性部分，它对每个哈希状态的元素执行 S-Box 操作。S-Box 操作通常是通过对每个输入元素执行 `x^3` 和 `x^6` 来实现的，从而使得哈希具有更强的非线性特性，增强其抗碰撞能力。

### 3.4.2 S-Box 单项式

```rust
// 单项式 S-Box 变换：计算 x^3 和 x^6，返回新的值
fn sbox_monomial<F: PrimeField64>(
    x: F, // 当前元素
    witness: &mut [F; NUM_COLUMNS], // 存储证明数据
    idx0: usize, // 对应列索引
    idx1: usize, // 对应列索引
) -> F {
    let x3 = x.cube(); // 计算 x^3
    let x6 = x3.square(); // 计算 x^6
    let out = x.mul(x6); // 计算 x^9 = x * x^6
    witness[idx0] = x3; // 保存 x^3 作为证明
    witness[idx1] = out; // 保存 x^9 作为证明
    out // 返回新的值
}

```

- **`sbox_monomial`**: 这是实际进行 S-Box 计算的函数，它计算 `x^3` 和 `x^6`，然后返回 `x * x^6`（即 `x^9`），并将中间结果保存到 `witness` 中。这些中间结果会在后续的验证过程中使用。

### 3.4.3 MDS 层

```rust
// MDS 层：对哈希状态进行线性变换，使用矩阵乘法
fn mds_layer<F: PrimeField64>(state_: &[F; SPONGE_WIDTH]) -> [F; SPONGE_WIDTH] {
    let mut result = [F::ZERO; SPONGE_WIDTH]; // 初始化输出结果数组

let mut state = [0u64; SPONGE_WIDTH]; // 使用 64 位的非规范化表示
    for r in 0..SPONGE_WIDTH {
        state[r] = state_[r].to_noncanonical_u64(); // 转换为非规范化表示
    }

// 通过矩阵乘法计算 MDS 层的输出
    for r in 0..12 {
        if r < SPONGE_WIDTH {
            let sum = mds_row_shf(r, &state); // 执行矩阵乘法
            let sum_lo = sum as u64;
            let sum_hi = (sum >> 64) as u32;
            result[r] = F::from_noncanonical_u96((sum_lo, sum_hi)); // 重新转换为规范化表示
        }
    }

result // 返回计算结果
}

```

- **`mds_layer`**: MDS（最大距离可分离）层用于通过矩阵乘法对哈希状态进行混合。它增强了哈希的扩散性，使得输出对于输入的任何小变化都具有敏感性。这一层通常是线性变换，通过使用 MDS 矩阵对哈希状态进行处理。

### 3.4.4 MDS 行计算

```rust
// 计算 MDS 矩阵的每一行的贡献
fn mds_row_shf(r: usize, v: &[u64; SPONGE_WIDTH]) -> u128 {
    debug_assert!(r < SPONGE_WIDTH); // 确保索引有效
    let mut res = 0u128;

// 遍历所有的列，计算每一列的加权和
    for i in 0..12 {
        if i < SPONGE_WIDTH {
            res += (v[(i + r) % SPONGE_WIDTH] as u128) * (MDS_MATRIX_CIRC[i] as u128);
        }
    }
    res += (v[r] as u128) * (MDS_MATRIX_DIAG[r] as u128); // 添加对角线元素的贡献

res // 返回结果
}

```

- **`mds_row_shf`**: 这是 MDS 层中的矩阵乘法的具体实现。它通过遍历 MDS 矩阵的列，计算每一行的加权和。每一行的贡献由矩阵的循环部分和对角线部分决定。

## 3.5 部分常量层和部分 MDS 层

```rust
// 部分常量层：对状态进行加法操作，将常量加入状态中
fn partial_first_constant_layer<P: PackedField>(state: &mut [P]) {
    for i in 0..SPONGE_WIDTH {
        state[i] += P::Scalar::from_canonical_u64(FAST_PARTIAL_FIRST_ROUND_CONSTANT[i]);
    }
}

// 部分 MDS 层初始化：初始化状态并进行 MDS 操作
fn mds_partial_layer_init<F: PrimeField64>(state: &mut [F; SPONGE_WIDTH]) -> [F; SPONGE_WIDTH] {
    let mut result = [F::ZEROS; SPONGE_WIDTH]; // 初始化结果数组
    result[0] = state[0]; // 将第一个状态元素直接传递
    // 对剩余的状态元素应用 MDS 矩阵进行混合
    for r in 1..SPONGE_WIDTH {
        for c in 1..SPONGE_WIDTH {
            let t = F::from_canonical_u64(FAST_PARTIAL_ROUND_INITIAL_MATRIX[r - 1][c - 1]);
            result[c] += state[r] * t; // 执行矩阵乘法
        }
    }
    result // 返回新的状态
}

```

- **`partial_first_constant_layer`**: 该函数负责将 `FAST_PARTIAL_FIRST_ROUND_CONSTANT` 加到状态中，这是 Poseidon 哈希中部分轮次的初始化操作。
- **`mds_partial_layer_init`**: 该函数初始化状态并执行部分 MDS 层的操作，它是 Poseidon 哈希中的一部分优化。

## 3.6 Trace 生成与电路约束

```rust
// `eval_packed_generic` 函数用于评估哈希过程中的每个步骤，并在电路中生成约束
fn eval_packed_generic<P: PackedField>(lv: &[P], yield_constr: &mut ConstraintConsumer<P>) {
    let mut state = [P::default(); SPONGE_WIDTH]; // 初始化状态
    let input = (0..SPONGE_WIDTH).map(|i| lv[reg_in(i)]).collect_vec(); // 从局部值中提取输入
    state.copy_from_slice(&input); // 设置初始状态

let mut round_ctr = 0; // 初始化轮次计数器
    // 处理完整的轮次
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_field(&mut state, round_ctr); // 执行常量层
        sbox_layer_field(lv, &mut state, r, true, yield_constr); // 执行S-Box层
        mds_layer_field(&mut state); // 执行MDS层

round_ctr += 1; // 更新轮次计数器
    }

// 处理部分轮次
    partial_first_constant_layer(&mut state); // 执行部分常量层
    mds_partial_layer_init_field(&mut state); // 初始化部分MDS层
    for r in 0..N_PARTIAL_ROUNDS - 1 {
        partial_sbox_layer(lv, &mut state, r, yield_constr); // 执行部分 S-Box 层
        state[0] += P::Scalar::from_canonical_u64(FAST_PARTIAL_ROUND_CONSTANTS[r]); // 加入常量
        mds_partial_layer_fast_field(&mut state, r); // 执行快速 MDS 层
    }
    partial_sbox_layer(lv, &mut state, N_PARTIAL_ROUNDS - 1, yield_constr); // 执行最后一轮部分 S-Box 层
    mds_partial_layer_fast_field(&mut state, N_PARTIAL_ROUNDS - 1); // 执行最后一轮部分 MDS 层

round_ctr += N_PARTIAL_ROUNDS; // 更新轮次计数器

// 处理完整的轮次
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_field(&mut state, round_ctr); // 执行常量层
        sbox_layer_field(lv, &mut state, r, false, yield_constr); // 执行S-Box层
        mds_layer_field(&mut state); // 执行MDS层

round_ctr += 1; // 更新轮次计数器
    }

// 为每个输出值生成约束
    for i in 0..SPONGE_WIDTH {
        yield_constr.constraint(state[i] - lv[reg_out(i)]); // 约束输出值与计算结果相等
    }
}

```

- **`eval_packed_generic`**: 这是评估哈希计算过程的核心函数。它通过构造哈希的每一轮，应用不同的层（常量层、S-Box层、MDS层），并生成相应的电路约束。这个函数最终确保哈希计算过程是符合预期的。

## 3.7 电路层面的 S-Box 层与 MDS 层

### 3.7.1 电路层的 S-Box

```rust
// S-box 电路实现：为电路约束生成 S-Box 层的约束
fn sbox_circuit<F: RichField + Extendable<D>, const D: usize>(
    input: ExtensionTarget<D>, // 输入目标（电路中一个扩展字段类型的目标）
    inter: ExtensionTarget<D>, // 中间结果目标
    output: ExtensionTarget<D>, // 输出目标
    builder: &mut CircuitBuilder<F, D>, // CircuitBuilder 用于构建电路
    yield_constr: &mut RecursiveConstraintConsumer<F, D>, // 生成递归约束
) {
    let cube = builder.cube_extension(input); // 计算输入的立方（x^3）
    let constraint = builder.sub_extension(cube, inter); // 生成约束：x^3 - 中间结果
    yield_constr.constraint(builder, constraint); // 添加约束到约束消费者

// 计算 x * x^6，并生成约束：x * x^6 - 输出
    let out = builder.mul_many_extension([input, inter, inter]);
    let constraint = builder.sub_extension(out, output);
    yield_constr.constraint(builder, constraint); // 添加约束到约束消费者
}

```

- **`sbox_circuit`**: 这是 Poseidon 哈希的 S-Box 层在电路中的实现。它首先计算输入 `x` 的立方（`x^3`），然后生成一个约束，确保计算结果与中间结果一致。接着，它计算 `x * x^6`，并生成一个约束，确保输出值正确。这里的 `builder` 用于在电路中构建约束。

### 3.7.2 电路层的 MDS

```rust
// MDS 电路实现：用于电路中对 MDS 层进行计算和约束
fn mds_layer_circuit<F: RichField + Extendable<D>, const D: usize>(
    state: &mut [ExtensionTarget<D>], // 当前状态
    builder: &mut CircuitBuilder<F, D>, // CircuitBuilder 用于构建电路
) {
    let res = (0..SPONGE_WIDTH)
        .map(|i| {
            // 遍历每列，构建电路约束
            let mut sum = (0..SPONGE_WIDTH)
                .map(|j| {
                    builder.mul_const_extension(
                        F::from_canonical_u64(MDS_MATRIX_CIRC[j]), // 使用 MDS 矩阵中的元素进行扩展
                        state[(j + i) % SPONGE_WIDTH], // 状态与矩阵元素相乘
                    )
                })
                .collect_vec();

// 将对角线矩阵元素相乘并添加到结果中
            sum.push(
                builder.mul_const_extension(F::from_canonical_u64(MDS_MATRIX_DIAG[i]), state[i]),
            );

builder.add_many_extension(sum) // 将所有项相加得到最终结果
        })
        .collect_vec();

state.copy_from_slice(&res); // 更新状态为计算后的新值
}

```

- **`mds_layer_circuit`**: 这是 MDS 层的电路实现。该函数根据 MDS 矩阵中的元素对状态进行扩展并计算新状态。它首先将每列与 MDS 矩阵的元素进行相乘，接着将结果相加，最后返回新的状态。这些操作通过电路约束来执行。

## 3.8 电路层的部分轮次和部分常量层

### 3.8.1 部分常量层电路

```rust
// 部分常量层电路实现：添加部分轮次的常量
fn partial_first_constant_layer_circuit<F: RichField + Extendable<D>, const D: usize>(
    state: &mut [ExtensionTarget<D>], // 当前状态
    builder: &mut CircuitBuilder<F, D>, // CircuitBuilder 用于构建电路
) {
    for i in 0..SPONGE_WIDTH {
        state[i] = builder.add_const_extension(
            state[i], // 将当前状态元素与常量相加
            F::from_canonical_u64(FAST_PARTIAL_FIRST_ROUND_CONSTANT[i]),
        );
    }
}

```

- **`partial_first_constant_layer_circuit`**: 这个函数实现了部分轮次的常量层，它将每个状态元素与部分常量进行加法操作，并将结果更新到状态中。常量来源于 `FAST_PARTIAL_FIRST_ROUND_CONSTANT`。

### 3.8.2 部分 MDS 层初始化电路

```rust
// 部分 MDS 层初始化电路实现：初始化部分MDS层的状态
fn mds_partial_layer_init_circuit<F: RichField + Extendable<D>, const D: usize>(
    state: &mut [ExtensionTarget<D>], // 当前状态
    builder: &mut CircuitBuilder<F, D>, // CircuitBuilder 用于构建电路
) {
    let mut result = [builder.zero_extension(); SPONGE_WIDTH]; // 初始化一个零状态
    result[0] = state[0]; // 传递第一个状态元素

// 对剩余的状态元素进行初始化并与部分 MDS 矩阵进行乘法运算
    for r in 1..12 {
        for c in 1..12 {
            result[c] = builder.mul_const_add_extension(
                F::from_canonical_u64(FAST_PARTIAL_ROUND_INITIAL_MATRIX[r - 1][c - 1]),
                state[r],
                result[c],
            );
        }
    }

state.copy_from_slice(&result); // 更新状态为新的计算结果
}

```

- **`mds_partial_layer_init_circuit`**: 这个函数实现了部分 MDS 层的初始化，它首先初始化一个零状态，然后将当前状态的每个元素与部分 MDS 矩阵进行乘法运算，最后更新状态为新的值。

## 3.9 电路层的部分 S-Box 层

### 3.9.1 部分 S-Box 层电路实现

```rust
// 部分 S-Box 层电路实现：为电路中的部分轮次生成 S-Box 层的约束
fn partial_sbox_layer_circuit<F: RichField + Extendable<D>, const D: usize>(
    lv: &[ExtensionTarget<D>], // 局部值
    state: &mut [ExtensionTarget<D>], // 当前状态
    r: usize, // 当前轮次
    builder: &mut CircuitBuilder<F, D>, // CircuitBuilder 用于构建电路
    yield_constr: &mut RecursiveConstraintConsumer<F, D>, // 递归约束消费者
) {
    let sbox_inter = lv[reg_partial_s0(r)]; // 获取 S-Box 中间值
    let sbox_out = lv[reg_partial_s1(r)]; // 获取 S-Box 输出值
    sbox_circuit(state[0], sbox_inter, sbox_out, builder, yield_constr); // 生成 S-Box 电路约束
    state[0] = sbox_out; // 更新状态
}

```

- **`partial_sbox_layer_circuit`**: 该函数为电路中的部分轮次生成 S-Box 层的约束。它首先提取局部值中的 S-Box 中间值和输出值，然后生成电路约束，确保 S-Box 的计算结果正确。

## 3.10. 哈希电路约束的生成与验证

```rust
// 为电路生成最终的约束：将最终的计算结果与电路输出进行比较
fn eval_ext_circuit(
    &self,
    builder: &mut CircuitBuilder<F, D>, // CircuitBuilder 用于构建电路
    vars: &Self::EvaluationFrameTarget, // 当前评估帧
    yield_constr: &mut RecursiveConstraintConsumer<F, D>, // 生成递归约束
) {
    let lv = vars.get_local_values(); // 获取局部值

let zero = builder.zero_extension(); // 创建零扩展值
    let mut state = [zero; SPONGE_WIDTH]; // 初始化状态
    let input = (0..SPONGE_WIDTH).map(|i| lv[reg_in(i)]).collect_vec(); // 提取输入值
    state.copy_from_slice(&input); // 设置初始状态

let mut round_ctr = 0; // 初始化轮次计数器
    // 完整轮次的计算
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_circuit(&mut state, round_ctr, builder); // 执行常量层
        sbox_layer_circuit(lv, &mut state, r, true, builder, yield_constr); // 执行S-Box层
        mds_layer_circuit(&mut state, builder); // 执行MDS层

round_ctr += 1; // 更新轮次计数器
    }

// 部分轮次的计算
    partial_first_constant_layer_circuit(&mut state, builder); // 执行部分常量层
    mds_partial_layer_init_circuit(&mut state, builder); // 执行部分 MDS 层初始化
    for r in 0..N_PARTIAL_ROUNDS - 1 {
        partial_sbox_layer_circuit(lv, &mut state, r, builder, yield_constr); // 执行 S-Box 层
        state[0] = builder.add_const_extension(
            state[0],
            F::from_canonical_u64(FAST_PARTIAL_ROUND_CONSTANTS[r]),
        ); // 加入常量
        mds_partial_layer_fast_circuit(&mut state, r, builder); // 执行快速 MDS 层
    }
    partial_sbox_layer_circuit(lv, &mut state, N_PARTIAL_ROUNDS - 1, builder, yield_constr); // 执行最后一轮 S-Box 层
    mds_partial_layer_fast_circuit(&mut state, N_PARTIAL_ROUNDS - 1, builder); // 执行最后一轮 MDS 层

round_ctr += N_PARTIAL_ROUNDS; // 更新轮次计数器

// 再次执行完整轮次
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_circuit(&mut state, round_ctr, builder); // 执行常量层
        sbox_layer_circuit(lv, &mut state, r, false, builder, yield_constr); // 执行S-Box层
        mds_layer_circuit(&mut state, builder); // 执行MDS层

round_ctr += 1; // 更新轮次计数器
    }

// 为每个输出生成约束，确保电路中的状态与输出值匹配
    for i in 0..SPONGE_WIDTH {
        let z = builder.sub_extension(state[i], lv[reg_out(i)]); // 计算约束
        yield_constr.constraint(builder, z); // 添加约束
    }
}

```

- **`eval_ext_circuit`**: 该函数负责将 Poseidon 哈希计算过程转化为电路约束。在电路中，首先计算完整轮次，接着进行部分轮次，最后再计算完整轮次。每一轮的计算都会生成对应的约束，确保计算结果在电路中正确。

## 3.11 验证与多项式承诺相关的部分

### 3.11.1 `generate_trace` 函数

```rust
// `generate_trace` 函数生成最终的跟踪数据，它将输入转换为多项式承诺
pub fn generate_trace(
    &self,
    inputs: Vec<([F; SPONGE_WIDTH], usize)>, // 输入数据和时间戳
    min_rows: usize, // 最小行数
    timing: &mut TimingTree, // 用于跟踪性能的计时器
) -> Vec<PolynomialValues<F>> { // 返回一个包含多项式值的向量
    // 生成trace行，生成多项式值并转换为相应的多项式
    let trace_rows = timed!(
        timing,
        "generate trace rows", // 标记此操作
        self.generate_trace_rows(inputs, min_rows)
    );
    let trace_polys = timed!(
        timing,
        "convert to PolynomialValues", // 标记转换操作
        trace_rows_to_poly_values(trace_rows) // 将trace数据行转换为多项式值
    );
    trace_polys // 返回多项式值
}

```

- **`generate_trace`**: 该函数的目的是生成 Poseidon 哈希的跟踪数据，并将其转换为多项式值，方便用于零知识证明。它首先生成所有的trace行，然后将这些trace行转换为多项式值，最终得到的结果将用于多项式承诺。

### 3.11.2 `trace_rows_to_poly_values` 函数

```rust
// `trace_rows_to_poly_values` 函数将跟踪数据行转换为多项式值
pub fn trace_rows_to_poly_values<F: Field>(
    trace_rows: Vec<[F; NUM_COLUMNS]>, // 传入的trace数据行
) -> Vec<PolynomialValues<F>> { // 返回多项式值
    let mut polys = Vec::new(); // 初始化一个多项式集合

for row in trace_rows {
        let mut poly_vals = Vec::new(); // 存储每行的多项式值
        for &val in row.iter() {
            poly_vals.push(PolynomialValues::from_value(val)); // 将每个值转换为多项式
        }
        polys.push(poly_vals); // 添加到多项式集合中
    }

polys // 返回多项式集合
}

```

- **`trace_rows_to_poly_values`**: 该函数将跟踪数据行转换为多项式值，以便后续操作使用。每一行的值都被转换成一个 `PolynomialValues` 对象，这些对象最终用于多项式承诺和零知识证明的计算。

## 3.12 约束生成与电路验证

### 3.12.1 `constraint_degree` 函数

```rust
// `constraint_degree` 函数返回电路的约束度数
fn constraint_degree(&self) -> usize {
    3 // 返回约束的度数
}

```

- **`constraint_degree`**: 该函数定义了电路约束的度数。约束度数决定了电路的复杂度和多项式承诺的计算复杂度。这里返回的 `3` 表示电路的每个约束都是三次的（即三次多项式约束）。

### 3.12.2 `eval_packed_generic` 与电路约束

```rust
// `eval_packed_generic` 为每一轮计算生成对应的电路约束
fn eval_packed_generic<P: PackedField>(lv: &[P], yield_constr: &mut ConstraintConsumer<P>) {
    let mut state = [P::default(); SPONGE_WIDTH]; // 初始化状态
    let input = (0..SPONGE_WIDTH).map(|i| lv[reg_in(i)]).collect_vec(); // 从局部值中提取输入
    state.copy_from_slice(&input); // 设置初始状态

let mut round_ctr = 0; // 初始化轮次计数器
    // 执行每个轮次的约束生成，包含常量层、S-box 层和 MDS 层
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_field(&mut state, round_ctr); // 执行常量层
        sbox_layer_field(lv, &mut state, r, true, yield_constr); // 执行 S-box 层
        mds_layer_field(&mut state); // 执行 MDS 层

round_ctr += 1; // 更新轮次计数器
    }

// 执行部分轮次的约束生成
    partial_first_constant_layer(&mut state); // 执行部分常量层
    mds_partial_layer_init_field(&mut state); // 执行部分 MDS 层初始化
    for r in 0..N_PARTIAL_ROUNDS - 1 {
        partial_sbox_layer(lv, &mut state, r, yield_constr); // 执行 S-box 层
        state[0] += P::Scalar::from_canonical_u64(FAST_PARTIAL_ROUND_CONSTANTS[r]); // 加入常量
        mds_partial_layer_fast_field(&mut state, r); // 执行快速 MDS 层
    }
    partial_sbox_layer(lv, &mut state, N_PARTIAL_ROUNDS - 1, yield_constr); // 执行最后一轮 S-box 层
    mds_partial_layer_fast_field(&mut state, N_PARTIAL_ROUNDS - 1); // 执行最后一轮 MDS 层

round_ctr += N_PARTIAL_ROUNDS; // 更新轮次计数器

// 执行最后一轮完整轮次的计算
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_field(&mut state, round_ctr); // 执行常量层
        sbox_layer_field(lv, &mut state, r, false, yield_constr); // 执行 S-box 层
        mds_layer_field(&mut state); // 执行 MDS 层

round_ctr += 1; // 更新轮次计数器
    }

// 为每个输出值生成约束
    for i in 0..SPONGE_WIDTH {
        yield_constr.constraint(state[i] - lv[reg_out(i)]); // 生成约束，确保输出值正确
    }
}

```

- **`eval_packed_generic`**: 该函数生成了 Poseidon 哈希电路中的每个计算步骤的约束，包括常量层、S-box 层和 MDS 层。它逐步通过每一轮的计算生成电路约束，确保每一轮的结果都满足预期。

## 3.13 测试部分

### 3.13.1 `test_stark_degree` 函数

```rust
// `test_stark_degree` 用于测试电路的约束度数是否符合预期
#[test]
fn test_stark_degree() -> Result<()> {
    const D: usize = 2;
    type C = PoseidonGoldilocksConfig;
    type F = <C as GenericConfig<D>>::F;
    type S = PoseidonStark<F, D>;

let stark = S {
        f: Default::default(),
    };
    test_stark_low_degree(stark) // 测试电路的低度数约束
}

```

- **`test_stark_degree`**: 该测试用来确保电路的约束度数符合预期，检查电路是否满足约束条件。

### 3.13.2 `test_eval_consistency` 函数

```rust
// `test_eval_consistency` 用于验证电路计算的一致性
#[test]
fn test_eval_consistency() {
    const D: usize = 2;
    type C = PoseidonGoldilocksConfig;
    type F = <C as GenericConfig<D>>::F;
    type S = PoseidonStark<F, D>;

let stark = S::default();

init_logger();

let input: ([F; SPONGE_WIDTH], usize) = (F::rand_array(), 0);
    let rows = stark.generate_trace_rows(vec![input], 4); // 生成trace行

let mut constraint_consumer = ConstraintConsumer::new(
        vec![GoldilocksField(2), GoldilocksField(3), GoldilocksField(5)],
        GoldilocksField::ONE,
        GoldilocksField::ZERO,
        GoldilocksField::ZERO,
    );
    eval_packed_generic(&rows[0], &mut constraint_consumer); // 执行约束验证
    for &acc in &constraint_consumer.constraint_accs {
        assert_eq!(acc, GoldilocksField::ZERO); // 验证约束一致性
    }
}

```

- **`test_eval_consistency`**: 该测试验证了电路的计算是否一致，即输出结果是否符合预期的约束。如果所有的约束都得到满足，则测试通过。

## 3.14 基准测试

### 3.14.1 `poseidon_benchmark` 函数

```rust
// `poseidon_benchmark` 用于进行性能基准测试，测试 Poseidon 哈希电路的计算效率
#[test]
fn poseidon_benchmark() -> Result<()> {
    const NUM_PERMS: usize = 100;
    const D: usize = 2;
    type C = PoseidonGoldilocksConfig;
    type F = <C as GenericConfig<D>>::F;
    type S = PoseidonStark<F, D>;
    let stark = S::default();
    let config = StarkConfig::standard_fast_config();

init_logger();

let input: Vec<([F; SPONGE_WIDTH], usize)> =
        (0..NUM_PERMS).map(|_| (F::rand_array(), 0)).collect(); // 随机生成输入数据

let mut timing = TimingTree::new("prove", log::Level::Debug);
    let trace_poly_values = timed!(
        timing,
        "generate trace", // 生成trace数据
        stark.generate_trace(input, 8, &mut timing)
    );

let cloned_trace_poly_values = timed!(timing, "clone", trace_poly_values.clone()); // 克隆trace数据

let trace_commitments = timed!(
        timing,
        "compute trace commitment", // 计算trace承诺
        PolynomialBatch::<F, C, D>::from_values(
            cloned_trace_poly_values,
            config.fri_config.rate_bits,
            false,
            config.fri_config.cap_height,
            &mut timing,
            None,
        )
    );
    let degree = 1 << trace_commitments.degree_log;

// 执行一个伪造的 CTL 数据
    let ctl_z_data = CtlZData {
        helper_columns: vec![PolynomialValues::zero(degree)],
        z: PolynomialValues::zero(degree),
        challenge: GrandProductChallenge {
            beta: F::ZERO,
            gamma: F::ZERO,
        },
        columns: vec![],
        filter: vec![Some(Filter::new_simple(Column::constant(F::ZERO)))],
    };
    let ctl_data = CtlData {
        zs_columns: vec![ctl_z_data.clone(); config.num_challenges],
    };

prove_single_table(
        &stark,
        &config,
        &trace_poly_values,
        &trace_commitments,
        &ctl_data,
        &GrandProductChallengeSet {
            challenges: vec![ctl_z_data.challenge; config.num_challenges],
        },
        &mut Challenger::new(),
        &mut timing,
    )?;

timing.print(); // 打印基准测试结果
    Ok(())
}

```

- **`poseidon_benchmark`**: 这个函数执行了一个基准测试，测试 Poseidon 哈希电路的性能。它通过生成随机输入并计算相应的多项式承诺，评估计算的时间和效率。最终输出性能结果。

1. Poseidon哈希函数基本介绍

Poseidon在代码中的具体执行方式包括以下6步：

1. 初始化与常量定义 目标：定义常量矩阵（如 MDS 矩阵）、轮次常量、哈希状态。核心操作：初始化哈希状态、轮次计数器等。

2. 完整轮次计算 目标：执行完整轮次计算，包括常量层、S-box 层和 MDS 层。核心操作：

常量层：每轮加上特定的轮次常量。
S-box 层：对哈希状态的每个元素进行非线性变换（如 x^3 和 x^6）。
MDS 层：对状态进行矩阵变换以增强扩散性。

3. 部分轮次计算 目标：执行部分轮次的计算，部分轮次通常包括单项式 S-box 和 MDS 层。核心操作：

执行部分常量层和快速 MDS 层，优化计算过程。
将输入状态与部分常量相加，执行部分的 MDS 变换。

4. 电路约束生成 目标：生成电路约束，确保每个计算步骤的输出符合预期。核心操作：

使用 CircuitBuilder 构建电路。
对每一轮计算（常量层、S-box 层、MDS 层）生成相应的约束。
确保电路的输出值与计算结果一致。

5. 生成多项式承诺 目标：将生成的trace数据转换为多项式并生成承诺。核心操作：

将哈希计算过程中的trace数据行转换为多项式值。
使用多项式批量处理来生成承诺。

6. 证明生成与验证 目标：使用多项式承诺生成最终的零知识证明。核心操作：

将多项式承诺与挑战结合生成最终的证明。
确保证明的正确性和有效性。

2. Poseidon 哈希的trace填充机制

在 Poseidon 哈希电路的实现中，row 和 column 是用来表示哈希计算过程中的数据和约束的结构。它们分别对应着电路中不同的输入、输出以及各个计算层的中间值。在跟踪（trace）数据的生成过程中，每一行（row）代表一次哈希计算的状态，而每一列（column）则代表哈希过程中的特定变量或计算步骤。

2.1 Row 和 Column 对应关系

Row:
- 每一行表示哈希计算的一个“时间步”或者计算过程中的某个阶段。例如，一行可能包含当前哈希状态（输入、输出、时间戳等）。
- 在电路中，row 可以包含多个 column，每个 column 代表计算中不同的值。
Column:
- 每一列表示哈希过程中的一个特定变量，如输入数据、输出数据、中间计算结果、常量、时间戳等。
- 例如，reg_in(i) 表示输入列，第 i 个输入，reg_out(i) 表示输出列，第 i 个输出。FILTER 列可以表示是否需要进行特定的筛选或操作。

2.2 Trace 填充

Trace:
- trace数据（trace）由多行（row）组成，每一行记录了哈希计算过程中的输入输出及中间状态。
- Trace 中的每一行都包含了不同列的数据。
Trace 填充过程:
- 在生成 trace 时，每一行的各列会依次填充计算结果。具体来说，generate_trace 函数会根据输入数据生成对应的 trace 数据，每个 trace 行包括从输入到输出的多个数据列。

2.3 具体实现

generate_trace_rows

rust
// `generate_trace_rows` 用于生成整个过程的trace行
fn generate_trace_rows(
    &self,
    inputs_and_timestamps: Vec&lt;([F; SPONGE_WIDTH], usize)>, // 输入数据和时间戳
    min_rows: usize, // 最小行数
) -> Vec&lt;[F; NUM_COLUMNS]> { // 返回生成的trace数据行
    let num_rows = inputs_and_timestamps
        .len()
        .max(min_rows)
        .next_power_of_two(); // 确保行数为2的幂次

    let mut rows = Vec::with_capacity(num_rows); // 初始化存储行的向量
    for input_and_timestamp in inputs_and_timestamps.iter() {
        let rows_for_perm = self.generate_trace_rows_for_perm(*input_and_timestamp, true);
        rows.push(rows_for_perm); // 为每个输入生成trace数据行
    }

    let default_row = self.generate_trace_rows_for_perm(([F::ZEROS; SPONGE_WIDTH], 0), false);
    while rows.len() &lt; num_rows {
        rows.push(default_row); // 如果行数不足，填充默认行
    }
    rows // 返回所有生成的trace数据行
}

generate_trace_rows: 该函数生成一个包含多个 row 的 trace。每一行是一个包含多个列的数据数组。例如，在每一行中，可能会有输入列、输出列、时间戳列等。

generate_trace_rows_for_perm

rust
复制编辑
// 生成单个哈希的trace数据行，包括输入数据、输出数据以及时间戳
fn generate_trace_rows_for_perm(
    &self,
    input_and_timestamp: ([F; SPONGE_WIDTH], usize), // 输入数据和时间戳
    need_ctl: bool, // 是否需要使用CTF（Cross Table Filter）
) -> [F; NUM_COLUMNS] { // 返回生成的trace数据行
    let (hash, mut rows) = poseidon_with_witness(&input_and_timestamp.0); // 计算哈希并生成证明
    rows[FILTER] = F::from_bool(need_ctl); // 设置FILTER字段（控制标志）
    for i in 0..SPONGE_WIDTH {
        rows[reg_in(i)] = input_and_timestamp.0[i]; // 将输入数据填充到rows中的相应列
        rows[reg_out(i)] = hash[i]; // 将哈希结果填充到输出列
    }
    rows[TIMESTAMP] = F::from_canonical_usize(input_and_timestamp.1); // 设置时间戳
    rows // 返回填充后的完整trace数据行
}

generate_trace_rows_for_perm: 该函数为每个输入数据生成一个完整的trace数据行。每个 row 包含多个 column，如输入列、输出列、时间戳列、以及其他计算中间结果的列。

3. 代码详解

接下来将重点分析一下PoseidonStark的代码结构

3.1 核心数据结构和常量

// PoseidonStark 结构体，使用泛型 F 和常量 D
// F: 是有限域类型，D: 是扩展域的深度
// PhantomData&lt;F> 用来告诉 Rust 编译器该结构体与 F 类型相关，但实际不直接存储它
#[derive(Copy, Clone, Default)]
pub struct PoseidonStark&lt;F, const D: usize> {
    pub(crate) f: PhantomData&lt;F>, // 用 PhantomData 标明结构体与 F 关联
}

Poseidon Stark: 这是一个结构体，目的是实现 Poseidon 哈希的 Stark 电路。PhantomData<F> 是为了告诉 Rust 编译器，虽然我们不直接存储 F 类型的值，但我们会在类型中用到它。
常量定义: 代码中定义了一些常量，像 ALL_ROUND_CONSTANTS 和 MDS_MATRIX_CIRC，它们是 Poseidon 哈希计算的核心部分，涉及每一轮的常量和矩阵运算。

3.2 Poseidon 哈希的计算流程

3.2.1 `poseidon_with_witness` 函数

// `poseidon_with_witness` 计算 Poseidon 哈希，并生成与输入状态相关的“证明” witness
// 输入数据是一个长度为 SPONGE_WIDTH 的数组，输出是哈希结果和证明数据
pub fn poseidon_with_witness&lt;F: PrimeField64>(
    input: &[F; SPONGE_WIDTH], // 输入数据
) -> ([F; SPONGE_WIDTH], [F; NUM_COLUMNS]) { // 返回计算结果和证明数据
    let mut state = *input; // 初始化哈希状态，直接使用输入数据作为初始状态
    let mut witness = [F::ZEROS; NUM_COLUMNS]; // 初始化证明数据，所有值设为零
    let mut round_ctr = 0; // 初始化轮次计数器

    // 执行完整轮次的哈希计算
    full_rounds(&mut state, &mut witness, &mut round_ctr, true);
    // 执行部分轮次的哈希计算
    partial_rounds(&mut state, &mut witness, &mut round_ctr);
    // 再次执行完整轮次的哈希计算
    full_rounds(&mut state, &mut witness, &mut round_ctr, false);

    // 确保轮次计数器的最终值为预期的 N_ROUNDS
    debug_assert_eq!(round_ctr, N_ROUNDS);

    (state, witness) // 返回计算后的状态和证明数据
}

poseidon_with_witness: 这是一个核心函数，负责执行 Poseidon 哈希的完整计算，并生成对应的证明数据（即 witness）。哈希计算分为三个阶段：完整轮次、部分轮次和再次完整轮次。

3.2.2 `full_rounds` 函数

// 处理完整的哈希轮次（包括常量层、S-Box层和MDS层）
fn full_rounds&lt;F: PrimeField64>(
    state: &mut [F; SPONGE_WIDTH], // 当前哈希状态
    witness: &mut [F; NUM_COLUMNS], // 存储证明数据
    round_ctr: &mut usize, // 当前轮次
    is_first_full_round: bool, // 是否为第一次完整轮次
) {
    for r in 0..HALF_N_FULL_ROUNDS { // 完整轮次共需要 HALF_N_FULL_ROUNDS 轮
        constant_layer(state, *round_ctr); // 执行常量层
        sbox_layer(state, witness, r, is_first_full_round); // 执行S-Box层
        *state = mds_layer(state); // 执行MDS层
        *round_ctr += 1; // 轮次计数器递增
    }
}

full_rounds: 处理完整的轮次，在每一轮中，哈希状态会经过常量层、S-Box 层和 MDS 层的变换，最终得到新的状态。

3.2.3 `partial_rounds` 函数

// 处理部分轮次的计算
fn partial_rounds&lt;F: PrimeField64>(
    state: &mut [F; SPONGE_WIDTH], // 当前哈希状态
    witness: &mut [F; NUM_COLUMNS], // 存储证明数据
    round_ctr: &mut usize, // 当前轮次
) {
    partial_first_constant_layer(state); // 执行部分常量层
    *state = mds_partial_layer_init(state); // 初始化部分MDS层

    for i in 0..N_PARTIAL_ROUNDS { // 处理每一轮部分轮次，部分轮次总共有 N_PARTIAL_ROUNDS 轮
        state[0] = sbox_monomial(state[0], witness, reg_partial_s0(i), reg_partial_s1(i)); // 执行单项式S-Box层
        unsafe {
            state[0] = state[0].add_canonical_u64(FAST_PARTIAL_ROUND_CONSTANTS[i]); // 加入常量
        }
        *state = mds_partial_layer_fast(state, i); // 执行快速MDS层
    }
    *round_ctr += N_PARTIAL_ROUNDS; // 更新轮次计数器
}

partial_rounds: 处理部分轮次。在部分轮次中，首先执行常量层，然后进行 MDS 层的初始化，最后执行每一轮的单项式 S-Box 和 MDS 层。

3.3 生成trace数据

// `generate_trace_rows` 生成trace数据行，通常在多项式承诺系统中使用
fn generate_trace_rows(
    &self,
    inputs_and_timestamps: Vec&lt;([F; SPONGE_WIDTH], usize)>, // 输入数据和时间戳
    min_rows: usize, // 最小行数
) -> Vec&lt;[F; NUM_COLUMNS]> { // 返回生成的trace数据行
    let num_rows = inputs_and_timestamps
        .len()
        .max(min_rows)
        .next_power_of_two(); // 保证行数为2的幂次

    let mut rows = Vec::with_capacity(num_rows); // 初始化存储行的向量
    for input_and_timestamp in inputs_and_timestamps.iter() {
        let rows_for_perm = self.generate_trace_rows_for_perm(*input_and_timestamp, true); // 为每个输入生成一行trace数据
        rows.push(rows_for_perm); // 将生成的行添加到向量中
    }

    let default_row = self.generate_trace_rows_for_perm(([F::ZEROS; SPONGE_WIDTH], 0), false); // 创建一个默认行
    while rows.len() &lt; num_rows { // 如果行数小于所需的数量
        rows.push(default_row); // 添加默认行直到行数满足要求
    }
    rows // 返回所有生成的trace数据行
}

generate_trace_rows: 该函数用于生成trace数据行，这些数据行包含哈希计算的每个步骤及其输入输出。生成的行数会被调整为 2 的幂次，以适应多项式承诺的要求。

3.3.1 `generate_trace_rows_for_perm` 函数

// 生成单个哈希的trace数据行，包括输入数据、输出数据以及时间戳
fn generate_trace_rows_for_perm(
    &self,
    input_and_timestamp: ([F; SPONGE_WIDTH], usize), // 输入数据和时间戳
    need_ctl: bool, // 是否需要使用CTF（Cross Table Filter）
) -> [F; NUM_COLUMNS] { // 返回计算出的trace数据行
    let (hash, mut rows) = poseidon_with_witness(&input_and_timestamp.0); // 计算Poseidon哈希和生成证明
    rows[FILTER] = F::from_bool(need_ctl); // 设置FILTER字段
    for i in 0..SPONGE_WIDTH {
        rows[reg_in(i)] = input_and_timestamp.0[i]; // 将输入数据填充到rows中的相应列
    }
    rows[reg_out(0)] = hash[0]; // 将哈希结果的第一个元素存储在输出列中
    rows[reg_out(1)] = hash[1]; // 将哈希结果的第二个元素存储在输出列中
    rows // 返回生成的完整trace数据行
}

generate_trace_rows_for_perm: 这个函数为每一个输入生成一行trace数据。它包含输入、输出数据以及时间戳等信息，并且可以选择是否需要Cross Table Filter（CTF）。

3.4 S-Box 层和 MDS 层

3.4.1 S-Box 层

// S-box 层：对每个输入元素进行非线性变换。
// 这个变换是通过计算 x^3 和 x^6 来实现的
fn sbox_layer&lt;F: PrimeField64>(
    state: &mut [F; SPONGE_WIDTH], // 当前哈希状态
    witness: &mut [F; NUM_COLUMNS], // 存储证明数据
    r: usize, // 当前轮次
    is_first_full_round: bool, // 是否是第一次完整轮次
) {
    for i in 0..SPONGE_WIDTH {
        // 根据是否是第一次完整轮次，选择不同的列
        let idx0 = if is_first_full_round {
            reg_full0_s0(r, i)
        } else {
            reg_full1_s0(r, i)
        };
        let idx1 = if is_first_full_round {
            reg_full0_s1(r, i)
        } else {
            reg_full1_s1(r, i)
        };

        // 对当前哈希状态的每个元素应用单项式S-Box
        state[i] = sbox_monomial(state[i], witness, idx0, idx1);
    }
}

sbox_layer: 该函数是 Poseidon 哈希中的非线性部分，它对每个哈希状态的元素执行 S-Box 操作。S-Box 操作通常是通过对每个输入元素执行 x^3 和 x^6 来实现的，从而使得哈希具有更强的非线性特性，增强其抗碰撞能力。

3.4.2 S-Box 单项式

// 单项式 S-Box 变换：计算 x^3 和 x^6，返回新的值
fn sbox_monomial&lt;F: PrimeField64>(
    x: F, // 当前元素
    witness: &mut [F; NUM_COLUMNS], // 存储证明数据
    idx0: usize, // 对应列索引
    idx1: usize, // 对应列索引
) -> F {
    let x3 = x.cube(); // 计算 x^3
    let x6 = x3.square(); // 计算 x^6
    let out = x.mul(x6); // 计算 x^9 = x * x^6
    witness[idx0] = x3; // 保存 x^3 作为证明
    witness[idx1] = out; // 保存 x^9 作为证明
    out // 返回新的值
}

sbox_monomial: 这是实际进行 S-Box 计算的函数，它计算 x^3 和 x^6，然后返回 x * x^6（即 x^9），并将中间结果保存到 witness 中。这些中间结果会在后续的验证过程中使用。

3.4.3 MDS 层

// MDS 层：对哈希状态进行线性变换，使用矩阵乘法
fn mds_layer&lt;F: PrimeField64>(state_: &[F; SPONGE_WIDTH]) -> [F; SPONGE_WIDTH] {
    let mut result = [F::ZERO; SPONGE_WIDTH]; // 初始化输出结果数组

    let mut state = [0u64; SPONGE_WIDTH]; // 使用 64 位的非规范化表示
    for r in 0..SPONGE_WIDTH {
        state[r] = state_[r].to_noncanonical_u64(); // 转换为非规范化表示
    }

    // 通过矩阵乘法计算 MDS 层的输出
    for r in 0..12 {
        if r &lt; SPONGE_WIDTH {
            let sum = mds_row_shf(r, &state); // 执行矩阵乘法
            let sum_lo = sum as u64;
            let sum_hi = (sum >> 64) as u32;
            result[r] = F::from_noncanonical_u96((sum_lo, sum_hi)); // 重新转换为规范化表示
        }
    }

    result // 返回计算结果
}

mds_layer: MDS（最大距离可分离）层用于通过矩阵乘法对哈希状态进行混合。它增强了哈希的扩散性，使得输出对于输入的任何小变化都具有敏感性。这一层通常是线性变换，通过使用 MDS 矩阵对哈希状态进行处理。

3.4.4 MDS 行计算

// 计算 MDS 矩阵的每一行的贡献
fn mds_row_shf(r: usize, v: &[u64; SPONGE_WIDTH]) -> u128 {
    debug_assert!(r &lt; SPONGE_WIDTH); // 确保索引有效
    let mut res = 0u128;

    // 遍历所有的列，计算每一列的加权和
    for i in 0..12 {
        if i &lt; SPONGE_WIDTH {
            res += (v[(i + r) % SPONGE_WIDTH] as u128) * (MDS_MATRIX_CIRC[i] as u128);
        }
    }
    res += (v[r] as u128) * (MDS_MATRIX_DIAG[r] as u128); // 添加对角线元素的贡献

    res // 返回结果
}

mds_row_shf: 这是 MDS 层中的矩阵乘法的具体实现。它通过遍历 MDS 矩阵的列，计算每一行的加权和。每一行的贡献由矩阵的循环部分和对角线部分决定。

3.5 部分常量层和部分 MDS 层

// 部分常量层：对状态进行加法操作，将常量加入状态中
fn partial_first_constant_layer&lt;P: PackedField>(state: &mut [P]) {
    for i in 0..SPONGE_WIDTH {
        state[i] += P::Scalar::from_canonical_u64(FAST_PARTIAL_FIRST_ROUND_CONSTANT[i]);
    }
}

// 部分 MDS 层初始化：初始化状态并进行 MDS 操作
fn mds_partial_layer_init&lt;F: PrimeField64>(state: &mut [F; SPONGE_WIDTH]) -> [F; SPONGE_WIDTH] {
    let mut result = [F::ZEROS; SPONGE_WIDTH]; // 初始化结果数组
    result[0] = state[0]; // 将第一个状态元素直接传递
    // 对剩余的状态元素应用 MDS 矩阵进行混合
    for r in 1..SPONGE_WIDTH {
        for c in 1..SPONGE_WIDTH {
            let t = F::from_canonical_u64(FAST_PARTIAL_ROUND_INITIAL_MATRIX[r - 1][c - 1]);
            result[c] += state[r] * t; // 执行矩阵乘法
        }
    }
    result // 返回新的状态
}

partial_first_constant_layer: 该函数负责将 FAST_PARTIAL_FIRST_ROUND_CONSTANT 加到状态中，这是 Poseidon 哈希中部分轮次的初始化操作。
mds_partial_layer_init: 该函数初始化状态并执行部分 MDS 层的操作，它是 Poseidon 哈希中的一部分优化。

3.6 Trace 生成与电路约束

// `eval_packed_generic` 函数用于评估哈希过程中的每个步骤，并在电路中生成约束
fn eval_packed_generic&lt;P: PackedField>(lv: &[P], yield_constr: &mut ConstraintConsumer&lt;P>) {
    let mut state = [P::default(); SPONGE_WIDTH]; // 初始化状态
    let input = (0..SPONGE_WIDTH).map(|i| lv[reg_in(i)]).collect_vec(); // 从局部值中提取输入
    state.copy_from_slice(&input); // 设置初始状态

    let mut round_ctr = 0; // 初始化轮次计数器
    // 处理完整的轮次
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_field(&mut state, round_ctr); // 执行常量层
        sbox_layer_field(lv, &mut state, r, true, yield_constr); // 执行S-Box层
        mds_layer_field(&mut state); // 执行MDS层

        round_ctr += 1; // 更新轮次计数器
    }

    // 处理部分轮次
    partial_first_constant_layer(&mut state); // 执行部分常量层
    mds_partial_layer_init_field(&mut state); // 初始化部分MDS层
    for r in 0..N_PARTIAL_ROUNDS - 1 {
        partial_sbox_layer(lv, &mut state, r, yield_constr); // 执行部分 S-Box 层
        state[0] += P::Scalar::from_canonical_u64(FAST_PARTIAL_ROUND_CONSTANTS[r]); // 加入常量
        mds_partial_layer_fast_field(&mut state, r); // 执行快速 MDS 层
    }
    partial_sbox_layer(lv, &mut state, N_PARTIAL_ROUNDS - 1, yield_constr); // 执行最后一轮部分 S-Box 层
    mds_partial_layer_fast_field(&mut state, N_PARTIAL_ROUNDS - 1); // 执行最后一轮部分 MDS 层

    round_ctr += N_PARTIAL_ROUNDS; // 更新轮次计数器

    // 处理完整的轮次
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_field(&mut state, round_ctr); // 执行常量层
        sbox_layer_field(lv, &mut state, r, false, yield_constr); // 执行S-Box层
        mds_layer_field(&mut state); // 执行MDS层

        round_ctr += 1; // 更新轮次计数器
    }

    // 为每个输出值生成约束
    for i in 0..SPONGE_WIDTH {
        yield_constr.constraint(state[i] - lv[reg_out(i)]); // 约束输出值与计算结果相等
    }
}

eval_packed_generic: 这是评估哈希计算过程的核心函数。它通过构造哈希的每一轮，应用不同的层（常量层、S-Box层、MDS层），并生成相应的电路约束。这个函数最终确保哈希计算过程是符合预期的。

3.7 电路层面的 S-Box 层与 MDS 层

3.7.1 电路层的 S-Box

// S-box 电路实现：为电路约束生成 S-Box 层的约束
fn sbox_circuit&lt;F: RichField + Extendable&lt;D>, const D: usize>(
    input: ExtensionTarget&lt;D>, // 输入目标（电路中一个扩展字段类型的目标）
    inter: ExtensionTarget&lt;D>, // 中间结果目标
    output: ExtensionTarget&lt;D>, // 输出目标
    builder: &mut CircuitBuilder&lt;F, D>, // CircuitBuilder 用于构建电路
    yield_constr: &mut RecursiveConstraintConsumer&lt;F, D>, // 生成递归约束
) {
    let cube = builder.cube_extension(input); // 计算输入的立方（x^3）
    let constraint = builder.sub_extension(cube, inter); // 生成约束：x^3 - 中间结果
    yield_constr.constraint(builder, constraint); // 添加约束到约束消费者

    // 计算 x * x^6，并生成约束：x * x^6 - 输出
    let out = builder.mul_many_extension([input, inter, inter]);
    let constraint = builder.sub_extension(out, output);
    yield_constr.constraint(builder, constraint); // 添加约束到约束消费者
}

sbox_circuit: 这是 Poseidon 哈希的 S-Box 层在电路中的实现。它首先计算输入 x 的立方（x^3），然后生成一个约束，确保计算结果与中间结果一致。接着，它计算 x * x^6，并生成一个约束，确保输出值正确。这里的 builder 用于在电路中构建约束。

3.7.2 电路层的 MDS

// MDS 电路实现：用于电路中对 MDS 层进行计算和约束
fn mds_layer_circuit&lt;F: RichField + Extendable&lt;D>, const D: usize>(
    state: &mut [ExtensionTarget&lt;D>], // 当前状态
    builder: &mut CircuitBuilder&lt;F, D>, // CircuitBuilder 用于构建电路
) {
    let res = (0..SPONGE_WIDTH)
        .map(|i| {
            // 遍历每列，构建电路约束
            let mut sum = (0..SPONGE_WIDTH)
                .map(|j| {
                    builder.mul_const_extension(
                        F::from_canonical_u64(MDS_MATRIX_CIRC[j]), // 使用 MDS 矩阵中的元素进行扩展
                        state[(j + i) % SPONGE_WIDTH], // 状态与矩阵元素相乘
                    )
                })
                .collect_vec();

            // 将对角线矩阵元素相乘并添加到结果中
            sum.push(
                builder.mul_const_extension(F::from_canonical_u64(MDS_MATRIX_DIAG[i]), state[i]),
            );

            builder.add_many_extension(sum) // 将所有项相加得到最终结果
        })
        .collect_vec();

    state.copy_from_slice(&res); // 更新状态为计算后的新值
}

mds_layer_circuit: 这是 MDS 层的电路实现。该函数根据 MDS 矩阵中的元素对状态进行扩展并计算新状态。它首先将每列与 MDS 矩阵的元素进行相乘，接着将结果相加，最后返回新的状态。这些操作通过电路约束来执行。

3.8 电路层的部分轮次和部分常量层

3.8.1 部分常量层电路

// 部分常量层电路实现：添加部分轮次的常量
fn partial_first_constant_layer_circuit&lt;F: RichField + Extendable&lt;D>, const D: usize>(
    state: &mut [ExtensionTarget&lt;D>], // 当前状态
    builder: &mut CircuitBuilder&lt;F, D>, // CircuitBuilder 用于构建电路
) {
    for i in 0..SPONGE_WIDTH {
        state[i] = builder.add_const_extension(
            state[i], // 将当前状态元素与常量相加
            F::from_canonical_u64(FAST_PARTIAL_FIRST_ROUND_CONSTANT[i]),
        );
    }
}

partial_first_constant_layer_circuit: 这个函数实现了部分轮次的常量层，它将每个状态元素与部分常量进行加法操作，并将结果更新到状态中。常量来源于 FAST_PARTIAL_FIRST_ROUND_CONSTANT。

3.8.2 部分 MDS 层初始化电路

// 部分 MDS 层初始化电路实现：初始化部分MDS层的状态
fn mds_partial_layer_init_circuit&lt;F: RichField + Extendable&lt;D>, const D: usize>(
    state: &mut [ExtensionTarget&lt;D>], // 当前状态
    builder: &mut CircuitBuilder&lt;F, D>, // CircuitBuilder 用于构建电路
) {
    let mut result = [builder.zero_extension(); SPONGE_WIDTH]; // 初始化一个零状态
    result[0] = state[0]; // 传递第一个状态元素

    // 对剩余的状态元素进行初始化并与部分 MDS 矩阵进行乘法运算
    for r in 1..12 {
        for c in 1..12 {
            result[c] = builder.mul_const_add_extension(
                F::from_canonical_u64(FAST_PARTIAL_ROUND_INITIAL_MATRIX[r - 1][c - 1]),
                state[r],
                result[c],
            );
        }
    }

    state.copy_from_slice(&result); // 更新状态为新的计算结果
}

mds_partial_layer_init_circuit: 这个函数实现了部分 MDS 层的初始化，它首先初始化一个零状态，然后将当前状态的每个元素与部分 MDS 矩阵进行乘法运算，最后更新状态为新的值。

3.9 电路层的部分 S-Box 层

3.9.1 部分 S-Box 层电路实现

// 部分 S-Box 层电路实现：为电路中的部分轮次生成 S-Box 层的约束
fn partial_sbox_layer_circuit&lt;F: RichField + Extendable&lt;D>, const D: usize>(
    lv: &[ExtensionTarget&lt;D>], // 局部值
    state: &mut [ExtensionTarget&lt;D>], // 当前状态
    r: usize, // 当前轮次
    builder: &mut CircuitBuilder&lt;F, D>, // CircuitBuilder 用于构建电路
    yield_constr: &mut RecursiveConstraintConsumer&lt;F, D>, // 递归约束消费者
) {
    let sbox_inter = lv[reg_partial_s0(r)]; // 获取 S-Box 中间值
    let sbox_out = lv[reg_partial_s1(r)]; // 获取 S-Box 输出值
    sbox_circuit(state[0], sbox_inter, sbox_out, builder, yield_constr); // 生成 S-Box 电路约束
    state[0] = sbox_out; // 更新状态
}

partial_sbox_layer_circuit: 该函数为电路中的部分轮次生成 S-Box 层的约束。它首先提取局部值中的 S-Box 中间值和输出值，然后生成电路约束，确保 S-Box 的计算结果正确。

3.10. 哈希电路约束的生成与验证

// 为电路生成最终的约束：将最终的计算结果与电路输出进行比较
fn eval_ext_circuit(
    &self,
    builder: &mut CircuitBuilder&lt;F, D>, // CircuitBuilder 用于构建电路
    vars: &Self::EvaluationFrameTarget, // 当前评估帧
    yield_constr: &mut RecursiveConstraintConsumer&lt;F, D>, // 生成递归约束
) {
    let lv = vars.get_local_values(); // 获取局部值

    let zero = builder.zero_extension(); // 创建零扩展值
    let mut state = [zero; SPONGE_WIDTH]; // 初始化状态
    let input = (0..SPONGE_WIDTH).map(|i| lv[reg_in(i)]).collect_vec(); // 提取输入值
    state.copy_from_slice(&input); // 设置初始状态

    let mut round_ctr = 0; // 初始化轮次计数器
    // 完整轮次的计算
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_circuit(&mut state, round_ctr, builder); // 执行常量层
        sbox_layer_circuit(lv, &mut state, r, true, builder, yield_constr); // 执行S-Box层
        mds_layer_circuit(&mut state, builder); // 执行MDS层

        round_ctr += 1; // 更新轮次计数器
    }

    // 部分轮次的计算
    partial_first_constant_layer_circuit(&mut state, builder); // 执行部分常量层
    mds_partial_layer_init_circuit(&mut state, builder); // 执行部分 MDS 层初始化
    for r in 0..N_PARTIAL_ROUNDS - 1 {
        partial_sbox_layer_circuit(lv, &mut state, r, builder, yield_constr); // 执行 S-Box 层
        state[0] = builder.add_const_extension(
            state[0],
            F::from_canonical_u64(FAST_PARTIAL_ROUND_CONSTANTS[r]),
        ); // 加入常量
        mds_partial_layer_fast_circuit(&mut state, r, builder); // 执行快速 MDS 层
    }
    partial_sbox_layer_circuit(lv, &mut state, N_PARTIAL_ROUNDS - 1, builder, yield_constr); // 执行最后一轮 S-Box 层
    mds_partial_layer_fast_circuit(&mut state, N_PARTIAL_ROUNDS - 1, builder); // 执行最后一轮 MDS 层

    round_ctr += N_PARTIAL_ROUNDS; // 更新轮次计数器

    // 再次执行完整轮次
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_circuit(&mut state, round_ctr, builder); // 执行常量层
        sbox_layer_circuit(lv, &mut state, r, false, builder, yield_constr); // 执行S-Box层
        mds_layer_circuit(&mut state, builder); // 执行MDS层

        round_ctr += 1; // 更新轮次计数器
    }

    // 为每个输出生成约束，确保电路中的状态与输出值匹配
    for i in 0..SPONGE_WIDTH {
        let z = builder.sub_extension(state[i], lv[reg_out(i)]); // 计算约束
        yield_constr.constraint(builder, z); // 添加约束
    }
}

eval_ext_circuit: 该函数负责将 Poseidon 哈希计算过程转化为电路约束。在电路中，首先计算完整轮次，接着进行部分轮次，最后再计算完整轮次。每一轮的计算都会生成对应的约束，确保计算结果在电路中正确。

3.11 验证与多项式承诺相关的部分

3.11.1 `generate_trace` 函数

// `generate_trace` 函数生成最终的跟踪数据，它将输入转换为多项式承诺
pub fn generate_trace(
    &self,
    inputs: Vec&lt;([F; SPONGE_WIDTH], usize)>, // 输入数据和时间戳
    min_rows: usize, // 最小行数
    timing: &mut TimingTree, // 用于跟踪性能的计时器
) -> Vec&lt;PolynomialValues&lt;F>> { // 返回一个包含多项式值的向量
    // 生成trace行，生成多项式值并转换为相应的多项式
    let trace_rows = timed!(
        timing,
        "generate trace rows", // 标记此操作
        self.generate_trace_rows(inputs, min_rows)
    );
    let trace_polys = timed!(
        timing,
        "convert to PolynomialValues", // 标记转换操作
        trace_rows_to_poly_values(trace_rows) // 将trace数据行转换为多项式值
    );
    trace_polys // 返回多项式值
}

generate_trace: 该函数的目的是生成 Poseidon 哈希的跟踪数据，并将其转换为多项式值，方便用于零知识证明。它首先生成所有的trace行，然后将这些trace行转换为多项式值，最终得到的结果将用于多项式承诺。

3.11.2 `trace_rows_to_poly_values` 函数

// `trace_rows_to_poly_values` 函数将跟踪数据行转换为多项式值
pub fn trace_rows_to_poly_values&lt;F: Field>(
    trace_rows: Vec&lt;[F; NUM_COLUMNS]>, // 传入的trace数据行
) -> Vec&lt;PolynomialValues&lt;F>> { // 返回多项式值
    let mut polys = Vec::new(); // 初始化一个多项式集合

    for row in trace_rows {
        let mut poly_vals = Vec::new(); // 存储每行的多项式值
        for &val in row.iter() {
            poly_vals.push(PolynomialValues::from_value(val)); // 将每个值转换为多项式
        }
        polys.push(poly_vals); // 添加到多项式集合中
    }

    polys // 返回多项式集合
}

trace_rows_to_poly_values: 该函数将跟踪数据行转换为多项式值，以便后续操作使用。每一行的值都被转换成一个 PolynomialValues 对象，这些对象最终用于多项式承诺和零知识证明的计算。

3.12 约束生成与电路验证

3.12.1 `constraint_degree` 函数

// `constraint_degree` 函数返回电路的约束度数
fn constraint_degree(&self) -> usize {
    3 // 返回约束的度数
}

constraint_degree: 该函数定义了电路约束的度数。约束度数决定了电路的复杂度和多项式承诺的计算复杂度。这里返回的 3 表示电路的每个约束都是三次的（即三次多项式约束）。

3.12.2 `eval_packed_generic` 与电路约束

// `eval_packed_generic` 为每一轮计算生成对应的电路约束
fn eval_packed_generic&lt;P: PackedField>(lv: &[P], yield_constr: &mut ConstraintConsumer&lt;P>) {
    let mut state = [P::default(); SPONGE_WIDTH]; // 初始化状态
    let input = (0..SPONGE_WIDTH).map(|i| lv[reg_in(i)]).collect_vec(); // 从局部值中提取输入
    state.copy_from_slice(&input); // 设置初始状态

    let mut round_ctr = 0; // 初始化轮次计数器
    // 执行每个轮次的约束生成，包含常量层、S-box 层和 MDS 层
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_field(&mut state, round_ctr); // 执行常量层
        sbox_layer_field(lv, &mut state, r, true, yield_constr); // 执行 S-box 层
        mds_layer_field(&mut state); // 执行 MDS 层

        round_ctr += 1; // 更新轮次计数器
    }

    // 执行部分轮次的约束生成
    partial_first_constant_layer(&mut state); // 执行部分常量层
    mds_partial_layer_init_field(&mut state); // 执行部分 MDS 层初始化
    for r in 0..N_PARTIAL_ROUNDS - 1 {
        partial_sbox_layer(lv, &mut state, r, yield_constr); // 执行 S-box 层
        state[0] += P::Scalar::from_canonical_u64(FAST_PARTIAL_ROUND_CONSTANTS[r]); // 加入常量
        mds_partial_layer_fast_field(&mut state, r); // 执行快速 MDS 层
    }
    partial_sbox_layer(lv, &mut state, N_PARTIAL_ROUNDS - 1, yield_constr); // 执行最后一轮 S-box 层
    mds_partial_layer_fast_field(&mut state, N_PARTIAL_ROUNDS - 1); // 执行最后一轮 MDS 层

    round_ctr += N_PARTIAL_ROUNDS; // 更新轮次计数器

    // 执行最后一轮完整轮次的计算
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_field(&mut state, round_ctr); // 执行常量层
        sbox_layer_field(lv, &mut state, r, false, yield_constr); // 执行 S-box 层
        mds_layer_field(&mut state); // 执行 MDS 层

        round_ctr += 1; // 更新轮次计数器
    }

    // 为每个输出值生成约束
    for i in 0..SPONGE_WIDTH {
        yield_constr.constraint(state[i] - lv[reg_out(i)]); // 生成约束，确保输出值正确
    }
}

eval_packed_generic: 该函数生成了 Poseidon 哈希电路中的每个计算步骤的约束，包括常量层、S-box 层和 MDS 层。它逐步通过每一轮的计算生成电路约束，确保每一轮的结果都满足预期。

3.13 测试部分

3.13.1 `test_stark_degree` 函数

// `test_stark_degree` 用于测试电路的约束度数是否符合预期
#[test]
fn test_stark_degree() -> Result&lt;()> {
    const D: usize = 2;
    type C = PoseidonGoldilocksConfig;
    type F = &lt;C as GenericConfig&lt;D>>::F;
    type S = PoseidonStark&lt;F, D>;

    let stark = S {
        f: Default::default(),
    };
    test_stark_low_degree(stark) // 测试电路的低度数约束
}

test_stark_degree: 该测试用来确保电路的约束度数符合预期，检查电路是否满足约束条件。

3.13.2 `test_eval_consistency` 函数

// `test_eval_consistency` 用于验证电路计算的一致性
#[test]
fn test_eval_consistency() {
    const D: usize = 2;
    type C = PoseidonGoldilocksConfig;
    type F = &lt;C as GenericConfig&lt;D>>::F;
    type S = PoseidonStark&lt;F, D>;

    let stark = S::default();

    init_logger();

    let input: ([F; SPONGE_WIDTH], usize) = (F::rand_array(), 0);
    let rows = stark.generate_trace_rows(vec![input], 4); // 生成trace行

    let mut constraint_consumer = ConstraintConsumer::new(
        vec![GoldilocksField(2), GoldilocksField(3), GoldilocksField(5)],
        GoldilocksField::ONE,
        GoldilocksField::ZERO,
        GoldilocksField::ZERO,
    );
    eval_packed_generic(&rows[0], &mut constraint_consumer); // 执行约束验证
    for &acc in &constraint_consumer.constraint_accs {
        assert_eq!(acc, GoldilocksField::ZERO); // 验证约束一致性
    }
}

test_eval_consistency: 该测试验证了电路的计算是否一致，即输出结果是否符合预期的约束。如果所有的约束都得到满足，则测试通过。

3.14 基准测试

3.14.1 `poseidon_benchmark` 函数

// `poseidon_benchmark` 用于进行性能基准测试，测试 Poseidon 哈希电路的计算效率
#[test]
fn poseidon_benchmark() -> Result&lt;()> {
    const NUM_PERMS: usize = 100;
    const D: usize = 2;
    type C = PoseidonGoldilocksConfig;
    type F = &lt;C as GenericConfig&lt;D>>::F;
    type S = PoseidonStark&lt;F, D>;
    let stark = S::default();
    let config = StarkConfig::standard_fast_config();

    init_logger();

    let input: Vec&lt;([F; SPONGE_WIDTH], usize)> =
        (0..NUM_PERMS).map(|_| (F::rand_array(), 0)).collect(); // 随机生成输入数据

    let mut timing = TimingTree::new("prove", log::Level::Debug);
    let trace_poly_values = timed!(
        timing,
        "generate trace", // 生成trace数据
        stark.generate_trace(input, 8, &mut timing)
    );

    let cloned_trace_poly_values = timed!(timing, "clone", trace_poly_values.clone()); // 克隆trace数据

    let trace_commitments = timed!(
        timing,
        "compute trace commitment", // 计算trace承诺
        PolynomialBatch::&lt;F, C, D>::from_values(
            cloned_trace_poly_values,
            config.fri_config.rate_bits,
            false,
            config.fri_config.cap_height,
            &mut timing,
            None,
        )
    );
    let degree = 1 &lt;&lt; trace_commitments.degree_log;

    // 执行一个伪造的 CTL 数据
    let ctl_z_data = CtlZData {
        helper_columns: vec![PolynomialValues::zero(degree)],
        z: PolynomialValues::zero(degree),
        challenge: GrandProductChallenge {
            beta: F::ZERO,
            gamma: F::ZERO,
        },
        columns: vec![],
        filter: vec![Some(Filter::new_simple(Column::constant(F::ZERO)))],
    };
    let ctl_data = CtlData {
        zs_columns: vec![ctl_z_data.clone(); config.num_challenges],
    };

    prove_single_table(
        &stark,
        &config,
        &trace_poly_values,
        &trace_commitments,
        &ctl_data,
        &GrandProductChallengeSet {
            challenges: vec![ctl_z_data.challenge; config.num_challenges],
        },
        &mut Challenger::new(),
        &mut timing,
    )?;

    timing.print(); // 打印基准测试结果
    Ok(())
}

poseidon_benchmark: 这个函数执行了一个基准测试，测试 Poseidon 哈希电路的性能。它通过生成随机输入并计算相应的多项式承诺，评估计算的时间和效率。最终输出性能结果。

原创
学分: 13
分类: Layer2
标签: zkVM zkMIPS

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。

【zkMIPS系列】ZKM Prover—Poseidon STARK

1. Poseidon哈希函数基本介绍

2. Poseidon 哈希的trace填充机制

2.1 Row 和 Column 对应关系

2.2 Trace 填充

2.3 具体实现

3. 代码详解

3.1 核心数据结构和常量

3.2 Poseidon 哈希的计算流程

3.2.1 poseidon_with_witness 函数

3.2.2 full_rounds 函数

3.2.3 partial_rounds 函数

3.3 生成trace数据

3.3.1 generate_trace_rows_for_perm 函数

3.4 S-Box 层和 MDS 层

3.4.1 S-Box 层

3.4.2 S-Box 单项式

3.4.3 MDS 层

3.4.4 MDS 行计算

3.5 部分常量层和部分 MDS 层

3.6 Trace 生成与电路约束

3.7 电路层面的 S-Box 层与 MDS 层

3.7.1 电路层的 S-Box

3.7.2 电路层的 MDS

3.8 电路层的部分轮次和部分常量层

3.8.1 部分常量层电路

3.8.2 部分 MDS 层初始化电路

3.9 电路层的部分 S-Box 层

3.9.1 部分 S-Box 层电路实现

3.10. 哈希电路约束的生成与验证

3.11 验证与多项式承诺相关的部分

3.11.1 generate_trace 函数

3.11.2 trace_rows_to_poly_values 函数

3.12 约束生成与电路验证

3.12.1 constraint_degree 函数

3.12.2 eval_packed_generic 与电路约束

3.13 测试部分

3.13.1 test_stark_degree 函数

3.13.2 test_eval_consistency 函数

3.14 基准测试

3.14.1 poseidon_benchmark 函数

0 条评论

专栏: zkMIPS解读

文章目录

3.2.1 `poseidon_with_witness` 函数

3.2.2 `full_rounds` 函数

3.2.3 `partial_rounds` 函数

3.3.1 `generate_trace_rows_for_perm` 函数

3.11.1 `generate_trace` 函数

3.11.2 `trace_rows_to_poly_values` 函数

3.12.1 `constraint_degree` 函数

3.12.2 `eval_packed_generic` 与电路约束

3.13.1 `test_stark_degree` 函数

3.13.2 `test_eval_consistency` 函数

3.14.1 `poseidon_benchmark` 函数