1. Basic Introduction to the Poseidon Hash Function

The specific implementation of Poseidon in code involves the following six steps:

1. Initialization and Constant Definition

Goal: Define constant matrices (such as the MDS matrix), round constants, and hash state.

Core Operations: Initialize the hash state, round counter, etc.

2. Full Round Computation

Goal: Perform full round computations, including constant layer, S-box layer, and MDS layer.

Core Operations:

• Constant Layer: Add specific round constants in each round.
• S-box Layer: Apply nonlinear transformations (such as x³ and x⁶) to each element in the hash state.
• MDS Layer: Perform matrix transformations on the state to enhance diffusion.

3. Partial Round Computation

Goal: Execute partial round computations, which usually include monomial S-box and MDS layers.

Core Operations:

• Execute partial constant layer and fast MDS layer to optimize the computation process.
• Add partial constants to the input state and perform a partial MDS transformation.

4. Circuit Constraint Generation

Goal: Generate circuit constraints to ensure that each computation step produces the expected output.

Core Operations:

• Use CircuitBuilder to construct the circuit.
• Generate constraints for each round (constant layer, S-box layer, MDS layer).
• Ensure the circuit’s output values match the computation results.

5. Polynomial Commitment Generation

Goal: Convert generated trace data into polynomials and produce commitments.

Core Operations:

• Convert trace data rows from the hash computation into polynomial values.
• Use batched polynomial processing to generate commitments.

6. Proof Generation and Verification

Goal: Use polynomial commitments to generate the final zero-knowledge proof.

Core Operations:

• Combine polynomial commitments with challenges to generate the final proof.
• Ensure the proof’s correctness and validity.

2. Trace Filling Mechanism in Poseidon Hash

In the implementation of the Poseidon hash circuit, rows and columns are structures used to represent data and constraints during the hashing process. They correspond to different inputs, outputs, and intermediate values at each computation layer within the circuit. In the process of generating trace data, each row represents a state of the hash computation, while each column represents a specific variable or computation step.

2.1 Row and Column Correspondence

Row:

• Each row represents a “time step” or a certain stage in the hash computation. For example, one row may contain the current hash state (inputs, outputs, timestamps, etc.).
• In the circuit, a row can include multiple columns, each representing a different value in the computation.

Column:

• Each column represents a specific variable in the hashing process, such as input data, output data, intermediate results, constants, timestamps, etc.
• For example, reg_in(i) represents the input column for the i-th input, and reg_out(i) represents the output column for the i-th output. The FILTER column can indicate whether specific filtering or operations are needed.

2.2 Trace Filling

Trace:

• A trace consists of multiple rows, each recording inputs, outputs, and intermediate states of the hash computation.
• Each row in the trace contains data for different columns.

Trace Filling Process:

• During trace generation, the columns of each row are filled with computed results in sequence. Specifically, the generate_trace function produces the trace data based on input data, and each trace row includes multiple data columns ranging from input to output.

2.3 Implementation Details

generate_trace_rows

// `generate_trace_rows` is used to generate the trace rows for the entire process
fn generate_trace_rows(
    &self,
    inputs_and_timestamps: Vec<([F; SPONGE_WIDTH], usize)>, // Input data and timestamps
    min_rows: usize, // Minimum number of rows
) -> Vec<[F; NUM_COLUMNS]> { // Returns the generated trace rows
    let num_rows = inputs_and_timestamps
        .len()
        .max(min_rows)
        .next_power_of_two(); // Ensure the number of rows is a power of 2

    let mut rows = Vec::with_capacity(num_rows); // Initialize the vector to store 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); // Generate trace rows for each input
    }

    let default_row = self.generate_trace_rows_for_perm(([F::ZEROS; SPONGE_WIDTH], 0), false);
    while rows.len() < num_rows {
        rows.push(default_row); // If not enough rows, pad with default rows
    }
    rows // Return all generated trace rows
}

• generate_trace_rows: This function generates a trace containing multiple rows, each row being an array of values across multiple columns. For instance, each row may include input columns, output columns, timestamp columns, etc.

generate_trace_rows_for_perm

// Generates a trace data row for a single hash, including input data, output data, and timestamp
fn generate_trace_rows_for_perm(
    &self,
    input_and_timestamp: ([F; SPONGE_WIDTH], usize), // Input data and timestamp
    need_ctl: bool, // Whether to use CTF (Cross Table Filter)
) -> [F; NUM_COLUMNS] { // Returns the generated trace data row
    let (hash, mut rows) = poseidon_with_witness(&input_and_timestamp.0); // Compute the hash and generate witness
    rows[FILTER] = F::from_bool(need_ctl); // Set the FILTER field (control flag)
    for i in 0..SPONGE_WIDTH {
        rows[reg_in(i)] = input_and_timestamp.0[i]; // Fill input data into the corresponding columns
        rows[reg_out(i)] = hash[i]; // Fill hash result into output columns
    }
    rows[TIMESTAMP] = F::from_canonical_usize(input_and_timestamp.1); // Set timestamp
    rows // Return the fully populated trace data row
}

• generate_trace_rows_for_perm: This function generates a complete trace data row for each input. Each row consists of multiple columns, such as input columns, output columns, timestamp columns, and other intermediate values.

3. Code Analysis

Next, we’ll focus on analyzing the code structure of PoseidonStark.

3.1 Core Data Structures and Constants

// The PoseidonStark struct, using generic F and constant D
// F: Finite field type, D: Depth of the extension field
// PhantomData<F> is used to indicate to the Rust compiler that this struct is associated with F, even though it doesn't store it directly
#[derive(Copy, Clone, Default)]
pub struct PoseidonStark<F, const D: usize> {
    pub(crate) f: PhantomData<F>, // PhantomData indicates the struct is tied to F
}

• PoseidonStark: This is a struct that implements the Poseidon hash as a STARK circuit. PhantomData<F> tells the Rust compiler that the struct uses the type F, even though it doesn’t store a value of that type directly.
• Constant Definitions:
• The code defines several constants, such as ALL_ROUND_CONSTANTS and MDS_MATRIX_CIRC, which are core components of the Poseidon hash computation, involving constants and matrix operations used in each round.

3.2 Poseidon Hash Computation Process

3.2.1 poseidon_with_witness Function

// `poseidon_with_witness` computes the Poseidon hash and generates a witness related to the input state
// The input is an array of length SPONGE_WIDTH, and the output includes the hash result and witness data
pub fn poseidon_with_witness<F: PrimeField64>(
    input: &[F; SPONGE_WIDTH], // Input data
) -> ([F; SPONGE_WIDTH], [F; NUM_COLUMNS]) { // Returns the result and witness
    let mut state = *input; // Initialize the hash state directly with input data
    let mut witness = [F::ZEROS; NUM_COLUMNS]; // Initialize the witness with zeros
    let mut round_ctr = 0; // Initialize round counter

    // Perform full rounds of hash computation
    full_rounds(&mut state, &mut witness, &mut round_ctr, true);
    // Perform partial rounds
    partial_rounds(&mut state, &mut witness, &mut round_ctr);
    // Perform another set of full rounds
    full_rounds(&mut state, &mut witness, &mut round_ctr, false);

    // Ensure the final round count matches expected N_ROUNDS
    debug_assert_eq!(round_ctr, N_ROUNDS);

    (state, witness) // Return the final state and witness
}

• poseidon_with_witness: This is a core function responsible for executing the full Poseidon hash computation and generating the corresponding witness data. The hash process includes three phases: full rounds, partial rounds, and another set of full rounds.

3.2.2 full_rounds Function

// Handles full hash rounds (including constant layer, S-box layer, and MDS layer)
fn full_rounds<F: PrimeField64>(
    state: &mut [F; SPONGE_WIDTH], // Current hash state
    witness: &mut [F; NUM_COLUMNS], // Witness data storage
    round_ctr: &mut usize, // Round counter
    is_first_full_round: bool, // Whether this is the first set of full rounds
) {
    for r in 0..HALF_N_FULL_ROUNDS { // There are HALF_N_FULL_ROUNDS full rounds
        constant_layer(state, *round_ctr); // Execute the constant layer
        sbox_layer(state, witness, r, is_first_full_round); // Execute the S-box layer
        *state = mds_layer(state); // Execute the MDS layer
        *round_ctr += 1; // Increment the round counter
    }
}

• full_rounds: This function handles full rounds of the Poseidon hash. In each round, the state undergoes transformation through the constant layer, S-box layer, and MDS layer, eventually producing a new state.

3.2.3 partial_rounds Function

// Handles the computation of partial rounds
fn partial_rounds<F: PrimeField64>(
    state: &mut [F; SPONGE_WIDTH], // Current hash state
    witness: &mut [F; NUM_COLUMNS], // Stores witness data
    round_ctr: &mut usize, // Current round counter
) {
    partial_first_constant_layer(state); // Execute the partial constant layer
    *state = mds_partial_layer_init(state); // Initialize the partial MDS layer

    for i in 0..N_PARTIAL_ROUNDS { // Process each of the N_PARTIAL_ROUNDS partial rounds
        state[0] = sbox_monomial(state[0], witness, reg_partial_s0(i), reg_partial_s1(i)); // Execute the monomial S-Box layer
        unsafe {
            state[0] = state[0].add_canonical_u64(FAST_PARTIAL_ROUND_CONSTANTS[i]); // Add round constant
        }
        *state = mds_partial_layer_fast(state, i); // Execute the fast MDS layer
    }
    *round_ctr += N_PARTIAL_ROUNDS; // Update the round counter
}

• partial_rounds: Handles the partial rounds. In these rounds, the constant layer is executed first, followed by the initialization of the MDS layer, and then each round performs the monomial S-Box and MDS layer computations.

3.3 Generating Trace Data

// `generate_trace_rows` generates trace data rows, typically used in polynomial commitment systems
fn generate_trace_rows(
    &self,
    inputs_and_timestamps: Vec<([F; SPONGE_WIDTH], usize)>, // Input data and timestamps
    min_rows: usize, // Minimum number of rows
) -> Vec<[F; NUM_COLUMNS]> { // Returns the generated trace data rows
    let num_rows = inputs_and_timestamps
        .len()
        .max(min_rows)
        .next_power_of_two(); // Ensure the number of rows is a power of 2

    let mut rows = Vec::with_capacity(num_rows); // Initialize the vector to store rows
    for input_and_timestamp in inputs_and_timestamps.iter() {
        let rows_for_perm = self.generate_trace_rows_for_perm(*input_and_timestamp, true); // Generate a trace row for each input
        rows.push(rows_for_perm); // Add the generated row to the vector
    }

    let default_row = self.generate_trace_rows_for_perm(([F::ZEROS; SPONGE_WIDTH], 0), false); // Create a default row
    while rows.len() < num_rows { // If the number of rows is less than required
        rows.push(default_row); // Add default rows until the count is sufficient
    }
    rows // Return all generated trace rows
}

• generate_trace_rows: This function generates trace data rows, which contain each step of the hash computation and their inputs/outputs. The number of rows is adjusted to the next power of 2 to meet the requirements of polynomial commitment schemes.

3.3.1 generate_trace_rows_for_perm Function

// Generates a trace data row for a single hash, including input data, output data, and timestamp
fn generate_trace_rows_for_perm(
    &self,
    input_and_timestamp: ([F; SPONGE_WIDTH], usize), // Input data and timestamp
    need_ctl: bool, // Whether Cross Table Filter (CTF) is needed
) -> [F; NUM_COLUMNS] { // Returns the computed trace data row
    let (hash, mut rows) = poseidon_with_witness(&input_and_timestamp.0); // Compute Poseidon hash and generate witness
    rows[FILTER] = F::from_bool(need_ctl); // Set the FILTER field
    for i in 0..SPONGE_WIDTH {
        rows[reg_in(i)] = input_and_timestamp.0[i]; // Fill input data into corresponding columns
    }
    rows[reg_out(0)] = hash[0]; // Store the first hash output in the output column
    rows[reg_out(1)] = hash[1]; // Store the second hash output in the output column
    rows // Return the fully generated trace data row
}

• generate_trace_rows_for_perm: This function generates a trace data row for each input, including input data, output data, and timestamp. It also supports an optional Cross Table Filter (CTF) flag.

3.4 S-Box Layer and MDS Layer

3.4.1 S-Box Layer

// S-box layer: applies a nonlinear transformation to each input element.
// This transformation is implemented by computing x^3 and x^6
fn sbox_layer<F: PrimeField64>(
    state: &mut [F; SPONGE_WIDTH], // Current hash state
    witness: &mut [F; NUM_COLUMNS], // Stores witness data
    r: usize, // Current round
    is_first_full_round: bool, // Whether it's the first full round
) {
    for i in 0..SPONGE_WIDTH {
        // Choose different columns based on whether it's the first full round
        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)
        };

        // Apply monomial S-Box to each element of the hash state
        state[i] = sbox_monomial(state[i], witness, idx0, idx1);
    }
}

• sbox_layer: This function implements the nonlinear part of the Poseidon hash, performing an S-Box operation on each element of the hash state. The S-Box operation typically involves computing x^3 and x^6, which enhances nonlinearity and strengthens collision resistance.

3.4.2 S-Box Monomial

// Monomial S-Box transformation: computes x^3 and x^6, returns the new value
fn sbox_monomial<F: PrimeField64>(
    x: F, // Current element
    witness: &mut [F; NUM_COLUMNS], // Stores witness data
    idx0: usize, // Column index
    idx1: usize, // Column index
) -> F {
    let x3 = x.cube(); // Compute x^3
    let x6 = x3.square(); // Compute x^6
    let out = x.mul(x6); // Compute x^9 = x * x^6
    witness[idx0] = x3; // Save x^3 for proof
    witness[idx1] = out; // Save x^9 for proof
    out // Return the new value
}

• sbox_monomial: This function performs the actual S-Box computation. It calculates x^3 and x^6, then returns x * x^6 (i.e., x^9), and stores the intermediate results in the witness array for later verification.

3.4.3 MDS Layer

// MDS layer: applies a linear transformation to the hash state using matrix multiplication
fn mds_layer<F: PrimeField64>(state_: &[F; SPONGE_WIDTH]) -> [F; SPONGE_WIDTH] {
    let mut result = [F::ZERO; SPONGE_WIDTH]; // Initialize the result array

    let mut state = [0u64; SPONGE_WIDTH]; // Use 64-bit non-canonical representation
    for r in 0..SPONGE_WIDTH {
        state[r] = state_[r].to_noncanonical_u64(); // Convert to non-canonical form
    }

    // Compute MDS layer output via matrix multiplication
    for r in 0..12 {
        if r < SPONGE_WIDTH {
            let sum = mds_row_shf(r, &state); // Perform matrix multiplication
            let sum_lo = sum as u64;
            let sum_hi = (sum >> 64) as u32;
            result[r] = F::from_noncanonical_u96((sum_lo, sum_hi)); // Convert back to canonical form
        }
    }

    result // Return the result
}

• mds_layer: The MDS (Maximum Distance Separable) layer mixes the hash state using matrix multiplication. It enhances diffusion, making the output highly sensitive to input changes. This layer is a linear transformation based on an MDS matrix.

3.4.4 MDS Row Computation

// Computes the contribution of each row in the MDS matrix
fn mds_row_shf(r: usize, v: &[u64; SPONGE_WIDTH]) -> u128 {
    debug_assert!(r < SPONGE_WIDTH); // Ensure index is valid
    let mut res = 0u128;

    // Iterate over all columns to compute the weighted sum
    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); // Add diagonal element's contribution

    res // Return the result
}

• mds_row_shf: This function implements the matrix multiplication part of the MDS layer. It computes the weighted sum for each row by iterating through the circular part of the MDS matrix and adding the diagonal element’s contribution.

3.5 Partial Constant Layer and Partial MDS Layer

// Partial constant layer: adds constants to the state
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]);
    }
}

// Partial MDS layer initialization: initializes the state and performs MDS operation
fn mds_partial_layer_init<F: PrimeField64>(state: &mut [F; SPONGE_WIDTH]) -> [F; SPONGE_WIDTH] {
    let mut result = [F::ZEROS; SPONGE_WIDTH]; // Initialize result array
    result[0] = state[0]; // Directly pass the first state element
    // Apply MDS matrix to mix the remaining state elements
    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; // Perform matrix multiplication
        }
    }
    result // Return the new state
}

• partial_first_constant_layer: This function adds FAST_PARTIAL_FIRST_ROUND_CONSTANT to the state. It’s an initialization step for partial rounds in the Poseidon hash.
• mds_partial_layer_init: This function initializes the state and performs part of the MDS layer operation. It’s an optimization step within Poseidon hashing.

3.6 Trace Generation and Circuit Constraints

// `eval_packed_generic` evaluates each step of the hash process and generates constraints for the circuit
fn eval_packed_generic<P: PackedField>(lv: &[P], yield_constr: &mut ConstraintConsumer<P>) {
    let mut state = [P::default(); SPONGE_WIDTH]; // Initialize state
    let input = (0..SPONGE_WIDTH).map(|i| lv[reg_in(i)]).collect_vec(); // Extract input from local values
    state.copy_from_slice(&input); // Set initial state

    let mut round_ctr = 0; // Initialize round counter
    // Process full rounds
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_field(&mut state, round_ctr); // Apply constant layer
        sbox_layer_field(lv, &mut state, r, true, yield_constr); // Apply S-Box layer
        mds_layer_field(&mut state); // Apply MDS layer

        round_ctr += 1; // Update round counter
    }

    // Process partial rounds
    partial_first_constant_layer(&mut state); // Apply partial constant layer
    mds_partial_layer_init_field(&mut state); // Initialize partial MDS layer
    for r in 0..N_PARTIAL_ROUNDS - 1 {
        partial_sbox_layer(lv, &mut state, r, yield_constr); // Apply partial S-Box layer
        state[0] += P::Scalar::from_canonical_u64(FAST_PARTIAL_ROUND_CONSTANTS[r]); // Add constant
        mds_partial_layer_fast_field(&mut state, r); // Apply fast MDS layer
    }
    partial_sbox_layer(lv, &mut state, N_PARTIAL_ROUNDS - 1, yield_constr); // Final partial S-Box layer
    mds_partial_layer_fast_field(&mut state, N_PARTIAL_ROUNDS - 1); // Final partial MDS layer

    round_ctr += N_PARTIAL_ROUNDS; // Update round counter

    // Process final full rounds
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_field(&mut state, round_ctr); // Apply constant layer
        sbox_layer_field(lv, &mut state, r, false, yield_constr); // Apply S-Box layer
        mds_layer_field(&mut state); // Apply MDS layer

        round_ctr += 1; // Update round counter
    }

    // Generate constraints for each output value
    for i in 0..SPONGE_WIDTH {
        yield_constr.constraint(state[i] - lv[reg_out(i)]); // Constrain output value to match the result
    }
}

• eval_packed_generic: This is the core function for evaluating the hash computation process. It constructs each round of the hash, applying different layers (constant, S-Box, MDS), and generates the corresponding circuit constraints. It ensures that the hash computation follows the expected rules.

3.7 S-Box and MDS Layers at the Circuit Level

3.7.1 Circuit-Level S-Box

// S-Box circuit implementation: generates constraints for the S-Box layer in the circuit
fn sbox_circuit<F: RichField + Extendable<D>, const D: usize>(
    input: ExtensionTarget<D>, // Input target (a field extension target in the circuit)
    inter: ExtensionTarget<D>, // Intermediate result target
    output: ExtensionTarget<D>, // Output target
    builder: &mut CircuitBuilder<F, D>, // CircuitBuilder for constructing the circuit
    yield_constr: &mut RecursiveConstraintConsumer<F, D>, // Constraint consumer for recursive constraints
) {
    let cube = builder.cube_extension(input); // Compute cube of input (x^3)
    let constraint = builder.sub_extension(cube, inter); // Constraint: x^3 - intermediate
    yield_constr.constraint(builder, constraint); // Add constraint to constraint consumer

    // Compute x * x^6 and generate constraint: x * x^6 - output
    let out = builder.mul_many_extension([input, inter, inter]);
    let constraint = builder.sub_extension(out, output);
    yield_constr.constraint(builder, constraint); // Add constraint to constraint consumer
}

• sbox_circuit: This is the circuit-level implementation of the Poseidon S-Box layer. It first computes the cube of input x (x^3) and generates a constraint ensuring the result matches the intermediate value. Then it calculates x * x^6 and generates a constraint ensuring the final output is correct. The builder is used to construct these constraints within the circuit.

3.7.2 MDS Layer in Circuit

// MDS Circuit Implementation: Computes and constrains the MDS layer in a circuit
fn mds_layer_circuit<F: RichField + Extendable<D>, const D: usize>(
    state: &mut [ExtensionTarget<D>], // Current state
    builder: &mut CircuitBuilder<F, D>, // CircuitBuilder used to build the circuit
) {
    let res = (0..SPONGE_WIDTH)
        .map(|i| {
            // Traverse each column to build circuit constraints
            let mut sum = (0..SPONGE_WIDTH)
                .map(|j| {
                    builder.mul_const_extension(
                        F::from_canonical_u64(MDS_MATRIX_CIRC[j]), // Use elements from the MDS matrix
                        state[(j + i) % SPONGE_WIDTH], // Multiply state with matrix elements
                    )
                })
                .collect_vec();

            // Multiply diagonal matrix elements and add to result
            sum.push(
                builder.mul_const_extension(F::from_canonical_u64(MDS_MATRIX_DIAG[i]), state[i]),
            );

            builder.add_many_extension(sum) // Sum all terms to get the final result
        })
        .collect_vec();

    state.copy_from_slice(&res); // Update the state with the newly computed values
}

• mds_layer_circuit: This is the circuit-level implementation of the MDS layer. It expands the state using the elements of the MDS matrix and computes the new state. Each column is multiplied by the corresponding matrix elements, then summed. These operations are executed through circuit constraints.

3.8 Partial Rounds and Partial Constant Layer in Circuit

3.8.1 Partial Constant Layer Circuit

// Partial Constant Layer Circuit Implementation: Adds constants for partial rounds
fn partial_first_constant_layer_circuit<F: RichField + Extendable<D>, const D: usize>(
    state: &mut [ExtensionTarget<D>], // Current state
    builder: &mut CircuitBuilder<F, D>, // CircuitBuilder used to build the circuit
) {
    for i in 0..SPONGE_WIDTH {
        state[i] = builder.add_const_extension(
            state[i], // Add the current state element with the constant
            F::from_canonical_u64(FAST_PARTIAL_FIRST_ROUND_CONSTANT[i]),
        );
    }
}

• partial_first_constant_layer_circuit: This function implements the partial round’s constant layer by adding constants to each state element. The constants are sourced from FAST_PARTIAL_FIRST_ROUND_CONSTANT.

3.8.2 Partial MDS Layer Initialization Circuit

// Partial MDS Layer Initialization Circuit: Initializes state for partial MDS layer
fn mds_partial_layer_init_circuit<F: RichField + Extendable<D>, const D: usize>(
    state: &mut [ExtensionTarget<D>], // Current state
    builder: &mut CircuitBuilder<F, D>, // CircuitBuilder used to build the circuit
) {
    let mut result = [builder.zero_extension(); SPONGE_WIDTH]; // Initialize a zeroed state
    result[0] = state[0]; // Pass through the first state element

    // Initialize remaining state elements and perform multiplication with partial MDS matrix
    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); // Update the state with the new computed result
}

• mds_partial_layer_init_circuit: This function implements the initialization for the partial MDS layer. It starts with a zeroed state, then multiplies the state elements with the partial MDS matrix and updates the state accordingly.

3.9 Partial S-Box Layer in the Circuit

3.9.1 Implementation of the Partial S-Box Layer Circuit

// Partial S-Box Layer Circuit Implementation: Generates constraints for partial rounds of the S-Box layer in the circuit
fn partial_sbox_layer_circuit<F: RichField + Extendable<D>, const D: usize>(
    lv: &[ExtensionTarget<D>], // Local values
    state: &mut [ExtensionTarget<D>], // Current state
    r: usize, // Current round
    builder: &mut CircuitBuilder<F, D>, // CircuitBuilder used to construct the circuit
    yield_constr: &mut RecursiveConstraintConsumer<F, D>, // Recursive constraint consumer
) {
    let sbox_inter = lv[reg_partial_s0(r)]; // Get intermediate S-Box value
    let sbox_out = lv[reg_partial_s1(r)]; // Get S-Box output value
    sbox_circuit(state[0], sbox_inter, sbox_out, builder, yield_constr); // Generate S-Box circuit constraint
    state[0] = sbox_out; // Update state
}

• partial_sbox_layer_circuit: This function generates S-Box layer constraints for partial rounds in the circuit. It extracts the intermediate and output values from local values, then creates circuit constraints to ensure the correctness of the S-Box computation.

3.10 Generation and Verification of Hash Circuit Constraints

// Generate final constraints for the circuit: compare the final computed result with the circuit output
fn eval_ext_circuit(
    &self,
    builder: &mut CircuitBuilder<F, D>, // CircuitBuilder used to construct the circuit
    vars: &Self::EvaluationFrameTarget, // Current evaluation frame
    yield_constr: &mut RecursiveConstraintConsumer<F, D>, // Generates recursive constraints
) {
    let lv = vars.get_local_values(); // Get local values

    let zero = builder.zero_extension(); // Create a zero extension value
    let mut state = [zero; SPONGE_WIDTH]; // Initialize state
    let input = (0..SPONGE_WIDTH).map(|i| lv[reg_in(i)]).collect_vec(); // Extract input values
    state.copy_from_slice(&input); // Set initial state

    let mut round_ctr = 0; // Initialize round counter

    // Full rounds computation
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_circuit(&mut state, round_ctr, builder); // Execute constant layer
        sbox_layer_circuit(lv, &mut state, r, true, builder, yield_constr); // Execute S-Box layer
        mds_layer_circuit(&mut state, builder); // Execute MDS layer

        round_ctr += 1; // Update round counter
    }

    // Partial rounds computation
    partial_first_constant_layer_circuit(&mut state, builder); // Execute partial constant layer
    mds_partial_layer_init_circuit(&mut state, builder); // Execute partial MDS layer initialization
    for r in 0..N_PARTIAL_ROUNDS - 1 {
        partial_sbox_layer_circuit(lv, &mut state, r, builder, yield_constr); // Execute S-Box layer
        state[0] = builder.add_const_extension(
            state[0],
            F::from_canonical_u64(FAST_PARTIAL_ROUND_CONSTANTS[r]),
        ); // Add constant
        mds_partial_layer_fast_circuit(&mut state, r, builder); // Execute fast MDS layer
    }
    partial_sbox_layer_circuit(lv, &mut state, N_PARTIAL_ROUNDS - 1, builder, yield_constr); // Execute final S-Box layer
    mds_partial_layer_fast_circuit(&mut state, N_PARTIAL_ROUNDS - 1, builder); // Execute final MDS layer

    round_ctr += N_PARTIAL_ROUNDS; // Update round counter

    // Execute full rounds again
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_circuit(&mut state, round_ctr, builder); // Execute constant layer
        sbox_layer_circuit(lv, &mut state, r, false, builder, yield_constr); // Execute S-Box layer
        mds_layer_circuit(&mut state, builder); // Execute MDS layer

        round_ctr += 1; // Update round counter
    }

    // Generate constraints for each output to ensure state matches output values in the circuit
    for i in 0..SPONGE_WIDTH {
        let z = builder.sub_extension(state[i], lv[reg_out(i)]); // Compute constraint
        yield_constr.constraint(builder, z); // Add constraint
    }
}

• eval_ext_circuit: This function is responsible for transforming the Poseidon hash computation into circuit constraints. It first computes the full rounds, then the partial rounds, and finally another set of full rounds. Each round generates corresponding constraints to ensure the correctness of the computation in the circuit.

3.11 Verification and Polynomial Commitment-Related Sections

3.11.1 The generate_trace Function

// The `generate_trace` function generates the final trace data by converting inputs into polynomial commitments
pub fn generate_trace(
    &self,
    inputs: Vec<([F; SPONGE_WIDTH], usize)>, // Input data and timestamps
    min_rows: usize, // Minimum number of rows
    timing: &mut TimingTree, // Timer for performance tracking
) -> Vec<PolynomialValues<F>> { // Returns a vector of polynomial values
    // Generate trace rows, convert to polynomial values, and transform into corresponding polynomials
    let trace_rows = timed!(
        timing,
        "generate trace rows", // Tag this operation
        self.generate_trace_rows(inputs, min_rows)
    );
    let trace_polys = timed!(
        timing,
        "convert to PolynomialValues", // Tag conversion operation
        trace_rows_to_poly_values(trace_rows) // Convert trace rows to polynomial values
    );
    trace_polys // Return polynomial values
}

• generate_trace: This function generates trace data for the Poseidon hash and converts it into polynomial values, which are used for zero-knowledge proofs. It first generates all trace rows, then transforms them into polynomial values, which are ultimately used for polynomial commitments.

3.11.2 trace_rows_to_poly_values Function

// The `trace_rows_to_poly_values` function converts trace data rows into polynomial values
pub fn trace_rows_to_poly_values<F: Field>(
    trace_rows: Vec<[F; NUM_COLUMNS]>, // Input trace data rows
) -> Vec<PolynomialValues<F>> { // Returns polynomial values
    let mut polys = Vec::new(); // Initialize a collection of polynomials

    for row in trace_rows {
        let mut poly_vals = Vec::new(); // Store polynomial values for each row
        for &val in row.iter() {
            poly_vals.push(PolynomialValues::from_value(val)); // Convert each value into a polynomial
        }
        polys.push(poly_vals); // Add to the polynomial collection
    }

    polys // Return the collection of polynomials
}

• trace_rows_to_poly_values: This function converts trace data rows into polynomial values for further use. Each value in a row is transformed into a PolynomialValues object, which are then used for polynomial commitments and zero-knowledge proof computations.

3.12 Constraint Generation and Circuit Verification

3.12.1 constraint_degree Function

// The `constraint_degree` function returns the degree of constraints for the circuit
fn constraint_degree(&self) -> usize {
    3 // Returns the degree of constraints
}

• constraint_degree: This function defines the degree of constraints in the circuit. The constraint degree determines both the circuit’s complexity and the computation complexity of polynomial commitments. A return value of 3 means each circuit constraint is a cubic (degree 3 polynomial) constraint.

3.12.2 eval_packed_generic and Circuit Constraints

// `eval_packed_generic` generates corresponding circuit constraints for each round of computation
fn eval_packed_generic<P: PackedField>(lv: &[P], yield_constr: &mut ConstraintConsumer<P>) {
    let mut state = [P::default(); SPONGE_WIDTH]; // Initialize state
    let input = (0..SPONGE_WIDTH).map(|i| lv[reg_in(i)]).collect_vec(); // Extract input from local values
    state.copy_from_slice(&input); // Set initial state

    let mut round_ctr = 0; // Initialize round counter
    // Generate constraints for full rounds: constant layer, S-box layer, MDS layer
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_field(&mut state, round_ctr); // Execute constant layer
        sbox_layer_field(lv, &mut state, r, true, yield_constr); // Execute S-box layer
        mds_layer_field(&mut state); // Execute MDS layer

        round_ctr += 1; // Update round counter
    }

    // Generate constraints for partial rounds
    partial_first_constant_layer(&mut state); // Execute partial constant layer
    mds_partial_layer_init_field(&mut state); // Execute partial MDS layer initialization
    for r in 0..N_PARTIAL_ROUNDS - 1 {
        partial_sbox_layer(lv, &mut state, r, yield_constr); // Execute S-box layer
        state[0] += P::Scalar::from_canonical_u64(FAST_PARTIAL_ROUND_CONSTANTS[r]); // Add constant
        mds_partial_layer_fast_field(&mut state, r); // Execute fast MDS layer
    }
    partial_sbox_layer(lv, &mut state, N_PARTIAL_ROUNDS - 1, yield_constr); // Final S-box layer
    mds_partial_layer_fast_field(&mut state, N_PARTIAL_ROUNDS - 1); // Final MDS layer

    round_ctr += N_PARTIAL_ROUNDS; // Update round counter

    // Final set of full rounds
    for r in 0..HALF_N_FULL_ROUNDS {
        constant_layer_field(&mut state, round_ctr); // Execute constant layer
        sbox_layer_field(lv, &mut state, r, false, yield_constr); // Execute S-box layer
        mds_layer_field(&mut state); // Execute MDS layer

        round_ctr += 1; // Update round counter
    }

    // Generate constraints for each output value
    for i in 0..SPONGE_WIDTH {
        yield_constr.constraint(state[i] - lv[reg_out(i)]); // Ensure output values match
    }
}

• eval_packed_generic: This function generates constraints for every step in the Poseidon hash circuit, including the constant layer, S-box layer, and MDS layer. It incrementally performs each round’s computations and generates corresponding constraints to ensure correctness of results.

3.13 Testing Section

3.13.1 test_stark_degree Function

// `test_stark_degree` checks if the circuit's constraint degree meets expectations
#[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 for low-degree constraints in the circuit
}

• test_stark_degree: This test ensures the circuit’s constraint degree meets the expected value, verifying that the circuit adheres to required constraint rules.

3.13.2 test_eval_consistency Function

// `test_eval_consistency` verifies consistency in circuit computation
#[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); // Generate trace rows

    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); // Perform constraint verification
    for &acc in &constraint_consumer.constraint_accs {
        assert_eq!(acc, GoldilocksField::ZERO); // Verify constraint consistency
    }
}

• test_eval_consistency: This test verifies whether the circuit’s computation is consistent — that is, whether the output satisfies the expected constraints. If all constraints are satisfied, the test passes.

3.14 Benchmarking

3.14.1 poseidon_benchmark Function

// `poseidon_benchmark` performs a performance benchmark to test the computation efficiency of the Poseidon hash circuit
#[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(); // Randomly generate input data

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

    let cloned_trace_poly_values = timed!(timing, "clone", trace_poly_values.clone()); // Clone trace data

    let trace_commitments = timed!(
        timing,
        "compute trace commitment", // Compute trace commitments
        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;

    // Perform a dummy CTL data computation
    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(); // Print benchmark results
    Ok(())
}

• poseidon_benchmark: This function performs a benchmark test for the Poseidon hash circuit’s performance. It evaluates computational efficiency by generating random inputs and computing the corresponding polynomial commitments. Finally, it outputs the performance results.

‍

Subscribe to the ZKM Blog to stay updated with the latest research by ZKM. If you have any questions about the article, you can contact the ZKM team on discord: discord.com/zkm