# Zerokit RLN Module

[![Crates.io](https://img.shields.io/crates/v/rln.svg)](https://crates.io/crates/rln)
[![License: MIT](https://img.shields.io/badge/License-MIT-blue.svg)](https://opensource.org/licenses/MIT)
[![License: Apache 2.0](https://img.shields.io/badge/License-Apache%202.0-blue.svg)](https://opensource.org/licenses/Apache-2.0)

The Zerokit RLN Module provides a Rust implementation for working with
Rate-Limiting Nullifier [RLN](https://lip.logos.co/ift-ts/raw/rln-v2) zkSNARK proofs and primitives.
This module allows you to:

- Generate and verify RLN proofs
- Work with Merkle trees for commitment storage
- Implement rate-limiting mechanisms for distributed systems

## Quick Start

> [!IMPORTANT]
> Version 0.7.0 is the only version that does not support WASM and x32 architecture.
> WASM support is available in version 0.8.0 and above.

### Add RLN as dependency

We start by adding zerokit RLN to our `Cargo.toml`

```toml
[dependencies]
rln = "2.0.1"
```

## Basic Usage Example

The RLN object constructor requires the following files:

- `rln_final.arkzkey`: The proving key in arkzkey format.
- `graph.bin`: The graph file built for the input tree size

Additionally, `rln.wasm` is used for testing in the rln-wasm module.

```rust
use rln::prelude::{hash_to_field_le, keygen, poseidon_hash, Fr, RLNWitnessInput, RLN};

fn main() {
    // 1. Initialize RLN with parameters:
    // - the tree depth;
    // - the tree config, if it is not defined, the default value will be set
    let tree_depth = 20;
    let mut rln = RLN::new(tree_depth, "").unwrap();

    // 2. Generate an identity keypair
    let (identity_secret, id_commitment) = keygen().unwrap();

    // 3. Add a rate commitment to the Merkle tree
    let leaf_index = 10;
    let user_message_limit = Fr::from(10);
    let rate_commitment = poseidon_hash(&[id_commitment, user_message_limit]).unwrap();
    rln.set_leaf(leaf_index, rate_commitment).unwrap();

    // 4. Get the Merkle proof for the added commitment
    let (path_elements, identity_path_index) = rln.get_merkle_proof(leaf_index).unwrap();

    // 5. Set up external nullifier (epoch + app identifier)
    // We generate epoch from a date seed and we ensure is
    // mapped to a field element by hashing-to-field its content
    let epoch = hash_to_field_le(b"Today at noon, this year");
    // We generate rln_identifier from an application identifier and
    // we ensure is mapped to a field element by hashing-to-field its content
    let rln_identifier = hash_to_field_le(b"test-rln-identifier");
    // We generate a external nullifier
    let external_nullifier = poseidon_hash(&[epoch, rln_identifier]).unwrap();
    // We choose a message_id satisfy 0 <= message_id < user_message_limit
    let message_id = Fr::from(1);

    // 6. Define the message signal
    let signal = b"RLN is awesome";

    // 7. Compute x from the signal
    let x = hash_to_field_le(signal);

    // 8. Create witness input for RLN proof generation
    let witness = RLNWitnessInput::new(
        identity_secret,
        user_message_limit,
        message_id,
        path_elements,
        identity_path_index,
        x,
        external_nullifier,
    )
    .unwrap();

    // 9. Generate a RLN proof
    // We generate proof and proof values from the witness
    let (proof, proof_values) = rln.generate_rln_proof(&witness).unwrap();

    // 10. Verify the RLN proof
    // We verify the proof using the proof and proof values and the hashed signal x
    let verified = rln.verify_rln_proof(&proof, &proof_values, &x).unwrap();
    assert!(verified);
}
```

### Comments for the code above for point 5

The `external nullifier` includes two parameters.

The first one is `epoch` and it's used to identify messages received in a certain time frame.
It usually corresponds to the current UNIX time but can also be set to a random value or generated by a seed,
provided that it corresponds to a field element.

The second one is `rln_identifier`
and it's used to prevent a RLN ZK proof generated for one application to be re-used in another one.

### Features

- **Stateful Mode**: Merkle tree management APIs for commitment storage and membership proofs.
- **Stateless Mode**: Allows the use of RLN without maintaining state of the Merkle tree.
- **[Parallel Processing](#parallel-processing)**:
  Optional parallel computation during proof generation for improved performance.
- **[Multi-Message-ID](#multi-message-id)**: Consume multiple message_id units in a single proof.
- **[Partial Proof Generation](#partial-proof-generation)**:
  Accelerate proof generation by caching the infrequently-changing portion of the witness,
  so only the small message-specific remainder is computed on each proof.
- **Pre-compiled Circuits**: Ready-to-use circuits with Merkle tree depth of 10 and 20.
  > **Note:** The crates.io package only includes tree depth 20 resources
  > (arkzkey and graph files) that are compiled into the binary at build time.
  > Tree depth 10 resources and `.wasm` files are excluded from the package
  > to stay within the crates.io size limit.
  > If you need tree depth 10 or `.wasm` circuit files,
  > download them from the
  > [GitHub repository](https://github.com/vacp2p/zerokit/tree/master/rln/resources).
- **Wasm Support**: WebAssembly bindings via rln-wasm crate with features like:
  - Browser and Node.js compatibility
  - Optional parallel feature support using
    [wasm-bindgen-rayon](https://github.com/RReverser/wasm-bindgen-rayon)
  - Headless browser testing capabilities
- **Merkle Tree Implementations**: Multiple tree variants optimized for different use cases:
  - **Full Merkle Tree**: Fastest access with complete pre-allocated tree in memory.
    Best for frequent random access (enable with `fullmerkletree` feature).
  - **Optimal Merkle Tree**: Memory-efficient sparse storage using HashMap.
    Ideal for partially populated trees (enable with `optimalmerkletree` feature).
  - **Persistent Merkle Tree**: Disk-based storage with [sled](https://github.com/spacejam/sled)
    for persistence across application restarts and large datasets
    (enable with `pmtree-ft` feature).

## Building and Testing

### Prerequisites

```sh
git clone https://github.com/vacp2p/zerokit.git
make installdeps
cd zerokit/rln
```

### Build Commands

```sh
# Build with default features
cargo make build

# Test with default features
cargo make test

# Test with stateless features
cargo make test_stateless

# Test with multi_message_id features
cargo make test_multi_message_id
```

## Advanced: Custom Circuit Compilation

The `circom-rln` (<https://github.com/rate-limiting-nullifier/circom-rln>) repository
contains the RLN circuit implementation used for
[pre-compiled](https://github.com/vacp2p/zerokit/tree/master/rln/resources)
RLN circuit for zerokit RLN.
If you want to compile your own RLN circuit, you can follow the instructions below.

### 1. Compile ZK Circuits for getting the zkey file

This script actually generates not only the zkey file for the RLN circuit,
but also the execution wasm file used for witness calculation.
However, the wasm file is not needed for the `rln` module,
because current implementation uses the iden3 graph file for witness calculation.
This graph file is generated by the `circom-witnesscalc` tool in [step 2](#2-generate-witness-calculation-graph).

To customize the circuit parameters, modify `circom-rln/circuits/rln.circom`:

```circom
pragma circom 2.1.0;
include "./rln.circom";
component main { public [x, externalNullifier] } = RLN(N, M);
```

Where:

- `N`: Merkle tree depth, determining the maximum membership capacity (2^N members).

- `M`: Bit size for range checks, setting an upper bound for the number of messages per epoch (2^M messages).

> [!NOTE]
> However, if `N` is too big, this might require a larger Powers of Tau ceremony
> than the one hardcoded in `./scripts/build-circuits.sh`, which is `2^14`.
> In such case, we refer to the official
> [Circom documentation](https://docs.circom.io/getting-started/proving-circuits/#powers-of-tau)
> for instructions on how to run an appropriate Powers of Tau ceremony
> and Phase 2 in order to compile the desired circuit. \
> Additionally, while `M` sets an upper bound on the number of messages per epoch (`2^M`),
> you can configure lower message limit for your use case,
> as long as it satisfies `user_message_limit ≤ 2^M`. \
> Currently, the `rln` module comes with
> [pre-compiled](https://github.com/vacp2p/zerokit/tree/master/rln/resources)
> resources for tree depths of `10` and `20`.
> RLN circuits with Merkle tree depths of `10` and `20` respectively,
> both with a bit size of `16`, allowing up to `2^10` or `2^20` registered members
> and a `2^16` message limit per epoch.

#### Install circom compiler

You can follow the instructions below or refer to the
[installing Circom](https://docs.circom.io/getting-started/installation/#installing-circom)
guide for more details.
Make sure to use the specific version `v2.1.0`.

```sh
# Clone the circom repository
git clone https://github.com/iden3/circom.git

# Checkout the specific version
cd circom && git checkout v2.1.0

# Build the circom compiler
cargo build --release

# Install the circom binary globally
cargo install --path circom

# Check the circom version to ensure it's v2.1.0
circom --version
```

#### Generate the zkey and verification key files example

```sh
# Clone the circom-rln repository
git clone https://github.com/rate-limiting-nullifier/circom-rln

# Install dependencies
cd circom-rln && npm install

# Build circuits
./scripts/build-circuits.sh rln

# Use the generated zkey file in subsequent steps
cp zkeyFiles/rln/final.zkey <path_to_rln_final.zkey>

# Use this repository for multi-message-id circuit compilation
git clone -b multi-message-id https://github.com/vacp2p/circom-rln.git
```

### 2. Generate Witness Calculation Graph

The execution graph file used for witness calculation can be compiled
following instructions in the
[circom-witnesscalc](https://github.com/iden3/circom-witnesscalc) repository.
As mentioned in step 1, we should use `rln.circom` file from `circom-rln` repository.

```sh
# Clone the circom-witnesscalc repository
git clone https://github.com/iden3/circom-witnesscalc

# Checkout the specific version and load submodules
cd circom-witnesscalc \
&& git checkout build-circuit/v0.1.1 \
&& git submodule update --init --recursive

# Build the circom-witnesscalc tool
cargo build

# Generate the witness calculation graph
cargo run -p build-circuit ../circom-rln/circuits/rln.circom <path_to_graph.bin>
```

### 3. Generate Arkzkey Representation for zkey file

For faster loading, compile the zkey file into the arkzkey format using
[ark-zkey](https://github.com/seemenkina/ark-zkey).
This is a fork of the [original](https://github.com/zkmopro/ark-zkey) repository
with uncompressed arkzkey support.

```sh
# Clone the ark-zkey repository
git clone https://github.com/seemenkina/ark-zkey.git

# Build the ark-zkey tool
cd ark-zkey && cargo build

# Generate the arkzkey representation for the zkey file
cargo run --bin arkzkey-util <path_to_rln_final.zkey>
```

This will generate the `rln_final.arkzkey` file, which is used by the `rln` module.

> [!NOTE]
> You can use this [convert_zkey.sh](./convert_zkey.sh) script
> to automate the process of generating the arkzkey file from any zkey file.

Run the script as follows:

```sh
chmod +x ./convert_zkey.sh
./convert_zkey.sh <path_to_rln_final.zkey>
```

## FFI Interface

RLN provides C-compatible bindings for integration with C, C++, Nim, and other languages through
[safer_ffi](https://getditto.github.io/safer_ffi/).

The FFI layer is organized into several modules:

- [`ffi_rln.rs`](./src/ffi/ffi_rln.rs) — Implements core RLN functionality,
  including initialization functions, proof generation, and proof verification.
- [`ffi_tree.rs`](./src/ffi/ffi_tree.rs) — Provides all tree-related operations
  and helper functions for Merkle tree management.
- [`ffi_utils.rs`](./src/ffi/ffi_utils.rs) — Contains all utility functions and structure definitions
  used across the FFI layer.

## Parallel Processing

The `parallel` feature flag should be enabled for end-user clients
where fastest individual proof generation time is required.
For server-side proof services handling multiple concurrent requests,
this flag should be disabled
and applications should use dedicated worker threads per proof instead.
The worker thread approach provides significantly higher throughput
for concurrent proof generation.

## Multi-Message-ID

The `multi-message-id` feature flag enables consuming multiple message_id units in a single proof.

**Key capabilities:**

- Burn multiple message_id units in one proof execution with corresponding nullifiers
- Use selector bits to determine which message_id slots are consumed
- Generate one proof instead of multiple for better computational efficiency

When enabled, the RLN module API allows specifying
multiple message_id values and selector bits during witness creation.
The proof generation and verification processes
are updated accordingly to handle the multi-message-id logic.

**Slashing across modes:**

Two services can independently run in either normal or multi-message-id mode to generate proofs.
The full structured format of `RLNWitnessInput` and `RLNProofValues`
is only needed for witness calculation, proof generation, and proof verification.

After verification, each active nullifier and its `(x, y)` pair can be extracted individually —
unused slots can be ignored.
These normalized pairs are then stored separately
and checked for duplicate nullifiers via `compute_id_secret` function.

## Partial Proof Generation

**How it works:**

Partial proof generation is an optimization technique
that allows us to split the proof generation process into multiple stages:

- Pre-computation: Whenever the Merkle tree changes, compute and cache the partial witness portion
  that corresponds to the Merkle proof and other static components of the witness.
- Partial proof generation: For each message, compute only the small per-message witness portion
  and combine it with the cached partial witness to generate a partial proof.
- Proof finalization: Finish the partial proof with the message-specific computation
  to produce the final valid proof.

**Observed speedup:** Finishing a partial proof is roughly **2.5–3× faster**
than generating a full proof from scratch,
since the expensive Merkle proof contribution is pre-computed
and reused across multiple messages.
See the [preliminary benchmarks](https://github.com/logos-storage/rln-fast#benchmarks)
in the [rln-fast](https://github.com/logos-storage/rln-fast) repository for details.

**Using cached partials across recent roots**. To reuse partial proofs while the tree changes,
cache the Merkle path alongside the root used to build the partial proof
and verify against a bounded set of recent roots
(for example, the last few roots) via APIs like [`verify_with_roots`](./src/public.rs#L743).
This keeps cached partials usable for short-lived historical roots while limiting replay risk;
when a root falls out of the allowed window or a member is removed/slashed,
rebuild the partial proof with the latest root and path
so revoked members cannot keep proving with stale roots.

**When this optimization is less effective:** In environments where the membership set changes very frequently,
the cached data is invalidated often and the overhead of pre-computation may outweigh the benefit.

## Detailed Protocol Flow

1. **Identity Creation**: Generate a secret key and commitment
2. **Rate Commitment**: Add commitment to a Merkle tree
3. **External Nullifier Setup**: Combine epoch and application identifier
4. **Proof Generation**: Create a zkSNARK proof that:
   - Proves membership in the Merkle tree
   - Ensures rate-limiting constraints are satisfied
   - Generates a nullifier to prevent double-usage
5. **Proof Verification**: Verify the proof without revealing the prover's identity
6. **Slashing Mechanism**: Detect and penalize double-usage attempts

## Getting Involved

Zerokit RLN public and FFI APIs allow interaction with many more features than what briefly showcased above.

We invite you to check our API documentation by running

```bash
cargo doc --no-deps
```

and look at unit tests to have a hint on how to interface and use them.

- Check the [unit tests](https://github.com/vacp2p/zerokit/tree/master/rln/tests)
  for more usage examples
- Check the [rln-cli examples](https://github.com/vacp2p/zerokit/tree/master/rln-cli/src/examples)
  for complete interactive Rust examples of RLN features
  (relay, stateless, multi-message-id, partial)
- [RFC specification](https://lip.logos.co/ift-ts/raw/rln-v2)
  for the Rate-Limiting Nullifier protocol
- [Multi-Message-ID RLN RFC](https://lip.logos.co/ift-ts/raw/multi-message_id-burn-rln)
  for details on the multi-message-ID extension
- [Zerokit API documentation](https://lip.logos.co/ift-ts/raw/zerokit-api.html)
  for comprehensive API reference
- [GitHub repository](https://github.com/vacp2p/zerokit)
  for the latest updates
