About

Semaphore is a zero-knowledge gadget which allows Ethereum users to prove their membership of a set which they had previously joined without revealing their original identity. At the same time, it allows users to signal their endorsement of an arbitrary string. It is designed to be a simple and generic privacy layer for Ethereum dApps. Use cases include private voting, whistleblowing, mixers, and anonymous authentication. Finally, it provides a simple built-in mechanism to prevent double-signalling or double-spending.

This gadget comprises of smart contracts and zero-knowledge components which work in tandem. The Semaphore smart contract handles state, permissions, and proof verification on-chain. The zero-knowledge components work off-chain to allow the user to generate proofs, which allow the smart contract to update its state if these proofs are valid.

Semaphore is designed for smart contract and dApp developers, not end users. Developers should abstract its features away in order to provide user-friendly privacy.

Try a simple demo here or read a high-level description of Semaphore here.

Basic features

In sum, Semaphore provides the ability to:

  1. Register an identity in a smart contract, and then:

  2. Broadcast a signal:

    • Anonymously prove that their identity is in the set of registered identities, and at the same time:

    • Publicly store an arbitrary string in the contract, if and only if that string is unique to the user and the contract’s current external nullifier, which is a unique value akin to a topic. This means that double-signalling the same message under the same external nullifier is not possible.

About external nullifiers

Think of an external nullifier as a voting booth where each user may only cast one vote. If they try to cast a second vote a the same booth, that vote is invalid.

An external nullifier is any 29-byte value. Semaphore always starts with one external nullifier, which is set upon contract deployment. The owner of the Semaphore contract may add more external nullifiers, deactivate, or reactivate existing ones.

The first time a particular user broadcasts a signal to an active external nullifier n, and if the user's proof of membership of the set of registered users is valid, the transaction will succeed. The second time she does so to the same n, however, her transaction will fail.

Additionally, all signals broadcast transactions to a deactivated external nullifier will fail.

Each client application must use the above features of Semaphore in a unique way to achieve its privacy goals. A mixer, for instance, would use one external nullifier as such:

SignalExternal nullifier
The hash of the recipient's address, relayer's address, and the relayer's feeThe mixer contract's address

This allows anonymous withdrawals of funds (via a transaction relayer, who is rewarded with a fee), and prevents double-spending as there is only one external nullifier.

An anonymous voting app would be configured differently:

SignalExternal nullifier
The hash of the respondent's answerThe hash of the question

This allows any user to vote with an arbitary response (e.g. yes, no, or maybe) to any question. The user, however, can only vote once per question.

About the code

This repository contains the code for Semaphore's contracts written in Soliidty, and zk-SNARK circuits written in circom. It also contains Typescript code to execute tests.

The code has been audited by ABDK Consulting. Their suggested security and efficiency fixes have been applied.

A multi-party computation to produce the zk-SNARK proving and verification keys for Semaphore will begin in the near future.

How it works

Inserting identities

An identity is comprised of the following information:

  1. An EdDSA private key. Note that it is not an Ethereum private key.
  2. An identity nullifier, whih is a random 32-byte value.
  3. An identity trapdoor, whih is a random 32-byte value.

An identity commitment is the Pedersen hash of:

  1. The public key associated with the identity's private key.
  2. The identity nullifier.
  3. The identity trapdoor.

To register an identity, the user must insert their identity commitment into Semaphore's identity tree. They can do this by calling the Semaphore contract's insertIdentity(uint256 _identityCommitment) function. See the API reference for more information.

Broadcasting signals

To broadcast a signal, the user must invoke this Semaphore contract function:

broadcastSignal(
    bytes memory _signal,
    uint256[8] memory _proof,
    uint256 _root,
    uint256 _nullifiersHash,
    uint232 _externalNullifier
)
  • _signal: the signal to broadcast.
  • _proof: a zk-SNARK proof (see below).
  • _root: The root of the identity tree, where the user's identity commitment is the last-inserted leaf.
  • _nullifiersHash: A uniquely derived hash of the external nullifier, user's identity nullifier, and the Merkle path index to their identity commitment. It ensures that a user cannot broadcast a signal with the same external nullifier more than once.
  • _externalNullifier: The external nullifier at which the signal is broadcast.

To zk-SNARK proof must satisfy the constraints created by Semaphore's zk-SNARK circuit as described below:

The zk-SNARK circuit

The semaphore-base.circom circuit helps to prove the following:

That the identity commitment exists in the Merkle tree

Private inputs:

  • identity_pk: the user's EdDSA public key
  • identity_nullifier: a random 32-byte value which the user should save
  • identity_trapdoor: a random 32-byte value which the user should save
  • identity_path_elements: the values along the Merkle path to the user's identity commitment
  • identity_path_index[n_levels]: the direction (left/right) per tree level corresponding to the Merkle path to the user's identity commitment

Public inputs:

  • root: The Merkle root of the identity tree

Procedure:

The circuit hashes the public key, identity nullifier, and identity trapdoor to generate an identity commitment. It then verifies the Merkle proof against the Merkle root and the identity commitment.

That the signal was only broadcasted once

Private inputs:

  • identity_nullifier: as above
  • identity_path_index: as above

Public inputs:

  • external_nullifier: the 29-byte external nullifier - see above
  • nullifiers_hash: the hash of the identity nullifier, external nullifier, and Merkle path index (identity_path_index)

Procedure:

The circuit hashes the given identity nullifier, external nullifier, and Merkle path index, and checks that it matches the given nullifiers hash. Additionally, the smart contract ensures that it has not previously seen this nullifiers hash. This way, double-signalling is impossible.

That the signal was truly broadcasted by the user who generated the proof

Private inputs:

  • identity_pk: as above
  • auth_sig_r: the r value of the signature of the signal
  • auth_sig_s: the s value of the signature of the signal

Public inputs:

  • signal_hash: the hash of the signal
  • external_nullifier: the 29-byte external nullifier - see above

Procedure:

The circuit hashes the signal hash and the external nullifier, and verifies this output against the given public key and signature. This ensures the authenticity of the signal and prevents front-running attacks.

Cryptographic primitives

Semaphore uses MiMC for the Merkle tree, Pedersen commmitments for the identity commitments, Blake2 for the nullifiers hash, and EdDSA for the signature.

MiMC is a relatively new hash function. We use the recommended MiMC construction from Albrecht et al, and there is a prize to break MiMC at http://mimchash.org which has not been claimed yet.

We have also implemented a version of Semaphore which uses the Poseidon hash function for the Merkle tree and EdDSA signature verification. This may have better security than MiMC, allows identity insertions to save about 20% gas, and roughly halves the proving time. Note, however, that the Poseidon-related circuits and EVM bytecode generator have not been audited, so use it with caution. To use it, checkout the feat/poseidon branch of this repository.

Quick start

Semaphore has been tested with Node 11.14.0 and Node 12 LTE. Use nvm to manage your Node version.

Clone this repository, install dependencies, and build the source code:

git clone git@github.com:kobigurk/semaphore.git && \
cd semaphore && \
npm i && \
npm run bootstrap && \
npm run build

Next, either download the compiled zk-SNARK circuit, proving key, and verification key (note that these keys are for testing purposes, and not for production, as there is no certainty that the toxic waste was securely discarded).

To download the circuit, proving key, and verification key, run:

# Start from the base directory

cd circuits && \
./circuits/scripts/download_snarks.sh

To generate the above files locally instead, run:

# Start from the base directory

cd circuits && \
./circuits/scripts/build_snarks.sh

This process should take about 45 minutes.

Build the Solidity contracts (you need solc v 0.5.12 installed in your $PATH):

# Start from the base directory

cd contracts && \
npm run compileSol

Run tests while still in the contracts/ directory:

# The first command tests the Merkle tree contract and the second
# tests the Semaphore contract

npm run test-semaphore && \ 
npm run test-mt

Usage

The Semaphore contract forms a base layer for other contracts to create applications that rely on anonymous signaling.

First, you should ensure that the proving key, verification key, and circuit file, which are static, be easily available to your users. These may be hosted in a CDN or bundled with your application code.

The Semaphore team has not performed a trusted setup yet, so trustworthy versions of these files are not available yet.

Untrusted versions of these files, however, may be obtained via the circuits/scripts/download_snarks.sh script.

Next, to have full flexibility over Semaphore's mechanisms, write a Client contract and set the owner of the Semaphore contract as the address of the Client contract. You may also write a Client contract which deploys a Semaphore contract in its constructor, or on the fly.

With the Client contract as the owner of the Semaphore contract, the Client contract may call owner-only Semaphore functions such as addExternalNullifier().

Add, deactivate, or reactivate external nullifiiers

These functions add, deactivate, and reactivate an external nullifier respectively. As each identity can only signal once to an external nullifier, and as a signal can only be successfully broadcasted to an active external nullifier, these functions enable use cases where it is necessary to have multiple external nullifiers or to activate and/or deactivate them.

Refer to the high-level explanation of Semaphore for more details.

Set broadcast permissioning

Note that Semaphore.broadcastSignal() is permissioned by default, so if you wish for anyone to be able to broadcast a signal, the owner of the Semaphore contract (either a Client contract or externally owned account) must first invoke setPermissioning(false).

See SemaphoreClient.sol for an example.

Insert identities

To generate an identity commitment, use the libsemaphore functions genIdentity() and genIdentityCommitment() Typescript (or Javascript) functions:

const identity: Identity = genIdentity()
const identityCommitment = genIdentityCommitment(identity)

Be sure to store identity somewhere safe. The serialiseIdentity() function can help with this:

const serialisedId: string = serialiseIdentity(identity: Identity)

It converts an Identity into a JSON string which looks like this:

["e82cc2b8654705e427df423c6300307a873a2e637028fab3163cf95b18bb172e","a02e517dfb3a4184adaa951d02bfe0fe092d1ee34438721d798db75b8db083","15c6540bf7bddb0616984fccda7e954a0fb5ea4679ac686509dc4bd7ba9c3b"]

To convert this string back into an Identity, use unSerialiseIdentity().

const id: Identity = unSerialiseIdentity(serialisedId)

Broadcast signals

First obtain the leaves of the identity tree (in sequence, up to the user's identity commitment, or more).

const leaves = <list of leaves>

Next, load the circuit from disk (or from a remote source):

const circuitPath = path.join(__dirname, '/path/to/circuit.json')
const cirDef = JSON.parse(fs.readFileSync(circuitPath).toString())
const circuit = genCircuit(cirDef)

Next, use libsemaphore's genWitness() helper function as such:

const result = await genWitness(
    signal,
    circuit,
    identity,
    leaves,
    num_levels,
    external_nullifier,
)
  • signal: a string which is the signal to broadcast.
  • circuit: the output of genCircuit() (see above).
  • identity: the user's identity as an Identity object.
  • leaves the list of leaves in the tree (see above).
  • num_levels: the depth of the Merkle tree.
  • external_nullifier: the external nullifier at which to broadcast.

Load the proving key from disk (or from a remote source):

const provingKeyPath = path.join(__dirname, '/path/to/proving_key.bin')
const provingKey: SnarkProvingKey = fs.readFileSync(provingKeyPath)

Generate the proof (this takes about 30-45 seconds on a modern laptop):

const proof = await genProof(result.witness, provingKey)

Generate the broadcastSignal() parameters:

const publicSignals = genPublicSignals(result.witness, circuit)
const params = genBroadcastSignalParams(result, proof, publicSignals)

Finally, invoke broadcastSignal() with the parameters:

const tx = await semaphoreClientContract.broadcastSignal(
    ethers.utils.toUtf8Bytes(signal),
    params.proof,
    params.root,
    params.nullifiersHash,
    external_nullifier,
    { gasLimit: 500000 },
)

Contract API

Constructor

Contract ABI:

constructor(uint8 _treeLevels, uint232 _firstExternalNullifier)

  • _treeLevels: The depth of the identity tree.
  • _firstExternalNullifier: The first identity nullifier to add.

The depth of the identity tree determines how many identity commitments may be added to this contract: 2 ^ _treeLevels. Once the tree is full, further insertions will fail with the revert reason IncrementalMerkleTree: tree is full.

The first external nullifier will be added as an external nullifier to the contract, and this external nullifier will be active once the deployment completes.

Add, deactivate, or reactivate external nullifiiers

Contract ABI:

addExternalNullifier(uint232 _externalNullifier)

Adds an external nullifier to the contract. Only the owner can do this. This external nullifier is active once it is added.

  • _externalNullifier: The new external nullifier to set.

deactivateExternalNullifier(uint232 _externalNullifier)

  • _externalNullifier: The existing external nullifier to deactivate.

Deactivate an external nullifier. The external nullifier must already be active for this function to work. Only the owner can do this.

reactivateExternalNullifier(uint232 _externalNullifier)

Reactivate an external nullifier. The external nullifier must already be inactive for this function to work. Only the owner can do this.

  • _externalNullifier: The deactivated external nullifier to reactivate.

Insert identities

Contract ABI:

function insertIdentity(uint256 _identityCommitment)

  • _identity_commitment: The user's identity commitment, which is the hash of their public key and their identity nullifier (a random 31-byte value). It should be the output of a Pedersen hash. It is the responsibility of the caller to verify this.

Off-chain libsemaphore helper functions:

Use genIdentity() to generate an Identity object, and genIdentityCommitment(identity: Identity) to generate the _identityCommitment value to pass to the contract.

To convert identity to a string and back, so that you can store it in a database or somewhere safe, use serialiseIdentity() and unSerialiseIdentity().

See the Usage section on inserting identities for more information.

Broadcast signals

Contract ABI:

broadcastSignal(
    bytes memory _signal,
    uint256[8] memory _proof,
    uint256 _root,
    uint256 _nullifiersHash,
    uint232 _externalNullifier
)
  • _signal: the signal to broadcast.
  • _proof: a zk-SNARK proof (see below).
  • _root: The root of the identity tree, where the user's identity commitment is the last-inserted leaf.
  • _nullifiersHash: A uniquely derived hash of the external nullifier, user's identity nullifier, and the Merkle path index to their identity commitment. It ensures that a user cannot broadcast a signal with the same external nullifier more than once.
  • _externalNullifier: The external nullifier at which the signal is broadcast.

Off-chain libsemaphore helper functions:

Use libsemaphore's genWitness(), genProof(), genPublicSignals() and finally genBroadcastSignalParams() to generate the parameters to the contract's broadcastSignal() function.

See the Usage section on broadcasting signals for more information.

libsemaphore

libsemaphore is a helper library for Semaphore written in Typescript. Any dApp written in Javascript or Typescript should use it as it provides useful abstractions over common tasks and objects, such as identities and proof generation.

Note that only v1.0.14 and above works with the Semaphore code in this repository. v0.0.x is compatible with the pre-audited Semaphore code.

Available types, interfaces, and functions

Types

SnarkBigInt

A big integer type compatible with the snarkjs library. Note that it is not advisable to mix variables of this type with bigNumbers or BigInts. Encapsulates snarkjs.bigInt.

EddsaPrivateKey

An EdDSA private key which should be 32 bytes long. Encapsulates a Buffer.

EddsaPublicKey

An EdDSA public key. Encapsulates an array of SnarkBigInts.

SnarkProvingKey

A proving key, which when used with a secret witness, generates a zk-SNARK proof about said witness. Encapsulates a Buffer.

SnarkVerifyingKey

A verifying key which when used with public inputs to a zk-SNARK and a SnarkProof, can prove the proof's validity. Encapsulates a Buffer.

SnarkWitness

The secret inputs to a zk-SNARK. Encapsulates an array of SnarkBigInts.

SnarkPublicSignals

The public inputs to a zk-SNARK. Encapsulates an array of SnarkBigInts.

Interfaces

EddsaKeyPair

Encapsulates an EddsaPublicKey and an EddsaPrivateKey.

interface EddsaKeyPair {
    pubKey: EddsaPublicKey,
    privKey: EddsaPrivateKey,
}

Identity

Encapsulates all information required to generate an identity commitment, and is crucial to creating SnarkProofs to broadcast signals.

interface Identity {
    keypair: EddsaKeyPair,
    identityNullifier: SnarkBigInt,
    identityTrapdoor: SnarkBigInt,
}

SnarkProof

Note that broadcastSignal() accepts a uint256[8] array for its _proof parameter. See genBroadcastSignalParams().

interface SnarkProof {
    pi_a: SnarkBigInt[]
    pi_b: SnarkBigInt[][]
    pi_c: SnarkBigInt[]
}

Functions

genPubKey(privKey: EddsaPrivateKey): EddsaPublicKey

Generates a public EdDSA key from a supplied private key. To generate a private key, use crypto.randomBytes(32) where crypto is the built-in Node or browser module.

genIdentity(): Identity

This is a convenience function to generate a fresh and random Identity. That is, the 32-byte private key for the EddsaKeyPair is randomly generated, as are the distinct 31-byte identity nullifier and the 31-byte identity trapdoor values.

serialiseIdentity(identity: Identity): string

Converts an Identity into a JSON string which looks like this:

["e82cc2b8654705e427df423c6300307a873a2e637028fab3163cf95b18bb172e","a02e517dfb3a4184adaa951d02bfe0fe092d1ee34438721d798db75b8db083","15c6540bf7bddb0616984fccda7e954a0fb5ea4679ac686509dc4bd7ba9c3b"]

You can also spell this function as serializeIdentity.

To convert this string back into an Identity, use unSerialiseIdentity().

unSerialiseIdentity(string: serialisedId): Identity

Converts the string output of serialiseIdentity() to an Identity.

You can also spell this function as unSerializeIdentity.

genIdentityCommitment(identity: Identity): SnarkBigInt

Generates an identity commitment, which is the hash of the public key, the identity nullifier, and the identity trapdoor.

async genProof(witness: SnarkWitness, provingKey: SnarkProvingKey): SnarkProof

Generates a SnarkProof, which can be sent to the Semaphore contract's broadcastSignal() function. It can also be verified off-chain using verifyProof() below.

genPublicSignals(witness: SnarkWitness, circuit: SnarkCircuit): SnarkPublicSignals

Extracts the public signals to be supplied to the contract or verifyProof().

verifyProof(verifyingKey: SnarkVerifyingKey, proof: SnarkProof, publicSignals: SnarkPublicSignals): boolean

Returns true if the given proof is valid, given the correct verifying key and public signals.

Returns false otherwise.

signMsg(privKey: EddsaPrivateKey, msg: SnarkBigInt): EdDSAMiMcSpongeSignature)

Encapsualtes circomlib.eddsa.signMiMCSponge to sign a message msg using private key privKey.

verifySignature(msg: SnarkBigInt, signature: EdDSAMiMcSpongeSignature, pubKey: EddsaPublicKey): boolean

Returns true if the cryptographic signature of the signed msg is from the private key associated with pubKey.

Returns false otherwise.

setupTree(levels: number, prefix: string): MerkleTree

Returns a Merkle tree created using semaphore-merkle-tree with the same number of levels which the Semaphore zk-SNARK circuit expects. This tree is also configured to use MimcSpongeHasher, which is also what the circuit expects.

levels sets the number of levels of the tree. A tree with 20 levels, for instance, supports up to 1048576 deposits.

genCircuit(circuitDefinition: any)

Returns a new snarkjs.Circuit(circuitDefinition). The circuitDefinition object should be the JSON.parsed result of the circom command which converts a .circom file to a .json file.

async genWitness(...)

This function has the following signature:

const genWitness = async (
    signal: string,
    circuit: SnarkCircuit,
    identity: Identity,
    idCommitments: SnarkBigInt[] | BigInt[] | ethers.utils.BigNumber[],
    treeDepth: number,
    externalNullifier: SnarkBigInt,
)
  • signal is the string you wish to broadcast.
  • circuit is the output of genCircuit().
  • identity is the Identity whose identity commitment you want to prove is in the set of registered identities.
  • idCommitments is an array of registered identity commmitments; i.e. the leaves of the tree.
  • treeDepth is the number of levels which the Merkle tree used has
  • externalNullifier is the current external nullifier

It returns an object as such:

  • witness: The witness to pass to genProof().
  • signal: The computed signal for Semaphore. This is the hash of the recipient's address, relayer's address, and fee.
  • signalHash: The hash of the computed signal.
  • msg: The hash of the external nullifier and the signal hash
  • signature: The signature on the above msg.
  • tree: The Merkle tree object after it has been updated with the identity commitment
  • identityPath: The Merkle path to the identity commmitment
  • identityPathIndex: The leaf index of the identity commitment
  • identityPathElements: The elements along the above Merkle path

Only witness is essential to generate the proof; the other data is only useful for debugging and additional off-chain checks, such as verifying the signature and the Merkle tree root.

formatForVerifierContract = (proof: SnarkProof, publicSignals: SnarkPublicSignals

Converts the data in proof and publicSignals to strings and rearranges elements of proof.pi_b so that snarkjs's verifier.sol will accept it. To be specific, it returns an object as such:

{
    a: [ proof.pi_a[0].toString(), proof.pi_a[1].toString() ],
    b: [ 
         [ proof.pi_b[0][1].toString(), proof.pi_b[0][0].toString() ],
         [ proof.pi_b[1][1].toString(), proof.pi_b[1][0].toString() ],
    ],
    c: [ proof.pi_c[0].toString(), proof.pi_c[1].toString() ],
    input: publicSignals.map((x) => x.toString()),
}

stringifyBigInts = (obj: any) => object

Encapsulates snarkjs.stringifyBigInts(). Makes it easy to convert SnarkProofs to JSON.

unstringifyBigInts = (obj: any) => object

Encapsulates snarkjs.unstringifyBigInts(). Makes it easy to convert JSON to SnarkProofs.

genExternalNullifier = (plaintext: string) => string

Each external nullifier must be at most 29 bytes large. This function keccak-256-hashes a given plaintext, takes the last 29 bytes, and pads it (from the start) with 0s, and returns the resulting hex string.

Multi-party trusted setup

The Semaphore authors will use the Perpetual Powers of Tau ceremony and a random beacon as phase 1 of the trusted setup.

More details about phase 2 will be released soon.

Security audit

The Ethereum Foundation and POA Network commissioned ABDK Consulting to audit the source code of Semaphore as well as relevant circuits in circomlib, which contains components which the Semaphore zk-SNARK uses.

All security and performance issues have been fixed. The full audit report will be available soon.

Credits

  • Barry WhiteHat
  • Chih Cheng Liang
  • Kobi Gurkan
  • Koh Wei Jie
  • Harry Roberts

Many thanks to:

  • Jordi Baylina / iden3
  • POA Network
  • PepperSec
  • Ethereum Foundation

Resources

To Mixers and Beyond: presenting Semaphore, a privacy gadget built on Ethereum - Koh Wei Jie

Privacy in Ethereum - Barry WhiteHat at the Taipei Ethereum Meetup

Snarks for mixing, signaling and scaling by - Barry WhiteHat at Devcon 4

Privacy in Ethereum - Barry WhiteHat at Devcon 5

A trustless Ethereum mixer using zero-knowledge signalling - Koh Wei Jie and Barry WhiteHat at Devcon 5

Hands-on Applications of Zero-Knowledge Signalling - Koh Wei Jie at Devcon 5