[NRG#3 Proposal] Semaphore v4 in Noir

[MBelegris]

Title

Nethermind Research

Summary

This proposal details implementing semaphore circuits in Noir, updating smart contracts to use the Noir on-chain verifier and proof package. We will document, benchmark, and test the implementation, releasing it under the MIT license.

The semaphore circuit consists of identity, group, and nullifier components. We will modularly build verification using a BabyJubJub public key generator, proof of membership validation, and nullifier computation. We will update Solidity verifiers, replacing semaphoreVerifier.sol with Noir’s Ultraplonk verifier.

Noir version: 1.0.0
Semaphore version: 4.9.0

Team

Michael Belegris: MSc in Information Security with a focus in cryptography and blockchain applications. Michael has worked on engineering research by implementing newly published zk-friendly hash functions for use on-chain, off-chain and in circuits as well as implementing attacks on mix-networks proving their insecurity. Additionally, Michael has helped in the teaching of block ciphers by building a learning tool for the AES and DES ciphers. This can all be seen on his GitHub at https://github.com/Mbelegris.

Timeline and Deliverables

The semaphore circuit is separated into 3 main categories: identity, group and the nullifier. We aim to build verification of each modularly: a BabyJubJub public key generator, proof of membership validation and finally the nullifier computation. Using the standard library’s embedded curves we aim to prove inclusion in the BabyJubJub field. Similarly, we will use the in-built Poseidon and merkle proof verifiers for the LIMT. We will provide circuit tests that can be run using noir test as well as clear documentation.

To update the packages, we will generate the solidity verifiers for the new circuits and replace calls to the circom verifiers to the Noir ones. Specifically with the proof package, we will create a new generate-proof-noir.ts that will similarly generate a noir proof using the noir export call and the noir_codegen package for typescript binding generation. For the smart contracts, we aim to generate the ultraplonk verifier, and replace the calls to the circom verifier to the noir verifier.

Phase 1: Scope Semaphore Library

We aim to decompose the semaphore library’s packages (circuits, contracts and proof) into its relevant functions. Here we will also survey Noir’s libraries for existing corresponding implementations to build upon.

• Decompose libraries into functions
• Analyse and determine best existing libraries to use and verify version compatibility. Should these not be available or up-to-date, we aim to implement them as part of their relevant phase.

Timeline: 1 week

Phase 2: Build circuits

Using the analysis and decomposition from phase 1 and the technical reference, we will implement the following circuit.

Public Values:

Merkle Root, Nullifier, scope

Private Values:

Merkle proof length, merkle proof siblings, merkle proof indices, secret

Relation To Prove:

• BabyJubJub EdDSA public key generator from secret input, as the noir-elgamal existing implementation is old we aim to bring it to the latest version of noir.
• Merkle proof verifier for the Lean IMT specification as the existing verifier in zk-kit noir does not include a lean IMT implementation.
• Nullifier and identity commitment using Noir’s poseidon implementation.

We aim to provide testing of each module as well as the entire relation similarly to the existing testing and check for compatibility in outputs. Additionally, we will benchmark the above for proving time, verification time and constraint number.

Timeline: 2 weeks

Phase 3: Update SDK and Smart Contract packages

Currently, there are 2 packages that would require updating to facilitate the change from Circom to Noir: proofs and contracts containing the proof generation logic and the on-chain logic.

1. Create generate-proof-noir.ts that will implement the proof generation logic using the new Noir circuits. This will be equivalent to the current generate-proof.ts which generates a proof using circom. We aim to export and create typescript bindings to do so.
2. Replace the current SemaphoreVerifier.sol with a Noir equivalent that implements the UltraPlonk verifier. The SemaphoreGroups.sol contract will point to the new verifier.

Tests verifying the validity of the proofs and erroneous conditions for both cases will be provided following the existing testing.

A gas cost estimate will also be provided as a benchmark together with proving times of the new Noir Semaphore proofs.

Timeline: 2 weeks.

Phase 4: End-to-End Testing and Benchmarks

Provide a full detailed testing of the entire Semaphore-noir implementation coupled with benchmarks assessing its performance.

The testing will cover:

• Compatibility with existing Semaphore implementation
• Unit tests
• Equivalent testing existing in the current semaphore-circom implementation

The benchmarks will cover:

• Proving/Verification time
• Constraint Number
• Proof size

We will compile this information into the final report, detailing the implementation and the benchmarks.

Timeline: 2 Week

Start Date

13 March 2025

Questions

1. What Noir version should we use?
2. What should be included in each report? How is the first report different to the second?