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 group work against proof size and verifier cost. Building on Mercury's representation of a multilinear evaluation as the constant coefficient of a 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; the fourth evaluation is not transmitted but recovered from the Laurent evaluation identity. It 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. 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 grid opening. For $N=2^{\mu}$ and $b=\sqrt{N}$, it has a $4\mathbb{G}_1+8\mathbb{F}$ proof, a three-term pairing check, $O(N)$ field operations, and exactly $N+2b-6$ opening MSM scalars. 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 a 2.16 ms verifier within single-run noise of the lowest measured. Carina's opening performance is in the same leading tier as the prover-oriented mKZG and CHOPIN implementations, while its 452-byte proof and 2.81 ms verifier improve on both. Compared with the verifier-oriented Mercury, Carina roughly halves opening time at the cost of a modest verifier slowdown.