Hyperledger實戰之——分布式系統（3）

——本文是作者自己原創編寫的電子書中的部分章節，在此分享給各位CSDN的讀者。

接上篇

3.3.2 一些經典共識算法

Paxos 算法

分布式系統領域，最重要、最著名的共識算法首推 Paxos，是Lesile Lamport（萊斯利 蘭波特）}提出的方案。

Lesile 是 2013年的圖靈獎得主，LaTex 排版軟體的發明人。1990年，Lesile 在一篇送出給 ACM TOCS Jnl. 的論文中，用神話故事的方式提出了 Paxos 共識算法\footnote{Lamport L. How to make a multiprocessor computer that correctly executes multiprocess progranm[J]. IEEE transactions on computers, 1979(9):690-691.}，但當時的評審委員會沒有讀懂他的算法，于是建議他用數學語言、而不是用神話故事來描述算法的核心。Lesile 很生氣并拒絕修改論文，并且撤回了這篇論文。

後來，微軟的 Butler Lampson 讀懂了這篇論文，并在 1996年 的 WDAG 上提出了重新稽核這篇文章。1997年，MIT 的 Nancy Lynch（又是FLP裡面的那位L – Nancy Lynch）在 WDAG’97 \footnote{11th International Workshop on Distributed Algorithms. Saarbrücken, Germany, September 24-26, 1997}上改寫了 Lesile 的論文并給出了 Paxos 的數學證明。于是直到 1998年 的 ACM TOCS 上，這篇對于分布式計算領域至關重要的論文才被接受了。

後來 2001年，Lesile Lamport 終于使用簡單的語言而不是神話故事重新描述了 Paxos 算法 \footnote{Lamport, Leslie. “Paxos made simple.” ACM Sigact News 32.4(2001):18-25.}，但仍然拒絕使用數學語言來講述 Paxos 。關于 Paxos 算法的原理和細節，各位讀者可以參照各種專著，本節不做展開叙述。

PoW 共識

PoW 本來是一類共識機制的總稱，并不是專指比特币網絡使用的共識算法。但由于一些原因導緻 PoW 幾乎被升華到了比特币「靈魂」的高度，是以值得花一些篇幅來解釋一下它的工作原理。

PoW 的本質是計算一個叫做 nonce 的數值，已知:

• 前一區塊的 hash 值 previous_hash、目前區塊的 Merkle樹的根 hash 值 data_hash、時間戳 timestamp;
• 目前區塊難度 difficulity;
• 求滿足下列條件的 nonce 值:

一般說來，對于大部分第一次接觸 PoW 的人來講，最難了解的部分是* BeginZeroBits()* 方法，或者稱作 * Difficulty()* 方法。實際上這個方法沒什麼神秘的，它做的事情就是數（shǔ）數（shù） – 計算從最高位開始的連續零的個數。

用自然語言來解釋前面的公式就是：尋找一個合适的 nonce 值，使得四個字段（前區塊 hash 、目前區塊資料 hash、時間戳、 nonce）的 hash 值的最高 n 位都是零，而且 n 大于等于 difficulty 。如果用更簡單的圖檔來描述的話，就是這個樣子（見圖\ref{fig:ds_008}）了:

由于 hash 算法的雪崩效應特性，即使輸入資料發生最微小的變化，也會導緻 block_hash 的值産生不可區分性的改變。要得到一個滿足最高位連續幾個零的 block_hash，除了窮舉 nonce 值暴力計算之外，沒有其他辦法。

比如要為 Hello, world! 算一個高位連續16個零的 hash 值，從``0’'開始枚舉 nonce 的話需要計算\textbf{4251}次才能得到一個滿足要求的結果（見圖\ref{fig:ds_009}）。

前面的核心算法如果用僞代碼（見代碼\ref{lst:ds_001}）來描述的話，大概是這個樣子：

while true
	  blockHash = sha256（previousHash，dataHash，timeStamp，nonce）
	  zBits = countLeadingZeroBits（blockHash）
	  if zBits >= difficulty
	    return nonce
	  else
	    nonce++
           

這樣一個算法，自從有了比特币的加持，你不點個贊膜拜一下的話都會被嘲笑``不懂區塊鍊’'。

盡管 （計算依賴類）PoW 算法浪費了大量的寶貴能源，不過算法背後的思想堪稱精妙絕倫，值得我們深入探究。知其是以然，之後才能真正了解它對于加密數字貨币的重要性。

前文談到比特币使用的區塊鍊技術實際上脫胎于 Surety，而比特币使用的 PoW 是從哪兒來的呢？這就要從「垃圾郵件」談起了。

PoW 的全稱是 Proof of Work，這一機制最早是由Cynthia Dwork和 Moni Naor 提出來的算法。在當時的網際網路上，由于批量發送電子郵件的低成本，導緻電子郵件成為了正常營銷手段，并造成了垃圾電子郵件的泛濫。為了解決這個的問題，Dwork 和 Naor 在文章\footnote{Dwork, Cynthia;Naor, Moni(1993). Pricing via Processing, Or, Combatting Junk Mail, Advances in Cryptology. CRYPTO’92: Lecture Notes in Computer Science No. 740. Springer: 139–147.} 中提出了 pricing function 的概念：在發送端需要計算一個「成本稍高、但并不棘手」的問題，才可以發送郵件。以此來大幅提高批量發送郵件的成本，同時又不會對于日常的發送普通郵件造成太大影響。

1997年，Adam Back 在 pricing function 的基礎上設計了 hashcash 并将其應用于垃圾郵件治理和 DoS 攻擊，并在 2002年将其以論文

\footnote{Adam Back, Hashcash - A Denial of Service Counter-Measure, technical report, August 2002.}的形式發表。其核心思想是:

• 發件方在郵件頭部添加「郵件簽名」，其中包含收件人位址，時間戳和一個 counter;
• 郵件簽名的 SHA-1 哈希值的前\numfont{20}位全部為0。

這種情況下，除了窮舉 counter 之外，發件方沒有任何辦法可以得出有效的郵件簽名。這個 hashcash 就足以證明該郵件不太可能是垃圾郵件。而在郵件的接收端，隻需要非常低的成本就可以驗證 hashcash 的有效性。

鑒于其計算成本和時間成本，正常發送一兩封郵件的時間成本并不明顯，是以不會對普通使用者有太大影響。但是批量發送郵件的成本就超出郵件推銷員們的接受範圍了。

細心的讀者應該能看出來，比特币使用的 PoW 完全就是 hashcash 中的郵件簽名。比特币白皮書中也明确提到了 ``To implement a distributed timestamp server on a peer-to-peer basis，we will need to use a proof-of-work system similar to Adam Back’s Hashcash，rather than newspaper or Usenet posts’’ 。是以從 PoW 的角度來看，比特币這麼一個金蛋居然是從垃圾郵件治理的技術中孵化出來的，是不是有一點意外呢。

前面提到的這兩篇論文是如此的偉大，一舉奠定了後來的整個加密數字貨币關于共識機制的思想基礎。Pricing 一文作為思想的提出者當然居功至偉，其主要 focus 在定義和尋找适合用作 pricing function 的數學問題。而 Hashcash 一文則清晰地闡述了 PoW 的核心思想：1）隻能暴力計算 counter 值;2）驗證成本極低。

2004年，\namefont{Hal Finney} 借鑒了 hashcash 的工作原理搭建了 \abbrfont{RPoW} – resuable proof of work 系統。正因如此，2009年比特币上線之後，在中本聰本尊現身之前，Hal 一度被懷疑是 Satoshi 的真身。實際上這一猜測也并不離譜，Hal 是加密數字貨币的積極提倡者和探索者之一，是比特币的早期貢獻者之一，是第一筆比特币交易的接受方，是中本聰之後的第二位比特币礦工，是和 Satoshi 住在同一個小鎮長達10年的鄰居。不幸的是，Hal 患了肌萎縮性側索硬化症（漸凍人症），于2014年8月28日離世。此外，他還是人體冷凍技術的首個采用者，他去世後遺體被空運到美國亞利桑那州的 Alcor 生命延續基金會，儲存在零下 195 攝氏度的低溫下，等待有一天被喚醒…好像有點八卦了，還是接着說 PoW 吧。

前面已經用自然語言、圖檔和僞代碼把 PoW 的理念解釋得很清晰了。實際上用生活的語言解釋起來更容易了解：假設你是一個高中生，要熟練掌握一個實體公式，一般需要幾個小時的認真學習、或者幾十個小時的邊走神兒邊學習。但要檢驗你是不是掌握了這個公式就很簡單：出兩道題做一下。能把題做出來就證明你掌握了這個公式。

PoW 也是一樣的原理：能給出滿足要求的 counter/nonce 值，就證明你不是壞人，系統就會接受你送出的請求。在比特币白皮書中明确寫了 PoW 是沿襲了 hashcash。這麼看來，區塊鍊是脫胎于 Surety，PoW 是借鑒了 hashcash，是不是這樣就可以說比特币其實沒有什麼創新呢?

答案當然是否定的。雖然不是比特币發明了 PoW ，但比特币是第一次把 PoW 用做分布式系統的共識機制，然後才開啟了加密數字貨币的傳奇曆程。在結束關于 PoW 的介紹之前，還有一個小小的誤解需要說明一下。受比特币的影響，很多程式員以為 PoW 就是以 hash 為基礎的。但實際上 hash 隻是實作 PoW 的一個選項，除了 hash 之外，卷積求導、大質數分解等運算都可以拿來實作 PoW 。此外，PoW是一個共識機制，是一類共識算法的總稱，并不是特指以某一個共識算法。

pBFT共識算法

pBFT 的全稱是 Practical Byzantine Fault Tolerance，是 Miguel Castro 和 Barbara Liskov 在1999年的文章中提出來的，它在一定程度上解決了原始 BFT 算法的效率問題，把算法複雜度從指數級降低到多項式級，是第一個在工程應用中可行的 BFT 類算法。它的發明人之一的 Barbara Liskov 是計算機領域的一位傑出的女性科學家，由于提出六大設計原則之一的著名的 Liskov Substitute Principle 2008年獲得了圖靈獎。從 pBFT 到 LSP，可以想象 Barbara Liskov 可不是隻搞理論的學究，其工程能力也一定是頂級的存在。

接下來我們試圖用最簡單的方式來解釋一下 pBFT 的工作過程。

如圖\ref{fig:ds_010}所示，pBFT 算法的的共識過程中會有幾個基本角色和概念:

• client（用戶端）：用戶端發起交易請求到主節點;
• primary（主節點）：主節點負責将來自用戶端的請求排序，然後按順序廣播給備份節點;
• backup（備份節點）：除主節點之外的其他節點;
• view（視圖）：某個節點擔任主節點的網絡快照，當一個主節點失效時，就要啟動視圖更換。算法中用到的是一個連續編号的整數。

pBFT 的各節點會輪流擔任 primary 主節點。在運作 pBFT 共識的分布式系統中，網絡的所有節點都是兩兩之間直接連通的，這一點也是 pBFT 和比特币網絡的 PoW 共識不一樣的地方。下面在介紹 pBFT 工作過程的時候會看到，為什麼要求所有節點兩兩互通。

pBFT 的過程分為幾個階段:

• 1. request 階段：用戶端 c 向主節點 p 發起請求 REQUEST，其中包括用戶端的簽名資訊。

     < R E Q U E S T , o , t , c > σ c \mathtt{<REQUEST, o, t, c>\sigma _{c}} <REQUEST,o,t,c>σc​

     • o：請求的操作；
     • t：時間戳；
     • c：用戶端身份資訊；
     • σ c \sigma_{c} σc​：用戶端 c 在 REQUEST 消息上的簽名。

• 1. pre-prepare 階段：節點收到用戶端的請求，進行一系列的校驗。

     校驗通過的話，為該請求配置設定一個序列号，然後向所有備份節點廣播 PRE-PREPARE 消息，其中包含主節點的簽名資訊。

     < < P R E − P R E P A R E , v , n , d > σ p , m > \mathtt{<<PRE-PREPARE, v, n, d>\sigma _{p}, m>} <<PRE−PREPARE,v,n,d>σp​,m>

     • v：視圖編号；
     • n：REQUEST 的序列号；
     • d：m的摘要；
     • σ p \sigma_{p} σp​：主節點 p 在 PRE-PREPARE 消息上的簽名；
     • m：請求消息。

• 1. prepare 階段：備份節點在收到 PRE-PREPARE 消息之後，進入準備階段，并向所有節點發送準備消息 PREPARE。

     < P R E P A R E , v , n , d , i > σ i \mathtt{<PREPARE, v, n, d, i>\sigma _{i}} <PREPARE,v,n,d,i>σi​

     • v：視圖編号；
     • n：REQUEST 的序列号；
     • d：消息m的摘要；
     • i：節點i的編号；
     • σ i \sigma_{i} σi​：節點 i 在 PREPARE 消息上的簽名。

• 1. commit 階段：每個節點收到\textbf{2f+1}個或以上一緻的 PREPARE 消息，則向其他節點發送一條 COMMIT 消息。

     < C O M M I T , v , n , d , i > σ i \mathtt{<COMMIT, v, n, d, i>\sigma _{i}} <COMMIT,v,n,d,i>σi​

     • v：視圖編号；
     • n：REQUEST 的序列号；
     • d：消息m的摘要；
     • i：節點i的編号；
     • σ i \sigma_{i} σi​：節點 i 在 COMMIT 消息上的簽名。

• 1. reply 階段：如果節點 i 收到了\textbf{2f+1}個 COMMIT 消息，則運作 REQUEST 請求中的操作 o，并傳回 REPLY 消息。

     < R E P L Y , v , t , c , i , r > σ i \mathtt{<REPLY, v, t, c, i, r>\sigma _{i}} <REPLY,v,t,c,i,r>σi​

     • v：視圖編号；
     • t：時間戳；
     • c：client；
     • i：節點i的編号；
     • r：對 REQUEST 操作的執行結果；
     • σ i \sigma_{i} σi​：節點 i 在 REPLY 消息上的簽名。

前面講到過，共識算法按照容錯類别可以分為 CFT 和 BFT。CFT 類算法可以容忍網絡中存在一定比例的故障節點，這種情況下仍然可以在保證 liveness 和 safety 的前提下達成共識。相比之下，BFT 類算法不僅可以容忍一定比例的故障節點，還可以容忍一定比例的拜占庭節點（惡意節點），并在保證 liveness 和 safety 的前提下達成共識。

有些區塊鍊研發人員受比特币影響，以為區塊鍊的容錯能力都是 50 % 50\% 50%，其實不是這樣的，每一種 BFT 的容錯能力是不一樣的。比如著名比特币使用的 PoW 的容錯能力是：惡意節點不超過 50 % 50\% 50%。需要強調的是： 50 % 50\% 50% 是由 PoW 的``機率類算法’'特性決定的，而且隻是一個不太靠譜的理論值。實際的情況是，如果有人能控制比特币網絡 30 % 30\% 30%甚至更少的算力就可能威脅到比特币價值網絡了。

而 pBFT 的容錯能力和 PoW 是不一樣的，這是由 pBFT 的工作原理決定的。假設網絡中有 n 個節點的話，拜占庭節點的個數 f 的上限是:

f = n − 1 3 \mathtt{f = \frac{n - 1}{3}} f=3n−1​

也就是說，pBFT 能容忍的故障/惡意節點的個數必須小于節點總數的三分之一。

其他共識算法

後來，Paxos 算法又衍生出了 zab 和 raft算法。zookeeper 使用了 zab 算法，Fabric v1.4.1+ 版本支援 raft 算法。網絡上關于這些算法的資料很多，為節省篇幅此處就不展開講了。

3.3.3 資料同步

除了「共識」之外，還有一類「一緻性協定」對于區塊鍊或者其他的分布式系統都很重要。共識隻是盡力保證每一筆交易的「一緻性」，但并不是每一筆交易都達成一緻了，整個系統的所有資料就一緻。一些節點可能會故障重新開機，在重新開機期間的所有交易都沒有參與共識。

還有一些節點可能是在系統運作了一段時間之後才加入的，在加入之前的所有交易都沒有參與共識…類似的情況，就會導緻單純依靠「共識」在有些情況下不能保證系統的資料一緻性的，還有一類專門用來處理資料的同步問題，其中最經典的就是 Gossip 協定。

Gossip 協定

Gossip 協定也稱作 Epidemic Protocol，是1987年 Alan Demer 等人在 ACM 上發表的論文 《Epidemic algorithms for replicated database maintenance》中提出的。算法的初衷是解決分布式資料庫中節點資料同步的問題，是基于流行病傳播方式的節點或者程序之間資訊交換的協定，目前在分布式系統中被廣泛使用。

Gossip 的理論基礎是\textbf{六度分隔理論}，簡單來說就是一個人通過6中間人就可以認識世界上的任何一個人。假設每個人認識150個人，那麼他的六度就是 15 0 6 = 11 , 390 , 625 , 000 , 000 150^6=11,390,625,000,000 1506=11,390,625,000,000（大約是11.4萬億），去掉重複認識的人，這個數字遠遠超過地球上的人口總數。

首先來看一下 Gossip 協定的執行流程：

• 種子節點在收到消息之後，周期性的将消息傳遞給自己可以連接配接到的節點;
• 接受到傳遞過來的消息的節點，随機選擇 N 個與自己鄰接的節點，然後将消息傳遞給這些鄰接節點;
• 節點隻接受消息，但是并不會回報結果;
• 每次在尋找節點傳遞消息的時候，都會像沒有發送過的節點進行傳遞消息;
• 收到消息的節點，不會向發送節點傳送消息。

由 Gossip 協定的執行流程可以知道：

• Gossip 協定的消息傳播需要一個種子節點，并且消息傳輸需要種子節點發起。
• 消息在整個網絡中傳輸需要一定的時間，并不能保證某一個時刻所有的節點都會收到消息，但是理論上來說，最終所有的節點都會收到消息，所有 Gossip 協定是一個最終一緻性的協定。

Gossip 協定的目标是将消息發送到網絡中的每一個節點上。節點兩兩之間進行通信的時候有以下三種方式:

• push-gossip：節點 p 将資料 {\ttfamily <key,value,version>} 及對應的版本号推送給 q 節點，節點 q 更新 p 中比自己新的資料;
• pull-gossip：節點 p 僅将資料 {\ttfamily <key,version>} 推送給節點 q，節點 q 将本地比節點 p 新的資料 {\ttfamily <Key,value,version>} 推送給 節點 p，節點 p 更新本地
• push-pull-gossip：與 pull-gossip 類似，隻是多了一步，節點 p 再将本地比節點 q 新的資料推送給節點 q，節點 q 更新本地資料。

直到資料同步完畢。

待續……