The Shift Reduction

The shift reduction is a key internal routine in Binius64. It is a common reduction target of both the AND and MUL reductions.

The shift reduction takes, as input, evaluation claims on the oblong-multilinearizations of the prover's constraint arrays. The entire shift reduction is designed to process claims of this form, and in particular to reduce them to further evaluation claims, now directly on the witness.

We carry out this program in the following sub-pages.

• Mathematizing Constraint Arrays. In order to have any hope of assessing the validity of evaluation claims on the oblong-multilinearizations of the prover's constraint arrays, we need to express those objects in terms of the prover's actual witness. We devote this entire page to achieving that task.
• The Sumchecks. Here, our task is to process the prover's evaluation claims using an efficient sumcheck. We show that there is a hidden two-phase structure in our sumcheck; the resulting protocol is very vaguely Spartan-like [Set20], but more complicated.
• Prover Implementation. Here, we explain our efficient prover implementation of the above protocol. It's not obvious how the tables of values required within our sumchecks should be prepared efficiently, and in particular, in a way that leverages the constraint system's sparsity.