Add Bn254 Garaga hints to operate

[Eikix]

Garaga is a "Efficient pairing library using polynomial representation of field elements, written in Cairo 🐺 (Cairo Zero). It'll soon be audited, and integrated as a syscall on Starknet.

Problem: Garaga relies on specific hints that speed up the computation. These hints are implemented in the old Python-VM and need to be added to the Cairo-VM Rust hint manager.
Note: using this hints doesn't hurt the security, reliability or provability of the computations.

Solution: add the hints to the Cairo-VM in Rust.

Process: in order to refine this issue ->

• Take each Garaga required hint, add it in the Hint manager of Cairo-vm rs
• Implement the logic of it in Rust -> translate the existing python logic
• Test the behaviour using the Groth16 verifier / unit test cases for the curve operations

First file to consider (in the list) is: https://github.com/keep-starknet-strange/garaga/blob/main/src/bn254/fq.cairo

Investigation task: Try to implement the first hint of the list in Cairo-VM Rust. Work hand in hand with @feltroidprime to coordinate the effort with the python implementation and to accelerate the cleaning up of the original hints.

Caveats and how tos:

• How to match the python string and extract variables?
• How to test the behaviour unitarily -> Feltdroidprime will work on unit test cases in Cairo for the hints
• How to manipulate program_input and program_output, example:

        %{
          for var_name in list(program_input.keys()):
              fill_element(var_name, program_input[var_name])
       %}

Additional context
This will also be useful for Cairo 1 -> When Starknet wants to use Bn254 operations in the current network (Current version of Cairo compiler), it'll need to call garaga through syscalls, like it is currently doing for P256 (Braavos hardware signer).

[feltroidprime]

Happy to guide you closely with this.
Side node: Hints managing program_input is not necessary for Starknet. They are mainly used to input test data. We can overcome this by inputing test vectors manually and slighlty change cairo programs to have the test values hardcoded.

[feltroidprime]

Mainly the hints will require some BigInt lib (signed), as negative values should be also handled.
A polynomial lib implementing euclidean divisions for polynomials.
and Starknet 's poseidon hash function.

[pefontana]

Hi Guys!
We can make something like we do with some Kakarot hints. We added the hints they needed under a feature flag, here is the PR #1476
Right now we are finishing other Starknet projects, so we can't focus on implementing these hints, but if you want to send some PRs implementing them, we will be happy to help

[Eikix]

Hi Guys! We can make something like we do with some Kakarot hints. We added the hints they needed under a feature flag, here is the PR #1476 Right now we are finishing other Starknet projects, so we can't focus on implementing these hints, but if you want to send some PRs implementing them, we will be happy to help

I'd be happy to try to do that this week:)!

Update: I see you already have a garaga.rs file in your hint processor

I suggest to turn it into a feature called "garaga", akin to "test_utils" feature.