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 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 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.

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.

Problem

Currently, zerokit RLN uses both semaphore-rs Field and ark-ec Fr data types to carry field arithmetic, in order to use natively primitives from dependencies implemented for one type and the other.

However, while the semaphore-rs Field type corresponds to a big-endian byte vector without Montgomery reduction, the arkworks Fr type does operations directly in the more efficient Montgomery form, hence modulo p reduction is implicit.

This issue partially overlaps with the second item of https://github.com/vacp2p/zerokit/issues/31: while, in the latter, we ask to maximize usage of the Fr type, here we aim to exclusively use Fr along the whole module. Such refactor might require much more time than what is expected for zerokit v0.1 release.

Acceptance Criteria

• [x] Use exclusively the arkworks Fr field type to perform arithmetic in zerokit RLN

This PR addresses https://github.com/vacp2p/zerokit/issues/29 by adapting and integrating in a single space-efficient Merkle tree implementation:

• Kilic's RLN Merkle Tree implementation;
• semaphore-rs Merkle tree implementation.

In contrast to the previous zerokit Merkle tree implementation (mainly based on semaphore-rs' one), preliminary performance tests for the one proposed in this PR shows that, on average:

• an update_next call runs 4-5 microseconds slower (that is, ~4s overall delay for setting all leaves of a tree of depth 20);
• a new tree is initialized ~60x times faster;
• theoretically, setting N leaves should now require ~2^(log2(N)+1)*32 bytes instead of ~2^(N+1)*32;

The first two items can be verified running: cargo test test_merkle_performance --release -- --nocapture However, the same test should be adapted to the previous zerokit implementation -now removed- to effectively compare results.

A thorough analysis on storage performance (third item) and possible optimizations will follow in https://github.com/vacp2p/research/issues/127.

Problem

In zerokit RLN, CircomBuilder from ark-circom library is used to load the corresponding .wasm and .r1cs circuit files.

This process may take up to 2-3 minutes at every RLN instance creation (witness generation and zk proof verification times are not affected)

Acceptance criteria

• [x] Find out if this is expected behavior;
• [x] Minimize as much as possible loading time for circuit resources within ark-circom;
• [x] If loading time are still not practical, implement alternative circuit loading mechanisms.

This PR expands public zerokit RLN APIs by adding:

• set_next_leaf : set leaf to the next available free index;
• delete_leaf: to delete a leaf at a certain index;
• generate_rln_proof and verify_rln_proof: to verify zk proofs with input/output similar to Kilic's RLN implementation;
• key_gen: to generate a pair of (id, commitment), with commitment = PoseidonHash(id);
• hash: for hashing arbitrary signals to field elements.

Tests for each new rust and C API are also provided.

In order to implement set_next_leaf, the module now integrates a slightly customized version of semaphore-rs merkle tree and poseidon_tree implementations.

This PR will ease integration of zerokit RLN in nwaku implementation, with minimal edits to the latter.

Problem

Create a merkle tree that allows one to insert identity commitments and make merkle proofs.

From spec (https://github.com/vacp2p/rfc/blob/670816fa01f84fbde12a44f72f30e9b9458aaf5a/content/docs/rfcs/32/README.md):

{
  root: bigint
  indices: number[]
  path_elements: bigint[][]
}

See:

• https://github.com/appliedzkp/zk-kit/blob/main/packages/protocols/tests/rln.test.ts#L44
• https://github.com/appliedzkp/zk-kit/blob/main/packages/protocols/src/utils.ts#L27
• https://github.com/kilic/rln/blob/7ac74183f8b69b399e3bc96c1ae8ab61c026dc43/src/merkle.rs
• https://github.com/worldcoin/semaphore-rs/blob/main/src/merkle_tree.rs

Acceptance criteria

Merkle tree struct and merkle proofs can be created

Problem

We want to be able to use RLN through Circom circuits in Nim.

Notes

Currently this issue is a bit too big, so will probably want to split this up into smaller tasks.

Some relevant links:

• https://github.com/kilic/rln
• https://github.com/status-im/nim-waku/blob/master/waku/v2/protocol/waku_rln_relay/rln.nim
• https://github.com/appliedzkp/rln
• https://github.com/appliedzkp/zk-kit/tree/main/packages/protocols/src
• https://github.com/appliedzkp/zk-kit/blob/main/packages/protocols/tests/rln.test.ts#L44
• https://github.com/appliedzkp/zk-kit/blob/acaf3f43a0aab447905cdd9d6b9b24a8d99344fb/packages/protocols/src/witness_calculator.js

Acceptance criteria

RLN API is usable through nim-waku and has feature parity with existing implementation.

This PR addresses https://github.com/vacp2p/zerokit/issues/28, by updating zerokit RLN Merkle tree implementation so that trees are initialized by passing the tree_height = N in order to be able to accumulate at most 2^N hash leaves.

Previously, Merkle tree implementation followed semaphore-rs one, and trees were initialized by passing the total number of node levels (including the pre-images of the hash leaves), i.e. tree_height+1.

As a consequence, previous circuits embedded in zerokit RLN, correspond to height equal to 15 and 19. Since nwaku requires a tree of height 20 for implementing RLN-RELAY, the corresponding circuit was added in the library and tests were updated to cover this case as well.

This PR affects https://github.com/vacp2p/zerokit/pull/27, and one between https://github.com/status-im/nwaku/pull/1030 and https://github.com/status-im/nwaku/pull/1060, mainly due to tests' hardcoded values that need to be updated.

There are some reasons we might want to refactor this piece of code, to be elaborated on in this issue.

This issue is not blocking the initial release.

It'd be useful with a Makefile that installs all dependencies etc in a uniform way. This makes it easier for new people to be onboarded to this project and reduces cognitive overhead. Probably per crate. See Nimbus/nwaku as examples.

It'd be great to have WASM support so we can use Zerokit through browsers directly.

This issue corrsponds to already opened PR by @richard-ramos https://github.com/vacp2p/zerokit/pull/38

Currently in the code we have places where we do this conversion:

usize::try_from( some_u64_value ).unwrap();

// The u64 value might come from a function like u64::from_be_bytes

This will cause an error in 32 bit architectures, since usize max value depends on the architecture. To avoid this, lengths should be stored as u32 instead of u64

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

While attempting to implement go-rln-zerokit, I noticed that the resulting static libraries size are very large compared to kilic/rln:

• kilic/rln ⁃ aarch64-apple-darwin: 21.9MB ⁃ x86_64-apple-darwin: 22.6MB ⁃ aarch64-apple-ios: 21.8MB ⁃ x86_64-apple-ios: 22.6MB ⁃ universal (supporting aarch64-apple-ios,x86_64-apple-ios): 44.4MB
• vacp2p/zerokit ⁃ aarch64-apple-darwin: 57.7MB ⁃ x86_64-apple-darwin: 59.5MB ⁃ aarch64-apple-ios: 152MB ⁃ x86_64-apple-ios: 60.5MB ⁃ universal (supporting aarch64-apple-ios,x86_64-apple-ios): 212.5MB

While this is not an issue for desktop architecture, it is certainly not nice to have an app size increase due to the libraries it uses (also, I find it interesting that aarch64-apple-ios is 152MB, compared to the 60.5MB of x86_64-apple-ios).

I used the following commands to generate the static libs.

rustup target add aarch64-apple-ios x86_64-apple-ios x86_64-apple-darwin aarch64-apple-darwin
cargo build --release --target=x86_64-apple-darwin --lib
cargo build --release --target=aarch64-apple-darwin --lib
cargo lipo --release

Acceptance criteria

• [ ] Reduce as much as possible library size by checking/refactoring dependencies and the module