BN254 precompiles design

[han0110]

In our current EVM circuit strategy, implementing BN254 precomiles inline seems to be impractical (probably fine to do add but definitely not fine for scalar mul or pairing), so we could delegate the computation to another sub-circuit BN254 circuit built from halo2wrong, then communicate the input by bn254_table. First we need to estimate how many different input could happen inside a single block (30M gas):

Operation	Worst Case Gas Cost	Maximum Different Input	Row Cost 1
BN254Add	≥ 100 + 150	≤ 120000 ≈ 216.87	257 ≈ 28.01
BN254SalarMul	≥ 100 + 6000	≤ 4919 ≈ 212.26	41880 ≈ 215.35
BN254Pairing	≥ 100 + 45000	≤ 666 ≈ 29.38	?

The maximum different input seems small enough to be packed into a single table.

But there is a problem, the pairing input could be variable size, for the table we could simply use RLC the sync the bytes, but for the BN254 circuit it needs to be able to handle variable size input.

So we could follow the Keccak circuit design, to repeat the region add_gt_and_pairing, which also checks if the output is identity, but the row cost of this region will be much more expensive than other 2 operations so it could be an easy thing to exploit (e.g. a transaction with 30M gas repeating calling pairing).

Footnotes

1. Row cost is estimated using https://github.com/privacy-scaling-explorations/halo2wrong/tree/v2 and the could be easily reduced by allocating more advice columns (but for sure more cost on prover/verifier). ↩

[KimiWu123]

HI @han0110, I think this issue was addressed by #500 and we could close this. What do you think?

[han0110]

Sounds good to me