feat: Precompile 0x08 ecPairing

[Eikix]

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

[feltroidprime]

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.

[feltroidprime]

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 .

[tekkac]

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.

[Eikix]

Awesome!! Thank you for your input