Polynomial commitment

The polynomial commitment is the building block behind modern SNARKs. The prover encodes a computation as a polynomial and the verifier checks the relations by evaluating it at random points, relying on the Schwartz-Zippel lemma (two distinct degree-d polynomials agree on at most d points). The commitment scheme is what makes that check succinct, binding (you cannot change the polynomial after committing) and, depending on the construction, hiding.

The choice of scheme defines the properties of the whole proof system. KZG (Kate, Zaverucha and Goldberg, ASIACRYPT 2010) gives constant-size commitments and proofs, relies on elliptic-curve pairings and requires a trusted setup; it powers PLONK and the SNARKs deployed on Ethereum. FRI (Ben-Sasson et al., ICALP 2018) builds on Reed-Solomon codes and hash functions, is transparent and resistant to quantum attacks in exchange for larger proofs, and powers STARKs.

Real cases confirm this. EIP-4844 (proto-danksharding), live on Ethereum since the Dencun upgrade in March 2024, uses KZG commitments over the data blobs. PLONK (Gabizon, Williamson and Ciobotaru, 2019) adopts KZG as its commitment scheme, while StarkWare and Starknet build their STARKs on FRI. For anyone designing on-chain infrastructure, the polynomial commitment is the piece that sets the cost, transparency and security profile of the entire system.