从随机信标和其他策略中选举领导者

区块链设置中的领导者选举旨在选择将确定要附加到区块链的下一个块的参与者。 通常，从一组验证器中为每个槽选择一个验证器，并有权在该槽中使用新块扩展链。 （我们假设验证者保持准确的时间并就当前时隙号达成一致。）在本文中，我们探索了以下策略 随机领导选举 在共识协议中。 （有关一般随机性的更多信息，请参阅我们之前的文章， 公共随机性和随机性信标，其中 我们研究了用于生成可公开验证且不可预测的随机性的独立协议。） 

为什么领导人选举很重要

选举诚实和积极的领导者对于连锁店的健康发展至关重要。 恶意验证者不应该能够使领导者选举过程产生偏见，以更频繁地让自己成为领导者。 否则，区块的生产可能会落入可以审查交易或完全停止区块链的各方手中。 在最长链式共识协议中，领导者产生无效块（或根本没有块）可能导致链暂时分叉。 在拜占庭容错式共识协议中，糟糕的领导者会触发一个视图更改子协议，这会产生通信开销。 

委员会选举备选方案

委员会选举是一个相关的问题，其目标是选择一些固定大小的验证者的均匀随机子集 k. 这个功能本身就很有用，因为区块链设置中经常需要小组委员会来减少验证器集的大小，从而使共识运行得更快（许多例子是 Algorand 的排序 和 以太坊的委员会选择). But committee election is also useful for leader election, allowing the validators to avoid re-running a leader election protocol if the elected leader fails to show up. 如果以固定顺序选举委员会而不是领导者，则如果第一个委员会成员不可用，则第二个委员会成员可以成为领导者。 

一个好的选举协议的属性

在领导人选举协议中，领导人应该是不可预测的。 如果攻击者知道即将到来的领导者是谁，它可能会对他们发起拒绝服务 (DoS) 攻击以阻止他们发布区块。 攻击者然后可以取消下一位领导者等等，使区块链停止。 不可预测性也可能会得到加强，以确保验证者本身不会知道何时会领先，这对于防止贿赂可能很重要。

Leader选举过程应该具备以下三个属性：

• 公平：每个诚实验证者的概率为 1/N 从一组中选出 N 验证器（一个宽松的概念 博弈论公平允许 即使在恶意多数存在的情况下也能建立领导人选举，尽管轮数下限不固定）。
• 不可预测性：对手直到一段时间才知道下一个领导者 T 在领导者宣布下一个区块之前。
• 唯一：在每个时隙中只选择一个领导者。

秘密领导人选举

秘密领导人选举是一个不可预测的选举 T = 0。在这个过程中，领导者在发布区块之前不为任何人所知。 这完全消除了 DoS 攻击的窗口：在领导者暴露自己之前，攻击者不知道要攻击谁，使其最佳策略成为随机猜测。 而在领导者发布其区块后，再进行攻击已经来不及了，因为领导者已经履行了对协议的责任。 

“在领导者发布其区块之后”的概念实际上是一种简化，因为我们在现实世界中没有即时广播。 具有强大网络地位的攻击者可能会注意到领导者首先广播一个块，并且能够迅速破坏领导者，创建一个不同的块，并抢先运行原始广播。 

虽然这是一个非常强大的攻击模型，但已经提出了针对它的防御措施。 Algorand 提出了 擦除模型，其中领导者实际上能够擦除在其槽中签署区块所需的密钥 before 广播它，所以当领导者采取任何公开行动时攻击真的太晚了。 麻省理工学院媒体实验室的三位研究人员 Thaddeus Dryja、Quanquan C. Liu 和 Neha Narula， 建议 领导者在广播之前在其区块上计算 VDF，以确保自适应攻击者无法及时构建替代有效区块以使其接受所需时隙。

其他选举方式 

最简单的领导人选举过程是 轮循，其中领导者是按确定性顺序选出的。 尽管这种方法是可预测的，因此容易受到 DoS 攻击，但它适用于验证器具有良好 DoS 保护的许可系统。

领导者也可以使用外部的输出来选举 随机信标，如果一个可用并且被信任是安全的。 不幸的是，共识参与者自己运行分布式随机信标 (DRB) 协议是很棘手的，因为这些协议通常假定可靠广播或共识的概念，而这又需要再次选举领导者，从而引入循环依赖。

电流 以太坊领导人选举 是一个很好的案例研究。 每个新领导者计算一个可验证随机函数 (VRF) 输出（纪元号上的 BLS 签名）并将该值异或到混合中。 epoch结束时mix的价值 i 定义纪元期间的领导者和小组委员会 i+2。 领导者和他们的日程安排可以提前一个纪元（目前约 6.4 分钟）预测。 该协议容易受到公平性攻击，因为最后一位领导者可能会选择公布或保留他们对混合的贡献，从而对下一次选举的结果产生一点影响。 如果最后  k 领导勾结，他们可能会介绍 k  偏见，使恶意用户的选举更有可能。 以太坊基金会正在积极研究更先进的领导人选举技术，我们将在下面讨论。

基于 VRF 的领导人选举

另一种方法，由 Algorand，是一个 基于 VRF 的领导人选举，其中涉及每个验证器私下计算 VRF 输出并检查输出是否低于阈值。 这个过程已经过滤掉了大部分验证器，因为选择的阈值不太可能低于它。 剩下的少数几个验证者显示他们的 VRF 输出，并且 VRF 值最低的验证者被选出。 这种方法实现了完美的不可预测性（或保密性），但不保证唯一性。 一些验证者可能没有收到来自所有潜在领导者的消息，并可能认为错误的领导者赢得了选举，导致这些验证者从主链中分叉。 

VRF 评估定期使用随机信标的输出播种，以降低验证者自己查看他们将领先于哪个时隙的可预测性。 此属性可防止攻击者在验证者成为领导者时悄悄地破坏验证者学习时隙，并在验证者即将宣布区块时发起攻击。 这种方法还有助于防止贿赂攻击，在这种情况下，验证者向外部各方证明它将成为特定时隙中的领导者，并收受贿赂以换取作为领导者完成某些任务（例如，阻止交易）。

这种方法，其中当选的领导人的数量是一个随机变量，被称为 概率领导选举 （请）。 PLE 可能导致没有领导者被选为给定的插槽。 这相当于选举了一个恶意或离线的领导者，因为插槽最终将被跳过，从而降低共识协议的效率。

但是 PLE 最大的警告是可能会选举出多个领导者，因此需要某种打破平局的程序。 平局会给达成共识带来风险，因为拥有获胜输入的验证者可能仅将其报告给网络的一半，这可能会导致所选领导者的分歧。 此外，解决关系的过程可能需要额外的时间和沟通，从而影响效率。 Dfinity, 在中更详细地讨论 第一个帖子 在本系列中，使用基于 VRF 的随机信标来选举单个领导者； 但是，这样做会牺牲不可预测性。 理想情况下，任何选择领导者的过程都应该完全避免联系并且仍然是不可预测的，这将我们带到了这个研究领域的圣杯——单一秘密领导者选举。

单一秘密领导人选举 

的目标 单一秘密领导人选举 (SSLE) 是从一组验证器中选择一个独特的领导者，同时保持公平性和不可预测性。 Protocol Labs 将这个概念描述为 研究问题，斯坦福大学计算机科学家兼 a16z 密码研究顾问 Dan Boneh，以及 Saba Eskandarian、Lucjan Hanzlik 和 Nicola Greco，后来提出 SSLE 的正式定义. 这种唯一性避免了打破平局程序产生的共识风险和效率成本。 具体来说，协议实验室的 Sarah Azouvi 和都灵理工大学的 Danielle Cappelletti， 显示 与最长链协议中的 PLE 相比，当使用 SSLE 时，区块的最终确定速度要快得多（如果对手控制三分之一的股份，则速度要快 25%）。 因此，开发实用的 SSLE 协议是一个重要的问题。

在最常见的方法中，我们称之为 基于洗牌 （用于原始 SSLE 论文和 以太坊 SSLE 提案), 每个验证者注册一个 教廷大使 看起来很随意，但他们可以证明属于他们。 然后将随机数编译成一个列表。 该列表被打乱，使得随机数与提交它们的验证者断开链接； 也就是说，给定随机列表，没有对手可以分辨出哪个验证器提交了哪个随机数。 然后根据公众选择列表索引 随机信标，并且领导者通过证明洗牌列表的那个索引处的随机数属于他们来揭示自己。 

由于只选择了一个索引，因此基于混洗的协议总是输出一个 独特 领导者。 因为随机信标是为了输出统一的随机值而构建的，所以协议也是 公平: each validator has an equal chance of being elected. 此外，如果改组正确（即，均匀随机）并且随机数变得无法链接到验证者的身份，则该协议还实现了 不可预测性.

洗牌是必要的，因为虽然简单地从基于随机信标的未洗牌列表中选择一个索引已经提供了唯一性和公平性，但不可预测性更难实现：如果对手知道哪个验证者提交了哪个随机数，它就知道谁在选定的位置提交了随机数索引并可以识别领导者。 

以下两种方法以不同的方式对列表进行洗牌。 更简单的是 以太坊 SSLE 提案，其中， n 验证者通过 Tor 提交他们的随机数，以取消验证者身份与其随机数的链接。 一旦所有验证者都注册了，就会使用公共随机信标对列表进行洗牌，然后验证者按照洗牌列表的顺序成为领导者。 虽然这个方案是可行的——选举必须只运行一次 n 插槽——这种对 Tor 的依赖可能是不可取的（就像依赖任何外部协议的安全性一样）。 此外，它并非完全不可预测：在第一个之后 n-1 首领现身，决赛 nth 领导者是众所周知的。

原始的 SSLE 论文没有使用 Tor，而是通过将其随机数附加到列表、打乱列表、以及 重新随机化 随机数。 这种重新随机化意味着每个随机数都被映射到一个新的、不可链接的字符串，这样它所属的验证者仍然可以证明对重新随机化的随机数的所有权。 假设至少有一个洗牌器是诚实的，重新随机化使得对手无法分辨任何特定随机数在洗牌后最终处于哪个位置。

虽然原始 SSLE 论文中的这种顺序洗牌方法避免了对 Tor 的依赖并实现了 SSLE 的形式属性，但它是昂贵的：每当新的验证者注册时，他们必须将整个洗牌列表发布到区块链，重新随机化所有随机数，并且提供他们诚实地这样做的证据，这导致每个验证者的线性通信量。 对于一组不变的验证者，每次选举都必须完成（摊销）一次，因为领导者一旦透露了 nonce 的证明就会重新注册。 该论文给出了一个可调的效率-可预测性权衡：如果我们愿意允许少量的可预测性，我们可以改为只洗牌列表的较小子集，从而降低成本。 在效率和安全性之间取得良好的平衡具有挑战性，因此，SSLE 协议尚未在实践中得到广泛应用。 

方便地，这种顺序洗牌方法也可用于解决委员会选举问题，通过使用随机信标从列表中选择 k 个不同的索引作为委员会成员。 这是一个很好的成就，因为基于 VRF 的方法无法轻松解决该问题，因为运行基于概率 VRF 的协议 k 时代可能会根据随机性选择不同的委员会规模。 

SSLE 的其他方法

另一种基于洗牌的方法是 来自 DDH 的自适应安全 SSLE. 这种结构稍微复杂一些，但实现了更强的安全概念，防止 自适应对手 在 Algorand 的擦除模型中. 这个对手是自适应的，因为它可以选择在协议期间破坏哪些验证器，而不是在协议开始之前。 

SSLE 的另一个挑战是以与其权益成正比的概率选出每个验证者，而不是均匀地随机选择。 基于混洗的协议可以天真地通过允许每个验证者注册多个随机数来实现这一点：一个随机数代表他们持有的每个权益单位。 然而，洗牌的成本随着权益单位的数量线性增加 S，即使对于现实的股权分配来说也变得非常昂贵。 优雅的 基于 MPC 的 SSLE 方法的复杂性仅随日志增加 S，它还避免了对可信设置或随机信标的需要。 However, compared to shuffling-based approaches, it requires more rounds of communication (logarithmic in the number of participants) per elected leader

***

我们在这张方便的表格中总结了我们的分析。

	公平	不可预测性/ 保密*	唯一
循环	✓	✗	✓
理想的随机性信标	✓	✗	✓
以太坊的领导人选举（当前）	✗	✗	✓
基于 VRF 的领导人选举 (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* 循环信标是完全可预测的，但在其余信标中 ✗ 意味着这个概念在一定程度上得到了实现： ideal-randomness beacon 是不可预测的，但敌手与当选的领导者同时学习输出，因此当选的领导者可能在宣布区块之前受到攻击； Etherum 的信标在大约 6 分钟内是不可预测的，并且可能会略有偏差以损害公平性； Algorand 以很小的概率选出多个领导者。

SSLE 是一个很有前途的方向，实现了公平性、不可预测性和唯一性。 它的采用面临的两个突出挑战是效率和适应不均匀股权分配的能力。 此外，我们强调的基于混洗的 SSLE 方法假设存在无偏随机信标，这在实践中并不容易实现。 由于 SSLE 最近才被正式定义，我们很可能会在不久的将来看到改进的协议来应对其挑战。 

***

米兰达基督 是哥伦比亚大学计算机科学专业的博士生，她是理论小组的成员和总统研究员。 她还是 a16z crypto 的研究实习生。

约瑟夫·波诺（Joseph Bonneau） 是 a16z crypto 的研究合作伙伴。 他的研究重点是应用密码学和区块链安全。 他曾在墨尔本大学、纽约大学、斯坦福大学和普林斯顿大学教授加密货币课程，并获得了剑桥大学的计算机科学博士学位和斯坦福大学的学士/硕士学位。

瓦莱里娅·尼古拉连科 是 a16z crypto 的研究合作伙伴。 她的研究重点是密码学和区块链安全。 她还研究了 PoS 共识协议中的远程攻击、签名方案、后量子安全和多方计算等主题。 她在 Dan Boneh 教授的指导下获得了斯坦福大学的密码学博士学位，并作为核心研究团队的一员从事 Diem 区块链工作。

***

责任编辑： 蒂姆·沙利文

***

此处表达的观点是引用的个人 AH Capital Management, LLC (“a16z”) 人员的观点，而不是 a16z 或其关联公司的观点。 此处包含的某些信息是从第三方来源获得的，包括来自 a16z 管理的基金的投资组合公司。 虽然取自被认为可靠的来源，但 a16z 并未独立验证此类信息，也不对信息的持久准确性或其对特定情况的适用性做出任何陈述。 此外，该内容可能包含第三方广告； a16z 未审查此类广告，也不认可其中包含的任何广告内容。

此内容仅供参考，不应被视为法律、商业、投资或税务建议。 您应该就这些事项咨询您自己的顾问。 对任何证券或数字资产的引用仅用于说明目的，并不构成投资建议或提供投资咨询服务的要约。 此外，本内容并非针对也不打算供任何投资者或潜在投资者使用，并且在任何情况下都不得在决定投资于 a16z 管理的任何基金时作为依据。 （投资 a16z 基金的要约仅通过私募备忘录、认购协议和任何此类基金的其他相关文件提出，并应完整阅读。）任何提及、提及或提及的投资或投资组合公司所描述的并不代表对 a16z 管理的车辆的所有投资，并且不能保证这些投资将是有利可图的，或者将来进行的其他投资将具有类似的特征或结果。 由 Andreessen Horowitz 管理的基金进行的投资清单（不包括发行人未允许 a16z 公开披露的投资以及对公开交易的数字资产的未宣布投资）可在 https://a16z.com/investments 获得/。

其中提供的图表仅供参考，在做出任何投资决定时不应依赖。 过去的表现并不预示未来的结果。 内容仅在所示日期生效。 这些材料中表达的任何预测、估计、预测、目标、前景和/或意见如有更改，恕不另行通知，并且可能与他人表达的意见不同或相反。 有关其他重要信息，请参阅 https://a16z.com/disclosures。