Polynomial Commitments
"Dubbed “magic math” by Buterin, polynomial commitments are being eyed as a way to verify the state of the network at low computational cost, a key goal of the future network [of Ethereum].
Polynomial commitments are similar to the polynomials we all came to learn and love in elementary school: a math expression with both variables and coefficients (i.e., Y=2X).
Buterin describes polynomial commitments as “a sort of ‘hash’ of some polynomial P(x) with the property that you can perform arithmetic checks on hashes.” The original paper on polynomial commitments, meanwhile, synthesizes the math scheme as “six algorithms” that show proof of an event occurring with as little computing data as possible.
“We suggest replacing Merkle trees by magic math called “polynomial commitments” to accumulate blockchain state,” Buterin said in the Ethereum Foundation blog post. “Benefits include reducing the size of stateless client witnesses (excluding contract code and state data) to near zero.”
(For the mathematically inclined, a three-part series on polynomial commitments hosted by Eth 2.0’s Justin Drake can be found here.)
The current Merkle tree setup takes about 0.5 MB per transaction. Ryan estimates polynomial commitment schemes would reduce the weight of state proofs to between 0.001 and 0.01 MB. For a network that recently averages around 700,000 transactions per day, the savings in terms of data computation add up.
Multiple projects outside of Ethereum also lean on polynomial commitments in their own way, including Zcash’s zero-knowledge proof, Halo."
