Paper 2024/504

Polylogarithmic Proofs for Multilinears over Binary Towers

Abstract

The use of small fields has come to typify the design of modern, production-oriented SNARKs. In this work, we treat multilinear polynomial commitment over tiny fields. A tiny-field polynomial—in the nomenclature of Diamond and Posen (EUROCRYPT '25)—is defined over a field that has fewer elements than the polynomial itself has coefficients. We focus on multilinears over the field with just two elements. In this work, we generically reduce the problem of tiny-field commitment to that of large-field commitment. We introduce a sumcheck-based compiler—called "ring-switching"—which, upon being fed a multilinear polynomial commitment scheme over some large extension field, yields a further scheme over that field's ground field. The resulting scheme lacks embedding overhead, in that its commitment cost, on each input, equals that of the large-field scheme on each input of identical size (in bits). Its evaluation protocol's overhead is linear for the prover and logarithmic for the verifier, and is essentially optimal. Instantiating our ring-switching reduction on the BaseFold (CRYPTO '24) large-field multilinear polynomial commitment scheme—or more precisely on a characteristic-2 adaptation of that scheme that we develop at length—we obtain an extremely fast polynomial commitment scheme for bit-valued multilinears. Our scheme outperforms its state-of-the-art peers, a fact we demonstrate experimentally.

Note: Recompute performance benchmarks; further improve exposition.