kakarot
kakarot copied to clipboard
kkrt-labs
feat: Precompile 0x08 ecPairing
Feature Request
Describe the Feature Request
feat: Explore / propose strategy (if applicable, MVP implementation) for EVM Precompiled contract -> 0x08 ecPairing
https://www.evm.codes/precompiled
alt_bn128 pairing logic is implemented in this file https://github.com/tekkac/cairo-alt_bn128/blob/c2ec87cc9b57846f2d89861f77b4bee69e2a5720/alt_bn128_pair.cairo#L143-L167 , the main part being the Miller loop, but it uses unsafe hints from this file https://github.com/tekkac/cairo-alt_bn128/blob/main/alt_bn128_gt.cairo
The author originally thought these hints could be verified in Cairo like for ec_add and ec_mul, but this is another type of ellipitic curve the same tricks don't apply here. Native implementation (without hints + verification) implies arithmetics over FQ12 which are very costly. Nethermind has a more advanced implementation of the miller loop for bls12-381 https://github.com/NethermindEth/optimized_ecc_cairo/blob/main/lib/pairing.cairo , but the miller loop is ~1 million step per iteration, with tens of iterations at minimum.
The smartest move would be to discover if a hint can be used with a small verification cost, but this requires much deeper knowledge of maths, and we don't have the certainty that it is even possible.
In fact in https://github.com/tekkac/cairo-alt_bn128/blob/main/alt_bn128_gt.cairo, There might be a trick to verify the hint of gt_line_slope though, but not the arithmetics like fq12_mul .
I wrote the code above and I plan to work on it more soon. My idea is to use a larger field to verify the mutiplication using a new hint (polynomial division). It would increase the number of steps though, but we might get away with it. Will report back.
