Aleo共识协议(Bullshark)公开报告 - ZKSECURITY

本文概述了Aleo使用的共识协议Bullshark,Bullshark协议是PBFT协议的进化版本。该协议通过多轮投票达成共识,包括提议、投票和验证投票三个阶段。Bullshark通过流水线技术优化,允许每个参与者在每轮中提出提议,并通过超时和垃圾回收机制来保证协议的效率和可维护性。

Aleo 合成器

代码被发现具有详尽的文档和高质量。此外,团队以高度合作的方式行事,并且是我们发现本报告中许多问题的关键。

你可以在这里找到完整的报告

该报告受到了 Aleo 团队的好评:

apruden

victor

以下是报告概述部分的复制/粘贴


Aleo 中的 Bullshark

在本节中,我们将概述 Aleo 实现的共识协议,即 Bullshark。

Bullshark 共识协议是共识协议长期演进的结果,可能从第一个实际的共识协议(PBFT)开始。这个想法在大多数(所有?)这些协议中或多或少地保持不变:参与者的集合是固定的,并且他们一起按轮次前进:

  1. 在第一轮中,“领导者”广播一个提案。
  2. 在第二轮中,参与者对提案进行投票。
  3. 在第三轮中,参与者对投票进行投票。

如果你看到足够多的参与者对提案进行了投票,并且足够多的参与者看到了这一点(“对投票进行投票”部分),那么我们就可以“提交”一个提案。在区块链术语中,提交提案意味着最终确定提案并将其包含的交易应用于区块链的状态。

这个基本的 3 步提交过程从未真正得到改进。相反,大多数主要的优化都是通过使用流水线技术获得的。例如,Hotstuff 协议通过让领导者在每一轮中都提出提案来引入这种流程的流水线。最近,Bullshark 通过让每个参与者在每一轮中都提出提案来引入另一种类型的流水线。(另一个最近的协议 Shoal 在单个协议中引入了两种流水线技术。)

更具体地说,在 3f+1 个参与者(其中只有 f 个可能是恶意的)之间的一轮 bullshark 就像这样:

  1. 在一轮开始时,每个参与者将一批新的交易(可以被认为是一个区块)广播给其他每个参与者。(请参阅列表末尾的批次是如何创建的。)
  2. 如果你收到来自某人的一个批次,请确保这是你在这轮中看到的来自他们的唯一批次,存储它并对其进行签名。
  3. 一旦你收集到你的批次的 2f+1 个签名,这将为你的批次生成一个证书,你可以将其广播给所有人。
  4. 一旦你在这轮中观察到 2f+1 个证书,请为下一轮生成一批交易,其中你还包括 2f+1 个观察到的证书。这应该看起来像一个批次的有向无环图(或 DAG)。
  5. 返回到步骤 1。

为了在本报告的其余部分解释具体的例子,我们使用以下类型的图表:

bullshark

这仍然不能让我们知道参与者如何就提交的内容达成一致。Bullshark 的“提交规则”非常简单:在每个偶数轮(例如,第 2、4 轮等)中,选择一个领导者(例如,通过循环选举),并且如果存在 f+1 个引用它的证书,则提交他们的 DAG(他们的批次以及他们传递链接到的所有批次)。

领导者的批次被称为锚(anchor),并且锚有可能在偶数轮中没有被提交。但是,如果一个锚被一些诚实的节点提交,它总是会被所有其他诚实的节点稍后提交。这是因为提交的锚将始终包含在另一个锚的 DAG 中。

这个属性被称为quorum intersection(法定人数交集)属性,并且可以很容易地证明。如果一个锚在偶数轮 i 中被提交,那是因为它在第 i+1 轮中被 f+1 个证书引用。我们称这个集合为 A。第 i+2 轮中的任何区块(包括锚区块)都必须包括来自第 i+1 轮的 2f+1 个证书。我们称那个集合为 B。

我们需要证明 A∩B≠∅,或者换句话说,交集包含至少一个证书,或者换句话说,当一个区块被提交时,总会有一条路径通向下一个偶数轮的任何区块中的该区块。这并不难证明:多重集 |A∪B|=(f+1)+(2f+1)=3f+2,它比一轮中的顶点总数多 1 个顶点,因此具有一些多重性。

由于领导者及其锚的提案和认证速度可能很慢,因此添加了超时以确保参与者在移动到下一轮之前等待一定的时间让领导者出现。具体来说,在偶数轮中,参与者将等待看到一个锚进行认证,并将等待一个经过认证的锚包含在他们的下一个提案中。在奇数轮中,参与者将等待看到对锚的投票进行认证,并将等待对锚的经过认证的投票包含在他们的下一个提案中。

最后一个(重要的)微妙之处是,如上所述,如果节点没有观察到任何提交,该协议允许节点的存储无限增长。为了防止这种情况发生,添加了一个垃圾回收(garbage collection)协议,以便在 DAG 增长时修剪 DAG 的较旧部分。因此,当发生提交时,DAG 将被遍历到某个“垃圾回收边界(garbage collection frontier)”,并且该边界左侧的所有内容都将被丢弃。

  • 原文链接: blog.zksecurity.xyz/post...
  • 登链社区 AI 助手,为大家转译优秀英文文章,如有翻译不通的地方,还请包涵~
点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
zksecurity
zksecurity
Security audits, development, and research for ZKP, FHE, and MPC applications, and more generally advanced cryptography.