感謝 Paul (Tzu Chun) Yu Chung Fu-Chuan 的 review
簡介
- RLN是一種零知識裝置，可為去中心化、匿名環境下的應用程式提供防止 Spam 攻擊的解決方案。
- 所謂 Spam 攻擊，在傳統的網路環境上指的是透過大量的垃圾訊息，致使真正使用產品的人無法正常使用的一種攻擊手段，比如在收發 Email 的平台，傳送大量廣告或者夾帶惡意軟體的訊息，讓使用者無法正常接收重要的訊息
- 而在去中心化的世界中，想像一個聊天軟體，其中使用者是匿名的。現在，每個人都可以發送無限量的訊息，但我們卻沒有能力踢出任何成員，因為垃圾訊息發送者是匿名的，在這種情況下這個聊天軟體很快就會淪為各種廣告的遊樂場而無法正常使用
為什麼需要使用 RLN
- 在匿名環境下，對於 application 來說無法分辨正在使用產品是人或者機器人，比如常見的投票場景，如果投票人是匿名並且沒有任何防止機制的話，投票結果就可以透過人為操控(比如透過bot產生大量地址影響投票結果)
- 在 Semaphore 中，我們利用 nullifier 去限制某個人可以送 signal 的次數，但當這個人不遵守規則的時候我們也不能對他做什麼懲罰他(只能拒絕請求)，因為我們也無法連結這個 signal 與特定的人
如何達成
分別由三個部分組成，分別是:
- 使用者註冊
- 使用者互動
- 使用者刪除
使用者註冊
在註冊階段，使用者需要產生 secret key，可以想像是一把使用者的私鑰，用來代表自己的身份，之後我們可以透過這把私鑰產生 identity commitment (可以理解成公鑰)，並儲存在 Merkle tree 的其中一個 leaf 裡面
此時有個部分需要注意，這個 identity commitment 需要與使用者提供的 「抵押」做連結，如此才可以懲罰使用者，原文如下:
RLN wouldn’t work if there were no punishment for spam; that’s why to become a member, a user has to register and provide something at stake
此為RLN的特點，也就是下面一系列機制的緣起
使用者互動
一般來說當我們想要防止某種 spam 攻擊時，最簡單的做法是我去限制每個 user 請求的速率，簡單來說就是「當使用者在 X 時間(epoch)內傳送超過 Y 次請求，我們要去限制他」，要在匿名的情境下達到這個需求，RLN 引入了 Secret Sharing 的概念
所謂 Secret Sharing 指的是我們把 secret key 分成幾部分，當使用者與 application 互動在一段時間內達到某個次數後，我們即可以拼湊出使用者真正的 key
我們在高中有學過，對一個多項式來說，我們可以利用拉格朗日插值法透過已知的點求得(逼近)方程式，比如說有以下 (x, y) 的組合:
則由以上可以得出通過這三點的多項式可以表示為:
其中的細節就先不贅述，只要知道這個特性後，我們就可以把建立一個多項式 secret key，其可以分割成 k 個部分，而如果我們每次與使用者互動時都揭露一部分(類似得到方程式的一個解)，當使用者提供了 k 個點後我們即可以還原他的 secret key，此即是 Shamir’s Secret Sharing (SSS) 的精神
所以此時對於 user 來說，只要他每次送出訊息的時候帶有這個多項式上的一點 (x,y)，當他提供 k 個點以後他的 secret key 就可以被還原出來了
使用者刪除
RLN最後一個機制是他允許任何知道某使用者 secret 的人可以將這個使用者從 Merkle Tree 中刪除，當使用者的 secret 與抵押品掛勾時，RLN會把這些抵押品送給第一個提供 secret 的人
實作細節
首先先借用官網的一張圖，這邊分成幾個部份去看，並且我會搭配官方提供的 POC application 下去講述整個流程，主要是自己在看的過程感覺還是需要實際看到程式碼才比較能理解各個步驟的 input/output
註冊
先從圖上的右上方開始，首先使用者一開始會產生 secret key，經由 hash 過後會變成 identity commitment，接著在註冊的階段會判斷有無重複並塞入 Merkle Tree 裡面(圖右下角)，這邊文件有特別提到他們使用了 Incremental Merkle Tree 來減少 gas 的消耗
在註冊之後，使用者拿到幾個資訊 (leaf index, witness, rln identifier)，第一個是代表你的 commitment 位於 Merkle Tree 的位置，witness 則是一組資訊(我的理解是他是包含 Merkle tree 的 root, path element 等等一系列的資訊，足以使 user 在沒有提供 secret 的情況下證明他在 tree 裡面，詳細witness包含的內容可以參考這裡)，rln identifier 則是每個 application 不同的一組亂數
P.S. 當其他 user 註冊的時候，所有的已存在的 user 都需要去拿新的 witness 才能傳送訊息(因為 witness 會改變)
互動
當使用者真正要送出訊息的時候，他必須要提供
- witness (也就是自己是成員的證明)
- 符合多項式上的一點 (x,y)
- 正確的 nullifier
首先第一點由剛剛 register 步驟的 output 取得，接著第二點 x 的部分以使用者的 message(signal)，計算出對應的 y 值，在最基礎的 RLN 中，由於我們的多項式是一個單純的線性方程式
我們設定 a0 為 secret key，也就是圖上的右邊，而 a1 為hash(a0, external nullifier) 如此一來把 x 帶入即可得到 y 值，這邊就完成了第二點
其中 external nullifier 的部分可以參考圖左上，主要是由 epoch (代表一段時間)與 rln identifier (每個 application 會有的獨特 id)，之所以會有這兩個變數加入的原因是，我們想要的是這個使用者在「這個application」的「這段時間」 只能傳送一次訊息，避免使用同一組身份在兩個 application 登入時會意外揭露自己的 secret
最後是 internal nullifier，也就是圖中左下的部分，主要是由剛剛算出來的 a1 做hash可以得到，具體用途等等再說
刪除
在刪除的步驟中，文件中寫到，只要實作「第一個回報某個使用者 secret key 的人可以取得這個 user 的抵押品」這個 function，即可提供兩個功能:
1. 使用者自行退出
2. 使用者因為 spam 行為被揭露 secret，並由揭露的使用者取得抵押品
這個功能很好理解，但是在實際運行的時候我們還要考慮另一個問題，當任何人發送 message 時，我們要如何檢查哪個 user 已經超過 rate limit 需要被懲罰呢？比較直觀的的方法是去對每兩組(x, y)都去計算一條多項式，但是這種方法太沒效率並且只能在多項式的次方較小的時候才有可能
所以這邊RLN的做法是，提供一個可以公開(不會讓使用者被揭露)但是對於這個時候的使用者是唯一的值 internal nullifier，其值為 hash(a1)，如此可以快速比對某個人在這個時間是否有送超過兩次訊息，有的話再進行後續的計算
延伸 — NRLN
在上面的案例中，我們使用的是一個簡單的線性方程式，所以當使用者公開兩個點以上，secret 就被揭露了，也就是說這個方程式只能處理 「一段時間只允許使用者送出一次訊息」 這種情境，但現實情況中我們更多的是需要 「在一天內可以發送 100 次請求」這種類型的限制，所以我們的方程式需要一點點的修改
在 @libsem/protoco 或 nrln.circom 中，我們可以看到 RLN 是怎麼實作這個部分的
與原本的方程式相比，大部分的計算部分是一樣的，主要的變化就是我們的 secret 從一個單一的數值變成一個 array 了，另外原本的方程式會因為傳入的 limit 參數不同而變成不同次方項的方程式，可以整理成以下:
- a0 不變
- a1 變為 coeffe[0] = hash(identity_commitment[0], epoch)
- coeffe[1] = hash(identity_commitment[1], epoch)
- coeffe[2] = hash(identity_commitment[2], epoch)
- ….
- coeffe[limit-1] = hash(identitySecret[limit-1], epoch)
而此時整個 Secret Sharing 的方程式就可以寫成
透過以上更改，就可以在使用者傳送超過 limit 次數後才揭露整個使用者的身分並且依舊滿足之前的各種
Q & A
底下是幾個我們在研究這個 Protocol 的時候會想知道的問題:
Q: 在使用者刪除的機制中，secret 被揭露出來代表的是? 另外，有提供吹哨者機制嗎?
A: 第一，與系統在某epoch互動太多次的人會被視為是Spammer，也就是攻擊系統的人，第二，吹哨者機制的部分文件中好像沒有看到相關的敘述，比較像是任何人都有經濟誘因去檢舉其他人
Q: 對於 user rate limit 的限制，是如何只在這段時間生效 (是怎麼讓這個 user 在下個時段還可以繼續送訊息不會被揭露)
A: 參考實作細節的圖片，在產生的多項式裡面 a1 的部分由 external nullifier 構成，而 external nullifier 又是由 epoch & rln nullifier 組成，其中的epoch代表時間段，所以不同時間段的多項式會不一樣，也就避免使用者在下個 epoch 送的 message 會揭露上個 epoch 的多項式
結語
在去中心化且匿名的世界中想要做到傳統 Web 2已經習以為常的功能，看起來相對之下複雜了不少，Rate Limit 這個功能看起來只是一個很普通不過的基礎功能，但相信在類似的基礎建設都慢慢被實做出來的一天，到最後所有人都可以很方便的在去中心化的世界實現各種各樣的功能與應用。
Reference
Docs
RLN spec (canonical Poseidon + IncrementalQuinTree)
Video
Project
https://github.com/akinovak/libsemaphore-modules
