Context

Notation

• $|z|$: CCS whole witness length
• $|\text{x}|$: public instance length (set to 1 in this case)
• $|\text{w}{\text{CCS}}|$: private CCS witness length, i.e. $|z| = |\text{x}| + |\text{w}{\text{CCS}}| + 1$
• $t$: number of matrices in CCS
• $B$: Ring coefficient bound, which is chosen to be a power of two
• $\kappa$: number of rows in Ajtai matrix
• $L$: $B^L > \frac{p}{2}$ for a finite field with prime $p$ ($|\vec{\text{f}}| = |\text{w}_{\text{CCS}}| \cdot L$)
• $\vec{\text{f}}$: decomposed witness for the folding scheme
• $\text{nv}$: Number of variables for MLE = $\lceil\text{log}_2|\vec{\text{f}}|\rceil = \lceil\text{log}2(|\text{w}{\text{CCS}}| \cdot L)\rceil$
• $b, k$: $b^k = B$
• $s$: Number of NTT splits of the ring
• $\tau$: degree-extension of ring split component
• $d$: cyclotomic degree of the ring ($d = s\cdot \tau$)

Ring configuration

We choose the following Goldilocks ring configurations:

$$ \mathcal{R}_p = \mathbb{Z}_p[X]/(X^{24}-X^{12}+1)\\

\mathcal{R}p = \prod{j = 1}^{8}\mathbb{Z}_p[X]/(X^{3} - \zeta_j)\,\, \text{and}\,\, \zeta_j = \omega^i\,\,\text{a root of unity},\\\text{where}:\, i \in \mathbb{Z}_Z^* = \{i: \text{gcd}(i, Z) = 1\} \,\\\text{and}\, p=2^{64}-2^{32}+1 $$

This configuration allows for doing NTT multiplications, i.e. element wise degree 3 extension field multiplications. This was chosen over Starkprime since its modulus is too big to compare in performance, and over Babybear since it result in degree 9 extension field multiplications for security of the ring.