Future work for MACI

Hey everyone. Today we wanted to discuss potential research topics for MACI, and collaboratively figure out how to best approach them, so please do comment on this or reach out on our discord.

Please note that this discusses the current implementation of MACI by PSE, which originated from Vitalik’s post. This implementation does not 100% follows the original proposal.

Let’s start with a recap on MACI, and how this implementation differs from the original post.

What is MACI again

Minimal Anti Collusion Infrastructure (MACI) aims to be the most secure and scalable voting system. We will soon look into why this (the most secure) is not yet the case.

In MACI, we have two type of users (in its most basic form):

• a voter
• a coordinator

The voter is identified by an EdDSA key, which is stored in a merkle tree on chain. Voters can cast votes from any ethereum wallet, however only votes signed by a registered key will be counted.

The coordinator, identified by a EdDSA key which is made public for each poll (and can vary), is supposed to be an honest figure which is in charge of tallying the results. This figure can decrypt all votes, and decide to not tally the votes (liveness issue). On the other hand, thanks to the Zero Knowledge circuits and the smart contracts, they are not able to censor any voter, nor provide invalid results.

Registration

Registration can be gated in several ways, however this is outsourced to a gatekeeping system, which while for now bespoke, will soon be replaced by Excubiae. In simple terms, potential voters provide some evidence that they can pass they gatekeeping requirements, such as proof of passport (not implemented yet), anon adhaar, owning an EAS attestation, together with an EdDSA public key, and if everything checks out, they are added to a merkle tree (which is part of the MACI contract)

Now that they are registered, they can access any poll that is spawned from the MACI contract where they registered.

In an ideal scenario, users would register to this smart contract by passing very strong anti-sybil checks (proof of passport) then could reuse their identity for any voting.

Joining a Poll

Registered users can prove ownership of a key stored inside the MACI state tree in order to join a Poll with a new key. This is akin to Semaphore signaling: you are part of a group (merkle tree), and you want to send an anonymous signal; you can send the signal as long as you can prove membership of the group. And the way you do that is by sending a zk proof that you know the private key that would derive a public key inside the merkle tree, without specifying which key exactly.

By using different wallets (or relayers), and waiting for others to join the tree, you could effectively join polls anonymously with a new key.

At the moment of joining, you are assigned some voice credits which determine your voting power (these can be constant or assigned based on some custom criteria). Voters might also need to pass another gatekeeper at this stage if this is something that is required by the contract deployed.

Voting

We mentioned before that the coordinator makes public their EdDSA key, this is used by voters to generate a shared key using ECDH.

At the time of voting, the user would generate a random EdDSA key, take the coordinator public key and compute the shared key:

sharedKey = ECDH(coordinatorPublic, randomPrivate)

Now with this key they can encrypt their message (vote or key change) using Poseidon cipher (paper).

The message format can be seen here. I’ts important to notice that each message has a nonce which must be sequential.

Then, the vote is sent on chain to a Poll smart contrat, alongside the public ephemeral key. This will be used by the coordinator to generate the shared key and be able to decrypt the vote. Passing an invalid encrypted message or public ephemeral key will result in the vote not being counted.

The message is hashed together with the public key and inserted into an hash chain on chain. The coordinator thus must process each message with the key that is sent.

Coordinator processing

The coordinator is in charge of tallying votes and does so by doing the following:

1. Fetch contract events to pull signups and votes
2. Reconstructs all structures locally
3. Decrypts votes and process them
   • check validity of signature (all votes must be signed with the voter private key)
   • check validity of credits used
   • check validity of option chosen
4. When processing votes it starts populating user ballots (a ballot looks akin to a mapping between vote option and vote weight)
5. Generate circuit inputs for proving each batch of message processing (we do things in batches because otherwise circuit constraints would go up the roof)
6. Generate proofs for a batch and post them on chain
7. Tally the votes (in batches of n ballots)
   • sum up votes to generate the tally
8. Generate inputs for the tally circuit
9. Generate proofs and post them on chain

Currently the bottleneck is the coordinator, as they do all the heavy lifting. It might be possible to reduce the constraints of the circuits by requesting that users send zk proofs of the validity of their vote/ballot when voting, so the validation is not needed on the coordinator side.

How it differs from the original implementation

According to the original protocol specs, voters can change keys. A message to change key works just as any other vote, however the public key parameter of the message must be the one of the new key. The vote should still be signed with the original private key. A coordinator can track key changes so if they do decide to collude, they would still be able to inform potential bribers that the key change happened.

However, currently key changes are not really “implemented” per se. This is because messages are processed in reverse order. This was originally discussed and implemented here.

On the other hand, a voter could send a key change message at the end to nullify all of their previous votes.

What are the issues that we would like to solve

Problem 1: Coordinator pitfalls

In MACI, the coordinator can:

• decrypt all votes and collude with either voter or briber
• decide to not finalise a poll

They cannot:

• Censor users - all votes are stored on a on-chain data structure (hash chain) and must be processed by the coordinator (we prove that inside the circuits)
• Provide invalid results - circuits accept public inputs coming from variables stored in the smart contracts (number of signups, merkle tree data for the signup tree, data for the votes data structure, number of votes, coordinator key) - zk proofs must be computed and verified on chain for each batch of votes

Based on the above, we can see that the ability for a single coordinator to be able to decrypt votes and finalise a poll is not great.

Possible solutions

Below are some of potential solutions we could implement to solve this problem

• co-SNARK
• HE/FHE
• Multiple coordinators

It seems that for both the co-SNARK or HE/FHE approches, aside from collusion between the nodes (which effectively in both cases hold the key for decryption collaboratively), we could be increasing the anti coercion properties of MACI.

On the other hand, liveness might still be an issue even with a k of n protocol, but it does get better than it is currently, where we rely on a single entity to post the results.

What is not clear yet, is how much performance would be affected by these solutions, neither how complex it would be to implement them. Furthermore, what is the most “future proof” solution?

Something else to consider with either of the above approaches is how to keep nodes incentivised to participate? Seems like similar solutions are introducting some sort of economic component to reward well behaving nodes, and punish (slash) the ones that do not participate “correctly”.

The approach with multiple coordinators could definitely help with the liveness issue, as we’d only need one out of x coordinators to provide the results, and we can also be sure that these are correct. However, now instead of one entity being able to decrypt the votes, we have multiple entities with such privileges, which could all be colluding with bribers or with voters themselves. The protocol would not change, but instead each voter would need to be submitting votes encrypted with the multiple coordinators keys.

Co Snark

Some ground work on a MPC version of MACI has been done by Lev and Yaroslav.

Given the increased computation requirements for MPC nodes, it is suggested that voters take on some of the burden, by providing a zk proof attesting the validity of their vote/ballot.

Homomorphic Encryption

We are seeing an increase in similar protocols being proposed/implemented, namely Vocdoni Z and CRISP (Enclave). Vocdoni Z plans to use homomorphic encryption, while CRISP will use fully homomorphic encryption.

It seems like this approach would require more changes to the protocol, compared to MPC.

Problem 2: Accessing data for proof of inclusion

One of the recent changes for the new version of MACI is to allow users to signup anonymously to each Poll. That is because currently there are no key changes due to the reverse message processing, and even if there were, it would not be possible to be anonymous to the coordinator as they could be tracking the key changes.

For that, the new version will work akin to Semaphore:

1. Signup to the MACI contract (by passing some gatekeeping controls, ideally something strong and generic like proof of passport/national id)
2. For each poll that is span up from this MACI contract, users can join a poll by submitting a zk proof (akin to submitting a signal in a semaphore group) where they prove ownerhsip of a key inside the MACI state tree. If the proof is valid and they have not registered twice (nullifier), then they can register to the Poll state with a new anonymous key.

In order to submit the proof of inclusion, they will need to fetch the data, and given we want this proof to be submitted client side, we might eventually run into cases where users cannot join polls because they are not able to download all of the data required to generate the merkle tree structure.

This problem is something that Semaphore faces too, so any solution would be helping out both projects (and potentially more).

Problem 3

Refer to https://hackmd.io/@ctrlc03/SySlmXBPke