Blockchain BFT-style POS 的背景知識
前言
- 這篇假設讀者是 Blockchain 門外漢（就和我一樣），嘗試從頭說明 BFT-style POS (BFT: Byzantine Fault Tolerance; POS: Proof-of-Stake) 需要的前置知識。目前有些 Blockchain 採用或即將使用 BFT-style POS (Etherem 的 Casper FFG、EOS的 DPOS BFT、ThunderToken 的 The Thunder Protocol)，下篇說明 BFT-style POS 的概念和背後設計的精神。
- 討論 Blockchain consensus algorithm 的術語不怎麼一致，本篇視情境會引用不同家的術語，並指出來源。
- 新手上路，有錯還請指正。
Blockchain 的特性 / 為什麼要用 Blockchain
Blockchain 是分散式資料庫，讓參與者透過 consensus algorithm 得出一致、不可修改的資料。
Blockchain 最大特性是去中心化，以及因應去中心化而必要的資料驗證機制。兩個互相不信任的人 (例如不同國家的公司)，藉由 Blockchain 背書，可相信交易結果成立且無法再被更動。
傳統作法需要一個權威可信的機關背書。例如簽定法律合約，然後藉由政府背書，有人違反合約時，可透過法律途徑要求政府強制執行合約內容。
目前還沒出現非用 Blockchain 不可的情境，我個人的看法是: 待 Blockchain 的生態圈成熟後，有些情境用 Blockchain 會比較方便。《區塊勢》有討論一些使用情境。
下圖有助於了解使用 Blockchain 的必要需求:
Blockchain 入門文件
大力推薦阮一峰的系列文章，淺顯易懂又精闢:
《區塊鏈懶人包》也值得一看，從許多不同面向介紹生態圈。
對 Blockchain 的誤解
這是我沒接觸 Blockchain 前主要的誤解
- 以為任何使用者都可以參與 → 實際上需要大量儲存空間和網路頻寬，所以一般使用者不會自己跑 Blockchain 的節點 ，如同一般使用者不會自己架 database server 來用。
- 以為 Blockchain 都很耗電 → 實際上只有 POW (Proof of Work) 如此，且整個趨勢往 POS 邁進，如今似乎往 BFT-style POS 走？(Ethereum POS FAQ 提及 BFT-style POS 這個詞)
什麼是 Consensus Algorithm？
這裡採用 ThunderCore white paper 的定義:
A consensus protocol enables maintaining a “linearly ordered log” of transactions in a distributed fashion such that the following two properties hold:
* Consistency: at any point in the execution, all honest participants have consistent logs of transactions — that is, either their logs are identical, or one participant’s log is a prefix of the other’s.
* Liveness: any honest protocol participant can propose to add a transaction; this transaction is then guaranteed to be incorporated into their logs within some fixed, small amount of time; additionally, whenever a participant sees some transaction in their log, the same transaction will appear in every other participant’s log within some fixed, small amount of time.
In essence, these properties mean that from the view of the participants, they are communicating with a trusted third party that maintains a global, ordered, append-only log of transactions that anyone can add to — in essence a public ledger.
粗略地說，consensus algorithm (protocol) 具備兩個屬性:
- Consistency: 任何時間任何參與者的 prefix of logs 一致。
- Liveness: 參與者新增的資料，在一小段時間後會出現在所有參與者的 logs 裡。
後面會討論這兩個特性如何影響不同作法的設計。
此外，除了演算法的好壞，經濟誘因也是一大重點。引用區塊勢的看法:
畢竟，區塊鏈的正常運作主要靠的是經濟誘因的設計。讓想要做壞事的人知道，做好事其實可以賺比較多錢，做壞事並不划算而且失敗的風險還很高，就可以確保區塊鏈的安全穩定運作。
Proof of Work (POW)
POW 是 Blockchain 最早的 consensus algorithm。Bitcoin 和目前 Ethereum 採用 POW。《区块链入门教程》有詳細的介紹。
POW 主要問題有:
- 非常浪費電力，耗電量比許多國家還多。一筆 BitCoin 交易的耗電量比 200,000 筆 VISA 交易還多(參考資料: Digiconomist )。
- 礦池有規模經濟，相較於個體戶，可以用較低的成本取得更高的計算力。導致出塊的節點容易集中在少數組織上，結果是 Bitcoin 的幾個主要礦池聯手就有 >50% 的計算力 (https://www.blockchain.com/pools)，Ethereum 也有一樣的問題 (https://etherscan.io/stat/dextracker)。這違反去中心化的精神。
- POW 需要大量計算，提高出塊速度 (即降低 block time) 會提高 stale rate (或著說增加orphan block，即不在主鏈上的 block)。提高 stale rate 會造成計算力強大的節點相對地更有效率出塊，導致更中心化 [*1]。Vitalik 寫的 Toward a 12-second Block Time 有深入分析 [*2]。所以 Bitcoin 訂block time 的期望值為 10 分鐘; Ethereum 訂 15秒 [*3]。避免中心化的代價是較高的 transaction latency 和較低的 throughput。
Ps.
- #1 這裡的論點是 orphan block 沒有報酬，讓礦工容易作白工。stale rate 愈高，礦池相對計算力愈好，導致獨立礦工傾向加入礦池。Toward a 12-second Block Time 的 “Stales, Efficiency and Centralization” 有些計算說明。我沒看懂計算細節，不過直觀上似乎合理。
- #2 Vitalik 的 On Slow and Fast Block Times 似乎從其它角度說明更短的 block time 有其它好處，所以縮短 block time 不見得是壞事。還沒看。
- #3 Ethereum 能調低 block time 是因為有條件地給 orphan block 報酬 (uncle block)，讓獨立礦工有誘因在較低的 block time 下工作。
Proot of Stake (POS)
使用 POS 的前提是 Blockchain 上必須有 cryptocurrency。想參與出塊的節點，要先押上「財產」(i.e., cryptocurrency) 才能參與出塊，直到退出出塊節點，才能退回扣留的財產。這樣參與者比較不想傷害 Blockchain。類似員工入股公司，利益和公司綁在一起。Ethereum 稱押上財產的步驟為 deposit。
POS 解決 POW 本質上的問題 (浪費電和規模經濟導致容易中心化)，但也有它自身的問題。主要的問題是 Nothing at stake，這裡引用 Ethereum POS FAQ 的說明:
In many early (all chain-based) proof of stake algorithms, including Peercoin, there are only rewards for producing blocks, and no penalties. This has the unfortunate consequence that, in the case that there are multiple competing chains, it is in a validator’s incentive to try to make blocks on top of every chain at once, just to be sure:
反觀 POW，計算力是固定的，分散計算力在分叉上並不划算 (0.9*0.5 + 0.1*0.5 = 0.5)，無此問題。
POS 的解法是找出亂投票的參與者，然後扣除他們的押金。
Chain-based POS
Chain-based POS 作法和 POW 一樣，只是改成「隨機」選擇一個參與節點出塊，避免浪費電力。
POW 和 chain-based POS 背後的精神是只要 >50% 的節點誠實 (照規則作事)，挑選出塊節點的方式夠隨機。那麼，理論上誠實節點會一同產生出最長鏈，結果就會正確。
POS 和 POW 的差異是 POS 用押注的比例決定出塊的機率，而 POW 是計算能力占全體的比例決定出塊的機率。
chain-based POS 有些問題:
- 和 POW 一樣: 沒有明確的 finality。只能說去掉主鏈尾端 k 個區塊，剩下的部份 99% 確定不會變了。
- 不易舉證參與者是否不誠實出塊，Ethereum POS FAQ 有討論兩種處罰機制，各自有它的限制。
於是有了 BFT-style POS，可克服 chain-based POS 兩個問題。BFT-style POS 的概念源出 PBFT。
PBFT (Practical Byzantine Fault Tolerance)
PBFT 的做法是選定一群 validators，選定一位 proposer。然後分多個階段執行。假設最多 f 個不誠實節點，有 2f + 1 的誠實節點:
- Pre-prepare: proposer 收到 client 的要求，依規定產生提案，傳遞給 validators。
- Prepare: validators 收到 proposal，驗證通過後，廣播 prepare message。驗證不過的話，不作任何事。
- Commit: validators 收到 2f + 1 validators prepare messages，廣播 commit messages。
- Reply: validators 收到 2f + 1 commit messages 後，執行 proposal，並回傳「已執行」給 client
client 收到 f+1 個 reply messages 後，確認 request 已完成。
上述流程裡，Commit 是很關鍵的一步。對某一個參與者 A 來說，收到 2f+1 prepare message 只有 A 知道大家同意提案，但有可能因為網路問題或是有不誠實參與者，結果只有部份人收到 2f+1 prepare message。這樣大家還沒達成共識。
A 收到 2f+1 commit message 後，表示 2f+1 參與者有收到 2f+1 的 prepare message，可以推論 2f+1 參與者知道這個提案通過。此時 A 才可確認此提案已 finalize。若 B 有收到 2f+1 prepare message，但沒收到 2f+1 commit message，B 不認為提案已 finalized，但 B 也不會推翻此提案。
《PBFT实用拜占庭容错算法深入详解》有詳細的說明，但 prepare、commit 步驟的細節描述和論文略有不同，我只有大致看論文部份內容，再找時間細讀論文。
BTW，當 proposer 沒正常運作時，PBFT 有一套處理機制，似乎過於複雜，所以有其它 consensus algorithm 想簡化這部份。
為什麼覆議比例要求 2f+1 (或是 2/3)？
《同步系统和异步系统容错率的思考》有說明此點。參考他的說明，以下是我的理解。
在說明為什麼是 2/3 以前，要先討論運行的環境是分散性系統裡的 synchronous system、partial synchronous system 或 asynchronous system。
Synchronous System
任何節點發的訊息，會在已知某個時間內被收到。
假設有 n 個節點，f 個是壞人 (不誠實)。系統正確運作的前提是好人要比壞人多，所以好人最少要有 f + 1 個:
n >= 2f + 1
f <= (n-1) / 2
f < n/2 (~50% 容錯率)POW、chain-based POS 假設運行於此系統，所以聲稱容錯率是 50% (無法防範 51% 攻擊)。
Partial Synchronous System
Partial synchrony means that a system behaves like a synchronous system most of the time, but it sometimes exceeds the bounds for network delay, process pauses, and clock drift.
PBFT 假設運行於此系統。
- 假設
n個節點內有f個壞人。 - 因為是 partial sync system，有些節點可能無法投票，不能等收齊票才作決定。
- 壞人破壞 liveness 的作法是不投票。在這種攻擊情境下，最多只能收到
n — f票。這時必須做決定才能保證 liveness。 - 壞人破壞 consistency 的作法是對不同人傳遞相反訊息 (在 PBFT 裡是只傳 prepare message 給部份參與者），所以好人的票要比壞人多 (
f + 1)，才能保證 consistency。這表示至少要收到2f + 1票才能作決定。
我們無法分辨壞人會一齊不投票或是投相反票，必須一併考慮。假設收到 x 票後可以作決定，並且此決定滿足 consistency 和 liveness，由上面的討論得知:
n - f ≥ xx ≥ 2f + 1
由上述式子導出
n - f ≥ 2f + 1
n ≥ 3f + 1
f ≤ (n-1) / 3
f < n/3得出: 壞人最多不能超過 n/3 (容錯率 33%)，且最少要收到 2n/3 的票才能作決定。
Asynchronous System
無法確保訊息何時會傳達。
無法保證 liveness，容錯率是 0%。
小結
至此，已說明需要的前置知識，下篇會接著說明 BFT-style POS 概念和幾個屬於此類的 consensus algorithm。
