WHIR from Scratch

A hands-on, 8-phase implementation of the WHIR polynomial commitment scheme in Rust, built from first principles using Arkworks.

Each phase is a standalone module with detailed explanatory comments and tests. The code is meant to be read linearly — later phases import from earlier ones.

Phases

Phase	Module	Topic	Key Concepts
1	phase1_fields	Field Arithmetic	BN254 scalar field, roots of unity, cosets, Lagrange interpolation
2	phase2_ntt	Number Theoretic Transform	Horner's method, Cooley-Tukey butterfly NTT/INTT, coset NTT
3	phase3_reed_solomon	Reed-Solomon Codes	RS encoding via coset NTT, minimum distance, decoding, proximity
4	phase4_merkle	Merkle Trees	SHA-256 hashing, tree construction, opening proofs, batch verification
5	phase5_multilinear	Multilinear Polynomials	Boolean hypercube, MLE, equality polynomial, partial evaluation (folding)
6	phase6_sumcheck	Sumcheck Protocol	Linear sumcheck, quadratic sumcheck for inner products
7	phase7_folding	Codeword Folding	Polynomial folding, codeword folding, fold consistency, proximity testing
8	phase8_whir	WHIR Protocol	RS commitment, equality weights, WHIR prover and verifier

Prerequisites

• Rust (stable)

Running

# Run all tests
cargo test -- --nocapture

# Run a specific phase
cargo test phase1 -- --nocapture
cargo test phase8 -- --nocapture

Conventions

• Little-endian bit ordering throughout: index i = b_0 + 2*b_1 + 4*b_2 + ... where b_0 is the least significant bit. Even indices have x_0 = 0, odd indices have x_0 = 1.
• Coset domains: RS codewords are evaluated over g * H_n (a coset of the multiplicative subgroup), not the subgroup itself.
• Simplified WHIR: This implements the core protocol (commit, sumcheck, fold, query, verify). Production WHIR additionally includes OOD sampling, proof-of-work, batching, and Fiat-Shamir via a cryptographic sponge.

References

• WHIR: Reed-Solomon Proximity Testing with Super-Fast Verification
• Arkworks

Thank you claude on designing a phase by phase exercises