[NRG#3 Proposal] Semaphore v4 in Noir

[qpzm]

Summary

We propose implementing the Semaphore v4 proof system in Noir.

1. First, we will implement a Lean Incremental Merkle Tree in Noir that optimizes the Incremental Merkle Tree by eliminating placeholder hashing for empty sibling nodes during upward propagation.
2. Second, we will align the system with Semaphore v4 specifications by updating the identity schema from Poseidon to EdDSA, adapting the proof package to the updated membership proof scheme and generating an optimized Solidity verifier.
3. In the first week, we have developed a mvp repo with the semaphore circuit and the honk solidity verifier.

Team

MODORI is a blockchain-focused company offering comprehensive solutions—from development and consulting to investment—designed to help anyone launch and grow a successful blockchain venture in today's market. We offer two main products: Elyfi v2, a multi-tranche lending protocol, and waveX, a perpetual DEX on the Soneium chain.

Hyunmin Lee: @qpzm has been a solidity developer at MODORI since Nov 2021. During this time, he won 1st place in Secureum's 34th and 36th races, and conducted numerous solidity audits. As a zk-resident at Electisec, he contributed significant findings (2 high, 1 medium) in the Summa versionB developed with Halo2. He has also delivered technical presentations on STARK VM and Polynomial Commitment Schemes.

Donguk Seo: @donguks is the CTO at MODORI, with a background in blockchain R&D and smart contract development. He was a researcher at Decipher, a global blockchain research group, where he authored "Understanding the Ethereum Beacon Chain," providing an in-depth look at its foundational design, core algorithms, and associated implementation code. Recently, thanks to qpzm's influence, he has delved deeply into ZK, studying zkTLS protocols such as Reclaim Protocol and Primus.

KyoungWan Chae: @KyoungWan has been a solidity developer at MODORI since Aug 2022. He has experience in developing various smart contracts. He developed Lending Protocol on the Ethereum and DEX and Bonding Curve on the TON blockchain. He is also a researcher at decipher and wrote RWA in a bear market. He believes that ZK will play an important role in asset authentication in RWA and is continuing his research on ZK.

We believe ZK WebProof is crucial for bringing real-world assets (RWA) on-chain. As we integrate Noir circuits to prove more detailed arguments, this project is a perfect opportunity to deepen our involvement in Noir. While there is a JSON extractor in noir, verifying conditional statements like filtering array entry satisfying data[i].token == "ETH" or HTML responses created by server-side rendering throws a new challenge, so we're planning to develop an HTML parser in Noir as well.

Timeline and Deliverables

First Month

Phase 1: Develop MVP circuit & HonkVerifier - 1 week

• Deliverables:
  • A mvp semaphore circuit built with EdDSA and Lean IMT
  • A foundry test for HonkVerifier

Phase 2: Porting and Development - 1 week

• Deliverables:
  • A reviewed semaphore circuit.
    • We will review BoundedVec for input path.
    • If necessary, add, update and remove functions for Lean IMT.
  • Updated Semaphore contract using the new verifier contract.

Phase 3: Integration and Testing - 1 week

• Deliverables:
  • Compare UltraHonk and UltraPlonk verifiers regarding proof size, proof generation time and verification gas.
  • Updated demo like https://demo.semaphore.pse.dev/
  • Updated proof package aligned with the new circuits.

Phase 4: Deployment and Review - 1 week

• Deliverables:
  • Thorough testing and benchmarks of the new Noir circuit proof and verification process.
  • Deployment of all system components.
  • Completion of final documentation and user guides.
  • A comprehensive review of the project outcomes along with recommendations for future improvements.

Start Date

Today. We are already diving deep into Noir and this project because we believe ZK is the endgame.

Questions

• merkle.nr includes add, delete, and update functions, but the semaphore contract can only be implemented with the calculate_root function. Do these functions need to be included in the spec?
• Between UltraHonk and UltraPlonk, which one do you prefer?

  Barretenberg currently offers two provers: UltraPlonk and UltraHonk. In short, UltraHonk is faster and uses less RAM, but its verifier contract is significantly more expensive. UltraPlonk is optimized for on-chain verification, but proving is costlier.

• noir-lang/ec indicates that it is deprecated. Is noir-edwards safe to use?