MACI Anonymous Conflict of interest checks

[ctrlc03]

Motivation

With MACI potentially being used in Optimism next RPGF round, it is time to think how MACI can be amended to allow for anonymously checking conflict of interests.

This discussions aims to provide a proposal, and gather feedback from the community.

OP's RPGF rounds

In all of OP's RPGF rounds run so far, the users allowed to vote were chosen by the community and the OP foundation. These are called BadgeHolders, and the badge is essentially an EAS attestation.

BadgeHolders are asked to disclose any conflict of interest before voting starts, and the Foundation's job is to confirm whether there are any more conflicts that should be accounted for.

Proposed Design

First of all, we need to understand how to efficiently represent conflict of interests. We need to consider that this data needs to be stored on a smart contract and passed to a zk-SNARK circuit, to ensure that the correct data is used by the coordinator.

Data Representation

Given MACI's vote options are represented as unsigned integers, from 0 to 5 ** voteOptionTreeDepth, an easy approach could be to store conflict of interests as an array of unsigned integers for which the user cannot vote. This would be a blacklist, vs a whitelist, as we (well correctly if I'm wrong) assume that overall it's likely that conflicts of interests per voter are less than half of the total projects eligible for a round.

As an example, given 10 vote options, and 3 conflict of interests for option 3, 4, 8 we would have an array like this:

[3, 4, 8]

On the other hand, we could instead create an array of length max vote options, with elements being 1 for can vote, and 0 cannot vote, as shown below:

[1, 1, 1, 0, 0, 1, 1, 1, 0, 1]

Before we decide which of the two representations to go for, we also need to think about how to succinctly represent such data, perhaps we could hash it or construct a Merkle Tree with it?

Succinct representation

Hashing the data brings one problem, we cannot hash arbitrarily long amount of data, we need to know before hand the length of the ciphertext. Sure, we could create Poseidon hash functions which hash up to max vote options, though it might not be very efficient at scale.

What about Merkle trees?

We could create a Merkle tree for each voter, and store in their state leaf the merkle root, and the tree depth as well. This way we would have predictable length input, and then we could use the root and depth to check whether the option is part of the tree.

In this case, it makes sense to use a fixed length array, as described above when representing allowed options as 1, and use that to create a merkle tree.

Contracts changes

On the contract level, we are going to need to have a contract where we can fetch this information from. This could either be a separate contract, the EASGatekeeper contract or even come directly from the EAS attestation data field. Either way, this data needs to be inserted into the user StateLeaf. Looking at the state leaf, this currently looks like this:

StateLeaf

{
  "signupTimestamp": "bigint",
  "voiceCreditBalance": "bigint",
  "maciPublicKey": {
     "x": "bigint",
     "y": "bigint"
  }
}

We could add a field that holds the root of the merkle tree with these options.

{
  "signupTimestamp": "bigint",
  "voiceCreditBalance": "bigint",
  "maciPublicKey": {
     "x": "bigint",
     "y": "bigint"
  },
  "conflictOfInterestsRootHash": "bigint"
}

The signup event should be amended to include this field too:

 event SignUp(
    uint256 _stateIndex,
    uint256 indexed _userPubKeyX,
    uint256 indexed _userPubKeyY,
    uint256 _voiceCreditBalance,
    uint256 _timestamp,
    uint256 _conflictOfInterestsRootHash
 );

TS (crypto/domainobjs/core/cli) changes

The TypeScript code should be amended to accomodate those changes too. First of all, the StateLeaf should include the new root parameter. Furthermore, we could also include the full array of conflict of interests, though this should not be part of the circuit and contracts serialization functions. We will also need to consider whether it's efficient to store this data for each state leaf, or dynamically fetch it (from where TBD) each time we process a message. These data could for instance be pulled in the genMaciState utility. At a minimum, within this utility we should account for the root hash to be pulled from the events.

On the crypto package side, I can't think of any changes at this time.

Within the core package, we should ensure we have this data saved for each state leaf, as it will need to be passed to the circuit. Within the Poll.ts we can easily validate if a message is valid by checking if the corresponding entry in the conflict of interests array is 1 or 0. Given we will need to construct a merkle tree locally to generate the inclusion proof, we could perhaps store only the blacklisted options, and fill with 0 the other leaves where the option is allowed (this needs much more thought for sure).

In terms of message validation, around this line we could add the following logic:

if (this.stateLeaf.conflicts[command.voteOptionIndex] === 1) {
    throw new ProcessMessageError(ProcessMessageErrors.ConflictOfInterest);
}

Then, talking about inputs to the message processing circuit, we will need to pass the conflict of interests root (part of the state leaf) and path elements for the proof of inclusion (to be generated with a local tree). The path indices can be generated in the circuit. On top of that, we will need to pass an array of 1 or 0 for whether each message has a vote option that is allowed or not. So when sending a message batch of five messages, we would also need to send whether they should be counted or not, thus another array of the same length.

Circuit changes

Ok now the most interesting part, and perhaps most complex. How do we include this logic into the circuit, keeping it as optimized as possible, and also prevent coordinator from being able to censor votes.

As usual, the circuit will accept the state leaf corresponding to a command's stateLeafIndex field. The state leaf needs to be hashed and used as leaf for the inclusion proof, to validate that it's part of MACI's state tree. On top of that, we now need to also check whether the option is blacklisted or not.

We can use the voteOptionIndex as input to QuinGeneratePathIndices, so that we can generate the path indices from the index of the vote to reach the root. Now together with the path elements passed as input, and with the leaf being 1 or 0 depending on whether the option is allowed or not, we can generate the root. Then use this root hashed with the other parts of the state leaf to verify whether this leaf is part of the state tree. This way we can be sure that if the coordinator tries to censor votes by sending 0 for an option (when it should be valid instead so 1), then the generated merkle root would be different, causing the hash of the state leaf to not validate within the state tree.

Within the MessageValidator template, we add another input which is whether the vote option is allowed or not, then check whether all checks + this input is equal to 8 (or 7 for non qv). This way we'd get back whether the message is valid or not.

In terms of performance, we'd be adding more inputs to the circuit, and one more inclusion proof to be calculated for each message. Is there a way to make this more efficient?

Thinking about proof verification on the contract side and public inputs required to prevent cheating by the coordinator, I think that the state tree root is enough to prevent censoring, but I might have missed something.

Will this always be accurate?

Well, it really depends on the work done beforehand. MACI's can guarantee correct execution cryptographically, though it is not an easy feat to correctly validate conflicts of interests for all voters.

Future work

Potential future work that could come after this:

• weighted conflict of interests:
  • users could be either allowed to not vote
  • users could be allowed to vote for a certain project but their vote would only count a %

Should this go into MACI's core protocol

Short answer, I believe it should not. This proposal adds several constraints to the circuit and logic that would make the protocol less efficient for normal voting rounds.

[crisgarner]

Declaring conflict of interest wouldn't be enough in most cases as the round owner needs to verify if it's a valid declaration of conflict of interest, a solution could be having a Gatekeeper that requires that the declared conflict is approved by the owner of the round.

[ctrlc03]

Yes this is mentioned above. The round organizer must be doing the work to verify and add new conflicts of interests that weren't declared. The data can go either in the EAS data field or in the gatekeeper. The proposed solution was to create a merkle tree with the conflicts of interest, which must be done by the organizer

[baumstern]

Should this go into MACI's core protocol

Short answer, I believe it should not. This proposal adds several constraints to the circuit and logic that would make the protocol less efficient for normal voting rounds.

100% agree.

[crisgarner]

Another thing to consider, having exclusion proofs for conflict of interests, bad actors could use it to bribe voters into not voting for an option and get a recipe that they didn't.

[ctrlc03]

There's no receipt that one did or did not. if they do vote for one they can't, it just won't be counted
did I misunderstand your comment?

[ctrlc03]

Or you mean that one could bribe an user to disclose a certain (and possibly not true) conflict of interest so they would be sure they can't vote for that one option?

[crisgarner]

Or you mean that one could bribe an user to disclose a certain (and possibly not true) conflict of interest so they would be sure they can't vote for that one option?

This one, and you can prove that you didn't vote for that one right?

[ctrlc03]

well no need to prove that, there are guarantees that if you vote for one option that you are not allowed to, then it won't be considered as valid