# MACI v3 Design propoasl

> This is a proposal for MACI v3 in collaboration with 3327

## Abstract

MACI is a private voting protocol offering an unique property, anti collusion. Currently, the protocol has been mostly used in public goods funding application, but there are untapped use cases where MACI could also be of great use, namely governance, and local elections.

### Issues

It is no secret that MACI has several issues, some of which are presented below in no particular order:

* It costs money to use
* A coordinator can decrypt votes before the poll ends and thus collude with bribers
* Key changes and reverse message processing still do not solve key selling and are bad UX
* A voter might not have an incentive to not sell their key in the current architecture, just wait for another maci/poll instance to be deployed

#### Costs

Given the on chain nature of MACI, there are some costs involved. Can these be completely removed? Well not really, unless we want to lose the censorship resistant properties of blockchains.
Can these be offset? Yes totally, we could (and will) look into [Paymasters](https://www.alchemy.com/overviews/what-is-a-paymaster) and bringing certain logic [off-chain](https://ethresear.ch/t/maci-with-mostly-off-chain-happy-path/19527/) but anything not involving blockchains opens up for censoring (not referring to the paymaster example here), so at the end of the day to be completely sure you will not be censored, you will have to submit your own transactions on chain.

Having said that, any improvement when it comes to reducing costs, is more than accepted and the MACI roadmap does 100% include AA improvements as well as implementing some sort of relayer system as described in Vitalik's post.

#### Coordinator can decrypt votes before the poll ends

This is quite a serious issue, and solving this one is a high priority. Given that the coordinator can access intermediate tally results, or put simply, can decrypt all votes at all times, this gives them extreme power. For instance, they could be colluding with bribers to show them the actions of their bribees. At that point, MACI anti collusion protection would not hold true anymore.

For instance, key changes would not really mean much if a coordinator can correlate the new key with the old one. Please refer to this [issue](https://github.com/privacy-scaling-explorations/maci/issues/1566) for more info.

**Key changes and reverse message processing**

This is a tough one, as every time we start brainstorming about this we go down the rabbit hole. Let's take a look at "all" possible scenarios where:

1. Key changes are enabled and we process messages in sequential order
2. Key changes are disabled and we process messages in sequential order
3. Key changes are enabled and we process messages in reverse order
4. Key changes are disabled and we process messages in reverse order

Something to keep in mind that will apply to all scenarios is that if you give away your original key without having a copy, it doesn't matter whether there's key changes or which order the messages are processed, you won't be able to do anything about it. For that, we will need to resort to other ways to prevent users from selling their voting rights.

Let's get started.

**key changes + sequential order**

Bad:

* briber can bribe you by saying:
* you signup
* you send a keychange message with this key the briber controls
* this can be bundled up in one smart contract call with a custom contract made by the briber
* Result: you lost your voting rights

Good:

* If the voter has already signed up before they are contacted by the briber, and a poll is running, they could have already changed the key and then the briber couldn't really trust bribing the user because the first key would be invalid even if sold to the briber (unless they first ask the coordinator for confirmation)
* Sequential ordering makes things so much easier on the client side, no need to be strict about batches, can just keep track of the nonce client side and continue sending messages, overwrite, etc.

**no key changes + sequential order**

Bad:

* I'm not sure

Good:

* You cannot change the key to one that the briber owns
* If you share your key with the briber you can still override messages so at the end of the day this is challenge between you and the briber to guess each other nonces. For example
* Voter signups and sends his first batch of votes [1, 2, 3, 4]
* Briber tries to bribe and gets a copy of the key (they confirm it's valid by checking the signup tree)
* They are not really sure if the bribee sent a vote or not already, and are unsure of which nonce to use. They send 10 votes [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. At this point from vote 5 to 10 they might work but what if there are no voice credits available? At that point the briber could instead decide to send as many messages as there are vote options so [1, 2, 3, 4, 5, n], all with vote weight zero. This way they might be able to override some (most maybe) votes from the bribee. But they could not be sure. This could be because imagining the bribee sent votes with nonces [1,2,3,4] and there being 10 options, the briber sends votes with nonce [1,2,3,4,5,6,7,8,9,10], they would only be able to overwrite half of the vote options, given the first 4 messages would be invalid due to the expected nonce being 5. At this point you might think that the briber can never be sure so why would he bribe? (unless of course they could collude with the coordinator and know all bribee actions).
* UX is just so much better, no key changes makes code smaller, frontend/client applications would have such an easier time integrating maci and allowing for vote overriding (which is quite tough currently with reverse processing)

**No key changes + reverse processing order**

Bad:

* Reverse processing is bad UX and makes it hard to overwrite previous votes (you can only submit every vote in one batch, to override you will need to re-submit the same batch + your changes and that becomes hard to track on the frontend, especially when each message is encrypted with an ephemeral key)

Good:

* If you share the key it's a race to whoever sends the last message (or batch) to invalid previous ones - compared to the case with normal ordering where you have to guess nonces, here you can be sure that sending the final batch with the nonces in reverse order ending with 1 will always work - This becomes a race with the briber and something they might be able to win due to them likely having more funds available (if you need the bribe means you probably need money?) - for this I would say it's semi-good not really a good point in favour of this flow

**Key changes enabled + reverse processing order**

Bad:

* Reverse processing is bad UX and makes it hard to overwrite previous votes (as describe above)
* Key changes only use is to invalidate all previous messages. So the briber will never pay a bribe for a key change, only to actually buy the full key rights.

Good:

* You can overwrite messages by sending the last message but this becomes a race with the bribee/briber

#### No incentives to not sell your key

Currently, there are no incentives to not sell your key. Sure, you might lose access to a voting round, but then for another round you can register with a new key and that's it.

What if there was a way to incentive users to not sell their key? Something along the lines of losing reputation, imagine you sell your key to the briber, then he could prove he used it and your reputation would be affected by that and thus you might be negated access to any other polls?

Or, what if the poll specific keys were generated as follows:

Original secret = "secret"

Poll1 secret = "secret" + pollId = "secret1"
Poll2 secret = "secret" + pollId = "secret2"

One of the disadvantages of the anon poll joining flow is that these keys are throwaway so you could sell the key for the poll and still keep possession of your original key to join other polls. But if you sell your "secret1" or "secret2" then you basically give out your original key.

This could be done inside the circuit that is used to generate the proof for joining the poll, as we already have the secret (private key) as input to the circuit to generate the original public key + nullifier.

Having this public "salt" value doesn't make it any less hard to bruteforce the original key.

We will also get into another way to make key selling harder in the next few sections when we start talking about adding multiple trees in the maci contract.

### Features

#### Do not allow coordinator to decrypt the results until the end of the poll

This proposed solution does not prevent collusion between the parties in charge of the key, and the could be achieved with MPC, though the same issue would be present in an MPC protocol too.

The solution was proposed by Aleksander from [3327](https://3327.io) and can be called "key sharding". We believe this approach will work well in use cases such as local governance, where there can be different parties running for the election, each with their own interests.

Furthermore, this change does not affect the protocol, as long as MACI is aware, the public key is required to deploy the poll, and the private key to run the finalisation. How this key is calculated can be an external component (thus customisable).

We start by defining the role of "Guardian", which is an entity that guards the key from the coordinator. To generate the coordinator key we start by deciding how many guardians will be involved. Let's image we start with three guardians, now the MACI key will be generated from:

MACI PrivateKey: Gs1, Gs2, Gs3, Cs (Gs = Guardian secret, Cs coordinator secret)
MACI PublicKey: Gp1, Gp2, Gp3, Cp (Gp = Guardian public, Cp = coordinator public)

Each of the Gs is sharded into multiple shards (to be decided on initialisation), each of them given to a member of of the Guardian "party".

To bootstrap the key we generate the public keys Gp(n), add them up and give it to the coordinator. The coordinator will then Calculate the final public key, let's call it Fp. Now they can deploy a poll, and they do not have access to the private key, so they cannot decrypt the messages.

At the end of the poll, we then can send the secrets to the coordinator so they can compute the final private key, let's call it Fs. Now the coordinator can decrypt and process then votes, though it's too late to collude with bribers. All other properties of MACI still remain so they cannot censor any votes. Though they still can decide to not provide any results (though in the local elections case, I wonder what happens if the ruling party or whoever is the coordinator in this case just decides to not publish results, a riot?).

The generation of the Gs and Gp would be on a k to n protocol, so only k out n participants are needed to generate the Guardian secret. On the other hand, to generate the protocol secret, we need a n to n, so every guardian is needed to generate the protocol key, reducing the risk of collusion between them.

If we can implement this, then we would make it very hard for messages to be decrypted before the end of the round, imagine in a 10 party system, all 10 of them would need to agree to share their secret with the coordinator before the round ends. This way there would be no collusion possible between a briber and the coordinator, making a lot of the attacks on MACI unfeasible.

#### One MACI contract and multiple trees

Feeding back to the issue of users selling their key, what if selling their key was basically the end of their participation in global governance? Sounds deep, but hear us out.

Let's imagine the MACI contract become a registry of polls and a registry of state trees. This would incentivise re-usal of code, of signup lists, and also penalise key selling even more as users will not be able to access any poll.

Through a list of reliable gatekeeper contracts, and following a [minimal proxy pattern](https://solidity-by-example.org/app/minimal-proxy/) we could have several implementation contracts deployed and with the use of [clones with immutable args](https://github.com/wighawag/clones-with-immutable-args) we could allow new gatekeepers to be deployed in a safe way - we know the implementation code will not change and that it is the trusted and audited one.

This way, round operators could deploy their gatekeeper contracts with their own constructor parameters, or directly use another gatekeeper contract. When creating a poll, they would just need to specify from which gatekeeper contract to accept signups, and anonymously allow users joining their poll.

This would lead to some sort of three signup phase to join the first poll:

1. Signup to MACI by passing a strong sybil resistance mechanism - [zk passport](https://github.com/zk-passport/proof-of-passport)
2. Signup to a specific gatekeeper by passing custom requirements (e.g. country passport, owning NFT, owning an EAS attestation, etc.) and by proving you signed up the first tree
3. Signup to the poll anonymously by proving you signed up to the tree requested by the poll

Given this flow, if you sell your original key, you will not be able to join any more polls deployed from this MACI instance.

Some of the drawbacks with this flow would be the initial high number of signups and thus the potential costs, as well as forcing everyone to go through one sybil solution at the top. A more relaxed flow, until an identity solution like zk passport is more widely available (i.e. more passports support as well as a larger usebase), could start by implementing the cloneable proxy pattern for gatekeepers, and start by making the MACI contract a registry of state trees, to incentive reusal of contracts/lists rather than spinning up new contracts every time. State trees gated by strong identity solutions like anon-adhaar could be easily re-used through several events/polls.

#### Custom voice credits per poll

One issue in the current MACI architecture is that for each poll span up from a single MACI instance, the voice credits are always the same. This makes the concurrent poll design not adapt for quadratic funding, where usually voice credits are based on a contribution given. So if they need to contribute money to signup, each poll (round) to which they vote for, will start with the same voice credits. However, this is not ideal as the contribution will have only be made once, and thus for only one round.

MACI v3 could remove the `initialVoiceCreditProxy` from the MACI signup, and instead add it at the Poll level. The state leaf in the signup tree would simply become the hash of the MACI public key, and what we know now as the `StateLeaf` could be created on the poll when joining it. This feeds into the anonymous poll joining work being carried out by [3327](https://3327.io) and would simplify the data required for the poll joining proof generation, as the voice credits would not be needed anymore.

Thus, each Poll could define a custom `initialVoiceCreditProxy`, to either assign constant credits, or custom based on certain conditions (money contributed in QF, tokens held in DAO governance, etc.).

This would work very well in DAOs too, as each vote is a point in time vote with the balance had at time of signup (something akin to [snapshot](https://snapshot.org/#/)).

#### Custom Tally Function

(define function of vote) - encode a function into the circuit and evaluate whether this was used ( @ZjAqj4FTQ1Sq2KM2tNx6oA please add details here )

The idea is to be able to support differt voting/tallying algorithms, and do it at the tally level to simplify the logic of the circuits. i.e. each voter can only vote max 10 to each project, they vote 20, rather than checking if each vote is > 10 and adding extra constraints for each message we process, we instead allow voters to submit > 10 and use more of their voice credits, but when tallying, we check if each ballot on this vote option has > 10 as weight, we limit that to 10. This way we save constraints but reach the same result.

MACI should be used as the base layer for all types of voting, and this is the first step for it.

Another untapped use case of MACI could be collection of signatures, referdum or petition. For instance, registering for a poll created for a petition, could be directly thought as signing the petition. Basically, a state tree (holding poll signups) could be thought as a signature collection mechanism. This way, we wouldn't even need any tallying, just

#### Reduce (or completely remove) costs for users

In order to reach actual adoption, it is important to remove costs for users, otherwise they might not be incentivised to participate in the system.

Account abstraction is one of the first steps into this, such as introducing paymaster to subsidise gas costs. However, at a scale, a paymaster is not enough. Imagine 1 bilion voters, that would be too much of a cost for the organisers. On top of paymasters for small rounds, we plan to work a sort of relayer system as described [here](https://ethresear.ch/t/maci-with-mostly-off-chain-happy-path/19527) - some of the tasks are detailed [on our gh board](https://github.com/orgs/privacy-scaling-explorations/projects/40/views/21).
The goal is to build a simple system where one (or more) entity can submit votes on behalf of users. This entity (relayer) collects votes, and once it has `batchSize` votes they add them to a merkle tree or hash chain and post the hash on chain. The actual vote data is published on IPFS so that voters can check. Voters when submitting votes will get back a confirmation and the index of the position of their vote(s) in the next batch. We wanted to have a sort of claim system where a user could submit claims that their messages were not counted for, but there is no way to ensure that claims are valid, so it would open up the system for span and availability attacks where a coordinator (even if honest) would have to submit confirmation that the claim is invalid for infinite claims, thus making it too expensive for them to continue using the system.

For that, we believe at least for now, users who believe they have been censored, can go directly on chain, and to support honest users, we could even have a paymaster (the issue here is either supporting everyone or supporting none with expenses, as supporting only some would basically mean censoring others who try to use the system to submit votes on chain when the paymaster funds run out). While not perfect, this is still an improvement from the current system, where in a happy path scenario, users do not need to pay to use the system.

### Simplify code by removing key change and use sequential processing

In order to better improve user experience and easiness of integration, MACI v3 should come without the key change, which we have proven above (unless there's something we missed?) has no real value, and with sequential order processing of messages.

With sequential processing it will be very easy to implent batching on frontends/clients as messages won't need to be sent all in one batch, but the nonce can easily be tracked on the frontend for new messages to be sent afterwards (whether they are new votes or overriding previous ones).

### Registry contracts

In order to keep track of data for polls, we should be adding registries contracts. These contracts will hold an immutable record of the available vote options, as well as an address in case the voting round involves funding.

At his simplest, a registry contract could hold a state variable named `roundData` which is a string containing the IPFS hash of the round metadata. The metadata could look something like:

{
    pollName: "name",
    description: "A Poll for x country election"
}

Then for each project, we could have a structure akin to the following, stored in a mapping or array.

struct project {
    metadataPin: string 
    address: address
}

Ideally this contract should be deployed before a poll is started and should be somehow linked to a poll/tally contract.