# XVIII, IX Finality Consensus in JAM

## Ch 18. BEEFY Distribution

### **📌 18\. Beefy Distribution（Beefy 分發機制）**

這段描述了 **Beefy 協議的簽章與分發機制**，主要目的是讓驗證者（Validator）對每個最終確定的區塊 BB 進行 BLS 簽章，並提供最簡潔的最終性證明給第三方系統。

---

**🔹 逐步翻譯與解析**
--------------

### **📖 主要內容翻譯**

> 對於每個驗證者所導入的已最終確定的區塊 BB，該驗證者應使用 **BLS 簽名**（基於 BLS12-381 曲線，參見 Hopwood 等人 2020 年的研究），對該區塊的 **最新的 Beefy MMR** 之 **Keccak 哈希值** 進行簽名。這些簽名應當被公開發布與自由分發，連同所簽署的原始數據一起提供。
>
> 這些簽名可以被 **聚合**（Aggregated），以便於向第三方系統提供簡潔的最終性證明。簽名與聚合的完整機制由 **Jeff Burdges、Ciobotaru 等人 2022 年的研究** 定義。
>
> **數學表達方式：**
>
> - 設 **FvF_v** 為驗證者索引 vv 所發布的簽名承諾： Fv≡Sκ′v(XB⌢HK(EM(last(β)b\]))F\_v ≡ Sκ′\_v (X\_B ⌢ HK (EM (last(β)\_b\]))
> - 其中： XB=$jam_beefyX\_B = \\$jam\\\_beefy

---

**🔹 詳細解釋**
-----------

這段內容主要描述 **Polkadot 的 Beefy 協議** 如何透過 **BLS 簽章與聚合** 來提供 **簡潔的最終性證明**。我們拆解重要部分來解釋：

### **1️⃣ 為何需要 BLS 簽章？**

- 在區塊鏈系統中，**最終性（Finality）** 是指 **一個區塊被確認後無法再被更改或撤銷**。
- Polkadot 使用 **Beefy 協議** 來 **加速最終性傳播**，讓區塊的最終性可以被外部輕量級客戶端（如輕錢包、橋接鏈）快速驗證。
- **BLS 簽章（BLS12-381 橢圓曲線）** 是一種可聚合簽章（Aggregate Signature），這意味著 **多個驗證者的簽章可以合併成單一簽章**，大幅降低驗證成本。

>[name=yu2C] [BLS 驗證聚合的簽章](https://medium.com/web3foundation/apk-proofs-by-hand-and-sage-3f5feb3fcca4), 並不會知道每一把公鑰的內容
> - 可驗證的訊息會是 constant
> - 驗證者收到可驗證的 commitment 之後
> - 需要的訊息 : an indication of who has participated in the signing + a constant size proof provided by this protocol.
> - 所有成員 key 的 commitment 只會是 EC 上的兩個點, 不論參與者有多少人, 長度都是 constant
> - eg: committee 總共有 $N$ 個人, 但是只有 sub-set 的 $M$ 個人參與簽名
> - ED25519 需要驗證 $M$ 次, $\mathscr{O}(M)$
> - BLS 只需要驗證 1 次, $\mathscr{O}(1)$
> - 但兩者都需要知道 $N$
>
> ### 過程
>
> 1. committee 的總成員數 $C$
> $$C=\{0, 1,...,N-1\}$$
> 2. 每個成員 $i$ 的 $\mathrm{pk}$ 表示為 $\mathrm{pk}_i$
> $$P_C=\{\mathrm{pk}_i=(\mathrm{pk}x_i, \mathrm{pk}y_i)|i\in C\}$$
> where (x, y) <- pair 是 EC 上面的兩個點
> 3. $S$ 是對 $msg$ 簽章的 subcommittee
> $$\sigma(msg)=\sum_{j\in S \subseteq C}\sigma_{j}(msg)$$
> 3.1 要怎麼知道是否 $j$ 都在 $S$ 裡面? 用 bit-vector
> $$b=(b_i): i\in\{0, ...,N-1\}$$
> $$b_i=\begin{cases}1 \quad i\in S \\ 0 \quad i\notin S\end{cases}$$
> 3.2 所以 aggregated 的簽章者 $pk$ 為
> $$\mathrm{apk}_S=\sum_{i\in C}b_{i}\mathrm{pk}_{i}$$
> 4. 這樣驗證者一旦知道 $\sigma(msg)$ 和正確的 $\mathrm{apk}_S$ 就可以驗證
> $$e(msg, \mathrm{apk}_S)=e(\sigma(msg), g_2)$$
> where $e$ 是 EC 上面的計算函數(bilinear pairing function)
> Q: 如何知道收到的 $\mathrm{apk}_S$ 是正確的? 因為假設環境是資源有限的, 不希望收到所有的 $pk_i$
> A: 用 SNARK?

### **2️⃣ 什麼是 Beefy MMR？**

- **MMR（Merkle Mountain Range）** 是一種特殊的 Merkle 樹，適用於 **持續增長的數據集合**（如區塊鏈）。
- 在 Polkadot 的 **Beefy 協議** 中，**每個區塊的 MMR 根（Merkle 根）** 是驗證最終性的核心數據。
- 這裡的 **最新 Beefy MMR** 指的是當前區塊 BB 的最新 **Merkle Mountain Range 根哈希值**。

### **3️⃣ 簽章機制**


- 每個驗證者都會針對區塊 BB 產生的 **最新 MMR 根哈希值**，使用 **Keccak 雜湊函數** 計算哈希值。
- 然後，使用 **BLS 秘鑰 Sκ′vSκ′_v** 進行數字簽章，並發布簽章結果：
- **Sκ′vSκ′_v** ：驗證者 vv 的 BLS 簽章私鑰。
- **XB=$jam_beefyX\_B = \\$jam\\\_beefy** ：表示簽章所涉及的固定前綴（可能是協議識別符）。
- **HK(EM(last(β)b))HK(EM(\\text{last}(\\beta)_b))** ：
- $\text{last}(\beta)_\mathbf{b}$ ：歷史區塊 $\beta$ 中最新的 **Beefy MMR 根**。
- **EM(⋅)EM(\\cdot)** ：某種編碼方式（Encoding Method）。
- **HK(⋅)HK(\\cdot)** ：Keccak 哈希函數，確保 MMR 根以固定長度表示。

### **4️⃣ 為何要聚合簽章？**

- **聚合簽章的目標是降低驗證成本**：
- 傳統簽章：如果 1000 個驗證者，每個人都提供一個簽章，則需要驗證 1000 次。
- **BLS 聚合簽章**：可以將這 1000 個簽章合併為 1 個簽章，**只需驗證 1 次**，大幅提高效率。

---

**🔹 總結**
---------

1. **驗證者對每個最終確定的區塊 BB 進行 BLS 簽章**，簽名的內容是區塊的最新 **Beefy MMR 根哈希值**（經 Keccak 雜湊）。
2. **簽章與原始數據應公開分發**，使任何人都可以驗證這些簽章。
3. **簽章可聚合（Aggregated Signatures）**，這意味著多個驗證者的簽章可以合併為一個，減少存儲與驗證成本。
4. **這種機制提供了 Polkadot 給第三方系統（如輕客戶端、跨鏈橋）一種高效的最終性證明**，確保區塊不會被回滾或篡改。

這是 **Polkadot 輕量級客戶端（如輕錢包）與跨鏈橋技術的關鍵**，讓外部系統可以信任 Polkadot 的最終性，而不必自己參與完整的驗證流程。

## Ch 19. GRANDPA and The Best Chain

### **📌 Grandpa 協議中的最佳區塊選擇**

這段內容描述了 **Grandpa（GHOST-based Recursive Ancestor Deriving Prefix Agreement）最終性協議** 中，**如何選擇最佳區塊（Best Block, $B^\flat$）作為鏈的最前端（Head）**。

Polkadot 區塊鏈使用 **Grandpa 協議** 來確保區塊的最終性（Finality），而節點（Nodes）會根據特定規則來選擇 **最佳區塊**，以此作為進一步投票的基礎。

---

**🔹 逐步翻譯與解析**
--------------

### **📖 主要內容翻譯**

> 節點（Nodes）根據 **Stewart 和 Kokoris-Kogia（2020）** 所定義的 **Grandpa 協議** 參與共識。
> 我們定義 **最新最終確定的區塊** 為 **$\mathbf{B}^\natural$**（即已經通過 Grandpa 協議確定的區塊）。所有與區塊和狀態相關的術語，都以相同的上標表示。
> **最佳區塊 $\mathbf{B}^\flat$ 來自一組可接受的區塊集合**，並且必須滿足以下條件：
>
> 1. **$\mathbf{B}^\flat$ 的祖先區塊包含 $\mathbf{B}^\natural$**（即它是 **已最終確定區塊的後代**）。
> 2. **區塊不包含未最終確定的區塊，其中存在雙重投票（Equivocation）**
> - 也就是說，如果某個時段內出現兩個有效區塊，則它們不能同時存在於這條鏈上。
> 3. **該區塊已通過審計（Audited）**。

#### **數學表示：**

1. **$\mathbf{B}^\flat$ 的祖先區塊中，應包含 $\mathbf{B}^\natural$：**
- 這表示 $\mathbf{H}^\flat$（區塊頭）所屬的祖先集合中，必須包含 $\mathbf{H}^\natural$（已最終確定區塊的區塊頭）。
2. **$\mathbf{B}^\flat$ 是一個可接受的區塊：**
- $\mathbf{U}^\flat$ 代表這個區塊是「有效的」（⊺⊺ 表示真值，即符合條件）。
3. **避免雙重投票（Equivocation）：**
- 這表示：
1. **不能存在兩個不同的區塊 HAH_A 和 HBH_B**，但它們的時間戳相同（即 HAT=HBTH\_A^T = H\_B^T）。
2. **這些區塊不能同時屬於 B♭B^\\flat 的祖先區塊集合**。
3. **但其中至少有一個不是 B♮B^\\natural 的祖先**（即它可能是一個分叉）。

> **結論**：這條規則確保 **區塊鏈上不會同時出現雙重投票的未最終確定區塊**，以維護鏈的一致性。

---

**🔹 如何選擇最佳區塊？**
----------------

在這些可接受的區塊中，我們會選擇 **包含最多由 Seal-Key 簽署的祖先區塊的區塊作為最佳區塊 B♭B^\\flat**，而不是使用 **Fallback Key（備選金鑰）** 簽署的區塊。這樣可以確保區塊來自最可信的驗證者。

#### **數學表示：**


- **mm**：所選區塊的評分值。
- **A♭A^\\flat**：最佳區塊 B♭B^\\flat 的祖先集合。
- **TAT_A**：該祖先區塊是否由 **Seal-Key 簽署**（如果是，則加分）。

> **結論**：
>
> - 在所有符合條件的區塊中，我們選擇 **Seal-Key 簽署的祖先數最多的區塊作為最佳區塊 B♭B^\\flat**。
> - **這個最佳區塊將成為節點進行 Grandpa 投票的依據**。

---

**🔹 總結**
---------

1. **最新最終確定區塊 B♮B^\\natural 是所有區塊的基礎**，任何候選最佳區塊 B♭B^\\flat 必須是它的後代。
2. **選擇最佳區塊 B♭B^\\flat 的規則：**
- **不能包含未最終確定的雙重投票區塊**（避免出現兩個有效但相衝突的區塊）。
- **區塊必須通過審計**（確保區塊的完整性與合法性）。
3. **在所有符合條件的區塊中，選擇 Seal-Key 簽署祖先數最多的區塊作為最佳區塊 B♭B^\\flat**。
4. **這個最佳區塊將成為節點在 Grandpa 共識協議中進行投票的依據**。

這些規則確保了 **Polkadot 的 Grandpa 協議能夠選擇最可信的區塊，防止雙重投票，並維持鏈的一致性與安全性**。