# VI. Block Production and Chain Growth

本章節描述了 JAM 的區塊產生機制 Safrole，以及它是如何運作以限制新區塊產製的速率並防止分叉的。

Safrole 的目標
- 限制新區塊的產生速率，以維持網路穩定與同步性。
- 防止分叉，即避免在相同時間（slot）內產生多個具有相同祖先（ancestors）的區塊
- 透過限制 timeslot=6 sec 的時間內產生任何區塊的作者數量來達成
- 保護產塊者的身份匿名性，降低攻擊者識別與針對行為的風險

Safrole 的機制
- Epoch 和時段 (Time Slot)：Safrole 將時間劃分為 epoch，每個 epoch 又劃分為多個時段 (Time Slot)。每個時段的長度固定為 6 秒。
- 驗證者 (Validator)：是一組動態選擇的密鑰持有者的密鑰持有者，有權生產區塊。
- 密封金鑰 (Sealing Key)：每個驗證者在每個 epoch 都會獲得一組密封金鑰（Sealing Key），用於產塊簽名。
- RingVRF：Safrole 使用 RingVRF 加密函式生成密封金鑰。
- 票券 (Ticket)：每個驗證者有一張 ticket，競賽得分最高的數個驗證者獲得生產區塊的權利。
- 金鑰輪換(Key Rotation)：每個 epoch 生成一次密封金鑰序列，每個潛在區塊對應一個金鑰。
- 備用金鑰序列：如果票券系統出現問題，Safrole 會使用備用金鑰序列函數來生成密封金鑰序列。

## 6-1 時間記錄 (Timekeeping)
JAM 網路中的時間追蹤機制。 該機制將時間劃分為一系列離散的時段（slot），每個時段的長度固定為 6 秒。 每個區塊都與一個特定的時段索引相關聯，用於標識區塊產生的時間。

Safrole 共識機制使用時段索引來安排驗證者在特定的時段產製區塊，並使用 $τ$ 和 $τ'$ 來追蹤和更新時段索引。

- Notation:
- $\tau, \tau'$： 代表最近一個區塊和當區塊所在的 **Slot Index**。
- $\mathbf{H}_t$： 代表從當前區塊的 **Header** 中提取出的 **Slot Index**。
- $\mathbb{H}_t$: 代表所有可能的 **Time Slot Index** 的集合，為 32 位元 unsigned int 集合。
- $\mathsf{E}$: 代表一個 **Epoch** 的總 **Slot** 數。($\mathsf{E} = 600$, $\mathsf{P} = 6$ (The slot period, in seconds))
- $e, e'$: 這兩個變數代表前一個區塊和當前區塊分別屬於哪個 **epoch**。
- $m, m'$: 這兩個變數代表前一個區塊和當前區塊在各自的 **Epoch** 中所處的第幾個 **Slot**。

#### 名詞解釋
- **橢圓曲線 (Elliptic Curve)**：一種特殊的平面代數曲線，在現代密碼學中扮演著重要角色，例如，用於生成密碼金鑰和數位簽章。
- **環簽名 (Ring Signature)**：一種數位簽名方案，允許多個使用者對一條訊息進行簽名，而不透露具體是哪個使用者簽名的。
- **Bandersnatch 環根 (Ring Root)**：代表一個環簽名的根，利用橢圓曲線是 Safrole 系統中的一個重要概念，用於驗證 RingVRF 證明。
- **票券 (Ticket)**： 一種用於參與共識或其他機制的憑證，每個票券包含一個可驗證的隨機識別碼和一個進入索引，用於選擇下一個 epoch 的出塊者。
- **時段索引 (Slot index)**: 用來標記區塊在整個區塊鏈中的位置 (第幾個區塊)。
- **時段密封者序列 (Slot-sealer series)**： 包含了一系列的 Bandersnatch 公鑰，用於在不同的時隙中對區塊進行簽名，決定每個時段的出塊者。

#### Formula
:::info
$\tau$: 前一個區塊的 slot index。
$\mathbb{N}_{T}$: 32 位元 unsigned int。
$\tau^\prime$: 當前區塊的 slot index。
$\mathbf{H_t}$： Block Header。

Formula 意義:
slot index 是 int，block header 包含此資訊
:::
$6.2$
$let\ e\ R\ m = \frac{\tau}{E}$
$e'\ R\ m' = \frac{\tau'}{E}$
:::info
$\mathbf{e}$、$\mathbf{m}$: 前一個區塊所屬的 epoch 和在該 epoch 的 slot index。
$\mathbf{e'}$、$\mathbf{m'}$: 當前區塊所屬的 epoch 和在該 epoch 的 slot index。
$\mathbf{E}$: 代表每個 epoch 包含的 slot 總數。

Formula 意義:
可透過 slot index $\tau$ 和 $\tau^\prime$ 除以 $\mathsf{E}$ ，算出區塊所屬的 epoch 和在 epoch 中的時段索引。($\mathsf{R}$ 代表的是取餘數運算)
:::

## 6-2 Safrole Basic State (Safrole 基本狀態)
Safrole 的狀態 γ 是 Safrole 共識機制的核心，用於儲存和管理與區塊產製和共識相關的重要資訊，確保 JAM 網路的區塊產製過程的規律性、安全性和公平性。它包含以下四個組成部分：
$(6.3)\ \ \gamma \equiv (\gamma_\mathbf{k}, \gamma_\mathbf{z}, \gamma_\mathbf{s}, \gamma_\mathbf{a})$

:::info
$\gamma$： Safrole 系統。
$\gamma_\mathbf{k}$：下個 epoch 將成為 active set 的驗證者金鑰集
$\gamma_\mathbf{z}$：當前 epoch 用於提交 ticket 驗證身份的 Bandersnatch ring root
$\gamma_\mathbf{s}$: slot key sequence，各個區塊生產者的 key。
$\gamma_\mathbf{a}$: ticket accumulator，priority queue 用來決定下一個 epoch 的區塊生產者。

:::
$(6.4)\ \ \gamma_\mathbf{s} \in \mathbb{Y}_R$
:::info
$\gamma_\mathbf{z}$：當前 epoch 的根，由 **下一個** epoch 的每個驗證者的單個 Bandersnatch 金鑰組成的 Bandersnatch 環根。
$\mathbb{Y}_R$: 所有可能的 Bandersnatch 環根的集合。
:::


$(6.5)\ \ \gamma_a \in [\mathbb{C}]_{: E},\ \
\gamma_s \in [[\mathbb{C}]_E \cup [\mathbb{H}_B]]_E$
:::info
$\gamma_\mathbf{a}$ : 這是票券累加器，包含了 **最多 $\mathsf{E}$ 個** 得分最高的票券。

- $\mathbb{C}$ : 代表票券的集合。
- $\mathbb{[C]}_{:\mathsf{E}}$ : 表示票券集合包含 **最多 $\mathsf{E}$ 個** 元素的集合。

$\gamma_\mathbf{s}$ : 為 **slot-sealer series**

- $\mathbb{H}_B$ : Header 上的 Bandersnatch 公鑰
- $\mathbb{[C]_{E} ∪ [H_B]_E}$ : 包含 $\mathsf{E}$ 個票券或 $\mathsf{E}$ 個 Bandersnatch 公鑰的序列
- **slot-sealer series** : 表示一個包含 $\mathsf{E}$ 個元素的序列，其中每個元素是一個票券或一個 Bandersnatch 公鑰。
:::

$(6.5)\ \ \ \mathbb{C} \equiv (y \in \mathbb{H}, r \in \mathbb{N}_N)$
:::info
$\mathbb{C}$ : 票券。
$\mathbf{y}$ : Verifiably random ticket identifier ，用於在 Safrole 的 epoch 競賽中作為分數的隨機數。
$\mathbb{H}$ : Hash(隨機數由 hash 產生)
$r$ : Ticket index。
$\mathbb{N}_\mathrm{N}$ : 自然數。

定義了一個票券的結構。每個票券由兩個部分組成：一個由 hash 產生的隨機值 verifiably random ticket identifier $y$ 和一個表示 ticket index $r$。
:::
## 6-3 Key Rotation (描述 key 在跨 epoch 的輪轉)
每個 **Validator** 都有一個獨一無二的 key， public key和 metadata 組成，這個key可識別一個驗證者，每個 **Epoch** 會進行一次 Validator key 輪換。

Safrole 系統中維護了三個 Validator key set：
- 活躍驗證者金鑰集 (**Active Set**) $(\kappa)$：當前 epoch 有權生產 Bloack 和執行驗證過程的 Node 的 Validator key set。
- 待處理驗證者金鑰集 (**Pending Set**) $(\gamma_k)$：下一個 epoch 中將會成為 Active Set 的 Validator key set。
- 暫存驗證者金鑰集 (**Staging Set**) $(\iota)$：即將被加入到待處理驗證者金鑰集中的金鑰。

### Key 組成
- Bandersnatch key $(k_b)$: 這是 Validator key 的第一個部分，長度為 32 bytes，用於生成和驗證簽名，以及參與 Ring-VRF 的生成。
- Ed25519 key $(k_e)$: 這是 Validator key 的第二個部分，長度也是 32 bytes，主要用於生成和驗證 Ed25519 簽名，例如在提交 Ticket 和發布訊息時使用。
- BLS key $(k_{BLS})$: 這是 Validator key 的第三個部分，長度為 144 bytes，用於生成和驗證 BLS 簽名，例如在參與 Grandpa 共識協議時使用。
- Metadata $(k_m)$: 這是 Validator key 的最後一個部分，長度為 128 bytes，包含驗證器的中繼數據，例如硬體地址、網路地址等信息，用於識別和管理驗證器。

### 密鑰 Rotate 流程

Epoch 開始時的更新：
- 待定金鑰集 (**Pending Set**) $\gamma_\mathbf{k}$ 會成為新的暫存金鑰集(**Staging Set**) $\iota$ 。
- 暫存金鑰集(**Staging Set**) $\iota$ 會成為新的活躍金鑰集 (**Active Set**) $\kappa$ 。
- 系統會根據新的活躍集 $\kappa$ 生成新的 Bandersnatch 環根。
- 特殊情況： 如果有驗證者被標記為違規，其對應的密鑰在待定集中會被替換為全零的密鑰。

優點
- 安全性： 定期更換金鑰可以降低單一個金鑰被盜用的風險。
- 防止壟斷： 防止少數驗證者長期控制網絡，確保網絡的去中心化。
- 引入新驗證者： 為新的驗證者提供加入網絡的機會。

graph TD
    A[開始] --> B{是否為新的 epoch?};
    B -- 是 --> C[將 Staging Set 的 Validator key 集合 γ_k 設置為 Active Set κ'];
    B -- 否 --> F[結束];
    C --> D[將前一個 epoch 的 Active Set 集合 κ 移至 Last Epoch Active Set λ'];
    D --> E[更新 epoch 的 Bandersnatch 金鑰根 γ_z'];
    E --> F;

### Formula

$(6.7) \ \ \ \ \iota \in [\mathbb{K}]_V,\
\gamma_k \in [\mathbb{K}]_V,\
\kappa \in [\mathbb{K}]_V,\
\lambda \in [\mathbb{K}]_V$

:::info
$\mathbf{[\mathbb{K}]_\mathbf{V}}$ : 代表了一個包含所有驗證者金鑰的集合。

- $\iota$ (**Staging Set**): 代表一個特定的驗證者公鑰。這個公鑰可能與系統中的某個節點相關聯。
- $\gamma_{\mathbf{k}}$ (**Pending Set**) : 代表下一個 epoch 中將要 active 的一組驗證者公鑰。
- $\kappa$ (**Active Set**) : 代表當前 epoch 中正在使用的 validator key 集合。
- $\lambda$ (**Last Epoch Active Set**) : 上一個 epoch active 的 validator set key
:::


:::info
==這是一個 STF，請他把當成跨 epoch 的 Key Roatation (等號右邊會轉換成左邊，往左 shift 一格)==

- $\iota$ : 在新 epoch 剛開始時的 $\gamma_{\mathbf{k}}$，我們先複製起來並 assign 成 $\iota$
- $z$ : 由 $\gamma^{\prime}_{\mathbf{k}}$ (注意這是轉換後的 state) 經由 $\mathcal{O}$ (The Bandersnatch ring root function) 生成的 ring root
- $\Phi(\mathbf{k}){}$ : 踢掉被懲罰的 validator set

Process :

- $\Phi(\iota) \to \gamma^{\prime}_{\mathbf{k}}$ : 將 epoch 一開始的 validator ($\iota$) 去除掉這輪更新後的 punished validator set -> 轉換成下一輪準備成為候選 validator set
- $\gamma_{\mathbf{k}} \to \kappa^{\prime}$ : 把 "準備要 active 的 valiator set" 更新上去成 "當前 epoch active 的 validator set"
- $\kappa \to \lambda^{\prime}$ : "當前 acitve 的 validator set" 更新成 "對下個 epoch 來說是上一個 active set 的 $\lambda$"
- $z \to \gamma^{\prime}_{z}$ : 把生成的環 root $z$ 更新成 $\gamma^{\prime}_{z}$ (想成新的 $pk$ set)
- $\gamma^{\prime}_{z}$ : 更新後的 ring root，需要存在新的 state (也就是 Safrole 的其中一個 state)裡
:::

- Φ(ι): 是一個函數，用於處理違規的驗證者。如果一個驗證者在違規者列表 ψo 中，那麼這個驗證者的所有密鑰都會被替換為全零的序列。
- z: 是新的 Bandersnatch 環根，由當前 epoch 的待定密鑰集 γk 中所有驗證者的
驗證者若屬於違規者集合ψo'，則其對應的金鑰將被替換為全為零的空金鑰。

## 6-4 Sealing and Entropy Accumulation (密封與熵累積)
描述關於區塊 Header 封裝（sealing）和熵累積（entropy accumulation）的機制提升區塊鏈的安全性。
### 密封 (Sealing)：
每個區塊 **Header** 都必須經過密封才能被視為有效。
區塊 **Header** 密封包含兩個簽名(形式相同)：
- 密封簽章 (Seal 簽章) : 對 Header 的一個「蓋章」，用來證明這個區塊是有效的。
- VRF 輸出 : 使用當前時段的密封簽章加入隨機數再透過 VRF 函式得出值，並同時引入隨機性並可被驗證。
### 熵累積 (Entropy Accumulation)
提供系統的隨機性，用於生成隨機數和備用金鑰。
熵累加器包含 $(\eta_0$, $\eta_1$, $\eta_2$, $\eta_3)$：儲存當前和過去三個 epoch 的熵累積值。

### Formula
:::info
$i$ : sealing key
逆時針 : mod (這邊是 600)

$\mathsf{X}_E$：用於生成 VRF 輸出 $\mathbf{H}_v$ 的熵源。
$\mathsf{X}_F$：用於生成備用密封簽章的熵源，也就是使用備用金鑰序列時。
$\mathsf{X}_T$：用於生成 ticket 密封簽章的熵源，也就是使用票務系統時。
$jam\_entropy$、$jam\_fallback\_seal$ 和 $jam\_ticket\_seal$ 是三個預先定義的常數，它們是固定的字串值。
:::
$\gamma_{s}^{\prime} \in \left[ \mathbb{C} \right] \Longrightarrow
\begin{cases}
i_y = \mathcal{Y}(H_s), \\
H_s \in \mathbb{F}_{H_a}^{\mathcal{E}_U(H)} \langle X_T - \eta_{3}^{\prime} + i_r \rangle, \\
T = 1
\end{cases}$
:::info
公式 (60):
表示當使用票券 ($\mathbf{C}$) 密封區塊時，密封簽章 $\mathbf{H_s}$ 和 VRF輸出 $i_\mathbf{y}$ 的生成方式：

$\mathbf{H}_s$ 是由索引為 $\mathbf{H}_t$ 的驗證者的 Bandersnatch 金鑰簽署的簽章。
$\mathbf{H}_s$ 簽章訊息包含：
- $\mathsf{X}_T$ : 固定的上下文字串
- $\eta'_3$ : 前三個 epoch 的熵累加器值。
- $i_r$ : ticket index $r$ 。

$\mathbf{H}_a$ 區塊生成者 bandersnatch key。
**VRF**:
- $\mathbf{i_y}$ : 將 $\mathbf{H_s}$ 進行 $Y$ (VRF) Hash function 的運算結果。
- $Y(H_s)$ 指的是 Hs 的 VRF 輸出。

VRF (可驗證隨機函數)

VRF 是一種密碼學函數，它可以生成可驗證的隨機數。也就是說，任何人都可以驗證生成的隨機數是否有效，並且該隨機數是由特定的私鑰持有者生成的。
:::

公式 (61):
:::info
表示當使用備用密鑰集合 ($\mathbf{H_B}$) 密封區塊時，密封簽章 $\mathbf{H_s}$ 和 VRF輸出 $i$ 的生成方式

$\mathbf{H_s}$ 是由索引為 $\mathbf{H_t}$ 的驗證者的金鑰簽署的 Bandersnatch 環簽章。

$\mathbf{H_s}$ 簽章訊息包含：
- $\mathsf{X_T}$ : 固定的上下文字串
- $\eta^{\prime}_{3}$ : 前三個 epoch 的熵累加器值。
VRF:
- $i$ : Bandersnatch key of the block author
:::
公式 (62):
:::info
$\mathbf{H}_v$ : 在 header 儲存的 entropy-rielding VRF signature
透過將 $\mathsf{X}_E$ 和 $\mathbf{H}_s$ 做 VRF function 串接而成
:::


公式 (66)：
:::info
熵累加器，利用來自 VRF 的輸出，以確保系統的隨機性。
$\eta$ 代表熵累加器，它是一個包含 4 個值的序列 $\eta_0$, $\eta_1$, $\eta_2$, $\eta_3$。
:::

公式 (67)
:::info
這個公式表示，當一個新的區塊被添加到鏈上時，會根據之前的隨機性累加器狀態 η0 和當前區塊的驗證結果 Y(Hv) 計算出新的隨機性累加器狀態 η0'。

$\mathcal{H}$ : 一個哈希函數
$\mathbf{H}_v$ : 在 header 儲存的 entropy-rielding VRF signature
$\mathcal{Y}(\mathbf{H}_{v})$ : 對 $\mathbf{H}_v$ 執行 VRF function。

公式 (67) 的意義：
$\eta'_0 \equiv \mathcal{H}(\eta_0 \frown \mathcal{Y}(\mathbf{H}_v))$: 表示將當前區塊的熵累加器的第一個元素 $\eta_0$ 和當前區塊的 $\mathbf{H}_v$ 的 VRF 輸出 $\mathcal{Y}(\mathbf{H}_{v})$ 串聯起來，然後再計算其hash。
:::

公式 (68)
:::info
在每個 epoch 結束時，會將之前的隨機性累加器 tuple 從 $(\eta_0, \eta_1, \eta_2)$ shift 成 $(\eta_1, \eta_2, \eta_3)$，保存最近三個 epoch 的隨機值狀態。
:::

## 6-5 The Slot Key Sequence
Safrole 會在每個 epoch 開始時，生成一個包含 E 個金鑰的序列，每個金鑰都對應 epoch 中的一個 slot。
每個 Block Header 包含其時段索引 $\mathbf{H}_t$，以及由對應於該時段的金鑰所簽署的有效密封簽章 $\mathbf{H}_s$ 。
金鑰實際代表某個驗證者的假名，該驗證者被在相應 slot 有生產 block 的權限。


公式 (69)
:::info
描述了如何決定後續 Slot 的 Key Sequence $\gamma'_s$ 如何變動

下一個區塊和當前區塊屬於同一個 epoch ($e^{\prime} = e$): 沿用當前區塊的密封金鑰序列：則後續時段沿用金鑰序列 $\gamma'_s$。

下一個區塊屬於新的 epoch ($e^{\prime} = e + 1$)，並且滿足兩條件：
- 1. 當前區塊的 slot index m 大於等於 $\mathsf{Y}$ (已經過了 Ticket 提交時段） ($\mathsf{Y} = 500$, constant)。
- 2. 票累加器 $\gamma_\mathbf{a}$ 中的 ticket 數量為 $\mathsf{E}$（已經收集到了足夠 ticket)。

則使用 $\gamma'_s$ 使用累加器結果並透過 $Z$ 函數重新排序票。

不滿足則使用備用金鑰序列
:::

公式 (70)
::: info
這個公式定義了函數 $Z$，它用於對一個序列進行重新排序。具體來說，$Z$ 函數將一個長度為 $\mathsf{E}$ 的序列 $\mathbf{s}$，按照特定的規則重新排序成一個新的序列。

規則為: ${s_0, s_{|s|-1}, s_1, s_{|s| - 2}, s_2, s_{|s| -3}}$
:::

公式 (71)
::: info
定義函數 $F$，利用熵 $r$ 和驗證者金鑰集 $\mathbf{k}$ 作為輸入，並輸出一個包含 $\mathsf{E} 個 Bandersnatch 公鑰的序列。這個序列將作為該 epoch 的 Key Sequence，決定每個 block 出塊者。
:::

## 6-6 The Markers

epoch 標記和 winning-tickets 標記是 Header 中的資訊，助於所有節點可僅使用 Header 追蹤驗證者金鑰集的變化。

epoch 標記

### Formula

公式 (72)：時期標記(epoch marker)($\mathbf{H}_e$)
:::info
如果下一個區塊屬於新的 epoch ($e^\prime > e$)，則 $\mathbf{H}_e$ 包含兩個部分：
- $\eta_1'$：在這 epoch 使用的墒值。
- $[k_b | k \in \gamma^\prime_k]$：下一個 epoch 中所有驗證者的 Bandersnatch 金鑰列表。
否則，$\mathbf{H}_e$ 為空。
:::
公式 (73)：獲勝票標記(winning-tickets marker)( $\mathbf{H}_w$ )
:::info
如果滿足以下條件，則 $\mathbf{H}_w$ 等於 $Z(\gamma_{\mathrm{a}})$：
- 1. 下一個區塊和當前區塊屬於同一個 epoch ($e^{\prime} = e$)。
- 2. 當前區塊的時段索引 $m$ 小於 $\mathsf{Y}$，而下一個區塊的時段索引 $m'$ 大於等於 $\mathsf{Y}$(下一個區塊是票提交期結束後的第一個區塊)。
- 3. 票累加器 $\gamma_a$ 中的票數等於 $\mathsf{E}$ 。

否則，$\mathbf{H}_w$ 為空。
:::

### Extra notes:
Bandersnatch 金鑰 流程
1. 金鑰生成：每個驗證者在加入 JAM 網絡時，都會生成一對 Bandersnatch 金鑰：私鑰和公鑰。
私鑰由驗證者秘密保管，用於生成簽名和證明。
公鑰公開發布，其他節點可以使用公鑰來驗證簽名和證明。
2. Ring-VRF 生成：在每個 epoch 開始時，系統會收集所有驗證者的 Bandersnatch 公鑰，並使用這些公鑰生成一個 Ring-VRF（環可驗證隨機函數）。
Ring-VRF 的作用是允許匿名驗證，任何知道其中一個驗證者私鑰的人都可以生成一個有效的證明，證明他們是環中的一員，但不需要透露他們是哪個驗證者。
3. Ticket 提交：驗證者使用他們的 Bandersnatch 私鑰對 Ring-VRF 進行簽名，生成一個匿名的證明，也就是 ticket。
ticket 包含一個可驗證的隨機票證標識符和票證的輸入索引。
驗證者將 ticket 提交到網絡中，參與爭奪下一個 epoch 產生區塊的權利。
4. Ticket 驗證和排序：其他節點可以使用 Ring-VRF 和驗證者的 Bandersnatch 公鑰來驗證 ticket 的有效性。
系統會根據 ticket 的分數對 ticket 進行排序，分數越高，表示驗證者在下一個 epoch 產生區塊的權利越大。
5. Slot key sequence 生成：
根據排序後的 ticket，系統會生成下一個 epoch 的 slot key sequence (γ_s)。
γ_s 決定了每個 slot 的區塊生產者。
6. 區塊密封：被選中的區塊生產者使用 γ_s 中對應時間戳記的 Bandersnatch 金鑰對區塊進行簽名，生成一個密封簽章。
這個簽章證明了該區塊是由被授權的驗證者生成的，並且防止區塊被篡改。

graph TD
    A[驗證者生成 Bandersnatch 金鑰對] --> B{收集所有驗證者的 Bandersnatch 公鑰};
    B --> C[生成 Ring-VRF];
    C --> D[驗證者使用私鑰對 Ring-VRF 簽名生成 ticket];
    D --> E[提交 ticket];
    E --> F[驗證 ticket 並排序];
    F --> G[生成 slot key sequence γ_s];
    G --> H[區塊生產者使用 γ_s 中對應的金鑰密封區塊];
    H --> I[驗證區塊的密封簽章];