Introduction to ZK-STARKs

Remco Bloemen [e-mail]

$$$$

---

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

$\mathtt{F}(\mathtt{X},\mathtt{Y})$.

I give you

$\mathtt{X}$ and

$\mathtt{Z}$ and proof that “I know an

$\mathtt{Y}$ such that

$\mathtt{F}(\mathtt{X},\mathtt{Y})=\mathtt{Z}$” without revealing

$\mathtt{Y}$.

• $\mathtt{X}$ public input, old balances.
• $\mathtt{Y}$ secret input, trades.
• $\mathtt{Z}$ public output, new balances.

---

Scalable DEX

“I know an

$\mathtt{Y}$ such that

$\mathtt{F}(\mathtt{X},\mathtt{Y})=\mathtt{Z}$”

• public input
  $\mathtt{X}$: (merkle root of) old balances.
• secret input
  $\mathtt{Y}$: trades.
• public output
  $\mathtt{Z}$: (merkle root of) new balances.

$\mathtt{F}$ verifies maker and taker signatures on the trades and updates the balances.

---

Naive solution

• I give you
  $\mathtt{X}$,
  $\mathtt{Y}$ and
  $\mathtt{Z}$.
• You compute
  $\mathtt{F}(\mathtt{X},\mathtt{Y})$ and verify that it is
  $\mathtt{Z}$.

Problems:

• 📀 I need to send data size
  $O(\mathtt{X}+\mathtt{Y}+\mathtt{Z})$, i.e. all the trades.
  💾 We want
  $O(\mathtt{X}+\mathtt{Z}+\mathtt{F})$, only merkle roots.
• ⏳ You need to do computations
  $O(\mathtt{F})$.
  ⌛ We want constant gas.
• 🤫 You now know
  $\mathtt{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
  $\mathrm{deg}(P+Q)=max(\mathrm{deg}P,\mathrm{deg}Q)$.
• Multiply
  $\mathrm{deg}(P\times Q)=\mathrm{deg}P+\mathrm{deg}Q$.
• Divide
  $\mathrm{deg}\frac{P}{Q}=\mathrm{deg}P-\mathrm{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

$\mathtt{F}(\mathtt{X},\mathtt{Y})=\mathtt{Z}$ to mean the following:

$$\begin{array}{rlrl}{F}_0& :=\mathtt{X}& F_i& :=F_{i-2}+F_{i-1}\\ F_1& :=\mathtt{Y}& \mathtt{Z}& :=F_{1000}\end{array}$$

---

Computational trace

---

Computation with

$n$ steps and

$w$ registers. The trace

$T$ is a

$n\times w$ table.
Here

$n=1000$ and

$w=2$. Restate algorithm as constraints on

$T_i$

Example:

$\mathtt{X}=3$,

$\mathtt{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{array}{rlrl}{T}_{i+1,0}& =T_{i,1}& T_{i+1,1}& =T_{i,0}+T_{i,1}\end{array}$$

and boundary constraints:

$$\begin{array}{rlrlr}{T}_{0,0}& =\mathtt{X}& T_{999,1}& =\mathtt{Z}& \end{array}$$

---

‟I know

$y$ such that

$f(x,y)=z$.”

$\iff$

‟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\dots 999$.

(Actual implementation uses

$P_j({\omega }^i)=T_{i,j}$ with

$\omega$ 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\dots 999$:

$\iff P_1(i+1)=P_0(i)+P_1(i)$ for

$i=0\dots 999$

$\iff P_1(i+1)-(P_0(i)+P_1(i))=0$ for

$i=0\dots 999$

$\iff Q(x)=P_1(x+1)-(P_0(x)+P_1(x))$ is zero when

$x$ is an integer

$0\dots 999$.

---

$R(x)=(x-0)\cdot (x-1)\cdot (x-2)\cdots (x-999)$ is a polynomial and is zero only when

$x$ is an integer

$0\dots 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{array}{rlrlrl}{T}_{i+1,0}& =T_{i,1}& \Rightarrow & & C_0(x)& =\frac{P_0(x+1)-P_1(x)}{\prod _{[0\dots 998]}^i(x-i)}\\ T_{i+1,1}& =T_{i,0}+T_{i,1}& \Rightarrow & & C_1(x)& =\frac{P_1(x+1)-(P_0(x)+P_1(x))}{\prod _{[0\dots 998]}^i(x-i)}\end{array}$$

Boundary constraints:

$$\begin{array}{rlrlrl}{T}_{0,0}& =X& \Rightarrow & & C_2(x)& =\frac{P_0(x)-X}{x-0}\\ T_{999,1}& =Z& \Rightarrow & & C_3(x)& =\frac{P_1(x)-Z}{x-999}\end{array}$$

---

‟I know

$y$ such that

$f(x,y)=z$.”

$\iff$

‟I know a trace

$T$ such that the constraints hold.”

$\iff$

‟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

$\mathtt{X}$,

$\mathtt{Z}$ and a merkle roots of

$P_0$ and

$P_1$.

You give me random values

${\alpha }_0$,

${\alpha }_1$,

${\alpha }_2$,

${\alpha }_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

$\beta$, we can fold the coefficients and get a polynomial of degree

$\frac{n}{2}$.

$$P^{\prime }(x)=(a_0+a_1\beta )+(a_2+a_3\beta )x+\cdots +(a_{n-1}+a_n\beta )x^{\frac{n}{2}}$$

This can be computed using:

$$P^{\prime }(x)=P(x)+(\frac{\beta }{2x}-\frac{1}{2})(P(x)-P(-x))$$

---

$$P(x)=a_0+a_{1}x+a_2{x}^2+a_3{x}^3\cdots +a_n{x}^n$$

Given a random number

$\beta$, we can fold the coefficients and get a polynomial of degree

$\frac{n}{2}$.

$$P^{\prime }(x)=(a_0+a_1\beta )+(a_2+a_3\beta )x+\cdots +(a_{n-1}{a}_n\beta )x^{\frac{n}{2}}$$

---

$$P^{\prime }(x)=P(x)+(\frac{\beta }{2x}-\frac{1}{2})(P(x)-P(-x))$$

$$\begin{array}{rlrlrlrlrlrlrl}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 & +& 2a_{n-1}{x}^{n-1}\\ \\ \frac{\beta }{2x}(P(x)-P(-x))=& a_1\beta & & & +& a_3\beta x^2& & & +& \cdots & +& a_{n-1}\beta x^{n-2}\\ \\ \frac{1}{2}(P(x)-P(-x))=& a_{1}x& & & +& a_3{x}^3& & & +& \cdots & +& a_{n-1}\beta x^{n-1}\\ \\ (\frac{\beta }{2x}-\frac{1}{2})(P(x)-P(-x))=& a_1\beta & -& a_{1}x& +& a_3\beta x^2& -& a_3{x}^3& +& \cdots & +& a_{n-1}\beta x^{n-1}\end{array}$$

$$P^{\prime }(x)=(a_0+a_1\beta )+(a_2+a_3\beta )x+\cdots +(a_{n-1}+a_n\beta )x^{\frac{n}{2}}$$

---

I compute

$C(x)={\alpha }_0\cdot C_0(x)+{\alpha }_1\cdot C_1(x)+{\alpha }_2\cdot C_2(x)+{\alpha }_3\cdot C_3(x)$.

I give you the merkle root of

$C$ and claim

$\mathrm{deg}C=1024$.

You give me a random value

${𝛽}_0$.

---

I give you the merkle root of

$C^{\prime }$ and claim

$\mathrm{deg}{C}^{\prime }=512$.

You give me a random value

${𝛽}_1$.

---

…

I give you the constant

$C^{″}$.

---

You verify

$C^{″}$ using

$\mathtt{X}$,

$\mathtt{Y}$, the

$\alpha$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.

---