| The WhitePaper Reading Club Privacy Hub | Research Day [03] | 20 Nov 2025 |
|---|---|
| A Note on Adding Zero-Knowledge to STARKs | [Rongxin] |
Summary
Shows how to add privacy features to STARK proof systems so they don't reveal witness info while proving computations are correct.
Why This Is Important
Production STARK implementations (Plonky2, Risc-Zero, Triton) had gaps in their ZK protocols that could leak witness data. This work provides a way to fix these issues while maintaining efficiency for real deployments
Key Innovation
Identifies where ZK breaks inside STARK systems and provides the correct masking/randomization rules to fix it—clarifying how polynomial IOPs behave under FRI queries and quotient decompositions. It pinpoints subtle leakage sources and explains how to correctly handle: FRI (low-degree testing via random folding of evaluations), FFT-based quotient splits (q(X) decomposition across roots of unity), extension-field queries (each query in 𝔽_{p^e} equals e base-field leaks), and FRI folding (evaluation mixing that implicitly expands query count)—all of which earlier implementations misapplied, causing witness leakage.
Overview
(i) STARKs use polynomial IOPs + FRI; achieving zero-knowledge requires hiding witness polynomials against both DEEP queries and all FRI-induced query closures. (ii) Formalizes BSCR-style randomization ŵ(X)=w(X)+v_H(X)·r(X), proving the exact degree requirement: 2·d·(e·n_F + n_D) + n_D ≤ h ≤ |H| for perfect ZK. (iii) Shows FFT decomposition is not ZK-safe by default: the simulator must work inside a splitting field where v_D(X^d) fully factors, which prior systems ignored. (iv) Provides a corrected construction for perfect ZK in permutation (grand-product) arguments, fixing leakage found in Plonky2/Halo2 due to incomplete constraint propagation.
Background
(i) STARK basics: Witness → low-degree extension on domain H; constraints → quotient q(X) divisible by Z_H(X)=X^{|H|}−1. (ii) FRI: Low-degree testing via evaluation folding; each fold mixes evaluations and reduces degree, requiring strong randomizer masks. (iii) Masking (core idea): To achieve ZK, each witness polynomial w(X) is masked as ŵ(X) = w(X) + v_H(X)·r(X) where v_H(X) is the vanishing polynomial and r(X) is a random low-degree polynomial. This ensures that (a) all DEEP queries, (b) all FRI queries, and (c) all implicit queries induced by FFT splits or extension-field evaluations see values statistically independent of w(X). (iv) A query in Fₚₑ corresponds to e base-field queries due to Galois conjugation; the randomizer must have enough entropy to mask all of them. (v) Common failures: Incorrectly sized r(X), misunderstanding how masking interacts with FRI folding, and ignoring implicit queries from quotient splitting or permutation constraints—all of which can reveal structural information about the witness.
Team
(i) Ulrich Haböck — StarkWare (ex-Polygon Labs); author of widely used FRI notes; polynomial IOP researcher. (ii) Al-Kindi — Polygon Technology; works on STARK arithmetization and polynomial commitments.
Component Deep Dive
| 1. BSCR Randomization | Without correct masking, FRI folding + extension-field queries leak true witness evaluations. (i) Randomizer r(X) over degree h ensures folded/extended queries become statistically uniform. (ii) h must satisfy full query-closure bound: e·n_F + n_D ≤ h (or the stronger 2·d·(e·n_F + n_D) + n_D for FFT-style splits). (iii) Ensures perfect honest-verifier ZK over all DEEP + FRI query sets. |
|---|---|
| 2. FFT Quotient Decomposition | FFT-type splits induce hidden evaluation points that must also be masked. (i) Each explicit query creates d implicit queries through q_i(z^d). (ii) Simulator must operate in the splitting field K where v_D(X^d) is fully factored. (iii) Earlier protocols omitted this, causing incomplete zero-knowledge. |
| 3. Alternative Decompositions | Avoids FFT leakage and makes ZK masking simpler. (i) Canonical monomial split: q(X)=Σ X^{k̂(i−1)}q_i(X); needs h ≥ 2·(e·n_F + n_D). (ii) Lagrange decomposition: q(X)=Σ L_{H_i}(X)·q_i(X); most flexible and easiest to randomize. |
| Perfect ZK for Permutation Arguments | Incomplete constraints leaked whether the challenge α matched witness values. (i) α hitting witness range forces Z(x)=0 in forward/backward propagation. (ii) Solution: mute constraint updates when α−w_1(x)=0 or α−w_2(x)=0. (iii) Restores completeness while maintaining soundness and perfect ZK. |
| 5.Performance Analysis | Developers need to know whether correct ZK is expensive. (i) Overhead ratio ≈ 1 + 4/(3·log|H|) for typical wide-trace AIRs. (ii) Hashing cost unchanged; main cost is slightly larger FFTs over |H|+h. (iii) Overall proving cost increases modestly. |