MACI message processing order and bribery prevention

[ctrlc03]

This discussion aims to be the place where MACI's users and developers can discuss what is the best direction going forward on the order of message processing.

As of MACI v1.2.0 release, MACI processes messages in reverse order. Thus, the last message posted by a user will be processed first, requiring the nonce to be set to 1. This opens up a number of problems for applications integrating MACI. At the same time, it can be useful against certain bribery scenarios.

Let's start by looking at a MACI's message structure:

Message = {
    nonce: int,
    pubKey: string,
    voteOption: int,
    salt: int,
    voteWeight: int,
    signature: string,
    messageType: int,
    stateIndex: int
}

When processing messages (regardless of the order), the following checks are performed (some are omitted for the sake of this discussion):

1. The nonce is previous nonce + 1 (starting from 0)
2. The voteOption is within the range of the number of options
3. The signature is valid for the public key associated with the stateIndex (to not confuse it with the public key in the message which could be different if the message is a key change message)
4. The stateIndex (position in the signup merkle-tree-like structure) is of a signed up user
5. The voteWeight does not go over the remaining voice credit balance for the user

Looking at the nonce, we can see how the order of processing is important.

Applications examples

Taking as an example a voting frontend trying to submit multiple votes for a user, the user will need to submit all messages in one batch, in reverse order. Let's imagine 20 votes in a batch, the message array will have the following nonces order: [20, 19, .., 1]. What happens if the user wants to send another vote, or overwrite certain votes? Well, if they were to send another vote with nonce 21, this would not be valid, as it would be the first message processed and 21 != 0 + 1 (nonce check). The other option is for the user to send all of the votes again, however for ideal privacy, each message should have been encrypted using a key generated with ECDH(coordinator public key, ephemeral key), thus a client application would need to either store all of the ephemeral keys to decrypt all messages sent in the previous batch (by first fetching all on-chain events), or store the messages in the client app storage. At this point, they will need to resubmit the batch with the new vote(s). Furthermore, what if we need to submit more votes than we can fit in one block? This becomes quite complex to handle, as an user would need to submit multiple transactions via a client app, greatly affecting UX and introducing multiple edge cases.

As another example, a user decides to change their key, with reverse processing, the user should first send a message using the new key, and then a message with the key change request -> nonces [2, 1].

You can see from the above examples, how processing messages in normal (ascending) order would make building on MACI much easier. Let's assume we sent the 20 messages batch, and want to change one vote for a certain vote option, easy, we send a vote with nonce 21. All we need to keep track of is the nonce.

Bribery

So, why are messages processed in reverse order?

Reverse processing was introduced to prevent a type of attack where a briber would collude with a voter to sign up, and then submit a message to change their key to a key that the briber controls. This way the briber would have assurance that they could submit the vote they want.

Let's take as an example the following:

1. Alice signs up with pub key pub1
2. Bob (Briber) bribes Alice and asks her to submit a key change message to pub2 (owned by Bob)
3. Bob submits a vote with pub2
4. Alice submits a vote with pub1

If messages were processed in the same order as they were submitted, Alice's vote would not be valid, due to it being signed with a private key priv1 - which now would not be valid.

On the other hand, due to messages being processed in reverse order, Alice's last message would be counted as valid as the key change would have not been processed yet. Then, Bob's vote would not be counted as valid as the current key for Alice would be pub1.

Let's look at other scenarios, and check which processing order is the best option (or if it even matters at all?):

Scenario	Best option
User signs up and submits a key change message straight away from another address, then the briber bribes them and they would be fine with normal processing. Even with the maci key, the briber would not be sure that the key wasn’t changed. With reverse processing it would still be a race till the last message as the first key change could be overwritten straight away	Normal processing
User signs up and is bribed, they change their key to one controlled by the briber. In normal processing the briber would have now full control, vs reverse processing it could be overwritten	Reverse processing
User signs up using a device which generates the key, stores it on the device, and the device is sold to the briber. Either solution will not work	Order doesn’t matter
User signs up using a mechanism that batches signup and first key change to the briber's new key. Normal processing would allow the briber to be in control, with reverse processing it would be a race to sending the last valid message. The bribed user should have a copy of the private key to be able to actually do anything	Reverse processing
User signs up and sells their key. The briber wouldn't really know if they performed a key change or not from any other address. So they cannot be certain the key is valid. If reverse order, they (briber) would need to send the last message with nonce 1 and could potentially overwrite everything else. They do have the ability to confirm that the sold private key corresponds to the public key used to sign.	Normal processing
User signs up with a public key given by the briber. They do not have the corresponding private key.	Order doesn’t matter

Some questions to discuss

Would like to get people's opinions here, think of more scenarios together and see which way is better for the future.

• What type of bribery can we actually prevent?
• Should we think that we can prevent bribery if this involves devices where the key is generated and never exposed?
• Are there better ways to prevent bribery that is not related to the order of processing messages?
• What about key selling? Do we expect a user to still have a copy of their key if they sell it?
• What is more likely?
  • A coordinator bribing after a user signed up remotely?
  • A coordinator bribing after a user signed up, face to face? Can they still submit a key change before they submit the key change requested by the briber?
  • A coordinator forcing the voter to give up their private key using force (so being f2f)? I wouldn't expect this to be something we should keep in mind, as there's nothing we can do imo.
  • Bribing by using a device where the original key never leaves and there is no way for the bribed user to get the key, and the first message is changing the key to a briber controlled key?
• Can we have two versions of MACI, one with normal processing and one with reverse processing? One might offer better bribery protection, another be more practical to use for applications with less at stake?

A quick note on El-Gamal

In terms of potential future ugrades, El-Gamal looks like the most logical first step forward for MACI. The 3327 team implement a PoC for it, though it looks like the current proposed design would not work when messages are processed in reverse order. This is due to the message used to generate a new key with El-Gamal re-randomization being sent before the voting starts (the proposed solutions includes adding phases: signup, key deactivation/generation, voting). If the deactivation messages are sent before voting starts, and messages are processed in reverse order, it will be the last message processed for the user, so actually being useless. While there might be ways around this, I believe it's worth considering if it's safe to switch the message processing order back to it being sequential.

References

• Solution to the key-selling attack (where a new key created by trusted hardware) #116
• Problem of vote overriding and key switching #415
• Coordinator message processing fails to tally votes properly in case key change or key deactivation performed  #717
• https://maci.pse.dev/docs/v0.x/faq
• https://maci.pse.dev/docs/key-change#how-maci-messages-are-processed
• Investigate adding a password argument to messages to further enhance bribery resistance #1239 -> audit suggestion on using a password arg in the first message

[kittybest]

I remember that some guy in the audit team proposed a way to process the message normally, what's the conclusion of that method? (I lose in following up the discussion QQ) Will it affect the answer of the listed questions?

[ctrlc03]

Good point, thanks for bringing that up! I'll add that idea too

[yuetloo]

Just wanted to add that the reverse processing is also used to enable reallocation with nonce cancellation

In the following examples, votes from Day 1 were discarded because the nonces being processed from Day 2 because of reverse processing.

Note also if Alice submits fewer votes (votes for few projects), the app will need to submit "blank" vote to cancel previous nonce.

1. Votes reallocation with key change
   a) Day 1

• Alice signs up with pub key pub1
• Alice submits vote a with pubkey=pub2 nonce=3
• Alice submits vote b with pubkey=pub2 nonce=2
• Alice submits key change with newKey=pub2, oldKey=pub1, nonce=1

b) Day 2,

• Alice submits new vote a with pubkey=pub2 nonce=3
• Alice submits new vote b with pubkey=pub2 nonce=2
• Alice submits key change with newKey=pub2, oldKey=pub1, nonce=1

2. Votes reallocation with topup
   a) Day 1

• Alice signs up with pub key pub1
• Alice submits vote a with pubkey=pub1 nonce=4
• Alice submits vote b with pubkey=pub1 nonce=3
• Alice submits vote c with pubkey=pub1 nonce=2
• Alice submits topup with pubkey=pub1, nonce=1

b) Day 2,

• Alice submits vote d with pubkey=pub1 nonce=4
• Alice submits vote e with pubkey=pub1 nonce=3
• Alice submits blank vote (voteweight=0) with pubkey=pub1 nonce=2
• Alice submits topup with pubkey=pub1, nonce=1

[ctrlc03]

I think the same would work with normal order, just a voter would need to account for a key change and submit overriding votes with the new key. Same way as in reverse, an app would need to submit blank votes to completely nullify votes which are not included in the new (client-side) ballot, though they would not need to re-submit votes which are not changed (which is better ux)

In terms of topup, in your example, the topup at day 1 would still work because it's just a topup, as long as the conditions are met (whatever token used for topup is transferred) the topup message will always be processed - + there is no nonce for topup so other messages should be shifted to nonce = 1 from nonce = 2

[0xmad]

If we assume that briber has lots of power, it's not a problem "spam" and get desired vote in poll results with reverse processing. The bad thing here, user won't know about it because briber can switch keypair as well. So, here is the question: maybe it's possible to add verification for my own results so I can make sure my private key wasn't stolen and actually my votes are used in poll results, and how to prove it and don't allow briber to do the same.

[crisgarner]

If you have some kind of verification, won't this be used as a way to show a receipt for bribery?

[ctrlc03]

I'm not sure how feasible it would be to prove that your key wasn't used. Messages are encrypted using ECDH(randomKey, coordinatorPubKey) - so it might be possible that a briber used your key and sent a message which you cannot decrypt