# 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.