Semaphore e2e interface as example

[oskarth]

Problem

As an example, it'd be useful to have something that works end to end.

Acceptance criteria

A lot of the code for Semaphore already exists. This should:

• Have basic protocol / public API that can be mimicked for other constructs
• Basic Rust tests
• FFI for important functionality
• (Outside of this repo) basic integration through e.g. nwaku

[oskarth]

First two items done here https://github.com/vacp2p/zerokit/tree/master/semaphore

[oskarth]

Rest of work deprioritized assuming things go well with RLN critical path

[Ben-PH]

Benchmarking Report: Semaphore Protocol Evaluation

Overview

I've conducted benchmarks comparing our Merkle trees against zk-kit incremental trees, as well as our Poseidon implementation against light-poseidon, under task ift:2025q2-zerokit:semaphore-parts-bench.

• Poseidon Hash Implementation:

  • Results indicate that our implementation is more performant.
  • Functional equivalence is confirmed.

• Merkle Tree Implementation:

  • Lean-IMT: No inherent performance advantages were observed in general use cases.
  • Proof Generation: Our full Merkle tree, regardless of the hash chosen, shows performance advantages.
  • Batch Setup and Proof Verification: Our full/optimal Merkle trees, coupled with our Poseidon hash implementation, demonstrate better performance.

• Hash-Free Setup:

  • Tree initialization without hashing takes roughly 1% of the time compared to when including a hash. This suggests that efforts to improve performance should consider the hashing function and tree implementation together.

Benchmarking Context

• Hardware: Benchmarks were conducted on a Ryzen 7 3700X with 32GB RAM.
• Data Generation: Seeded ChaCha8Rng PRNG was used for portable, deterministic data generation with high entropy.

Recommendations

• Verification of Data: Confirm that the benchmark data is truly representative. If verified, proceed with follow-up tests in a deployment environment.
• Future Work: Confirm these results can be replicated in a deployment context.
• investigate #[inline(always)] (see why the clippy lint warns it for context)

Conclusion

Based on the current findings, our implementations of Poseidon and Merkle trees show promising performance advantages. Verification of these findings and testing in real-world scenarios are recommended for next steps.

(ETA):

• The zk-kit implementation did not show any data as benchmarked that indicates for further pursuit. Non performance indicators (documentation, api structure, etc) appears to not provide a (qualitative) benefit to proceed with it.
• Performance differences aside. The light-poseidon implementation seems to have a slightly more refined api and documentation, and is not limited to a width of [Fr; 8].

You can see the result I generated in the file attached

criterion_report.tar.gz

to run/review the benchmarks yourself: #305 (cargo bench --bench poseidon_benchmark)and #308 (cargo bench --bench imt_benchy) will get you there

[Ben-PH]

One thing to note, that isn't necisarily a raw-performance issue, is the interface of zk-kit crate in terms of tree creation, and data primitives.

• The construction is of signature fn new(leaves: &[[u8; N]], hash: impl Fn(&[u8]) -> [u8; N]) -> ..., and later use of the tree asks for the hashing function to be provided again: fn insert(&mut self, leaf: &[u8; N], hash: impl Fn(&[u8]) -> [u8; N]). If my limited understanding is correct, the hash-function must not vary within each tree-instance, and this pattern contradicts this.
• the use of &[u8] (and friends) as the data primitive instead of &[Fr]. In a domain where Fr is the canonical representation of data, having u8 as the canonical throughout the interface, instead of just at the entry/exit points, raises questions.

[vplasencia]

Hey @Ben-PH

Thank you very much for the benchmarks and suggestions. I've just created an issue to track them: zk-kit/zk-kit.rust#78

I was wondering if there's any additional documentation or specifications on the data structures being benchmarked with LeanIMT?

[vplasencia]

For more context, the LeanIMT Rust implementation was recently created as part of the Semaphore V4 push for mobile support. It's still early and definitely has room for improvement. If there's enough interest and adoption, we plan to optimize it further and improve the developer experience.

The LeanIMT implementations in JavaScript and Solidity have already been optimized.