Paper 2026/1438

Vela and Carina: Fast Pairing-Based Multilinear Polynomial Commitments from Reciprocal Polynomials

Abstract

Pairing-based multilinear polynomial commitments offer succinct verification for sum-check-based proof systems, but existing schemes trade prover work against proof size and verifier cost. Building on Mercury's representation of a multilinear evaluation as the constant coefficient of a (reciprocal) Laurent polynomial, we construct two schemes with different performance trade-offs. Vela uses inversion symmetry to derive a half-length auxiliary polynomial and opens two polynomials at $z$ and $z^{-1}$ with one univariate KZG proof. Vela has a $2\mathbb{G}_1+3\mathbb{F}$ proof, a two-term pairing check, and approximately $2N$ opening MSM scalars, at the cost of $O(N\log N)$ field operations on the prover side. Carina applies the same constant-term reduction once in each coordinate and jointly proves evaluation claims for the committed bivariate polynomial and two auxiliary polynomials with one opening at four bivariate points. The four points form a grid, allowing Carina to restructure the opening equation to save verifier works and proof size. Carina has a $4\mathbb{G}_1+8\mathbb{F}$ proof, a three-term pairing check, and $O(N)$ field operations plus exactly $N+2\sqrt{N}-6$ MSM works on the prover side. We prove perfect evaluation completeness, computational commitment binding, and knowledge soundness in the AGM and ROM, with explicit random-oracle error bounds under a falsifiable bilinear $q$-type DLOG assumption. Our curve-generic Rust implementation also provides common implementations of six pairing-based baselines. On BLS12-381 at $\mu=20$, Vela gives the smallest measured proof (200 bytes, 1.88x smaller than the next smallest) and the lowest verification median, 2.06 ms. Carina's opening median remains in the same leading tier as the prover-oriented mKZG and CHOPIN implementations, while its 452-byte proof and 2.67 ms verification median improve on both. Compared with the verifier-oriented Mercury, Carina's opening median is 1.96x faster at the cost of a 0.48 ms verification slowdown.