Semaphore v.4 in Noir

[NikitaMasych]

Distributed Lab can develop the semaphore v.4 in Noir within one week.

Noir Circuit

Have primitives:

• Secret to Public Point on Baby JubJub - noir-lang/eddsa
• Poseidon Hash - noir_stdlib

Need primitives:

• Merkle Root Computation with Poseidon - as Circom implementation which can be used for any binary Merkle Tree.

Draft:

use eddsa::eddsa_to_pub;
use std::{hash::poseidon::bn254::hash_2, field::bn254::assert_lt};

global MAX_DEPTH: u32 = 32;
global L: Field = 2736030358979909402780800718157159386076813972158567259200215660948447373041;

fn calculate_root<let N: u32>(leaf: Field, indices: Field, paths: [Field; N]) -> Field {
    let index_bits: [u1; N] = indices.to_be_bits();
    let mut current = leaf;

    for i in 0..paths.len() {
        current = if (index_bits[i] == 0) {
            hash_2([current, paths[i]])
        } else {
            hash_2([paths[i], current])
        };
    }

    current
}

fn main(
    secret: Field,
    indices: Field,
    paths: [Field; MAX_DEPTH],
    message: pub Field,
    scope: pub Field,
) -> pub (Field, Field) {
    assert_lt(secret, L);

    let pk = eddsa_to_pub(secret);
    let identity = hash_2([pk.0, pk.1]);
    let root = calculate_root(identity, indices, paths);
    let nullifier = hash_2([scope, secret]);

    let _ = message * message;

    (root, nullifier)
}

Proof TS package

TS Wrapper around circuit implementation.

Current npm package @semaphore-protocol/proof
works with SnarkJS; need to update it to support Barrettenberg.

Contracts

Solidity contract verifying circuit proofs.

SemaphoreVerifier.sol
verifies SnarkJS proofs; need to update it to support Barretenberg.

Team

Distributed Lab.

Previous Noir contributions:

1. Noir's HashMap - feat: Add HashMap to the stdlib #4242
2. PLUME - https://github.com/distributed-lab/noir-plume
3. Verkle Tries - https://github.com/distributed-lab/noir-verkle

Timeline and Deliverables

1 week:

• Noir Semaphore circuit with tests and benchmarks.
• Proof package updated to support Noir Circuit.
• Solitidy Contract encompassing needed TS changes and tests.
• Documentation in all engaged code.

Start Date

It should already be ready by the end of 14 March (some changes and answers to the questions below can affect deadlines but not dramatically).

Questions

1. Shall implementation focus on UltraHonk support?
2. Where shall code reside? (standalone fork of semaphore or morphed with upstream)
3. Shall implementation be compatible with Semaphore in Circom, or do you oversee some generic cryptography? (i.e. hashes, fields, etc.)