---
reference: https://spec.polkadot.network/sect-block-production
---

# 5. Block Production

# 5.1 Introduction

Polkadot Host 使用 BABE (Blind Assignment for Blockchain Extension) protocol 進行區塊的產生，BABE 在每一個 epoch 開始時都會執行， 透過 Block-Production-Lottery 用來找到哪些 slots 應該產生區塊並通知其他區塊生產者，區塊產生者會記錄這些樹狀結構，維持區塊鏈的最新狀態 (可能有分支就需要處理，透過通知了解其他人產生的資訊)。

### 5.1.1. Block Producer

被授權可以輪流產生區塊的人

### 5.1.2 Block Authoring Session Key Pair

- 是一個 SR25519 的 key pair
- 由區塊產生者 $P_j$ 使用自己的帳戶密鑰([Definition 187](https://spec.polkadot.network/id-cryptography-encoding#defn-account-key))進行簽名
- 這一個 key pair 將會使用於 Block-Production-Lottery 算法中計算其抽籤的數值 (使用在 VRF 作為 secret key，產生出隨機數值。)

> Difinition 59. Epoch and Slot
> - 區塊生產週期 (block production epoch) $\varepsilon$ : 是一個固定長度的時間段，在該時間段內，區塊生產者的名單是不會改變的。
> - 週期編號 (epoch index): 每個 epoch 具有有順序的編號，從創世塊 (genesis) 開始，第 $n$ 週期被表示為 $\varepsilon_n$
> - 每個 epoch 會再區分為固定長度的區間，被稱為 slot
> - 每個 slot 的 index，被稱為 slot number
> - 每個 slot 有等長的時間長度，被稱為 slot duration
> - 每個 slot 會分配給一部分的區塊生產者，允許他們在該 slot 產生產生區塊。
>
> 在 Polkadot 中，slot 是一個長度為 6 秒的時間單位，每一個 slot 可以包含一個 block, 但也有可能不只一個 block。
> 在 Polkadot 中，2400 個 slots 可以組成一個 epoch，每一個 epoch 將會是 4 小時的長度。

> Definition 60. Epoch and Slot Duration
> - 使用 $sc_n$ 來表示在 epoch $\varepsilon_n$ 的 slot 總數
> - 該數值 $sc_n$ 是設定在 `duration` 欄位中，可以透過 Polkadot Runtime 初始化時透過呼叫 `BabeApi_configuration` ([Section C.11.1.](https://spec.polkadot.network/chap-runtime-api#sect-rte-babeapi-epoch)) 拿到。(slot 數量對應時間)
> - $S_B$：用來表示 block $B$ 被生產的 slot
> - $B_c$：用來表示所有在 slot $s$ 產生的區塊集合

> Definition 61. Epoch Subchain
> - $SubChain (\varepsilon_n)$: 指的是所有在該 epoch $\varepsilon_n$ 的 slot 中所產生的區塊，組成的 $BT$ (Block Tree) 路徑圖 (path graph)。
> - 當 slot 產生超過一個 block 時，被選擇的區塊也需要是在 $\text {Longest-Chain}(BT)$ 中的區塊。(最長鏈的一部分)

> Definiation 62. Equivocation
>
> 假如在一個 slot 生產了超過一個區塊，將會導致模稜兩可的狀況發生
> - 透過驗證者進行簽名，並包含對應的 slot number，來避免該狀況發生
> - Polkadot Host 必須偵測這種模稜兩可的事件是否發生，並且將該事件提供給 Runtime

> Definition 63. BABE Consensus Message
> $CM_b$, BABE 的共識訊息
> $$
CM_b =
\begin{cases}
1 \quad (\text{Auth } C, r) \\
2 \quad A_i \\
3 \quad D \\
\end{cases}
> $$
> >
> 訊息分為三個部份
>
> 1. 記錄下一個 epoch data 的資訊，Runtime 將會在每一個 epoch 的第一個 block 傳送該訊息，權限集合(-> 該區塊的授權清單 -> 可能的區塊生產者) ($Auth_C$) 以及隨機數 ($r$) 將會被使用在下一個 epoch 中 ($\varepsilon_n + 1$)，如果 $\varepsilon_n + 1$ 到 $\varepsilon_n + k$ 的被跳過的話 (i.e. BABE 沒有產生區塊 -> 沒有驗證者的 VRF 結果小於 throshold)，那個該 epoch data ($Auth_C, r$) 將會被下一個 epoch 使用 ($\varepsilon_n + k + 1$)。
>
> 2. 記錄禁用狀態: 是一個 32-bit 的整數, $A_i$, 可以立即暫停被指定的授權者(禁止某個授權者的權限)
>
> 3. 記錄下一個 epoch 的描述資訊，該訊息只會在設定改變以及每個 epoch 的第一個 block 時送出，提供這一些資訊給下一個 epoch 使用。
>
> - $D$ 是可變動的資料型態
>
> $$
> D = \{1, (c, 2_{nd})\}
> $$
>
> $c$ 是 slot 不為空的機率，可以透過兩個 unsigned 64-bit 整數計算得到, $c = \frac{c_{\text{nominator}}}{c_{\text{denominator}}}$
>
> - $2_{nd}$ 是指 secondary slot
>
> secondary slot: secondary slot 會與 primary slot 一起運作，在每個 slot 中會進行計算，從授權清單中找出一個該 block 的次要生產者 (候補人選)，當沒有任何人獲得該區塊的生產權限時(VRF 結果都大於 throshold)，將會透過 sceondary slot 來保持區塊持續的產生。
> 詳細算法參考官方文件: [Definition 67: Secondary Slots](https://spec.polkadot.network/sect-block-production#defn-babe-secondary-slots)

[什麼是 Verifiable Random Function (VRF)?](/VNWEBbEVQkO2e3DFwD3WRw)

## 5.2 Block Production Lottery

區塊生產者若想要在特定的 epoch 內產生區塊，需要執行 Block Production Lottery 算法，來確定自己抽中了哪一個 slot，就可以在指定的時間內產生區塊 (slot 代表允許生產區塊的時間點)

為了確保區塊的持續產生，當沒有任何人抽中區塊生產的資格，BABE 將會使用 secondary slots 指派一個預先公開的候補區塊生產者。

> Definition 64. BABE Constant
> - BABE 常數是一個機率值，代表某個 slot 將不會是空的，且被使用在 Winning Threshold 的計算。(機率越高，代表越多 slot 目前是可以用於計算 Winning Threshold)
> - 這個常數以有理數的形式表達 $(x,y)$, x是分子，y是分母。
>
> **(嘗試理解、待確認)** 如果 BABE 常數越小
> - 代表某些 slot 是空的，但是他們沒有被使用來計算 Winning Threshold, 會導致區塊生產過程中，選擇到有效 slot 的機會降低。

> Definition 65. Winning Threshold
> - Winning Threshold 表示為 $T_{\varepsilon_n}$
> - 該閾值將與 Block-Production-Lottery 一起使用，來決定區塊生產者是否為該時段(slot)的獲勝者
> $$
> A_w = \sum_{n=1}^{|Auth_C(B)|} \left( w_A \in \text{Auth}_C(B)_n \right)
> $$
> $$
> T_{\varepsilon_n} = 1 - (1 - c)^{\frac{w_a}{A_w}}
> $$
>
> - $A_w$ 是權威清單 (Definition 33. Authority List) 在 epoch $\varepsilon_n$ 中的權重總和
> - $w_a$ 是區塊作者的權重
> - $c \in (0,1)$ 是 BABE 常數 (Definition 64)

### 5.2.1 Primary Block Production Lottery

> [Definition 66. BABE Slot VRF transcript, output, and proof](https://spec.polkadot.network/sect-block-production#defn-babe-vrf-transcript)

#### Algorithm 6. Block Production Lottery

輸入 $sk$ （區塊生產者的密鑰)

1. 取得該 epoch ($\varepsilon_n$) 的隨機數
- 隨機數是透過 VRF 所計算獲得 (參考 [Definition 76. Randomness Seed](https://spec.polkadot.network/sect-block-production#defn-epoch-randomness))
2. 遍尋該 epoch 中的每一個 slot (1~$sc_n$)
3. 使用 VRF 計算該 slot 的數值
- 輸入隨機數 ($r$), slot number ($i$), secret key ($sk$)
- VRF 將會獲得一個證明方法 ($\pi$) 以及輸出值 ($d$)
4. 將 VRF 的輸出結果儲存到一個陣列($A$)中
5. 重複步驟 2 至 4，直到所有的 slot 被訪問完畢。
6. 輸出陣列 $A$ (每個 slot 的抽籤結果)

> [Definition 67. Secondary Slots](https://spec.polkadot.network/sect-block-production#defn-babe-secondary-slots)
> TODO
> 簡單來說，就是透過一些計算找到候補的區塊生產者，來保持區塊穩定持續產生。

## 5.3 Slot Number Calculation

為了保護整個網路的安全性，區塊生產者必須確保 slot number 對應到正確的時間，需要透過定期的估算本地時鐘相對於網路的時間偏差。

Polkadot 使用 Median Algorithm 來實現不需要外部的時間來源，就能達到時間的同步，為了保持同步性，區塊生產者必須定義的估算本地時間與網路時間的偏差

推估需要兩個參數：
- $k$ : 被修剪過的最佳鏈 (Pruned Best Chain) ([Definition 70](https://spec.polkadot.network/sect-block-production#defn-prunned-best))
- $s_{cq}$ : 鏈的品質 ([Definition 71](https://spec.polkadot.network/sect-block-production#defn-chain-quality))

這些參數是基於正式的[安全分析](https://research.web3.foundation/Polkadot/protocols/block-production/Babe#5-security-analysis)結果進行選擇的

目前假設與目標

- 每天時鐘偏移 1 秒
- 三年內對 BABE 的攻擊者成功機率低於 0.5%
- 該設計對於抵抗網路延遲能力的時間可以達到 slot time 的 $\frac{1}{3}$
- BABE 常數 $c$ 的值設定為 0.38

所有驗證者都需要在每個同步週期開始時，執行中位數算法 (Median-Algorithm)，使用上個週期所有區塊的到達時間來更新驗證者的時間同步性。

這個算法在每個週期只會執行一次

- 驗證者必須在每個同步週期執行中位數算法 (Median-Algorithm)，以確保所有驗證者的時間都能有效地同步。
- 該算法只在該週期的所有區塊都已確認後執行，即使區塊只是機率上的確認 ([Definition 70](https://spec.polkadot.network/sect-block-production#defn-prunned-best)))，以確保該算法基於已知且可驗證的數據進行計算。
- 驗證者的時間同步目標，應該是新同步週期的第一個 slot，確保所有驗證者在相同時間下去產生新一輪的區塊。

---
TODO: 移動至 3. Synchronization

> Definition 33. Authority List
> - Authority list 是 block $B$ 在 consensus engine $C$ 中的權威清單，被寫做 $Auth_C(B)$，每一個權威者都會在這個清單中。
>
> $$
> (pk_A, w_A)
> $$
>
> - $pk_A$ 是權威 $A$ 的 session public key (Definition 190)
> - $w_A$ 是一個 unsigned 64-bit integer，用來表示權威的權重
> - $Auth_C(B)$ 是 Polkadot 狀態的一部分，這個數值在創世狀態([Section A.3.3.](https://spec.polkadot.network/id-cryptography-encoding#section-genesis))中被設定。
> - 權威及對應的權重可以從 Runtime 取得 ([Section C.10.1](https://spec.polkadot.network/chap-runtime-api#sect-rte-grandpa-auth))
---

> Definition 68. Slot Offset
> - $\text{Slot-Offset}(s_i, s_j)$ 用來表達 $s_i$ 與 $s_j$ 之間，所存在的 slot 數量 (計算上要包含 $s_j$)
> 例如：
> - $\text{Slot-Offset}(s_i, s_i) = 0$
> - $\text{Slot-Offset}(s_i, s_{i+1}) = 1$

> Definition 69. Relative Time Synchronization
> - 相對時間的同步可以透過 slot number 與 local clock timestamp 進行描述 $(s_{sync}, t_{sync})$
> - 用來記錄 slot number 與本機時間同步的最後一個位置 (最後一個 pair)

### Algorithm 7. Slot Time

輸入： $s$ (slot number)
輸出： $t_{\text{sync}} + \text{Slot-Offset}(s_{\text{sync}}, s) \times T$

- $t_{sync}$ : 當前同步時間
- $\text{Slot-Offset}(s_{\text{sync}}, s)$ : 計算 $s_sync$ 及 $s$ 的 slot 偏移量 (時間偏移量)
- $T$ : 每個 slot 的持續時間

這個算法是透過當前的時間以及 slot 位移量，來計算出特定 slot ($s$) 的實際時間。

### Algorithm 8. Median Algorithm

輸入：
- ${\mathfrak{{{E}}}}$ : 想要估算的同步週期
- $s_{sync}$ : 用於估算的 slot time

1. 初始化一個空的集合 $T_s$，用來儲存計算出來的 timestamp
2. 遍尋所有在同步週期 ${\mathfrak{{{E}}}}$ 中的區塊 $B$
3. 計算區塊 $B$ 的生產時間 ($t^B_{est}$)
$$
t^B_{est} = T_B + \text{Slot-Offset}(s_B, s_{sync}) \times T
$$
- $t^B_{est}$ 是計算出來的區塊 $B$ 的生產時間
- $T_B$ 是區塊 $B$ 的到達時間 (傳到 node, 驗證者記錄下的時間)
- $s_B$ 為區塊 $B$ 的 slot number，$s_{sync}$ 為當前同步的 slot number
- $T$ 是每一個 slot 的持續時間 ([Definition 59](https://spec.polkadot.network/sect-block-production#defn-epoch-slot))
4. 將 $t^B_{est}$ 加入 $T_s$ 集合中
5. 持續訪問在該週期中的區塊，直到所有區塊訪問完畢。
6. 回傳 $T_s$ 的中位數

> Definition 70. Pruned Best Chain
> 是指在最長鏈中，修剪掉最後 k 個區塊剩下的鏈
> 如果 k = 140，那個將會修剪掉最後 140 個區塊，在修剪完的最佳鏈中，最後一個(機率上)已確定的區塊，即為該修剪最佳鏈中的最終區塊

> Definition 71. Chain Quality
> - chain quality $s_{cq}$ 代表 slot 的數量，被使用來推估本地時間的偏差，目前 $s_{cq} = 3000$ (等同於更新週期的長度 ([Definition 73](https://spec.polkadot.network/sect-block-production#defn-sync-period)))
> - 為了進行這個計算，每一個區塊生產者必須儲存每一個區塊抵達的時間 (Definition 72)

> Definition 72. Block Arrival Time
> - $T^j_B$ 代表一個本地的時間，當 node j 接收到 block B 的時間點
> - 若 block B 就是 node j 所產生的，那麼 $T^j_B$ 將會等於區塊的產生時間
> - 如果不會造成混搖的話，可以將 j 在符號中捨棄，block B 的抵達時間可以被標視為 $T_B$

> Definition 73. Sync Period
> 同步週期 (${\mathfrak{{{E}}}}$) 是每個驗證者重新評估本機時間偏移的時間間隔
> - 第一個同步週期 ${\mathfrak{{{E}}}}_1$ 是在創世塊(genesis block)建立後就開始
> - 每個更新週期 ${\mathfrak{{{E}}}}_i$ 在前一個週期 ${\mathfrak{{{E}}}}_{i-1}$ 結束後開始
> - 更新週期的長度等於 $s_{qc}$ ([Definition 71](https://spec.polkadot.network/sect-block-production#defn-chain-quality))，並且以 slot 的數量表示。

Image 5. Median Algorithm 在第一個週期的執行範例，$s_{cq} = 9$, $k = 1$ 作為參數。

- 每個區塊上的數字代表 slot number,
- 可以發現有些 slot number 重複出現，代表有不同的區塊生產者，都在相同的 slot number 產生區塊。
- 在這個案例中，白色的區塊是最長鏈 (longest chain)，該路徑區塊數量最多且時間最早。
- Stored Arrival Times 是記錄區塊抵達該 node 的時間 (驗證者被要求記錄該資訊)
- Current Clock 是本機時間，需要定期被同步修正

> (自己理解的)解釋以下圖片 Median Algorithm 運作方式：
>
> #### 參數準備
>
> Median Algorithm 會傳入兩個參數：
>
> - 參數 $s_{cq} = 9$，代表著更新週期的範圍，等同於 9 個 slot。
> - `{11}` 將屬於下一個更新週期，所對應到的 current clock 為第 12 個 slot，因此 $s_{sync} = 12$
> - 參數 $k = 1$，代表要在最長鏈上，刪除最後一個區塊，來獲得修剪後的最佳鏈 (pruned best chain)
> - 最長鏈： `{0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11}`
> - 修剪後的最佳鏈： `{0, 1, 2, 4, 5, 6, 7, 8, 9, 10}`
>
> #### 開始執行 Median Algorithm:
>
> 輸入
> - ${\mathfrak{{{E}}}}$: `{0, 1, 2, 4, 5, 6, 7, 8, 9, 10}` ($node$ $j$ 在該更新週期內所記錄下的區塊)
> - $s_{sync}$ : 12 (同步的目標 slot)
>
> 步驟
> 1. 初始化一個時間集合 $T_S$
> 2. 遍尋同步週期內的區塊 (for B in ${\mathfrak{{{E}}}}$)
> - 推估該區塊的真實時間
> - 將該區塊真實時間加入 $T_S$
> 3. 回傳 $T_S$ 的中位數


## 5.4 Production Algorithm

- 在每個 epoch，每位區塊生產者應該要執行 Invoke-block-Authoring 演算法，來在被授予的 slot 中產生區塊
- 被產生的區塊需要包含 `Pre-Digest` (Definition 74) 以及 `Block Signature` (Definition 75)，作為 Pre-Runtime 及 Seal digest 的項目。

> [Definition 74. Pre-Digest](https://spec.polkadot.network/sect-block-production#defn-babe-header)
> TODO: 需要先閱讀第二章關於 block header 以及 Digest 相關資訊，會比較容易理解

### Algorithm 9. Invoke-Block-Authoring

輸入：
- $sk$: secret key
- $pk$: public key
- $n$: 第 n 個 epoch
- $BT$: Block Tree


> [Definition 75. Block Signature](https://spec.polkadot.network/sect-block-production#defn-block-signature)
> 區塊生產者對該區塊的簽名 (詳細資訊請參考官方文件)

## 5.5 Epoch Randomness

- 每個 epoch ($\varepsilon_n$) 開始時，將會從 Runtime 接收到隨機性種子 (randomness seed) $R_{\varepsilon_{n+1}}$ (Definition 76)，
- 隨機性種子會參與下一次 epoch $\varepsilon_{n+1}$ 的區塊生產抽籤
- 隨機性種子會透過 consensus message 放在區塊的 digest 中

> Definition 76. Randomness Seed
> - 隨機性種子 $R_{\varepsilon}$ 是一個 32-byte 的數值
> - 隨機性種子是基於前一個 epoch VRF 的輸出內容
> - $\varepsilon_0$ 以及 $\varepsilon_1$ 的隨機性種子，是由創世狀態提供 ([Section C.11.1.](https://spec.polkadot.network/chap-runtime-api#sect-rte-babeapi-epoch))
> 隨機性可以從 consensus message 中拿到

## 5.6 Verfiying Authorship Right

Polkadot 節點接收到區塊生成之後，會透過執行 Verify-Authorship-right 和 Verify-Slot-Winner 來驗證區塊生產者是否有權利在給定的 slot 裡面產生區塊

### Algorithm 10. Verify Authorship Right

TODO: 詳細算法請參考[官方文件](https://spec.polkadot.network/sect-block-production#algo-verify-authorship-right)

TODO: 驗證作者的資訊是否正確，需要先閱讀第二章，會比較容易理解區塊中儲存的內容。

### Algorithm 11. Verify Slot Winner

VRF 的輸出包含了隨機數與驗證方法，其隨機數會被使用於區塊抽籤時與 winning threshold 數值進行比較，來決定該驗證者是否能在該 slot 中進行區塊的產生。

而此演算法就是要使用對應的驗證方法，來檢查該區塊的生產者，是否為區塊抽籤中贏得這個 slot 的驗證者。


- Epoch-Randomness 定義於 [Definition 76.](https://spec.polkadot.network/sect-block-production#defn-epoch-randomness)
- $H_{BABE}(B)$ 是 BABE 的 header 定義於 [Definition 74.](https://spec.polkadot.network/sect-block-production#defn-babe-header)
- $(o,p)$ 是區塊抽籤的結果 (Block-Production-Lottery) 由 VRF 所輸出的隨機數與驗證方法
- Verify-VRF 於 [Section A.1.3.](https://spec.polkadot.network/id-cryptography-encoding#sect-vrf) 有介紹
- $T_{\varepsilon_n}$ 是 winning threshold 被定義於 [Definition 65](https://spec.polkadot.network/sect-block-production#defn-winning-threshold)

## 5.7 Block Building Process

區塊建立的流程，將會於 Invoke-Block-Authoring 觸發 Build-Block 的動作。

### Algorithm 12. Build Block

TODO: 詳細算法請參考[官方文件](https://spec.polkadot.network/sect-block-production#algo-build-block)

TODO: 驗證作者的資訊是否正確，需要先閱讀第二章，會比較容易理解區塊中儲存的內容。