Introduction to ZK-STARKs
Remco Bloemen remco@0x.org
$$ \def\F{\mathtt {F}} \def\X{\mathtt {X}} \def\Y{\mathtt {Y}} \def\Z{\mathtt {Z}} $$
Disclaimer: contains math
- If you don't understand something
- Not your fault, this stuff is hard
- Nobody understands it fully
- If you don't understand anything
- My fault, anything can be explained at some level
- If you do understand everything
- Collect your Turing Award & Fields Medal
- Many open questions
Zero knowledge proofs
We know some algorithm $\F(\X, \Y)$.
I give you $\X$ and $\Z$ and proof that “I know an $\Y$ such that $\F(\X, \Y) = \Z$” without revealing $\Y$.
- $\X$ public input, old balances.
- $\Y$ secret input, trades.
- $\Z$ public output, new balances.
Scalable DEX
“I know an $\Y$ such that $\F(\X, \Y) = \Z$”
- public input $\X$: (merkle root of) old balances.
- secret input $\Y$: trades.
- public output $\Z$: (merkle root of) new balances.
$\F$ verifies maker and taker signatures on the trades and updates the balances.
Naive solution
- I give you $\X$, $\Y$ and $\Z$.
- You compute $\F(\X, \Y)$ and verify that it is $\Z$.
Problems:
- 📀 I need to send data size $O(\X + \Y + \Z)$, i.e. all the trades.
💾 We want $O(\X + \Z + \F)$, only merkle roots. - ⏳ You need to do computations $O(\F)$.
⌛ We want constant gas. - 🤫 You now know $\Y$, the secret input.
🤷 We don't care.
Math refresher: Polynomials
Constant | $a_0$ |
Linear | $a_0 + a_1 x$ |
Parabola | $a_0 + a_1 x + a_2 x^2$ |
Cubic | $a_0 + a_1 x + a_2 x^2 + a_3 x^3$ |
Quartic | $a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4$ |
... | $a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n$ |
Can be uniquely described in three ways:
- $n + 1$ Coefficients
- $n + 1$ Points
- $n$ Zeros* and a scaling factor
(* Zeros might be imaginary.)
Can do math with them:
- Add $\deg (P + Q) = \max (\deg P, \deg Q)$.
- Multiply $\deg (P \times Q) = \deg P + \deg Q$.
- Divide $\deg \frac{P}{Q} = \deg P - \deg Q$
- Division works when zeros match.
Toy example: Fibonnacci
We want to prove the 1000-th Fibonacci number starting from a public and a secret value. Take $\F(\X, \Y) = \Z$ to mean the following:
$$ \begin{aligned} F_0 &:= \X & F_i &:= F_{i - 2} + F_{i - 1} \\ F_1 &:= \Y & \Z &:= F_{1000} \\ \end{aligned} $$
Computational trace
Computation with $n$ steps and $w$ registers. The trace $T$ is a $n × w$ table. Here $n = 1000$ and $w = 2$. Restate algorithm as constraints on $T_{i}$
Example: $\X = 3$, $\Y = 4$:
n | $T_{n, 0}$ | $T_{n, 1}$ |
---|---|---|
0 | 3 | 4 |
1 | 4 | 7 |
2 | 7 | 11 |
3 | 11 | 18 |
... | ... | ... |
999 | $F_{999}$ | $F_{1000}$ |
Encode the algorithm as a set of transition constraints:
$$ \begin{aligned} T_{i + 1, 0} &= T_{i, 1} & T_{i + 1, 1} &= T_{i, 0} + T_{i, 1} \end{aligned} $$
and boundary constraints:
$$ \begin{aligned} T_{0, 0} &= \X & T_{999, 1} &= \Z & \end{aligned} $$
‟I know $y$ such that $f(x,y)=z$.”
$⇔$
‟I know a trace $T$ such that the constraints hold.”
Trace polynomials
For each register $j$, create a polynomial $P_j(x)$ of degree $999$ such that $P_j(i) = T_{i, j}$ for $i = 0 … 999$.
(Actual implementation uses $P_j(ω^i) = T_{i, j}$ with $ω$ a $n$-root of unity to allow $O(n \log n)$ FFT and FRI. Also rounds $n$ up to the next power of two. Ignore for now.)
Consider the constraint $T_{i + 1, 1} = T_{i, 0} + T_{i, 1}$ for $i = 0 … 999$:
$⇔ P_1(i + 1) = P_0(i) + P_1(i)$ for $i = 0 … 999$
$⇔ P_1(i + 1) - (P_0(i) + P_1(i)) = 0$ for $i = 0 … 999$
$⇔ Q(x) = P_1(x + 1) - (P_0(x) + P_1(x))$ is zero when $x$ is an integer $0 … 999$.
$R(x) = (x - 0) ⋅ (x - 1)⋅ (x - 2) ⋯ (x - 999)$ is a polynomial and is zero only when $x$ is an integer $0 … 999$.
This means
$$ C(x) = \frac{Q(x)}{R(x)} $$
is also a polynomial.
Create functions that are polynomial only when the constraints are satisfied:
Transition constraints:
$$ \begin{aligned} T_{i + 1, 0} &= T_{i, 1} &⇒&& C_0(x) &= \frac {P_0(x + 1) - P_1(x)} {\prod^i_{[0 … 998]}\left( x - i\right)} \\ T_{i + 1, 1} &= T_{i, 0} + T_{i, 1} &⇒&& C_1(x) &= \frac {P_1(x + 1) - (P_0(x) + P_1(x))} {\prod^i_{[0\dots998]}\, (x - i)} \end{aligned} $$
Boundary constraints:
$$ \begin{aligned} T_{0, 0} &= X &⇒&& C_2(x) &= \frac {P_0(x) - X} {x - 0} \\ T_{999, 1} &= Z &⇒&& C_3(x) &= \frac {P_1(x) - Z} {x - 999} \\ \end{aligned} $$
‟I know $y$ such that $f(x,y)=z$.”
$⇔$
‟I know a trace $T$ such that the constraints hold.”
$⇔$
‟I know polynomials $P_0$ and $P_1$ such that $C_0$, $C_1$, $C_2$, $C_3$ are polynomial.”
Interactive proof
I give you $\X$, $\Z$ and a merkle roots of $P_0$ and $P_1$.
You give me random values $α_0$, $α_1$, $α_2$, $α_3$.
Fast Reed-Solomon Interactive Oracle Proof II
$$ P(x) = a_0 + a_1 x + a_2 x^2 + a_3 x ^3 \cdots + a_n x^n $$
Given a random number $β$, we can fold the coefficients and get a polynomial of degree $\frac{n}{2}$.
$$ P'(x) = (a_0 + a_1 β) + (a_2 + a_3 β) x + \cdots + ( a_{n-1} + a_n β) x^{\frac n2} $$
This can be computed using:
$$ P'(x) = P(x) + \left( \frac{β}{2x} - \frac{1}{2}\right) \left(P(x) - P(-x) \right) $$
$$ P(x) = a_0 + a_1 x + a_2 x^2 + a_3 x ^3 \cdots + a_n x^n $$
Given a random number $β$, we can fold the coefficients and get a polynomial of degree $\frac{n}{2}$.
$$ P'(x) = (a_0 + a_1 β) + (a_2 + a_3 β) x + \cdots + ( a_{n-1} a_n β) x^{\frac n2} $$
$$ P'(x) = P(x) + \left( \frac{β}{2x} - \frac{1}{2}\right) \left(P(x) - P(-x) \right) $$
$$ \begin{aligned} P(x) ={}& a_0 &{}+{}& a_1 x &{}+{}& a_2 x^2 &{}+{}& a_3 x ^3 &{}+{}& \cdots &{}+{}& a_{n-1} x^{n-1} &{}+{}& a_n x^n \\ P(-x) ={}& a_0 &{}-{}& a_1 x &{}+{}& a_2 x^2 &{}-{}& a_3 x ^3 &{}+{}& \cdots &{}-{}& a_{n-1} x^{n-1} &{}+{}& a_n x^n \\ P(x) - P(-x) ={}& && 2a_1 x && &{}+{}& 2a_3 x ^3 &{}+{}& \cdots &{}+{}& 2 a_{n-1} x^{n-1} \\ \\ \frac{β}{2x} \left(P(x) - P(-x)\right) ={}& a_1 β && &{}+{}& a_3 β x^2 && &{}+{}& \cdots &{}+{}& a_{n-1} β x^{n-2} \\ \\ \frac{1}{2} \left(P(x) - P(-x)\right) ={}& a_1 x && &{}+{}& a_3 x^3 && &{}+{}& \cdots &{}+{}& a_{n-1} β x^{n-1} \\ \\ (\frac{β}{2x}-\frac{1}{2}) \left(P(x) - P(-x)\right) ={}& a_1 β &{}-{}& a_1 x &{}+{}& a_3 β x^2 &{}-{}& a_3 x^3 &{}+{}& \cdots &{}+{}& a_{n-1} β x^{n-1} \\ \end{aligned} $$
$$ P'(x) = (a_0 + a_1 β) + (a_2 + a_3 β) x + \cdots + ( a_{n-1} + a_n β) x^{\frac n2} $$
I compute $C(x) = α_0 ⋅ C_0(x) + α_1 ⋅ C_1(x) + α_2 ⋅ C_2(x) + α_3 ⋅ C_3(x)$.
I give you the merkle root of $C$ and claim $\deg C = 1024$.
You give me a random value $𝛽_0$.
I give you the merkle root of $C'$ and claim $\deg C' = 512$.
You give me a random value $𝛽_1$.
...
I give you the constant $C''$.
You verify $C''$ using $\X$, $\Y$, the $α$s and the $𝛽$s.
Fiat-Shamir transform
All you do is give me random numbers. Why don't I replace you by a pseudo random number generator!
Seed PRNG with all prover messages, extract random 'verfier' messages.
Send all the proof at once.