feat: Spartan SNARK implementation

[Autoparallel]

Not sure this belongs directly in Sonobe itself, but for cases where we want faster compression using Spartan would be excellent. Basically, we would just want to take this and implement the ark-snark SNARK trait.

There may have been a dated attempt here from the arkworks team themselves: https://github.com/arkworks-rs/spartan/

---

Please remove issue if not relevant.

[arnaucube]

Yes it is relevant indeed! Thanks for opening this issue^^
It has been on the horizon since months ago, and a couple of weeks ago mentioned in this comment: #182 (comment)

Current arkworks-rs/spartan is a translation of the microsoft/spartan into arkworks field & curves usage, but not adapted to the arkworks snark trait. Once the arkworks-rs/spartan implements the arkworks SNARK trait, we would be able to just use it in the sonobe decider instead of the current Groth16.

Additionally, once that is ready, a further step would be to adapt it to work directly for RelaxedR1CS instead of R1CS, as it is done in microsoft/Nova/src/spartan, so that we can simplify the decider circuits.

[Autoparallel]

I'd honestly love to tackle this issue but I'd probably need some assistance. I'm still learning this stuff.

Regardless, do you think you'd want to pull in spartan = "0.8.0" and implement it inside of this repo somewhere? It seems a bit out of place and I agree that having arkworks-rs/spartan carry the implementation would be the most straightforward. I just worry that it may be a bit of juggling dependencies.

[arnaucube]

That's awesome!!
Yes, it should be fully independent of the sonobe repo probably. I think that probably a fork of arkwors-rs/spartan, adapting it to fit into the arkworks SNARK trait, and then a PR can be opened to arkworks-rs/spartan repo so that the rest of the arkworks community can enjoy of the improvement.

[rsinha]

Revisting this thread. Is there a plan to support Spartan?

[winderica]

Hey @rsinha, Spartan support is definitely on our roadmap, but unfortunately I don't think we can do this in the near future.

Currently all maintainers are quite busy with other projects. While I have been trying to spend some time on Sonobe, my priority is to improve code quality, so that we can get prepared for big features such as lookup arguments and better deciders (based on Spartan or CP-SNARKs). Only after that will I start looking into Spartan integration.