State Machine Replication in the Libra Blockchain 讀後筆記

最近 Facebook 推出 Libra，包含加密貨幣、blockchain 和 consensus protocol。官網有相當豐富的資料，像是 Life of a Transaction 介紹使用者發出 transaction 到被執行的過程裡，發生什麼事。

這篇著重在 Libra blockchain 使用的 consensus protocol LibraBFT，它也是 BFT-style POS 的協定。關於 consensus protocol 的背景知識，可參考先前的介紹:

• Blockchain BFT-style POS 的背景知識
• Blockchain 的 BFT-style POS
• PaLa: A Simple Partially Synchronous Blockchain 讀後筆記

HotStuff

LibraBFT 是基於 chained-based HotStuff，所以整個結構 87% 像。而 Pala 也有受到 HotStuff 影響，所以 Basic Pala 和 HotStuff 也很像。共同的優點有:

• 將 view change (替換出塊者) 放在一般流程裡，隨時都在 view change。這解決 PBFT 最複雜的問題 。據我不精確的理解，PBFT 是出塊者有問題後，才找出下個出塊者，並達成目前狀態的共識。Subtle Details in PBFT 有描述細節，我沒細看。
• 投票者只會回傳同意票給出塊者，再由出塊者廣播共識結果給大家。而不是所有人傳給所有人，訊息傳遞量從 O(N²) 降為 O(N)。
• 最佳狀況在滿足條件後就開始下回合出塊，不用等時限到了，才開始下一回合。提升 throughput。

HotStuff 的論文不好讀，有興趣可參考別人消化後的描述:

HotStuff: the consensus protocol behind Facebook’s LibraBFT

LibraBFT 論文滿好讀的，而且有滿多篇幅描述實作，本文是用 LibraBFT 描述來說明。

State Machine Replication

摘錄論文的介紹

State Machine Replication (SMR) protocols are meant to provide an abstract state machine distributed over the network and replicated between many processes, also called nodes. Specifically, a SMR protocol is started with some initial execution state. Every process can submit commands and observe a sequence of commits. Each commit contains the execution state that is the result of executing a particular command on top of the previous commit. Commands may be rejected during execution: in this case, they are called invalid commands.

假設執行是 deterministic (在任何 node 有一樣的過程和結果)，consensus protocol 要滿足兩個性質:

• (safety) All honest nodes observe the same sequence of commits.
• (liveness) New commits are produced as long as valid commands are submitted.

每個參與出塊的節點也稱為 validator。在 validator 裡，consensus protocol 和 blockchain 是不同模組，執行 command 和改變 state 是 blockchain 的工作，consensus protocol 只要知道執行後的 state 為何，確保 state 的變化符合規範。

出處: https://developers.libra.org/docs/assets/papers/libra-consensus-state-machine-replication-in-the-libra-blockchain.pdf

除了 safety (Pala 稱為 consistency) 和 liveness，還有 fairness 也是 consensus protocol 的重要性質，它的意思是 client 送出的 transaction 最後會被執行。本篇提到日後再討論此點。舉例來說，如果出塊者看 Alice 不順眼，刻意不挑 Alice 的 transaction 而不會被制裁，這樣就沒有 fairness。

Round

每個 round 會有一個指定的 leader，由它打包 command (使用者送的 transaction)成 block，送出給其它 nodes。nodes 會投票同意 （vote) block 或是在超時後投票 (timeout) 要求換 leader。

一但收到 N — f 的 vote，或是 f + 1 的 timeout，就會進入下一個 round。這裡 f 表示壞人上限數量，N > 3f 表示 nodes 總數。

Pala 的 timeout 要求N — f 個，不過兩者都表示原本的 round ( Pala 稱為 epoch) 已無法成功出塊了。Pala 的 timeout 時間是定值，而 LibraBFT 的 timeout 時間會隨著 round 增加而可能增加 (後述)。

除了 round 外，另有 epoch 表示同一批 validator 的任期。每個 epoch 從 round 1 開始遞增，一但 commit epoch + 1 的 command，同一 epoch 後面的指令就不會被執行了。

Pala 有同樣的概念，只是 Pala 稱為 session 而不是 epoch。另外，本篇論文沒有談到如何處理讓不同任的 validators 交接 (Pala有討論）。

Records

LibraBFT 共有四種 record:

• block: 由 leader 在指定的 round 提案，包含待執行的 command。
• vote: node 投票同意 block 和執行後的 state。
• quorum certificate (QC): vote 的集合，並帶有一個選擇性的欄位 commitment (後述)。
• timeout: 投票表示要換 leader。

每個 record 都有 author 和 signature 的欄位，signature 是用 private key 簽整份 record (key + value) 但不含 signature 部份。透過 author 和 signature 可驗證 record 內容沒有被修改。

和 Ethereum 不同的是，合法的 records 會是 block 和 QC 交錯相接，而不是都用 block 串連。下面是示意圖 (C 是 QC):

出處: https://developers.libra.org/docs/assets/papers/libra-consensus-state-machine-replication-in-the-libra-blockchain.pdf

從這結構可得知必須處理完一個 block 才會處理下一個，無法像 doubly-pipelined Pala 那樣最多可同時處理 K 個 block。若 network delay 大於出塊時間 (e.g. 100ms 比 50ms)，同時處理 K >1 個 block 可提升 throughput。

Protocol

流程如下圖:

出處: https://developers.libra.org/docs/assets/papers/libra-consensus-state-machine-replication-in-the-libra-blockchain.pdf

1. round 1 的 leader node3 出了 block B1，傳給所有 nodes。
2. 其它 node 同意，回傳 vote V1。
3. node3 收齊票 (包含自己的 vote)，形成 C1，傳給所有 nodes。
4. (3 和 1 之間的間隔時間) node0 是 round 2 的 leader，收齊其它 nodes 的狀態，確定有 N — f 個 nodes 進入 round 2 後，產生 B2，回到步驟 1 ~ 3。

Data Synchronization

Leader 在提案以前，會先確保足夠人數進入同一 round 才會出塊。

nodes 之間會定時互相傳播自己的狀態，然後向別人取得不足的部份。同步的流程為:

1. 送出 DataSyncNotaification。
2. 依其它人的狀態，向對方發 DataSyncRequest。
3. 收到 DataSyncRequest 後，回覆 DataSyncResponse。

目前的實作很陽春，request 一次傳自己全部的狀態，response 一次回覆全部缺的部份。詳細資料欄位如下:

Voting Constraint

先說明符號:

• B 表示 block。
• C 表示 quorum certificate。
• B ← C 表示 C 的上一個 record 接到 B，意即 C 有記錄 B 的 hash。
• round(B) 表示 B 的 round 是多少。
• 對 B’ ← C’ ← B 來說，previous_round(B) 表示 round(B’)

除了只能投目前 round 的 block 以外，nodes 投票時還要遵守兩個規則:

• First voting constraint: 投過 round x 的票後只能投 round y (y > x) 的票。
• Second voting constraint: 看過 2-chain B0 ← C0 ← B1 ← C1 後，收到新的 block B，previous_round(B) ≥ round(B0)

第一個規則很直覺，只能投更新的 block。若同一 round 裡，leader 不守規則產生兩個不同的 block，voter 只會投看到的第一個，不會 double vote。

第二個規則表示有看到兩個連續通過的 block 後，新的 block B 至少要接上 B0 或 round 數比它大的 block。注意，這裡沒有要求 B 所在的 chain 上面一定有 B0。

Commit Rule

對 3-chain B0 ← C0 ← B1 ← C1 ← B2 ← C2 且 round(B2) = round(B1)+1 = round(B0)+2 來說，B0 以及它之前的 records 的狀態稱為 committed。

一但 committed，表示記錄就不會掉了，和 Pala 的 finalized 等義。

前面提到 QC 有個選擇性的欄位 commitment，用來記錄最新的 committed state。以這裡的例子來說，C2 的 commitment 會記錄 state(C0)。

直觀來說，若 node A 看到上述的 B0 ← … ← C2，表示 A 知道有 N — f 的 nodes 知道 B0 ← C0 ← B1 ← C1。所以之後通過的 block B，會滿足 previous_round(B) ≥ round(B0)。表示 B 所在的 chain 上必定包含 B0。

Confirmation Delay

論文裡沒提，不過由 commit rule 可得知最快需要三個 block 才會 commit 第一個 block，若網路時間很小可忽略，最佳情況下，使用者發出 transaction 立即被包入 block 的話，需要三個出塊時間可確認 transaction 不會消失。

basic Pala 則是需要兩個 block。會有這樣的差異是兩者 voting constraint 不同，由此衍生出的 commit rule (finalized rule) 因此不同。若出塊時間很小，二和三的差異可忽略。

Punishment

有了 voting constraint 和 commit rule，大家可以舉報誰不遵守規則，驗證後可懲罰 (例如沒收 stake-in 的 token)。

Network

文中提到在 P2P synchronization protocol 之上有加一層 gossip overlay，在 broadcast 的時候會隨機傳給 K (≤N) 個 nodes，然後透過收到的 nodes 繼續散佈資料。不過本篇為簡化討論，假設 K = N。

考慮到網路狀況會變化，timeout 的值是個函式:

duration(n) = delta * (n - nc - 2)^r

• n 表示目前的 round。
• nc 表示最後一個 committed block 的 round。
• delta 和 r 是常數。

直觀來說，愈久沒有新的 committed block，timeout 時間愈久。假設無法同意新的 block 是因為網路狀況不佳，逐漸加長 timeout 時間合理。但若是因為 byzantine node (惡意節點) 造成的，反而讓 byzantine node 拖更久沒有 liveness。

實際情況依「惡意節點和網路狀況不穩」何者較容易發生，才好決定參數怎麼設。

其它

還有描述何時可清舊資料、對 leader 和 voters 的經濟誘因、如何決定每個 round 的 leader 等，描述沒特別深入，這裡略過不提。

證明部份我有大略看過，這裡也略過不提。

剩下比較有意思的是文中提供許多 Rust 實作的程式碼和資料結構宣告，有助於了解細節。文裡大致有描述到，不過看 code 更為精確可避免會錯意。

剛好我前陣子實作了 Pala 的 proof of concept，和 LibraBFT 的作法對照，有不同的發現:

• Pala PoC 是將每個動作拆細，收到每一事件會有不同對應的 callback，像是收到 vote 就呼叫 onReceivedVote()。
• LibraBFT 是有個 main handler，收到資料時先存到 record store，依一些規則觸發執行 main handler 的時機。然後 main handler 會從 record store 取得資料更新 local state，然後依此決定要作的事 (建立 block、vote、boradcast、etc)。精神上有點像 React，不知是否是因為 Facebook 員工熟悉 React，所以延續一樣的模式。

兩個作法更有優缺點，有多些經驗後再來消化心得。

結語

整篇看起來滿愉快的，清淅易懂。雖然仍處於 PoC (或 prototype) 階段，可以看得出來作者們用心思考 consensus protocol 和實作的細節。由於內容和 basic Pala 很像 (都受 chained HotStuff 影響)，主要收獲是再次強化對這個體系的理解。

給我主要的啟發是，若不需要相容 Ethereum，設計上少了一些限制 (如 record 串接規則、出塊時間的彈性)。還有看到實作上一些相同的想法，令人會心一笑。