Skip to main content
Version: v2.0_alpha

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=21888242871839275222246405745257275088548364400416034343698204186575808495617p=21888242871839275222246405745257275088548364400416034343698204186575808495617

with generator:

995203441582195749578291179787384436505546430278305826713579947235728471134995203441582195749578291179787384436505546430278305826713579947235728471134 54720607179598188055616014363143187721370911001040085859245510466439521239055472060717959818805561601436314318772137091100104008585924551046643952123905

and within the finite field with modulo pp.

Key Pairs

MACI uses Node.js's 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:

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 Edwards-curve 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 nn inputs and produces 1 output:

y=poseidonn([x1,x2,...,xn])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 FF mod pp.

Message Encryption

In order to encrypt messages, MACI uses Poseidon in DuplexSponge mode. This provides an encryption function and a decryption function:

  • CC as poseidonEncrypt(ks[0],ks[1],N,l,t[])poseidonEncrypt(k_s[0], k_s[1], N, l, t[])
  • poseidonDecrypt(ks[0],ks[1],N,l,C)poseidonDecrypt(k_s[0], k_s[1], N, l, C)

In more details,

  • 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[]

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 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.

  • 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.

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 sign-ups 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 re-computed. 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 tdt_d required number of hashes need to be computed
  • mergeSubRoots(): 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 dtd_t

Domain Objects

Verifying Keys

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.

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 kk. 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:

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

Message

A message is an encrypted command using the shared key ksk_s between the voter and the coordinator. The plaintext tt is computed as such:

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]

While the message can be computed with the formula below:

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

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){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

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])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 slsl as the poseidon4poseidon_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 = poseidon_4([sl_{A_x}, sl_{A_y}, sl_{v}, sl_{t}])

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 = 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 blake256blake_{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 {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.