MACI with mostly-off-chain "happy path"

For background, see: Minimal anti-collusion infrastructure

One of the challenges of MACI is that it requires data to be submitted on-chain for each vote, which incurs significant transaction fees. This post suggests a mechanism by which votes can be off-chain by default; a vote would only need to go on-chain if the coordinator is actively attempting to censor voters.

When a user makes a vote, take the following steps:

  1. The user locally generates their vote, as in regular MACI
  2. The user sends their vote to the coordinator
  3. The coordinator replies with a signature, specifying which position of the next batch the user’s vote will be included at
  4. When the coordinator submits their next batch, they submit only a hash to the chain. The hash must be the Merkle root of all votes that have been sent to the coordinator since the previous round. The coordinator is also required to publish the full set of votes (eg. on IPFS).

The ZK-SNARK enforces that the final vote results are the result of processing all submitted votes, including votes that have been published via this hash mechanism.

Users have access to two extra features:

  1. They have the ability to submit a vote directly to chain. The coordinator is forced to process both types of votes (included via hash, and included directly)
  2. If a user has a cryptographically signed promise, they can publish that promise on chain as a challenge. Any future message that the coordinator submits (a batch or the final result) must come with a SNARK proving that the correct votes have been included at the provided challenge positions.

This ensures the following properties:

  • Assuming an honest coordinator, onchain costs go down to O(1) per batch period
  • Censorship resistance is maintained, because users can go onchain worst-case
  • We mitigate attacks where the coordinator pretends to accept a vote, but then fails to include it, hoping that most voters will not notice or re-open any kind of software daemon, by providing signatures:
    • If a user fails to get a signature immediately, they go straight to voting onchain.
    • If a user gets a signature, and they do come back to check after the batch, they can check on IPFS (or ask the coordinator) for the Merkle branch associated with their vote; if it does not match their signature, they can publish their signature to chain, which effectively halts the entire vote and prevents it from giving a result. Hence, trying to censor even one voter becomes extremely risky for a coordinator.
6 Likes

A problem with these sort of designs is that there isn’t any way to punish censorship. While users who are censored can get around the censorship, the operators have no incentive to not censor. In this case, you can only punish the censor if they are dumb or make a mistake (promise to include but then don’t). The system cannot stop the censor from simply ignoring the censored user.

Most services (especially those run in the US) actively censor any accounts/users who have opted-in to privacy in the past. IIUC the proposed system would allow these users to pay extra to bypass censorship, but the censorship will continue as it is today.

I feel like we need solutions that allow us to punish censors, rather than just giving high-cost alternatives that censored users can utilize (if they are wealthy enough).

I don’t have a solution to this problem, but it feels like since we have witnessed rampant censorship on Ethereum lately, we shouldn’t be designing systems that are cheap for the uncesnored users and expensive for censored users. I think there may be value (in the greater good sense of the word) in keeping the system equally expensive for everyone, so at least there isn’t disincentive to engaging in censored activities (which are often exactly the type of activities we should be encouraging). If we build a two-tier system where users who don’t speak out against their government, utilize privacy tools, or express dissent about The Current Thing can do everything cheaply while users who engage in such activities have to pay more, we are driving people to not engage in those activities.

Other than the above concerns the system seems reasonable though.

4 Likes

Currently working on relevance work related to MACI, which you might find interesting:

  1. Accelerating user proof generation using GPUs.
    GitHub - Mirror-Tang/vortex: Modular ZK proof layer

  2. A comprehensive study on ZK auditing, including an analysis of vulnerabilities found in MACI.
    Zero-Knowledge Proof Vulnerability Analysis and Security Auditing

At the same time:
Doing more work off-chain in the short term can help the popularization of ZK applications on Ethereum and the participation of more enterprise users. However, in the long term, the original intent of building Ethereum was to enable it to support more diversified functions and computing capabilities. I believe that compared to Rollups, Danksharding is the ultimate solution. Let’s keep persevering and draw strength from the imitators. I urge every reader to pay attention to the progress of work on Danksharding.

2 Likes

Erasure Coding

  • Fragment votes into n pieces with redundancy r.
  • Use the formula for reconstruction: ( n_{required} = \lceil n/2 \rceil + r )
  • Store fragments across multiple nodes.

Multi-party Computation (MPC)

  • Use MPC protocols to securely aggregate vote fragments.
  • Reveal only the computed result, keeping individual votes encrypted:
    \text{Result} = \text{MPC}(\text{Encrypted Fragments})

Benefits

  • Fault Tolerance: Operates even with node failures.
  • Security: No single node has enough data to compromise the vote.
  • Privacy: Votes remain encrypted, enhancing voter confidentiality.
1 Like

Two possible ideas:

  1. Whenever we end up turning the coordinator into an MPC (or FHE decryptor), we allow each of the participants to submit batches. This gives us an N-of-N assumption for liveness. If we want to relax this, we could require such batches to get k signoffs (k is tunable), and get a (N-k)-of-N assumption
  2. Make the default vote submission interface anonymized. So you “sign in” to provide an anonymized vote by proving that you are a voter without revealing which one. So the coordinator cannot refuse any specific voter without refusing all of them.
5 Likes