# 區塊鏈技術與應用

## 我已經知道了這些東西

- [x] 雪崩效應
- [x] SHA-3（Keccak 256）
- [x] P2P
- [x] 區塊鏈紀錄哪些資料
- [x] 區塊鏈的礦工怎麼做題
- [x] Markle Tree (Hash Chain (?))
- [x] 什麼是 diff（可以看一下 GitHub 的 Commit）

## 我先預習了這個東西

- [x] 智能合約撰寫的課
- [x] [Vol.112 What exactly is blockchain?（有蠻大的幫助）](https://www.youtube.com/watch?v=TVlo66aOZE0)

## Meme

:::spoiler Is Git a blockchain?
:::

## 區塊鏈（Blockchain）簡介

- 2008 年由中本聰於《比特幣白皮書》中提出「區塊鏈」概念。
- 分散式鏈式結構，P2P。


### 處理交易的方式

- 要同時維護許多交易。
- 由許多的礦工去處理單筆交易，維護上鍊並得到獎勵。

## 探討區塊鏈的資料結構（Data Structure）

- 鏈狀的原因：時序（Time Series）性，每個區塊均有時間戳。


- 資料與資料的關係：Hash Chain，具有前一筆資料的 hash value。
- 資料只紀錄 diff，不記錄整個帳本的整體。

## 探討區塊鏈的演算法（Algorithm）

- 如果有許多的礦工去處理單筆交易，只有一個人可以得到獎勵，那麼誰會得到獎勵？
- 票多的贏，票少的輸。
- 運氣好的人。
- 拳頭大的人。

- 基本上這樣的方法都可以歸納成以下兩種方法
- Proof of Work（工作量證明，PoW）
- Proof of Stake（持有量證明，PoS）

- 怎麼只讓一個人得到獎勵？
- PoW 做題。
- 挖礦，可能是先挖到的先贏。
- 嘗試 revert hash value，解到前面有 N 個 0 （可以說低於某個閥值）之後就算挖到礦。
- 挖到礦之後讓許多人驗貨。

- 因為先挖到的先贏，所以其他人會直接血本無歸，很浪費電
- 另一個方式（PoS）質押多的人贏。

### 題目

基本上可以視為 $\text{Hash}(\text{Prev_hash_value}, \text{Pack}, \text{nonce})$

- $\text{Prev_hash_value}$ 為前一次的 hash 值。
- $\text{Pack}$ 為訊息，例如交易紀錄。
- 算 nonce。

如果交易紀錄的訊息量太大，可以嘗試雜湊。

--

為什麼每個人的題目不一樣？

Pack 的 `Hash 01` 通常放 `no one -> address: _`，`address` 為礦工地址，因此導致 `nonce` 也必須要不一樣，每個人算的題不同。

## 區塊鏈的安全性

- 交易紀錄每個人都可以寫，所以可能會讓別人轉出自己的帳號。
- 所以我們需要數位簽章，具備驗證性、不可否認性、完整性。

## 數位簽章

- 具有機密性、完整性、不可否認性
- $\sigma$ should provide by Sender and non repudiable.

### The syntax of Digital Signature
- $\text{Generater}(n) -> \text{SK}, \text{VK}$
- Generate two keys.
- The first key should used to sign the message (Signing Key, $\text{SK}$), and the second key (Verification Key, $\text{VK}$) should used to verify the message.
- The sender doing this stuff. Generate $\text{SK}$ and $\text{VK}$.
- VK should be public. Everyone can verify the message.
- $\text{Sign}(\text{SK}, \text{message}) -> \sigma$
- $\text{Verify}(\text{VK}, \sigma, \text{message}) -> \text{Accept/Reject}$

#### Bad Practice

> Alice and Bob want to send the message with digital signature. Alice send the message and the hash value of message to Bob, and Bob should verify the hash value of message is equals the hash value send by Alice. Consider the Authentication, Integrity, and Non-Repudication, is it satisfied?

- For the Authentication, the way of the digital signature can't satisfy.
- For the Integrity, the way of the digital signature can satisfy.
- For the Non-Repudication, the way of the digital signature can't satisfy.

### Hash-then-sign

For the sender:

- $\text{message} = \text{hash}(\text{message}) = \text{h} \rightarrow \text{sign}(\text{h}, \text{sk}) \rightarrow \sigma$

For the receiver:

- $\text{message} \rightarrow \text{hash}(\text{message}) = \text{h} \rightarrow \text{verify}(\text{h}, \text{vk}, \sigma) \rightarrow \text{Accept/Rejected}$

### The Role of the digital signature in the blockchain

- Make sure the transation from the owner.

## Elliptic Curve Cryptography (ECC)

- $y = \sqrt{x^3 + ax + b}$
- ECC make sure any two point $A, B$ in the curve doing "plus operator" should exists the third point interact with the curve. When we draw a vertical line in the third point, it should interact the forth point. The forth point is $A+B$.

### Elliptic Curve Hardness (Discrete Logarithm Problem)

> $\bf{E}$ is an Elliptic Curve as a group. Consider a generator $P$ and another element $T$. The DL problem is to find the integer $d$ where $1 \le d \le \#E$.

- Given $P, \alpha P$, find $\alpha \in \bf{Z}_p$, which $P$ is a generator of $\bf{E}$.
- $\alpha$ is hard to find since we have $T$ and $P$ but $d$ is hard to find.

### How Elliptic Curve work on Digital Sign (Elliptic Curve Digital Sign Algorithm, ECDSA)

- $\text{Gen}(n)$: Let $p$ be a prime, $\bf{E}$ is EC over mod $p$. Select $P$ is the generator of $\bf{E}$.
- The Verification Key, $\text{VK}$ is $(\bf{E}, P, \alpha P)$.
- The Sign Key, $\text{SK}$ is $\alpha$.

- $\text{sign}(\text{SK}, m)$: $H: \{0, 1\}^{*} \rightarrow \bf{Z}_p$
1. random $r \in \bf{Z}_p$
2. Compute $\sigma_1 = rP$
3. Compute $\sigma_2 = r^{-1}(H(m) + \alpha \times u)$ which $u=H(rP, \alpha P, m)$

- $\text{verify}(\text{VK}, m, \sigma):\space\space \sigma_2 \cdot \sigma_1 = P(H(m) + \alpha \times u) = PH(m) + \alpha P u$
- Since we have $\alpha P$ and $P$ in verification key and $H(m)$, $u = H(rP, \alpha P, m)$ could be calculate, we can check the both side of the formula is equal.

### How Digital Sign work on Block Chain

- Sign the message by: $\text{Sign}(sk_{\text{Alice}}, tx_i) \rightarrow \sigma_i$
- Broadcast the pair of message and sign: $(tx_i, \sigma_i)$

## 區塊鏈相關的應用

### 找零錢包

- 轉錢出去時，將零錢轉到下一個錢包，該錢包直接刪除。
- 避免出現 $r$ 與 $\alpha$ 能夠被破解。

## 區塊如何上鍊

- 有人幫忙挖礦
- 6 confirmations.
- 大概一個小時會好
- 發生 fork 時短鏈會被拋棄

## 區塊鏈的共識

Nice reference if you need it: https://homes.cs.washington.edu/~jrl/cse422wi24/notes/blockchain_3.pdf

### Byzantin General's Problem (1982)

#### Description

- Assume $n$ generals. One is the commanding general (CG).
- CG would like to propose an order (Attack or Retreat)
1. All loyal ones reach the same direction
2. If CG is loyal, then all loyal ones will obey CG's order.

     Exercise
     
     You know CG is 100% loyal. Byzantine Brocast becomes trivial.
     You know CG is 100% triator. All general retreat.

#### Definition

- Entities: nodes (General), sender (CG), the node 1 is sender.
- $[n] = \{1, ..., n\}$ denotes the set of all nodes.
- Honest node
- Corrupted nodes (a subset of nodes), controlled by an adversary.
1. Send/Transmit arbirity messages.
2. Share info.
3. Coordinated attacker.
4. Stop.
5. Incorrect step.
- We only consider the static corruption model, decides corrupted nodes at the beginning.

#### The synchronous network

If an honest nodes sends a message in round $r$ to an honest recipient, the recipient gets it at the beginning of $r+1$.

#### The consistency and validaty

- Consistency: If two honest nodes output $b_1$, $b_2$, then $b_1$ = $b_2$.
- Validaty: If $S$ is honest with input $b$ then all honest ones output $b'$.

#### Naive Protocol

- Define $<b>_i = (b, \sigma)$, where $\sigma = \text{sign}(sk_i, b)$.
- For every iterate
- Round 1: $P_1$ sends $<b>_1$ to eveyone
- Round 2: If $<b'>_1$ is received and passes verify, then vote $<b'>_i$, else vote $<0>_i$
- Round 3: If no bit or both bit received more then $n/2$ from distinct nodes, where $n$ is the count of the vote, output $0$. Else, output bit more than $n/2$ votes from distinct nodes, where $n$ is the count of the node.
- When $n = 50$, $P_1$ is honest, and corruptions is 25, it may affect the honest node since the $P_{25}$ will be affected by the vote.
- When $n = 50$, $P_1$ is honest, and corruptions is 24, it may not affect the honest node since the $P_{26}$ still vote $b$ where $b$ is send by $S$.
- When $n = 50$, $P_1$ is corrupted, and corruptions is 1, it will affect the honest node.

#### Dolve - Strong Protocal

- Definition
- Input of $P_1$: $b$
- Each node $i$ maintain a set $\text{extr}_i$, $\text{extr_i}_i$ can be $\{\phi\}$, $\{0\}$, $\{1\}$, or $\{0, 1\}$
- $\{0, 1\}$ if received bits satisfied the count of ${0}$ greater than $n/2$ and the count of ${1}$ greater than $n/2$.
- $<b>_{S}$: message $b$ attached with a valid signature on b under $P_K$ of nodes in $S \in [n]$.
For example, $<b>_{1, 2, 3, 4} = (<b>_1, <b>_2, <b>_3, <b>_4)$.
- Protocal
- $f$ is the number of corrupted nodes.
- Round 0: $P_1$ sends $<P>_1$ to every.
- For each round $r=1$ to $f+1$, $P_i$ receives every msg $\tilde{b}$ with $r$ signatures $<\tilde{b}>_{1, j_1, j_2, ..., j_r}$, if $\tilde{b} \not\in \text{extr}_i$, add $\tilde{b}$ to $extr_i$ send $<\tilde{b}>_{1, j_1, j_2, ..., j_r, i}$ to everyone.
- End of $f+1$ round, if $|extr_i| = 1$, otherwise output $0$.
- Example 1
- P4 is bad.
- Round 0: $P_1$ send $<1>_1$ to everyone.
- Round 1: $P_2$ = received $<1>_{1}$, $P_3$ received $<1>_{1}$, $P_4$ received $<1>_{1}$.
- Round 2:
- $P_2$ received $<1>_{1, 3}$ from $P_3$, $extr_i = \{1\}$
- $P_3$ received $<1>_{1, 2}$ from $P_2$, $extr_i = \{1\}$
- $P_4$ decide not to do anything.
- Hey we got 1.
- Example 2
- P1 is bad.
- Round 0: $P_1$ send $<0>_1$ to everyone.
- Round 1: $P_2$ = received $<0>_{1}$, $P_3$ received $<0>_{1}$, $P_4$ received $<0>_{1}$.
- Round 2:
- $P_2$ received $<0>_{1, 3, 4}$, $extr_2 = \{0\}$
- $P_3$ received $<0>_{1, 2, 4}$, $extr_3 = \{0\}$
- $P_4$ received $<0>_{1, 2, 3}$, $extr_4 = \{0\}$
- Hey we got 0.

#### Byzantine Broadcast without Signature

- In conclusion, the lower bound (Impossibilty) is $f \ge \dfrac{1}{3}\space \text{corruption}$, means the good nodes should greater than $\dfrac{2}{3}n + 1$.
- The upper bound is Byzantine Broadcast with Signature (Voting).
- The steps:
- Every node holds a "Sticky bit"
- Leader of iteration $r$ is defined by $H(r)$
- Initially, sender's sticky bit is its input bit, else everyone's is $\perp$.
- For every iteration $r=1, ..., k$.
- Round 0: Leader $L_r$ sends a proposed bit $b$ to everyone where $b$ is chosen as follows. If $L_r$'s sticky bit is not $\perp$, set $b$ with the sitcky bit, otherwise, $\{0, 1\}$ at random.
- Round 1: Everyone votes on a bit by sending the bit. If the node has a non-$\perp$ sticky bit than choose sticky bit, otherwise, choose the bit proposed by $L_r$.
- Round 2: Everyone checks the votes it has received. If at least $\dfrac{2n}{3}$ votes on the same sticky bit $b'$ update its sticky bit to be $b'$, else update its sticky bit to be $\perp$.
- Output: Finally, everyone outputs its own sticky bit's value.

#### 定義區塊鏈的協定

- Consistency: 所有的節點都會有一個相同線性有序性 log 的 view。
- Liveness: If some honest node receives some legel tx in some round r, then tx will appear in every honest nodes's "finalized log" by the end of $r + T_{conf}$

#### 利用 Byzantine Broadcast 建構區塊鏈

- 需要 Multi-value Byzantine Broadcasting
- n nodes: $0 \sim n-1$
- Digital Signature (For verify txs) + Byzantine Broadcast.
- Sender $S_k$ of $BB_k$ collects every txs ($tx_1 || tx_2 || tx_3 || ... || tx_l$).
- At any time, suppose $BB_0, ..., BB_K$ have finished and their outputs are $m_0, ..., m_k$.
The nodes current output log is $m_0 || ... || m_k$

## DeFi

### 什麼是 Finance

- Finance is the process that involves the creation, management, and investment of money and financial assets.

### 什麼是 CeFi

- 傳統的 Centrialized financial
- 機構會持有使用者的資產
- 會有一些手續費
- 交易紀錄被牢牢監察

### Defi User

- User
- Contract = Protocol
- Keeper
- Oracle
- Bridge

### Decentralize Lending




### Other Problem on Oracle

- How do we ensure nodes get paid for service?
- By PoC it may add transaction on block and get paid of it.
- It also may have something like PoS to ensure the data is correct by bet.

- How to ensure that oracle reports are mined in a timely way?
- We may have some data response with timestamp and check the reports of the data.
- It also have the block with timestamp on it so it may not a big deal of it.
- But the latency may have some issue since fetch the data already passed a hour.

- How do we ensure that a majority of nodes are honest?
- We can't ensure of it, but we may fetch multiple data sources and get the value by median (Continuous) or vote the value (Discreate).

## 一些 hash 的介紹

### Merkle–Damgård Construct
- 將訊息以固定單位的長度截斷，並且搭配 Compression Function $f:\{0, 1\}^{2l} -> \{0, 1\}^{l}$
- 第一次 Iterator 時有一個 $IV$ 作為初始向量（Initial Vector）。
- 最後一次有一個長度的 Length Padding。
- 如果沒有 Length Padding 的話會[長度擴充攻擊](https://zh.wikipedia.org/wiki/%E9%95%BF%E5%BA%A6%E6%89%A9%E5%B1%95%E6%94%BB%E5%87%BB)。


### Merkle Tree

- Merkle–Damgård Construct 是 hash chain，時間複雜度是 $O(N)$。
- Markle Tree 可以把這件事情以樹狀描述，平行運算，時間複雜度是 $O(\log{N})$
空間複雜度比 Merkle–Damgård Construct 高，需要 $O(N)$ 的儲存空間。