Binius

fri-pcs starks snark

Things needed in order to create a SNARK:

• field: binary fields
• pcs: small field polynomial commitment using concatenated codes
• arithmetisation: virtual polynomial construction in multilinear setting similar to hyperplonk

Let’s write what i think about binius, it’s use case, and the efficiency that it promises.

Historically, proof systems based on IOPs have gone through various changes:

• starting with GGPR13, pinocchio that introduced R1CS
• then, came the PCP world of Groth16 based on pairings, with one of most efficient verifier that I know of.
• Bulletproofs got introduced to the world that completely removed the use of trusted setups based PCS, field-agnostic, truly ZK, but with just one caveat: linear verifier
• Came the world of PLONK [GWC19], it’s arithmetisation, world of KZG10, it’s modularity and arithmetisation allowed so many additional things on top: custom gates, lookup tables
• On another side of the coin, there was brewing a wildly theoretical yet promising idea of STARKs (BBSHR18) with their own world of arithmetisation called AIR, although very similar to plonkish arithmetisation used in Halo2, with a completely separate idea of IOPP, i.e. proofs of proximity based on RS codes. Although proof sizes were large, mainly due to logarithmic size of merkle path proofs.

Binius main ace is using binary field extensions. Arithmetic of binary fields is so rich and flexible, it’s addition is just XOR, and multiplication can be done efficiently using algorithm similar to karatsuba multiplication.

Let’s start with understanding field used in binius and it’s advantages over classical prime field and their extensions:

Binary Fields

Now, binary fields are an interesting area of research in implementation phase because it has multiple ways of representation, and each representation has different arithmetic asymptotic complexity.

field ${\mathbb{F}}_2$:

• addition: XOR
• multiplication: for ${\mathbb{F}}_2$, it’s just repeated xor.
  • for extension fields, can be done efficiently using an algorithm similar to karatsuba-multiplication

Two ways of representing $\text{GF}(2^k)$:

• univariate basis - two ways of representing in univariate basis as well, namely:
  • polynomial basis: elements are represented as degree k-1 polynomial $A_{k-1}{\alpha }^{k-1}+\cdots +A_1\alpha +A_0$ by equivalence class ${\mathbb{F}}_2/f(x)$, where f(x) is any irreducible in the kth power.
  • normal basis: elements are represented as taking powers of an element from the field
• multilinear basis - there’s one other way of representing elements, i.e. Multilinear basis, where elements are represented by monomials: $1,X_0,X_1\cdot X_0,X_2\cdot X_1\cdot X_0,\dots ,X_0\dots X_{l-1}$, with each coefficient in ${\mathbb{F}}_2$.

Binary field towers

Binius realises binary extension field using towers formalised in Weidemann et al..

Basic idea is to derive sequence of polynomial rings inductively

• start with ${\tau }_0={\mathbb{F}}_2=\{0,1\}$
• set ${\tau }_1={\tau }_0[X_0]/(X_0^2+X_0+1)={\mathbb{F}}_{2^2}$, namely $\{0,1,X_0,1+X_0\}$.
• set ${\tau }_2={\tau }_1[X_1]/(X_1^2+X_0{X}_1+1)={\mathbb{F}}_{2^{2^2}}$
• continue this further with ${\tau }_0\subset {\tau }_1\subset \cdots \subset {\tau }_{i-1}\subset {\tau }_i={\tau }_{i-1}[X_{i-1}]/f_{i-1}(X_{i-1})$, where $f_{i-1}(X_{i-1})=X_{i-1}^2+X_{i-1}{X}_{i-2}+1$ is an irreducible in ${\tau }_i$

Weidemann showed that $f_{i-1}[X_{i-1}]$ is irreducible for each $i>1$, and ${\tau }_i$ form a field isomorphic to ${\mathbb{F}}_{2^{2^i}}$ and, by construction, ${\tau }_i={\tau }_{i-1}[X_{i-1}]$, ${\tau }_{i-1}$ is a subfield of ${\tau }_i$ as constant polynomials (due to equivalence class). Ring construction for ${\tau }_i$ happens as:

$$\begin{array}{c}{\tau }_i={\mathbb{F}}_2[X_0,\dots ,X_{i-1}]/(X_0^2+X_0+1,\dots ,X_{i-1}^2+X_{i-1}{X}_{i-2}+1)\end{array}$$

Notation used in binius: ${\mathcal{T}}_l:={\mathcal{T}}_{\iota -1}[X_{\iota -1}]/X_{\iota -1}^2+X_{\iota -1}{X}_{\iota -2}+1$, with initial ${\mathcal{T}}_0:={\mathbb{F}}_2$ and ${\mathcal{T}}_1:={\mathbb{F}}_2[X_0]/X_0^2+X_0+1$. This gets us a tower construction where ${\mathcal{T}}_{\iota }$ is isomorphic to ${\mathbb{F}}_{2^{2^{\iota }}}$and ${\mathcal{T}}_0\subset {\mathcal{T}}_1\subset \dots {\mathcal{T}}_{\iota }$. Monomials $1,X_0,X_0\cdot X_1,\dots ,X_0\dots X_{\iota -1}$ represent the basis of ${\mathcal{T}}_{\iota }$ as ${\mathbb{F}}_2$ vector space, i.e. $\forall v\in {\mathcal{B}}_{\iota }$, thus, $v$ is represented as boolean vector $\{v_0,v_1,\dots ,v_{\iota -1}\}$, and give ${\beta }_v={\prod }_{i=0}^{\iota -1}(v_i{X}_i+(1-v_i))$.

For example: take $\iota =3$, $v$ represents all the basis vector for monomials in multilinear basis of ${\mathcal{T}}_l$, i.e.

• $(0,0,0)\to 0$: ${\beta }_0=1$
• $(0,0,1)\to 1$: ${\beta }_1=X_0$
• …
• $(1,1,1)\to 7$: ${\beta }_7=X_0{X}_1{X}_2$

Main advantage of Binary field extensions:

• efficient embeddings
• small-to-large multiplication: multiplying a ${\mathcal{T}}_{\iota }$ with ${\mathcal{T}}_{\iota +k}$ takes only $2^k\text{Uptheta}(2^{\log 3\cdot \iota })$

Now, we have a field, using that we can derive polynomials in multilinear basis, let’s understand PCS needed to commit to these polynomials:

Error Correcting codes

• A code $[n,k,d]$ represents code of block length $n$ with message length $k$ such that any two code $v_1,v_2$ are $d$ distant to each other.
• linear code over field $K$ is a k-dimensional linear subspace $C\subset K^n$
• $C^{\prime }s$ $m-$fold interleaved code for any $m\ge 1$, defined as subset $C^m\subset (K^n{)}^m$
  • represents length-n block code over alphabet $K^m$, represented as rows of matrices in $K^{m\times n}$
• RS code: $R{S}_{K,S}[n,k]$, $S=\{s_0,s_1,\dots ,s_{n-1}\}\subset K$ where the code $C$ is defined as $\{(p(s_0),p(s_1),\dots ,p(s_{n-1}))|p(X)\in K[X{]}^{<K}\}$
• Problem with RS codes, is that it requires alphabet of large length

why RS codes are not suitable for binary fields?

Extension Code

let $C:=[n,k,d]\subset K^n$ be a code with generator matrix $M\in K^{n\times k}$, and a $K-$vector space $V$ over $K$.

So, message space $\mathcal{M}$ for $C$ is a $K^k$ with alphabet in $K^n$. Representing a vector space $V$, containing each element as message from $C$. Extension code $\hat{C}\subset V^n$ is the image of map $V^k\to V^n:t\mapsto M.t$.

Let $\eta$ be the the dimension for $V$ over $K$, then an element in vector space $V^k$, can be defined as $\{v_0,v_1,\dots ,v_{\eta -1}\}$, where $v_i$ itself belongs to ${\mathcal{M}}_C$, and $\hat{C}$ represents matrix multiplication of each element in $v_i$ to generator matrix of $C$.

Basic PCS

consists of five methods: $\mathsf{Setup},\mathsf{Commit},\mathsf{Open},\mathsf{Prove},\mathsf{Verify}$:

• $\mathsf{Setup}(1^{\lambda },l,K)$: field $K$, choose $l=l_0+l_1$, write $m_0:=2^{l_0}$, and $m_1:=2^{l_1}$, return code $C:[n,m_1,d]$ where $n=2^{\mathcal{O}(l)}$
• $\mathsf{Commit}(C,K,t)$: evaluate $t(X_0,\dots ,X_{l-1})$ at ${\left\{0,1\right\}}^l$ as lagrange basis coefficients: $t=(t_0,\dots ,t_{2^l-1})$.
  • express $t_i$ into matrix of dimension: $m_0\times m_1$.
  • encode matrix $(m_i{)}_{i=0}^{m_0-1}$ row wise into $(u_i{)}_{i=0}^{m_0-1}$ with row length ${\rho }^{-1}{m}_1$
  • output a merkle root committing to each encoded column of matrix $(u_i{)}_{i=0}^{m_0-1}$
• $\mathsf{Open}()$
• $\mathsf{Prove}(r=\{r_0,\dots ,r_{l-1}\})$
• $\mathsf{Verify}(\pi )$

Concatenated Codes

small field PCS

polynomial IOP

define Polynomial oracle:

• $\text{submit}(\mathbf{\iota },l,t)$: $\mathcal{P}$ submit a multilinear polynomial $t\in {\mathcal{T}}_{\iota }[X_0,\dots ,X_{l-1}{]}^{\le 1}$, outputs $(\text{receipt},\iota ,l,[t])$ to $\mathcal{P},\mathcal{V}$, where $[t]$ is a unique handle/identifier for polynomial $t$.
• $\text{query}([t],r)$: from $\mathcal{V}$, $r\in {\mathcal{T}}_{\iota }$, outputs $\text{evaluate}(t(r_0,r_1,\dots ,r_{l-1}))$

define polynomial predicate as boolean valued function for a $\mu -$ary $l-$variate polynomial over ${\mathcal{T}}_{\iota }$: ${\text{Upphi}}_{\iota ,l}:{\mathcal{T}}_{\iota }[X_0,X_1,\dots ,X_{l-1}{]}^{\mu }\to \{0,1\}$

Uses hyperplonk’s polynomial predicates as:

• $\text{Query}(\iota ,l\in N,s\in {\mathcal{T}}_{\tau },r\in {\mathcal{T}}_{\tau }^l):T\mapsto T(r_0,r_1,\dots r_{l-1})=s$
• $\text{Sum}(e\in {\mathcal{T}}_{\iota }):T\mapsto T(v{)}_{v\in {\mathcal{B}}_l}=e$
• $\text{Zero}:T\mapsto \forall v\in {\mathcal{B}}_l:T(v)=0$, basically for all v in basis, T evaluates to 0.
• $\text{Product}(\iota ,l):(T,U)\mapsto {\prod }_{v\in {\mathcal{B}}_l}T(v)={\prod }_{v\in {\mathcal{B}}_l}U(v)$ conditioned on the rule that neither evaluates to zero on the basis.
• $\text{Multiset}(\mu )$: for $2.\mu -$ary multiset: $(T_0,T_1,\dots ,T_{\mu -1},U_0,U_1,\dots ,U_{\mu -1})\mapsto \{(T_0(v),T_1(v),\dots ,T_{\mu -1}(v))|v\in {\mathcal{B}}_l\}=\{(U_0(v),U_1(v),\dots ,U_{\mu -1}(v))|v\in {\mathcal{B}}_l\}$
• $\text{Permutation}(\mu ,\sigma \in (\{0,\dots ,\mu -1\}\times {\mathcal{B}}_l))$: $\sigma$ is a bijection $\{0,\dots ,\mu -1\}\times {\mathcal{B}}_l\to \{0,\dots ,\mu -1\}\times {\mathcal{B}}_l$ such that $(T_0,T_1,\dots ,T_{\mu -1}):T_{i^{\prime }}(v^{\prime })=T_i(v)$, where $\sigma (i,v)=(i^{\prime },v^{\prime })$
• $\text{Lookup}(T,U)\mapsto \forall v\in {\mathcal{B}}_l\exists v^{\prime }\in {\mathcal{B}}_l:U(v)=T(v^{\prime })$

Virtual Polynomial: an l-variate virtual polynomial contains a list of handles $[t_0],\dots ,[t_{\mu -1}]$, each $t_i$ over ${\mathcal{T}}_{\iota }$, and an arithmetic circuit with gates representing $l_i-$ary gate $t_i(X_0,\dots ,X_{l_{l_i-1}})$. This means gates can have arity greater than 2.

For example: for a polynomial $T[X_0,X_1,X_2]$ containing three polynomials $t_0,t_1,t_2$, each having arity $l_i$. Let arity be:

• $t_0$: 2-ary gate: $t_0(X_0,X_1)=X_0\cdot X_1$
• $t_1$: 1-ary gate: $t_1(X_0)=X_0^2$
• $t_2$: 3-ary gate: $t_3(X_0,X_1,X_2)=X_0+X_1-X_2$

Now, putting these polynomials in an arithmetic circuit:

flowchart TB
X0-->t0
X1-->t0
t0--X_0*X_1-->t2
X2-->t1
X2-->t2("t2=t0(X0,X1)-t1(X2)+X2")
t1--X_2^2-->t2
t2-->out(out=X_0*X_1+X_2^2-X_2)

Polynomial protocol: takes list of virtual polynomials $[T_0],\dots ,[T_{\mu -1}]$, and a $\mu -$ary predicate ${\text{Upphi}}_{\iota ,l}$

• evaluation protocol: $\text{Upphi}$ as ${\mathsf{Query}}_{\iota ,l}(r,s)$
• composition polynomial: take list of $l-$variate handles $[t_0],\dots ,[t_{\mu -1}]$, and a $\mu$-variate composition polynomial $g\in {\mathcal{T}}_{\iota }[X_0,\dots ,X_{\mu -1}]$ such that $T:=g(t_0(X_0,\dots ,X_{l-1},\dots ,t_{\mu -1}(X_0,\dots ,X_{l-1}))$.

References

• FRI
• STARKs
• Binary extension fields
  • Multiplication in Binary Fields
  • Bit-Serial and Bit-Parallel Montgomery Multiplication and Squaring over $GF(2^m)$
• Brakedown
• Linear codes
• Hyperplonk
• Binius
• Vitalik’s binius post and implementation