How to compile zerokit for wasm and see example code:

1. Make sure you have nodejs installed and the build-essential package if using ubuntu.
2. Install wasm-pack

curl https://rustwasm.github.io/wasm-pack/installer/init.sh -sSf | sh

3. Compile zerokit for wasm32-unknown-unknown:

cd rln
wasm-pack build --release

4. Launch example app

cd www
npm install
npm start

5. Browse http://localhost:8080 and open the developer tools to see console logs

Problem

Currently, zerokit RLN supports naive Merkle Tree implementation: when a RLN object is created, a tree of height N+1 is initialized (including the leaves level) with a total of 2^(N+1)-1 allocated nodes that remain allocated for the whole life of the RLN object, even in case the tree is empty or accumulates less than 2^N leaves.

For space-efficiency reasons we would like to add support to a Merkle trees implementations that progressively allocates only those nodes which are necessary to prove membership of currently non-empty leaves.

Acceptance criteria

• [x] Implement Incremental Merkle Tree with APIs compatible with current Merkle Tree implementation (aligned to https://github.com/vacp2p/zerokit/issues/28)
• [ ] ~~No regression in performances with respect to current implementation.~~
• [ ] ~~If regression in performance, evaluate space/time tradeoffs and followup with a better solution.~~

This PR updates some zerokit RLN APIs in light of the security design changes discussed in https://github.com/vacp2p/research/issues/152, https://github.com/Rate-Limiting-Nullifier/rln_circuits/issues/1 and implemented in https://github.com/Rate-Limiting-Nullifier/rln_circuits/pull/2.

In particular external_nullifier is now computed as the Poseidon hash of epoch and RLN identifier, while in generating shares the nullifier is computed only by hashing the a1 coefficient (see above issues for more details).

Note that all circuit resources had to be re-generated and that new circuits are not compatible with previous ones.

@richard-ramos @fryorcraken could you please ensure that these changes doesn't break anything in rln-wasm and js-rln ? (should not, but better we double check)

FYI: @curryrasul @AtHeartEngineer

This PR addresses https://github.com/vacp2p/zerokit/issues/19.

Progress

• [x] Implement byte serialization/deserialization of custom data structure (RLN Witness and Proof values);
• [x] Extend/update RLN Rust public API to support all required features;
• [x] Extend/update RLN C public API to support all required features.

This PR is a first step towards a fully working implementation of persisted Merkle trees in zerokit.

The PR integrates the pmtree module developed by PSE, as described in https://github.com/vacp2p/zerokit/issues/65, and checks correctness of implementations using SledDB for on-disk persistence and HashMap for in-memory storage.

A new feature pmtree is added in order to swap from the current default OptimalMerkleTree implementation to pmtree. However, at the moment this feature is disabled (will fallback to OptimalMerkleTree), since some pmtree's APIs still need to be aligned with zerokit module and other MT implementations.

Follow-up PRs will ensure that all 3 FullMerkleTree, OptimalMerkleTree and pmtree implementations are aligned and interchangeable by enabling the corresponding feature flag.

@curryrasul @AtHeartEngineer

To make the credentials generated by RLN more compatible with Semaphore, we need to update the secret generation to include generation of the identity_trapdoor and identity_nullifier as mentioned in Semaphore's docs - https://semaphore.appliedzkp.org/docs/technical-reference/circuits

This will allow re-using the same credentials for Semaphore groups and RLN

cc: @s1fr0 @oskarth

This PR partially addresses https://github.com/vacp2p/zerokit/issues/69.

Items completed

• [x] Basic documentation for how to use RLN in Zerokit.
• [x] Document public crate APIs documentation so that meaningful info appears when running cargo doc

In order to minimize the cognitive overhead given by following the tutorial proposed in first item, further APIs might be added in parallel PRs with the goal to minimize the amount of code required (e.g. simplify serialization, etc). Such effort will ease the understanding and design of a CLI interface as requested by https://github.com/vacp2p/zerokit/issues/70.

At the moment, such parallel PRs consist of:

• https://github.com/vacp2p/zerokit/pull/75

Merging/closing them PRs is a prerequisite for this one to be merged.

This PR allows the following feature - https://github.com/status-im/nwaku/issues/1266.

Changes the C FFI of set_leaves to init_tree_with_leaves, and adds a new function called set_leaves_from, which init_tree_with_leaves uses internally, with starting index 0.

This WIP PR addresses https://github.com/vacp2p/zerokit/issues/16 solving previous issues with proving and verifying keys import, proof generation/verification, RLN witness fields, etc. It further removes some unnecessary crates.

This PR partially addresses https://github.com/vacp2p/zerokit/issues/69, by adding new APIs to ease user interaction while using public APIs.

The main goal is to reduce the cognitive overhead required to interface with public APIs, by providing helper function which automate non-RLN specific tasks (mainly I/O serialization/deserialization).

Merging this PR is a requirement for merging the documentation PR https://github.com/vacp2p/zerokit/pull/74, which was already updated to refer to such new APIs.

Problem

UPDATE: This is becoming a waterfall release which keeps getting delayed, which was never the intention. We want to take existing code and cut it into an initial 0.1 release.

We want to publish a release v0.1 for Zerokit with a first ~~mature~~ version of the RLN module.

Before that, it is desirable to clean-up the RLN module library code and implement different optimizations which are already standard in other libraries.

These allow to: make the RLN module more efficient and easily integrable in projects employing the RLN primitive; bring a cleaner code and optimized cross-module primitives (e.g., Merkle trees) to new zerokit modules.

Scope

Release zerokit v0.1 with a RLN module that can replace and improve Kilic's RLN module currently employed by nwaku.

Must have:

• [x] Sanity check main features included / bug fixes included -- Err on side of not accepting more scope
• [x] Release branch with release note and tag
• [ ] Announce release on Discord and Twitter

Initial list of issues, many nice to haves that can be dealt with separately:

• [x] https://github.com/vacp2p/zerokit/issues/29

• [ ] Maximize usage of only arkworks dependencies (e.g., replace Semaphore's Field with arkworks Fr, etc.) and remove unnecessary ones (might require adapting/integrating used primitives e.g. Poseidon hash)
  • [x] https://github.com/vacp2p/zerokit/issues/35
  • [ ] https://github.com/vacp2p/zerokit/pull/44
• [ ] Eventually add/update APIs to address new needs resulting from completions of milestones in the RLN-RELAY track https://github.com/status-im/nwaku/issues/1062 or other tracks:
  • [ ] https://github.com/vacp2p/zerokit/pull/45 (contains https://github.com/vacp2p/zerokit/pull/36)

• [ ] Reduce size of compiled libraries (might require partial refactoring of dependencies) https://github.com/vacp2p/zerokit/issues/37

Acceptance criteria

Issues defined in scope addressed.

Risks and uncertainty

Removing some dependencies (e.g. semaphore-rs) might result not trivial, since there might some implementation used across the code base that should be ported to the replacing dependencies.

Out of scope

This milestone's scope requires a RLN module which can replace (in terms of APIs and efficiency) Kilic's RLN module. However, integration of zerokit v0.1 in nwaku is out-of-scope and is tracked in https://github.com/status-im/nwaku/issues/1061.

Notes and links

This first issue partially overlaps with https://github.com/vacp2p/research/issues/127, where a thorough performance analysis of employing Incremental Merkle trees is performed. This milestone will clearly benefit from completion of https://github.com/vacp2p/research/issues/127, and new items will be added to the above issues list to implement any eventual optimization found.

As per the discussion here - https://github.com/vacp2p/zerokit/pull/86#discussion_r1044331978. When the benchmarking needs become more significant, we will use the inbuilt library or an alternative to benchmark to understand where the code can be optimized.

Problem

Currently, zerokit semaphore module implements wrappers around API exposed by semaphore-rs, a submodule of the semaphore crate.

This doesn't allow the same flexibility and easy features extension currently allowed e.g., by the zerokit RLN module.

Furthermore, using submodules makes hard to deal with any eventually breaking change introduced by submodule's dependencies, as happened in https://github.com/vacp2p/zerokit/pull/79. This results in a failing zerokit compilation and leaves few possibilities to solve such issue quickly without relying on forks and/or dependencies' developers response.

Acceptance criteria

• [ ] Refactor semaphore module similarly as the RLN module (public API, FFI, zk resources, MT implementation, etc.)

Problem

Currently we are doing special-purpose APIs for e.g. RLN. It'd be useful to factor out the general parts and allow and Circom-based circuits to be used through Zerokit.

Context

Obviously not doable for all APIs, but e.g. prove and verify + general format for inputs seems doable? Especially if it is using JSON or whatever for passing data.

(This doesn't mean we shouldn't also have special purpose APIs that are useful for specific circuits).

Acceptance criteria

Some way of dealing with with generic Circom circuits (e.g. ones that the library doesn't know about!) to do basic prove and verify operations.

Problem

As a dapp developer I'm required to know and deal with a lot of different runtimes/domains (JS/Circom/Solidity/Rust/ZK etc). Minimizing cognitive overhead would be useful.

Context

Also see https://github.com/vacp2p/zerokit/issues/69

As well as https://book.getfoundry.sh/forge/tests for Foundry forge tool. Might make sense to "bundle" foundry or similar based scripts for interacting with smart contracts.

Acceptance criteria

• [ ] Proposal of MVP CLI API that allows for interacting with RLN - e.g. create groups, adding members, etc. -- separate out must have for MVP and nice to have future work

Problem

As a developer, it isn't clear how to get started with RLN in Zerokit.

Context

Zerokit has multiple crates, where RLN is the most important one right now. Currently, usage of this is mostly aimed towards Waku usage, e.g. RLN Relay. There are many other uses for RLN too.

E.g. see for example https://github.com/Rate-Limiting-Nullifier/rlnjs#usage

Acceptance criteria

• [ ] Basic documentation for how to use RLN in Zerokit.
• [ ] To extent that API currently doesn't allow standalone usage, issues should be cut out and addressed

Background

Tracking this issue based on https://github.com/vacp2p/zerokit/pull/67#discussion_r1019377045.

Problem

The roots generated by FullMerkleTree and OptimalMerkleTree should be the same.

Acceptance Criteria

• [ ] The test at https://github.com/vacp2p/zerokit/blob/master/rln/src/poseidon_tree.rs#L87 is updated with this assertion