PlonKathon is part of the program for [MIT IAP 2023] Modern Zero Knowledge Cryptography. Over the course of this weekend, we will get into the weeds of the PlonK protocol through a series of exercises and extensions. This repository contains a simple python implementation of PlonK adapted from py_plonk, and targeted to be close to compatible with the implementation at https://zkrepl.dev.
TODO
- Add support for custom gates. TurboPlonK introduced support for custom constraints, beyond the addition and multiplication gates supported here. Try to generalise this implementation to allow circuit writers to define custom constraints.
- Add zero-knowledge. The parts of PlonK that are responsible for ensuring strong privacy are left out of this implementation. See if you can identify them in the original paper and add them here.
- Add support for lookups. A lookup argument allows us to prove that a certain element can be found in a public lookup table. PlonKup introduces lookup arguments to PlonK. Try to understand the construction in the paper and implement it here.
To see the proof system in action, run python3 test.py
from the root of the repository. This will take you through the workflow of setup, proof generation, and verification for several example programs.
We specify our program logic in a high-level language involving constraints and variable assignments. Here is a program that lets you prove that you know two small numbers that multiply to a given number (in our example we'll use 91) without revealing what those numbers are:
n public
pb0 === pb0 * pb0
pb1 === pb1 * pb1
pb2 === pb2 * pb2
pb3 === pb3 * pb3
qb0 === qb0 * qb0
qb1 === qb1 * qb1
qb2 === qb2 * qb2
qb3 === qb3 * qb3
pb01 <== pb0 + 2 * pb1
pb012 <== pb01 + 4 * pb2
p <== pb012 + 8 * pb3
qb01 <== qb0 + 2 * qb1
qb012 <== qb01 + 4 * qb2
q <== qb012 + 8 * qb3
n <== p * q
Examples of valid program constraints:
a === 9
b <== a * c
d <== a * c - 45 * a + 987
Examples of invalid program constraints:
7 === 7
(can't assign to non-variable)a <== b * * c
(two multiplications in a row)e <== a + b * c * d
(multiplicative degree > 2)
Our "assembly" language consists of AssemblyEqn
s:
class AssemblyEqn:
"""Assembly equation mapping wires to coefficients."""
wires: GateWires
coeffs: dict[Optional[str], int]
where:
@dataclass
class GateWires:
"""Variable names for Left, Right, and Output wires."""
L: Optional[str]
R: Optional[str]
O: Optional[str]
Examples of valid program constraints, and corresponding assembly:
program constraint | assembly |
---|---|
a === 9 | ([None, None, 'a'], {'': 9}) |
b <== a * c | (['a', 'c', 'b'], {'a*c': 1}) |
d <== a * c - 45 * a + 987 | (['a', 'c', 'd'], {'a*c': 1, 'a': -45, '': 987}) |
Let
for any
The trusted setup is a preprocessing step that produces a structured reference string:
-
$x \in \mathbb{F}$ is a randomly chosen, secret evaluation point; and -
$d$ is the size of the trusted setup, corresponding to the maximum degree polynomial that it can support.
In this repository, we are using the pairing-friendly BN254 curve, where:
p = 21888242871839275222246405745257275088696311157297823662689037894645226208583
-
$\mathbb{G}_1$ is the curve$y^2 = x^3 + 3$ over$\mathbb{F}_p$ ; - $\mathbb{G}2$ is the twisted curve $y^2 = x^3 + 3/(9+u)$ over $\mathbb{F}{p^2}$; and
- $\mathbb{G}_T = {\mu}r \subset \mathbb{F}{p^{12}}^{\times}$.
We are using an existing setup for
The prover creates a proof of knowledge of some satisfying witness to a program.
@dataclass
class Proof:
@classmethod
def prove_from_witness(
cls,
setup: Setup,
program: Program,
witness: dict[Optional[str], int]
):
The proof consists of:
proof element | remark |
---|---|
commitment to left wire polynomial | |
commitment to right wire polynomial | |
commitment to output wire polynomial | |
commitment to permutation polynomial | |
commitment to |
|
commitment to |
|
commitment to |
|
opening of |
|
opening of |
|
opening of |
|
opening of the first permutation polynomial |
|
opening of the second permutation polynomial |
|
opening of shifted permutation polynomial |
|
commitment to the opening proof polynomial | |
commitment to the opening proof polynomial |
In the preprocessing stage, the verifier computes a VerificationKey
corresponding to a specific Program
.
@dataclass
class VerificationKey:
# Generate the verification key for this program with the given setup
@classmethod
def make_verification_key(cls, program: Program, setup: Setup):
The VerificationKey
contains:
verification key element | remark |
---|---|
commitment to multiplication selector polynomial | |
commitment to left selector polynomial | |
commitment to right selector polynomial | |
commitment to output selector polynomial | |
commitment to constants selector polynomial | |
commitment to the first permutation polynomial |
|
commitment to the second permutation polynomial |
|
commitment to the third permutation polynomial |
|
(from the |
|
an $n$th root of unity, where |