# Merkle Tree-Based Revocation Mechanisms for Verifiable Credentials

Merkle trees are widely used in revocation systems for verifiable credentials, particularly in blockchain and smart contract contexts. They enable efficient and privacy-preserving revocation through two main approaches: membership proofs in a list of valid credentials and non-membership proofs in a list of revoked credentials. Benchmarks indicate that while membership proofs are faster to compute, non-membership proofs tend to be more efficient overall, as they require updates only when credentials are revoked, making them more scalable and cost-effective for real-world use.

## Membership Proof in a list of Valid Credentials

In this approach, users prove that their credential is included in a list of valid credentials.

The Incremental Merkle Tree (IMT) and the Sparse Merkle Tree (SMT)[^1] are commonly used for membership proofs.

LeanIMT[^2] is an optimized implementation of an IMT.

## Non-Membership Proof in a list of Revoked Credentials

In this approach, users prove that their credential is not included in a list of revoked credentials.

The SMT is commonly used for non-membership proofs.

## System Behavior for Each Approach

### Number of actions per approach.

Using membership proofs over a list of valid credentials means updating the tree every time a new credential is issued. In contrast, with non-membership proofs over a list of revoked credentials, updates are needed only when a credential is revoked. Since revoked credentials are usually far fewer than valid ones, this approach is much more efficient.

### Scalability of the approaches.

When trees become very large (e.g., millions of credentials), performing operations directly on them becomes inefficient and may reduce anonymity. In such cases, techniques like Private Information Retrieval (PIR) could help preserve privacy, but they remain too slow for production-scale use today.[^3]

## Membership and Non-Membership Proofs Tech Stack

- Both approaches are usually implemented with Circom + SnarkJS, using Groth16 as the proving system, which ensures fast client-side generation and low-cost smart contract verification.
- Since Groth16 is commonly used, these methods require a trusted setup per circuit. Membership and non-membership proofs are also compatible with other proving systems such as Plonk, Fflonk, and UltraHonk.

## Complexity Analysis

### Time Complexity

| Operation | LeanIMT | SMT |
| --------------------- | ---------------------------------------------------------------------- | ---------------------------------------- |
| Notation | n = number of leaves | n = maximum supported leaves |
| Insert | $O(\log n)$ | $O(\log n)$ |
| Generate Merkle Proof | $O(\log n)$ | $O(\log n)$ |
| Verify Merkle Proof | $O(\log n)$ | $O(\log n)$ |
| Search | $O(n)$ - requires scanning all leaves <br> $O(1)$ - if index is cached | $O(\log n)$ - guided traversal using key |

### LeanIMT

$n$: Number of leaves in the tree.

- The time complexity of Insert, Update, Generate Merkle Proof and Verify Merkle Proof is $O(\log n)$.
- Search operation has time complexity $O(n)$, since it requires traversing all the leaves to find the desired one, as the structure does not support direct leaf access.
- If the index of the leaf is saved (cached), since its position does not change when new values are added, the search cost improves from O(n) to O(1).

### SMT

$d$: Maximum depth of the tree.

- The time complexity of Insert, Update, Generate Merkle Proof and Verify Merkle Proof is $O(d)$.
- The search operation remains $O(d)$, as the key guides direct traversal from the root to the corresponding leaf.

### Space Complexity

| Structure | Complexity | Notation |
| --------- | ---------- | -------------------------------- |
| LeanIMT | $O(n)$ | $n$ = number of leaves |
| SMT | $O(n)$ | $n$ = number of non-empty leaves |

### LeanIMT
$n$: Number of leaves in the tree.

The space complexity of the LeanIMT is $O(n)$.

### SMT

$n$: Number of non-empty leaves in the tree.

The space complexity of the SMT is $O(n)$.

### Practical Depth Ranges

- LeanIMT: In practice, LeanIMTs are used with relatively small tree depths, typically between 10 and 32 levels, since they grow dynamically with the number of inserted elements. This corresponds to handling between roughly $2^{10}$ (≈ 1k) and $2^{32}$ (≈ 4B) leaves, which is sufficient for most incremental use cases.
- SMT: SMTs usually have fixed depths between 64 and 256, depending on the key space size. This depth is constant regardless of how many keys are actually used.
A tree with depth $d$ can theoretically address up to $2^{d}$ unique keys (leaves). In practice, only a very small subset of this key space is populated, and the SMT efficiently stores only non-default nodes.

### Complexity Analysis Insights

LeanIMTs scale with the amount of actual data, while SMTs scale with the size of the key space.
SMTs efficiently store key/value maps using direct access paths and sparse storage, whereas LeanIMTs rely on linear search.

## Benchmarks

LeanIMT and SMT implementations were benchmarked across Circom circuits, Node.js performance, browser performance, and on-chain costs to evaluate their overall efficiency and practicality.

### System Specifications and Software environment

All the benchmarks were run in an environment with these properties:

**System Specifications**

Computer: MacBook Pro

Chip: Apple M2 Pro

Memory (RAM): 16 GB

Operating System: macOS Sequoia version 15.6.1

**Software environment**

Node.js version: 23.10.0

Circom compiler version: 2.2.2

Snarkjs version: 0.7.5

### Running the benchmarks

- GitHub repository to run benchmarks: https://github.com/vplasencia/vc-revocation-benchmarks
- Browser App: https://vc-revocation-benchmarks.vercel.app

### Circuit Benchmarks

The circuits are written using the Circom DSL.

### Number of Non-linear Constraints

Fewer constraints indicate a more efficient circuit.



### Proof Size

Groth16 Proof Size is always fixed, independent of circuit size: ~ 805 bytes (in JSON format).

### ZK Artifact Size

#### WASM File Size
- SMT ≈ 2.2-2.3 MB
- LeanIMT ≈ 1.8 MB

#### ZKEY File Size
From tree depth 2 to 32:

- SMT: grows from 1.4 MB to 5.9 MB.
- LeanIMT: grows from 280 kB to 4.4 MB.

#### Verification Key JSON File Size
Constant at ~2.9 kB for both.

### Circuit Insights

- At every tree depth, SMT has between ~1560 and ~1710 more constraints than LeanIMT.
- While the absolute difference grows slowly with depth, the relative ratio decreases: for small depths, SMT can have over 4x more constraints, but by depth 32 it is only about 1.22x more.
- This shows that LeanIMT provides a large relative improvement for small trees, while still maintaining an absolute advantage for larger trees.
- The WASM artifacts remain almost constant in size for both (1.8 MB vs 2.3 MB).
- LeanIMT produces smaller proving keys across all depths. Both exhibit near-linear ZKEY growth as tree depth increases, but LeanIMT remains consistently lighter, up to 25-30% smaller than SMT.
- LeanIMT is more efficient overall since both its WASM and ZKEY files are lighter.

### Node.js Benchmarks


### Non-Membership ZK Proofs (SMT)

- Proof generation takes around 250-350 ms and scales mildly with tree depth, showing stable performance even for large trees.
- Proof verification is constant at roughly 9 ms across all depths.

### Node.js Insights

- LeanIMT is faster across all operations, from 1.5x (ZK proof generation) up to nearly 20x (Merkle proof generation).
- ZK verification times are similar, since they depend primarily on the proof system rather than the data structure.
- LeanIMT is ideal for systems that need frequent updates and fast client-side proof generation, while SMT is better when non-membership proofs are required.

### Browser Benchmarks

Benchmark setup: 1024 Members in the tree.

| Function | LeanIMT (ms) | SMT (ms) | LeanIMT Advantage |
| --------------------- | ------------ | -------- | ----------------- |
| Add Member | 0.12 | 2.67 | 22 x faster |
| Generate Merkle Proof | 0.03 | 0.17 | 5.7 x faster |
| Generate ZK Proof | 299.77 | 455.68 | 1.5 x faster |

### Browser Insights

- LeanIMT remains faster across all operations in the browser.
- Both SMT and LeanIMT are practical for browser-based applications.

### Smart Contract Benchmarks

- Insert 100 leaves into the tree.
- Verify one ZK proof with a tree of 10 leaves.

### Function Gas Costs

| Operation | LeanIMT (gas) | SMT (gas) | Difference | LeanIMT Advantage |
| --------------- | ------------- | --------- | ---------- | ----------------- |
| Insert | 181,006 | 1,006,644 | -825,638 | ≈5.6 x cheaper |
| Verify ZK Proof | 224,832 | 224,944 | ≈0 | Same |

### Deployment Costs

| Contract | LeanIMT (avg gas) | SMT (avg gas) |
| -------------- | ------------------------ | -------------------- |
| Bench Contract | 461,276 | 436,824 |
| Verifier | 350,296 | 349,864 |
| Library | 3,695,103 _(PoseidonT3)_ | 1,698,525 _(SmtLib)_ |

### Smart Contract Insights

- LeanIMT is significantly cheaper for insert operations, reducing gas consumption by around 82% compared to SMT.
- Verification costs are identical between both, as they share the same Groth16 verifier logic.
- Both implementations remain practical for mainnet deployment.
- LeanIMT costs a bit more to deploy due to the Poseidon library.

## Report Takeaways

- Membership proofs are faster to compute than non-membership proofs.
- Overall, LeanIMT offers better performance for membership proofs and client-side use cases, while SMT remains the preferred option when non-membership proofs are required.

## Next Steps

- Optimize as much as possible the SMT implementation on each programming language.
- Create a new and more efficient data structure for non-membership proofs.

## References

[^1]: Sparse Merkle Tree (SMT) paper: https://docs.iden3.io/publications/pdfs/Merkle-Tree.pdf
[^2]: LeanIMT paper: https://zkkit.org/leanimt-paper.pdf
[^3]: Ethereum Privacy: Private Information Retrieval - https://pse.dev/blog/ethereum-privacy-pir