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\mathrm{\_}commitment=poseidon([identity\mathrm{\_}commitment,user\mathrm{\_}message\mathrm{\_}limit])$$

In rln-v3:

$$rate\mathrm{\_}commitment=poseidon([identity\mathrm{\_}commitment,user\mathrm{\_}message\mathrm{\_}limit,user\mathrm{\_}epoch\mathrm{\_}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\mathrm{\_}nullifier=poseidon([epoch,rln\mathrm{\_}identifier])$$

$$nullifier=poseidon([identity\mathrm{\_}secret,external\mathrm{\_}nullifier,message\mathrm{\_}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 -

// 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\mathrm{\_}epoch\mathrm{\_}limit\ast user\mathrm{\_}epoch\mathrm{\_}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)\le 64bits$$

$$size(user\mathrm{\_}epoch\mathrm{\_}limit)\le 12bits$$

$$user\mathrm{\_}epoch\mathrm{\_}limit\le 3600$$

$$user\mathrm{\_}epoch\mathrm{\_}limit\le epoch$$

$$user\mathrm{\_}epoch\mathrm{\_}quotient<user\mathrm{\_}epoch\mathrm{\_}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

Comments on Performance

Proof generation was tested on an M2 Macbook Air, 16g Memory, around ~90ms with the additional constraints.