Ⅰ 知鏈區塊鏈金融應用實踐平台成績怎麼算
1. 工作量證明（PoW）
中本聰在2009年提出的比特幣（Bitcoin）是區塊鏈技術最早的應用，其採用PoW作為共識演算法，其核心思想是節點間通過哈希算力的競爭來獲取記賬權和比特幣獎勵。PoW中，不同節點根據特定信息競爭計算一個數學問題的解，這個數學問題很難求解，但卻容易對結果進行驗證，最先解決這個數學問題的節點可以創建下一個區塊並獲得一定數量的幣獎勵。中本聰在比特幣中採用了HashCash[4]機制設計這一數學問題。本節將以比特幣採用的PoW演算法為例進行說明，PoW的共識步驟如下：
節點收集上一個區塊產生後全網待確認的交易，將符合條件的交易記入交易內存池，然後更新並計算內存池中交易的Merkle根的值，並將其寫入區塊頭部；
在區塊頭部填寫如表1.1所示的區塊版本號、前一區塊的哈希值、時間戳、當前目標哈希值和隨機數等信息；
表1.1 區塊頭部信息
隨機數nonce在0到232之間取值，對區塊頭部信息進行哈希計算，當哈希值小於或等於目標值時，打包並廣播該區塊，待其他節點驗證後完成記賬；
一定時間內如果無法計算出符合要求的哈希值，則重復步驟2。如果計算過程中有其他節點完成了計算，則從步驟1重新開始。
比特幣產生區塊的平均時間為10分鍾，想要維持這一速度，就需要根據當前全網的計算能力對目標值（難度）進行調整[5]。難度是對計算產生符合要求的區塊困難程度的描述，在計算同一高度區塊時，所有節點的難度都是相同的，這也保證了挖礦的公平性。難度與目標值的關系為：
難度值=最大目標值/當前目標值 （1.1）
其中最大目標值和當前目標值都是256位長度，最大目標值是難度為1時的目標值，即2224。假設當前難度為，算力為，當前目標值為，發現新區塊的平均計算時間為，則
根據比特幣的設計，每產生2016個區塊後（約2周）系統會調整一次當前目標值。節點根據前2016個區塊的實際生產時間，由公式（1.4）計算出調整後的難度值，如果實際時間生產小於2周，增大難度值；如果實際時間生產大於2周，則減小難度值。根據最長鏈原則，在不需要節點同步難度信息的情況下，所有節點在一定時間後會得到相同的難度值。
在使用PoW的區塊鏈中，因為網路延遲等原因，當同一高度的兩個區塊產生的時間接近時，可能會產生分叉。即不同的礦工都計算出了符合要求的某一高度的區塊，並得到與其相近節點的確認，全網節點會根據收到區塊的時間，在先收到的區塊基礎上繼續挖礦。這種情況下，哪個區塊的後續區塊先出現，其長度會變得更長，這個區塊就被包括進主鏈，在非主鏈上挖礦的節點會切換到主鏈繼續挖礦。
PoW共識演算法以算力作為競爭記賬權的基礎，以工作量作為安全性的保障，所有礦工都遵循最長鏈原則。新產生的區塊包含前一個區塊的哈希值，現存的所有區塊的形成了一條鏈，鏈的長度與工作量成正比，所有的節點均信任最長的區塊鏈。如果當某一組織掌握了足夠的算力，就可以針對比特幣網路發起攻擊。當攻擊者擁有足夠的算力時，能夠最先計算出最新的區塊，從而掌握最長鏈。此時比特幣主鏈上的區塊大部分由其生成，他可以故意拒絕某些交易的確認和進行雙花攻擊，這會對比特幣網路的可信性造成影響，但歷派這一行為同樣會給攻擊者帶來損失。通過求解一維隨機遊走問題，可以獲得惡意節點攻擊成功的概率和算力之間的關系：
圖1.1 攻擊者算力與攻擊成功概率
2. 權益證明（PoS）
隨著參與比特幣挖礦的人越來越多，PoW的許多問題逐漸顯現，例如隨著算力競爭迅速加劇，獲取代幣需要消耗的能源大量增加，記賬權也逐漸向聚集了大量算力的「礦池」集中[6-9]。為此，研究者嘗試採用新的機製取代工作量證明。PoS的概念在最早的比特幣項目中曾被提及，但由於穩健性等原因沒被使用。PoS最早的應用是點點幣（肢肢賀PPCoin），PoS提出了幣齡的概念，幣齡是持有的代幣與持有時間乘積的累加，計算如公式（1.4）所示。利用幣齡競爭取代算力競爭，使區塊鏈的證明不再僅僅依靠工作量，有效地解決了PoW的資源浪費問題。
其中持有時間為某個幣距離最近一次在網路上交易的時間，每個節點持有的幣齡越長，則其在網路中權益越多，同時幣的持有人還會根據幣齡來獲得一定的收益。點點幣的設計中，沒有完全脫離工作量證明，PoS機制的記賬權的獲得同樣需要進行簡單的哈希計算：
其中proofhash是由權重因子、未飢逗消費的產出值和當前時間的模糊和得到的哈希值，同時對每個節點的算力進行了限制，可見幣齡與計算的難度成反比。在PoS中，區塊鏈的安全性隨著區塊鏈的價值增加而增加，對區塊鏈的攻擊需要攻擊者積攢大量的幣齡，也就是需要對大量數字貨幣持有足夠長的時間，這也大大增加了攻擊的難度。與PoW相比，採用PoS的區塊鏈系統可能會面對長程攻擊（Long Range Attack）和無利害攻擊（Nothing at Stake）。
除了點點幣，有許多幣也使用了PoS，但在記賬權的分配上有著不同的方法。例如，未來幣（Nxt）和黑幣（BlackCion）結合節點所擁有的權益，使用隨機演算法分配記賬權。以太坊也在逐步採用PoS代替PoW。
3. 委託權益證明（DPoS）
比特幣設計之初，希望所有挖礦的參與者使用CPU進行計算，算力與節點匹配，每一個節點都有足夠的機會參與到區塊鏈的決策當中。隨著技術的發展，使用GPU、FPGA、ASIC等技術的礦機大量出現，算力集中於擁有大量礦機的參與者手中，而普通礦工參與的機會大大減小。
採用DPoS的區塊鏈中，每一個節點都可以根據其擁有的股份權益投票選取代表，整個網路中參與競選並獲得選票最多的n個節點獲得記賬權，按照預先決定的順序依次生產區塊並因此獲得一定的獎勵。競選成功的代表節點需要繳納一定數量的保證金，而且必須保證在線的時間，如果某時刻應該產生區塊的節點沒有履行職責，他將會被取消代表資格，系統將繼續投票選出一個新的代表來取代他。
DPoS中的所有節點都可以自主選擇投票的對象，選舉產生的代表按順序記賬，與PoW及PoS相比節省了計算資源，而且共識節點只有確定的有限個，效率也得到了提升。而且每個參與節點都擁有投票的權利，當網路中的節點足夠多時，DPoS的安全性和去中心化也得到了保證。
4. 實用拜占庭容錯演算法（PBFT）
在PBFT演算法中，所有節點都在相同的配置下運行，且有一個主節點，其他節點作為備份節點。主節點負責對客戶端的請求進行排序，按順序發送給備份節點。存在視圖（View）的概念，在每個視圖中，所有節點正常按照處理消息。但當備份節點檢查到主節點出現異常，就會觸發視圖變換（View Change）機制更換下一編號的節點為主節點，進入新的視圖。PBFT中客戶端發出請求到收到答復的主要流程如圖4.1所示[10] [11]，伺服器之間交換信息3次，整個過程包含以下五個階段：
圖4.1 PBFT執行流程
目前以PBFT為代表的拜占庭容錯演算法被許多區塊鏈項目所使用。在聯盟鏈中，PBFT演算法最早是被Hyper ledger Fabric項目採用。Hyperledger Fabric在0.6版本中採用了PBFT共識演算法，授權和背書的功能集成到了共識節點之中，所有節點都是共識節點，這樣的設計導致了節點的負擔過於沉重，對TPS和擴展性有很大的影響。1.0之後的版本都對節點的功能進行了分離，節點分成了三個背書節點(Endorser)、排序節點(Orderer)和出塊節點(Committer)，對節點的功能進行了分離，一定程度上提高了共識的效率。
Cosmos項目使用的Tendermint[12]演算法結合了PBFT和PoS演算法，通過代幣抵押的方式選出部分共識節點進行BFT的共識，其減弱了非同步假設並在PBFT的基礎上融入了鎖的概念，在部分同步的網路中共識節點能夠通過兩階段通信達成共識。系統能夠容忍1/3的故障節點，且不會產生分叉。在Tendermint的基礎上，Hotstuff[13]將區塊鏈的塊鏈式結構和BFT的每一階段融合，每階段節點間對前一區塊簽名確認與新區塊的構建同時進行，使演算法在實現上更為簡單，Hotstuff還使用了門限簽名[14]降低演算法的消息復雜度。
5. Paxos與Raft
共識演算法是為了保障所存儲信息的准確性與一致性而設計的一套機制。在傳統的分布式系統中，最常使用的共識演算法是基於Paxos的演算法。在拜占庭將軍問題[3]提出後，Lamport在1990年提出了Paxos演算法用於解決特定條件下的系統一致性問題，Lamport於1998年重新整理並發表Paxos的論文[15]並於2001對Paxos進行了重新簡述[16]。隨後Paxos在一致性演算法領域占據統治地位並被許多公司所採用，例如騰訊的Phxpaxos、阿里巴巴的X-Paxos、亞馬遜的AWS的DynamoDB和谷歌MegaStore[17]等。這一類演算法能夠在節點數量有限且相對可信任的情況下，快速完成分布式系統的數據同步，同時能夠容忍宕機錯誤（Crash Fault）。即在傳統分布式系統不需要考慮參與節點惡意篡改數據等行為，只需要能夠容忍部分節點發生宕機錯誤即可。但Paxos演算法過於理論化，在理解和工程實現上都有著很大的難度。Ongaro等人在2013年發表論文提出Raft演算法[18]，Raft與Paxos同樣的效果並且更便於工程實現。
Raft中領導者占據絕對主導地位，必須保證伺服器節點的絕對安全性，領導者一旦被惡意控制將造成巨大損失。而且交易量受到節點最大吞吐量的限制。目前許多聯盟鏈在不考慮拜占庭容錯的情況下，會使用Raft演算法來提高共識效率。
6. 結合VRF的共識演算法
在現有聯盟鏈共識演算法中，如果參與共識的節點數量增加，節點間的通信也會增加，系統的性能也會受到影響。如果從眾多候選節點中選取部分節點組成共識組進行共識，減少共識節點的數量，則可以提高系統的性能。但這會降低安全性，而且候選節點中惡意節點的比例越高，選出來的共識組無法正常運行的概率也越高。為了實現從候選節點選出能夠正常運行的共識組，並保證系統的高可用性，一方面需要設計合適的隨機選舉演算法，保證選擇的隨機性，防止惡意節點對系統的攻擊。另一方面需要提高候選節點中的誠實節點的比例，增加誠實節點被選進共識組的概率。
當前在公有鏈往往基於PoS類演算法，抵押代幣增加共識節點的准入門檻，通過經濟學博弈增加惡意節點的作惡成本，然後再在部分通過篩選的節點中通過隨機選舉演算法，從符合條件的候選節點中隨機選舉部分節點進行共識。
Dodis等人於1999年提出了可驗證隨機函數（Verifiable Random Functions，VRF）[19]。可驗證隨機函數是零知識證明的一種應用，即在公私鑰體系中，持有私鑰的人可以使用私鑰和一條已知信息按照特定的規則生成一個隨機數，在不泄露私鑰的前提下，持有私鑰的人能夠向其他人證明隨機數生成的正確性。VRF可以使用RSA或者橢圓曲線構建，Dodis等人在2002年又提出了基於Diffie-Hellman 困難性問題的可驗證隨機函數構造方法[20]，目前可驗證隨機函數在密鑰傳輸領域和區塊鏈領域都有了應用[21]。可驗證隨機函數的具體流程如下：
在公有鏈中，VRF已經在一些項目中得到應用，其中VRF多與PoS演算法結合，所有想要參與共識的節點質押一定的代幣成為候選節點，然後通過VRF從眾多候選節點中隨機選出部分共識節點。Zilliqa網路的新節點都必須先執行PoW，網路中的現有節點驗證新節點的PoW並授權其加入網路。區塊鏈項目Ontology設計的共識演算法VBFT將VRF、PoS和BFT演算法相結合，通過VRF在眾多候選節點中隨機選出共識節點並確定共識節點的排列順序，可以降低惡意分叉對區塊鏈系統的影響，保障了演算法的公平性和隨機性。圖靈獎獲得者Micali等人提出的Algorand[22]將PoS和VRF結合，節點可以採用代幣質押的方式成為候選節點，然後通過非互動式的VRF演算法選擇部分節點組成共識委員會，然後由這部分節點執行類似PBFT共識演算法，負責交易的快速驗證，Algorand可以在節點為誠實節點的情況下保證系統正常運行。Kiayias等人提出的Ouroboros[23]在第二個版本Praos[24]引入了VRF代替偽隨機數，進行分片中主節點的選擇。以Algorand等演算法使用的VRF演算法為例，主要的流程如下：
公有鏈中設計使用的VRF中，節點被選為記賬節點的概率往往和其持有的代幣正相關。公有鏈的共識節點范圍是無法預先確定的，所有滿足代幣持有條件的節點都可能成為共識節點，系統需要在數量和參與度都隨機的節點中選擇部分節點進行共識。而與公有鏈相比，聯盟鏈參與共識的節點數量有限、節點已知，這種情況下聯盟鏈節點之間可以通過已知的節點列表進行交互，這能有效防止公有鏈VRF設計時可能遇到的女巫攻擊問題。
7. 結合分片技術的公式演算法
分片技術是資料庫中的一種技術，是將資料庫中的數據切成多個部分，然後分別存儲在多個伺服器中。通過數據的分布式存儲，提高伺服器的搜索性能。區塊鏈中，分片技術是將交易分配到多個由節點子集組成的共識組中進行確認，最後再將所有結果匯總確認的機制。分片技術在區塊鏈中已經有一些應用，許多區塊鏈設計了自己的分片方案。
Luu等人於2017年提出了Elastico協議，最先將分片技術應用於區塊鏈中[25]。Elastico首先通過PoW演算法競爭成為網路中的記賬節點。然後按照預先確定的規則，這些節點被分配到不同的分片委員會中。每個分片委員會內部執行PBFT等傳統拜占庭容錯的共識演算法，打包生成交易集合。在超過的節點對該交易集合進行了簽名之後，交易集合被提交給共識委員會，共識委員會在驗證簽名後，最終將所有的交易集合打包成區塊並記錄在區塊鏈上。
Elastico驗證了分片技術在區塊鏈中的可用性。在一定規模內，分片技術可以近乎線性地拓展吞吐量。但Elastico使用了PoW用於選舉共識節點,這也導致隨機數產生過程及PoW競爭共識節點的時間過長，使得交易延遲很高。而且每個分片內部採用的PBFT演算法通訊復雜度較高。當單個分片中節點數量較多時，延遲也很高。
在Elastico的基礎上，Kokoris-Kogias等人提出OmniLedger[26]，用加密抽簽協議替代了PoW選擇驗證者分組，然後通過RandHound協議[27]將驗證者歸入不同分片。OmniLedger。OmniLedger在分片中仍然採用基於PBFT的共識演算法作為分片中的共識演算法[28]，並引入了Atomix協議處理跨分片的交易，共識過程中節點之間通信復雜度較高。當分片中節點數量增多、跨分片交易增多時，系統TPS會顯著下降。
Wang等人在2019年提出了Monoxide[29]。在PoW區塊鏈系統中引入了分片技術，提出了連弩挖礦演算法（Chu ko-nu mining algorithm），解決了分片造成的算力分散分散問題，使得每個礦工可以同時在不同的分片進行分片，在不降低安全性的情況下提高了PoW的TPS。
Ⅱ Raft演算法
Raft演算法是解決分布式系統共識的問題的演算法，Raft是基於Multi-Paxos的基礎上做了簡化和限制。不同於Paxos的難以理解，Raft設計的首要目的就是可理解性，一個易於理解、實現簡單的分布式一致性協議。
Raft 將一致性演算法分解成了幾個關鍵模塊，例如領導人選舉、日誌復制和安全性，本文將主要基於 raft論文 簡單分析raft演算法。
Raft是強領導(Strong leader)模型，一切以leader為主，比如日誌只能由leader復制到其他伺服器。所以leader的選舉是非常重要的一部分。
首先介紹raft演算法的三個服務狀態：
任意時間集群中只能由一個leader存在。
Raft使用心跳機制實現leader選舉。在服務啟動的時候，處於follower角色，需要注意的是每個服務於leader的心跳超時的時間是隨機的(150-300 毫秒)。
如上圖，集群中有三個幾點A、B、C，超時時間分別為150ms、200ms、300ms剛啟動時任期編號都是0，都處於follower角色。節點A與leader的心跳超時時間最短，最先從follower狀態轉為candidate，並增加自己的任期編號，先給自己投上一張選票，並向集群中其他節點發送投票信息，當B、C節點接受到A的投票請求之後，在任期為1的這個階段沒有給其他節點投過票，便接受A的投票請求。此時節點A接受到了集群中超過一半的節點的投票，便成為任期為1的leader。
上訴是最簡單的選舉流程，裡面有很多概念都需要解釋，比如為什麼超時時間不一樣？任期編號是什麼？投票比較的規則又是什麼？
1. 任期編號
每個leader在當選期間都有一個自己的任期編號，它是全局單調遞增的數字。每個節點都存儲這當前的leader的任期編號，當處於candidate階段的時候，發起投票的時候會把當前任期編號加一。
而且當一個節點接受到比自己任期高的請求時，會將自己的任期編號更新為高的任期編號，如果當前角色是leader，會從leader轉換為follower角色。當接受到任期編號比自己小的請求時，節點會直接拒絕這個請求。
2. 投票比較規則
a. 先到先服務：一個節點在一個任期只能投一票，如果A、B節點都請求C節點投票，C節點如果先投給A之後、就會拒絕B的投票請求。
b.日誌完整性：一個節點接受的投票信息如果它的日誌比自身小，將會拒絕該投票請求。
c.過半策略：當某節點接受到了集群中超過一半的節點投票之後，成為該次任期的leader，向其他節點發送leader心跳。
d. 在等待投票期間，candidate 可能會收到另一個聲稱自己是 leader 的伺服器節點發來的 AppendEntries RPC 。如果這個 leader 的任期號（包含在RPC中）不小於 candidate 當前的任期號，那麼 candidate 會承認該 leader 的合法地位並回到 follower 狀態。
3.隨機超時
前面提高過，每個幾點與leader的心跳超時時間是不同的，這樣的好處在於避免瓜分票數的情況存在，能快速的進行leader選舉。如果各個節點的超時時間都是一樣的，就容易出現瓜分票數的情況存在，每個節點都沒有獲得超過一半的投票，就會開啟下一輪的選舉，選舉時間就會很長。使用隨機超時機制，正常情況下，一個時間段里只有一個節點發起投票請求。
下圖是整個集群中服務角色變化的流程圖。
Leader選舉出來之後為客戶端提供服務，將接受到的指令作為一個新的日誌項追加到日誌中去，然後並行的發起 AppendEntries RPC 給其他的伺服器，讓它們復制該日誌項。當該日誌項被安全地復制（過半的節點已復制完成），leader 會應用該日誌項到它的狀態機中（狀態機執行該指令）然後把執行的結果返回給客戶端。如果 follower 崩潰或者運行緩慢，或者網路丟包，領導人會不斷地重試 AppendEntries RPC（即使已經回復了客戶端）直到所有的 follower 最終都存儲了所有的日誌。
上圖展示了日誌的格式，一個日誌項包含三部分
Leader通過 AppendEntries RPC 將日誌復制到其他節點。
AppendEntries RPC：
接收者實現：
上訴是AppendEntries RPC的參數的接受流程。term與leaderId不用介紹很簡單，而prevLogIndex、prevLogTerm的作用是日誌的一致性檢測，如果 follower 在它的日誌中找不到包含相同索引位置和任期號的條目，那麼他就會拒絕該新的日誌條目。一致性檢查就像一個歸納步驟：一開始空的日誌狀態肯定是滿足 Log Matching Property（日誌匹配特性） 的，然後一致性檢查保證了日誌擴展時的日誌匹配特性。因此，每當 AppendEntries RPC 返回成功時，leader 就知道 follower 的日誌一定和自己相同（從第一個日誌條目到最新條目）。
正常操作期間，leader 和 follower 的日誌保持一致，所以 AppendEntries RPC 的一致性檢查從來不會失敗。然而，leader 崩潰的情況會使日誌處於不一致的狀態（老的 leader 可能還沒有完全復制它日誌里的所有條目）。如下情況：
在 Raft 演算法中，leader 通過強制 follower 復制它的日誌來解決不一致的問題。這意味著 follower 中跟 leader 沖突的日誌條目會被 leader 的日誌條目覆蓋。
Leader 針對每一個 follower 都維護了一個 nextIndex ，表示 leader 要發送給 follower 的下一個日誌條目的索引。當選出一個新 leader 時，該 leader 將所有 nextIndex 的值都初始化為自己最後一個日誌條目的 index 加1。如果 follower 的日誌和 leader 的不一致，那麼下一次 AppendEntries RPC 中的一致性檢查就會失敗。在被 follower 拒絕之後，leaer 就會減小 nextIndex 值並重試 AppendEntries RPC 。最終 nextIndex 會在某個位置使得 leader 和 follower 的日誌達成一致。此時，AppendEntries RPC 就會成功，將 follower 中跟 leader 沖突的日誌條目全部刪除然後追加 leader 中的日誌條目（如果有需要追加的日誌條目的話）。一旦 AppendEntries RPC 成功，follower 的日誌就和 leader 一致，並且在該任期接下來的時間里保持一致。
本機簡單介紹了raft 的leader選舉和日誌復制，當然raft還有其他的特性本文並沒有介紹，推薦去看raft的論文，完整的了解raft。
我之前 ZAB協議 的文章分析了zookeeper的zab協議，這里對比一下兩者的異同。
最後 https://raft.github.io 這個網址詳細介紹了raft協議。
https://time.geekbang.org/column/intro/279
https://raft.github.io/
https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md