Open feltroidprime opened 1 week ago
Question: can I simplify the multi pairing implementation to skip the use of precomputed lines?
Here is the reference:
Question: can I simplify the multi pairing implementation to skip the use of precomputed lines?
Here is the reference:
Yes indeed, pre computing the lines is not necessary
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
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 newg2point.rs
file with the struct and implement it. Take advantage of the degree-2 extension field element in lambdaworks to simplify the computation, so thatG2Point
can be a struct containing twoQuadraticExtensionFieldElement<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
Next inside a
multi_miller_loop.rs
file, focus on creating the methodbuild_sparse_line_eval
. It takes twoQuadraticExtensionElement<F, T>
+ twoFieldElement<T>
and returns aPolynomial<F>
of degree 12.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 existingextf_mul
of garaga_rs.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 likemulti_miller_loop(Vec<G1G2Pair<F>>) -> Polynomial<F>
. Initialize a vec ofyInv
andxNegOvery
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 https://github.com/keep-starknet-strange/garaga/blob/7e16413f093f9f2d2fcd16b81c1aa15c5be27fdb/hydra/garaga/starknet/tests_and_calldata_generators/mpcheck.py#L59porting multi_pairing_check.py
multi_pairing_check.rs
that will re-use the components in step 1 and 2 of the previous step.Porting the MPCCalldataBuilder
mpc_calldata.rs.
MPCheckCalldataBuilder
class(list[G1G2Pair<F>], n_fixed_G2, public_pair:Option(G1G2Pair<F>)).
serialize_to_calldata
with ause_rust
flag in python and add a python test that compare both implementations using inputs from https://github.com/keep-starknet-strange/garaga/blob/7e16413f093f9f2d2fcd16b81c1aa15c5be27fdb/hydra/garaga/precompiled_circuits/multi_pairing_check.py#L402Important notes :
MultiMillerLoopCircuit
and theMultiPairingCheckCircuit
classes in python contains extra code that are not revelant., in particular the "sparsities" of the polynomials that are passed toextf_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.