Many thanks to Kobi Gurk for the original post introducing rerandomizable encryption to MACI, and to the Dora Factory team for discussions regarding actual implementation details of anonymous MACI.
Adding anonymity to MACI can reduce the reliance on the operator's integrity and further scale decentralized governance and community voting. The original MACI design lacks anonymity between users and the operator. Specifically, a user's behavior is transparent to the operator, meaning that the operator can map the user's behavior to their identity. This contradicts with the notion of anonymization. Ideally, the operator tallies the votes without knowing who voted for what, blocking collusion between the operator and users. To achieve this level of anonymization, MACI needs to hide a user's identity during voting.
A straightforward way is to have users provide zero-knowledge proofs of ownership of valid keys during voting without using or revealing the registered keys, so that the operator doesn't know who's voting. However, for users to provide proofs, the key set has to be public, which allows users to effectively sell keys to others. For this reason, a previously proposed light-weight MACI anonymization was not adopted.
One solution to this problem is to add a 2-of-2 MPC between the operator and a voter, as described in Adding anonymization to MACI. However, implementing 2-of-2 MPC can introduce much overhead and complexity to the system.
A recent post provided one possible solution to MACI anonymization with 2-of-2 MPC using Garbled Circuit and Oblivious Transfer can be found here.
For this reason, achieving MACI anonymization without MPC between users and the operator is preferred. One way to implement a non-MPC anonymous MACI is to use rerandomizable encryption, as described in Kobi Gurk's proposal.
The key-changing message is decomposed into two messages - a key deactivation message
Anonymization is achieved by the fact that anyone can deactivate their keys at any time, and provide a new key which the operator cannot correspond to any existing key. Thus when a new key is voting, it's anonymous.
The bookkeeping is done through a
Each element in
By encrypting the deactivation status, only the operator can see if the deactivation record is valid or not. Users cannot prove to others they actually deactivated their keys or not.
In addition to deactivation records, a
To ensure that users do act truthfully, a user has to generate a zero-knowledge proof every time when publishing a new key. They need to prove the existence of their deactivation record without telling the operator which deactivation record is.
Specifically, a user needs to prove the following to the operator:
(1) it owns the private key of the public key to deactivate;
(2) there is a deactivation record in the
The user doesn't need to prove the correctness of the
The role of ElGamal rerandomizable encryption in MACI anonymization
ElGamal rerandomizable encryption plays an important role to rerandomize the encrypted key status
Since The rerandomizable encryption function converts
A Complete Voting Cycle
In an anonymous MACI round, users start with signing up their keys to the operator's registry. All users are encouraged to deactivate their initially registered keys before they start voting.
When the operator receives
The operator will need to update the withdrawSet periodically. Users have to wait for the latest
(1) the proof is valid;
(2) the key status in deactivation record is
(3) the nullifier doesn't exist in the
If everything passes, a
If no user deactivates their keys, the aMACI round will just become a normal MACI round. If too few users deactivate their keys, they might be easily identified by the operator. As a result, the best practice is to have many users deactivate keys at the beginning of a round and update new keys right after the operator updates