From 0 to Bi(ge)nius: field extensions Thanks a lot to Oba, Nuliel, Hyunmin, Nico and Jim for the review ❤️Feel free to DM me on Twitter: @0xteddav if you find mistakes in this article or if you have any question. Binius is a new way to build SNARKs by Benjamin Diamond and Jim Posen (from Irreducible). It uses “towers of binary fields” (yes, it sounds complicated but it should become obvious by the end of this article) and a variation of the Hyperplonk IOP over binary fields, combined with the Brakedown polynomial commitment scheme for better prover efficiency.Here’s the paper: Succinct Arguments over Towers of Binary Fields.If you didn’t understand anything of what I just said, don’t worry. I will explain it all in simple terms so that the proof system is -hopefully- clear by the end of the series 🙏This first part will start with the basics. We’re going to look at what “small fields” are, then we’ll get to field extensions and finally reach the “towers”. Small fields: Goldilocks, Mersenne Big fields (think $>2^{256}$) are used in elliptic-curve-based SNARKs in order to ensure high levels of bit security.On the other hand, hash-based STARKs can afford to use smaller fields (think $2^{64}$ or even $2^{32}$), leading to significant gains in prover efficiency.But the crucial part in verification is sampling a random number r from the field and checking “some” equality at r. If the field is too small, the prover could trick the verifier. That’s where extension fields come in: most of the operations will be done in the small fields while some operations are moved to the larger extension field. We will get into the details later in the article.I’m going to assume that you know what a prime field is. If you don’t, stop here and Google it 🔍What we call “small field” is basically just taking a smaller prime (yes, $2^{64}$ is “small”) and reducing every number modulo that prime.For example, the “Goldilocks field” (I don’t know why it’s named this way) uses $p=2^{64}-2^{32}+1$ while “Mersenne31” uses $p=2^{31}-1$.When doing modular math using these fields, any number will be less than 64 and 31 bits for Goldilocks and Mersenne31, respectively. Why small fields? The idea is simple: make things faster!Generating a ZK proof takes a lot of computational power: due to the modular math operations, to interpolate, and evaluate polynomials. Researchers have been trying to improve that.Small fields speed things up by: