# rln-v3 PoC
## Introduction
The premise of rln-v3 is to have 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 per Alice’s user set epoch. Bob can send `w` messages per Bob’s user set epoch”
- Practically, this is `x msg/y seconds`
What rln-v3 allows is higher flexibility and ease of payment/stake for users who have more predictable usage patterns, and consequently, more predictable bandwidth usage on the network, 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`, which is much higher than the usage she would have, and hence, she would have to overpay 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, hereafter referred to as `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])
$$
In **rln-v3:**
$$
rate\_commitment = poseidon([identity\_commitment, user\_message\_limit, user\_epoch\_limit])
$$
### Modification to Circuit Inputs
As we know previously, 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`, with the same `external_nullifier`, where the `external_nullifier` and `nullifier` are defined as below
$$
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, and therefore, 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).
However, 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 it is kept private, the verifier does not have access to that value, and hence 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 epoch is not a multiple of `user_epoch_limit`
- A user with `user_epoch_limit` of 120, passes in an epoch of `240`, can generate `user_message_limit` proofs, without being slashed
Since we perform operations on the `epoch`, we must include it as a circuit input, which was previously removed from the circuit inputs to rln-v2. Therefore, the new circuit inputs are as follows -
```jsx
// 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`, the `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
$$
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) \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\_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 proofs, they should maintain a log of nullifiers seen in the last epoch, 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.
However, with the rln-v3 scheme, we need to increase the size of the nullifier log used, which previously cleared itself every second, to now, the higher bound of the `user_epoch_limit`, which is `3600`. So 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 can be found here - [https://github.com/vacp2p/gnark-rln/blob/9b05eddc89901a06d8f41b093ce8ce12fd0bb4e0/rln/rln.go](https://github.com/vacp2p/gnark-rln/blob/9b05eddc89901a06d8f41b093ce8ce12fd0bb4e0/rln/rln.go)
## Comments on Performance
Proof generation was tested on an M2 Macbook Air, 16g Memory, around ~90ms with the additional constraints.