Outer Loop: Iterate Over x_out Values

for x_out_val in x_out_start..x_out_end {
    let mut inner_acc: [Acc8S<F>; UNIVARIATE_SKIP_DEGREE] = [Acc8S::<F>::new(); UNIVARIATE_SKIP_DEGREE];

What’s happening: - Process each x_out value in this chunk - inner_acc[j]: Bigint accumulator for summing over all (x_in’, b) at this x_out - Uses 8-limb signed accumulator to avoid frequent modular reductions

Inner Loop: Iterate Over x_in’ Values

for x_in_prime in 0..num_x_in_half {
    let base_step_idx = (x_out_val << iter_num_x_in_prime_vars) | x_in_prime;
    let row_inputs = R1CSCycleInputs::from_trace::<F>(preprocess, trace, base_step_idx);

What’s happening: - base_step_idx = (x_out_val << iter_num_x_in_prime_vars) | x_in_prime: Constructs the timestep index \(t\) - Bit layout: [x_out bits | x_in’ bits] - This encodes the position in the execution trace - row_inputs: The 36 witness fields for this timestep \(t\)

Key insight: We fetch trace data once per (x_out, x_in’) and use it for both constraint groups!

Processing Group 0 (b=0)

let x_in_even = x_in_prime << 1;
let e_in_even = E_in[x_in_even];
let az0_bool = eval_az_first_group(&row_inputs);
let bz0_i128 = eval_bz_first_group(&row_inputs);

What’s happening: - x_in_even = x_in_prime << 1: Append bit 0 to get full x_in index for Group 0 - e_in_even = eq(tau_in, (x_in', 0)): The eq polynomial evaluation for this group - az0_bool[i]: Az values for Group 0 at all 10 base domain points \(y_i \in \{-4,...,5\}\) - bz0_i128[i]: Bz values for Group 0 at all 10 base domain points

Invariant check: az0_bool[i] * bz0_i128[i] = 0 for all i (constraints satisfied in base domain)

Lagrange Interpolation for Group 0

for j in 0..UNIVARIATE_SKIP_DEGREE {
    let coeffs = &coeffs_per_j[j];
    let mut sum_c_az0_i64: i64 = 0;
    let mut sum_c_bz0_s128 = S128::from(0i128);
    for i in 0..UNIVARIATE_SKIP_DOMAIN_SIZE {
        let c = coeffs[i] as i64;
        if az0_bool[i] {
            sum_c_az0_i64 += c;
        } else {
            let term = S128::from_i128(c as i128 * bz0_i128[i]);
            sum_c_bz0_s128 += term;
        }
    }
    let sum_az0_s64 = S64::from_i64(sum_c_az0_i64);
    let prod_s192 = sum_az0_s64.mul_trunc::<2, 3>(&sum_c_bz0_s128);
    inner_acc[j].fmadd(&e_in_even, &prod_s192);
}

What’s happening: For each extended point \(Y_j\):

1. Compute \(Az_0(Y_j)\) via Lagrange: \[Az_0(Y_j) = \sum_{i=0}^{9} c_{j,i} \cdot Az_0(y_i)\] Since \(Az_0(y_i)\) is boolean (0 or 1), this simplifies to: \[Az_0(Y_j) = \sum_{i: Az_0(y_i)=1} c_{j,i}\] This is sum_c_az0_i64

2. Compute \(Bz_0(Y_j)\) via Lagrange: \[Bz_0(Y_j) = \sum_{i=0}^{9} c_{j,i} \cdot Bz_0(y_i)\] This is sum_c_bz0_s128

3. Key optimization: Due to the invariant \(Az_0(y_i) \cdot Bz_0(y_i) = 0\):

   • If \(Az_0(y_i) = 1\), then \(Bz_0(y_i) = 0\), so we only add \(c_{j,i}\) to Az sum
   • If \(Az_0(y_i) = 0\), then we only add \(c_{j,i} \cdot Bz_0(y_i)\) to Bz sum
   • The sums have disjoint support!

4. Compute product: \(Az_0(Y_j) \cdot Bz_0(Y_j)\) as prod_s192

5. Accumulate: inner_acc[j] += e_in_even * prod_s192 This adds \(\text{eq}(\tau_{in}, (x_{in}', 0)) \cdot Az_0(Y_j) \cdot Bz_0(Y_j)\) to the accumulator

Processing Group 1 (b=1)

let x_in_odd = x_in_even + 1;
let e_in_odd = E_in[x_in_odd];
let az1_bool = eval_az_second_group(&row_inputs);
let bz1 = eval_bz_second_group(&row_inputs);

What’s happening: - x_in_odd = x_in_even + 1: Append bit 1 to get full x_in index for Group 1 - e_in_odd = eq(tau_in, (x_in', 1)): The eq polynomial evaluation for this group - Group 1 constraints (9 real + 1 padding to reach 10)

Padding logic:

let g2_len = core::cmp::min(NUM_REMAINING_R1CS_CONSTRAINTS, UNIVARIATE_SKIP_DOMAIN_SIZE);
let mut az1_bool_padded: [bool; UNIVARIATE_SKIP_DOMAIN_SIZE] = [false; UNIVARIATE_SKIP_DOMAIN_SIZE];
let mut bz1_s160_padded: [S160; UNIVARIATE_SKIP_DOMAIN_SIZE] = [S160::from(0i128); UNIVARIATE_SKIP_DOMAIN_SIZE];
az1_bool_padded[..g2_len].copy_from_slice(&az1_bool[..g2_len]);
bz1_s160_padded[..g2_len].copy_from_slice(&bz1[..g2_len]);

Pads Group 1 to 10 elements with zeros (satisfies constraints trivially).

Lagrange interpolation for Group 1: Same logic as Group 0, but with S160 bigints for Bz - Result: prod_s256 - Accumulate: inner_acc[j] += e_in_odd * prod_s256

Fold with E_out and Reduce

let e_out = E_out[x_out_val];
for j in 0..UNIVARIATE_SKIP_DEGREE {
    let reduced = inner_acc[j].reduce();
    acc_field[j] += e_out * reduced;
}

What’s happening: - After summing over all (x_in’, b), we have computed: \[\text{inner\_acc}[j] = \sum_{x_{in}', b} \text{eq}(\tau_{in}, (x_{in}', b)) \cdot Az_{t,b}(Y_j) \cdot Bz_{t,b}(Y_j)\] where \(t = (x_{out}, x_{in}')\)

• Multiply by \(\text{eq}(\tau_{out}, x_{out})\) and add to accumulator: \[\text{acc\_field}[j] \mathrel{+}= \text{eq}(\tau_{out}, x_{out}) \cdot \text{inner\_acc}[j]\]

• reduce(): Convert bigint accumulator back to field element (modular reduction)

Parallel Reduction

.reduce(
    || [F::zero(); UNIVARIATE_SKIP_DEGREE],
    |mut a, b| {
        for j in 0..UNIVARIATE_SKIP_DEGREE {
            a[j] += b[j];
        }
        a
    },
)

What’s happening: - Combine results from all parallel chunks - Sum up acc_field[j] across all chunks to get final \(g_1(Y_j)\) values

Final result: Returns [F; UNIVARIATE_SKIP_DEGREE] containing: \[g_1(Y_j) = \sum_{t \in \{0,1\}^{\log T}} \sum_{b \in \{0,1\}} \text{eq}(\tau_t, t) \cdot \text{eq}(\tau_b, b) \cdot Az_{t,b}(Y_j) \cdot Bz_{t,b}(Y_j)\]

for each extended evaluation point \(Y_j\).