# EC (Multi)-Scalar Multiplication For a given elliptic curve, scalar multiplication consists of adding a point `P` to itself `s` times, where `P` is a point satisfying the curve equation and `s` a scalar.\ \ `k.P = P+P+P+...+P (k times)`\ \ \ Multi scalar multiplication consists of the sum of `n` scalar multiplication with different points and scalars : $$ \sum\_{i=1}^{n} k\_i \times P\_i $$ A single `msm_g1` function in Garaga computes the multi-scalar multiplication for a given set of points and scalars for a given elliptic curve. Since it also works with `n=1`, it is also able to compute a single scalar multiplication. ```toml [package] name = "my_package_that_needs_ec_scalar_mul" version = "0.1.0" edition = "2024_07" [dependencies] garaga = "1.1.0" [cairo] sierra-replace-ids = false ``` {% hint style="info" %} You can also add the dependency using `scarb add garaga`. See the [installation guide](https://garaga.gitbook.io/garaga/using-garaga-libraries-in-your-cairo-project/..#installation) for more options. {% endhint %} The function will be importable using ```rust use garaga::ec_ops::msm_g1; use garaga::definitions::G1Point; ``` ```rust fn msm_g1( points: Span, scalars: Span, curve_index: usize, msm_hint: Span, ) -> G1Point { ``` As you can see, this function not only needs points and scalars, but also additional information, to perform the computation much more efficiently.\ \ Under `hydra/garaga/starknet/tests_and_calldata_generators/`, you will find in the file [`msm.py`](https://github.com/keep-starknet-strange/garaga/blob/main/hydra/garaga/starknet/tests_and_calldata_generators/msm.py) some tools to generate a cairo test (using `MSMCalldataBuilder.to_cairo_1_test()`) for this function given some points and scalars, or directly the raw calldata for starknet usage (using `MSMCalldataBuilder.serialize_to_calldata()`). ### Generating and using calldata \ An example contract is already [deployed](https://sepolia.voyager.online/contract/0x012686bdb4ca3f22ffc93dfe1e24d72294aac38a4f6b997b456fb4368fb3390b#readContract) on sepolia, solely holding an endpoint to this function.\ The source code to the contract is [here](https://github.com/keep-starknet-strange/garaga/blob/main/src/contracts/universal_ecip/src/lib.cairo) .\ \ You can try this deployed contract on any supported curves modifying the [`msm.py`](https://github.com/keep-starknet-strange/garaga/blob/main/hydra/garaga/starknet/tests_and_calldata_generators/msm.py) script at the end : ```python if __name__ == "__main__": import random c = CurveID.SECP256K1 order = CURVES[c.value].n msm = MSMCalldataBuilder( curve_id=c, points=[G1Point.gen_random_point(c) for _ in range(1)], scalars=[random.randint(0, order) for _ in range(1)], ) cd = msm.serialize_to_calldata( include_points_and_scalars=True, serialize_as_pure_felt252_array=False, ) print(cd) print(len(cd)) ``` The options are : * `include_points_and_scalars` : If set to `False`, the input points, scalars, and `curve_index` will not be part of the calldata. * `serialize_as_pure_felt252_array` : If set to `True`, preprend the total length of the calldata at the beginning. \\ These options are only useful when you want to use points and scalars from another source than the calldata.\ \ For example, checkout the [groth16 verifier contracts](https://github.com/keep-starknet-strange/garaga/blob/main/src/contracts/autogenerated/groth16_example_bn254/src/groth16_verifier.cairo). It makes a delegated call to the endpoint `msm_g1` using the already declared contract's class hash, and pushes the (fixed) points from the hardcoded verifying key, and the scalars from the groth16 proof. : ```rust impl IGroth16VerifierBN254 of super::IGroth16VerifierBN254 { fn verify_groth16_proof_bn254( ref self: ContractState, groth16_proof: Groth16Proof, mpcheck_hint: MPCheckHintBN254, msm_hint: Array, ) -> bool { groth16_proof.a.assert_on_curve(0); groth16_proof.b.assert_on_curve(0); groth16_proof.c.assert_on_curve(0); let ic = ic.span(); let vk_x: G1Point = match ic.len() { 0 => panic!("Malformed VK"), 1 => *ic.at(0), _ => { // Start serialization with the hint array directly to avoid copying it. let mut msm_calldata: Array = msm_hint; // Add the points from VK and public inputs to the proof. Serde::serialize(@ic.slice(1, N_PUBLIC_INPUTS), ref msm_calldata); Serde::serialize(@groth16_proof.public_inputs, ref msm_calldata); // Complete with the curve indentifier (0 for BN254): msm_calldata.append(0); // Call the multi scalar multiplication endpoint on the Garaga ECIP ops contract // to obtain vk_x. let mut _vx_x_serialized = core::starknet::syscalls::library_call_syscall( ECIP_OPS_CLASS_HASH.try_into().unwrap(), selector!("msm_g1"), msm_calldata.span() ) .unwrap_syscall(); ec_safe_add( Serde::::deserialize(ref _vx_x_serialized).unwrap(), *ic.at(0), 0 ) } }; ``` Here the `msm_hint` is used with `include_points_and_scalars=False` and `serialize_as_pure_felt252_array=True`\ \ Then the points from `ic` are pushed to the array, and the scalars from the groth16 proof's public inputs. Finally the curve identifier is pushed as well.\ \ In our example, we'll leave the default parameters that will include everything for a direct endpoint call.\ Simply run : ``` python hydra/garaga/starknet/tests_and_calldata_generators/msm.py ``` And copy paste the array in voyager to see!