feat: add bandersnatch curve

[dragan2234]

Pull Request type

Adding bandersnatch parameters https://eprint.iacr.org/2021/1152.pdf

Please check the type of change your PR introduces:

• [ ] Bugfix
• [x] Feature
• [ ] Code style update (formatting, renaming)
• [ ] Refactoring (no functional changes, no API changes)
• [ ] Build-related changes
• [ ] Documentation content changes
• [ ] Testing
• [ ] Other (please describe):

What is the current behavior?

Issue Number: N/A

What is the new behavior?

-

-

Does this introduce a breaking change?

• [ ] Yes
• [ ] No

Other information

[dragan2234]

@feltroidprime Thanks for the review, I have addressed the comments! It should be fine now.

Strange thing is that msm for 1,2,3 points are fine with bandersantch, but 256 points is failing for some reason

[feltroidprime]

@feltroidprime Thanks for the review, I have addressed the comments! It should be fine now.

Strange thing is that msm for 1,2,3 points are fine with bandersantch, but 256 points is failing for some reason

Yes it is expected, circuits have been compiled for up to 3 points for the LHS of the equation to verify https://github.com/keep-starknet-strange/garaga/blob/dac43112e3298cf64cc8eb656dff05f1d4072ec6/src/fustat/precompiled_circuits/ec.cairo#L10

For the RHS, it supports any number of points as it calls the same circuit in a loop : https://github.com/keep-starknet-strange/garaga/blob/dac43112e3298cf64cc8eb656dff05f1d4072ec6/src/fustat/ec_ops.cairo#L233 but for the LHS we would need to modify the outputs / add an extra circuit to call in a loop to allow the LHS computation for arbitrary number of points https://github.com/keep-starknet-strange/garaga/blob/dac43112e3298cf64cc8eb656dff05f1d4072ec6/hydra/precompiled_circuits/ec.py#L243 , depending on the number of coefficients in sum_dlog_div , see number of coefficients in function of n : https://github.com/keep-starknet-strange/garaga/blob/dac43112e3298cf64cc8eb656dff05f1d4072ec6/hydra/precompiled_circuits/all_circuits.py#L352-L357

For now, please just comment the n=256 line in the test so I can merge this, and we can add it later or make a specific n=256 circuit for it.

[dragan2234]

@feltroidprime Thanks for the explanation, just commented out line for testing 256 points

[dragan2234]

hi @feltroidprime can we merge this? I want to pull some benchmarks regarding proof costs/number of steps.

[feltroidprime]

closing as linked to deprecated code