PaLa: A Simple Partially Synchronous Blockchain 讀後筆記

fcamel

Published in

fcamel的程式開發心得

16 min readJan 20, 2019

了解一件事最好的方法就是用自己的話說一次，PaLa 的想法滿有趣的，這篇說明我讀完後的理解，敘述方式和論文略有不同。

之前寫了兩篇說明相關的背景知識，有需要可以參考:

1. 問題

需要去中心化、high throughput、low latency 的 blockchain，這樣在需要 blockchain 的使用情境下，不用擔心因為使用 blockchain 而降低太多效率。

可以從兩個方面提高 throughput (TPS, transaction per second) :

出塊時間 (block time)
每一區塊內打包的 transaction 數量 (block size)

目前最大的 open source blockchain 是 Ethereum。Ethereum 現階段還是使用 POW，因為使用 POW 的關係，大約 15s 出一個區塊 (數字有持續調整)。假設使用和 Ethereum 同樣的架構，只是 consensus protocol 換用 PaLa，理論上 PaLa 可以每秒出一塊。

POW 不能隨意提高 block size，因為會增加傳輸時間而影響 POW 的 stale rate。Vitalik 在 Toward a 12-second Block Time 有說明此點:

Another point that the paper makes is that the transit time is, beyond a certain point, proportional to block size; hence, cutting block size by 50% will also cut transit time to something like 25–40%; the nonscaling portion of the transit time is something like 2s

BFT-style POS 讓少數成員溝通達成共識，比較不用擔心 block size 造成的連鎖效應。綜合以上，理論上改用 PaLa (或其它 BFT-style POS) 可以同時增加出塊速度和單一區塊打包的 transaction 數量，共同提高 TPS。

相較於全民參與 (POW)，代議制度 (BFT-style POS，例如 PaLa) 的作法感覺沒有那麼去中心化，這點需要配套的選舉制度，這不在 PaLa 論文的討論範圍內。

2. 用詞

為方便說明起見，定義這篇文章的一些用詞:

節點: 後文沒特別強調的話，是指 proposer 或 validator。這裡我延續前兩篇的用詞，PaLa 裡面稱 validator 為 committee member。
廣播: 傳訊息給所有 proposer 和 validator。

3. 設計概念

PaLa 的想法來自 pipelined BFT。先複述 PBFT 提案步驟:

Pre-prepare: proposer 打包選定的 transactions 到新的區塊裡，簽名後送給 validators。
Prepare: validators 收到 proposal，驗證通過後，簽名同意票 (prepare message)，然後廣播。驗證不過的話，不作任何事。
Commit: validators 收到 2/3 validators 的 prepare messages 後，廣播 commit messages。
收到 2/3 commit message 後，定案此提案 (finalized)。

Pipelined

PBFT 不同輪的提案之間沒有關聯，但是 blockchain 的提案 (即區塊) 有關聯。可以善用 blockchain 的特性加速產生提案。在 blockchain 的使用情境，提案是 Bs → Bt，表示從 Block s 產生新的區塊 Block t，Block t 包含新的 transactions。

要求 validator Vi 手上有合法的 Bs 才能投票同意 Bt。這個投票傳達兩個訊息:

Vi 同意 Bt，相當於 PBFT 對 Bt 的 prepare message。
Vi 知道有 2/3 以上的 validators 知道 Bs 合法，相當於 PBFT Bs 的 commit message。

第二點是關鍵，在 PaLa 的演算法裡，不斷地使用這個概念推論其它人目前知道什麼資訊。

Local epoch

在有 m > 1 個 proposer 的情況下，怎麼知道現在由誰提案？

一個想法是用時間決定，比方說自 1970/01/01 到現在過了 t 秒，t % m 決定是第幾個 proposer 出塊。但不同節點的地理位置不同，對時可能會有誤差。在 block time 很短的情況下，誤差的影響更大。同一時間裡，有可能兩個 proposer 分別認為現在是 t 和 t + 1 秒，於是同時出塊。validator 也需要看時間判斷提案是否合規則，在時間有誤差的情況下，有許多不確定性。所以不適合用時間當基準。

從宏觀的角度來看，這是 proposer 和 validator 如何對 block 序號達成共識的問題。若大家都知道目前序號是多少，就知道由誰提案。

PaLa 定義 local epoch 為 block 的序號:

假設所有節點自行生出 block B0 (genesis block)，那麼，所有節點起始 local epoch 為 1
假設目前 local epoch 是 e-1，一段時間內 (演算法參數) 沒收到新的提案，廣播訊息 clock(e)
在 local epoch < e 的情況下，收到大家投票通過的 Be-1 或 2/3 的 clock(e)，更新 local epoch為 e

如此一來，節點們可以依 local epoch 決定作的事。

為什麼是 2/3?

在《Blockchain BFT-style POS 的背景知識》的「為什麼覆議比例要求 2/3？」有相關解釋，這裡用不同方式說明。

consensus protocol 有兩個重要指標:

Consistency: 任何時間任何參與者的 prefix of logs 一致。
Liveness: 參與者新增的資料，在一小段時間後會出現在所有參與者的 logs 裡。

直觀來說，投票最低門檻愈高，愈能避免壞人破壞 consistency，但也愈容易沒有 liveness。若門檻是 2/3，表示 >1/3 validators 不投票，會沒有 liveness。但可以容許 <1/3 的壞人，理由如下:

好人對同一編號的提案，只會投一次。
壞人要破壞 consistency，要送兩份提案給兩群不同的好人，然後由壞人兩邊都投票。
兩個提案都達標的話，表示一共有 2/3 + 2/3 = 4/3 票。4/3–1 = 1/3 (重覆投票的人數比例)，表示至少要有 1/3 壞人才能讓兩個提案同時成立。

套用一樣的想法檢視不同參數:

門檻 3/4: 3/4+3/4–1=1/2，壞人 ≥1/2 可破壞 consistency; >1/4 不投票可破壞 liveness。
門檻 8/9: 8/9+8/9–1=7/9，壞人 ≥ 7/9 可破壞 consistency; >1/9 不投票可破壞 liveness。
門檻 5/9: 5/9+5/9–1=1/9，壞人 ≥ 1/9 可破壞 consistency; >4/9不投票可破壞 liveness。

印證了直觀看法:通過提案門檻愈高，對 consistency 的保護愈強; 但對 liveness 保護愈弱。

門檻 2/3 剛好是平衡點，可容許少於 1/3 壞人，兼具 consistency 和 liveness。

4. PaLa Protocol

這裡假設已知 m 個 proposers 和 n 個 validators。如何選出它們是別的議題。
下面省去一些瑣碎檢查的描述，像是要確認收到資料正確才會存下來。

名詞定義

LE: local epoch的值。
Bt: 表示 block 是在 LE = t時產生的。
Nt: Bt 的 notarization，表示 Bt 有 ≥ 2n/3 的同意票。
Ct: 表示某個 blockchain C 的最後一個 block 是 Bt，同義於 Epoch of C 是 t。
freshest notarized chain: 每個節點有各自的 freshest notarized chain。假設某個節點有多個 chain Ci，i 的值最大的 chain 就是 freshest notarized chain (例如該節點有 C2, C3，那 C3 就是 freshest notarized chain)。
函式 CurrentProposer(e) 接收 local epoch 的值 e，決定目前的 proposer 是誰。一個簡單的實作是 e % m。
chain[i] 表示 chain 裡第 i 個 block。chain[i].e 表示該 block 的 epoch。chain[i].e = chain[i-1].e + 1，則 chain[i] 是 normal block; 反之是 timeout block。
Finalize(C) 接收 chain C，去掉最後一個 normal block，輸出結果為 finalized chain。為什麼要用 normal block 呢? 從證明的觀點來看，normal block 可免除潛在的 fork，這樣定義 finality 很穩。那為何 timeout block 無法提供一樣的保證？

這裡說明當 proposer 是壞人時，他如何取得只有他自己才有的 notarization。之後他可以扣著 notarization，等必要的時候再丟出來。以此為前提，想像下面的流程:

大家有 N1，大家投完 B1 → B2 但只有 B2 的 proposer P2 有 N2，然後 timeout
下個 proposer 提案 B1 → B3 給大家投票，但只有 B3 的 proposer P3 有 N3，然後又 timeout
這時 P2 丟出 N2 給大家，下個 proposer P4 會提案 B2 →B4。一樣只有 proposer 有 N4，然後 timeout。此時大家的 freshest notarized chain 是 B1 → B2
P3 丟出 N3 給大家，下個 proposer P5 會提案 B3 → B5。一樣只有 proposer 有 N5。此時 freshest notarized chain 是 B1 → B3
這時若 P4 丟出 N4，大家的 freshest notarized chain 會改成 B1 → B2 →B4，如果可以用 timeout block (B4) 作 finality 條件，B2 會 finalized。
若之後 P5 丟出 N5，大家的 freshest notarized chain 變成 B1 → B3 → B5，結果之前的 B2 並沒有 finalized

在不誠實 validator < n/3 的情況下，上述的例子有可能發生。因此，timeout 不能作為 finality 的條件。

Proposer and Validator

收到 Bt 時:

有需要就更新 freshest notarized chain

收到 Nt 時 (可能是收齊 2n/3 同意票觸發，或是直接取得匯整的結果):

若 t> LE，更新 LE = t
有需要就更新 freshest notarized chain

收到 2n/3 clock(t) 時:

若 t > LE，更新 LE = t

Proposer

更新 LE = t 時，若 CurrentProposer(t) 是自己:

LE = t 的原因是收到 Nt-1，直接提案
LE = t 的原因是收齊 clock(t)，等一下下 (演算法參數，論文內稱為 1sec) 再提案。多等一下有可能收到更多資訊，有機會從更新的 freshest notarized chain 出塊
廣播提案 Bs → Bt，Bs 是 freshest notarized chain 的最後一個 block
同一個 local epoch 下，提案內容必須一樣，不然會造成 fork

Validator

更新 LE = t 時:

若先前已收到 Bs → Bt，檢查能否投同意票 (後述)

收到 Bs → Bt 時:

若 LE = t，檢查是否可投同意票 (後述)

符合檢查同意票條件時 (LE = t 且收到 Bs → Bt)，若以下條件都成立，投同意票:

Bt 合法: CurrentProposer(t) 的簽名無誤且 Block 內容合法
LE = t 的當下的 freshest notarized chain 是 Cs (即最後一個 block 是 Bs)。這裡選用 LE = t 當下的 freshest notarized chain，而不是收到 Bt 當下的 freshest notarized chain (後者可能比前者新)，是想提供一點彈性，增加出塊成功的機率
先前不曾投票同意 Bt

Timeout:

假設 LE = e，經過一段時間 (演算法參數，論文內稱為 1min，是 1sec 的六倍) 沒收到新的提案，廣播 clock(e+1)

5. 雜項討論

證明 Consistency

詳情看論文。這裡只提 Lemma 1 (uniqueness for each epoch number):

Let chain and chain’ be two notarized chains in the honest view of a good execution such that chain[-1].e = chain’[-1].e, it must be that chain = chain’

證法如下:

假設 chain 和 chain’ 的 epoch 一樣。表示至少有 2n/3 + 2n/3 = 4n/3 票。
好人有 Ng 個，壞人有 Nb 個。只有壞人才會兩邊都投，所以: Ng + 2Nb = n + Nb
由於前提是壞人 < n/3，n + Nb < n + n/3 = 3n/4 ( →←)

得證 chain = chain'。

藉由 Lemma 1，減少需要列舉討論的情境，列舉討論完後，就能說明前述流程有保證 consistency。

證明 Liveness

詳情看論文。論文的前提 “strong period of synchony” 意思是進入一但進入網路全通的狀態，之前所有沒傳到的訊息都會傳到。所以，大家的 local epoch 會更新成一樣的值。直觀來看，有這個前提就能保證 liveness，我沒讀剩下的證明。

不過要保證這個前提成立，在 network layer 要付出代價。比方說所有訊息都要 application layer ACK，沒收到 ACK 就不停地重傳。這是一個無效率但有保證滿足前提的作法。

Chain of Trust

Notarization 是 validators 投票的結果，不在原本的 block 裡。但新加入的節點要驗證 blockchain 的正確性，需要 notarization。

論文沒討論怎麼實作較適當。直覺將 notarization 寫入 blockchain 裡比較簡單。可能的作法是 proposer 在出 Bs → Bt 時，將 Ns 寫入 Bt 裡。

5. Proposer 輪替

論文沒討論這點，不過只要確認新 proposer 名單進入 finalized chain，就可以加入 CurrentProposer() 的輸出了。

6. Validator 輪替

( PaLa 稱這為 committee reconfiguration scheme )

前述的流程，是對現有的 validators 達成共識，雖然其它節點可驗證 blockchain 上的 block 是否有照規則作，無法保證新的 validator 有追上最新 finalized chain。因為 finality 是基於現有 validators 投票結果推論出的，新 validators 沒參與先前投票，不確定他們認知的 finalized chain 是什麼。

解法的概念很簡單: 交接期讓新舊 validators 一同投票，兩組 validators 都同意才能出塊，出塊後就表示雙方對 finalized chain 達成共識。

具體作法是引入新的函式 Comm(chain[:i-1])，表示接收 chain 裡第一個 block 到第 i-1 的 block，輸出第 i 個 block 要由那些 validators 投票。Comm(chain[:i]) ≠ Comm(chain[:i-i]) 表示發生輪替。

為了方便說明，這裡更新投票流程如下:

Comm(chain[:i-1]) = (VSi, VSj)。VSi 和 VSj 是兩組不同的 validators，分別有 n 位。要提案產生 chain[i] 時，需要 VSi 和 VSj 各自 2n/3 同意票才行。特別的是，VSi 和 VSj 成員可以完全一樣、部份交集或完全不同。
收到 VSi 或 VSj 2n/3 的 clock(e-1)，表示 timeout，更新 LE = e

後面用例子說明輪替。簡化說明起見:

Bi 表示已收到 Ni 的 block
(Bi) 表示還沒產生提案的 block

B1 -> B2 
VS1   VS1
VS1   VS1

上圖表示 B1、B2 由 VS1 投票。假設 B1 和 B2 包含新的 validators 清單 VS2。那麼，B3 通過以後，Comm(chain[:3]) = (VS1, VS2)，因為 B2 finalized 後，下任 validators 清單就確定了。

B1 -> B2  -> B3  -> (B4)
VS1   VS1    VS1    VS1
VS1   VS1    VS1    VS2

這時 B4 需要分別收到 VS1 和 VS2 各自 2n/3 同意票才過關 (notarized)。取得同意後，表示 VS1 和 VS2 的 Finalized(chain[:4]) 都是 B1 → B2 → B3，此時 VS1 能放心卸任。所以，Comm(chain[:4]) = (VS2, VS2)，如下圖所示:

B1 -> B2  -> B3  -> B4  -> (B5)
VS1   VS1    VS1    VS1    VS2
VS1   VS1    VS1    VS2    VS2

換句話說，交接需要兩個 normal block:

第一個 normal block (B4) 讓 validators 從 (VS1, VS1) → (VS1, VS2)
第二個 normal block (B5) 讓 validators 從 (VS1, VS2) → (VS2, VS2)

7. Doubly-pipelined PaLa

前述的作法要求收到 Bs → Bt 時，必須自己的 freshest notarized chain 的最後一個 block 是 Bs，才能投同意票。造成 validators 可能要等收齊資料才能投票。

為了加快出塊速度，proposer 和 validator 容許 k 個 unnotarized block (先前的版本等同於 k = 1)。

前述流程需作下列修改:

local epoch 改用 (e, s) 表示，e 的意思和之前一樣，s 是流水號 1、2、3 …。每個新 epoch 的 s = 1
Validator 在 LC = e 時，超過一段時間沒收到新區塊 B(e, -)，廣播 clock(e+1)。對時的方法和先前一樣
時間 e 時，選定的 Proposer 可連續出 k 個 unnotarized block B(e, s)、B(e, s+1)、…、B(e, s+k-1)
Validator 投票規則比較複雜一點，後述。
Finalized(chain) 會去掉最後 k 個 normal block 和之後的 block。

收到 B(e1, s1) → B(e2, s2) 時，滿足以下全部條件才投同意票:

已知的 chain 有包含到 B(e1, s1)
同一個序號 (e, s) 只投一次
LC ≥ e2
s2 ≤ k 或是 B(e2, 1) 到 B(e2, s2-k) 已 notarized
LC = e 時，一樣記住當下的 freshest notarized chain chain。B(e’, s1) → B(e, 1) 的 B(e’, s1) 是 chain 的最後一個 block

8. 結語

PaLa 描述得滿完整的，理論上沒有 network partition 的情況下，doubly-pipelined PaLa 應該會很順; 有 network partition 時，使用 local epoch 應該可以有 deterministic 的行為，感覺滿有潛力的。

此外就是所有論文都有的問題，要自行思考一些實作細節，像是如何重傳沒傳到的資料，或是不斷失敗提案或投票的情況下，表示自己的 freshest notarized chain 很可能和大眾不同，要用其它方法取得之前漏取的資料。