---
依靠 validator 的 assurance 判斷哪一個 core 的資料是可用的

代表 core 出問題，可能會有一些機制去重啟 core or what ? 待補充..

---

# XI. Guarantee, Assurance, Availability

目標 :
1. 為了後續的 auditing 可以下載完整以及正確的資料，需要確認 report 的 availability
2. 在 accumulation 前，確認 in-core 的計算結果無誤

方法 : 計算收到驗證者所提交的 assurance $\mathbf{E}_A$ 數量，只要收到超過 $\frac{2}{3}$ 個驗證者提交的 assurance，該 report 就會被視為 available

## 前情提要

- Work package 是由 work items 所組成
- In-core 階段，會由 core 執行 work items 的計算邏輯產生 work output
- 由 guarantor 擔保由 core 產生 work report (work report 包含 work output)
- work report 的資料被切割(erasure coding) 成 segments 分配給 validator 做驗證
- work outputs 對應到 work results， work results 被封裝到 work report，準備提交到鏈上


## 11.1. State
定義 Work report 的狀態

:::info
$\rho$ : work-report 的初始狀態，正在被確認 availability，還未進入 accumulation。
$w$ : work-report
$\mathbb{W}$ : work-report set
$t$ : timeslot，用於確認 work report 是否 timeout
$\mathbb{N}_T$ : timeslot
C : core 數量
:::

### 11.1.1. Work Report
定義 Work report 的內容，不包含 work report 產生的過程

:::info
$\mathbb{W}$ : work report 集合
$s$ : work-package 規範(specification)
$\mathbb{S}$ : work-report 規範集合
$x$ : refinement context
$c$ : core-index
$a$ : 授權者(authorizer) hash
$\mathbf{o}$ : authorizer output
$\mathbb{Y}$ : octet strings/blobs set
$l$ : segment-root lookup dictionary
$\mathbf{r}$ : work results，1 <= #item <= I
$\mathbb{L}$ : work results 集合
I : item 數量
:::

限制 work items 的大小，避免有工作量大的 spam
:::info
J = 8
$w_\mathsf{l}$ : work-report 的 segment-root lookup dictionary
$\mathbf{p}$ : prerequsitie package
:::

### 11.1.2. Refinement Context

定義 refine 的上下文

:::info
$a$ : anchor on header hash
$s$ : posterior state root，儲存狀態變化的 Merkle trie 的 root
$b$ : posterior BEEFY root
$l$ : lookup-anchor，儲存 refine 的計算過程在 lookup anchor block
$t$ : timeslot
$\mathbf{p}$ : prerequisite work-packages
:::

### 11.1.3. Availability

:::info
$h$ : work package hash
$l$ : 可審查(audit)的工作綑綁包(work bundle)長度 (section 14.4 會定義)
$u$ : erasure-root
$e$ : segment-root
$n$ : segment-count
:::

### 11.1.4. Work Result


:::info
$\mathbb{L}$ : work results 集合
$s$ : state 要被改變或 refine code 要被執行的 service index
$c$ : 被 reported 的 service code hash
$l$ : work item 的 payload hash，在 refine 階段會產生，在 accumulation 的邏輯會使用到
$g$ : gas prioritization ratio，決定執行 item 的 accumulation 需要多少 gas
$\mathbf{o}$ : work outputs
$\mathbb{Y}$ : octet string
:::
output error 或 code error
:::info
$\mathbb{J}$ : work output 或 code error
$\infty$(out of gas) : gas 不足 error
閃電(panic) : unexpected program termination
$\mathbf{BAD}$: 在 lookup-anchor block 裡的 code 不可用
$\mathbf{BIG}$: code 可用，但是超過限制的大小
:::

為了確保公平地使用區塊的 extrinsic space，要限制 work-reports 的 size。

:::info
$w_\mathsf{o}$ : report 的 authorizor output
對於所有的 work results 的所有成功的($\notin \mathbb{J}$) work outputs 大小總和 $\le \mathsf{W}_R$

:::

## 11.2.1. [*The Assurances* Extrinsic](https://graypaper.fluffylabs.dev/#/911af30/142400142400) Eq. 11.8~11.14
Assurance extrinsics $\mathbf{E}_A$ 是 validator 接收到 erasure coded segments 之後驗證接收到的資料無誤，向鏈上提交的**保證**。
- Assurance 只驗證 work-package 資料的正確性，不驗證邏輯。
:::info
$\mathbf{E}_A$ : assurance extrinsic, 一個序列的 assurance 值，一個驗證者最多只會有一個
$a$ : anchor
ℍ : hash function
f : 對每一個 core 的可用性
$𝔹_c$ : bitstring, 長度為C, 讓驗證者聲明哪些核心的資料是可用的。
$v$ : validator index
V : validator set
$s$ : signature，validator 的 public key
𝔼 : 簽名集合

假設有 3 個 core A, B, C
val1 認為 core A,B 的資料是可用的 => bitstring : 110
:::

- 所有的 anchor 都需要指向 parent hash，用於追蹤和驗證
- assurance 要依照 validator index 排序
:::info
$a_{a}$: anchor
$\mathbf{p}$ : header 的 parent hash
:::

- 簽名會附帶 jam_available 訊息與序列化的 parent hash 和 bitstring
- work report 會被包在 guarantee extrinsics 後提交到鏈上

:::info
$\kappa^{\prime}$ : guarantees assurances 的 validator set
$\langle$ $\rangle$ : 簽名附帶的 message
ℌ : Blake 2b 256-bit hash function
𝓔 : octet-sequence encode function
X$_{A}$: bitstring，用於識別是哪種訊息，這邊指的是 jam_available
^ : sequence 串接
$a_{f}$ : bitstring

:::
- core 必須要在有 pending avabilable 的 report 才可以設定 bitstring，而且提交 assurance 沒有發生 timeout。

:::info
U = 5: 超過 5 個 timeslots 就 timeout
:::
---
## 11.2.2. Availability Reports
定義在 core 裡等待被 available 的 work-report，只要接收到 $\frac{2}{3}$ 以上的 validator assurances 就可以被視為 available。
> 從 validator 的角度 : 這個 core 傳送的資料是有效的
> 從 core 的角度 : work-report 是 available


:::info
$\mathbf{W}$ : work report
$\rho^{\dagger}$ : pending available work-report 的中繼狀態。
$c$ : core
C : core set
:::
已經 available 的 report 會被剃除，在定義 $\delta^{\prime}$ (accumulation) 和 $\rho^{\ddagger}$ 會被使用到。

:::info
$\rho^{\ddagger}$ : 已經 guaranteeing，還未 assuring
$\rho^{\dagger}$ : 已經 judging，還未 guaranteeing
$\rho$ : 正在驗證 available，等待進入 accumulation

當有一個 core 處理的 work package 被視為 available 時，狀態會被移除。
否則，$\rho^{\ddagger}\equiv\rho^{\dagger}$
:::

## 11.3 [*Guarantor* Assignments](https://graypaper.fluffylabs.dev/#/911af30/145e01145e01)
:::info
$G$ : Guarantor
$⟦\mathbb{N}_\mathsf{C}⟧_{\mathbb{N}_V}$ : 屬於哪個 Core
$⟦\mathbb{H}_K⟧_{\mathbb{N}_V}$ : Validator Key(Ed25519)
:::


:::info
(11.18) Rotation Function: 把 $\mathbf{c}$ 中 $\mathcal{x}$ 的平移 $\mathcal{n}$

(11.19) Permute Function: 拿來排列用的，先 shuffle 然後輪轉
* $\mathcal{F}$(.) Fisher Shuffle Function: 會吃兩個參數 (Squence, seed(entropy))
* $\lfloor\frac{\mathsf{C} \cdot \mathcal{i}}{\mathsf{V}}\rfloor$ 應該被寫成 $\lfloor\frac{\mathsf{C}}{\mathsf{V}} \cdot \mathcal{i}\rfloor$ 會比較好理解
* see [0, 0, 0, 1, 1, 1, 2, 2, 2,...]
* $\lfloor\frac{\mathcal{t} \mod \mathsf{E}}{\mathsf{R}}\rfloor$ 每 $\mathsf{R}$ = 10 秒 輪轉一次

(11.20) $\mathbf{G}$: 正式定義為 ( 重新排列的 Core, 被過處理的 $\mathcal{k'}$ )
(11.21) $\mathbf{G}^*$: 上一輪的 $\mathbf{G}$，用來檢查上一輪的 $\mathbf{G}$
* $\lfloor\frac{\tau' - \mathsf{R}}{\mathsf{E}}\rfloor$ = $\lfloor\frac{\tau'}{\mathsf{E}}\rfloor$ 檢查同個 epoch
:::

## 11.4 [Work Report *Guarantees*](https://graypaper.fluffylabs.dev/#/911af30/144c02144c02)
:::info
(11.22) $\mathbf{E_G}$ 由 [$\mathcal{w}$, $\mathcal{t}$, $\mathcal{a}$] 構成
* $\mathcal{w}$: work report
* $\mathcal{t}$: time
* $\mathcal{a}$: crendential

(11.23) $\mathbf{E_G}$ 需要根據 core 順序排序
:::

:::info
(11.24) $\mathcal{g}$: work report
* $\mathcal{g_a}$: crendential 憑證，由 [$\mathcal{v}$, $\mathcal{s}$] 構成
* $\mathcal{v}$: validator index
* $\mathcal{s}$: signature
* $(\mathbf{k}_{v})_{e}$ 這樣表示的 key 長怎樣?
* $\mathbf{k}_\mathcal{v}$ 是分配到該 work report 的 validator 的 key
* $(\mathbf{k}_{v})_{e}$, is the second 32 octets.(see: [(6.10)](https://graypaper.fluffylabs.dev/#/911af30/0d97010d9701))
* 
* $\mathbb{H}_\mathbf{E}$ The set of Ed25519 public keys

(11.25) ($\mathbf{c}$, $\mathbf{k}$): core 和 validator 的選擇取決於是不是同個 Rotation Time

:::

:::info
(11.28) $\mathcal{g}$: work report
* $\mathcal{w}$: work report

每一個 $\mathcal{w}$ implies 兩件事情:
1. 尚未處理完全的  為空或是距離上一次提交 report 的時間超過 $\mathsf{U}$ = 5 timeslots
2. 他的 $\mathcal{w_a}$ (authorizer hash)，存在 authorizer pool 裡面
:::


:::info
(11.29)
1. $\sum_{ r \in \mathcal{w}_r } (\mathcal{r}_g) \leq \mathsf{G}_A$: 所有的 work result gas 加總要小於等於 $\mathsf{G}_A$
* $\mathcal{r}_g$: work result 的 gas
* $\mathsf{G}_A$: 100,000 The total gas allocated to a core for Accumulation

2. $\mathcal{r}_g \geq \delta[\mathcal{r}_s]_g$: 每一筆 work result gas 要大於等於該 service account 最小的 required gas.
* $\delta$: The (prior) state of the service accounts.
:::

### 11.4.1. Contextual Validity of Reports


:::info
(11.30)
1. $\mathbf{x}$: extrinsic 裡 全部 contexts 的 集合
2. $\mathbf{p}$: extrinsic 裡 全部 work-package hash( ($\mathcal{w}_s)_h$ ) 的集合

:::danger
註: 這個 $\mathbf{p}$ 是 package hash( $(\mathcal{w}_\mathbf{s})_h$ ) 不是 prerequisite( $(\mathcal{w}_\mathbf{x})_p$ )
:::

:::


:::info
(11.31)
$\mathbf{p}$ 的長度會跟所有 work report 形成的集合一樣長，因為一個 work report 只會有一個 hash
:::


:::info
(11.32) 對於每一個 work report 的 **context**，錨定區塊（anchor block）必須位於最近的 H 個區塊之內，並且通過確認它出現在我們最近的區塊集合 $\beta$ 中來確保其詳細資訊是正確的。

$\beta$: the most recent blocks
* [$\beta$ 如何更新?](https://hackmd.io/8ENyojJxT06CscW7asWGCQ)

1. $\mathbf{x}_a$ = $\mathcal{y}_h$: $\mathbf{x}_a$ 錨定要指向 $\mathcal{y}_h$
* $\mathbf{x}_a$: anchor
* $\mathcal{y}_h$: $\mathcal{y}$ block 的 header hash
2. $\mathbf{x}_s$ = $\mathcal{y}_s$: $\mathbf{x}_s$: $\mathbf{x}_s$ 要指向 $\mathcal{y}_s$
* $\mathbf{x}_s$: posterior state-root
* $\mathcal{y}_s$: $\mathcal{y}$ block 的 state root
3. $\mathbf{x}_b$ = $\mathcal{H}_{K}(\mathcal{E}_M(\mathcal{y}_b))$: ==??-->==[等第七章完成](https://hackmd.io/8ENyojJxT06CscW7asWGCQ)
* $\mathbf{x}_b$: posterior Beefy root
* $\mathcal{H}_{K}(\mathcal{E}_M(\mathcal{y}_b))$:
:::

:::info
(11.33)
對於每一個 work report 的 **context**，lookup-anchor time 必須在過去 $\mathsf{L}$ timeslots 以內。

$\mathsf{L}$ = 14,400 timeslots

:::

:::info
(11.34)
對於每一個 work report 的 **context**，都會存在一個祖先 block符合以下兩件事情。

1. $\mathcal{h}_t$ = $\mathcal{x}_t$:
lookup-anchor time($\mathcal{x}_t$) 必須等於 某個祖先的 timeslot index($\mathcal{h}_t$)

2. $\mathcal{H}(h)$ = $\mathcal{x}_l$:
lookup-anchor header hash($\mathcal{x}_l$) 必須等於 某個祖先的 header hash

:::danger
註: anchor block 及 lookup-anchor block 是不同的東西 ==--> 差別是?==
:::

:::


:::info
(11.37)
對於每個 work package ($\mathcal{p}$)，皆不屬於下面四個 set:
1. $\bigcup_{\mathcal{x}\in\beta} \mathcal{K}(\mathcal{x}_\mathbf{p})$: Recent block 的 package/report
* $\mathcal{K}$(.): The set of keys of a dictionary.
* $\mathcal{x}_\mathbf{p}$ 是 **recent block** 的 work-pakage **dictionary**

:::danger
請注意看好 $\mathcal{x} \in \beta$，$\mathcal{x}$ 不是 $\mathcal{w}_x$
:::

2. $\bigcup_{\mathcal{x}\in\xi} \mathcal{x}$: 這個 epoch 所有的歷史 package/report
* $\xi \in ⟦\mathbb{H}⟧_\mathsf{E}$
* $\mathsf{E}$ = 600: The length of an epoch in timeslots

:::danger
請注意看好 $\mathcal{x} \in \xi$，$\mathcal{x}$ 不是 $\mathcal{w}_x$
:::

3. $\mathbf{q}$: 正在被決定的 report ( $\vartheta$ 是 accumulation queue) 的 prerequisite
==待補充見 ch.12==

4. $\mathbf{a}$: 還沒被決定 (judge, garantee) 的 report ( $\rho$ 是 pending report) 的 prerequisite
* $\rho$ 的定義: pending reports
* 

:::

:::info
(11.38)
對於每一個 work report，都存在有一個 work package (來自於 prerequisite($\mathcal{w}_\mathbf{p}$) 或是 segment-root lookup dictionary($\mathcal{w}_\mathbf{l}$) ==--> $\mathcal{w}_\mathbf{l}$?==

這個 $\mathcal{p}$ 會符合以下**兩個條件之一**:
1. 要嘛來自 Extrinsics($\mathbf{p}$)
2. 要嘛來自 recent history($\beta$)
:::

:::info
(11.39, 11.40)
對於每個 work report 我們要確保 segment-root lookup($\mathcal{w}_\mathbf{l}$) 被包含於 present block 或是 recent work-package history。

1. $\mathbf{p}$: present block dictionary set，由 { $(\mathcal{g}_\mathcal{w})_{\mathcal{h}}$ : $(\mathcal{g}_\mathcal{w})_{\mathcal{e}}$} 組成的 dictionary set:
* $(\mathcal{g}_\mathcal{w})_{\mathcal{h}}$: work-package 的 hash
* $(\mathcal{g}_\mathcal{w})_{\mathcal{e}}$: work-package 的 segment-root

2. $\bigcup_{\mathcal{b}\in\beta} \mathcal{b}_\mathbf{p}$: recent work-package history dictionary set
:::

:::info
(11.41)
對於每個 work report 都存在有一個 work result($\mathcal{r}$)，我們必須確保
* $\mathcal{r}_c$ = $\delta[\mathcal{r}_s]_c$
* $\mathcal{r}_c$: 這個 work result 的 code，也就是說其實你應該知道 service account 的 code hash 長怎樣。
* $\delta[\mathcal{r}_s]_c$: The (prior) state of the service accounts 用 work result index 去取得的 code hash
> We include the hash of the code of the service at the time of being reported c, which must be accurately predicted within the work-report.

:::

## **[11.5. Transitioning for Reports](https://graypaper.fluffylabs.dev/#/911af30/15b50115b501)**

:::info
(11.42)
對於每個 core，我們定義:

${\rho}'$ = ${\rho}^‡$

除了某些情況下存在有任何一筆外部資料（extrinsic）取代了一個項目（entry）。
在這種情況下，新值將包括當前時間 ${\tau}'$，這樣可以在足夠的時間過去後，不考慮該值的可用性（availability）而對其進行取代。(see: 11.28)
:::

==$\mathcal{E}_{\mathcal{M}}$ 裡 $\mathcal{M}$ 的用途(應該要是個長度?)==