ProveKit v2 Whitepaper (WIP)
This browser cannot display the PDF inline. Open the compiled whitepaper.
ProveKit v2 Whitepaper (WIP)
A web-readable treatment of scheduled-witness R1CS, WHIR, and zero-knowledge commitments for a practical proof system.
Draft status. This page mirrors the current research branch. Sections marked (tbc) are intentionally shown as unfinished; the text is not a production security claim or a completed protocol specification.
A proof pipeline designed around the witness
The construction starts with a two-stage R1CS whose first-stage witness is independent of verifier challenges and whose second-stage witness can be derived after those challenges arrive. It then turns the resulting constraints into multilinear and Reed-Solomon claims that WHIR can fold and verify.
The zero-knowledge sections add randomized zero-checks and masked commitments so that the verifier can check consistency without learning the underlying witness. The appendix collects the current soundness notes, correlated-agreement statement, and alternative VEIL direction.
R1CS with scheduled witnesses. (tbc)
Two-round R1CS, to support lookups into tables, which are baked into the R1CS matrices. The witness consists of
Round-1 witness : These witnesses are independent of the verifier challenge Includes public inputs, constants, and lookup table multiplicities.
Round-2 witness : These witnesses depend on the verifier challenges. These are the verifier challenges themselves, the logUp inverses and their sums.
The complete witness for the constraint system is of the form
with and ,
subject to constraints
with , and where is the entrywise (Hadamard) product. As for the witness, we split the matrices into
with and corresponding to the - and -parts. Typically the system is partially decoupled, with each starting with a large block of zero rows, but we currently do not leverage simpler representations than the ones above.
We need:
Definition of the first stage R1CS with auxiliary lookup relation
Definition of randomized R1CS (with two stages), and its soundness error
Split-witness builder.
There is a split-witness builder for stepwise computation of the complete witness.
Preliminaries
Although the entire construction described in the writeup applies to arbitrary prime fields, we confine ourselve to the the following choices. Let be the Goldilocks prime field [citation pending], with the Solinas prime
as modulus. We denote by any cryptographically large extension, in our case the degree 3 extension , using…
Notation
Boolean Hypercube , indexing in natural order via , multivariate and multilinear polynomials, Lagrange polynomial
Inner product notation.
Multilinears and univariates
Given a function (a vector of values) we will write
for its multilinear extension, and associate to it the univariate polynomial
defined by the values of over , where is the decomposition of the index into bits. Under this values-to-coefficient regime, we identify the space of multilinears (in variables) with the univariate space
in a way that is particularly efficient for Reed—Solomon encoding.
Univariate evaluation
Evaluation at a point is a linear functional and can be written as inner product with
and its values over the hypercube are the powers of in natural order.
Interleaved representation
In alignment with the sumcheck protocol, we will often think of a multilinear decomposed into its -prefix functions
Here we again used the identification , by each index specifying the prefix via its bits. We call the interleaved representation of , with interleaving depth . In terms of their univariate polynomials,
which is the FFT decomposition of .
Liftings
Given a multilinear in variables, and , we call
its lifting to variables. In terms of the values over the hypercube, lifting simply places the original vector (the values over ) on the prefix cube
and pads it with zero on the remainder of . In terms univariate representations,
We use lifting to uniformize our R1CS across the two stages at no additional cost.
Properties of interleaved Reed—Solomon codes
Are RS codes over an extension field. Same rate, same distance.
The protocol without zero-knowledge
In this section we describe the main construction for proving a two-stage R1CS, yet without the additional measures for zero-knowledge. The protocol is a combination Spartan [1] and WHIR [2] as a general inner-product argument. We skip the proving the values of the public circuit polynomials, which in [1] is handled by SPARK, and assume that the verifier does compute their values by itself. In this way we obtain succinct proof sizes, yet the verifier costs are of the same order as the witness size.
Arithmetization.
We consider the R1CS witness vectors padded to their next power of two, i.e. as functions
and we denote their multilinear extensions again by the same letters. Likewise, the number of overall constraints are padded to a power of two, say , and we view the R1CS matrices as functions
with the same notation for their multilinear extensions.
Throughout the following we assume that . We lift to the same number of variables as , and likewise we do for the second stage matrix polynomials . The resulting system has
as the combined witness polynomial, and
for , as the combined matrix polynomials.
Encoding.
We encode and in interleaved manner, using the same basecode
which corresponds to the first basecode of WHIR. (We will discuss the setup of WHIR later.) The multilinears and are decomposed into -prefix components, which are then encoded non-systematically, using their univariate representation from . The resulting words
the interleaved Reed—Solomon code of interleaving depth , where has only non-zero components. (These are the prefix embeddings of the components of .) Thus committing to the lifted causes no overhead compared to , given that .
Lifting small commitments.
Whenever , we commit the univariate representation of over a projection of , the image of the multiplicative homomorphism
Since is an FFT domain, the map is -to- and onto. The committed word is from the smaller code
which has the same relative rate as . The lifted word
belongs to , since is of degree less than . By means of the projection we simulate without paying the price of committing over the larger domain.
The IOPP
Given the commitment of as interleaved word on , and proximity parameter , the target of the protocol is to show that is -close to a solution of our augmented constraint system, characterized by and and the inputs . That is, we want to prove that the committed function belongs to
where refers to the interleaved representation of as component polynomials of degree . The protocol is divided into three phases.
Phase 1.
The first phase is devoted to the second stage of the R1CS. The prover receives the stage-2 challenge from the verifier, and responds with the commitment of the lifted witness .
Phase 2.
The Spartan zero-check. We prove constraint satisfaction of the multilinears
for . For showing that
we run the sumcheck protocol on its inner product with , where is random. This reduces the above claim to evaluation claims
where are the verifier challenges drawn in the course of the sumcheck rounds.
Phase 3.
The third phase of the protocol is devoted to proving the linear claims (15), which is done by WHIR on the combined witness . For public input and challenge consistency, we further add the constraints
where are the challenges drawn in the second stage of the R1CS. The WHIR proof of proximity eventually reduces the linear claims on to claims on the combined matrix polynomials, which need to be checked by the verifier at full expense.
Let us give the formal description of our IOPP. For simplicity we assume that
Recall that .
Note that computing the matrix values (21) requires field operations, where is the maximum number of non-zero entries in the R1CS matrices. While these values can be proven via the SPARK polynomial commitment scheme for sparse multilinears [1], our main use case pivots for letting the verifier take the burden of matrix evaluation.
Soundness.
Without specifying the corresponding soundness notions, let us informally state the soundness guarantees of the protocol, for proximity parameters up to the Johnson radius. This means that as in the main relation (13) satisfies
where is the relative minimum distance of the base code . The corresponding list size bound is
the combinatorial Johnson bound, with . WHIR with rounds involves the further Reed—Solomon codes , with each round having its own proximity parameter , again assumed to be within the Johnson radius. (See Section 4.)
Let us roughly sketch the analysis behind Theorem 1. First of all, the entire protocol aims to prove a proximate solution of the lifted R1CS, specified by and the prefix-embedded second stage matrices . Unlike in certain univariate arithmetizations, see [3], lifting by prefix-embedding does not change the circuit logic — it only introduces variables that are never used. The lifted system has the same soundness error as the original one, i.e. , and from the point of view of , it is equivalent to ask for a second stage response satisfying the lifted system, or a smaller witness satisfying the original system.
This is the reason why Phase 1 is a randomized reduction from the main claim to that the extended prover transcript belongs to
(Here, the distance refers to the interleaved representation of and .) Note, that the proximate is not demanded of lifted form, in other words, it is not asked to stem from a -proximate of the non-lifted word on . (In fact, we do not rule out that is not as close to .) A usual pigeon-hole argument on the number of -proximates of bounds the soundness error of this reduction by
as stated in the theorem.
The same list size bound also scales the soundness errors of Phase 2, which is a reduction from to that the prover transcript , extended by its proposed sumcheck polynomials and the final claims , belongs to
The first term of the soundness error (23),
attributes the reduction from the domain identity to the inner product with . The other term,
is the soundness errors of each of the rounds of the sumcheck protocol, on the cubic zero-check expression.
Finally, and without going into details, Phase 3 is a reduction from to the final verifier relation , which trades the correlated agreement claim
for consistency checks on the WHIR sumcheck polynomials and the aggregated WHIR claim on the final polynomial revealed in plain. (The latter claim involves the evaluation claims on the matrix polynomials .) Its soundness error is , the overall error of WHIR with rounds on the five claims (19) and (20). We describe the protocol in the next section.
WHIR
For completeness we give a concise description of the WHIR [2] proof of proximity to constrained Reed—Solomon codes. Given a word defined on some set, , WHIR [2] is an interactive oracle proof of proximity to a univariate polynomial , the multivariate representation of which, say , satisfies a linear claim of the form
where is a publicly known (and often succinctly evaluable) multilinear. Similar to Basefold [4] and preceding works, e.g. [5, 6] [7, 8], the construction of WHIR rests on the connection between multilinear sumcheck specialization and the FRI-like folding of their univariate representations.
Setup
The mechanics of WHIR is in alignment with a specified sequence of univariate spaces
with . (These will correspond to the number of remaining variables after each round.) As before, we commit polynomials in interleaved representation, using the linear isomorphism
by FFT decomposition (5), for each . The decomposed polynomials, elements from
are then committed as words from the interleaved codes
with specified base codes of (typically increasing) minimum distance. Their evaluation domains are chosen as multiplicative cosets in , and are of size for some .
Each round further specifies for the number of samples in the consistency check between adjacent oracles, as described below.
The IOPP.
In the following is an FFT-friendly prime field, and a finite extension of it. The protocol starts with initial claim (24) and consists of rounds. Each round reduces a claim on the previous polynomial to a claim on a new polynomial.
In the aggregation step, the combined kernel is
and .
Soundness.
Every round of WHIR is a randomized reduction in the verifier randomnesses , , and , where
(Again, is the multilinear representation of , and the distance refers to the interleaved representation of .) We use somewhat lazy notation here, hiding the dependency of on the previous messages: The inner product kernel incorporates the specialized sumcheck claim on the previous oracle , its values at the in-domain queries, and the claimed value for at the single out-of-domain point . We note that in the case , since is revealed in plain, , the distance condition in (26) becomes vacuous.
The soundness analysis of the sumcheck phase, in parallel with the multilinear combinations of the interleaved components, is the most technically involved part. Its proof relies on (degree-) curve decodability of Reed—Solomon codes, yielding correlated agreement under the additional constraints imposed by the inner products. Without specifying the intermediate relations for each step of a WHIR round, we state its soundness properties as an (interactive oracle) reduction. For a detailed analysis we refer to [9, Section 6.4], which generalizes in a straight-forward manner to arbitrary inner product constraints.
Adding zero-knowledge
Randomizing .
Recall that in the end of Phase Step 2 of Protocol 1, the prover reveals the values , , , which are subject to
where are the random challenges collected over the rounds of the sumcheck. In this section we discuss two different strategies to prevent these values from leaking private witness data. Both extend the witness (either or ) by random values, and add trivial gates to assure their propagation through the R1CS matrices.
Randomization by extension field elements.
This is the canonical solution, where the openings over are randomized by random witnesses over . Note that it is sufficient to randomize and ; the value of is then uniquely determined by (27), as long as .
We allocate two private extension field variables in the second stage R1CS, and set their values to . Their gates are
located at arbitrary row indices . Then
with , , not depending on the two random witnesses , .
The bound in Lemma 1 is essentially tight, as multivariate Lagrangians have exactly a fraction of zeros in . In other words, local randomization of the witness propagates only to almost all points outside the witness domain.
However, the fraction of exceptional points is of order , and excluding them does not conflict our soundness goals.
For completeness we also cite an extension to multiple evaluation points:
The proof shows that the determinant is a non-zero multilinear in the coordinates of . We postpone it to the appendix.
Randomization by basefield elements.
It is tempting to believe that the univariate strategy from [12], which randomizes an extension field opening by extension-field-degree many basefield values, carries over to the multilinear world in a straight-forward manner. However, the best generic result we found is the following one, which has a way too large bound for the exceptional set.
The proof of the lemma relies on the well-known Moore determinant as a distinguisher for -linear independence. However, we require the property also over the field of rational functions in several variables, and hence state it in full generality.
For a proof of Lemma 4, we refer the reader to [13, Lemma 1.3.3].
It is hard to tell whether the Schwartz—Zippel bound in Lemma 3 is tight. A high polynomial degree is not a guarantee for a large set of zeros. We tried shortly with GPT-5.6, but did not achieve significant improvements. However, it proposed the following work around, which explicitly uses the multiplicative structure of the Lagrangians.
Blowing up soundness.
Instead of a single set of size , we choose several sets
in a very particular manner, so that their exceptional sets are statistically independent. (The latter will be possible because of the tensor structure of the Lagrangians.) Each is a set of points contained in a sub-cube of small dimension
with its free part touching the variables only, meaning that its points do not vary outside these coordinates. We further require that the free variables are disjoint between the sets, i.e.
whenever . The crux is that for each such set , we can drop its fixed variables in the proof of Lemma 3, as long as their -terms are not zero, since a common non-zero factor does not change -linear independence. The exceptional set for is only in the variables , independent of the other variables, and we arrive at the following statement.
In our application we would use , to make the second term in (30) of order . That is, we would require random witnesses over to randomize , and another random witnesses for . They can be placed at arbitrary positions in the witness, yet their constraints (as before of the form , or ) have to respect the positioning described above.
Zero-check masking
The zero-check, Phase Step 2 in Protocol 1, is turned into zero-knowledge by using the sumcheck randomization from Libra [14]. The prover commits to the univariate polynomials
where is the degree of the sumcheck (18). These polynomials define the sparse mask
which is overlaid with the hypercube sum (18). The prover claims the sum , the computation of which is almost for free via the succinct representation
Then both run the sumcheck on the combined claim
where is random, and is the target claim. (In our case is be the multivariate zero-check term, and .)
The sparse mask carries sufficient entropy to perfectly hide the witness in the sumcheck polynomials
for , as the following lemma shows.
For the sake of completeness, we give a proof the lemma.
The sumcheck reduces the claim (33) to that
where
for which the prover sends the values , , . The complementary term
can be proven in zero-knowledge by a separate protocol.
Let us quickly sketch the transcript simulator for the zero-check. The prover chooses arbitrary random polynomials and , with their image polynomials not satisfying the zero-check hypercube sum for random . Then it samples and and computes the hypercube sum
It then runs the sumcheck protocol on the valid claim (36). The (wrong) claim is chosen adaptively so that . For details, see reference pending.
Masked commitments.
To avoid witness information leakage from commitment openings, we use a slightly different approach than [15]. Instead of committing to a zero-knowledge encoding of witness, we overlay a witness polynomial with a sparse random mask without degree increase: Given witness and random , for some small , we commit to
which is again from . (This secures the witness for up to openings.) Obviously this does not bind the witness, unless we also commit to , which is required for ZO0K anyways (see Section 5.4).
For practical reasons, we jointly commit all masks required by the protocol in one shot.
We concatenate their coefficient vectors, append additional random coefficients, and encode the resulting vector as a single word from
Here the degree bound is at least larger than the total of all mask lengths, and can be chosen again a power of two, if this helps encoding performance. See Section 5.4 for details. (The choice of depends on the number of openings in the final proof of proximity, Protocol 3.)
The rationale behind masked commitments is the following. Adding the small mask in coefficient representation is a local modification of the witness, and the subsequent encoding of is as costly as that of . In contrast, even a tiny degree increase of the witness polynomial would lead to an overhead in the encoding step, where is the degree of .
WHIR in zero-knowledge
We describe an adaptation of ZO0K [15] to our technique for randomizing commitments as described in the previous section. The changes to the original protocol are minimal, and based on the fact that we can now also view masked polynomials as multilinears in the sumcheck claim. See Remark 6 for a one-to-one variant of [15].
The sumcheck rounds are randomized using the sparse Libra mask explained in Section 5.2, and information leakage via commitment openings is mitigated through the commitment masks as described above. In this multi-polynomial regime, ZO0K considers WHIR as a sumcheck prover, which gradually reduces composite claims of the form
involving a costly part, the inner product of a large (masked) witness polynomial with a public kernel , and a cheap part, certain public linear functionals , on the (small) masks committed by the prover so far:
The sparse sumcheck masks and the witness masks . The cheap part is not further reduced by the sumcheck logic; it is treated as constant function on the hypercube , which is passed through the rounds in a weighted form. The costly part is reduced in the usual sense, by folding. However, not before a fresh sumcheck mask enters the sum. In this manner, the number of masks in the claim (38) grow from round to round, but the costly part shrinks.
After the final round, the remaining claim, a linear functional in , , , is proven in zero-knowledge by an elementary proof of proximity, Protocol 3 below.
The required masks.
As pointed out in Section 5.3, we assume that the prover has committed beforehand to all the masks, as a single word from . Concretely, each sumcheck mask is committed as coefficient vector
from , and , appended by the coefficients of the commitment masks
from , where is taken from the subfield , assuming that the first witness polynomial is over . (In our application, our is the composite witness polynomial, both of which have their own basefield mask, and .) The number of coefficients is chosen according to how often the commitment of is queried in the course of WHIR:
the number of queries on in the final opening protocol, Protocol 3. The concatenated coefficient vectors (39) and (40) are encoded in zero-knowlege manner, by appending to the message another random coefficients
before the Reed—Solomon encoding. For reasons to be explained later, another random elements are appended to it. Overall, encodes the joint mask vector
parsed as coefficient vector of ,
as Reed—Solomon codeword over with evaluation domain .
Initialization.
The initial claim is on the unmasked polynomial , and of the form
where the inner product kernel is public. This is of the form (38) with
The latter can be easily computed as a linear functional on the coefficient vector : The multilinear representation of is non-zero only on the first points of the hypercube and thus
in the index notation of the hypercube.
Modifications of a WHIR round.
Let us describe the changes of round in Protocol 2, . At the beginning of the round, the prover has already committed to , , , satisfying the linear constraint
We think of the claim as for the quadratic expression
where is the sum of the mask functionals in (44).
Step 1: Masking phase.
Identical to the sumcheck randomization in Section 5.2. The prover takes the masks , it committed before running the protocol. They define the sumcheck mask
in as many variables as the sumcheck phase of the WHIR round consumes, . It claims
The verifier sends a random , which reduces (44) to the combined claim
Step 2: Sumcheck phase.
Both prover and verifier proceed with the sumcheck rounds on the combined claim (57). In the course of it, the prover provides the quadratic refinement polynomials the verifier has sent . After the last sumcheck round, the claim (46) is reduced to
which linear in and the masks, now including .
Step 3: Commit.
The prover takes , and commits to
as a word from . This masked commitment is required also in the last round . The new ensemble of polynomials, , and , , is subject to the linear constraint
which are of the form (38).
Step 4: Query phase.
In the query phase, the verifier asks the masked polynomial for the value at the out-of-domain sample and uses the values of the previous to constrain at the points . In terms of the new ensemble, these claims are the linear constraints
for , where are the univariate Lagrangians of degree . These constraints are again of the form (38).
Step 4: Aggregation of claims.
The verifier samples a random for combining the above claims (47), (48) and (49) on the new ensemble into a single claim of the form (38), with the following linear functionals:
As before, the inner product (52) on and the evaluation (54) on are inexpensive to compute.
The final opening protocol.
The final claim after round is of the form
It is proven via an independent proof of proximity to , and , satisfying the joint claim (55). For improving soundness, we constrain the prover to a single proximate mask by asking it for the value
at a random out-of-domain point , at commit time of . (See the full protocol description in Section A.) We use the same random point to prove invariance of the mask component under the Frobenius automorphism , which leaves invariant. The prover also provides the value of the component
at , i.e.
If , then with high probability , proving that (and ) is over .
Impact on soundness (tbc)
While all other measures from Section 5.1, Section 5.2, Section 5.3 do not affect soundness, except for introducing another round for combining
This is different for the ZO0K modification of WHIR, Section 5.4. The final opening proof, Protocol 3, is an independent proof of proximity for the final masked WHIR oracle and the joint commitment of all masks and blinders. As a consequence we are only able to bound the number of proximates pairs by
and likewise the additional multiplier is present in all other steps of the protocol.
where are the corresponding
The non-interactive STARK (tbc)
Merkle commitments (tbc)
The
Fiat—Shamir / BCS transform (tbc)
Example parameters (tbc)
Benchmarks (tbc)
Outlook v3 (tbc)
The complete protocol (tbc)
The complete protocol takes all the measures from Section 5 into account.
The first stage witness is
Appended by the zero-check masks laid out as basefield vectors.
Appended by basefield randomizers for at , as described in Section 5.1 (at any position)
Commitment masks as in Section 5.4: The masks and are committed as codeword in . Here for the combined witness poly splits as , and is over the basefield. (The other masks are over .)
The propagation constraints for the basefield randomizers are placed according to Lemma 5. No randomness appended to .
Correlated agreement (tbc)
Let be an arbitrary finite field,
be a polynomial (in the coordinates of an arbitrary basis) of total degree .
The theorem is direct consequence of line decodability [citation pending], also called collinearity of proximates property in [9]. Given a of proximates of the random linear combinations, one for each, then a notable fraction of it lies on a line.
Proofs: IOPP soundness (tbc)
Protocol 1
Let us outline the soundness properties of the protocol. In the following we write
for the Johnson list size bound on the number of proximates from at distance .
Phase Step 1:
The first phase is a reduction depending on the verifier challenges , where
where as before, the distance refers to the interleaved representations of the polynomials. The phase is a single-step reduction, and its soundness error is as follows.
Phase Step 2:
The second phase, the zero-check, reduces to , where
depends on the verifier challenges (and the preceding ). The soundness error of this reduction is
again scaled by the number of joint - and -proximates of and . The components correspond to the roundwise soundness errors of that phase. The first term is the probability of that is a zero of the multilinear extension of , , despite being non-trivial. The second term is for the rounds of the sumcheck. Each stands for the probability that the specialization of the sumcheck claim to the random is satisfied by a joint proximate , although not both claims for and hold.
Phase Step 3:
The third phase reduces to the final verifier relation of the protocol. This is
where , , , are the folding proposals committed by in the first rounds of WHIR, together with their values , , at the verifier DEEP queries , and is the final folding proposal revealed in plain.
The soundness error of this phase is that of joint WHIR,
and will be described in the following section.
Soundness ZO0K. (tbc)
For now, only few notes:
For simplicity, we assume the masks as given. (The full story is a bit more complicated as it needs to take into account the proximates of the masks.) Suppose that with notable probability in the prover is able to provide which close to a poly , so that
the new ensemble with and satisfies the -specialized claim (47),
the folding agrees on a density subset of with . (Which is caused by (48) and (49) satisfied with notable prob.)
Then, with the help of line decodability, all intermediate foldings are proximate to polys, the mv rep of which satisfy the specialized claim, up to that has a close poly , satisfying the combined claim (57).
The complete protocol (tbc)
Proofs: IOPP zero-knowledge (tbc)
ZO0K (tbc)
As elaborated in Section 5.2, the sumcheck polynomials of each round will be uniformly distributed over the relation of consistent polynomials, independent of the witness.
Further, by construction the queried values (in- and out of domain) are identically distributed field elements ( or if the first round oracles), independent of the witness.
The simulator can be constructed similar to the sumcheck simulator.
The complete protocol (tbc)
Alternatives to ZO0K
Proposal 1: VEIL
In its most simple variant, the followings steps need to be taken.
Securing the witness queries.
We need to randomize the witnesses and for the number of queries from . (No R1CS modification necessary). Recall we commit the witnesses in interleaved manner, using the FFT decomposition, and thus we need to randomize the witnesses properly, so that each component is affected equally: Thinking of as the not yet decomposed vector, add a contiguous interval of random values, where is the interleaving depth, at any place in the not used padding space of it. For likewise, but we may take into account that less than many components are non-zero.
Isolator polynomials.
In its most simple variant, the prover samples addionally to two random polynomials over the extension field ,
and commits them together with and , respectively. These `isolator polynomials’ are combined together with and in an additional (virtual) batching step before entering WHIR:
After we combined (19) and (20) into a single inner product claim on the combined witness poly, the prover reveals
on the combined isolator polynomial . with and replaced by and .
The verifier draws a further randomness to combine the two claims into a claim on the linear combination . This combination is not committed, the values of it are computed from those of and .
Run WHIR on the virtual linear combination .
The isolator polynomial entirely decouples the distribution of the future run of WHIR from the past (and thus the witnesses). WHIR is run entirely in non-zk mode, no changes here.
While the prove size increases only marginally (by one extension field element per query, likewise for ), prover cost does, since the prover has to hash the isolator polys. Moreover, we most likely hit memory bounds in this variant of VEIL.
A more prover friendly variant.
To mitigate the memory bounds, we insert isolator polynomials in the first round of WHIR instead.
The prover only samples a single
from the base code of and , and commits either together with . This is much less overhead (both compute and memory).
Modified first round of WHIR:
The sumcheck phase is randomized in the usual manner, using
These are committed separately, and in zk manner.
After specializing the sumcheck claim to , the prover reveals
and the claims for and are combined via another verifier randomness .
We now proceed with the virtual linear combination . (The query phase, the aggregation phase.)
The value is proven separately.
References
- [1] Srinath Setty. Spartan: Efficient and General-Purpose zkSNARKs without Trusted Setup. CRYPTO 2020. 2020.
- [2] Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, Eylon Yogev. WHIR: Reed–Solomon Proximity Testing with Super-Fast Verification. IACR preprint archive 2024/1586. 2024.
- [3] Ulrich Haböck, Adrian Hamelink, Andrew Milson. Lifted FRI: A Uniform Multi-domain Polynomial Commitment Scheme. 2025.
- [4] Hadas Zeilberger, Binyi Chen, Ben Fisch. BaseFold: Efficient Field-Agnostic Polynomial Commitment Schemes from Foldable Codes. IACR preprint archive 2023/1705. 2023.
- [5] Jonathan Bootle, Alessandro Chiesa, Yuncong Hu, Michele Orr`u. Gemini: Elastic SNARKs for Diverse Environments. EUROCRYPT 2022. 2022.
- [6] Binyi Chen, Benedikt Bünz, Dan Boneh, Zhenfei Zhang. Hyperplonk: PLONK with a Linear-Time Prover and High-Degree Costum Gates. IACR ePrint Archive 2020/1355. 2022.
- [7] Adrian Hamelink. Gemini. hackmd.io. 2022.
- [8] Tohru Kohrita, Patrick Towa. Zeromorph: Zero-Knowledge Multilinear-Evaluation Proofs from Homomorphic Univariate Commitments. IACR preprint archive 2023/917. 2023.
- [9] Ulrich Haböck. Basefold in the List Decoding Regime. IACR preprint archive 2024/1571. 2024.
- [10] Ulrich Haböck. A note on mutual correlated agreement for Reed-Solomon codes. Cryptology ePrint Archive, Paper 2025/2110. 2025.
- [11] Rohan Goyal, Venkatesan Guruswami. Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes. Cryptology ePrint Archive, Paper 2025/2054. 2025.
- [12] Ulrich Haböck, Al Kindi. A note on adding zero-knowledge to STARKs. Cryptology ePrint Archive, Paper 2024/1037. 2024.
- [13] David Goss. Basic Structures of Function Field Arithmetic. Springer. 1996.
- [14] Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, Dawn Song. Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation. Cryptology ePrint Archive, Paper 2019/317. 2019.
- [15] Alessandro Chiesa, Giacomo Fenzi, Guy Weissenberg. Zero-Knowledge IOPPs for Constrained Interleaved Codes. Cryptology ePrint Archive, Paper 2026/391. 2026.
- [16] Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf. Proximity Gaps for Reed-Solomon Codes. FOCS 2020. 2020.
- [17] Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, Shubhangi Saraf. On Proximity Gaps for Reed—Solomon Codes (Full Version). Cryptology ePrint Archive, Paper 2025/2055. 2025.