International Association
for Cryptologic Research

We introduce Zinc, a hash-based succinct argument for integer arithmetic. Zinc's goal is to provide a practically efficient scheme that enables bypassing the arithmetization overheads that many field-based state-of-the-art succinct arguments currently present, and which can be of orders of magnitude in many applications. By enabling proving statements over the integers, we are able to arithmetize many operations of interests with almost no overhead. This includes modular operations involving any moduli, not necessarily prime, and possibly involving multiple moduli in the same statement. In particular, Zinc allows to prove statements for the ring $\mathbb{Z}/n\mathbb{Z}$ for arbitrary $n\geq 1$. At its core, Zinc is a succinct argument for proving relations over the rational numbers $\mathbb{Q}$, even though when applied to integer statements, an honest prover and verifier will only operate with integers. Zinc consists of two main components: 1) Zinc-PIOP, a framework for proving algebraic statements over the rationals by modding out a randomly chosen prime q, followed by running a suitable PIOP over $\mathbb{F}_q$ (this is similar to the approach from Campanelli and Hall-Andersen, with the difference that we use localizations of $\mathbb{Q}$ to enable prime modular projection); and 2) Zip, a Brakedown-type Polynomial Commitment Scheme which is built from what we call an IOP of Proximity to the Integers. The latter primitive guarantees that a prover is using a polynomial with coefficients close to being integral. Importantly, and departing from Campanelli and Hall-Andersen, and Block et al., our schemes are purely code and hash-based, and do not require hidden order groups. In its final form, Zinc operates similarly to other hash-based schemes using Brakedown as their PCS, with the perk that it enables working over $\mathbb{Z}$ (and $\mathbb{Q}$) natively.

We introduce two folding schemes for lookup instances: FLI and FLI+SOS. Both use a PIOP to check that a matrix has elementary basis vectors as rows, with FLI+SOS adding a twist based on Lasso’s [STW23] SOS-decomposability. FLI takes two lookup instances {a_1}, {a_2} ⊆ {t}, and expresses them as matrix equations 𝑀_𝑖 · t^T = a_i^T for i=1,2, where each matrix 𝑀_𝑖 ∈ F^{𝑚 × 𝑁} has rows which are elementary basis vectors in F^𝑁. Matrices that satisfy this condition are said to be in R_{elem}. Then, a folding scheme for R_{elem} into a relaxed relation is used, which combines the matrices 𝑀_1, 𝑀_2 as 𝑀_1 + 𝛼 𝑀_2 for a random 𝛼 ∈ F. Finally, the lookup equations are combined as (𝑀_1 + 𝛼 𝑀_2)* t^T = (a_1 + 𝛼 a_2)^T. In FLI, only the property that a matrix is in R_{elem} is folded, and this makes the FLI folding step the cheapest among existing solutions. The price to pay is in the cost for proving accumulated instances. FLI+SOS builds upon FLI to enable folding of large SOS-decomposable [STW23] tables. This is achieved through a variation of Lasso's approach to SOS-decomposability, which fits FLI naturally. For comparison, we describe (for the first time to our knowledge) straightforward variations of Protostar [BC23] and Proofs for Deep Thought [BC24] that also benefit from SOS-decomposability. We see that for many reasonable parameter choices, and especially those arising from lookup-based zkVMs [AST23], FLI+SOS can concretely be the cheapest folding solution.

We establish new results on the Fiat-Shamir (FS) security of several protocols that are widely used in practice, and we provide general tools for establishing similar results for others. More precisely, we: (1) prove the FS security of the FRI and batched FRI protocols; (2) analyze a general class of protocols, which we call \emph{$\delta$-correlated}, that use low-degree proximity testing as a subroutine (this includes many ``Plonk-like'' protocols (e.g., Plonky2 and Redshift), ethSTARK, RISC Zero, etc.); and (3) prove FS security of the aforementioned ``Plonk-like'' protocols, and sketch how to prove the same for the others. We obtain our first result by analyzing the round-by-round (RBR) soundness and RBR knowledge soundness of FRI. For the second result, we prove that if a $\delta$-correlated protocol is RBR (knowledge) sound under the assumption that adversaries always send low-degree polynomials, then it is RBR (knowledge) sound in general. Equipped with this tool, we prove our third result by formally showing that ``Plonk-like'' protocols are RBR (knowledge) sound under the assumption that adversaries always send low-degree polynomials. We then outline analogous arguments for the remainder of the aforementioned protocols. To the best of our knowledge, ours is the first formal analysis of the Fiat-Shamir security of FRI and widely deployed protocols that invoke it.