Multilinear Polynomial Commitments

[mratsim]

Production-grade commitments

KZG is implemented and IPA is WIP for verkle trees (#275).

• FRI commitments https://eprint.iacr.org/2020/654

Multilinear

The SNARKs world is moving to multilinear polynomial commitment schemes (multilinear PCS), in particular to remove the need of large FFTs that require a lot of memory, and scale with O(n log n).

Commiting to a multilinear polynomial

These schemes can be composed on top of an univariate PCS like KZG10:

• Gemini: https://eprint.iacr.org/2022/420
• LogUp+: https://eprint.iacr.org/2023/1284
• Zeromorph: https://eprint.iacr.org/2023/917

Multilinear PCS

• BCG20: https://eprint.iacr.org/2020/1426
• Brakedown, Ligero & Shockwave: https://eprint.iacr.org/2021/1043

[mratsim]

A very promising one: Binius

We introduce an efficient SNARK for towers of binary fields. Adapting Brakedown (CRYPTO '23), we construct a multilinear polynomial commitment scheme suitable for polynomials over tiny fields, including that with 2 elements. Our commitment scheme, unlike those of previous works, treats small-field polynomials with zero embedding overhead. We further introduce binary-field adaptations of HyperPlonk's (EUROCRYPT '23) product and permutation checks, as well as of Lasso's lookup. Our scheme's binary PLONKish variant captures standard hash functions—like Keccak-256 and Grøstl—extremely efficiently. With recourse to thorough performance benchmarks, we argue that our scheme can efficiently generate precisely those Keccak-256-proofs which critically underlie modern efforts to scale Ethereum.

https://eprint.iacr.org/2023/1784
https://gitlab.com/UlvetannaOSS/binius