Skip to main content
Version: v2.x

MACI v1.0 Specification

info

This document is a copy of the MACI 1.0 Specification (for audit) document, created in July 2021 for one of MACI's formal audits.

This historical document is stored here for informational purposes. We do not intend to edit it. As a result, some of the information within this document may be outdated.

This is a detailed specification meant to assist auditors in reviewing MACI version 1.0.

We thank the Zkopru team for their protocol specification, which this document adopts.

Audit scope

The commit hashes relevant to this audit are the following:

NameCommit
appliedzkp/maci (v1 branch)2db5f625b67a6b810bd851950d7a42c26189088b
weijiekoh/circomlib (feat/poseidon-encryption branch)0e78dde8c813b95f4585b0613927e9c4269de500

The scope of the audit with regards to the circomlib library covers:

  • all the JS files that MACI references, excluding those which are not referenced by MACI's TS files
  • all circuit files excluding those which are not referenced by MACI's circuit files

Statements that we wish to challenge

Through this audit, we wish to challenge the following statements:

  1. MACI exhibits collusion resistance
    • No one except a trusted coordinator should be certain of the validity of a vote, reducing the effectiveness of bribery
  2. MACI exhibits receipt-freeness
    • No voter may prove (besides to the coordinator) which way they voted
  3. MACI provides privacy
    • No one except a trusted coordinator should be able to decrypt a vote
  4. MACI is uncensorable:
    • No one (not even the trusted coordinator) should be able to censor a vote
  5. MACI provides unforgeability
    • Only the owner of a user's private key may cast a vote tied to its corresponding public key
  6. MACI provides non-repudiation
    • No one may modify or delete a vote after it is cast, although a user may cast another vote to nullify it
  7. Correct execution
    • No one (not even the trusted coordinator) should be able to produce a false tally of votes

1. Cryptographic primitives

Elliptic Curve Cryptography

MACI uses the Baby Jubjub Elliptic Curve as defined in this paper by Whitehat, Baylina, and Bellés.

1.1. The Baby Jubjub curve

Following the Baby Jubjub paper, we define the scalar field \(p\) as such:

p=21888242871839275222246405745257275088548364400416034343698204186575808495617p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

The field Fp\mathbb{F}_p is the finite field with modulo pp.

The generator point of Baby Jubjub GG is:

995203441582195749578291179787384436505546430278305826713579947235728471134,
5472060717959818805561601436314318772137091100104008585924551046643952123905

1.2. Private key generation

A private key is a random integer in the field Fp\mathbb{F}_p.

MACI uses the Node.js crypto.randomBytes(32) function to generate a cryptographically strong pseudorandom 32-byte value, as well as an algorithm to prevent modulo bias. In pseudocode this is expressed as:

lim = 2 ** 256
min = lim - p
rand = null
while true:
rand = BigInt(crypto.getRandomBytes(32))
if rand >= min:
break

privKey = rand % p

1.3. Private key formatting

The following procedures require that a private key be formatted into a scalar that can be multiplied with a point on the Baby Jubjub curve.

  1. Public key generation
  2. ECDH shared key generation

The algorithm to do so is as such:

  1. Hash the private key using blake512\mathsf{blake512} as such: h1=blake512(s)h_1 = \mathsf{blake512}(s)
  2. Take the lowest 32 bytes of h1h_1 as a buffer and prune it to derive h2h_2. To prune the buffer, we: 2.1. Clear the lowest three bits of the 0th byte 2.2. Clear the highest bit of the 31st byte 2.3. Set the second-highest bit of the 31st byte to 1.
  3. Convert h2h_2 to its little-endian integer representation. We denote this as h3h_3
  4. Shift h3h_3 right by 3 bits to get the formatted private key h4h_4

1.4. Public key generation

A public key is a point on the Baby Jubjub curve. It is deterministically derived from a private key ss, the procedure to do so is almost identical to RFC8032.

  1. Format the private key [1.3]
  2. Multiply GG by 8 and multiply the resulting point by the formatted private key to derive the public key AA: B=8GB = 8 \cdot G A=Bh4A = B \cdot h_4

1.5. Digital signature generation

We use the Edwards-curve Digital Signature Algorithm (EdDSA) to sign messages. The code which implements signature generation and verification is iden3's implementation in the circomlib library.

Given a private key ss, its public key AA [1.4] and a message MFpM \in \mathbb{F}_p, we derive the signature R8,SR8, S as such:

  1. Hash the private key using blake512\mathsf{blake512} as such: h1=blake512(s)h_1 = \mathsf{blake512}(s)
  2. Format ss [1.3] to generate AA [1.4]
  3. Convert MM to a buffer in little-endian format, concatenate it with the 32nd to 64th bytes of h1h_1, and hash the result with blake512\mathsf{blake512}, and interpret the hash in little-endian format as a value rr in the field Fp\mathbb{F}_p
  4. Multiply rr with BB to get R8R8
  5. Hash R8R8, AA, and MM: hm=poseidon4([R8[0],R8[1],A[0],A[1],m])hm = \mathsf{poseidon_4}([R8[0], R8[1], A[0], A[1], m])
  6. Calculate S=hmh3+rS = hm \cdot h_3 + r
  7. The signature is R8,SR8, S

1.6. Digital signature verification

Given a message MM, a signature R8R8, SS, and a public key AA, we verify the signature in this manner:

  1. hm=poseidon4(R8[0],R8[1],A[0],A[1],M)hm = \mathsf{poseidon_4}(R8[0], R8[1], A[0], A[1], M)
  2. The signature is valid if the following are equal: 2.1. (G8)S(G \cdot 8) \cdot S 2.2. ((hm8)A)+R8((hm \cdot 8) \cdot A) + R8

Hash functions

1.7. Poseidon

We define poseidonn\mathsf{poseidon_n} as a hash function which accepts nn inputs and produces one output yy:

y=poseidonn([x1,x2,...,xn])y = \mathsf{poseidon_n}([x_1, x_2, ..., x_n])

where xi,yFpx_i, y \in \mathbb{F}_p.

We use the implementation provided by circomlib, which uses the S-box x5x^5 and the following RFR_F and RPR_P values:

nnttRFR_FRPR_P
23857
34856
45860
56860

We verified that circomlib's poseidonn\mathsf{poseidon_n} implementation matches the reference implementation using the procedure documented here.

1.8. SHA256

SHA256 is used to compress public inputs to a circuit into a single field element in Fp\mathbb{F}_p. This reduces zk-SNARK verification gas costs. SHA256 is defined in RFC6234. We use implementations in the EVM as well as ethers.js.

Symmetric encryption

1.9. Poseidon in DuplexSponge mode

We use the Poseidon permutation function in DuplexSponge mode to encrypt each command and its signature. This method is described by the authors of the Poseidon hash function here.

We refer to the encryption function which produces ciphertext CC as poseidonEncrypt(ks[0],ks[1],N,l,t[])\mathsf{poseidonEncrypt}(k_s[0], k_s[1], N, l, t[]) where:

  • ksk_s is the shared key, a point on the Baby Jubjub curve
  • NN is the nonce, which we hardcode to 0
  • ll is the length of the plaintext t[]t[]

At the time of writing, the Javascript and circom code for Poseidon encryption / decryption is in this fork of the original iden3 codebase.

poseidonDecrypt(ks[0],ks[1],N,l,C)\mathsf{poseidonDecrypt}(k_s[0], k_s[1], N, l, C) is the decryption function that reverses poseidonEncrypt\mathsf{poseidonEncrypt}.

Shared-key generation

1.10. Elliptic-curve Diffie–Hellman (ECDH)

As will be described below, each command [2.5] is encrypted with a key that only the coordinator and the user know. In order to securely generate this shared key, we use the ECDH algorithm.

The coordinator's public key cPkcPk is known to all. Their private key cSkcSk is secret.

When the user publishes a message (i.e. casts a vote), they generate an ephemeral keypair with private key eSkeSk and public key ePkePk.

The user generates the shared key kk using the coordinator's public key cPkcPk and the user's ephemeral private key eSkeSk.

The user encrypts the command and signature with kk to form a message [2.6].

The user sends their ephemeral public key ePkePk along with the ciphertext. The coordinator can recover the same shared key using their private key cSkcSk and the given ephemeral public key ePkePk.

To generate kk from cPkcPk and eSkeSk:

  1. Format eSkeSk [1.3]
  2. Multiply the point cPkcPk by the above result

Merkle trees

We use quinary Merkle trees (5 leaves per node) rather than binary Merkle trees (2 leaves per node) due to the gas and circuit constraints when using the Poseidon hash function.

1.10. Accumulator queue

When users sign up or publish messages, they invoke a smart contract function that enqueues a leaf into an accumulator queue (which we dub an AccQueue). This is a data structure which is akin to a quinary Merkle tree. When a user inserts a leaf into the AccQueue, the Merkle root of all the leaves is not yet updated. Rather, the leaf is either simply stored or the root of a subtree is updated.

The height of the subtree tst_s is less than the full height of the tree tdt_d. The coordinator must merge all the subtrees to compute the Merkle root of all the leaves, allowing users to save gas when they enqueue leaves.

It exposes the following interface:

  1. enqueue(leaf): Enqueues a leaf into a subtree
  2. mergeSubRoots(): Merge all subtree roots into the shortest possible Merkle tree to fit
  3. merge(): Calculate the Merkle root of all the leaves at height tdt_d

The AccQueue keeps track of levels\mathsf{levels} and indices\mathsf{indices} for the latest subtree. It also keeps track of a list of all the subtree roots.

An AccQueue which supports subtrees of depth dd has the following as mutable state:

State itemDescription
levels[33][4]\mathsf{levels[33][4]}Leaf/node values at each subtree level
indices[33]\mathsf{indices[33]}The next available leaf/node index per subtree level
subRootLevels[33][4]\mathsf{subRootLevels[33][4]}Leaf/node values for the tree formed by subroots as leaves
subRootIndices[33]\mathsf{subRootIndices[33]}The next available leaf/node index per subroot level
subRoots[]\mathsf{subRoots[]}All the roots of complete subtrees
numLeaves\mathsf{numLeaves}The number of enqueued leaves
1.10.1. Enqueuing a leaf

To enqueue a leaf ll in an AccQueue:

  1. For each nn in 0...(d+1)0...(d+1), either:
    • Store the leaf in levels[n][indices[n]]\mathsf{levels[n][indices[n]]} if indices[n]<5indices[n] < 5, and break from the loop, or
      • Compute poseidon5([levels[n][0],levels[n][1],levels[n][2],levels[n][3],l)\mathsf{poseidon_5}([levels[n][0], levels[n][1], levels[n][2], levels[n][3], l), clear all values of levels[n]levels[n], clear indices[n]indices[n], and continue the loop with the hash as ll
  2. Increment numLeaves\mathsf{numLeaves} by 1
  3. If numLeaves\mathsf{numLeaves} is a multiple of 5ts5^{t_s}:
    • Append levels[ts][0]\mathsf{levels}[t_s][0] to subRootssubRoots
    • Clear levels[ts]\mathsf{levels}[t_s]
    • Clear indices\mathsf{indices}

Effectively, four out of five times it is invoked, an enqueue operation may or may not require the contract to perform a hash function. When it does, only up to tdt_d required number of hashes need to be computed.

1.10.2. Merging subroots

Before computing the main Merkle root, it is necessary to compute the smallSRTroot (the smallest subroot tree root). This is the Merkle root of a tree which is small enough to fit all the subroots, it uses a similar mechanism to enqueuing leaves [1.10.2].

The AccQueue.sol contract provides the mergeSubRoots(uint256 _numSrQueueOps) function which allows the coordinator to specify the number of queue operations to execute. The entire tree may be merged in a single transaction, or it may not. Multiple calls to mergeSubRoots may be required due to the block gas limit.

1.10.3. Computing main root

A similar operation to [1.10.2] and [1.10.3] is used to derive the main Merkle root (with depth tdt_d).

1.11. Groups on the alt_bn128 elliptic curve

We refer to the G1G_1 and G2G_2 cyclic groups as defined in EIP-197.

2. Domain objects

2.1. Verifying key

A verifying key vkvk is comprised of the following elements:

  1. α\alpha, a point in the curve on which G1G_1 is defined
  2. β\beta, a point in the curve on which G2G_2 is defined
  3. γ\gamma, a point in the curve on which G2G_2 is defined
  4. δ\delta, a point in the curve on which G2G_2 is defined
  5. ic[]ic[], a list of points in the curve on which G1G_1 is defined

A verifying key is used to validate a zk-SNARK proof. Each unique permutation of parameters to a particular circuit has a different verifying key.

2.2. Private key

A private key kk represents a participant's ability to broadcast or decrypt messages under a unique identity and generation of a shared key [1.9], it translates to a scalar point on the Baby Jubjub elliptical curve. To avoid confusion with Ethereum's ECDSA encryption, MACI requires serialisation bound with the prefix macisk.

2.2.1. Serialisation

To represent kk as a serialised private key, it is converted into big-endian hexadecimal format (lowercase; using the Node.js BigInt.toString(16) function) and concatenated with the prefix, no padding is applied during this process.

For example, the following private key in decimal format:

37851825598381891092793460603970297192082505330501908308470771672722312640613785182559838189109279346060397029719208250533050190830847077167272231264061

is serialised as:

macisk.85e56605303139aca49355df30d94f225788892ec71a5cfdbe79266563d5f3d

2.2.2. Deserialisation

To revert a serialised key back to its unserialised form kk, the string is manipulated to isolate the hexadecimal value by removing the prefix (through the Node.js operation String.slice()) and is prepended 0x for conversion from hexadecimal back to its big-endian primitive.

2.3. Public key

A public key pp represents a users identity derived from kk and therefore is also a point on the Baby Jubjub curve. It too requires serialisation, but to clarify the contrast to private keys it is assigned the prefix macipk.

2.3.1. Serialisation

To get a serialised public key from public key coordinates, the variable uu is defined as public key's y-coordinate, a 32 bit buffer vv is created and iterated over each uninitialised byte to:

  1. assign the result of a bitwise AND (&) operation between values uu and 255255 to byte nn
  2. shift uu right by 8 bits (>>)

The result vv is a hexadecimal big-endian value which is prendend its prefix to declare it as a serialised key.

2.3.2. Deserialisation

To reverse the effects of serialisation and return the unpacked public key, we must remove the prefix (using the method defined in [2.2.2]) and convert back to a buffer from hexadecimal. A return variable yy is initialised and the buffer is then iterated over each byte to:

  1. shift uu left by the result of 88 multiplied by nn bits (<<)
  2. assign yy the result of addition between yy and uu

The result yy is the public key's y-coordinate, to then compute the x-coordinate we must look at the equation for the twisted Edwards elliptic curve (as defined in EIP-2494):

ax2+y2=1+dx2y2ax^2 + y^2 = 1 + dx^2y^2

solving for xx, results:

xx = dy2ay21\mathsf{\sqrt{\frac{dy^2 - a}{y^2 - 1}}}

2.4. Keypair

A keypair is a private key and its corresponding public key.

2.5. Command

A command represents an action that a user may take. Such as casting a vote in a poll or changing their public key if bribed. It is made up of the following parameters:

SymbolNameSizeDescription
cmicm_iState index50State leaf index where the signing key is located
cmpxcm_{p_{x}}Public key x-coordinate253If no change is necessary this parameter should reflect the current public key's x-coordinate
cmpycm_{p_{y}}Public key y-coordinate253If no change is necessary this parameter should reflect the current public key's y-coordinate
cmivcm_{i_{v}}Vote option index50Option state leaf index of preference to assign the vote for
cmwcm_wVoting weight50Voice credit balance allocation, this is an arbitrary value dependent on a user's available credits
cmncm_nNonce50State leaf's index of actions committed plus one
cmidcm_{id}Poll id50The poll's identifier to cast in regard to
cmscm_sSalt253An entropy value to inhibit brute force attacks

The parameters; cmicm_i, cmivcm_{i_{v}}, cmncm_n, cmwcm_w and cmidcm_{id} are packed into a singular 250 bit value pp, defined as the sum of bitwise right shifts from 0 to 250, incrementing by 50 for each parameter. This reduces gas expenditures when generating a poseidon4\mathsf{poseidon_{4}} hash of a command hcmh_{cm}, expressed as:

hcmh_{cm} = poseidon4([p,cmpx,cmpy,cms])\mathsf{poseidon_{4}([p, cm_{p_{x}}, cm_{p_{y}}, cm_s])}

2.5.1. Signing a command

To sign a command with a public key AA:

  1. Compute M=hcmM = h_{cm}
  2. Sign MM using EdDSA [1.5]
  3. The signature is R8,SR8, S

2.5.2. Verifying a signature

We use the method described in [1.6]

2.6. Message

A message represents an encrypted command. Given a shared key ksk_s derived using ECDH [1.10] and plaintext tt, we compute:

t=[p,cmpx,cmpy,cms,R8[0],R8[1],S]t = [p, cm_{p_{x}}, cm_{p_{y}}, cm_s, R8[0], R8[1], S]

MM = poseidonEncrypt(ks[0],ks[1],cmn,7,t)\mathsf{poseidonEncrypt}(k_s[0], k_s[1], cm_n, 7, t)

2.6.1. Decrypting a message

To decrypt a message using ksk_s is expressed as

[p,R8[0],R8[1],cms][p, R8[0], R8[1], cm_s] = poseidonDecrypt(M,ks[0],ks[1],cmn,7)\mathsf{poseidonDecrypt}(M, k_s[0], k_s[1], cm_n, 7)

To unpack pp to its original five parameters, it must be separated into 50 bit values from the parent 250 bit value. To extract 50 bits at byte nn, we:

  1. initialise 50 bits
  2. shift left by nn bits
  3. bitwise AND with pp
  4. shift right by nn bits

2.7. Ballot

A Ballot represents a particular user's votes in a poll, as well as their next valid nonce. It is akin to a voting slip, which belongs to only one voter and contains a list of their choices.

SymbolNameComments
bltvblt_{v}An array of vote weightsbltv[i]blt_{v[i]} refers to the vote weights assigned to vote option ii
bltnblt_nThe current nonceStarts from 0 and increments, so the first valid command must have nonce 1
bltdblt_dThe vote option tree depth

The hash bltblt is computed as such:

  1. Compute the Merkle root of bltvblt_v, arity 5, of a tree of depth bltdblt_d; let this value be bltrblt_r
  2. Compute poseidon2([bltn,bltr])\mathsf{poseidon_2}([blt_n, blt_r])

2.8. State leaf

A state leaf represents a user's participation declared through an identity (their public key) and information relevant to their ability or right to cast votes in a poll (their voice credit balance and the block timestamp at which they signed up).

We define a state leaf slsl as the poseidon4\mathsf{poseidon_4} hash of the following:

SymbolNameComments
slPxsl_{P_x}Public key's x-coordinate
slPysl_{P_y}Public key's y-coordinate
slvsl_{v}Voice credit balance
sltsl_{t}Block timestampIn Unix time (seconds since Jan 1 1970 UTC)

The hash slsl is computed as such:

sl=poseidon4([slAx,slAy,slv,slt])sl = \mathsf{poseidon_4}([sl_{A_x}, sl_{A_y}, sl_{v}, sl_{t}])

2.8.1. Blank state leaf

A blank state leaf slBsl_B has the following value:

67690069702050995205089487237184717246608671711222352707736005679250380087626769006970205099520508948723718471724660867171122235270773600567925038008762

This value is computed as such:

Abx=10457101036533406547632367118273992217979173478358440826365724437999023779287A_{b_x} = 10457101036533406547632367118273992217979173478358440826365724437999023779287 Aby=19824078218392094440610104313265183977899662750282163392862422243483260492317A_{b_y} = 19824078218392094440610104313265183977899662750282163392862422243483260492317 slB=poseidon4([Ab0,Ab1,0,0])sl_B = \mathsf{poseidon_4}([A_{b0}, A_{b1}, 0, 0])

The code to derive AbxA_{b_x} and AbyA_{b_y} is here. The function call required is pedersenHash.getBasePoint('blake', 0)

  1. Hash the string PedersenGenerator_00000000000000000000000000000000_00000000000000000000000000000000 with blake256\mathsf{blake_{256}}. In big-endian hexadecimal format, the hash should be 1b3ef77ef2cd620fd2358e69dd564f35556aad552fdd7f06b777bd3a1d697160
  2. Set the 255th bit to 0. The result should be 1b3ef77ef2cd620fd2358e69dd564f35556aad552fdd7f06b777bd3a1d697120
  3. Use the method to convert a buffer to a point on the BabyJub curve described in [2.3.2]
  4. Multiply the point by 8. The result is the point with x-value AbxA_{b_x} and y-value AbyA_{b_y}

Given the elliptic curve discrete logarithm problem, we assume that no-one knows the private key sFps \in \mathbb{F}_p and by using the public key generation procedure in [1.4], we can derive AbxA_{b_x} and AbyA_{b_y}. Furthermore, the string above (PedersenGenerator...) acts as a nothing-up-my-sleeve value.

3. Higher-level concepts

3.1. Actors

There is a coordinator and one or more users.

Coordinator

The coordinator's public key is cPkcPk and their private key is cSkcSk.

User

A user's ephemeral public key is ePkePk and their ephemeral private key is eSkeSk.

3.2. How MACI prevents collusion

In governing systems, collusion can be described as the ability to distort any ballot through acts of influence, most often witnessed as bribery. Such arrangements require the bribee to vote in a manner requested by the briber, and for the former to provide proof (such as the transaction hash of a vote) to receive compensation (e.g. a monetary incentive) for their compliance.

MACI provides collusion-resistance assuming that:

  • it uses an identity system which is sybil-resistant
  • the coordinator is honest

That said, even if the coordinator is dishonest, they can neither tamper nor censor with its execution.

In MACI, the contents of a vote can only be decrypted by the coordinator. Moreover, the validity of a vote cannot be proven, as participants can revoke past actions through key-changes. Therefore, inhibiting the adversary in validating the fulfillment of such agreements.

To clarify how this works, consider the following situation between Alice and Eve involving a vote option A:

  1. Alice registers her identity during the sign up period, in preparation for the upcoming poll
  2. The sign up period ends and the voting period begins, Eve bribes Alice to oppose option A
  3. Alice casts a message for option A, in which she simultaneously:
    • Votes in opposition of A
    • Changes her keypair by submitting a new public key
  4. Eve is uncertain whether Alice has voted for her preference due to the secrecy of the message, regardless she assumes confirmation upon receiving the transaction hash
  5. Alice broadcasts a message from the new keypair registered in step 3 and casts a vote in support of poll A in turn, voiding her initial vote in opposition

Eve is doubtful whether her request was actually satisfied and is unaware of Alice casting a new vote to void the first, she decides not to compensate Alice because of the uncertainty surrounding her compliance.

3.3. Gatekeeper contract

The gatekeeper contract is an abstraction of logic that any deployment of MACI can modify. It is a way to whitelist signups to the system. For example, a custom gatekeeper contract may only allow addresses that own a certain ERC721 token for registration.

3.4. Initial voice credit proxy

The voice credit contract is another abstraction of logic that any deployment can configure at preference. It is a mechanism to define or admit voting power among participants based on, for instance, one's token balances. MACI only supports 2322^{32} (unit256) values for voice credit balances.

3.5. Verifying key registry

In MACI there are two zkSNARK circuits each ensuring:

  • the correct registration of messages to the state tree
  • the correct execution of the tallying of votes

Each of these circuits involves ownership of an independent verifying key to validate each when successfully executed, these are generated during the trusted setup and are initialised to the registry for generating proofs.

3.6. State

The state tree

Each leaf of the state tree encodes a participant's identity (public key) and the Unix timestamp at which they signed up. It has an arity of 5 and its depth is hardcoded to 10.

The default leaf value is the hash of a blank state leaf [2.8.1], insertions begin at index 1. Leaf 0 is reserved to inhibit a denial-of-service attack as explained below in [6.1].

The ballot tree (per poll)

Each leaf within the ballot trees stores a participant's vote within a poll, it shares the same arity and depth as the state tree. It also has index 0 reserved for a blank leaf following the same basis.

The message tree (per poll)

Each leaf within the message tree correlates to a command cast from participants within a poll, it too like the state tree has a default nothing-up-my-sleeve value at leaf zero. Except it is a Keccak256 hash of the string "Maci" modulo the SNARK field size pp [1.1].

3.7. System flow

When a user signs up

Registration is initiated by fulfilling the requirements specified in the gatekeeper contract and calling the signUp() method in the MACI contract. This enqueues adding a new leaf to the state tree for it to be merged by the coordinator once appropriate.

When a user publishes a message

Publishing messages requires users to encrypt a command using a shared key generated using ECDH [1.10] and submitting the ciphertext through the publishMessage() function. The message is then queued for processing by the co-ordinator once published.

When the coordinator merges the state queue

To subsidise gas costs for users, registration does not require the state root to be updated at its full depth, which would incur a gas cost linear to the depth. Rather, the use of the Accumulator Queue system described in [1.10] enqueues leaves. As such, the coordinator must compute the state tree root after the voting period is over and before they process messages.

Which first requires the merging of subroots [1.10.1], this creates the shortest possible tree that contains all the state leaves. Which may or may not require multiple transactions (in the form of batches) due to the restriction of the block gas limit. Once all the subroots have been computed they are merged [1.10.2] to compute the state root at its full depth.

After merging, the state-ballot commitment hash currentSbCommitment is initialised, which is a poseidon3\mathsf{poseidon_{3}} representation of the state's Merkle root, the ballot's Merkle root and a salt. At initialisation the Merkle roots are equal to the trees at full depth.

When the coordinator merges the message queue

The process of merging queues are the same in both the message and state trees.

When the coordinator processes the messages

As large zk-SNARK circuits take up a lot of disk space and require a large amount of resources to compile, it is not feasible to prove the correctness of message processing for all messages in a single proof. Rather, we process messages in batches. With each batch of messages at a particular index, the coordinator proves, using a zk-SNARK proof, intermediate currentSbCommitment values for subroots at a relative depth. The authenticity of this statement is confirmed using the registry's processing verifying key. The outcome of processing all batches, which must occur in consecutive order, is the same as if all the messages were processed in one go.

When the coordinator tallies the votes

To index tallying of votes in a poll, a tally commitment hash tallyCommitment is recorded which conforms similarly to the state-ballot commitment hash. The coordinator submits a new commitment hash and it's relative proof to tally the votes, which requires the verifying tallying key (queried from the registry) and the public input hash to validate the claim. Which is a SHA256 representation of the following parameters:

  • a packed value of; the number of signups, batch start index and batch size (packedVals [6.2])
  • the state-ballot commitment hash
  • the current tally commitment hash
  • the new tally commitment hash

The proof is then verified (see below) and the tally commitment hash is updated with the new value, this process is continued through iteration of the batch index until all pending votes have been tallied.

When a 3rd party verifies the tally

Any 3rd party contract may verify a leaf in tallyCommitment on-chain using a combination of Merkle proofs and hashing. Client developers should implement these functions as needed. We do not implement these functions in MACI to minimise contract size.

4. Command-line interface

Applications that use MACI are likely to be run in the browser. Users who sign up and vote can do so via web3 interactions. Only the coordinator needs to run scripts to deploy MACI, set verifying keys, deploy Polls, merge trees, process messages, and tally votes.

To make these processes easy to use, we provide command-line interface tools.

The integration tests and shell scripts in the cli directory provide examples of the order in which to execute them.

CommandDescriptionNotes
genMaciPubkeyGenerate a MACI public key from a private keyOnly the coordinator needs to run this, as users should generate their keys in the browser and should be automated by the client application
genMaciKeypairGenerates a MACI private key and public keyOnly the coordinator needs to run this, as users should generate their keys in the browser and should be automated by the client application
deployVkRegistryDeploy the VkRegistry contractExecuted only the coordinator
setVerifyingKeysSet verifying keys to the VkRegistryExecuted only the coordinator
createDeploy a new instance of MACIExecuted only the coordinator
deployPollDeploy a new poll on a MACI instanceExecuted only the coordinator
signupSign up a userMainly for testing; as users are more likely to use the client application instead of the CLI
publishSubmit a message to a pollMainly for testing; as users are more likely to use the client application instead of the CLI
mergeMessagesMust be executed before generating proofsExecuted only the coordinator
mergeSignupsMust be executed before generating proofsExecuted only the coordinator
genProofsGenerate all message processing and vote tallying proofsExecuted only the coordinator
proveOnChainSubmit proofs to the PollProcessorAndTallyer contractExecuted only the coordinator

5. Ethereum contracts

5.1. MACI

FunctionPermissionsNotes
init(VkRegistry _vkRegistry, MessageAqFactory _messageAqFactory)Coordinator onlyInitialise factory, helper and registry contracts that share equal ownership
signUp(PubKey memory _pubKey, bytes memory _signUpGatekeeperData, bytes memory _initialVoiceCreditProxyData)Executable only during the sign-up period and after initialisationParticipant registration and voice credit assignment
mergeStateAqSubRoots(uint256 _numSrQueueOps, uint256 _pollId)Executable only by poll contract _pollId and after initialisationMerge queued state leaves to form the state tree subroots
mergeStateAq(uint256 _pollId)Executable only by poll contract _pollId and after initialisationMerge the state subroots to form the state root
getStateTreeRoot()Non-applicableQuery the state root
deployPoll(uint256 _duration, TreeDepths memory _treeDepths, PubKey memory _coordinatorPubKey)Executable only after initialisationCreate a new poll
getPoll(uint256 _pollId)Non-applicableQuery a poll address

5.2. Poll

FunctionPermissionsNotes
getDeployTimeAndDuration()Non-applicableQuery the deployment timestamp and duration
numSignUpsAndMessages()Non-applicableQuery the number of participants and messages cast
currentSbAndTallyCommitments()Non-applicableQuery the current state-ballot and tally commitments hashes
publishMessage(Message memory _message, PubKey memory _encPubKey)Executable only during the voting period and if the message limit has not been not metSubmit a message (whether valid or not) to the message queue
hashMessageAndEncPubKey(Message memory _message, PubKey memory _encPubKey)Non-applicableQuery a hash of a message and public key coordinates
mergeMaciStateAqSubRoots( uint256 _numSrQueueOps, uint256 _pollId)Executable only by the coordinator and after the voting periodMerge queued state leaves to form the state subroots
mergeMaciStateAq(uint256 _pollId)Executable only by the coordinator and after the voting periodMerge the state subroots to form the state root and initialise the state-ballot commitment hash
mergeMessageAqSubRoots(uint256 _numSrQueueOps)Executable only by the coordinator and after the voting periodMerge the queued message leaves to form the message tree subroots
mergeMessageAq()Executable only by the coordinator and after the voting periodMerge the message tree subroots to form the message tree root
batchEnqueueMessage(uint256 _messageSubRoot)Executable only by the coordinator and after the voting periodSubmit a batch of messages to the queue

5.3. PollFactory

FunctionPermissionsNotes
setMessageAqFactory(MessageAqFactory _messageAqFactory)Coordinator onlyInitialise the message factory contract
deploy(uint256 _duration, TreeDepths memory _treeDepths, BatchSizes memory _batchSizes, PubKey memory _coordinatorPubKey, VkRegistry _vkRegistry, IMACI _maci, address _pollOwner)Coordinator onlyCreate a new poll

5.4. VkRegistry

FunctionPermissionsNotes
isProcessVkSet(uint256 _sig)Non-applicableQuery whether a signature is valid for message processing
isTallyVkSet(uint256 _sig)Non-applicableQuery whether a signature valid for tallying votes
genProcessVkSig(uint256 _stateTreeDepth, uint256 _messageTreeDepth, uint256 _voteOptionTreeDepth, uint256 _messageBatchSize)Non-applicableGenerate a signature (used for verifying key mapping lookups) for message processing by compressing parameters into a singular value
genTallyVkSig(uint256 _stateTreeDepth, uint256 _intStateTreeDepth, uint256 _voteOptionTreeDepth)Non-applicableGenerate a signature (used for verifying key mapping lookups) for vote tallying by compressing parameters into a singular value
setVerifyingKeys( uint256 _stateTreeDepth, uint256 _intStateTreeDepth, uint256 _messageTreeDepth, uint256 _voteOptionTreeDepth, uint256 _messageBatchSize, VerifyingKey memory _processVk, VerifyingKey memory _tallyVk)Coordinator onlyInitialise verifying keys for processing and tallying to the contract alongside specifying each tree depth
hasProcessVk(uint256 _stateTreeDepth, uint256 _messageTreeDepth, uint256 _voteOptionTreeDepth, uint256 _messageBatchSize)Non-applicableQuery whether the signature of the parameters is valid for message processing
getProcessVkBySig(uint256 _sig)Non-applicableQuery a processing verifying key by providing a valid signature
getProcessVk(uint256 _stateTreeDepth, uint256 _messageTreeDepth, uint256 _voteOptionTreeDepth, uint256 _messageBatchSize)Non-applicableQuery a processing verifying key by providing parameters to generate a valid signature
hasTallyVk(uint256 _stateTreeDepth, uint256 _intStateTreeDepth, uint256 _voteOptionTreeDepth)Non-applicableQuery whether the signature of the parameters is valid for vote tallying
getTallyVkBySig(uint256 _sig)Non-applicableQuery a tallying verifying key by providing a valid signature
getTallyVk(uint256 _stateTreeDepth, uint256 _intStateTreeDepth, uint256 _voteOptionTreeDepth)Non-applicableQuery a tallying verifying key by providing parameters to generate a valid signature

5.5. PollProcessorAndTallyer

FunctionPermissionsNotes
sha256Hash(uint256[] memory array)Non-applicableHash an array of values (using SHA256) moduluo the snark field size
processMessages(Poll _poll, uint256 _newSbCommitment, uint256[8] memory _proof)Executable only by the coordinator and after the voting periodProcess state messages relative to a new state-ballot commitment given that the proof is valid
verifyProcessProof(Poll _poll, uint256 _currentMessageBatchIndex, uint256 _messageRoot, uint256 _currentSbCommitment, uint256 _newSbCommitment, uint256[8] memory _proof)Non-applicableQuery whether a message processing proof is valid
genProcessMessagesPublicInputHash(Poll _poll, uint256 _currentMessageBatchIndex, uint256 _messageRoot, uint256 _numSignUps, uint256 _currentSbCommitment, uint256 _newSbCommitment)Non-applicableHash of the coordinators public key, packedVals, current state-ballot commitment and message root
genProcessMessagesPackedVals( Poll _poll, uint256 _currentMessageBatchIndex, uint256 _numSignUps)Non-applicableGenerate a packed 250-bit value packedVals for message processing
genTallyVotesPackedVals( uint256 _numSignUps, uint256 _batchStartIndex, uint256 _tallyBatchSize)Non-applicableGenerate a packed 100-bit value packedVals for vote tallying
genTallyVotesPublicInputHash( uint256 _numSignUps, uint256 _batchStartIndex, uint256 _tallyBatchSize, uint256 _newTallyCommitment )Non-applicableHash of the current tally commitment, the new tally commitment, packedVals and the state-ballot commitment
tallyVotes(Poll _poll, uint256 _newTallyCommitment, uint256[8] memory _proof)Executable only by the coordinator and after the voting periodTally votes relative to a new tally commitment given that the proof is valid
verifyTallyProof(Poll _poll, uint256[8] memory _proof, uint256 _numSignUps, uint256 _batchStartIndex, uint256 _tallyBatchSize, uint256 _newTallyCommitment)Non-applicableQuery whether a vote tallying proof is valid

6. zk-SNARKs

The zk-SNARK circuits in MACI are written in the circom language. Proofs are Groth16 and are generated using the rapidsnark prover.

We use custom tools to simplify the process of writing circuits, testing them, and generating proving and verifying keys. These tools are not in scope of the audit but it is useful to know them.

circom-helper allows developers to test circom circuits quickly and easily. It compiles circuits and exposes a JSON-RPC API which allows developers to generate witnesses and access signal values without writing command-line glue scripts.

zkey-manager simplifies the process of zkey file management for circuits written in circom.

Please note that MACI requires the coordinator to generate proofs on an x86 machine (Intel / AMD) or VM. Other processors (e.g. ARM) are not supported.

6.1. Message processing circuit

The message processing circuit, defined in circuits/circom/processMessages.circom, allows the coordinator to prove that they have correctly applied each message in reverse order, in a consecutive batch of 5 ^ msgBatchDepth messages to the respective state leaf within the state tree.

Parameters

ParameterDescription
stateTreeDepthDepth of the state tree, this value must be equal to 10
msgTreeDepthDepth of the message tree, this must be the same value passed to the deployPoll() contract function of MACI.sol
msgBatchDepthDepth of a tree that exactly fits the number of messages in a batch, this must be the same value passed to the deployPoll() contract function of MACI.sol
voteOptionTreeDepthDepth of the vote option tree, this must be the same value passed to the deployPoll() contract function of MACI.sol

The state tree, message tree, and vote option trees all have an arity of 5. As such, it is possible to calculate the maximum number of signups, messages per poll, and vote options per poll.

Input signals

Input signalDescription
numSignUpsNumber of users that have completed the sign up
indexThe batch index of current message batch
pollEndTimestampThe Unix timestamp at which the poll ends
msgRootThe root of the message tree
msgsThe batch of messages as an array of arrays
msgSubrootPathElementsAs described below
coordinatorPublicKeyHashposeidon2([cPkx,cPky])\mathsf{poseidon_2}([cPk_x, cPk_y])
newSbCommitmentAs described below
coordPrivKeyThe coordinator's private key
batchEndIndexThe last batch index
encPubKeysThe public keys used to generate shared ECDH encryption keys to encrypt the messages
currentStateRootThe state root before the commands are applied
currentStateLeavesThe state leaves upon which messages are applied
currentStateLeavesPathElementsThe Merkle path to each incremental state root
currentSbCommitmentAs described below
currentSbSaltAs described below
newSbCommitmentAs described below
newSbSaltAs described below
currentBallotRootThe root of the ballot tree before messages are applied
currentBallotsThe ballots upon which ballots are applied
currentBallotsPathElementsThe Merkle path to each incremental ballot root
currentVoteWeightsThe existing vote weight for the vote option in the ballot which each command refers to
currentVoteWeightsPathElementsThe Merkle path from each vote weight to the vote option root in its ballot
currentSbCommitment and newSbCommitment

The currentSbCommitment is the poseidon3\mathsf{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 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 currentSbCommitment (that is, the state root, ballot root, and currentSbSalt)
  2. That maxVoteOptions <= (5 ^ voteOptionTreeDepth)
  3. That numSignUps <== (5 ^ stateTreeDepth)
  4. That coordinatorPublicKeyHash is a hash of public key that is correctly derived from coordPrivKey
  5. That each message in msgs exists in the message tree
  6. 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

How messages are decrypted and applied

The circuit uses Poseidon decryption [1.9] to decrypt each message. The shared key is derived using ECDH [1.10] and the nonce is always equal to a value of 0.

The procedure to apply a command to a state leaf and ballot leaf is as such:

  1. Check if the signature is valid [1.6]
  2. Check if the user has enough voice credits
    • To do so , we check if slv+(bltvcmiv)2(cmw)20sl_v + (blt_{v_{cm_{i_v}}})^{2} - (cm_{w})^2 \geq 0
  3. Check if the vote weight is less than 147946756881789319005730692170996259609 which is approximately p\sqrt p
    • This ensures that the square of the vote weight will not overflow pp
  4. Check if the nonce is valid
  5. Check if the state leaf index is valid
  6. Check if the timestamp is valid
  7. Check if the vote option index is valid.

If any of the above are invalid, the command is invalid.

If the command is valid:

  1. Verify that the state leaf at cmicm_i is a member of the state root
  2. Verify that the ballot leaf at cmicm_i is a member of the ballot root
  3. Update the state root by replacing the state leaf at cmicm_i:
    • Set slPxsl_{P_x} to cmPxcm_{P_x}
    • Set slPysl_{P_y} to cmPycm_{P_y}
    • Set slvsl_{v} to cmivcm_{i_v}
  4. Update the ballot root by replacing the ballot leaf at cmicm_i:
    • Set bltv[cmiv]blt_{v[cm_{i_v}]} to cmwcm_{w}, update bltvblt_v, and update bltblt [2.7]

If the command is invalid:

  1. Verify that the state leaf at index 0 is a member of the state root
  2. Verify that the ballot leaf at index 0 is a member of the ballot root

The state leaf at index 0 is a blank state leaf, and the ballot leaf at index 0 is a blank ballot leaf. It should be impossible to update the 0th state leaf or 0th ballot leaf. The reason that these blank leaves exist at index 0 is to prevent an attack where a user sets cmicm_i to the maximum possible value (5105^{10}), which would force the coordinator to have to compute the Merkle path of leaf 51015_{10} - 1. Which is would take such a long time that it would constitute a denial-of-service attack on the coordinator that prevents them from generating proofs in a reasonable time.

Order of message processing

Messages are applied in reverse order. This prevents an attack where a briber colludes with a user to sign up and then immediately change their key to the briber's, ceding control entirely. Rather, the user may render previous commands invalid even if said commands are key-change commands. For instance:

If messages are processed in last-in-first-out order
  1. User signs up with public key uu
  2. Briber tells user to change their key to bb, they comply
  3. Briber can now vote for anything they want using bb and their commands will be valid
  4. The user cannot change the key as they do not know the briber's private key
If messages are processed in first-in-first-out order
  1. User signs up with public key uu
  2. Briber tells user to change their key to bb, the nonce of this command is 2, the user complies
  3. Briber submits a vote, the nonce of this command is 1
  4. User changes their key to kk, the nonce of this command is 2
  5. User votes for a vote option using public key uu, the nonce of this command is 1

The commands at (3) and (2) are invalid because the commands at (5) and (4) are processed first. The command at (3) is invalid not only because the briber does not know the private key to kk, but also because the expected nonce is 3.

6.2. Ballot tallying circuit

After the coordinator processes all message batches, each ballot contains the votes per vote option. The next step is to tally each vote so as to produce the following results:

  1. Votes per vote option
  2. Total voice credits per vote option
  3. Total spent voice credits

As an illustration, consider the following Ballots for 5 uses. Assume that there are 5 vote options and all messages have already been processed.

[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[1, 1, 1, 1, 1]

The final tally should be:

  1. Votes per vote option: [3, 5, 7, 9, 11]
  2. Total voice credits per vote option: [3, 9, 19, 33, 26]
  3. Total spent voice credits: 66

The coordinator uses the ballot tallying circuit (tallyVotes.circom) to generate proofs that they have correctly computed the tally. As there are many ballots to tally, each proof only computes the tally for a batch of ballots. Each proof is chained to the previous one such that each proof is also a proof of knowledge of the preimage of the previous tally commitment.

Parameters

ParameterDescription
stateTreeDepthDepth of the state tree, this value must be equal to 10
intStateTreeDepthDepth of the intermediate state tree, 5 ** intStateTreeDepth is the batch size
voteOptionTreeDepthDepth of the vote option tree, this must be the same value passed to the deployPoll() contract function of MACI.sol

Input signals

Input signalDescription
numSignUpsThe number of users that signup
indexStart index of given batch
sbCommitmentAs described below
currentTallyCommitmentAs described below
newTallyCommitmentAs described below
stateRootThe root of the state tree after all messages have been applied
ballotRootThe root of the ballot tree after all messages have been applied
sbSaltThe salt used to produce sbCommitment
ballotsThe ballots in the batch being tallied
ballotPathElementsThe Merkle path to each ballot leaf
votesThe votes in each ballot cast per result
currentResultsThe current tally of votes per vote option
currentResultsRootSaltA random value
currentSpentVoiceCreditSubtotalThe subtotal of voice credits spent across all vote options
currentSpentVoiceCreditSubtotalSaltA random value
currentPerVOSpentVoiceCreditsThe voice credits spent on each vote option so far
currentPerVOSpentVoiceCreditsRootSaltA random value
newResultsRootSaltA random value
newPerVOSpentVoiceCreditsRootSaltA random value
newSpentVoiceCreditSubtotalSaltA random value
sbCommitment

The commitment to stateRoot, ballotRoot, and sbSalt:

poseidon3([stateRoot,ballotRoot,sbSalt])\mathsf{poseidon_3}([\mathsf{stateRoot}, \mathsf{ballotRoot}, \mathsf{sbSalt}])

Proving preimage of sbCommitment is one out of the several steps required to prove that the votes were tallied correctly. By establishing that the coordinator knows ballotRoot, the coordinator can (using other parts of the circuit) prove that they know the preimage of the ballot leaves in the batch being tallied.

currentTallyCommitment and newTallyCommitment

A tally is represented by a tally commitment, which is the poseidon3\mathsf{poseidon_3} hash of:

  1. tcrtc_{r}: a commitment to the votes per option
    • This is the hash of the Merkle root rrr_r of the votes and a salt rsr_s, computed as poseidon2([rr,rs])\mathsf{poseidon_2}([r_r, r_s])
  2. tcttc_t: a commitment to the total spent voice credits
    • This is the hash of the total spent voice credits tct_c and a salt tst_s, computed as poseidon2([tc,ts])\mathsf{poseidon_2}([t_c, t_s])
  3. tcptc_p: a commitment to the spent voice credits per vote option
    • This is the hash of the Merkle root of the spent voice credits per vote option pvp_v and a salt psp_s, computed as poseidon2([pv,ps])\mathsf{poseidon_2}([p_v, p_s])

The tally commitment is computed as such:

poseidon3([tcr,tct,tcp])\mathsf{poseidon_3}([tc_r, tc_t, tc_p])

Statements that the circuit proves

  1. That the coordinator knows the preimage of sbCommitment (see above)
  2. That index is less than or equal to numSignUps
  3. That each ballot in ballots is in a member of the ballot tree with the Merkle root ballotRoot at indices batchStartIndex to batchStartIndex + (5 ** intStateTreeDepth)
  4. That each set of votes (votes[i]) has the Merkle root bltrblt_r whose value equals ballots[i][1]
  5. That the tally is valid, which is:
    • That the sum of votes per vote option is correct
    • That the sum of voice credits per vote option is correct
    • That the subtotal of the spent voice credits is correct