---
# System prepended metadata

title: 'Group 1: What Fault-Tolerance doing in Blockchain'

---

# 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條件
    * 為何是三階段
        * 我認為是無法同步的原因(不確定)
        * 因為無法判斷是不回應還是運算過慢，所以需要多個階段

### 研究方向二

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