2 parties: prover, verifier

High-level idea:

1. Prover wants to prove one statement.
2. Transform the statement to a program.
3. Transform the program to a circuit.
4. Transform and compress the circuit to a few polynomials.
5. Use polynomial commitments to reduce checking.

Sudoku Example (PLONK):

1. Prover wants to prove a Sudoku solution is correct.
2. Write a program which can verify the correctness of a Sudoku solution. Prove the program output True.
3. Transform the program to a circuit composed of addition and multiplication logic gates.
4. Transform the circuit to a constraint system by gate constraints and compress the system into a single polynomial equation. $Q_L(x)a(x)+Q_R(x)b(x)+Q_O(x)c(x)+Q_M(x)a(x)b(x)+Q_C(x)=0$
5. Generate a few polynomials from copy constraints, using coordinate pair accumulator.
6. Make commitments to polynomials and open them at random point.

Features

• Updatable setup: setup process is updatable. All setup participants were corrupt and shared with each other the secret randomness- then if any point someone honest comes and contributes more randomness to the setup then from that point on then the parameters are secure as long as that additional randomness doesn't get released.
• Universal: Can be used to prove arbitrary program. If you want to change the statement you want to prove, then as long as it is fixed within a certain bound fixed in advance, then that's fine.
• fan-in 2 and unlimited fan-out

Benchmark

Hash

<aside> 💡 Machine Spec: Surface Pro 6, with an i7–8650U CPU at 2.1GHz, 4 physical cores, 16GB RAM

</aside>

PLONK Benchmarks II — ~5x faster than Groth16 on Pedersen Hashes | by Thomas Walton-Pocock | Aztec | Medium

PLONK Benchmarks I — 2.5x faster than Groth16 on MiMC | by Thomas Walton-Pocock | Aztec | Medium

PLONK Benchmarks I — 2.5x faster than Groth16 on MiMC | by Thomas Walton-Pocock | Aztec | Medium

• Groth16 is not universal — i.e. if you change the circuit (modify your private smart contract), you need to do a new trusted setup.
• MiMC is a cryptographic hash function family designed specifically for SNARK applications.

memory usage Benchmarking ZKP Development Frameworks: the Pantheon of ZKP - Ethereum Research (ethresear.ch)

Permutation Check

All you need is a permutation check. Permutations are easier to check on multiplicative subgroups.

3 checks: gate, copy/wire, public inputgg

The hard part is the permutation check which solves copy constraints.