[Semaphore Circuit] Breakdown

Technical Tutorials
[Semaphore Circuit] Breakdown
none 0.0 0
1

Introduction

The Semaphore circuit is a foundational component of the Semaphore protocol, designed to ensure privacy, anonymity, and verifiability in decentralized applications. Semaphore enables users to prove membership in a group without revealing their identity, while also generating unique identifiers (nullifiers) to prevent double actions such as double-voting or double-spending. This tutorial provides a step-by-step explanation of the Semaphore circuit code, breaking it down into its key components and explaining their functions in detail.

By the end of this tutorial, you will gain a clear understanding of:

  • How the Semaphore circuit generates identity commitments using elliptic curve cryptography.
  • The role of Merkle trees in verifying membership.
  • How nullifiers are used to enforce single-use proofs within specific scopes.
  • Security mechanisms embedded within the circuit to protect against tampering and malleability.

Building the Circuit

For installation and project setup, check out Part1 of this section in the series.

Complete Circuit code

you can check out the semaphore repo here

pragma circom 2.1.5;

include "babyjub.circom";
include "poseidon.circom";
include "binary-merkle-root.circom";
include "comparators.circom";

// The Semaphore circuit can be divided into 3 main parts.
// The first part involves the generation of the Semaphore identity,
// i.e. the public key and its hash, which is called the commitment
// and is used as a public value.
// In the second part, it is verified whether or not the identity commitment is part
// of the Merkle tree, i.e. the Semaphore group. That is, a proof of membership is verified.
// The third part covers the generation of a nullifier, i.e. the hash of the scope of the proof
// and the secret used to derive the public key (secret scalar). The nullifier is used to prevent the same
// proof from being verified twice.
// The circuit lastly includes the message, which is an arbitrary anonymous value defined by
// the user, or the hash of that value.
template Semaphore(MAX_DEPTH) {
    // Input signals.
    // The input signals are all private except 'message' and 'scope'.
    // The secret is the scalar generated from the EdDSA private key.
    // Using the secret scalar instead of the private key allows this circuit
    // to skip steps 1, 2, 3 in the generation of the public key defined here:
    // https://www.rfc-editor.org/rfc/rfc8032#section-5.1.5, making the circuit
    // more efficient and simple.
    // See the Semaphore identity package to know more about how the identity is generated:
    // https://github.com/semaphore-protocol/semaphore/tree/main/packages/identity.
    signal input secret;
    signal input merkleProofLength, merkleProofIndices[MAX_DEPTH], merkleProofSiblings[MAX_DEPTH];
    signal input message;
    signal input scope;

    // Output signals.
    // The output signals are all public.
    signal output merkleRoot, nullifier;

    // The secret scalar must be in the prime subgroup order 'l'.
    var l = 2736030358979909402780800718157159386076813972158567259200215660948447373041;

    component isLessThan = LessThan(251);
    isLessThan.in <== [secret, l];
    isLessThan.out === 1;

    // Identity generation.
    // The circuit derives the EdDSA public key from a secret using
    // Baby Jubjub (https://eips.ethereum.org/EIPS/eip-2494),
    // which is basically nothing more than a point with two coordinates.
    // It then calculates the hash of the public key, which is used
    // as the commitment, i.e. the public value of the Semaphore identity.
    var Ax, Ay;
    (Ax, Ay) = BabyPbk()(secret);

    var identityCommitment = Poseidon(2)([Ax, Ay]);

    // Proof of membership verification.
    // The Merkle root passed as output must be equal to that calculated within
    // the circuit through the inputs of the Merkle proof.
    // See https://github.com/privacy-scaling-explorations/zk-kit/blob/main/packages/circuits/circom/binary-merkle-root.circom
    // to know more about how the 'BinaryMerkleRoot' template works.
    merkleRoot <== BinaryMerkleRoot(MAX_DEPTH)(identityCommitment, merkleProofLength, merkleProofIndices, merkleProofSiblings);

    // Nullifier generation.
    // The nullifier is a value that essentially identifies the proof generated in a specific scope
    // and by a specific identity, so that externally anyone can check if another proof with the same
    // nullifier has already been generated. This mechanism can be particularly useful in cases
    // where one wants to prevent double-spending or double-voting, for example.
    nullifier <== Poseidon(2)([scope, secret]);

    // The message is not really used within the circuit.
    // The square applied to it is a way to force Circom's compiler to add a constraint and
    // prevent its value from being changed by an attacker.
    // More information here: https://geometry.xyz/notebook/groth16-malleability.
    signal dummySquare <== message * message;
}

Code Walkthrough

1. File Inclusions

include "babyjub.circom";
include "poseidon.circom";
include "binary-merkle-root.circom";
include "comparators.circom";
  • babyjub.circom : Provides functionality for Baby Jubjub elliptic curve operations, which are used for generating public keys.
  • poseidon.circom : Includes the Poseidon hash function, optimized for zk-SNARK circuits.
  • binary-merkle-root.circom : Implements binary Merkle tree root calculation, necessary for membership proof verification.
  • comparators.circom : Contains comparators for numerical constraints, such as verifying the secret scalar.

These inclusions provide the building blocks for implementing the Semaphore protocol.

2. Circuit Template Definition

template Semaphore(MAX_DEPTH) {
  • template Semaphore(MAX_DEPTH) : Defines a reusable circuit template for Semaphore. The MAX_DEPTH parameter specifies the depth of the Merkle tree used to verify group membership.

3. Input Signals

signal input secret;
signal input merkleProofLength, merkleProofIndices[MAX_DEPTH], merkleProofSiblings[MAX_DEPTH];
signal input message;
signal input scope;
  • secret : A private scalar derived from the EdDSA private key. It is the core secret of the identity.
  • merkleProofLength : The length of the Merkle proof provided for membership verification.
  • merkleProofIndices : Indicates the path (left or right) at each level in the Merkle tree.
  • merkleProofSiblings : Contains the sibling hashes required to compute the Merkle root.
  • message : An arbitrary user-defined value, often hashed for anonymity.
  • scope : A public parameter defining the context of the proof, ensuring the nullifier’s uniqueness.

4. Output Signals

signal output merkleRoot, nullifier;
  • merkleRoot : The Merkle root calculated within the circuit. It must match the externally provided root for the proof to be valid.
  • nullifier : A hash value derived from the secret and scope. It ensures uniqueness and prevents double usage of the same proof.

5. Secret Scalar Validation

var l = 2736030358979909402780800718157159386076813972158567259200215660948447373041;

component isLessThan = LessThan(251);
isLessThan.in <== [secret, l];
isLessThan.out === 1;
  • Purpose: Ensures that the secret lies within the prime subgroup order l of the Baby Jubjub curve.
  • How it works:
    • LessThan(251) : Compares the secret with l to confirm it is valid.
    • Constraint isLessThan.out === 1 : The comparison must evaluate to true for the circuit to pass.

6. Identity Generation

var Ax, Ay;
(Ax, Ay) = BabyPbk()(secret);

var identityCommitment = Poseidon(2)([Ax, Ay]);
  • Purpose: Derives the public identity commitment from the secret scalar.
  • Steps:
    1. Public Key Derivation: BabyPbk() computes the elliptic curve public key (Ax, Ay) from the secret using the Baby Jubjub curve.
    2. Identity Commitment: Applies the Poseidon hash to the public key components [Ax, Ay] to generate the identity commitment, which acts as the unique public identifier.

7. Proof of Membership Verification

merkleRoot <== BinaryMerkleRoot(MAX_DEPTH)(identityCommitment, merkleProofLength, merkleProofIndices, merkleProofSiblings);
  • Purpose: Verifies that the identityCommitment belongs to the Semaphore group.
  • How it works:
    • BinaryMerkleRoot(MAX_DEPTH) : Reconstructs the Merkle root from the inputs.
    • Input Details:
      • identityCommitment : The leaf node being checked.
      • merkleProofLength : Defines the depth of the path.
      • merkleProofIndices : Specifies the directions at each level (0 for left, 1 for right).
      • merkleProofSiblings : Contains sibling hashes needed to compute the root.
    • Constraint: The calculated merkleRoot must match the externally provided root.

8. Nullifier Generation

nullifier <== Poseidon(2)([scope, secret]);
  • Purpose: Prevents double usage of the same proof within a given scope .
  • How it works:
    • Combines the scope and secret as inputs to the Poseidon hash function.
    • Produces a unique nullifier for the specific identity and scope combination.
    • Use Case: Ensures actions like voting or spending are one-time per user per scope.

9. Message Constraint

signal dummySquare <== message * message;
  • Purpose: Adds a constraint to message to prevent tampering.
  • Details:
    • Squaring the message introduces a dependency, making it part of the circuit’s constraints.
    • Protects against Groth16 malleability, where attackers might alter the proof after creation.

Summary

The Semaphore circuit performs four essential tasks:

  1. Validates that the secret is within a valid range.
  2. Generates an identity commitment using elliptic curve operations and hashing.
  3. Verifies the commitment’s inclusion in a Merkle tree (proof of membership).
  4. Computes a unique nullifier to prevent double usage of proofs.

This modular design ensures privacy, efficiency, and security, making Semaphore a robust protocol for anonymous, verifiable actions.

Conclusion

Congratulations! You’ve completed a hands-on implementation of zero-knowledge proofs. This process may seem complex initially, but as you create more advanced circuits, you’ll see how useful ZKPs can be for privacy-preserving computation.

We encourage you to continue your exploration of topics on zk proofs. If you’re interested in diving deeper, you can follow up on the pathway here Zero-Knowledge Proofs on the Celo Blockchain: A Comprehensive Tutorial Series - Pathways - Celo Academy

Resources

Circom docs
SnarkJS
0xparc Circom Workshop
Semaphore repo

About the author

I’m Jonathan Iheme, A full stack block-chain Developer from Nigeria. With a great passion for Zero Knowledge Technology.

linkedIn
Twitter