# 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