Wanchain星系共识探索03—出块者选择算法

在上一篇解读文章中，我们介绍了星系共识的整体架构和流程以及随机数生成算法。在共识过程中，节点会组建成两大星群——RNP星群和EL星群，前者负责随机数的生成，在上一篇文章中已进行了详细而形象化的介绍，后者负责打包交易提出区块，而这一工作的核心难点就是解决出块者选择问题，本文将深入介绍EL星群中出块者选择的流程原理和重要作用。

在我们第一篇文章中讲述到，在区块链共识协议中要解决的两个核心问题是出块者选择（Leader selection）和合法链选择（Chain selection），无论在哪种共识协议中，合理的出块者选择都是重中之重，我们设计随机数生成算法引入熵的一个关键作用就是要用于出块者选择。

合理的出块者选择对保证链的 安全性 和 活性 至关重要，一个好的出块者选择算法是共识健康运行的基石。我们先说说 出块者选择对链安全性的意义 ，链的发展延长本质上就是块的不断接续，而完成打包提出区块的就是这些出块者，他们一方面决定哪些交易写入区块进而上链确认，另一方面也通过选择接入的父区块决定着链的发展走向，在网络中共识节点善恶并存的环境下，一个好的出块者选择算法就是要保证诚实节点能够获得更多的出块权，进而主导链的发展。当然，不同的共识协议在不同的安全假设之下，出块者选择算法的设计也是不同的。

• 工作量证明（PoW）的安全假设：50%以上算力安全

在这一安全假设下，PoW采用hash运算的方式进行出块者选择，即节点通过大量hash试算来寻找解决难题的随机数据，也就是挖矿，这一过程中由于hash函数运行结果的不可预测性，任何节点在hash试算上不存在优势，是纯粹算力的竞争，而50%以上安全算力就保证了出块者中大部分是诚实节点，进而保证了链的安全性。

• 类BFT协议的安全假设：2/3以上节点安全

在这一安全假设下，类BFT协议通常采用轮流坐庄或概率选择的方式进行出块者选择，无论采用哪种方式，都必然能够保证诚实节点获得多数出块权，同时要求共识网络中节点必须对提议的区块进行投票，只有获得了2/3以上投票的区块才算最终合法区块，进而保证了链的安全性。

• 权益证明（PoS）的安全假设：50%以上权益安全

在这一安全假设下，PoS协议通过依据节点权益持有量比例随机选取出块者，而这一选择的关键就在于随机性的安全性，保证了随机源的安全就保证了在大量出块者选择过程中诚实节点能够获得多数出块权，进而主导链的发展，保证了链的安全性。

上面通过介绍了常见共识协议在不同安全假设下出块者选择的设计方法，当然也有特殊的混合模式，这里不进行详细论述。由上可见，合理的出块者选择对保证链的安全是极其重要的，我们可以用一个简单的反向例子来直观理解，如果在比特币挖矿中，某个恶意节点找到了挖矿的窍门进而获得了半数以上的出块权，那么他就可以任意的重构链来实现双花等攻击，任何一笔交易都将不再可信，这将是对比特币生态系统的毁灭性打击。

我们再来简单说说 出块者选择对保证链活性的重要意义 。对于活性的定义在不同的解读文章中都有论述参考，我们简而言之，就是链可以持续稳定的发展延长，有效合法的交易经过一段时间可以得到确认。出块者本就担负着链发展建设的重任，很显然他们就是保证链活性的主体，有很多共识模型（如Snow White）对于如何保证链活性都有深入的研究和探索。总体来说，要保证链活性，需要解决两个问题：一是保证出块者活性，被选中的出块者要是活跃的，积极参与共识过程的，而不能是离线或者休眠状态，进而导致大量区块的缺失，影响链的正常发展；二是保证节点间数据一致性，诚实节点必然能够接收到有效合法交易，并诚实的将其打包进入区块上链确认。加上上面对安全性的论述就能保证链的活性。而出块者的活性就要由出块者选择来保证，这一选择是一个广义的概念，并不一定狭义的体现在具体选择算法之中，而是在整体的设计理念里加以考虑，Wanchain的星系共识中对此进行了着重思考，并通过权益概念的全新定义、委托机制的设计和奖惩机制的刺激妥善解决，我们在此不做详细说明，后续解读文章将具体解释。

2.  出块者选择算法需要考虑的几个问题

上面介绍了出块者选择算法的重要性，那在设计一个出块者选择算法时应该重点考虑哪些问题呢，或者哪些性质才是评定一个出块者选择算法好坏的衡量标准呢？

1） 公平性： 出块权是依据共识节点资质均衡分配的。例如PoW中算力越高，获得出块权的机会越大，而PoS中权益持有量越大，获得出块权的机会越大。这是一个很自然合理的性质，但它的外延很广，出块者选择就像博彩，想要实现真正的公平性也需要规避很多问题，我们以一个例子来说明：假设A和B是两个共识节点，通过掷骰子的方式决定谁是出块者，点数为奇数则A获得出块权，为偶数则B获得出块权，公平条件下，骰子是被“上帝”掷出，A和B的机会各一半，而如果A获得了掷骰子的权利，那么公平性就被打破了，他可以多次试验甚至直接摆出奇数点数来霸占出块权，进而独自决定链的发展甚至肆意进行攻击，这是十分可怕的。

2） 可验证性： 出块权的合法性是可以被公开验证的。例如PoW中区块头hash值小于难度值可以被全网运算验证。这条性质是显而易见的必然要求，区块链作为去中心化的系统，其运行必然是接受全网监督认可的，区块的合法性验证是基本要求之一，而区块合法性除了交易合法性和结构的合法性外，出块者的合法性也是必须要被验证的一点，所以任何的出块者选择算法都必须保证出块权的归属是可以被正确验证的。

3） 匿名性： 出块者通过匿名方式隐私参与共识。这条性质并不是必然要求，之所以提出是因为匿名性可以解决共识中可能出现的安全风险，如腐蚀攻击。具体来说，如果出块者在其出块权归属时间之间被全网所知，那么恶意节点有可能通过贿赂等方式将其腐蚀，把原本的诚实节点变成恶意节点，进而进行攻击，甚至直接进行网络攻击导致出块者掉线，这就增强了恶意节点的攻击能力或削减了诚实节点获得的出块权，所以实现匿名性对于共识协议来说也是一个需要考虑的问题，很多项目（如Dfinity、Algorand）大多采用VRF算法来实现匿名性，但VRF也存在其自身的缺陷和弊端，现在也有项目（如Ouroboros Crypsinous）提出使用零知识证明进行匿名共识，但还没有具体实现。

3.  常见的出块者选择算法

介绍过出块者选择算法的重要意义和衡量标准，我们简单列举三个典型的算法来具体了解一下当前常用的出块者选择方式：

1）算力竞争

算力竞争的方式是区块链系统里最早使用的出块者选择算法，最典型的就是比特币系统，是比较简单粗暴又直接有效的方式。共识节点打包交易后，通过不断调整区块头中的随机数来反复运算区块头的hash值，当hash值小于当前区块要求的难度值时就形成了符合要求的合法区块，此时就获得了出块权，成为一名合法的出块者，也就是完成了整个挖矿过程。这种方式的好处就是对于所有参与节点都是公平的，任何节点不会在hash运算上取得优势，只要总体算力超过一半是安全的，那么链就是安全的。同时， 这种方式在同一区块高度可能存在多个合法区块和合法出块者，会出现短暂分叉，这也是比特币系统需要等待确认时间的原因。 目前来看这种出块者选择算法是共识协议中去中心化程度最高的，当然随着技术的发展和研究的深入，挖矿也从最初的cpu挖矿逐步发展到gpu、asic挖矿，算力增长迅速，很多项目为抵抗芯片挖矿通过增加存储要求设计了新的共识协议，如Zcash的Equihash。

2）Verifiable Random Function（VRF）

VRF用于出块者选择算法是为了解决匿名性而提出，具体方式是先设置一个合理的阈值，节点利用自身的私钥对某一随机数据进行运算（如签名），得到的结果小于设置的阈值则为合法出块者，获得出块权。这一过程中由于私钥运算只能节点自身进行，保证了其他节点不能获知出块权归属，而计算结果如签名结果可以被公开验证，确保了出块权合法性可以被验证，形成了完整的出块者选择过程。显然，这种方式是概率性的，若想某一区块高度可以有尽量多的合法出块者，就需要尽量提高阈值，反之想要某一区块高度可以有尽量少的合法出块者，就需要尽量降低阈值，这对阈值的设置就有极高的要求，同时对私钥运算结果的分布也要有较好的预期，这往往是很难做到的，就 容易出现某一区块高度有大量合法出块者而形成密集分叉，某一区块高度没有合法出块者而形成空白， 所以VRF算法虽然解决了匿名性问题，但在具体使用中仍然存在难以避免的问题。

3）follow-the-satoshi

follow-the-satoshi是PoS中常见的一种出块者选择算法，具体方式是将所有的代币进行 排序 编号，通过一个随机源产生一个随机数，这个随机数落到了哪个代币的编号上，那么这枚代币的持有者就是合法的出块者，获得了出块权。这种方式显然是唯一确定性的， 难点就在于如何找到一个安全的随机源来产生真随机数。 Cardano项目当前就采用了follow-the-satoshi的方式进行出块者选择，其随机数的生成使用了多方计算、门限秘密分享等多种密码学技术，保证了随机源的安全性，但在出块者选择的匿名性上还没有实现。但就随机数生成而言，另一种方式就是使用链上的某段历史数据的hash值，其中以Algorand为代表，将之前某个区块的数据和当前区块高度进行混合运算hash值作为随机数，算是一个较好的伪随机源，但仍有被刻意控制的风险。关于随机数的生成和相关性质这里不再过多论述，感兴趣的读者可以参考上一篇解读文章。

4.  Galaxy ULS算法原理流程

  兜兜转转介绍了这么多，最后还是要回到我们的主题，Wanchain星系共识的出块者选择算法——ULS算法，ULS代表的是unique leader selection，即唯一出块者选择，ULS算法在设计之初就考虑到了公平性、可验证性和匿名性，采用了秘密分享、零知识证明等多种密码学手段， 实现了固定时间窗口内的唯一合法出块者的匿名选择，在保证链安全性的基础上，尽量降低短分叉几率，提升共识效率， 下面我们就形象化介绍星系共识ULS算法的整体原理流程。

1）EL星群选择

EL星群节点是运行ULS算法的主体，那我们就从EL星群的来源说起，在星系共识的第一篇解读中有简短介绍，这里我们再进行一次详细说明。在PoS协议中，话语权由权益持有量决定，而我们将这一对应关系在EL星群的选择过程中进行实现。基于Wanchain共识合约中当前Committee的质押状态，可计算每个节点的权益值和其权益比例，利用Random Beacon提供的随机数，运行follow-the-stake-ratio算法，类似于follow-the-satoshi的过程，形象地说，就是Committee中节点按照其权益比例划分了一块钟表的表盘，每个节点拥有一段与其权益占比相同的时间窗格，然后随机数就是拨动时间指针的上帝之手，指针落到哪个时间窗格，此窗格的拥有者就被选入EL星群，每轮选择独立进行，某一节点有可能被多次选入，所以最后EL星群有可能是一个多重集，选出的EL星群将肩负起运行ULS算法的责任。

2）秘密消息序列（Secret Message Array）生成

EL星群被选择组建之后，需要先进性一次链上的通信协商，这一过程是为了在星群内部生成一个秘密消息序列，用于后续出块权分配，是我们实现匿名性的关键一步。为保证秘密消息序列不会被某些恶意节点控制，进而影响到后续算法运行，我们将这一过程拆分成两个阶段，也就是SMA1和SMA2。在SMA1阶段，星群中每个节点选择一个随机数，将其利用自身公钥加密后发送到链上，完成对随机数选择的承诺，保证任何节点选定的随机数在后续阶段不可更改。在SMA2阶段，星群中每个节点将自己选择的随机数用所有节点（包括自身）的公钥加密发送到链上，同时提供协调性证明（DLEQ proof），这里对照在SMA1阶段利用自身公钥加密的数据就可确保随机数并未更改，同时协调性证明保证了所有公钥加密的都是同一个随机数。这一阶段完成后，所有EL星群节点都可以自行解密，得到随机数据序列，也就是我们的秘密消息序列，准备运行出块权分配算法。

3）EL星群节点排序

秘密消息序列生成后，随机数进行更新，新产生的随机数将作为种子对EL星群节点进行排序，具体方式就是将星群节点公钥与随机数接续进行hash运算，基于运算结果进行升序排列，这一排序结果将用于后续出块权分配。显然，排序是在秘密消息序列后基于新随机数进行的，任何节点无法影响，完全是随机的排序结果。

4）出块权分配

在上述三项工作完成后，就可以为EL星群节点进行出块权分配。在之前的解读中我们说过，一组EL星群负责一个epoch内区块的生成，那么这个epoch内每个slot的出块权如何决定呢？首先将当前随机数和epoch编号和slot编号进行hash运算，运算结果取EL星群节点数量的模结果，如hash值是2019，目前EL星群节点数量50，取模结果就是19，那么EL星群节点排序中的第19位即被选为合法出块者，获得出块权。这一选择过程是等概率进行的，结合EL星群节点选择时的按权益比例进行，确保了出块者选择是按权益持有量合理进行的，确保了公平性；合法出块者在提出区块时需要提供合法性凭证，这一凭证可被公开验证，确保出块合法性的可验证性；合法出块者选择中使用了秘密消息序列，而这一消息序列只在EL星群内部共享，其他节点不可知，就保证了选择过程的匿名性。 由此可见，ULS算法的是全面考虑了公平性、可验证性和匿名性的创新 性设计，将对保证链的安全性和活性起到重要的积极作用。

以上简单介绍了星系共识的出块者选择算法——ULS算法，详细内容在星系共识论文中有着具体的描述，在后续的星系共识探索中我们会再深入介绍星系共识设计中其他的精彩内容，敬请期待。