Rate-Limit-Nullifier V2

The idea was proposed by Lev Soukhanov @levs57

RLN V1

Current RLN circuit uses first-degree polynomial for shares generation (and slashing). Therefore, there is a limit - one message per epoch.

There have been attempts to make schemes in which the message limit per epoch is greater than one. For example N-RLN scheme. But this approach is very problematic, cause the bigger the limit - the more complicated is the circuit (more R1CS, etc.).

Update to V2

Instead of using higher degree polynomials we can just add additional input to hash-function (for a1 coefficient generation) - counter.

So, for the epoch limit n, the scheme will be:

• A(X) = a_0 + a_1 * x, where
  • a_0 - secret generated by user
  • a_1 - Hash(a_0, external_nullifier, k), where 1 <= k <= n
  • internal_nullifier = Hash(a_1)

Only thing we need to check is that the k parameter is in the range from 1 to n = epoch limit. Therefore user won't be able to use k > n, and if user uses same k twice they'll be slashed.

Thus, the scheme remains as simple as it was while at the same time providing more flexibility.

Additional info

There are also other cool features that come along with using this scheme:

• Internal nullifier value is different for different messages during the epoch (so it's more anonymous)
• It's more secure and resistant to algebraic attacks (which could arise in N-RLN scheme linked above)

Different Rate-Limits

By using this scheme we can create circuit, that will allow us to use different rate-limits for different users, for example based on their stake.

We can do that by commiting to not only our secret, but our secret and limit:

1. Registry (map) is stored on a smart-contract, where keys are public keys (pubkey = Hash(privkey)) of users and values are some metadata (for example limit number or stake amount);
2. Merkle tree, where leaves = Hash(pubkey, limit)

For example, the possible limit is 1000 (n = 1000), and each message costs 0.001 ETH (so you will have 1000 messages limit if you stake 1 ETH).

So, when you join app you attach the amount of stake you want and also send the pubkey and commitment = Hash(pubkey, limit), and zk-proof that the limit (public input for the circuit) you set for yourself is correct.

Signalling will use other circuit, where your limit is private input, and the counter k is checked that it's in the range from 1 to limit.