Open this lesson in your favourite AI. It'll walk you through the why, explain the demo, and quiz you on the try-it list.
Schwartz–Zippel is the single most important theorem behind every probabilistic proof system. It says: if are two polynomials of degree at most over , then a uniformly random satisfies with probability at most . For and that's a soundness error of — 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.
Schwartz–Zippel (univariate form): if has degree at most and is not the zero polynomial, then for any . Hence for random , . Used as a fingerprint: , so testing equality at a random point fails with probability .
Use these three in order. Each builds on the one before.
In one paragraph, state Schwartz–Zippel and explain in plain English why it underpins probabilistic equality checking. Use the analogy of comparing two long files by hashing them at one random offset.
Walk me step by step through the proof of Schwartz–Zippel for univariate polynomials — base case, inductive step, and the use of the fact that $\deg(P) \geq |\text{roots}(P)|$ over a field. Where does the field assumption enter?
SNARK soundness errors are typically stated as $O(d/|\mathbb{F}|)$. In a real protocol like Plonk, $d$ is the size of the circuit (millions). What concrete prime sizes does this force, and why does this drive the field choice for systems targeting 100+ bits of security?
// 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))
}
go run main.go