Longfellow ZK

2.2.1. Extend method in Field F_p

The extend(f, n, m) method interprets the array f[0..n] as the evaluations of a polynomial P of degree less than n at the points 0,...,n-1, and returns the evaluations of the same P at the points 0,...,m-1. For sufficiently large fields |F_p| = p >= m, polynomial P is uniquely determined by the input, and thus extend is well defined.¶

As there are several algorithms for efficiently performing the extend operation, the implementor can choose a suitable one. In some cases, the brute force method of using Lagrange interpolation formulas to compute each output point independently may suffice. One can employ a convolution to implement the extend operation, and in some cases, either the Number Theoretic Transform or Nussbaumer's algorithm can be used to efficiently compute a convolution.¶

2.2.2. Extend method in Field GF 2^k

The previous section described an extend method that applies to odd prime-order finite fields which contain the elements 0,1,2...,m. In the special case of GF(2^k), the extend operator is defined in an opinionated way inspired by the Additive FFT algorithm by Lin et al [additivefft]. Lin et al. define a novel polynomial basis for polynomials as an alternative to the usual monomial basis xⁱ, and give an algorithm for evaluating a degree-(d-1) polynomial at all d points in a subspace, for d=2^ell, and for polynomials expressed in the novel basis.¶

Specifically, this document implements GF(2¹²⁸) as GF{2}[x] / (Q(x)) where¶

    Q(x) = x^{128} + x^{7} + x^{2} + x + 1

With this choice of Q(x), x is a generator of the multiplicative group of the field. Next, choose GF(2¹⁶) as the subfield of GF(2¹²⁸) with g=x^{(2^{128}-1) / (2^{16}-1)} as its generator, and beta_i=g^i^ for 0 <= i < 16 as the basis of the subfield. For relevant problem sizes, this allows encoding elements in a commitment scheme with 16-bits instead of 128.¶

Writing j_i for the i-th bit of the binary representation of j, that is,¶

    j = sum_{0 <= i < k} j_i 2^i     j_i \in {0,1}

inject integer j into a field element inj(j) by interpreting the bits of j as coordinates in terms of the basis:¶

    inj(j) = sum_{0 <= i < k} j_i beta_i

In this setting, define the extend operator to interpret the array f[0..n] to consist of the evaluations of a polynomial p(x) of degree at most n-1 at the n points x \in { inj(i) : 0 <= i < n } and to return the set { p(inj(i)) : 0 <= i < m} which consist of the evaluations of the same polynomial p(x) at the injected points 0,...,m-1.¶

This convention allows this operation to be completed efficiently using various forms of the additive FFT as described in [longfellow] [additivefft].¶

3.1.1. The FSPRF Keystream Generator

The FsPrf object generates an infinite sequence of pseudorandom bytes organized into 16-byte blocks. Block i (for i \ge 0) is computed as:¶

  Block[i] = AES256(SEED, ID(i))

where SEED is the 32-byte hash digest H(\text{tr}), and ID(i) is the 16-byte little-endian encoding of integer i.¶

use aes::{
    Aes256,
    cipher::{BlockEncrypt, KeyInit, generic_array::GenericArray},
};
use sha2::{Digest, Sha256};
use crate::algebra::{Field, Rng};

#[derive(Clone)]
pub struct FsPrf {
    _key: [u8; 32],
    cipher: Aes256,
    block_counter: u64,
    read_pointer: usize,
    output_buffer: [u8; 16],
}

impl FsPrf {
    pub fn new(key: [u8; 32]) -> Self {
        let key_arr = GenericArray::from(key);
        let cipher = Aes256::new(&key_arr);
        Self {
            _key: key,
            cipher,
            block_counter: 0,
            read_pointer: 16, // Force refill on first read
            output_buffer: [0u8; 16],
        }
    }

    fn refill(&mut self) {
        assert!(self.block_counter < 0x10000000000);
        let mut inp = [0u8; 16];
        for i in 0..8 {
            inp[i] = ((self.block_counter >> (8 * i)) & 0xff) as u8;
        }
        let mut block = GenericArray::from(inp);
        self.cipher.encrypt_block(&mut block);
        self.output_buffer.copy_from_slice(&block);
        self.block_counter += 1;
        self.read_pointer = 0;
    }

    pub fn get_bytes(&mut self, len: usize) -> Vec<u8> {
        let mut buf = Vec::with_capacity(len);
        for _ in 0..len {
            if self.read_pointer >= 16 {
                self.refill();
            }
            buf.push(self.output_buffer[self.read_pointer]);
            self.read_pointer += 1;
        }
        buf
    }
}

3.4.1. 1. Bounded Natural Numbers (generate_nat / nat)

Samples a uniformly distributed integer in [0, m - 1] via minimal bitmask rejection sampling:¶

impl Transcript {
    pub fn nat(&mut self, n: usize) -> usize {
        assert!(n > 0, "nat(0) is undefined");
        let mut nn = n;
        let mut l = 0;
        while nn != 0 {
            nn >>= 8;
            l += 1;
        }
        let mut msk = 0;
        while (n & msk) != n {
            msk = (msk << 1) | 1;
        }

        loop {
            let b = self.bytes(l);
            let mut r = 0usize;
            for i in (0..l).rev() {
                r = (r << 8) | (b[i] as usize);
            }
            r &= msk;
            if r < n {
                return r;
            }
        }
    }
}

3.4.2. 2. Combinations Without Replacement (generate_nats_wo_replacement / choose)

Samples k distinct natural numbers uniformly from [0, n - 1] without replacement (used for Ligero column query indices) using an in-place Fisher-Yates shuffle:¶

impl Transcript {
    pub fn choose(&mut self, n: usize, k: usize) -> Vec<usize> {
        if n == 0 || k == 0 {
            return Vec::new();
        }
        assert!(n >= k);
        let mut a: Vec<usize> = (0..n).collect();
        let mut res = vec![0; k];
        for i in 0..k {
            let val = self.nat(n - i);
            let j = i + val;
            a.swap(i, j);
            res[i] = a[i];
        }
        res
    }
}

3.4.3. 3. Field Elements and Vectors (generate_field / generate_challenge)

• Prime Fields (e.g. NIST P-256 scalar field \mathbb{F}_p): Samples 32 bytes from bytes(32) and rejects if the integer value \ge p.¶
• Binary Extension Fields (e.g. \text{GF}(2^{128})): Samples 16 bytes directly from bytes(16) and interprets them as the polynomial coefficients in \text{GF}(2)[X]/(X^{128} + X^7 + X^2 + X + 1). Subfield elements in \text{GF}(2^{16}) sample 2 bytes from bytes(2) and map to the subfield basis.¶

impl Transcript {
    pub fn get_elt_field<F: Field + 'static>(&mut self) -> F {
        F::sample(self)
    }

    pub fn generate_challenge<F: Field + 'static>(&mut self, n: usize) -> Vec<F> {
        (0..n).map(|_| self.get_elt_field::<F>()).collect()
    }
}

impl Rng for Transcript {
    fn bytes(&mut self, len: usize) -> Vec<u8> {
        self.get_random_bytes(len)
    }
}

4.1.1. Constructing a Merkle tree from n digests

pub fn sha256_bytes(data: &[u8]) -> Vec<u8> {
    let mut hasher = Sha256::new();
    hasher.update(data);
    hasher.finalize().to_vec()
}

#[derive(Clone, Debug)]
pub struct MerkleHeap {
    pub num_leaves: usize,
    pub layers: Vec<Vec<u8>>,
    pub root: Vec<u8>,
}

impl MerkleHeap {
    pub fn new(leaves: &[Vec<u8>]) -> Self {
        let n = leaves.len();
        let mut layers = vec![Vec::new(); 2 * n];
        layers[n..(n + n)].clone_from_slice(&leaves[..n]);
        for i in (1..n).rev() {
            let mut data = Vec::new();
            data.extend_from_slice(&layers[2 * i]);
            data.extend_from_slice(&layers[2 * i + 1]);
            layers[i] = sha256_bytes(&data);
        }
        let root = layers[1].clone();
        Self {
            num_leaves: n,
            layers,
            root,
        }
    }
}

4.1.2. Constructing a proof of inclusion

This section describes how to construct a Merkle proof that k input digests at indicies i[0],...,i[k-1] belong to the tree. The simplest way to generate such a proof is to produce independent proofs for each of the k leaves. However, this turns out to be wasteful in that internal nodes may be included multiple times along different paths, and some nodes may not need to be included at all because they are implied by nodes that have already been included.¶

To address these inefficiencies, this section explains how to produce a batch proof of inclusion for k leaves. The main idea is to start from the requested set of leaves and build all of the implied internal nodes given the leaves. For example, if sibling leaves are included, then their parent is implied, and the parent need not be included in the compressed proof. Then it suffices to revisit the same tree and include the necessary siblings along all of the Merkle paths. It is assumed that the verifier already has the leaf digests that are at the indicies, and thus the proof only contains the necessary internal nodes of the Merkle tree that are used to verify the claim.¶

It is important in this formulation to treat the input digests as a sequence, i.e. with a given order. Both the prover and verifier of this batch proof must use the same order of the requested_leaves array.¶

pub fn open_merkle_heap(
    mh: &MerkleHeap,
    leaf_indices: &[usize],
) -> Result<Vec<Vec<u8>>, &'static str> {
    let n = mh.num_leaves;
    let mut seen = vec![false; n];
    let mut is_on_path = vec![false; 2 * n];
    for &idx in leaf_indices {
        if idx >= n {
            return Err("Leaf index out of bounds in Merkle opening");
        }
        if seen[idx] {
            return Err("Duplicate leaf index in Merkle opening");
        }
        seen[idx] = true;
        is_on_path[n + idx] = true;
    }
    for i in (1..n).rev() {
        is_on_path[i] = is_on_path[2 * i] || is_on_path[2 * i + 1];
    }

    let mut path = Vec::new();
    for i in (1..n).rev() {
        if is_on_path[i] {
            if is_on_path[2 * i] && !is_on_path[2 * i + 1] {
                path.push(mh.layers[2 * i + 1].clone());
            } else if !is_on_path[2 * i] && is_on_path[2 * i + 1] {
                path.push(mh.layers[2 * i].clone());
            }
        }
    }
    Ok(path)
}

4.1.3. Verifying a proof of inclusion

This section describes how to verify a compressed Merkle proof. The claim to verify is that "the commitment root defines an n-leaf Merkle tree that contains k digests s[0], ..., s[k-1] at corresponding indices i[0], ..., i[k-1]." The strategy of this verification procedure is to deduce which nodes are needed along the k verification paths from index to root, then read these values from the purported proof, and then recompute the Merkle tree and the consistency of the root digest. As an optimization, the defined[] array avoids recomputing internal portions of the Merkle tree that are not relevant to the verification. By convention, a proof for the degenerate case of k=0 digests is defined to fail. It is assumed that the indices[] array does not contain duplicates.¶

pub fn verify_merkle_proof<F>(
    n: usize,
    root: &[u8],
    leaf_indices: &[usize],
    path: &[Vec<u8>],
    mut leaf_hash_fn: F,
) -> Result<(), &'static str>
where
    F: FnMut(usize) -> Vec<u8>,
{
    let mut seen = vec![false; n];
    let mut is_on_path = vec![false; 2 * n];
    for &idx in leaf_indices {
        if idx >= n {
            return Err("Leaf index out of bounds in Merkle proof verification");
        }
        if seen[idx] {
            return Err("Duplicate leaf index in Merkle proof verification");
        }
        seen[idx] = true;
        is_on_path[n + idx] = true;
    }
    for i in (1..n).rev() {
        is_on_path[i] = is_on_path[2 * i] || is_on_path[2 * i + 1];
    }

    let mut layers: Vec<Option<Vec<u8>>> = vec![None; 2 * n];
    for &idx in leaf_indices {
        layers[n + idx] = Some(leaf_hash_fn(idx));
    }

    let mut path_idx = 0;
    for i in (1..n).rev() {
        if is_on_path[i] {
            let left_val = if is_on_path[2 * i] {
                layers[2 * i].clone()
            } else {
                let val = path.get(path_idx).cloned();
                path_idx += 1;
                val
            };
            let right_val = if is_on_path[2 * i + 1] {
                layers[2 * i + 1].clone()
            } else {
                let val = path.get(path_idx).cloned();
                path_idx += 1;
                val
            };

            if let (Some(left_val), Some(right_val)) = (left_val, right_val) {
                let mut data = Vec::with_capacity(left_val.len() + right_val.len());
                data.extend_from_slice(&left_val);
                data.extend_from_slice(&right_val);
                layers[i] = Some(sha256_bytes(&data));
            } else {
                return Err("Missing path value in Merkle proof verification");
            }
        }
    }

    if path_idx != path.len() {
        return Err("Not all Merkle path elements were consumed");
    }

    if let Some(computed_root) = &layers[1] {
        if computed_root == root {
            Ok(())
        } else {
            Err("Merkle root mismatch")
        }
    } else {
        Err("Merkle root was not computed")
    }
}

4.2.1. Constraints on parameters

• BLOCK < |F| The block size must be smaller than the field size.¶
• BLOCK > NREQ The block size must be larger than the number of columns requested.¶
• BLOCK = NREQ + WR¶
• BLOCK >= 2 * (NREQ + WR) + (NREQ + WR) - 2¶
• BLOCK >= 2 * (NREQ + WR) - 1.¶
• WR >= NREQ (and thus WR >= NREQ) to avoid wasting too much space.¶

4.4.1. Low-degree test

In the low-degree test, the verifier sends a challenge vector consisting of nwqrow = NROW - 3 field elements, u_ldt[0..nwqrow]. This challenge is generated via the Fiat-Shamir transform. The prover computes the linear combination:¶

y_ldt = T[ILDT][0..BLOCK] + sum_{i = 0 ... nwqrow - 1} u_ldt[i] * T[IW + i][0..BLOCK]

and returns the BLOCK elements of y_ldt. Notice that the random blinding row ILDT (row 0) is included with implicit coefficient 1, while rows 1 (IDOT) and 2 (IQD) are excluded because their polynomial degree is DBLOCK (2 \cdot \text{BLOCK} - 1) rather than BLOCK. The verifier applies the extend method to this response, and verifies consistency with the opened columns of the tableau requested at the challenge indices.¶

4.4.2. Linear and Quadratic constraints

The linear test is represented by a matrix A, and a vector b, and aims to verify that A * W + b = 0. The constraint matrix A is given as input in a sparse form: it is an array of LigeroTerm triples (c,j,k) in which c indicates the constraint index, j represents the witness index, and k represents the linear coefficient. For example, if the first constraint (at index 0) is W[2] + 2*W[3] - 3 = 0, then the linear constraints array contains the terms (0,2,1), (0,3,2) and the b vector has b[0]=-3.¶

The quadratic constraints are given as input in an array lqc[] that contains triples (x,y,z); one such triple represents the constraint that W[x] * W[y] = W[z]. To process quadratic constraints, tableau T is augmented with 3 extra rows per triple, called Qx, Qy, and Qz which hold copied witnesses and their products. If the i-th quadratic constraint is (x,y,z), then the prover sets Qx[i] = W[x], Qy[i] = W[y] and Qz[i] = W[x] * W[y]. Next, the prover adds a linear constraint that Qx[i] - W[x] = 0, Qy[i] - W[y] = 0 and Qz[i] - W[z] = 0 to ensure that the copied witness is consistent.¶

In this sense, the quadratic constraints are reduced to linear constraints, and the additional requirement for the verifier to check that each index of the Qz row is the product of its counterpart in the Qx and Qy row.¶

The prover computes the quadratic test polynomial y_quad across degree DBLOCK. The middle WR witness values of y_quad are identically zero by construction and are omitted from the proof. The proof contains only the non-zero segments: quad_poly_low of length NREQ (elements 0..NREQ) and quad_poly_high of length DBLOCK - BLOCK (elements BLOCK..DBLOCK).¶

4.4.3. Selection of challenge indicies

The last step of the prove method is for the verifier to select a subset of NREQ unique indices (sampled without replacement) from the range 0..(NCOL - DBLOCK) and request that the prover open these columns of tableau T (at column offsets DBLOCK + idx). These opened columns, along with their column blinding nonces and Merkle authentication paths, are then used to verify consistency with the polynomial responses sent by the prover.¶

4.4.4. Ligero Prover procedure

The statement_hash argument is application-dependent and commits to the circuit or statement being proven.¶

impl<F: Field + 'static> LigeroProver<F> {
    pub fn prove(
        &self,
        commit: &LigeroCommitResult<F>,
        lqc: &[LqcTriple],
        a: &[LigeroTerm<F>],
        b: &[F],
        statement_hash: &[u8],
        ts: &mut Transcript,
    ) -> LigeroProof<F> {
        ts.write_bytes(statement_hash);

        let geom = self.geometry;
        let nwqrow = geom.total_rows - 3;
        let nq = lqc.len();

        let u_ldt = gen_uldt(ts, nwqrow);
        let alphal = gen_alphal(ts, b.len());
        let alphaq = gen_alphaq(ts, nq);
        let u_quad = gen_uquad(ts, geom.num_quad_rows);

        let y_ldt = self.prove_compute_y_ldt(commit, &u_ldt);
        let a_full = self.prove_compute_a_full(lqc, a, &alphal, &alphaq);
        let y_dot = self.prove_compute_y_dot(commit, &a_full);
        let y_quad = self.prove_compute_y_quad(commit, &u_quad);

        let y_quad_0 = y_quad[0..geom.num_queries].to_vec();
        let y_quad_2 = y_quad[geom.block_len..geom.dblock_len].to_vec();

        ts.write_elt_field_slice(&y_ldt);
        ts.write_elt_field_slice(&y_dot);
        ts.write_elt_field_slice(&y_quad_0);
        ts.write_elt_field_slice(&y_quad_2);

        let idx = ts.choose(geom.encoded_len - geom.dblock_len, geom.num_queries);
        let mut query_nonces = Vec::with_capacity(geom.num_queries);
        for &col in &idx {
            query_nonces.push(commit.nonces[col].clone());
        }
        let merkle_paths =
            open_merkle_heap(&commit.merkle, &idx).expect("Failed to open Merkle heap");

        let mut req = Vec::new();
        for row in 0..commit.tableau.len() {
            for &col in &idx {
                let col_idx = col + geom.dblock_len;
                req.push(commit.tableau[row][col_idx]);
            }
        }

        LigeroProof {
            ldt_poly: y_ldt,
            linear_poly: y_dot,
            quad_poly_low: y_quad_0,
            quad_poly_high: y_quad_2,
            column_nonces: query_nonces,
            queried_columns: req,
            merkle_paths,
        }
    }

    fn prove_compute_y_ldt(&self, commit: &LigeroCommitResult<F>, u_ldt: &[F]) -> Vec<F> {
        let geom = self.geometry;
        let nwqrow = geom.total_rows - 3;
        let mut y_ldt = commit.tableau[geom.ldt_row_idx()][0..geom.block_len].to_vec();
        for i in 0..nwqrow {
            axpy(
                &mut y_ldt,
                &commit.tableau[geom.witness_row_start() + i][0..geom.block_len],
                u_ldt[i],
            );
        }
        y_ldt
    }

    fn prove_compute_a_full(
        &self,
        lqc: &[LqcTriple],
        a: &[LigeroTerm<F>],
        alphal: &[F],
        alphaq: &[Vec<F>],
    ) -> Vec<F> {
        let geom = self.geometry;
        let nwqrow = geom.total_rows - 3;
        let nq = lqc.len();

        let mut a_full = vec![F::zero(); nwqrow * geom.witnesses_per_row];
        for term in a {
            a_full[term.witness_idx] += term.coeff * alphal[term.constraint_idx];
        }

        let nqtriples_w = geom.num_quad_rows * geom.witnesses_per_row;
        let ax_offset = (nwqrow - 3 * geom.num_quad_rows) * geom.witnesses_per_row;
        let ay_offset = ax_offset + nqtriples_w;
        let az_offset = ay_offset + nqtriples_w;

        for i in 0..geom.num_quad_rows {
            let mut j = 0;
            while j < geom.witnesses_per_row && j + i * geom.witnesses_per_row < nq {
                let idx = j + i * geom.witnesses_per_row;
                let l = lqc[idx];
                a_full[ax_offset + idx] += alphaq[idx][0];
                a_full[l.x] -= alphaq[idx][0];
                a_full[ay_offset + idx] += alphaq[idx][1];
                a_full[l.y] -= alphaq[idx][1];
                a_full[az_offset + idx] += alphaq[idx][2];
                a_full[l.z] -= alphaq[idx][2];
                j += 1;
            }
        }
        a_full
    }

    fn prove_compute_y_dot(&self, commit: &LigeroCommitResult<F>, a_full: &[F]) -> Vec<F> {
        let geom = self.geometry;
        let nwqrow = geom.total_rows - 3;
        let mut y_dot = commit.tableau[geom.linear_row_idx()][0..geom.dblock_len].to_vec();
        for i in 0..nwqrow {
            let mut a_ext = vec![F::zero(); geom.block_len];
            let start = i * geom.witnesses_per_row;
            a_ext[geom.num_queries..(geom.num_queries + geom.witnesses_per_row)]
                .copy_from_slice(&a_full[start..(start + geom.witnesses_per_row)]);
            let a_evals = self.rs_block.encode_row()(&a_ext);
            vaxpy(
                &mut y_dot,
                &commit.tableau[geom.witness_row_start() + i][0..geom.dblock_len],
                &a_evals[0..geom.dblock_len],
            );
        }
        y_dot
    }

    fn prove_compute_y_quad(&self, commit: &LigeroCommitResult<F>, u_quad: &[F]) -> Vec<F> {
        let geom = self.geometry;
        let mut y_quad = commit.tableau[geom.quad_row_idx()][0..geom.dblock_len].to_vec();
        for i in 0..geom.num_quad_rows {
            let mut tmp = commit.tableau[geom.quad_z_row_start() + i][0..geom.dblock_len].to_vec();
            for j in 0..geom.dblock_len {
                tmp[j] -= commit.tableau[geom.quad_x_row_start() + i][j]
                    * commit.tableau[geom.quad_y_row_start() + i][j];
            }
            axpy(&mut y_quad, &tmp, u_quad[i]);
        }
        y_quad
    }
}

6.2.1. Remark

Let m <= n, A = bindv(EQ_{m}, X) and B = bindv(EQ_{n}, X). It is true that A[i] = B[i] for i < m. However, it is also true that A[i] = 0 for i >= m, whereas B[i] is in general nonzero. Thus, care must be taken when computing a further binding bindv(A, Y), which is in general not the same as bindv(B, Y). A second binding is not needed in this document, but certain closed-form expressions for the binding found in the literature agree with these definitions only when m is a power of 2.¶

6.3.1. Layered circuits

A circuit consists of NL layers. By convention, layer j computes wires V[j] given wires V[j + 1], where each V[j] is an array of field elements. A wire is an element V[j][w] for some j and w. Thus, V[0] denotes the output wires of the entire circuit, and V[NL] denotes the input wires.¶

A circuit is intended to check that some property of the input holds, and by convention, the check is considered successful if all output wires are 0, that is, if V[0][w] = 0 for all w.¶

6.3.2. Quad representation

The computation of circuit is defined by a set of quads Q[j], one per layer. Given the output of layer j + 1, the output of of layer j is given by the following equation:¶

  V[j][g] = SUM_{l, r} Q[j][g, l, r] V[j + 1][l] V[j + 1][r] .

The quad Q[j][] is thus a three-dimensional array in the indices g, l, and r where 0 <= g < NW[j] and 0 <= l, r < NW[j + 1]. In practice, Q[j][] is sparse.¶

The specification of the circuit contains an auxiliary vector of quantities LV[j] with the property that V[j][w] = 0 for all w >= 2^{LV[j]}. Informally, LV[j] is the number of bits needed to name a wire at layer j, but LV[j] may be larger than the minimum required value.¶

6.3.3. In-circuit assertions

In the libzk system, a theorem is represented by a circuit such that the theorem is true if and only if all outputs of the circuit are zero. It happens in practice that many output wires are computed early in the circuit (i.e., in a layer closer to the input), but because of layering, they need to be copied all the way to output layer in order to be compared against zero. This copy seems to introduce large overheads in practice.¶

A special convention can mitigate this problem. Abstractly, a layer is represented by two quads Q and Z, and the operation of the layer is described by the two equations¶

  V[j][g] = SUM_{l, r} Q[j][g, l, r] V[j + 1][l] V[j + 1][r]
       0  = SUM_{l, r} Z[j][g, l, r] V[j + 1][l] V[j + 1][r]

Thus, the Z quad asserts that, for given layer j and output wire g, a certain quadratic combination of the input wires is zero.¶

The actual protocol verifies a random linear combination of those two equations, effectively operating on a combined quad QZ = Q + beta * Z for some random beta.¶

To allow for a compact representation of the two quads without losing any real generality, the following conditions are imposed:¶

• The two quads Q and Z are disjoint: for all layers j and output wire g, if any Q[j][g, ., .] are nonzero, then all Z[j][g, ., .] are zero, and vice versa.¶
• Z is binary: Z[j][g, l, r] \in {0, 1}¶

With these choices, the two quads allow a compact sparse representation as a single list of 4-tuples (g, l, r, v) with the following conventions:¶

• If v = 0, the 4-tuple represents an element of Z, and Z[j][g, l, r] = 1.¶
• If v != 0, the 4-tuple represents an element of Q, and Q[j][g, l, r] = v.¶
• All other elements of Q and Z not specified by the list are zero.¶

Moreover, this compact representation can be transformed into a representation of QZ = Q + beta * Z by replacing all v = 0 with v = beta.¶

7.2.1. Serializing a single field element

Unless specified otherwise, a field element, referred to as an Elt, is serialized to bytes in little-endian order. For example, a 256-bit element of the finite field F_p256 is serialized into 32-bytes starting with the least-significant byte.¶

• write_elt(e, F): produces a byte encoding of a field element e in field F.¶

7.2.2. Serializing an element of a subfield

In some cases, when both Prover and Verifier can explicitly conclude that a field element belongs to a smaller subfield, then both parties can use a more efficient sub-field serialization method. This optimization can be used when the larger field F is a field extension of a smaller field, and both parties can conclude that the serialized element belongs to the smaller subfield.¶

• write_subfield(Elt e, F2, F1): produce a byte encoding of a field element e that belongs to a subfield F2 of field F1.¶

B.1.1. Vector 1

• Leaves: 4bf5122f344554c53bde2ebb8cd2b7e3d1600ad631c385a5d7cce23c7785459a dbc1b4c900ffe48d575b5da5c638040125f65db0fe3e24494b76ea986457d986 084fed08b978af4d7d196a7446a86b58009e636b611db16211b65a9aadff29c5 e52d9c508c502347344d8c07ad91cbd6068afc75ff6292f062a09ca381c89e71 e77b9a9ae9e30b0dbdb6f510a264ef9de781501d7b6b92ae89eb059c5ab743db¶
• Root: f22f4501ffd3bdffcecc9e4cd6828a4479aeedd6aa484eb7c1f808ccf71c6e76¶
• Proof for leaves (0,1): 084fed08b978af4d7d196a7446a86b58009e636b611db16211b65a9aadff29c5 f03808f5b8088c61286d505e8e93aa378991d9889ae2d874433ca06acabcd493¶
• Proof for leaves (1,3): e77b9a9ae9e30b0dbdb6f510a264ef9de781501d7b6b92ae89eb059c5ab743db 084fed08b978af4d7d196a7446a86b58009e636b611db16211b65a9aadff29c5 4bf5122f344554c53bde2ebb8cd2b7e3d1600ad631c385a5d7cce23c7785459a¶

B.2.1. Vector 1: WriteBytes

• Description: Using Fp, the test steps are to (a) initialize the transcript object with the 4-byte string test; (b) write an array of bytes of size 100 that contains the integers 0, 1, 2, ..., 99; (c) generate 16 field elements:¶

  • 0x8b297f0bffd583c6c6b6796385d5fd20a08665733b833970ebdd1054bbbc1b14¶
  • 0x0667c08ad7f38efec5f30dc8aa4f20d749cdcf96d63a770f9810ac5c0ca8dcb1¶
  • 0xc8037fc12d4da00b5dc7597e3042f33f72a06f970cb71fb6b103ebb5419d8a6b¶
  • 0xfbbcfa1eac48728fbfdacc1c21e2f78119457e0846337e46140e38e62856c4c5¶
  • 0x5358ae603691cc759faeb572fb6642654ea1c3dbc8f81d00276dd8c4df95aa58¶
  • 0x5266158c3c895dede5a23b6ce85a9f564b8059ebfcd1741f54497ec58189873e¶
  • 0x3ecea4b2343c007fc32f2aff40dc7320945f101ecae5d52494db21ad326e9739¶
  • 0x6462dd575e6b874118607212feec7ce5417ae3bf0f2e86604596f35d48bbaea2¶
  • 0x6d56c703c369edea3595db6b958241580ae9b4a76fead961413ed9e9e5852dcd¶
  • 0x6d31073cee650212a71b7b13e9f951e00ef3b14a008a79dd95047b26a4a83d06¶
  • 0x1b9e2a6666da63c43e52227d91a8a7f0bd5311f63c2e3a18839133375639e6cb¶
  • 0x332ea49dd23dd4745631ecbb15696192b1fa127256baf7a0483fd27db6f09a48¶
  • 0x43e735927ccbdc4d5ce912675d638d6d3dc8eef3def34504304e938846f157d6¶
  • 0xdc4a8868ae75e733a7257a8589230392a98d78594836dfccd01304742b5b3ad5¶
  • 0x976353931711c634f2691e507b119fd7f6e653d419a2620676122db08db18765¶
  • 0x332729ab436dca654866a9382deaee0add6fb7e90a80261f1488e56598e8bc99¶

B.2.2. Vector 2: WriteFieldElement

• Starting from the state at the end of Vector 1, (a) write the field element '7' in Fp; (b) generate 16 field elements¶

  • 0x609db3e9a8f548df038519fa46cef23eb8c6553d3c1f698604e60a51613a738e¶
  • 0x1cb69cb31999eb88e83c7586aac53f5e3286b084b0cf9e43619b48df01e0a310¶
  • 0x3bf36e3ddc690a1b12b417628c115959b373d056c90c42dc2417baf46f538868¶
  • 0xe336594f29dcda52e48896517b5cdb2d062ffd861ab02db5f8ca197aacc635f6¶
  • 0xc1f396a8bad16bb0f57da6d380402a25b571bd4691226d11449a741440e325c8¶
  • 0x5195336ec73751de066e3a8939b40c3c5555f1a513486dfc50dcf4c2d47e6ff2¶
  • 0x8dcf872f3ded2b7ed1d1ee9a2b125bedc6eacd3c09b3a4a5286d8fc2fc3a6634¶
  • 0x950dd2ef7be25eab686a6688497962ee4ad521da12b9ff3d8e56ad9435885b12¶
  • 0xe14389d1d8448678cac33fdbc9aab20dba019e75149d170dd2f353891cd4b84f¶
  • 0xe84906c09cd6423865baf64e48027cc598d52bdb90b17524c87ea892e53b5200¶
  • 0x493cea587f1ec5622c04221cd6e5a41c26c1c1c24c0375f7aaa367d9678d83bc¶
  • 0x5aca0010aced30bcb3b84a7f10ea39c4269ab7c92fcb6cff52958d8921ef2cc5¶
  • 0x4498fa8340f41467c0fa813bd0ca83ef6e1c4b85c7b1168a94339fd9e8296139¶
  • 0xf9a95b738a8e775421b1baa503abbeed2d283b236ebba25e1954b3c993d30a3d¶
  • 0x98178711d03a0b1204ebb56b37bd3a2724dfb08e4dc925609391768b126d21f2¶
  • 0x79251f49534f5c4b10b798b2dbf6e80a3b07593f616ce6a9617ccc61040aac78¶

B.2.3. Vector 3: WriteFieldElementArray

• Starting from the state at the end of Vector 2, (a) write the 2-long array of field elements [8, 9]; (b) generate 16 field elements:¶

  • 0xae1a921288590205fc24543303ff527476359b8db4a983b2886a133b02f3217e¶
  • 0x8c5d52a04b295f9fdb45ab66100fa00ca32c9634aa87cbbdb2bc3e1912459feb¶
  • 0x12f82963b5b242156f6e9eb756eddee7652b60c7d6394403f7bd995e0b9bcd9c¶
  • 0x880aa50b049b3939055deb7933749d338bb3fb5f64a9adf95019e6cfc232995c¶
  • 0xf8558f693f0fa6df20a37147a898fb4c678831f566d80113bbe2cdcd18285da2¶
  • 0xbbcc8d9b46f88bc8c6cec0ad2d5e49508b7db91d548548eddc61800de1329e1c¶
  • 0x479a17244398caae8155a73438a22583df7de10a8a2e12ad53ddd3bc7305fac9¶
  • 0x9ba1917f1227932250288a843f64b4e7b7f47a5fbc16c111f6e1f76235ccf38c¶
  • 0xd1582138045d1636fb7f677c9e8a4a4143ce2b2bb54fb4f49fb0ad1fee5df6b4¶
  • 0x05331e5b8508f79c017a8dfbbb805f3f8c5e3e4bc417e44849b9212439646331¶
  • 0xb6b95862194ca52dcaa9ee651b7fc5b708f43feae108bb9a7f95213f4d069048¶
  • 0xe86b1602f0a54c4e237867ebaf05e7581464fd238e50f6ed9c3cea63909c8e60¶
  • 0xb7280439f3b21b113ff29cefe39292d5e2d137709c3d3cec36473a0f97a24e62¶
  • 0xbeaa5e08257d232506fb3e46c6daa29e0859c34c7d0cd673bc6706ee261ae059¶
  • 0x0691ead55728cd087a1952b22b6628ba4e26fbefc8debeec5e6fbc3a16f637be¶
  • 0x47dc31f6d8bc9c44290781176df3e4b95ac8793a4a42fa5859c564d92d6d5af5¶

B.2.4. Vector 4: Nat

• Starting from the state at the end of Vector 3, (a) write the 4-byte string "nats"; (b) call nat(n) with the following list of parameters: [1, 1, 1, 2, 2, 2, 7, 7, 7, 7, 32, 32, 32, 32, 256, 256, 256, 256, 1000, 10000, 60000, 65535, 100000, 100000]. The result of each call corresponds to:¶

  • [0, 0, 0, 0, 0, 0, 3, 0, 4, 5, 10, 30, 27, 22, 100, 189, 3, 92, 999, 3105, 40886, 51590, 56367, 10678]¶

B.2.5. Vector 5: Choice

• Starting from the state at the end of Vector 4, (a) write the 6-byte string "choose"; (b) call choose(m, 20) for the following values of m:¶

  • m=31, k=20: [10, 29, 30, 11, 4, 15, 16, 28, 19, 21, 25, 18, 17, 3, 5, 23, 24, 22, 6, 1]¶
  • m=32, k=20: [3, 17, 18, 8, 30, 7, 14, 19, 25, 23, 12, 4, 31, 16, 0, 6, 20, 27, 11, 10]¶
  • m=63, k=20: [9, 56, 61, 45, 35, 53, 51, 3, 39, 32, 31, 6, 59, 58, 54, 22, 27, 62, 55, 19]¶
  • m=64, k=20: [12, 52, 39, 17, 51, 38, 58, 2, 28, 27, 46, 63, 61, 50, 40, 55, 47, 13, 56, 32]¶
  • m=1000, k=20: [157, 668, 572, 138, 913, 994, 797, 249, 440, 723, 489, 241, 383, 108, 710, 341, 406, 585, 42, 692]¶
  • m=65535, k=20: [40745, 48408, 17108, 44500, 53993, 10008, 24910, 52200, 61265, 54989, 41237, 25958, 28697, 61187, 34729, 3525, 9005, 38627, 9724, 12169]¶

B.3.1. Vector 1: s-gonal Circuit over P-256 (Field ID 2)

• Description: Circuit C(n, m, s) = 0 \iff (s - 2)m^2 - (s - 4)m - 2n = 0 verifying that n is the m-th s-gonal polygonal number over the NIST P-256 scalar field \mathbb{F}_p.¶
• Field: P-256 Scalar Field (Field ID 2, order p = 115792089210356248762697446949407573530086143415290314195533631308867097853951)¶
• Witness Inputs: W = [w_0, w_1, w_2, w_3] = [1, 45, 5, 6] with public input w_0 = 1, and private inputs n = 45, m = 5, s = 6.¶

• Explicit Circuit Definition:¶

  • Inputs: N_{\text{in}} = 4, N_{\text{pub}} = 1.¶

  • Layer 1 (Intermediate wires U = [u_0, u_1, u_2, u_3, u_4] from input W):¶

    • u_0 = 1 = w_0 \cdot w_0¶
    • u_1 = m^2 = w_2 \cdot w_2¶
    • u_2 = s - 2 = w_3 \cdot w_0 - 2 \cdot w_0 \cdot w_0¶
    • u_3 = (s - 4)m = w_3 \cdot w_2 - 4 \cdot w_0 \cdot w_2¶
    • u_4 = 2n = 2 \cdot w_0 \cdot w_1¶

  • Layer 0 (Output wire y_0 = 0 from intermediate U):¶

    • y_0 = u_2 \cdot u_1 - u_3 \cdot u_0 - u_4 \cdot u_0 = (s-2)m^2 - (s-4)m - 2n = 0¶

• Proof System Parameters:¶

  • RATE_INV: 4 (\rho = 1/4)¶
  • NREQ: 6 (query count)¶
  • NCOL: 64 (encoded codeword length)¶
• Commitment Root: 803aba51698a4bc4dddaa74b1d9971b8ec7c49c4847a7ff18e41dd476edf9b04¶
• Sumcheck Proof Size: 768 bytes¶
• Sumcheck Proof (hex): ed0282f97ed9c5be6ced2c1092a34579d9786d1de4dc5404c4d3435f84bbc1a0ea352432ab6ad5b2e46e1b126c18103748824fb252ac17406898c6c27d70fb3b87b96f0d4c7992b03e160e17b0c98efba101daca039575c793b6bedd4dd10541e2d6701be3e75c019a63fa1595741b3e25c7e111014a4dd792bb47e6aec01aa39da1d23e9ac2386889efe3a024a6622bede3f862a41d8267dadbfb491901a6e6845b0503dab880fc756684f4bf3e71acf1eacb596aa6bc9364eaa0e2c3093dfebde19129e45b77c16d27405766a2bd5db5203ab0c116a253127f666354b1cf97c71fa6fc3f90016fa778aea298eaf379f34b043b5da3bd161fec2530eddbfb0e247e4e615f4469abd04fa996ecf232e6fde51763eacb87dacc10b5b2aabf99790c745c33d07537d414be750e6c0dedc14b72b4e5e86be92a7aa87606ad2e8d01d1b1306672a1ab21cd6f676272baadfac7b2fb453daef8415e2f38128f833f6c7b8579a9a4c6f1cc6517bba16e904726ed462896a797dae48f817b81be630a95629f60d183eedd9a4c433ef2f0a4a4294ad5690f2c07b3385e3f2e73fb2abbe3e75148bc1051abd7ce21c46f42517911c2c790cc2101ee85fa50620b644f12b8fc0c9f8522fecaee7c284b7e7006c88df35d1c4f6bae0268751507872f47780c4bfe833a7a0b6f4f403d0d1b58bf891a48083a78ac5e473f7e012b388fe2f4433099d256c6b153cfc422d6f48f6229a7107ca4d5dda7d7ffc033ef3ba2269179089e4889f379d1f97f03b3f0b3206245781dd6841f820fd931ad42fd8a1f44077dbd42f7ea2d3c4d5ecc85e5688c2a5f67abe0a456390b85f9fc2d13a5ca864023e611c6b1ba75967bcbb2f2a8c142a7044e9c54b96a09981fe5b674815e9fd7d8a8d76169e11800edceb9928ec62feb70f0e3593fed2ab0d545f29b1d2ea20cfd8320f828609d5e45cf0dff488401e170d2945ed7559c49f5de2bc7f063f4d63d400922fd141c40d4a74abf045e1b7af4b50ea1fe5fb215cdd286e4ba0e9708bde5320999b8682f9ef6c05744395290815697ca993103f0c0a7704730a05212¶
• Ligero Proof Size: 4652 bytes¶
• Total ZK Proof Size: 5452 bytes¶
• Complete Proof Serialization (hex): 803aba51698a4bc4dddaa74b1d9971b8ec7c49c4847a7ff18e41dd476edf9b04ed0282f97ed9c5be6ced2c1092a34579d9786d1de4dc5404c4d3435f84bbc1a0ea352432ab6ad5b2e46e1b126c18103748824fb252ac17406898c6c27d70fb3b87b96f0d4c7992b03e160e17b0c98efba101daca039575c793b6bedd4dd10541e2d6701be3e75c019a63fa1595741b3e25c7e111014a4dd792bb47e6aec01aa39da1d23e9ac2386889efe3a024a6622bede3f862a41d8267dadbfb491901a6e6845b0503dab880fc756684f4bf3e71acf1eacb596aa6bc9364eaa0e2c3093dfebde19129e45b77c16d27405766a2bd5db5203ab0c116a253127f666354b1cf97c71fa6fc3f90016fa778aea298eaf379f34b043b5da3bd161fec2530eddbfb0e247e4e615f4469abd04fa996ecf232e6fde51763eacb87dacc10b5b2aabf99790c745c33d07537d414be750e6c0dedc14b72b4e5e86be92a7aa87606ad2e8d01d1b1306672a1ab21cd6f676272baadfac7b2fb453daef8415e2f38128f833f6c7b8579a9a4c6f1cc6517bba16e904726ed462896a797dae48f817b81be630a95629f60d183eedd9a4c433ef2f0a4a4294ad5690f2c07b3385e3f2e73fb2abbe3e75148bc1051abd7ce21c46f42517911c2c790cc2101ee85fa50620b644f12b8fc0c9f8522fecaee7c284b7e7006c88df35d1c4f6bae0268751507872f47780c4bfe833a7a0b6f4f403d0d1b58bf891a48083a78ac5e473f7e012b388fe2f4433099d256c6b153cfc422d6f48f6229a7107ca4d5dda7d7ffc033ef3ba2269179089e4889f379d1f97f03b3f0b3206245781dd6841f820fd931ad42fd8a1f44077dbd42f7ea2d3c4d5ecc85e5688c2a5f67abe0a456390b85f9fc2d13a5ca864023e611c6b1ba75967bcbb2f2a8c142a7044e9c54b96a09981fe5b674815e9fd7d8a8d76169e11800edceb9928ec62feb70f0e3593fed2ab0d545f29b1d2ea20cfd8320f828609d5e45cf0dff488401e170d2945ed7559c49f5de2bc7f063f4d63d400922fd141c40d4a74abf045e1b7af4b50ea1fe5fb215cdd286e4ba0e9708bde5320999b8682f9ef6c05744395290815697ca993103f0c0a7704730a0521276b5b1ff2c0f08b364e0c90463874b7a76aead588a0578abd97995a7acc018faa3616f94202b67601ace16cfa22118b6d3c358a9602db7b4c41cf3cad18f0c45016e975539c3308d01c6398983c249a7d7ef16b56c075d2e5768ce4548dcc4e89a69487862c72b530ad0c86d0254b5324e20a9fbbe424505cf354e3e8ef74ecaca42ce218f8ebddeaf17a46e31016bff10c73496d511ca71d3ee15fdbb7a3904bfae54b1581beb69cc2b0c890fbb74baa431eec4cef4ad02df96f82bd5ac46c4e26c97007a5377b096adaf4679a39b6322eefeaf4d2a596964457f7e40d658af1a489d73d0f0d9aebd01703f10423f096f352b2eceba178e81e9917eaa5f1df0fc7b7dff769848968a09789ab02a54b6c1176e34a9a8f1da2cf19ae2c37d05a542407401e53e23a3c2f1c0427578f71933f335ef419a3804338629c5b05220ff077d527eeb62fa14e6410ddd2bfd704eabf68ae2eff1c3df789acd0b651dddfa7569c524daad94e3b0c16c5bfe9ae509c138e1c6164c18b17047b6aa08d4b490b227ebe71d884fd6b6c64b3aedf6a184e8f2364ce58365210b22f9be3527f219e97845a53f0d975f26e97125bb2125223f9a86202ac62ca3c4e650295d2eda824aaee83318308714b3c37ba11b7f4c92c1a53eb9279c473610e2ce9dacf55993f1cb794852fe80c1be4f203c82422826a72eb7ce93a806f709d998504f785cbfcce45c56c3ee3154074e99a3c2e53fea547119ea179ec7d0bfe784556b25d7d6e56fe095b33f2d05e5ac1b8c3fd581811c57648bbef03dad260649070a2446c8592f3e7693a2f1e9ee86473788840517e38d6bc99e2919b3994a6b6a35efb0b6a37225353d4663a61636cfcd81ae2164027586165b804d3ff9e818774b6dce75b32aa849cc964bdaef98457cf2abf90544087d3eaf9dff4897285934cfb6ce49298d4479739de6f80581c0398ba30cffed7b093c3bc2074b558059a7db87ade76ad0348c4ec12499b8d0d3e03a354d27eb901485cea2b58edf01e0859e694c704bb12f2d28227166b476d676f009e4e302fda4ca5ec0692dede769ae800be3e614f3f5ff2552fc2528c94b24fcf74f8b61e0ea76903dca73afb62b35b9fac7dc0bcaad0c17267683aac5e823cd6dbd796f3210dea30491d5bd2d8dd6daabda79213dc3956200cacee1dc8319a3de252f3fb8df6079cc2f4be51c873be5f6668103c9d8a4a5c505bcdd14174eeb1f3c82c156d2d3bc57f68501b9d5ba5af10372797b1a93d738c013c0625833861ffdfaf7a9b0e00f8a33a41f87d72100f75b4b70e8ded7b9a0f44f954915faf6bfc721b367698abcc6b33be195e2a99a326997af0568a9f0e5b65984ec416b715d9f2b2b9ad742eb051fd7c29d0f1c955050b5c38dd1c85c09b1e080ff0dc9c8f10de0d86d07ddbb98267f3c3bf27ae62bac922a62ecbe8c8e1a78b1c19ab25dbf95c52ac077a2610063ac19382d149a18e54ab3b7a843250a186d8540184df41bd5a6be7e3660ef28bba8bb9f4407dbd3b638a30e4a18c7f60404ec06872065179fc55a1195ced24ef2b3798a28acbfbc320ac4d8b1850e6bfb3d3a5730d29bd3f93d6530cccc5f669a058bf14590ce383f6093a386a01cfa72cc429a3d127939fbb73778a8ce92202c29ccdb61fedef35cb7d6cbc98d559f81afd81a472dc8cfbf47074731f18ee4b8871ec5c7508328ad16319c11de3dd35de85e9000a8c8dd77947a60221cc16b8278d4b03bf6858c252c1c19b7fbb432c39fe6db2f04bc7e7ffbda7afef966eaffc1a10e271f688c6f5fc95328f94196dff3a42b5e7c4960b5e457aa322afeaddf2dd4cc756e7379bf3266faf76c4153d4bfbef3fcd2fad88b1e7e7d78246cbfa96b7f9edbedf02d210dc247ed0fd14218243eb3c6cd0866cd2cd49f84a567c780b1d15ad44e5ecb916b0819bb8d57ac002a7b007a35c4fdd3fa48694131a637482f781666a3d69c5010d406ef8c46fd239545520a5363d67d61bad1750d37b087c1e3611a12d47e477f5fe986cae604828cae4bfbbc7415d64cd5e755848755a0d9d3120ad46eea8d860fa8593d45fef897767ce05ec5feac76d8f21910bc0ada856aeaa777629048ef63619b9a06c668a2414e46f859a2fdb1ba63e8718fa6ce4bf532b2fb0b8ff4efc9e35514c0ff4b62cb9730116947bef69325f3a4c1c6553b7bd161754f8008d8057ec47e747c61954419b634dec16eb6adfeafb1a0e9fafbb2a9c85fcf9bced400000000540000002b520d64d1a48758b4e6b56b93cda7b71767e41aa21bc5a402f968032a5d990b35d916cce85bc34911ea5f3413ae54313eb9ac0de227c1144dfc0835d6ac56fb37cda5179524c5390e72928bf48c4d7f2c6ead37d9cbf9b53f4219ed6ba49b8620a6a6ea318ea301b442a8be1c6198b0950ff8e748772dd208758a9b6d4ada5bb54472abd5aef2cf83f64227b8e8528f6883130523388ac249501c5678fce39ee6098cf92e675f98ca0fd7f16d83f18879a6a54196a2bf0cc8222d791e9870ab8444ab45f7abf52736bd00b8e1583f31faf872d474aab7503100adaa4eabed15dd194b4ce7576b58e33ca6c044b104545764d9af7b7708cb8a9d7d2eb82564c24b9ec487aca878ac6f243cf89dccff327fa5c61698a0f14f33ddfadccd7748482c72c5234b5a2663256ac36644692aaeab1038b87c40be582d28d495f9042be70a724e89c5462323ca1dca74273a6f2bd8f8b1f51c7da4f0f66732d4040d29c916ac01b6e1f7cd411a8783caf37f0b8fc60c330c6fe1377f956273ebd37c6aa2acb55ed76b7589c4e4ab006085057f301369f9b4407745ec25420dad03bc2c134efe1ad4dd9ef9f03a617f79c69a4d90e44c2ccf48ac1ea1f7450fe7b1603ec96e70400ec7ed1d645e13161a9c42a7aee7922a3910d9c7a4a2375849375f8c408d7ce8eedc7fd61082f91483d4ae597530423109fae058b90f43f63f397e1afe4ad76b9d73be712c9ce50c5feaa4ccff48f9053f130a04cee5121781f4ca524e9bc381bf627dcac1aabb1cb6781b4510874f60a8e1c188016e6b49f67827c9512b3f2b3d412b35b3e371e6f40014d975f54c54e0f404d6cb999196504009a891b0f2710df5054a387cdc5cb7bb147f154e1d33519782410234e6e1f001e511e3896b61ac9e75d111da33a0c3c91414f37ba8b169809e735453e9698f643af6f1b76feb3f50f8e65f42e8803d2f128e36928c021a8a8e8411a9f02d36efc09a1f71cee349a36dc6162254eb04210eb08cae8e955a5720891fd89f5b7bd61c0e0bf62471a70e8f8ca8addde0aba195388d60452fa98ec72d5aa4751a3a820db5e869cc80f2f9a62d18f7367d1c1ad339dfd5760dc9c11b244a52d7275349a721d80939f2143bed6891a68b950946453c7efb8c885974e6e2509b63aa59278e30b78659f736c5a6f84e9c0e5cfb04de3a06a35e3be04e7d9bf85ee025cf5b4ed1a5038ab30e6d304245c6d5573a3ead0da8de3375985a8c32ca06658532f827ca216d8d24c4ce16ae39361b877bf4cd0994394144bb8e52737ed70732eea60cf5aec5f474bed7baa5124ec1e454c818da069aee55b9e36b46807b460d5ee2684d650c3ebbe7d5425186e6a63ef2497b4e9028976991850310faab526bf6a3f0c9800c655aa5bff7cabc560f82d4e885c496d3111025215121adff4a55487783399b76d3a0e7376fede3865e3558f219d82fc60207d921549c858dfc8c08fddb61e51c776e9650ef8c757f9d52c64793e3b30c87e18bdf0de670ddfdfe3785026ea7acabc069bca44ee228d707a03d78d0ef64a1a5c9bf5a66d9a5fcc8168954fb699cd74f4568007e9d7d147ea2cabe9e85e00425f60dc895309529d6251a295d883cae2f92cc200a5bcd6616d8125517d95366ce99e151d51a3b43784537c55ca470dc003aa92f72a706d9558711fe3cce3603f40d90d041cf58b8f3b93d2079b55104ccf9694dcc2dc7b38cd7b3395db8a0b6e570c6f7fbad44d44111ef8cbc38c66a26571835f13d66eabd68de56a707508e850b1d8057d3bb0389833dd4b0060c0437a75418bcea0ad4d0907c22ebac99ea69f04015635ffd217672b5531e2d6484572c4093462c7464f9af152fabe10b8515a160750e246302e640d837778443985dabcab9a19e9ebfbabb1d511f8fbd1ce7d163c6bc85513a3954876f064d855de13479202a87c513db6f43efcf3fe734c740606c1aa43d5c42a3807a8c06e25c4952bbb951b4d58269d67016e301b8660cae3bf4ebe556cbc7ba99b0b020cb52faffffc9ba2f9cd6d88e91cabbed8f9c325785b9885113198b52bd28324c1f332b82accf2055642c4af0cae07c1bf46f9cafecd81d1aefe8e3b777f19ecdd3a6e921faae6e1d8e20764e12dc1d02917ae0dfeb1cdad107c1744b980c9405d8d3ff53869e77c1e299d419216ad68894fcee7e4328b3b347abd813f9a833f32cf932591570bebfe056b5b98ffb614e576192a4d4af8b740216d833d7334eb9eab0334c635f86c681d6c9c9327f179963b6982b1853eb50e7d57b760c190735ccd5835d669b10fb5ac684d3086abb77b5252aff7d2b7f808561a7a54af2573e605ecf373e1f3d5525b83dc45bf33a8cc79fd3114c1d4d94395f0e9611ae3021839f6f81c072ef6b6044e735c5f269a23686f9d566a26782c12bf5db4660330f123a54d70aa6e55d6293da388a73ecf15f6693cd86dd83525003b1cdd22bf5af0bb25ea5ded5c5bff67a06284c9236883eb6aa4b8ea0d94c588a777b54da4bade065be29ce4d1c1a91d24624562f20cd7e6b4ec25fc0699c2cc4c815b8c3bd973bb93d0811afd518e7db3c94ef99331a0eab493f88c47f14c47dde5b647628baa1743fffba43b69fa5a7004ed8b061d0bf599cd7a880d20485b51c51bd3de82f01123357546eddfdd002223cfb33f23e97b9df42a04379be4447b2a6c30eaa849e9179e334561b05c83d9a489cc5b4e4ee00c5668a89631c6cd1b5add22e5fdf680b4755841fb5e1e806b7cc6709d94e3d9fe184388f17f26a947d58a95881c73bf7ec078cb3c6c8bee6b48e898da3dade41a871977e54a1047038edb550b7eadd781888e15d7796940d0999c3104bdebbfbbe716c584f3bd31326de132ec74bcbd1294f9b6ab57eba429b36c242ef34d36bbaec8d42882869f26949568a7bbee76b77f54f40002eaa717071e002a8a29dd7fd6ebd7df3811e090ac3117df4e30e8868b26d4cf4c3437b1a53f14bf515798fe3a5001a7bfc0a8caeef488175e9d8836a28ba65461462c16ab66c0a8d8148f3b84c0a6a4cbafa900bc09c4f319f578644ff618d50496d2b2d1e63f8232b263308bb55afcb77232f210c1677d84df6d9309fc40e551b15458c635b5c3edbf88aceb4973d9fdbc2750b1fff5f96ac8c54dc83bdbdec3dc01d34e510509377e69eff08ad3d5b120c72e8a432e627982b11b6dec534a3423bb529c527637171825bc1990501ee480b23711803a4a3c48372fb266759c496ad4d6a56299f7b379a783d07aa30cc45b1f0094995a5aa0791f4b5309f43295fbb71a20e0bc4addb75589d8e577650b1109b969f8ffe6f26b957c263f38419bb67e4e651adba049a41fa861772f036c172ecf3d8742590996ee4951e608b384c1e6764c1618de6548d239a6325fbed9233f6e0da4e1775d718a1e5f744b2858f67c585a54c912e7ea58dfb58d1ed2ebb7149f6f1019e0ec86e64c3e70fba3f0b8462a5401655ecf7386e9f7040098995fd83be5336c1c9b063458f3a327bd5d5753e73a96fc2f86a2610f18e3fb5173109c65bb95bb2232785241f472597ba75969369ee893dfeaeee6307256db5a8fd3294cee178863db9c8dbe711aef2f709da7cc9be00aba6e43266acc4870b69b474f3639e5d04c3064ee652fc5ea5afee2d5f7d7e2d1a3a95868c9f2524934ba53673cd1e76ea8390f07b9d73bedf84a753b37d8c5d3e64652c9fe6bd238e5433eaac08ff61ea34c3cfcfb6882485766a2658338a60dac5d934899cad1a05688b8244e51b29ecfb1c0b000000ed0aea43f9d6715158ff3048e550629bada9ff6c99b48d9af59f83236ea427401c22d30673117dfd8c17e7caa1c432f72a661c5ecdac243925674d3b168d33b9f29bda3f42a9180c278f91064af6b79e4a2517217e457d488e88111c19eaf1aa239215789d94305bd5a975e397af5b5419443803bb8a7f63c9450c80a96bffcde555370e8c6bb3a0f2d2ffa3e41d00c6ee362d64fa8afa3ffeea6bd8a964cab8911b768452b297bb3bc7930eb61c5ad38dc7aa310c8368131733f4ce4bea67f4ad5b85bbedc01b9fc28afdee1d52d8204d6b3fb8323b3836a858fdc1cf9e7e7ad6fd1e4e8bf95277824ab90310ae2402c4665cf76a478a4726ab63e0ff55ef853e6ed3030d04b66028e7e2b56d12c0fc42aef74d0a19ca21bc77143b589e5bc8dffeb34ffa0084c67395ec2f3aea8e4c1c1f9644482f364e8471931422be6eb6562d371f966b11e9e0d2c850537f83992f43de669d091b472a5a242731a0156c¶

B.3.2. Vector 2: Quadratic Polynomial Circuit over GF(2^128) (Field ID 5)

• Description: Circuit verifying (s + 1)m^2 + (s + 1)m + n = 0 over the binary field \text{GF}(2^{128}).¶
• Field: \text{GF}(2^{128}) (Field ID 5, polynomial representation modulo x^{128} + x^7 + x^2 + x + 1)¶
• Witness Inputs: W = [w_0, w_1, w_2, w_3] = [1, 84, 5, 6] with public input w_0 = 1, and private inputs n = 84, m = 5, s = 6.¶

• Explicit Circuit Definition:¶

  • Inputs: N_{\text{in}} = 4, N_{\text{pub}} = 1.¶

  • Layer 1 (Intermediate wires U = [u_0, u_1, u_2, u_3, u_4]):¶

    • u_0 = 1 = w_0 \cdot w_0¶
    • u_1 = m^2 = w_2 \cdot w_2¶
    • u_2 = s + 1 = w_3 \cdot w_0 + w_0 \cdot w_0¶
    • u_3 = (s + 1)m = w_3 \cdot w_2 + w_0 \cdot w_2¶
    • u_4 = n = w_0 \cdot w_1¶

  • Layer 0 (Output wire y_0 = 0):¶

    • y_0 = u_2 \cdot u_1 + u_3 \cdot u_0 + u_4 \cdot u_0 = (s+1)m^2 + (s+1)m + n = 0¶

• Proof System Parameters:¶

  • RATE_INV: 4 (\rho = 1/4)¶
  • NREQ: 6 (query count)¶
  • NCOL: 64 (encoded codeword length)¶
• Commitment Root: 30dafd53c4f2441bb8457cd84fa69b3a822fbda58a46527d5cec8ce1903bc504¶
• Sumcheck Proof Size: 384 bytes¶
• Sumcheck Proof (hex): 6240c86a95637590efc064be3f0e9d28fc212291b18e5e3afed5099df504c6478aaa530725347ed936fb115880fe03f394808f716d78e8dd8dde5b5bd3f2f489a71c546509defd48dfb6650b3095fd6737451138f90326c07013cb02076ecab74c74af12fafa59cd8fdf6ae0315d1a5ee40de4c200b7d051bbfb98626e86ccdcc4f2995317ebb77628e811cb190156e6b9cf8cfb4fc62b478e49e262e6f4453f6e6c5298fc74b14cd2a9ef3ff9872f67452f9012a79e6517347af882d1e0bd70113cb1307823bf2e57b45515cfce5e8b0c33e9a941524ba5355f0c444d96138347da64051e89579e5ee002b8346d1b53c26c695f208d5f5b784f90e4ae33b7bbe9e0d29e9e2ad103933ab99a684b7611ed1a15977f59e2d60d05a2cf24212ff20c59ea4f435404b9fa889934fd8d550807142c664890f7d0a9ba27ea040d03ebfd4bf8ce06ff90509700bcde7042d213adb43c2fb1f46143226c273b09bd650bab9b3aec6cd5419edb1bcd616911c2b3898d07c5faf9fa121da18a01f5a1ea9b¶
• Ligero Proof Size: 2632 bytes¶
• Total ZK Proof Size: 3048 bytes¶
• Complete Proof Serialization (hex): 30dafd53c4f2441bb8457cd84fa69b3a822fbda58a46527d5cec8ce1903bc5046240c86a95637590efc064be3f0e9d28fc212291b18e5e3afed5099df504c6478aaa530725347ed936fb115880fe03f394808f716d78e8dd8dde5b5bd3f2f489a71c546509defd48dfb6650b3095fd6737451138f90326c07013cb02076ecab74c74af12fafa59cd8fdf6ae0315d1a5ee40de4c200b7d051bbfb98626e86ccdcc4f2995317ebb77628e811cb190156e6b9cf8cfb4fc62b478e49e262e6f4453f6e6c5298fc74b14cd2a9ef3ff9872f67452f9012a79e6517347af882d1e0bd70113cb1307823bf2e57b45515cfce5e8b0c33e9a941524ba5355f0c444d96138347da64051e89579e5ee002b8346d1b53c26c695f208d5f5b784f90e4ae33b7bbe9e0d29e9e2ad103933ab99a684b7611ed1a15977f59e2d60d05a2cf24212ff20c59ea4f435404b9fa889934fd8d550807142c664890f7d0a9ba27ea040d03ebfd4bf8ce06ff90509700bcde7042d213adb43c2fb1f46143226c273b09bd650bab9b3aec6cd5419edb1bcd616911c2b3898d07c5faf9fa121da18a01f5a1ea9b3edfb458a51019d7ab9d3f0890c1c216c1e4e2b2c087cea41515e0dbe8ae74b8923bc6f7ec3396c391e422f440d9b9f85a2e47a8c43682f41bea847fac6ddaa246dab1978ee40772bb75fa4571a773bb3a7e1947eeec8d74b7c42a800a0de3c8463fcf42223b5204c34bb261d8708e96695648bbb4bd534dd3a852032a5a23c641e66955d62f95d2bf6acdc16e401aeb355b55f6c7df1fa5493e152633dd67b05451e156baed83c4b6b154e44779cd30d382b43cfb918db00d0f7e6ed000ede91460ec372a93c7263f54666cdf2d558e0a56f62914e46eaee62b19e1b5ba179bb96044de94a5964acc4ff7c175f25be4fed23d1096414f307104eaf47e9c756a54fbf66e974c607946b689560486601c6d351ce7925a6ffe3d960ace99b9b5fdbbb2ca9d8b56736af217f21ed813e517fe4f3c78fcafa0b47a01307fef9dc4d2c9fe979532e97d1452034d904db212ffea8c152cdab17bafd8037d519dabe985091844be5d630ebba0ba17765839c35543e40162c66ae7b73f9d018c463aaa6034545321a445e83fb706b03f4971bc2c28d529d36c5440c2942e9c22908e5a2f2347e19b793e15e0852686e29a2029977b3ba6c346ecf3bceca062b5130ac652925cbca1da5f99528742bfd37d32710296363d2d2dda271eafe8ffdab7f2c378fb56de4804e8dfb0887e504f5b3c0a1c040a91e4ed07a35a487be0f1c1221d2d3950c7db515c5e4c557d2508fc8d13c70efc9f99e667f8a0995b9d2b3f15a3b29493a370aa72bece76d5c1614ccac7f8a4427a0cbcf38d7b46249e13ff8a38de34baf543b88990809ff36271f33a9c62c4d79ddfb271ec6554430c7eff2ddb380a11f45d772d5f61d051f6c9a4bf188fad665105add63a91c89f9847ea498fd4d148fcb439d216593fd6cda35cdd541b70dc213c9ac9f172336743b5d9b9f0092358436be52d50ba60e7d7c9c4d75415527f4c04647f433b02b7955421a405ed7ef857289b65bef3539deca0df3f44c67bd0f86b02afddd2eaf2df6b9ba3649733946263e6da1ec940a9047547a6296f465821313eeb867d988aed265b82eb5387b402da5412750ec00175350a9579b1f458b668155ba582d31b5d71331f2d41978ee556b7e529dea3e0fbbde3d83fcb11871c478dd3ddb15fc27e628487950e1c320449d0bed51ad492d371d066d55c4db059a1c59c267094ae3087746b1e61c809ce332b7354d1e4b593f335d980dc1f0579e171a0bd092761a12006f3b5445400000084517983aa1a7acab37c5181b97ddb5d183e7a30b7e9884798a1ad1333c2c14c61fd3a7d917c0e4537af67339705ac87e322061e9a147d45067342f418a655334b4588edccadd095e883e9aaecffd81c02e951c856dc5ec383fb28cc228ccc269c71ba2bf849a9d61bae28f935d474eb5b163f1bee4bbe0dee075869b0335e5fe98780182348b1ba71767cc88958065a0403e65c7f95d6de372aced94abd8bbd885d0f6d38451210d7fddbb8523ad24204fbd51152f5ac27a948e9e3788f14e7179ad246b576448614fecb01c2d4dd83ee2f5adbaf7750e986c03086a13f5be9a5e12e9ff31e8450b0c7623113a70837c5310991f2344e058687333d18893813a17939ad8bac01008f045c5711e2bfff6b16d4ed928a078e4a55eb72c65500f6f4ef4d02b4363836cdf4e9c82b761e1824c54d7285c1a5f0b3996af3088c52df6b9e746c73043aa4262717e733d508761dcac98315686357b39624b9912a2bb18e692e87b31ad3f26bd3b3246a678f6b9be9272611c21b6fbb1962e1473c76089d9b039fd9b32adb3a614f9644edd80a7e7d9348c675feee9fdc7231c50bf481d4b74328bdee990dc0af51f0a9ce68a34340cbf6067d65a1bc5b64069e11b8b1a3bbc72f3c5d517befd88b288ca28f8a2adcb8308eda9e97fb4ab325b567524999b568c401c0d94ea358434d786b2349ad878b197df169e78bbbdb2008611c7b0ee75ac194c86517ff4e592debce41c3972344dfadc6af0a1c84c1aedd5b6b3c0ab3500a12677c73f8c6aaf7f9526ee5020bb01874d32ee0449c6dd835282a15dea4fabad0dcf06dea8e7b9e55c9a70686756f1f6db32f01b450968521e67614b361c51a3673fb5cf4b313d35b041599d95a54d17de65204a289c04b33a33f3d15a58a90b90fe9c0d05894f75c48000e8892866e516f605c58466c0652df4df4245cf61ecb43ce23ac6d64259d89a0c02a156957159feef112d1639851e0b1b2e97aa138b6b7657ade0eb2df303cba9e4a729e79061ccd89116c56f313a082edb0e311185b2820bec856acf95497f23b04be15e7059206f93db9a6837071bff558f8d7ec8ff91c089b7c3baabbf8a8770741d353cb0541383867b0a96dce09199b453bcfeddb8f633797bca30f720faf649c4a67a488ecf4388c5e7383cf508114629bf0d2bc0692bcb364748b6a728b2607125c74568624affa5174e400c0c17235340b2e9f56010abaf23e594942196c7ff4d4856d264f5bcb330ad31030347df134b7f40d68080358488029de0f12d707a15fa0737b04f1c9b3f1bf8227cf67201ce2b347f47eb14d1377666c472b1a5fd34dc22002183103944f1e277def38512a4c5dabd0b535d2bd02033df67499240c94b625212b1b57b26dd82a6b126a9f9d6b92cad7920fa68e4dc4f74ffe46f31c05f2c2b675f6050fd33c865c8a03724f9ff9789500b4ddf43ffe7eda857f7670288c27641fb9dc7c63c8a916920cc7c76f6eb3dc9b083444cfb1d77470290f3b671967030db402ffdb49fd38f424639cf0aaff985144f29040a3ad1359bddaae36dbba740ee4f0c97b194dc7d1742827db2f33965e30fa4f37c8217eaddfc34082526df5755b4338db89e4221b919409fad65d1abf4810ef67183ee40a916de209eead26fa5156116f9b72440eafde88be86e28a0a04e88fe29e4472b9ccd3a192ae00f6f52baee0540251869ec728cd03bb2201bcffcf5bc3d9c345d2b14b4f544363cacaf0c088c56cb8dc0dc8f126136e1b82c0b7577c8a22b1448c1f588c9f34a1fc5a76986f4b98a6c4f25a832f48feab33f45e0f48bc9e5a058a0d447d5e0d996b8930d0f8248a98542f6e74cc99630b559b7c4c1ccc08e0f1b1bc053347822ea65b7a62c87190fcace20c00000090481e0835d39fd8a96a8621f6b07090b791b96bc168be8b925875f9651cef09b13b3d19fa1108a15833209497ce19b540a98823b2b717a32336eab1c03722b620c9edc47b837e7e9dbcdeacf6e21e6b7c32bb3667017684860a0f3df8e24aeabb3ccd2f56fa81bf67f1cb75f09fa40b53d4f15f0392430a00430902b3d88062d100629620fa4365b48a8b1a70d7bfc59766bb8f66746774cf468ce1c10d2a494e4309fcf32119b14aaf3bb94b30d100410551a0de356601da0289d1573931745b3d015b150bdf91ed0fa201b77bf13f928b7da499f4b9d84ca44d988515ca586768192b8340d3438938f37cd9e78206164622646df66ee8e9da522c387dbd783dcead20c990b95f5ca3a75a2fded5094377f65585e0b39fd656856db6f3bbcd74ac6c094e80ac1e7b437b0a45249f7f795e969b2f85066970895e4bf70c168b2239ed30178e7cde0bb7b317d15f3e632e665cf53e883b8cd1301635d74c479c1cea5be7574af47527b3fc7fa49563b3a4d1a19eb593507625b8ba55cbd4ff01¶