6 posts tagged with "security"

Minimal Anti Collusion Infrastructure (MACI) is a public good that allows one to run secure, private, on-chain voting polls.

Given MACI's open source nature, it's common for our core team to develop new features or to fix issues based on community feedback. However, it's been less common for external contributors to make significant changes to the core protocol.

Well, this soon will be a reality thanks to a MACI improvement proposal sent by the 3327 team. 3327 is collective of 10+ people working on improving blockchain technologies, with a focus on research and engineering. Their engineering team previously worked on implementing the ElGamal flow into MACI (here's a nice presentation on it from Marija Mikić at EthCC [6]). The work described in this post aims to be its direct replacement due to its simplified nature and several additional benefits.

This proposal can be divided into two parts:

1. bring unconditional privacy to MACI's voters
2. optimise inefficient merkle tree structure holding messages, by replacing it with a hash chain

1) Enable unconditional voter privacy​

Currently with MACI, if a voter performs a key change, the voter's new key would not be anonymous to the coordinator. The coordinator could collude with a bad actor to inform the latter of the key change, as the coordinator would have access to all decrypted messages.

The key focus of this improvement is to enable users to be completely anonymous by removing the link between the original signup key and the key used for voting. How would this work? Well, users sign up to vote via the MACI contract, and depending on the gatekeeper in use, they'd have to prove that they've passed the entry condition. Now, given knowledge of this key, they can signup with a new key to polls deployed by this same MACI contract.

Thus, voters can prove anonymously that they know the preimage of a StateLeaf, by passing this information to a zk-SNARK circuit, and validating this proof within the poll contract when joining with the new key. You might be thinking that everyone knows the preimage of a state leaf, as it's public information that can be taken from the contracts' logs. However, the circuit will not accept the public key directly but would instead take the private key and use it to generate the public key. This way, only users with knowledge of a specific private key can generate a valid inclusion proof.

Now after signing up to the Poll with this new key, there will not be any link to the original key, and users will effectively be anonymous. Of course users should ensure that they are using different wallets where possible.

Finally, with the use of a nullifier, it will not be possible for the same original key to be used to signup more than once for each new poll.

Are there any drawbacks? Well, yes. There will be an extra step for users to register to individual Polls. We aim to offset this cost and additional step soon either with gasless transactions or by moving some logic off-chain.

2) Message structure optimisation​

On top of the improvements to anonymity, the 3327 team aims to also replace the Merkle tree used for storing messages with a hash chain. Some of the benefits of this approach are:

• unlimited number of messages
• removal of expensive merge operations from the coordinator
• cheaper to send messages as only one hash is required to update the hash chain
• less constraints on the circuits due to simplified logic

Unlimited messages

Merkle trees are usually bound by a depth property. Together with the number of leaves per node, we can calculate the max capacity of a tree. For instance, for a binary tree with a depth of 10, we can host up to 2^10 (1024) leaves. On the other hand, hash chains do not have a limit, unless if we wanted to set one, so we technically can support an unlimited number of messages.

Cheaper operations

Hashing the previous hash chain with the message is cheaper than inserting into a Merkle tree. Additionally, removing the need for the coordinator to perform merge operations on the accumulator queues that were used on chain will greatly reduce costs and processing time.

Smaller circuits

As cited in their proposal, processing message inclusion proofs for k messages in a tree with height h requires k * h hashing operations within the circuit with 2 * k * h signal values for inclusion proofs. Processing messages with chain hashes removes the unnecessary inclusion proofs and requires only k hashes to be computed for k messages without any extra signals, as the requirement is to prove that the order and inclusion of all messages are correct.

A call for MACI grant proposals​

So what does this mean for you, Anon?

As an open-source project of PSE with support from the Ethereum Foundation, MACI is fortunate to have the resources to invest in the maintenance and improvement of the protocol. This means we're able to fund full-time developers as well as allocate grants for various research and development initiatives.

We encourage all community members to contribute to the improvement and ongoing development of MACI! After all, our goal is to build the most secure e-voting system, and this cannot be accomplished without all of your support.

As a team, we are incredibly excited about this proposal and will continue to work hard to help the 3327 team get this upgrade production-ready over the next 3 months.

To contribute to MACI, submit issues, or learn more about it, you can reach out to us either via Discord or GitHub issues.

If you have an ambitious idea you'd like to work on, reach out to us and we could create a proposal to build together! If you don't yet have a specific idea but are still keen to work on MACI, we have some research ideas which might inspire you and we could collaborate on a grant together. Feel free to explore these ideas below and get in touch:

• MACI coordinator in a TEE
• Group wise matching
• Folding schemes for MACI's circuits

References​

• 3327 team
• 3327 ElGamal flow
• 3327 ElGamal API
• Marija Mikić - Anonymity in MACI - EthCC [6]
• MACI Original idea
• MACI Anonymization

During ETHDam's Quadratic Funding round, run on clr.fund, we discovered a critical bug in MACI. The issue stemmed from the lack of validation on MACI public keys within the Poll contract. A user (spoiler alert, it was a self-inflicted denial of service (DoS)) was able to submit a MACI public key which was not a point of the Baby JubJub elliptic curve, and it broke everything.

So... what happened, really?​

Well, during the ETHDam round, there was an issue with the subgraph that caused the frontend web app to incorrectly display that the voting period had ended, which prevented users from voting.

A quick way for us to identify the issue was to directly call the Poll's smart contract to submit an invalid vote. If the contract accepted votes, that meant that it was not a MACI issue. Given the contract accepted votes, it immediately helped us confirm that the bug was a frontend issue. What we didn't know at the time was that this vote, as well as its associated key, would cause a denial of service.

The message in question can be seen on Gnosis Chain's block explorer. Below is proof that the wallet which submitted the invalid key is from one of our teammates (just in case you thought we'd want to censor it :P).

{
  "address": "0xc59975735ed4774b3Ee8479D0b5A26388B929a34",
  "msg": "This is proof that I control this wallet and dossed MACI by mistake while doing an invalid vote",
  "sig": "0x8962b66462630f12476d7bdb348f08af574ba40dd32c6f149ea26717830f13f50f4e95574e8fc909dd3dd1e20bcd85ae2c3caaf41bed6b123973353635483b7f1b",
  "version": "2"
}

One can verify the message using etherscan, paste the address, message and signature. Don't take our word for it, verify!

The message was sent alongside an invalid MACI public key. As a result, due to how MACI messages are processed, the zk-SNARK circuit failed to generate a proof, which prevented the QF round from finalizing.

A MACI public key is (supposedly, at least) a point on the Baby JubJub elliptic curve. The mistake that MACI's code made was to not validate at the smart contract level that the keys accepted as arguments were actually valid points on the curve. At the time the bug was triggered, the two coordinates of the point (x and y) were only checked to be less or equal to the curve prime order.

The MACI key in question looked like the below object:

{
  "x": 1,
  "y": 1
}

In MACI, messages are (well, should be) encrypted using a shared key generated using a random keypair and the coordinator's public key. This allows for the coordinator to reverse the process - as long as they have the random public key - and decrypt the message using the same shared key. This is achieved using Elliptic-curve Diffie–Hellman (ECDH).

Shared key generation from the user's side:

ECDH(randomKeyPair.privateKey, coordinatorPublicKey)

Shared key generation from the coordinator's side:

ECDH(coordinatorPrivateKey, randomKeyPair.publicKey)

The randomKeyPair.publicKey that was sent as {x: 1, y: 1} was eventually passed by the coordinator to a zk-SNARK circuit to try and decrypt the corresponding message and perform further processing.

When passed to the circuit, the code would perform the ECDH operation by performing a scalar multiplication between the public and the coordinator private key. This happens inside the MessageToCommand template, which calls the ECDH template. Here, there is a call to escalarMulAny which in turns calls SegmentMulAny, where we encounter the final call to Edwards2Montgomery where the error pops up.

Looking inside the Edwards2Montgomery template, we can see the operation that is performed on the public key. In short, the point is converted from the Twisted Edwards form to Montgomery form, as it allows for cheaper operations inside the circuit (whereas outside it is represented in its original Twisted Edward form).

The equation to convert between the two forms is presented below:

                1 + y       1 + y
    [u, v] = [ -------  , ---------- ]
                1 - y      (1 - y)x

We can see how passing a y of 1, the equation would result in a division by zero. Below you can see the full stack trace of the error:

Error in template Edwards2Montgomery_349 line: 38
Error in template SegmentMulAny_362 line: 81
Error in template EscalarMulAny_364 line: 163
Error in template Ecdh_365 line: 23

Please note that passing x as 0 would also trigger this error, though within the EscalarMulAny template, this case is handled and the G8 point is passed instead, preventing an error while generating the proof.

Given this issue, we weren't able to complete the proof generation for message processing. It is somewhat good news, as once a message is posted to MACI's smart contracts, it's not possible to censor it even if these messages trigger bugs.

How was the round saved?​

After understanding the bug, the team came up with a solution that would both allow EthDAM to pay out projects with cryptographic guarantee of the results, as well as provide a solution that is fully transparent and verifiable. After all, MACI is all about verifiability.

Given that the clr.fund round was run using a token with no monetary value (EthDAMToken), instead of spinning up a new round and asking users to re-submit their votes, we opted for an automated solution which would scrap all signups and contribution of this token, as well as all messages, and to re-submit them to the new clr.fund round contracts.

This way, voters can validate that all signups and votes were included, and by not submitting this invalid message, being able to generate zk-SNARK proofs and validate publicly the final tally result.

The script in question can be found in a gist. In a nutshell, the script pulled all signups from the original round fundingRound contract, and submitted them on the new contract, after having approved the new contract to spend all EthDAMToken tokens. Then, it pulls the messages, aside from the invalid one, and posts them to the new Poll contract.

After this, the EthDAM team was able to complete the tally alongside ZK proofs to be submitted on chain.

How did we fix MACI?​

To fix the bug, we added code to validate that a given point is on the curve. The Solidity library, found within the original Baby JubJub paper, was originally developed by yondonfu and for sake of simplicity, it was copied over to the MACI's repo. The code needed just a couple of small upgrades to work with more recent Solidity versions (0.8.20).

/**
 * @dev Check if a given point is on the curve
 * (168700x^2 + y^2) - (1 + 168696x^2y^2) == 0
 */
function isOnCurve(uint256 _x, uint256 _y) internal pure returns (bool) {
  uint256 xSq = mulmod(_x, _x, Q);
  uint256 ySq = mulmod(_y, _y, Q);
  uint256 lhs = addmod(mulmod(A, xSq, Q), ySq, Q);
  uint256 rhs = addmod(1, mulmod(mulmod(D, xSq, Q), ySq, Q), Q);
  return submod(lhs, rhs, Q) == 0;
}

As seen in the code above, the function will evaluate the Baby JubJub equation using the input public key x and y values. Any value that is not on the curve, will be rejected, as shown below:

// check if the public key is on the curve
if (!CurveBabyJubJub.isOnCurve(_encPubKey.x, _encPubKey.y)) {
  revert InvalidPubKey();
}

The bug was fixed with this PR. On top of preventing such invalid values from being accepted by the contract, we also added more validation across the TypeScript libraries to make it harder for users to make such mistakes.

Footnote​

The MACI team would like to first of all thank EthDAM's team for their patience while we navigated through this issue, and trusting us with coming up with a transparent solution for the round.

Furthermore, we thank mikerah from HashCloak for helping to review the fix, and their expertise in handling security incidents like this. Together with them, we looked at other repositories using similar code, looking for the same mistake, though we did not find similar protocols where an invalid key would cause a denial of service. If you are a ZK developer reading this, we hope this was a lesson that would help remind us all to always validate user input for future scenarios.

Finally, a big thank you to Raphael for explaining the math behind the issue, and suggesting that full point validation would end up being a much better solution than just not accepting y = 1.

Contract addresses​

Below is a list of the contract addresses for this EthDAM round. All code is verified on Gnosis's block explorer and can be reviewed.

RoundToken

• EthDAMToken

clr.fund Instance

• clr.fund

Original round

• FundingRound
• MACI
• Poll

New Round

• Funding Round
• MACI
• Poll
• Tally
• MessageProcessor

MACI New Version​

We decided to publish a new version of MACI with the fix (and other changes made since the 1.2 release). The new version is 1.2.1.

Please do not use the 1.2 version of the contracts for any new deployments, as it contains the bug described in this post. All other packages are safe, though 1.2.1 is the recommended version to use.

We are pleased to announce the release of MACI v1.2.0!

This is our first release since MACI v1.1.1 just over one year ago. This new release focuses on improved developer experience, security, performance and clearer documentation for users looking to learn and use MACI.

Background​

MACI - Minimal Anti-Collusion Infrastructure - is an Ethereum application that provides privacy and collusion resistance for on-chain voting. If you're new to MACI, we first recommend reading our documentation for background information and technical details.

Refactoring Work​

We prioritized enhancing MACI's developer experience by refactoring its code, fixing bugs, and improving documentation.

Key refactoring activities were:

1. Upgrading libraries to their latest versions and substituting obsolete dependencies with up-to-date and actively maintained alternatives.
2. Making the code standardized, modular, well-documented, and uniformly formatted.
3. Fixing bugs and community-reported issues.

Library Updates​

MACI has relied on custom code and dependencies since its initial implementation, notably from repositories by one of the original MACI developers, Koh Wei Jie. We felt that MACI could benefit from a dependency refresh, so we've shifted towards using actively maintained open-source libraries, such as circomkit and zk-kit.

Circomkit has become our go-to for circuit-related tasks, such as compiling circuits, generating test zkeys, and unit tests.

We've moved reusable circuit logic, like our Poseidon permutation encryption and decryption code, into zk-kit. This not only benefits MACI through more circuit usage and testing but also supports wider community adoption.

These efforts are part of a broader initiative at Privacy and Scaling Explorations (PSE) to foster open-source development and contribute to public goods. By aligning MACI with these values, we aim to enhance its utility and encourage collaborative growth. In the coming months, we're committed to extracting more of our circuit logic for broader use (track progress here) and contributing to projects that align with our mission.

Code Refactor​

We've undergone extensive efforts to clean up MACI's code:

• Removed dead and redundant code.
• Split monolithic files into smaller, logically structured ones.
• Improved documentation with detailed code comments and tools like (TypeDoc and solidity-docgen) for automatic doc generation.
• Enforced strong type safety on the TypeScript components.
• Optimized and modularized the smart contract code.
• Extended the test suites.

These improvements aim to simplify the onboarding process for new developers, ensuring they can easily navigate and effectively utilize MACI.

New Features​

Flexible Voting Strategies​

After years of built-in quadratic voting (QV) in MACI, we now support non-quadratic voting polls. This opens up the door to potential integrations with a wider variety of projects, such as DAO governance applications.

The new version of the Tally circuit (specific for non-QV), has reduced constraints, enabling a quicker proof generation process for vote tallying.

We invite projects interested in leveraging this secure, on-chain voting mechanism to reach out for potential integrations. We hope to continue to expand support for additional voting methodologies, so please let us know your project's needs!

New Gatekeeper​

In our effort to fortify MACI against Sybil attacks, we've integrated an innovative gatekeeper mechanism: EAS - you can view the contract here.

As part of configuring a MACI deployment, the coordinator sets a user signup gatekeeper contract. This contract dictates the criteria a user must pass in order to participate in a poll. For example, user might need to prove ownership of a certain NFT, or prove that they have passed some sort of proof-of-personhood verification.

With the addition of this new gatekeeper, EAS (and soon™ Hats Protocol, MACI instances could be configured to e.g. only allow Ethereum accounts with a trusted EAS attestation or those designated with a specific role by the Hats Protocol. These modules open up new avenues for access control strategies.

We expect to continue to expand our gatekeeper capabilities and welcome the community to come up with new and innovative ways to grant access to MACI's rounds, helping make MACI more customizable and sybil-resilient. The Hats Protocol gatekeeper is currently in progress and will be released soon™ (in v1.2.1).

Documentation Website​

We're excited to announce that all MACI documentation has been unified on our new website, maci.pse.dev!

This platform will serve as the definitive resource for all information related to MACI, including blog releases, documentation updates, and roadmap progress. Please report any inconsistencies you may find. As always, we welcome suggestions on how to make it better.

Security Audit​

Thanks to thorough reviews by PSE's internal Audit team, clr.fund's developer, yuetloo, and our core development team, we've identified and addressed several bugs during our recent refactoring efforts. Most notably, a critical bug in MACI v1.x discovered by Kyle, which could have allowed coordinators to censor votes, has been fixed.

For more details on our recent audit, please refer to our audit docs or view the full report.

After this audit and the resulting fixes, we feel more confident with MACI and its security.

Trusted Setup Ceremony​

Following the successful completion of our MACI trusted setup ceremony for MACI v1.1.1, we are preparing for a new ceremony to cover the security enhancements added in our v1.2.0 circuits.

To accomplish this, we'll leverage the tooling of P0tion, which helps to streamline and automate Groth16 phase2 ceremonies.

We'll update this page after the ceremony completes to include the production-ready zkey artifacts. In the meantime, the artifacts for v.1.1.1 can be found on our website, and the tallyVotes artifacts can still be used in production.

Get Involved​

MACI is deeply committed to our community, through our open initiatives like public roadmaps, transparent repository management, and a public Discord channel for interaction with our team.

With every issue, PR, feature and roadmap iteration, we welcome feedback to ensure that the continued development of MACI reflects your and the community's needs. Keep an eye out on our documentation, GitHub discussions and our official Twitter/X account for updates.

For those looking to contribute directly, report bugs, or offer feedback, our GitHub repository is open for issues and discussions. We're eager to assist with your projects or contributions.

For practical implementation insights, review our docs as well as the clr.fund and QF repositories as reference implementations. Both are quadratic funding implementations, a mechanism which otherwise is highly susceptible to collusion and bribery. Most notably, clr.fund is already working on integrating MACI v1.2.0, after having used v0.x until now. You can follow their development effort under this GitHub branch.

For any other questions or feedback, please reach out to us via PSE's Discord, in our #🗳️-maci channel. We're excited to connect and collaborate with you!

References​

• MACI GitHub repository
• MACI documentation
• A technical introduction to MACI 1.0 - Kyle Charbonnet
• Minimal anti-collusion infrastructure - Vitalik
• PSE Discord server

Release​

Here's the link to the new release code in GitHub: v1.2.0 Release.

We are pleased to announce the release of an updated version of MACI - Minimal Anti-Collusion Infrastructure v1.1.1.

This new release brings a more secure product, new features, and a much needed documentation refresh. Before we dive into the updates, let's refresh your memory on what MACI is and what it was created to achieve.

Background​

MACI is an application that provides collusion resistance for on-chain voting processes. It was originally created after Vitalik's post, and has since been revisited and improved.

MACI revolves around the need for a trusted coordinator. The coordinator is in charge of setting up the system, publishing its public key, and computing the tally of the votes. Below are the main properties of MACI:

Since its inception, MACI has been adopted by different projects, most notably clr.fund and QFI. These projects prove how effective MACI can be, especially when integrated with applications that are otherwise prone to collusion, such as funding Public Goods.

For a more detailed description of MACI, please refer to the v1 technical introduction article.

Security Audit​

MACI was audited by HashCloak in the summer of 2022. The audit team discovered certain high risk vulnerabilities, whose fixes were the focus of the MACI team in the past months.

In more details, the audit revealed two high risk issues within the zk-SNARK circuits:

• Incomplete validation when processing messages
• Integer overflow which could have allowed users to affect a coordinator's effort of calculating the subsidy by either making it incorrect or by intercepting the calculation

Another notable security issue was the lack of initialization of the AccQueue contract. This contract is used to store messages (votes or topups) for the different polls. Without inserting a zero value hash into the merkle tree contract as the first message during initialization, a malicious user could have performed a denial of service attack on a poll. This could have resulted in the poll results taking a very long time before being tallied by the coordinator.

All of these issues have been successfully resolved, on top of fixing minor issues and general code optimizations. The updated product uses a more up to date and secure version of Solidity, and more thorough test cases to verify the correctness of the solution.

New Features​

Top Up Credit​

Rather than requiring a user to sign up multiple times, it is now possible to top up voice credits by sending a top up message on the Poll contract. Withdrawals are not enabled as this would allow a malicious user to bribe others offline to transfer their keys.

Now, the Poll contract will hold all the funds deposited from users for the current poll. At the end of a poll, the coordinator can transfer the funds to a hardcoded address which can be used to fund public goods.

When a user deposits tokens by calling topup, they will also need to specify the stateTree index. The topup function will insert a topup message into the message queue for them. When the voting period ends, any call of topup function will be rejected. Both voting and topup messages have the same ending time, which ensures there is a well-defined ending state for each poll.

Please note that in this approach, the initial credit is still shared across multiple polls, and the actual credit an user can spend in a given poll is the following: totalCredit=initialCredit+topupCredit where the topupCredit is the voice credit amount deposited by the user during the voting period of the given pollID.

For a detailed description, please refer to this document.

Pairwise Subsidy​

Pairwise subsidy is a new way to reduce collusion in quadratic funding applications. If two contributors collude with each other, they can extract most of the public funding pool if they have enough funds.

In this post, Vitalik introduced this kind of collusion and also proposed a protocol to penalize this behavior. As a generalized solution, the more correlation between contributions, the smaller subsidy should be allocated to this project, as this reduces the risk of collusion between contributors. It should be noted that this solution assumes that an identity system is in place to prevent the same entity from registering with two different identities.

Please refer to this post for a more detailed explanation of the implementation.

Finally, please note that currently it is not possible to generate the zkeys for the subsidy circuit with with the vote options parameter larger than $5^2$. This issue is documented here and the team will focus on finding a solution to be able to support larger vote options.

Coordinator Service​

MACI now includes a sample coordinator service.

There are two roles in the coordinator service: admin (i.e. MACI coordinator) and user (i.e. a voter). The admin's responsibility is to ensure that the code remains updated and that the backend services are live. The user can then simply send HTTP requests to the backend server to interact with MACI, for instance, by signing up and publishing a message on chain.

The coordinator service has been wrapped into two docker instances: one for the backend server to accept user requests; one for the Mongodb service to store all necessary information on the current state such as smart contract addresses, zero knowledge proof keys and so on.

For further reading on coordinator services, please refer to this doc.

How to use MACI​

MACI can be used as a standalone application to carry out on-chain polls, or be implemented into new projects that can then benefit from its properties.

For use as a standalone application, a cli package is provided which allows coordinators and voters to use MACI. Please refer to this doc for details on how to use it.

To implement MACI into a project, the documentation can be used a reference, as well as reviewing how clr.fund and qf use MACI in their code.

MACI 0.x​

MACI version 0.x will be discontinued. MACI 1.x has feature parity, more robust code and newest features. Users are encouraged to use the latest version. Starting February 7, 2023, the team will focus solely on resolving issues for MACI 1.x, and will cease to provide support for version 0.x.

How to get involved​

Should you wish to get involved with MACI or simply report a bug, feel free to visit the repository and open an issue, or comment under an open issue to notify the team of your intention to work on it.

For any other enquiry, please reach out to us via the Privacy and Scaling Explorations (PSE) Discord.

References​

• MACI GitHub repository
• A technical introduction to MACI 1.0 - Kyle Charbonnet
• Minimal anti-collusion infrastructure - Vitalik
• Pairwise Subsidy
• Security Audit

Release​

Here is a link to the new release code in GitHub - v1.1.1 Release.

Introduction​

MACI, which stands for Minimal Anti-Collusion Infrastructure, is an application that allows users to have an on-chain voting process with greatly increased collusion resistance. A common problem among today’s on-chain voting processes is how easy it is to bribe voters into voting for a particular option. Oftentimes this bribery takes the form of “join our pool (vote our way) and we will give you a cut of the rewards (the bribe)”. Since all transactions on the blockchain are public, without MACI, voters can easily prove to the briber which option they voted for and therefore receive the bribe rewards.

MACI counters this by using zk-SNARKs to essentially hide how each person voted while still revealing the final vote result. User’s cannot prove which option they voted for, and therefore bribers cannot reliably trust that a user voted for their preferred option. For example, a voter can tell a briber that they are voting for option A, but in reality they voted for option B. There is no reliable way to prove which option the voter actually voted for, so the briber does not have the incentive to pay voters to vote their way.

Background​

For a general overview, the history and the importance of MACI, see Release Announcement: MACI 1.0 by Wei Jie, one of the creators. He also created a very helpful youtube video on the overview of MACI. To see the origin of the idea of MACI, see Vitalik’s research post on Minimal Anti-Collusion Infrastructure. Lastly, it is recommended to understand the basic idea behind zk-SNARKs, as these are a core component of MACI. The following articles are great resources:

• Introduction to zk-SNARKs — Consensys
• What are zk-SNARKs — Zcash
• An approximate introduction to how zk-SNARKs are possible — Vitalik
• zkSNARKs in a nutshell — Ethereum.org

This article will go over the general workflow of MACI and how it is capable of providing the following tenets (taken word for word from Wei Jie’s article):

• Collusion Resistance: No one except a trusted coordinator should be certain of the validity of a vote, reducing the effectiveness of bribery
• Receipt-freeness: No voter may prove (besides to the coordinator) which way they voted
• Privacy: No one except a trusted coordinator should be able to decrypt a vote
• Uncensorability: No one (not even the trusted coordinator) should be able to censor a vote
• Unforgeability: Only the owner of a user’s private key may cast a vote tied to its corresponding public key
• Non-repudiation: No one may modify or delete a vote after it is cast, although a user may cast another vote to nullify it
• Correct execution: No one (not even the trusted coordinator) should be able to produce a false tally of votes

System Overview​

Roles​

In the MACI workflow, there are two different roles: users (voters) and a single trusted coordinator. The users vote on the blockchain via MACI smart contracts, and the coordinator tallies up the votes and releases the final results.

The coordinators must use zk-SNARKs to prove that their final tally result is valid without releasing the vote of every individual. Therefore, even if a coordinator is corrupt, they are unable to change a user’s vote or add extra votes themselves. A corrupt coordinator can stop a vote by never publishing the results, but they can’t publish false results.

Before sending their vote on the blockchain, users encrypt their vote using a shared key that only the user and coordinator can know. This key scheme is designed so that every individual user shares a distinct key with the coordinator. This prevents any bribers from simply reading the transaction data to see which option a user voted for. The encrypted vote is now considered a “message” and the user sends this message to a MACI smart contract to be stored on-chain.

A very simplified illustration of this encryption can be seen below:

Vote Overriding and Public Key Switching​

Before a user can cast a vote, they must sign up by sending the public key they wish to use to vote to a MACI smart contract. This public key acts as their identity when voting. They can vote from any address, but their message must contain a signature from that public key. When casting an actual vote after signing up, a user will bundle a few variables — including a public key, their vote option, their vote amount, and a few others — into what is called a “command”. Then, the user signs the command with the public key they originally used to sign up. After that, the user encrypts the signature and command together so that it is now considered a message. This more complex description of how a message is constructed is illustrated below:

Users are able to override their previous vote as long as they sign their command with the previous public key. If the command is properly signed by the user’s previous public key, then the message is considered valid and the coordinator will count this as the correct vote. So, when a user provides a public key in their vote that is different than their previous public key, they may now submit a new vote signed by this new public key to override their previous vote. If the signature is not from the previous public key, the message will be marked as invalid and not counted toward the tally. Therefore, the public key can be thought of as the user’s voting username, and the signature is the voting password. If they provide the correct signature, they can submit a vote or change their public key — or both.

This feature, which I refer to as public key switching, is designed to counter the bribery attack where a user simply shows the briber their message, and then decrypts it for the briber to see which way the user voted. Public key switching allows users to change their public key and create invalid messages in favor of the bribers. The bribers have no way of telling if the user switched their public keys before sending in the vote shown to the bribers.

This can be quite confusing so here is an example:

1. Bob signs up with public key 1
2. Bob then creates a command that contains — a vote for option A and public key 2
3. Bob signs this command with public key 1, the key he used to sign up
4. Bob encrypts this command into a message and submits it to the MACI smart contracts
5. The coordinator decrypts this message, and checks to ensure that the command is signed by Bob’s previous key — public key 1. This message is valid.
6. The coordinator then records Bob’s vote for option A and updates his public key to public key 2

At this point, Bob has successfully voted for option A, and in order to override this vote must send in a new vote with a signature from public key 2. At this point, a briber now tries to get Bob to vote for option B:

1. Bob creates a command that contains — a vote for option B and public key 1
2. Bob signs this command with public key 1, encrypts the message and submits it to the MACI smart contracts
3. Bob shows the briber the decrypted message as proof of his vote for option B
4. The coordinator decrypts Bob’s message and sees that the signature does not match up with public key 2 — Bob’s previous key added in his previous message. Therefore this message is invalid and this vote is not counted in the final tally.
5. The briber has no way of knowing whether the vote was valid or invalid, and so is not incentivized to offer bribes to other users.

In order to get a good idea of how MACI works, it’s important to know how the zk-SNARKs are able to prove that the coordinator decrypted each message and tallied the votes properly. The next section gives a quick and much oversimplified overview of zk-SNARKs, although the readings listed in the introduction are much more helpful.

zk-SNARKs​

Essentially, zk-SNARKs allow users to prove they know an answer to a specific mathematical equation, without revealing what that answer is. Take the following equation for example,

X + Y = 15

I can prove that I know 2 values, X and Y that satisfy the equation without revealing what those two values are. When I create a zk-SNARK for my answer, anyone can use the SNARK (a group of numbers) and validate it against the equation above to prove that I do know a solution to that equation. The user is unable to use the SNARK to find out my answers for X and Y.

For MACI, the equation is much more complicated but can be summarized as the following equations:

encrypt(command1) = message1
encrypt(command2) = message2
encrypt(command3) = message3
…
Command1 from user1 + command2 from user2 + command3 from user3 + … = total tally result

Here, everyone is able to see the messages on the blockchain and the total tally result. Only the coordinator knows what the individual commands/votes are by decrypting the messages. So, the coordinator uses a zk-SNARK to prove they know all of the votes that:

1. Encrypt to the messages present on the blockchain
2. Sum to the tally result Users can then use the SNARK to prove that the tally result is correct, but cannot use it to prove any individual’s vote choices.

Now that the core components of MACI have been covered, it is helpful to dive deeper into the MACI workflow and specific smart contracts.

Workflow​

The general workflow process can be broken down into 4 different phases:

1. Sign Up
2. Publish Message
3. Process Messages
4. Tally Results

These phases make use of 3 main smart contracts — MACI, Poll and ​​PollProcessorAndTallyer. These contracts can be found on the MACI github page. The MACI contract is responsible for keeping track of all the user signups by recording the initial public key for each user. When a vote is going to take place, users can deploy a Poll smart contract via MACI.deployPoll().

The Poll smart contract is where users submit their messages. One MACI contract can be used for multiple polls. In other words, the users that signed up to the MACI contract can vote on multiple issues, with each issue represented by a distinct Poll contract.

Finally, the PollProcessorAndTallyer contract is used by the coordinator to prove on-chain that they are correctly tallying each vote. This process is explained in more detail in the Process Messages and Tally Results sections below.

Sign Up​

The sign up process for MACI is handled via the MACI.sol smart contract. Users need to send three pieces of information when calling MACI.signUp():

1. Public Key
2. Sign Up Gatekeeper Data
3. Initial Voice Credit Proxy Data

The public key is the original public key mentioned in above sections that the user will need to vote. As explained in earlier sections, they can change this public key later once voting starts. The user’s public key used to sign up is shared amongst every poll.

MACI allows the contract creator/owner to set a “signUpGateKeeper”. The sign up gatekeeper is meant to be the address of another smart contract that determines the rules to sign up. So, when a user calls MACI.signUp(), the function will call the sign up gatekeeper to check if this user is valid to sign up.

MACI also allows the contract creator/owner to set an “initialVoiceCreditProxy”. This represents the contract that determines how many votes a given user gets. So, when a user calls MACI.signUp(), the function will call the initial voice credit proxy to check how many votes they can spend. The user’s voice credit balance is reset to this number for every new poll.

Once MACI has checked that the user is valid and retrieved how many voice credits they have, MACI stores the following user info into the Sign Up Merkle Tree:

1. Public Key
2. Voice Credits
3. Timestamp

Publish Message​

Once it is time to vote, the MACI creator/owner will deploy a Poll smart contract. Then, users will call Poll.publishMessage() and send the following data:

1. Message
2. Encryption Key

As explained in sections above, the coordinator will need to use the encryption key in order to derive a shared key. The coordinator can then use the shared key to decrypt the message into a command, which contains the vote.

Once a user publishes their message, the Poll contract will store the message and encryption key into the Message Merkle Tree.

Process Messages​

Once the voting is done for a specific poll, the coordinator will use the PollProcessAndTallyer contract to first prove that they have correctly decrypted each message and applied them to correctly create an updated state tree. This state tree keeps an account of all the valid votes that should be counted. So, when processing the messages, the coordinator will not keep messages that are later overridden by a newer message inside the state tree. For example, if a user votes for option A, but then later sends a new message to vote for option B, the coordinator will only count the vote for option B.

The coordinator must process messages in groups so that proving on chain does not exceed the data limit. The coordinator then creates a zk-SNARK proving their state tree correctly contains only the valid messages. Once the proof is ready, the coordinator calls PollProcessorAndTallyer.processMessages(), providing a hash of the state tree and the zk-SNARK proof as an input parameters.

The PollProcessorAndTallyer contract will send the proof to a separate verifier contract. The verifier contract is specifically built to read MACI zk-SNARK proofs and tell if they are valid or not. So, if the verifier contract returns true, then everyone can see on-chain that the coordinator correctly processed that batch of messages. The coordinator repeats this process until all messages have been processed.

Tally Votes​

Finally, once all messages have been processed, the coordinator tallies the votes of the valid messages. The coordinator creates a zk-SNARK proving that the valid messages in the state tree (proved in Process Messages step) contain votes that sum to the given tally result. Then, they call PollProcessorAndTallyer.tallyVotes() with a hash of the correct tally results and the zk-SNARK proof. Similarly to the processMessages function, the tallyVotes function will send the proof to a verifier contract to ensure that it is valid.

The tallyVotes function is only successful if the verifier contract returns that the proof is valid. Therefore, once the tallyVotes function succeeds, users can trust that the coordinator has correctly tallied all of the valid votes. After this step, anyone can see the final tally results and the proof that these results are a correct result of the messages sent to the Poll contract. The users won’t be able to see how any individual voted, but will be able to trust that these votes were properly processed and counted.

Conclusion​

MACI is a huge step forward in preventing collusion for on-chain votes. While it doesn’t prevent all possibilities of collusion, it does make it much harder. MACI can already be seen to be in use by the clr.fund, which has users vote on which projects to receive funding. When the possible funding amount becomes very large, users and organizations have a large incentive to collude to receive parts of these funds. This is where MACI can truly make a difference, to protect the fairness of such important voting processes such as those at clr.fund.

The Privacy & Scaling Explorations team is proud to release version 1.0 of Minimal Anti-Collusion Infrastructure (MACI). MACI enables collusion resistance for decentralised applications, particularly voting and quadratic funding systems. This release is a major upgrade to the project and provides better developer experience and gas savings for users.

The code is in the v1 branch of the appliedzkp/macirepository and will be merged soon.

MACI 1.0 was audited by Hashcloak. All vulnerabilities found have been fixed. The audit report can be found here. We would like to thank our highly professional and responsive auditors for surfacing these issues and providing clear feedback for addressing them.

About MACI​

MACI is a set of smart contracts and zero-knowledge circuits upon which which developers can build collusion-resistant applications, such as voting systems or quadratic funding platforms. MACI per se is not a user-facing application. Rather, developers may build applications on top of it. In turn, such applications can benefit from the following properties:

• Collusion resistance: no-one, except a trusted coordinator, can be convinced of the validity of a vote, reducing the effectiveness of bribery.
• Receipt-freeness: a voter cannot prove, besides to the coordinator, which way they voted.
• Privacy: no-one, except a trusted coordinator, should be able to decrypt a vote.
• Uncensorability: no-one, not even the trusted coordinator, should be able to censor a vote.
• Unforgeability: only the owner of a user’s private key may cast a vote tied to its corresponding public key.
• Non-repudiation: no-one may modify or delete a vote after it is cast, although a user may cast another vote to nullify it.
• Correct execution: no-one, not even the trusted coordinator, should be able to produce a false tally of votes.

Practically speaking, MACI provides a set of Typescript packages, Ethereum smart contracts and zero-knowledge circuits. It inherits security and uncensorability from the underlying Ethereum blockchain, ensures unforgeability via asymmetric encryption, and achieves collusion resistance, privacy, and correct execution via zk-SNARKs.

Please note that MACI does not and will not have a token. In other words, it does not represent an investment opportunity.

MACI’s history​

MACI stems from an ethresear.ch post by Vitalik Buterin. Subsequently, the initial codebase was written in late 2019 and early 2020 by grantees with the Ethereum Foundation, namely Kendrick Tan, Koh Wei Jie, and Chih-Cheng Liang. MACI then saw developer adoption at ETHDenver in February 2020, where Auryn Macmillan and others started work on clr.fund, a protocol for the Ethereum community to allocate funds for Ethereum-based public goods.

After the event, we continued to work with clr.fund to improve MACI and integrate it with their application. clr.fund has completed seven rounds of public goods funding, the last of which saw more than US$6000 worth of contributions. At the time of writing, it is currently running an eighth round with more than US$20k in contributions.

Work on version 1.0 started in late 2020 with the goal of reducing the gas and computational requirements, as well as to improve its flexibility and usability, without compromising any of its anti-collusion, security, and trust guarantees. We also took this opportunity to keep up with new techniques, ideas, and tooling from the rapidly advancing Ethereum and zero-knowledge ecosystem.

Finally, in early 2021 we were very fortunate to bring on Cory Dickson to the team. His work on writing documentation, revamping MACI’s integration test suites, working with our auditors to fix bugs, and collaborating with external teams has been invaluable to the project.

Why is MACI important?​

It is very difficult for naive voting systems, particularly those which are integrated into smart contract platforms, to prevent collusion. For instance, if a simple Ethereum transaction represents a vote, a briber can easily examine its calldata, tell how its sender voted, and reward or punish them accordingly.

More broadly, collusion resistance is particularly important for cryptoeconomic systems. Vitalik Buterin describes the motivations behind MACI in On Collusion. He argues that systems that use cryptoeconomic incentive mechanisms to align participants’ behaviour can be vulnerable to collusion attacks, such as bribery. In another post, he elaborates:

if you can prove how you voted, selling your vote becomes very easy. Provability of votes would also enable forms of coercion where the coercer demands to see some kind of proof of voting for their preferred candidate.

To illustrate this point, consider an alleged example of collusion that occurred in round 6 of Gitcoin grants (a platform for quadratic funding software projects which contribute to public goods). In How to Attack and Defend Quadratic Funding, an author from Gitcoin highlights a tweet by a potential grant beneficiary appeared to offer 0.01 ETH in exchange for matching funds:

They explain the nature of this scheme:

While creating fake accounts to attract matching funds can be prevented by sybil resistant design, colluders can easily up their game by coordinating a group of real accounts to “mine Gitcoin matching funds” and split the “interest” among the group.

Finally, MACI is important because as crypto communities are increasingly adopting Decentralised Autonomous Organisations (DAOs) which govern through token voting. The threat of bribery attacks and other forms of collusion will only increase if left unchecked, since such attacks target a fundamental vulnerability of such systems.

What’s new?​

In this release, we rearchitected MACI’s smart contracts to allow for greater flexibility and separation of concerns. In particular, we support multiple polls within a single instance of MACI. This allows the coordinator to run and tally many elections either subsequently or concurrently.

We’ve kept the ability for developers to provide their own set of logic to gate-keep signups. For instance, application developers can write custom logic that only allows addresses which own a certain token to sign up once to MACI in order to participate in polls.

An additional upgrade we have implemented is greater capacity for signups, votes, and vote options. With MACI 1.0, a coordinator can run a round that supports more users, votes, and choices than before, even with the same hardware.

We adopted iden3’s tools for faster proof generation. Furthermore, we rewrote our zk-SNARK circuits using the latest versions of snarkjs, circom, and circomlib. We also developed additional developer tooling such as circom-helper and zkey-manager.

Finally, we significantly reduced gas costs borne by users by replacing our incremental Merkle tree contracts with a modified deposit queue mechanism. While this new mechanism achieves the same outcome, it shifts some gas costs from users to the coordinator. A comparison of approximate gas costs for user-executed operations is as follows:

Finally, we are looking forward to collaborating with other projects and supporting their development of client applications and new use cases. For instance, clr.fund team has indicated that they would like to upgrade their stack to MACI v1.0, and other projects have expressed interest in adopting MACI. We hope that through collaboration, the Ethereum community can benefit from our work, and vice versa.

Further work​

There is plenty of space for MACI to grow and we welcome new ideas. We are keen to work with developers who wish to do interesting and impactful work, especially folks who would like to learn how to build applications with zk-SNARKs and Ethereum.

Negative voting​

We thank Samuel Gosling for completing a grant for work on negative voting. This allows voters to use their voice credits to not only signal approval of a vote option, but also disapproval. Please note that the negative voting branch, while complete, is currently unaudited and therefore not yet merged into the main MACI codebase.

Anonymisation​

A suggested upgrade to MACI is to use ElGamal re-randomisation for anonymity of voters. While all votes are encrypted, currently the coordinator is able to decrypt and read them. With re-randomisation, the coordinator would not be able to tell which user took which action.

Coordinator tooling​

We are working on tooling that makes it easier for coordinators to interface with deployed contracts and manage tallies for multiple polls. This will allow users to generate proofs and query inputs and outputs from existing circuits through an easy-to-use API. We hope that this will drive more adoption of MACI and offload the need for bespoke infrastructure.

Trusted setup​

Unlike other ZKP projects, MACI does not have an official trusted setup. Instead, we hope to assist teams implementing MACI in their applications to run their own trusted setup. For instance, clr.fund recently completed a trusted setup (on a previous version of MACI) for a specific set of circuit parameters. Other teams may wish to use a different set of parameters on MACI 1.0, which calls for a different trusted setup.

Conclusion​

This release marks a step towards the hard problem of preventing collusion in decentralised voting and quadratic funding systems. We are excited to share our work and please get in touch if you are a developer and are interested in getting involved in any way.