Commitment

As we've already hinted at, commitment is a cryptographic procedure which plays a role akin to "dropping something in a secure dropbox". Once a thing has been committed to, then it can't be touched or changed. This is useful when we want to "bind" the prover to a choice, before later generating random challenges to test the validity of his choice. If he could retroactively modify his choice after seeing our challenges, the protocol would stop being secure. Thus it's essential that once the thing has been dropped into the box, it can't be changed.

In our setting, the "thing" getting dropped into the box is a multilinear polynomial (or a batch of them). Moreover, we want more than just a commitment scheme: we also want a scheme that supports evaluation. That is, once the prover has (figuratively) dropped a polynomial into the secure box, we want a way for the verifier to later securely learn the evaluation of that polynomial at points of his choosing.

This is more-or-less a restatement of the definition of the multilinear polynomial oracle machine. Here, we describe how that machine gets instantiated—specifically, we describe how the prover should drop a polynomial in the box.

Subsection Directory

This subsection contains the following pages:

• Error-Correcting Codes. Here, we drop a primer on error-correcting codes, and why they're useful in SNARKs like Binius.
• The Additive NTT. Here, explain Binius's key code—the binary-field Reed–Solomon code—as well as a crucial algorithm, called the additive NTT, that lets us execute that code's encoding procedure efficiently (this algorithm is due to Lin, Chung and Han [LCH14]).
• The Procedure. Having dealt with the preliminaries, here we record our commitment scheme, including various practicalities around Merklization.
• Batched Commitment. Here, we describe how to generalize our commitment procedure so as to make it support the simultaneous commitment of many polynomials.