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 adds)

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.

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

https://eprint.iacr.org/2020/010.pdf

Remco Bloemen
Math & Engineering
https://2π.com