###### tags: ` estimation`

# On-chain verifier
In this document we make some back-of-the-envelope computations to see how feasible it is to verify SNARKs on main-net. We have some preliminary benchmarks made by Kenneth that show how expensive each function is. The goal of this document is to use those values and estimate SNARK verification on-chain. Similarly, we will estimate how much data the script needs to process, to understand if we are within the script data budget.

We analyse two SNARKs systems, Groth16 and vanilla-Plonk.

## Preliminary benchmarks
The current limit for on-chain scripts is 10,000,000,000 of the units in the file, but the basic Plutus stuff will add a lot on top of the costs of executing the builtins.

The values of interest for this analysis are the following (were x is the size of the input in bits divided by 64):

bls12_381_G1_compress    : 3341914
bls12_381_G1_uncompress  : 16511372
bls12_381_G1_add         : 1046420
bls12_381_G1_equal       : 545063
bls12_381_G1_hashToCurve : 66311195 + 23097*x 
bls12_381_G1_mul         : 94607019 + 87060*x (we use 94955259, with x = 4)
bls12_381_G1_neg         : 292890
bls12_381_G2_compress    : 3948421
bls12_381_G2_uncompress  : 33114723
bls12_381_G2_add         : 2359410
bls12_381_G2_equal       : 1102635
bls12_381_G2_hashToCurve : 204557793 + 23271*x
bls12_381_G2_mul         : 190191402 + 85902*x
bls12_381_G2_neg         : 307813
bls12_381_GT_finalVerify : 388656972
bls12_381_GT_millerLoop  : 402099373
bls12_381_GT_mul         : 2533975
blake2b_256                     : 358499 + 10186*x (521475, with x = 16)
addInteger                      : 85664 + 712*max(x,y) (88512, with x = y = 4)
multiplyInteger                 : 1000 + 55553*(x+y) (641924, with x = y = 4, and we include the price of modular reduction, as we need one per mult)
divideInteger                   : if x>y
                                  then  809015 + 577*x*y
                                  else  196500
modInteger                      : 196500  
expInteger                      : We estimate 32 mults and adds (23373952)

## Groth16 verifier
The verifier needs to run the following check:

$$e([A]_1, [B]_2) =? e([\alpha]_1, [\beta]_2) * e\left(\sum_{i=0}^l a_i \left[\frac{\beta * u_i(x) + \alpha * v_i(x) + w_i(x)}{\alpha}\right]_1, [\gamma]_2\right) * e([C]_1, [\delta]_2)$$

Note that the above is a pairing equation, meaning that we are checking if
$e(a,b) = e(c,d) * e(e,f) * e(g,h)$. This check can be translated to:
$$
\begin{aligned}
lhs &\leftarrow ml(a,b) \\
rhs &\leftarrow ml(c,d) * ml(e,f) * ml(g,h) \\
\texttt{accept}&\iff \texttt{final_verify}(lhs, rhs)
\end{aligned}
$$

We can do some ZK engineering to bring the number of l to 1, with some minor effect on the verifier (in the best case, a hash function of some public values). This means that the number of operations required for a Groth16 verifier are:
* 4 `bls12_381_G1_uncompress` (16511372)
* 4 `bls12_381_G2_uncompress` (33114723)
* 1 `bls12_381_G1_mul` (97392939)
* 1 `bls12_381_G1_add` (1046420)
* 4 `bls12_381_GT_millerLoop` (402099373)
* 2 `bls12_381_GT_mul` (2533975)
* 1 `bls12_381_GT_finalVerify` (388656972)

This results in a total of 2,299,066,153. With the limit of 10,000,000,000, this means that a Groth16 proof uses around 23% of the execution budget. Note, however, that the basic Plutus operations add a lot on top of the costs of executing the builtins, so we shouldn't expect to reach the limit.

In terms of size, we are handling:
* 4 G1 elements (48 bytes)
* 4 G2 elements (96 bytes)
* 1 scalar (32 bytes)

resulting in 608 bytes. The current limit for scripts is 16384 bytes, which means a Groth16 verifier uses less than 4% of the data limit per script.

## Plonk verifier
We assume there are no public inputs, so l = 1.
The number of operations required for a vanilla plonk verifier are (the numbering refers to each step of the verifier as in the [original paper](https://eprint.iacr.org/2019/953.pdf) as per Feb-2023):
* (1) 9 `bls12_381_G1_uncompress` (16511372)
* (2) 6 `less than` checks, over `Integer` type (free or failure)
* (3) 1 `less than` check, over `Integer` type (free or failure)
* (4) 6 `blake2b_256` of at most 1KB (521475)
* (5) 1 modular exponantiation (23373952 - super uper bound. depends on the number of gates)
* (6) 2 `multiplyInteger` (641924)
* (6) 1 `divideInteger` (196500)
* (7) 1 `multiplyInteger` (641924)
* (8) 8 `multiplyInteger` (641924)
* (8) 7 `addInteger` (88512)
* (8) 1 `modInteger` (196500)
* (9) 6 `bls12_381_G1_uncompress` (16511372)
* (9) 17 `multiplyInteger` (641924)
* (9) 9 `bls12_381_G1_mul` (97392939)
* (9) 9 `bls12_381_G1_add` (1046420)
* (10) 2 `bls12_381_G1_add` (1046420)
* (10) 4 `multiplyInteger` (641924)
* (10) 5 `bls12_381_G1_mul` (97392939)
* (10) 5 `bls12_381_G1_add` (1046420)
* (11) 1 `bls12_381_G1_uncompress` (16511372)
* (11) 10 `multiplyInteger` (641924)
* (11) 7 `addInteger` (88512)
* (11) 1 `modInteger` (196500)
* (11) 1 `bls12_381_G1_mul` (97392939)
* (12) 2 `bls12_381_G2_uncompress` (33114723)
* (12) 2 `bls12_381_G1_mul` (97392939)
* (12) 4 `bls12_381_G1_add` (1046420)
* (12) 2 `bls12_381_GT_millerLoop` (402099373)
* (12) 1 `bls12_381_GT_finalVerify` (388656972)

In summary, the number of operations are the following:
* 16 x bls12_381_G1_uncompress (16511372)
* 17 x bls12_381_G1_mul (97392939)
* 20 x bls12_381_G1_add (1046420)
* 2 x bls12_381_G2_uncompress (33114723)
* 2 x bls12_381_GT_millerLoop (402099373)
* 1 x bls12_381_GT_finalVerify (388656972)
* 6 x blake2b_256 (521475)
* 1 x modular exponantiation (23373952)
* 42 x multiplyInteger (641924)
* 1 x divideInteger (196500)
* 14 x addInteger (88512)
* 2 x modInteger (196500)

We can see that this is a bit more convoluted than Groth16.. But we have less miller loops. A preliminary check gets us a computation of 3,255,167,757, which is 33% of the execution budget.

For the amount of data that the verifier needs to operate with:
* 18 G1 elements (48 bytes)
* 2 G2 elements (96 bytes)
* 7 scalars (32 bytes)

This results in 1280 bytes, which is around 8% of the allowed budget.