Minimal anti-collusion infrastructure

We are staring to implment this http://github.com/barryWhiteHat/maci

If anyone wants to join this effort please join https://t.me/joinchat/LUgOpE7J2gstRcZqdERyvw

Hey everyone, just wanted to point out this topic, since it’s about a quadratic funding app built on MACI.
The project started at ETHDenver, where @barryWhiteHat and @weijiekoh helped us wrap our heads around MACI.

2 Likes

Hi all, I’ve recorded a basic explainer and demo of MACI: https://www.youtube.com/watch?v=sKuNj_IQVYI

It’s based on the implementation we’ve built here: https://github.com/barryWhiteHat/maci

4 Likes

EDIT I realized that MMRs were unnecessary for this, so I updated the post accordingly.

EDIT 2 After thinking about this more, I realized there is a further simplification where we replace the hash of the history with a nonce. I also realized that the vote buyer and vote seller can do a 2 party MPC to create a signed message for which only the buyer knows the nonce, so this does not totally prevent the attack that was described. This still seems like it could be an improvement to me though, in that instead of writing a potentially large new public key to the state, we are only writing a nonce.

This attack described by @barryWhiteHat seems concerning to me.

This mitigates the attack, but if the attacker guesses the number of messages a user sends during the key-switch phase, then they can still offer to pay for the first vote after the key-switch phase by requesting that number of key-switch-messages followed by an action message. Thus, this only decreases the expected number of votes per attacker money by a factor roughly equal to the number of key-switch messages in this phase.

With an eye to preventing this kind of attack here is a version of MACI which makes this kind of attack impossible harder. I think it also simplifies the protocol somewhat, but there can be O(1) additive increase in message size, ZK-SNARK circuit size, and state-per-participant.

In order to avoid vote-selling by an attacker that can add the first messages to the list, it is necessary to have any sequence of messages be “undoable” in the sense that you must be able to add more messages to the list that invalidate these actions. To this end, in this version of MACI we get rid of the key_change messages. Instead, we require action messages to include the tip of a hash chain of all messages previously sent from that account a randomly generated nonce.

The operator now maintains state[i].action and state[i].nonce for each participant. When a message is received, the operator checks that the signature is valid and state[i].tip_hash = message.nonce. If these checks pass, then state[i].action is updated to the new action and the update state[i].nonce is (optionally) updated to a new nonce.

A participant will now always be able to update their action, even if they update their initial action in the first message received by the system. Additionally, the participant sending the last message received by the system will not be able to prove their vote, because even if they expose their final encrypted message, they will be able to make actions beforehand that cause the hash chain tip on the final message to be invalid change the nonce, invalidating that message.

Indeed, since the nonce and action are updated simultaneously, one could just modify the action field to contain a few extra bytes of data to be ignored by the mechanism. This leaves the protocol almost exactly the same as the original, the only change is that the change_key messages are removed and a comparison against the old action is added to the message and SNARK.