MACI - Minimal Anti-Collusion Infrastructure is a collection of smart contracts, ZK circuits, and ts packages that we can use to build programs on top. We have already dealt with this topic, we summarized what has been done in MACI so far (our previous research on MACI and blog Can MACI really destroy the collusion?).

This blog is a continuation of the previous one, but here we are dealing with the topic of Anonymity in MACI. Namely, the problem that we saw as "burning" in MACI is that the coordinator can see how which voter voted. There is no problem if the coordinator is honest, but what if he is not?!👿

So how do voters vote in MACI? What type of encryption do they use? 🔐 How does the coordinator summarize all the votes and publish the results of the votes? 

Voters vote using MACI smart contracts. Before sending their vote to the blockchain, they first encrypt their vote (actually, they encrypt the signature and the command) using a shared key. Voters send this encrypted message to the MACI smart contract, which will be stored on-chain. Using shared keys, the coordinator decrypts each vote. It should be noted that each voter will have a different shared key, and that only the voter and the coordinator know that key. The process described above can be seen more clearly in the image below.

After decryption, the coordinator needs to prove the voting was valid and reveal the results of the voting. This should be done so that everyone is sure of the voting results, without releasing the votes of every individual. So the coordinator will make ZK proofs. In this way, the anonymity of voting is almost completely preserved, up to the coordinator.

Let's study encryption 🗝️!

To understand the idea behind preventing collusion (we don’t want the coordinator to know which user took what action), we need to understand what encryption is currently being used and the proposed new encryption, as well as why it is necessary to do so.

ECDH encryption

MACI uses an Elliptic-curve Diffie–Hellman shared key. ECDH allows two parties, each having an elliptic curve public-private key pair, to establish a shared key. Let G be a generator point on the elliptic curve over a finite field Fp (where p is a prime number). Let prA and prB be the private keys of two different people, A and B. Then pubA=prA∗G and pubB=prB∗G are their public keys. ECDH is based on the property of elliptic curve points:

(prA∗G)∗prB=pubA∗prB=shared_key=pubB∗prA=(prB∗G)∗prA.

In this way, both of them know the shared key, and they get it using their private key and the other person's public key. In this way, each person's private key remains secret.

The algorithm's security lies in the difficulty of calculating the discrete logarithm.

EC ElGamal encryption

We propose to use ElGamal encryption and re-randomization in MACI. Let G be a generator point on the elliptic curve over a finite field Fp (where p is a prime number). Let prA and prB be the private keys of two different people, A and B. Then pubA=a∗G and pubB=b∗G are their public keys. Let person A be the person who will encrypt the data. For this purpose, person A should do the following:

1. choose an arbitrary x from the interval (1,p);
2. calculate x∗G=:X;
3. assigns a point on the elliptic curve M(m,y) to the message m, where person A chooses y so that the point M is a point on the elliptic curve;
4. calculate Me:=M+pubB∗x;
5. send M and X to person B.

Person B needs to decrypt the data. For this purpose, person B should do the following:

1. calculate pubB∗x==prB∗G∗x==prB∗X;
2. decrypts the message M(m,y)==Me−pubB∗x.

Note that when encrypting a message, person A needs to know the public key of person B, while person B can decrypt the message without knowing the public key of person A (which is not possible with decryption that relies on a shared key, i.e., ECDH).

Similar to the ECDH algorithm, the security of ElGamal is based on the difficult or almost impossible computation of the discrete logarithm of a large prime number.

Re-randomization

We usually use re-randomization when we want to convey the same message, but two cipher texts cannot be connected. That function randomizes an existing cipher text, so it's still decryptable under the original public key it was encrypted for.

Suppose we are working with the same elliptic curve. Assume that the notation we used above holds. We want the input parameters to be X and Me and the output parameters to be X1 and Me1 to hide the same message. For this purpose, person A should do the following:

1. choose an arbitrary z from the interval (1,p);
2. calculate X1:=z∗G+X;
3. calculate Me1:=Me+pubB∗z;
4. output Me1  and  X1.

If you now understand how the encryption we explained in the lines above works, then the following picture applies to you 😁.

How to achieve voting without collusion while protecting voter privacy?

It is essential for the ecosystem to be able to use a decentralized voting system that is completely resistant to collusion. First, it is important to protect the privacy of a particular voter in every sense (on-chain and off-chain), especially if the voting is related to some significant funding 💰. MACI does not currently completely suppress collusion, which is seen if the coordinator is not honest. In the following lines, the idea of how it can be achieved so that the coordinator does not know how which voter voted is presented in detail.

Therefore, in the future, MACI would represent the perfect system for voting in a decentralized system - a system completely resistant to collusion.

In order to achieve the desired result, it is necessary to change the protocol. As we said before, the current protocol allows the voter to vote and change the public key (voters can send two types of messages).

For example, If the voter is blackmailed, he can create a command with the content of the option he wants to vote for and with a new public key. He can sign it with his previous public key, encrypt it (using ECDH encryption), and submits it to the MACI smart contracts. However, the same voter can then vote for the option the blackmailer wants without that vote being valid (which the blackmailer will not know). 

How does it achieve this ⁉️ 

The voter creates a command with the content of the option the blackmailer wants and the previous public key. He signs it with his previous public key, encrypts it (using ECDH encryption), and submits it to the MACI smart contracts. When the voting is over, the coordinator decrypts the first message, validates the signature, records this vote (because it is valid), and updates the voter's public key. Then the coordinator decrypts the second message and sees that the signature does not match the new public key, and therefore this message is invalid. But the voter can decrypt this message, too, as proof of his vote for the option blackmailer wants.

How should the protocol be changed to have a voting system that is completely resistant to collusion?💡

We want to preserve these two nice features: 

1. the voter can prove to the blackmailer that he voted for that option for which he was blackmailed (without that vote is valid);
2. all votes are encrypted and stored on-chain. 

But we also want to add a feature:

The coordinator can not know which option the voter voted for. 

In the current protocol, when a voter's public key is changed, the coordinator knows that the change has occurred. From there, the coordinator knows how the voter voted (although the public key change helped the voter to deceive the blackmailer).

As we do not want that coordinator to know who is the "owner" of the new public key, we need to disable the coordinator from seeing the link between the old and new public key of the voter 🔗. In order to achieve this, the voter must prove (he needs to make ZK proof) that he owns the private key for the old public key and to be able to create a new one based on that. For this purpose, we will need to create a set containing all deactivated public keys and their encrypted states. But here, we have to be careful. We have to make sure that based on the previous public key, the voter can create exactly one new public key. For this reason, we will need nullifiers and the set where we store them. 

In conclusion, we will need two new sets. Let's mark the first with D and the second with N. Set D is public, while set N is private. We must expand the set of states. There should be a field in that set that says whether the voter's public key is active or inactive.

Also, we will need two new message types. 1️⃣ The first type of message should be to deactivate the old public key. After deactivation, the coordinator adds the old public key with its encrypted state (using ElGamal encryption) to set D.

2️⃣ Second type of message is that the voter creates a new public key, proving that he is the owner of the old deactivated one. To achieve this, the voter needs to make a ZK proof that the element (old deactivated public key of the voter, (X, Me)) belongs to the set D, where (X, Me) is the ElGamal encrypted message, as well he needs to prove that he knows the private key for the old public deactivated key. Also, the output of the circuit should be (X1, Me1), which is obtained by rerandomization (X, Me) and nullifier, which is the hash of the private key. The content of the message itself should be: (X1, Me1), nullifier, the ZK proof, and the new public key. Of course, the message is encrypted. The coordinator decrypts the message; if the proof is valid, the nullifier doesn't already exist in the set N, places the nullifier in the set N, adds a new public key, and updates its state. Note that in this way, the coordinator does not know the old public key of the voter whose vote he is processing. In this way, complete anonymity of voting was achieved.

A golden example 😁

We now want to illustrate the entire protocol with an example. We want person A to be a voter. Person A wants to prove to the blackmailer that she voted for option 1️⃣, even though she will vote for option 2️⃣.  Also, person A wants the coordinator not to know which option she voted for. Person A can do it, for example, like this.

1. Person A accesses the vote with public key 1. Votes for option 2️⃣, change the public key to public key 2, signs the command with public key 1, and encrypts it.
2. Person A then votes for option 1️⃣ , signs the vote with public key 1, and encrypts it.
3. Person A deactivates his public key. 
4. Person A activates a new public key based on the old public key using ZK proof and rerandomization.

Let's see what happens when the coordinator processes the messages.

1. The first message will be valid and will update the state related to the public key of person A (a vote for option 2️⃣ will be entered, and the new public key of person A will become public key 2).
2. The second message will not be valid, and there will be no state change (because person A's public key has become public key 2, not 1, as signed in the message). 
3. It will change the state of public key 2 of person A to inactive. When the key state is inactive, that vote is not counted in the total. Therefore, the vote for option 2️⃣ is not counted at this time. Also, the coordinator updates set D and write the public key 2 and the encrypted states (using ElGamal encryption) - vote for option 2️⃣.
4. New key - public key 3 (of person A, but the coordinator does not know that it is the public key of person A) writes to the set of public keys and registers a new state (vote for option 2️⃣ is now written, and this key is considered active).

Conclusion 

In this blog, we talked about: 

• New and existing encryption types in MACI;
• How to trick the blackmailer;
• How to avoid a coordinator knowing which voter voted for what option.

We hope you liked our blog, Anonymity in MACI. 🚀 If you are interested in all the details of our research, you can look at our research. 🔎 We renovated our Discord and would love to have you, so come check it out! ⚡️