Design considerations

There are few principles we use when translating the system to MPC, and few necessary changes to the standard MACI.

1. Moving things that are provable client-side to the client. In standard MACI, the server decrypts all messages, and processes them, checking correctness as a first step. Computations in MPC are much costlier, so we opt to push a lot of work to the client side. Specifically, the encrypted message is accompanied with a Groth16 zk-proof, which validates that the message:
   • Decrypts to a well-formed vote
   • The signature is correct
   • The vote vector is correct for this user
   • Keychange is correct

1. Parallel processing. The main bottleneck in the arithmetic MPC is round-complexity, therefore normal sequential processing of votes 1-by-1 is inefficient. Instead, we use oblivious stable sort by key as a main primitive, and custom permutation arguments for the proof. As a funny byproduct, the behavior differs from standard MACI in a subtle way (which doesn't break coercion-resistance). Namely, it is possible to "time travel" - for example, the sequence of keychanges $K_2 \rightarrow K_3$, $K_1 \rightarrow K_2$ ​ correctly changes they key from ​$K_1$ to $K_3$. The keychanges from a single key are still ordered by timestamp, and only the first one is valid, so the normal coercion-resistance mechanism works.

2. Keychange non-collision. For our approach, it is very convenient that the graph of all key-changes of an individual user is a forest (disjoint collection of trees). We enforce it in a following way:

   • First of all, our keys are not actual keys, and better thought of as "vote identifiers", any vote contains normal signature of a public key, and the identifier​ $K$.
   • Initial identifier is still set to be ​$K_{\text{init}}=P_{\text{user}}$.
   • On a keychange, new key $K'$​ must be obtained as $K' = \text{Hash}(K, R)$​, where $K$​ is an old key, and $R$ is supplied by the user. This is checked in the zk-proof provided by the client, and guarantees the impossibility of reaching the same key from two different keys, provided that we use a collision resistant hash function.

3. For optimisation reasons, we might require the voter to send a pair of transactions: first one registering vote id, and second one with the vote. This is done to enable the following trick: user sends both their part of the PlonK input commitment, and encrypted vote which contains their input, with the proof that these two pieces are in accord. Then, in MPC we do not need to provide decryption witness and can just use the sum of user commitments as an input column.

The extensive discussion on this is here