15种区块链共识算法全面详解
1,摘要
本文盡可能列出所有主要的共識算法,評估各自的優劣之處。共識算法是區塊鏈的核心技術,本文會跟隨作者的理解,持續更新。如果讀者發現有所遺漏,或是存在錯誤,希望能通過評論指出。
2,區塊鏈共識算法
2.1 工作量證明(PoW,Proof of Work)
優點: 自2009年以來得到了廣泛測試,目前依然得到廣泛的使用。
不足:速度慢。耗能巨大,對環境不好。易受“規模經濟”(economies of scale)的影響。
使用者: Bitcoin、Ethereum、LiteCoin、Dogecoin等。
類型:有競爭共識(Competive consensus)。
解釋:PoW是是首個共識算法。它是由中本聰在他的論文中提出的,用于建立分布式無信任共識并識別“雙重支付”(double spend)問題。PoW并非一個新理念,但是中本聰將Pow與加密簽名、Merkle鏈和P2P網絡等已有理念結合,形成一種可用的分布式共識系統。加密貨幣是這樣系統的首個基礎和應用,因而獨具創新性。
在PoW的工作方式中,區塊鏈參與者(稱為“礦工”)要在區塊鏈中添加一塊交易,必須解決某種“復雜但是無用”的計算問題。
只要由礦工提交的工作有超過一半是值得信任的,那么Bitcoin就是安全的。
從某種角度來看,PoW有點像買彩票,只是概率高一點而已。
技術原理:
工作量證明最核心的技術原理是散列函數(哈希)。在比特幣中,PoW工作其實就是如何去計算一個區塊的目標哈希值問題,讓用戶進行大量的窮舉運算,同時得出這個哈希值還必須滿足一些必要條件,這個條件在區塊鏈中其實就是一個難度系數值,通過計算出的哈希值是否符合前面N位全是0,最終達成工作量證明。
舉個例子:
比如現在給出一個固定的字符串“Hello, blockchain”,現在要求計算的難題是將這個字符串與一個隨機數(Nonce)拼接起來,并通過SHA256哈希計算一個固定256位長度的哈希值,如果計算結果得到的前5位全是0,即認為滿足計算條件,同時得到的隨機數(Nonce)值證明為達成工作量證明的有效隨機數。
2.2 權益證明(PoS,Proof of Stake)
優點:節能、攻擊者代價更大、不易受“規模經濟”的影響。
不足:“無利害關系“(Nothing at stake)”攻擊問題。
使用者:Ethereum(即將推出)、Peercoin、Nxt。
類型:有競爭共識。
解釋:
類似于財產儲存在銀行,這種模式會根據你持有數字貨幣的量和時間,分配給你相應的利息。
簡單來說,就是一個根據你持有貨幣的量和時間,給你發利息的一個制度,在股權證明POS模式下,有一個名詞叫幣齡,每個幣每天產生1幣齡,比如你持有100個幣,總共持有了30天,那么,此時你的幣齡就為3000,這個時候,如果你發現了一個POS區塊,你的幣齡就會被清空為0。你每被清空365幣齡,你將會從區塊中獲得0.05個幣的利息(假定利息可理解為年利率5%),那么在這個案例中,利息 = 3000 * 5% / 365 = 0.41個幣,這下就很有意思了,持幣有利息。以太坊就是采用POS共識算法。
從某種角度來看,PoS有點像銀行存款,你持有的時間越長,本金越大,你得到的利息會越多。
技術原理:
每個曠工都有出塊(即挖礦)的權力,只要出塊成功,就有系統給出的獎勵,這里不需要通過復雜的計算來挖礦,問題只在于誰來出塊,股權越大,出塊的概率就越大,反之,則相反。POS有很多變種,股權可以是持有幣的數量,或者支付的數量等等。
go的demo代碼實現:
package mainimport ("time""strconv""crypto/sha256""math/rand""fmt""encoding/hex" )//實現pos挖礦的原理type Block struct {Index intData string //PreHash stringHash stringTimestamp string//記錄挖礦節點Validator *Node}func genesisBlock() Block {var genesBlock = Block{0, "Genesis block","","",time.Now().String(),&Node{0, 0, "dd"}}genesBlock.Hash = hex.EncodeToString(BlockHash(&genesBlock))return genesBlock }func BlockHash(block *Block) []byte {record := strconv.Itoa(block.Index) + block.Data + block.PreHash + block.Timestamp + block.Validator.Addressh := sha256.New()h.Write([]byte(record))hashed := h.Sum(nil)return hashed }//創建全節點類型 type Node struct {Tokens int //持幣數量Days int //持幣時間Address string //地址 }//創建5個節點 //算法的實現要滿足 持幣越多的節點越容易出塊 var nodes = make([]Node, 5) //存放節點的地址 var addr = make([]*Node, 15)func InitNodes() {nodes[0] = Node{1, 1, "0x12341"}nodes[1] = Node{2, 1, "0x12342"}nodes[2] = Node{3, 1, "0x12343"}nodes[3] = Node{4, 1, "0x12344"}nodes[4] = Node{5, 1, "0x12345"}cnt :=0for i:=0;i<5;i++ {for j:=0;j<nodes[i].Tokens * nodes[i].Days;j++{addr[cnt] = &nodes[i]cnt++}}}//采用Pos共識算法進行挖礦 func CreateNewBlock(lastBlock *Block, data string) Block{var newBlock BlocknewBlock.Index = lastBlock.Index + 1newBlock.Timestamp = time.Now().String()newBlock.PreHash = lastBlock.HashnewBlock.Data = data//通過pos計算由那個村民挖礦//設置隨機種子rand.Seed(time.Now().Unix())//[0,15)產生0-15的隨機值var rd =rand.Intn(15)//選出挖礦的曠工node := addr[rd]//設置當前區塊挖礦地址為曠工newBlock.Validator = node//簡單模擬 挖礦所得獎勵node.Tokens += 1newBlock.Hash = hex.EncodeToString(BlockHash(&newBlock))return newBlock }func main() {InitNodes()//創建創世區塊var genesisBlock = genesisBlock()//創建新區快var newBlock = CreateNewBlock(&genesisBlock, "new block")//打印新區快信息fmt.Println(newBlock)fmt.Println(newBlock.Validator.Address)fmt.Println(newBlock.Validator.Tokens)}輸出結果: {1 new block
72e8838ad3bb761c7d3ba42c4e6bad86409dd3f4ce958c890409c4b9ddf44171
e4f9575cfb14ee146810862c9e5cc78ebff185f5888f428dbb945bd9060b31f7
2018-06-29 19:29:04.827332898 +0800 CST m=+0.000837770 0xc42007e0a0}
0x12341
2.3 委任權益證明(DPOS,Delegated Proof-of-Stake)
優點:
節能、快速、高流量博客網站Steemit就使用了它。EOS 的塊時間是 0.5 秒。
不足:
略為中心化、擁有高權益的參與者可投票使自己成為一名驗證者。這是近期已在 EOS 中出現的問題。
采用者:BitShares、Steemit、EOS、Lisk、Ark。
類型:協同型共識
解釋:在 DPoS 系統中,權益持有者可以選舉領導者(或稱為見證人,Witness)。經權益持有者授權,這些領導者可進行投票。該機制使得 DPoS 要快于正常的 PoS。
例如,EOS 中選舉出 21 位見證人,并且有一堆節點(潛在的見證人)作為候選者。一旦見證人節點死亡或是做出了惡意行為,新節點就會立刻替代見證人節點。見證人會因為生成區塊而獲得一筆支付費用。該費用是由權益持有者設立的 。
通常,所有節點采用輪詢方式,一次生成一個區塊。該機制防止一個節點發布連續的塊,進而執行“雙重支付”攻擊。如果一個見證人在分配給他的時間槽中未生成區塊,那么該時間槽就被跳過,并由下一位見證人生成下一個區塊。如果見證人持續丟失他的區塊,或是發布了錯誤的交易,那么權益持有者將投票決定其退出,用更好的見證人替換他。
在 DPoS 中,礦工可以合作生成塊,而不是像在 PoW 和 PoS 中那樣競爭生成。通過區塊生成的部分中心化,DPoS 的運行可以比其它共識算法呈數量級快。
從某種角度來看,DPOS有點像是議會制度或人民代表大會制度。如果代表不能履行他們的職責(當輪到他們時,沒能生成區塊),他們會被除名,網絡會選出新的超級節點來取代他們。EOS就是采用DPOS共識算法。
技術原理:
假設n為21,競選的節點有幾百個,持幣人對這些節點進行投票,選出票數最多的21位,由這21位輪流來出塊。
GO DEMO簡單實現:
輸出結果: [{NODE 1 num 0} {NODE 2 num 0} {NODE 3 num 0} {NODE 4 num 0}
{NODE 5 num 0} {NODE 6 num 0} {NODE 7 num 0} {NODE 8 num 0} {NODE 9
num 0} {NODE 10 num 0}] [{NODE 1 num 3} {NODE 2 num 3} {NODE 3 num 3}]
區塊號: 0 節點名稱: Genis Block 節點投票數: 0 區塊號: 1 節點名稱: NODE 1 num 節點投票數: 3
區塊號: 2 節點名稱: NODE 2 num 節點投票數: 3
2.4 拜占庭容錯(PBFT,Practical Byzantine Fault Tolerance)
優點:高速、可擴展。
不足:通常用于私有網絡和許可網絡。
采用者:Hyperledger Fabric、Stellar、Ripple、Dispatch
解釋:拜占庭將軍問題是分布式計算中的一個經典問題。問題描述為,幾位拜占庭將軍分別率領部隊合力包圍了一座城市。他們必須一致決定是否發起攻城。如果一些將軍在沒有其他將軍參與的情況下決定發起攻城,那么他們的行動將以失敗告終。將軍們之間相互隔著一定的距離,必須依靠信息傳遞進行交流。 一些加密貨幣協議在達成共識時使用了特定版本的 BFT,每種版本都具有各自的優缺點:
[1] 實用拜占庭容錯(PBFT,Practical Byzantine Fault Tolerance):首個提出的該問題解決方案稱為“實用拜占庭容錯”(PBFT),當前已被 Hyperledger Fabric 采用。PBFT 使用了較少(少于 20 個,之后會稍有增加)的預選定將軍數,因此運行非常高效。它的優點是高交易通量和吞吐量,但是不足之處在于是中心化的,并用于許可網絡。
從某種角度來看,PBFT有點像《天黑請閉眼殺人游戲》的玩法。
[2] 聯邦拜占庭協議(FBA,Federated Byzantine Agreement):另一類拜占庭將軍問題的解決方案是 FBA,已被 Stellar 和 Ripple 等代幣使用。FBA 的通用理念是每個拜占庭將軍負責自身的鏈、消息一旦到來,通過排序建立事實。在 Ripple 中,將軍(驗證者)是 Ripple 基金會預先選定的。在 Stellar 中,任何人都可以成為驗證者,需要用戶選擇去相信哪個驗證者。
由于 FBA 可提供令人難以置信的吞吐量、低交易開銷和網絡擴展性,我相信 FBA 類公式算法是目前提出的最好的分布式共識發現算法。
技術原理:
PBFT基于拜占庭將軍問題,一致性的確保主要分為這三個階段:預準備(pre-prepare)、準備(prepare)和確認(commit)。流程如下圖所示:
其中C為發送請求端,0123為服務端,3為宕機的服務端,具體步驟如下:
1.Request:請求端C發送請求到任意一節點,這里是0
2.Pre-Prepare:服務端0收到C的請求后進行廣播,擴散至123
3.Prepare:123,收到后記錄并再次廣播,1->023,2->013,3因為宕機無法廣播
4.Commit:0123節點在Prepare階段,若收到超過一定數量的相同請求,則進入Commit階段,廣播Commit請求;
5.Reply:0123節點在Commit階段,若收到超過一定數量的相同請求,則對C進行反饋;
更多原理細節可參考《第13課 共識層PBFT共識算法》
)
GO demo代碼樣例:
package mainimport ("os""fmt""net/http""io" )//聲明節點信息,代表各個小國家 type nodeInfo struct {//標示id string//準備訪問的方法path string//服務器做出的相應writer http.ResponseWriter}//存放四個國家的地址 var nodeTable = make(map[string]string)//拜占庭在Fabric中的使用 func main() {//獲取執行的參數userId :=os.Args[1]//獲取執行的第一個參數fmt.Println(userId)//./main Apple//創建四個國家的地址nodeTable = map[string]string {"Apple":"localhost:1111","MS":"localhost:1112","Google":"localhost:1113","IBM":"localhost:1114",}node:=nodeInfo{userId,nodeTable[userId],nil}fmt.Println(node)//http協議的回調函數//http://localhost:1111/req?warTime=8888http.HandleFunc("/req",node.request)http.HandleFunc("/prePrepare",node.prePrepare)http.HandleFunc("/prepare",node.prepare)http.HandleFunc("/commit",node.commit)//啟動服務器if err:=http.ListenAndServe(node.path,nil);err!=nil {fmt.Print(err)}}//此函數是http訪問時候req命令的請求回調函數 func (node *nodeInfo)request(writer http.ResponseWriter,request *http.Request){//設置允許解析參數request.ParseForm()//如果有參數值,則繼續處理if (len(request.Form["warTime"])>0){node.writer = writer//激活主節點后,廣播給其他節點,通過Apple向其他節點做廣播node.broadcast(request.Form["warTime"][0],"/prePrepare")}}//由主節點向其他節點做廣播 func (node *nodeInfo)broadcast(msg string ,path string ){//遍歷所有的國家for nodeId,url:=range nodeTable {if nodeId == node.id {continue}//調用Get請求//http.Get("http://localhost:1112/prePrepare?warTime=8888&nodeId=Apple")http.Get("http://"+url+path+"?warTime="+msg+"&nodeId="+node.id)}}func (node *nodeInfo)prePrepare(writer http.ResponseWriter,request *http.Request) {request.ParseForm()//fmt.Println("hello world")//在做分發if(len(request.Form["warTime"])>0){//分發給其他三個人node.broadcast(request.Form["warTime"][0],"/prepare")}}func (node *nodeInfo)prepare(writer http.ResponseWriter,request *http.Request){request.ParseForm()//調用驗證if len(request.Form["warTime"])>0{fmt.Println(request.Form["warTime"][0])}if len(request.Form["nodeId"])>0 {fmt.Println(request.Form["nodeId"][0])}node.authentication(request) }var authenticationsuccess = true var authenticationMap = make(map[string]string) //獲得除了本節點外的其他節點數據 func (node *nodeInfo)authentication(request *http.Request) {//接收參數request.ParseForm()if authenticationsuccess!=false {if len(request.Form["nodeId"])>0 {authenticationMap[request.Form["nodeId"][0]]="ok"}}if len(authenticationMap)>len(nodeTable)/3 {//則拜占庭原理實現,通過commit反饋給瀏覽器node.broadcast(request.Form["warTime"][0],"/commit")} }func (node *nodeInfo)commit(writer http.ResponseWriter,request *http.Request){//給瀏覽器反饋相應io.WriteString(node.writer,"ok")}如何運行:開啟4個終端,eg:
./pbft Apple ./pbft IBM ./pbft MS ./pbft Google然后在瀏覽器輸入:http://localhost:1112/req?warTime=1234 輸出結果:
okokok2.5 分布式一致性協議- RAFT算法
優點:
模型比Paxos更簡單,但提供了同等的安全性。有多種語言的實現可用。
不足:通常用于私有網絡和許可網絡。
采用者:IPFS Private Cluster、Quorum。
解釋:
將拜占庭將軍問題根據常見的工作上的問題進行簡化:假設將軍中沒有叛軍,信使的信息可靠但有可能被暗殺的情況下,將軍們如何達成一致性決定?
對于這個簡化后的問題,有許多解決方案,第一個被證明的共識算法是 Paxos,由拜占庭將軍問題的作者 Leslie Lamport 在1990年提出,但其論文難懂而出名,所以斯坦福大學的教授在2014年發表了新的分布式協議 Raft。與 Paxos 相比,Raft 有著基本相同運行效率,但是更容易理解,也更容易被用在系統開發上。
我們還是用拜占庭將軍的例子來幫助理解 Raft。
Raft 的解決方案大概可以理解成 先在所有將軍中選出一個大將軍,所有的決定由大將軍來做。選舉環節:比如說現在一共有3個將軍 A, B, C,每個將軍都有一個隨機時間的倒計時器,倒計時一結束,這個將軍就會把自己當成大將軍候選人,然后派信使去問其他幾個將軍,能不能選我為總將軍?假設現在將軍A倒計時結束了,他派信使傳遞選舉投票的信息給將軍B和C,如果將軍B和C還沒把自己當成候選人(倒計時還沒有結束),并且沒有把選舉票投給其他,他們把票投給將軍A,信使在回到將軍A時,將軍A知道自己收到了足夠的票數,成為了大將軍。在這之后,是否要進攻就由大將軍決定,然后派信使去通知另外兩個將軍,如果在一段時間后還沒有收到回復(可能信使被暗殺),那就再重派一個信使,直到收到回復。
技術原理:
Raft要求系統在任意時刻最多只有一個Leader,正常工作期間只有Leader和Followers。Raft算法將時間分為一個個的任期(term),每一個term的開始都是Leader選舉。在成功選舉Leader之后,Leader會在整個term內管理整個集群。如果Leader選舉失敗,該term就會因為沒有Leader而結束。
(1)Raft 節點狀態
從拜占庭將軍的故事映射到分布式系統上,每個將軍相當于一個分布式網絡節點,每個節點有三種狀態:Follower,Candidate,Leader,狀態之間是互相轉換的,可以參考下圖:
每個節點上都有一個倒計時器 (Election Timeout),時間隨機在 150ms 到 300ms 之間。有幾種情況會重設 Timeout:
(1)收到選舉的請求
(2)收到 Leader 的 Heartbeat (后面會講到)
在 Raft 運行過程中,最主要進行兩個活動:
(1)選主 Leader Election
(2)復制日志 Log Replication
技術原理
(1)選主 Leader Election
1)正常情況下選主
假設現在有如圖5個節點,5個節點一開始的狀態都是 Follower。
在一個節點倒計時結束 (Timeout) 后,這個節點的狀態變成 Candidate 開始選舉,它給其他幾個節點發送選舉請求 (RequestVote)
其他四個節點都返回成功,這個節點的狀態由 Candidate 變成了 Leader,并在每個一小段時間后,就給所有的 Follower 發送一個 Heartbeat 以保持所有節點的狀態,Follower 收到 Leader 的 Heartbeat 后重設 Timeout。
這是最簡單的選主情況,只要有超過一半的節點投支持票了,Candidate 才會被選舉為 Leader,5個節點的情況下,3個節點 (包括 Candidate 本身) 投了支持就行。
(2) 2.2 Leader 出故障情況下的選主
一開始已經有一個 Leader,所有節點正常運行。
Leader 出故障掛掉了,其他四個 Follower 將進行重新選主。
4個節點的選主過程和5個節點的類似,在選出一個新的 Leader 后,原來的 Leader 恢復了又重新加入了,這個時候怎么處理?在 Raft 里,第幾輪選舉是有記錄的,重新加入的 Leader 是第一輪選舉 (Term 1) 選出來的,而現在的 Leader 則是 Term 2,所有原來的 Leader 會自覺降級為 Follower
(3)2.3 多個 Candidate 情況下的選主
假設一開始有4個節點,都還是 Follower。
有兩個 Follower 同時 Timeout,都變成了 Candidate 開始選舉,分別給一個 Follower 發送了投票請求。
兩個 Follower 分別返回了ok,這時兩個 Candidate 都只有2票,要3票才能被選成 Leader。
兩個 Candidate 會分別給另外一個還沒有給自己投票的 Follower 發送投票請求。
但是因為 Follower 在這一輪選舉中,都已經投完票了,所以都拒絕了他們的請求。所以在 Term 2 沒有 Leader 被選出來。
這時,兩個節點的狀態是 Candidate,兩個是 Follower,但是他們的倒計時器仍然在運行,最先 Timeout 的那個節點會進行發起新一輪 Term 3 的投票。
兩個 Follower 在 Term 3 還沒投過票,所以返回 OK,這時 Candidate 一共有三票,被選為了 Leader。
如果 Leader Heartbeat 的時間晚于另外一個 Candidate timeout 的時間,另外一個 Candidate 仍然會發送選舉請求。
兩個 Follower 已經投完票了,拒絕了這個 Candidate 的投票請求。
Leader 進行 Heartbeat, Candidate 收到后狀態自動轉為 Follower,完成選主。
實現代碼參考: https://github.com/goraft/raft 或者
https://github.com/happyer/distributed-computing/tree/master/src/raft
2.6 有向無環圖(DAG,Directed Acyclic Graphs)
優點:
由于 DAG 的非線性結構,它是高度可擴展的、快速、節能、立即實現終結性(Finality)。
不足:只能通過使用 Oracle 實現智能合約。
采用者:Iota、HashGraph、Byteball、RaiBlocks/Nano。
解釋:DAG 是一種更通用形式的區塊鏈。由于其獨特結構,DAG 內在支持高可擴展性,因此也得到了廣泛的使用。
從根本上說,任何區塊鏈系統都具有線性結構,因為區塊是依次添加到鏈中的。這使得相比于并行向鏈中添加區塊,線性區塊鏈在本質上是非常緩慢的。但是對于 DAG 而言,每個區塊和交易只需數個前期區塊得到確認,就可以并行地添加到區塊和交易中。這意味著,DAG 在本質上是高可擴展的。
DAG 存在多種變體,取決于:
· 如何選取前期區塊驗證的算法,也稱為“Tip 選擇算法”。
· 交易完成的順序。
· 如何抵達完成狀態。
下面列出一些廣為使用的 DAG 項目。
1 Tangle(IOTA)
image
解釋:Tangle是一種 DAG 共識算法,由 IOTA 使用。為了發送一個 IOTA 交易,用戶需要驗證接收到的前兩個交易。在更多交易添加到 Tangle 的情況下,這種二對一、前瞻性支付的共識可加強交易的有效性。由于共識是由交易確定的,因此理論上,如果有人可以生成三分之一的交易,那么他就可以說服網絡中的其余部分,使得他的無效交易變成有效的。一旦交易量足夠大,使得個人難以創建三分之一交易量,這時 IOTA 就會在一個稱為“協調器(The Coordinator)”的中心節點上對網絡中的所有交易做“復核”(double-checking)。按 ITOA 的說法,協調員的工作類似于輔助輪。一旦 Tangle 達到一定的規模,協調員就會被從中移除。
2 Hashgraph
解釋:Hashgraph 是由 Leemon Baird 開發的一種 Gossip 協議共識。節點隨機與其它節點共享自身已知的交易,最終所有交易都被以 Gossip 協議傳播到(Gossip around)到所有節點。Hashgraph 對于私有網絡是一個很好的選擇。但我們并不會看到它實現在以太坊這樣的公共網絡中,或是不通過 Gossip 協議隨機傳播交易。
3 Holochain
解釋:Holochain 十分類似于 HashGraph,但不同于 Hashgraph。它提供了一種可用于構建去中心化應用的數據結構。用戶可以具有自己的鏈,并向其中添加包括金融交易在內的數據。鏈可以采用復雜的方式合并、拆分和交互。數據以去中心化的方式存儲(類似于 Bittorrent)。數據具有一個哈希值,即一個對應于數據的數學指紋。如果有人意圖篡改數據,那么我們就會注意到在數據和哈希值之間存在不匹配,這樣就可拒絕數據為無效的。數字簽名保證了數據的作者身份。Holochain 可看成是“Bittorrent+git+ 數字簽名”。
4 Block-Nano
解釋:Nano(以前稱為 Raiblocks)是以纏繞在區塊鏈上的方式運行,這種方式被稱為“塊狀格子”(Block-lattice)。在 Block-lattice 結構中,每個用戶(地址)都有自己的鏈,只有用戶本身可寫,每個用戶都擁有所有鏈的副本。
每個交易都可分解為發送者鏈上的發送區塊,以及接收者鏈上的接收區塊。Block-lattice 看上似乎太簡單,以至于無法工作,但它已經在實際運行了。Block-lattice 的獨特結構的確無法抵制一些獨特的攻擊向量,例如 Penny-spend 攻擊。在這種攻擊中,攻擊者通過向大量空錢包發送數額可忽略不計的金錢,導致必須要追蹤的鏈數量急劇膨脹。
5 SPECTRE
解釋:SPECTRE,即“序列化 PoW 事件并通過遞歸選舉確認交易”(Serialization of Proof-of-work Events, Confirming Transactions via Recursive Elections),是提議的一種 Bitcoin 擴展解決方案。它利用 PoW 和 DAG 的組合實現可擴展的共識。在 SPECTER 中,一個挖掘的區塊指向多個父節點,而不僅僅是單個節點,這使得網絡每秒可以處理多個區塊。而挖掘指向某些父區塊的區塊,這將支持區塊的有效性。與 PoW 的“最長鏈勝出”的原則相比,SPECTER 使用的原則可描述為“擁有最多子節點的區塊勝出”。SPECTRE 尚未得到實際運行測試,因此可能會存在一些新的攻擊向量。但我認為,SPECTRE 很有可能成為一種修正 Bitcoin 問題的潛在好做法。
6 ByteBall
解釋:ByteBall 使用 DAG 建立交易間的偏序關系,此外還在 DAG 中添加了“主鏈”(MC,Main Chain)。
圖 DAG 中加粗顯示的“主鏈”
MC 允許在交易間定義全序關系,即更早加入(直接或間接)MC 的交易,必定更早出現在全序中。如果存在“雙重支付”問題,那么將視較早出現在全序中的交易版本為有效的,而其它所有的交易均被視為是無效的。
根據交易在圖中的位置,MC 可得到確定性的定義。相關詳細信息,請參閱白皮書。作為一般性規則,MC 傾向于采納由一些總所周知用戶所給出的交易,這樣的用戶被稱為“證人”(Witnesses)。證人列表是由用戶自己定義的,因為列表中包括了用戶發布的每個交易。然后,MC 沿著 DAG 內路徑推進。推進原則包括:
· MC 上相鄰交易的證人列表要么完全相同,要么只存在一個突變。
· 與其它鏈相比,MC 中為經過最多數量的由見證人認證的交易。
ByteBall 也是首個在系統中包含 Oracle 的平臺。Oracle 是在 DAG 中添加智能合約功能所必需的。
2.7 容量證明(PoC,Proof of Capacity)
優點:
它類似于 PoW,只是使用空間替代了計算。因此更加環境友好。
可用于惡意軟件檢測。通過確定處理器的 L1 緩存是否為空(例如,具有足夠空間在沒有緩存未命中的情況下計算 PoSpace 過程),或是包含一個拒絕被逐出(evicted)的例程。
可用于反垃圾郵件措施,以及防范拒絕服務(DoS)攻擊。
不足:激勵機制可能存在問題。
使用者: Butcoin、Chia、SpaceMint。
類型:協同型共識。
解釋:PoSpace,也稱為 PoC,通過分配一定數量的內存或磁盤空間用于解決服務提供者所提供挑戰的方式,顯示了某個人對某個服務(例如發送郵件)具有合法的興趣。該理念是由 Dziembowski 等在 2015 年形式化定義的。雖然 Ateniese 等人的論文名稱也是“Proof-of-space”,但它事實上一種采用 MHF(Memory Hard Function,一種計算代價取決內存的哈希算法)的 PoW 協議。
PoSpace 非常類似于 PoW,只是使用存儲替代了 Pow 中的計算。PoSpace 與 MHF 和可回收性證明(PoR,Proof of Retrievability)有關,但也在很大程度上存在著差異。
PoSpace 是由證明者 (Prover) 發送給驗證者 (Verifier) 的一小塊數據,該數據確認了證明者已經保留了一定量的空間。出于實用性上的考慮,驗證過程需要盡量高效,即消耗盡可能少的空間和時間。出于公平性上的考慮,如果驗證者沒有保留所聲明數量的空間,那么它應該難以通過驗證。PoSpace 的一種實現方式是通過使用一個難以實現 Pebbling 的圖。驗證者請求證明者構建對一個“非 Pebbling 圖”標記。證明者提交標記,進而驗證者請求證明者在提交中開放多個隨機位置。
由于存儲的通用本質,以及存儲所需的更低耗能,PoSpace 被認為是一種更公平、更綠色的替換方法。
2.8 延遲工作量證明(dPoW,Delayed Proof-of-Work)、
優點:
節能、安全性增加、可以通過非直接提供 Bitcoin(或是其它任何安全鏈),添加價值到其它區塊鏈,無需付出 Bitcoin(或是其它任何安全鏈)交易的代價。
不足:
只有使用 PoW 或 PoS 的區塊鏈,才能采用這種共識算法。
在“公證員激活”(Notaries AcTIve)模式下,必須校準不同節點(公證員或正常節點)的哈希率,否則哈希率間的差異會爆炸(下文將給出詳細解釋)。
采用者:Komodo
類型:協同型共識(CollaboraTIve consensus)
解釋:dPoW 是一種混合共識方法,允許一個區塊鏈利用第二個區塊鏈的哈希算力(Hashing Power)所提供的安全。該機制是通過一組公證員節點(Notary Node)實現的。公證員節點實現將第一個區塊鏈的數據添加到第二個區塊鏈中。進而,第二個區塊鏈請求在兩個區塊鏈間達成妥協,弱化第一個區塊鏈的安全。Komodo是首個使用該共識方法的區塊鏈,它就是附加于 Bitcoin 區塊鏈之上的。
使用 dPoW 的區塊鏈也可以使用 PoW 或 PoS 共識方法工作,并可以附加在任何采用 PoW 的區塊鏈上。但對于由 dPoW 提供安全的區塊鏈,當前 Bitcoin 給出了最高安全層級的哈希率。下圖展示了主區塊鏈的單個記錄以及其所附著的 PoW 區塊鏈。
dPoW 系統中有兩種類型的節點:公證人節點和正常節點。64 個公證人節點是由 dPoW 區塊鏈的權益持有者(stakeholder)選舉產生的,它們可從 dPoW 區塊鏈向所附加的 PoW 區塊鏈添加經公證確認的塊。一旦添加了一個塊,該塊的哈希值將被添加到由 33 個公證人節點簽署的 Bitcoin 交易中,并創建一個哈希到 Bitcoin 區塊鏈的 dPow 塊記錄。該記錄已被網絡中的大多數公證人節點公證。
為避免公證人節點間在挖礦上產生戰爭,進而降低網絡的效率,Komodo 設計了一種采用輪詢機制的挖礦方法。該方法具有兩種運行模式。在“無公證人”(No Notary)模式下,支持所有網絡節點參與挖礦,這類似于傳統 PoW 共識機制。而在“公證人激活”(Notaries AcTIve)模式下,網絡公證人使用一種顯著降低的網絡難度率挖礦。“公證人激活”模式下,允許每位公證人使用其當前的難度挖掘一個區塊,而其它公證人節點必須采用 10 倍難度挖礦,所有正常節點使用公證人節點難度的 100 倍挖礦。
但這會導致一些問題。我在與 Komodo 創始人的一次談話中提及,這將導致公證人礦工和正常礦工間的哈希率存在很高的差異:
圖 本文作者與 Komodo 創始人間就不一致性問題進行交流的截圖
dPoW 系統在設計上支持區塊鏈在沒有公證人節點的情況下繼續運行。在這種情況下,dPoW 區塊鏈可以基于初始的共識方法繼續運行,但將不再具有所附著區塊鏈增添的安全。
所有使用 dPoW 的區塊鏈可增加安全,同時降低能耗。例如,Komodo 使用 Equihash 哈希算法防止使用 ASIC 挖礦。其公證人節點依賴于一種輪詢挖礦方法,獎勵機制考慮了降低節點間競爭的可能性。這些節點將會引發過度耗能或算力。
此外通過非直接提供 Bitcoin 安全,Komodo 這類 dPoW 區塊鏈可以向其它區塊鏈添加價值,無需付出任何 Bitcoin 交易的代價。Komodo 此后附著到 Bitcoin,而第三個使用 dPoW 的區塊鏈可以將自身附著到 Komodo。使用這種方式,dPoW 區塊鏈不必直接附著到 Bitcoin 區塊鏈,就從 Bitcoin 的高哈希率中受益。
最后一點,公證人節點和正常節點分離的功能,確保了初始共識機制在公證人節點失敗時繼續運行。這種相互獨立性建立了一種獎勵機制,使得其它網絡無需依賴于 Bitcoin 網絡的直接功能,即可支持 Bitcoin 網絡的繼續維護。
2.9 權威證明(PoA,Proof-of-Authority)
優點:節能、快速。
不足:略為中心化。雖然可用于公有區塊鏈,但是通常用于私有區塊鏈和許可區塊鏈。
使用者:POA.Network、Ethereum Kovan testnet、VeChain。
類型:協同型共識。
解釋:基于 PoA 的網絡、事務和區塊,是由一些經認可的賬戶認證的,這些被認可的賬戶稱為“驗證者”(Validator)。驗證者運行的軟件,支持驗證者將交易(transaction)置于區塊中。該過程是自動的,無需驗證者持續監控計算機,但需要維護計算機(權威節點)不妥協(uncompised)。
驗證者必須滿足以下三個條件:
使用 PoA,每個個體都具有變成驗證者的權利,因此存在一旦獲取就保持驗證者位置的動機。通過對身份附加一個聲譽,可以鼓勵驗證者去維護交易的過程。因為驗證者并不希望讓自己獲得負面聲譽,這會使其失去來之不易的驗證者地位。
2.10 權重證明(PoWeight,Proof-of-Weight)
優點:節能、高度可定制和可擴展
不足:可能難以實現激勵、
采用者:Algorand。
類型:有競爭共識。
解釋:權重證明(PoWeight)是一類很寬泛的共識算法,它基于Algorand共識模型。其基本理念是在 PoS 中,用戶所擁有的網絡中令牌的百分比,表示了該用戶“發現”下一個區塊的概率。PoWeight 系統中還使用了其它一些相對加權值,實現包括聲望證明(PoR,Proof of Reputation)和空間證明(Proof of Space)。
2.11. 聲譽證明(PoR,Proof of Reputation)
優點:非常適用于私有區塊鏈和許可區塊鏈。
不足:只能用于私有區塊鏈和許可區塊鏈。
采用者:GoChain。
類型:協同型共識。
解釋:PoR 類似于 PoA。GoChain 文檔中給出了如下描述:
PoR 共識模型依賴參與者在保持網絡安全中的聲譽。參與者(區塊簽名者)必須具有足夠重要的聲譽。一旦他們嘗試欺騙系統,那么他們將要面對嚴重的財政上的和自己名聲上的后果。這是一個相對的概念,如果他們被抓到試圖欺騙,那么幾乎所有的業務將會受到嚴重的影響。規模越大的企業,通常將會失去更多。這樣,相比使用更少的企業(即更小規模的商業),規模更大的企業更易于被選定。
一旦一個企業證明了自己的聲譽,并通過了驗證,那么他們必須經投票參與到權威節點網絡中。這時,PoR 的操作與 PoA 網絡一樣,即只有權威節點可以簽名并驗證區塊。
2.12. 所用時間證明(PoET,Proof of Elapsed Time)
優點:
參與代價低。更多人可輕易加入,進而達到去中心化。
對于所有參與者而言,更易于驗證領導者是通過合法選舉產生的。
控制領導者選舉過程的代價,是與從中獲得的價值成正比的。
不足:
盡管 PoET 的代價低,但是必須要使用特定的硬件。因此不會被大規模采納。
不適用于公有區塊鏈。
采用者:HyperLedger Sawtooth
類型:有競爭共識
解釋:PoET 共識機制算法通常用于許可區塊鏈網絡,它可決定網絡中獲得區塊者的挖礦權利。許可區塊鏈網絡需要任何預期參與者在加入前驗證身份。根據公平彩票系統的原則,每個節點具有同等的可能成為勝出者。PoET 機制賦予大量可能的網絡參與者以平等勝出的機會。
PoET 的工作機制如下:網絡中的每位參與節點都必須等待一個隨機選取的時期,首個完成設定等待時間的節點將獲得一個新區塊。區塊鏈網絡中的每個節點會生成一個隨機的等待時間,并休眠一個設定的時間。最先醒來的節點,即具有最短等待時間的節點,喚醒并向區塊鏈提交一個新區塊,然后廣播必要的信息到整個對等網絡中。同一過程將會重復,以發現下一個區塊。
在 PoET 網絡共識機制中,需要確保兩個重要因素。第一,參與節點在本質上會自然地選取一個隨機的時間,而非某一個參與者為勝出而刻意選取了較短的時間。第二,勝出者的確完成了等待時間。
PoET 理念是由著名的芯片制造巨頭 Intel于 2016 年早期提出的。Intel 為解決“隨機領導者選舉”的計算問題,實現了一個可用的高科技工具。
這種內在機制允許應用在受保護的環境中執行受信任的代碼,它確保了上面提出的兩個要求得到滿足,即隨機選擇所有參與節點的等待時間,以及勝出參與者真正完成了等待時間。
這種在安全環境中運行可信代碼的機制也同時考慮到了其它一些網絡的需求。它確保了受信代碼的確運行在安全環境中,并不可被其它外部參與者更改。它也確保了結果可被外部參與者和實體驗證,進而提高了網絡共識的透明度。
PoET 通過控制代價實現了共識過程,該代價依然是與從過程中獲得的價值成正比。這是保證加密貨幣經濟持續繁榮的一個關鍵需求。
2.13 歷史證明(PoHistory,Proof of History)
采用者:Solana
解釋:其基本理念是不相信交易中的時間戳,而是證明交易在某個事件之前或之后的某個時刻發生。
如果我們對某期《紐約時報》的封面拍了張照片,那么我們就創建了一個證明,即我們的拍照時間是在該報紙發行之后,或許也可能是我們有某種途徑影響了紐約時報的正常發行。我們可以使用 PoHistory 創建一個歷史記錄,證明一個事件是發生在特定時間之后的。
區塊鏈共識算法全面詳解
PoHistory 是一種高頻可驗證延遲函數(VDF,Verifiable Delay Function)。VDF 求值需要完成特定數量的順序步驟,然后生成一個唯一的輸出。該輸出可被高效地和公開地驗證。
VDF 的一個特定實現使用了持續運行于其上的順序抗預映射哈希(Pre-image Resistant Hash),其中前一次循環生成的輸出將用于下一次循環的輸入。計數和當前輸出形成周期性記錄。
如果使用了 SHA256 哈希函數,那么不使用 2128核的暴力攻擊,該過程是不可能并行化的。
因此我們可以確認,每個計數器在生成過程中都的確經歷了一定的時間。進而,每個計數器記錄的順序與實時情況是一致的。
2.14 單點共識(SOLO)
使用者:Frabric
解釋:Solo共識模式是指Order節點為單節點通信模式,由Peer節點發送過來的消息由一個Order節點進行排序和產生區塊。
由于排序服務只有一個Order為所有節點(Peer)服務,沒有高可用性和可擴展性,不適合用于生產環境,可以用于開發和測試環境。
技術原理:
Solo共識工作時序如下圖所示。圖中所描述的范圍是在SDK發起交易到交易落地這整個過程。
在Order節點容器啟動時,啟動Solo排序服務,開啟監SDK發送過來的消息,收到消息后調用Solo服務進行數據區塊處理。其中,Solo模式調用過程說明:
(1)SDK通過gRPC連接Peer,發送交易信息Tx;
(2)Peer調用合約后,將返回結果再回復給SDK;
(3)SDK通過gRPC連接Order,將(2)的sdkPeerReply發送給Order,執行Solo共識服務:
A.接收消息
B.消息入列
C.消息排序
D.消息切塊(根據時間或交易數量分切)
E.生成區塊
F.寫入區塊文件
G.通知Peers
首先order設置共識機制為“solo”,多機多節點部署需要至少兩臺服務器,一臺 Order 排序服務節點,一臺 peer 節點,每新加一臺額外的服務器都可作為新的 peer 節點來加盟。
2.15 活動證明(PoActivity,Proof Of Activity)
使用者:Decred
解釋:為避免出現惡性通貨膨脹(當大量貨幣充斥系統時就會發生),比特幣將只生成兩千一百萬枚。這意味著,在某些時候,比特幣區塊獎勵補貼將終止,比特幣礦工將只能收取交易費用。
一些人猜測這可能會導致由“公地悲劇(Tragedy of the commons)”所引發的安全問題,人們出于自身利益考慮行事并破壞系統。因此,人們提出了PoActivity作為一種替代 Bitcoin 的激勵結構。PoActivity 是一種結合了 PoW 和 PoS 的混合方法。
在 PoActivity 中,挖礦一開始使用的是傳統的 PoW,礦工們爭相解決加密難題。根據實現,挖掘的區塊不包含任何交易,它們更像模板。因此,勝出的區塊將只包含頭部信息,以及礦工的獎勵地址。
此時,系統將切換到 PoS。PoActivity 根據頭部信息選擇一組隨機驗證者對新區塊簽名。如果一位驗證者所擁有的系統中代幣越多,那么該驗證者被選中的可能性也會越大。一旦所有驗證者已簽名,那么模板就會變成一個完整的區塊。
如果在完成區塊時,某些選定的驗證者是不可用的,那么就選擇下一個勝出區塊,并選擇一組新的驗證者,依此類推,直到區塊收到到正確數量的簽名。費用由礦工和在區塊上簽名的驗證者分攤。
對 PoActivity 的批評包括挖掘區塊耗能過高(與 PoW 一樣),以及無法阻止驗證者做雙重簽名(與 PoS 一樣)。
3,參考
(1)分布式共識算法專欄 - 匯集各種共識算法
https://recomm.cnblogs.com/blogpost/11284374?page=1
(2)區塊鏈共識算法全面詳解 http://www.elecfans.com/blockchain/843819.html
(3)共識算法DPOS原理及實現 https://www.meiwen.com.cn/subject/hxqzyftx.html
(4)拜占庭PBFT簡單實現 https://www.meiwen.com.cn/subject/prvjuftx.html
(5)PBFT算法 https://www.meiwen.com.cn/subject/owzvyxtx.html
總結
以上是生活随笔為你收集整理的15种区块链共识算法全面详解的全部內容,希望文章能夠幫你解決所遇到的問題。