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?
