# XVII. Auditing and Judging

# (驗證 garantee 封裝內容對不對, 在 accumulate 之後)

審計與判斷系統在理論上等同於 Elves 協議中由 Jeff Burdges、Cevallos 等人在 2024 年提出的機制。關於該機制的完整安全性分析，請參閱該研究。在術語上有所不同。

* Elves 協議是一個分布式協議，主要用於處理區塊鏈系統中的驗證與共識，特別是針對區塊的支持、批准和包含機制進行安全性設計。

| Elves | Jam | Explanation |
| -------- | -------- | -------- |
| Backing（支持）| Guaranteeing（保證）| 這是對某個候選區塊的初步支持，通常由一組驗證者確認其基本合法性與有效性。|
| Approval（批准）| Auditing（審計）| 對區塊進行深入檢查，驗證其內容是否符合協議規範（例如交易有效性）。|
| Inclusion（包含）| Accumulation（累積）| 將審計通過的區塊納入到鏈中，這是一個最終確認的過程，保證區塊被正式記錄。|

## 17.1. Overview

Auditting 要求每個節點對來自 Jam 鏈中每個區塊的新工作報告（work-reports）進行**隨機但確定性的提取、評估和裁定（judgment）**。在進行任何評估之前，

節點需要聲明並證明其對審計的需求。在隨後的特定公共時間點，如果出現 **Wonky** 的狀況，節點需要擴大其審計的工作報告集合。這些擴展事件被稱為 **tranches**。

如果 Work Report 的所有聲明意圖均獲得正面裁定，則該 Work Report 被視為 Audited。
如果某 Block 內的所有新工作報告都是 Audited，則該 Block 被視為 Audited。
**Finalised Block 的 ==其中?== 一個必要條件就是 Audited。**

需要注意的是，雖然最終會對某區塊是否已被審計達成共識，但這種共識可能不會在該區塊被最終確定時立刻達成。然而，這並不影響該系統的加密經濟保障。 在正常運作中，工作報告最終不會出現負面裁定，因此審計階段不會有直接後果(fallback, fork)。但在少見情況下，如果某工作報告有負面裁定，則可能發生以下幾種情況：
1. 如果超過 $\frac{2}{3}V$ 的裁定為正面，則發出負面裁定的驗證者可能因浪費時間而受到懲罰。
2. 如果負面裁定超過 $\frac{1}{3}V$，則包含該工作報告的區塊會被列入 禁列表（ban-listed）。該區塊及其所有後續區塊將被忽略，並且無法繼續構建。

無論哪種情況，一旦獲得足夠的裁定票數，區塊作者可構建一個 Judgment Extrinsic($\mathbf{E}_D$) 並將其上鏈以記錄結果（具體內容請參見第 10 節）。 所有聲明和裁定都會連同相關元數據（簽名的材料）一起向所有驗證者公佈。驗證者在收到這些確定的數據後，應更新（$J$ 和 $A$）。

## 17.2. [Data Fetching](/@JAM4Polkadot/Content/%2F%40JAM4Polkadot%2FrymWBYJNyl#1431-Exporting)

針對每個需要審計的工作報告（work-report），我們使用其 erasure-root 來向足夠數量的保證者（assurers）請求 erasure-coded chunks。從每個保證者處提取三類項目（如果網絡協議良好，應能通過單次請求完成）：

1. work-package super-chunks，
2. extrinsic segments super-chunks。
3. self-justifying imports super-chunks

我們可以通過以下方式照順序驗證重構數據的準確性：

1. 確保重構的 work-package hash 與 work-report 裡面 work-package specification 的 hash 相等。

2. 驗證 extrinsic segments，確保每個 hash 都與 work-item 的 hash 相符。

3. 驗證每個匯入的 segment。因為 justification 需遵從 concatenated segments。這可以確認每個 segment 的 hash 包含在 work-item 的 Merkle root 和 index of the corresponding work-item 中。

對於 Exported segments，不需要以相同方式重構，而是應通過執行 Refine 邏輯 來確定其正確性，這與保證（guaranteeing）過程中的方法一致。

Work-package specification 經過上面的驗證後的數據進行重新計算，並被驗證其正確性。這就是 Auditting。

## 17.3. [Selection of Reports](https://graypaper.fluffylabs.dev/#/911af30/1d2d001d2d00)

每一位 validator 都應該要對收到的有效 Block 盡到 auditing dity，檢查區塊的有效性與正確性。

* 確保區塊中所有 Extrinsic 跟 STF 都有照 protocol 做，無違規行為

:::warning
**這邊是 off-chain logic**，全部都是鏈下運作，並沒有 consensus 可以用，所有 validator 都應該**獨立運作**使用自己的 local data 跟收到的區塊做審計。
:::

考慮角度 :

* validator index $i$
* recent block $\mathbf{B}$
* $\rho$ : 區塊 $\mathbf{B}$ 之前的 core allocation
* $\kappa$ : 區塊 $\mathbf{B}$ 之前的有效 validator set
* $\mathbf{H}$ : header

Validator $i$ 收到區塊 $\mathbf{B}$，驗證 $\rho$, $\kappa$, $\mathbf{H}$

:::info
定義準備審查的 work report 序列為 $\mathbf{Q}$(可以是空集合)

* $\left[[.\right]]_{\mathsf{C}}$ : 序列的長度為 # of cores。

實際上是將所有 core 處理的 work report 拿出來做審計

* 讀進來的 core 裡面的 work report 是 available -> 提出
* 如果尚未 available，則設為 $\varnothing$ (沒必要審查)
* $\mathbf{W}$ : The sequence of work-reports which have now become available and ready for accumulation
:::


定義一開始可驗證的隨機數 tranche evidence $s_{0}$。由 validator $v$ 簽章

* 當成 initial state 對於 Header 來說(?
* 屬於此 $\mathbf{H}_{v}$ 中的 validator $v$ 正在審查
* ==這樣是只有 header 的作者 $\mathbf{H}_{a}$ 需要做審查?==
* 有可能, 因為這邊只是定義 initial state
:::info
使用 VRF function 來生成 (需要隨機生成所以用 vrf)

* 使用活躍驗證者集合 $\kappa$ 中編號 $v$ 的 bandersnatch 金鑰 $b$
* 簽章內容 : jam_audit | hash(==ID of validators?==)
* $\mathsf{X}_{U}$ : $jam_audit: Bandersnatch Audit selection entropy
* $\mathbf{H}_{v}$ : [the entropy-yielding vrf signature](/ek3wRMPERIudG41mFuirfA?stext=9021%3A51%3A1%3A1733471038%3AuxxdZ_&both=)
* 
* $\mathbf{H}_{a}$ : 區塊作者的 $pk$
* $\mathbf{H}_{s}$ : header seal?
* remind : $i_{\mathbf{y}}$ for ticket hash

:::


定義非零的 item $\mathbf{a}_{0}$，審查批次(audit tranche)，等待審制的報告
:::info

* $c$ : core
* $w$ : work report
* $w\neq \varnothing$ : 只審查有內容的 work report
* $\mathbf{p}_{...+10}$ : 從 set $\mathbf{p}$ 中隨機選最多 10 個項目
* 資源有限的環境中也可進行審查

從 core set $\mathbb{N}_{\mathsf{C}}$ 中讀取 core $c$ 與其==數據 $\mathbf{Q}_{c}$(work report 的序列)==，並將序列做洗牌

* $Q_c$ 是index
* $\mathcal{F}$ : shuffle function ; more info in appendix F
* $r=\mathcal{Y}(s_{0})$ : random seed ($v$ 的 identity)
* 藉由上面 vrf function 的 $s_{0}$ 的 output(hash) 來對序列做排序
:::

---

定義 JAM 中的當前批次(current tranche) $n$ 為 $\mathsf{A}=8$ 秒一次
:::info

* $n$ : 目前的批次(current tranche)
* $\mathcal{T}$ : The current time expressed in seconds after the start of the Jam Common Era. See section 4.4.
* $\mathsf{P}=6 \text{ sec}$ : slot period
* $\mathsf{A}= 8 \text{ sec}$
* $\mathsf{P}\cdot\mathbf{H}_{t}$ : 區塊高度對應的時間 (slot週期*區塊高度)
* $\mathcal{T}-\mathsf{P}\cdot\mathbf{H}_{t}$ : 在區塊內對應的時間
:::

:::success
為何鏈下的 audit 會跟鏈上的時間有關? -> 不會直接影響到鏈上, 但還是自己訂一個鏈下的時間

1. 因為審查的 work report 牽扯到 STF 的轉換，需要與鏈上的時間做一定程度的同步。
2. audit 的機制也是在新的區塊生成後觸發的。
:::
:::success 下面內容的 summary
**有哪些情況新一輪會保留上一輪 $\mathbf{Q}$ 中的某些 items?**

* 收到 negative judgement
* 需要重審，validator 需要對此 report 做出判決
* judgement 的數量不夠多
* 由特殊的 vrf ($s_{n}$)決定是否此審計與判決有效

審查公告 : 為了讓所有 validator 都可以對這個公告做驗證

* 公告內容是簽章過的 statement :
* 公告需審查的 core
* vrf 簽章
* 上一輪尚未 judgement 的公告
* 發布公告這個動作會被視為完成 audit 的動作
* ==看不懂, 先去看下面公式==
:::

在每一個 tranche $n$ 中，確保公告集合 $S$ 包含所有 validator 發的公告與證據 $s_{n}$。以確保所有公告都可被檢閱、審查


定義 validator statement annoucement set $S$
:::info
annoucement | tranche | content | header hash

validator $v$ 用自己的 Ed25519 $pk$ 對訊息做簽章

簽章內容 :

* $\mathsf{X}_{I}$ = $jam_announce : Ed25519 Audit announcement statements
* $n$ : 批次(tranche)
* $\mathbf{x}_{n}$ : 把批次 $n$ 裡 core 對應的 work report 做排序，以便後續其他 validator 方便做驗證
* 將非零 item $\mathbf{a}_{n}$ 裡面的元素提出來，分別做序列化與 hash 後，再序列化一次
* $\mathcal{E}$ : codec function，序列化
* $\mathcal{E}_{2}(c)$ : 把 core $c$ 做序列化成兩個 byte 的 list
* total core $\mathsf{C}$ = 341
* $\mathcal{H}(\mathbf{H})$ : 鏈上 header 的 hash，提供當時對應的鏈上狀態
:::


:::info
定義 $A_{n}$ 為判斷**哪些** validator 在批次 $n$ 中被要求對每一個 work report 提交 audit 的"感覺"

* 一組 validator set(subset of $\kappa$)，被要求對 work report $w$ 做 audit

==validator 被分配到要審查哪個 core 裡面的 work report 的可能排序，直到 current $n$ 之前都無法被正確的 evaluated==
==這種感覺只能從自己或是其他 validator 的 announcement 來猜測?==
(只會知道自己審查的 work report 的正確性，並且有責任)

* 輸入 work report set $\mathbb{W}$
* 輸出 $\mathbb{N}_{\mathsf{V}}$ 中各個 validator 被分配到審查報告的可能排序("感覺")
* $\wp$ 是 power set
* 可能取 1 ~ 1023 個人都有可能

==A_n 到底怎麼來? 會被finalized嗎?==
:::

:::info
對於每個 core $c$ 對應的 work report $w$，會有 function $q_{0}$ 將每一個 $w$ 交付給負責處理的 validator $v$

* 在 $n=0$ 就會確定 validator $v$ 所負責的 $c, w$ pair by $q_{0}$
:::
:::success
The relation of $q_{0}$ and $A_{n}$

* $q_{0}$ : 在一開始 $(n=0)$ 由 $a_{0}$ 決定 $(c, w)$ 映射到 $v$ 的分配
* 靜態的，固定的
* $A_{n}$ : validator $v$ 收集由其他 validators 發的公告 $S$ 來決定自己的 $A_{n}$
* 在 $n$ 之前不確定
* 在 $n$ 結束之後會 finalized
* 但是不排除 $n+i$ 階段收到延遲的 annoucement、或是裡面的 validators 沒有按照規定時間內完成 judgement 導致需要更改 $A_n$
* 也許會直接棄用
:::

---
judgement 對於後續 $n$ 增加之後如何處理，以及最終輸出 $U$


給定 work report，給出正面與負面 judgement 的 validator set

* 對於每個 work report's core mapping 到 judgement space
* Work report <> core 的關係是什麼?
* 每一個 core 都會有 work report，$\mathbf{Q}$ 在讀進來的時候格式就是這樣
* core 會處理(產生) work report，這邊 validator 的審查結果不只對 work report 本身還對於 core 處理的表現????????
* guarantor 才會產生 work report
* 

:::info
定義 validator indice，對於審查的結果為 T or F

* $J$ : True or False 的 validator set
* 不需要考慮 judgement 是從哪個 $n$ 做決定的 -> 應該是只關心最後大家的共識
:::

定義 $\mathbf{a}_{n}$ (audit tranche after first tranche $\mathbf{a}_{0}$ )
有可能被遲來的資訊修改 $(J_{\mathsf{T}}, A_{n-1})$，並影響到 node 的動作

:::info
**決定 $n$ 應該要審查哪些 $w$**

$\mathbf{a}_{n}$ 由 VRF 與尚未做出 judgement $(no-show)$ 的 validator 所影響

* 
* *subsequent tranche evidence* $s_{n}(w)$ :
* 與 work report 有關的可驗證隨機數
* 會影響到此 work report 是否會進到審查 $\mathbf{a}_{n}$ 中
* VRF func : audit | output | work report hash | tranche
* 
* missing audit $m_{n}$ : threshold
* 此 work report $w$ ，上一個 tranche ($n-1$) 應該要做出 judgement 的 validator set $A_{n-1}(w)$ 扣掉已經做出正向審查的 validators $J_{\mathsf{T}}(w)$
* $\frac{\mathsf{V}}{256\mathsf{F}}\mathcal{Y}(s_{n}(w))_{0}<m_{n}$
* $\mathsf{F}=2$ : The audit bias factor (empirical by optimal)
* $\mathsf{V} = 1023$ : The total number of validators
* $\mathcal{Y}(s_{n}(w))_{0}$ : VRF output(hash) 的第一個 byte
* see ch 3.8 hash

-> 對於每個 $w$ 把 $no-show$ 的 validator 繼續丟進去審查批次(audit tranche)中
:::

---
審計公告必須遵從一定的格式發表，以好比較前後審查報告的差異 -> 應該在說 $\mathbf{a}_{n}$ 的變動條件
收到新資訊後 audit requirement $A_{n}$

* 變少 : 先前 announced 過的 work report 通過
* e.g. 收到對於 $no-show$ work report 更多的 $J_{\mathsf{T}}$
* 變多 : 需要更多的 audit 流程
* e.g 發現新的 annoucement 包含尚未做出 judgement 的 work report

一旦 $\mathbf{a}_{n}$ 確定了，validators 就有責任對 work report 做出審查。需要重建 work package 與相關數據來確認裡面的邏輯

* 透過向 1/3 的 validators 要求 erasure-coding root 來重建
* 第三方 : 原始提交 work report 的 guarantor 的 preimage
* ==how?== : 知道 preimage -> lookup anchor -> work package

對於任何已經被 assured 過的 work report $w$ 或是任何需要的數據都會有候選的 work package encoding $F(w)$ 可以被 decoded 成完整的 work package

* ==透過 erasure coding's Merkle root 重建 erasure coded chunks== -> how??
* 或是透過 work package 的 hash (preimage)

嘗試在 reproduce $c$ 給的 $w$ -> $e_{n}$ (對 core 的評價?)

:::info
對於所有 package 都會有 $F(w)$ by encoding package $p$。
接著把 $p, c$ 丟進去 work computation func $\Xi$ 就可以重建 work 的 result (因為是 deterministic)

* 如果無法 decode ，或是找不到 $p$ 代表此 work report 是無效的 $F$
* 有沒有 function $F(w)$ 可以對應到 $\mathcal{E}(p)$
* 可能 by erasure coding 或是利用 preimage 的 hash
:::

基於以上 $e_{n}$ 的判斷標準，validators 可以做出 judgement set $\mathbf{j}_{n}$
所有的 $\mathbf{j}_{*}$ 都必須公告以形成共識 $J$，假設有 $F$，就會被紀錄到 $\mathbf{E}_{D}$
:::info
validator 在 tranche $n$ 對 $w$ 做出簽章 :

* $\mathcal{S}$ 就是簽章函數
* $\mathsf{X}_{e(w)}$ : 對於 $w$ 的 judgement $(T, F)$
* 會有人對同個 $w$ 簽很多同樣的 $J_T$ 或是簽兩份 $J_T, J_F$ 嗎?
:::


### work report $w$ 什麼情況被認定 audited

:::info

* 沒有任何的 $J_F$，並且在某些 $n$ 中存在 $J_T$ 來自於我們要求 audit 的 validators $A_{n}(w)$
* \> 2/3 的 validator 對其 $J_T$
:::


### block $\mathbf{B}$ 什麼情況被認定 audited

:::info
$\mathbf{U}$ : 此區塊被認定為 audited
對於所有 work report $w$，都已經被認定為 audited $U(w)$
:::

任何 block $\mathbf{B}$ 在被 GRANDPA 投票 finalized 之前，必須先成為 audited 狀態

對於以下條件的區塊(鏈)我們會忽視掉 :

* 至少 1/3 的 report 被 judged 為 $J_{F}$
* 任何包含不可 author 區塊的鏈

The $best \; block$ : 那些最遵守 Safrole 共識且不包含任何被丟棄區塊的鏈

* 所以實作上，還是會有 fallback 甚至 fork 的情況發生

對於 block author 來說，藉由 $\mathbf{E}_{D}$ 來把 judgement 的共識帶上鏈。

* non-valid judgement (沒超過 2/3 的 judgement, 尚未 validity): 就會標註這個 block 是 invalid
* 這個更新後的 $\mathbf{E}_{D}$ 就會把 $\rho$ 裡面的 pending work 去除掉

---

### 額外補充

[for potential attack](https://matrix.to/#/!ddsEwXlCWnreEGuqXZ:polkadot.io/$VHV9rHxBAtYSwsBbdk-p-ZtCWyDHkxb7j1cGl0LwUmY?via=polkadot.io&via=matrix.org&via=parity.io)


#### Audit is not STF

#### $H_v$ 其實是 redundant 因為裡面紀錄了 verdict 其實就在 $E_{D}$ 裡面, 只是為了給 light client(只讀取 header) 方便而已

#### missing audit $m_{n}$ 只會把 $J_T$ slashing 掉，因為如果出現 $J_F$ 就會發動非常召集讓所有 $v$ 都做出 audit

#### $\mathbf{E}_{D}$ 會在 audit process 結束後決定，但是 audit process 會在區塊與區塊之間

* 所以 audit 完之後決定的 $E_D$ 就是下一個區塊要讀進來的 $E_D$ ?
* 正常來說 $E_D$ 應該要是 empty，只有某些 $v$ 做出不對的動作才會被添加進 $E_D$

Path : 收到 $B(H, E)$ -> 想要 $B$ audited 之後被 finalized -> 需要 forall $w$ audited -> 需要 "$J_T$ > 2/3" 或 "沒有任何 $J_F$ 且 $A_n$ 這些被要求需要做出審查的人都投了 $J_T$" ->

* 如果此 $w$ 有 $J_F$ 那會要求所有 validator 都重新審查一遍
* 如果發現你亂投 -> fault $\mathbf{f}$ or culprits $c$
* 對於已經 annouce 卻尚未送出審查的 missing audit $m_n$ 需要達到一定數量才會通過

-> $v$ 為何被 assign or annoucement?

* 對於每一個 $n$, $v$ 會計算 $s_{n}$ 然後丟進 $a_{n}$ 來決定此輪要對哪些報告做審查
* Based on VRF -> 所以不是 $v$ 自己選擇的，是隨機的
* $v$ 能夠選擇的只有 announcement -> 被加到 $A_n$ 裡
* $a_{0}$ 其實是最一開始每個 $v$ 隨機取 10 個 $w$ 去審查
* 每一個 $c$ 裡的 $w$ 會有平均三個 $v$ 做審查 at $n=0$