Mathematical Background

In this section, we record various mathematical preliminaries. This section should be viewed more as a dictionary than as a novel: you don't need to read it cover-to-cover. It's just here so that we can point to it later.

Throughout, we abbreviate $\mathcal{B}_\ell \coloneqq \{0, 1\}^\ell$ for the $\ell$-dimensional boolean cube.

Section Directory

This section contains the following subsections.

• Binary Towers. Here, we record preliminaries on the algebraic objects known as fields. We also discuss towers of binary fields, the field construction we use throughout Binius.
• Multilinear Polynomials. Binius deals throughout with multivariate polynomials, and in particular multilinear ones. Here, we explain these objects, as well as multilinear extensions.
• The PIOP and IOP Models. In cryptography—and in particular, in Binius—it is often convenient to formulate, and operate within, certain idealized models of computation in which specific oracles exist. Here, we explain the idealized models we work with.
• The Sumcheck. The sumcheck protocol is perhaps our single, most important fundamental building block. Here, we sketch the protocol and its proof of security.