The following is an attempt to explain how modern hash-based multilinear ZK-SNARKs work from the ground up, for someone familiar only with basic discrete math.11Systems built on univariate polynomials like STARKs and Plonky2 are pretty different under the hood, and will not be covered here. We’ll build up a set of tools one at a time, each with some rough motivation for why you might want it, and then piece them all together into a working proof system at the end. The particular system we’ll construct is optimized for understanding rather than performance, but the core ideas should still carry over to fancier schemes that swap out some of the tools for faster/smaller alternatives.22E.g. WHIR for commitments, Lasso for lookups, ZOOK for zero-knowledge, etc.
If you don’t know what a ZK-SNARK is, quickly read this first, I won’t do much explaining of what they are and why they’re useful here. For a much more complete treatment, see Justin Thaler’s Proofs, Arguments, and Zero-Knowledge.
§1.Finite fields
Everything in this document happens in a finite field. Informally, a field is a set of numbers where we can add, subtract, multiply and divide (by anything except zero), and all the usual rules of arithmetic hold, e.g. .
The fields we’ll use are almost all large prime fields,33Except for extension fields, which we’ll cover in Section 2.1.1. which are basically just the integers modulo some massive prime :
For a prime , the field is the integers , with addition, subtraction and multiplication all done modulo .
For example, in : , , .
Note: Division works by multiplying by an inverse, e.g. in since , is the inverse of and thus and , etc. Negatives work by wrapping around, e.g. and in .
Why finite? Because it means every value fits in a fixed number of bits while arithmetic is still exact. With e.g. rationals our numbers can explode in size over the rounds of our proof, and with floats we get rounding errors and a bunch of other nastiness.44Floats technically aren’t a field at all, as floating point addition isn’t associative.
Why a prime? The integers mod are only a field when is prime. Otherwise we end up with non-zero numbers without inverses, which breaks division. Much of what we’ll build relies on the Schwartz-Zippel lemma (more on this soon!), which only applies over fields. There are more exotic finite fields too, but integers mod are simple and generally performant on commodity CPUs and GPUs.
Why large? As we’ll see, almost every way a cheating prover can get lucky happens with probability proportional to , where is the number of elements in the field (e.g. ). Thus we want to be really big, typically at least .
The one issue with doing everything in a finite field is that we have to be careful to make sure our inputs and computed values don’t wrap around , but we won’t worry about that here.
§2.Tables & Extensions
We’ll define a table to be a list of cells, all of which are values from the same finite field . Tables are indexed by bits, , where is the low bit, so a table is a function .55If you’re unfamiliar with some of this notation: is the set of all lists of bits, i.e. with copies, so it has elements, one per cell. For example: .Likewise, is the set of all lists of field elements. The arrow in just means takes an input from and returns a value in .Fun fact: is often called the boolean hypercube, since its points are the corners of an -dimensional cube.
Consider the table , where . We can read it as a function of its input bits (remembering that is the low bit), i.e.:
Note: A table is only defined for 0/1 inputs, i.e. , not for arbitrary field elements.
Consider the table , i.e. . Observe that we can construct a polynomial such that for , by simply linearly interpolating between the two values, i.e.:
Let . Again, we can construct via linear interpolation of its cells:
Now return to the table . We can construct such that for as an interpolation between and in .
is a multilinear polynomial, as it has degree at most in each variable . We can generalize this to arbitrary size tables.
For a table of any , we can construct , a polynomial with degree at most one in each variable (multilinear), which equals the table’s cell at every 0/1 point.
If two multilinear polynomials in variables agree on every 0/1 input, they are the same polynomial.
Multilinear extensions of tables are extremely useful, because they turn tables into polynomials, and we can do a lot of cool things with polynomials.
§2.1.Identity testing
Say we want to check whether two tables are equal.
Turns out, simply drawing a random “challenge” and evaluating whether is enough to say with high confidence whether they are equal. If , this will pass 100% of the time. If they are different, it will pass with probability at most .
Proof: By Corollary 2.0.1, if , , thus is a non-zero multilinear polynomial. The test passes iff that difference evaluates to at .
By the Schwartz-Zippel lemma, a non-zero polynomial in variables of total degree77The total degree of a polynomial is the largest sum of exponents in one term. For example, has total degree 2. at most is zero at a uniformly random point with probability at most .
is multilinear, so it has total degree at most .88Its largest possible term is . Thus, the test passes with probability at most .
This is great news because, as discussed in Section 1, the field we sample from is very large, typically at least . Even for a table with more than a trillion entries (e.g. cells), the chance of holding for random when is at most .
§2.1.1.Extension fields
Sometimes, even if our field is quite large (e.g. ), is too weak of a bound to be secure, for example if this check is one step amongst many and the errors are additive. However, using a larger field for a table is not free. A larger field can require using multiple machine words to store each cell, which can drastically decrease efficiency. Thus, we often store tables with cells in a prime field such that values from that field fit in a single machine word, and then draw challenges from a larger extension field99A larger field that contains . See Finite field on Wikipedia for how these are built in general. . The Schwartz-Zippel lemma applies unchanged, because a table with cells in is also a table with cells in .
Note: Despite the similar name, extension fields have nothing to do with a table’s multilinear extension. They’re completely unrelated concepts, don’t mix them up!
For example, a popular base field is the Goldilocks field, with , whose elements fit in a single 64-bit word. Its quadratic extension consists of elements with , where is a new symbol satisfying .1010This works because has no square root in , much like how the complex numbers extend the reals with an satisfying , which has no real square root. Arithmetic works just like with complex numbers, except becomes , e.g. . sits inside as the elements with .
This squares the field size to , which matters most for bounds with a big numerator. In Section 5 we’ll see a soundness bound of , which for over the Goldilocks field is only , well within reach of a cheating prover who can retry many times.1111Which is possible once the protocol is made non-interactive. See Section 9. Over the extension , it’s .
We want to use extension fields sparingly though, as each element takes two machine words to store, and multiplying two of them takes three or four base field multiplications. That’s why the computation’s own tables stay in the base field , and only challenges and values derived from them live in the extension.1212Note: Multiplying a base field element by an extension field element (e.g. a challenge) takes only two base field multiplications, since .
§2.2.Folding
We said we could compare tables by evaluating their extensions at a random , but how should we actually compute given some ? We could work out all coefficients of , then plug into every term, but there’s a faster way: folding.
For example, folding by replaces each adjacent pair of cells (those differing only in ) with a linear interpolation between them at :
is an ordinary table with cells, indexed by the single bit . Its cells are values of with fixed to :
Folding by leaves a table with a single cell:
and indeed .
Folding a table by some produces a table with cells:
Cell by cell, each adjacent pair becomes .
Applying this repeatedly, folding by , then , and so on through leaves a single cell equal to . Each fold halves the table, so this takes fewer than multiplications in total.1414If the cells are in and the challenges are drawn from an extension field , the cells become elements of after the first fold.
Folding gives us both a way to efficiently evaluate a table’s multilinear extension at a specific point and a way to turn a claim about a large table into a claim about a table half its size, which will come in handy later.
§2.3.Extensions as weighted sums
As we just saw, folding by , then , and so on through leaves a single cell equal to . Each fold only ever combines cells by scaling them by or and adding them up, so that final cell (and thus as well) is just a weighted sum of ‘s original cells! Each cell’s weight is the product of the factors it picked up, one per fold,1515 if its -th bit is and if it is and these weights form a table of their own that we’ll call the table:
For a point , the table has cells:
Putting this together:
For any table and any , the value is equal to the sum of ‘s cells, each weighted by the matching cell of , i.e.:
This property, that evaluating a table’s multilinear extension can be expressed as a weighted sum over the underlying table, will be useful later.
§3.Commitments
Our end goal is a ZK-SNARK. We’ll get to the ZK (zero-knowledge) part later, so for now let’s focus on the SNARK, short for Succinct Non-Interactive Argument of Knowledge1616It’s an argument rather than a proof because we assume a prover can’t break cryptography (e.g. find hash collisions). I’ll be using these terms interchangeably here, sorry!: a proof system that lets one person (the prover) prove1717Well, more like convince with overwhelming probability. We use the word prove here but technically a false claim can still get accepted, just with some very very tiny (like a 1 in ) chance. to another person (the verifier) that a statement is true,1818Formally, it must be complete (an honest prover always convinces the verifier) and sound (a cheating prover almost never does). with a proof that is small and fast to check, even if the statement is about a very large computation.1919We’ll cover the non-interactive part in Section 9, and ignore it for now.
When constructing SNARKs, we often end up wanting a system that lets a prover commit to a table, such that once committed, the prover cannot change any of its cells, and a verifier can later query/open parts of it and trust that the answers are faithful to the same table the prover committed to. This property is often called binding: once the prover has committed to some table , it’s stuck with it, and can’t open the commitment to values from any other table.
This is useful because we often want the verifier to make some kind of random challenge and test something about a table with it. But that only works if the prover can’t change its table on the fly after seeing the challenge. Committing to the table first ensures that.
We ideally want our commitments to be succinct, meaning the commitment and each opening proof are much smaller than the table and checking an opening is much cheaper than reading the whole table.
Merkle trees are one such succinct commitment scheme. The prover just sends a single hash (the root hash of the tree) to the verifier, then can later open the value of a specific cell by providing its value along with some sibling hashes, which the verifier can easily use to check the claimed cell value is faithful. Each opening costs only a logarithmic number of hashes, so they work great if we only need to access a small number of specific cells.
For our use cases, we’ll want a commitment scheme that lets us efficiently open a table’s multilinear extension at a specific point, rather than specific cells. Merkle trees on their own can’t help us: the evaluation of a multilinear extension is a weighted sum of the whole table, so with a Merkle tree we’d have to open every single cell, which is not efficient/practical. Polynomial commitment schemes solve exactly this. We’ll discuss how to actually build them later. For now, we’ll treat them as a black box with two steps:
- Commit. The prover sends a short commitment to a table , e.g. a single hash.2020When we say the prover commits to a table, we mean it sends a commitment.
- Open. Later, if the prover wishes to show , it can send along with a short proof that , which the verifier checks against the commitment.
Commitments/openings are succinct but not free by any means, so the fewer tables we need to commit to and the fewer openings we have to perform, the better.
§4.Sum-check
Say we, the prover, have some table and we want to convince some verifier that . That is, if has cells and :
The sum-check protocol2121Lund, Fortnow, Karloff and Nisan (1992) is an interactive protocol that lets the verifier check a claim like (4.1) using only rounds of short back-and-forth messages and a single evaluation of at a random point,2222For example, if the prover has committed to , by opening the commitment at that point. without ever reading the whole table.
The protocol works in rounds, and each round shrinks the claim from a table to that table folded in half. The key tool is a polynomial the prover sends each round, which we’ll call the round polynomial. For the current table , it is simply the sum of the cells of folded by , as a function of :
Two things make this polynomial useful. First, folding by or just picks out half of the table, so together they cover every cell:
which is our original claim (4.1). Second, is just a line: each term has degree at most in , since is multilinear, and a sum of lines is a line. So the prover can send it as just two numbers.
The prover and verifier start with the claim “ sums to .” Each round turns a claim about a table into a claim about that table folded in half. In round :
- The prover sends the round polynomial of the current table.2323Since is a line, this is just two field elements, e.g. its two coefficients.
- The verifier checks that equals the current claimed sum, and rejects if not.
- The verifier picks a random and sends it to the prover.
- The new claim is that the current table folded by sums to . The prover folds its table by .
After rounds, the table has been folded down to a single cell, which should equal . The final claim is that this one cell equals , and the verifier checks it with its single evaluation of .
If a prover wants to claim an incorrect sum, how likely is it the verifier fails to catch them? As it turns out, just as unlikely as passing the identity test from earlier, at most .
Proof: Imagine the prover is lying about the sum. In round 1, it has to send a round polynomial whose values at and add up to its claimed sum, or the verifier’s check fails immediately. The true round polynomial adds up to the true sum, so the prover is forced to send a different one.2424True = what an honest prover would send for folded by the challenges so far.
Both are lines, and two different lines cross at one point or not at all. So at some random from the verifier, the prover’s line and the true line almost certainly disagree there. Thus the new claim is still a lie, just about a table half the size.
With high probability, this will keep happening round after round. The prover can’t make the lie go away, and just keeps passing it down. After rounds, the lie is about a single cell, , which the verifier can check directly.
The only way for the prover to get away with a lie is if some lands exactly where the prover’s line crosses the true one, which happens with probability at most in each round. So, across all rounds, the chance a lying prover gets a lucky at least once is at most .2525This follows from the union bound.
§4.1.Sum-check over elementwise products
In practice, the table we want to make a sum claim about is often2626We’ll discuss more soon, but e.g. summing a table against a mask, evaluating a multilinear extension at a point, and multiplying matrices all take this form. an elementwise product of other tables. For two tables and of the same size, the claim looks like:
You might assume we could just multiply the tables cell by cell into a single table and run sum-check on that. But the final check would need at a point, and since isn’t committed, there’s no easy way to prove its value.2727Couldn’t the verifier compute it as , you ask? No, that can have degree in each variable, so it isn’t , which is multilinear by definition.
So instead, we fold both and by the same value each round, making the round polynomial:
The one real difference from the original sum-check protocol is that is no longer a line. Each term is a product of two lines in , so it has degree at most , and so does their sum. A quadratic is determined by three points, so each round the prover sends three values, e.g. , and , instead of two.
The protocol is otherwise unchanged: the verifier checks against the current claim, picks a random , and the new claim is .2828To compute , the verifier recovers from its three values, e.g. by Lagrange interpolation. At the end, the verifier just needs and ,2929Which it can get by e.g. opening their commitments. and checks that their product equals .
Nothing here is special to two tables. For a product of tables, each round polynomial has degree at most and the prover sends values per round.
The bound on soundness is the same as before, just multiplied by , so . The argument is nearly identical to Theorem 4.0.1. The only change is that two different polynomials of degree at most agree on at most points, rather than one.3030Their difference is a non-zero polynomial of degree at most , which has at most roots. So each round, a random lets the lie escape with probability at most , and across rounds, at most .
§4.2.Sum-check over elementwise polynomials
A product is just one way to combine tables cell by cell. For example, given tables and , we might want to prove a claim like this:
Each term of this sum is a polynomial in and : it only involves additions, subtractions and multiplications of the two tables’ values at the same cell, and constants. In general, we can take any polynomial in variables and any tables of the same size, and prove a claim about:
The protocol is mostly unchanged from before, with the exception of the degree of the round polynomial. Each folded cell is a line in , so if has total degree , each term of has degree at most , and so does .3131Recall that the total degree is the largest sum of exponents in one term. For example, has total degree , from the term . The prover sends values per round, and at the end, the verifier needs , applies to them, and checks the result against .
Soundness bounds are the same as sum-check over elementwise products of tables, , where is the total degree of . The proof again mirrors Theorem 4.0.1.
§4.3.Proving elementwise polynomial relations
So far, we’ve used sum-check to prove, well, the sums of tables.3232Or of any polynomial combining several tables cell by cell, like . But a sum loses information, since many different tables have the same sum. Often we want to prove something stronger, that every cell of one table is the result of applying some operation to the matching cells of other tables. For example, say the prover holds tables and , and claims that a third table is their elementwise product:
We’ll use our identity test from earlier, where we take a random point and check that equals . The trouble is, how do we compute ? As mentioned in Section 4.1, the naive guess does not work: .27
So what do we do? Recall from Theorem 2.3.1 that we can rewrite any extension as a weighted sum over the table:
Now a claim about can be rewritten as a claim about the sum of a product of three tables, and we can use the sum-check protocol to prove such a claim!3333If is a committed table, this is often called a zero-check and written as e.g. . Many systems speed it up with optimizations from Gruen (2024).
Thus, to prove (4.3.1), we start from a claim at a random point . If is the final output of the computation, the verifier picks and can compute itself (assuming is some public table), otherwise, this claim was left behind by proving a later operation that used . Then, we run rounds of sum-check to reduce it down to a claim about the product of , and at some random .
At this point, the verifier can compute itself, since its product formula takes only work.3434Since the product formula from Definition 2.3.1 is multilinear in and matches the table at every 0/1 point, by Theorem 2.0.1 it is , and we can just plug into it. The prover then makes claims for the value of and , and the verifier checks that the final equation holds given them.
What we’ve built is a reduction: if the claim about is false, then with high probability at least one of the new claims about or is false too.3535Protocols like this, which use random challenges to turn one claim about committed tables into new ones, are called interactive oracle reductions (IORs).
This is a really big deal! We started with a claim about the output at a random point, and ended with claims about the inputs and at a random point. Those claims can get checked in one of two ways:
- If the table is committed or public, the prover can just open the commitment for it at , or the verifier can compute it directly.3636See Section 3 if you need a refresher on the mechanism here.
- Otherwise, the table is the output of some earlier operation, and we can repeat this process for that operation, reducing the claim to new ones about its inputs.3737Assuming the operation is polynomial. Non-polynomial operations like ReLU can’t be reduced to their inputs in this way. We’ll explain how to deal with them in Section 5.1.
We can repeat this as many times as we want, working backwards until every claim lands on a committed or public table. This means the verifier can check an entire chain of operations without ever seeing the intermediate tables, and the prover only needs to commit the ones that can’t be reduced further!
With this technique, a cheating prover gets through with probability at most from the identity test, plus from the sum-check, since its round polynomials have degree at most . By the union bound, this is at most overall.
To be clear, nothing here is special to products. To prove for any polynomial of total degree , we just sum-check instead, which spits out claims, one for each . The round polynomials then have degree at most , so the bound becomes .
§4.4.Proving matmuls
The elementwise relations we learned to prove so far with sum-check only combine values across tables at the same cell, but matrix multiplication is different. With a matmul, each cell of the output depends on a whole row of one input and a whole column of the other, so we can’t prove it using the technique from Section 4.3 out of the box.
An matrix is just a table with cells.3838Assume , and are powers of two. If they aren’t, we can always just pad them with zeros. Its index bits split into two groups: bits for the row, and bits for the column.
We’ll write for the cell in row and column , where and are each a group of bits, and for its multilinear extension.
Say the prover holds an matrix and a matrix , and claims that :
How do we prove this? We’ll obviously start with an identity test. As we proved earlier, to check it’s enough to check their multilinear extensions agree at a random point , i.e.:
But how do we compute ? This time, unlike the elementwise case in Section 4.1, the naive guess actually works:3939In the elementwise case, and both have the same variables in their terms, so their product has degree in each. In this case though, the row variables appear only in and the column variables only in , and just gets summed away, so the RHS of (4.4.3) is still multilinear.
Note: , as a function of , is the table we get by folding the row bits of by . Likewise, is the table we get by folding the column bits of by .4040Folding works on any group of bits, not just the lowest. We just pair up cells that differ only in the bit being folded. Both folded tables have cells, indexed by the same bits.
Thus claim (4.4.2) becomes:
which is provable via sum-check over the product of the two folded tables, and after its rounds, reduces down to claims about the inputs and each at a single point.4141As in the elementwise relation case, the value of is itself just a claim, either left behind by a later operation or checked directly at the end of the chain.
Again, just like with elementwise relations, we started with a claim about the output at a random point, and ended with claims about the inputs and at a random point. So if e.g. was itself computed by an earlier matrix product, we can use the claim about as the starting point for proving that product, and so on.
A cheating prover gets through only if it gets lucky on the identity test, with probability at most , or on the sum-check, with probability at most .4242Since for the identity test and the sum-check runs for rounds with round polynomials of degree . By the union bound, the chance of either happening is at most .
This is also fairly efficient for the prover! Besides actually doing the matmul, the only real extra work the prover must do is folding and , which takes about field multiplications4343And about twice as many additions., plus a sum-check over tables of size .
§5.Lookups
Say we have a table with cells, and a fixed public table with cells. By fixed public table, we mean is fixed before the proof starts and doesn’t depend on the computation.4444For example, with , (5.1) says every cell of is a prime less than 10. Typically is far bigger than , so most entries of are used many times, and some not at all. Can we convince a verifier who does not hold that every value of is in ? i.e.:
Proving this is non-obvious. We don’t have any techniques so far that let us prove things about sets in this way. The trick is to turn (5.1) into a statement we do know how to prove.4545There are several ways to do this; lookup schemes are a very active area of research! We’ll use LogUp, a scheme from 2022, but there are many other designs, e.g. Plookup and Lasso. One such method is called LogUp, which turns it into a statement about sums, which fits nicely with the sum-check tooling we’ve built up.
For each entry of , let count how many cells of equal .4646If contains a value more than once, it doesn’t matter which of them we use for counting, only the total matters. Then if every cell of appears in , the following holds for any :
Why does this work? Well, the left-hand side has one term per cell of , and if we group cells of the same value together, a value that appears times in contributes , which is exactly the term the right-hand side has for . If some value in is missing from , the left-hand side has a term and the right-hand side doesn’t, so no choice of makes them equal.4747Thus if any works, we’re good.
To prove this equality to the verifier, we can first commit to , then have the verifier provide us with some random for an identity test:
This is great, but (5.3) still isn’t something we can sum-check directly, since its terms are fractions rather than polynomials in the cells. So the prover computes the fractions itself, as two new tables:
and proves they’re correct using an identity test + sum-check with elementwise relations that are polynomial,4848The right-hand side of (5.4) is because the table of all ones has the constant as its multilinear extension. i.e.:
Unlike the intermediate tables of a computation, claims about , and can’t be carried backwards to earlier tables, since they’re whatever the prover says they are. So the prover must commit to them, and claims about them are checked via openings on their commitments. With those tables established, (5.3) becomes as simple as:
Whew okay, that was a lot of steps. To summarize:
- The prover commits to .
- The verifier sends a random .
- The prover commits to and .
- The prover proves (5.6), by claiming a value for both sums and running sum-check on each.
- The prover proves for every , via an identity test at a random , followed by sum-check on (5.4).
- The prover proves for every the same way, with an identity test at a random and sum-check on (5.5).
A cheating prover gets through only if it gets a lucky , which has probability at most ,4949Multiplying out the denominators in (5.2) gives a non-zero polynomial of degree at most , and would have to land on one of its roots. If lands directly on some , then has no inverse, so no can satisfy anyway. or if it gets lucky on one of the identity tests or sum-checks, which adds at most , and is marginal in comparison.5050The side adds , from the identity test, its sum-check over a product of three tables, and the sum-check on . The side is the same with in place of . Note that because of the in the numerator, this is a much weaker bound than we’ve seen before, so we’ll almost certainly have to draw from an extension field as described in Section 2.1.1.
Isn’t building and committing two new tables expensive? Somewhat, and it’s the main cost of LogUp. has as many cells as , so the prover pays for field inversions5151This can be done efficiently in bulk, see Montgomery’s trick. plus a commitment to a table of that size. And since is drawn from an extension field, the cells of are extension field elements, which makes that commitment more expensive still. is usually much cheaper, at most inversions and cells, and is typically far smaller than .
Note: In practice, a refinement called LogUp-GKR that removes the need to commit to and is often used instead of plain LogUp, but we won’t cover it here to keep things simple.
§5.1.Proving elementwise non-polynomial relations
Now say we want to prove that some table of size is just a version of some table that’s had some non-polynomial operation , e.g. a ReLU, applied elementwise:
Assume the cells of only take values in some small set , for example all 16-bit integers. 
We can make a table that matches inputs/outputs of , and look up pairs in this table to prove (5.1.1).
Let have rows and two columns, every possible input alongside . Our claim is thus that every pair is a row of . Each input appears in exactly one row, so this forces .
We don’t have any machinery to prove this kind of paired lookup, so we’ll need to reduce this to a standard single-value lookup like in (5.1). We can do this like so: have the verifier send a random , and use it to squash each pair into a single value, forming two final tables:
Note that unlike and in LogUp, the prover won’t have to commit or send these two tables to the verifier. It just computes them for itself, and as we’ll see any claims about or just end up reducing to claims about , and the public table .
We then prove every cell of appears in . A pair that isn’t a row of only survives squashing if is unlucky. For each row , the pair squashes onto that row’s value only if . The LHS is a non-zero polynomial of degree at most in , and thus a random makes it zero with probability at most .5252This is via Schwartz-Zippel again, as in Theorem 2.1.1. By the union bound over all rows, a bad pair survives with probability at most .5353If is big, e.g. if covers all 16-bit integers, this bound is fairly weak, so we likely need to draw from an extension field for security.
Like for any lookup, this ends with a claim about at some random point , and one about at another point . The claim about is easy to check, as is public and the verifier can compute it itself. For , since is linear in and , the naive guess works this time: . Thus the prover sends and , and the verifier checks they combine to the claim. That leaves two claims to check.
The claim about can be carried backwards as usual, if is the result of some earlier operation. For , carrying it backwards would mean using to turn it into a claim about , which is exactly what we can’t do, since isn’t a polynomial. So instead, the prover must commit to before the verifier sends , and the claim about is checked by opening it.5454If were committed after , the prover could pick incorrect values for that still squash onto valid rows of .
Overall, a cheating prover gets through with probability at most from squashing, plus the lookup’s own bound, for in total.5555Note: This doesn’t count the openings of the committed tables, which depend on the commitment scheme! Generally the term dominates, so looking up pairs costs barely more than looking up single values.
§6.Merging claims
Often we end up with several claims about the same table. For example, if a table is the input to two different operations, proving each one leaves behind its own claim about at a different point. If is a committed table, we’d need to do an opening for each claim, and if it’s an intermediate table, we’d have to carry each claim back through whatever operations produced separately. Both of these are expensive, particularly openings, so we’d like to squash them all into one claim if possible.
Say we have claims for several points . By Theorem 2.3.1, each one is just a weighted sum of ‘s cells, . So, if we have the verifier pick a random weight for each claim , we can rewrite a check of all of them like so:
If every claim holds, the weighted sum is obviously zero. The “w.h.p.” is about the other direction: if any claim is false, then , so the second line’s left-hand side is a non-zero polynomial of degree in the ‘s, and by Schwartz-Zippel5656Go back to Theorem 2.1.1 if you need a refresher!, it’s zero with probability at most .5757Note: It’s important that the ‘s are only drawn once every claim is fixed, otherwise a cheating prover could choose its lies so that they cancel out in the weighted sum.
The last line is a sum over the elementwise product of two tables, and , so we can prove it with sum-check (Section 4.1). At the end, the verifier needs and at a single random point . It can compute itself, and the one claim left about gets checked like any other (by opening if it’s committed, or by reducing it further via sum-check if possible). So no matter how many claims we make about a table, we only ever have to check one!
Note: Nothing here needs the weights to be tables. Any pile of claims of the form , each a public-weighted sum of the same table, merges into one in exactly the same way.5858This will be helpful later (Section 8.2.1), when making our proofs zero-knowledge leaves us with a big pile of exactly these kinds of claims.
This does come with a slight soundness cost, though. A cheating prover now also gets through if it gets lucky with the ‘s, with probability at most , or on the sum-check, with probability at most , so at most extra overall.
§7.Polynomial commitments
Since Section 3, we’ve been waving our hands about how we’ll actually implement commitments and openings for our tables.5959Everything we’ve built so far, where we treat commitments as a black box, is what’s called a polynomial IOP (a type of interactive oracle proof), and pairing one with a polynomial commitment scheme turns it into a real SNARK. Let’s open the black box and discuss how to implement a polynomial commitment scheme (PCS), specifically Ligero-PC.6060There are a ton of polynomial commitment schemes, just like lookup schemes, such as KZG and Brakedown-PC. Some, like KZG, are built on elliptic curve pairings (instead of hashes), which give much smaller proofs but need a trusted setup and aren’t quantum-resistant. Ligero-PC gets its name from the Ligero paper, where the idea first appeared.
We’ll need to introduce two tools/tricks before describing the scheme: a way to compute from a single weighted sum of a table ‘s rows, and Reed-Solomon codes.
§7.1.Evaluating extensions from a weighted sum of rows
Say we have a table with cells. No matter its “true” structure (whether it represents a matrix or a flat table or a tensor, etc), we can lay it out as a matrix with columns and rows, such that . We’ll let the low bits of a cell’s index pick its column, and the high bits pick its row, so each row is a run of consecutive cells.6161To keep the low bits first like in our table notation, we’ll write with the column index before the row index. For example, would become:
If we want to evaluate at some point , we can equivalently think about this as evaluating at the point split by column/row into and , i.e.:
Recall Theorem 2.3.1, which states we can write as a weighted sum of ‘s cells:
Generalizing this to matrices, we notice can be split into a product of column and row parts:
Thus by plugging this into Theorem 2.3.1 for , and pulling out the column part of the inner sum we can write:
The inner sum doesn’t depend on , so let’s give it a name: . It’s a table of cells, one per column, so we can think of it as a single row. Each of its cells is a weighted sum down the matching column of , so as a whole, is a weighted sum of all the rows of , with weights .6262Notice that this is just with its row bits folded by !
The outer sum is thus a weighted sum of with weights , which by Theorem 2.3.1 is its extension at :
Why did we just do all that? Well, now, if a prover just sends , the verifier can finish evaluating itself by folding , which is cheap since only has cells, rather than ‘s full cells. For example, take from earlier and , so and . The row weights are , so:
and folding by gives , which matches from before.
The problem is, of course, that nothing stops the prover from sending a fake which folds to whatever it wants, e.g. if it wants to claim , it can just send , which folds to . The verifier needs some way to check is really the correct weighted sum of the committed rows.
One naive idea would be to commit a Merkle tree of ‘s columns, and then have the verifier randomly check some entries of by opening the matching columns of and ensuring . The problem is that a cheating prover only needs to fake one entry of to change what it folds to (e.g. differs from only in its first cell), so each random column only catches the lie with probability .
If only there was a way to spread any lie in across most of the columns… oh, that’s exactly what error-correcting codes do! We’ll use Reed-Solomon, though other linear codes can work too.
§7.2.Reed-Solomon codes
Fix a positive “rate” such that is an integer, e.g. .
To encode a row6464We say “row” since that’s how we’ll use RS codes in our commitment scheme, encoding each row of a matrix, but to be clear they work on any list of values. of values, treat them as the coefficients of a polynomial (i.e. )6565Careful: this is a different way to read a row as a polynomial than the multilinear extension! There, were the values at and , while here they’re coefficients. and evaluate it at fixed, distinct points .
The list of those values of is called the row’s codeword, , such that its -th cell is .
For example, consider the row . With and the points , i.e. , so .
Reed-Solomon codes are useful for us because they’re massively redundant. Changing just one value of a row changes most of the codeword:
If , then and differ in of their cells.
With rate , two different rows’ codewords differ in more than half their positions, meaning checking a single random codeword cell has at least a 50% chance of telling them apart.
The other property of Reed-Solomon codes that will come in handy is that their encoding is linear:
For any rows of values and any :
In other words, encoding a weighted sum of rows gives the same result as taking that weighted sum of their codewords. This is exactly what we need: if the prover commits to the codewords of ‘s rows and later sends us a weighted sum of those rows (e.g. ), the verifier can encode it themselves and check it against the committed codewords!
§7.3.Ligero-PC
We’re now finally ready to discuss the complete implementation of our polynomial commitment scheme, Ligero-PC.6666Note: Cryptography papers usually build hash-based commitment schemes like this in two steps. First, they design an IOP that swaps our polynomial IOP’s assumption of a magical device that tells you a committed polynomial’s value at any point for the weaker assumption of a device that only lets you read a few entries of a committed table. Then they compile that IOP into a SNARK that doesn’t assume the existence of the weaker magical device, via the BCS transformation, which uses Merkle tree openings and Fiat-Shamir (Section 9) to make everything practical & non-interactive. Here, we’ll present both steps together as one unit.
§7.3.1.Commitments
To commit to some table , the prover does the following:
- Lay out as an matrix .6767Note: and are important parameters to tune for proof size and speed. During an opening, the prover will send (which has values) and opened columns ( values, where is the number of columns the verifier checks, see Section 7.3.2), so the proof size is . Given , is minimized when , i.e. , so should be a lot wider than it is tall. The verifier’s work scales similarly, since it encodes and sums each opened column.
- Encode every row with RS, giving an matrix of codewords .
- Build a Merkle tree whose leaves are (hashes of) the columns of , and send the root to the verifier.
§7.3.2.Openings
To prove for any , the prover/verifier do the following:
- The prover sends , as defined in (7.1.1), to the verifier.
- (Value check) The verifier checks that by folding.
- The verifier computes itself, and then picks random column indexes to request from the prover.
- The prover opens those columns of , each with its Merkle path.6868See Wikipedia if you need a refresher on how Merkle trees work.
(Column check) For each opened column , the verifier checks that:
If all column checks pass, the opening is successful.
Why the column check works might not be obvious at first glance, so let’s break it down. Let be row of . Each row of is just the codeword of the matching row of , i.e. . Thus for every column :
The first equality is just linearity (Theorem 7.2.2), which says a weighted sum of codewords is the codeword of the same weighted sum of rows. The second is the definition of from (7.1.1). Thus, if the prover is honest, the check will pass.
How likely is it that a cheating prover gets a false opening accepted? Assume for now that every row of is a valid RS codeword. To pass the value check with a false , the prover must send some fake . By Theorem 7.2.1, differs from in more than a fraction of columns, and each of those columns fails the column check. Thus, given our assumption about :
RS codeword, Theorem 7.3.1
Note: We’ll see that we can’t quite guarantee every row of is a codeword, only that it’s close to one, but this bound barely changes. More on this below.
Unlike ~all our other bounds, this one doesn’t improve as the field gets bigger. The only parameters that matter are and . Opening more columns () costs proof size, since each one comes with values and another Merkle path. A smaller RS rate () means fewer columns for the same security, but longer codewords, so more work for the prover when encoding and a bigger Merkle tree to build.
But what if the rows of aren’t RS codewords?6969It’s okay if is made up of codewords from a random -shaped matrix, not necessarily the “true” , it just needs to be composed of RS codewords period. We made this assumption above, but if it’s not true, a cheating prover could just hash whatever matrix it wants for , making our soundness argument above useless. Luckily we can prove that, with high probability, the column check will catch any that’s far from being made of RS codewords, which turns out to be all we need.7070As long as is drawn randomly after the prover committed to the table. If not, the prover could build ‘s errors to cancel out under exactly the weights .The fix is to squash in a proximity test: a second weighted sum of the rows, with weights the prover couldn’t predict.1.The verifier picks a random weight for every row, and the prover sends , the value that folds to by .1.Then the verifier picks a random , and the prover sends in place of . The verifier then checks this folds to , the same trick as the mask row in Section 8.3.2.The original Ligero-PC sends as a separate row instead, but squashing lets us save bandwidth.
Why only far? If only a few cells of are corrupted, the opened columns will usually miss them. But that’s fine, since a few corrupted cells can make a check fail, but can’t get a false claim accepted. What matters is that is -close, meaning it matches some matrix whose rows are all valid RS codewords, in all but at most columns. As long as , a -close has only one such ,7171Each would match outside its own bad columns, so the two would differ in at most columns. But by Theorem 7.2.1, two different codewords differ in more than that. which corresponds to the RS encoding of .
So the only way for a malicious prover to cheat is to hash a -far .7272-far just means “not -close”. How likely is such an to pass a column check? Not likely: by Diamond and Posen (2023), summing the rows of a -far with weights , for a random , gives something -far from every RS codeword with probability at least about . And when the sum is -far, each opened column in the column check catches it with probability more than . So taking all of this into account, the true soundness of openings is:
,
Proof: A cheating prover can only get lucky in three ways:
- is -far, but summing its rows with the weights happens to give something close to an RS codeword anyway. As explained above, this happens with probability about .
- is -far and its weighted sum isn’t close to any RS codeword, so each opened column catches it with probability more than , but all columns miss anyway. This happens with probability less than .
- is -close, so to pass the value check the prover must send a fake . A column misses it only if it’s one of the fewer than columns where the fake and true codewords agree, or one of the at most corrupted columns. Thus all columns miss with probability at most .
The chance of any of these occurring is their sum, via the union bound.
Note: The first two terms of Theorem 7.3.2 only depend on whether is close to RS codewords, which doesn’t change between openings. So if a table will be opened many times, its first opening can use lots of columns to show it’s -close for a tiny , and later openings then need far fewer, since only is left.7373For example, say and we want soundness. A one-off opening needs about columns. Showing is very close, say -close, takes about columns, but after that, each opening only needs about .
§8.Zero-knowledge
ZK-SNARK stands for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge. So far, we’ve built a lot of tools that achieve the succinct and argument of knowledge parts, but not discussed zero-knowledge or non-interactivity. Luckily, all of our existing tools can be modified/augmented fairly easily to be both ZK (keep reading!)7474Another common way to turn a SNARK into a ZK-SNARK is to write its verifier as a circuit, prove that circuit with a separate zero-knowledge proof system, and share only that proof, like this. and non-interactive (see Section 9). First, let’s discuss why our tools as is are not considered zero-knowledge.
For a protocol to be zero-knowledge, the verifier should learn nothing beyond the fact that the claim is true from a proof. Our tools so far are all pretty leaky. Almost every message the prover sends to the verifier gives the verifier an equation that can be aggregated together with others to solve for the underlying committed tables.7575Some concrete examples: •Sum-check. For , the first round polynomial has , so the verifier learns that .•Openings. is a weighted sum of ‘s rows, so opening at reveals . Open it again at and the verifier gets , and with two equations in two unknown rows, it can solve for the whole table!•Opened columns. Each one reveals a codeword entry of every row, which is yet another equation per row. How do we make it such that a verifier can’t learn anything about our committed tables, even from many proofs?
What if, before sending a value computed from a secret, we just added some fresh random value (a mask) to it? In theory, this works surprisingly well:
If some mask is drawn uniformly at random, independently of , then is uniformly random, no matter what is.
This is the same idea as a one-time pad in cryptography, and it comes with the same two big caveats:
- A mask can only be used once. If the verifier sees and , it can subtract them to get , and the mask cancels out entirely.
- A mask must never leak. If any other message reveals or something computed from it, the verifier can use it to cancel out the mask and recover . So we have to be careful that not only does each message not leak a mask, but neither does any combination of messages, etc.
If we’re careful to obey these rules, we can make our proof zero-knowledge by applying masks to any leaky messages (masking them).7676Note: Technically masking gives only what’s called honest-verifier zero-knowledge, which only holds for a verifier that generates its challenges randomly like it’s supposed to. But this is fine, once the protocol is made non-interactive (see Section 9), the challenges come from a hash, so the verifier can’t deviate anyway. The tricky part is doing this without breaking soundness, since the verifier still needs to check what the prover sends.
Our tools leak in two different ways, which we’ll fix separately:
- Through the values the prover sends, like sum-check’s round polynomials. The challenge here is that the verifier has to check these values without ever seeing them (Section 8.1).
- Through the commitments themselves. Each opening reveals columns of straight from the commitment, which the verifier checks against the Merkle root. These can’t be masked after the fact, so the masking has to be built into the commitment (Section 8.3).
We’ll start with the values.
§8.1.Hiding values with committed pads
All of our tools involve the prover sending the verifier values computed from secrets: sum-check’s round polynomials, the helper values in lookups, etc.
We’ll need to mask these too if we want to achieve full zero-knowledge, but we can’t just throw random masks on everything because the verifier needs these values to do arithmetic checks on, e.g. in sum-check the verifier must check . If a prover sends instead of , the verifier can’t run this check anymore, a cheating prover could claim any number and say “that’s the true value plus my mask, trust me bro.”
So how can the verifier check something it can’t see? Well, it already does this with commitments: it never sees a committed table, but the prover can still convince it of facts about it. So what if the prover committed to its masks too?7777This is the core idea of VEIL (Dalal, Hemo, Rabinovich and Rothblum, 2026), which most of this section follows. Let’s see how that might work.
At the start of each proof, we’ll have the prover generate a long list of fresh random masks and commit to them as one table . We’ll call these committed masks pads.7878As in one-time pad. Then, whenever the prover would normally send some secret value to the verifier, it sends instead. As long as each pad is used only once, by Theorem 8.0.1, every is uniformly random and tells the verifier nothing (on its own).
But how do we still allow the verifier to do checks on these values, when it doesn’t know the pads? In short, we’ll turn every check into a claim about committed values, which the prover can prove later (Section 8.2).
§8.1.1.Linear checks
Take for example the check from the first round of sum-check:
If the prover sends and , the verifier’s desired check becomes:
This equivalent form has only pads on the left and values the verifier knows on the right, so it’s now just a claim about a weighted sum of a committed table! That’s very close to what our openings from Section 7 already let us check.7979Recall: evaluating a multilinear extension at some point is equivalent to evaluating a weighted sum of the table with weights . See Theorem 2.3.1. The one wrinkle is that a plain opening proves a sum of the table weighted by , while this is a sum weighted by something else (here, just picking out two cells). Luckily, as we’ll see in Section 8.2, it’s fairly straightforward to prove this nonetheless.
We can do this for every linear check the verifier normally makes, turning checks into claims about the committed pads, which we’ll save to verify later.8080Using the method described in Section 8.2. Note that this means the verifier no longer does its checks live as it gets messages from the prover, and instead just writes them all down and waits to check them at the very end.
Generalizing this, as long as a check is linear in the secret values , substituting for every secret value turns it into a claim of the form:
where is some public weight table (zero on every pad the claim doesn’t touch), and is a public number. We’ll see how to prove these claims soon in Section 8.2.
What about the claims passed between sum-checks? Recall from Section 4.3 that a sum-check proving ends with a claim about , which becomes the starting claim of the next sum-check, the one proving how was computed. With pads, the prover just sends padded, so the next sum-check’s first check, , has hidden values on both sides. But it’s still linear, so it turns into a pad claim like any other. So claims get passed all the way back up the chain without ever being revealed.
§8.1.2.Non-linear checks
Not all checks are linear, sometimes a check multiplies secret values together. For example, at the end of a sum-check over an elementwise product of tables (Section 4.1), the verifier needs to check that , where , and are all secret. Naively substituting , , etc would result in a claim involving a product of two pads, which isn’t of the form (8.1.1).
It’s important we have some way to do these checks. Luckily, there’s a neat trick we can do to effectively turn them linear, and thus we can verify them using the same machinery we’ll verify all our linear claims with. It’s a bit complex, buckle up.
Let’s get formal. Say the verifier needs to check the following claim, where are secret values (each already sent padded as ), and is some public polynomial where every term has the same total degree , a.k.a. is homogeneous:8181For example, is homogeneous of degree , but isn’t. If isn’t homogeneous, we can always make it so by introducing a public constant and multiplying each term by enough copies of to bring it up to degree , e.g. becomes .
How do we prove this without revealing the ‘s? If the verifier knew the ‘s, it’d be easy, would just be a public number and “ “ would be a linear claim. Our first instinct might be to use the padded values so the verifier can compute itself. Expanding it gives plus a bunch of terms where the ‘s and ‘s are multiplied together. Call the sum of those terms . The verifier can’t compute itself, since it involves secrets, so the prover sends it padded, and the check becomes:
This is linear in the secrets and , but nothing ensures the the prover sends is correct, so a prover lying about could just send whatever makes up the difference. And we can’t fix this by checking directly, since is a non-linear combination of the ‘s and ‘s, which puts us right back where we started. What we need is a way to prevent a cheating prover from using to cancel a lie in , without needing to actually check itself.
The trick is to have the verifier send a random challenge that scales , but only after the prover has sent . That way, the difference that would need to make up depends on , and thus a cheating prover can’t know in advance which would cancel out a lie.8282This trick comes from QuickSilver (Yang et al., 2021). The prover scales each by and masks it with a fresh pad , sending . It turns out that since is homogeneous, expanding always gives a polynomial in whose top coefficient is exactly . For example, with :
Here the top coefficient is , and the other two, and , contain pads. Generalizing this, for any homogeneous of degree , the top coefficient is always , and the other coefficients, which we’ll call , all involve pads:
don’t depend on , so the prover can compute them in advance and send them, padded, before the verifier picks . They play the same role as in the naive idea, but now, since they’re sent before is chosen and only appear on lower powers of , they can’t be used to cancel out a lie in .
Swapping in the prover’s claim for , the verifier’s check becomes:
The left-hand side is linear in the secret values , since the verifier knows . The right-hand side is a public number, since the verifier knows every . So this is now a linear check, which the verifier can turn into a claim about the pads like any other!
To summarize, to prove , the prover/verifier do the following:
- The prover computes and sends .
- The verifier sends a random .
- The prover sends each .
- The verifier saves the linear claim (8.1.2), plus one linear claim for each , to make sure the prover sent the ‘s honestly.8383Each was already sent padded as , so substituting gives the pad claim .
Why is this sound? If , the two sides of (8.1.2) are different polynomials of degree in , whatever ‘s the prover sent, and so they agree with probability at most by Schwartz-Zippel. Note this is a new way for a cheating prover to get lucky that the non-ZK version didn’t have. Going zero-knowledge costs us a little soundness!
Why is it zero-knowledge? All sent values derived from secret values are masked by fresh pads, and so via Theorem 8.0.1, they are uniformly random and the verifier learns nothing.
§8.2.Proving claims about pads
By the end of a proof, the verifier is sitting on a big pile of claims about the pads, each of the (8.1.1) form:
Let’s now discuss how we’ll actually prove these. Looking at the form of these claims, we can quickly tell we’ll want to use sum-check somehow to prove this, as it’s just an elementwise product of two tables, and . But we can’t just use sum-check as is, the back-and-forth messages that sum-check requires would leak information about the pads, and we can’t mask those or we’ll just keep recursively generating more and more pad claims.
Instead of masking the sum-check’s messages, we’ll mask the pads themselves, all at once. A masked table looks like pure noise (Theorem 8.0.1), so we can prove things about it without masking any of the messages involved. So back at the very start of the proof, alongside we’ll also have the prover commit to a table of uniformly random masks, the same size as , which it never uses anywhere else.
Thus, to prove some claim , we just run the following protocol:
- The prover sends
- The verifier sends a random
The prover proves the following with standard, non-ZK sum-check:
(8.2.1)- The sum-check ends needing , which the verifier computes itself, and , which the prover proves by opening at . It never opens on its own, since would leak information about the pads.8484 isn’t committed itself, but if and are committed with the same column positions, then by linearity (Theorem 7.2.2), each column of ‘s encoding is just times ‘s column plus ‘s. So the verifier can combine the opened columns itself and run an ordinary opening.
Why is this sound? Let’s rearrange (8.2.1) like so:
Notice that if the prover is lying, and thus , the left-hand side is a non-zero polynomial of degree , so by Schwartz-Zippel, it’s zero with probability .
Why is this zero-knowledge? Everything the verifier sees in step 3 is computed from , and since is uniformly random and never used anywhere else, those values are uniformly random too (Theorem 8.0.1), and the verifier learns nothing about .8585And doesn’t help either: given , it’s just , which the verifier could compute itself.
§8.2.1.Merging pad claims
Proving every pad claim this way would be very expensive, though. Each claim would need its own sum-check and opening, and worse, its own mask table , since a mask can only be used once. Luckily, we can merge them all into one, exactly like in Section 6: each pad claim is a public-weighted sum of the same table , so the verifier draws a random weight for each claim , and they squash into the single claim:
which, with high probability, only holds if every claim does. It’s of the same form as before, so the prover proves it with the protocol above, once, with a single .
Note that each of the challenges we’ve added along the way (, , , , etc) give a cheating prover more chances to get lucky, at most each. So zero-knowledge isn’t quite free, but over a big enough field the soundness cost is pretty negligible.
So all the verifier ever learns is that every claim about the pads holds. That means we can make any of our tools zero-knowledge by masking every value it sends with pads, and leaving behind only claims about the pads instead of checks.
§8.3.ZK commitments
Ligero-PC openings leak in two ways we haven’t dealt with yet: through the columns of the prover reveals for the column check, and through the row it sends.
We can’t make the column reveal ZK with pads, because the verifier needs to hash the columns to check them against the Merkle root, and hashes change wildly and non-algebraically with their inputs. A column hashed with a pad has nothing to do with the column on its own, so the check can’t be turned into a claim about committed pads. So to stop the column reveal/check from leaking, we’ll need to make the committed columns masked from the start.
While we’re at it, we’ll also hide the row the prover sends this way. We could pad it, but that would take pads for every opening, whereas a mask hidden inside the commitment costs just one extra row.
Let’s start with the columns.
§8.3.1.Masking the RS codewords of
Each opened column contains a codeword entry of every row, so it leaks a little about each one. One naive idea to make this ZK would be to add random noise to directly (i.e. mask it), but then its rows wouldn’t be valid RS codewords anymore, and thus the column check would fail. Instead, we’ll need to add the randomness before RS encoding.
Specifically, before encoding, the prover extends each row of with a random tail of extra coefficients, so instead of it encodes :
where is the concatenation of and . So every row of is still a valid RS codeword, just of a row with values instead of . Linearity still holds, so the column check still works, and the value check just ignores the tail, folding only the first entries of the row the prover sends.
Is this zero-knowledge? Yup! Each codeword entry is now the row’s value plus the tail’s value at that point, so the tail acts as a mask (Theorem 8.0.1). The catch is that these masks all come from the same random coefficients, so they aren’t independent.8686E.g. with , the tail at is . That’s a fine mask alone, but at any second point it’s a fixed multiple of the first, so two opened entries can cancel it. Being handwavy here, we can think of each random coefficient as having enough randomness to mask one entry. Formally, this is because a random polynomial with coefficients is -wise independent. This means as long as at most distinct columns are ever opened, they reveal nothing about the row.8787Except at , so the evaluation points must avoid . This is another reason why we generally want to merge all claims about a table into one (Section 6), so only one set of columns is ever revealed, keeping us well under .
The cost is that rows now have values, so with rate the codewords grow from to entries, which means more data for the prover to encode, hash and store.
Note: Each Merkle leaf should also be hashed with some random bytes (a salt), otherwise the verifier could guess and check columns against the tree.
§8.3.2.Masking rows sent during openings, i.e.
Tails hide the opened columns, but the verifier still sees the row itself. As we saw, padding it would take pads per opening, so instead we’ll hide it with a single mask row, committed alongside the data.
Before committing, we’ll have the prover append an extra row8888Technically a few rows, not one, because a single base field row isn’t random enough to hide values from an extension field (Section 2.1.1). See Haböck and Al Kindi (2024) for more. of uniformly random masks to , which gets a tail, and is encoded and committed like every other row.8989Even though is already random, it needs a tail to help mask the weighted sum of tails that contains. Now, to open :
- The prover sends and , where .9090As usual, are fresh pads.
- The verifier sends a random .
- The prover sends instead of .9191Tails included, so entries. As above, the value check folds only the first and the column check encodes all of them.
- (Value check) The verifier folds by , and the result should be .9292Folding is just a weighted sum of the cells (Theorem 2.3.1), so folding gives whatever folds to (a.k.a. ), plus times what folds to (a.k.a. ). It can’t check this directly, but substituting and turns it into a linear claim about the pads (Section 8.1.1), which it records.
- (Column check) As before, but treating as one more row with weight , i.e.:
Why do we need ? Without it, the value check would just be “ folds to “, and nothing checks against the committed , so a cheating prover could claim whatever it wants and pick a to make up the difference. Adding the random challenge fixes this, since the verifier only sends it after the prover has locked in and (by sending them padded), and thus the prover can’t choose a that perfectly cancels a fake . The column check then forces to fold to , so a fake only passes if happens to make the two lies cancel exactly, which happens with probability at most .9393This is via the Schwartz-Zippel lemma again, as in Theorem 2.1.1.
Is this zero-knowledge? Yes! By Theorem 8.0.1, is just plus a uniformly random row, so it’s uniformly random too.9494Okay, technically not completely random, as it must fold to . But the verifier never learns , and even if it did, is random and hides . And itself stays hidden by its pad, so unlike in a plain opening, the verifier never even learns the value it opened.9595In practice, often isn’t sent at all: it only appears inside a claim together with pads, and the mask row’s part () is sent without any padding. The opening and the proof of the pad claims then happen in one step, with one challenge blinding both the data rows and the pads.
§9.Fiat-Shamir
So far, every tool we’ve introduced requires the verifier to be in communication with the prover to complete the proof. In some circumstances this kind of interactive proof is fine, but to satisfy the “N” in ZK-SNARK, we want our proofs to be non-interactive. With non-interactive proofs, anyone in the world can verify them after the fact, and they can more easily be generated under tight latency constraints as we don’t need to wait for messages from the verifier.
So, do we have to throw out all our tools and try to think of some new non-interactive ones? Luckily, no, thanks to a simple trick called the Fiat-Shamir transformation9696From Fiat and Shamir (1986). which turns any interactive proof into a non-interactive one.
The idea is really simple: at any point where we’d normally wait for the verifier to send a random challenge, just hash everything the verifier would have seen so far (the transcript) and use that as the challenge. Anyone can later recompute the exact same hashes themselves, even if they weren’t in contact with the prover while the proof was being generated.
Why does this work? Each challenge is a hash of the prover’s earlier messages, so changing any of those messages changes the challenge too. Thus because hashes are unpredictable, the prover can’t know what challenge it’ll get until it has already settled on its messages, just like in the interactive version.9797This is why it’s really important that we hash everything a challenge is meant to test. If some value the prover can choose isn’t hashed, the challenge doesn’t depend on it, so the prover can compute the challenge first and then choose whatever value passes the check the challenge is used in. Getting this wrong has broken real proof systems, see Dao et al. (2023).
There’s just one big issue: grinding. Against a real verifier, a cheating prover only gets one shot per challenge. But under Fiat-Shamir, it can just keep tweaking its message over and over offline until it happens to get a lucky challenge. Specifically, if each attempt succeeds with probability , then attempts succeed with probability up to about .9898This assumes the hash behaves like a truly random function, a.k.a. the random oracle model.
For a degree- round polynomial over the Goldilocks field, , so an attacker who can afford hashes (the Bitcoin network does /s) can succeed at cheating with probability , yikes! This is one of the main reasons why we draw challenges from an extension field (Section 2.1.1), as e.g. over the chance of success even after attempts is only .
§10.Putting it all together
That’s all the tools we need! It might seem limiting to have to express everything in terms of tables and matrices, but they’re actually enough to prove arbitrary computation. This is because any program can be rewritten as an arithmetic circuit, a DAG of addition and multiplication gates, and any such circuit is provable with our tools (e.g. group wire values into tables, turn gates into elementwise polynomial relations, use matmuls or lookups to line up each gate with its input wires).9999Custom circuits are the fastest option when the computation is fixed ahead of time, but they’re a lot of work to build and optimize, and awkward for programs whose control flow depends on their inputs. zkVMs like SP1 prove arbitrary computations with one fixed circuit by committing to a trace of a general-purpose CPU running the program (i.e. a table where each row is one executed instruction), and proving that trace is faithful. Every row is checked against the same elementwise relations (e.g. if the instruction is an ADD, its output is the sum of its inputs), and lookups check that each row’s instruction and register values match the program/CPU’s current state. Some operations (e.g. bit manipulation) make for awkward (and thus expensive) circuits though, so we generally try to prove those with lookups instead (Section 5.1).
To recap how the pieces fit together into a full ZK-SNARK:
- The prover commits to every table that can’t be justified any other way (inputs, outputs of non-polynomial operations, etc) and its pads (Section 8.1), using Ligero-PC (Section 7) with tails and mask rows so the commitments don’t leak data about the tables (Section 8.3).
- Starting from a claim about the output at a random point, it works backwards through the computation. For every elementwise relation or matrix product, a sum-check turns claims about the operation’s output into claims about its inputs (Section 4.3), while lookups take care of operations that aren’t polynomials (Section 5.1).
- Every value the prover reveals along the way is masked with pads to randomize them and keep the proof zero-knowledge. Every check on those values the verifier would normally make is turned into a claim about the pads instead (Section 8.1).
- Claims that pile up on the same committed table get merged (Section 6), so each table only gets opened once.
- At the very end, all the claims about the pads get merged into one megaclaim and proven in one go (Section 8.2).
- Since every random challenge is just generated via a hash of the transcript so far (Section 9), the whole thing can be a single proof file that anyone can check later.
Note: Turning programs into circuits is called arithmetization. Many proof systems, e.g. Spartan and HyperPlonk, are designed to prove only circuits written in a specific format such as R1CS or Plonkish. This allows them to build one verifier that works for every circuit, at the expense of a one-time setup step to commit each circuit’s gates and wiring, and having to commit to every wire value in each proof.100100This is useful if the verifier implementation has to be fixed, e.g. for smart contracts, or a circuit that verifies other proofs. The GKR-style approach we focused on (which is best for wide, shallow circuits) is just one way to put these tools together, and the same ideas can be used to build provers for R1CS, Plonkish, etc.
There are so many more ways to build and think about ZK-SNARKs than we covered here. For further reading, check out Justin Thaler’s Proofs, Arguments, and Zero-Knowledge.
§11.Commitments at scale
The tools above really are all we need to build a ZK-SNARK. However, for tables that are really big (~terabytes), and/or get opened across many proofs, our commitments need a few extra tricks to be practical for real world deployments.
§11.1.Recursive openings
Recall that for a Ligero-PC opening on a table , the prover must send both the row ( field elements) and opened columns ( field elements each) to the verifier. Since is fixed at by construction, the sizes of the row and the columns trade off against each other. For large tables (e.g. cells), no matter how we balance and , we’ll be sending hundreds of megabytes to the verifier for each opening!101101For example, with the best balance is a row of cells. Its cells are extension field elements (Section 2.1.1), so that’s about MB for the row alone.
But notice that the row and the columns aren’t checked in the same way. For columns, the verifier must hash them against the commitment’s Merkle root, so it truly needs the columns’ full contents. But the row is only checked via arithmetic, and we have a lot of tools to reduce arithmetic checks down into statements that are cheaper to verify… so maybe we can avoid sending the row?
Observe that the two checks we do on are both checks on a weighted sum of its cells, with public weights:
- The value check: Folding by is a weighted sum with weights .
The column check: is , the row’s polynomial evaluated at column ‘s point (see Section 7.2 for a refresher), which looks like:
This is a weighted sum of the row’s cells, where cell has weight .
Right now, the verifier computes these sums itself, from the row it was sent. But we can check a weighted sum of a committed table without ever seeing it, since a sum-check reduces it to a single opening (see the end of Section 6). So what if the prover committed to as a new table, , instead of sending it? The verifier could then check those weighted sums against the commitment, without ever having to be sent the full row.
Concretely, to prove :
- The prover commits to , which is just laid out as a matrix.
- The verifier then picks columns of , and the prover opens them as usual.
- The value check and the column checks become claims about , which are merged into one (Section 6) and sum-checked, leaving a claim about at a random point.102102Note: To finish the sum-check, the verifier also needs to evaluate the merged weights’ extension at the random point itself (Section 6). That’s cheap, since both kinds of weights have extensions with a product formula. For it’s the one in Definition 2.3.1, and for the column checks’ weights it’s:
- That claim is resolved with an opening of .
But step 4 is an opening too, which means sending a row again. The difference is that is far smaller than , so a row from it is much shorter. If it’s still not small enough, we can repeat this trick as many times as we need, committing to ‘s row instead of sending it, opening that, etc etc.
This is a bigger deal than it might seem at first! Notice that because the original table’s row is never sent, its length barely matters, so we can lay out as a matrix with long rows and tiny columns, which will make sending the columns super cheap. If we do the same thing for and the tables at every level below it, we can get the cost of an opening down to just sending a few short columns from each level and a small row at the end (plus a sum-check for each new table). For a -cell table, that’s around a megabyte with recursive openings, versus hundreds of megabytes without.
This isn’t entirely a free lunch though, as recursion slightly erodes soundness. Each level of recursion gives a cheating prover the same chances to get lucky as a normal opening (Section 7.3.2), plus a merge and a sum-check. So a recursive opening with levels is about times as likely to be fooled as a non-recursive one.103103Specifically, if level ‘s commitment (with ‘s at ) has rows, cells, codewords of length and opened columns, a false claim passes with probability at most:Here the first two sums are each commitment’s own opening error (Theorem 7.3.2), and the last sum is the merge () and the sum-check () at each level . We can just open a few more columns per level to make up for this.
What about zero-knowledge? In a zero-knowledge opening (Section 8.3.2), the row the prover sends is the masked one, , which is uniformly random (Theorem 8.0.1). Thus is uniformly random, so it’s safe to have every deeper level of recursion use plain non-ZK openings, as they could only reveal information about the uniformly random . Only the first level needs to be zero-knowledge!
§11.2.Refreshing commitments
Some tables are ephemeral, committed only for one proof and then never used again. Others might get committed once and then used over and over across many proofs. The zero-knowledge commitments we’ve constructed can’t hide a table forever though, since the random tails we added in Section 8.3 only hide the table while at most distinct columns have been opened, and every opening reveals some new random columns. Once a commitment hits that limit, it’s no longer safe to open, and we need to make a new one to “refresh” it.104104Recursive openings (as described above in Section 11.1) make long tails cheap, so can be huge, and once a table’s first opening has shown it’s close to RS codewords, later openings only need a few columns each. But on a long enough time scale, we’ll hit the limit eventually.
But how can a verifier trust that our new commitment holds the same underlying table? With a link proof! Say the old commitment is of and the new one is of , with fresh tails. To prove , the verifier picks a random point , opens both commitments at it (Section 7.3.2), and checks that the two opened rows fold to the same value.105105This is just the identity test (Theorem 2.1.1) on and . Only the first cells of each row get folded, since their tails are different on purpose. In practice these are ZK openings (Section 8.3.2), so the comparison becomes a claim about the pads (Section 8.2).
Note: The old commitment is already known to be close to RS codewords, so just a few of its columns are enough. The new one hasn’t been opened before, so the verifier opens lots of its columns to show it’s close to RS codewords too.
To trust a new commitment, the verifier has to check every link between it and the original. So rather than linking each new commitment to the one before it, which makes the path longer with each additional commitment, we’ll have the link all new commitments directly to the first one (the root commitment), which gets one big opening up front to show it’s close to RS codewords, and serves as the table’s permanent source of truth.
Note: Each link spends a few of the root’s columns, so a root can only be linked to so many commitments. If that’s not enough, we can link new commitments to other commitments below the root, forming a tree of commitments. Every extra layer multiplies how many commitments we can have, but only adds one more link for the verifier to check. In practice, one layer is usually plenty.