Vortex polynomial commitment

 

Commitment

Vortex has much in common with Ligero (frankly speaking, it has been built using Ligero idea). So, imagine we have a list of polynomials $f_0,\dots,f_{k-1}$. We want to commit them and evaluate at the same point at the same time. We describe each polynomial as vector $a_i$ where

\[f_i(x) = \sum_{j=0}^{n-1} x^j\cdot a_{i,j}\]

For simplicity, let’s define the interpolation function $Int$ that works as follows (it takes the vector elements as polynomial coefficients and evaluates it at point $x$):

\[Int_{a_i}(x) = f_i(x)\]

Then, we organize these vectors into the matrix $W \in \mathbb{F}^{k\times n}$. Image

Same as in Ligero, we extend our matrix with additional columns by replacing each word $a_i$ with its codeword $a_i’$, resulting in a matrix $W’ \in \mathbb{F}^{k\times m}$, where $m > n$.

Then we hash each column, receiving $m$ values of $h_i$ — we will use these values as our commitment to the polynomials $f_i$. Image

Open

Given input $r$ from the verifier, the prover responds with values $y_0,\dots,y_{k-1}$ where

\[y_i = f_i(x)\]

Prove & Verification

  • The verifier samples a challenge $\beta$
  • The prover responds with $u = B\cdot W$, where $B = (1, \beta, \beta^1,\dots,\beta^{k-1})$. Note that naturally, each element in $u$ equals to the sum of corresponding polynomials’ coefficients over corresponding weight – polynomial $i$ will be multiplied by $\beta^i$. Image
  • Then, the verifier samples $t$ indexes $q_1,\dots,q_t$ where $q_i \in [m]$
  • The prover opens the corresponding columns $s_1,\dots,s_t$ from the matrix $W’$ Image
  • The verifier computes the Reed-Solomon encoding of $u$ named $u’$.
  • The verifier checks:
    • $hash(s_i) == h_{q_i}$ for each $i\in [t]$
    • $B\cdot s_i == u’_{q_i}$ → this follows from the linearity of Reed-Solomon
  • The verifier checks that $Int_u(x) = B\cdot y$. This check follows from the following observation: $a\cdot Int_c(x) = Int_{a\cdot c}(x)$, so:
    • $1 \cdot Int_{w_0}(x) = 1 \cdot y_0$ → $Int_{u_0}(x) = 1 \cdot y_1$
    • $\beta \cdot Int_{w_1}(x) = \beta \cdot y_1$ → $Int_{u_1}(x) = \beta \cdot y_1$
    • $\beta^2 \cdot Int_{w_2}(x) = \beta^2 \cdot y_2$ → $Int_{u_2}(x) = \beta^2 \cdot y_2$
    • etc.

The parameter $t$ is selected according to the security parameters.