什麼拜占庭將軍問題？比特幣是如何解決的?——深入淺出分散式共識性（一）
- 2019 年 11 月 10 日
- 筆記
之前《淺談分散式CAP定理》簡單介紹了數據在分散式系統中存在的必然定理。簡單回顧一下，一個數據在一個節點需要同步到另外一個節點的過程中，在未完成同步的時候，會出現數據不一致的情況，所以此時必然存在分區容錯性（Partition tolerance）。分散式系統只能從一致性（Consistency）或可用性（Availability）之間去選擇。
CAP講的是分散式一致性，而這次我們來聊聊分散式共識性。很多開發者一直以為一致性與共識性是同一個東西，但兩者講的是完全不同的東西。
- 一致性：A點同步B點數據，然後兩者之間的數據可以達成一致。
- 共識性：一個或多個節點提議了一個值應當是什麼後，採用一種大家都認可的方法，使得系統中所有進程對這個值達成一致意見。
共識性比較常見的場景就是選主，例如redis主掛掉了，集群通用共識性演算法選出一個主。比特幣之類的電子貨幣也需要更複雜的共識性演算法。
下面我們一步步聊下分散式共識性的一些常見演算法與問題。
拜占庭將軍問題
Leslie Lamport(論文排版系統LaTeX的開發者，同時也是2013年的圖靈獎得主)在其論文中描述了如下系統：
一組拜占庭將軍分別各率領一支軍隊共同圍困一座城市。
為了簡化模型，將各支軍隊的行動策略限定為進攻或撤離兩種。因為部分軍隊進攻部分軍隊撤離可能會造成災難性後果，因此各位將軍必須通過投票來達成一致策略，即所有軍隊一起進攻或所有軍隊一起撤離。
同時各位將軍分處城市不同方向，他們只能通過信使互相聯繫。在投票過程中每位將軍都將自己投票給進攻還是撤退的資訊通過信使分別通知其他所有將軍，這樣一來每位將軍根據自己的投票和其他所有將軍送來的資訊就可以知道共同的投票結果而決定行動策略。
此系統的名字叫做拜占庭將軍問題。從描述中，可以顯然知道，將軍們需要通過少數服從多數的演算法在分散式的場景下進行投票決議一個一致性的決定去執行。
在拜占庭將軍問題中，默認是認為信使是不會被截獲並且消息會傳遞到的。更多的情況中，將軍中可能會出現叛徒、信使會被截獲冒充、消息無法到達。而叛徒或信使冒充會惡意地向其他將軍投票，給不同將軍展示不同的投票結果，從而破壞了將軍們執行的一致性。而此類錯誤則稱為拜占庭錯誤。
如果系統能處理拜占庭將軍錯誤正常運行的話，則稱系統擁有拜占庭容錯「Byzantine fault tolerance」，簡稱為BFT。
舉個例子
假設當時有5位將軍投票（單數投票的結果必能形成少數服從多數），其中有1名是叛徒，4名忠誠的將軍中出2人投進攻，2人投撤離的。
這時候叛徒可能故意給2名投進攻的將軍送信表示投進攻，而給另外2名投撤離的將軍送信表示投撤離。這樣在2名投進攻的將領看來，投票結果是3人投進攻，從而發起進攻；而在2名投撤離的將軍看來則是3人投撤離。這樣各支軍隊的一致協同就遭到了破壞，結果是災難性的。
即使這5個將軍都是忠誠的，但投票結果是需要信使在將軍之間去傳遞的，而這些信使在傳遞過程中是有可能被截冒充或者並沒有傳遞到將軍的投票結果，最終還是會影響軍隊的一致協同。
上述的故事映射到電腦系統中，將軍便成了電腦，而信使則是通訊系統。有人會覺得這個問題可以通過加密或簽名的方式解決，但本質上加密過程、簽名演算法也會出錯。雖然加密和簽名一定程度是可以解決這個問題，但這個問題並不是要討論這些加密簽名的強度，而是更多地在於研究集群系統客觀上已經出現錯誤了，他們要怎麼在存在錯誤的情況下讓系統正常的工作。
經典的簡單解決
首先要知道，為什麼這個標題是經典的簡單解決？因為這個解決只是個簡單的解決，在現代系統很多場景中，並不具有普遍的解決能力。
大家看完上面的例子，可能會湧現一種想法，就是在收到來自同一個將軍的投票後，交換各自的結果檢驗看該將軍是否叛徒。例如A將軍把進攻指令發給B將軍，把撤離指令發給C將軍，那麼BC將軍交互一下來自A將軍的指令，就可以知道A將軍是個叛徒，然後把他揪出來幹掉，不再聽他的指令。
但是這種做法根本不能解決問題。雖然在BC交換指令後，可以知道有叛徒的存在，但其實你並不能確定A就是叛徒，因為有可能BC交換指令的過程出現」拜錯「，所以上面的思路並不能解決問題。
回到問題本身，我們是需要在存在錯誤的情況下讓系統正常進行，所以我們只需要設計一套系統在兼容這些」叛徒「就足夠了。怎麼理解？回到拜占庭軍隊上，拜占庭軍隊攻下一座城池至少需要6個將軍，那麼讓軍隊裝備更多將軍，例如10個，在通過兩兩交互指令驗證完消息後，可以知道有多少個叛徒的存在。只要忠誠的將軍數大於等於6那麼就可以執行指令（進攻或撤離），否則軍隊則按兵不動。這個容錯率可以根據自己的系統進行設置，在這個方案被提出時，容錯率描述是1/3。
開頭也說到這個方案在現代系統並不具有普遍解決問題的能力。一是類似比特幣這種分散式記賬本千千萬個節點，如果要進行兩兩的資訊驗證，這個過程和開銷是非常大的，會變得不實際。另外就是並不是所有性質的系統都能允許錯誤節點的執行，例如註冊中心、交易中心等。
先進的解決——比特幣的工作量證明
在「簡單解決」的方案提出之後，有非常多的方案演算法被提出，實用拜占庭容錯（PBFT）、聯邦拜占庭協議（FBA）、授權拜占庭容錯演算法（dBFT）等等。由於其中的複雜度與文章篇幅問題，不一一贅述，有興趣可以到網上查閱。
但其中一個比較有意思的是比特幣中所用到的工作量證明「Proof Of Work，POW」可以大概提一下。
工作量證明是一種對應服務與資源濫用、或是拒絕服務攻擊的經濟對策。一般是要求用戶進行一些耗時適當的複雜運算，並且答案能被服務方快速驗算，以此耗用的時間、設備與能源做為擔保成本，以確保服務與資源是被真正的需求所使用。（來自維基百科的解釋）
結合比特幣的場景去理解，用戶是需要通過挖礦來獲得比特幣，而挖礦是需要花費大量的計算資源的。這個挖礦的過程其實是比特幣設計的一道解密演算法，用戶（節點）是需要一定量的計算才能獲得答案，然後其他給節點驗算，成功後最終獲得比特幣獎勵爭取記賬權。一句話概括工作量證明就是不校驗你的過程，只看你的結果，但獲取這個結果是有壁壘的。具體的演算法原理在後續講到共識性演算法的應用我們再用新篇幅去闡述。
那麼比特幣怎樣才能造假呢？其實它本質依然是少數服從多數的投票，節點獲取結果後是需要其他節點進行驗證投票的，如果你擁有大於50%的假節點，的確是可以篡改數據，控制交易。但是工作量證明引入使得構造一個節點的成本已經足夠大了，在千千萬的節點下想要構造大於50%的假節點，估計有這種財力去實現的人已經可以統治地球了。
拜占庭將軍錯誤看似一個非常嚴重的問題，能造成災難性後果，但其實在大部分場景下並不會出現「拜錯」。下一篇將會落到比較應用層面的共識性演算法，聊下市面上主流的分散式中間件是怎麼在不考慮「拜錯」的情況下，解決分散式共識性問題的。
更多技術文章、精彩乾貨，請關注
個人部落格：zackku.com
公眾號：Zack說碼
