The original MACI protocol utilizes encrypted voting messages and allows key changes that provide a baseline for anonymous voting. However, anonymity is compromised when the malicious coordinator and an external briber collude and the coordinator provides decrypted votes and key change messages to the briber, thus revealing the votes of every user. The mitigation for this type of attack was implemented by using ElGamal encryption and rerandomization along with zero-knowledge proofs to hide the link between key changes. Although the ElGamal extension of the protocol provides improved anonymity, a certain complexity overhead is added to the protocol, as seen through the increased number of smart contract transactions and zero-knowledge circuit additions and modifications that highly impact the performance and usability of the protocol.
Protocol Improvements
We propose an overhaul of the anonymity improvement protocol by reducing the number of messages in the protocol (compared with the ElGamal modified protocol) and introducing the poll-based anonymized state tree. The modification of the protocol introduces the poll-joining message which creates a new node in the poll state tree data structure on the ZK proof testifying that the new entry in the poll state is created based on some key in the original MACI state tree but without revealing the link. A nullifier for the created node is stored in the smart contract and prevents double-spending of the original state tree nodes in the same poll.
Another improvement of the protocol includes replacing the message tree with a chain of messages with the chain hash as an analog of the tree root hash. This optimization brings four major improvements to the protocol:
Message tree size grows exponentially with the number of leaves, which allocates a lot of space on the smart contract. The message chain is implemented as an array that is linear in size. Furthermore, as the coordinator collects messages from the events, it is not required to explicitly store messages in the Poll smart contract. The only storage requirement is storing batch hashes after every batch-size number of messages, for constructing valid batch proofs in the message processing phase.
Message tree requires expensive merge operations to compute the root hash. The message chain hash is efficiently computed with each addition of a new message in the chain, as a hash of the previous chain hash and new messages, paid by the voter. This computation requires only one hashing operation per message in contrast to multiple batch transactions for merging the accumulator leaves paid by the coordinator.
The current ZK circuit for handling messages relies on inclusion proofs which requires inclusion proof processing with each message. 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.
The combination of the poll-based state tree and message hash chain will also significantly reduce the overall gas costs of the protocol. The test results show that changing the message tree structure to the hash chain, even with explicit storage of all message hashes in the smart contract, on average reduces message publishing gas costs from 496,029 to 403,353 for 100 published messages. This reduction is even more significant when only the batch hashes are stored instead of all message hashes. Removing the message tree merging step reduces the coordinator’s tree merging cost to 0, as the entire step becomes obsolete with the hash chain. With the reduced number of constraints in the message processing circuit, the message batch size can be larger resulting in fewer batch proofs submitted by the coordinator - further reducing the overall gas costs.
Joining the poll with the number of voting credits equal to the number of voting credits listed in the global state tree node may result in a privacy breach. That is why the number of credits associated with the new anonymous key needs to be less than or equal to the number of credits in the original state tree node. This modification provides another level of anonymization, hiding the link to the original number of voting credits. A best-case example would be a poll where all keys have the same number of credits.
Project Overview
The original MACI protocol utilizes encrypted voting messages and allows key changes that provide a baseline for anonymous voting. However, anonymity is compromised when the malicious coordinator and an external briber collude and the coordinator provides decrypted votes and key change messages to the briber, thus revealing the votes of every user. The mitigation for this type of attack was implemented by using ElGamal encryption and rerandomization along with zero-knowledge proofs to hide the link between key changes. Although the ElGamal extension of the protocol provides improved anonymity, a certain complexity overhead is added to the protocol, as seen through the increased number of smart contract transactions and zero-knowledge circuit additions and modifications that highly impact the performance and usability of the protocol.
Protocol Improvements
We propose an overhaul of the anonymity improvement protocol by reducing the number of messages in the protocol (compared with the ElGamal modified protocol) and introducing the poll-based anonymized state tree. The modification of the protocol introduces the poll-joining message which creates a new node in the poll state tree data structure on the ZK proof testifying that the new entry in the poll state is created based on some key in the original MACI state tree but without revealing the link. A nullifier for the created node is stored in the smart contract and prevents double-spending of the original state tree nodes in the same poll.
Another improvement of the protocol includes replacing the message tree with a chain of messages with the chain hash as an analog of the tree root hash. This optimization brings four major improvements to the protocol:
The combination of the poll-based state tree and message hash chain will also significantly reduce the overall gas costs of the protocol. The test results show that changing the message tree structure to the hash chain, even with explicit storage of all message hashes in the smart contract, on average reduces message publishing gas costs from 496,029 to 403,353 for 100 published messages. This reduction is even more significant when only the batch hashes are stored instead of all message hashes. Removing the message tree merging step reduces the coordinator’s tree merging cost to 0, as the entire step becomes obsolete with the hash chain. With the reduced number of constraints in the message processing circuit, the message batch size can be larger resulting in fewer batch proofs submitted by the coordinator - further reducing the overall gas costs. Joining the poll with the number of voting credits equal to the number of voting credits listed in the global state tree node may result in a privacy breach. That is why the number of credits associated with the new anonymous key needs to be less than or equal to the number of credits in the original state tree node. This modification provides another level of anonymization, hiding the link to the original number of voting credits. A best-case example would be a poll where all keys have the same number of credits.
Issues
Public Board https://github.com/orgs/privacy-scaling-explorations/projects/40/views/20
1527
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
Team
The work is being carried out by the https://3327.io team
Blog Post for more details
https://maci.pse.dev/blog/upcoming-grants-2024