RLN on mainnet - Implementation Roadmap

[s-tikhomirov]

This document outlines the steps to implement the mainnet-ready RLN smart contract as in the specification based on its current implementation deployed on testnet.

Implementation Stages

We suggest implementing the specification in multiple stages. The primary goal of this stage-based approach is to limit the scope of each stage, simplifying both implementation and testing.

Each stage description includes a membership state transition diagram representing the contract's state at the end of that stage (if it differs from the previous stage). After completing all stages, the diagram must match the one defined in the specification.

Note: membership states don't have to be stored explicitly. It is up to the implementation to either store membership states or derive the current state just-in-time based on timestamps and other data. The only requirement is that the contract behaves in the way described in the specification.

Add Rate-Limiting Constraints

Implement rate-limiting constraints on individual memberships and the entire membership tree.

Suggested steps:

• Define constraints on the minimum and maximum rate limits for a single membership.
• Define constraints on the maximum rate limit for all memberships in the tree.
• Enforce these constraints during membership registration.

Stub Membership State Management

Introduce the necessary fields and data structures for storing membership states and related data.

Each membership must store:

• Its current state.
• The timestamp when the state was assigned.
• The timestamp when the state becomes invalid.
• The address of the membership holder (msg.sender during registration).

Assign the Active state to a membership upon successful registration.

graph TD;
    NonExistent --> |"register"| Active;

Time-Related Membership State Updates

Membership state transitions can result from either time progression or user transactions. This stage focuses on time-based state updates.

Two time-based state transitions are implemented:

• From Active to GracePeriod.
• From GracePeriod to Expired.

graph TD;
    NonExistent --> |"register"| Active;
    Active -.-> |"time T passed"| GracePeriod;
    GracePeriod -.-> |"time G passed"| Expired;

Suggested steps:

• Define an internal state transition function:
  • Include a modifier to check that msg.sender is the membership holder.
  • Add modifiers to enforce constraints based on the current and new states (e.g., onlyActiveState, onlyGracePeriodState).
• Implement a function to update membership states when sufficient time has passed.

Membership Extensions

A membership holder may extend their membership by sending an extension transaction. An extension returns the membership to the Active state and is only possible from the GracePeriod state. This stage excludes deposit-related conditions.

graph TD;
    NonExistent --> |"register"| Active;
    Active -.-> |"time T passed"| GracePeriod;
    GracePeriod --> |"extend"| Active;
    GracePeriod -.-> |"time G passed"| Expired;

Suggested steps:

• Add a public extend function.
• Verify that msg.sender is the membership holder.
• If the membership state is recorded as GracePeriod, and sufficient time has passed for its transition to Expired, update the state to Expired.
• Check if the membership is in GracePeriod.
• If all conditions are met, extend the membership.

Add Membership Deposit Lock-Up and Withdrawal

To register a membership, a user must lock up a deposit. When a membership enters the GracePeriod, the holder may choose to either extend it or withdraw the deposit.

graph TD;
    NonExistent --> |"register"| Active;
    Active -.-> |"time T passed"| GracePeriod;
    GracePeriod --> |"extend"| Active;
    GracePeriod -.-> |"time G passed"| Expired;
    GracePeriod --> |"withdraw"| Expired;

Note: In the final state transition diagram, a withdraw action from GracePeriod leads to the Erased state instead of Expired. However, since membership erasure is not yet implemented at this stage, the Expired state is temporarily reused as the destination for both transitions from GracePeriod.

Suggested steps:

• Add data structures to store deposit data, including membership, amount, and the time deposited.
• Implement a function that calculates the required deposit amount based on the rate limit and a reference price (the price for 1 message per epoch). Ensure careful handling of monetary rounding.
• Enforce the deposit requirement during membership registration.
• Add a public withdraw function for deposit withdrawal:
  • Verify that msg.sender is the membership holder.
  • Check if the membership state is outdated and update it if necessary.
  • Enforce the conditions defined in the specification.
  • Upon successful withdrawal, update the membership state and associated metadata.

Erase Membership from the Tree After Deposit Withdrawal

A membership is erased either upon deposit withdrawal or when its slot is overwritten by another membership. This stage implements erasing the membership upon withdrawal.

graph TD;
    NonExistent --> |"register"| Active;
    Active -.-> |"time T passed"| GracePeriod;
    GracePeriod --> |"extend"| Active;
    GracePeriod -.-> |"time G passed"| Expired;
    GracePeriod --> |"withdraw"| Erased;
    Expired --> |"withdraw"| Erased;

Suggested steps:

• Implement an internal function to erase membership data from the tree.
• Modify the withdraw function so that it transitions from GracePeriod to Erased instead of Expired.
• Add support for withdraw from an Expired membership.

Reuse Tree Slots of Expired Memberships

Implement deposit withdrawal after the membership associated with that deposit is erased from the tree.

graph TD;
    NonExistent --> |"register"| Active;
    Active -.-> |"time T passed"| GracePeriod;
    GracePeriod --> |"extend"| Active;
    GracePeriod -.-> |"time G passed"| Expired;
    GracePeriod --> |"withdraw"| Erased;
    Expired --> |"withdraw"| Erased;
    Expired --> |"another membership reuses slot"| ErasedAwaitsWithdrawal;
    ErasedAwaitsWithdrawal --> |"withdraw"| Erased;

Suggested steps:

• Add a data structure to store information about ErasedAwaitsWithdrawal memberships and their deposits.
• Enable deposit withdrawal for holders of such memberships.

The state transition diagram should now match the final form as in the specification.

[richard-ramos]

Implement a function to update membership states when sufficient time has passed.

To reduce gas cost and need to interact with the smart contract, my suggestion would be to not have function used to update the membership state, but instead calculate the state (for Active/GracePeriod/Expired). Since we store the timestamp in which a membership is supposed to end, it should be trivial to determine whether a membership is in any of those states.

[richard-ramos]

Each membership must store:

• The timestamp when the state was assigned.

Could we skip storing this data? (to reduce gas cost). If this data is informative, the user could obtain such info from the event MemberRegistered(uint256 idCommitment, uint256 index) since it is possible to obtain the block number / timestamp from the event.

[richard-ramos]

Looking at the specs in https://github.com/waku-org/specs/blob/master/standards/core/rln-contract.md:

If a new membership A overwrites an Expired membership B: membership B MUST become ErasedAwaitsWithdrawal; the current total rate limit MUST be decremented by the rate limit of membership B; the contract MUST take all necessary steps to ensure that the keeper of membership B can withdraw their deposit later. Registration MUST fail if the total rate limit of Active, GracePeriod, and Expired memberships, including the one being created, would exceed R_{max}.

What happens if after overwriting the expired membership B, the rate limit available is still insufficient to register the new membership A. Should it attempt to overwrite more expired memberships?

EDIT: added a possible solution to this problem i here: https://github.com/waku-org/waku-rlnv1-contract/blob/d0472967827cb58ca1ad74d9a037210a5d204ee1/contracts/Membership.sol#L115-L146 in which i loop over expired memberships. Since this can be potentially an expensive operation, I was thinking to maybe add a freeExpiredMemberships function https://github.com/waku-org/waku-rlnv1-contract/blob/d0472967827cb58ca1ad74d9a037210a5d204ee1/contracts/Membership.sol#L226-L234 in which the sender can pass the list of memberships to free, since they can obtain this information offchain, altho this could end up with users prefering to remove the memberships with largest registered rateLimit instead of oldest, but perhaps this is not a problem? wdyt?

[s-tikhomirov]

Implement a function to update membership states when sufficient time has passed.

To reduce gas cost and need to interact with the smart contract, my suggestion would be to not have function used to update the membership state, but instead calculate the state (for Active/GracePeriod/Expired). Since we store the timestamp in which a membership is supposed to end, it should be trivial to determine whether a membership is in any of those states.

I agree that we should not proactively apply time-related state updates. In the sentense you quote, I meant an internal (or private?) function that would be called from within other (public) functions that depend on the state of the membership in question. For example:

1. a user calls extend;
2. check what the membership state should be now;
3. if that state doesn't match the stored state, update the stored state;
4. proceed with the extension.

Does this sound reasonable? Or are you suggesting we don't even store the state explicitly, and only calculate it just-in-time when needed?

[s-tikhomirov]

Each membership must store:

• The timestamp when the state was assigned.

Could we skip storing this data? (to reduce gas cost). If this data is informative, the user could obtain such info from the event MemberRegistered(uint256 idCommitment, uint256 index) since it is possible to obtain the block number / timestamp from the event.

My reasoning for storing the "assigned at" timestamp was that it is needed for tree slot reusal. As per specification:

The new membership SHOULD overwrite the membership that has been Expired for the longest time.

Thus the contract needs to know, for each Expired membership, since when it has been expired, to select the oldest one.

Two thoughts here:

1. Can the contract extract this data from the event as you describe, namely, from within register function, when deciding which slot, if any, to overwrite?
2. If this feature incurs a heavy gas penalty, we could skip it altogether (it is a SHOULD after all) and just overwrite any Expired membership if it exists, regardless of its age.

[s-tikhomirov]

What happens if after overwriting the expired membership B, the rate limit available is still insufficient to register the new membership A. Should it attempt to overwrite more expired memberships?

Great question.

From the storage-saving perspective, it doesn't matter whether we overwrite an old or a recently expired membership. The rationale to overwrite the oldest one was to incentivize user B to withdraw: as time progresses, their expired membership becomes more and more likely to get overwritten. However, one could assume that if users forget to withdraw their membersips, it's not because they want to continue using their rate limit beyond its expiry, but rather because they don't care enough to send a withdrawal transaction to retrieve such a small deposit (it might not even recoup the gas fees: a minimal deposit is 1 USD; fees on an L2 should generally be lower, but who knows).

I would suggest the following:

1. let the user optionally specify a list of memberships to overwrite;
2. if such list is not provided, greedily look up just one (or maybe a few?) expired memberships; if their combined capacity is insufficient - just use a new slot.

What would be most efficient way to choose memberships to overwrite then? I see these options:

• combine N highest-rated memberships (possible option: N = 1);
• combine N "random" memberships (e.g., consider them in the order they are stored / can be extracted efficiently).

Longer term, I could envision a mechanism where user A is incentivized (with a lower registration price) to opt-in to overwriting old slots (and thus consume more gas). Otherwise, we have an undesired consequence that the increased gas cost of looking up expired membership(s) is borne by whoever registers a new membership, and not by the holder of the expired membership who did not withdraw their deposit timely. However, for me this sounds like an overkill for the initial implementation.

[richard-ramos]

Does this sound reasonable? Or are you suggesting we don't even store the state explicitly, and only calculate it just-in-time when needed?

I suggest to not store state explicitly, since we still need to read some information from the membership like expirationDate and the gracePeriod to determine whether we want to advance state or not, as well as some states in which it's not possible to have them advance automatically and would depend on someone performing a transaction: i.e: GracePeriod and Expired.

The gas cost for reading from storage is 2100 for each attribute, compared to doing the calculation which is cheaper, i.e. + and > and >= and <= are all 3 gas opcodes each, so reading 2 attributes (the expiration date and grace period) and doing the calculation is cheaper to doing an additional read for the status (2100) + writing the new status to storage (an update costs 5000 gas).

What I propose instead is calculate it like this. Do note that I'm assuming the grace period can be updated by the contract owner and would not affect existing memberships (this is something i want to evaluate with you,):

MembershipData memory member = memberships[someId];

// If we need to determine if a membership is expired
bool isExpired = member.expirationDate + member.gracePeriod > block.timestamp;

// If we need to determine if a membership is in grace period
uint256 now = block.timestamp;
uint256 expirationDate = member.expirationDate;
bool isGracePeriod = now >= expirationDate && now <= expirationDate + member.gracePeriod;

For the other states we can determine them based on existence of data:

• Active: we assume a membership exists is active if exists in memberships mapping/array. Operations that require knowing if a membership is expired or in grace period would do so by using the suggested logic above
• Erased: the membership is removed from memberships mapping/array
• ErasedAwaitsWithdrawal: this status would not be required, we can have a balances mapping that tracks balances that can be withdrawn, and when we're erasing the membership, we'd increase the balance: balances[owner] += membership[someId].amount

[richard-ramos]

Thus the contract needs to know, for each Expired membership, since when it has been expired, to select the oldest one.

In the contract I'm proposing we can identify the expired memberships by storing all the memberships in a double-linked list. The head will always contain the oldest membership. And newer memberships are always added at the end. In the case of memberships that are extended, the process would be to:

1. For the selected membership, read the next and prev memberships and link them together
2. Link the selected membership with the current tail, and make the selected membership become the new tail. The transactions in ethereum are executed sequentially so it's safe to assume that a selected membership that is extended will automatically be the newer (since the new expiration date is calculated as the block.timestamp + expirationTerm.

[richard-ramos]

    let the user optionally specify a list of memberships to overwrite;
    if such list is not provided, greedily look up just one (or maybe a few?) expired memberships; if their combined capacity is insufficient 

I like this approach. I was applying the second option greedily looking for memberships but indeed this can end up being costly, and also have a separate function anyone could call to expire a list of memberships. I can try combining this into the behaviour you suggest. The user could then to obtain offchain the list of expired memberships and choose those whose total rate limit is enough to cover the rate limit they wish to acquire

just use a new slot

This part IMO can be skipped, that way we enforce the maximum total rate limit

[s-tikhomirov]

also have a separate function anyone could call to expire a list of memberships

Not sure I understand this part: do you mean "erase expired memberships from the tree"?

just use a new slot

This part IMO can be skipped, that way we enforce the maximum total rate limit

Hm, we do need an option to use a new slot, at least for the very first membership. What am I missing here?

[s-tikhomirov]

I've created a PR https://github.com/waku-org/specs/pull/34 where I make changes to the spec that stem from ongoing discussions.

The most substantial change so far concerns the logic aroung Expired memberships' slot reuse. In certain scenarios it may be quite gas-intensive. On the other hand, we're unlikely to hit the limit of tree capacity (2^20 elements) any time soon, whereas gas costs for slot reuse would (unnecesarily?) burden users who register new memberships.

I'd suggest this change to the spec (see commit):

• if there is enough capacity (unallocated + expired), then the new membership MUST be registered;
• if unallocated rate limit by itself is insufficient, but reusing some expired memberships would help, then the contract MUST reuse enough expired memberships to register the new membership;
• in other cases, it's up to the implementation to decide whether to reuse expired slot(s) or to register a new membership entirely within the unallocated rate limit;
• other decisions are moved to the implementation level, in particular, if expired slots are reused, how to select which ones? It may be the oldest, the largest by rate limit, the ones that have been expired for the longest time, or some other metric that makes sense from the implementation point of view.