# 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. ---