# 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
We implement the optimization in the [`crate::msm_accumulator`] crate.
## IPA Verification Scalars
We use an optimization from [Bulletproofs](https://eprint.iacr.org/2017/1066.pdf) to reduce the verifier overhead in
inner product arguments that is also used in the [Dalek
implementation](https://doc-internal.dalek.rs/bulletproofs/inner_product_proof/index.html). 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.
\\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_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.