MACI v1.0 Specification
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:
Name | Commit |
---|---|
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:
- MACI exhibits collusion resistance
- No one except a trusted coordinator should be certain of the validity of a vote, reducing the effectiveness of bribery
- MACI exhibits receipt-freeness
- No voter may prove (besides to the coordinator) which way they voted
- MACI provides privacy
- No one except a trusted coordinator should be able to decrypt a vote
- MACI is uncensorable:
- No one (not even the trusted coordinator) should be able to censor a vote
- MACI provides unforgeability
- Only the owner of a user's private key may cast a vote tied to its corresponding public key
- 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
- 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:
The field is the finite field with modulo .
The generator point of Baby Jubjub is:
995203441582195749578291179787384436505546430278305826713579947235728471134,
5472060717959818805561601436314318772137091100104008585924551046643952123905
1.2. Private key generation
A private key is a random integer in the field .
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.
- Public key generation
- ECDH shared key generation
The algorithm to do so is as such:
- Hash the private key using as such:
- Take the lowest 32 bytes of as a buffer and prune it to derive . 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
. - Convert to its little-endian integer representation. We denote this as
- Shift right by 3 bits to get the formatted private key
1.4. Public key generation
A public key is a point on the Baby Jubjub curve. It is deterministically derived from a private key , the procedure to do so is almost identical to RFC8032.
- Format the private key [1.3]
- Multiply by 8 and multiply the resulting point by the formatted private key to derive the public key :
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 , its public key [1.4] and a message , we derive the signature as such:
- Hash the private key using as such:
- Format [1.3] to generate [1.4]
- Convert to a buffer in little-endian format, concatenate it with the 32nd to 64th bytes of , and hash the result with , and interpret the hash in little-endian format as a value in the field
- Multiply with to get
- Hash , , and :
- Calculate
- The signature is
1.6. Digital signature verification
Given a message , a signature , , and a public key , we verify the signature in this manner:
- The signature is valid if the following are equal: 2.1. 2.2.
Hash functions
1.7. Poseidon
We define as a hash function which accepts inputs and produces one output :
where .
We use the implementation provided by circomlib
, which uses the S-box and the following and values:
2 | 3 | 8 | 57 |
3 | 4 | 8 | 56 |
4 | 5 | 8 | 60 |
5 | 6 | 8 | 60 |
We verified that circomlib
's 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 . 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 as where:
- is the shared key, a point on the Baby Jubjub curve
- is the nonce, which we hardcode to 0
- is the length of the plaintext
At the time of writing, the Javascript and circom code for Poseidon encryption / decryption is in this fork of the original iden3 codebase.
is the decryption function that reverses .
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 is known to all. Their private key is secret.
When the user publishes a message (i.e. casts a vote), they generate an ephemeral keypair with private key and public key .
The user generates the shared key using the coordinator's public key and the user's ephemeral private key .
The user encrypts the command and signature with to form a message [2.6].
The user sends their ephemeral public key along with the ciphertext. The coordinator can recover the same shared key using their private key and the given ephemeral public key .
To generate from and :
- Format [1.3]
- Multiply the point 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 is less than the full height of the tree . 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:
enqueue(leaf)
: Enqueues a leaf into a subtreemergeSubRoots()
: Merge all subtree roots into the shortest possible Merkle tree to fitmerge()
: Calculate the Merkle root of all the leaves at height
The AccQueue keeps track of and for the latest subtree. It also keeps track of a list of all the subtree roots.
An AccQueue which supports subtrees of depth has the following as mutable state:
State item | Description |
---|---|
Leaf/node values at each subtree level | |
The next available leaf/node index per subtree level | |
Leaf/node values for the tree formed by subroots as leaves | |
The next available leaf/node index per subroot level | |
All the roots of complete subtrees | |
The number of enqueued leaves |
1.10.1. Enqueuing a leaf
To enqueue a leaf in an AccQueue:
- For each in , either:
- Store the leaf in if , and break from the loop, or
- Compute , clear all values of , clear , and continue the loop with the hash as
- Store the leaf in if , and break from the loop, or
- Increment by 1
- If is a multiple of :
- Append to
- Clear
- Clear
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 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 ).
1.11. Groups on the alt_bn128 elliptic curve
We refer to the and cyclic groups as defined in EIP-197.
2. Domain objects
2.1. Verifying key
A verifying key is comprised of the following elements:
- , a point in the curve on which is defined
- , a point in the curve on which is defined
- , a point in the curve on which is defined
- , a point in the curve on which is defined
- , a list of points in the curve on which 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 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 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:
is serialised as:
macisk.85e56605303139aca49355df30d94f225788892ec71a5cfdbe79266563d5f3d
2.2.2. Deserialisation
To revert a serialised key back to its unserialised form , 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 represents a users identity derived from 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 is defined as public key's y-coordinate, a 32 bit buffer is created and iterated over each uninitialised byte to:
- assign the result of a bitwise
AND (&)
operation between values and to byte - shift right by 8 bits (
>>
)
The result 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 is initialised and the buffer is then iterated over each byte to:
- shift left by the result of multiplied by bits (
<<
) - assign the result of addition between and
The result 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
):
solving for , results:
=
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:
Symbol | Name | Size | Description |
---|---|---|---|
State index | 50 | State leaf index where the signing key is located | |
Public key x-coordinate | 253 | If no change is necessary this parameter should reflect the current public key's x-coordinate | |
Public key y-coordinate | 253 | If no change is necessary this parameter should reflect the current public key's y-coordinate | |
Vote option index | 50 | Option state leaf index of preference to assign the vote for | |
Voting weight | 50 | Voice credit balance allocation, this is an arbitrary value dependent on a user's available credits | |
Nonce | 50 | State leaf's index of actions committed plus one | |
Poll id | 50 | The poll's identifier to cast in regard to | |
Salt | 253 | An entropy value to inhibit brute force attacks |
The parameters; , , , and are packed into a singular 250 bit value , 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 hash of a command , expressed as:
=
2.5.1. Signing a command
To sign a command with a public key :
- Compute
- Sign using EdDSA [1.5]
- The signature is
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 derived using ECDH [1.10] and plaintext , we compute:
=
2.6.1. Decrypting a message
To decrypt a message using is expressed as
=
To unpack 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 , we:
- initialise 50 bits
- shift left by bits
- bitwise AND with
- shift right by 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.
Symbol | Name | Comments |
---|---|---|
An array of vote weights | refers to the vote weights assigned to vote option | |
The current nonce | Starts from 0 and increments, so the first valid command must have nonce 1 | |
The vote option tree depth |
The hash is computed as such:
- Compute the Merkle root of , arity 5, of a tree of depth ; let this value be
- Compute
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 as the hash of the following:
Symbol | Name | Comments |
---|---|---|
Public key's x-coordinate | ||
Public key's y-coordinate | ||
Voice credit balance | ||
Block timestamp | In Unix time (seconds since Jan 1 1970 UTC) |
The hash is computed as such:
2.8.1. Blank state leaf
A blank state leaf has the following value:
This value is computed as such:
The code to derive and is here. The function call required is pedersenHash.getBasePoint('blake', 0)
- Hash the string
PedersenGenerator_00000000000000000000000000000000_00000000000000000000000000000000
with . In big-endian hexadecimal format, the hash should be1b3ef77ef2cd620fd2358e69dd564f35556aad552fdd7f06b777bd3a1d697160
- Set the 255th bit to 0. The result should be
1b3ef77ef2cd620fd2358e69dd564f35556aad552fdd7f06b777bd3a1d697120
- Use the method to convert a buffer to a point on the BabyJub curve described in [2.3.2]
- Multiply the point by 8. The result is the point with x-value and y-value
Given the elliptic curve discrete logarithm problem, we assume that no-one knows the private key and by using the public key generation procedure in [1.4], we can derive and . 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 and their private key is .
User
A user's ephemeral public key is and their ephemeral private key is .
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:
- Alice registers her identity during the sign up period, in preparation for the upcoming poll
- The sign up period ends and the voting period begins, Eve bribes Alice to oppose option A
- 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
- 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
- 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 (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 [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 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.
Command | Description | Notes |
---|---|---|
genMaciPubkey | Generate a MACI public key from a private key | Only the coordinator needs to run this, as users should generate their keys in the browser and should be automated by the client application |
genMaciKeypair | Generates a MACI private key and public key | Only the coordinator needs to run this, as users should generate their keys in the browser and should be automated by the client application |
deployVkRegistry | Deploy the VkRegistry contract | Executed only the coordinator |
setVerifyingKeys | Set verifying keys to the VkRegistry | Executed only the coordinator |
create | Deploy a new instance of MACI | Executed only the coordinator |
deployPoll | Deploy a new poll on a MACI instance | Executed only the coordinator |
signup | Sign up a user | Mainly for testing; as users are more likely to use the client application instead of the CLI |
publish | Submit a message to a poll | Mainly for testing; as users are more likely to use the client application instead of the CLI |
mergeMessages | Must be executed before generating proofs | Executed only the coordinator |
mergeSignups | Must be executed before generating proofs | Executed only the coordinator |
genProofs | Generate all message processing and vote tallying proofs | Executed only the coordinator |
proveOnChain | Submit proofs to the PollProcessorAndTallyer contract | Executed only the coordinator |
5. Ethereum contracts
5.1. MACI
Function | Permissions | Notes |
---|---|---|
init(VkRegistry _vkRegistry, MessageAqFactory _messageAqFactory) | Coordinator only | Initialise 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 initialisation | Participant registration and voice credit assignment |
mergeStateAqSubRoots(uint256 _numSrQueueOps, uint256 _pollId) | Executable only by poll contract _pollId and after initialisation | Merge queued state leaves to form the state tree subroots |
mergeStateAq(uint256 _pollId) | Executable only by poll contract _pollId and after initialisation | Merge the state subroots to form the state root |
getStateAqRoot() | Non-applicable | Query the state root |
deployPoll(uint256 _duration, MaxValues memory _maxValues, TreeDepths memory _treeDepths, PubKey memory _coordinatorPubKey) | Executable only after initialisation | Create a new poll |
getPoll(uint256 _pollId) | Non-applicable | Query a poll address |
5.2. Poll
Function | Permissions | Notes |
---|---|---|
getDeployTimeAndDuration() | Non-applicable | Query the deployment timestamp and duration |
numSignUpsAndMessages() | Non-applicable | Query the number of participants and messages cast |
currentSbAndTallyCommitments() | Non-applicable | Query 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 met | Submit a message (whether valid or not) to the message queue |
hashMessageAndEncPubKey(Message memory _message, PubKey memory _encPubKey) | Non-applicable | Query a hash of a message and public key coordinates |
mergeMaciStateAqSubRoots( uint256 _numSrQueueOps, uint256 _pollId) | Executable only by the coordinator and after the voting period | Merge queued state leaves to form the state subroots |
mergeMaciStateAq(uint256 _pollId) | Executable only by the coordinator and after the voting period | Merge 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 period | Merge the queued message leaves to form the message tree subroots |
mergeMessageAq() | Executable only by the coordinator and after the voting period | Merge the message tree subroots to form the message tree root |
batchEnqueueMessage(uint256 _messageSubRoot) | Executable only by the coordinator and after the voting period | Submit a batch of messages to the queue |