PBFT協議在超過100個節點的時候性能會下降，能優化PBFT使其能支持更高量級（1000）的節點嗎？

---

謝邀。

首先要搞清為什麼PBFT，乃至所有的BFT都沒法應用於超過100個節點。原因的關鍵在於O(N^2)的消息複雜度。這是什麼意思呢？點對點的消息傳輸需要發一個消息就夠了，這是O(1)的消息複雜度，要是廣播一個消息，需要把消息發給網路里所有人一人一份，就是O(N)的消息複雜度，而想要可靠地，在有拜占庭節點（惡意節點）存在的網路里廣播一條消息的話，至少需要O(N^2)的消息複雜度，也就是說，如果網路有100個節點，如果你想讓確認網路里的其他人都確實地收到你的消息，你至少要發10000條消息。

這性能一看就好不了。

於是才有了比特幣，它把可靠的那部分用獎勵，挖礦和最長鏈解決了，於是再大的網路也只是O(N)的消息複雜度，這就scalable了。但是另一個問題就出現了——大網路里傳輸效率和延遲有瓶頸，而這種瓶頸會制約可靠性。也就是說你廣播的東西太大的話，比特幣的那套獎勵，挖礦和最長鏈的東西就不是那麼好使了。

於是，目前所有的提高scalability的方法基本上就是結合兩者，也就是分層。無論是叫分層也好，委員會選舉也好，差不多想法就是我們把某一部分的可靠性用比特幣的方法解決，剩下的部分用BFT。這其實和代議制民主很像——所有人一起討論事情太難了，那麼我們讓所有人選代表，然後選出來幾個代表討論事情就高效多了。

但接下來的問題是這兩部分怎麼對接？兩個方法對於惡意節點的數量要求不一樣（BFT必須嚴格少於1/3，比特幣的話是算力小於1/4），要不要獎勵（自私挖礦算不算惡意呢？），共識類型不一樣（BFT是最終共識，比特幣是最長鏈共識，也就是允許分叉），是許可還是非許可。這些都是處理起來很讓人頭疼的問題，基本上，所有的分層演算法都得要給出這些東西。而我目前為止還沒有看到一個完全找不出漏洞的演算法。

就拿你說的sharding的那篇文章說吧。這個Elastico，或者叫SCP，我很驚訝這個竟然能發表，他們對於無窮小量的處理太隨意了。我不是說他們結果一定不對，但是他們的證明是有問題的。

他們分層非常的幼稚，他的方法就是簡單的隨機選，而隨機選的時候，他們就是簡單的說如果我們的隨機方法是公平的，那麼當這個小組的人數很大的時候，這個小組惡意節點超過1/3的可能無窮小。

首先這個結果看起來就很扯，因為你要求小組人數很大，而他們最終的消息複雜度是O(nc^3)，c是小組的大小，這個東西只有在c小於n的立方根的時候才會小於O(n^2)。而他們的證明裡說c要大於600的時候就很安全了，這也就是說，他們的方法只有在網路里有超過600^3節點的情況下才會優於普通BFT，而在模擬的時候他們用的是1000個節點的網路，他們可沒證明在這麼小的網路里他們還能保證這一點，我相信1000個節點選10個節點惡意節點多於1/3的概率可不小。

而且他們的證明完全沒意義，因為光保證一個小組的安全是不夠的，它需要證明的其實是：對於任意n和相應的c，當c大於一個值的時候，裡面有不超過1/3的小組裡有超過1/3的惡意節點的概率無窮小，可是他證明的是c大於一個值的時候每個小組裡有超過1/3的惡意節點概率無窮小。甚至，他們需要證明在一段時間內這個概率無窮小（如果它輸出真的很高，那麼每天就會達成上千次共識了）。稍微有點概率基礎的人都知道，拋開隨機的次數談小概率事件就是耍流氓。你需要c很大來保證惡意節點超過1/3的概率無窮小，同時n很大才能超過傳統BFT。那麼就算小組有600個節點你的概率是百萬分之一，可是想要超過傳統BFT的話，你需要600^3個節點，那麼每輪就會隨機產生360000個小組，那麼基本上3輪就會出現被惡意節點控制的小組，這證明完全沒意義。

---

推薦閱讀：