Learn about: Binius - A proof system on binary fields
Recently, Vitalik Buterin wrote on binary fields and their potential to generate zero-knowledge proofs.
Binary fields are finite fields with characteristic equal to two.
We can view them as polynomials whose coefficients can only take the values 0 and 1, so 1 + x^2 + x^6 are elements in some binary field but not 5 + x!
We can also associate them with bitstrings and define operations over them so that they behave like fields.
The simplest binary field is the integers modulo 2. The addition operation is simply binary XOR and multiplication is the binary AND.
We can make bigger binary fields by considering polynomials with coefficients in the binary field modulo an irreducible polynominal (e.g, 1 + x + x^2 or 1 + x + x^3 + x^4 + x^8).
The 1st allows us to make a field over bitstring of size 2 and the 2nd, over bitstring of size 8.
Binius builds field extensions using a towered approach: we start from the simplest binary field and build a degree two extension over it. Then, we build another binary extension over the new field, using the irreducible polynomial 1 + xy + y^2.
We continue creating new fields from the previous one using the irreducible polynomial 1 + y z + z^2.
This comes with some advantages when we consider Binius’s polynomial commitment scheme.
The commitment scheme is based on Brakedown, a hash-based polynomial commitment scheme.
It is very fast, at the expense of larger proof sizes (on the order of the square root of the degree of the polynomial).
By using an efficient packing scheme and leveraging an additive fast Fourier transform algorithm for encoding, Binius can commit to polynomials really fast!
If you want to learn more, check out the LambdaClass introductory posts on Binius: here and here.
Stay tuned: 🐦 Twitter | 🗨️ Telegram | 👾 Discord | 🌐 Website | 🌌 Galxe | 📝 Manifesto
