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

1 Like

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.

3 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

7 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.

1 Like

Hi,

I am a bit confused here about the collusion resistance property.

Seems it is a mixture of two classic security properties studied in the digital remote voting community.

First, it looks quite similar to receipt-freeness, where a voter is prohibited from selling his vote as there is no way for him/her to prove the voted option.

But we have another desired property, coercion resistance, formalized by JCJ. It showed that a coerced voter can evade coercion/threat from the adversary by giving away a fake credential or revoting to overwrite the coerced vote.

So I see the collusion resistance property is essentially equivalent to recipient-freeness here.
I think coercion is also a potential threat to blockchain-based voting protocol. I need coercion resistance in MACI as well.

1 Like

MACI is receipt-free in precisely the way you described.

A voter in MACI can create a fake receipt that is indistinguishable from a legitimate vote, by switching keys and casting a new vote and sharing a receipt from the now invalid vote.