MACI Process Messages Circuit

Repo link

This circuit allows the coordinator to prove that they have correctly processed each message in reverse order, in a consecutive batch of 5 ^ msgBatchDepth messages to the respective state leaf within the state tree. Coordinators would use this circuit to prove correct execution at the end of each Poll.

The processMessages circuit will try to decrypt the messages, and based on the content of the message, update within itself the trees, to generate a proof that the coordinator's off-chain processing was done correctly. In other words, the circuit takes a final state, an initial state, and the leaves (messages and user signups) - it processes these messages via the different state transitions to finally check that the expected state is correct. The pre-requisites for this circuit are:

• the related Poll has ended
• the state tree has been merged
• the message tree has been merged

This circuit requires the coordinator's private key, hence a proof for this circuit can only be generated by the coordinator. The private key is needed in order to generate the ECDH shared key used to decrypt the messages.

info

A version working with non quadratic voting (non-qv) is also available. This version is called processMessagesNonQV and is to be used when the Poll is not using the quadratic voting feature. Note that by default MACI works with quadratic voting.

Parameters

#	Parameter	Description
0	State tree depth	Allows $(2^{n})$ signups.
1	Message tree depth	Allows $(5^{n})$ votes or key-change messages.
2	Message batch tree depth	Allows $(5^{n})$ messages to be processed per batch.
3	Vote option tree depth	Allows $(5^{n})$ vote options.

Inputs

Input signal	Description
inputHash	The SHA256 hash of inputs supplied by the contract
packedVals	Described below
pollEndTimestamp	The Unix timestamp at which the poll ends
msgRoot	The root of the message tree
msgs	The batch of messages as an array of arrays
msgSubrootPathElements	Described below
coordinatorPubKeyHash	$poseidon_2([cPk_x, cPk_y])$
newSbCommitment	Described below
coordPrivKey	The coordinator's private key
coordPubKey	The coordinator's public key
encPubKeys	The public keys used to generate shared ECDH encryption keys to encrypt the messages
currentStateRoot	The state root before the commands are applied
currentStateLeaves	The state leaves upon which messages are applied
currentStateLeavesPathElements	The Merkle path to each incremental state root
currentSbCommitment	Described below
currentSbSalt	Described below
newSbCommitment	Described below
newSbSalt	Described below
currentBallotRoot	The root of the ballot tree before messages are applied
currentBallots	The ballots upon which ballots are applied
currentBallotsPathElements	The Merkle path to each incremental ballot root
currentVoteWeights	The existing vote weight for the vote option in the ballot which each command refers to
currentVoteWeightsPathElements	The Merkle path from each vote weight to the vote option root in its ballot

inputHash

All inputs to this circuit are private except for inputHash. To save gas during verification, the MessageProcessor contract hashes the following values using SHA256 and uses the hash as the sole element of $ic$:

1. packedVals
2. coordinatorPubKeyHash
3. msgRoot
4. currentSbCommitment
5. newSbCommitment
6. pollEndTimestamp

The hash is computed using the sha256 Solidity function and is then subject to modulo $p$.

packedVals

packedVals is the following values represented as one field element. Consider that a field element is roughly 253 bits. The big-endian bit-representation is as such:

Bits	Value
1st 53 bits	0
2nd 50 bits	batchEndIndex
3rd 50 bits	currentMessageBatchIndex
4th 50 bits	numSignUps
5th 50 bits	maxVoteOptions

For instance, if maxVoteOptions is 25 and batchEndIndex is 5, and all other values are 0, the following is the packedVals representation in hexadecimal:

140000000000000000000000000000000000019

currentSbCommitment and newSbCommitment

The currentSbCommitment is the $poseidon_3$ hash of the state tree root, the ballot tree root, and a random salt. The purpose of the random salt, which should be unique to each batch, is to ensure that the value of currentSbCommitment always changes even if all the commands in a batch are invalid and therefore do not change the state tree or ballot tree root.

The result of applying a batch of messages to currentSbCommitment is newSbCommitment.

currentSbSalt

The salt used to produce currentSbCommitment (see above).

newSbSalt

The salt used to produce newSbCommitment (see above).

msgSubrootPathElements

The index of each message in msgs is consecutive. As such, in order to prove that each message in msgs is indeed a leaf of the message tree, we compute the subtree root of msgs, and then verify that the subtree root is indeed a subroot of msgRoot.

A simplified example using a tree of arity 2:

             r
           /  \
          s    ...
       /    \
      o     o
     / \   / \
   a   b  c  d

To prove that a...d are leaves of the tree with root r, we prove that the leaves have the subroot s with depth 2, and then prove that s is a member of r at depth 1.

The implementation for this is in the QuinBatchLeavesExists circuit in https://github.com/privacy-scaling-explorations/maci/blob/dev/circuits/circom/trees/incrementalQuinTree.circom.

This method requires fewer circuit constraints than if we verified a Merkle proof for each leaf.

Statements that the circuit proves

1. That the prover knows the preimage to inputHash (see above)
2. That the prover knows the preimage to currentSbCommitment (that is, the state root, ballot root, and currentSbSalt)
3. That maxVoteOptions <= (5 ^ voteOptionTreeDepth)
4. That numSignUps <= (2 ^ stateTreeDepth)
5. That coordPubKey is correctly derived from coordPrivKey
6. That coordPubKey is the preimage to the Poseidon hash of coordPubKey (provided by the contract)
7. That each message in msgs exists in the message tree
8. That after decrypting and applying each message, in reverse order, to the corresponding state and ballot leaves, the new state root, new ballot root, and newSbSalt are the preimage to newSbCommitment