# Group 1: What Fault-Tolerance doing in Blockchain

### 組員
何宗諭 (電機所博班)
李育論 (電機所碩班)

## Proposal

### 動機

我(何宗諭)是電機所陳和麟教授的博士生，近期主要的研究與分散式演算法有關，希望從分散式的領域找到可切入區塊鍊的研究。

首先，整理老師上課的內容與自己的心得(與持續讀相關論文)，並引導出題目的主軸
* 中心化(Centration)與去中心化(De-centration)
* 為何要去中心化呢?
* 從計算複雜度的角度來看，中心化雖然可以保證計算解穩定，但在peer-to-peer的架構中，大量的節點，頻繁的transaction會讓中心式的計算量**不可行**
* 去中心化 $\neq$不等於 沒有中心化
* 想像**去中心化**是一種程度上的動作(De-Centralizing)，所以有些架構離中心化很近，有些離中心化很遠，在程度上有所不同(但就是不可能沒有中心化)
* 離中心化**較遠**的概念：存在一種規則(Mechanism)，此規則不輕易變動，所有參與者都知道這規則，在規則上進行活動或決策，所導致的一切獎勵或者懲罰**都是來自於規則**本身所造成，而非來自於某些人的決策
* 規則越複雜，越常變動，可以想像此系統越中心化
* 越**去中心化**，規則應該是簡易越不容易改變，(例如：$e=mc^2$}

* Mechanism (規則) $\to$和 Incentive(誘因)
* 可以設計任何完美的規則，但缺乏誘因的規則，就是不切實際
* 如老師上課提到：比特幣因為洗錢交易而有價值
* 因為人們相信PoW的機制的回饋，所以才有誘因參與計算
* 又或者：程式開發者，若可以獲得一定比例的獎勵(隨著越多人使用)，就是最好的誘因願意開發更穩定的系統
* 如果不存在誘因，就沒有區塊鍊的必要
* 例如：畢業證書，中心化即可

* 若欺騙(不誠實)行為能獲利，就是攻擊的誘因
* 規則 $\to_{形成}\to$ 誘因 $\to_{導致}\to$ 攻擊
* 規則 $\to_{設計}\to$ FT $\to_{限制}\to$ 攻擊
* 因此，False的發生是必然存在於分散式環境，所以任何分散式系統都需要FT，但FT必定會影響Concensus的運算時間，因此，我們才需要關注使用的FT演算法是否合理
* Fault-Tolerance(容錯) 與 Concensus (共識)
* 不誠實的行為
* 節點中可能(一定?)存在不誠實的行為
* 可以設計一個Penalty機制，減少不誠實的誘因
* Ethereum的POS 有Penalty機制?(不確定)
* 考慮到Penalty的討論範圍過大，先把問題限縮在容錯問題上
* 拜占庭將軍問題(Byzantine faulty)
* 描述系統中出現不誠實的節點時，需要多少的可信節點(例如$\cfrac{2}{3})$才能達成正確的共識
* 拜占庭容錯(BFT)
* 解決系統中錯誤的演算法概念
* 考慮到不同的時間複雜度及功能，因此延伸出不同實作方法
* Practical BFT 能大幅降低時間複雜度，是一種可行性方法，且已成功用於分散式系統
* Paxon
* 針對資料傳遞時可能會Crash的改良方法，一般被認為為Non-Byzantine
* 例如：延遲、毀損、消失等問題

### 研究方向一

不同的FT演算法的差異跟下列有關
* 運算複雜度
* 所能解決的能力

思考這些已經存在的演算法是否有改善的空間，在改善之前，先就這些演算法深入探討

* 實作PBFT和Paxon，並理解他們的適用條件
* 比特幣怎麼用PBFT方法，這個方法的時間複雜度是否有改善的空間

#### PBFT
* 三階段的投票機制
以四個人為例
1. 第一階段：Pre-prepare
* 主導者負責發起提議
* 主導者接受到訊號，準備行動
* 怎麼決定誰是主導者(leader/Primary)
* 挖到礦?
* 主導者將帶有簽章的(pre-prepare)訊息給其他人(Validator)
2. 第二階段：Prepare
* 收到(pre-prepare)訊息的其他人，可決定是否同意此項動作
* 若同意則再將同意的prepare帶著自己的簽章發給其他人
* 當發出prepar的人收到3則prepare訊息時，則狀態轉變成prepared

3. 第三階段：Commit
* Prepared狀態的人，若願意執行，發出帶有簽章的Commit給其他人，並進入Commited狀態
* Committed 狀態下若收到3則Commit訊息，則開始執行
* 執行完成後回應，並進入下一輪

* 概念
* 節點數 $3f+1$ 可容許最多 $f$不誠實者
* 所以$2f+1$的同意可以視為2/3同意
* 若主導者要欺騙大家，則其他人驗證有問題，可以不執行此動作，最後可發出View-Change，更換主導者
* 思考
* 為何是$2f+1$而不是$3f$者$f+1$
* $f+1$ 比例過低無法達成共識
* $3f$可以，但是會浪費太多的運算時間
* $2f+1$ 滿足BFT的2/3條件
* 為何是三階段
* 我認為是無法同步的原因(不確定)
* 因為無法判斷是不回應還是運算過慢，所以需要多個階段

### 研究方向二

#### 跨鍊
* 目前還在用論文理解