Release v0.8.0

[seemenkina]

rln-wasm

• Bring back wasm support for zerokit
• Investigate the possibility of using parallel computations
• Update README

rln

• Audit witness calculation part for RLN module
• Audit atomic_operation function for tree structure

docs

• bug(docs): Docs fail to build on docs.rs #256
• Consider using cargo-rdme to generate README.md content #303

[vinhtc27]

Zerokit rln-wasm module

Background

Zerokit rln-wasm module was originally built with Wasmer, but it has significant drawbacks:

• Difficult to support due to compatibility issues.
• Very slow performance.
• Problems with parallel execution.

Goal: This release aims to explore alternative web-compatible solutions that deliver high performance.

Current Status

• We have revived the old approach using the ark-circom crate (version v0.5.0) with the wasm feature enabled as a baseline for benchmarking and comparison. feat(rln-wasm): porting the rln-wasm feature from v0.6.1 to v0.7.0 #292
• This approach uses a .wasm file for witness calculation, with JS bindings that allow witness computation outside RLN.

Challenges with the Current Approach

The current implementation introduces major compatibility issues:

• Wasmer runtime: Does not support 32-bit architectures. wasmer-wasix fails to compile on arm and armv7 linux builds wasmerio/wasmer#4227 (comment)
• Dependency on ark-circom: Vendor the latest v0.5.0 release with wasm support requires a custom fork of wasmer due to dependency conflicts. https://github.com/vinhtc27/wasmer
• Parallel execution not yet supported in the browser: Enable parallel execution in rln-wasm #109

Potential Solutions to Improve rln-wasm

As part of the transition away from ark-circom #282, we can consider the following improvements:

1. Witness Calculation

• We have migrated to iden3 for witness calculation in the RLN module.
• Currently, rln-wasm uses JS bindings to witness_calculator.js, which is generated from circom-rln during circuit compilation.
• Performance could be improved if circom-witnesscalc gains native Wasm compatibility. wasm compatibility? iden3/circom-witnesscalc#10

2. Key Parsing & Circom Reduction

• Upon reviewing the arkworks-rs/circom-compat codebase, it appears that the read_zkey function and the CircomReduction struct do not rely on the wasmer and wasmer-wasix dependencies.
• Those dependencies are mainly used for witness generation, which rln-wasm handles via JS bindings. Maybe we can remove the need for ark-circom completely for zerokit.
• The CircomReduction struct and the read_zkey function in ark-circom can be duplicated into zerokit directly with minimal changes.

3. WebAssembly Runtime Selection (if still needed)

• Existing Rust WebAssembly runtimes are listed here.
• Out-of-the-box browser support:
  • wasmer ✅(but lacks support for 32-bit)
  • wasm3 ✅ (but lacks active maintenance)
  • wasm-micro-runtime ⚠️ (best performance but requires Rust bindings from C)
  • WasmEdge ⚠️ (2nd best performance but requires Rust bindings from C++, but native JS API in Rust look easy to use)
  • Wasmtime and a few other Rust-based runtimes ❌ (support 32-bit but lack browser support Make Wasmtime work on the web bytecodealliance/wasmtime#6504 or have too few stars).
• Recommended Approach:
  • If browser support is a priority, the latest Wasmer version is the best option.
  • If 32-bit compatibility is required, Wasm3 should be explored, but performance might be a problem.
  • If performance is the main concern, WasmEdge should be considered.
• WebAssembly runtime benchmark: article.

4. Parallel Execution Solutions

• Parallel execution using Web Workers and wasm-bindgen-rayon.
• Use threads with WebAssembly, Rust, and wasm-bindgen which use SharedArrayBuffer with security requirements
• There is also SIMD optimization proposal for Rust in wasm32 target

Next Steps

• Determine if ark-circom can be removed; if not, assess whether it can use a different runtime.
  • Update: I was able to remove ark-circom and wasmer from zerokit. Check out commit.
• If ark-circom needs to be replaced, explore alternative solutions in this Circom comparison article.
• Explore all parallel execution methods suitable for browsers in WebAssembly.

[vinhtc27]

Benchmark Comparison of rln-wasm

I recently added benchmarks in this PR for the rln-wasm module.
Additionally, I ran the same benchmarks on the previous version, v0.6.1, in the benchmark-v0.6.1 branch, as well as on an older version of zerokit-wasm-research before ark-circom and wasmer were removed commit 3093cd9.

UPDATE: I also added a benchmark for rln-wasm in the browser, which imports the rln_wasm_bg.js file into an HTML file for direct use, and fixed some data files for the benchmark, such as this file and fork to the benchmark-v0.7.0 branch for later use.

Benchmark Results

All benchmarks were conducted on my MacBook Pro M1.

The results indicate a significant improvement in the latest version compared to the previous rln-wasm.

Old Version (v0.6.1)

Latest Version (zerokit-wasm-research)

• Additionally, the CI workflow for macOS produced similar results for the latest version:

• The browser benchmark result is as follows:

Performance Analysis

I also ran benchmarks on the zerokit-wasm-research branch using the commit 3093cd9.

• The results were similar to those of the latest version, suggesting that the performance improvements primarily came from changes introduced in v0.7.0.
• Removing ark-circom primarily improved build time, reduced package size, and resolved compatibility issues. It does not appear to have provided any direct performance benefits yet from Rust benchmarks, but smaller package size could benefit browsers through faster loading times.

UPDATE:

I added the arkzkey feature to the rln-wasm module, and it shows a 100x improvement in the wasm_new function.

• The browser benchmark result is as follows:

[sydhds]

Iden3 Witness Calculator Integration Review

Background

Iden3 code was previously copy and paste (with some modifications) from the circom-witnesscalc repository.

Ideally we would like to remove this code and import (as a git submodule) the circom-witnesscalc repository.

Analysis

Current iden3 code was imported from circom-witnesscalc repository at commit id: 5cb365b.

Here is a review of the modifications file by file:

graph.rs

Addition: fn fr_to_u256(...) && fn u256_to_fr for type conversion
Modification: fn evaluate(...) returns Vec instead of Vec
Cleanup: remove some println! or eprintln! (fn propage(...), fn tree_shake(...), fn value_numvering(...), fn constants(...)
Optim: function shl has been optimized with bit shifting
Optim: unroll code in functions bit_and, bit_or, bit_xor
Misc: code format (most likely using cargo fmt) + some cargo clippy fixes

storage.rs

Optim: vec init with capacity (in function: fn deserialize_witnesscalc_graph)

proto.rs

This file is not present in git repository because it is automatically generated at build time by protoc (the protobuf compiler) - see build.rs)

iden3calc.rs (versus lib.rs)

The function calc_witness signature was changed to match the current argument provided by calculate_rln_witness:

current signature:

fn calc_witness<I: IntoIterator<Item = (String, Vec<Fr>)>>(inputs: I,graph_data: &[u8],) -> Vec<Fr

git signature:

fn calc_witness(inputs: &str, graph_data: &[u8]) -> Result<Vec<U256>, Error>

Test PR & Benchmark

The following PR: Iden3 Witness Calculator Integration Review (benchmark) has all the modification to compare performance between current iden3 code & git code. Note that the PR import crate using a git url: however this is not accepted by crate.io when publishing (will need to use a git submodule here).

Benchmark between current code & git 5cb365b:

cargo bench --bench calc_witness_benchmark
    Finished `bench` profile [optimized] target(s) in 0.30s
     Running benches/calc_witness_benchmark.rs (target/release/deps/calc_witness_benchmark-a99fe92ffbd0a84d)
Gnuplot not found, using plotters backend
calc_witness/Circom-witnesscalc current
                        time:   [1.9723 ms 1.9780 ms 1.9850 ms]
Found 12 outliers among 100 measurements (12.00%)
  11 (11.00%) high mild
  1 (1.00%) high severe
calc_witness/Circom-witnesscalc crate(git)
                        time:   [2.0480 ms 2.0512 ms 2.0550 ms]
Found 1 outliers among 100 measurements (1.00%)
  1 (1.00%) high mild

As we can see there is no significant difference of performance between the two.

Benchmark between current code & git de9e6f15800d3f37e5d60da4dbc8e07b49c815e6 (last commit as of Apr 3rd, 2025).

cargo bench --bench calc_witness_benchmark
    Finished `bench` profile [optimized] target(s) in 0.29s
     Running benches/calc_witness_benchmark.rs (target/release/deps/calc_witness_benchmark-492c5651ef3961ef)
Gnuplot not found, using plotters backend
calc_witness/Circom-witnesscalc current
                        time:   [1.9058 ms 1.9078 ms 1.9100 ms]
Found 2 outliers among 100 measurements (2.00%)
  2 (2.00%) high mild
Benchmarking calc_witness/Circom-witnesscalc crate(git): Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 11.0s. You may wish to increase target time to 14.8s, enable flat sampling, or reduce sample count to 60.
calc_witness/Circom-witnesscalc crate(git)
                        time:   [2.9105 ms 2.9157 ms 2.9220 ms]
Found 4 outliers among 100 measurements (4.00%)
  2 (2.00%) high mild
  2 (2.00%) high severe

By using the latest commit in the git repository, we can see some performance regressions.

Note: the git code was imported locally in order to remove some print calls (for a fair benchmark).

Conclusion & next steps

For now, I would recommend using a git submodule but stick to the original commit id (5cb365b). It would allow us to
contribute upstream with modifications and optimizations. In case, we need to later fork the repository, we could still use this git submodule to track it.

Next steps:

• Investigate the performance regressions with the latest git id

[sydhds]

Performance regression using latest circom-witnesscalc repo

Finding the 2 commits where the regression occurs

By using the benchmark implemented in the previous post (draft PR), we need to bisect between:

• Original import commit - Dec 8th, 2024
• Last commit - March 23th, 2025

After many attempt (some commits require some minor modification in order for the benchmark code to compile):

circom-witnesscalc repo (local):

git stash && git checkout 7c51ea50899a51680060798938031588d593b044 && git stash apply

zerokit repo:

cargo bench --bench calc_witness_benchmark
  Gnuplot not found, using plotters backend
  calc_witness/Circom-witnesscalc current
                          time:   [1.9662 ms 1.9697 ms 1.9731 ms]
  Found 1 outliers among 100 measurements (1.00%)
    1 (1.00%) low mild
  calc_witness/Circom-witnesscalc crate(git)
                          time:   [2.1153 ms 2.1176 ms 2.1199 ms]

VS ->

circom-witnesscalc repo (local):

git stash && git checkout 8ebe1ffb8d6a45cd85a8c700fcafefb2f8306d02 && git stash apply

zerokit repo:

Gnuplot not found, using plotters backend
calc_witness/Circom-witnesscalc current
                        time:   [1.9171 ms 1.9221 ms 1.9270 ms]
Found 1 outliers among 100 measurements (1.00%)
  1 (1.00%) high mild
calc_witness/Circom-witnesscalc crate(git)
                        time:   [2.9681 ms 2.9732 ms 2.9785 ms]
Found 6 outliers among 100 measurements (6.00%)
  4 (4.00%) high mild
  2 (2.00%) high severe

Code changes between the two commits seems, after a quick first look, too simple to produce a performance regression.

Why profiling benchmark was a dead end

Profiling the benchmark sounds like a first good approach:

Setup for profiling

sudo echo 0 |sudo tee /proc/sys/kernel/kptr_restrict
sudo echo -1 |sudo tee /proc/sys/kernel/perf_event_paranoid

Flamegraph

Using cargo flamegraph on unit test test_witness_bench:

cargo clean
cargo flamegraph -o calc_witness.svg --dev --no-inline --test protocol -- test_witness_bench

EDIT test_witness_branch to use calc_witness_2 function, then:

cargo clean
cargo flamegraph -o calc_witness_2.svg --dev --no-inline --test protocol -- test_witness_bench

OR:

perf record -F max --call-graph dwarf,16384 -g -o perf.data ./target/debug/deps/protocol-37774d76ca74b304 --nocapture test_witness_bench
~/.cargo/bin/flamegraph --inverted --no-inline -o calc_witness_2_perf.svg --perfdata perf.data

from this blog post

Hint:

• Click on test_witness_bench then graph::evaluate to focus the view
  • Issue: lots of Unknown (if using perf directly)

Comparing the two produced flamegraph svg files and selecting only the stacktrace of test_witness_bench, does not bring any
useful information. Unfortunately :-/

Profiling specific unit test in circom-witnesscalc

Let's focus -> we need to benchmark only the portion of code that is responsible for the performance regression:

Step 1: serialize the data used in the benchmark (as we know this particular data is causing the regression)

Modify our benchmark with something like:

    let fs_nodes = std::fs::File::create("nodes.json").unwrap();
    serde_json::to_writer(fs_nodes, &nodes).unwrap();
    let fs_inputs = std::fs::File::create("inputs.json").unwrap();
    serde_json::to_writer(fs_inputs, &inputs_buffer).unwrap();
    let fs_outputs = std::fs::File::create("outputs.json").unwrap();
    serde_json::to_writer(fs_outputs, &signals).unwrap();

Run the benchmark (with only 1 iteration) in order to get our data.

Step 2: Writing a small unit test in 2 circom-witnesscalc repo (local repositories)

Here we used 2 git repositories (one at commit 8ebe1ff, the second one at commit 7c51ea5) and add the following unit test:

    #[test]
    fn test_evaluate() {

        let f_nodes = std::fs::File::open("../zerokit/rln/nodes.json").unwrap();
        let nodes: Vec<Node> = serde_json::from_reader(f_nodes).unwrap();
        let f_inputs = std::fs::File::open("../zerokit/rln/inputs.json").unwrap();
        let inputs: Vec<U256> = serde_json::from_reader(f_inputs).unwrap();
        let f_outputs = std::fs::File::open("../zerokit/rln/outputs.json").unwrap();
        let outputs: Vec<usize> = serde_json::from_reader(f_outputs).unwrap();

        let mut res_f = 0;
        let mut counter = 0u64;
        let mut elapsed = std::time::Duration::new(0, 0);
        // for _i in 0..100
        {
            let start = std::time::Instant::now();
            let res = evaluate(nodes.as_slice(), inputs.as_slice(), outputs.as_slice());
            elapsed = start.elapsed();
            res_f = res.len();
            counter += 1;
        }

        dbg!(res_f);
        dbg!(counter);
        dbg!(elapsed);
    }

Elapsed time between the 2 repository shows some differences, but we need to understand why.

After further investigation, we identify the evaluate function spend the majority of its time into

• pub fn eval(&self, a: U256, b: U256) -> U256
• pub fn eval_fr(&self, a: Fr, b: Fr) -> Fr

The eval or eval_fr function execute a given operation with the given operators. Luckily for us, only a few operations
are used in our cases (Mul, Add, Sub, Shr, Band).

We've added timings for each operation and then, we could produce this:

Operation	8ebe1ff (average nanosecs - cumulative microsecs)	7c51ea5
Band	301 ns / 9 µs	3828 ns / 114 µs
Shr	509 ns / 15 µs	2995 ns / 89 µs
Sub	548 ns / 22 µs	307 ns / 12 µs
Add	447 ns / 3721 µs	298 ns / 2483 µs
Mul	2047 ns / 28979 µs	456 ns / 6374 µs

As we can see, there is a huge performance gap between the 2 MUL operation implementations.

Step 3: Mul operation (or finding where is our bottleneck)

Mul operation implementation (commit 8ebe1ff):

U256 multiplication implementation comes from the ruint crate and documented as:

Compute $\mod{\mathtt{self} ⋅ \mathtt{rhs}}_{\mathtt{modulus}}$.

Returns zero if the modulus is zero.

See mul_redc for a faster variant at the cost of some pre-computation.

The code is quite basic:

    /// Compute $\mod{\mathtt{self} ⋅ \mathtt{rhs}}_{\mathtt{modulus}}$.
///
/// Returns zero if the modulus is zero.
///
/// See [`mul_redc`](Self::mul_redc) for a faster variant at the cost of
/// some pre-computation.
#[inline]
#[must_use]
pub fn mul_mod(self, rhs: Self, mut modulus: Self) -> Self {
  [...] // omitted for clarity

  // Compute full product.
  let overflow = algorithms::addmul(product, self.as_limbs(), rhs.as_limbs());
  debug_assert!(!overflow);

  // Compute modulus using `div_rem`.
  // This stores the remainder in the divisor, `modulus`.
  algorithms::div(product, &mut modulus.limbs);

  modulus
}

Mul operation implementation (commit 7c51):

Fr multiplication implementation comes from the ark-ff crate.

Implementation can be found here:

    /// This modular multiplication algorithm uses Montgomery
    /// reduction for efficient implementation. It also additionally
    /// uses the "no-carry optimization" outlined
    /// [here](https://hackmd.io/@zkteam/modular_multiplication) if
    /// `P::MODULUS` has (a) a non-zero MSB, and (b) at least one
    /// zero bit in the rest of the modulus.
    #[inline]
    fn mul_assign(a: &mut Fp<Self, N>, b: &Fp<Self, N>) {
        T::mul_assign(a, b)
    }

mul_assign code can be found here.

Montgomery wikipedia article quote:

Montgomery modular multiplication relies on a special representation of numbers called Montgomery form. 
The algorithm uses the Montgomery forms of a and b to efficiently compute the Montgomery form of ab mod N. 
The efficiency comes from avoiding expensive division operations. 
Classical modular multiplication reduces the double-width product ab using division by N and keeping only the remainder. 

The Montgomery algorithm is further optimised with:

• #[unroll_for_loops(12)]
• // No-carry optimisation applied to CIOS and later: ark_ff_asm::x86_64_asm_mul!(...)
• // Alternative implementation // Implements CIOS.

Summary

Profiling is not an easy task but at the end, we successfully identify where the performance bottleneck comes from.

Next steps:

• Discuss and find a (pragmatic?) solution!
  • Should we keep the imported code as it is OR
  • Should we import the code (using a git submodule)
    • Which commit to use (latest - perf regression), original (perf ok but old), latest with no perf regression (a bit old)
  • Should we notify the circom-witnesscalc repo about the perf regression?
  • Should we try to improve the ruint mul_mod implementation?

[vinhtc27]

Benchmarking rln-wasm with Parallel Execution Enabled

After exploring the idea of using Web Workers and wasm-bindgen-rayon to accelerate the rln-wasm module, here are the benchmark results.

All tests were performed in the browser using a simple HTML file without Webpack (same as the previous benchmark report), though the current version can also be served with Webpack if needed, as I've already separated the Node-compatible version from the vanilla browser JS version. The implementation was tested in Chrome, Firefox, and Safari.

The implementation and benchmarks can be found in this PR.

---

Multithreaded Mode Enabled

This configuration enables the multithreaded mode:

---

Multithreaded Mode with arkzkey Feature Enabled

This configuration enables the arkzkey feature in addition to multithreading, resulting in faster instance creation time:

---

Summary of Improvements

Parallel computation improves proof generation time by more than 3 times compared to the previous fastest benchmark

The parallel feature of all arkworks dependency crates (which internally use the rayon crate) enables this speedup. By initializing the thread pool in the browser using wasm-bindgen-rayon, computations are distributed across multiple workers.

Essentially, all future optimizations using rayon in the RLN module will automatically benefit rln-wasm as well.

For optimal performance, it's recommended to use navigator.hardwareConcurrency property on browser to determine the ideal number of threads for each machine — this is also the configuration used for the benchmark.

---

Compatibility

Most modern browsers support WebAssembly threads, as shown in the WebAssembly Feature Extensions Report.

To support older browsers, we can include feature detection logic in the rln-wasm documentation. This helps users determine whether to use single-threaded or multi-threaded mode.

Based on my testing, there's no need to compile separate builds. Simply skipping the call to initThreadPool will allow the module to run in single-threaded mode without affecting its functionality.

---

Next Steps

The rln-wasm module is already capable of compiling a build that runs in the browser. However, I'm currently working on setting up tests using wasm-bindgen-test in Rust and enabling it in the CI workflow.
There is still one remaining issue with initThreadPool within Rust codebase, which is the same as the one mentioned in this comment. Once resolved, the CI tests will help ensure any future changes to the rln-wasm module are thoroughly checked.

[vinhtc27]

Benchmarking MerkleTree with Parallel Execution Enabled

After applying Rayon to parallelize both OptimalMerkleTree and FullMerkleTree from the rln-utils module, here are the benchmark results:

The implementation and benchmarks can be found in this PR.

OptimalMerkleTree

• override_range operation improved by 1.7×.
• other operations showed a slight performance increase due to some internal refactoring.

FullMerkleTree

• override_range operation improved by 2×.
• other operations showed no significant change.

Current Implementation

• The utility function update_hashes uses Rayon to parallelize and speed up hash recalculations.
• This works because, at each tree level, parent hashes are computed independently — each one depends only on two child nodes that are already computed. Since no two parents share children, all hash computations at the same level can run in parallel without conflicts or synchronization overhead.
  • The override_range operation benefits the most, as it uses set_range, which internally calls update_hashes.
  • The set and delete operations also use update_hashes, but since they typically update only one node, parallelization offers no benefit — sequential execution is faster in this cases.

// Use parallel processing when the number of pairs exceeds the threshold
if current_index_max - current_index >= MIN_PARALLEL_NODES {
    let updates: Vec<((usize, usize), H::Fr)> = (current_index..current_index_max)
        .step_by(2)
        .collect::<Vec<_>>()
        .into_par_iter()
        .map(|index| {
            // Hash two child nodes at positions (current_depth, index) and (current_depth, index + 1)
            let hash = self.hash_couple(current_depth, index);
            // Return the computed parent hash and its position at (parent_depth, index >> 1)
            ((parent_depth, index >> 1), hash)
        })
        .collect();

    // Insert computed parent hashes into the tree
    for (parent, hash) in updates {
        self.nodes.insert(parent, hash);
    }
} else {
    // Fallback to sequential update for small ranges
    for index in (current_index..current_index_max).step_by(2) {
        let hash = self.hash_couple(current_depth, index);
        self.nodes.insert((parent_depth, index >> 1), hash);
    }
}

• The most compute-intensive part lies in the hash_couple method. When the number of leaf updates exceeds MIN_PARALLEL_NODES, the updates are first flattened and parallelized. After that, all computed hashes are sequentially inserted into the tree.
• I experimented with using Arc and RwLock to allow hash updates during computation, and also tried DashMap for lock-free concurrent updates. However, benchmarks showed that the current approach—avoiding any locking during multi-threaded computation—is significantly faster.
• The optimal value for MIN_PARALLEL_NODES, as determined by the benchmark below, helps decide whether parallel execution is significant compared to a simple sequential update (e.g., in set or delete).

Min Parallel Nodes Threshold

Operations / Min Parallel Nodes	1	2	4	8	16	32	64
OptimalMerkleTree::set	7.8986 µs	6.6001 µs	6.4124 µs	6.4119 µs	6.4708 µs	6.5630 µs	6.5732 µs
OptimalMerkleTree::delete	15.613 µs	12.929 µs	13.150 µs	12.784 µs	12.742 µs	12.868 µs	12.756 µs
OptimalMerkleTree::override_range	2.4334 ms	2.4089 ms	2.3816 ms	2.3573 ms	2.3957 ms	2.4705 ms	2.6829 ms

• The benchmark results show that applying Rayon with a threshold of 1 (always parallelizing) adds unnecessary overhead. Raising the threshold to at least 2 improves performance by roughly 20% for small operations.
• A threshold of 8 appears to be optimal. Setting it too high causes top-level tree operations (with fewer nodes) to miss the benefits of parallelization — and when the number of nodes drops below 8, such as when computing higher and higher levels of the tree, sequential execution starts to become faster.

Example:

                    Root
                  ┌──┴──┐
                [8]    [9]           ← 2 nodes  → Sequential
               /  \    /  \
             [4] [5] [6] [7]         ← 4 nodes  → Sequential
            / \  / \  / \  / \
          [0][1][2][3][4][5][6][7]   ← 8 nodes  → Parallel
          /\ /\ /\ /\ /\ /\ /\ /\
         [  Leaf nodes: 16 total  ]  ← 16 nodes → Parallel