BN254 Point Compression for L2s
A Groth16 proof has two points and one . In the BN254 pairing curve these take 64 and 128 bytes respectively uncrompressed totaling 256 bytes for a proof. With compression points will take only 32 and 64 bytes respectively, halving the size of a proof.
On Ethereum calldata costs gas per byte, so any compression would need to perform better than that. This gives a budget of 512 and 1024 gas for and point compression respectively. This will be hard to achieve. On Optimism the cost of calldata is higher by a factor
Where the dynamic_overhead
is set to 0.684
and the gas price ratio fluctuates wildly with the last half year ranging between to . Taking the lower bound this puts the compression budget at 550 gas per byte, or 17k gas per point and double for . This seems doable, let's do it!
The field
The base field are the numbers modulo where
Addition and multiplications are trivially implemented using EVMs addmod
and mulmod
operations at 8 gas each. so we can add up to five elements using add
without overflowing. Negation can be done using but the result will be unreduced in range . so we can also add up to five unreduced negations without overflowing.
Exponentiation can be done using repeated multiplication. Efficient strategies for specific exponents can be found using addchain so the exact cost depends on the exponent. Exponentiation can also be done using the modexp
precompile which for costs to gas, depending on the exponent.
Inversion in
By Fermat's little theorem, in we have . Dividing both sides by we get
Computing this takes using an addition chain generated with addchain. Implemented using mulmod
this would take at least gas. The modexp
precompile costs gas.
To do. Inversion using half-extended GCD?
Square roots in
taking the square root of both sides we would get but is not an integer so this does not lead to a usable method. Instead is an integer. By Fermat's little theorem in we have . Dividing both sides by we get and taking the square root on both sides we get . We also have so is an integer. Observe
So if we have then . It can be shown that if the square root does not exist, so this method covers all square roots. In fact, only half of the elements in have a square root, and if it exists for it is absent for and vice versa.
The exponential takes using an addition chain generated with addchain, which takes at least gas using mulmod
. Using modexp
the exponent takes gas.
The field
Construct the extension field . That is, each element is written with , much like the complex numbers. In fact, we get all of our complex arithmetic identities:
Multiplication as above requires . It can be done with fewer multiplications using Karatsuba's method. Take , and , then the result is . This requires . Since addmod
and mulmod
cost the same in EVM, this is not a worthwhile trade-off. (To do. We can change some to cheaper add
s)
Squaring as above requires . Factoring as we can exchange one for an .
Square roots in
Square root is the hard part. We can again take inspiration from Gnark and see that it uses algorithm 9 from ARH12. This amounts to computing
This is a lot of exponentiation in , for which we cannot use the affordable precompile. So instead we consider a more traditional approach, algorithm 8 from ARH12. Give with we are looking for such that:
which gives the system of quadratic equations
The solution to this is
Show me
we take and substitute this back in the first equation and apply the quadratic formula
The inner needs to have a specific value, only one will result in a square for the outer square root. There does not seem to be an efficient method of computing this sign other than trying both values. Since trying is expensive (involves a modexp
) it is better to provide it as a hint. The outer reflects the two possible solutions of the quadratic equation.
Computing the square root requires two square roots and one inversion, which can be done using three calls to modexp
costing gas total.
Compressing points
The elliptic curve are the satisfying a short Weierstrass equation
One such solution is , which is the chosen generator for this group.
Give an coordinate we can recover the coordinate by taking the square root of . This has either two solutions or none. This means that we can distinguish the point as (when fully reduced) exactly one will be and exactly one will be an odd number.
Compressing points
The elliptic curve are the satisfying a short Weierstrass equation
where .
Given an coordinate we can recover the same as before, but now with math happening in . Given :
The coordinate is a square root of this value. As before, is also a solution.
Compressing two points
In Ote15 an efficient method for storing two points on the same curve is presented. (As mentioned by Zac Williamson). Given two points on a curve compute
we can recover the two points by
For the special case we can instead store . An extra bit is required to distinguish these cases.
Implementation and benchmark
An implementation of the above and compression is done in Solidity in Verifier.sol.
- Decompressing points takes gas so becomes worthwhile at gas/byte.
- Decompressing points takes gas so becomes worthwhile at gas/byte.
These numbers are close enough that we can consider doing both and compression. For a Groth16 verification this adds gas overhead, so becomes worthwhile at gas/byte. This is not economical on Ethereum, but it is on Optimism.
Safety
This compression method takes in existing proofs, so zero-knowledge is unaffected. After decompression it calls the original verifier, so soundness is unaffected. This leaves completeness, which is only preserved if the method works for all valid proofs. This can be accomplished by making sure the method works on all points in and , taking care to handle zero values and the point at infinity correctly. (Although it is at best extremely unlikely a valid proof will contain those.)
Appendix: Abusing ECADD?
Given such that the ecadd
precompile returns for 150 gas
if , or else
This contains an inversion for much cheaper than we can do, but it seems hard to extract this. The first case could maybe be abused to compute , but turning this in to a problem with valid points is going to be challenging.
References
- BN05 Baretto, Naehrig (2005). Pairing-Friendly Elliptic Curves of Prime Order.
- Shi10 Shirase (2010). Barreto-Naehrig Curve With Fixed Coefficient.
- BDMO10 Beuchat et al. (2010). High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves.
- ARH12 Adj, Ridrígues-Henríquez (2012). Square root computation over even extension fields.
- DLZZ22 Dai, Lin, Zhao, Zhou (2022). Fast Subgroup Membership Testings for , and on Pairing-friendly Curves.
- AGO22 Adiguzel-Goktas, Ozdemir (2022). Square Root Computation In Finite Fields.
- Wan22 Wang (2022). BN254 For The Rest Of Us.
- EIP-196: Precompiled contracts for addition and scalar multiplication on the elliptic curve alt_bn128.
- EIP-197: Precompiled contracts for optimal ate pairing check on the elliptic curve alt_bn128.
- EIP-198: Big integer modular exponentiation.
- EIP-1108: Reduce alt_bn128 precompile gas costs.
- EIP-2565: ModExp Gas Cost.
- BN254.sol by Espresso Systems.
- EllipticCurve.sol by The Witnet Project.
- BN256G2.sol by Mustafa Al-Bassam.
- BLS.sol by Antonio Sanso. See also the Ethresearch post.
https://eprint.iacr.org/2020/010.pdf