Explore Nova Integration with MACI

[samajammin]

Creating this issue to track previous research & development efforts.

As of 2023-10-01, work has paused on this, but we hope to return to this work soon™

Summary

As part of MACI scaling efforts (to support one million concurrent voters on the platform), the team has researched SNARK folding schemes to minimize on-chain proving costs. We are working to add Nova support to MACI, which allows the aggregation of multiple MACI circuit instances, saving on-chain verification costs by batching state updates more efficiently.

SNARK Folding Scheme

Nova’s recursive folding scheme is instrumental in this process, and Nova-Scotia functions as an intermediary layer, interpreting circom generated R1CS and the witness generation executable. This allows us to convert MACI circuits into a format Nova can readily process. The process involves altering the MACI circuit to the StepCircuit interface as defined in Nova and modifying the on-chain verifier contract. The work also includes adding BN256-Grumpkin curve support for Nova. This necessitates modifications in these repos:

1. MACI- This adjustment requires modifications in the contracts, CLI, and core folders. The on-chain verifier contract also demands alterations.
2. Halo2Curves - In the halo2curves repository, BN256-Grumpkin curves support is already present. However, we needed to implement the hash_to_curve method to establish Pedersen commitment keys on BN256 curves. To achieve this, we’re relying on the Simplified SWU and the Try and Increment algorithms for hashing, while employing the SVDW algorithm for short Weierstrass curves
3. Nova- In the Nova repository, we’re tasked with implementing the Group trait for BN256-Grumpkin curves.
4. Nova-Scotia - The Nova-Scotia repository demands minimal modifications. Our main requirement is importing G1 and G2 from the BN256-Grumpkin curves in the halo2curves repository.

Benchmarks

Work was initiated to collect benchmarks to see what kind of performance improvements we can get. @chaosma presented on this zkParis event on July 20th 2023 - here's his talk "Nova Folding with MACI Circuits":
https://www.youtube.com/watch?v=EluF3gL2SEI

You can find some of his benchmark work here:

• https://github.com/chaosma/maci/tree/nova-benchmark
• https://github.com/chaosma/nova-maci

Eventually the goal here is to turn this research / PoC into a production-facing feature for MACI.

Input welcome

This issue is mostly my attempt at picking up the pieces of various work done by previous team members (h/t to @chaosma @daodesigner & potentially others). If anyone has additional research or development resources around this, or would like to submit a grant proposal around this work, please let us know!

Additional references

• https://hackmd.io/@chaosma/B1gmar_Sn