Skip to content

Zerocheck

A vanishing argument for compositions of small-field multilinears

As we explain in detail in the arithmetization section of this site, the main reduction targets of M3 are channel-balancing claims and vanishing claims. In this site subsection, we introduce the zerocheck, our key tool for processing vanishing claims.

Vanishing claims entail, by definition, that for some particular table whose columns are multilinears, a certain multivariate polynomial (with as many variables as that table has columns) vanishes identically over that table's rows.

The classical tool for these sorts of claims is the zerocheck protocol, as is more-or-less explained in HyperPlonk. (Zerocheck itself is a thin wrapper around sumcheck.) In our setting, the polynomials we're interested in zerochecking are in general defined over tiny fields. It is imperative, for efficiency's sake, that we exploit this advantage; that is, we must adopt a zerocheck protocol which exploits our polynomials' various small fields of definition. This research area was initiated by Gruen's Some Improvements for the PIOP for ZeroCheck.

We note that the multilinears over which our zerochecks operate are themselves often virtual. Our zerocheck, upon terminating, will thus output evaluation claims which themselves pertain to virtual polynomials, in general. In order to reduce these claims to further claims about committed (i.e., so-called "raw") polynomials, we will need to perform further reductions. Binius contains logic designed to unroll these latter reductions, which themselves often mandate further sumchecks.

Subsection Directory

This subsection contains the following pages:

  • Review. Here, we drop a crash course on the basic zerocheck, mainly for use as a reference.
  • Univariate Skip. The univariate skip—an advanced zerocheck variant, which we use in Binius—is designed to secure additional efficiency gains in the setting of small-field polynomials.
  • The Rest. Here, we treat the remainder of the small-field zerocheck, which takes place after the univariate skip finishes. This looks a lot like a standard, non-rectangular zerocheck, with a catch: the final evaluation claims will be rectangular.