Module curdleproofs::notes::optimizations

Curdleproofs optimizations

Curdleproofs is optimized for quick verification. This section goes into more details on the optimizations deployed.

MSM Accumulator

Throughout the protocol there are checks of the form \[C \stackrel{?}{=} \bm{x} \times ( \bm{g} \ || \ \bm{h} \ || \ G_T \ || \ G_U \ || \ H \ || \ \bm{R} \ || \ \bm{S} \ || \ \bm{T} \ || \ \bm{U}) \] These checks form the bottleneck of the verifiers computation and we can save significant amounts of work by accumulating these checks into a single multiscalar multiplication that is checked at the end of the protocol.

We implement the optimization in the crate::msm_accumulator crate.

IPA Verification Scalars

We use an optimization from Bulletproofs to reduce the verifier overhead in inner product arguments that is also used in the Dalek implementation. We will demonstrate the optimization for the $SameMsm$ argument, but same reasoning applies for the $DLinner$ argument as well.

The verifier computes only three checks in the entire $SameMsm$ argument: namely in Step 3 it checks that $A = x G_1$, $Z_T = x T_1$, and $Z_U = x U_1$. This means that although the prover needs to compute the intermediate vectors $\bm{G}, \bm{T}, \bm{U}$ at each step in order to compute the $\pi_j$ values, the verifier does not and it can compute the final $A, Z_T, Z_U, G_1, T_1, U_1$ directly from the initial $A, Z_T, Z_U, \bm{G}, \bm{T}, \bm{U}$ and the $B_A, B_T, B_U, \bm{\gamma}$ values.

Using a simple example where the starting $|\bm{G}| = 8$, we see that $\bm{G}$ gets changed as follows: \[ \begin{array}{c c c c c c c c c c c c c c c c c} & \bm{G} = & (G_1’ & || & G_2’ & || & G_3’ & || & G_4’ & || & G_5’ & || & G_6’ & || & G_7’ & || & G_8’) \\ & \bm{G} = & ( G_1’ & + & \gamma_1 G_5’ & || & G_2’ & + & \gamma_1 G_6’ & || & G_3’ & + & \gamma_1 G_7’ & || & G_4’ & + & \gamma_1 G_8’ ) \\ & \bm{G} = & ( G_1’ & + & \gamma_2 G_3’ & + & \gamma_1 G_5’& + & \gamma_1 \gamma_2 G_7’ & || & G_2’ & + & \gamma_2 G_4’ & + & \gamma_1 G_6’ & + & \gamma_1 \gamma_2 G_8’) \\ & \bm{G} = & ( G_1’ & + & \gamma_3 G_2’ & + & \gamma_2 G_3’ & + & \gamma_2 \gamma_3 G_4’ & + & \gamma_1 G_5’ & + & \gamma_1 \gamma_3 G_6’ & + & \gamma_1 \gamma_2 G_7’ & + & \gamma_1 \gamma_2 \gamma_3 G_8’) \end{array} \] such that the final $G_1$ value is equal to \[ ( 1, \ \gamma_3, \ \gamma_2, \ \gamma_{2} \gamma_3, \ \gamma_1, \ \gamma_1 \gamma_3, \ \gamma_1 \gamma_2, \ \gamma_1 \gamma_2 \gamma_3 ) \times \bm{G} \] If we set $\bm{\delta} = (\gamma_m, \ldots, \gamma_1)$ to be the reverse of $\bm{\gamma}$ then we see a useful structure \[ G_1 = ( 1, \ \delta_1, \ \delta_2, \ \delta_{1} \delta_2, \ \delta_3, \ \delta_1 \delta_3, \ \delta_2 \delta_3, \ \delta_1 \delta_2 \delta_3 ) \times \bm{G} \] namely that $G_1 = \bm{s} \times \bm{G}$ where $s_i = \sum_{ j = 1 }^{m} \delta_j^{b_{i,j}}$ for $b_{i,j}$ such that $i = \sum_{j = 1}^m b_{i,j} 2^j$ is the binary decomposition of $i$.

Grandproduct Verifier Optimizations

The non-optimized grandproduct verifier is required to compute a vector $\bm{G}’ = \bm{u} \circ \bm{G}$ for some public vector $\bm{u}$. Then $\bm{G}‘$ is used as input to the $DLInner$ common reference string. Computing $\bm{G}’ = \bm{u} \circ \bm{G}$ would cost $n$ scalar multiplications that cannot be accumulated efficiently. However, when we look into how the vector $\bm{G}‘$ is used in $DLInner$, it is used only once during \[ AccumulateCheck( \bm{\gamma} \times \bm{L}_{D} + (B_D + \alpha D) + \bm{\gamma}^{-1} \times \bm{R}_{D} \stackrel{?}{=} d \bm{s}’ \times \bm{G}’ ) \] This check is equivalent to accumulating the check \[ AccumulateCheck( \bm{\gamma} \times \bm{L}_{D} + (B_D + \alpha D) + \bm{\gamma}^{-1} \times \bm{R}_{D} \stackrel{?}{=} (d \bm{s} \circ \bm{u} ) \times \bm{G} ) \] We thus edit the $DLInner$ verifier to only take the original generators as input in $crs_{DLInner} = (\bm{G}, H)$, however to take $\bm{u}$ one of the public inputs $\phi_{DLInner} = (C, D, z, \bm{u})$. The accumulated check can then be run efficiently.

A second optimization we run is that the non-optimized grandproduct verifier is required to compute a group element \[ D \gets B - (1, \beta, \ldots, \beta^{\ell - 1} ) \times \bm{g}’ + \alpha \beta^{\ell + 1} \bm{1} \times \bm{h}’ \] for \[ \bm{g}’ \gets ( (\beta^{-1} g_2 , \beta^{-2} g_3, \ldots, \beta^{-(\ell-1)} g_{\ell} ) \ || \ \beta^{-\ell} g_1 ) \ \land \ \bm{h}’ \gets \beta^{-(\ell + 1)} \bm{h} \] Expanding we see that \[ \begin{align*} (1, \beta, \ldots, \beta^{\ell - 1} ) \times \bm{g}’ & = (1, \beta, \ldots, \beta^{\ell - 1} ) \times ( (\beta^{-1} g_2 , \beta^{-2} g_3, \ldots, \beta^{-(\ell-1)} g_{\ell} ) \ || \ \beta^{-\ell} g_1 ) \\ & = ( (\beta^{-1} g_2 , \beta^{-1} g_3, \ldots, \beta^{-1} g_{\ell} ) \ || \ \beta^{-1} g_1 ) \\ & = \beta^{-1} \sum_{i=1}^{\ell} g_{i} \end{align*} \] Similarly \[ \begin{align*} \alpha \beta^{\ell + 1} \bm{1} \times \bm{h}’ & = \alpha \beta^{\ell + 1} \bm{1} \times \beta^{-(\ell + 1)} \bm{h} \\ & = \alpha \sum_{i = 1}^{n_{bl}} h_i \end{align*} \] If we store $g_{\mathsf{sum}} = \sum_{i=1}^{\ell} g_{i}$ and $h_{\mathsf{sum}} = \sum_{i=1}^{\ell} h_{i}$ in the CRS then we can compute \[ D \gets B - \beta^{-1} g_{\mathsf{sum}} + \alpha h_{\mathsf{sum}} \] in just $2$ scalar multiplications.