Overview

This is our progress update for NRG #3 to implement Semaphore in Noir. In this version, we add the Noir Semaphore Circuit along with an updated TypeScript SDK with respect to the Noir circuit. We also share statistics such as test coverage and benchmarks of the circuit in this report. In the end we compile a list of discoveries and hurdles we encountered and our plans for the final report.

Project progress

In the first month of the project, we've finalized the first 2 deliverables:

1. Semaphore circuits implementation in Noir
2. SDK functionality enhancements

Both deliverables include tests written in TypeScript, with the Noir circuit also featuring native tests. To facillitate the SDK functionality, we've forked and updated the snark-artifacts repo to add the necessary helper functionality and precompiled circuits.

We've initiated implementation of the verifier contract and will continue refining this component over the next month, as we detail further in the subsequent sections.

With the circuit and SDK complete, we began benchmarking to evaluate performance and identify areas for improvements. Benchmarking will remain a continuous effort throughout the next month as we assess whether we're able to make the library faster.

Links to relevant repositories:

• semaphore-noir
• snark-artifacts
• semaphore-noir-benchmarks

Statistics

Test coverage

Tests have been added for the new SDK functionality in generate-proof-noir and verify-proof-noir:

In addition, we've added tests for the Noir circuit in packages/circuits-noir, both in TypeScript and directly in Noir itself. There is, as far as we know, no test coverage tool for a Noir circuit, which is why it is not included in the table.

Benchmarks

For benchmarking we cloned the existing Semaphore benchmarking repo and updated the browser and node benchmarks accordingly. Those benchmark the Semaphore-Noir SDK functionality (generateNoirProof and verifyNoirProof). The repo also contains the gas estimates in a static json file.

Additionally, we have benchmarked the gate count directly on the Noir circuit with bb gates.

To get more precise insights on the Noir side, we plan to add benchmarking for witness generation, proving and verifying for the circuit, separately from the SDK.

Machine details: MacBook Pro, Intel Core i7 (6-core, 2.6 GHz), 32 GB RAM.

Node Benchmarks

Version details:

• @aztec/bb.js 0.82.2
• @noir-lang/noir_js 1.0.0-beta.3
• @noir-lang/noir_wasm 1.0.0-beta.3

Proof Generation

Proof Verification

Browser Benchmarks

Proof Generation

Gas estimates

Gate Count

Version details:

• nargo version = 1.0.0-beta.3
• bb 0.82.2

Discoveries and hurdles along the way

In this section, we provide more detail on several topics that we encountered along the way. Some were unexpected challenges, while others are improvements that have already been applied for performance.

Parameterizing the circuit in Noir vs Circom

In Circom, the Semaphore template is parameterized as follows (ref):

template Semaphore(MAX_DEPTH) { .. }

In Noir, we are using a hardcoded global that has to be overwritten to be adjusted (ref):

#![allow(unused)]
fn main() {
// This value can get updated by overwriting this line.
pub global MAX_DEPTH: u32 = 10;
}

From discussions in Discord with the Noir team, we concluded this would be the cleanest way for the time being. The Noir circuit is present in the semaphore-noir packages, but not used directly; instead, a set of precompiled circuits in the snark-artifacts repo is used or the user passes the compiled circuit themselves. In case of the user directly passing the Noir circuit, they would be able to set the value as desired, either by hardcoding it or by updating it via a script.

Another option suggested by the team is to create a workspace with different packages for the different depths. In the case of Semaphore where depth varies between 1 and 32 we felt this would be too verbose in comparison to the chosen approach.

For testing the Noir program in TypeScript, we use a simple replace function to adjust the global to the desired value.

For context; in Circom using a parameterized template generates a part of a circuit based on the passed value for the parameter, and this is composable within a larger circuit (repo reference).

UltraHonk proof generated by the Barretenberg JS doesn't match the proof data required by the Solidity verifier

The proof data is generated by the Barretenberg backend as:

let ProofData = UltraHonkBackend.generateProof(witness, { keccak: true })

It has 4 bytes of prepended data compared to the proof required by the Solidity verifier contract. We currently have to remove the first 4 bytes in ProofData before passing it to the verification contract. (Note: Based on the comments we saw on Discord, it seems like the issue is fixed in v0.82. Currently we are using v0.72.1. We will update the version and test it in the future versions.)

Verifier contract too large

Semaphore provides 32 verification keys for circuits of merkle tree depths 1 to 32. In the original contract, all keys are stored in a single bytes type, and the correct keys set are returned based on the input depth. However for UltraHonk, the verifier contract itself is very large and cannot include additional functions to select keys based on the depth; this exceeds the 24KB contract size limit set by the EVM (even when using the Solidity optimizer). Additionally, the verification keys for UltraHonk are also too large to store in a single contract.

Currently, our design is to split the Noir verifier into one main verifier contract and three external libraries ---- one for controlling verification keys based on depth, and two for storing the verification keys. At present, we store the necessary addresses in the main verifier contract and call them through delegatecall(). We plan to refactor the contracts to avoid using delegatecall and also to optimize for lower gas consumption.

Usage of multithreading to improve SDK benchmarks

To improve the performance of generating and verifying proofs with Barretenberg backend, we utilize the multithreading function built in the SDK:

new UltraHonkBackend(bytecode, { threads: nrThreads })

We updated the proving and verifying functions in the Semaphore SDK to accept an optional thread count parameter. In this way we leverage multithreading in both browser and node environments and have been able to improve benchmarking.

Improvement of Noir circuit

The Noir team immediately spotted some low hanging fruit for optimization in the following snippet of the circuit:

#![allow(unused)]
fn main() {
let index_bits: [u1; 32] = indexes.to_le_bits();
 let mut node = identityCommitment;
 for i in 0..MAX_DEPTH {
     if i < merkleProofLength {
         let sibling = hashPath[i];
         if index_bits[i] == 0 {
             node = poseidon([node, sibling]);
         } else {
             node = poseidon([sibling, node]);
         }
     }
 }
}

The proposed optimizations:

1. The array index_bits could actually be parameterised by MAX_DEPTH
2. Avoid expensive operation call in a conditional, in this case the poseidon hash, by lifting it out of the if else

#![allow(unused)]
fn main() {
let index_bits: [u1; MAX_DEPTH] = indexes.to_le_bits();
let mut node = identityCommitment;
for i in 0..MAX_DEPTH {
    if i < merkleProofLength {
        let sibling = hashPath[i];
        let (left, right) = if index_bits[i] == 0 {
            (node, sibling)
        } else {
            (sibling, node)
        };
        node = poseidon([left, right]);
    }
}
}

For MAX_DEPTH 10, this brought down the gate count from ~25k to ~16k.

Next steps

In the second and final month of this grant project, we'll be working on several tasks, following the initial proposal.

A major focus is to improve the verifier contract. We plan to do some refactoring to lower the gas usage and the deployment cost. We will also replace the delegatecall for security. The current version of the contract was generated for bb 0.72 and this will be upgraded to 0.82.2. Finally, the contracts will be deployed to Sepolia for testing.

With regard to the Noir circuit, we hope to uncover further optimization opportunities after the Noir team already shaved off a good amount of gates from the initial implementation. We also plan to expand benchmarking to include timings on proof generation and verification directly with bb instead of on the SDK. This will provide the Noir team a better foundation to assist us in analyzing and sharing suggestions for optimizing these numbers.

Of course, we hope developers will be eager to integrate Semaphore-Noir into their projects. To support this, we'll create a simple write-up to guide them throughout the process. For this, we plan to publish all necessary packages for easy usage.

Finally, we'll ensure that all code is reviewed and fixed, and we will deliver the final benchmarks and final report.