區塊鏈poa演算法

『壹』 區塊鏈共識演算法——（二）PoS共識（Proof of Stake）

2011 年 7 月, 一 位 名 為 Quantum Mechanic 的 數 字 貨 幣 愛 好 者 在 比 特 幣 論 壇 首次提出了權益證明 PoS 共識演算法. 隨後, Sunny King 在 2012 年 8 月發布的點點幣 (Peercoin, PPC) 中首次實現. PoS 由 系統中具有最高權益而非最高算力的節點獲得記賬 權, 其中權益體現為節點對特定數量貨幣的所有權, 稱為幣齡或幣天數 (Coin days)

PoS是考慮到PoW的最大缺陷：浪費資源而提出的，簡單來說就是 誰的權益大，誰說了算 。

PoS共識機制（Proof of Stake 權益證明）通過權益記賬的方式，解決效率低下、資源浪費、節點一致性等問題。

各個節點需要滿足一定的條件（如抵押一定的代幣）才能成為驗證節點（權益提高），系統通過演算法在其中選擇一部分作為出塊節點（礦工），每隔一段時間重新選擇，演算法會保證完全隨機，不可被操控。只有出塊節點才能進行數據處理，爭奪記賬權。

權益主要由權益因子決定，可以是持幣數量，也可以是幣齡及兩者的結合。

以太坊在之後很有可能會改用PoS進行共識，其更加符合以太坊高效率的特點。

『貳』 環保鏈gc為什麼大漲

以慈善為由，嚴格的進入資格，虛擬的雲礦機，大量售賣。
在5月30號，環保鏈GC在新加坡的新交所開盤交易，起步價1usut，迅速拉升至32usdt，接著就一直在5usdt左右徘徊至今。總交易量四十多萬。今年五月，經過全員投票決定，又登上了「星交所」，上線交易開盤價為1USDT，一個月來得到了幣友們的廣泛共識，價格逐漸漲高，五月底漲到100多元人民幣一枚。
GREENCHAIN基於POA（ProofofAuthority）演算法，之所以制定為POA演算法，是因為它可以更快地確認交易，通過區塊鏈傳輸更多數據，為未來相關應用提供更好的踐和使用。編碼基於POA（ProofofAuthority）演算法，並兼容非常著名且穩定的區塊鏈以太坊（POW演算法和POS演算法），這將使環保鏈能夠現多鏈多幣種傳輸，具有更大的擴展空間。

『叄』 POA(Proof of Activity)區塊鏈共識演算法

POA(Proof of Activity)演算法是一個區塊鏈的共識演算法，基本原理是結合POW(Proof of work)和POS(Proof of stake)演算法的特點進行工作，POW演算法和POS演算法的具體內容可以參考：

POW演算法 ： https://www.jianshu.com/p/b23cbafbbad2
POS演算法 ： https://blog.csdn.net/wgwgnihao/article/details/80635162

POA演算法相比於其他演算法可以改進網路拓撲，維持在線節點比例，需求更少的交易費同時減少共識演算法過程中的能量損耗。
POA演算法需求的網路中同樣包含兩類節點，礦工和普通參與者，其中普通參與者不一定一直保持在線。POA演算法首先由礦工構造區塊頭，由塊頭選出N個幣，這N個幣的所有者參與後續的校驗和生成塊的過程。
從這里可以看到POA演算法不僅與算力有關，後續的N個參與者的選舉則完全由參與者在網路中所擁有的幣的總數量決定。擁有越多幣的參與者越有機會被選為N個後續的參與者。而後續N個參與者參與的必要條件是這N個參與者必須在線，這也是POA命名的由來，POA演算法的維護取決於網路中的活躍節點(Active)。

POA演算法的一個理想的基本流程是，類似於POW協議，礦工構造出一個符合難度要求的塊頭，通過礦工得到的塊頭計算衍生出N個幣的編號，從區塊鏈中追溯可以得到這幾個幣目前所述的參與者。礦工將這個塊頭發送給這N個參與者，其中前N-1個參與者對這個塊進行校驗和簽名，最後第N個參與者校驗並將交易加入到該塊中，將這個區塊發布出去，即完成一個區塊的出塊。
一個理想過程如下圖所示：

在實際運行中，無法保證網路上所有參與者都在線，而不在線的參與者則無法進行校驗和簽名，這個無法被校驗和簽名的塊頭則會被廢棄。
即在實際運行中，應該是一個礦工構造出塊頭後廣播給各個參與者簽名，同時繼續重新構造新的塊頭，以免上一個塊頭衍生的N個參與者存在有某一個沒有在線，而導致塊頭被廢棄。
因此，在這種情況下，一個塊是否被確認不僅與礦工的計算能力有關同時也與網路上的在線比例有關。
與純POW相比，在與比特幣(POW)同樣10分鍾出一個塊的情況下，POA由於會有參與者不在線而產生的損耗，因此，10分鍾內礦工可以構造的塊的數量會更多，即塊頭的難度限制會降低，那麼礦工在挖礦過程中會造成的能量損耗也會降低。
與純POS相比，可以看到POA的出塊流程並不會將構造區塊過程中的相關信息上鏈，可以明顯減少區塊鏈上用於維護協議產生的冗餘信息的量。

本節對上訴協議中一些參數設置進行分析

在礦工構造出塊頭後對塊頭進行校驗和區塊構造的N個參與者的數量選定比較類似於比特幣中每一個塊的出塊時間的選取。比特幣中選擇了10分鍾作為每一個塊的期望出塊時間並通過動態調節難度來適應。
這里N的取值同樣可以選擇選定值或者動態調節。動態調節需要更加復雜的協議內容，同時可能會帶來區塊鏈的數據膨脹，而復雜的協議也增加了攻擊者攻擊的可能性。另外暫時沒有辦法證明動態調節可以帶來什麼好處。靜態調節在後續的分析(4 安全分析)中可以得到N=3的取值是比較合適的。

從上面的描述可以看到，構造新的區塊的除了礦工還有從塊頭中衍生出來的N個幣所有者。在構造出一個新的區塊後，這些參與者同樣應該收到一定的激勵，以維持參與者保持在線狀態。
礦工與參與者之間的非配比例與參與者的在線狀態相關。給予參與者的激勵與參與者保持在線狀態的熱情密切相關，越多參與者保持在線狀態，能更好地維持網路的穩定。因此，可以在網路上在線參與者不夠多的時候，提高參與者得到的激勵分成比例，從而激發更多的參與者上線。
如何確定當前參與者的在線情況呢？可以最後第N個參與者構造區塊時，將構造出來但是被廢棄的塊頭加入到區塊中，如果被丟棄的塊頭數量過多，說明在線人數過低，應當調節分成比例。
同時最後第N個參與者與其他參與者的分成同樣需要考慮，第N個參與者需要將交易加入區塊中，即需要維護UTXO池，同時第N個參與者還需要將被丟棄的塊頭加入新構建的區塊中。
為了激勵其將廢棄區塊頭加入新構建的區塊中，可以按照加入的區塊頭，適當增加一點小的激勵。雖然加入更多的區塊頭，可以在下一輪的時候增加分成的比例，應當足夠激勵參與者往區塊中加入未使用的塊頭了(這里參與者不可能為了增加分成而更多地加入區塊頭，每一個區塊頭都意味著一位礦工的工作量)。
一個參與者如果沒有維護UTXO池則無法構造區塊，但是可以參與前N-1個的簽名，因此為了激勵參與者維護UTXO池，作為最後一個構造區塊的參與者，必須給予更多的激勵，比如是其他參與者的兩倍。

從3.2的描述中可以知道一個用戶必須在線且維護UTXO池才可能盡可能地獲得利益。這種機制勢必會導致一些用戶將自己的賬戶託管給一個中心化的機構。這個機構一直保持在線，並為用戶維護其賬戶，在被選為構造區塊的參與者時參與區塊的構建並獲取利益。最後該機構將收益按照某種形式進行分成。
上面說到參與者必須用自己的密鑰進行簽名，而託管給某個機構後，這個機構在可以用這個密鑰簽名構造區塊的同時，也有可能使用這個密鑰消費用戶的財產。這里可以採用一種有限花銷的密鑰，這個密鑰有兩個功能，一個是將賬戶中的部分財產消費出去，另一個是將所有財產轉移到一個指定賬戶。在託管的時候可以使用這個密鑰，在被通知部分財產被花費後可以立即將所有財產轉移到自己的另一個賬戶下，以保證財產的安全。

從上面的分析可以看到，POA的安全性與攻擊者所擁有的算力和攻擊者所擁有的股權有關。假設攻擊者擁有的在線股權佔比為 ，則攻擊者的算力需要達到其他所有算力的 倍才能達成分叉。假設攻擊者股權總佔比為 ，網路中誠實用戶的在線比例為 ，則攻擊者的算力需要達到其他所有算力的 倍才能達成攻擊。
攻擊的分析表格如下：

從上文的分析可以看到，POA演算法相比於其他演算法可以改進網路拓撲，維持在線節點比例，需求更少的交易費同時減少共識演算法過程中的能量損耗。同時，PoA協議的攻擊成本要高於比特幣的純PoW協議。

參考文獻：Proof of Activity: Extending Bitcoin』s Proof of Work via Proof of Stake

『肆』 Codex Network經濟模型篇 （PoA、PoV、CPoA）

什麼是Proof of Asset(PoA)模型？

區別於常見的POW/POS共識治理機制， PoA 是以資產作為算力單位的一種共識治理機制，其中A代表Asset,即資產的含義。

POA的含義

Proof of Asset 指代的是， 所有參與方以所持有的系統認可的資產為算力單位進行競爭 。 跨鏈挖礦指跨鏈用戶通過充值，映射或鎖倉等方式進入的各類鏈外資產，比如 BTC 、ETH 等，將自動根據該跨鏈資產換算成挖礦算力。由於每個跨鏈資產都有不同的跨鏈資產算力換算，跨鏈資產算力換算的參數，是各跨鏈資產通過各資產當日價格平均數進行換算，以保障不同資產之間算力換算的平衡和公平。同時該參數同時可以社區投票在一定范圍內進行調整，給與Codex系統一定的操作空間，作為宏觀調整的工具。

作為資產挖礦的一種，在 Codex 生態系統中， 通過跨鏈充值、映射或鎖倉的的資產 ，類似BTC、ETH等，在現實生活中，BTC、ETH的產出，是以實際礦機消耗電能的方式形成的。PoA治理機制的關鍵一環，是我們洞悉資產的本質之後，我們可以將BTC、ETH等資產，等價的當做礦機資源，從而引申出「 資產挖礦 」的概念。

舉個栗子

以BTC為例，既然該資產是由算力挖礦產出的，那麼一定數量的BTC本質上對應了一定數量的算力，那麼在Codex的生態系統中，通過對該算力的空間平移，我們實現了算力在另一條公鏈上的算力移植，經過換算後，開啟了在Codex上的算力挖礦行為。

POA解決的問題

Proof of Asset 的模式解決 Codex 整個生命周期中外部資產鎖定的問題 ，作為一條專注於DeFi應用的金融公鏈，錨定的主流資產是該公鏈生存的基石。因此任何時刻對於願意將資產鎖定在Codex系統中的用戶，都應當給與適量的 CDX 獎勵。同時通過跨鏈的方式引入了外部因子，因此Codex在發展過程中，將會持續受到外部因子的影響和條件，如同PoW的公鏈一般，會進行自我調節和多方競爭，這更有利於Codex的長期發展。

什麼是Proof of Vote（PoV）模型？

在 Codex的生態系統中 ， 生態建設者秉持著產出公平，選舉平等，社區共建的原則 ，而PoV共識機制，正是為了解決其選舉平等而誕生的機制。

POV的含義

Proof of Vote 指用戶利用所 持有的CDX參與系統的選舉，並獲得獎勵的過程 。這個過程類似於Proof ov Stake（PoS）過程。它通過一票一投的方式投票給某些節點， 以獲取到CDX見證人節點的投票分紅和節點收益。

生態系統節點

Codex生態系統擁有二種節點，分別是 見證人節點 和 信託節點 。而與PoV機制密切相關的，則是見證人節點。

見證人節點是Codex系統運行的節點，主要職責是維護系統安全、正常請求處理、線上治理等工作。 見證人節點需要質押2萬枚CDX才能建立，成為見證人節點擁有20%的PoV節點收益，這部分收益分為二部分，其中5%恆定為節點挖礦收益，剩下15%為用戶投票分紅收益。

信託節點主要職責是守護Codex跨鏈中繼橋和跨鏈網關充值的用戶資產 ，信託節點不參與Codex鏈上治理，Codex每個中繼橋擁有3-7名不同數量的信託節點。伴隨著跨鏈鏈接的主鏈增加，信託節點的數量也將逐步增加。 信託節點擁有系統單獨分配的收益權 。

POV解決的問題

Proof of Vote的模式解決了Codex的系統維護和安全問題 ，並且後續可以通過內部與外部算力比例來動態調整收益率，可以促進資產挖礦和節點挖礦的動態競爭，實現內部因子自我調整和競爭。

什麼是Conditioned Proof of Asset（CPoA）模型？

見證人節點擁有Codex的系統的治理權，所以要有效的保護Codex系統節點之間的有效競爭。Codex作為一個PoS的系統， 其安全性依託於用戶抵押的CDX，抵押的CDX越多，系統越安全 。

CPoA的含義

Conditioned Proof of Asset 是指， 外部資產持有者在參與外部資產挖礦的過程中，並不能獲得資產挖礦過程中全部資產挖礦算力產出 。會有一個額外質押CDX判定條件來進行判定，外部資產挖礦者需要根據自己持有的外部數質押等量的CDX，才可以獲得對應的資產挖礦算力產出。

Codex作為一個建立在Cosmos生態系統內部的跨鏈DeFi公鏈，天然的需要鏈接其他的優質資產，在解決了這個問題之後， 就需要去對自身系統內部的維護及安全性去做一些措施和激勵，去增設更多的有效競爭，系統就會越安全 。讓原生資產與跨鏈資產、跨鏈資產與跨鏈資產之間去競爭性的共同參與資產挖礦，多方之間是一個相互依存又相互競爭的關系。

在啟動資產挖礦後，資產挖礦採用條件挖礦。每個外部資產挖礦的1個BTC見證人節點需要質押500枚CDX，每個ETH資產挖礦見證人節點需要質押10枚CDX。 滿足條件即為完全挖礦，可以獲得全區塊獎勵的20% 。對於未滿足條件挖礦的見證人節點，可以按照BTC和CDX的質押比例，獲得全區塊鏈獎勵的20%乘以質押系數的收益，剩餘收益中的50%累計到下一個出塊獎勵中，50%累計到Codex基金會中，用於Codex生態發展激勵、DeFi激勵和預防黑天鵝等問題。

CPoA的作用

Conditioned Proof of Asset 的模式會讓 資產挖礦參與者、見證人節點和Codex基金會等參與方產生正向商業博弈 ，使整個系統始終會有一個較為主力的臨時商業既得利益者（ 這個既得利益者會隨著時間、價格、資產挖礦算力等變數條件而變化 ）去無形推動整個生態。

『伍』 區塊鏈中PoW是指什麼

是指工作量證明機制，是區塊鏈的一種共識機制。指在區塊鏈系統中，根據每個節點在運算的過程中所做出的貢獻來確定許可權的一種演算法。工作量證明機制是現在區塊鏈應用最為廣泛的一種共識機制。共識機制是區塊鏈系統中很重要的一部分，如果出現問題，那麼整個系統都會出問題，在區塊鏈開發中是必須要注意的。這是之前我一個在煊凌科技上班的人告訴我的，他雖然只是裡面的銷售，但是對區塊鏈的了解也比大部分人要全面。

『陸』 poa共識機制

我在使用puppeth工具創建PoA共識機制的時候，這里提示，要提供至少一個賬戶，請問，這里的賬戶作用是什麼？ 是指挖礦的賬戶嗎？

答：poa是授權挖礦機制，這個設的是允許哪些賬戶挖礦，沒有設置的賬戶是不能挖礦的。後期可以通過投票機制修改授權挖礦賬戶。

鏈客區塊鏈技術問答社區

『柒』 區塊鏈的共識機制

所謂「共識機制」，是通過特殊節點的投票，在很短的時間內完成對交易的驗證和確認；對一筆交易，如果利益不相乾的若干個節點能夠達成共識，我們就可以認為全網對此也能夠達成共識。北京木奇移動技術有限公司，專業的區塊鏈外包開發公司，歡迎洽談合作。下面我們將一下區塊鏈的幾種共識機制，希望對大家了解區塊鏈基礎技術有幫助。

因為區塊鏈技術的發展， 大家對共識機制這個詞也不再陌生，隨著技術發展，各種創新的共識機制也在發展。

POW工作量證明

比特幣就是使用PoW工作量證明機制，到後來的以太坊都是PoW的共識機制。Pow相當於算出很難的數學難題，就是計算出新區塊的hash值，而且計算的難度會每一段時間就會調整。PoW雖然是大家比較認可的共識機制,計算會消耗大量的能源,還有可能會污染環境。

POS權益證明

通過持有Token的數量和時長來決定獲得記賬權的機率。相比POW，POS避免了挖礦造成大量的資源浪費，縮短了各個節點之間達成共識的時間，網路環境好的話可實現毫秒級，對節點性能要求低。

但POS的缺點同樣明顯，持有Token多的節點更有機會獲得記賬權，這將導致「馬太效應」，富者越富，破壞了區塊鏈的去中心化。

DPOS權益證明

DPOS委託權益證明與POS原理相同，其主要區別在於，DPOS的Token持有者可以投票選舉代理人作為超級節點，負責在網路上生產區塊並維護共識規則。如果這些節點未能履行職責，將投票選出新的節點。同樣的弊端也是傾向於中心化。

POA權威證明

POA節點之間無需進行通信即可達成共識，因此效率極高。並且它也能很好地對抗算力攻擊，安全性較高。但是POA需要一個集中的權威節點來驗證身份，這就意味著它會損害區塊鏈的去中心化，這也是在去中心化和提高效率之間的妥協。

『捌』 區塊鏈技術的六大核心演算法

區塊鏈技術的六大核心演算法
區塊鏈核心演算法一：拜占庭協定
拜占庭的故事大概是這么說的：拜占庭帝國擁有巨大的財富，周圍10個鄰邦垂誕已久，但拜占庭高牆聳立，固若金湯，沒有一個單獨的鄰邦能夠成功入侵。任何單個鄰邦入侵的都會失敗，同時也有可能自身被其他9個鄰邦入侵。拜占庭帝國防禦能力如此之強，至少要有十個鄰邦中的一半以上同時進攻，才有可能攻破。然而，如果其中的一個或者幾個鄰邦本身答應好一起進攻，但實際過程出現背叛，那麼入侵者可能都會被殲滅。於是每一方都小心行事，不敢輕易相信鄰國。這就是拜占庭將軍問題。
在這個分布式網路里：每個將軍都有一份實時與其他將軍同步的消息賬本。賬本里有每個將軍的簽名都是可以驗證身份的。如果有哪些消息不一致，可以知道消息不一致的是哪些將軍。盡管有消息不一致的，只要超過半數同意進攻，少數服從多數，共識達成。
由此，在一個分布式的系統中，盡管有壞人，壞人可以做任意事情(不受protocol限制)，比如不響應、發送錯誤信息、對不同節點發送不同決定、不同錯誤節點聯合起來干壞事等等。但是，只要大多數人是好人，就完全有可能去中心化地實現共識
區塊鏈核心演算法二：非對稱加密技術
在上述拜占庭協定中，如果10個將軍中的幾個同時發起消息，勢必會造成系統的混亂，造成各說各的攻擊時間方案，行動難以一致。誰都可以發起進攻的信息，但由誰來發出呢?其實這只要加入一個成本就可以了，即：一段時間內只有一個節點可以傳播信息。當某個節點發出統一進攻的消息後，各個節點收到發起者的消息必須簽名蓋章，確認各自的身份。
在如今看來，非對稱加密技術完全可以解決這個簽名問題。非對稱加密演算法的加密和解密使用不同的兩個密鑰.這兩個密鑰就是我們經常聽到的」公鑰」和」私鑰」。公鑰和私鑰一般成對出現, 如果消息使用公鑰加密,那麼需要該公鑰對應的私鑰才能解密; 同樣，如果消息使用私鑰加密,那麼需要該私鑰對應的公鑰才能解密。
區塊鏈核心演算法三：容錯問題
我們假設在此網路中，消息可能會丟失、損壞、延遲、重復發送，並且接受的順序與發送的順序不一致。此外，節點的行為可以是任意的：可以隨時加入、退出網路，可以丟棄消息、偽造消息、停止工作等，還可能發生各種人為或非人為的故障。我們的演算法對由共識節點組成的共識系統，提供的容錯能力，這種容錯能力同時包含安全性和可用性，並適用於任何網路環境。
區塊鏈核心演算法四：Paxos 演算法(一致性演算法)
Paxos演算法解決的問題是一個分布式系統如何就某個值(決議)達成一致。一個典型的場景是，在一個分布式資料庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那麼他們最後能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個「一致性演算法」以保證每個節點看到的指令一致。一個通用的一致性演算法可以應用在許多場景中，是分布式計算中的重要問題。節點通信存在兩種模型：共享內存和消息傳遞。Paxos演算法就是一種基於消息傳遞模型的一致性演算法。
區塊鏈核心演算法五：共識機制
區塊鏈共識演算法主要是工作量證明和權益證明。拿比特幣來說，其實從技術角度來看可以把PoW看做重復使用的Hashcash，生成工作量證明在概率上來說是一個隨機的過程。開采新的機密貨幣，生成區塊時，必須得到所有參與者的同意，那礦工必須得到區塊中所有數據的PoW工作證明。與此同時礦工還要時時觀察調整這項工作的難度，因為對網路要求是平均每10分鍾生成一個區塊。
區塊鏈核心演算法六：分布式存儲
分布式存儲是一種數據存儲技術，通過網路使用每台機器上的磁碟空間，並將這些分散的存儲資源構成一個虛擬的存儲設備，數據分散的存儲在網路中的各個角落。所以，分布式存儲技術並不是每台電腦都存放完整的數據，而是把數據切割後存放在不同的電腦里。就像存放100個雞蛋，不是放在同一個籃子里，而是分開放在不同的地方，加起來的總和是100個。

『玖』 區塊鏈 --- 共識演算法

PoW演算法是一種防止分布式服務資源被濫用、拒絕服務攻擊的機制。它要求節點進行適量消耗時間和資源的復雜運算，並且其運算結果能被其他節點快速驗算，以耗用時間、能源做擔保，以確保服務與資源被真正的需求所使用。

PoW演算法中最基本的技術原理是使用哈希演算法。假設求哈希值Hash(r)，若原始數據為r（raw），則運算結果為R（Result）。

R = Hash(r)

哈希函數Hash()的特性是，對於任意輸入值r，得出結果R，並且無法從R反推回r。當輸入的原始數據r變動1比特時，其結果R值完全改變。在比特幣的PoW演算法中，引入演算法難度d和隨機值n，得到以下公式：

Rd = Hash(r+n)

該公式要求在填入隨機值n的情況下，計算結果Rd的前d位元組必須為0。由於哈希函數結果的未知性，每個礦工都要做大量運算之後，才能得出正確結果，而算出結果廣播給全網之後，其他節點只需要進行一次哈希運算即可校驗。PoW演算法就是採用這種方式讓計算消耗資源，而校驗僅需一次。

 

PoS演算法要求節點驗證者必須質押一定的資金才有挖礦打包資格，並且區域鏈系統在選定打包節點時使用隨機的方式，當節點質押的資金越多時，其被選定打包區塊的概率越大。

POS模式下，每個幣每天產生1幣齡，比如你持有100個幣，總共持有了30天，那麼，此時你的幣齡就為3000。這個時候，如果你驗證了一個POS區塊，你的幣齡就會被清空為0，同時從區塊中獲得相對應的數字貨幣利息。

節點通過PoS演算法出塊的過程如下：普通的節點要成為出塊節點，首先要進行資產的質押，當輪到自己出塊時，打包區塊，然後向全網廣播，其他驗證節點將會校驗區塊的合法性。

 

DPoS演算法和PoS演算法相似，也採用股份和權益質押。

但不同的是，DPoS演算法採用委託質押的方式，類似於用全民選舉代表的方式選出N個超級節點記賬出塊。

選民把自己的選票投給某個節點，如果某個節點當選記賬節點，那麼該記賬節點往往在獲取出塊獎勵後，可以採用任意方式來回報自己的選民。

這N個記賬節點將輪流出塊，並且節點之間相互監督，如果其作惡，那麼會被扣除質押金。

通過信任少量的誠信節點，可以去除區塊簽名過程中不必要的步驟，提高了交易的速度。
 

拜占庭問題：

拜占庭是古代東羅馬帝國的首都，為了防禦在每塊封地都駐扎一支由單個將軍帶領的軍隊，將軍之間只能靠信差傳遞消息。在戰爭時，所有將軍必須達成共識，決定是否共同開戰。

但是，在軍隊內可能有叛徒，這些人將影響將軍們達成共識。拜占庭將軍問題是指在已知有將軍是叛徒的情況下，剩餘的將軍如何達成一致決策的問題。

BFT：

BFT即拜占庭容錯，拜占庭容錯技術是一類分布式計算領域的容錯技術。拜占庭假設是對現實世界的模型化，由於硬體錯誤、網路擁塞或中斷以及遭到惡意攻擊等原因，計算機和網路可能出現不可預料的行為。拜占庭容錯技術被設計用來處理這些異常行為，並滿足所要解決的問題的規范要求。

拜占庭容錯系統 ：

發生故障的節點被稱為 拜占庭節點 ，而正常的節點即為 非拜占庭節點 。

假設分布式系統擁有n台節點，並假設整個系統拜占庭節點不超過m台（n ≥ 3m + 1），拜占庭容錯系統需要滿足如下兩個條件：

另外，拜占庭容錯系統需要達成如下兩個指標：

PBFT即實用拜占庭容錯演算法，解決了原始拜占庭容錯演算法效率不高的問題，演算法的時間復雜度是O(n^2)，使得在實際系統應用中可以解決拜占庭容錯問題
 

PBFT是一種狀態機副本復制演算法，所有的副本在一個視圖（view）輪換的過程中操作，主節點通過視圖編號以及節點數集合來確定，即：主節點 p = v mod |R|。v：視圖編號，|R|節點個數，p：主節點編號。

PBFT演算法的共識過程如下：客戶端（Client）發起消息請求（request），並廣播轉發至每一個副本節點（Replica），由其中一個主節點（Leader）發起提案消息pre-prepare，並廣播。其他節點獲取原始消息，在校驗完成後發送prepare消息。每個節點收到2f+1個prepare消息，即認為已經准備完畢，並發送commit消息。當節點收到2f+1個commit消息，客戶端收到f+1個相同的reply消息時，說明客戶端發起的請求已經達成全網共識。

具體流程如下 ：

客戶端c向主節點p發送<REQUEST, o, t, c>請求。o: 請求的具體操作，t: 請求時客戶端追加的時間戳，c：客戶端標識。REQUEST: 包含消息內容m，以及消息摘要d(m)。客戶端對請求進行簽名。

主節點收到客戶端的請求，需要進行以下交驗：

a. 客戶端請求消息簽名是否正確。

非法請求丟棄。正確請求，分配一個編號n，編號n主要用於對客戶端的請求進行排序。然後廣播一條<<PRE-PREPARE, v, n, d>, m>消息給其他副本節點。v：視圖編號，d客戶端消息摘要，m消息內容。<PRE-PREPARE, v, n, d>進行主節點簽名。n是要在某一個范圍區間內的[h, H]，具體原因參見 垃圾回收 章節。

副本節點i收到主節點的PRE-PREPARE消息，需要進行以下交驗：

a. 主節點PRE-PREPARE消息簽名是否正確。

b. 當前副本節點是否已經收到了一條在同一v下並且編號也是n，但是簽名不同的PRE-PREPARE信息。

c. d與m的摘要是否一致。

d. n是否在區間[h, H]內。

非法請求丟棄。正確請求，副本節點i向其他節點包括主節點發送一條<PREPARE, v, n, d, i>消息, v, n, d, m與上述PRE-PREPARE消息內容相同，i是當前副本節點編號。<PREPARE, v, n, d, i>進行副本節點i的簽名。記錄PRE-PREPARE和PREPARE消息到log中，用於View Change過程中恢復未完成的請求操作。

主節點和副本節點收到PREPARE消息，需要進行以下交驗：

a. 副本節點PREPARE消息簽名是否正確。

b. 當前副本節點是否已經收到了同一視圖v下的n。

c. n是否在區間[h, H]內。

d. d是否和當前已收到PRE-PPREPARE中的d相同

非法請求丟棄。如果副本節點i收到了2f+1個驗證通過的PREPARE消息，則向其他節點包括主節點發送一條<COMMIT, v, n, d, i>消息，v, n, d, i與上述PREPARE消息內容相同。<COMMIT, v, n, d, i>進行副本節點i的簽名。記錄COMMIT消息到日誌中，用於View Change過程中恢復未完成的請求操作。記錄其他副本節點發送的PREPARE消息到log中。

主節點和副本節點收到COMMIT消息，需要進行以下交驗：

a. 副本節點COMMIT消息簽名是否正確。

b. 當前副本節點是否已經收到了同一視圖v下的n。

c. d與m的摘要是否一致。

d. n是否在區間[h, H]內。

非法請求丟棄。如果副本節點i收到了2f+1個驗證通過的COMMIT消息，說明當前網路中的大部分節點已經達成共識，運行客戶端的請求操作o，並返回<REPLY, v, t, c, i, r>給客戶端，r：是請求操作結果，客戶端如果收到f+1個相同的REPLY消息，說明客戶端發起的請求已經達成全網共識，否則客戶端需要判斷是否重新發送請求給主節點。記錄其他副本節點發送的COMMIT消息到log中。
 

如果主節點作惡，它可能會給不同的請求編上相同的序號，或者不去分配序號，或者讓相鄰的序號不連續。備份節點應當有職責來主動檢查這些序號的合法性。

如果主節點掉線或者作惡不廣播客戶端的請求，客戶端設置超時機制，超時的話，向所有副本節點廣播請求消息。副本節點檢測出主節點作惡或者下線，發起View Change協議。

View Change協議 ：

副本節點向其他節點廣播<VIEW-CHANGE, v+1, n, C , P , i>消息。n是最新的stable checkpoint的編號， C 是 2f+1驗證過的CheckPoint消息集合， P 是當前副本節點未完成的請求的PRE-PREPARE和PREPARE消息集合。

當主節點p = v + 1 mod |R|收到 2f 個有效的VIEW-CHANGE消息後，向其他節點廣播<NEW-VIEW, v+1, V , O >消息。 V 是有效的VIEW-CHANGE消息集合。 O 是主節點重新發起的未經完成的PRE-PREPARE消息集合。PRE-PREPARE消息集合的選取規則：

副本節點收到主節點的NEW-VIEW消息，驗證有效性，有效的話，進入v+1狀態，並且開始 O 中的PRE-PREPARE消息處理流程。
 

在上述演算法流程中，為了確保在View Change的過程中，能夠恢復先前的請求，每一個副本節點都記錄一些消息到本地的log中，當執行請求後副本節點需要把之前該請求的記錄消息清除掉。

最簡單的做法是在Reply消息後，再執行一次當前狀態的共識同步，這樣做的成本比較高，因此可以在執行完多條請求K（例如：100條）後執行一次狀態同步。這個狀態同步消息就是CheckPoint消息。

副本節點i發送<CheckPoint, n, d, i>給其他節點，n是當前節點所保留的最後一個視圖請求編號，d是對當前狀態的一個摘要，該CheckPoint消息記錄到log中。如果副本節點i收到了2f+1個驗證過的CheckPoint消息，則清除先前日誌中的消息，並以n作為當前一個stable checkpoint。

這是理想情況，實際上當副本節點i向其他節點發出CheckPoint消息後，其他節點還沒有完成K條請求，所以不會立即對i的請求作出響應，它還會按照自己的節奏，向前行進，但此時發出的CheckPoint並未形成stable。

為了防止i的處理請求過快，設置一個上文提到的 高低水位區間[h, H] 來解決這個問題。低水位h等於上一個stable checkpoint的編號，高水位H = h + L，其中L是我們指定的數值，等於checkpoint周期處理請求數K的整數倍，可以設置為L = 2K。當副本節點i處理請求超過高水位H時，此時就會停止腳步，等待stable checkpoint發生變化，再繼續前進。
 

在區塊鏈場景中，一般適合於對強一致性有要求的私有鏈和聯盟鏈場景。例如，在IBM主導的區塊鏈超級賬本項目中，PBFT是一個可選的共識協議。在Hyperledger的Fabric項目中，共識模塊被設計成可插拔的模塊，支持像PBFT、Raft等共識演算法。
 

 

Raft基於領導者驅動的共識模型，其中將選舉一位傑出的領導者(Leader)，而該Leader將完全負責管理集群，Leader負責管理Raft集群的所有節點之間的復制日誌。
 

下圖中，將在啟動過程中選擇集群的Leader（S1），並為來自客戶端的所有命令/請求提供服務。 Raft集群中的所有節點都維護一個分布式日誌（復制日誌）以存儲和提交由客戶端發出的命令（日誌條目）。 Leader接受來自客戶端的日誌條目，並在Raft集群中的所有關注者（S2，S3，S4，S5）之間復制它們。

在Raft集群中，需要滿足最少數量的節點才能提供預期的級別共識保證， 這也稱為法定人數。 在Raft集群中執行操作所需的最少投票數為 (N / 2 +1) ，其中N是組中成員總數，即 投票至少超過一半 ，這也就是為什麼集群節點通常為奇數的原因。 因此，在上面的示例中，我們至少需要3個節點才能具有共識保證。

如果法定仲裁節點由於任何原因不可用，也就是投票沒有超過半數，則此次協商沒有達成一致，並且無法提交新日誌。

 

數據存儲：Tidb/TiKV

日誌：阿里巴巴的 DLedger

服務發現：Consul& etcd

集群調度：HashiCorp Nomad
 

只能容納故障節點(CFT)，不容納作惡節點

順序投票，只能串列apply，因此高並發場景下性能差
 

Raft通過解決圍繞Leader選舉的三個主要子問題，管理分布式日誌和演算法的安全性功能來解決分布式共識問題。

當我們啟動一個新的Raft集群或某個領導者不可用時，將通過集群中所有成員節點之間協商來選舉一個新的領導者。 因此，在給定的實例中，Raft集群的節點可以處於以下任何狀態: 追隨者(Follower)，候選人(Candidate)或領導者(Leader)。

系統剛開始啟動的時候，所有節點都是follower，在一段時間內如果它們沒有收到Leader的心跳信號，follower就會轉化為Candidate；

如果某個Candidate節點收到大多數節點的票，則這個Candidate就可以轉化為Leader，其餘的Candidate節點都會回到Follower狀態；

一旦一個Leader發現系統中存在一個Leader節點比自己擁有更高的任期(Term)，它就會轉換為Follower。

Raft使用基於心跳的RPC機制來檢測何時開始新的選舉。 在正常期間， Leader 會定期向所有可用的 Follower 發送心跳消息（實際中可能把日誌和心跳一起發過去）。 因此，其他節點以 Follower 狀態啟動，只要它從當前 Leader 那裡收到周期性的心跳，就一直保持在 Follower 狀態。

當 Follower 達到其超時時間時，它將通過以下方式啟動選舉程序：

根據 Candidate 從集群中其他節點收到的響應，可以得出選舉的三個結果。

共識演算法的實現一般是基於復制狀態機（Replicated state machines），何為 復制狀態機 ：

簡單來說： 相同的初識狀態 + 相同的輸入 = 相同的結束狀態 。不同節點要以相同且確定性的函數來處理輸入，而不要引入一下不確定的值，比如本地時間等。使用replicated log是一個很不錯的注意，log具有持久化、保序的特點，是大多數分布式系統的基石。

有了Leader之後，客戶端所有並發的請求可以在Leader這邊形成一個有序的日誌（狀態）序列，以此來表示這些請求的先後處理順序。Leader然後將自己的日誌序列發送Follower，保持整個系統的全局一致性。注意並不是強一致性，而是 最終一致性 。

日誌由有序編號（log index）的日誌條目組成。每個日誌條目包含它被創建時的任期號（term），和日誌中包含的數據組成，日誌包含的數據可以為任何類型，從簡單類型到區塊鏈的區塊。每個日誌條目可以用[ term, index, data]序列對表示，其中term表示任期， index表示索引號，data表示日誌數據。

Leader 嘗試在集群中的大多數節點上執行復制命令。 如果復製成功，則將命令提交給集群，並將響應發送回客戶端。類似兩階段提交(2PC)，不過與2PC的區別在於，leader只需要超過一半節點同意（處於工作狀態）即可。

leader 、 follower 都可能crash，那麼 follower 維護的日誌與 leader 相比可能出現以下情況

當出現了leader與follower不一致的情況，leader強制follower復制自己的log， Leader會從後往前試 ，每次AppendEntries失敗後嘗試前一個日誌條目（遞減nextIndex值）， 直到成功找到每個Follower的日誌一致位置點（基於上述的兩條保證），然後向後逐條覆蓋Followers在該位置之後的條目 。所以丟失的或者多出來的條目可能會持續多個任期。
 

要求候選人的日誌至少與其他節點一樣最新。如果不是，則跟隨者節點將不投票給候選者。

意味著每個提交的條目都必須存在於這些伺服器中的至少一個中。如果候選人的日誌至少與該多數日誌中的其他日誌一樣最新，則它將保存所有已提交的條目，避免了日誌回滾事件的發生。

即任一任期內最多一個leader被選出。這一點非常重要，在一個復制集中任何時刻只能有一個leader。系統中同時有多餘一個leader，被稱之為腦裂（brain split），這是非常嚴重的問題，會導致數據的覆蓋丟失。在raft中，兩點保證了這個屬性：

因此， 某一任期內一定只有一個leader 。
 

當集群中節點的狀態發生變化（集群配置發生變化）時，系統容易受到系統故障。 因此，為防止這種情況，Raft使用了一種稱為兩階段的方法來更改集群成員身份。 因此，在這種方法中，集群在實現新的成員身份配置之前首先更改為中間狀態（稱為聯合共識）。 聯合共識使系統即使在配置之間進行轉換時也可用於響應客戶端請求，它的主要目的是提升分布式系統的可用性。

『拾』 區塊鏈共識演算法——（四）PoA共識（Proof of Activity）

PoA共識（Proof of Activity）也稱為活動證明，其結合了PoW工作量證明與PoS權益證明的特點並進行了相應擴展，PoA共識具有更為復雜的記賬節點選取，同時有更為公平的獎勵機制。

PoA活動證明，主要的優勢是利用公平的激勵措施保證節點保持在線狀態，調動節點積極性，線上礦工即使不挖礦也有一定的概率獲取收益。大大提高了全網維護質量。

step1：每個礦工先利用自身算力通過工作量證明機制後得出nonce並生成一個空區塊頭，這個區塊頭除了沒有交易信息數據外其他數據與正常區塊一致。

step2：最先生成空區塊的節點廣播全網節點，全網節點接收到消息後，將此區塊的hash值與上一區塊的hash值進行拼接，然後加上n個固定後綴值進行再hash，最後得出n個值作為輸入，進入follow-the-satoshi程序，然後可輸出n個隨機權益持有者。

step3：前n-1個隨機權益持有者對空區塊進行簽名，第n個隨機權益持有者即為獲取到記賬權的節點，他將在空區塊的基礎上添加交易數據與簽名。

step4：第n個隨機權益持有者將打包好的區塊廣播全網，全網節點接收到區塊後進行驗證，驗證成功後上鏈。

step5：產生空區塊的礦工與第n個隨機權益持有者以及前n-1個已簽名的隨機權益持有者共享交易費獎勵。