Nova on MACI devlog

Introduction

MACI stands for Minimal anti-collusion infrastructure which has widely used in various applications such as anonymous voting and quadratic funding. We plan to add Nova support for MACI so that we can aggregate multiple MACI circut instances (i.e. batches) together. This will save on-chain verification cost and reduce prover time.

The major tools are the Nova repo and Nova-Scotia repo. Nova repo implements recursive nova folding scheme describe by nova paper. Nova-Scotia is a middle layer that read circom generated R1CS and witness generation executable which allow us to convert MACI circuit into format required by Nova.

In this blog, we will describe the steps needed based on our dev work. Nova currently only supports pasta curves. However, MACI runs on BN256 curve and EVM only supports BN256 curve operation (e.g. pairing). In this case, we have to add BN256-Grumpkin curves support for Nova in order to use the Nova-Scotia. Besides MACI repo, we still need modify other

$3$ repos: halo2curves, nova, nova-scotia.

MACI

StepCircuit Interface

The first thing we need to do is to change the MACI circuit to StepCircuit interface defined in Nova. In MACI v1.0, the only public signal in MessageProcessor.circom (i.e. StepCircuit in terms of Nova) is inputHash. inputHash=hash(inputState, outputState, auxSignals). Nova requires the input and output has the same format. We changed it as:
inputHash=hash(inputStateRoot, auxSignals)
outputHash=hash(outputStateRoot,auxSignals)
Here the auxSignals are hash of other private signals to ensure the soundness of the circuit.

After this modification, we need modify the affected parts in contracts, cli and core folders as well.

On-chain verifier

The second thing to modify is the on-chain verifier contract. In MACI v1.0, the verifier contract only allows for a single public signal. As our new change, we need it to accept array of public signals. Here is the new interface:

    function verify(
        uint256[8] memory _proof,
        VerifyingKey memory vk,
        uint256[] memory inputs
    ) override public view returns (bool)

From groth16 paper, the verifier verifies:

$$e([A{]}_1,[B{]}_2)=e([\alpha {]}_1,[\beta {]}_2)+e(\sum _{i=0}^{l-1}{a}_i\cdot [vk.ic[i]{]}_1,[\gamma {]}_2)+e([C{]}_1,[\delta {]}_2)$$
where

$\{a_i{\}}_{i=0}^{l-1}$ are public inputs with

$a_0=1$. We only needs to modify the second term on the right hand side.

halo2curves

In most recent halo2curves repo, the BN256-Grumpkin curves supports are added. However, it still missed some functions to support the Nova Group interface.

hash to curve

In order to setup pedersen commitment keys on BN256 curves, we need to implement hash_to_curve method required by Nova repo. There are several algorithms to do this.

Simplified SWU algorithm.

The pasta curves used this algorithm. For BN256 curve

$E:Y^2=X^3+3$ (which has

$A=0$), which need map to "normal" case where both

$A,B$ are non-zero. This can be done by an isogeny that mapping between

$E^{\prime }\stackrel{iso\mathrm{\_}map}{\to }E$.

1. (x', y') = map_to_curve_simple_swu(u) # (x', y') is on E
2. (x, y) = iso_map(x', y') #(x, y) is on E

The whole process is:

$$t\stackrel{hash}{\to }u\stackrel{map\mathrm{\_}to\mathrm{\_}curve}{\to }(x^{\prime },y^{\prime })\stackrel{iso\mathrm{\_}map}{\to }(x,y)$$
We need to implement above

$3$ functions. The first thing we need to find is the isogeny map between

$E^{\prime }$ and

$E$, which is curve specific. However, the degree of isogeny map is too high, this algorithm is not suitable.

Try and increment algorithm

This is the simpliest algorithm. In expectation, it only require two tries which is fast enough. We first hash a message to base element:

$t=hash(msg)$. Then:

// pseudo rust code
fn try_and_increment<C:CurveAffine>(t: C::Base) {
    let mut x = t;
    loop {        
        let y2 = (x*x+a)*x + b;
        if (y2.is_square()) {
            let y = y2.square_root();
            return C::Base::new(x, y);
        }
        *x += C::BASE::ONE;
    }
}

Depending on the field, we have different algorithms to calculate the square root in above algorithm. We omit the detail here.

SVDW algorithm

As we mentioned before the simplified SWU algorithm requires

$A\cdot B\ne 0$, we have to find isogeny mapping

$E^{\prime }\to E$ such that

$E^{\prime }$ coefficients are non-zero. It turned out for BN256 curve, the isogeny mapping has degree

$59$ which is too high for practical use. It's better that we choose SWDW algorithm which works for any short weierstrass curves.

Nova

With the preparation of halo2curve library, we are able to implement Group trait as well as other necessary traits required by Nova library for BN256-Grumpkin curves. This step is a straightforward implementation comparing the pallas-vesta curves.

Nova-Scotia

This repo requires minimal modifications, we just need import

$G_1,G_2$ from BN256-Grumpkin curves in halo2curves as we already added all necessary components in halo2curves and Nova.

Nova-Maci

The workflow of Nova-Maci library is the following grpah:

1. In MACI library, maci-cli will generate R1CS file, circuitInputs and witnessGenExe artifacts.
2. Nova-Scotia will create PublicParams based on the size of R1CS file, generate witness using witnessGenExe and circuitInputs, and finally IVC Circuit from R1CS file
3. Nova-Scotia will call Nova library to generate either RecursiveSNARK or CompressedRecursiveSNARK for each step
4. Verifier will verify the last step of RecursiveSNARK or CompressedRecursiveSNARK

On-chain Verifier

This is the last missing piece. We could use circom or bellperson library to write the verifier on Spartan proof that created by Spartan prover from Nova library.

Reference

MACI
nova
nova-scotia
nova-maci

tags: public nova nova-maci