---
reference: https://spec.polkadot.network/chap-state
---

# 2.1. Introdoction

**Definition 1. Discrete State Machine (DSM)**
:::info
State transition system 是一個 tuple
$$
(\Sigma, S, s_{0}, \delta)
$$
where

- $\Sigma$ 所有可能輸入的可數集合
- $S$ 所有可能 state 的可數集合
- $s_{0} \in S$ initial state
- $\delta$ state-transition function(STF, 狀態轉換函數)
- Polkadot 裡面稱為 ==Runtime==
$$\delta: S \times \Sigma \to S$$
:::

**Definition 2. Path Graph**
:::info

$P_{n}$ : 一條無分支, 含有 $n$ 節點的鏈(樹)

- 頭跟尾的 vertex degree=1
- 其他 $(n-2)$ nodes 的 vertex degree=2
- 可表示為以下數列
$$P_{n}=(v_{1}, v_{2}, ...,v_{n})$$
where
- $e_{i}=(v_{i}, v_{i+1})$ for $1 \le i \le n-1$ 是連結 $v_{i}$ 與 $v_{i+1}$ 的邊 (edge)
:::

**Definition 3. Blockchain**
:::info
Blockchain $C$ 是一個 directed path graph (有向圖)

- 圖中每一個 node 都看成一個 **Block** called $B$
- unique sink of $C$ called **Genesis block**
- source is called Head of $C$
- 對於任意頂點 $(B_{1}, B_{2})$ where $B_{1} \to B_{2}$
- $B_{2}$ 是 $B_{1}$ 的 **parent**
- $B_{1}$ 是 $B_{2}$ 的 **child**
- 表示成
$$B_{2}:=P(B_{1})$$
<img src="https://hackmd.io/_uploads/HyRrUKDZ1g.png" width="40%">

child 會去引用 parent 的 hash value ([Definition 10](/eATgSX25QU6eR57zh8SOXQ?both=&stext=3681%3A38%3A1%3A1731600947%3A4eDUEs)), 以防篡改 (tamper-proof) 路徑圖

- 一旦對 child 做任何修改就會影響到 hash value

:::

## 2.1.1. Block Tree

- Block 是一條一條的 chain 起來的，但是有時會因為網路延遲等原因區塊鏈就會 fork(分叉)成多條 subchain(子鏈)。這種資料結構稱為 block tree。

**Definition 4. Block**
:::info
區塊鏈的 BT(Block Tree) 是被 Polkadot Host 觀察所有不同版本的區塊鏈組成的一個 union

- 所有 block 都是圖中的一個 nodes, $B_1$ 被連接到 $B_2$ 如果 $B_{1}$ 是 $B_{2}$ 的 parent
:::
當最後一個區塊在 $BT$ 中被確定時，有機會可以修剪 $BT$ 以釋放區塊鏈的資源，去除那些尚未被確定或是永遠不會被確定的區塊

**Definition 5. Pruned Block Tree(PBT)**
:::info
修剪過的 $BT$ ，指的是去除那些不包含最新確定區塊的分支。

- 修剪過程: $BT \leftarrow PBT$
- 當修剪樹枝後不會造成有歧義的風險時，我們使用 $BT$ 來指稱 $PBT$
:::

[Definition 6](/eATgSX25QU6eR57zh8SOXQ?stext=1925%3A26%3A1%3A1731599416%3Ahbm3XJ&both=) 提供凸顯 $BT$ 各分支的方法
**Definition 6. Subchain**
:::info
$G$ 是 $BT$ 的根(root)，$B$ 是 $BT$ 裡的其中一個 node。

- $\mathrm{Chain}(B)$ 指的是在 $BT$ 中從 $G$ 到 $B$ 的 path graph
- path graph 其實就是一條鏈
- 對於鏈 $C=\mathrm{Chain}(B)$ :
- 我們定義 **C 的頭(head)** 為 $B$
$$B = \overline{C}$$
- 定義 $|C|$ 為 path graph 的長度

如果 $B^{\prime}$ 是 $\mathrm{Chain}(B)$ 中的另一個 node

- 定義 $\mathrm{Subgraph}(B^{\prime}, B)$ 為從 $B$(head) 到 $B^{\prime}$(root) 的 subgraph
- 定義 $|\mathrm{Subgraph}(B^{\prime}, B)|$ 為 subgraph 的長度
- $\mathbb{C}_{B^{\prime}}(BT)$ 定義為以 $B^{\prime}$ 為 root 的 $BT$ 的 subchain 集合
- $BT$ 中所有鏈的集合，可表示成 $\mathbb{C}_{G}(BT)$ = $\mathbb{C}_{G}$ = $\mathbb{C}$
:::

**Definition 7. Longest Chain**
:::info
如何決定 $C_1$, $C_2$ 誰是最長的鏈？

- 比較鏈的長度：
- 如果 $|C_1| > |C_2|$，那麼 $C_1 > C_2$
- 若長度相同 $|C_1| = |C_2|$，則比較最後一個區塊的抵達時間 ([Definition 72](https://spec.polkadot.network/sect-block-production#defn-block-time))
:::

**Definition 8. Longest Path**
:::info
- $\mathrm{Longest-Path}(BT)$ 此函數會回傳 $BT$ 中含有最早區塊到達時間的最長路徑 ([Definition 72](https://spec.polkadot.network/sect-block-production#defn-block-time))
- $\mathrm{Longest-Leaf}(BT)$ 此函數會回傳 $\mathrm{Longest-Path}(BT)$ 鏈的 head
:::

因為區塊鏈中的所有區塊都包含對其 parent 區塊的資訊，所以事實上(de facto) $BT$ 就是一顆樹。所以 $BT$ 會自然的對區塊有 partial order 的關係

**Definition 9. Descendant and Ancestor**
:::info
- $B > B^{\prime}$ : $B$ 是 $B^{\prime}$ 的後代
- $B < B^{\prime}$ : $B^{\prime}$ 是 $B$ 的祖先
:::

# 2.2. State Replication
Polkadot 節點的複製是藉由同步 extrinsics(外部指令)的歷史紀錄。但是，只有在大量交易被同時批量處理並且同步時才有實用性。Extrinsics 結構組成看 [章節 2.2.1](#2.2.1.-Block-Format) 。Polkadot 節點之間可能會出現狀態不一致的狀況，就像其他複製的 state machine 一樣。

## 2.2.1. Block Format
- 一個 Polkadot 區塊是由 一個 **block header** 和 一個 **block body** 組成。
- Block body 由 extrinsics 組成，而 extrinsics 是交易概念的泛化。
- Extrinsics 可以包含底層區塊希望驗證和追蹤的任何一組外部數據。

**Block Header** 是一個 5-tuple 元素，其中包含 :
- parent_hash : 32-byte [Blake2b hash值](https://spec.polkadot.network/id-cryptography-encoding#sect-blake2)，由 SCALE 編碼的 parent block header 計算而來。
- number : 當前區塊鏈中的索引。表示此區塊的祖先區塊數量。創世狀態的編號為 0。
- state_root : Merkle trie 的根結點。Merkle trie 的 leaves 實作系統的儲存系統。
- extrinsics_root : 讓 Runtime 驗證 block body 的 extrinsics 的完整性。
- digest : 用來儲存任何與鏈相關的輔助資料，幫助 light clients 與區塊互動而無需存取完整的 storage 和共識相關的資料，包含區塊簽名。

**Header Digest** : 是一個由多個 digest items 組成的陣列，這些 digest items 具有不同的資料型態。[(詳細細節看 Polkadot spec)](https://spec.polkadot.network/chap-state#defn-digest)

**Block body** : 由一連串的 extrinsics 組成，每個 extrinsics 被編碼成一個 byte array。Extrinsics 的內容對 Polkadot Host 是不透明的。因此，從 Polkadot Host 來看，block body 只是一個使用 SCALE 編碼的 byte arrays。

# 2.3. Extrinsics
區塊的主體由一系列 Extrinsics 組成。廣義上來說，Extrinsics 是來自狀態之外的資料，可觸發狀態轉移。
## 2.3.1. Preliminaries
### Extrinsics 分類：
- Transaction(交易) Extrinsics: 用戶簽名並廣播到網絡的交易。
- Inherent(固有) Extrinsics: Polkadot Host 生成，僅包含在該節點產生的區塊中。
### Extrinsics 的角色：
- 觸發狀態轉移： Extrinsics 是外部數據，可以引發區塊鏈狀態的變化。
- 區塊組成部分： Extrinsics 是區塊的主體，每個區塊包含多個 Extrinsics。
### Polkadot 主機的處理：
- 不限制 Extrinsics 的內部結構： Polkadot 主機不對 Extrinsics 的具體格式和內容進行限制。
- 視為二進位數據： Polkadot 主機將 Extrinsics 視為二進位序列，由運行時負責解碼和處理。
## 2.3.2. Transactions
### 交易的提交和傳播：
- 網絡傳輸： 交易通過 Transactions Network 提交。
- 本地提交： 交易也可以通過離線工作者（Off-chain Worker）透過 Host API提交。
### 交易的驗證和處理：
- 提交給 Runtime： 所有新交易都會提交給 Runtime。
- 驗證交易有效性： 運行時檢查交易是否符合當前狀態和規則。
- 廣播交易： 如果交易有效，Polkadot Host 會將其廣播給其他節點，並會避免重複傳輸。
- Transaction Pool & Transaction Queue： Polkadot Host 使用 Transaction Pool 和 Transaction Queue 來管理待處理和已傳輸的交易。
## 2.3.3. Inherents
Inherents Extrinsics 是一類特殊的 Extrinsic，由區塊生產者直接插入到區塊中，而不是通過網絡廣播。它們主要用於提供區塊的上下文信息，例如區塊的生成時間、鏈接的平行鏈等。

### 生成過程：
- Polkadot 主機提供數據： 主機提供一些固有數據，例如區塊的時間戳、BABE 時隙、平行鏈信息等。
- 運行時生成 Extrinsics： 運行時使用 BlockBuilder_inherent_extrinsics 函數，根據提供的數據生成固有 Extrinsics。
- 插入區塊： 生成的固有 Extrinsics 被直接插入到當前區塊中。
### 數據類型：
- Timestamp： 區塊生成的時間。
- BABE Slot： 與 BABE 共識算法相關的 Slot 信息。
- Parachain inherent data： 有關平行鏈的候選者和相關數據。

# 2.4. State Storage Trie
Polkadot Host 用 hash table 來儲存 state 的資訊，每個 key 都有相對應的 data entry。
除了有 byte array length 的上限 ([Section A.2.2.1.](https://spec.polkadot.network/id-cryptography-encoding#sect-sc-length-and-compact-encoding))。因為 encoding algorithm 在 storage trie 中儲存 key-value 時限制的。

## 2.4.1. Accessing System Storage
我們將存取 storage 公式化
**Stored value**
函數 $\mathrm{StoreValue}$ 檢索 state storage 中儲存在特定 key 下的 value
$$\mathrm{StoredValue}: \mathcal{K} \to \mathcal{V}$$
- 找到對應的 key-value pair，沒找到就是 $\phi$ (empty)

## 2.4.2. General Structure
為保持系統 state 的 integrity(完整性)，儲存的 data 需要在 *radix tree* 進行重新排序並 hash
- *radix tree* = **state trie** or **trie**

為了在給定時間內一致且有效的計算全部/部分 state storage 的 Merkle hash，重新排列是必要的。

Trie 是用來計算 state 的 *Merkle root*([$\mathrm{H}_{r}$](https://hackmd.io/eATgSX25QU6eR57zh8SOXQ?both=&stext=3728%3A38%3A1%3A1731933643%3Amp3-jq))，為了驗證 state database 的有效性(Validity)。
Polkadot Host 會用 encoding algorithm 來計算那些儲存在 trie nodes 的 value，以確保計算的 Merkle hash($\mathrm{H}_{r}$) 與 Polkadot Host 實際運行的是相符的。

## 2.4.3. Trie Structure
## 2.4.4. Merkle Proof
## 2.4.5. Managing Multiple Variants of State
# 2.5. Child Storage
## 2.5.1. Child Tries
# 2.6. Runtime Interactions
## 2.6.1. Interacting with the Runtime
## 2.6.2. Loading the Runtime Code
## 2.6.3. Code Executor