區塊鏈面試指南–之共識演算法

最近,一張關於區塊鏈高薪職位的招聘照片火爆網路:

可以看到,月薪遠遠高出行業其他工程師一大截,可以說簡直完爆!

基本覆蓋國內一線網際網路大公司,最高月薪達100K。

當我們還在瞭解什麼是區塊鏈的時候,行業巨頭已經開始紛紛招兵買馬,佈局區塊鏈。

不知不覺中,一個新興的工作崗位正在慢慢誕生:區塊鏈研發工程師。

對於普通傳統的程式設計師群體,該怎麼向區塊鏈靠齊呢?

錯過了AI,大資料,人工智慧,能否搭上區塊鏈的末班車?

我認為:

一切皆有可能

這也是我著手寫這一系列的初衷:

區塊鏈技術距離我們並不遙遠,比人工智慧要容易多得多。

為什麼?

先來看幾個區塊鏈的招聘要求:

看了招聘要求,你會發現沒有特別高高在上的要求,前面幾項都是計算機通用要求:

要求計算機等相關專業;
對計算機理論、網路知識有了解;
精通linux,熟悉C /Java/go語言;

以上種種都是對後臺伺服器研發人員的要求,所以如果你目前從事後臺研發,那恭喜你已經具備滿足區塊鏈研發的60%職位要求。

剩下40%就是我這個系列要著重講述的部分。

我整理彙總了招聘網站上對於區塊鏈崗位的招聘要求,按優先順序重要性做了排序:

  • 1、熟練掌握以太坊/比特幣/區塊鏈的原理、機制;
  • 2、理解主流共識演算法,包括不限於PoW,PoS,DPoS,PBFT,Paxos,Raft等;
  • 3、熟悉智慧合約和Solidity程式設計優先;
  • 4、熟悉各種資料結構和演算法,對密碼學,安全協議和加密演算法有研究;
  • 5、Hyperledge, 以太坊等公開區塊鏈專案研究或參與者;

後面幾點是對第一點的具體描述,本系列主要從技術層面講解區塊鏈的幾個核心技術點:

  • 1、共識機制、共識演算法
  • 2、區塊鏈中的密碼學技術
  • 3、智慧合約和solidity程式設計
  • 4、超級賬本Hyperledge

一共分為4篇來講述區塊鏈中的用到的技術,本篇是整個區塊鏈面試指南的第一篇:

介紹區塊鏈中的共識機制和共識演算法。


本文大綱:

1、什麼是共識機制?

2、主流的共識演算法有哪些?

3、目前主流區塊鏈(比特幣、以太坊等)分別採用哪種共識演算法?

4、哪種共識演算法最好?


1、什麼是共識機制?

我們都知道,區塊鏈可以看作一本記錄所有交易的分散式公開帳簿,區塊鏈網路中的每個參與者都把它看作一本所有權的權威記錄。

公開賬本歷史資料不可篡改,只允許往後新增,每個節點都具有相同的許可權,那麼就帶來一個問題:

公開賬本每個新區塊由誰來負責寫入?

因為所有節點都一樣,如果所有節點同時一起寫入賬本資料,那麼肯定資料會不一致。

因此需要一種機制來保證區塊鏈中的每一區塊只能由一個節點來負責寫入,如何選出寫入賬本資料的節點,這就是共識機制。讓平等的參與者按照某種秩序達成一致意見。

打個比方,

現在有一箇中心資料庫,所有客戶端都能來查詢,每個客戶端許可權都是一樣,但如果要對資料庫進行增刪改,不好意思,每次只允許一個客戶端來操作,通俗講,就是讓資料庫序列修改資料庫。通過一個演算法機制來抉擇出操作的客戶端。這個機制就是共識機制,所謂的共識就是在人人平等的社會裡需要大家共同形成一個共識,產生一個操作者、臨時決策者,代表大家來進行中心化的操作,大家按照這個共識來維持去中心化的網路世界。


2、主流的共識演算法有哪些?

區塊鏈中的共識演算法說到底還是分散式系統中最重要的一致性問題:

在分散式網路中如何保證資料一致性。

說到一致性問題,就不得不提大名鼎鼎的拜占庭將軍問題。是 Leslie Lamport 1982 年提出用來解釋一致性問題的一個虛構模型。拜占庭是古代東羅馬帝國的首都,由於地域寬廣,守衛邊境的多個將軍(系統中的多個節點)需要通過信使來傳遞訊息,達成某些一致的決定。但由於將軍中可能存在叛徒(系統中節點出錯),這些叛徒將努力向不同的將軍傳送不同的訊息,試圖會干擾一致性的達成。

具體詳情內容可執行google,我這裡只說結論:

Leslie Lamport 證明,當叛變者不超過1/3時,存在有效的演算法,不論叛變者如何折騰,忠誠的將軍們總能達成一致的結果。如果叛變者過多,則無法保證一定能達到一致性。

對於拜占庭將軍問題分兩種情況:

1)針對非拜占庭錯誤的情況,一般包括 Paxos、Raft 及其變種。

分散式資料庫設計一般都是基於paxos或raft演算法。

對於paxos原理,可參考我之前寫的一篇文章:

幣夏:理解這兩點,也就理解了paxos協議的精髓​zhuanlan.zhihu.com

資料庫基本採用raft和paxos的變種:

2)對於要能容忍拜占庭錯誤的情況,一般包括 PBFT 系列、PoW 系列演算法等。

從概率角度,PBFT 系列演算法是確定的,一旦達成共識就不可逆轉;而 PoW 系列演算法則是不確定的,隨著時間推移,被推翻的概率越來越小。


具體共識演算法介紹:

1)拜占庭共識演算法系列PBFT/DBFT機制:

拜占庭假設是對現實世界的模型化,由於硬體錯誤、網路擁塞或斷開以及遭到惡意攻擊,計算機和網路可能出現不可預料的行為。拜占庭容錯協議必須處理這些失效,並且這些協議還要滿足所要解決的問題要求的規範。這些演算法通常以其彈性t作為特徵,t表示演算法可以應付的錯誤程序數。很多經典演算法問題只有在n ≥ 3t 1時才有解,如拜占庭將軍問題,其中n是系統中程序的總數。

拜占庭容錯能夠容納將近1/3的錯誤節點誤差,IBM建立的Hyperledger就是使用了該演算法作為共識演算法。

DBFT機制,是由權益來選出記賬人,然後記賬人之間通過拜占庭容錯演算法來達成共識,這種方式的優點是:

  • 1)專業化的記賬人;
  • 2)可以容忍任何型別的錯誤;
  • 3)記賬由多人協同完成,每一個區塊都有最終性,不會分叉;
  • 4)演算法的可靠性有嚴格的數學證明;

缺點:

  • 1)當有1/3或以上記賬人停止工作後,系統將無法提供服務;
  • 2)當有1/3或以上記賬人聯合作惡,且其它所有的記賬人被恰好分割為兩個網路孤島時,惡意記賬人可以使系統出現分叉,但是會留下密碼學證據;

對於拜占庭將軍問題可自行網上查詢資料,很多這裡不再贅述。

2)工作量證明PoW

工作量證明,Proof of Work,通過計算來猜測一個數值(nonce),得以解決規定的 hash 問題(來源於 hashcash)。保證在一段時間內,系統中只能出現少數合法提案。

同時,這些少量的合法提案會在網路中進行廣播,收到的使用者進行驗證後會基於它認為的最長鏈上繼續難題的計算。因此,系統中可能出現鏈的分叉(Fork),但最終會有一條鏈成為最長的鏈。

3)權益證明PoS

權益證明,Proof of Stake,2013 年被提出,最早在 Peercoin 系統中被實現,類似現實生活中的股東機制,擁有股份越多的人越容易獲取記賬權。

典型的過程是通過保證金(代幣、資產、名聲等具備價值屬性的物品即可)來對賭一個合法的塊成為新的區塊,收益為抵押資本的利息和交易服務費。提供證明的保證金(例如通過轉賬貨幣記錄)越多,則獲得記賬權的概率就越大。合法記賬者可以獲得收益。

PoS 是試圖解決在 PoW 中大量資源被浪費的缺點。惡意參與者將存在保證金被罰沒的風險,即損失經濟利益。

一般的,對於 PoS 來說,需要掌握超過全網 的資源,才有可能左右最終的結果。這個也很容易理解,三個人投票,前兩人分別支援一方,這時候,第三方的投票將決定最終結果。

4)授權股權證明機制DPOS

PoS 的改進演算法,DPOS與POS原理相似。與POS的主要區別在於節點選舉若干代理,由代理人驗證和記賬。

PoW機制和PoS機制雖然都能有效地解決記賬行為的一致性共識問題,但是現有的比特幣PoW機制純粹依賴算力,導致專業從事挖礦的礦工群體似乎已和比特幣社群完全分隔,某些礦池的巨大算力儼然成為另一箇中心,這與比特幣的去中心化思想相沖突。PoS機制雖然考慮到了PoW的不足,但依據權益結餘來選擇,會導致首富賬戶的權力更大,有可能支配記賬權。

股份授權證明機制( Delegated Proof of Stake,DPoS)的出現正是基於解決PoW機制和PoS機制的這類不足。

當然,隨著科技的發展,在未來可能還會誕生更好的共識機制。


3、目前主流區塊鏈分別用的是什麼共識演算法?

主流區塊鏈採用的共識演算法彙總如下:

1)PoW共識演算法代表:比特幣&萊特幣&以太坊

比特幣採用的是PoW(Proof of Work),工作量證明,通過計算來猜測一個數值(nonce),得以解決規定的 hash 問題。

直接看比特幣原始碼:

https://github.com/bitcoin/bitcoin/blob/master/src/rpc/mining.cpp

https://github.com/bitcoin/bitcoin/blob/master/src/primitives/block.h

需要以下引數:

block的版本 version
上一個block的hash值: prev_hash
需要寫入的交易記錄的hash樹的值: merkle_root
更新時間: ntime
當前難度: nbits

挖礦的過程就是找到x使得以下等式成立:

SHA256(SHA256(version   prev_hash   merkle_root   ntime   nbits   x )) < TARGET

上式的x的範圍是0~2^32, TARGET可以根據當前難度求出的。由於hash的特性,找這樣一個x只能暴力搜尋。

PoW共識演算法的核心是所有節點通過暴力查詢x,使得上面的等式成立。

誰先找到誰就或者這一區塊的寫入權,並獲得獎勵,因此pow共識機制對所有節點都公平,誰的算力強誰就更有機會更高概率獲得寫入權。

以太坊也是採用PoW工作量證明演算法,具體實現演算法叫(Ethash)

具體內容可以看官方wiki:https://github.com/ethereum/wiki/wiki/Ethash

2)PoS機制代表:Peercoin & Nxt

點點幣(Peercoin )的權益證明機制結合了隨機化與幣齡的概念,未使用至少30天的幣可以參與競爭下一區塊,越久和越大的幣集有更大的可能去簽名下一區塊。然而,一旦幣的權益被用於簽名一個區塊,則幣齡將清為零,這樣必須等待至少30日才能簽署另區塊。同時,為防止非常老或非常大的權益控制區塊鏈,尋找下一區塊的最大概率在90天后達到最大值,這一過程保護了網路,並隨著時間逐漸生成新的幣而無需消耗大量的計算能力。點點幣的開發者聲稱這將使得惡意攻擊變得困難,因為沒有中心化的挖礦池需求,而且購買半數以上的幣的開銷似乎超過獲得51%的工作量證明的雜湊計算能力。

權益證明必須採用某種方法定義任意區塊鏈中的下一合法區塊,依據賬戶結餘來選擇將導致中心化,例如單個首富成員可能會擁有長久的優勢。為此,人們還設計了其他不同的方法來選擇下一合法區塊。

NXT幣採用隨機方法預測下一合法區塊,使用公式查詢與權益大小結合的最小雜湊值。由於權益公開,每個節點都可以合理的準確度預計哪個賬戶有權建立區塊。

3)DPoS共識演算法代表:Bitshare & EOS

位元股( Bitshare)是一類採用DPoS機制的密碼貨幣,它期望通過引入一個技術民主層來減少中心化的負面影響。

位元股引入了見證人這個概念,見證人可以生成區塊,每一個持有位元股的人都可以投票選舉見證人。得到總同意票數中的前N個(N通常定義為101)候選者可以當選為見證人,當選見證人的個數(N)需滿足:至少一半的參與投票者相信N已經充分地去中心化。

見證人的候選名單每個維護週期(1天)更新一次。見證人然後隨機排列,每個見證人按序有2秒的許可權時間生成區塊,若見證人在給定的時間片不能生成區塊,區塊生成許可權交給下一個時間片對應的見證人。DPoS的這種設計使得區塊的生成更為快速,也更加節能。DPoS充分利用了持股人的投票,以公平民主的方式達成共識,他們投票選出的N個見證人,可以視為N個礦池,而這N個礦池彼此的權利是完全相等的。持股人可以隨時通過投票更換這些見證人(礦池),只要他們提供的算力不穩定,計算機宕機,或者試圖利用手中的權力作惡。

位元股還設計了另外一類競選,代表競選。選出的代表擁有提出改變網路引數的特權,包括交易費用、區塊大小、見證人費用和區塊區間。若大多數代表同意所提出的改變,持股人有兩週的審查期,這期間可以罷免代表並廢止所提出的改變。這一設計確保代表技術上沒有直接修改引數的權利以及所有的網路引數的改變最終需得到持股人的同意。


4、哪種共識演算法最好?

每一種共識演算法都有各自的應用場景,沒有絕對的好壞之分。到底選擇哪個共識來進行區塊鏈的實施取決於哪類網路和資料。

最近很反感一種現象:很多新區塊鏈一上來就說自己的共識演算法是PoA、PoB~PoZ(a到z的字母都快被用完了),動不動就說是顛覆性的,可實際上還是對以上介紹的幾種共識演算法的模仿或小改造,讓初入區塊鏈行業的人很懵逼,覺得好高大上,純屬嚇唬人。

結束語

歡迎掃碼關注個人公眾號,一起探討技術: