Zinc II: A Brakedown PCS Over the Rationals

What problem are we solving?

Part 1 built Zinc-PIOP: a polynomial interactive oracle proof over $\mathbb Q$ for integer-arithmetic relations. Sample a random prime $q$, project the witness through $\phi_q: \mathbb Z_{(q)} \to \mathbb F_q$, run a Spartan-shaped sum-check inside $\mathbb F_q$. Lemma 2.1 from Part 1 carried the whole soundness story — a bounded-bit-size witness can fool at most $\mathrm{poly}(\lambda)$ primes, so random-prime sampling catches cheats.

A PIOP isn’t a real argument though. To compile, we need a polynomial commitment scheme that:

• Works over $\mathbb Q_B$, not $\mathbb F_q$. The PIOP’s witness oracle is multilinear with rational coefficients.
• Extracts to bit-size-bounded rationals. Lemma 2.1 only bites when the extracted witness has bounded entries. A generic $\mathbb Q$-PCS gives unbounded extraction, which kills soundness.
• Doesn’t use hidden-order groups. The whole point of Zinc was to dodge the RSA-style assumptions CHA24 inherits.

That PCS is Zip. It’s a Brakedown variant — Merkle-commit encoded rows of the coefficient matrix — built around a new primitive: the IOP of Proximity to the Integers (IOPP-to-$\mathbb Z$). Plus a new linear code, JEA (Juxtaposed Expand-Accumulate), that survives the move from $\mathbb F_q$ to $\mathbb Q$ without bit-size blowup.

This part: Zip’s contract, the commit/test/eval phases, the two combinatorial lemmas that drive its soundness, JEA codes, the extractor wrinkle, and how the pipeline compiles to a hash-only succinct argument via iCOS.

Prerequisites. Multilinear polynomials, the equality polynomial $\widetilde{eq}$, and the sum-check protocol (the Spartan article covers all three). Comfort with the projection $\phi_q$ and the localization $\mathbb Z_{(q)}$ from Part 1. We build up Brakedown from scratch next, no prior exposure needed.

Brakedown in a Nutshell

Zip is a Brakedown variant, so spend a minute on Brakedown first. Original setting: $\mathbb F_q$. Goal: commit to a multilinear $f(X_1, \ldots, X_\mu)$ with coefficients in $\mathbb F_q$, later prove $f(\mathbf q) = y$ for a query point $\mathbf q$ and value $y$.

The tensor identity

This is the engine the whole scheme rides on, so let’s derive it from scratch. A multilinear polynomial in $\mu$ variables is determined by its $2^\mu$ values on the boolean hypercube $\{0, 1\}^\mu$, via

$f(\mathbf X) = \sum_{\mathbf b \in \{0, 1\}^\mu} f(\mathbf b) \cdot \widetilde{eq}(\mathbf b, \mathbf X),$

where $\widetilde{eq}(\mathbf b, \mathbf X) = \prod_{i = 1}^{\mu} \big(b_i X_i + (1 - b_i)(1 - X_i)\big)$ is the multilinear extension of the equality indicator (the “selector” that’s 1 when $\mathbf X = \mathbf b$ on the cube and 0 elsewhere — see Spartan for the underlying MLE machinery).

Now assume $\mu$ is even and split it as $\mu/2 + \mu/2$. Write $\mathbf b = (\mathbf b^{(1)}, \mathbf b^{(2)})$ and $\mathbf X = (\mathbf X^{(1)}, \mathbf X^{(2)})$, each half of length $\mu/2$. Because $\widetilde{eq}$ is a product over coordinates, it factors:

$\widetilde{eq}(\mathbf b, \mathbf X) = \widetilde{eq}(\mathbf b^{(1)}, \mathbf X^{(1)}) \cdot \widetilde{eq}(\mathbf b^{(2)}, \mathbf X^{(2)}).$

Substituting:

$f(\mathbf X) = \sum_{\mathbf b^{(1)}} \sum_{\mathbf b^{(2)}} f(\mathbf b^{(1)}, \mathbf b^{(2)}) \cdot \widetilde{eq}(\mathbf b^{(1)}, \mathbf X^{(1)}) \cdot \widetilde{eq}(\mathbf b^{(2)}, \mathbf X^{(2)}).$

Set $\dim = 2^{\mu/2}$ and define the coefficient matrix $\mathbf v^f \in \mathbb F_q^{\dim \times \dim}$ by $\mathbf v^f_{\mathbf b^{(1)}, \mathbf b^{(2)}} = f(\mathbf b^{(1)}, \mathbf b^{(2)})$, plus the equality vectors

$\mathbf q_1 = \big(\widetilde{eq}(\mathbf b^{(1)}, \mathbf X^{(1)})\big)_{\mathbf b^{(1)} \in \{0,1\}^{\mu/2}}, \qquad \mathbf q_2 = \big(\widetilde{eq}(\mathbf b^{(2)}, \mathbf X^{(2)})\big)_{\mathbf b^{(2)} \in \{0,1\}^{\mu/2}}.$

The double sum collapses to a quadratic form:

$f(\mathbf X) = \mathbf q_1 \cdot \mathbf v^f \cdot \mathbf q_2^T.$

That’s the tensor identity — evaluating a multilinear at $\mathbf X = \mathbf q$ becomes “row-combine the matrix with $\mathbf q_1$, then column-combine with $\mathbf q_2$.” Brakedown’s commit phase commits to the matrix; the eval phase rides this identity.

(This is the form Brakedown uses verbatim, modulo notation. The Brakedown paper writes it as $g(\mathbf r) = \langle \mathbf q_1 \otimes \mathbf q_2, \mathbf u \rangle$ — same equation with the matrix flattened into a vector.)

Worked example, carried through the section. Let’s pin down a concrete instance and reuse it across every phase. Take $\mathbb F_{11}$, $\mu = 2$, so $\dim = 2$ and $f$ has 4 coefficients on the hypercube $\{0, 1\}^2$. Pick

$f(0,0) = 2, \quad f(0,1) = 3, \quad f(1,0) = 5, \quad f(1,1) = 7.$

The coefficient matrix is

$\mathbf v^f = \begin{pmatrix} f(0,0) & f(0,1) \\ f(1,0) & f(1,1) \end{pmatrix} = \begin{pmatrix} 2 & 3 \\ 5 & 7 \end{pmatrix}.$

Pick the query point $\mathbf q = (3, 4)$. The equality vectors are

$\mathbf q_1 = (\widetilde{eq}(0, 3),\, \widetilde{eq}(1, 3)) = (1 - 3,\, 3) = (-2, 3) \equiv (9, 3) \pmod{11},$

$\mathbf q_2 = (\widetilde{eq}(0, 4),\, \widetilde{eq}(1, 4)) = (1 - 4,\, 4) = (-3, 4) \equiv (8, 4) \pmod{11}.$

The tensor identity says $f(3, 4) = \mathbf q_1 \cdot \mathbf v^f \cdot \mathbf q_2^T$. Step-by-step:

$\mathbf q_1 \cdot \mathbf v^f = (9, 3) \begin{pmatrix} 2 & 3 \\ 5 & 7 \end{pmatrix} = (9 \cdot 2 + 3 \cdot 5,\; 9 \cdot 3 + 3 \cdot 7) = (33, 48) \equiv (0, 4) \pmod{11},$

$(0, 4) \cdot (8, 4)^T = 0 \cdot 8 + 4 \cdot 4 = 16 \equiv 5 \pmod{11}.$

Sanity check by direct expansion: $f(3, 4) = 2 \cdot (1-3)(1-4) + 3 \cdot (1-3) \cdot 4 + 5 \cdot 3 \cdot (1-4) + 7 \cdot 3 \cdot 4 = 12 - 24 - 45 + 84 = 27 \equiv 5 \pmod{11}$. ✓ The identity holds.

Hold on to $\mathbf v^f, \mathbf q_1, \mathbf q_2$. We’ll keep using them.

Commit phase

Pick a linear code $\mathcal C$ over $\mathbb F_q$ — a $\mathbb F_q$-subspace of $\mathbb F_q^{\mathsf n}$ of dimension $\dim$ with good minimum distance. Encode each row $\mathbf v_i^f$ separately via $\mathsf{Enc}_{\mathcal C}: \mathbb F_q^{\dim} \to \mathbb F_q^{\mathsf n}$. Merkle-commit each encoded row. Output $\dim$ Merkle roots — that’s the commitment.

Worked example, continued. For our running case ($\dim = 2$), pick the simplest rate-$1/2$ Reed–Solomon-style code with length $\mathsf n = 4$ that sends $(a, b) \mapsto (a, b, a + b, a + 2b)$. Generator matrix:

$G = \begin{pmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 2 \end{pmatrix}.$

Encode each row of $\mathbf v^f$:

$\mathsf{Enc}_{\mathcal C}(\mathbf v_1^f) = (2, 3) \cdot G = (2,\; 3,\; 2 + 3,\; 2 + 6) = (2, 3, 5, 8) \pmod{11},$

$\mathsf{Enc}_{\mathcal C}(\mathbf v_2^f) = (5, 7) \cdot G = (5,\; 7,\; 5 + 7,\; 5 + 14) = (5, 7, 1, 8) \pmod{11}.$

The committed encoded matrix:

$\hat{\mathbf u} = \begin{pmatrix} 2 & 3 & 5 & 8 \\ 5 & 7 & 1 & 8 \end{pmatrix}.$

Merkle-commit each row. Output: two Merkle roots — one per row. That’s the whole commitment. (Real Brakedown uses $|\mathbb F_q| \approx 2^{128}$ and far longer codewords, but the shape is identical.)

Testing phase — “are these rows really codewords?”

The Merkle commitment binds the prover to some word in $\mathbb F_q^{\mathsf n}$ per row, but nothing forces those words to be codewords. Testing checks that.

1. $\mathsf V$ samples random coefficients $r_1, \ldots, r_{\dim} \in \mathbb F_q$.
2. $\mathsf P$ sends $\bar{\mathbf v} = \sum_i r_i \cdot \mathbf v_i^f \in \mathbb F_q^{\dim}$ (the random linear combination of the underlying message rows).
3. $\mathsf V$ samples $J \subseteq [\mathsf n]$ with $\lvert J \rvert = \Theta(\lambda)$. For each $j \in J$, $\mathsf V$ opens column $j$ of every committed row (getting $\hat u_{1,j}, \ldots, \hat u_{\dim, j}$) and checks

$\mathsf{Enc}_{\mathcal C}(\bar{\mathbf v})_j = \sum_i r_i \cdot \hat u_{i,j}.$

Worked example, continued. Say $\mathsf V$ samples $\mathbf r = (1, 2)$. The prover sends

$\bar{\mathbf v} = 1 \cdot (2, 3) + 2 \cdot (5, 7) = (2 + 10,\; 3 + 14) = (12, 17) \equiv (1, 6) \pmod{11}.$

To check consistency, $\mathsf V$ encodes $\bar{\mathbf v}$ and compares against an open column. Encoding:

$\mathsf{Enc}_{\mathcal C}(\bar{\mathbf v}) = (1, 6) \cdot G = (1,\; 6,\; 1 + 6,\; 1 + 12) = (1, 6, 7, 2) \pmod{11}.$

Suppose $\mathsf V$ samples column $j = 2$ (the third position, 0-indexed). The prover opens that column: $\hat u_{1, 2} = 5$ and $\hat u_{2, 2} = 1$. $\mathsf V$ checks

$\mathsf{Enc}_{\mathcal C}(\bar{\mathbf v})_2 = 7 \;\stackrel{?}{=}\; 1 \cdot \hat u_{1, 2} + 2 \cdot \hat u_{2, 2} = 1 \cdot 5 + 2 \cdot 1 = 7. \;\checkmark$

One column-open per draw of $j$; repeat $\Theta(\lambda)$ times for soundness. In our toy case the codeword length is only 4, so a few opens already cover most positions — over a real Brakedown setup, $\mathsf n$ is millions but only $\Theta(\lambda)$ opens are sampled.

Why this works (correlated agreement). The Brakedown soundness lemma — proximity gaps for linear codes — says: if any committed word $\hat{\mathbf u}_i$ is far from every codeword, then the random combination $\sum_i r_i \cdot \hat{\mathbf u}_i$ is also far from every codeword w.h.p. over $\mathbf r$. Far-from-codeword means $\mathsf{Enc}_{\mathcal C}(\bar{\mathbf v})$ disagrees with the linear combination on many columns, so $\Theta(\lambda)$ random columns catch the disagreement. Pass the test e.w.n.p. → every $\hat{\mathbf u}_i$ is the encoding of a unique nearby $\mathbf v_i$.

The intuition stripped down. A malicious prover wants to commit to something other than an honest encoding. Two failure modes the verifier wants to catch:

• The committed row isn’t a codeword at all (just a bag of $\mathbb F_q$ values that happen to hash). Testing’s column opens catch this — a non-codeword disagrees with every codeword on many positions, and any column-equation $\mathsf{Enc}(\bar{\mathbf v})_j = \sum r_i \hat u_{i,j}$ acts as a spot check that the prover’s “encoding” matches what the code structure demands.
• The committed row is a codeword but the prover lies later about what $\mathbf v_i$ it encodes. The randomized linear combination ties everything to one cross-check: if the prover is honest about all $\mathbf v_i$, the random linear combination $\sum r_i \mathbf v_i$ and the encoded linear combination $\mathsf{Enc}(\bar{\mathbf v})$ agree everywhere; if not, they disagree on a $\delta$-fraction of positions (where $\delta$ is the code distance), so column opens catch it.

Eval phase — “and does it give the claimed value?”

Once $\mathsf V$ trusts the rows are codewords, prove $f(\mathbf q) = y$ via the tensor identity.

1. $\mathsf P$ sends the partial sum $\bar{\mathbf v} = \sum_i \mathbf q_{1,i} \cdot \mathbf v_i^f \in \mathbb F_q^{\dim}$. Honestly, $\bar{\mathbf v} = \mathbf q_1 \cdot \mathbf v^f$ — the row-combine half of the tensor identity.
2. Code-consistency check. Same shape as testing: $\mathsf V$ samples $J$, opens column $j$ for each $j \in J$, checks $\mathsf{Enc}_{\mathcal C}(\bar{\mathbf v})_j = \sum_i \mathbf q_{1,i} \cdot \hat u_{i,j}$. This pins $\bar{\mathbf v}$ to be the genuine linear combination of the committed rows.
3. Final eval check. $\mathsf V$ checks $y = \bar{\mathbf v} \cdot \mathbf q_2^T = \sum_i \bar v_i \cdot \mathbf q_{2,i}$. By the tensor identity, this equals $f(\mathbf q)$.

Worked example, finishing. Replay with $\mathbf q_1 = (9, 3)$ in place of the random $\mathbf r$.

Prover sends $\bar{\mathbf v} = \mathbf q_1 \cdot \mathbf v^f = (9, 3) \cdot \mathbf v^f = (0, 4) \pmod{11}$ — the same partial sum we computed during the tensor-identity warm-up.

Code-consistency: $\mathsf V$ encodes $\bar{\mathbf v}$ and spot-checks against a random column.

$\mathsf{Enc}_{\mathcal C}((0, 4)) = (0,\; 4,\; 0 + 4,\; 0 + 8) = (0, 4, 4, 8) \pmod{11}.$

Open column $j = 0$: $\hat u_{1, 0} = 2$, $\hat u_{2, 0} = 5$. Check:

$\mathsf{Enc}_{\mathcal C}(\bar{\mathbf v})_0 = 0 \;\stackrel{?}{=}\; 9 \cdot 2 + 3 \cdot 5 = 18 + 15 = 33 \equiv 0 \pmod{11}. \;\checkmark$

Final eval check: $y \stackrel{?}{=} \bar{\mathbf v} \cdot \mathbf q_2^T = (0, 4) \cdot (8, 4)^T = 0 \cdot 8 + 4 \cdot 4 = 16 \equiv 5 \pmod{11}$. So the verifier accepts $f(3, 4) = 5$. Matches the direct computation. ✓

The eval phase is essentially the testing phase with $\mathbf q_1$ in place of the random $\mathbf r$, plus one final inner-product check against $\mathbf q_2$.

What survives, what changes for $\mathbb Q$

Brakedown’s whole soundness story rests on (a) the linear code having good distance and (b) the correlated-agreement lemma. Over $\mathbb F_q$ both are clean — fields have nice distance theory and the lemma is well-established.

Moving to $\mathbb Q$ breaks both:

• Distance. Random-matrix codes don’t exist over $\mathbb Q$ the way they do over $\mathbb F_q$. Building a code with good distance and cheap encoding over $\mathbb Q$ is the JEA problem (§JEA).
• Correlated agreement. Brakedown’s lemma uses field structure. Over $\mathbb Q$ we need different combinatorial tools — that’s Lemmas 2.4 and 2.5 (§Why a Single Integrality Check…).
• Bounded extraction. A finite field bounds entry bit-size by $\log \lvert\mathbb F\rvert$ for free. Over $\mathbb Q$ nothing bounds it — the extra integrality + size check in Zip’s testing phase is what supplies the bound.

Zip is the result of stitching these three patches into Brakedown’s template.

The Contract: Two Bit-Size Bands

Zip is a multilinear PCS for $f \in \mathbb Q_B^{\mathrm{multilin}}[\mathbf X]$ with one notable asymmetry between completeness and soundness:

with $B' < B$ related by

$B = 2 \cdot B' + (6 \cdot \dim + 2) \cdot (\lambda + \log \dim),$

where $\dim = 2^{\mu/2}$ is the side-length of the coefficient matrix (we’ll see this shape in a moment).

The IOPP-to-$\mathbb Z$ analogy. This shape mirrors any IOP of proximity to a code. There, the honest prover sends a real codeword, but the scheme only guarantees that a passing prover sent something close to a codeword — close enough that decoding pins down a unique nearby codeword. Zip plays the same game with integers: the honest prover sends an integral polynomial in $\mathbb Z_{B'}$, but the scheme only guarantees the passing prover sent something close to integral — where “close” means “rational with bounded bit-size $B$.”

The slack from $B'$ to $B$ is the analog of the proximity radius in a codeword IOPP. The lemmas below set its size.

Zip is both an IOPP-to-a-code (over $\mathbb Q$, via its underlying linear code) and an IOPP-to-$\mathbb Z$ (via a single bit-size check in the testing phase). The two checks slot together cleanly.

What the verifier actually sees

Before any protocol walk, anchor on what’s on the wire. Across the full commit + test + eval interaction, the verifier sees:

• At commit time. $\dim$ Merkle roots — one per encoded row of the coefficient matrix.
• During testing. A single random-linear-combination vector $\bar{\mathbf v} \in \mathbb Q^{\dim}$ from the prover, plus $\Theta(\lambda)$ column openings (one Merkle path per opened column, each revealing $\dim$ entries from the committed rows).
• During eval. A single projected vector $\bar{\mathbf v}_q \in \mathbb F_q^{\dim}$ from the prover, plus another $\Theta(\lambda)$ column openings.

That’s it. No big-integer polynomial is ever sent in the clear. The verifier’s whole job is to run two consistency checks against the random-linear-combinations the prover supplies, against $\Theta(\lambda)$-sized samples of the underlying committed words.

The Commit Phase

Same shape as Brakedown’s commit phase (§Brakedown in a Nutshell). The one structural twist: encode and commit happen over $\mathbb Q$, not $\mathbb F_q$.

Setup. Multilinear $f(X_1, \ldots, X_\mu)$ with $\mu$ even and coefficients in $\mathbb Q_B$. Set $\dim = 2^{\mu/2}$.

Step 1. Arrange $f$‘s coefficients on the hypercube $\{0, 1\}^\mu$ into a $\dim \times \dim$ matrix $\mathbf v^f$, each row $\mathbf v_i^f$ a length-$\dim$ vector of $\mathbb Q_B$ entries. (The tensor split derived in §Brakedown in a Nutshell.)

Step 2. Encode each row with the underlying linear code $\mathcal C_\lambda$ over $\mathbb Q$:

$\mathsf{Enc}_{\mathcal C_\lambda}(\mathbf v_i^f) \in \mathbb Q^{\mathsf n}.$

We’ll cover which code in §JEA — for now, treat it as a black box mapping a $\dim$-vector to an $\mathsf n$-vector with good distance.

Step 3. Merkle-commit each encoded row independently:

$\mathsf{cm} = \big(\mathsf{Commit}(\mathsf{Enc}_{\mathcal C_\lambda}(\mathbf v_i^f))\big)_{i \in [\dim]}.$

$\dim$ separate Merkle roots. Prover work is dominated by the $\dim$ encodings; each is a $\dim$-by-$\mathsf n$ generator-matrix multiplication.

The only structural twist vs. Brakedown. $\mathcal C_\lambda$ is a code over $\mathbb Q$, not $\mathbb F_q$. Everything else looks identical.

The Testing Phase

Testing is where Zip earns the “IOP of Proximity to the Integers” name. The phase is Brakedown’s standard random-linear-combination check plus one new step: an integrality + bit-size check on the prover’s response.

Protocol walkthrough.

1. $\mathsf V$ samples $r_1, \ldots, r_{\dim}$ uniformly from $[0, 2^\lambda - 1]$ — small $\lambda$-bit integer challenges. (The formal protocol uses $[0, q_0 - 1]$ for a fixed public prime $q_0 \approx 2^\lambda$ — a technicality that streamlines a few lemmas. For intuition, treat it as the $\lambda$-bit interval shown.)

2. $\mathsf P$ sends $\bar{\mathbf v} = \sum_{i \in [\dim]} r_i \cdot \mathbf v_i^f \in \mathbb Q^{\dim}$.

3. (The new step.) $\mathsf V$ rejects if any entry $\bar v_j$ is not an integer or has $|\bar v_j| > \dim \cdot 2^{B' + \lambda}$.

4. $\mathsf V$ samples a random subset $J \subseteq [\mathsf n]$ with $|J| = \Theta(\lambda)$. For each $j \in J$:

   • Open the Merkle commitments at column $j$, yielding $\hat u_{1,j}, \ldots, \hat u_{\dim, j}$. Reject if any $\hat u_{i,j}$ is not an integer of expected bit-size.
   • Check $\mathsf{Enc}_{\mathcal C_\lambda}(\bar{\mathbf v})_j = \sum_i r_i \cdot \hat u_{i,j}$.

Steps 1, 2, 4 are Brakedown verbatim. Step 3 is the only new ingredient. A single line of code: “are all entries integers, and is each at most $\dim \cdot 2^{B'+\lambda}$?”

What each step buys. Steps 1, 2, 4 are Brakedown’s correlated-agreement check — except with negligible probability (e.w.n.p.), they guarantee every $\hat{\mathbf u}_i$ is close to a unique codeword $\mathsf{Enc}_{\mathcal C_\lambda}(\mathbf v_i)$. That’s just “prover committed to some codeword in each row.”

Step 3 does the new work. It guarantees, e.w.n.p., that those underlying $\mathbf v_i$ vectors aren’t just rationals but bounded rationals: $\mathbf v_i \in \mathbb Q_B^{\dim}$. That’s the IOPP-to-$\mathbb Z$ part of Zip.

By the time testing passes, $\mathsf V$ knows the prover is committed to bit-size-bounded rational rows. That’s exactly Lemma 2.1’s precondition — and Lemma 2.1 is what the eval phase rides on top of.

Why a Single Integrality Check Pins Bit-Size

The Step 3 check is one integer comparison. Why does it pin bit-size so cleanly? Two combinatorial lemmas about random rational linear combinations.

Lemma 2.4 — “random linear combination of large rationals stays large”. Let $\mathbf v = (v_1, \ldots, v_n) \in \mathbb Q^n$, not all zero. Let $S = [0, 2^s - 1]$. Sample $r_i \leftarrow S$ for each $i$. Then for any $b \geq 1$,

$\Pr\!\left[\,\Bigl|\sum_i r_i v_i\Bigr| < 2^b\,\right] \;\leq\; \min\!\left\{1, \frac{2^b}{\|\mathbf v\|_\infty \cdot 2^s}\right\}.$

Read: if some $v_i$ has very large magnitude, a random small-integer combination almost certainly produces a large magnitude. The “size barrier” $\|\mathbf v\|_\infty \cdot 2^s$ scales with how large $v_i$ is.

Lemma 2.5 — “random linear combination of fractions rarely lands on an integer”. Let $\mathbf v \in \mathbb Q^n$, not all zero, with $v_i = a_i / b_i$ in lowest form. Let $M \geq 1$, and suppose some index $i$ has both $b_i > M$ and $v_i \neq 0$ — one entry with a denominator exceeding $M$. Then

$\Pr\!\left[\,\sum_i r_i v_i \in \mathbb Z \,\Big|\, r_i \leftarrow [0, M - 1]\,\right] \;\leq\; \frac{1}{M}.$

Read: a random small-integer combination of rationals where one has a large denominator almost never lands on an integer.

A tiny worked example

Take $n = 2$, $M = 5$ (so $r_1, r_2 \in \{0, 1, 2, 3, 4\}$). Consider three candidate vectors:

• Vector A: $\mathbf v = (1, 2)$. Both small integers. Every random combination $r_1 + 2 r_2$ is a small integer. Step 3 passes — and it should, this is the honest case.

• Vector B: $\mathbf v = (1, 1/7)$. One entry has denominator $7 > M = 5$. By Lemma 2.5, $\Pr[r_1 + r_2/7 \in \mathbb Z] \leq 1/5$. Concretely, $r_1 + r_2/7$ is an integer iff $7 \mid r_2$, and $r_2 \in \{0, 1, 2, 3, 4\}$ contains only $r_2 = 0$ satisfying this — so the probability is exactly $1/5$. The cheating prover gets caught $4/5$ of the time.

• Vector C: $\mathbf v = (1, 1000)$. Both integers, but the second exceeds the magnitude band. By Lemma 2.4 with $\|\mathbf v\|_\infty = 1000$, sampling interval size $M = 5$ (so $s = \log_2 M$), magnitude bound $N = 1000$: $\Pr[|r_1 + 1000 r_2| < 1000] \leq 1000/(1000 \cdot 5) = 1/5$. The bound is tight here — only $r_2 = 0$ produces a small magnitude (probability $1/5$, contributing $r_1 \in [0, 4]$); any $r_2 \geq 1$ already pushes $|r_1 + 1000 r_2| \geq 996$. The cheating prover slips through $1/M$ of the time and gets caught the rest.

  Scaling intuition: as $\|\mathbf v\|_\infty$ grows past $N$, the lemma’s ratio $N/(\|\mathbf v\|_\infty \cdot M)$ shrinks proportionally — but the unavoidable $r_n = 0$ slot keeps a floor near $1/M$. Zip pushes this floor to negligible by sampling $r_i$ from a $\lambda$-bit interval ($M \approx 2^\lambda$).

The two lemmas are the $\mathbb Q$-analogs of Brakedown’s correlated-agreement / proximity-gap lemmas. Brakedown needs random linear combinations of “close-to-codeword” words to stay close. Zip needs random linear combinations of large rationals to stay large, and random linear combinations of fractions to rarely be integers. Same kind of combinatorial statement; different ring.

How they combine

Step 3 demands the linear combination be both an integer and small (magnitude $< \dim \cdot 2^{B'+\lambda}$). With $r_i$ drawn from $[0, 2^\lambda - 1]$:

• Lemma 2.5 with $M = 2^\lambda$ says: if any $\mathbf v_i$ has an entry with denominator $> 2^\lambda$, the linear combination is hardly ever an integer. So passing the integrality check forces all denominators bounded by $2^\lambda$ e.w.n.p.
• Lemma 2.4 with $s = \lambda$ says: if any $\mathbf v_i$ has an entry with magnitude $\gg 2^{B'}$, the linear combination’s magnitude likely exceeds $\dim \cdot 2^{B'+\lambda}$. So passing the magnitude check forces all numerators bounded too.

Combine: passing Step 3 e.w.n.p. forces $\mathbf v_i \in \mathbb Q_B^{\dim}$ for each $i$. The slack constant $(6 \dim + 2)(\lambda + \log \dim)$ in the $B = 2 B' + \ldots$ formula absorbs the multiplicative factors hidden in the lemma-chain.

The Evaluation Phase

The eval phase proves a claim $f(\mathbf q) = y$ for a query point $\mathbf q \in \mathbb Z_B^\mu$ and value $y \in \mathbb Z$. The protocol is “Brakedown’s eval, but every check happens modulo a verifier-sampled random prime.”

Protocol walkthrough.

1. $\mathsf V$ samples a random $\Omega(\lambda)$-bit prime $q \in \mathcal P_\lambda$.

2. Bad-denominator branch. If any $\mathbf v_i^f$ has an entry whose denominator is divisible by $q$ — i.e., $\mathbf v_i^f \notin \mathbb Z_{(q)}^{\dim}$ — $\mathsf P$ aborts. (Same shape as Zinc-PIOP’s Step 2 from Part 1. Bounded by the same Lemma-2.1 logic: a bit-size-bounded witness can have at most $\mathrm{poly}(\lambda)$ primes dividing any denominator, so this branch fires negligibly often.)

3. Otherwise, $\mathsf P$ uses $f(\mathbf q) = \mathbf q_1 \cdot \mathbf v^f \cdot \mathbf q_2^T$ with $\mathbf q_1, \mathbf q_2 \in \mathbb Z^{\dim}$ and sends the projected partial sum

$\bar{\mathbf v}_q = \sum_{i \in [\dim]} \phi_q(\mathbf q_{1,i}) \cdot \phi_q(\mathbf v_i^f) \in \mathbb F_q^{\dim}.$

4. $\mathsf V$ samples $J \subseteq [\mathsf n]$ with $|J| = \Theta(\lambda)$. For each $j \in J$:
   • Open the Merkle commitments at column $j$, yielding $\hat u_{1,j}, \ldots, \hat u_{\dim, j}$.
   • Code-consistency check. $\mathsf{Enc}_{\mathcal C_{\lambda, q}}(\bar{\mathbf v}_q)_j = \sum_i \phi_q(\mathbf q_{1,i}) \cdot \phi_q(\hat u_{i,j})$, where $\mathcal C_{\lambda, q} = \phi_q(\mathcal C_\lambda)$ is the projected code.
   • Final eval check. $\phi_q(y) = \sum_i \bar v_{q, i} \cdot \phi_q(\mathbf q_{2, i})$.

The two soundness pieces.

The code-consistency check, by Brakedown’s argument applied to the projected code $\phi_q(\mathcal C_\lambda)$, gives e.w.n.p. that $\bar{\mathbf v}_q = \sum_i \phi_q(\mathbf q_{1,i}) \cdot \phi_q(\mathbf v_i^f)$. This is why the projected code needs good distance — JEA codes are designed for exactly this (next section).

The final eval check then gives $\phi_q(y) = \phi_q(f(\mathbf q))$ — equality modulo $q$. We want full $\mathbb Q$-equality. To get there, we invoke Lemma 2.1 from Part 1. That lemma needs bit-size-bounded $\mathbf v_i$. The testing phase delivers them. The two phases interlock: testing pins entry bit-sizes; eval rides Lemma 2.1 on top of that bound.

JEA Codes: A Linear Code That Survives Over $\mathbb Q$

Every Brakedown-style PCS rests on a code with good distance and cheap encoding. Over $\mathbb F_q$ that’s solved — Brakedown’s recursive code, Basefold’s, Reed–Solomon. Over $\mathbb Q$, the standard tricks fail.

Why standard codes break. Brakedown’s and Basefold’s codes are built recursively via iterative matrix multiplications, with random field elements at each level. Over $\mathbb F_q$, those are $\log q$ bits. Naively translating to $\mathbb Z$ — replacing field elements with integers — produces matrices whose entries blow up to thousands of bits after a few recursion levels. Encoding then needs huge-integer multiplications, defeating the whole purpose.

Reed–Solomon works over any ring, but encoding is $O(\mathsf n \log \mathsf n)$ via FFT — fine for runtime, but it kills the linear-time-prover benefit Brakedown buys you.

JEA’s answer: keep the matrix sparse with small entries. Adapted from [BFK+24]‘s expand-accumulate codes, drawing randomness from $[0, s - 1] \subset \mathbb Z$ instead of $\mathbb F_q$.

Picture two stacked sparse integer matrices: each row has only $O(\log n)$ nonzero entries, all $\sim \log s$ bits. Encoding is a sparse-matrix-vector multiply with bounded-bit numbers — no recursion, no field elements, no bit-size blowup.

Construction (Definition 6.1)

Let $n, d \geq 1$. Let $A \in \mathbb Z^{n \times n}$ be the upper-triangular all-ones accumulator matrix. Let $S = [0, s - 1]$ for some integer $s > 1$.

• $E_1 \in \mathbb Z^{d \times n}$: each row is a uniformly random weight-$t$ vector with nonzero entries drawn from $S$, where $t = \gamma \log n$. (“BP” — bounded-positions.)
• $E_2 \in \mathbb Z^{d \times n}$: each entry is independently nonzero with probability $p = t/n$ (drawn from $S$ when nonzero), zero otherwise. (“Ber” — Bernoulli.)

Form $M_{\mathsf{BP}} = E_1 \cdot A$ and $M_{\mathsf{Ber}} = E_2 \cdot A$. Two linear codes over $\mathbb Q$: $\mathcal C_{\mathsf{BP}}, \mathcal C_{\mathsf{Ber}}$. The JEA code is their concatenation:

$\mathsf{Enc}_{\mathcal C_{\mathsf{JEA}}}(\mathbf v) = (\mathbf v \cdot M_{\mathsf{BP}}) \,\|\, (\mathbf v \cdot M_{\mathsf{Ber}}).$

Length $2n$, dimension $d$.

Why this works over $\mathbb Q$

$M_{\mathsf{BP}}$ and $M_{\mathsf{Ber}}$ are sparse (because $E_1, E_2$ are), and nonzero entries have $\sim \log s$ bits. Encoding a $B'$-bit-entry integer vector costs $B'$-bit-by-$\log s$-bit multiplications and $\sim (B' + \log s)$-bit additions. No bit-size blowup. Specifically, $B' \approx 2\lambda$ and $\log s \approx 4\lambda$ are the operative numbers for Zinc — all operations stay $O(\lambda)$ bits.

Projection requirement

The eval phase calls $\mathsf{Enc}_{\mathcal C_{\lambda, q}} = \mathsf{Enc}_{\phi_q(\mathcal C_\lambda)}$ — the code projected mod a random $q$. Brakedown’s column-consistency soundness relies on the projected code having good distance.

Theorem 6.5 (paraphrased). As long as $s$ is large enough, the entries of $M_{\mathsf{BP}}, M_{\mathsf{Ber}}$ projected mod $q$ look uniform in $\mathbb F_q$ (e.w.n.p. over the choice of $q$).

So the projected code is essentially a JEA code over $\mathbb F_q$, which is exactly what [BFK+24] analyzed. The size threshold: per Remark 6.7, $s \approx 2^{4\lambda}$ suffices. The factor of $4$ comes from a Markov-bound chain in the projection-error analysis; Remark 6.8 conjectures it can drop to $2^{2\lambda}$ via better concentration. Operationally, $s$ controls generator-matrix bit-width — $4\lambda$ bits is fine, $2\lambda$ would be tighter.

The Extractor And the Expected-Polytime Wrinkle

Every PCS soundness story needs an extractor. Zip’s has one quirk that doesn’t show up in finite-field schemes.

The wrinkle. In any code-based PCS, a malicious prover can replace some entries of the committed word $\hat{\mathbf u}_i$ with arbitrary bit-strings — the Merkle tree commits to whatever bits the prover hashes in. Over a finite field $\mathbb F$, those bit-strings are at most $\log \lvert\mathbb F\rvert = O(\lambda)$ bits, so the extractor reads the entire entry at unit cost. Over $\mathbb Q$, the prover can write an arbitrarily long bit-string into a single entry. Reading it naively is not polynomial-time.

The fix. The extractor reads at most a fixed number of bits per entry — concretely

$\log(\|M_\mathcal C\|_\infty \cdot \dim) + 2 B' + (6 \dim + 2) \log(2^\lambda \cdot \dim) \text{ bits},$

where $\|M_\mathcal C\|_\infty$ is the largest absolute value in the JEA generator matrix. If the entry’s encoding exceeds that budget, it records the position as a ”$\perp$ disagreement” and moves on, instead of trying to read the rest.

Consequence. The extractor runs in expected polynomial time, not strict polynomial time. By Lindell’s witness-extended emulation (Lin01), expected-polytime extraction is equivalent to standard knowledge soundness for our purposes — the formal soundness statement still goes through.

The rest of the extractor is a standard rewinding-style PCS extractor: sample challenges $\mathbf r$, run the prover, retry on failure, build up $\dim$ linearly independent successful challenges, invert to recover the witness. Just over $\mathbb Q$, with the bit-budget cap as the one new ingredient.

Compilation: The Pipeline

Two pieces left: turning the PIOP-plus-PCS into an IOP, then turning that IOP into a succinct argument.

PIOP → IOP. Replace each polynomial oracle $[[\tilde w]]$ in Zinc-PIOP with a Zip commitment — a tuple of Merkle roots over encoded coefficient-matrix rows. Replace each polynomial-oracle query in sum-check with a Zip evaluation IOP execution certifying the queried value. Result: a regular hash-based IOP, no polynomial-oracle abstraction left.

IOP → succinct interactive argument via iCOS. The COS transformation [COS20] compiles an IOP into a SNARK by Merkle-committing every oracle and applying Fiat–Shamir. It requires the underlying IOP to satisfy state-restoration knowledge soundness. Zip provides only standard knowledge soundness (the stronger property is flagged as future work in §2.4 of the paper), so we use iCOS — the interactive variant of COS, which skips the Fiat–Shamir step. The result is succinct interactive, not non-interactive.

Beneath iCOS sits iBCS [CDGS23], the vector-commitment-based BCS variant. Both transformations are “Merkle-commit every oracle, answer queries via Merkle openings” — succinctness comes from Merkle path length being $O(\log \mathsf n)$ rather than $\mathsf n$.

The takeaway. From the engineer’s seat: “Zinc-PIOP → IOP via Zip → succinct interactive argument via iCOS → (eventually) SNARK via Fiat–Shamir.” The final non-interactive step is open work — the paper flags state-restoration soundness as the missing piece.

What This Buys You

The full system, end-to-end:

• Hash-only. Every cryptographic primitive is collision-resistant hashing. No hidden-order groups, no RSA assumptions, no pairings. The random oracle for Fiat–Shamir is the only model dependency, standard for any hash-based SNARK.
• Plausibly post-quantum. Nothing in the security argument relies on group cryptography. Subject to the random oracle being instantiable, the construction has a path to PQ security.
• Multi-modulus over $\mathbb Z$. From Part 1’s R1CSℓ structure. Zip plays no direct role here, but Zip is what unlocks it by removing the hidden-order-group dependency.

Concrete cost shape. No benchmarks are published yet (Section 2.4 of the paper flags implementation as ongoing), so this is the asymptotic profile:

• Commit: $\dim$ encodings of $\dim$-length integer vectors with a sparse JEA generator matrix. Roughly $O(\dim^2 \cdot t)$ small-integer ops, where $t = \gamma \log \dim$.
• Test: $\Theta(\lambda)$ Merkle openings per row, plus the random-linear-combination + bit-size check.
• Eval: $\Theta(\lambda)$ Merkle openings, plus a $\dim$-by-$\dim$ matrix-vector product modulo a random $\Omega(\lambda)$-bit prime.
• Bit-widths everywhere: all operations bounded to $O(\lambda)$-bit or $O(B)$-bit integers. No thousand-bit arithmetic anywhere — that was the whole point.

Extending Part 1’s headline table:

What We Didn’t Cover

A short list of what’s in the paper but not in this walkthrough:

• Full state-restoration soundness analysis for Fiat–Shamir compilation — flagged as further work in §2.4. Without it, the final scheme is interactive.
• Formal proofs of Lemmas 2.4 and 2.5 — §5.4.1.
• The general algebraic-relations machinery (§4) — Zinc-PIOP works for any algebraic indexed relation, not just R1CSℓ. We focused on R1CSℓ throughout.
• The full extractor analysis — Protocols 10 and 11 in §5.4.3, plus Lemma 5.24 on expected running time.
• JEA distance bounds — §6, Theorem 6.5 and the chain of lemmas underneath. We stated the result; the analysis is several pages of Markov-bound chasing.
• Implementation and benchmarking — flagged as ongoing in the paper.

Conclusion

Five core ideas drive Zinc + Zip:

1. A Brakedown-style PCS over $\mathbb Q$ is possible if you’re careful about what the prover commits to, what the testing phase proves, and what code you use.
2. The IOPP-to-$\mathbb Z$ abstraction — “prover knows a word close to integral” — slots into Brakedown’s existing IOPP-to-code abstraction. Zip is both at once.
3. Two combinatorial lemmas (2.4, 2.5) replace Brakedown’s correlated-agreement bounds in the $\mathbb Q$ setting. Easier to state than Brakedown’s, in fact.
4. JEA codes — sparse generator matrix, small entries — are a linear code that survives translation from $\mathbb F_q$ to $\mathbb Q$ without bit-size blowup. Most other linear codes don’t.
5. iCOS is the standard Merkle compilation step. Fiat–Shamir for non-interactivity is open work.

What makes Zinc + Zip significant: it’s the first hash-only succinct argument for native integer-arithmetic statements, with multi-modulus support at zero arithmetization overhead, and a plausibly post-quantum path. The construction recipe — “hash + linear code over $\mathbb Q$” — is clean, and unlocks a class of relations that previously required RSA-style assumptions to handle efficiently.

Open theoretical question: sharpen the JEA projection-error analysis to drop $s$ from $2^{4\lambda}$ to $2^{2\lambda}$ (Remark 6.8) and shave constants. Open practical question: implementation — benchmarks against Brakedown over $\mathbb F_q$ will show whether the bit-bookkeeping overhead is small enough in practice for the integer-arithmetic flexibility to pay off.

References

• Zinc (this paper): Garreta, A., Waldner, H., Hristova, K., Dall’Ava, L. (2025). “Zinc: Succinct Arguments with Small Arithmetization Overheads from IOPs of Proximity to the Integers.” Nethermind Research.
• Part 1 of this walkthrough: Zinc I: A PIOP Over the Rationals That Bypasses Arithmetization.
• CHA24 (mod-AHP): Campanelli, M., Hall-Andersen, M. (2024). “Fully-succinct arguments over the integers from first principles.” https://eprint.iacr.org/2024/1548
• Brakedown: Golovnev, A., Lee, J., Setty, S., Thaler, J., Wahby, R. S. (2023). “Brakedown: Linear-time and field-agnostic SNARKs for R1CS.” CRYPTO 2023.
• BFK+24 (EA codes over fields): Block, A. R., Fang, Z., Katz, J., Thaler, J., Waldner, H., Zhang, Y. (2024). “Field-agnostic SNARKs from expand-accumulate codes.” CRYPTO 2024.
• BHR+21 (integer PCS): Block, A. R., Holmgren, J., Rosen, A., Rothblum, R. D., Soni, P. (2021). “Time- and space-efficient arguments from groups of unknown order.” CRYPTO 2021.
• COS20 (COS transformation): Chiesa, A., Ojha, D., Spooner, N. (2020). “Fractal: Post-quantum and transparent recursive proofs from holography.” EUROCRYPT 2020.
• CDGS23 (iBCS): Chiesa, A., Dall’Agnol, M., Guan, Z., Spooner, N. (2023). “On the security of succinct interactive arguments from vector commitments.” https://eprint.iacr.org/2023/1737
• CY24: Chiesa, A., Yogev, E. “Building Cryptographic Proofs from Hash Functions.”
• Lin01 (witness-extended emulation): Lindell, Y. (2001). “Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation.”
• BSBHR18 (IOPP): Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M. (2018). “Fast Reed-Solomon Interactive Oracle Proofs of Proximity.”