Capstok — learn by doing

Why this matters

Schwartz–Zippel is the single most important theorem behind every probabilistic proof system. It says: if $P \neq Q$ are two polynomials of degree at most $d$ over $\mathbb{F}_p$ , then a uniformly random $r \in \mathbb{F}_p$ satisfies $P(r) = Q(r)$ with probability at most $d/p$ . For $d \sim 2^{20}$ and $p \sim 2^{256}$ that's a soundness error of $2^{-236}$ — astronomically small. This single fact is why the verifier can read just one point of a polynomial and be statistically certain the prover isn't lying. Without Schwartz–Zippel there are no SNARKs, no STARKs, no commitment-based ZK. Internalise the bound and the proof.

Demo

Schwartz–Zippel (univariate form): if $P \in \mathbb{F}[X]$ has degree at most $d$ and is not the zero polynomial, then $|\{r \in S : P(r) = 0\}| \leq d$ for any . Hence for random , . Used as a fingerprint: , so testing equality at a random point fails with probability .

P \in \mathbb{F}[X],\ \deg P \leq d,\ P \not\equiv 0 \implies \Pr_{r \xleftarrow{\mathdollar } S}[P(r) = 0] \leq \frac{d}{|S|}.

Try it yourself

Run the snippet and confirm the empirical agreement rate is consistent with the bound $100 / 1{,}000{,}003 \approx 10^{-4}$ . (You should see something like 0–3 collisions in 100,000 draws.)
Increase the polynomial degree to 500 and rerun. Confirm the empirical rate scales linearly with degree, matching the $d/p$ bound.
Reduce $p$ to a 12-bit prime (e.g. 4093). With degree-100 polynomials, the bound becomes $\sim 0.024$ , which the empirical estimate should now visibly approach.

References

// main.go
package main

import (
	"fmt"
	"math/rand"
)

const p = 1_000_003 // a 20-bit prime

func peval(coeffs []int64, x int64) int64 {
	var acc int64 = 0
	for i := len(coeffs) - 1; i >= 0; i-- {
		acc = (acc*x+coeffs[i]) % p
	}
	return acc
}

func main() {
	// Two distinct degree-100 polynomials
	rng := rand.New(rand.NewSource(1))
	P := make([]int64, 101)
	for i := range P {
		P[i] = rng.Int63n(p)
	}
	Q := make([]int64, 101)
	copy(Q, P)
	Q[42] = (Q[42] + 1) % p // tweak one coefficient -> P != Q

	// Probability of agreement at a random point
	N := 100_000
	agreements := 0
	evalRng := rand.New(rand.NewSource(2))
	for i := 0; i < N; i++ {
		r := evalRng.Int63n(p)
		if peval(P, r) == peval(Q, r) {
			agreements++
		}
	}
	fmt.Printf("Empirical agreement rate : %f\n", float64(agreements)/float64(N))
	fmt.Printf("Schwartz-Zippel bound    : %f\n", float64(100)/float64(p))
}

Run: go run main.go

Catch a Lying Prover With One Random Point (Schwartz-Zippel)

Why this matters

Demo

Try it yourself

References