So we have a snark that processes votes one at a time. We need to add a way for users to

1. Que their votes in smart contract
2. Get added to the list of people who are able to join the quorum
3. Place their deposit int he smart contract.

The coordinator should be able to

1. Provide a snark proof that they updated the state correctly.
2. Provide a snark proof that they counted all the votes correctly.

https://hackmd.io/bnHseWFlQ5OzQpkjGBNUYA

From the spec FAQ:

for example for a user with trusted hardware:
User has trusted hardware that allows a single key change. The user has initial public key $pk$ and public key $pk2$
User registers with $pk$
User changes to $pk2$, with the trusted hardware attesting this is the second public key and no further key changes are allowed
Briber gets $sk2$ and the attestation and then uses $pk2$

https://vitalik.ca/general/2019/10/01/story.html

Add a decryption component so we can decrypt command inside the snark.

This should be added in circom and then called as a gadget from this repo.

Option 1: have the vote option tree root be an array of subroots, to support more than 2 ^ 7 vote options with 512g ram

Option 2: max out the Node memory limit and tradeoff witness generation time to get more than 2 ^ 10 vote options. See the benchmarks here: https://docs.google.com/document/d/1F9aovtY0ZA2iLuBO7s3uE0ar6iO7RFCaL7VMHVWqIQI/edit

We can provide a contract function which returns multiple values related to the MACI contract in once single call. This will reduce the number of required calls to the Ethereum provider by the CLI when it uses genMaciStateFromContract() (in cli/ts/utils.ts).

• Describe how people would use this as a tool
• Ideally people shouldn't know how MACI works under the hood.
• e.g. maci deploy deploys contracts etc

Refer to: #91

When a 3rd-party contract wants to trustlessly prove that they know the final vote tally of vote option n from MACI contract m, they should be able to do the following:

1. Have access to the salt s and vote tally commitment c, which should be retrievable on-chain from m
2. Have access to the full vote tally r. Assume that the coordinator gives them this data off-chain.
3. Generate a Merkle proof: proof = genMerkleProof(n, r)
4. Show that hash(proof.root, s) == c
5. Show that genMerkleRoot(proof.elements, proof.indices) == proof.root

See: https://hackmd.io/9nLUTbAvQUqjewfPTOifzw to choose the right t value. For binary Merkle trees, use t=3. Use a different value for hashing a Message.

Should Decrypt use Poseidon instead of MiMC7?

What's wrong

We currently encrypt plaintext with mimc hashes.

Explore how and why use a Poseidon based encryption/decryption method.

What's wrong

MACI is a highly evolving project and the data structure or variables might be constantly changing. It might be hard to update the spec frequently to reflect every change in the pull requests.

But the spec is still a good source to understand the design rationale of the project. We can create a task to track material changes that need to be updated in spec.

TODO

• #89

The UpdateStateTree circuit needs more unit tests. In particular, it needs tests which demonstrate that the no-op scenarios work as intended. This is a slightly heavy lift as MaciState contains asserts which make it difficult to generate such no-op commands, but that is exactly what we need to do for these tests.

• EddsaSpongeVerifier (copy from Semaphore?)
• HashLeftRight (done)
• Selector
• Replace MerkleTreeUpdate with MerkleTreeInclusionProof

Some of the cryptographic code (in crypto/) is custom-written and could do with a review.

• A README to explain what is T3, T6, and T11.
• Implement the circuit
• Gas cost benchmarking and number of constraints
  • for state update tree, and
  • the quad vote tally tree

Operator needs to create proofs from the encrhpted signatures in teh smart contract in the smart contract.

They should also be able to reveal the vote count.

The logic to create these proofs and broadcast them needs to be implemented.

Related to #89 and #90.

Here are two related questions:

1. How much on-chain work should MACI do to make the final vote tally available?
2. How much on-chain work should client applications do to access the final vote tally?

Two more questions:

3. How much on-chain work should MACI or client apps do to allow client apps to access the entire tally?
4. Can there be a compromise in the case where client apps can efficiently access the tally of one or more vote option(s) at a time?

As of the time of writing, our answers to the following questions are:

1. A minimal amount. We should just expose a cryptographic commitment to the final tally.
2. As much is needed.
3. MACI: a minimal amount. Just publish the final tally off-chain. Client apps: as much as needed
4. Yes. This issue will describe two ways to do this. The first way is to stick with PR #89 where the commitment to the final tally is a Merkle root, and to access a leaf in the final tally, the client app can just provide a Merkle proof to the leaf they need. The downside is that we need one proof per leaf.

The second way is as such:

1. At the end of the final tally, we have the commitment to the final results = c
2. Then, we publish [b0, b1, b2, b3] which are hashes of each batch of leaves [l0, l1, l2, l3], [l4, l5, l6, l7], and so on
3. We also publish the leaves off-chain.
4. When a client app wants to access the raw value of l5 in a trustless (verifiable) way, it does this:
   a. Provide a Merkle proof p from b1 to c
   b. Provide the raw values of [l4 ... l7]
5. If p is valid and hash([l4...l7]) == b1, then access l5. One benefit is that the client app can also access l4, l6, and l7 at the same time.

We currently won't implement this second method but we'll keep this issue open as a reference.

Going with the spirit of trying to keep PRs as concise as possible, this PR fixes the logic behind the circom circuit for the state tree update according to the spec https://hackmd.io/koAV1hpVSzuB1HZZCo844g

In updateStateTree.circom, we have component signature_verifier = VerifySignature(MESSAGE_WITHOUT_SIGNATURE_LENGTH); and MESSAGE_WITHOUT_SIGNATURE_LENGTH is 7.

In verify_signature.circom, VerifySignature takes k inputs. But we only use it for 7 inputs.

Also, there is a limit of 11 inputs as we use Hasher11:

  component M = Hasher11();
  for (var i = 0; i < k; i++){
    M.in[i] <== preimage[i];
  }
  for (var i = k; i < 11; i++){
    M.in[i] <== 0;
  }

We should modify VerifySignature to make the number of inputs constant so that anyone else who uses this code won't get surprised when they try to sign a plaintext of more than 11 items.

e.g. BatchUpdateStateTree(4, 4, 4, 4), BatchUpdateStateTree(5, 5, 5, 5) etc

The final invocation of proveVoteTallyBatch() requires that the sender pass in a uint256[] memory _finalResults value. There is be an upper limit on the size of the array (a simple test showed that the limit is between 2 ** 5 and 2 ** 6 values), and make it impossible to tally the final batch.

I have a workaround in mind but I will think of more solutions:

Create a function which accepts a batch of values from the full list of results, and inserts each value into a Merkle tree, and store the root on-chain. One transaction is required per batch. Once all batches have been inserted, the final invocation of proveVoteTallyBatch() can look up the root and use it to verify that the commitment to the final tally is correct. Doing so will, however, reveal the results before the final invocation of proveVoteTallyBatch().

Edit (3 May 2020): After discussing with @kobigurk, I've created issue #91 and will close this issue in favour of it.

We need a snark that is able to count the votes privaetly and just publish the result.

This is executed after the coordinatior has processed all of the previous commands.

#57

A quintree is ideal for Poseidon-based Merkle tree accumulators. But this will take a lot of work to implement.

Started work here: https://github.com/weijiekoh/maci/tree/feat/quadtree

Also see https://github.com/Loopring/protocols/blob/master/packages/loopring_v3/contracts/impl/libexchange/ExchangeBalances.sol#L95 for an example of a quadtree impl.

https://hackmd.io/xdT2x2-AQqmwrluZ2jkSxg

The larger the state and message tree depths, the more gas that a user (or relayer) has to pay to sign up or publish a message. The larger the vote option tree, state tree, and message tree depths, the longer it will take for the coordinator to generate proofs.

We can assume that the coordinator has more computational power than the average user, so it's okay to set the vote option tree to the maximum feasible size on consumer hardware (5 ^ 5 = 3125 leaves).

The message tree size should be large enough such that each user can cast 1 vote per vote option, plus an additional key-change message on top of that.

Let the depth of the state tree be s, the depth of the message tree be m, the depth of the vote option tree be v, and the number of voice credits as c.

Each user should be able to publish at least c + 1 messages, or 5 ** v + 1 messages, whichever is smaller. This is to let them either spend all their voice credits (1 credit per vote) or vote for up to all available vote options. Let this value be n.

The depth of the message tree should therefore be ceil(log2(2 ** s * n)).

E.g. Assuming that each user has 99 voice credits, the vote option tree depth is 4, and the state tree depth is 4:

n = 2 ** 4 + 1 = 17
ceil(log2(2 ** 4 * 17)) = 9

Predefined tree depths

Ultimately, whoever builds upon MACI has to decide exactly which tree depths works for their use case, and they have to be responsible for its specific trusted setup.

That said, if we use a Quadtree (see #101), we can support larger trees.

CC: we should just use Large because the gas savings are not that large

Motivation

In the book "Radical Markets" page 119, negative votes are proposed as a cheaper way to let a voter's favorite candidate stands out from a less favorable one.

To show why it's cheaper, consider a 2 candidate situation, and a voter Alice prefers Catherine over Carl. To make Catherine win Carl by 2 votes, Alice could

• vote +2 for Catherine, which costs 4 voice credits, or
• vote +1 for Catherine and -1 for Carl, which costs 2 voice credits only.

The result is useful in the situation that you have 3 candidates, the first two are widely loved by one camp of voters and hated by another, and the third is less hated but also not popular enough.

In the positive vote only situation, the voters would strategically vote the first two but not the third, to prevent the hated one winning.

But with the negative vote situation, the votes expect the first two get almost equally positive and negative votes and the third one could stand out. The voting dynamic is studied in this paper.

Possible design choices in MACI

Thanks to @weijie for writing this section.

Two ways are possible to implement negative votes in MACI. We demonstrate this with examples.

Alice has 99 voice credits
Bob has 99 voice credits

Vote options: party A and party B

Possibility 1 (hides information. e.g. the fact that a vote is polarised)

Bob votes for party A with 81 positive voice credits.
Party A now has +9 votes.

Alice does not like party A. She votes for party A with 36 negative voice credits.
Party A now has (+9) + (-6) = +3 votes.

Final tally = [3, 0]

Possibility 2 (shows information, e.g. the fact that a vote is polarised)

Bob votes for party A with 81 positive voice credits.
Party A now has 9 positive votes and 0 negative votes.

Alice does not like party A. She votes for party A with 36 negative voice credits.

Party A now has 9 positive votes and 6 negative votes.

Final tally = [(9, 6), (0, 0)]

Discussion

In Possibility 1 we have to worry about the overflow/underflow. Say, if party A only has -6 votes, what would the result look like?

The Possibility 2 we tally the positive vote and negative votes in a different array. We don't have to worry about the overflow/underflow in this case.

Experiment

Circuit is happy with negative inputs?

Consider this circuit. Input { 'a': -1, 'b': 4 } would gives witness [ 1n, -4n, -1n, 4n ]

 template Multiplier() {
       signal private input a;
       signal private input b;
       signal output c;
       
       c <== a*b;
   }

component main = Multiplier();

This either means the current circuit support negative vote natively or we have to handle the range of input values carefully.

Summary of discussion with @weijiekoh yesterday.

What's wrong

The circomlib assembly evm code supports up to Poseidon T6. To hash more than 5 items, we either need to implement new evm code or hash items with only T6.

How can we fix that

Currently, we have objects "Message" and "vote options" that need hashing more than 5 items. For vote options, since we expect supporting up to 2**10 of options, we build a merkle tree for it.

To hash 11 items in message, there are two options we can explore.

Option 1:

Hasher2(
    Hasher2 (
        Hasher5(a1, a2, a3, a4, a5),
        Hasher5(a6, a7, a8, a9, a10)
    ),
    a11
)

Option 2 (@kobigurk's proposal):

c= 0
out1_1, out1_2,out1_3,  out1_4, out1_5, c' = permutation6(a1,a2,a3,a4,a5, c)
out2_1, out2_2,out2_3,  out2_4, out2_5, c'' =permutation6(a6,a7,a8,a9,a10, c')
out_final, _, _, _, _, _ = permutation6(out1_1,out2_1,a11, 0, 0, c'')

Where permutation6 is Poseidon t=6, but we output all elements in the state, instead of only the first element.

SubTasks

• A README to explain Poseidon.
• Implement the circuit
• Gas cost benchmarking and number of constraints
  • for state update tree, and
  • the quad vote tally tree

This also entails regenerating the snark files (use the npm script in the circuits submodule to do so), and replacing them in the shared Dropbox folder.

This might not be necessary as we can reasonably assume that snarkjs works as long as the witness is correct. The proof generation for the snarks can also take a prohibitively long time. The batch UST snark test takes 4 minutes including proof generation. A solution is that we can just write the tests and comment out the proof generation steps.

Build a UI that makes this easy for users to vote.

The UI should force them to update their public key before voting.

Suggestions on how to proceed with this task:

1. Clone the repository and try out the build and test steps: https://github.com/barryWhiteHat/maci/blob/master/README.md

2. Read the spec and focus on the processMessage contract functionn updateStateTree circuit, and quadratic vote tally circuit.

3. Modify the spec with the solution for negative votes

4. Modify the contract, circuits, and tests. The tests are:

   • circuits/ts/__tests__/BatchUpdateStateTree.test.ts
   • circuits/ts/__tests__/UpdateStateTree.test.ts
   • circuits/ts/__tests__/QuadVoteTally.test.ts
   • contracts/ts/__tests__/Maci.test.ts

5. Don't worry about Maci.test.ts at the start. It's perfectly fine to update it last.

6. Get familiar with the way that CircleCI performs a trusted setup whenever we modify a circuit, and take advantage of it to save time. You can download the circuit, proving keys, verification keys, and verifier contracts from CircleCI artifacts. See also: https://github.com/barryWhiteHat/maci/blob/master/.circleci/config.yml#L46

Link from Barry: https://ethresear.ch/t/batch-deposits-for-op-zk-rollup-mixers-maci/6883

No longer necessary thanks to #73.

• The snark should output the salted hash of the cumulative tally for each batch of leaves

• The vote leaves should be private inputs

• The coordinator can reveal the final salt and results at the end

• TODO: update spec, circuit code, and tests