Learn STARK proofs by building one from scratch in Go.
This tutorial teaches you the core concepts of STARK (Scalable Transparent ARgument of Knowledge) through working code. No prior cryptography knowledge required.
- What Problem Does STARK Solve?
- Core Concept: Computation as Polynomials
- Building Block 1: Finite Fields
- Building Block 2: Polynomials
- Building Block 3: Merkle Trees
- The STARK Protocol
- Running the Code
- Limitations of This Implementation
The Problem: Alice claims she computed something correctly (e.g., the 1000th Fibonacci number). Bob wants to verify this without re-doing all 1000 steps.
STARK's Solution: Alice generates a short proof that Bob can verify quickly. If the proof passes, Bob is convinced the computation is correct—without trusting Alice or repeating her work.
Alice (Prover) Bob (Verifier)
───────────────── ─────────────────
Runs computation
↓
Generates proof ──────────────► Verifies proof
(expensive) (cheap & fast)
Key Properties:
- Scalable: Verification time is logarithmic in computation size
- Transparent: No trusted setup required (unlike SNARKs)
- Post-quantum secure: Based on hash functions, not elliptic curves
STARK's fundamental insight: encode computation steps as polynomial evaluations.
A polynomial of degree d is uniquely determined by d+1 points. This means:
- If two polynomials agree on more than
dpoints, they are identical - If a polynomial passes through specific points, it encodes specific data
We want to prove: "I correctly computed 8 steps of Fibonacci starting from F(0)=1, F(1)=1."
The execution trace records each step:
Step | F(n-2) | F(n-1) | F(n)
-----|--------|--------|-----
0 | 0 | 1 | 1
1 | 1 | 1 | 1
2 | 1 | 1 | 2
3 | 1 | 2 | 3
4 | 2 | 3 | 5
5 | 3 | 5 | 8
6 | 5 | 8 | 13
7 | 8 | 13 | 21
The constraint: At every step ≥ 2: F(n) = F(n-1) + F(n-2)
If we encode each column as a polynomial and the constraint holds at all steps, we have a valid Fibonacci computation.
All arithmetic happens in a finite field—a set of numbers where addition, subtraction, multiplication, and division are always well-defined and stay within the set.
- Prevents number overflow (all results stay bounded)
- Every non-zero element has a multiplicative inverse
- Enables exact polynomial arithmetic
// field.go - Core finite field element
const DefaultFieldSize = 3*1<<30 + 1 // Prime: 3 × 2³⁰ + 1
type FieldElement struct {
V int64 // Value (always in range [0, Prime-1])
F Field // The field this element belongs to
}
// All operations return results mod Prime
func (e FieldElement) Add(o FieldElement) FieldElement {
return NewFEWithField((e.V+o.V)%e.F.Prime, e.F)
}
func (e FieldElement) Mul(o FieldElement) FieldElement {
return NewFEWithField((e.V*o.V)%e.F.Prime, e.F)
}
// Inverse via Fermat's Little Theorem: a⁻¹ = a^(p-2) mod p
func (e FieldElement) Inv() FieldElement {
return e.Pow(e.F.Prime - 2)
}Key insight: In a prime field of size p, for any a ≠ 0:
a^(p-1) = 1(Fermat's Little Theorem)- Therefore
a^(p-2) × a = 1, soa^(p-2)is the inverse ofa
Polynomials are the language of STARK. We need:
- Basic operations (add, multiply, divide)
- Evaluation at a point
- Interpolation (finding a polynomial through given points)
Given n points, find the unique polynomial of degree n-1 passing through all of them.
// poly.go - Lagrange interpolation
func Interpolate(pts [][2]int64) Poly {
n := len(pts)
result := Poly{}
for i := 0; i < n; i++ {
xi, yi := pts[i][0], pts[i][1]
// Build basis polynomial: product of (x - xⱼ) for j ≠ i
basis := NewPoly([]int64{1})
denom := NewFE(1)
for j := 0; j < n; j++ {
if i != j {
// basis *= (x - xⱼ)
basis = basis.Mul(NewPoly([]int64{-pts[j][0], 1}))
// denom *= (xᵢ - xⱼ)
denom = denom.Mul(NewFE(xi - pts[j][0]))
}
}
// Scale by yᵢ / denom and add to result
scale := NewFE(yi).Mul(denom.Inv())
result = result.Add(basis.MulScalar(scale.V))
}
return result
}How it works:
- For each point
(xᵢ, yᵢ), build a basis polynomial that is:1atxᵢ0at all otherxⱼ
- Multiply each basis by
yᵢand sum them up
A Merkle tree commits to a list of values with a single hash (the root). Later, you can prove any element's membership with a short path.
Root = H(H01, H23)
/ \
H01 = H(L0,L1) H23 = H(L2,L3)
/ \ / \
L0 L1 L2 L3
// merkle.go - Build tree from leaf hashes
func NewMerkleTree(leafs []int64) *MerkleTree {
hashes := make([]int64, nextPow2(len(leafs)))
copy(hashes, leafs)
nodes := [][]int64{append([]int64{}, hashes...)}
// Build tree bottom-up
for len(hashes) > 1 {
next := make([]int64, len(hashes)/2)
for i := 0; i < len(hashes); i += 2 {
next[i/2] = hash2(hashes[i], hashes[i+1])
}
nodes = append(nodes, next)
hashes = next
}
return &MerkleTree{Root: hashes[0], Nodes: nodes}
}To prove leaf Lᵢ is in the tree, provide sibling hashes along the path to root:
func (t *MerkleTree) Proof(idx int) []int64 {
var proof []int64
for _, level := range t.Nodes {
if len(level) == 1 {
proof = append(proof, level[0])
break
}
// XOR with 1 gets sibling index
proof = append(proof, level[idx^1])
idx >>= 1
}
return proof
}Now we combine everything into a proof system.
// trace.go - Generate Fibonacci trace
func FibonacciTrace(steps int) Trace {
data := make([][]int64, steps)
for i := range data {
switch i {
case 0:
data[i] = []int64{0, 1, 1}
case 1:
data[i] = []int64{1, 1, 1}
default:
f2, f1 := data[i-1][1], data[i-1][2]
data[i] = []int64{f2, f1, f1 + f2}
}
}
return NewTrace(data)
}Purpose: Add redundancy so errors become detectable.
We interpolate each trace column into a polynomial, then evaluate it on a larger domain:
// stark.go - Extend trace via polynomial interpolation
func extendTrace(t Trace, f Field) [][]FieldElement {
n, ext := t.Rows(), t.Rows()*ExtensionFactor // 4x extension
dom := NewDomain(f, ext)
result := make([][]FieldElement, t.Cols)
for c := 0; c < t.Cols; c++ {
// Interpolate column to polynomial
col := t.Col(c)
pts := make([][2]int64, n)
for i, v := range col {
pts[i] = [2]int64{int64(i), v}
}
poly := Interpolate(pts)
// Evaluate on extended domain
result[c] = make([]FieldElement, ext)
for i := 0; i < ext; i++ {
result[c][i] = poly.Eval(dom.Pts[i])
}
}
return result
}Why extend?
- Original trace: 8 points → polynomial of degree 7
- Extended trace: 32 points from the same polynomial
- If prover cheats (uses wrong polynomial), errors appear in ~75% of extended points
Hash each row of the extended trace and build a Merkle tree:
func buildLeafs(ext [][]FieldElement) []int64 {
leafs := make([]int64, len(ext[0]))
for i := range leafs {
var acc int64
for c := range ext {
acc = hash2(acc, ext[c][i].Hash())
}
leafs[i] = acc
}
return leafs
}
// In Prove():
tree := NewMerkleTree(buildLeafs(ext))
commitment := tree.Root // This single value commits to entire traceThe constraint polynomial C(x) encodes: "the Fibonacci rule holds at every step."
For valid computations, C(x) = 0 at all trace points.
func constraintPoly(t Trace, f Field) (Poly, Domain) {
n := t.Rows()
dom := NewDomain(f, n)
pts := make([][2]int64, n)
for i := range pts {
if i < 2 {
pts[i] = [2]int64{int64(i), 0} // No constraint for first 2 steps
} else {
// Residual: F(n) - F(n-1) - F(n-2) should be 0
residual := t.Get(i, 2) - t.Get(i, 1) - t.Get(i, 0)
pts[i] = [2]int64{int64(i), residual}
}
}
return Interpolate(pts), dom
}If C(x) = 0 at all domain points, then C(x) is divisible by the vanishing polynomial:
Z_H(x) = (x - 0)(x - 1)(x - 2)...(x - (n-1))
The quotient polynomial is:
Q(x) = C(x) / Z_H(x)
If C(x) truly vanishes on the domain, Q(x) exists and has low degree. This is the key proof!
func quotientPoly(cp, vp Poly) Poly {
if cp.Degree() < vp.Degree() {
return NewPoly([]int64{0})
}
q, _ := cp.Div(vp)
return q
}FRI (Fast Reed-Solomon IOP of Proximity) proves a polynomial has low degree through iterative folding:
func friFold(vals []FieldElement, beta FieldElement) []FieldElement {
half := len(vals) / 2
out := make([]FieldElement, half)
for i := 0; i < half; i++ {
// Combine pairs: new[i] = vals[i] + β × vals[i + half]
out[i] = vals[i].Add(beta.Mul(vals[i+half]))
}
return out
}Each fold halves the number of evaluations while preserving low-degree structure.
The verifier checks:
- Merkle proofs: Sample values actually came from the committed trace
- Constraint check:
C(x) = 0at sampled points - Quotient check:
C(x) = Q(x) × Z_H(x)at sampled points
func Verify(p *Proof) bool {
// 1. Verify Merkle proofs
for i, pt := range p.SamplePts {
// Recompute leaf hash from provided values
var acc int64
for _, v := range p.SampleVals[i] {
acc = hash2(acc, v.Hash())
}
// Walk up the proof path
for j := 0; j < len(p.MerkleProofs[i])-1; j++ {
acc = hash2(acc, p.MerkleProofs[i][j])
}
if acc != p.Commitment {
return false // Merkle proof failed
}
}
// 2. Verify constraints at sample points
extDom := NewDomain(p.Field, p.TraceSize*ExtensionFactor)
for i, pt := range p.SamplePts {
x := extDom.Pts[pt]
// C(x) should be 0
cv := p.Composition.Eval(x)
if !cv.IsZero() {
return false
}
// C(x) should equal Q(x) × Z_H(x)
if !cv.Eq(p.Quotient.Eval(x).Mul(p.Domain.Vanishing(x))) {
return false
}
}
return true
}In an interactive protocol, the verifier sends random challenges. Fiat-Shamir makes this non-interactive: derive challenges by hashing the transcript.
type Transcript struct{ state int64 }
func (t *Transcript) Absorb(v int64) {
t.state = hash(t.state + (v << 1) | (v >> 63))
}
func (t *Transcript) Challenge(f Field) FieldElement {
t.state = hash(t.state + 0x7f4a7c15)
return NewFEWithField(t.state, f)
}Both prover and verifier derive the same challenges from the same transcript.
go run .Output:
=== STARK Prover (Go) ===
Fibonacci trace:
Step | F(n-2) | F(n-1) | F(n)
-----|--------|--------|-----
0 | 0 | 1 | 1
...
7 | 8 | 13 | 21
Proving: 8 rows x 3 cols
Commitment: 4320595585746542080
Verifying...
Sample 0 (pt 11): merkle OK
Sample 0 (pt 11): constraints OK
...
VALID
Result: VALID
This is an educational implementation, not production-ready:
| Feature | This Code | Production STARK |
|---|---|---|
| Zero-knowledge | ❌ No | ✅ Randomized masking |
| FRI protocol | Simplified folding | Full query phase |
| Domain | Linear {0,1,2,...} | Multiplicative subgroup |
| Hash function | Educational | Cryptographic (Poseidon, etc.) |
| Constraints | Single Fibonacci rule | Full AIR system |
| Security | Demonstrative | 128+ bit security |
What you learned:
- Encoding computation as polynomials
- Low-degree extension for error amplification
- Merkle commitment for efficient verification
- Polynomial constraints and quotient arguments
- FRI for low-degree testing
- Fiat-Shamir for non-interactivity
Next steps for deeper understanding:
- Study the full FRI protocol with query phases
- Learn AIR (Algebraic Intermediate Representation)
- Explore production implementations: StarkWare, Winterfell
┌─────────────────────────────────────────────────────────────┐
│ STARK Proof Flow │
├─────────────────────────────────────────────────────────────┤
│ 1. Execution Trace → Record computation steps │
│ 2. Low Degree Extension → Add redundancy (4x) │
│ 3. Merkle Commitment → Hash to single root │
│ 4. Constraint Poly → Encode rules as C(x) │
│ 5. Quotient Poly → Q(x) = C(x) / Z_H(x) │
│ 6. FRI Folding → Prove low degree │
│ 7. Fiat-Shamir → Derive challenges from transcript │
│ 8. Verification → Check Merkle + constraints │
└─────────────────────────────────────────────────────────────┘
The core insight: A valid computation produces a low-degree polynomial. STARK proves this without revealing the entire polynomial—only through random spot-checks and algebraic structure.
This project is licensed under the BSD 3-Clause License - see the LICENSE file for details.