Groth16 Tweaks
$$ \gdef\F{\mathbb{F}} \gdef\G{\mathbb{G}} \gdef\g{\mathrm{G}} \gdef\h{\mathtt{H}} \gdef\e{\mathrm{e}} \gdef\Z{\mathrm{Z}} $$
Ethereum cost model
See evm.codes and the yellow paper. Calldata costs $16$ gas per zero bytes with a discounted price of $4$ for zero bytes. So the expected cost of a uniformly random byte is $15.95$ gas. On L1 calldata-gas and gas are the same, on L2s the latter is substantially cheaper.
- $\G_1$ element is 64 bytes uncompressed and costs $1024$ calldata-gas.
- Cost of $\G_1$ point decompression is TBD.
- $\G_2$ element is 128 bytes uncompressed and costs $2048$ calldata-gas.
- Cost of $\G_2$ point decompression is TBD.
- $\G_1$ addition costs $150$ gas.
- $\G_1$ scalar multiplication costs $6000$ gas.
- A $n$-pairing check costs $45\,000 + n ⋅ 34\,000$ gas.
- Keccak hash of $n$ bytes costs $30 + 6 ⋅ \ceil{\frac{n}{32}}$ gas.
- SHA256 hash of $n$ bytes costs $60 + 12 ⋅ \ceil{\frac{n}{32}}$ gas.
A Groth16 verification with $p$ public inputs (excluding constant $w_0 = 1$) costs
$$ 181\,150 + p ⋅ 6150 \text{ gas} + 4096 \text{ calldata gas} $$
This excludes overhead and cost of transferring/computing the public input. This includes the $4$ pairings currently required.
https://eips.ethereum.org/EIPS/eip-196 https://eips.ethereum.org/EIPS/eip-197 https://eips.ethereum.org/EIPS/eip-1108 https://eips.ethereum.org/EIPS/eip-2565
Does it make sense to use point compression on L2s?
Hash public inputs?
What if we use Keccak or SHA256 to hash all public inputs to a single field element, basically fixing $p = 1$.
3 P
Groth16 is well-known to only require 3 pairings, yet Ethereum implementations require 4, this costs an extra $34\,000$ gas that seems avoidable.
Pairing.negate(proof.A), proof.B,
vk.alfa1, vk.beta2,
vk_x, vk.gamma2,
proof.C, vk.delta2
- Instead of negating variable
proof.A, can negate compile time constantsvk.beta2,vk.gamma2andvk.delta2. (But negating G1 is very cheap)
Can we instead get the $α⋅β⋅\g_3$ term (and add $L_0$) through trusted setup?
$$ L' = γ^{-1} ⋅ \p{α ⋅ β + L_0(τ)} ⋅ \g_1 $$
$$ \begin{aligned} {\overline L} &= \sum_{i ∊ [1, p)} w_i ⋅ \p{γ^{-1} ⋅ L_i(τ) ⋅ \g_1} \\ \end{aligned} $$
then check
$$ \e(A, B) = \e(L' + {\overline L}, γ ⋅ \g_2) + \e(C, δ ⋅ \g_2) $$
Shorter proofs?
Groth16 contains an argument setting lower bounds on proof sizes and structure, but these all assume non-interactive proofs. If we allow for Fiat-Shamir constructions, can we create cheaper proofs?
