Ulvetanna Team
April 1, 2024

FRI-Binius: Improved Polynomial Commitments for Binary Towers

In a new research paper, we adapt BaseFold's multivariate FRI commitment scheme to binary towers, significantly reducing proof sizes in Binius.

In November 2023, we published Succinct Arguments over Towers of Binary Fields, our cryptography research that provides the theoretical results underpinning Binius. Today, we released a follow-up work that leverages the Fast Reed-Solomon IOPP (FRI) to construct a new polynomial commitment scheme (PCS) for binary tower fields. Binius initially used a variation of the Brakedown PCS, which yielded proof sizes that are asymptotically of size \(O(\sqrt n)\) for polynomials with \(n\) coefficients. The key innovation in Succinct Arguments over Towers of Binary Fields was to adapt Brakedown to work with Reed–Solomon codes even on polynomials over tiny binary fields like \(\mathbb{F}_2\). This would be impossible without our block-level encoding variant, due to the limitation that the alphabet of a Reed–Solomon must be larger than the codeword length.

In Polylogarithmic Proofs for Multilinears over Binary Towers, we construct a multilinear PCS that combines ideas from the binary field FRI protocol of Ben-Sasson et al., the BaseFold multilinear PCS of Zeilberger, Chen, and Fisch, and the Binius block-level encoding technique due to Ulvetanna's research team. By reducing the cost of PCS verification, the new argument, which we call FRI-Binius, will enable more efficient recursive proof composition. Our paper's contributions are

  1. We draw a new connection between the Novel Polynomial Basis additive NTT and binary field FRI. Based on that connection, we prescribe a specific and convenient choice of mathematical objects left generic by the original FRI paper.
  2. We adapt the BaseFold multilinear PCS to binary towers with block-level encoding, thereby supporting tiny binary fields like \(\mathbb{F}_2\) with no embedding overhead during the commitment phase.
  3. We show how the new PCS is a generalization of the Brakedown-style PCS, allowing for a rich trade-off spectrum between prover and verifier efficiency.
  4. We present improved proof sizes for PCS proofs for a range of polynomial sizes. The size of an opening proof for a polynomial over \(\mathbb{F}_2\) with \(2^{32}\) coefficients is now 3.5 MiB with FRI-Binius compared to 11.5 MiB with the original PCS.

Follow our blog and @UlvetannaHQ on X (formerly Twitter) for future updates. We are actively looking for more exceptional engineers and computer scientists to help us push the limits of verifiable computing. Please see our careers page if you want to join us on this journey!

RELATED POSTS

Ulvetanna Team

|

April 1, 2024

Ulvetanna Team
April 1, 2024

FRI-Binius: Improved Polynomial Commitments for Binary Towers

In a new research paper, we adapt BaseFold's multivariate FRI commitment scheme to binary towers, significantly reducing proof sizes in Binius.

READ ARTICLE

Ulvetanna Team

|

January 22, 2024

Ulvetanna Team
January 23, 2024

Elliptic Curve ZK-Proof Acceleration on AMD Versal

We present a novel system demo accelerating elliptic curve cryptography on AMD's Versal heterogeneous compute platform.

READ ARTICLE

Ulvetanna Team

|

November 20, 2023

Ulvetanna Team
November 20, 2023

Binius: a Hardware-Optimized SNARK

In a new research paper, we demonstrate a performance-optimized approach to SNARK construction based on towers of binary fields.

READ ARTICLE