Alin Tomescu

Multilinear polynomial commitment schemes (MLE PCS)

 
  • Mar 25, 2026

tl;dr: A catalog of polynomial commitment schemes for multilinear polynomials (i.e., multivariate polynomials where each variable has degree at most 1). These are the workhorse of modern SNARKs based on the sumcheck protocol.

$ \def\pcs{\mathsf{PCS}} \def\kgen{\mathsf{Gen}} \def\comm{\mathsf{Commit}} \def\open{\mathsf{Open}} \def\verify{\mathsf{Verify}} \def\eval{\mathsf{Eval}} $

Introduction

A polynomial commitment scheme (PCS) lets a prover commit to a polynomial $f$ and later prove that $f(\vec{r}) = v$ for a point $\vec{r}$ chosen by the verifier.

A multilinear polynomial in $\mu$ variables is a polynomial $f(x_1, \ldots, x_\mu) \in \F[x_1, \ldots, x_\mu]$ where each variable $x_i$ has individual degree at most 1. Any function $g : \{0,1\}^\mu \rightarrow \F$ has a unique multilinear extension (MLE): the unique multilinear polynomial $\tilde{g}$ satisfying $\tilde{g}(\vec{b}) = g(\vec{b})$ for all $\vec{b} \in \{0,1\}^\mu$.

Preliminaries

We use $\term{n} = 2^\term{\mu}$ to denote the number of evaluations of the multilinear polynomial (i.e., the number of coefficients) and $\term{\lambda}$ to denote the security parameter.

All complexities in the tables below are stated in big-$O$ notation (omitted for brevity).

Error-correcting codes

The hash-based schemes rely on error-correcting codes (ECCs) for messages of length $k$ and codewords of length $N$.

The two key parameters of a code are:

  • Relative rate $\rho = k/N$
    • Higher rate means less redundancy.
  • Relative distance $\delta = d/N$, where $d$ is the minimum distance of the code
    • i.e., the minimum Hamming distance between any two distinct codewords
    • Higher distance means more errors can be detected.

The code families used in the table below are:

  • RS: Reed-Solomon codes. Maximum distance separable (MDS) codes achieving $\delta = 1 - \rho$. Encoding requires $O(n \log n)$ via FFT.
  • Expander / Spielman: Linear-time encodable codes based on expander graphs[^Spie96]. Achieve constant $\rho$ and $\delta$, but with small concrete distance.
  • Random foldable: Codes with recursive folding structure (generalizing RS), supporting FRI-style protocols over arbitrary fields1.
  • RAA: Repeat-Accumulate-Accumulate codes. Linear-time encodable codes combining repetition, permutation, and two accumulation steps.
  • LDPC: Low-density parity-check codes. Sparse linear codes with linear-time encoding.
  • LT codes: Any linear-time encodable code (e.g., expander, RAA, LDPC).

Known MLE PCS schemes

Complexities may be off in many places. (This is Claude reading the papers & filling in the tables, with me correcting only some of them.) Assumptions may be off too.

Hash-based / code-based (transparent, plausibly post-quantum)

Scheme Year Code $\rho$ $\delta$ CRS size Prover Verifier Proof size ZK
Ligero2 2017 RS (interleaved) $\rho$3 $1-\rho$ $1$ $n$ $\lambda\sqrt{n}$ $\lambda\sqrt{n}$  
Ligero++4 2020 RS (interleaved) $\rho$3 $1-\rho$ $1$ $n \log n$ $\lambda\log^2 n$ $\lambda\log^2 n$  
Brakedown5 2021 Expander (Spielman) $\approx 0.65$ $\approx 0.04$ $1$ $n$ $\lambda\sqrt{n}$ $\lambda\sqrt{n}$  
Orion6$^,$7 2022 Spielman (tensor) $1/4$ $\approx 0.055$ $1$ $n$ $\lambda\log^2 n$ $\lambda\log^2 n$  
BaseFold1 2023 Random foldable $1/c$8 $\approx 1-1/c$ $1$ $n \log n$ $\lambda\log^2 n$ $\lambda\log^2 n$  
DeepFold9 2024 RS $\rho$3 $1-\rho$ $1$ $n \log n$ $\lambda\log^2 n$ $\lambda\log^2 n$ ✓
WHIR10 2024 RS (constrained) $\rho$3 $1-\rho$ $1$ $n \log n$ $\lambda\log^2 n$ $\lambda\log^2 n$  
Blaze11 2024 RAA $1/r$12 $\approx 0.19$ $1$ $n$ $\lambda\log^2 n$ $\lambda\log^2 n$  
FICS13 2025 Any LT code $\rho_0$14 $\delta_0$14 $1$ $n$ $\lambda\log n \log \log n$ $\lambda\log n \log \log n$  
Ligerito15 2025 Any linear code $\rho_0$14 $\delta_0$14 $1$ $n \log n$ $\frac{\lambda\log^2 n}{\log \log n}$ $\frac{\lambda\log^2 n}{\log \log n}$  
Bolt16 2026 Sketched (LDPC) $\rho$17 $\delta(\rho)$17 $1$ $n$ $\lambda\log n \log\log n$ $\lambda\log n \log\log n$  

Ligero2 encodes evaluations as a matrix and uses interleaved Reed-Solomon proximity tests.

Ligero++4 composes Ligero’s interleaved code testing with an inner product argument (from Aurora) to reduce proof size from $O(\sqrt{n})$ to polylogarithmic; combined with GKR for structured polynomial evaluation, it yields a PCS with $O(\log^2 n)$ verifier.

Brakedown5 achieves linear-time proving using expander-based codes and is the first built system with a linear-time prover; it is also field-agnostic.

Orion6 reduces proof size from $O(\sqrt{n})$ to $O(\log^2 n)$ via proof composition (“code switching”).

BaseFold1 generalizes FRI-style folding to arbitrary foldable codes, enabling field-agnostic MLE commitments.

DeepFold9 adapts FRI to the list decoding radius setting, achieving $\approx 3\times$ smaller proofs than unique-decoding-based schemes like BaseFold.

WHIR10 is an IOPP for constrained Reed-Solomon codes with super-fast verification (hundreds of microseconds); it directly supports multilinear polynomial queries and serves as a drop-in replacement for FRI/BaseFold.

Blaze11 achieves linear-time proving over binary extension fields using Repeat-Accumulate-Accumulate (RAA) codes; concretely faster than all prior schemes for large polynomials ($\ge 2^{25}$) with much smaller proofs than Brakedown.

FICS13 is an IOPP for multilinear evaluation that achieves linear prover time with improved query complexity $O(\lambda \cdot \log\log n + \log n)$, compiled into a PCS via BCS.

Ligerito15 uses Ligero’s matrix-vector product protocol with a partial sumcheck, supporting any linear code with efficiently-evaluable generator matrix rows.

Bolt16 introduces sketched codes (composing random LDPCs) with $(3+\varepsilon) \cdot n$ field additions plus $(1+\varepsilon) \cdot n$ Merkle hashing for commitment. The code supports any rate close to 1, is systematic, and has constant distance. Bolt is $\approx 1.34\times$ faster than Brakedown and $\approx 1.41\times$ faster than Blaze for commitment, with $\approx 2\times$ smaller proofs than Brakedown.

Lattice-based (transparent, post-quantum)

Build a comparison table for lattice-based MLE PCS schemes. Known schemes include: Wee-Wu18 (2022; succinct vector, polynomial, and functional commitments from lattices), Albrecht et al.19 (2022; lattice-based SNARKs with a PCS component), Cini et al.20 (2024; post-quantum PCS with fast verification and transparent setup), Greyhound21 (2024; fast polynomial commitments from lattices), and Jindo22 (2026; practical lattice-based PCS for ZK arguments).

Discrete-log-based (transparent)

Scheme Year Assumption CRS size Prover Verifier Proof size ZK
Hyrax23 2018 DL $\sqrt{n}$ $n$ $\sqrt{n}$ $\sqrt{n}$  

Hyrax23 uses a “split-and-fold” approach over Pedersen commitments with $O(\sqrt{n})$ generators. No trusted setup is needed.

Pairing-based (transparent)

Scheme Year Assumption CRS size Prover Verifier Proof size ZK
Kopis-PC24 2020 SXDH $n$ $n$ $\sqrt{n}$ $\log n$  
Dory25 2020 SXDH $n$ $n$ $\log n$ $\log n$  

These schemes use pairings but require no trusted setup – the CRS consists of random group elements in $\mathbb{G}_1$ and $\mathbb{G}_2$.

Kopis-PC24 extends Hyrax by using doubly-homomorphic commitments (via SXDH pairings) to compress the commitment to $O(1)$ size and the proof to $O(\log n)$; verification remains $O(\sqrt{n})$.

Dory25 achieves logarithmic verification using inner-pairing-product arguments.

Pairing-based (trusted setup)

Scheme Year Assumption CRS size Prover Verifier Proof size ZK
PST26 2013 $q$-SBDH + pairings $n$ $n$ $\log{n}$ $\log{n}$  
Libra27 2019 $q$-SBDH + ext. PKE $n$ $n$ $\log n$ $\log n$ ✓
Gemini28 2022 pairings $n$ $n$ $\log n$ $\log n$  
Orion+29 2022 CRHF + expander codes + KZG $\sqrt{n}$ $n$ $\log n$ $\log n$  
Zeromorph30 2023 pairings $n$ $n$ $\log n$ $\log n$ ✓
Testudo31 2023 pairings $\sqrt{n}$ $n$ $\log n$ $\log n$  
KZH-232 2025 pairings $n$ $n$ $\sqrt{n}$ $\sqrt{n}$  
KZH-$\log n$32 2025 pairings $n$ $n$ $\log n$ $\log n$  
Mercury33 2025 pairings $n$ $n$ (no FFTs) $\log n$ $1$  
Samaritan34 2025 pairings $n$ $n$ $\log n$ $1$  

PST26 is the first multilinear PCS, reducing multilinear evaluation proofs to pairing checks.

Libra27 defines a zkVPD (zero-knowledge verifiable polynomial delegation) scheme, which is an MLE PCS with zero-knowledge. The underlying PCS is PST-based (via Zhang et al.), but Libra shows that adding ZK requires only a small masking polynomial with $O(d\ell)$ random coefficients (instead of an exponential-sized one), yielding an efficient zkVPD. The one-time trusted setup depends only on the input size $n$, not the circuit.

Gemini28 reduces multilinear evaluations to univariate KZG35 claims via “split-and-fold,” yielding elastic SNARKs where the prover can trade time for space.

Orion+29 (from the HyperPlonk paper) improves on Orion by replacing Merkle-tree batch openings with KZG-based multilinear PCS batch openings, shrinking proofs from $O(\log^2 n)$ to $O(\log n)$ while keeping the linear-time prover; the KZG SRS is only $O(\sqrt{n})$ since it operates on the column hashes.

Zeromorph30 also reduces to univariate KZG commitments via a multilinear-to-univariate isomorphism.

Testudo31 combines PST with inner pairing product arguments (MIPP) to achieve $O(\log n)$ proof size and verification with only $O(\sqrt{n})$ SRS size. The prover operates on $\sqrt{n}$-sized polynomials (vs. $n$-sized in PST). Testudo proposes wrapping the PCS verification inside a Groth16 circuit, compressing the final proof to $O(1)$.

KZH32 combines ideas from Hyrax and KZG, representing polynomial evaluation as a matrix-vector multiplication; the commitment is a single $\mathbb{G}_1$ element. KZH-2 requires only $O(\sqrt{n})$ opening time and proof size. KZH-$\log n$ achieves $O(\log n)$ proof size and verifier time but with quasilinear commitment time; it avoids target group elements (unlike Dory).

Mercury33 and Samaritan34 (concurrent work) achieve constant proof size with a linear-time prover and no prover FFTs; both provide generic frameworks for transforming univariate PCS into multilinear PCS.

Groups-of-unknown-order-based (transparent)

Scheme Year Assumption CRS size Prover Verifier Proof size ZK
DARK36 2019 strong RSA + adaptive root $1$ $n \log n$ $\log n$ $\log n$  
Dew37 2022 GGM (class groups) $1$ $n^3$ $\log n$ $1$ ✓
DewTwo38 2025 strong RSA + modular consistency $1$ $n \log n$ $\log n$ $\log \log n$ ✓

DARK36 constructs a PCS for $\mu$-variate degree-$d$ polynomials from integer commitments in groups of unknown order; for multilinear polynomials ($d=1$), proofs have $O(\log n)$ size.

Dew37 achieves constant-size evaluation proofs from class groups but has cubic prover time.

DewTwo38 significantly improves on Dew with quasi-linear prover time, $O(\log \log n)$ proof size, and security under falsifiable assumptions (not the GGM). Concretely, DewTwo proofs are under 4.5KB for $n \le 2^{30}$.

Known SNARK frameworks from MLE PCSs

Libra27 is also a SNARK framework that combines its zkVPD (listed above) with a linear-time GKR prover and the sumcheck protocol, yielding the first ZKP with optimal $O(C)$ prover time and succinct $O(d \log C)$ proof size and verification for depth-$d$ log-space uniform circuits of size $C$.

Spartan39 later showed how to build SNARKs from any MLE PCS + sumcheck (without GKR), driving much of the demand for efficient MLE PCS constructions.

HyperPLONK29 adapts PLONK to the multilinear setting, replacing univariate polynomial IOPs with multilinear ones and using the sumcheck protocol for high-degree custom gates, achieving a linear-time prover.

References

For cited works, see below

  1. BaseFold: Efficient Field-Agnostic Polynomial Commitment Schemes from Foldable Codes, by Hadas Zeilberger and Binyi Chen and Ben Fisch, in Cryptology ePrint Archive, Paper 2023/1705, 2023, [URL] ↩ ↩2 ↩3

  2. Ligero: Lightweight Sublinear Arguments Without a Trusted Setup, by Scott Ames and Carmit Hazay and Yuval Ishai and Muthuramakrishnan Venkitasubramaniam, in Proceedings of the 2017 {ACM} {SIGSAC} Conference on Computer and Communications Security, 2017, [URL] ↩ ↩2

  3. For RS-based schemes, the rate $\rho \in (0,1)$ is a tunable parameter (typically $\rho = 1/2$); distance is $\delta = 1-\rho$ (MDS). ↩ ↩2 ↩3 ↩4

  4. Ligero$\mathplus$$\mathplus$: A New Optimized Sublinear {IOP, by Rishabh Bhadauria and Zhiyong Fang and Carmit Hazay and Muthuramakrishnan Venkitasubramaniam and Tiancheng Xie and Yupeng Zhang, in Proceedings of the 2020 {ACM} {SIGSAC} Conference on Computer and Communications Security, 2020, [URL] ↩ ↩2

  5. Brakedown: Linear-time and post-quantum SNARKs for R1CS, by Alexander Golovnev and Jonathan Lee and Srinath Setty and Justin Thaler and Riad S. Wahby, in Cryptology ePrint Archive, Paper 2021/1043, 2021, [URL] ↩ ↩2

  6. Orion: Zero Knowledge Proof with Linear Prover Time, by Tiancheng Xie and Yupeng Zhang and Dawn Song, in Cryptology ePrint Archive, Paper 2022/1010, 2022, [URL] ↩ ↩2

  7. A Crack in the Firmament: Restoring Soundness of the Orion Proof System and More, by Thomas den Hollander and Daniel Slamanig, in Cryptology {ePrint} Archive, Paper 2024/1164, 2024, [URL] ↩

  8. $c > 1$ is the code blow-up factor; e.g., $c = 2$ gives $\rho = 1/2$ and $\delta \approx 1/2$. ↩

  9. DeepFold}: Efficient Multilinear Polynomial Commitment from Reed-Solomon Code and Its Application to Zero-knowledge Proofs, by Yanpei Guo and Xuanming Liu and Kexi Huang and Wenjie Qu and Tianyang Tao and Jiaheng Zhang, in Cryptology {ePrint} Archive, Paper 2024/1595, 2024, [URL] ↩ ↩2

  10. WHIR: Reed–Solomon Proximity Testing with Super-Fast Verification, by Gal Arnon and Alessandro Chiesa and Giacomo Fenzi and Eylon Yogev, in Cryptology {ePrint} Archive, Paper 2024/1586, 2024, [URL] ↩ ↩2

  11. Blaze: Fast {SNARKs} from Interleaved {RAA} Codes, by Martijn Brehm and Binyi Chen and Ben Fisch and Nicolas Resch and Ron D. Rothblum and Hadas Zeilberger, in Cryptology {ePrint} Archive, Paper 2024/1609, 2024, [URL] ↩ ↩2

  12. $r \ge 1$ is the repetition factor; e.g., $r = 4$ gives $\rho = 1/4$ and $\delta \approx 0.19$ at that rate. ↩

  13. FICS} and {FACS}: Fast {IOPPs} and Accumulation via Code-Switching, by Anubhav Baweja and Pratyush Mishra and Tushar Mopuri and Matan Shtepel, in Cryptology {ePrint} Archive, Paper 2025/737, 2025, [URL] ↩ ↩2

  14. Depends on the chosen LT code; any code with constant rate $\rho_0$ and constant distance $\delta_0$ suffices. ↩ ↩2 ↩3 ↩4

  15. Ligerito: A Small and Concretely Fast Polynomial Commitment Scheme, by Andrija Novakovic and Guillermo Angeris, in Cryptology {ePrint} Archive, Paper 2025/1187, 2025, [URL] ↩ ↩2

  16. Bolt: Faster {SNARKs} from Sketched Codes, by Kobi Gurkan and Andrija Novakovic and Ron D. Rothblum, in Cryptology {ePrint} Archive, Paper 2026/310, 2026, [URL] ↩ ↩2

  17. Bolt supports any desired rate $\rho \in (0,1)$; the distance $\delta(\rho) > 0$ is a constant depending on $\rho$. ↩ ↩2

  18. Succinct Vector, Polynomial, and Functional Commitments from Lattices, by Hoeteck Wee and David J. Wu, in Cryptology ePrint Archive, Paper 2022/1515, 2022, [URL] ↩

  19. Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable, by Martin R. Albrecht and Valerio Cini and Russell W. F. Lai and Giulio Malavolta and Sri AravindaKrishnan Thyagarajan, in Cryptology ePrint Archive, Paper 2022/941, 2022, [URL] ↩

  20. Polynomial Commitments from Lattices: Post-Quantum Security, Fast Verification and Transparent Setup, by Valerio Cini and Giulio Malavolta and Ngoc Khanh Nguyen and Hoeteck Wee, in Cryptology {ePrint} Archive, Paper 2024/281, 2024, [URL] ↩

  21. Greyhound: Fast Polynomial Commitments from Lattices, by Ngoc Khanh Nguyen and Gregor Seiler, in Cryptology {ePrint} Archive, Paper 2024/1293, 2024, [URL] ↩

  22. Jindo: Practical Lattice-Based Polynomial Commitment for Zero-Knowledge Arguments, by Intak Hwang and Hyeonbum Lee and Jinyeong Seo and Yongsoo Song, in Cryptology {ePrint} Archive, Paper 2026/044, 2026, [URL] ↩

  23. Doubly-Efficient zkSNARKs Without Trusted Setup, by R. S. Wahby and I. Tzialla and A. Shelat and J. Thaler and M. Walfish, in 2018 IEEE Symposium on Security and Privacy (SP), 2018 ↩ ↩2

  24. Quarks: Quadruple-efficient transparent {zkSNARKs, by Srinath Setty and Jonathan Lee, in Cryptology {ePrint} Archive, Paper 2020/1275, 2020, [URL] ↩ ↩2

  25. Dory: Efficient, Transparent arguments for Generalised Inner Products and Polynomial Commitments, by Jonathan Lee, in Cryptology ePrint Archive, Report 2020/1274, 2020, [URL] ↩ ↩2

  26. Signatures of Correct Computation, by Papamanthou, Charalampos and Shi, Elaine and Tamassia, Roberto, in TCC’13, 2013 ↩ ↩2

  27. Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation, by Tiancheng Xie and Jiaheng Zhang and Yupeng Zhang and Charalampos Papamanthou and Dawn Song, in Cryptology {ePrint} Archive, Paper 2019/317, 2019, [URL] ↩ ↩2 ↩3

  28. Gemini: Elastic SNARKs for Diverse Environments, by Jonathan Bootle and Alessandro Chiesa and Yuncong Hu and Michele Orrù, in Cryptology ePrint Archive, Report 2022/420, 2022, [URL] ↩ ↩2

  29. HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates, by Binyi Chen and Benedikt Bünz and Dan Boneh and Zhenfei Zhang, in Cryptology ePrint Archive, Paper 2022/1355, 2022, [URL] ↩ ↩2 ↩3

  30. Zeromorph: Zero-Knowledge Multilinear-Evaluation Proofs from Homomorphic Univariate Commitments, by Tohru Kohrita and Patrick Towa, in Cryptology ePrint Archive, Paper 2023/917, 2023, [URL] ↩ ↩2

  31. Testudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup, by Matteo Campanelli and Nicolas Gailly and Rosario Gennaro and Philipp Jovanovic and Mara Mihali and Justin Thaler, in Cryptology ePrint Archive, Paper 2023/961, 2023, [URL] ↩ ↩2

  32. KZH}-Fold: Accountable Voting from Sublinear Accumulation, by George Kadianakis and Arantxa Zapico and Hossein Hafezi and Benedikt Bünz, in Cryptology {ePrint} Archive, Paper 2025/144, 2025, [URL] ↩ ↩2 ↩3

  33. MERCURY}: A multilinear Polynomial Commitment Scheme with constant proof size and no prover {FFTs, by Liam Eagen and Ariel Gabizon, in Cryptology {ePrint} Archive, Paper 2025/385, 2025, [URL] ↩ ↩2

  34. Samaritan: Linear-time Prover {SNARK} from New Multilinear Polynomial Commitments, by Chaya Ganesh and Sikhar Patranabis and Nitin Singh, in Cryptology {ePrint} Archive, Paper 2025/419, 2025, [URL] ↩ ↩2

  35. Constant-Size Commitments to Polynomials and Their Applications, by Kate, Aniket and Zaverucha, Gregory M. and Goldberg, Ian, in ASIACRYPT’10, 2010 ↩

  36. Transparent SNARKs from DARK Compilers, by Benedikt Bünz and Ben Fisch and Alan Szepieniec, in Cryptology ePrint Archive, Report 2019/1229, 2019, [URL] ↩ ↩2

  37. Dew: Transparent Constant-sized zkSNARKs, by Arasu Arun and Chaya Ganesh and Satya Lokam and Tushar Mopuri and Sriram Sridhar, in Cryptology ePrint Archive, Report 2022/419, 2022, [URL] ↩ ↩2

  38. DewTwo}: a transparent {PCS} with quasi-linear prover, logarithmic verifier and 4.{5KB} proofs from falsifiable assumptions, by Benedikt Bünz and Tushar Mopuri and Alireza Shirzad and Sriram Sridhar, in Cryptology {ePrint} Archive, Paper 2025/129, 2025, [URL] ↩ ↩2

  39. Spartan: Efficient and general-purpose zkSNARKs without trusted setup, by Srinath Setty, in Cryptology ePrint Archive, Report 2019/550, 2019, [URL] ↩

Search