WAKU2-RLN-CONTRACT: resource reuse of expired memberships

[s-tikhomirov]

This document explains how resources from expired memberships are reused in the RLNv2 contract.

Background

The RLNv2 contract manages memberships on-chain, each containing details such as an ID commitment, rate commitment, and rate limit. Rate commitments are stored in a Merkle tree (IMT), representing the membership set, while other information is stored in a mapping called memberships. Each memberships element contains the index at which the corresponding rate limit is stored in the tree.

The contract’s logic follows a state transition model for memberships, as described in the specification. Memberships change states (e.g., Active, GracePeriod, Expired) over time or through user transactions. Different states allow different actions; for instance, extending a membership is only possible in the GracePeriod state.

Membership states are calculated just-in-time based on the current timestamp and membership info (such as start times and duration of states). Importantly, state transitions triggered by time progression are applied lazily.

The contract operates based on the memberships mapping, allowing the tree data (rate commitments) to be updated lazily when needed, depending on which resources we aim to save or reuse.

Types of Resources

Each membership consumes on-chain resources, including storage and gas for operations. Managing complex membership states can increase the chance of bugs, so we aim to balance correctness, complexity, and resource efficiency.

Three types of resources are relevant:

• Rate limit
• Tree indices (slots)
• Tree data (rate commitments)

Reusing Rate Limit

The contract enforces an upper limit on the total rate limit of all memberships in the tree. When a membership expires, it should no longer allow sending messages, but immediate updates to contract storage upon time progression are challenging. As a result, expired memberships do allow sending messages temporarily. However, expired memberships should not block new registrations due to rate limit restrictions. Therefore, it must be possible to erase expired memberships and reuse their rate limits.

Currently, this process is semi-automatic. To reduce complexity, the future holder of a new membership is responsible for finding expired memberships (if necessary) and providing a list of their ID commitments for erasure, allowing rate limits to be reused. If no list is provided, the contract does not attempt to reuse rate limits of expired memberships, and attempts to register the new membership using free, un-allocated rate limit only.

Reusing Tree Indices

Each tree element is indexed, and the contract tracks the nextFreeIndex, which points to the next available tree index (aka slot). When a membership is erased, its index becomes vacant, and reusing these indices is preferable to incrementing nextFreeIndex, which would bloat the tree.

The contract manages a list of reusable indices and overwrites the corresponding tree elements when registering new memberships, ensuring tree indices are reused automatically without user intervention.

Reusing Tree Storage

When a membership is erased and its index is later reused, there are two options for handling the associated tree data (rate commitments):

1. Erase the data eagerly:

   • Overwrite the tree element with zeroes: LazyIMT.update(merkleTree, 0, index);
   • Overwrite the element with the new rate commitment later: LazyIMT.update(merkleTree, rateCommitment, index);

2. Leave the data in the tree until it is overwritten:

   • Only overwrite the element when a new rate commitment is registered: LazyIMT.update(merkleTree, rateCommitment, index);

The first approach requires more gas for the extra update but reduces the tree size between the erasure and new registration. The second approach saves gas but keeps old data in the tree, which temporarily increases the tree size.

The choice of whether to erase or keep data depends on optimizing gas usage versus tree size. A suggested approach is:

• Do not erase data if erasure occurs during a new membership registration to reduce user gas costs.
• Provide an optional cleanup function to erase expired memberships and their data, which administrators can run if the tree size becomes excessive.

Summary

The proposed strategies for resource reuse in the RLNv2 contract are:

• Rate limit: Allow users to optionally submit a list of expired memberships to reuse their rate limits for new registrations.
• Tree indices: Automatically reuse indices of erased memberships for new registrations.
• Tree data: Keep rate commitments of erased memberships in the tree by default until overwritten; provide an optional cleanup function to erase rate commitments explicitly.