Cryptographic work, such as commitments, is often the primary performance bottleneck in SNARKs. This cost is particularly pronounced when committed values are random and necessarily large, as is the case with PLONKish systems.
In recent years, a lot of innovation have been aimed at making commitments as cheap as possible. Circle STARKs and Binius, in particular, are hash-based and sound1 over small fields, M31 and GF[2] respectively. This means lower prover overhead and better hardware compatibility.
However, it should be noted that FRI, the scheme behind these improvements, involves superlinear-time procedures like FFTs, which become a new bottleneck when applied directly to large computations without recursion.
In this note, I will explore GKR, an interactive proof (IP) scheme that addresses cryptographic overhead differently—by nearly avoiding commitments in the first place. My primary aim is to accurately summarize available materials and research. I am very open to changes and improvements, so if anything is unclear or incorrect, please leave comments here.
Background
GKR08 is a relatively old scheme that is based on multivariate polynomials and the sum-check protocol. A technology that was largely ignored in favor of simpler designs featuring univariate polynomials and divisibility check. Lately, however, it has seen renewed interest as projects like Jolt, Expander, and Modulus have demonstrated not only its viability but also impressive performance results.
Notably, modern GKR-based systems demonstrate prover complexity, which is linear in the size of the computation and with a constant factor overhead. For some applications, like matrix multiplication, the prover is less than 10x slower than a C++ program that simply evaluates the circuit, Tha13.
Furthermore, the aforementioned Binius is multivariate and it too involves sumcheck. Even StarkWare's Circle-Stark-based proof system called Stwo used GKR for LogUp lookups. I think it is safe to say that there is currently a broad consensus on the relevance of GKR.
Multilinear functions & MLEs
Multilinear polynomial is a multivariate polynomial that is linear in each variable, meaning it has degree at most one in each variable. When multilinear polynomials defined over the boolean domain, they have a much lower degree compared to the univariate case for the same domain size, T23a.
For any multilinear polynomial over the boolean domain (the boolean hypercube), polynomial operations such as addition, multiplication, and evaluation can be performed using only the evaluations of on the boolean hypercube. This eliminates the need to explicitly reconstruct the polynomial from its evaluations, so there's no FFTs.
Multilinear extension (MLE) is used to translate functions into polynomials over the boolean domain . Every function and vector mapping from has exactly one extension polynomial that is multilinear.
The multilinear extension is a multivariate analog of the low-degree extensions (LDE) commonly present in STARKs. One thinks of as an "extension" of , as "begins" with itself but includes a large number of additional entries. This distance-amplifying nature of MLE, combined with the Schwartz-Zippel lemma, forms the first basic building block of multivariate interactive proofs and GKR in particular.
Sumcheck
The Sumcheck protocol allows a prover to convince a verifier that the sum of a multivariate polynomial over boolean inputs is computed correctly.
Sumcheck does not require to know anything about the polynomial to which it is being applied. It is only until the final check in the protocol that, depending on the performance/succinctness tradeoff, can choose to either request the polynomial and evaluate it directly or perform an oracle query, i.e., outsource the evaluation to via a polynomial commitment scheme (PCS).
This is an interactive protocol: If is the number of variables in , then rounds are required to complete the protocol. By applying the Fiat-Shamir transform, we can render the sumcheck non-interactive.
This post doesn't aim to explain the general workings of sumcheck. For that, I recommend T23a (section 4.1) or this blog post.
GKR
In GKR, we work with layered circuits. A circuit is layered if it can be partitioned into layers such that every wire in the circuit is between adjacent layers, L23. The number of layers is the depth of the circuit, denoted as . Note that many of today's variations of GKR allow for more arbitrary topologies just as well.
The arithmetic circuit encodes logic with addition and multiplication gates to combine values on the incoming wires. Accordingly, functions and are gate selectors that together constitute the wiring predicate of layer .
We encode wire values on a boolean hypercube , creating multi-linear extensions for each layer . The output is in , and inputs will be encoded in .
Gate selectors depend only on the wiring pattern of the circuit, not on the values, so they can be evaluated by the verifier locally, XZZ19. Each gate at layer has two unique in-neighbors, namely and .
and for all (the case where gate is a multiplication gate is similar), T23a. Selector MLEs are sparse, with at most non-zero elements out of .
Note, the above definition does not reflect how selector MLEs are computed in practice, it is an effective method for illustrating the relationship between selectors and wire values.
The GKR prover starts with the output claim and iteratively applies the sumcheck protocol to reduce it from one layer to the next until it arrives at the input. The values on the layers are related thusly:
A few things to note here: First, notice how gate selectors are indexed—this aligns with the convention that selectors at layer determine how values from the next layer are combined. Notice also that the -layer sumcheck is over boolean inputs of size , i.e., the number of gates in the next layer.
Protocol
- sends the output vector and claims that .
- sends random and computes .
- and apply sumcheck on the relation between and (using for the summand)
- and reduce two claims and to a single random evaluation/combination .
- and apply sumcheck on the reduced relation , alternating steps 4-5 for more times.
- checks that is consistent with the inputs vector .
1. sends the output vector and claims that
First, the has to evaluate the circuit at the given input vector . This is why the prover is always at least linear to the size of the computation (circuit).
A common notation would be to write the output vector as a function mapping output gate labels to output values, of them in total. The gate labels are the vertices of the boolean hypercube; for example, for , the 4 output labels are , , , .
In practice, though, and work with polynomials, not functions, so they have to compute multilinear extension from the vector . Same goes for the inputs . However, since computation on MLEs can be performed over evaluations, in practice no additional computation, like interpolation/IFFT, is even required!
2. sends random and computes
picks a random challenge . Crucially, the soundness error of the sumcheck protocol is inversely proportional to the size of the field from which challenges are drawn (due to the Schwartz-Zippel lemma), T23a. That's why in practice for challenge values, we use an extension field where is the extension degree.
For example, say we opt for M31 as a base field whose order is elements. Then, the probability of soundness error in sumcheck for an -variate summand polynomial is , which is too large, certainly for the non-interactive setting. Instead, we choose challenges from QM31—the extension field of M31 with . Now, for any reasonable , the soundness error can be considered negligible.
This soundness characteristic is a notable drawback of sumcheck-based systems, as it requires the GKR prover to work over extension fields after the second round, thus making field work the main contributor to the proving overhead. In Part 2, I'll cover the recent work from Bagad et al describing an algorithm that reduces the number of extension field operations by multiple orders of magnitude.
Also note that cannot yet trust correctly to encode the outputs. The remainder of the protocol is devoted to confirming that the output claim is consistent with the rest of the circuit and its inputs.
3. and apply sumcheck on the relation between and
For the first layer, and run a sumcheck on Equation with , between and , with fixed to .
In the first round of sumcheck, uses to fix the variable . In the remaining two rounds, picks randomly to fix the variables and , respectively. At the end of the sumcheck, from 's point of view, the relation on the sum (Equation ) is reduced to a simple check that the summand evaluates to .
To compute , must compute and locally. Remember that these depend only on the circuit's wiring pattern, not on the values. Since is recursive, also asks for the and values and computes to complete the sumcheck protocol.
In this way, and reduce a claim about the output to two claims about values in layer 1. While and could recursively invoke two sumcheck protocols on and for the layers above, the number of claims and sumcheck protocols would grow exponentially in . XZZ19
4. and reduce two claims and to a single random evaluation/combination
To avoid an exponential blow-up in complexity, and apply a "rand-eval" reduction subroutine.
Here I will describe a method from CFS17 based on random linear combination (RLC), as it is more commonly found in modern implementations. Later, for completeness, I will also include the method based on line restriction, as described in the original paper GKR08.
Given two claims and , picks random weights and computes the RLC as
In the next step, would use as the claim for the -th layer sumcheck.
5. and apply sumcheck on the reduced relation , alternating steps 4-5 for more times
For the layers , and would execute the sumcheck protocol on Equation instead of Equation
At the end of each layer's sumcheck protocol, still receives two claims about , computes their random linear combination, and proceeds to the next layer above recursively until the input layer. XZZ19
6. checks that is consistent with the inputs vector
At the input layer , receives two claims and from . Recall that is claimed to be a multilinear extension of the input vector .
If knows all the inputs in clear, they can compute and evaluate it at and themselves.
Alternatively, if doesn't know all inputs and is instead given an input commitment for succinctness or zero-knowledge reasons, then queries the oracle for evaluations of at and .
Ultimately, outputs if the evaluated values are the same as the two claims; otherwise, they output . XZZ19
Analysis
Let be a layered circuit of depth with input variables, having gates in layer . Naturally, is the total number of gates in the circuit, i.e., the circuit size.
- Rounds: .
- time:
- work: for 1 output.
- Communication: field elements.
- Soundness error:
The GKR protocol consists of one execution of the sumcheck protocol per layer. Therefore, the total communication cost (proof size) is field elements. The accumulated soundness error is due to the Schwartz-Zippel lemma. T23a
The prover must first evaluate the circuit, which takes time . It must also compute and at each layer, which, if done trivially, induces logarithmic overhead . The resulting time for the prover is . XZZ19
The verifier's work is , where is the number of outputs of the circuit, denotes the optimal time to evaluate all and , and the term is due to the time needed to evaluate . XZZ19
Part 2 will cover modifications and techniques that result in prover.
Zero Knowledge
To make the sumcheck protocol zero-knowledge, the polynomial in the sumcheck protocol is masked by a random polynomial.
To prove the sumcheck for the summand polynomial from Equation and a claim in zero-knowledge, generates a random polynomial with the same variables and individual degrees as , commits to , and sends a claim picks a random number , and together with executes the sumcheck protocol on
In the last round of this sumcheck, opens the commitment to at , and the verifier computes by subtracting from the last message, and compares it with 's original claim.
Chiesa et al. showed that as long as the commitment and opening of are zero-knowledge, the protocol is zero-knowledge.
Original method to reduce two claims to one
Let be a multilinear polynomial over with variables. The following is the description of a simple one-round subroutine from GKR08 with communication cost that reduces the evaluation of and to the evaluation of for a single point .
interpolates a unique line passing through and , such that and . The line can be formally defined as using the point-slope form. The points and are tuples with elements for a -variate polynomial .
By substituting and into , we get the tuple defined by linear polynomials over . sends a univariate polynomial of degree at most that is claimed to be , the restriction of to the unique line .
interprets and as 's claims for the values of and . also picks a random point , sets , and interprets as 's claim for the value of . See the picture and an example from T23a (Section 4.5.2).
References
- [Tha13] Justin Thaler (2013). "Time-Optimal Interactive Proofs for Circuit Evaluation"
- [T23a] Justin Thaler (2023). "Proofs, Arguments, and Zero-Knowledge". See also lecture notes.
- [L23] Jieyi Long (2023). "Efficient Arguments and Proofs for Batch Arithmetic Circuit Satisfiability"
- [XZZ+19]: Tiancheng Xie et al. (2019). "Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation"
- [G24] Ariel Gabizon (2024). zkWarsaw talk "The GKR method".
- statistically sound, as in likelihood of error is small, based on statistical measures according to field size and other factors. Also note that Circle STARKs and Binius must use extension fields in certain parts of computation, e.g. M31^4 for Circle-FFT.↩