Skip to content

The Cryptographic Layer

Succinctly verifying evaluation claims on multilinear polynomials

One of the most useful conceptual distinctions we work with is the PIOP–PCS boundary. Everything we do in Binius can be roughly classified in this way—i.e., in terms of whether it lives "above" or "below" the boundary.

Above the boundary—in PIOP land—we talk abstractly about committing to small-field polynomials, and also about querying them. We assume the existence of an ideal, abstract third-party oracle machine, which "sits on" the polynomials the prover commits to, for safe-keeping—and later evaluates these on-command for the verifier. This site thus far has taken place above that boundary. Our entire goal thus far has been first to mathematize an M3 instance of interest, and then steadily reduce its associated mathematical claims to evaluation claims.

Until this point, we have proceeded as if the verifier could evaluate committed polynomials directly, with the aid of a polynomial oracle machine. Of course, the reality is more complicated. We don't have abstract third-party oracles in real life; rather, we have complex protocols that let us act as if we did.

In this site section, we progress beneath the PIOP–PCS boundary, into the polynomial commitment schem. Here, we describe actual mechanisms by which the prover might commit, and the verifier later evaluate, multilinear polynomials over tiny binary fields. In this section, we work in the IOP model, an expedient we have already justified.

Section Directory

This section contains the following subsections:

  • Commitment. Here, we describe our commitment procedure: an algorithm that takes as input a small-field multilinear, and returns a "digest" of that multilinear—which, moreover, the verifier can later use as input to a secure evaluation protocol. This procedure takes place before any of the PIOP steps do.
  • Ring-Switching. Ring-switching is a key mathematical technique used in Binius. It lets us reduce the problem of evaluating a small-field multilinear (this is exactly the kind of claim that the reduction layer outputs) to another, more tractable problem: that of evaluating a sum claim pertaining to a product of large-field multilinears.
  • Batched Evaluation. Here, we describe perhaps the most technically involved procedure in the whole of Binius. This procedure, which refines and generalizes the main protocol of [DP24], simultaneously evaluates a number of sum claims (of the form output by our ring-switching protocol above). It evaluates these in "one shot"—i.e., by simultaneously handling both their sumcheck and evaluation components (this works even for sum claims on differently-sized polynomials).