Skip to main content

# RLN-v3: Towards a Flexible and Cost-Efficient Implementation

May 13, 2024
by
Aaryamann
7 min read

Improving on the previous version of RLN by allowing dynamic epoch sizes.

## Introduction​

Recommended previous reading: Strengthening Anonymous DoS Prevention with Rate Limiting Nullifiers in Waku.

The premise of RLN-v3 is to have a variable message rate per variable epoch, which can be explained in the following way:

- RLN-v1: “Alice can send 1 message per global epoch”

  Practically, this is `1 msg/second`

- RLN-v2: “Alice can send `x` messages per global epoch”

  Practically, this is `x msg/second`

- RLN-v3: “Alice can send `x` messages within a time interval `y` chosen by herself. The funds she has to pay are affected by both the number of messages and the chosen time interval. Other participants can choose different time intervals fitting their specific needs.

  Practically, this is `x msg/y seconds`

RLN-v3 allows higher flexibility and ease of payment/stake for users who have more predictable usage patterns and therefore, more predictable bandwidth usage on a p2p network (Waku, etc.).

For example:

- An AMM that broadcasts bids, asks, and fills over Waku may require a lot of throughput in the smallest epoch possible and hence may register an RLN-v3 membership of `10000 msg/1 second`. They could do this with RLN-v2, too.
- Alice, a casual user of a messaging app built on Waku, who messages maybe 3-4 people infrequently during the day, may register an RLN-v3 membership of `100 msg/hour`, which would not be possible in RLN-v2 considering the `global epoch` was set to `1 second`. With RLN-v2, Alice would have to register with a membership of `1 msg/sec`, which would translate to `3600 msg/hour`. This is much higher than her usage and would result in her overpaying to stake into the membership set.
- A sync service built over Waku, whose spec defines that it MUST broadcast a set of public keys every hour, may register an RLN-v3 membership of `1 msg/hour`, cutting down the costs to enter the membership set earlier.

## Theory​

### Modification to leaves set in the membership Merkle tree​

To ensure that a user’s epoch size (`user_epoch_limit`) is included within their membership we must modify the user’s commitment/leaf in the tree to contain it. A user’s commitment/leaf in the tree is referred to as a `rate_commitment`, which was previously derived from their public key (`identity_commitment`) and their variable message rate (`user_message_limit`).

In RLN-v2:

rate_commitment=poseidon([identity_commitment,user_message_limit])rate\_commitment = poseidon([identity\_commitment, user\_message\_limit])rate_commitment=poseidon([identity_commitment,user_message_limit])

In RLN-v3:

rate_commitment=poseidon([identity_commitment,user_message_limit,user_epoch_limit])rate\_commitment = poseidon([identity\_commitment, user\_message\_limit, user\_epoch\_limit])rate_commitment=poseidon([identity_commitment,user_message_limit,user_epoch_limit])

### Modification to circuit inputs​

To detect double signaling, we make use of a circuit output `nullifier`, which remains the same if a user generates a proof with the same `message_id` and `external_nullifier`, where the `external_nullifier` and `nullifier` are defined as:

external_nullifier=poseidon([epoch,rln_identifier])nullifier=poseidon([identity_secret,external_nullifier,message_id])external\_nullifier = poseidon([epoch, rln\_identifier]) \\ nullifier = poseidon([identity\_secret, external\_nullifier, message\_id])external_nullifier=poseidon([epoch,rln_identifier])nullifier=poseidon([identity_secret,external_nullifier,message_id])

Where:

- `epoch` is defined as the Unix epoch timestamp with seconds precision.
- `rln_identifier` uniquely identifies an application for which a user submits a proof.
- `identity_secret` is the private key of the user.
- `message_id` is the sequence number of the user’s message within `user_message_limit` in an epoch.

In RLN-v2, the global epoch was 1 second, hence we did not need to perform any assertions to the epoch’s value inside the circuit, and the validation of the epoch was handled off-circuit (i.e., too old, too large, bad values, etc.).

In RLN-v3, we propose that the `epoch` that is passed into the circuit must be a valid multiple of `user_epoch_limit` since the user may pass in values of the `epoch` which do not directly correlate with the `user_epoch_limit`.

For example:

- A user with `user_epoch_limit` of 120 passes in an epoch of `237` generates `user_message_limit` proofs with it, can increment the epoch by `1`, and generate `user_message_limit` proofs with it, thereby allowing them to bypass the message per epoch restriction.

One could say that we could perform this validation outside of the circuit, but we maintain the `user_epoch_limit` as a private input to the circuit so that the user is not deanonymized by the anonymity set connected to that `user_epoch_limit`. Since `user_epoch_limit` is kept private, the verifier does not have access to that value and cannot perform validation on it.

If we ensure that the `epoch` is a multiple of `user_epoch_limit`, we have the following scenarios:

- A user with `user_epoch_limit` of 120 passes in an epoch of `237`. Proof generation fails since the epoch is not a multiple of `user_epoch_limit`.
- A user with `user_epoch_limit` of 120 passes in an epoch of `240` and can generate `user_message_limit` proofs without being slashed.

Since we perform operations on the `epoch`, we must include it as a circuit input (previously, it was removed from the circuit inputs to RLN-v2).

Therefore, the new circuit inputs are as follows:

    // unchanged
    private identity_secret
    private user_message_limit
    private message_id
    private pathElements[]
    private pathIndices[]
    public x // messageHash

    // new/changed
    private user_epoch_limit
    private user_epoch_quotient // epoch/user_epoch_limit to assert within circuit
    public epoch
    public rln_identifier

The circuit outputs remain the same.

### Additional circuit constraints​

1. Since we accept the `epoch`, `user_epoch_quotient`, and `user_epoch_limit`, we must ensure that the relation between these 3 values is preserved. I.e.:

   epoch==user_epoch_limit∗user_epoch_quotient epoch == user\_epoch\_limit * user\_epoch\_quotientepoch==user_epoch_limit∗user_epoch_quotient

2. To ensure no overflows/underflows occur in the above multiplication, we must constrain the inputs of `epoch`, `user_epoch_quotient`, and `user_epoch_limit`. We have assumed `3600` to be the maximum valid size of the `user_epoch_quotient`.

size(epoch)≤64 bits size(user_epoch_limit)≤12 bits user_epoch_limit≤3600 user_epoch_limit≤epoch user_epoch_quotient<user_epoch_limit size(epoch) \leq 64\ bits \\ size(user\_epoch\_limit) \leq 12\ bits \\ user\_epoch\_limit \leq 3600 \\ user\_epoch\_limit \leq epoch \\ user\_epoch\_quotient < user\_epoch\_limitsize(epoch)≤64 bitssize(user_epoch_limit)≤12 bitsuser_epoch_limit≤3600user_epoch_limit≤epochuser_epoch_quotient<user_epoch_limit

### Modifications to external epoch validation (Waku, etc.)​

For receivers of an RLN-v3 proof to detect if a message is too old, we must use the higher bound of the `user_epoch_limit`, which has been set to `3600`. The trade-off here is that we allow hour-old messages to propagate within the network.

### Modifications to double signaling detection scheme (Waku, etc.)​

For verifiers of RLN-v1/v2 proofs, a log of nullifiers seen in the last epoch is maintained, and if there is a match with a pre-existing nullifier, double signaling has been detected and the verifier MAY proceed to slash the spamming user.

With the RLN-v3 scheme, we need to increase the size of the nullifier log used, which previously cleared itself every second to the higher bound of the `user_epoch_limit`, which is `3600`. Now, the RLN proof verifier must clear the nullifier log every `3600` seconds to satisfactorily detect double signaling.

## The implementation​

An implementation of the RLN-v3 scheme in gnark can be found here.

## Comments on performance​

- Hardware: Macbook Air M2, 16GB RAM
- Circuit: RLN-v3
- Proving system: `Groth16`
- Framework: `gnark`
- Elliptic curve: `bn254` (aka bn128) (not to be confused with the 254-bit Weierstrass curve)
- Finite field: Prime-order subgroup of the group of points on the `bn254` curve
- Default Merkle tree height: `20`
- Hashing algorithm: `Poseidon`
- Merkle tree: `Sparse Indexed Merkle Tree`

### Proving​

The proving time for the RLN-v3 circuit is `90ms` for a single proof.

### Verification​

The verification time for the RLN-v3 circuit is `1.7ms` for a single proof.

## Conclusion​

The RLN-v3 scheme introduces a new epoch-based message rate-limiting scheme to the RLN protocol. It enhances the user's flexibility in setting their message limits and cost-optimizes their stake.

## Future work​

- Implementing the RLN-v3 scheme in Zerokit
- Implementing the RLN-v3 scheme in Waku
- Formal security analysis of the RLN-v3 scheme

## References​

- Strengthening Anonymous DoS Prevention with Rate Limiting Nullifiers in Waku
- RLN Circuits
- Groth16
- Gnark
- Poseidon Hash
- Zerokit
- RLN-v1 RFC
- RLN-v2 RFC
- Waku

- Introduction
- Theory
  - Modification to leaves set in the membership Merkle tree
  - Modification to circuit inputs
  - Additional circuit constraints
  - Modifications to external epoch validation (Waku, etc.)
  - Modifications to double signaling detection scheme (Waku, etc.)
- The implementation
- Comments on performance
  - Proving
  - Verification
- Conclusion
- Future work
- References