论文阅读LaKSA: A Probabilistic Proof-of-Stake Protocol_区块链

这篇文章2021年发布在Network and Distributed Systems Security (NDSS) Symposium (CCF B)，新加坡科技与设计大学的Daniel Reijsbergen为第一作者。

摘要

我们提出了大规模的已知委员会股权协议(LaKSA)，这是一种基于链的股权证明协议，不局限于加密货币的应用。LaKSA通过轻量级委员会投票最大限度地减少节点之间地交互，从而产生比竞争系统更为简单、更为健壮和更具有可扩展性的提案。此外，LaKSA减轻了以前系统的其他缺点，例如奖励差异过高和确认时间过长，LaKSA通过设计大量的支持节点，并提供概率安全保证，其中客户端通过基于其区块链视图计算事务被还原的概率来做出提交决策。最后，我们对LaKSA进行全面的分析，阐述了其实验和评价，证明了该技术可以广泛应用于其他PoS协议。

引言

比特币的创新之一即中本聪共识(NC)用于维护区块链的分布式数据结构，在NC中每个参与节点都试图解决PoW难题来成为轮领导者，如果能找到解决方案，节点会宣布一个包含指向前一个块的哈希连接的块、PoW难题的答案、交易和元数据。通过遵循最长链规则来解决潜在的网络分叉，在这个非交互式的leader election过程中，一个块充当交易的媒介，作为一个容易被其他节点验证的领导者选举证明，并作为所有先前块的确认。NC协议可以扩展到许多块，但节点数目过多导致传统的BFT共识协议无法处理，因此也突出了NC的局限性：巨大的能量足迹、低吞吐量、依赖于没有大规模对抗行为的缓慢且不安全的块提交过程。此外，它的奖励频率和结构鼓励中心化，这一点放大了它的安全漏洞。

**权益证明协议(PoS)**可以减轻以上的一些缺点，因为在PoS中节点不根据算力进行投票，而是根据权益即区块链代币。在 PoS 中，新节点需要从现有节点获得权益——尽管这比比特币的完全无权限设置更具限制性，但 PoS 系统承诺多重好处。主要好处是减少了能源消耗，因为投票通常基于仅依赖短消息而不是资源密集型 PoW 谜题的加密彩票。有趣的是，由于参与节点及其权益是预先知道的，这些系统还承诺更快地提交块并具有更好的安全属性，即与标准 BFT 协议中的属性相似的属性。

然而，新的 PoS 方案的设计存在许多障碍。最近的几个系统尝试在 PoS 设置中应用最长链规则。这些提议模仿了 Nakamoto 的设计决策，这些决策引入了不希望的影响，例如鼓励集中化的高奖励差异。此外，尽管它们在概念上类似于 NC，但事实证明，用密码原语取代基于 PoW 的投票同时避免基本限制是极具有挑战性。例如，在 NC 中，同时在两个分支上处理 PoW 谜题的成本很高，因为节点最终将失去对失败分支的投资。然而，在 PoS 中对多个冲突的分支进行投票的成本是微不足道的——这被非正式地称为无风险问题。同样，在 PoS 设置中更容易发起远程攻击，在这种情况下，攻击者获得了大部分股权的节点的密钥，并创建了一个长的替代链。

在我们的工作中，(LaKSA)协议是一种PoS 协议，它解决了上述限制，同时在概念上保持简单并且没有类似 BFT 的消息复杂性。其中，委员会成员是伪随机和定期抽样的，通过投票支持它们对主链的首选观点，这些投票的证据包含在区块中，用户可以自行决定是否提交区块并对区块的交易采取行动，例如收到加密货币付款后发送包裹。

在LaKSA中，客户根据有多少票支持该块及其后代来计算该块可以恢复的概率，如果概率足够低就提交该块。我们展示了具有固定大小的伪随机委员会的设计的好处，虽然给自适应攻击者带来了漏洞，但我们讨论了如何用现有的网络级匿名技术来减轻这种威胁。通过降低委员会成员之间的互动程度，LaKSA可以扩展到大量活跃的参与者。奖励和参与节点的高频率块相结合，减轻了NC集中化的趋势。LaKSA的链选择算法目的在于收集尽可能多的视图信息，从而带来更高的安全性和更快的提交决策。CAP定理限制了分布式系统在们面对网络分区时选择可用性或者一致性，LaKSA重视可用性而不是一致性；然而在LaKSA中，分区的客户会注意到他们对链的看法，并没有为他们提交决策提供强有力的安全保证——通过假设验证使用得到了证明。

LaKSA增加了一个公平和联盟安全的奖励方案，是许多方案所忽略的，我们通过和Algorand(PoS)的详细比较强调了LaKSA对于主要设计选择的影响。Algorand 类似 BFT 的区块承诺方案侧重于单个轮次，而 LaKSA 聚合来自多个轮次的信息，因此在每个用户能够设置自己的安全阈值的意义上实现了更高的安全性和灵活性。我们彻底分析了我们的系统，通过实施展示了 LaKSA 的效率和可部署性，并讨论了替代设计选择和扩展。

贡献

LaKSA引入了一种新颖的链选择机制和概率提交规则通过统计假设检验应用进行分析。
可知LaKSA是第一个具有固定大小的伪随机委员会的具体协议，在和相关工作进行对比突出了LaKSA的优势。
最后，密码采样程序也是一个创新。

预备条件和要求网络和威胁模型

我们的系统由多个对等节点组成，这些节点寻求就分布式账本的状态达成共识。节点相互不信任，具有完全相同的权限和功能——即，没有节点或任何子集是可信的。节点由其唯一的公钥标识，为了避免 Sybil 攻击，我们假设节点需要在底层加密货币方面参与。我们假设节点的权益是总权益 n 的整数，初始节点集及其权益分配是在所有节点都知道的创世块中预定义的，权益分配由公钥与其对应权益单位之间的映射表示。该系统由希望进行加密货币交易且不一定参与共识协议的客户使用。

我们假设参与节点的时钟同步松散，因为协议在定时轮次中取得进展，节点通过点对点网络连接，在网络同步期间，消息在 Δ 秒内传递。我们假设一个部分同步的通信模型，其中网络可以与随机网络延迟异步，但同步最终会在称为全局稳定时间（GST）的未知时间段后恢复。我们通过假设在异步期间进一步限制这一点，尽管攻击者可以存在于所有现有的分裂中，但攻击者不能自适应地在分裂之间移动节点而不被检测到。

我们模型中的对手能够控制拥有 f = αn“恶意”权益单位的节点，对于任何 α ∈ [0, 1/3)，其中 n 表示权益单位的总数；因此实节点拥有 n - f = (1 - α)n 个权益单位。这里f 和 n 都是整数，对抗节点可以是拜占庭节点即它们可以根据对手的意愿失败或模棱两可的消息。我们假设 α < 1/3 在我们的对手模型和网络模型中都是一个界限。我们假设攻击者的目标是 a) 停止协议的进程，或 b) 使不妥协的客户端提交一个交易，该交易被恢复的概率高于客户端指定的阈值 p*。我们还讨论了旨在破坏其他协议属性的对抗策略，例如效率、吞吐量和公平性。

在我们的模型中，诚实节点忠实地执行协议，但可以离线，这意味着它们的块和消息不能被网络的其余部分接收。一个节点可能由于网络故障或由于其客户端由于软件或硬件故障而处于非活动状态而离线。此类故障通常是暂时的，但也可能是永久性的——例如，如果节点丢失了与其权益关联的私钥。为了让 LaKSA 满足下面讨论的活性属性，我们要求诚实节点在 GST 之后在线。根据 BFT 协议，在 GST 之后离线的任何节点都与对抗节点分组，诚实节点的暂时不可用会减慢块提交的速度，因为如果块提议者收到的选票较少，则对块的支持积累得更慢。然而，正如我们在第五节中讨论的那样，离线节点不会产生安全故障——即一个已提交的块被恢复是更有可能的。

所需属性

首先，我们需要两个基本属性：
Liveness
发送到网络的有效交易最终会添加到全局分类帐中并由所有客户端提交
Probabilistic Safety
如果对于客户端指定的概率 p∗ ∈ [0, 1]，客户端提交了一个事务，那么这个事务被还原的概率最多为 p∗
LaKSA 与传统的 BFT 协议不同，我们对安全性的定义是概率性的，宽松的安全属性使我们能够将系统扩展到成千上万的活跃参与者，并提出一个简单、健壮和高吞吐量的系统，同时仍然实现强大的客户端甚至特定于交易的安全性。
当我们在开放的加密货币环境中展示我们的工作时，我们还旨在实现以下附加属性。
Scalability
系统可以扩展到大量的节点
High Throughput
系统应该为交易提供高吞吐量，特别是共识机制不应该成为这种吞吐量的瓶颈
Efficiency
系统引入的开销应该是合理的，允许系统像今天一样部署在 Internet 上，而不需要强大的设备或资源
例如 CPU、内存和带宽
Fairness
一个拥有总股份 β 部分的诚实节点，应该在区块链的主链中存在大约 β，当区块链中的存在被转化为系统奖励时，这一点尤其重要。
Coalition Safety
任何具有总权益 α = ∑ αi 的节点联盟，其中 αi 是联盟节点的权益，对于一些小的 ε，不能获得超过总系统奖励的乘法因子 (1 + ε)α。

加密符号

我们做出标准的密码学假设，并使用以下密码学结构。
H(m) 是一个抗冲突的密码散列函数，为消息 m 生成一个散列值；
PRFk(m) 是一个键控伪随机函数（PRF），为键 k 和消息 m 输出一个伪随机字符串；
Signsk(m) 是一种签名方案，对于密钥 sk 和消息 m 产生相应的签名 σ ；
VrfySignpk(m, σ ) 是一个签名验证过程，如果 σ 是 m 在公钥 pk 对应的密钥下的正确签名，则返回 True，否则返回 False。

协议 A. Blockchain Structure

LaKSA通过区块链进行 *** 作，每个区块都包含一组交易、到前一个区块的链接以及各种元数据，块的结构如下：

其中， i 是整数，ri 是领导者生成的随机值；
H(B-1) 是前一个有效块的哈希值，块通过它编码父子关系；
V 是支持前一个区块的一组投票（见公式 2）；
F 是一组领导者先前已知的块中，都没有报告过的分叉块；
Txs 是包含在区块中的一组交易；
pk 是领导者的公钥；
σ 是一个签名，由领导者在除 pk 之外的所有先前字段上创建。

每个区块B支持它的前继块B-1通过节点投票选定在B的回合中B-1是它们首选链上的最后一个块，投票结构如下：

i是回合数；H(B-1) 是前一个有效块的哈希值；s是投票创建者被选为第i轮投票者的权益；
从本质而言，投票编码了一个权益单位，选民在给定的一轮中通过该权益单位支持选民的区块链观点。
由于我们的区块链包含遵循父子关系的块并且可能包含分叉，因此最终呈现的数据结构本质上是一棵树（参见图 2 中的示例）。然而，在这棵树中，只有一个分支被认为是交易严格排序的主链。交易由希望转移其加密代币或执行更高级别逻辑（例如智能合约）的区块链节点发起，交易通常还包括支付给回合领导者的费用，以将其附加到区块链中。

B. Voting Round

该协议从创世块引导，并在两轮中取得进展。这两个步骤各持续 Δ 秒，其中 Δ 如第 II 节中所定义——为简洁起见，我们将 Δ 视为所有延迟的界限，包括消息生成和处理时间。

每一轮的投票程序在 Alg. 1. 在第 i 轮开始时，每个节点获取该轮的伪随机信标 r，并确定投票者和领导者。在第 III-F 节中，我们展示了RoundBeacon信标生成的具体实例，并讨论了实现它的替代方法。在任何第 i 轮的第一步中，每个节点通过调用 VoterStake() 来检查它是否可以在第 i 轮投票，该函数返回它可以在第 i 轮投票中使用的权益单位的数量。如果返回正数，则该节点在第 i 轮中被称为投票者，它可以投票支持它认为是主链的最后一个区块以支持该链。为此，它创建了一个投票 v（参见公式 2）并将投票立即广播到网络。

其他节点通过检查
a) 它是否是真实的、格式正确的，而不是来自未来的，即不具有超过 i 的整数，
b) 它指向一个有效的前一个块，
c) 投票者来验证每个收到的投票是合法的，即 VoterStake() 返回声明的正股份数量。验证成功后，投票将添加到直接支持其前任区块的待决投票列表中。这些投票创建了一个所谓的虚拟块，由收集但尚未包含的投票组成，一个虚拟块可以支持另一个虚拟块；我们将在 § III-D 中进一步讨论这个问题。
在等待 Δ 秒收集和验证选票后，节点执行该轮的第二步。首先，节点检查 LeaderStake() 函数的输出，如果结果为正，则该节点是该轮的领导者。如果是这样，则节点确定主链 - 请参阅第 III-D 节中的详细信息。然后节点创建并传播一个新块，该块具有主链的最后一个块（可以是虚拟块）作为其前身，其中包括所有收集的选票和生成的随机值 ri . 恶意领导者可以审查——即拒绝包括——投票，但我们使用第 III-G 节中描述的激励机制来阻止这种攻击。
接收新块的节点验证
a）它是否真实、格式正确，而不是来自未来，
b）它指向一个有效的前一个块，
c）投票是否正确，
d）领导者是否合法，即 , LeaderStake() 返回一个正值。如果该块被验证，则将其附加到其相应的链中。除了指向前一个区块外，其区块中的领导者还会列出所有已知分叉，这些分叉在之前的区块中未报告，包括其他区块的待决投票。我们在§ III-C 中提出了选民/领袖选举的具体实例。 LaKSA 也可以通过其他程序来实施（例如，基于 § F 中讨论的 VRF），只要节点按照其持有的股份比例充当领导者和选民。我们不限制每轮节点的角色，即节点可以在给定的一轮中既是投票者又是领导者，或者只扮演其中一个角色，或者不扮演任何角色。

C. Leader and Voter Election

我们提出了一种选举领导人和选民的方法，该方法基于 Alg. 2中提出的一种新颖的密码抽样方法。此方法创建一个包含所有权益单位的数组，并从中伪随机抽样一部分。该方法使用唯一生成的 PRF 输出对权益单位进行采样。在一轮中，leader 和 voter 选举应该是独立的，因此 Sample() 函数需要一个角色参数——分别为“lead”和“vote”——来随机化这两个选举的 PRF 输出。该函数返回一个抽样公钥列表——每个密钥对应一个权益单位——并由输出列表的大小参数化。在下文中，q 表示每轮投票委员会从总质押 n 中选出多少质押单元，l 是领导者数量的类似参数。 VoterStake() 和 LeaderStake() 函数运行 Sample() 并返回给定公钥在抽样股权中出现的次数。在应用程序中。 A，我们表明我们的构造与计算有界对手的随机抽样没有区别。由于权益单位是随机均匀抽样的，因此在任何给定轮次中，权益为 s 的节点都可以在 0 到 s 次之间被选举为投票者。出于性能原因，可能希望每轮选举一个领导者，这是通过设置 l = 1 来实现的。
Limitations
描述的方法保证了在每个回合中采样完全相同的股权分数，因此节点能够更快做出提交决策。然而，这个的不足是对手可能会发起自适应攻击，例如(D)DOS-因为选出的节点在广播它们的消息之前是已知的，幸运的是可以使用多种提供网络匿名性的轻量级机制。例如用于加密货币的Dandelion提供了正式的匿名保证和低延迟和开销。将这种机制和LaKSA结合，会使攻击者识别节点IP地址的尝试变得复杂，从而缓解(D)DoS攻击。

在 PoS 区块链中解决此问题的另一种方法是使用具有秘密输入的加密原语（例如，Algorand中的 VRF 或唯一签名）来选择节点。使用这种方法，节点的角色只能由该节点本身揭示，例如，通过传播消息。正如我们在§VI中所示的那样，缺点是民选实体数量的结果差异，它减慢了块提交过程。在应用程序中我们展示了 LaKSA 如何与基于 VRF 的选举相结合，并且我们的承诺方案仍然适用。将“秘密”选举与固定委员会规模相结合的有效机制是一个开放的研究问题。

D. Chain Selection

LaKSA 不遵循比特币 NC 的最长链规则——相反，链的强度由支持其区块的权益来表示，为了改进对分叉的处理，我们结合了 GHOST 协议，该协议通过在计算链的总 PoW 权重时利用分叉块来提高 NC 的吞吐量和安全性。

分叉和虚拟块

在 LaKSA 中，投票有助于链的“权重”，并且对于确定主分支至关重要。简而言之，它们代表了利益相关者对他们对主链的看法的信念。为了比较链，节点遵循最大权益规则，即选择由更多权益加权投票支持的链。在 LaKSA 中，可以通过选择在连接的圆形信标上计算出的哈希值且其最后一个领导者的公钥较小的链来打破平局。 LaKSA 允许在一轮中不添加任何块的情况——例如，当一个故障节点被选为领导者或网络暂时异步时——或者该块包含很少或没有投票。在这种情况下，节点会创建一个虚拟块（参见 § III-B），它是一组尚未包含在主链中的已收到投票的块。

与“标准”块不同，虚拟块没有交易或签名。在链选择期间，节点不区分虚拟块和“标准”块：如果虚拟块比冲突的标准块强，则节点将支持虚拟块。选民可以通过投票支持区块的最新标准祖先来支持虚拟区块（见图 1）。在以后的轮次中，领导者可以对每轮未包含的投票进行整理，以创建一系列虚拟块，其中最新的作为新提出的标准块的前身。虚拟块然后由领导者与标准块一起传输。一个忽视在她的区块中包含投票的领导者有可能被另一个领导者覆盖，该领导者将未包含的投票聚合到虚拟区块中。被覆盖的块仍可能被稍后使用 GHOST 的块引用，如下所述，但即便如此，恶意领导者仍然会失去它的块奖励（参见 § III-G）。如果投票合法地出现在两个冲突的块中，例如，在同一轮中的虚拟块和被覆盖但被引用的标准块中，则忽略一个。由于虚拟块仅通过标准块创建，§ III-E 的提交程序仅在标准块上执行。

图 1 给出了一个示例，其中 q/n = 10%，并且第 i 轮的选民发表了七票支持块 Bi-1，第 i 轮的领导者创建了一个块 Bi，其中仅包含 4% 的股份的三票。因此，创建了一个拥有 6% 股权的虚拟区块 B′ i ，并且在第 i + 1 轮中，所有投票都隐含地支持该区块而不是 Bi，因此这一轮的领导者创建了一个区块 Bi+1，该区块聚合了虚拟区块的投票，并通过 B’ i 指向 Bi-1，我们强调块 Bi+1 还可以包含指向 Bi cf 的指针。

子树选择(GHOST)

当网络高度同步时，所提出的协议可能会很好地工作——这可以通过为 Δ 选择足够高的值来实现。然而，Δ 必须与交易吞吐量进行权衡：即只有当 Δ 低时，吞吐量才能高。如果 Δ 与网络延迟相比较小，则在定义的超时之前块无法到达节点的异步周期经常发生，导致高陈旧块率，从而损害系统的安全性。

为了使协议准备好承受这种情况，我们修改和扩展 GHOST 以使其适应我们的设置。链选择过程在 Alg .3中描述MainChain 程序从创世块开始，然后对于它的每个子块，该算法计算子块子树中的总权益，并为在其子树上聚合的权益最多的子块重复此过程，依此类推。当协议终止时，它输出表示主分支的最后一个块的块。链选择过程仅依赖于投票中编码的股份和虚拟块的收集投票——即那些不包含在任何实际块中的投票——并将它们包括在其链的总股份中。

为了说明链选择过程，我们在图 2 中展示了一个示例，其中 q/n = 10%。在我们的示例中：在第 i 轮中，领导者（即区块 E 的创建者）看到四个链，即分别以区块 P、G、D 和 J 结尾的链。为了确定主链，领导者从创世块 A 开始运行协议，并计算其子树的权益。 Block M 的子树权益为 11%，而 B 的子树权益为 15%。因此，B 被选中，并且领导者对该块重复相同的过程。最后，leader确定A、B、C、D为主链，并创建一个指向它的新区块E。此外，领导者引入了指向已知但尚未报告的分叉块（P、G、J）的指针（虚线）。需要这些指针来保持区块链视图的完整性。请注意，选择链 A、B、C、D 作为主链，尽管投票给该链的股份低于链 A、M、N、P 的股份。作为一个链中的不同链子树支持相同的链前缀，将 GHOST 与最大风险规则结合的一个优点是它需要对手与整个子树竞争，而不仅仅是它的主链，这使得安全攻击变得更加困难。重复该过程，第 i + 1 轮的领导者扩展 E 的链并报告分叉块 K 和 L。

E. Block Commitment

LaKSA 中的块提交由每个节点单独决定。每个节点指定 p*，它的风险级别和 B，即要提交的块。鉴于其当前对区块链的看法，它然后计算目标块 B 可以恢复的概率，给定我们的链选择程序，这个问题可以重新表述如下：对手可以创建比包含 B 的相应子树更强的子树的概率是多少？如果概率小于阈值 p*，则该块被提交。

对抗性子树必须植根于 B 的支持子树之外的块，否则它将支持B。支持子树的权益对于节点是已知的，并且可以通过 s = TreeStake(B) 简单地计算。对抗性子树可以源自任何前一轮，因此我们要求块 B 在其所有先前块也已提交之前不能提交。因此，对于每个块，我们考虑一个对抗性子树的潜在强度，该对抗性子树起源于 B 的父级，并且在当前轮之前有 k 个支持块。因此，支持分支和对抗分支在 k 轮中相互竞争。节点无法确定有多少权益单元支持对抗性子树，但这种知识对于提交 *** 作的安全性至关重要。因此，节点将这个权益分成以下总和：a) 丢失的权益，其中包括可能在分叉期间不知不觉地为对抗性分支做出贡献的权益单位，以及 b) 对抗性权益，即对手累积的权益的总和k 轮。

对抗性权益单位可能模棱两可，这意味着它们参与了同一轮中两个或多个不同区块或投票的创建。因此，有助于对抗分支的权益单元也可以出现在 B 的支持子树上。此外，它们的确切数量是未知的，尽管平均而言这将等于 αq。我们将在下面更详细地讨论模棱两可。我们假设丢失股份的最坏情况，即所有丢失的股份——即使它是诚实的——都被放置在一个未知的对抗子树中。这种情况可能发生在异步期间或网络分裂期间。该节点还保守地假设对手将赢得每场平局。但是，我们强调对抗性子树必须是内部正确的，例如，它不能有模棱两可的投票，否则诚实节点不会接受它。

假设测试

为了提交B，节点进行统计假设检验，以断言大部分网络是否与节点具有相同的支持树视图。为此，该节点计算一个所谓的 p 值，该值表示在 k 轮中获得总支持股权 s 的概率，假设是对支持分支的贡献比对对抗分支的贡献少。如果这个 p 值太低以至于我们可以安全地断定这个假设是无效的，我们就提交 B。 Alg.4 每轮调用一次，并且在每次调用期间提交尽可能多的块。为了实现安全性，我们使用传统 BFT 系统中存在的群体交集参数，除了在我们的例子中它是概率的。也就是说，在这样一个分裂的网络中，对手可能同时对两种观点产生模棱两可的投票；然而，如果节点看到她的目标区块由超过 2/3 kq 的质押支持，则该节点可以得出结论，这种情况在统计上是不可能的（参见§ IV-A 中的详细信息），这意味着大多数诚实节点会看到主链上的目标块，因为任何替代的对抗视图都不能随着时间的推移获得超过 2 /3 kq （因为 α < 1/3 ）。

该过程由 Alg.4，在该过程的核心，节点通过计算其对应的支持树位于假设分叉“安全”一侧的概率，不断提交主链的后续区块。根据参数，使用两个函数之一计算 p 值，即 HyperGeomProb 或 CramerBound（参见算法 4）。在第 IV-A 节中，我们更详细地讨论了这些算法，并表明它们确实给出了错误概率的上限。为了说明这个过程，我们在 App 中提供了一个示例。
为了使我们的演示简单，我们不通过 f（或类似的 α）参数对提交过程进行参数化。然而，它不会改变我们的方法，在实践中，它可能是一个有趣的特性，因为节点可以基于他们自己的对抗性假设以及他们的安全级别 p* 做出承诺决策。

模棱两可

尽管对抗性节点可以随意违反协议规则，但在 LaKSA 中，消息（即区块和投票）是经过签名的，因此对抗性节点可以对某些模棱两可的行为负责。特别是，以下行为是可检测的：a）通过在同一轮中产生冲突的投票或区块来模棱两可，或 b）支持或扩展比先前支持或扩展的链更弱的链。前者是一种无风险攻击，可以通过显示对手的两条签名消息来证明，这些消息在同一轮中支持或扩展不同的链。在后一种情况下，对手违反了链选择规则。这可以通过分别支持/扩展两条不同链 C1 和 C2 的任何一对签名消息 (m1, m2) 来证明，其中：Round(m1) < Round(m2) ∧ Stake(C1) > Stake(C2)。

尽管防止这种不当行为具有挑战性，但已经提出了通过导致行为不当的验证者失去其全部或部分存款/股权来抑制这种行为的解决方案。在这种方法下，该协议允许诚实节点向区块链提交模棱两可的证据以获得奖励，例如，在 Casper FFG的智能合约版本中实施的发现者费用，在 LaKSA 中实施这样的方案是未来工作的一个有趣方向。

F. Random Beacon

LaKSA 依靠伪随机信标来选举回合领导人和选民，这些信标很难被对手偏袒，这对安全很重要。 § IV-A 中的安全性分析依赖于这样一个假设，即对分叉的每个分支上的选民和区块提议者进行抽样不再成立。此外，过于可预测的信标容易受到针对选民和轮领导的自适应网络级攻击（例如 DoS），因为此类攻击的窗口与创建区块和发布区块之间的时间成正比。

在本文中，我们没有提出新的随机信标结构——相反，我们依赖先前提出的概念进行具体实例化。对于当前的实现，我们遵循了 Daian 等人的方法，其中信标完全由“稳定”主链块上聚合的随机值生成。更准确地说，如 § III-B 中所述，第 i 轮领导者将随机值 ri 插入其块中。对于安全参数 κ，即主链块的数量，在该参数之后回滚的概率可以忽略不计，当前轮 j 中的随机信标 r 使用随机预言机分两步从先前的随机值 r j−2κ , r j−2κ+1, r j−2κ+2, …, r j−κ 。对手可以对结果信标 r 产生偏见，但已经证明 [20] 短期对抗性偏见不足以获得长期的显着优势。

我们强调，使用随机信标来选择领导者/委员会并不特定于 LaKSA，其他随机信标结构也可用于实现该协议。最近的一些方法，例如 DFINITY和 RandHound，承诺了可扩展的随机性，并且可能比所提出的机制更能抵抗偏差。然而，更大的偏置电阻可能会以额外的计算开销为代价，我们将这些方案的调查与 LaKSA 结合起来作为未来的工作。

G. Rewards

LaKSA 介绍了算法中提出的奖励方案。Alg.5支持主链前一个区块的每个选民都会收到选民奖励 Rv 乘以该选民被抽样的权益单位数。一旦包含虚拟块的块被发布，它们的投票也会获得奖励。每个在主链上发布区块的领导者都会收到领导者奖励 Rl 和包含在块中的每个权益单位的包含奖励 Ri，领导者也可能会收到节点支付的交易费用，但我们省略了它们，因为它们是特定于应用程序的。

LaKSA 的奖励计划有几个目标。首先，它旨在激励选民立即发表支持他们最强烈观点的选票。分叉或“迟到”的投票和区块被标记在主链区块中，但它们没有得到奖励，尽管领导者仍然有动力将它们包括在内，因为他们加强了与主链的共同祖先区块。因此，试图等待几个区块投票给“过去最好的区块”的选民总是会失去他们的奖励。其次，它激励领导者按时发布他们的区块，因为在回合结束后收到的区块不会成为主链的一部分。毕竟，下一轮的选民会追随他们最强烈的观点，所以领导者会错过她的奖励。最后，该计划激励区块领导者包括所有收到的选票。审查选票的领导者会失去与审查的股份成比例的包含奖励。此外，审查领导者削弱了她自己的障碍。

分析 A.概率安全

在本节中，我们展示了仅当提交冲突块的概率确实低于 p* 时才提交块 B。为此，我们使用了一种基于统计假设检验的新型证明技术。当用户看到足够的支持权益以得出结论认为她不太可能在仅包含少数诚实用户的分支上时，用户提交了一个块。主要威胁是想要引起安全故障的对手，这意味着不同的诚实用户提交了两个冲突的块。为此，对区块链有不同看法的两个用户都必须看到足够的证据来提交他们的区块。

我们最坏的情况——即最有可能发生安全故障的情况——是诚实用户在分叉期间分裂的情况。对手可以通过同时对分叉的两个分支进行投票来增加安全故障的可能性。虽然事后可以惩罚模棱两可，但在分叉进行时无法检测到，因此在我们的安全分析中不能排除。我们假设权益的一部分 α ∈ [0, 1 3 ) 由对手控制。我们进一步假设分叉由两个分支组成，并且诚实的股份在它们之间平均分配。原因是如果一个分支比另一个强，那么在较弱的分支上提交块的可能性较小。类似地，没有必要考虑具有三个或更多分支的分叉，因为如果合并两个分支，则提交冲突块的概率会更高。最后，我们不考虑用户离线或被对手拒绝投票——这只会使一个分支更弱，安全故障的可能性更小，因此构成比所考虑的更弱的对抗场景。

用户无法直接观察两个分支上有多少用户——但是，她可以观察到有多少权益单元支持她的分支上的块。在最坏情况下，分支上的预期权益分数是 α + 1/2 (1 - α) = 1/2 (1 + α)，所以如果 α = 1/3 则为 2/3（这对于其他分支）。如果她观察到分支上的股份数量远高于这个分数，那么有证据表明她的分支更强大。在下文中，我们将制定是否有足够的证据来提交 B 作为假设检验的问题。在我们继续之前，我们注意到要提交 B，我们要求所有前面的块也已提交。因此，我们只关注 B 及其支持子树，而不考虑 B 的任何祖先（另请参见图 3 中的示例）。回想一下，有 n ∈ N 等权重的权益单位，其中单个节点可以控制许多权益单位。我们在每一轮中绘制一个大小为 q 个权益单位的委员会（例如，在图 3 中，它认为 q = 1 10 n）。我们假设 n 和 q 在分叉期间保持不变，因为它们是不经常变化的协议级参数。我们用 u 表示用户分支上每轮预期支持权益单位的数量。我们还假设 u 在分叉期间不会改变——即，用户不会在分叉进行时在分支之间移动。我们做出这个假设是因为 1）我们假设对手无法在分支之间自适应地移动用户（如第 II 节所述），以及 2）如果任何诚实用户意识到另一个分支，那么他们将能够检测到模棱两可并向两个分支机构的用户发送证据。我们假设在给定的第 l 轮中，用户有兴趣测试支持第 j 轮中出现的块 B 的权益数量是否足以提交它。原假设 H0 断言支持权益至多等于预期的最坏情况支持，即

在下文中，假设 H0 为真，我们计算在 B 的子树中观察到给定数量的支持权益的概率 p。该概率通常称为 p 值。如果 p 值低于 p∗，那么我们接受备择假设 H1 : u > 1/2 (1 + α)n 并提交区块。当然，这个实验可以在几个槽的过程中重复，直到 B 最终提交，或者如果 B 在分叉解决后被丢弃。因此，我们使用顺序假设检验。在下文中，我们首先关注在给定轮次 m 和 j 的零假设的情况下计算观察数据的概率——即区块 B 的支持权益，然后将其扩展到顺序设置。

设 Xi 为第 i 轮采样的支持用户持有的权益单位数。由于密码采样算法无需替换即可绘制，我们知道 Xi 具有超几何分布，其概率质量函数由下式给出

在第 j + 1 轮中绘制的支持单元的总数（其中单个单元可能在多个不同的轮中具有特征）。 . . , m 然后由 T = ∑m i= j+1 Xi 给出。由于 X1, X2, . . .都是同分布的，我们知道 T 具有 k = m - j 独立超几何随机变量的分布。因此，为了计算在原假设下观察到支持质押总量 t 的概率，我们可以在假设 u = 1 2 (1 + α)n。毕竟，在 H0 下包含的 u 的所有可能值中，这种选择将给出最高的概率。不幸的是，超几何随机变量的总和/卷积没有易于计算的概率质量函数。可以表示为 P(T = t) = q ∑ x2 =0 q ∑ x3 =0 … q ∑ xk =0 k ∏i=2 P(Xi = xi)P ( X1 = t − k ∑ i =2 x) 。该表达式源自附录的引理 B.1。其背后的直觉如下：对于所有可能的序列（x2，x3，…，xm），我们计算观察它的概率，然后将其乘以 X1 正好是 t 的概率减去序列之和.这就是在 Alg 中实现的。 4：递归封装了重复的和，而 P(X1 = t − ∑k i=2 xi) 的最终计算在第 14 行到第 18 行中完成。在数值上，它可以稍微简化——例如，没有必要考虑总和已经超过 t 的序列。然而，为了计算这个概率， *** 作的数量与 qk 大致成比例是不可避免的，即使对于适度的 k 值，它也非常大。这就是 Alg 的第 10 行 if 语句背后的直觉。 4：只有当 qm-j = qk 足够小，即低于取决于节点处理能力的某个阈值时，才会执行精确计算。

一种计算成本较低的方法是找到 T 分布的近似值。好的候选包括单个超几何（使用参数 kq、ku 和 kq 而不是 n、u 和 q）、二项式（我们用它而不是不替换地绘制）、泊松（近似二项式分布），或一个正态分布的（由中心极限定理）随机变量。然而，在下文中，我们转而关注 Cram ́ er-Chernoff 方法 [10]，这是一种限制随机变量 X 的概率 P(X ≥ x) 的通用方法。其原因有两个。首先，无论参数选择如何，它都为我们提供了感兴趣概率的严格上限，这比渐近有效的近似更安全。其次，它可以很容易地推广到随机变量的分布略有不同的设置。我们还研究了限制 T 的尾概率的其他方法，例如 Chernoff-Hoeffding 界，以及 [36] 和 [44] 的方法。

然而，我们发现 Cramer-Chernoff 界限是最清晰的，同时在计算上仍然可行。 Cramer-Chernoff 方法的基础是马尔可夫不等式 [10]，它指出对于任何非负随机变量 X 和 x > 0，它认为

rX 包括 Legendre-Fenchel 变换 1 或 X 在 Cramer 定理中用于大偏差 [10]、[22] 后的大偏差率函数。在我们的上下文中，t/k 是每轮累积的平均支持权益。如附录引理 B.3 所示，如果 t/k 高于预期的最坏情况支持权益（在我们的例子中为 qu/n），那么对手获胜的概率会以 k 呈指数级下降。事实上，函数 rX 表示该概率衰减的指数速率（因此得名“速率函数”）。

例如，设 n = 1500，u = 1000，q = 150。我们发现 rX (3/4 q) = rX (112) ≈ 2.50。这意味着在零假设下，我们观察到委员会平均支持 75% 连续 k 轮的概率至少呈指数下降，每轮的系数为 e−2.50 ≈ 0.082。这显示在图 4 中，对于 ̄ s= t/kq = 75%。在 15 轮之后，在 H0 下，平均 75% 的委员会观察到支持的概率低于 10 − 16 10 -16 10−16。

函数 cX (λ ) 没有方便的闭式表达式：它等于 2F1(-q, -u, -n, 1 - eλ ) ，其中 2F1 是高斯或普通超几何函数。因此，必须对速率函数进行数值评估。由于 cX (λ ) 在 λ ≥ 0 上是凸的（另见附录中的引理 B.2），因此只有一个局部最优值，因此我们可以使用黄金分割搜索的一些变体来找到它。 Alg.4 中的程序。图 4 如下：我们首先通过扩大基本区间来确定 λ 的搜索范围，直到我们观察到函数在区间中的某个点处减小。然后我们迭代地缩小间隔，直到它的宽度低于某个准确度阈值。速率函数的计算仍然不是微不足道的，尽管它取决于 q 的大小：对于 q = 150，我们发现在配备 2.5 GHz Intel Core i7 处理器的 MacBook Pro 上每秒可以计算大约 15 个实例，相比之下q = 30 时为 280/s，q = 750 时为 0.6/s。尽管如此，通过 Alg. 4，在实践中，单轮提交多个区块的可能性不大，因为提交的证据是缓慢积累的。此外，可以缓存 rX (x) 的评估，以在以后的轮次中加速 Commit 函数。

图 4 描绘了如果连续 k 轮观察到相同的平均支撑桩 ̄ s 时边界的演变。很明显，正如预期的那样，较大的委员会规模意味着较大偏差的可能性较小，因此用户能够更快地提交。因此，在安全性和效率之间存在权衡。即使 q = 30 并且平均有 24 个（即 ̄ s = 80%）权益单位投票支持一个区块，那么 p 值每轮下降近 75%（即 e−rX (24) ≈ 0.263） .尽管到目前为止我们只关注在第 m 轮中对插槽 j 中的块 B 进行的单个测试，但实际上，如果没有足够的证据立即提交，则对 B 的测试将执行多次。每次执行测试时，都有一定的错误概率，所以我们需要考虑这种累积。实现这一点最直接的方法如下：如果我们进行第 i 次测试，我们使用 p∗·γi 对一些 γ ∈ (0, 1) 作为我们的阈值。可能无限次试验后的总错误概率由 ∑∞i=1 p∗γi = γ 1−γ p∗ 限制。例如，如果 γ= 9/10 ，那么我们需要将概率阈值乘以 1−γ γ =1/9 （例如，如果我们最初将阈值设置为 10−16，那么我们现在将使用 ≈1.11 · 10−17 )，并且 p 值的阈值将每轮降低 10%（因此更难满足），这不是主要障碍：如前所述，即使委员会规模为 30，平均支持股权为 80%，p 值下降的速度也比每轮 10% 快得多，乘法因子 1/9 是仅在额外的 2 轮后相遇。

实验 Implementation

为了测试和评估 LaKSA，我们完全实施了它。我们的实现主要基于 Python。为了实现 p2p 网络堆栈，我们在部署 Ed25519 签名时使用了 Twisted 框架。这样做的好处是可以生成较短的公钥和签名（分别为 32 和 64 字节）。在我们的实现中，我们将投票编码为 80 字节，并且投票包含在各自的块中。尽管投票数是线性的，但即使对于较大的 q 值，引入的带宽开销也应该是可以接受的。例如，我们编码的 1000 个支持投票将消耗 80kB，这仅占 1MB 块的 8% 或 2MB 块的 4%。

Evaluation

配备我们的实现，我们在现实世界的环境中进行了一系列实验。我们建立了一个由分布在五大洲 15 个不同地点的物理机器组成的测试平台。我们使用这些机器总共运行了 100 个 LaKSA 节点。我们使用了一个简单的 p2p 泛洪，其中每个节点最多与五个对等点对等。我们首先调查了网络的吞吐量，我们获得了大约 10 Mbps 的平均端到端吞吐量。为了引入一个保守的设置并更好地表达现实世界的异构网络条件，我们没有通过有效的消息传播或地理对等点选择等技术来优化我们的网络。

在我们的设置中，我们所有的 100 个节点都被选为选民（即 q = 100），而每轮只有一个节点被选为领导者。从性能的角度来看，这样的设置例如相当于系统中有 2000 个节点且 q/n = 5% 时的设置。在我们的实验执行过程中，我们注意到协议步骤的持续时间之间存在不平衡。也就是说，投票只占实际承载交易的区块的一小部分，因此如果节点花费太多时间等待投票，那么这不会让我们使网络饱和。为了最大化吞吐量，我们为投票和块引入了单独的等待时间，即分别为 Δ1 和 Δ2，其中 Δ1 < Δ2，而不是两者的单个值 Δ。我们已经使用不同的 Δ1、Δ2 和块大小参数进行了一系列实验，我们的结果显示在表中。

我们测量以下三个性能指标：第 IV-E 节中定义的块和投票过时率 ψb 和 ψv，以及吞吐量——即每秒可用于潜在应用程序的千字节数。块大小引入了延迟和吞吐量之间的自然权衡。我们观察到，如果我们将块大小从 1MB（这是比特币的默认值）增加到 2MB，块陈旧率保持相似，并且吞吐量大约翻了一番。但是，如果我们将块大小增加到 4MB，那么小 Δ1 的陈旧率非常高，以至于吞吐量不会明显高于 2MB 块。如图所示，LaKSA 提供了 200 到 600 KB/s 之间的良好吞吐量，轮次延迟分别在 5 到 6.5 秒之间。在比特币中，2 进 2 出交易的大小约为 450 字节，这大致相当于每秒 450 到 1300 笔交易。特别是，我们发现 Δ1 = 1.5s 和 Δ2 = 4.0s 作为 2MB 块的有希望的配置。此外，我们调查了 LaKSA 节点产生的计算成本。我们使用单核 Intel i7 (3.5 GHz) CPU 来计算投票和块处理时间。平均而言，创建一个签名投票只需 53.25 μs，创建一个包含 100 个投票的新区块需要 17.22 ms，验证一个收到的包含 100 个投票的区块需要 10.08 ms。

与Algorand比较

在本节中，我们提供了与 Algorand [30] 的详细比较，后者是一种密切相关的 PoS 协议。 Algorand 与 LaKSA 有几个相似之处：1) 协议作为一系列轮次运行，2) 领导者和委员会成员在每一轮中根据轮次之间变化的随机信标来选择，3) 节点被选为领导者或委员会成员与其股份单位的数量成正比，4）委员会成员对领导者提出的区块进行投票，以及 5）如果他们获得足够数量的选票，则区块将被提交。尽管有这些相似之处，但 Algorand 和 LaKSA 之间存在两个主要区别。第一个是代替 Alg 的加密采样程序。 2，Algorand 在每一轮的随机信标上运行 VRF [38] 来选举领导和委员会成员。结果，每轮中的领导者和委员会成员的数量是随机的而不是固定的，并且增加的差异使区块承诺的安全性降低。其次，代替 Alg 的投票和顺序假设检验程序。如图 1 和 4 所示，Algorand 使用定制的拜占庭协议协议（BA？）来提交区块。然而，BA?包括许多步骤，在此期间没有将交易添加到区块链中，以及 BA 的安全性分析？比 LaKSA 更受限制。还有其他差异——例如，[30] 中没有讨论奖励和公平——但由于篇幅限制，我们只详细说明了两个主要差异。可以在 App 中找到 Algorand 的技术细节摘要。 D. 我们首先调查如果 Alg. 会产生什么影响。 LaKSA 的 2 被 Algorand 的委员会选择程序取代，因此 l 和 q 不再固定。

主要结果是，由于委员会规模而产生的额外差异使得使用假设检验做出整体承诺决策变得更加困难。方差方面的这种差异在 Tab 中得到了明确说明。应用程序 III。每轮 X 的支持权益数量以前是超几何的（从规模为 n 的群体中抽取 q 个样本而不进行替换，其中 u 支持用户的分支），而在 VRF 的设置中，它是二项式的，具有相当大的人口规模（抽取 n 个样本，使得每个样本都以 q/n 的概率在委员会中，并以 u/n 的概率支持用户的分支）。如果对手控制了三分之一的股份（即 u/n = 2/3 ），则在新设置中，方差通常会高出大约 3-4 倍。

正如我们从图 6 中看到的，更高的方差转化为块提交时间，也大约高出 3-4 倍。对于这个实验，我们计算了每轮平均支持权益的不同值 ̄ s 在 p∗ = 10−64, n = 1500, u = 1000, q = 150,和 γ = 0.99（如 § IV-A 中所述）。如果 X 是二项式分布的，那么 T = ∑m i=n+1 Xi 也是二项式分布的，所以我们不需要使用 Cram ́ er-Chernoff 方法来限制 VRF 设置的概率 P(T ≥ t)，因为我们可以直接计算。然而，Cram ́ er-Chernoff 界限的松散明显被 VRF 方法的较高方差所抵消。还可以看出，如果 ̄ s 足够高，那么 LaKSA 可以非常快速地提交区块。例如，如果 ̄ s 至少等于 98%，那么尽管安全要求非常高（即每轮的安全错误概率为 10-64），但 LaKSA 在 3 轮内提交。只要 ̄ s 高于 86%，LaKSA 就会在 10 轮内提交——每轮 5.5 秒（见 § V），这需要 55 秒，因此比比特币中 6 次确认的（平均）小时要短。尽管以上表明基于 VRF 的委员会选择增加了使用假设检验提交区块所需的轮数，但 Algorand BA 的价值主张是什么？算法是它在一轮之后提交块。但是，有几个重要的警告。首先是即使在最好的情况下，BA的两个阶段？每步走 2 步，因此 Algorand 中的一轮至少需要 λPRIORITY + 4 · λSTEP = 85 秒（另见 App.D），这与 15 轮 LaKSA 相同。 BA期间没有添加交易吗？步骤，而在 LaKSA 中，包含交易的块由其他包含交易的块确认。第二个是安全分析依赖于更大的委员会规模（最后一轮有 10,000 个股份单位）和比 LaKSA 更弱的对手（只控制 20% 的股份）。最后，LaKSA 中的每个用户都可以根据她的风险承受能力单独设置她的安全阈值 p∗，而 Algorand 有一组固定的安全参数来确定区块承诺。

论文阅读LaKSA: A Probabilistic Proof-of-Stake Protocol

发表评论

评论列表（0条）