Minimal anti-collusion infrastructure

Applications
7

I see, so the [T_\text{start}, T_\text{end}] period is repeatable: the registry is maintained, only the tally is performed at the end of each period. This is much less of a surveillance risk, because the window for accumulating a complete history ends once the setup is complete.

It still bugs me that this is centralized. Obviously you can’t make it decentralized in exactly the form given, because the private key k_\omega would need to be public. Instead, let’s say that each voter has two private keys, k_i and k_i', and submits \text{enc}(K_i, k_i') when a new election begins. All messages are sent in the clear:

\text{msg} = (i, \text{sign}(\text{action or enc(new }K_i, k_i'), k_i)),

but of course, the signature can’t be verified because no one knows the actual public key…yet. At the end of the election, voters sacrifice their k_i' and reveal it publicly, and the entire stream of messages is verified all at once before the tally is taken. For the next round of elections, the voter can make their old k_i into their new k_i' and pick another k_i, so that the key that is private in one election is revealed in the next one.

Until the reveal, it is impossible to know whether a given message has any effect, just as in the centralized scheme. So this is still collusion-resistant. One failing is that eventually, any potential briber knows that they were cheated, which is not possible in the centralized scheme, and invites possible retaliation even if the election is not affected.

Although anyone looking back through the history can (of course) figure out what all the messages mean, no one living the history can do this until the reveal. So the transactions are not truly private, but they stay secret long enough to have the intended effect.

1 Like
8

Yeah, I’ve thought about schemes that involve not revealing info until later, and they all run into the issue that if the briber is a little more patient they’re no good.

I agree the centralization is unfortunate! The nice thing though is that the centralization is only for the collusion-resistance guarantee, the centralized party can’t break anything else. Note that some meatspace verification being done by someone somewhere is indispensable because any scheme that requires anti-collusion infrastructure also requires unique-identity verification (or else someone can just gather up many identities and collude with themselves).

If we want to mitigate the centralization, the best that I can come up with is turning it from 1-of-1 into M-of-N via multi-party computation. We can potentially make the security even higher than 1/2 if we have a scheme that favors safety over liveness, and in the case where liveness fails detect it on-chain and automatically remove the non-live parties from the committee and restart.

1 Like
9

How does the withdraw of hte deposit works?

If I start with key x and update it to key y do I withdraw with key y ? Is the withdraw public in the smart contract ? Is the withdraw protected with the same coersion resistance mechanisim ?

My specific concern is something like this. I deposit eth and participate in a vote. Afterwards I withdraw my ETH deposit. If this is public I can use my withdrawal transaction from public key x as evidence to a briber that I did not update my key at any time during the Vote.

Its still possible here that I voted twice with the same public key. But I can run the probabilistic bribe attack above but this time at the end of the epoch. So I would reveal my vote that is close to the end of hte epoch and get bribed.

Let formalize the bribe amount. The operator creates a batch of transactions that overlap the end of the epoch and bribes each reveeler
cost_per_vote * (no_transparent_actions_in_batch / no_hidden_actions_in_batch)

The cost_per_vote is how valuable their votes are to them. In the quadratic voting analysis even if no_transparent_actions_in_batch < no_hidden_actions_in_batch this attack can still be more efficient.

1 Like
10

Key selling would be a case of transitive trust. If trust is reliant upon repeated interactions from a single individual, could that not also then be packaged and sold? How does that interact with incentive compatibility wrt mechanisms?

I have been a bit wary on sMPC, but not through code tests which I should perhaps engage in. How could we decouple trust from engaging with a key signing process? This of course assumes that individuals have varying collusive tendencies. It should be clear that the risk is through a break down of trust. Keys however might be distributed widely to ensure non-collusion without discretion, but that is a shaky argument.

Believe I have mentioned before, but ring signatures and threshold signatures are essentially dual, former requiring minimal endorsement, latter requiring maximal endorsement, ie collaboration in decryption as opposed to signing. It comes down to the manner in which the keys are served to people then and for what ideally limited purpose. ZK-SNARKs have opened us back to solutions from verifiable computation, but that does not address the trust issue in repeated execution of the protocol via any given party. We’d have to think in a multilinear way with trust levels so to speak, or it all falls back to 1-2 oblivious transfer. This appears to be the gold standard of any MPC as it is transitive on the single operation of a protocol.

Have to reread the collusion post, but those are my 200 wei for now.

1 Like
11

Coming back to the centralized version, I wonder if the following simpler scheme wouldn’t work better.

The idea is that, if you want to prevent bribery, you want a secret ballot; that’s what they were introduced for, in fact. I assume there is a good reason for us to assume messages are public (if only because they will be transmitted over the internet and not a secure private network), so why not just do as we do already with online secrecy and open an encrypted channel?

So, when a voter registers with the operator, rather than giving it her public key, they do a key exchange (as in, a handshake encrypted by public key crypto that results in each of them agreeing on a symmetric key). Now the operator is storing a separate totally secret key for each voter, and each voter can cast a ballot consisting of their voter number (in the clear) and the encrypted vote.

It is impossible to determine anything more than that a vote was cast, and even if a briber wants the voter to reveal a ballot as proof, the the voter would have to reveal both the ballot and their individual secret key in order for the briber to match it with an observed message. (This is different from the public/private key situation you worked with, because there, the briber does know how to encrypt a message to match it with an observed one.)

Note that even though each voter gets their own secret key, the operator isn’t storing any more information than in your scheme, which keeps track of an individual public key for each voter. The voters, in turn, are not responsible for any harder a task than when they had to hold a private key. Finally, the messages are secure against tampering since the key encrypting the vote has to be the one stored by the operator for the numbered voter, and if that key stays secret, only the voter can accomplish this.

Unless there is a need for the votes to be public (and I don’t see why that is at all desirable as a default), or there is some aspect of the operator’s workings that precludes a key exchange, wouldn’t this work?

1 Like
12

There is a need for encrypted votes to be public, which is that we don’t want to trust the operator for correctness, so we need the operator to be able to zero-knowledge prove that they counted all of the votes correctly and particularly did not “censor” any votes. The only thing a malicious operator should be able to break is the collusion resistance guarantee, not any safety or liveness guarantees.

1 Like
13

In both schemes, the votes are “public” in the sense that they appear, encrypted, on-chain. I meant that the secret-key scheme does not make it possible ever to prove (to the public, not the operator) how someone voted, unless they give up their secret key. Whereas of course, the public-key scheme does allow a claimed vote to be checked against the record by encrypting it.

Is there something about the public-key setup that makes a ZK proof possible where it is not possible for the secret-key setup? That is, given the stream of encrypted messages that are handled as you describe by the operator, there is a zero-knowledge proof that some correctly-signed votes and key-changes exist that make the alleged output and encrypt to the given messages; but given the stream of encrypted messages that I described, there is not a proof that some votes and some set of secret keys exist with that property? They both sound like the same kind of problem (and also that the proofs would be exceedingly long and hard to compute; however, in both cases, the circuit only needs to be constructed once when the contract is written).

(As an aside, in order for the ZK proof for the secret-key scheme to show that the votes were cast by the users and not made up by the operator, I would have to say that each user does have a public key, which is initially placed into the contract, and with which they also sign the votes that they encrypt onto the chain. Then the problem would contain an additional predicate that the same key was used for both. Only the operator sees the signature, but that is enough for the ZK proof to reflect the fact that it is valid, like in the public-key setup.)

1 Like
14

There’s also the possibility of a player agreeing with the operator on a key k1, but then using a different key k2 to encrypt the message, or that of a malicious operator claiming that another player did such a thing. Unless the exchanged key is somehow committed to on chain in a way that the player can verify, this seems unavoidable, and if the exchanged key is committed to on chain in a way that the player can verify then they could prove how they voted.

So I think the ability to specifically cancel a key is important.

2 Likes
15

I see the problem here: the public has no means to verify an operator’s claim that some vote is invalid due to encryption with the wrong key, or that some invalid vote is valid because it’s encrypted with a key that the operator knows but isn’t the one that particular voter should use. Fair enough: this violates the requirement that an operator failure shouldn’t affect the outcome of the vote.

Let’s modify my previous aside, which suggested that each user’s public key be kept on-chain for identity verification, to also keep the operator’s public-key encryption of the secret key of each user (the user as well as the ZKP can verify this because both would also have the operator’s public key and the user’s own secret key; no one else can learn anything from it). The operator (and, correspondingly, the ZKP), is required to use that secret key to decrypt votes. This ensures that a malicious operator can’t pretend that a vote is invalid, or that a vote encrypted with someone else’s secret key is valid, since the means to validate is visible, if not usable, to the public.

In general, it seems to me that by encrypting with the operator’s public key, any internal state maintained by the operator can be manifested in public, indecipherably, but still visibly enough to figure in a zero-knowledge proof that it was used correctly by the operator.

1 Like
16

But then wouldn’t a user be able to prove what their secret key is, if they’re the ones to encrypt it to the operator? I suppose you could get around that if the operator encrypts, but then that seems like it would put a lot of load on the operator to make many more proofs.

3 Likes
17

I don’t think this reveals anything that the people who can find out don’t already know. Maybe I should make explicit the structure that’s been coming together in pieces here.

The contract contains the following data object, annotated in some made-up, suggestive type system:

{
  registry : Map PublicKey (PubKeyEnc SymKey, SymKeyEnc (Signed Vote)),
  operatorPubKey : PublicKey
}

Each voter also has a data object:

{
  myVote : Vote,
  myPrivKey : PrivateKey,
  mySymKey : SymKey
}

The operator has a very simple data object:

{
  myPrivKey : PrivateKey
}

The voter and operator data are, of course, known only to the respective parties, while the contract data is public. For each voter, there is an entry in registry (with pseudocode crypto API):

registry[pubKeyOf(voter.myPrivateKey)] = 
  (
    pubKeyEnc(voter.mySymKey, contract.operatorPubKey),
    symKeyEnc(pubKeySign(voter.myVote, voter.myPrivKey))
  )

This can be constructed entirely by the voter, since it uses only data visible to them (their own and the contract’s).

Conversely, the operator can read each vote, including validating the voter:

votes = 
  symKeyDec
    (
      encSignedVote, 
      pubKeyDec(encSymKey, operator.myPrivKey)
    ).unsign(voterPubKey)
    for voterPubKey, (encSymKey, encSignedVote) in contract.registry.items()

Therefore, the operator can construct a proof that M(votes) == outcome, for whatever outcome. The proof is of the existence only of operator.myPrivKey, and because of the expression above, includes proofs of the validity of each vote. It shows that the various nonsense blobs in the contract are actually encryptions of correct data.

As you can see, only each voter knows their own symmetric key; it is stored as a message encrypted to the operator alone, and its correctness is established by the proof that the equation holds with the definition of votes given.

1 Like
18

Of course, only after posting that long thing did I understand what you were asking. I’ll leave it there since it seems useful, but I’ll answer your actual question here.

It does seem true that a voter could choose to reveal their own secret (symmetric) key in a way that someone else could verify, since it’s encrypted with the operator’s public key. And I do agree that this could be fixed if the operator actually kept their “public” key private, and placed that encrypted value themselves.

Would this actually require more zero-knowledge proofs? I think the voter could actually be sure their correct vote was used, if the expression for votes I gave in the long post is the one that goes into the overall proof: it requires checking the signature on their vote. The operator should be unable to produce any valid voter-signed message, particularly not in the way that this exploit we’re talking about would require: the operator would have to place the wrong symmetric key in the registry, which would result in the vote being censored just because it doesn’t decrypt correctly (but then break the proof because the signature is also not validated); to actually place a fake vote, the operator would have to somehow come up with a fake symmetric key that causes this bad decryption to be a correctly-signed vote. This is just not feasible.

The voter could of course give up their private key to a dishonest operator. However, the operator would still have to figure out an alternate symmetric key that would decrypt the actual encrypted vote to a signed, fake vote of their choice. I don’t think this is feasible either, though that depends on the encryption method and seems similar to actually cracking the encryption entirely.

1 Like
19

My proposal was that the operator put the voter’s symmetric key on-chain encrypted with the operator’s own public key. The voter would have no way of verifying that this was actually done, unless the encryption scheme is deterministic, and in the latter case the voter could prove to others what their key is.

I feel like any scheme that doesn’t involve a key revocation game is going to keep having these kinds of issues…

1 Like
20

After some thought, I have to agree that without the game it seems almost necessarily the case that a voter would be able to prove their vote. Essentially, the voter can prove their vote to a briber (thus soliciting a bribe) if they can supply a probabilistic algorithm computing their set of messages. In your scheme, they can enumerate it but not its complement. My scheme definitely has a deterministic proof of vote; actually, it shows up a lot earlier in the conversation, since the voter can always just reveal their “secret” key. Any voting scheme where the ultimate vote depends on a single message would have this problem; it has to be possible, no matter what the voter reveals, that they have omitted something important. Which is a game.

This has been very educational. I hope I wasn’t too obnoxious in the process.

1 Like
21

We are staring to implment this http://github.com/barryWhiteHat/maci

If anyone wants to join this effort please join https://t.me/joinchat/LUgOpE7J2gstRcZqdERyvw

1 Like
22

Hey everyone, just wanted to point out this topic, since it’s about a quadratic funding app built on MACI.
The project started at ETHDenver, where @barryWhiteHat and @weijiekoh helped us wrap our heads around MACI.

3 Likes
23

Hi all, I’ve recorded a basic explainer and demo of MACI: https://www.youtube.com/watch?v=sKuNj_IQVYI

It’s based on the implementation we’ve built here: https://github.com/barryWhiteHat/maci

7 Likes
24

EDIT I realized that MMRs were unnecessary for this, so I updated the post accordingly.

EDIT 2 After thinking about this more, I realized there is a further simplification where we replace the hash of the history with a nonce. I also realized that the vote buyer and vote seller can do a 2 party MPC to create a signed message for which only the buyer knows the nonce, so this does not totally prevent the attack that was described. This still seems like it could be an improvement to me though, in that instead of writing a potentially large new public key to the state, we are only writing a nonce.

This attack described by @barryWhiteHat seems concerning to me.

This mitigates the attack, but if the attacker guesses the number of messages a user sends during the key-switch phase, then they can still offer to pay for the first vote after the key-switch phase by requesting that number of key-switch-messages followed by an action message. Thus, this only decreases the expected number of votes per attacker money by a factor roughly equal to the number of key-switch messages in this phase.

With an eye to preventing this kind of attack here is a version of MACI which makes this kind of attack impossible harder. I think it also simplifies the protocol somewhat, but there can be O(1) additive increase in message size, ZK-SNARK circuit size, and state-per-participant.

In order to avoid vote-selling by an attacker that can add the first messages to the list, it is necessary to have any sequence of messages be “undoable” in the sense that you must be able to add more messages to the list that invalidate these actions. To this end, in this version of MACI we get rid of the key_change messages. Instead, we require action messages to include the tip of a hash chain of all messages previously sent from that account a randomly generated nonce.

The operator now maintains state[i].action and state[i].nonce for each participant. When a message is received, the operator checks that the signature is valid and state[i].tip_hash = message.nonce. If these checks pass, then state[i].action is updated to the new action and the update state[i].nonce is (optionally) updated to a new nonce.

A participant will now always be able to update their action, even if they update their initial action in the first message received by the system. Additionally, the participant sending the last message received by the system will not be able to prove their vote, because even if they expose their final encrypted message, they will be able to make actions beforehand that cause the hash chain tip on the final message to be invalid change the nonce, invalidating that message.

Indeed, since the nonce and action are updated simultaneously, one could just modify the action field to contain a few extra bytes of data to be ignored by the mechanism. This leaves the protocol almost exactly the same as the original, the only change is that the change_key messages are removed and a comparison against the old action is added to the message and SNARK.

1 Like
25

Hi,

I am a bit confused here about the collusion resistance property.

Seems it is a mixture of two classic security properties studied in the digital remote voting community.

First, it looks quite similar to receipt-freeness, where a voter is prohibited from selling his vote as there is no way for him/her to prove the voted option.

But we have another desired property, coercion resistance, formalized by JCJ. It showed that a coerced voter can evade coercion/threat from the adversary by giving away a fake credential or revoting to overwrite the coerced vote.

So I see the collusion resistance property is essentially equivalent to recipient-freeness here.
I think coercion is also a potential threat to blockchain-based voting protocol. I need coercion resistance in MACI as well.

1 Like
26

MACI is receipt-free in precisely the way you described.

A voter in MACI can create a fake receipt that is indistinguishable from a legitimate vote, by switching keys and casting a new vote and sharing a receipt from the now invalid vote.