9 posts tagged with "maci"

Why poll joining?​

In the original version of the MACI protocol, one state tree stored information about all registered users, their public key, number of credits, and registration timestamp. Users could vote using encrypted messages and change keys to mitigate potential bribes. However, the coordinator could still decrypt messages and track key changes. Even if the key was changed and the bribed users could cancel their previous votes by voting with their new key, the coordinator could still trace back the key-changing messages and determine the true votes of the bribed users. To remove the link between the original public key and the new, changed public key, we've implemented El Gamal modification of the protocol. This modification worked, but it was expensive from the contract side and introduced a big overhead to the protocol in general.

Even if the El Gamal modification was not the most efficient one, it pointed in the right direction where each user should get a new key for each poll and hide the link with their original key using ZK proofs. That is why we decided to follow that path and improve the protocol further. We introduced a new concept of poll joining.

What is poll joining?​

Poll joining represents a protocol change where each poll contains its own poll state tree that stores the keys of users who want to vote on that poll. The users join the poll by providing a new key that they will use in that specific poll. But wait, then anyone can create as many keys as they like and vote many times so we lose everything? Not really. The users submit their new public key and ZK proof that they own some key in the original MACI state tree. That way, only registered users can join the polls without revealing the link between the old and the new key. To prevent multiple joins, the user also provides a nullifier - computed as a hash of their private key. The submitted ZK proof also verifies that the nullifier is correctly computed from the same private key associated with the public key in the original MACI state tree. On the smart contract side, the user is prevented from joining the poll with an already spent nullifier.

What if some users have a very specific number of credits so they reveal themselves by giving the same number of credits to a new key? We have a solution for that also. The users submit their new desired credit balance which has to be less than or equal to their credit balance associated with the original key in the MACI state tree. The submitted ZK proof also verifies that this condition is valid. Furthermore, a poll can be created so that it sets balances for all keys to a constant value, completely keeping anonymity.

How does poll joining affect the protocol?​

The poll joining does introduce one extra step for the user. Besides that, all functions and circuits on the coordinator's side remain intact. However, poll joining introduces new interesting features for the MACI as it enables putting various conditions on who can join the poll and how their credits are transformed in each poll. Some polls may require a minimum number of credits for joining, others may put a cap on the number of credits to be spent in a poll. The new dynamics open a new world of possibilities for future updates. But wait, there is more!

What else was improved?​

Besides poll joining we have introduced a new feature that drastically lowered the overall cost of the protocol. Before we reveal what was the upgrade, we should first recap how the protocol worked in the original version, specifically the message processing. In the original protocol, users submitted their messages to the Poll smart contract. Each message was stored in a smart contract Merkle tree, the accumulator queue to be precise. At the end of the voting period, the coordinator had to merge the message tree by sending multiple merging messages for data structure subtrees so the final message root could be computed. When the message route was computed, the coordinator used inclusion proofs in the message processing circuit to prove that each processed message was indeed found in the message tree. This sounds like a really expensive procedure - because it was. Let's analyze what could be improved.

First, all messages need to be processed in the same order that they were submitted to the poll contract. Using a tree structure and inclusion proofs does indeed prove that, but if there only was a data structure that maintains the order of items in a given immutable order? Yes, you guessed it, it is Blockchain. Each block in the chain stores an immutable reference to a previous block, keeping the order. It sounds like we have to make the message object even more complex and keep the reference to the previous message, but that is not the way. We can start with a random value, a hash of an initial string, and call it a chain hash. When there are no messages, the chain hash keeps the initial value. Once a new message comes to the poll, we can compute the message hash (already done for the message tree in the original protocol) and update the chain hash to a hash value of the current chain hash and newly received message hash. Formally, $chainHash_i = hash(chainHash_{i-1}, messageHash_i)$

Second, the coordinator collects all messages from the smart contract events, so why should we explicitly store messages in the smart contract? With the chain hash approach - we don't. When the coordinator is processing messages, the only important thing for making sure that the messages are properly ordered and all messages are included is to check that the chain hash is correctly computed. Starting with an initial chain hash value we can process messages and incrementally update the chain hash in the circuit ending up with a value that has to match the last chain hash value in the smart contract. To optimize this procedure for batch message processing, we explicitly store chain hashes for each batch in the smart contract and verify the batch processing by submitting the chain hash values before and after the message batch. We can dynamically set the size of the batch, thus the number of stored batch chain hashes, based on the coordinator's processing power.

How efficient is this?​

We removed the entire message accumulator data structure that had exponential space complexity in the number of messages and introduced batch chain hashes of a linear space complexity with a constant of less than one. That resulted in removing the entire message merging step, executed multiple times until the tree was merged. We kept the high level of user anonymity but without the large overhead of the El Gamal approach. We have maybe introduced one extra step for the user to join the poll, but we also removed many steps of message processing and drastically lowered the costs for the coordinator. Not bad.

What is next?​

We are not stopping here, more interesting protocol upgrades are on the way that would improve the security of the protocol even further and eliminate another significant concern. Be patient, and enjoy the privacy!

Who are we?​

Visit 3327.io and find out. Special kudos to our Mihailo Radojević and Boris Cvitak who did a lot of heavy lifting so these cool features could be here today!

What are Public Goods?​

Public goods are services or products that are available for everyone to consume, regardless of whether they contribute to their creation. Examples include clean air, public parks, and open-source software. These goods are essential for community welfare but often face funding challenges due to their non-excludable and non-rivalrous nature. This is where blockchain technology steps in, offering a decentralised approach to funding these vital initiatives. Through blockchain, transparency and community participation in funding decisions are greatly enhanced.

What is MACI and how does it help fund Public Goods?​

At its core, MACI is a tool that ensures privacy and prevents collusion in voting and decision-making processes. This function is crucial in public goods funding scenarios, as it ensures that the allocation of funds is fair and uninfluenced by external factors.

Current state​

MACI can be used in different forms of decision making and voting.

Quadratic funding is one of the ways in which we could utilise MACI for public goods funding. Quadratic funding is a democratic mechanism for crowdfunding that seeks to promote equitable, inclusive funding for public goods such as open-source software, scientific research, and public art initiatives. By incorporating MACI, these platforms guarantee that votes on how funds are distributed are not swayed by bribery or external pressures. This approach ensures a democratic and equitable distribution of funds, leading to more effective and genuinely representative support for public goods.

Another way in which MACI is utilised is for communities to be able to vote in Retroactive Public Goods Funding (RetroPGF) rounds. For example, Optimism runs RetroPGF rounds which involve allocating funds to projects based on past contributions to the ecosystem, incentivising and rewarding valuable contributions retrospectively. We’ve incorporated MACI to the RPGF stack and thus communities would be able to independently run future rounds in a private and secure manner using maci-rpgf!

The Future looks bright​

As we look to the future, the potential of MACI in reshaping public goods funding is significant. MACI could be used for larger and more diverse funding initiatives, expanding its impact, potentially influencing even governmental approaches to public goods funding. The role of MACI in fostering a transparent, fair, and democratic process for funding public goods is set to be a game-changer. Learn more about MACI by reading through our documentation. Join us in our mission, connect with our team on Discord today!

Welcome to the intriguing world of blockchain! This guide delves into Minimal Anti-Collusion Infrastructure (MACI), essential for those exploring secure, private voting on the blockchain.

Understanding MACI’s Strengths​

MACI stands as a lighthouse of private, secure voting in blockchain voting. Key features include:

• Collusion Resistance: MACI combats collusion, a significant issue in blockchain voting, by making it impossible for voters to verify their choices to others.
• Privacy: A cornerstone of MACI, ensuring vote secrecy.
• Receipt-Freeness: Ensuring voters can’t prove beyond any reasonable doubt their vote to others.
• Hinders bribery: As anyone looking to bribe voters can’t confirm how voters placed their votes, this potentially discourages bribery.

These strengths make MACI vital in enhancing trustworthiness, especially for newcomers.

Use Cases for MACI​

Some potential use cases for MACI are as follows

• DAO Voting: For Decentralized Autonomous Organizations (DAOs), MACI secures votes for crucial decisions, maintaining democracy in these organizations.
• Public Goods Funding: On platforms like clr.fund , MACI ensures fair funding decisions, free from external influences via Quadratic Funding.
• Elections: MACI could also be used in governmental elections for people to cast secure votes for the leaders of their state!

These use cases demonstrate MACI's transformative role in making voting more accessible and trustworthy.

Where MACI May Not Be Ideal​

MACI's powerful features may not suit every scenario. For example:

• Transparent Governance: Where individual vote transparency is key, MACI’s privacy might not be the best option
• Simple Polling: In basic, non-sensitive blockchain polling, MACI's complexity might not be needed.

Recognising the context of the situation helps in choosing the right tool for blockchain voting needs.

Conclusion​

MACI is a significant advancement for secure, private voting. Understanding its strengths and appropriate applications is key to leveraging this technology. As the blockchain landscape evolves, tools like MACI will play an increasingly vital role. Dive deeper into MACI and its application via our documentation and by joining our team’s discussion via our Discord channel!

Hey Anon!

In this blog post, we’ll give a high-level, beginner friendly introduction of what Minimal Anti-Collusion Infrastructure (MACI) is, and how it could be used in a real-world context. We’ll take you through the essentials of MACI, making complex concepts accessible regardless of your background in the blockchain space.

What is MACI?​

MACI is a cutting-edge solution that ensures private, reliable voting on the blockchain.

Blockchain Voting Challenges for Beginners​

On-chain voting is a method of casting votes directly on the blockchain, leveraging its decentralized and transparent nature. While this provides us with censorship resistance and guarantees correct execution, the transparency of blockchains can be a double-edged sword. Given all transaction data is public by default, it means everyone can see how anyone voted. This ensures all votes are correctly counted but the visibility could lead to undue influence on voters' decisions, and potentially opens doors for unethical practices like voter bribery. The challenge, therefore, lies in preserving the privacy of each vote while maintaining the core principles of blockchain: transparency, process integrity, and security.

How MACI Offers a Solution​

Minimal Anti-Collusion Infrastructure, or MACI, steps in as an elegant solution to these challenges. Despite operating on-chain, it protects the privacy of voters and votes, thereby significantly reducing the chances of vote manipulation through bribery. How does it achieve this? By employing advanced cryptographic techniques like zero-knowledge proofs (zk-SNARKs), MACI ensures that while the outcome of the vote is public and transparent, individual voting choices remain private. For instance, let's say you vote in an election using MACI, you could claim to everyone that you voted for a particular candidate, but in reality, you might have voted for someone else. There's no way for anyone to verify your claim, making bribery less appealing.

Key Features of MACI​

MACI isn't just a tool; it's a fortress safeguarding the integrity of on-chain voting. Let's break down its key features:

• Collusion Resistance: MACI makes it virtually impossible for voters to be swayed by bribes, as they can't prove how they voted.
• Privacy: Your vote is your secret. Only you know where your support lies, thanks to the encryption technology MACI employs.
• Uncensorability: Every vote counts and cannot be blocked, edited or removed, ensuring a fair voting process.
• Unforgeability: Your vote is tied to your unique digital identity, preventing anyone else from casting a vote in your place.
• Non-repudiation: Once cast, your vote is set in stone. You can change your mind and vote again, but you can't erase your previous vote.
• Correct Execution: The final tally is accurate and tamper-proof, ensuring that the true voice of the voting population is heard.

These features come together to create a voting environment where your voice is heard, loud and clear, without fear of external influence or manipulation.

Technical Overview Simplified​

At its heart, MACI is built on Ethereum, a blockchain platform. This foundation provides a high level of security and trust. The real magic, however, lies in something called zk-SNARKs. Think of zk-SNARKs as a cloak of invisibility for your vote; they hide your voting choices while still guaranteeing the overall vote count to be tallied accurately. This blend of Ethereum's robust framework and the innovative use of zk-SNARKs makes MACI a reliable and secure choice for on-chain voting, ensuring that your vote is both private and counted.

If you’re interested in more of the technical details, check out the MACI documentation.

Real-World Applications and Limitations​

Imagine a world where funding for public goods, like community projects or open-source software, is decided through fair and transparent voting. This is where MACI shows its true potential. Quadratic funding is already harnessing MACI's capabilities to enhance user privacy and discourage any form of collusion in funding decisions.

However, like any system, MACI isn't perfect. Its effectiveness hinges on the honesty of the coordinator – the entity or person overseeing the voting process and tallying the results. A dishonest coordinator could pose risks, but thankfully, MACI is designed to minimise even this possibility, maintaining a high level of integrity in the voting process.

Conclusion​

As we've explored, Minimal Anti-Collusion Infrastructure (MACI) stands as a testament to the innovative solutions being developed in the blockchain space, especially for those new to this technology. It addresses the critical need for privacy and fairness in on-chain voting, ensuring that your vote remains your own, free from external pressures and manipulation.

Blockchain technology is continually evolving, and with tools like MACI, it's becoming more accessible and trustworthy. Whether you're a blockchain enthusiast, a developer, or someone just starting to explore this exciting field, MACI represents a significant step forward in creating a more democratic and transparent digital world.

We encourage you to delve deeper into MACI and the broader world of blockchain by reading through our documentation and installing MACI. Join us too on our Discord to report any bugs or to chat with our team. Your involvement can help shape a future where digital voting is not just secure, but also truly representative of the people's voice.

Together, let's embrace these advancements and contribute to a fairer, more transparent digital voting landscape.

Minimal Anti-Collusion Infrastructure (MACI), is making waves in the world of private, digital voting. But where did this technology originate? Vitalik Buterin is the mind that thought of MACI. In this post, we’ll dive into his vision for a more secure and private digital voting system.

Who is Vitalik Buterin?​

For those unfamiliar with the name, Vitalik Buterin is a Russian-Canadian programmer who co-founded Ethereum. Ethereum is a blockchain platform that has been a game-changer in the world of cryptocurrency and beyond. Vitalik’s passion for blockchain technology led him to explore various applications, including digital voting, which eventually culminated in the proposal of MACI.

What Inspired MACI?​

Vitalik was deeply concerned with the issues plaguing traditional and digital voting systems, such as fraud, lack of privacy, and potential manipulation. He imagined a system that could handle digital voting with utmost integrity, transparency, and security, ensuring that people’s votes would genuinely make a difference. This led to the birth of Minimum Anti-Collusion Infrastructure or MACI.

Breaking Down MACI​

MACI is a system designed for digital voting that protects against collusion and bribery, while ensuring privacy, authenticity, and that no vote can be censored. How? Through cleverly employing smart contracts on the Ethereum blockchain and something called Zero-Knowledge Proofs (ZKPs). This combination makes sure that no one, aside from a trusted coordinator who helps tally results, can view the votes. However, absolutely no one, not even the coordinator, can tamper with the results.

The Importance of Privacy​

One of Vitalik’s major concerns was the privacy of voters. In a world where data is often exposed or misused, the anonymity of a voter is of utmost importance in maintaining the integrity of the voting process. MACI ensures that votes remain a secret, and that only a trusted coordinator has the ability to decrypt them.

A Democratic Revolution​

Through MACI, Vitalik sought to revolutionise the democratic process. Imagine a world where communities could make decisions without fear of interference or manipulation. Where funds could be raised and allocated for public goods and services in a fair and transparent way. That’s what MACI is all about.

Final Thoughts​

Vitalik’s vision for MACI was not just a technological advancement, but a stride towards a more just and democratic society. Through blockchain technology, he has shown how innovation can be harnessed for the greater good, by protecting the sanctity of each vote. MACI is a testament to how technology can be a powerful tool in upholding democratic values and ensuring that every voice is heard. If you’re keen on learning more, dig in to our documentation here. Also, join us in building our future, connect with our team on Discord!

Greetings anons,

Happy 2024 and welcome to the new MACI documentation website and blog! Moving forward, we’ll post our latest project news and development updates here.

We have a few exciting announcements to share, but first, a quick review:

Overview of MACI​

WTF is MACI?​

Minimal Anti-Collusion Infrastructure (MACI) is an on-chain voting system which protects privacy and minimizes the risk of collusion and bribery.

MACI is a set of smart contracts and zero-knowledge circuits upon which developers can build applications, such as voting applications or quadratic funding platforms. It was originally proposed by Vitalik Buterin in 2019, then implemented and maintained by community members with support from the Ethereum Foundation. It's now actively maintained within Privacy & Scaling Explorations (PSE).

Using MACI, voting is private, yet voting results are public. On-chain votes are encrypted, and no voter can prove how they voted, but final results are published publicly and verified on-chain with cryptographic proofs to prevent censorship, bribery, collusion, fraud, and other nefarious acts common in public polling processes.

To understand the promise of on-chain voting, start with Vitalik's post on blockchain voting. For a general overview, brief history, and context on the importance of MACI, check out the Release Announcement: MACI 1.0 by Wei Jie, one of the creators. He also created a helpful overview of MACI video. Kyle Charbonnet wrote a great Technical Introduction to MACI 1.0 that provides a walkthrough on how MACI operates. I also recently presented an introduction to MACI at Devconnect 2023.

MACI Vision​

MACI is a public good that is quickly becoming a core piece of infrastructure for Ethereum-based applications to support on-chain voting while protecting user privacy.

Our MACI team’s vision is to build the most secure e-voting solution in the world.

Let's hop in to our updates to see how we plan to execute on this bold vision.

Project updates​

New year, new team, new roadmap!

1) New team​

Over the past few months we've undergone a lot of changes within MACI's core team. I'd like to take this chance to introduce and welcome our new core members!

MACI is now maintained and will be continuously be improved by our core team, which consists of:

• ctrlc03
• Sam Richards
• 0xmad
• kittybest
• crisgarner
• aguzmant103
• Vee

Now is a great time to mention that we stand on the shoulders of giants. Many gigabrains have made heroic advancements in this project - a big "thank you" to all those who have contributed to date! There are too many people to list here, but calling out a few notable players:

• Vitalik, Barry, Wei Jei for the original idea, architecture, initial implementation, and ongoing guidance
• Recent team members that helped launched our v1.1.1 release and have since moved on: Q, Jei, Chao, and Daehyun

We're excited to carry the baton forward to bring the vision of MACI to reality!

2) New roadmap​

As a team building in the open source space, we're taking a concerted effort to make our work more accessible and to foster more collaboration and feedback from our community. As part of this work, we're making our core team's roadmap public and will continue to do so.

Read our full 2024 roadmap here.

TL;DR: We'll be focusing most of our time on:

1. Developer experience (documentation, tooling, refactoring) so that MACI is easier for projects to integrate and use
2. Community engagement (integration support, hackathon bounties, conference presentations) to more quickly iterate and improve based off feedback
3. Quadratic Funding Experiments to advance real-world adoption of this technology

We're happy to share that these efforts are already underway. We expect to release a new and improved version of MACI within the next month. We're exploring MACI integrations and are in discussions with projects including Gitcoin Grants Stack and Optimism RetroPFG on how MACI could provide collusion resistance to those systems. Major shoutout to clr.fund (who became the first production project to integrate MACI back in 2020)! We're actively working with clr.fund to help them upgrade their stack to the latest version of MACI. Expect to see announcements of upcoming MACI-enabled quadratic funding rounds soon!

3) New documentation​

MACI now has a fresh new website, with revamped documentation!

We immediately recognized the need for improved educational content about MACI, as it's a complex project with several core components (ZK circuits, Ethereum smart contracts, TypeScript libraries). Whether you're a developer looking to integrate MACI into your application, an open-source developer interested in contributing, or a product manager seeking to understand the high-level mechanics of MACI, we want to hear from you in order to continuously improve your onboarding experience.

Please take a look and let us know what you think.

4) New community access​

Whether you're interested in contributing to MACI or looking to stay up-to-date on the latest happenings, it's now much easier to stay connected with us and the community. Here are some ways you can keep in touch:

• GitHub: open an issue or PR or join our discussions
• Discord: join the PSE server and hop in the #🗳️-maci channel to chat with our core team
• Twitter/X: follow our new handle @zkMACI for updates or to hit us up with feedback
• This website: we'll continue to post updates here (at least 1 blog post every quarter, we promise 🤞)!

Expect to see announcements around new MACI releases, integrations, event participation (quadratic funding rounds, conferences, hackathons), and grant RFPs.

We look forward to collaborating closely with our open source community this year!

How does that sound?​

Questions? Concerns? Ideas? We’d love to hear from you!

If there is a feature you think we should work on, or an initiative you'd like to collaborate with us on, please let us know! We welcome input from anyone in the community.

Onward and upward 🚀

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:

Property	Description
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 one can 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.

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​

Feature	Description
Top Up Credit	Users can now top up credits rather than having to sign up with a different MACI key
Pairwise Subsidy	Enhanced protection against collusion in quadratic funding
Coordinator Service	Sample coordinator server for easier MACI use

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.