RLN tree storage strategies

This document describes the various methods to store an RLN membership set (sparse merkle tree).

The two broad categories are, off-chain, and on-chain storage.

On-Chain Storage

This category involves storing the RLN membership set on-chain with various techniques.

1. Stateless storage

This strategy involves using a smart contract to merely serve as a coordination layer for registrations and withdrawals.

This is made possible by the usage of events emitted by the contract to signal new insertions/removals to be made by users to their local copy of the tree.

Solidity pseudocode:

function register(uint256 commitment) external {
    require(commitments[commitment] == 0, "double registration"); // there are other checks as well.
    commitments[commitment] = idCommitmentIndex;
    emit MemberRegistered(idCommitmentIndex, commitment);
    idCommitmentIndex += 1;
}

Advantages

• This seems to be the most gas efficient option, consuming about 45k - 70k gas
• Cheaper to register memberships, thereby lowering barrier of entry
• No race conditions, allows multiple registrations per block

Disadvantages

• Brings a lot of problems for coordination, since users have to maintain a copy of the tree locally and modify it every time there is a state change
  • Handling chain forks, reorgs gracefully
  • Handling missed insertions
• A user who just wants to be able to verify proofs MUST sync the whole tree, which is non-intuitive
• Complexities with having insertion time < block time of the chain

2. Full tree storage

This strategy involves using a smart contract with a full implementation of an incremental binary tree for registrations and withdrawals.

This is made possible by using @zk-kit/imt.sol/BinaryIMT.sol, which provides a BinaryIMT library for insertions, removals and root updates.

Solidity pseudocode:

BinaryIMTStorage binStorage;

function register(uint256 commitment) external {
    require(commitments[commitment] == 0, "double registration"); // there are other checks as well.
    BinaryIMT.insert(binStorage, idCommitmentIndex, commitment);
    emit MemberRegistered(idCommitmentIndex, commitment);
    idCommitmentIndex += 1;
}

function root() public pure {
    return BinaryIMT.root(binStorage);
}

Advantages

• The merkle root is available on-chain, allowing super-light verifiers who just need to look upon the state of the contract to be able to verify proofs
• Increases the barrier of entry (lower sybil count) by having registration intrinsically expensive, regardless of the staking strategy
• No race conditions, allows for multiple registrations per block
• No problem with coordination since the tree is stored onchain, storage can be saved on provers and verifiers

Disadvantages

• Expensive to register a membership, consuming about 800k gas

3. State transition proofs

This strategy involves using a smart contract which serves as a coordination layer for registrations, withdrawals and updates to the merkle root without having the whole tree on-chain.

This can be achieved by making use of "state transition proofs" of the merkle tree, which each user provides while registering to the membership set

Verifier private v;
uint256 public root;

function register(uint256 commitment, uint256[8] proof) external {
    require(commitments[commitment] == 0, "double registration"); // there are other checks as well.
    v.verifyProof(proof);
    emit MemberRegistered(idCommitmentIndex, commitment);
    // extract root from proof provided
    root = extractRoot(proof);
    idCommitmentIndex += 1;
}

Advantages

• The merkle root is available on-chain, allowing super-light verifiers who just need to look upon the state of the contract to be able to verify proofs
• Increases the barrier of entry (lower sybil count) by having registration intrinsically expensive, regardless of the staking strategy
• No problem with coordination since the tree is stored onchain, storage can be saved on provers and verifiers

Disadvantages

• Expensive to register a membership, should consume about 400k gas
• Race conditions when multiple registrations occur per block, only one will be valid, the rest will revert