1  # Rate-limit Nullifiers
  2  
  3  For an application, each user maintains:
  4  
  5  * User registration
  6  * User interactions
  7  * User removal
  8  
  9  Points to note:
 10  
 11  1. Network cannot reconstruct your key unless you send 2 messages
 12     within 1 epoch, which well behaving clients don't do.
 13  2. Requires clocks between nodes to be in sync.
 14  3. You create an keypair which is added to the set. These have a
 15     cost to create which deters spam.
 16  
 17  ## User registration
 18  
 19  * There exists a Merkle tree of published and valid registrations.
 20  * There exists a set of identity commitments in order to maintain
 21    and avoid duplicates.
 22  * There exists a set of Merkle roots from the above tree which acts
 23    as a set of registrations that have been rate-limited/banned.
 24  
 25  ### Registration process
 26  
 27  Let $K$ be a constant identity derivation path.
 28  
 29  1. Alice generates a secret key $a_0$ and derives an identity
 30     commitment: $\hash(K, a_0)$
 31  2. Alice publishes the identity commitment.
 32  3. The Network verifies that the identity commitment is not part of the
 33     set of identity commitments, providing the ability to append it to
 34     the membership Merkle tree.
 35  4. Alice and the Network append the identity commitment to the set of
 36     identity commitments, and to the membership Merkle tree.
 37  5. Alice notes down the leaf position in the Merkle tree in order to be
 38     able to produce valid authentication paths for future interactions.
 39  
 40  ## User interaction
 41  
 42  For each interaction, Alice must create a _ZK_ proof which ensures
 43  the other participants (verifiers) that she is a valid member of the
 44  app and her identity commitment is part of the membership Merkle tree.
 45  
 46  The anti-spam rule is also introduced in the protocol. e.g.:
 47  
 48  > Users must not make more than N interactions per epoch.
 49  
 50  In other words:
 51  
 52  > Users must not send more than one message per second.
 53  
 54  The anti-spam rule is implemented with a Shamir Secret Sharing
 55  Scheme[^1]. In our case the secret is the user's secret key, and
 56  the shares are parts of the secret key. If Alice sends more than one
 57  message per second, her key can be reconstructed by the Network, and
 58  thus she can be banned. For these claims to hold true, Alice's _ZK_
 59  proof must also include shares of her secret key and the epoch.
 60  
 61  ### Interaction process
 62  
 63  For secret-sharing, we'll use a linear polynomial:
 64  
 65  $$ A(x) = a_1 x + a_0 $$
 66  
 67  Where:
 68  
 69  $$ a_1 = \hash(a_0, N_\text{external}) $$
 70  
 71  $$ N_\text{external} = \hash(\text{epoch}, \text{RLN\_ID}) $$
 72  
 73  $\text{rln\_identifier}$ is a unique constant per application.
 74  
 75  We will also use the internal nullifier
 76  $N_\text{internal}$ as a mechanism to make a
 77  connection between a person and their messages without revealing their
 78  identity:
 79  
 80  $$ N_\text{internal} = \hash(a_1, \text{RLN\_ID}) $$
 81  
 82  To send a message $M$, we must come up with a share $(x, y)$, given the
 83  above polynomial.
 84  
 85  $$ x = \hash(M) $$
 86  $$ y = A(x) $$
 87  
 88  We must also use a _zkSNARK_ to prove correctness of the share.
 89  
 90  1. Alice wants to send a message `hello`.
 91  2. Alice calculates the field point $(x, y)$.
 92  3. Alice proves correctness using a _zkSNARK_.
 93  4. Alice sends the message and the proof (plus necessary metadata) to
 94     the Network.
 95  5. The Network verifies membership, the ZK proof, and if the rate-limit
 96     was reached (by seeing if Alice's secret can be reconstructed).
 97  6. If the key cannot be reconstructed, the message is valid and relayed.
 98     Otherwise, the Network proceeds with User removal/Slashing.
 99  
100  ## User removal
101  
102  In the case of spam, the secret key can be retrieved from the _SSS_
103  shares and the Network can use this to add the Merkle root into the
104  set of slashed users, therefore disabling their ability to send future
105  messages and requiring them to register with a new key.
106  
107  ### Slashing process
108  
109  1. Alice sends two messages in the same epoch.
110  2. The network now has two shares of Alice's secret key:
111  
112  $$ (x_1, y_1) $$
113  $$ (x_2, y_2) $$
114  
115  3. The Network is able to reconstruct the secret key ($k=2$):
116  
117  $$ a_0 = \sum_{j=0}^{k-1} y_j \prod_{\begin{smallmatrix} m\,=\,0 \\ m\,\ne\,j \end{smallmatrix}}^{k-1} \frac{x_m}{x_m - x_j} $$ 
118  
119  4. Given $a_0$, a _zkSNARK_ can be produced to add the Merkle root from
120     the membership tree to the banned set.
121  
122  5. Further messages from the given key will not be accepted for as long
123     as this root is part of that set.
124  
125  ## Circuits
126  
127  ### Interaction
128  
129  ```zkas
130  {{#include ../../../script/research/rln/rlnv1/signal.zk}}
131  ```
132  
133  ### Slashing
134  
135  ```zkas
136  {{#include ../../../script/research/rln/rlnv1/slash.zk}}
137  ```
138  
139  [^1]: <https://en.wikipedia.org/wiki/Shamir's_Secret_Sharing>