# Rate Limiting Nullifier (RLN)
> This part would introduce how RLN works and what could be implemented based on RLN
#### RLN
RLN is the acronym of “**Rate Limiting Nullifier**”, it is a protocol aiming to **prevent spam attack** in an anonymous environment, where we do not expect a centralized server/ controller existing.
#### Spam Attack
##### What is a spam attack?
Spam attack uses **unsolicited messages** (these requests do not need permissions/prior request from the recipient) in order to **phishing, advertising or spread malware.**
There are different type of media can be used in spam attack:
- email
- text message (any texting system we used in social media today)
For example, the adversary can use their email account to send tons of advertising emails through SMTP, an application protocol used in transmitting mails on Internet. This is a method of spam attack, in which **those recipients would have no choice but to see these advertising emails in their mailbox.**
##### Web2 (Centralized Server Exists)
In web2 (the server and data is controlled by the company), it is quite easy to prevent spamming.
Say there is a Eve spam attacking the server via sending text messages to the others. However, this poor Eve’s action **would be detected by the server since Eve had to send the message by requesting the server.** (see the quote below)
Moreover, everything including Eve’s data or ip address is known by the centralized server, and thus it is extremely simple for the server to ban Eve from his ip address/ userId.In fact, many apps have rate limits while sending messages, so it is quite common in the real world.
> Client - Server model is used in this case, and most of companies use this model to provide their service.
>
##### Web3 (decentralized and anonymous)
In the future we imagine, there will be no centralized server controlling the data and governing. And most importantly, we assume this environment being totally anonymous with the usage of **Anonymous Identity** such as **Semaphore**.
In this case, it is really hard to find out a spam attacker, since we could not identify the identity of the spam attack.
Thanks to RLN, we could deal with this issue now. Basically, RLN uses **the same strategy just like what web2 servers uses.**
---
#### A High Level of RLN
There are 3 steps to in the protocol of RLN.
1. **Register**: user should use a Anonymous Identity to register in the system **with a stake (this is used as a mechanism of punishment)**
2. **Interaction**: users can interact the system such as sending text messages through the system.
- If there’s no one spamming, it would be fine. The users would enjoy their tranquility in the system.
- However, if there’s anyone spamming the others. The other people can act as a whistleblower, either to report the spammer to **reveal the identity** of spammer and **withdraw the piece of stake from the spammer**. (which is nice, we would love to earn the money)
3. **Withdrawal/Slashing**: user can use their Identity to redeem their stake locked in the contract before.
---
#### More Details
##### Shamir Secret Sharing - How do RLN reveal the secret?
RLN uses a technique called “Shamir Secret Sharing” in cryptography to reveal spammer’s Identity. What’s this?
Suppose we use the secret key as a point $**(0, a_0)**$, and we put it in a line ($y = a_1 * x + a_0$).
Every message in RLN is like a point on line $y$ and it is called a **share** in this system. For example, in the figure below, we can observe the secret $(0, a_0)$ and the $share_1(x_1, y_1)$ stands for the message sent to the system.
> $x_i$ are the message content itself, and $y_i$ are the calculate result from the equation.
>
So, in when the user send the first message to the system, it would be fine. **Nonetheless, if users send too many message, their anonymousness would no longer exist.**
**Here is how the secret key would be revealed.**
The spammer sent 2 message to the system, so here we have $share_1 (x_1, y_1)$ and $share_2 (x_2, y_2)$. Since everyone’s secret key $(0, a_0)$ is hiding in the linear equation: $y = a_1 * x + a_0$, the secret $a_0$ could be easily calculate via the 2 points offered by the spammer.
#### More more details
##### Circuits
RLN also uses the technique of zkSNARKs build up a entire anonymous system. Its circuits and constraints can be built in different languages, but for now I would introduce the **version in circom.**
##### Register
In the stage of registration, user should **offer a secret key** (the can be generated by decentralized server) **to register their anonymous identity** in this system. And with the help (concept) of Semaphore, we can easily verify users’ identities through the proof. Furthermore, the specific message limit for each user can be customized in a private input `userMessageLimit` in circuit. With this input, we could customize different limits to the different people in the system.
> Semaphore protocol can refer to [this link](https://semaphore.pse.dev/).
>
```rust
signal identityCommitment <== Poseidon(1)([identitySecret]);
signal rateCommitment <== Poseidon(2)([identityCommitment, userMessageLimit]);
// we can check if the user's identity is valid here
root <== MerkleTreeInclusionProof(DEPTH)(rateCommitment, identityPathIndex, pathElements);
```
output: `root`
##### Interaction
In this stage, first the system would check: **If user is sending too many messages**.
```rust
template RangeCheck(LIMIT_BIT_SIZE) {
assert(LIMIT_BIT_SIZE < 253);
signal input messageId;
signal input limit;
signal bitCheck[LIMIT_BIT_SIZE] <== Num2Bits(LIMIT_BIT_SIZE)(messageId);
signal rangeCheck <== LessThan(LIMIT_BIT_SIZE)([messageId, limit]);
rangeCheck === 1;
}
...
// messageId range check
RangeCheck(LIMIT_BIT_SIZE)(messageId, userMessageLimit);
```
By using this method, we could simply check if the `messageId` is less than the `userMessageLimit`which is quite nice since we can deal with individual data in the circuit.
After that, the system calculate the $y$ for the sending message $x$ and a important value $nullifier$ which $y$ and $nullifier$ being output in the system.
```rust
// SSS share calculations
signal a1 <== Poseidon(3)([identitySecret, externalNullifier, messageId]);
y <== identitySecret + a1 * x; // x: hashed message content (public input)
// nullifier calculation
nullifier <== Poseidon(1)([a1]);
```
output: `y` & `nullifier`
> You might notice that there’s a **external nullifier (public input)** here and it varies in different applications using RLN to prevent the same identity leaking from app A to app B.
>
##### Slashing
The 3 outputs would be revealed in the system, but what can we do with these things?
In the system, since we would check the range of the messageId, users can only **send message indexing from 0 to (userMessageLimit-1) (0 ≤ messageId < userMessageLimit).**
If a spammer is sending too many messages, say n messages (`n == userMessageLimit`), **the spammer won’t be able to pass the test in** `RangeCheck()`**, and thus s/he would need to submit another message with reused messageId** (let say the spammer send `12` for its messageId).
However, the nullifier (`= Hash(Hash(identitySecret, externalNullifier, 12))`) is calculated this the the past period (imagine the shares $(x_i, y_i)$ are stored in a decentralized server.
Therefore, the output `y` can be used to reveal the spammer’s identity.
Whenever, the other users reveal the spammer’s identity, they can be this `slash()` function to make the locked stake from the spammer to their own asset.
```solidity
function slash(uint256 identityCommitment, address receiver, uint256[8] calldata proof) external {
require(receiver != address(0), "RLN, slash: empty receiver address");
User memory member = members[identityCommitment];
require(member.userAddress != address(0), "RLN, slash: member doesn't exist");
require(member.userAddress != receiver, "RLN, slash: self-slashing is prohibited");
require(_verifyProof(identityCommitment, receiver, proof), "RLN, slash: invalid proof");
delete members[identityCommitment];
delete withdrawals[identityCommitment];
uint256 withdrawAmount = member.messageLimit * MINIMAL_DEPOSIT;
uint256 feeAmount = (FEE_PERCENTAGE * withdrawAmount) / 100;
token.safeTransfer(receiver, withdrawAmount - feeAmount);
token.safeTransfer(FEE_RECEIVER, feeAmount);
emit MemberSlashed(member.index, receiver);
}
```
##### Withdrawal
The last step in the system would be redeem the stake from the contract. However, we still need to check the users’ identity and address; otherwise this would be withdrawn by other users.
```solidity
template Withdraw() {
signal input identitySecret;
signal input address;
signal output identityCommitment <== Poseidon(1)([identitySecret]);
// Dummy constraint to prevent compiler optimizing it
signal addressSquared <== address * address;
}
```
By the end of the process, we would use the function `withdraw()` on smart contract to redeem the stake.
```solidity
function withdraw(uint256 identityCommitment, uint256[8] calldata proof) external {
User memory member = members[identityCommitment];
require(member.userAddress != address(0), "RLN, withdraw: member doesn't exist");
require(withdrawals[identityCommitment].blockNumber == 0, "RLN, release: such withdrawal exists");
require(_verifyProof(identityCommitment, member.userAddress, proof), "RLN, withdraw: invalid proof");
uint256 withdrawAmount = member.messageLimit * MINIMAL_DEPOSIT;
withdrawals[identityCommitment] = Withdrawal(block.number, withdrawAmount, member.userAddress);
emit MemberWithdrawn(member.index);
}
/// @dev Releases stake amount.
/// @param identityCommitment: `identityCommitment` of withdrawn user.
function release(uint256 identityCommitment) external {
Withdrawal memory withdrawal = withdrawals[identityCommitment];
require(withdrawal.blockNumber != 0, "RLN, release: no such withdrawals");
require(block.number - withdrawal.blockNumber > FREEZE_PERIOD, "RLN, release: cannot release yet");
delete withdrawals[identityCommitment];
delete members[identityCommitment];
token.safeTransfer(withdrawal.receiver, withdrawal.amount);
}
```
#### Conclusion
RLN is a decent protocol solving the problem in decentralized and anonymous world with the help of zkSNARKs, Shamir Secret Sharing and stake mechanism. What’s more, it can be used in more applications such as voting system, or rate limiting cache access (CDN), where can be implemented in the real world (not only on blockchain).
Sign in with Wallet
Connect another wallet