3. Method 1

This method biases towards a faster opening time, and requires roughly half the compute of FastVerify. See A. Optimizations for more details.

For the following, the notation of BDFG21 is followed, namely

• $[k]=\{1,\dots ,k\}$
• For a set of points $(x_1,\dots ,x_k)$ and a polynomial $f_i$, $r_i$ is the unique degree $k-1$ polynomial such that $\forall j{r}_i(x_j)=f_i(x_j)$

M1Open

#![allow(unused)]
fn main() {
M1Open(transcript: Transcript, 
       evals: Vec<Vec<Scalar>>, 
       polys: Vec<Polynomial>, 
       point_set_index: usize) -> Proof
}

Let the polynomials be $(f_1,\dots ,f_t)$ and the points be $(x_1,\dots x_k)$

1. Check that evals has length $t$ and each element of evals has length $k$
2. Transcribes the following to the Merlin transcript
   • each of the evals row by row with the utf-8 message open evals
   • each of the points in order with the utf-8 message open points
3. Constructs $\gamma \in \mathbb{F}$ by
   • Reading SCALAR_SIZE bytes from transcript with utf-8 message open gamma
   • Intepreting the bytes as an integer in big endian modded by the modulus of the scalar field
4. Computing $$f_{\mathtt{sum}}=\sum _{i\in [t]}{\gamma }^{i-1}{f}_i$$
5. Polynomial divide to get $q=f_{\mathtt{sum}}/Z_{point\_set\_index}$, discarding the remainer
6. Compute $[q(x){]}_1$ and serialize in compressed form.

M1Verify

#![allow(unused)]
fn main() {
M1Verify(transcript: Transcript, 
         commits: Vec<Commitment>, 
         evals: Vec<Vec<Scalar>>,
         proof: Proof,
         point_set_index: usize) -> bool
}

Let the evals be $((y_{1,1},\dots y_{1,k}),\dots (y_{t,1},\dots y_{t,k}))$, commits be $(c_1,\dots ,c_t)$, and the points be $(z_1,\dots z_k)$. Commit $c_i$ must be for the polynomial that evaluates to $(y_{i,1},\dots ,y_{i,k})$ at points $(z_1,\dots ,z_k)$.

This method

1. Checks that each element has the correct length
   • Commits has length $t$
   • Each element of evals has length $k$
2. Transcribes the points/evals the same as in the opening
3. Reads $\gamma$ same is in the opening
4. For each $j\in [k]$, computes $$a_j=\sum _{i\in [t]}{\gamma }^{j-1}{y}_{i,j}$$ $a_j$ represents the value of ${\sum }_{i\in [t]}{\gamma }^{i-1}{r}_i(z_j)$
5. Use the $a_j$ to interpolate $\varphi ={\sum }_{i\in [t]}{\gamma }^{i-1}{r}_i$ using the previously computed lagrange polynomials $l_{i,j}$ as $$\varphi =\sum _{i\in [t]}{\gamma }^{i-1}{r}_i=\sum _{j\in [k]}{a}_j{l}_{\text{point\_set\_index},j}$$
6. Compute $\alpha =[\varphi (x){]}_1$
7. Compute $\beta ={\sum }_{i\in [t]}{\gamma }^{i-1}{c}_i$
8. Return true if $$e(\beta -\alpha ,g_2)=e(\text{proof},{\theta }_{\text{point\_set\_index}})$$