MACI Primitives
MACI primitives
This section provides a short introduction to the main primitives used by MACI.
Elliptic Curves
MACI uses the Baby Jubjub Elliptic Curve. The p
scalar field of choosing is:
$p=21888242871839275222246405745257275088548364400416034343698204186575808495617$
with generator:
$995203441582195749578291179787384436505546430278305826713579947235728471134$ $5472060717959818805561601436314318772137091100104008585924551046643952123905$
and within the finite field with modulo $p$.
Key Pairs
MACI uses Node.js's crypto.randomBytes(32)
function to generate a cryptographically strong pseudorandom 32byte value, as well as an algorithm to prevent modulo bias. In pseudocode this is:
lim = 2 ** 256
min = lim  p
rand = null
while true:
rand = BigInt(crypto.getRandomBytes(32))
if rand >= min:
break
privKey = rand % p
A public key is a point on the Baby Jubjub curve, which is deterministically derived from a private key s
.
Message Signing
To sign messages, MACI uses the Edwardscurve Digital Signature Algorithm (EdDSA), implemented by iden3.
Hash Functions
MACI uses the Poseidon hash function, which is proven to be very efficient in ZK applications. Poseidon accepts $n$ inputs and produces 1 output:
$y = poseidon_n([x_1, x_2, ..., x_n])$
Also, SHA256 is used to compress public inputs to a circuit into a single field element in the finite field $F$ mod $p$.
Message Encryption
In order to encrypt messages, MACI uses Poseidon in DuplexSponge mode. This provides an encryption function and a decryption function:
 $C$ as $poseidonEncrypt(k_s[0], k_s[1], N, l, t[])$
 $poseidonDecrypt(k_s[0], k_s[1], N, l, C)$
In more details,
 $k_s$ is the shared key, a point on the Baby Jubjub curve
 $N$ is the nonce, which we hardcode to 0
 $l$ is the length of the plaintext $t[]$
The implementation can be found here.
Shared Key Generation
The ECDH algorithm is used to generate a shared key, which is then used to encrypt each message. This allows to create messages which are only decryptable by the coordinator and the person sending the message.
In more details:

The coordinator's public key $cPk$ is known to all. Their private key $cSk$ is secret.

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

The user generates the shared key $k$ using the coordinator's public key $cPk$ and the user's ephemeral private key $eSk$.

The user encrypts the command and signature with $k$ to form a message.

The user sends their ephemeral public key $ePk$ along with the ciphertext. The coordinator can recover the same shared key using their private key $cSk$ and the given ephemeral public key $ePk$.
Merkle Trees
Rather than using Binary merkle trees, MACI uses Quinary merkle trees (5 leaves per node). This allows for more gas efficient computation using the Poseidon hash function.
Accumulator queue
This contract holds user signups and messages. When a leaf is inserted into the AccQueue
, the merkle root is not updated yet, instead the leaf is updated or the root of a subtree is recomputed. The smart contract exposes three functions:
enqueue(leaf)
: Enqueues a leaf into a subtree 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 $t_d$ required number of hashes need to be computedmergeSubRoots()
: Merge all subtree roots into the shortest possible Merkle tree to fit 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 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.merge()
: Calculate the Merkle root of all the leaves at height $d_t$
Domain Objects
Verifying Keys
A verifying key $vk$ is comprised of the following elements:
 $\alpha$, a point in the curve on which $G_1$ is defined
 $\beta$, a point in the curve on which $G_2$ is defined
 $\gamma$, a point in the curve on which $G_2$ is defined
 $\delta$, a point in the curve on which $G_2$ is defined
 $ic[]$, a list of points in the curve on which $G_1$ is defined
A verifying key is used to validate a zkSNARK proof. Each unique permutation of parameters to a particular circuit has a different verifying key.
Private Keys
MACI's private keys allow users to send and decrypt messages. This key translates to a scalar point on the Baby Jubjub elliptic curve. All keys are serialized with the prefix macisk
.
Public Keys
Public keys also translate to a point on the Baby Jubjub elliptic curve, and is derived from the private key $k$. These are serialized with the prefix macipk
.
Key Pair
A Key Pair is a private key and its corresponding public key.
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 

$cm_i$  State index  50  State leaf index where the signing key is located 
$cm_{p_{x}}$  Public key xcoordinate  253  If no change is necessary this parameter should reflect the current public key's xcoordinate 
$cm_{p_{y}}$  Public key ycoordinate  253  If no change is necessary this parameter should reflect the current public key's ycoordinate 
$cm_{i_{v}}$  Vote option index  50  Option state leaf index of preference to assign the vote for 
$cm_w$  Voting weight  50  Voice credit balance allocation, this is an arbitrary value dependent on a user's available credits 
$cm_n$  Nonce  50  State leaf's index of actions committed plus one 
$cm_{id}$  Poll id  50  The poll's identifier to cast in regard to 
$cm_s$  Salt  253  An entropy value to inhibit brute force attacks 
Message
A message is an encrypted command using the shared key $k_s$ between the voter and the coordinator. The plaintext $t$ is computed as such:
$t = [p, cm_{p_{x}}, cm_{p_{y}}, cm_s, R8[0], R8[1], S]$
While the message can be computed with the formula below:
$M$ = ${poseidonEncrypt}(k_s[0], k_s[1], cm_n, 7, t)$
Decrypting a message
To decrypt a message using $k_s$ is expressed as
$[p, R8[0], R8[1], cm_s]$ = ${poseidonDecrypt}(M, k_s[0], k_s[1], cm_n, 7)$
To unpack $p$ 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 $n$, we:
 initialise 50 bits
 shift left by $n$ bits
 bitwise AND with $p$
 shift right by $n$ bits
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 

$blt_{v}$  An array of vote weights  $blt_{v[i]}$ refers to the vote weights assigned to vote option $i$ 
$blt_n$  The current nonce  Starts from 0 and increments, so the first valid command must have nonce 1 
$blt_d$  The vote option tree depth 
The hash $blt$ is computed as such:
 Compute the Merkle root of $blt_v$, arity 5, of a tree of depth $blt_d$; let this value be $blt_r$
 Compute $poseidon_2([blt_n, blt_r])$
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 $sl$ as the $poseidon_4$ hash of the following:
Symbol  Name  Comments 

$sl_{P_x}$  Public key's xcoordinate  
$sl_{P_y}$  Public key's ycoordinate  
$sl_{v}$  Voice credit balance  
$sl_{t}$  Block timestamp  In Unix time (seconds since Jan 1 1970 UTC) 
The hash $sl$ is computed as such:
$sl = poseidon_4([sl_{A_x}, sl_{A_y}, sl_{v}, sl_{t}])$
Blank state leaf
A blank state leaf $sl_B$ has the following value:
$6769006970205099520508948723718471724660867171122235270773600567925038008762$
This value is computed as such:
$A_{b_x} = 10457101036533406547632367118273992217979173478358440826365724437999023779287$ $A_{b_y} = 19824078218392094440610104313265183977899662750282163392862422243483260492317$ $sl_B = poseidon_4([A_{b0}, A_{b1}, 0, 0])$
The code to derive $A_{b_x}$ and $A_{b_y}$ is here. The function call required is pedersenHash.getBasePoint('blake', 0)
 Hash the string
PedersenGenerator_00000000000000000000000000000000_00000000000000000000000000000000
with $blake_{256}$. In bigendian 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 xvalue $A_{b_x}$ and yvalue $A_{b_y}$
Given the elliptic curve discrete logarithm problem, we assume that no one knows the private key $s \in {F}_p$ and by using the public key generation procedure in [1.4], we can derive $A_{b_x}$ and $A_{b_y}$. Furthermore, the string above (PedersenGenerator...
) acts as a nothingupmysleeve value.