戏说zilliqa共识算法

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)，算是一个不错的优化了，不多说，上截图。

至于优化后的pbft算法，大家可以理解为，分片leader对马仔们说：“小弟们，都揣家伙了吗？揣了家伙的，报数！”。一旦确认分片中2/3以上的小弟揣了家伙，leader就要带上马仔们冲了（提交微区块，即micro-block）！

—————————————————————————————————

您可以通过以下方式关注Zilliqa官方最新动态：

twitter:https://twitter.com/Zilliqa

Blog:https://blog.zilliqa.com/

Reddit:https://www.reddit.com/r/zilliqa

Slack:https://invite.zilliqa.com/

Gitter:https://gitter.im/Zilliqa/

电报群:https://t.me/zilliqach

微博:https://www.weibo.com/zilliqa

PS: