Muhammed Ali Bingol 23rd June 2025

References

Introduction

STARK (Scalable Transparent Arguments of Knowledge) is a cryptographic protocol for proving computational integrity. STARKs operate by first encoding computations into algebraic execution traces represented by polynomials. These polynomials undergo low-degree extensions, allowing the verifier to conduct probabilistic low-degree tests efficiently. By employing hash functions (typically Merkle trees) combined with interactive challenges, STARKs achieve transparent verification without reliance on trusted setups and EC pairings.

• Part I: Statement, LDE & Commitment
• Part II: Polynomial Constraints
• Part III: FRI Commitment
• Part IV: The Proof

🌟Part I: Statement, LDE & Commitment

Problem Statement: We consider a sequence defined over a finite field $\mathbb{F}_p$ by the recurrence

Example (FibonacciSq sequence mod prime):

$a_{n+2} = a_{n+1}^2 + a^2_n \pmod{p}$ where $p=3⋅2^{30}+1=3221225473$

Statement to Prove:

• There exists a secret initial value $x$ (witness) such that starting from $a_0 = 1$ and $a_1 = x$, the above sequence $a_{1022} = 2338775057$ (mod $p$).
• As the prover we know that the value of $x =$ $3141592$.

LDE (Low Degree Extension): Helps encode our sequence.

Done in 3 steps: 1) Generate input 2) Interpolate 3) Extend domain

• Generate Input and interpolate:
  • This is what our data looks like: $a_0,a_1,a_2,....,a_{1022}$. This sequence is called the trace, as it records the path of computation.
  • These represent the first 1023 values in the Fibonacci square sequence with $a₀$ and $a₁$ set to 0 and $3141592$, respectively.
  • Next, choose another sequence of numbers: $y₀, y₁, y₂, ..., y₁₀₂₂$
  • For our case, chose: $1, g, g², g³, ..., g¹⁰²²$ as the y-coordinates that will map to our trace values $f(g^i) = a_i, \quad 0 \leq i \leq 1022$.
  • To visualize this:
• Extend domain
  • Pick a larger evaluation domain (8x)
  • $x'_j = {w \cdot h^j \mid j=0,1,\ldots,8191}$ where w, h - elements from F
  • We then evaluate $f(x'_j)$ at every point which produces a sequence of $M=8192$ field values: $f(x_j') = f(w), f(w · h¹), f(w · h²), …, f(w · h⁸¹⁹¹)$ (Reed-Solomon encoding.)
  • To visualize this:
• Commitment: Now, we need to commit to our LDE. The commitment will allow the prover to later reveal a small subset of specific values from $C$ as requested by the verifier, without needing to send the entire huge list.
  • Construct a Merkle tree with leaves as $C = (f(w \cdot h^j))$
  • The standard commitment used in STARKs is a Merkle tree.