# 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'\xrightarrow{iso\_map} 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\xrightarrow{hash} u\xrightarrow{map\_to\_curve} (x',y')\xrightarrow{iso\_map}(x,y)$$
We need to implement above $3$ functions. The first thing we need to find is the isogeny map between $E'$ 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\neq 0$, we have to find isogeny mapping $E'\rightarrow E$ such that $E'$ 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.
1. `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
1. `Nova-Scotia` will call `Nova` library to generate either `RecursiveSNARK` or `CompressedRecursiveSNARK` for each step
1. 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](https://github.com/privacy-scaling-explorations/maci)
[nova](https://github.com/microsoft/Nova)
[nova-scotia](https://github.com/nalinbhardwaj/Nova-Scotia)
[nova-maci](https://github.com/chaosma/nova-maci)

###### tags: `public` `nova` `nova-maci`