A. Optimizations

This contains all the optimizations made from the methods of BDFG21 and why they are correct. Please read the paper first 😘.

Method 1

This method is the fastest method for opening, and slightly slower for verification than Method 2. But, as written in the paper, verification is impractically slow for any appreciable number of polynomials/points. So here, we make an assumption to make the computation reasonable: each polynomial in $F=\{f_1,\dots ,f_N\}$ is opened at all the same points, that is (using the notation from the paper) $S_i=S_j=T\forall i,j\in [k]$. We also assume each polynomial $f_i$ is the same degree, $d$.

Method 1, Opening

Let $T=\{z_1,z_2,\dots z_t\}$. For brevity, assume sums over $i$ are done as ${\sum }_{i\in [k]}$

The prover has to compute, $[h(x){]}_1$, which means they must compute the coefficients of $h$ and then do $d+1-|T|$ ${\mathbb{G}}_1$ scalar multiplications and some addition. $h$ is defined as $$h(X):=\sum _i{\gamma }^{i-1}\frac{f_i(X)-r_i(X)}{Z_{S_i}(X)}=\frac{{\sum }_i{\gamma }^{i-1}\left(f_i(X)-r_i(X)\right)}{Z_T(X)}$$ Here, $r_i$ is the unique degree $|T|$ polynomial such that $r_i(z_j)=f_i(z_j)$. Note that polynomial fraction divides cleanly, because $f_i(z_j)-r_i(z_j)=0$ for all $j\in [t]$, meaning it has factors of $(X-z_j)$, and so does $Z_T(X)$.

The $r_i$ term is just the unique minimal degree polynomial you need to subtract from $f_i$ to allow $Z_T$ to cleanly divide it. But, this also means that $r_i$ is simply the remainder of dividing $f_i$ and $Z_T$. And the same applies for ${\sum }_i{\gamma }^{i-1}{f}_i$: ${\sum }_i{\gamma }^{i-1}{r}_i$ is just the remainder you get when you divide the sum of $f_i$s by $Z_T$! So all they need to do in order to compute $h$ is to

1. Compute ${\sum }_i{\gamma }^{i-1}{f}_i$
2. Use a polynomial division algorithm to divide by $Z_T$
3. Take the result and throw away the remainder

This makes opening very fast, because no interpolation is needed.

Method 1, Verification

For verification, the verifier needs to do a little more legwork than the prover. Let the commitment to the $i$-th polynomial be $c_i$

First, the verifier needs to compute $$Z_i:=[Z_{T\setminus S_i}(x){]}_2=[Z_{\varnothing }(x){]}_2=[1{]}_2=g_2$$ That's simple enough, now they have to compute $$\begin{array}{rl}F:& =\prod _{i}e({\gamma }^{i-1}(c_i[r_i(x){]}_1),Z_i)\\ & =e\left(\sum {\gamma }^{i-1}(c_i-[r_i(x){]}_1),g_2\right)\\ & =e\left(\sum {\gamma }^{i-1}{c}_i-{\left[\sum _i{\gamma }^{i-1}{r}_i(x)\right]}_1,g_2\right)\end{array}$$ Constraining the points lets them compute a single pairing instead of $k$! Now let's look at each side of pairing. To compute the LHS, they need to compute ${\sum }_i{\gamma }^{i-1}{r}_i$. Sadly, there's no nice way around this here, it must be interpolated, but they can interpolate ${\sum }_i{\gamma }^{i-1}{r}_i$ once rather than interpolate each $r_i$. That leaves us with

• $\sum {\gamma }^{i-1}{c}_i\to$ $N$ ${\mathbb{G}}_1$ scalar mults

• ${\left[{\sum }_i{\gamma }^{i-1}{r}_i(x)\right]}_1\to$ $|T|+1$ ${\mathbb{G}}_1$ scalar mults

Then all they're left with is the single pairing. Next they have to compute $e(W,[Z_T(x){]}_2)$. Computing $Z_T$ is pretty straightforward, and all they are left to do is the $d$ ${\mathbb{G}}_2$ scalar multiplications. If you already know your $T$ ahead of time, the $Z_T$ term can be cached.

This leaves us with the following amount of operations (other operations impact runtime fairly little)

Interestingly, the opening time gets smaller as the size of $T$ grows, due to the growing degree of the vanishing polynomial.

Method 2

Method 2 is an equally secure way to generate blocked openings, which biases computation slightly more to the opener than the verifer. They use the same assumptions as in Method 1.

Method2, Opening

The prover computes $h(X)=f(X)/Z_T(X)$ for $$f(X):=\sum _i{\gamma }^{i-1}{Z}_{T\setminus S_i}(X)(f_i(X)-r_i(X))=\sum _i{\gamma }^{i-1}(f_i(X)-r_i(X))$$ since $T\setminus S_i=\varnothing$ so $Z_{T\setminus S_i}=1$. This looks very familiar from method 1! Here they just compute $Z_T$ then compute the quotient $f/Z_T$ and for now, ignore the remainder. Then they compute $W:=[h(x){]}_1$. This is $\mathrm{deg}(h)+1=d-|T|+1$ ${\mathbb{G}}_1$ scalar multiplications.

This method has additional challenge other than $\gamma$, called $z$ which must take into account $W$. After seeing $W$, the verifier sends a $z\in \mathbb{F}$. In reality this should be abstracted away using a Fiat-Shamir transform.

The prover then computes $L(X):=f_z(X)-Z_T(z)h(X)$ for $$\begin{array}{rl}{f}_z(X):& =\sum _i{\gamma }^{i-1}{Z}_{T\setminus S_i}(z)(f_i(X)-r_i(z))\\ & =\sum _i{\gamma }^{i-1}{f}_i(X)-\sum _i{\gamma }^{i-1}{r}_i(z)\end{array}$$

Here we notice that we have already computed ${\sum }_i{\gamma }^{i-1}{r}_i(X)$ when we computed the remainder of $f/Z_T$. All they have to do is take this remainder, evaluate it at $z$, and then subtract it from ${\sum }_i{\gamma }^{i-1}{f}_i(X)$. They then evaluate $Z_T(z)$, compute $L(X):=f_z(X)-Z_T(z)h(X)$, then compute the polynomial $\frac{L(X)}{x-z}$ and evaluate $W^{\prime }:={\left[\frac{L(X)}{x-z}\right]}_1$.

Here, $L(X)$ is of degree $d$, so computing $W^{\prime }$ involves $d$ ${\mathbb{G}}_1$ scalar multiplications.

The proof then consists of $(W,W^{\prime })$.

Method 2, Verification

The verifier receives $W,W^{\prime }$, the commitments $c_i$, the evaluations of the $f_i$ at each $z_j\in T$ and computes $$\begin{array}{rl}F:& =-Z_T(z)W+\sum _i{\gamma }^{i-1}{Z}_{T\setminus S_i}(z)(c_i-[r_i(z){]}_1)\\ & =-Z_T(z)W+\sum _i{\gamma }^{i-1}(c_i-[r_i(z){]}_1)\\ & =-Z_T(z)W+\sum _i{\gamma }^{i-1}{c}_i-{\left[\sum _i{\gamma }^{i-1}{r}_i(z)\right]}_1)\end{array}$$ To do this, they do lagrange interpolation of ${\sum }_i{\gamma }^{i-1}{r}_i(X)$, evaluate it at $z$, then do the single ${\mathbb{G}}_1$ scalar multiplication. Computing ${\sum }_i{\gamma }^{i-1}{c}_i$ is $N$ ${\mathbb{G}}_1$ scalar multiplications, and one more for computing $-Z_T(z)W$. Next the verifier checks $e(F,g_2)=e(W^{\prime },[x-z{]}_2)$ Which involves 2 pairings, and 2 ${\mathbb{G}}_2$ scalar multiplications, yielding

Comparing the two methods, we get