What are Schwartz-Zippel circuits? How do they relate to iterative constraint systems? posted 19 hours ago

I've talked about iterative constraint systems in the past, which I really like as an abstraction to build interactive (and then non-interactive) proof systems. But I didn't really explain the kind of circuits you would implement using iterative constraint systems (besides saying that these would be circuits to implement permutations or lookup arguments).

Just to recap in a single paragraph the idea of iterative constraint system: they are constraint system where the prover fills the value of the witness registers (also called columns or wires) associated with a circuit, then ask for challenge(s), then fills the value of new registers associated with a new circuit. That new circuit is more powerful as it can also make use of the given challenge(s) as constant(s) and the previous witness registers.

Well I think here's one generalization that I'm willing to make (although as with every generalization I'm sure someone will find the exception to the rule): any iterative circuit implements a Schwartz-Zippel circuit. If you don't know about the Schwartz-Zippel lemma, it basically allows you to check that two polynomials $f$ and $g$ are equal on every point $x \in S$ for some domain $S$ (usually the entire circuit evaluation domain) by just checking that they are equal at a random point $r$. That is, $f(r) = g(r)$.

So my generalization is that the challenge(s) point(s) I mentioned above are always Schwartz-Zippel evaluation points, and any follow up iterative circuit will always compute the evaluation of two polynomials at that point and constrain that they match. Most of the time, there's actually no "final" constraint that checks that two polynomials match, instead the polynomial $f(x) - g(x)$ is computed and check to be equal to 0, or the polynomial $f(x)/g(x)$ is computed and checked to be 1.

This is what is done in the plonk permutation, for example, as I pointed out here.

Exercise: in the plonk permutation post above, would the iterative circuit be as efficient if it was written as the separate evaluation of $f$ and $g$ at the challenge points, and then a final constraint would check that they match?

EDIT: Pratyush pointed me to a paper (Volatile and Persistent Memory for zkSNARKs via Algebraic Interactive Proofs) that might introduce a similar abstraction/concept under the name algebraic Interactive Proofs (AIP). It seems like the Hekaton codebase also has an user-facing interface to compose such iterative circuits.