# SASSAFRAS

> [!Warning]
> 建議先閱讀 BABE 以及 VRF 相關內容

BADASS BABE 是一個固定時間的區塊生產協議，以確保每個時間段內精準的生成一個區塊，並且透過 `zk-SNARKs` 來建構 `ring-VRF` 以確保區塊生產過程中的隱私性。

> [!Tip]
> - 解決 slot 中可能沒有區塊或是有多個區塊被生產
> - 解決抽籤過程中缺乏匿名性的問題 (攻擊者將會提前知道區塊生產者是誰)

## 概要

> [!Tip]
> **重點**：為了改善 BABE 抽籤缺乏匿名性的問題，採用以下兩點
> - 透過 zk-SNARK 驗證抽獎券的提交者是一位被提名的驗證者
> - 透過隨機轉發找到一位代理人將抽獎券公開到鏈上

在每一個 epoch 開始時，我們會透過抽籤的方式 (Block-Production-Lottery)，確認每一位驗證者生產區塊的順序，每一位驗證者使用相同的 epoch 隨機數 (Randomness) 進行簽章，並會產生並公開一張抽獎券 (VRF output) ，可以透過該驗證者 public key 來驗證這張抽獎券，但這樣的驗證計算，也將會導致中獎者(獲得該 slot 區塊生產的權利)提早被知道是誰，而成為被攻擊的目標。
-> ==說出是誰中獎就會被扁==

為了保持區塊生產順序的匿名性，我們不行事先驗證該抽獎券是否中獎。否則該驗證者的身份會提早曝光，等到抽籤後才驗證該抽獎券的真實性，由誠實的驗證者聲明該抽獎券是他所擁有的，但是這樣任何人都可以送出假的抽獎券，但插槽將預先分配給他們，可能會造成最後可能沒有人有中獎 (假的抽獎券無法獲得 slot 的區塊生產權利)，這將違背該協議的目的 (想要確保每一個時段都能生成一個區塊)。
-> ==如果提前公開哪個票中獎會造成大家都偽造==

為了解決這個問題，我們需要在隱私保護下進行該抽獎券的驗證，當這位誠實的驗證者送出抽獎券時，應該要附上 SNARK 的聲明：「這是我使用我的 public key 以及 VRF 輸入所產生的抽獎券 (VRF 輸出)，我沒有告訴你我的 public key, 但是我的 public key 是在被提名的驗證者中的其中一個」，這將可以在抽籤前被驗證這個提交者，他是一位被提名的驗證者。

以上方法可以讓這張抽獎券具有匿名性 (因為沒有實際公開該驗證者的 public key, 因此不知道實際上是誰產生了這張抽獎券)，但是還需要一個方法讓該抽獎券匿名的發布到鏈上，有一種方法可以簡單的達成我們的目標，就是讓該驗證者將此抽獎券轉發到另一位驗證者手上，透過這位驗證者(代理人)將抽獎券公佈到鏈上。

> [!Note]
> TODO: zk-SNARK 介紹

## Plan

在一個 epoch $\varepsilon_m$ 中我們使用 BABE randomness $r_m$ 作為環形 VRF (ring VRF) 的輸入，將產生出一系列的輸出，並且將其發布到鏈上，當這些輸出被最終確定時，會對他們進行排序，這個排序將會決定 epoch $\varepsilon_{m+2}$ 中的區塊順序。

> [!Note]
> 一般的 VRF 輸出是一個 `value` 以及 `proof`，並且可以透過簽名者的 public key 對其進行驗證，這將導致該 VRF 輸出與特定的簽名者存在明確的連結性，不具有匿名性。
> ### Ring-VRF
> - 匿名性：簽名者會隱藏在一組(環)集合中，驗證者只能知道該輸出來自於這個集合(環)中的成員之一，但是無法知道具體是誰。

## Parameters

- $V$：被提名的驗證者(Nominated Validators)集合
- $s$：該 epoch 的 slot 數量 (每 6 秒一個 slot)
- $x$：冗餘因子(redundancy factor)：預期在 $s$ 個 slot 中，產生 $xs$ 張抽獎券，我們設定 $x = 2$
- $a$：每個驗證者在該 epoch 嘗試產生的抽獎券數量
- $L$：限制允許傳播 (gossip) 的抽獎券數量，以防止 DoS 攻擊

## Keys

除了每個驗證者自己的基本密鑰外，使用了一組基於 `SNARK-friendly curve` ([Jubjub](https://bitzecbzc.github.io/technology/jubjub/index.html)) 的密鑰對

- SNARK-friendly 密鑰對:
- 每一位驗證者透過 `SNARK-friendly curve: Jubjub` 產生密鑰對: $sk, pk$
- 這組密鑰對必須要再每個 epoch 隨機性生成前產生，以確保產生過程是不改竄改的。（**FIXME: 為什麼?**)
> [name=yu2C] 先產生 key pair 然後才輸入 function 產生 output。otherwise, 就有可能一直用不同的 key-pair 去試，直到產生想要的結果。

- 密鑰生成公式：
$$
KeyGen_{RV RF}:\lambda, r \mapsto (sk, pk)
$$

$\lambda$：安全參數 (**FIXME: 不太清楚**)
$r$：epoch 隨機數
- 聚合公鑰 (aggregated public key)
- 將所有驗證者的公鑰，透過 Merkle Tree 的方式來產生該聚合公鑰
$$
\text{Aggregate}_{\text{RV RF}} : v, \{ pk_v \}_{v \in V} \mapsto (apk, ask_v)
$$

#### 輸入

$v$：某個驗證者
$pk_u$：該驗證者的公鑰

#### 輸出

$apk$：聚合公鑰
$ask_v$：共路徑 (copath)

> [!Note]
> 共路徑 (copath):
> - 這是一組節點集合，記錄哪些節點與該驗證者公鑰進行 hash 可以產生成聚合公鑰 (Merkle Root)
> - 該資料集後可以用來證明，該驗證者的公鑰存在於驗證者集合中。

> [!Note]
> TODO: Merkle Tree 介紹

## Phases

以下將介紹當一組新的驗證者被提名後的流程

### 1. Setup

每一個 epoch，當一組新的驗證者 $V$ 被提名或是其他參數被變更時，協議會重新初始化，並設定新的閾值 $T$ 以及聚合公鑰 (aggregated public key) $apk$

每一個驗證者 $v \in V$ 應該執行以下步驟：

1. 計算閾值 $T$：
- 公式： $T = \frac{xs}{a|{V}|}$
- 該閾值用來防止攻擊者預測某個區塊生產者將會生產多少個額外的區塊 **(FIXME: 不太清楚，如果攻擊者知道了會發生什麼事？)**
2. 計算聚合公鑰(aggregated public key)及該驗證者公鑰的共路徑(copath)
$$
(a_{pk}, spk_v) = \text{Aggregate}_{RVRF}(v, \{ pk_v \}_{v \in V})
$$
3. **(FIXME: 看不太懂)** 獲得 SNARK CRS (Common Reference String)，並進行檢查以確認他是否有被竄改過，或是在驗證者 $v$ 之前是否已經完成這項檢查。

> [!Note]
> **FIXME: 不太清楚**
> CRS (Common Reference String) 是用於 SNARK 計算的一組公開參數，通常使用於系統設置階段生成，所有參與方必須依賴這些參數來進行證明和驗證。
> - 這是一組固定且公開的參數，用於生成和驗證 SNARK 證明。
> - 一旦 CRS 被竄改，系統的完整性和安全性將會有問題。

### (TODO: 待整理) 2. VRF generation Phase

該階段的目的是要將 $s$ 張抽獎券(VRF 的輸出)，公開發布到鏈上。(這數量不被保證，但是預期的數值將是 $xs$)

> $xs$: 冗餘因子 * slot 的總數

#### Randomness

在每個 epoch $\varepsilon_m$，我們使用隨機數 $r_m$ 提供給 BABE

$$
r_m = H(r_{m-1}, m, \rho_{m})
$$

我們使用 $r_m$ 作為 ring-VRF 的輸入，這對應的票券(VRF output)將會被使用在 $\varepsilon_{m+2}$

$\rho$ 是 BABE VRF 的輸出，

我們會水平執行 VRF 以及 ring-VRF

ring-VRF 的輸出會在 epoch $\varepsilon_m$ 時揭露，因此若直接使用 ring-VRF 作為隨機來源，下一個 epoch 的隨機數 $r_{m+1}$ 可能會提早暴露，這會破壞系統的隨機性及安全性。

因此我們選擇使用那些直到對應區塊生成後才揭露的 VRF 輸出

假如我們有一個 VDF (Verifiable Delay Function), 那麼所有參數和結果都要在前一個 epoch 中確定

$$
r_m = VDF(H(r_{m-2}, m-1, \rho_{m-1}))
$$

$\rho$ 是 BABE VRF 從 $\varepsilon_{m-2}$ 的輸出

VDF 將會執行在 $\varepsilon_{m-1}$ 開始

因此這個輸出將會在 $\varepsilon_m$ 開始之前在鏈上

### (TODO: 待整理) 3. Publishing Phase

我們希望至少多數的 slot 的區塊生產者是預先不會被知道的，因此，行為有善的驗證者應該保持他們的中獎票券為私有的 (不公開)，為了達到此目的，驗證者不會立即公開他們 VRF 的輸出，而是將這個輸出傳遞給令一個隨機選擇的驗證者 (代理驗證者)，由代理驗證者進行公開。

驗證者 $v$ 選擇其他驗證者 $v^{\prime}$，基於輸出 $out_{m,v,i}$，驗證者將選擇 $k = out_{m,v,i}mod|V|$，送出中獎票券給第 k 的驗證者(在固定序列中)

那麼該驗證者對於該訊息進行簽章：

$$
(v, l, env^{\prime}(out_{m,v,i}, \pi_{m,v,i}))
$$

$enc_v^{\prime}$：代表驗證者 $v^{\prime}$ 公鑰進行加密的過程
$l$： 對於中獎票券進行編號，0 到 $L-1$, 假如有超過 $L$ 個輸出小於 $T$，我們只進行 gossip 最低的 $L$ 個輸出，這個限制為了防止驗證者在網路上發送垃圾訊息

一旦驗證者接收到訊息，他會檢查是否有接收過相同 $v$ 及 $l$ 的訊息，如果已經接收過，會捨棄新的訊息，否則這個驗證者將會轉發訊息並解密，以了解自己是否為指定的代理，驗證者會進一步的轉發這些消息，以防止流量關聯(**FIXME: 看不懂**)

:::success
我看懂了 但我懶得寫 要寫的人來問我 by YCC
:::

### 4. Verification

### 5. Claiming the slots

## Probabilities and parameters

---

## References

- [Web3 Foundation - SASSAFRAS](https://research.web3.foundation/Polkadot/protocols/block-production/SASSAFRAS)
- [Ring Verifiable Random Functions and Zero-Knowledge Continuations](https://eprint.iacr.org/2023/002)