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 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.