戲說zilliqa共識演算法

最新 07-29

0x.0：有人的地方就有江湖！

話說，民國末期，一幫武林人士來到了一個名叫zilliqa的離島（你可以理解為Hong Kong），在這四面靠海的彈丸之地，勢必要通過拳腳功夫來維持秩序，於是大家提出由功夫最好的n個人來做武林盟主（DS委員會），維護秩序。OK，一場面向全島的功夫pk開始了，大家紛紛施展拳腳（跑pow1），一場有秩序的比拼結束後，n個大佬（DS委員會）產生了。

接下來，就該是老大們劃分地盤了，銅鑼灣，尖沙咀，旺角，油麻地，紅磡等等地盤（也就是zilliqa網路中的shard）總得有人來管吧。OK，大佬們又出招了，咱們當裁判，在一幫小弟裡面再搞一次功夫pk（跑pow2）選出L個大號的馬仔分別管理這L個地盤。

漸漸的，zilliqa建立起了一個動態穩定的有秩系統。為什麼是動態穩定呢？因為：大佬要退休，替大佬們賣命的大號馬仔難免在火併中送命（系統更迭），就像老話說的：三十年河東，三十年河西！

好啦，故事講完了，接下來正兒八經的談談zilliqa網路中所涉及的共識演算法。

0x.1：zilliqa所用到的共識演算法

zilliqa使用到的共識演算法有兩種，一個是pow演算法，也就是bitcoin所用的基於工作量的共識演算法。再者，zilliqa使用了實用拜占庭容錯演算法，也就是官方所謂的pbft。之所以會採用兩種演算法，zillqa給出的原因有幾點：一是，防止女巫攻擊；二是，幫助構建網路；三是，減小系統開銷，將分片的優勢儘可能發揮到極致。

0x.2：pow演算法

從whitepaper來看，zilliqa使用了兩種pow演算法，即pow1和pow2，區別在於計算hash時的參數有所不同，再者就是用途有所不同。

pow1演算法，主要用於DS委員會的產生和DS委員會leader的更迭。從其下圖中的演算法偽代碼可以看出，pow1會從最新的DS區塊中獲取一個隨機數r1以及從最近的TX區塊中獲取一個隨機數r2，nonce和mixHash則是基於公鑰，節點IP以及前期獲取的兩個隨機數r1和r2運算產生。值得注意的是，這一計算過程所採用的是Ethash算，也就是姨太（ethereum）所用的hash演算法。這裡順便回答一下礦主們的疑問：zil怎麼挖礦呢？當然可以用姨太礦機啦，再直白點用顯卡機咯。

接下來，我們就聊聊牛逼哄哄的DS委員會是如何產生的。道家云：「一生二，二生三，三生萬物」。zilliqa的網路也是從無到有的（當然，這都是屁話），那麼，既然要從一大幫的zilliqa節點中產生數百個DS節點（最終是有可能產生數百個節點的哦，我們看好zilliqa），那就得定個規矩，一切按規矩辦事：比誰的算力更強大，並且按照pow1計算速度來排隊，排在前頭的就是DS委員會中的大佬。或許，你會說如果惡意節點當選了怎麼辦。嗯，且聽下回分解！

OK，讓我們再來聊一聊pow2演算法。從下圖中可以看出，pow2演算法需要根據當前的DS區塊生成一個隨機數r，然後根據節點公鑰，IP和所獲取的隨機數r計算nonce和mixHash，隨後將nonce，mixHash，公鑰以及IP地址封包廣播。

DS委員會選出之後，此時網路中其餘非DS節點必須跑一次pow2演算法，當然跑得快的仍然也會有獎勵，也就是獲得成為分片leader的機會。一旦全網DS節點跑完一遍pow2並且向DS委員會廣播後，DS委員會將根據pow2運算結果排序並且將網路劃分為n個分片。

值得注意的是，如果有新節點希望加入zilliqa網路，他可以選擇跑pow1參與DS委員會競爭或者pow2加入到某個分片中。但是，zilliqa給出的whitepaper並未明確說明選擇pow1和pow2在一段時間內是否為互斥操作。也就是說，如果新節點選擇運算pow1且加入DS委員會未果，那麼新節點是否可以立即運算pow2加入某個分片呢？如果是不行，那新節點何時才能計算pow2加入新的分片呢？

0x.3：pbft演算法

公眾號前面轉載的文章已經介紹過pbft演算法，這裡也就不啰嗦了。此外，zilliqa採用EC-Schnorr多重簽名演算法，將pbft的時間複雜度降低到了o(n)，空間複雜度降低到了o(1)，算是一個不錯的優化了，不多說，上截圖。