zerokit/rln

Zerokit RLN Module

The Zerokit RLN Module provides a Rust implementation for working with Rate-Limiting Nullifier RLN 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

Add RLN as dependency

We start by adding zerokit RLN to our Cargo.toml

[dependencies]
rand = "0.8.7"
rln = "3.0.0"
zerokit-utils = "3.0.0"

Basic Usage Example

On native targets the example below uses the built-in default circuit resources, so no files need to be loaded.

To use custom circuits, supply your own resources (see Custom Circuit Compilation):

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

use rand::{rngs::ThreadRng, thread_rng};
use rln::prelude::{
    hash_to_field_le, Fr, Hasher, IdentityKeys, PoseidonHash, RLNBuilder, RLNWitnessInput,
    DEFAULT_TREE_DEPTH,
};
use zerokit_utils::merkle_tree::{OptimalMerkleTree, ZerokitMerkleTree};

fn main() {
    // 1. Build an in-memory Merkle tree with a given depth. For a persistent sled-backed
    // tree, use the `PmTree` type instead (see the tree variants under Features section).
    let tree = OptimalMerkleTree::<PoseidonHash>::default(DEFAULT_TREE_DEPTH).unwrap();

    // 2. Build a stateful RLN over the tree; on native targets the circuit `graph` and `zkey`
    // default to the single message-id resources.
    let mut rln = RLNBuilder::stateful().tree(tree).build();

    // 3. Generate an identity key pair.
    let identity_keys = IdentityKeys::generate::<PoseidonHash, ThreadRng>(&mut thread_rng());

    // 4. Add the rate commitment `H(id_commitment, user_message_limit)` as a leaf in the tree.
    let leaf_index = 10;
    let user_message_limit = Fr::from(10);
    let rate_commitment =
        Hasher::<PoseidonHash>::hash_pair(identity_keys.id_commitment(), user_message_limit);
    rln.set_leaf(leaf_index, rate_commitment).unwrap();

    // 5. Get the Merkle proof for the added commitment.
    let merkle_proof = rln.get_merkle_proof(leaf_index).unwrap();

    // 6. Set up the external nullifier `H(epoch, rln_identifier)` from an epoch seed and an
    // application identifier, each mapped to a field element by hashing to field.
    let epoch = hash_to_field_le(b"Today at noon, this year");
    let rln_identifier = hash_to_field_le(b"test-rln-identifier");
    let external_nullifier = Hasher::<PoseidonHash>::hash_pair(epoch, rln_identifier);

    // 7. Choose a `message_id` satisfying `0 <= message_id < user_message_limit`.
    let message_id = Fr::from(1);

    // 8. Compute the signal `x` by hashing the message to a field element.
    let x = hash_to_field_le(b"RLN is awesome");

    // 9. Build the witness and generate a proof with its public proof values.
    let witness = RLNWitnessInput::new_single()
        .identity_secret(identity_keys.identity_secret())
        .user_message_limit(user_message_limit)
        .merkle_proof(&merkle_proof)
        .x(x)
        .external_nullifier(external_nullifier)
        .message_id(message_id)
        .build()
        .unwrap();
    let (proof, proof_values) = rln.generate_proof(&witness).unwrap();

    // 10. Verify the proof against the signal `x` and the current tree root.
    let root = rln.get_root();
    let verified = rln
        .verify_with_roots(&proof, &proof_values, &x, &[root])
        .unwrap();
    assert!(verified);
}

Comments for the code above for point 6

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. The tree backend is configurable at the type level: pick a tree type, construct it, and pass it to RLNBuilder::stateful().tree(...):
  • Full Merkle Tree: Fastest access with complete pre-allocated tree in memory. Best for frequent random access (use the FullMerkleTree type).
  • Optimal Merkle Tree: Memory-efficient sparse storage using HashMap. Ideal for partially populated trees (use the OptimalMerkleTree type).
  • Persistent Merkle Tree: Disk-based storage with sled for persistence across application restarts and large datasets (use the PmTree type).
• Stateless Mode: Allows the use of RLN without maintaining state of the Merkle tree.
• Parallel Processing: Optional parallel computation during proof generation for improved performance.
• Multi-Message-ID: Consume multiple message_id units in a single proof.
• 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 are excluded from the package to stay within the crates.io size limit. If you need tree depth 10 resources, download them from the GitHub repository.

• Wasm Support: WebAssembly bindings via rln-wasm module with features like:
  • Browser and Node.js compatibility.
  • Optional parallel feature support using wasm-bindgen-rayon.
  • Headless browser testing capabilities.

Building and Testing

Prerequisites

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

make installdeps installs the build dependencies:

• cargo-make: the build and test runner.
• cmake and ninja-build: native build tools.
• wasm-pack 0.15.0 and Node.js 22.14.0 via nvm (only needed for rln-wasm builds and tests).

Automatic installation supports macOS (Homebrew) and Debian/Ubuntu (apt); on NixOS the packages are expected to come from your system configuration. On other systems (Windows, Fedora, ...), install the packages above manually, then run the cargo make commands directly.

Build Commands

# Build with default features
cargo make build

# Test with default features
cargo make test

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

To customize the circuit parameters, modify circom-rln/circuits/rln.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 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 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 guide for more details. Make sure to use the specific version v2.1.0.

# 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

# 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 repository. As mentioned in step 1, we should use rln.circom file from circom-rln repository.

# 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. This is a fork of the original repository with uncompressed arkzkey support.

# 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 script to automate the process of generating the arkzkey file from any zkey file.

Run the script as follows:

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.

The FFI layer is organized into several modules:

• ffi_rln.rs - Implements core RLN functionality, including initialization functions, tree operations, proof generation, and proof verification.
• ffi_utils.rs - Contains all utility functions and structure definitions used across the FFI layer.

Compared to the native Rust API, the FFI layer has the following limitations:

• Poseidon is the only supported hash; the generic ZerokitHasher layer is not exposed.
• Proofs are always Groth16 over BN254 (ArkGroth16Backend); the zkSNARK backend is not pluggable.
• Tree selection is limited to the built-in backends (FullMerkleTree, OptimalMerkleTree and the sled-backed PmTree); custom ZerokitMerkleTree implementations cannot cross the C boundary.
• Errors are returned as strings rather than typed errors.
• Identity secrets stay behind opaque handles that only expose redacted debug output and equality checks; raw secret bytes never cross the boundary on their own.

Working examples for C and Nim live in ffi_c_examples and ffi_nim_examples, each with its own README and build instructions.

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

How it works:

Multi-message-ID mode allows consuming multiple message_id units in a single proof execution. Instead of generating one proof per message slot, a single proof covers up to max_out slots:

• Each slot has a corresponding nullifier and (x, y) pair in the proof output
• Selector bits indicate which slots are actively consumed
• Unused slots can be ignored by the verifier

Slashing across modes:

Two services can independently run in either single 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 are ignored. These normalized pairs are stored separately and checked for duplicate nullifiers via the compute_id_secret function, regardless of which mode generated the proof.

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 in the 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. 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 an identity secret and derive its public identity commitment id_commitment = Poseidon(id_secret). The secret proves membership; only the commitment is shared.
2. Rate Commitment: Compute rate_commitment = Poseidon(id_commitment, user_message_limit) and insert it as a leaf in the Merkle tree. This registers the member and binds that member to a per-epoch message budget.
3. External Nullifier Setup: Compute external_nullifier = Poseidon(epoch, rln_identifier), scoping proofs to a time window (epoch) and to one application (rln_identifier) so a proof generated for one application cannot be replayed in another.
4. Proof Generation: Create a Groth16 zkSNARK proof that:
   • Proves the member's rate commitment is included in the Merkle tree
   • Enforces the rate limit by checking 0 <= message_id < user_message_limit
   • Derives a nullifier so reuse of the same message slot is detectable
5. Proof Verification: Verify the Groth16 proof against the signal and a recent Merkle root without learning the prover's identity.
6. Slashing Mechanism: If a member exceeds their limit (two proofs sharing an external_nullifier but with different message_id), Shamir secret sharing allows anyone to recover the member's id_secret from the two proofs and slash them.

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

cargo doc --no-deps

Or look at the documentation for the latest rln version.

• Check the unit tests for more usage examples
• Check the rln-cli examples for complete interactive Rust examples of RLN features (relay, stateless, multi-message-id, partial)
• Check the C examples and Nim examples for complete FFI usage from other languages
• RFC specification for the Rate-Limiting Nullifier protocol
• Multi-Message-ID RLN RFC for details on the Multi-Message-ID extension
• Zerokit API documentation for comprehensive API reference
• GitHub repository for the latest updates