# 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](/garaga/using-garaga-libraries-in-your-cairo-project.md#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!
--- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://garaga.gitbook.io/garaga/using-garaga-libraries-in-your-cairo-project/ec-multi-scalar-multiplication.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.