---
各種奇怪符號請在這裡找~
---

# III. Notational Conventions

## 3.1. Typography

- 小寫字母：用於局部變量。($h$, $\mathbf{h}$)
- 大寫字母：用於布林值或局部函數。($\mathsf{H}$)
- 黑板粗體：用於表示集合（如 $\mathbb{N}$ 表示自然數）。
- 花體字母：引用外部函數（如 $\mathcal{H}$ 表示哈希函數）。
- 希臘字母：表示具有特定全局含義的變量。($\rho$, $\tau$, $\sigma$, $\kappa$, ...)

## 3.2. Functions and Operators

- $\prec$ 可視為函數關係 $y \prec x \Longleftrightarrow \exists f: y = f(x)$
- $\mathcal{U}$ 會從參數列中取出第一個非零值

> `$\mathcal{U}$`: $\mathcal{U}$
> :question: $\prec$: 通常表示正比符號 ???????
> $\Longleftrightarrow$ $\equiv$
> `$\iff$`: $\iff$
> `$\Longleftrightarrow$`: $\Longleftrightarrow$

## 3.3. Sets

-  $\mathbf{s}$ 為冪集，$|\mathbf{s}|$ 表示集合內元素的數量。另外冪集下標可以指定子集合的大小
- with scalars
- apply function
- 互斥
- 空集合, 可空集合 (尾端加?)
- 非預期錯誤 ∇ (NABLA)

> `$\wp$`: $\wp$
> `$\mathfrak{P}$`: $\mathfrak{P}$
> `$\varnothing$`: $\varnothing$
> `$\nabla$`: $\nabla$: The term $\nabla$ is utilized to indicate the **unexpected failure** of an operation or that **a value is invalid or unexpected**

## 3.4. Numbers

1. $\mathbb{N}$ 自然數: 從 0 開始的所有非負整數
$\mathbb{N}_n$ 表示所有小於 n 的自然數

2. $\mathbb{Z}$ 整數: 所有正整數、負整數和 0
$\mathbb{Z}_{a \dots b}$ 表示 a <= x < b 區間的整數 `[a, b)`
$\mathbb{Z}_{x \dots +n}$ 表示從 x 開始，長度為 n 的整數區間

3. 常用範圍 $\mathbb{N}_{2^{32}}$, $\mathbb{N}_L$: 這代表 int32 的範圍，通常也代表 4GB 以內的位元組序列

4. 取餘 $\%$: $5 \% 3 = 2$
表示商和餘 $\mathsf{R}$, \eg $5 \div 3 = 1 \mathsf{R} 2$

> `$\remainder$` = $\mathsf{R}$ = `$\mathsf{R}$`
> `$\rem$` = $\text{\scriptsize{\%}}$

## 3.5. Dictionaries

字典的形式化定義

鍵唯一性約束。對於字典 𝑑，每個鍵 𝑘 在字典中最多只能對應唯一值 𝑣

字典的子鍵值查詢

字典的鍵刪除操作

有類型限制的字典。鍵 𝑘 必須屬於集合 𝐾。值 𝑣 必須屬於集合 𝑉

字典合併，key 重複時，優先保留右側 e 的 key 值

## 3.6. Tuples
Tuples 是具有特定順序的值組，每個項目可能來自不同的集合。元組使用括號表示。例如，自然數 3 和 5 的元組可以表示為 $t = (3, 5)$，它屬於自然數對的集合 $\mathbb{N} \times \mathbb{N}$，在本文件中也表示為 $(\mathbb{N}, \mathbb{N})$。

- 定義一個完整的 tuples 集合，一個有兩個命名為 a 和 b 的自然數成分的元組可以表示為 $T = a \in \mathbb{N}, b \in \mathbb{N}$

- 表示 tuple 中的特定項目，對於 $t = a \mapsto 3, b \mapsto 5$ 可透過下標表示 $t_a = 3, t_b = 5$

## 3.7. Sequence

Sequence 表示一組特定排列順序的序列。構成序列的所有元素均來自集合 $T$，可記為 $⟦T⟧$，並可定義為從自然數到集合 $T$ 的部分映射。

- **固定長度的序列**：包含 $n$ 個來自 $T$ 的元素的序列可記為 $⟦T⟧_n$，定義為從自然數集合 $\mathbb{N}_n$ 到 $T$ 的完整映射。
- **可變長度的序列**：長度最多 $n$ 的序列可記為 $⟦T⟧_{:n}$，而長度至少 $n$ 的序列可記為 $⟦T⟧_{n:}$。

- **索引**：第 $i$ 個元素記為 $s[i]$ or $s_i$
$[0, 1, 2, 3]_{\dots2} = [0, 1]$ 表示 $s$ 的前兩個元素
$[0, 1, 2, 3]_{1\dots+2} = [1, 2]$

- **長度**：序列 $s$ 的長度用 $|s|$ 表示
- **環形索引**：$\mathbf{s}[i]^\circlearrowleft \equiv \mathbf{s}[\,i \% |\mathbf{s}|\,]$
- **末尾元素**：$\text{last}(s)$ 表示序列 $s$ 的最後一個元素

### 3.7.1. Construction

- **增量構造**：可以通過遞增索引生成序列，例如：
$[f(i) \mid i \in \mathbb{N}_n] \equiv [f(0), f(1), \dots, f(n-1)]$

- **多重組合**：可以從多個序列生成新序列，例如：
$[i \cdot j \mid i \in [1, 2, 3], j \in [2, 3, 4]] = [2, 6, 12]$

### 3.7.2. Editing

- 序列連接符號 $\smallfrown$
- $[\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{y}_0, \mathbf{y}_1] \equiv \mathbf{x} \smallfrown \mathbf{y}$
- $\overset{\smallfrown}{\mathbf{x}} \equiv \mathbf{x}_0 \smallfrown \mathbf{x}_1 \smallfrown ....$
- 前 $n$ 個元素的序列 $\overset{\to n}{\mathbf{s}} \equiv [\mathbf{s}_0, \mathbf{s}_1, ..., \mathbf{s}_{n-1}]$
- 最後一個元素 $\overset{\leftarrow n}{\mathbf{s}}$
- 轉置 (transposition) 序列 $^T\mathbf{x}$
- $\mathbf{s}\ \smallsetminus \{v\}$ 表示序列 $\mathbf{s}$ 減掉最左邊的元素 $v$

### 3.7.3. Boolean values

布林值序列 $\mathbb{B}^s$ 是長度為 $s$ 的布林值 ($\{\top, \bot\}$) 序列。布林值與二進位數等價，例如 $\top = 1$，$\bot = 0$。
(GP v0.5.4) 新增 unary-not operator

### 3.7.4. Octets and Blobs

- 八位元組序列用 $\mathbb{Y}$ 表示。
- 特定長度 $x$ 的八位元組序列記為 $\mathbb{Y}_x$。
- ASCII 字串是八位元組序列的子集，記為 $\mathbb{Y}_{＄}$。

### 3.7.5. Shuffling

定義一個洗牌函數 $\mathcal{F}$，用於根據某些熵將序列的順序隨機化。熵可以為不確定的自然數序列或是雜湊

實作演算法可參照 [wiki](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Modern_method)

以下為附錄 F 中定義的演算法


:::info
F.1 為原始洗牌演算法定義
F.3 為 32 bits Hash 作為熵來源的洗牌算法
:::

## 3.8. Cryptography

### 3.8.1 Hashing

$\mathbb{H}$ 是一個輸出為 256-bit $(\mathbb{Y}_{32})$ 的 set
>[name=Shelley]
>$\mathbb{Y}$ 代表 octet sequence-八位元組的序列。
>$\mathbb{Y}_{32}$ 是長度為 32 個 byte 的 octet sequence。
>一個標準的 256-bit 的 Hash 會輸出 32 個 byte。
>Hash 值屬於 32-byte 的長度的 octet sequence。

- $\mathbb{H}^{0}$ 的輸出為 $\left[0\right]_{32}$

 : Blake2b 256-bit 的 hash
 : Keccak 256-bit 的 hash (只有在 BEEFY 用到)
 : 只想要對 $m$ 的前 $x$-byte 做 hash

- 但應該是做完 $\mathcal{H}(m)\in\mathbb{Y}$ 才取前 $x$-byte

hash function 的輸入應該要先經過 serialization codec $\mathcal{E}$ 序列化過後生成的 8-bit 序列

#### subset of codec : 下標是 # of 8-bit 序列


- 代表 $r\in\mathbb{Y}_{4}$, $x\in\mathbb{N}_{2^{32}}$


- 代表 $s\in\mathbb{Y}_{8}$, $y\in\mathbb{N}_{2^{64}}$

### 3.8.2 *Signing Schemes* 簽章方案

- 不用 Polkadot 的 SR25519，而是一般的 Ed25519
- 有跟 Polkadot 一樣的 BLS
- 新的 Bandsnatch
- RingVRF : 提供你匿名的簽章，只知道是 set 中的某個人簽的章，但不知道確切是誰。大概是藉由 alias 代替你簽章，然後 alias 可以鑑別你
- 因為在 Safrole 中，validators 可以匿名聲稱自己有 tickets
- Ring root 非常大 ，指定我們是用哪個 ring
- 

:::info

- 有效的 Ed25519 簽章 set，用 key $k$ 對 message $m$ 做簽章
- ==既然**有效**，代表有做驗證的動作? -> 所以是用 $pk$ 對 "已經有人用 $sk$ 簽署過的 $m$" 做驗證確保此簽章是有效 (or verifiable) 的?==
- 下面的 $k$ 是 $pk$ 已經暗示此簽章可驗證了
- ==為何是 64 byte string 的子集?==
- 
- 長度 32 的 byte-string
- Ed25519 的 $pk$
- 定義有效的 $pk$ set 為 $\mathbb{H}_{E}$
- 便於描述系統中 validator set
:::

:::info
$\mathbb{Y}_{BLS}$ : BLS 簽章的 $pk$ set
$\mathbb{Y}_{144}$ : 長度 144 的 byte-string set
:::

$\mathbb{H}_{B}$ : 有效 Bandersnatch $pk$ 的 set (like $\mathbb{H}_{E}$)

$\mathbb{F}^{m\in\mathbb{Y}}_{k\in\mathbb{H}_{B}}\left\langle x\in\mathbb{Y}\right\rangle\subset\mathbb{Y}_{96}$ : 有效簽章的 set，對 message $m$ 用 key $k$ 做簽章，==但是簽署的訊息是 context $x$(上下文)，也就是說別人用 $pk$ 來驗證不會知道你簽署的 message $m$ ?==
:::info

- 使用 Bandersnatch 的 $pk$ 對 message $m$ 加上 Additional data $x$ 做簽章，並輸出 (output, proof)
- x(Context)：輔助參數，可能是附加數據、協議名稱、交易識別碼或時間戳等，確保簽章在不同環境中的唯一性。
- 也有可能是 signing context(Appendix. I4.5)
- $m, x \in \mathbb{Y}$ : message, context 為 byte-string
- $k\in \mathbb{H}_{B}$ : 使用在有效 Bandersnatch key set 裡面的 $pk$ 做簽章
- $\mathbb{Y}_{96}$ : 限制輸出屬於長度 96 的 byte-string set
:::

 : 有效 Bandersnatch ringVRF 的 proof set
$\mathbb{F}^{m\in\mathbb{Y}}_{r\in\mathbb{Y}_{R}} \left\langle x \in \mathbb{Y} \right\rangle \subset \mathbb{Y}_{784}$

- 你可以生成**獨特**, **有效**且**匿名**的簽章，在已知的 set 裡的某個人簽了章
:::info
$m, x \in \mathbb{Y}$ : message, context 為 byte-string
$r\in \mathbb{Y}_{R}$ : Bandersnatch ring roots 的 set
- 這邊是 ring 的 root 而不是特定的 $pk$，可以隱藏是誰簽的章
- $\mathbb{Y}_{R} \subset \mathbb{Y}_{144}$ : 有效的 root，長度為 144 的 blob
- 想成用來指名哪一個匿名 key set 的 index
- $\mathbb{Y}_{784}$ : 限制輸出屬於長度 784 的 byte-string set

 : 由 " $pk$ set 對應的 $s$ " 生成 root 的 function
- $s$ (想成 $pk$ set 的在 ring 上映射?)，屬於有效 Bandersnatch key set 裡面的 $pk$ 形成的所有可能序列組合
-
:::

 : VRF 的 output，是一個 hash
$\mathcal{Y}\left(
\bar{\mathbb{F}}^{m}_{r} \left\langle x \right\rangle
\right)
\subset \mathbb{H} \text{ and
} \mathcal{Y}\left(
\mathbb{F}^{m}_{r}
\left\langle x \right\rangle
\right)
\subset \mathbb{H}$
兩者皆是 VRF 函數的 output，前者匿名，後者知道是誰簽的章

- output 是一個 hash，輸出高度被 message $m$ 影響而不是 additional context $x$
- The VRF output is independent of the additional context, so there isn't really a circular dependency [ref](https://matrix.to/#/!ddsEwXlCWnreEGuqXZ:polkadot.io/$w1RkTOQg7psGWHcB6qzcIipq4EmE11b0WliVulIobrQ?via=polkadot.io&via=matrix.org&via=parity.io)

 : 定義 $\mathcal{S}$ 是簽章的函數
:::info

- $\mathcal{S}_{k}(m)$ 使用 key $k$ 對 message $m$ 做簽章。會屬於 Bandersnatch 與 Ed25519 簽章的聯集
:::

## Appendix. G Bandersnatch Ring VRF : 把 $pk$ set 映射到一個 ring

[ringVRF 程式碼](https://github.com/davxy/bandersnatch-vrfs-spec/tree/main)
[ringVRF 論文](https://eprint.iacr.org/2023/002.pdf)


- Key Generation
- $\mathrm{rVRF.KeyGen}\to(sk, pk)$
- Evaluation: $deterministic$ 的 VRF output
- $\mathrm{rVRF.Eval}(sk, input)\to(output)$
- Signature
- $\mathrm{rVRF.Sign}(sk, ring, input, additional)\to(output)$
- $\sigma$ : ringVRF 的簽章，對 ringVRF output 的證明
- 包含 $\mathrm{in}$ (input) 與 $\mathrm{ad.}$ (additional data)


- vrf function 簽章的細節，其實是做驗證(verify) 的動作
- $\mathcal{Y}$ : output hash