<style> section { text-align: left; font-size: 3.0vh; } .mermaid { scale: 0.8; } code { color: #c7254e; } em { color: #e81dd1; } </style> # Revisiting MPC-MACI Yar, Lev, 2024 July 23 --- ## Voting properties * Soundness - voting outcome function is computed correctly. * Privacy - no additional information about voters choices is revealed. * Additional desirable property: non-coercibility - voter is unable to reveal any additional information about their vote (and whether they have voted or not). --- ## Caveats Non-coercibility is frequently referred as collusion resistance. This is expressive, but incorrect. For example, in a binary voting scenario, any part can try to bribe voters by promising to pay *everyone* if they win. Another good example is failure to prevent collusion in quadratic voting scenario. --- ## MACI Standard crypto-voting schemes (such as Semaphore) do not have non-coercibility. Real world voting systems typically do, in some form. MACI - minimal anti-collusion infrastructure, suggested by Vitalik Buterin, is a voting protocol which *does* have non-coercibility. --- ## MACI MACI (as originally described by Vitalik) works as follows: 1. There is a trusted coordinator which does the tallying. It maintains *private* list of valid public keys of voters. 2. Every voter is able to send transactions (over idealized private blockchain, to ensure non-censorability), encrypted with coordinator's public key. 3. There are to kinds of transaction: `vote` and `keyswitch`. Keyswitch allows the voter to replace their current public key with a different one. 4. Coordinator processes transactions in a sequence, and only counts actions that are signed with the *current* key. It outputs voting function and zk-proof of correct tally. --- ## MACI Example: Alice initially has public key A1. She sends the following sequence of transactions (all signed by first argument): `keyswitch(A1, A2)` `vote(A1, X)` `keyswitch(A1, A3)` `vote(A3,X)` `vote(A2, Y)` All transactions but first and last will be ignored, and result is that Alice has voted for option `Y`. Non-coercibility is achieved as follows - briber / coercing party can not be sure that Alice *did not* switch the key before sending the revealed transaction. --- ## Caveats 1. Hooman factor: Alice must actually run the resistance method. Low-agency voters can just choose to not be aware about it ("rational ignorance"). 2. Alice must unconditionally possess her private key - in particular should be able to use it from a device / internet connection not monitored by the attacker. 3. There is some sort of race during initial setup phase - i.e. when Alice registers her public key for the first time, a briber might try to buy it and rush to `keyswitch` it first. *In theory, this is somewhat mitigated by only doing this setup once and using the system for multiple votings.* --- ## 2PC attack on setup There is a well-known attack on setup, which works as follows: briber and Alice participate in 2PC (similar to TLS-Notary), and communicate with the setup server (and do whatever Alice is supposed to do during the setup). In the end of the protocol, Alice's private key is revealed to the briber. No good mitigations (barring meatspace ceremonies) are known, though there is some research related to kind of PoW functions which are hard to compute in 2PC. We typically refuse to consider "hard setup problem" altogether, and pretend that the briber only appears after some time after the setup. --- ## Real-world MACI Current version of MACI drastically differs from original Vitalik's vision.  --- ## Real-world MACI No, really. Unless we misunderstood something: * It processes the votes in a reverse order (which counters the racing attack, but instead now briber can try to send the vote last, which seems even worse). * And to add insult to injury, it also uses nonces which are set up by the voter (which is absolutely ineffective because briber will always request a nonce=1 keyswitch). * We sincerely hope that it is a misunderstanding on our side, and that actually we are idiots, because the alternative is far worse. * We will not discuss this system in our talk. :) --- ## MPC MACI - challenges * MACI has a weak point - trusted coordinator. But we could replace it with MPC? * We want to have a collaborative SNARK, so it is strictly better than normal MACI, and not a tradeof. * This seems very hard, as MACI is naturally a sequential computation. --- ## Initial approach - move as much data outside of MPC as possible - move as much verifications and checks outside of MPC as possible For example 1. Instead of checking user's signature server can require user to submit a public proof that they know private key for the public key encapsulated in the encrypted transaction 2. User can publicly prove that their encrypted vote vector is correct. This is particularly important if different users have different valid vote vectors (e.g. voting stake). 3. We can avoid running vote decryption circuit in MPC with a bit more involved technique, called "commitment trick" (see next slide) Note: Our first, and very general idea is to move as much data outside of MPC as possible. Voter will accompany the transaction with a zk proof, which asserts some statements about it. This removes the load from the coordinator and redistributes it to the user (which we believe is an acceptable tradeof even for non-MPC MACI, but for MPC is extremely important). 1. Instead of checking signature of the vote, we can expose the zk proof that user knows the private corresponding to the public key of the transaction on the "outside", and public key itself stays encrypted. This way, we do not need to check the signature of the public key on a server. 2. User can prove that their vote vector is correct, so this also does not need to be checked in MPC. This is particularly important if different users have different valid vote vectors (e.g. voting stake). 3. With a bit more involved technique, called "commitment trick" (see next slide), we can avoid running vote decryption circuit in MPC. --- ## Commitment trick El Gamal is relatively cheap in MPC, but we would like not to have it's decryption circuit in final SNARK. Our approach is as follows: user sends - encrypted vote - homomorphic commitment to this vote, *shifted right by some unique public random offset* - proof of integrity that shows that the decrypted message obtained by MPC coincides with the decommitment. Now, the commitment to the union of votes is just a sum of all the commitments exposed by individual valid votes. Note: Actually, message decryption using El Gamal is relatively cheap in MPC, because one can use sharing over the cryptographic group, but the question is how to combine it with collaborative SNARK - naive threshold decryption will not give a collaborative SNARK witness. Our approach is as follows: user sends the encrypted vote (to decrypt using threshold decryption), and a homomorphic commitment to this vote, *shifted right by some random offset* (it must be unique - they will need to re-submit vote in low probability scenario where different user also sends the vote with the same offset). They also provide proof of integrity that shows that encrypted message obtained by MPC *coincides* with decommitment. Now, the union of votes is just set to be a sum of all the commitments exposed by individual valid votes. Even in non-MPC MACI it allows to not run the decryption circuit, which is a significant portion of server work. For MPC version, it is even more crucial. --- ## Result of the approach The computation that actually needs to be done in MPC is purely sequential MACI core. As ORAM is out of question, we were able to instead simulate it using `log(m)` oblivious permutations. This, however, seems very involved. Additional issue was the necessity to keep the voter registry indefinitely. While not that big of a problem for a single party, for multiple untrusted parties that might be an issue. We have developed an approach that solves both of these problems - Keychain. --- ## What is keychain? Keychain is a *non-coercible private key*. It has some maximal power `MAXPOW`, and 1. Allows to make a signature of power `k <= MAXPOW`. 2. It is impossible to convince the briber that power `MAXPOW` is some particular value and not larger. 3. Amount of computational work required to create the keychain of power `MAXPOW` is linear in it, and marginal computational work to increase it by `1` is small (much smaller than a size of a typical bribe). --- ## Idealized keychain Private key is: - random root `r` - private key `p` - (practically unbounded) length parameter `MAXPOW` Public key of power `MAXPOW - k`: - $P_k = h^k_{(p)}(r)$ where $h_{(p)}(x) = h(x | p)$ --- ## Voting with keychain In the most basic scenario ballot is: - user id - vote - power `k` - proof that the vote is well-formed: + there exists user with this id + the vote itself is well-formed + the user knows a keychain of length at least `k` associated with this user id --- ## Selling keychain - a structured root attack Non-coercibility, depends on inability to prove that power `k` is maximal. However, if the root is chosen by the user, and they are *willing to be bribed*, such user can choose root in such a way that there is a negligible probability of finding a hash preimage of `r` - for example, structured root can start with a lot of leading zeros. Our "hard setup" ceremony chooses the root for the user, countering this attack. --- ## Keychain registrator We enstate a simple protocol that will delegate the obligation to generate *random* root to the registrator party ```mermaid sequenceDiagram participant U as User participant R as Registrator Note over U: generate private key p Note over R: generate random root r R->>U: r Note over U: choose MAXPOW, compute public key P Note over U: make a proof that P is well-formed U->>R: P, proof Note over R: verify proof of P, publish P ``` --- ## Required ingredients 1 2 years ago, we were unable to implement this protocol. This is clearly at least partially a `skill issue`, but not only it: Registration phase requires a proof that attests that user knows the keychain of *some* depth `MAXPOW`, without revealing it. This proof must be recursive. We have made a prototype using STARK system Plonky2, but actually, a EC-friendly proof is required - because registrator authority will likely also be an MPC, and checking STARK proof in MPC is likely impossible. --- ## Required ingredients 2 Our commitment trick is relatively hard to implement in practice. This is likele purely a skill issue, i.e. it is not a fundamental constraint of any sort. --- ## Required ingredients 3 - Tooling for MPC was inadequate, at that point. Namely, we needed a collaborative SNARK of oblivious sort, and it turned out to be harder than we expected. - However, we believe it should be possible now - and are in search of appropriate tooling for the task. --- ## Oblivious Sort Oblivious sort by register of size `r` can be constructed as radix sort, using oblivious `log(r)` random permutations to stable sort by each bit. This is a construction of Hamada et al. We are not sure what is the correct choice for oblivious permutation. We are considering a construction of Peeter Laud for SPDZ, and generic mixnet methods. --- ## Thanks ## Q&A?