🤫MACI 1.0: Under-constrained Circuit

Book an audit with Zokyo

Summary

Related Vulnerabilities: 1. Under-constrained Circuits, 2. Nondeterministic Circuits

Identified By: PSE Security Team

MACI is a dapp for collusion resistant voting on-chain. Encrypted votes are sent on-chain and a trusted coordinator decrypts the votes off-chain, creates a SNARK proving the results, and then verifies the proof on-chain. The SNARK circuit logic aims to prevent the coordinator from censoring any valid vote - the proof should fail verification if the coordinator attempts to do so. However, a missing logic constraint in the circuit allows the coordinator to shuffle some votes and render targeted votes as invalid. This effectively allows the coordinator to censor any vote they choose.

Background

In order to be able to vote, a user must sign up to the MACI smart contract with a public key. These public keys are stored on-chain in a merkle tree. Users need to know the private key of these public keys in order to vote. When users cast a vote, they encrypt their vote and post it on-chain. Users can override their previous vote by sending a new one. MACI has certain rules for a vote to be considered valid, and the newest valid vote will take precedence over all other votes. The vote includes a stateIndex which is the position of the associated public key in the merkle tree. If the voter doesn’t know the private key of the public key at stateIndex, the vote will be considered invalid. When the coordinator processes all of the votes, they must only count the newest valid vote for each user. The SNARK circuit logic is designed to constrain the coordinator to doing exactly that. Therefore, if the circuit works as intended, the coordinator is not able to create a proof of voting results that include invalid votes or exclude valid votes. It is censorship resistant.

The circuit ProcessMessages.circom takes as input an array of user public keys -currentStateLeaves[] - along with the votes to process - msgs[]. The vote actions in the msgs array are processed on the public keys in the currentStateLeaves array:

// The state leaves upon which messages are applied.
// Pseudocode
transform(currentStateLeaf[4], msgs[4]) ==> newStateLeaf4
transform(currentStateLeaf[3], msgs[3]) ==> newStateLeaf3
transform(currentStateLeaf[2], msgs[2]) ==> newStateLeaf2
transform(currentStateLeaf[1], msgs[1]) ==> newStateLeaf1
transform(currentStateLeaf[0], msgs[0]) ==> newStateLeaf0

In MACI, a valid vote message can be used to change a user’s public key. From that point on, user’s can only use the new public key to update/create votes. The transform function will output the updated state leaf with the new public key if it was changed.

The Vulnerability

The currentStateLeaf array is ordered by the coordinator. Therefore, the coordinator effectively has control over which public key a new vote message is applied to. Therefore, they can choose to apply a vote message from one user, to another user’s public key. This will cause that vote message to be considered invalid since it doesn’t match the public key.

There is a constraint ensuring that a message’s stateIndex matches the public key it was applied on, but this constraint only marks a vote message as invalid if so. Before the stateIndex is checked, the circuit checks other cases where the message may be invalid, such as if the public key matches this new vote message. If it gets marked as invalid, the stateIndex check won’t make any changes. This circuit is under-constrained.

If a malicious coordinator wants to censor msgs[3] (the 4th voting message), then they will set currentStateLeaf[3] to the 0 leaf. Then, msgs[3] will be marked as invalid since the public key doesn’t match. The check that currentStateLeaf[3].index === msgs[3].stateIndex is avoided since the message is already invalid. The coordinator has effectively censored msgs[3].

The Fix

The main issue that needs to be fixed is constraining voting messages to the intended public keys. The circuit is quite complicated so other changes needed to be made, but the most significant change was adding the following check before marking a vote message as invalid:

// Pseudo code
currentStateLeaf[i].index <== msgs[i].stateIndex

This check ensures that the vote message is applied to the intended public key (state leaf) before marking any message as invalid. Therefore, a coordinator can no longer mismatch vote messages to unintended public keys and purposefully mark them as invalid.

Conclusion

MACI (Merkle Anti-Collusion Infrastructure) is a decentralized application (dApp) designed to facilitate secure, collusion-resistant voting on the Ethereum blockchain. The voting process involves users submitting encrypted votes to the blockchain. These encrypted votes are later decrypted off-chain by a trusted entity called a coordinator. The coordinator then generates a zero-knowledge proof (zk-SNARK) verifying the integrity and accuracy of the vote tally, which is later verified on-chain.

Objective:

One of MACI's primary goals is to be censorship-resistant. This means that the coordinator shouldn't be able to exclude valid votes or include invalid ones in the voting results. The zk-SNARK circuit logic is there to ensure that the coordinator stays honest.

Vulnerability:

However, there was an oversight in the zk-SNARK circuit logic, which is detailed as follows:

1. How Voting Works: When users vote, they encrypt their vote and post it on-chain. Each vote is linked to a user's public key (saved in a Merkle tree on-chain), and only the owner of the associated private key can generate a valid vote for that public key. Users can also update their public keys by submitting a valid vote message.

2. The Problem: The coordinator, when processing votes, determines the order in which the votes are paired with the public keys. This means the coordinator can purposely mismatch a user's vote with another user's public key, rendering the vote invalid because it doesn't align with the expected public key.

3. The Loophole: There were constraints in place to check that a vote was linked to the correct public key. However, there was an order of operations issue. Before checking if a vote matched its intended public key, the circuit checked for other invalid conditions. If any of these other conditions were met first, the circuit marked the vote as invalid without ever checking the public key association. This allowed the coordinator to game the system and intentionally mark valid votes as invalid by mismatching them.

4. Example: Let's consider a scenario where a coordinator wants to censor a specific vote (e.g., msgs[3]). They can purposely pair this vote with an incorrect public key (currentStateLeaf[0], for example). Since the vote doesn't match this wrong public key, the circuit marks it as invalid before even checking if it was associated with the right public key in the first place. This flaw provides an avenue for the coordinator to selectively censor any vote they want.

The Solution:

The fix involved ensuring that each vote message was appropriately paired with its intended public key before any other validity checks occurred. This prevents the coordinator from intentionally mismatching votes to public keys to mark them as invalid. In essence, the solution restores the censorship-resistant property that MACI aims to achieve.

In simpler terms, there was a flaw in the system that allowed a trusted party (the coordinator) to exploit the order of checks and manipulate voting results. This flaw was identified and fixed to ensure that votes are always paired with the correct user and that the voting process remains fair and tamper-resistant.

References

1. Issue on Github