4. Reed Solomon

When discussing SNARKs, a prover aims to convince a verifier of a statement’s validity. In this setting, both the prover and the verifier have access to a random oracle, which they can query to receive truly random responses. Once a protocol is designed in this model, the random oracle can be instantiated with a concrete cryptographic hash function, resulting in a practical SNARK that can be deployed. This approach yields SNARKs with

• transparent setups (no trusted setup required)
• highly efficient implementations (avoiding public-key cryptography)
• plausible post-quantum security (i.e., security in the Quantum Random Oracle Model, or QROM)

Q How do we construct hash-based SNARKs?
A Key idea: Hash-based SNARKs replace algebraic commitments with Merkle-tree commitments over evaluations, relying on query efficiency and probabilistic checks instead of heavy cryptography

• We start by building an IOP (Interactive Oracle Proof). This is an interactive protocol between a prover and a verifier where the prover sends a large proof, and the verifier only makes a small number of queries into it. Typically, the proof length is L = O(n), and the number of queries is Q = O(log n)
• Next, we apply the BCS transformation. In this transformation, every message of the IOP is committed to using a Merkle tree. Instead of sending full messages, the prover sends commitments (Merkle roots), and whenever the verifier wants to read specific parts, the prover provides Merkle authentication paths
• To remove interaction, we apply the Fiat-Shamir transform, which replaces verifier randomness with hashes, compressing the interaction into a single non-interactive proof. The final efficiency of the SNARK largely depends on how efficient the underlying IOP is
• Now, to build efficient IOPs for NP statements (like R1CS), we use polynomial IOPs
• Here, instead of sending arbitrary data, the prover is restricted to sending polynomials. The verifier can query these polynomials at random field points and check consistency
• These polynomial IOPs are then compiled into standard IOPs and passed through the BCS transformation
• To make this work efficiently, we use polynomial commitment schemes, which allow the prover to commit to a polynomial and later open (prove) its value at specific points. Examples include pairing-based schemes like KZG, as well as hash-based commitments used in transparent systems
• In hash-based approaches (like those used in STARK-style systems), instead of sending the full polynomial, the prover evaluates it over many points (usually over a structured domain), commits to these evaluations using Merkle trees, and the verifier checks correctness by querying a few random positions. Additional tests (like low-degree testing) ensure that the evaluations correspond to a valid low-degree polynomial

Q How does Reed-Solomon comes into the picture?
A A Reed-Solomon (RS) code is just: “Take a low-degree polynomial and evaluate it over a set of points” - “It’s used to encode computation constraints (like R1CS) into polynomial form”. So instead of storing the polynomial itself, you store its evaluations over a domain (L)

$$RS[F,L,m]=f:L\to F|f\in F[X_1,...,X_m]$$

• f is a low-degree polynomial
• L is the evaluation domain
• Codeword = evaluations of f over L

When we talk about Constraint Reed-Solomon code: we add a constraint on top of RS. Instead of allowing any low-degree polynomial, we only allow those that satisfy a specific condition

$$CRS[F,L,m,\hat{w},\sigma ]=f\in RS[F,L,m]:\sum _{b\in {0,1}^m}\hat{w}(f(b),b)=\sigma$$

Where:

$$\hat{w}\in F[Z,X_1,...,X_m],\sigma \in F$$

• Start with a low-degree polynomial f
• Evaluate it over domain L
• Add a global constraint over Boolean hypercube {0,1}
• Only keep polynomials satisfying the constraint
• ( ŵ ) is a polynomial: ŵ ∈ F[Z, X₁, ..., Xₘ]
• ( σ ∈ F ) is a fixed target value
• You evaluate the polynomial (f) at Boolean points (b ∈ {0,1}^m)
• Then apply (ŵ) to the value f(b) and the point (b)
• Sum everything, and enforce: total = σ
• This lets you encode global constraints on the polynomial. For example, we can enforce: f(a) = α by designing (ŵ) such that the sum isolates that condition

And this is what allows us to use WHIR as an commitment scheme

Q What is WHIR ?
A WHIR is an IOPP (Interactive Oracle Proof of Proximity) designed specifically for Constrained Reed–Solomon (CRS) codes. As we said above that “we evaluate polynomial at many points and commit using Merkle trees”, Here WHIR provides IOP layer then and flow is like Computation → Polynomial → CRS → WHIR (IOPP) → BCS → Fiat–Shamir → SNARK, it replaces FRI in SNARKs, To be more precise in previous question:

• We reduced computation → polynomials (via R1CS / AIR)
• Then → CRS (Reed–Solomon + constraints)
• Now we need → a way to prove that a function is close to this CRS - this is what exactly WHIR does

WHIR proves that:

$$f\approx CRS[F,L,m,\hat{w},\sigma ]$$

• f is close to a low-degree polynomial
• AND satisfies the global constraint (from CRS)

So it’s doing both:

1. Low-degree testing (like FRI)
2. Constraint checking (like ŵ constraint)

WHIR reduces problem size using folding, each round shrinks dimension by factor (2^k)

• Parameter: k ≈ log m
• This is why: Rounds = O(m / k)
• Query Complexity: q_WH​IR = O((λ / k) · log m) = O(λ)
• Verifier Time = O(q_WH​IR · (2^k + m)), it has no divisions so it’s very efficient over finite fields
• Alphabet = F^{2^k} - Instead of single field elements, verifier works over chunks this comes from folding
• Proof length = O(n), Linear in input size (standard for IOPPs)

Scheme	Queries	Verifier Time	Alphabet
BaseFold	q_BF = O(λ · m)	O(q_BF)	F^2
FRI	q_FRI = O((λ / k) · m)	O(q_FRI · k · 2^k)	F^{2^k}
STIR	q_STIR = O((λ / k) · log m)	O(q_STIR · k · 2^k + λ^2 · 2^k)	F^{2^k}
WHIR	q_WH​IR = O((λ / k) · log m)	O(q_WH​IR · (2^k + m))	F^{2^k}
Q WHIR as Σ-IOP Compiler ?
A WHIR is not just a Reed–Solomon proximity test (like FRI). It is a Constrained Reed–Solomon (CRS) proximity test, it means low-degree property and constraint satisfaction (like sumcheck-style conditions)

• Earlier (FRI-style world): we prove polynomial correctness via evaluation checks, Verifier queries: “what is f(x)?”
• With WHIR: we can instead verify global constraints. i.e., sumcheck-style checks

WHIR gives a way to compile a Σ-IOP (sumcheck-based IOP) into a standard IOP

• Simply it let’s you replace the evaluation checks with sumcheck constraints over Boolean hypercube, so instead of: check f(x) = y, we do ${\sum }_{b\in {0,1}^m}\hat{w}(f(b),b)=\sigma$
• Left side (Σ-IOP):
  • Prover sends: polynomials (p̂, q̂)
  • Verifier performs: sumcheck-like queries
• Right side (after compilation using WHIR):
  • Everything is reduced to: f : L → F
  • Along with constraint: ${\sum }_{b\in {0,1}^m}\hat{w}(f(b),b)=\sigma$
• This gives us a clean pipeline R1CS → Sumcheck (Σ-IOP) → CRS → WHIR → BCS → Fiat–Shamir → SNARK
• WHIR = CRS proximity test + sumcheck support. This allows efficient transformation from R1CS to IOPs
• Basically FRI checks “is this a polynomial?” but WHIR checks “is this a polynomial AND does it satisfy computation?”

Q What is Proximity Gaps in Reed–Solomon?
A A collection S has a (δ, ε)-proximity gap if:

• Either: $Pr[f\in Sis\delta -closetoRS]=1$
• Or: $Pr[f\in Sis\delta -closetoRS]\le \epsilon$No intermediate case exists

For intuition let’s say a function is either, close to RS or far from RS, cannot be “half correct”, now random linear combination given C₁, C₂, ..., C_ℓ and we define as C* = Σ αⱼ Cⱼ, the the key property is If C* is close to RS → each Cⱼ is close.
This is important as it enables folding (FRI / WHIR), prevents error hiding and gives strong soundness guarantees

• A stronger version of Mutual Correlated Agreement (MCA) is used in WHIR that says not only each function is close but they also agree on same positions
• They’re also used in SNARKs, specifically in FRI, STIR and WHIR this provides low query complexity, efficient verification and soundness amplification

Proximity gap is the reason why random checks work