ZK Examples
For a peek at the math behind ZKPs
There are various options of what kind of front-end to use to design a ZK circuit. The PLONK system is one such way. We will describe it below, and it will be a good way of preparing us for the full PLONKish arithmetization used in halo2, which is what Axiom uses in production.
A PLONK circuit consists of a table/matrix with the following fixed columns and nearly arbitrary number of rows:
a | b | c | q_L | q_R | q_M | q_C | q_O |
|---|---|---|---|---|---|---|---|
. | . | . | | | | | |
where the numbers in the columns
are fixed once and for all at compile time. Meanwhile the numbers in columns
are called witnesses and specified by the prover each time a new proof is generated. What makes the circuit meaningful, and not a random collection of numbers, is that for each row
, the following equation is guaranteed to hold:
Since the
columns are fixed once and for all, specifying these numbers allows you to "mold" the circuit to constrain the witnesses
to perform certain computations.
For example, if you want to add
in row
, put:
a | b | c | q_L | q_R | q_M | q_C | q_O |
|---|---|---|---|---|---|---|---|
a_i | b_i | c_i | 1 | 1 | 0 | 0 | 1 |
To multiply
in row
, put:
a | b | c | q_L | q_R | q_M | q_C | q_O |
|---|---|---|---|---|---|---|---|
a_i | b_i | c_i | 0 | 0 | 1 | 0 | 1 |
To force
to be a known constant
, put:
a | b | c | q_L | q_R | q_M | q_C | q_O |
|---|---|---|---|---|---|---|---|
a_i | * | * | 1 | 0 | 0 | | 0 |
Note that
can be any numbers and it doesn't matter.
So far, we can use the above to do single line computations. There is one more ingredient: one can also specify once and for all that certain predetermined cells in the table above are always equal. For example, for some
, we must have
. This now allows us to carry results of previous computations into new computations, "chaining" to create longer computations.
To summarize, creating a ZK proof involves the following steps:
Once and for all, specify the circuit itself:
- Specify all cells in columns.
- Specify any equality constraints between cells.
- The verifier receives the above information in a compressed form.
- The prover holds onto a copy of the above information itself.
To submit a proof:
- Do the computation itself, i.e., generate the witnesses.
While circuit design involves just filling out a table using some front end, to actually create a proof there is a backend that takes the PLONK table above and does a bunch of computations involving polynomial commitment schemes. This part is largely independent of the circuit design, but different backends lead to different performance characteristics, which become important to understand for production use cases.