garaga-rs : MultiPairingCheck calldata builder

[feltroidprime]

Goal :

Having an equivalent of the serialize_to_calldata method for multi pairing checks.

As this is quite a large work, the recommended path to achieve it would be the following :

porting multi_miller_loop.py

1. Focus on creating the methods compute_doubling_slope, compute_adding_slope that can be found in https://github.com/keep-starknet-strange/garaga/blob/main/hydra/garaga/precompiled_circuits/multi_miller_loop.py#L151 . Note that those work on G2Points, so create a new g2point.rs file with the struct and implement it. Take advantage of the degree-2 extension field element in lambdaworks to simplify the computation, so that G2Point can be a struct containing two QuadraticExtensionFieldElement<F, T>

See :
https://github.com/lambdaclass/lambdaworks/blob/main/math/src/field/extensions/quadratic.rs
https://github.com/lambdaclass/lambdaworks/blob/8133ae54c7ebf3d340076e182f5184ad7fb6e2e1/math/src/elliptic_curve/short_weierstrass/curves/bls12_381/field_extension.rs#L27
https://github.com/lambdaclass/lambdaworks/blob/8133ae54c7ebf3d340076e182f5184ad7fb6e2e1/math/src/elliptic_curve/short_weierstrass/curves/bn_254/field_extension.rs#L26

2. Next inside a multi_miller_loop.rs file, focus on creating the method build_sparse_line_eval. It takes two QuadraticExtensionElement<F, T> + two FieldElement<T> and returns a Polynomial<F> of degree 12.

3. Then you should be able to create functions for double_step ,double_and_add_step, triple_step , bit_0_case, bit_1_case, bit_1_init_case re-using the already existing extf_mul of garaga_rs.

4. Finally get the loop_counter variables in hydra/definitions.py for bn and bls, and assemble everything to rebuild the full multi_miller_loop algorithm. The signature should be something like multi_miller_loop(Vec<G1G2Pair<F>>) -> Polynomial<F>. Initialize a vec of yInv and xNegOvery that are field elements at the beginning of this function and iterate over them.

This should be enough to re-code the extra_miller_loop_result method of the MPCCalldataBuilder

garaga/hydra/garaga/starknet/tests_and_calldata_generators/mpcheck.py

Line 59 in 7e16413

def extra_miller_loop_result(self) -> list[PyFelt] | None:

porting multi_pairing_check.py

1. Now create a multi_pairing_check.rs that will re-use the components in step 1 and 2 of the previous step.
2. This one will use the final exp witness already existing in garaga.
3. The work will be similar except that the bit_0, bit_1, bit_1_init_case are slightly different, and a new bit_00 case exists when there is two consecutive 0 in the loop_counter.
4. The key difference is that each time a extf_mul is called, you would need to store the references of Pis (list of Polynomial, Qi, and Ri. This process is named a "relation" in python.

Porting the MPCCalldataBuilder

mpc_calldata.rs.

1. Create a struct that include similar fields to the MPCheckCalldataBuilder class (list[G1G2Pair<F>], n_fixed_G2, public_pair:Option(G1G2Pair<F>)).
2. Implement the struct with methods similar to the python class, except for build_input_struct that is not needed.
3. Create a binding for the serialize_to_calldata with a use_rust flag in python and add a python test that compare both implementations using inputs from

   garaga/hydra/garaga/precompiled_circuits/multi_pairing_check.py

   Line 402 in 7e16413

   def get_pairing_check_input(

Important notes :

• The MultiMillerLoopCircuit and the MultiPairingCheckCircuit classes in python contains extra code that are not revelant., in particular the "sparsities" of the polynomials that are passed to extf_mul in python are not relevant in Rust for a first implementation. They were only used to take advantage of them in the generated cairo code.