# MACI voice credit issue

## Background

The following quotes are from the Telegram chat and provide some context for this issue:

> The goal is for our contracts to know how many voice credits were used to vote for each each project in the round.
> The problem is that it is not easy to determine the number of voice credits used to vote for each project from the final vote tally.
> the problem is that MACI currently gives the matching amount but forgets about the users actual funds that were donated and just gives the matching ?

> In QF, there are two pools of funding, the matching pool and the direct funding pool.

> The contributions to the direct funding pool are what we use to determine voice credits. This pool of funding should be allocated 1:1 compared to how voice credits are allocated.

> The matching pool, should be allocated according to the quadratic vote weight that each recipient receives.

> So basically, we would need MACI to give each project the ability to prove two things.
> 1. The total voice credits that were allocated to it for the round.
> 2. The total quadratic vote weight allocated to it for the round.
>

## Problem statement

Alice has 81 voice credits and spends them all on Project A. Now Project A has 9 votes.

Bob has 36 voice credits and spends them all on Project A. Now, Project A has 9 + 6 = 15 votes.

Charlie has 25 voice credits and spends none of them.

At the end of the vote tallying process, Project A has 15 votes. But nobody knows that Alice had spent 81 voice credits, Bob had spent 36 voice credits, and Charlie spent 0 voice credits. After all, the following scenario is also possible: Alice, Bob and Charlie could have each spent 25 voice credits on Project A, so it would have received `sqrt(25) * 3 = 15` votes. But in this thought experiment, only one scenario could have occurred.

Nor is it possible to determine the number of voice credits spent from the number of votes received. For instance, in the former scenario, Alice and Bob spent 117 voice credits, but in the latter scenario, Alice, Bob, and Charlie spent 75 voice credits.

81 + 36 + 0 = 117
25 * 3 = 75

Only the coordinator knows how many voice credit each users had spent.

**fix if incorrect please:** clrfund needs a way for a smart contract to know how many voice credits each vote option received, *in addition* to the vote tally (which is the sum of the square roots of the voice credits spent per vote).

## Solution

https://github.com/appliedzkp/maci/pull/119

## How to determine unspent voice credits

### Problem statement
Here is a second scenario: during the signup period, the InitialVoiceCreditProxy assigns 81 voice credits to Alice and 36 to Bob (and the total is 117 voice credits). During the voting period, Alice spends 25 voice credits and Bob spends 25 voice credits. Now, the total unspent voice credits is 117 - 50 = 67.

The voice credit tree solution above can only tell us that the number of voice credits spent per vote option.

Here is a naive manual solution: look at the `signUp()`s and the InitialVoiceCreditProxy logic and determine the total voice credits allocated. Then deduct the number of voice credits spent at the end of the tally process. But this is not ideal if you want a trustless/on-chain calculation.

### Solution

1. Modify the MACI contract to keep a running tally of the number of voice credits assigned by the InitialVoiceCreditProxy during the signup period. This value should be stored in the contract. Let this value be `totalVoiceCreditsAssigned`.

2. Modify `QuadVoteTally` to also tally the cumulative total of spent voice credits during the vote tallying process, and store the cumulative total on-chain as an output from the snark. This value should be salted and hashed to prevent data leakage and prevent Eve from gaining information about whether the voice credits spent by voters in a particular batch. Let this value be `spentVoiceCreditsCommitment`.

signal public input totalSpentVoiceCreditsCommitment
signal private input totalSpentVoiceCreditsSalt
signal public input totalSpentVoiceCredits
signal private input newTotalSpentVoiceCreditsSalt

signal h = hashLeftRight(totalSpentVoiceCredits, totalSpentVoiceCreditsSalt)
totalSpentVoiceCreditsCommitment == h

var cumulativeTotal = totalSpentVoiceCredits
for each state leaf:
    for each vote option leaf:
        cumulativeTotal += .....

newCommitment = hash(cumulativeTotal, newTotalSpentVoiceCreditsSalt)
signal output newTotalSpentVoiceCreditsCommitment

newTotalSpentVoiceCreditsCommitment <== newCommitment

3. Once the vote tally is complete, any contract can do the following:

function computeUnspentVoiceCredits(uint256 totalSpent, uint256 salt) public returns (uint256) {
    uint256 h = hashLeftRight(totalSpent, salt);
    require(h == spentVoiceCreditsCommitment);
    
    return totalVoiceCreditsAssigned - totalSpent;
}

## Impact of revealing spent & unspent voice credits on collusion resistance

It's still an open question as to exactly how to describe the impact of making the number of voice credits spent per vote option public as it depends on how many voters there are and the distribution of votes. But here are some scenarios where a briber/attacker could learn things that they otherwise would not. The question is: how much damage could they do with this information?

### Vulnerability 1: Eve can tell if not enough voice credits were allocated

From Tommy in the TG chat:

> I think the bigger and more likely vulnerability is the fact that a briber can tell that the voice credit amount received is less than what they bribed for, or fits into any vote scenario, especially if no one else votes for it because it's a scam - they'll likely receive nothing at the end of the round which will be an immediate red flag.

Scenario:

Eve (CEO of ECorp) bribes Alice to spend 100 voice credits towards ECorp, which ends up being one of the few (albeit invalidated) votes towards the vote option due to the voters' lack of faith in ECorp. Not only is it easy for Eve to determine voice credit distribution based on Vulnerability 2, **it's very likely that ECorp is going to receive less voice credits than initially bribed for**; even if ECorp receives over 100 voice credits from a small handful of sources - there's a good chance it wouldn't create the necessary vote scenario to provide plausible deniability (see Vulnerability 2).

### Vulnerability 2: Eve can make better guesses about the number of voters per vote option

Let's say that Eve is a briber. There is a MACI system which shows how many voice credits were spent per vote option after the tallying process is overss is overss is overss is overss is over. In this system, Eve can learn more information about how users had voted.

The more voters to each vote option receives, the more unlikely that this attack will succeed. But in the real world, there may be a long tail of vote options which receive very few voters.

For instance:

1. Option A receives 5 votes and 25 voice credits were spent on it.

Eve now knows that exactly 1 person voted for Option A (rather than 5 people each spending 1 voice credit each, or 2 people spending 4 + 9 voice credits, etc).

In other words, if we know that `voiceCredits(option) == sqrt(votes(option))` then we know that `numVoters(option) == 1`

2. Option A receives 8 votes and 34 voice credits were spent on it.

Eve knows that `sqrt(34)` is not a whole number. So it must be the sum of more than 1 square root. She makes the following guesses:

34 = 1 + 33
34 = 4 + 30
34 = 9 + 25 *and* sqrt(9) + sqrt(25) = 8. **jackpot!**
34 = 16 + 18

Eve thinks: maybe there are more than 2 voters.

34 = 1 + 1 + 32
34 = 1 + 4 + 29
34 = 1 + 9 + 24
34 = 1 + 16 + 17
34 = 9 + 9 + 16 *but* sqrt(9) + sqrt(9) + sqrt(16) = 10 **so (9, 9, 16) is incorrect**

and so on....

Maybe there are possible combinations in addition to 9 + 25. But Eve has at least ruled out a bunch of possibilities.

To automate the above, Eve can use WolframAlpha as such and find results which sum to 8.

https://www.wolframalpha.com/input/?i=PowersRepresentations%5B34%2C+34%2C+2%5D