Neo: Lattice-Based Folding Scheme for CCS

In Neo, a vector of field elements $z\in\mathbb{F}^m$ is first decomposed into a matrix of small coefficients, then committed via a random matrix. These homomorphic commitments allow the prover to fold many constraint-checks into one, using a single sum-check invocation over a small prime-field extension. The following explains the commitment scheme and how it enables the folding (sum-check) protocol.

Lattice-Based Matrix Commitment Scheme¶

Neo’s commitment scheme builds on Ajtai’s Hash Functions and Commitment Schemes Ajtai, 1996. In Ajtai’s scheme, the $\mathrm{Setup}$ samples a random matrix $M$ over a cyclotomic ring $R_q$, and $\mathrm{Commit}(pp,z)$ outputs $c = M z$ for a low-norm ring-vector $z$.

Neo adapts this to commit field vectors by embedding each scalar into a ring polynomial.

Concretely, fix a small prime field $\mathbb{F}_q$ and a base $b$ such that every field element fits in $d$ digits ($b^d > q$). We define a decomposition map $\text{Decomp}_b:\mathbb{F}_q^m\to \mathbb{F}^{d\times m}$ as below.

The commitment is then:

• Setup: Sample a random matrix $M\in R_q^{\kappa\times (m)}$ and output public parameters $pp=M$.
• Commit: To commit to $Z\in\mathbb{F}^{d\times m}$, convert each column of $Z$ into a ring element $z'_i$ as above, form the ring-vector $z'=(z'_1,\dots,z'_m)$, and output
  $$c = M ,z';\in R_q^\kappa.$$

  (3)
  Since each $z'_i$ has “low norm” (its coefficients are small), this binding commitment is secure under LWE/MISIS assumptions.

This scheme is formally an $S$-module homomorphic matrix commitment. In particular, if $\rho_1,\rho_2$ are rotation matrices (elements of the commutative ring $S$) and $Z_1,Z_2$ are two message matrices, the commitments satisfy

. Intuitively, matrix multiplication in the ring distributes over addition. Equivalently, the commit map $\text{Commit}(Z)=M,\mathrm{cf}^{-1}(Z)$ is linear over this ring. We will use this to combine commitments in the folding protocol.

Homomorphism and Pay-Per-Bit Properties¶

The commitment is linearly homomorphic, meaning you can add or scale commitments and it corresponds to adding or scaling the underlying vectors. For example, if $z_1,z_2\in\mathbb{F}_q^m$ and $c_i=\mathrm{Commit}(Z_i)$ are their commitments, then for any scalars $\alpha,\beta\in\mathbb{F}_q$ we have

In plain terms, $\mathrm{Commit}(z_1)+\mathrm{Commit}(z_2)=\mathrm{Commit}(z_1+z_2)$, etc. As a concrete toy example in $\mathbb{F}_7^2$: let $z_1=[5,3]$ and $z_2=[2,4]$. Then $z_1+z_2=[7,7]\equiv [0,0]\pmod 7$. Homomorphism guarantees

The same combination holds after embedding into matrices and ring elements. This linearity is crucial for folding many constraints into one check.

Another key feature is pay-per-bit cost. The cost of computing $c=Mz'$ scales roughly with the number of nonzero bits in $z'$, i.e. the bit-size of $z$. In effect, committing small integers is much cheaper than committing large ones. As the paper notes, “committing to a vector of bits is $32\times$ cheaper than committing to a vector of 32-bit values”. Intuitively, a ring multiplication $a\cdot b$ only “pays” for the nonzero coefficients of $b$. For example, consider $z=[1,1]\in\mathbb{F}_7^2$ versus $z=[5,3]$ (which have 1-bit vs 3-bit entries). The decomp matrix for $[1,1]$ has very few ones, so computing $Mz'$ involves fewer rotations/additions than for $[5,3]$. This pay-per-bit property can greatly speed up committing sparse or small witnesses.

Folding in the CCS Relation¶

In the CCS relation, the public instance includes constraint matrices ${M_j}$ and a polynomial $f$, and the prover’s witness is a vector $z=[x|w]$ whose entries satisfy $f(M_1 z,\dots,M_t z)=0$. Using Neo’s commitment, the prover first commits to $z$: it computes $Z=\mathrm{Decomp}_b(z)$ and sends $c = \mathrm{Commit}(Z)$, revealing the committed version of the input part $x$ and hiding the private witness $w$. The goal is to prove that the committed $z$ indeed satisfies all constraints $M_j z$ in one folded proof.

Because the commit is homomorphic, we can combine multiple checks into one. Specifically, Neo follows HyperNova’s approach of encoding all constraints into a single polynomial and using a sum-check protocol. The key ideas are:

1. Partial Evaluations: For each constraint matrix $M_j$, the prover computes the multilinear extension evaluation. Concretely, pick a random challenge $r\in\mathbb{F}_q^{\log n}$. Using the decomposed $Z$, compute the partial evaluation vectors $y_j = Z,M_j^T,r \in \mathbb{F}_q^d$. By the decomposition lemma, the weighted sum of these (according to powers of $b$) reconstructs the evaluation $M_j z$ at $r$. The prover sends $(r,{y_j})$ as evaluation claims along with $c$.
2. Polynomial Encoding & Sum-Check: The prover constructs a multivariate polynomial $Q(X)$ that encodes the constraint $f$ and the evaluations $y_j$. Roughly, $Q$ is designed so that
   $$\sum_{X\in{0,1}^d} Q(X) = f\bigl(M_1 z,\dots,M_t z\bigr),$$

   (9)
   by summing over the hypercube of binary vectors. The verifier and prover engage in the classic sum-check protocol to check this equality. The sum-check iteratively checks sums over slices of $Q$, and its final output is a claim that
   $$v = Q(r'),$$

   (10)
   at a fresh random point $r'\in\mathbb{F}_q^d$. Intuitively, this single claim replaces the many original checks. (Neo’s innovation is that this sum-check is done over a small prime-field extension, unlike prior lattice schemes over cyclotomic rings.)
3. Random Linear Combination: After sum-check, the prover has a single evaluation claim $v=Q(r')$ and also the original $y_j$ claims (now at point $r'$). These are all linear statements about the committed $Z$. The prover and verifier then take a random linear combination of all evaluation claims (and of the commitments $c$ themselves). By Lemma 2 of the paper, this preserves validity: if each individual claim was consistent with some $Z_i$, then a random combination is consistent with $Z = \sum \rho_i Z_i$. Crucially, the commitment scheme being an $S$-module homomorphism means the combined commitment $c' = \sum \rho_i c_i$ equals $\mathrm{Commit}(Z)$ for the combined witness matrix $Z$. In other words, many checks on different $Z_i$ are folded into one check on $Z$.
4. Final Check (Decomposition): The result is a single instance of the Matrix Evaluation relation: the prover has one commitment $c'=\mathrm{Commit}(z')$ and one evaluation $v=Q(r')$ to verify. At this point, the verifier checks that $z'$ is consistent with $c'$ (via the commitment opening) and that $Q(r')=v$. A final decomposition step ensures that $z'$ has small coefficients (necessary for security) by splitting $z'$ into base-$b$ form, which the prover can do using the split_b map. After this, one obtains a single folded CCS instance which the verifier checks directly.

Putting it all together, Neo’s folding protocol uses one sum-check over the hypercube and linear combinations of commitments to collapse many constraint-checks into one. The matrix commitment’s linearity makes the combination step simple and secure. In practice, this yields succinct proofs: the prover only pays homomorphic commitment and sum-check costs, and committing bits is especially cheap thanks to the pay-per-bit design. This achieves a lattice-based, post-quantum secure folding scheme for CCS that supports small prime fields (e.g. Goldilocks) and a single sum-check invocation.

Each step leverages the matrix commitment’s structure: the homomorphism makes step 4 valid, and pay-per-bit keeps commitment costs low in step 1. The sum-check step 3 uses standard multilinear sum-check arguments to fold many checks into one. Altogether, Neo provides a practical folding-friendly protocol: small-field-friendly, post-quantum secure, and efficient when witnesses have low bit-size.