Interactive Arithmetization and Iterative Constraint Systems posted July 2024

I think a lot about how to express concepts and find good abstractions to communicate about proof systems. With good abstractions it's much easier to explain how proof systems work and how they differ as they then become more or less lego-constructions put up from the same building blocks.

For example, you can sort of make these generalization and explain most modern general-purpose ZKP systems with them:

• They all use a polynomial commitment scheme (PCS). Thank humanity for that abstraction. The PCS is the core engine of any proof system as it dictates how to commit to vectors of values, how large the proofs will be, how heavy the work of the verifier will be, etc.
• Their constraint systems are basically all acting on execution trace tables, where columns can be seen as registers in a CPU and the rows are the values in these registers at different moments in time. R1CS has a single column, both AIR and plonkish have as many columns as you want.
• They all reduce these columns to polynomials, and then use the fact that for some polynomial $f$ that should vanish on some points ${w_0, w_1, \cdots}$ then we have that $f(x) = [(x - w_0)(x-w_1)\cdots] \cdot q(x)$ for some $q(x)$
• And we can easily check the previous identity by checking it at a single random point (which is highly secure thanks to what Schartz and Zippel said a long time ago)
• They also all use the fact that proving that several identities are correct (e.g. $a_i = b_i$ for all $i$) is basically the same as proving that their random linear combination is the same (i.e. $\sum_i r_i (a_i - b_i) = 0$), which allows us to "compress" checks all over the place in these systems.

Knowing these 4-5 points will get you a very long way. For example, you should be able to quickly understand how STARKs work.

Having said that, I more recently noticed another pattern that is used all over the place by all these proof systems, yet is never really abstracted away, the interactive arithmetization pattern (for lack of a better name). Using this concept, you can pretty much see AIR, Plonkish, and a number of protocols in the same way: they're basically constraint systems that are iteratively built using challenges from a verifier.

Thinking about it this way, the difference between STARK's AIR and Plonks' plonkish arithmetization is now that one (Plonk) has fixed columns that can be preprocessed and the other doesn't. The permutation of Plonk is now nothing special, the write-once memory of Cairo is nothing special as well, they're both interactive arithmetizations.

Let's look at plonk as a table, where the left table is the one that is fixed at compilation time, and the right one is the execution trace that is computed at runtime when a prover runs the program it wants to prove:

One can see the permutation argument of plonk as an extra circuit, that requires 1) the first circuit to be ran and 2) a challenge from the verifier, in order to be secure.

As a diagram, it would look like this:

Now, one could see the write-once memory primitive of Cairo in the same way (which I explained here), or the lookup arguments of a number of proof systems in the same way.

For example, the log-derivative lookup argument used in protostar (and in most protocols nowadays) looks like this. Notice that:

• in step 4 the execution trace of the main circuit is sent
• in step 6 the verifier sends a challenge back
• and in step 7 the prover sends the execution trace of the second circuit (that implements a lookup circuit) using the challenge

As such, the point I really want to make is that a number of ZKP primitives and interaction steps can be seen as an interactive process to construct a super constraint system from a number of successive constraint system iterated on top of each other. Where constraint system means "optionally some new fixed columns, some new runtime columns, and some constraints on all the tables including previous tables". That's it.

Perhaps we should call these iterative constraint systems.