【Flow】技术白皮书3：核心架构

type

status

date

slug

summary

1 Flow 架构

在大多数传统区块链中，每个完整节点都必须执行与运行系统相关的每个任务。这个过程类似于单周期微处理器，其中每步执行一条指令。相比之下，现代 CPU 设计利用流水线来实现更高的吞吐量和扩展性。

Flow 不是要求每个节点选择它们将包含在区块中的交易，计算区块的输出，就这些交易的输出与他们的同行达成共识，最后签署区块，将其附加到链上，而是采用流水线架构。在 Flow 中，不同的任务被分配给专门的节点角色：收集、共识、执行、验证和观察。这种设计允许个人在家庭互联网连接上高度参与共识和验证，同时利用大型数据中心来完成大部分繁重的执行工作。参与共识和验证的参与者通过加密经济激励让其他节点负责，从而允许 Flow 获得巨大的吞吐量改进，而不会破坏网络的去中心化或安全性。在只有共识节点和执行节点的系统中，与共识节点也执行块计算的架构相比，Flow 的吞吐量增加了 56 倍 [1]。

在共识节点以外的参与者执行任务的任何设计中，正确的任务执行不在共识的安全保证范围内。因此，该协议必须包括专用组件以确保安全的系统操作，即使存在中等数量的恶意参与者也是如此。在我们的第一份白皮书 [1] 中，我们正式分析了将任务委托给共识节点以外的其他参与者的安全隐患。我们研究的结果是交易执行可以转移到一组节点（执行节点），并将结果验证转移到一个独立的组（验证节点）。该协议必须包括以下组件以确保安全：

如果验证者检测到违反协议，则他们必须能够向共识节点提出上诉（正式：提交挑战）。

共识节点必须有能力判断挑战者或被挑战者是否正确（形式上：裁决挑战）。

当包含此类机制时，流水线架构与区块链一样安全，其中所有任务都由所有共识节点执行 [1]。在本文中，我们改进了架构，使得结果验证在许多验证节点上去中心化和并行化。此外，我们指定了执行验证的不同挑战和裁决协议的细节。

核心架构原则

上面，我们注意到节点必须能够在检测到协议违规时向共识节点提出上诉。对于提供安全保证以防止拜占庭攻击的上诉系统，系统必须具有以下属性。

可检测：网络中的单个诚实参与者可以检测确定性故障，并通过要求所有其他诚实节点重新创建错误执行的部分流程来向所有其他诚实节点证明错误。

可归属的：Flow 中的所有确定性过程都使用可验证的随机函数(VRF) [2] 分配给节点。任何检测到的错误都可以归因于负责该过程的节点。

可惩罚：参与 Flow 网络的每个节点都必须投入一个股份，如果发现该节点表现出拜占庭行为，则该股份将被削减。通过 slashing 可靠地惩罚错误是可能的，因为确定性过程中的所有错误都是可检测（注释1）的和可归因的。

可恢复：Flow 协议包含用于结果验证和解决潜在挑战的特定元素。这些元素用于阻止恶意行为者试图引发错误，这比削减惩罚更能使他们受益，因为他们犯下错误结果的可能性可以忽略不计。

注释1在 Flow 中，节点通过重新执行它们的工作来检查其他节点的协议兼容行为。在大多数情况下，验证在计算上是便宜的，除了计算一个区块中的所有交易之外。我们在 3.4 节中描述了验证块计算是如何分布式和并行化的，这样每个验证者只需要执行整个块计算的一小部分

假设

我们只关注股权证明区块链，其中所有参与者都是已知的，并且每个节点都可以通过其签名进行验证。

节点承诺（并为）在特定时间间隔内参与网络，我们称之为纪元。纪元是系统范围的。虽然节点可以参与多个 Epoch，但 Epoch 的结束是节点离开或加入系统的专用时间点。纪元被认为持续大约一周。确定 Epoch 长度和 Epoch 转换机制的技术细节留待以后发布。在本文中，我们考虑系统仅在一个时期内运行。

此外，我们还假设

存在可用于查看伪随机数生成器的可靠随机源。我们要求随机种子在种子本身生成和发布之前不能被任何单个节点预测。可能的解决方案包括 Dfinity 的随机信标 [3] 或基于延迟证明的系统 [4]。

可聚合的非交互式签名方案，例如BLS 签名[5]。

足够的补偿和罚没机制来激励节点遵守协议。

消息遍历时间受$Δt $限制的部分同步网络条件。此外，我们假设本地计算时间与消息遍历时间相比可以忽略不计。

在本文的许多地方，我们都提到了节点的分数。这是指一组节点的缩写形式，这些节点持有相应的部分股份。形式上，设 $N ^{(r)} $为角色为 $r 的所有节点的集合，s_α$ 为节点$ α ∈ N^{ (r)} 的股份。至少 κ$ 个节点（具有角色$ r$）的一部分指代任何子集

对于。

例如，声明“超过 2/3 的共识节点已经批准了一个区块”意味着批准节点持有超过的共识节点的累积股份。

1.1 角色

角色是节点可以提供给网络的服务。它们是：收集者角色、共识角色、执行角色、验证角色和观察者角色。我们将执行各自角色的网络节点称为收集器节点、共识节点等。从基础架构的角度来看，相同的硬件可以在网络中承载多个角色。但是，网络将各个角色视为独立的节点。具体来说，对于每个角色，一个节点独立地抵押、取消抵押和削减。我们进一步假设节点对其每个角色都有自己独立的质押密钥，即使所有角色都托管在同一硬件上。图 1 说明了各个角色的节点在正常操作期间交换的消息。

图 1：节点角色和它们交换的消息概述。为简单起见，仅显示正常操作期间的消息。在裁定罚没请求期间交换的消息被省略

1.1.1 收集者角色

收集者角色的中心任务是接收来自外部客户端的交易提交并将它们引入网络。抵押节点通过交易费用得到补偿，所有角色都需要最低抵押才能正式参与该角色。接收交易时，收集器节点检查交易是否格式正确。通过签署交易，节点保证在交易结果被密封之前存储它。（有关块密封的详细信息，请参阅第 3.5 节。）

集群：为了负载平衡、冗余和拜占庭弹性，收集节点被划分为集群。我们要求收集节点被平等地抵押。在一个纪元开始时，每个收集节点都被分配到一个集群。集群分配是使用随机信标输出随机化的。

集合：收集器节点的中心任务是从外部客户端收集格式良好的交易并将它们分批放入集合中。当收集器节点看到一个格式良好的交易时，它对该交易的文本进行哈希处理并签署该交易以表明两件事：第一，它是格式良好的，其次，它将承诺存储交易文本直到执行节点已完成处理。通过签名，收集器节点保证交易的存储，如果它不产生交易，随后将被惩罚（连同集群的其余部分）

收集器节点共享它们在集群中收到的所有格式良好的交易，并协作形成一个联合的交易集合。集群一次形成一个集合。在开始新的收集之前，当前的收集将关闭并发送到共识节点以包含在一个块中。第 3.1 节提供了有关集合的更多详细信息。

一个集群中的收集器节点必须就当前收集中包含的交易以及在什么时候关闭收集达成一致。何时关闭集合的决定基于许多因素，包括代币经济学，这超出了本文的范围。这种分布式协议要求节点运行共识算法。幸运的是，一个集群中的节点数量和一个集群要处理的交易量是适中的（注释2）。因此，已建立的 BFT 共识算法，如 Tendermint [6, 7, 8]，SBFT [9] 或 Hot-Stuff [10]，是完全足够的。

注释2 对于成熟的系统，我们预计每个集群大约有 20 到 50 个节点。

安全隐患：由于每个集群中的收集器相对较少，因此集群可能会被恶意行为者破坏。区块中引用的集群在其执行等待时可以保留集合内容。 4.2 节描述了这种攻击的缓解策略（Missing Collection Challenge）。

1.1.2 共识角色

共识节点的核心任务如下：

区块形成

共识节点从集合中形成区块。本质上，共识节点维护和扩展核心 Flow 区块链。在 Flow 中，区块定义了交易以及执行计算所需的其他输入（包括随机种子），但不定义区块执行后的结果计算状态。

许多节点需要达成接受提议区块的协议，这需要拜占庭容错 (BFT) 共识算法 [11, 12]。虽然 Flow 共识系统的具体设计仍在积极研究中，但我们将设计空间限制在具有以下保证的算法上。

该算法是经过验证的拜占庭算法，即只要不到三分之一的共识节点是拜占庭式的，它就会在诚实的参与者之间保持一致性。

即使在网络异步的情况下也能保证安全。根据安全定义 [13、14]，共识节点可能会在不同的时间点宣布一个区块最终确定，这取决于它们从其他共识节点收集的信息量。然而，一个安全的共识算法保证所有诚实的节点最终将宣布同一个区块为最终确定的。

在部分同步的网络条件下[15] 保证了活跃度。正如 Fischer-Lynch-Paterson (FLP) 定理所述，容错分布式共识系统无法在异步网络条件下同时保证安全性和活跃性 [16]。对于 Flow，在网络分裂的情况下，我们优先考虑安全性而不是活跃性。在极其罕见和不利的大规模网络分裂情况下，世界状态的一致性比网络的前向进展更重要。

图 2：区块封存在 Flow 区块链中的位置示意图。在区块被共识节点最终确定后，执行节点处理它们的交易并发出执行收据（见第 3.3 节），随后由验证者节点检查（见第 3.4 节）。如果发现计算结果的检查部分有效，验证者将结果批准发送回共识节点。一旦满足密封区块的条件（参见第 3.5 节），区块的计算结果密封将包含在共识节点生成的下一个区块中。

Flow 共识算法的一个理想核心特征是确定性最终性。一旦一个区块被任何共识节点最终确定，这个承诺将永远不会改变（注释3）。确定性最终性提供了一个显着优势，即 dapp 开发人员不必处理链重组的影响。

可持续性：我们不考虑工作量证明共识系统，因为它们的能源消耗过高。我们只关注权益证明系统，其中计算成本减少到必要的元素：主要是密码学和记账。

💡

注释3 通过 BFT 共识保证确定性最终性时，除非系统受到至少三分之一的拜占庭参与者的主动攻击。

区块封存

在计算出一个区块并验证计算状态后，共识节点会为相应的区块发布一个区块密封。 Block Seal 包含对区块执行后产生的计算状态的承诺。此外，它证明了该计算已被绝大多数验证者节点验证。

共识节点将区块封存作为它们最终确定的新区块的一部分发布。由于区块的交易在其最终确定后执行，区块计算结果的密封不能包含在区块本身中。相反，封存包含在后面的区块中。图 2 中显示了一个示例。

跟踪质押节点

共识节点维护一个质押节点表，其中包括节点的当前质押及其公钥。重要的是要注意，质押余额仅由共识节点跟踪，而不是计算状态的一部分。每当节点的股份更改，共识节点将此更新在其下一个最终区块中发布。

在正常操作期间，质押和取消质押只能在从一个纪元切换到下一个纪元时进行。然而，在一个纪元内可能会发生通过罚没发生的非自愿的权益更改，并且所有诚实节点在处理包含相应权益更新的区块时都会立即对其进行解释。

罚没削减

共识节点裁定削减挑战并相应地调整质押余额。

安全隐患

共识委员会是系统中的中央权力机构。共识委员会本身必须裁定针对委员会成员的挑战。这个过程的安全性和活跃性是通过BFT共识算法来保证的。 Flow 使用具有确定性最终性的共识算法。因此，dapp 开发人员不必处理链重组的额外复杂性。我们的结果适用于任何具有确定性最终性的拜占庭容错共识算法。 HotStuff [10, 17] 是领先的竞争者。然而，我们继续评估其他算法，例如 Casper CBC [18、19、20] 或 Fantômette [21]。

1.1.3 执行角色

执行节点计算它们提供的所有最终区块的输出。然后他们向收集器节点询问包含要执行的交易的集合。他们使用这些数据执行区块并将生成的计算状态作为执行收据发布。为了验证，计算被分解成分块。执行节点在执行收据中发布有关每个分块的附加信息（参见第 3.3 节），以使验证节点能够独立且并行地检查分块。

计算节点主要负责 Flow 在规模和效率方面的改进，因为只需要极少数这些强大的计算资源来计算和存储规范状态。

安全隐患

恶意执行节点可能会发布错误的执行收据。检测不正确执行结果的协议在第 3.4 节和第 4.1 节中挑战的裁决过程中进行了介绍。

1.1.4 验证角色

验证节点检查来自执行节点的计算。虽然每个节点只检查少量的分块，但所有验证节点一起将以压倒性的概率检查所有分块。对于每个分块，验证节点都会发布结果批准，前提是它同意结果。封存区块需要执行回执和结果批准。

安全隐患

与大多数区块链一样，Flow 必须解决验证者困境 [22]。在工作人员产生结果而验证者确认结果正确性的系统中，验证者有动机在不花费检查工作的情况下批准结果。这种激励冲突是验证者困境的核心。即使工人和验证者没有勾结，它仍然存在，因此额外的验证者无济于事。对于 Flow，我们开发了机密知识的专业证明（第 2.1 节）以克服验证者的困境（第 3.4.2 节了解更多详细信息）。

1.1.5 观察者角色

观察者节点将数据中继到协议外部实体，这些实体本身并不直接参与协议。

1.2 信息的局部性

信息的正确性可以使用链上信息进行加密验证

从数据的角度来看，Flow 区块链不是独立的。例如，计算状态的加密散列包含在区块中，但状态本身不是。这意味着任何人都可以使用 Flow 区块链中的哈希值（以及必须与实际数据一起提供的 merkle 证明）来验证计算状态的任何子集的完整性。但是，不可能从核心区块链中提取状态本身。

计算状态对于执行节点是本地的

对信息持有者的引用由持有者的签名保证

1.3 计算状态 vs网络基础设施状态

Flow 中的一个重要概念差异是处理属于计算状态的信息与网络基础设施本身。虽然计算状态由执行节点持有，但网络的基础设施状态由共识节点维护。为了说明差异，请考虑网络中节点不变的情况（节点永远不会离开、加入或更改权益）。然而，系统执行的交易会修改寄存器值，部署智能合约等。在这种设置下，只有计算状态发生变化。计算状态的完整性受到验证过程的保护（详见第 3.4 节）。相比之下，现在让我们考虑一种没有向系统提交交易的情况。区块仍然产生但不包含交易。在这种情况下，系统的计算状态保持不变。但是，当节点离开或加入时，网络基础设施的状态会发生变化。网络状态的完整性受到共识协议的保护。修改需要2/3以上的共识节点同意。

1.3.1 质押和罚没

网络状态本身主要包含所有质押节点的列表，其中包含节点的质押金额及其公共质押密钥。网络状态的更新与网络中的所有节点相关。因此，共识节点直接将更新记录到生成的区块中。此外，罚没挑战直接提交给共识节点进行裁决。（例如，第 4.1 节提供了挑战执行结果的详细协议。）由于共识节点维护网络状态，包括质押余额，它们可以直接削减行为不端节点的质押，而无需依赖执行节点更新余额。

2 通用技术

在本节中，我们描述了跨不同节点角色使用的方法和技术。

2.1 机密知识的专门证明（SPoCK）

SPoCK 允许任意数量的证明者证明他们拥有相同的机密知识（秘密）。密码证明不会泄露有关秘密的信息。每个证明者的 SPoCK 都是专属于他们的，没有秘密就无法复制或伪造。

Flow 中使用 SPoCK 协议来规避验证者困境 [22]（第 3.4.2 节）。该协议防止执行或验证节点相互复制执行结果或结果批准。因此，执行者如果没有及时完成的工作就无法得到补偿。在 Flow 中，秘密源自低级执行环境（例如虚拟机）的执行轨迹。执行整个计算是创建执行跟踪的最便宜的方法，即使计算的最终输出是已知的。

形式上，SPoCK 协议提供了两个中心保证：

任意数量的参与方都可以证明他们知道共享秘密而无需泄露秘密本身。

可以以任意顺序完全揭示证明，而不允许任何其他方假装知道。

SPoCK 协议的工作原理如下。

考虑一个具有状态转换函数的普通区块链，其中，是修改世界状态的交易区块，是处理区块之前的状态， $作为之后的状态。我们创建一个新函数以相同的方式工作，但有一个额外的秘密输出，使得对于相同的与。额外的输出是一个从执行计算中确定性得出的值，就像每个执行步骤的 CPU 寄存器的哈希值一样，它的获取成本不会比重新执行整个计算更便宜。我们可以假设的一组可能值非常大。

执行节点 Alice 向 S′（某种 merkle 根）发布签名证明，并使用 merkle 证明响应关于中值的查询。此外，它还发布了从派生的 SPoCK。

验证者节点，Bob 验证是的准确应用，并发布自己的SPoCK。

观察者可以确认两个 SPoCK 都来自同一个，并假设 Bob 实际上以高概率验证了输出(注释 4) 而不仅仅是“橡皮图章”结果。这不会在 Alice 和 Bob 主动勾结的情况下提供任何保护，但它确实可以防止惰性节点在实际上不知道结果正确的情况下“确认”结果。

💡

注释4我们假设诚实节点不会接受未经证实的$ ζ 值，因为如果 ζ $值不正确，它们将被削减。因此，观察者可以假设统计上超过 2/32/32/3 个 SPoCK 是通过对各个块的真实重新计算获得的。

SPoCK 的创建方式如下：

使用（或的加密散列）作为确定性密钥生成过程的种子，生成公钥/私钥对。
使用私钥 sk 对你的公开身份（如节点 ID）进行签名，并将签名与确定性生成的公钥 pk 一起发布：

所有观察者都可以验证签名，看到 Alice 和 Bob 都必须有权访问私钥 sksksk，但签名本身不允许恢复这些私钥。 Alice 和 Bob 必须都知道用于生成私钥的相同底层秘密$ ζ$。

为了密封一个区块，必须为每个分块验证几个 SPoCK。我们早期 BLS 实施的基准表明，密封区块的所有证明都可以在单个 CPU 内核上以秒为单位进行验证。跨多个 CPU 内核的并行化非常简单。通过使用矢量化 CPU 指令（例如 AVX-512 或加密协处理器）可以进一步缩短验证时间。

3 交易处理流程

在本节中，我们给出了交易处理流程的正式定义。图 3 提供了我们在第 3.1-3.5 节中详细讨论的各个阶段的高层次概述。为了简洁明了，我们专注于核心步骤，省略了为节省带宽、运行时间等而进行的协议优化。在第 3.6 节中，我们制定了定理 2，证明即使在存在拜占庭参与者的情况下，密封计算结果的正确性也有概率保证。

为了正式定义节点交换的消息，我们使用受 Protobuf 启发的（注释5）伪代码 [23]。

注释5具体来说，我们使用 Protobuf，只是为了简洁起见省略了字段编号。

图 3：交易处理流程。六边形框表示各个阶段的开始，这在第 3.1 – 3.5 节中进行了讨论。箭头显示具有特定角色的节点之间的消息交换。绿色框代表广播操作，其中内容被中继到网络中的所有质押节点（独立于它们各自的角色）。白框是节点在本地执行的操作。

3.1 收集器角色：将交易批量打包到集合中

如 1.1.1 节所述，有多个收集器集群，每个集群一次维护一个集合。只要集群非空，集群就可以决定关闭其集合。作为关闭集合的一部分，它由集群的收集器节点签名，以表明它们同意其内容的有效性并承诺存储它，直到块被密封。

【定义 1】保证集合是由其集群中超过 2/32/32/3 的收集者签名的交易列表。通过对集合签名，收集器节点证明：

集合中的所有交易都是格式良好的；

该集合不包含重复的交易；

存储集合，包括所有包含交易的全文。

保证集合被认为是不可变的。一旦一个集合得到其集群中的收集器的保证，它的引用就会被提交给共识节点以包含在一个区块中（参见消息 1）。

消息 1：收集器节点向共识节点发送一条 GuaranteedCollection消息，以通知它们有保证的集合。对于要保证的集合，集群 (clusterIndex) 中超过 2/3个收集器必须对其进行签名。 aggregatedCollectorSigs 不是单独存储签名，而是聚合签名。

3.2 共识角色：将计算线性化为区块

共识节点从收集器集群接收，并通过第 1.1.2 节中概述的 BFT 共识算法将它们包含在区块中。最终区块的结构在消息 2 中给出。构成核心区块链的通用字段是、。此外，该区块包含一个作为熵源，它由共识节点的随机信标生成。根据预定义的众所周知的协议，处理区块的节点将使用它作为多个随机数生成器的种子。在 Flow 中，可靠且可验证的随机性来源对于系统弹性的拜占庭至关重要。

消息 2：共识节点向全网广播区块。当且仅当超过个共识节点已签名时，他们的区块才有效。我们不是单独存储签名，而是在中存储聚合签名。

提交的指定了接下来要执行的新交易。在正常操作期间，共识节点只需要消息提供的信息。特别是，它们仅使用集合哈希 ()，但不需要检查集合的交易，除非执行结果受到质疑。

blockSeals与链中的先前区块有关，先前区块的执行结果刚刚被密封。区块封存包含对区块执行后计算结果状态的承诺，并证明该计算已被绝大多数验证者节点验证。 3.5 节详细描述了共识节点如何密封区块。

字段和只是为了完整性。为简洁起见，我们没有给出消息和的结构。

将列出已提交给共识节点的所有罚没挑战（但不一定由共识节点裁定）。任何抵押节点都可以提交罚没挑战。一些挑战，例如第 4.1 节中讨论的错误计算挑战，需要被挑战的节点响应并提供补充信息。

提交的将包含任何更新网络基础设施状态（详见第 1.3 节）。最重要的是，由于罚没、质押和取消质押请求而导致的质押变化都记录在该字段中。通过在区块中包含和，它们的出现将持久保存在链中。由于所有质押节点都必须遵循最近完成的区块才能履行各自的职责，因此在区块中记录此信息也可以作为一种公开广播的方式。

3.3 执行角色：计算区块中的交易

当执行节点收到一个最终确定的区块时，如消息 2 所示，它们缓存它以供执行。一旦执行节点具有以下信息，它就可以计算一个区块。

前一个区块的执行结果必须可用，因为它用作下一个区块的起始状态。在大多数情况下，执行节点还计算了先前的区块，并且结果输出状态是已知的。或者，执行节点可能会从不同的执行节点请求前一个区块的结果状态。

执行节点必须从收集器节点获取区块中引用的所有集合的文本。

3.3.1 并行验证分块

在完成一个区块的计算后，执行节点向共识节点和验证节点广播执行收据。我们将在第 3.3.2 节中更详细地讨论执行收据的详细信息。执行收据的核心是执行节点对其最终结果的承诺。

此外，它还包括中间结果，可以在不重新计算整个分块的情况下并行检查计算的各个部分。必须在专门的步骤中验证执行结果的正确性，以确保商定的计算状态。在执行阶段，区块计算由计算优化节点完成。因此，我们假设作为独立验证过程的一部分，由任何其他节点重新计算的区块将始终较慢。

为了解决瓶颈问题，我们采用了一种类似于拆分并行验证的方法 [24]。我们将执行收据定义为由单独的分块组成，每个分块都构造为可独立验证。在这些分块的子集上定义了验证过程（第 3.4 节）

通过将区块计算分解成单独的分块，我们可以跨多个节点分布和并行执行验证。让我们考虑一个包含个分块的区块。此外，设为每个验证节点检查的区块中分块的分数（意思是，每个验证节点必须挑选这么多个分块来执行验证）。的参数值由协议生成（详见第 3.6 节）。

对于的上限函数。如果所有验证节点都完全参与，则具有个验证节点的成熟系统将重新计算总的分块。因此，平均而言，每个区块被执行次。

例如一个区块有10个分块，每个验证节点检查的分块的分数=2/10, 那么每个验证节点需要检查的分块数量是2个。如果有20个验证节点，检查次数是2*20=40次，每个区块被执行40/10=4次.

例如，具有个验证节点的成熟系统可以将一个大区块分解为个分块。在的情况下，每个验证节点将检查个分块，并且每个块将由不同的验证节点（平均）进行验证。 42 的冗余因子使系统对拜占庭参与者具有弹性（参见第 3.7 节）。

重要的是，每个分块的计算消耗应该差不多相同，并不可能超过设定的阈值。如果分块的执行时间相差很大，则分配给检查长时间运行的分块的验证者可能不会在区块被密封之前完成（参见第 3.5 节）。因此，执行节点可以通过以长期运行的块为目标来攻击网络，以引入未经验证的计算不一致。

通过强制执行具有相似计算消耗的区块来缓解此弱点。具体来说，我们引入了以下系统范围的参数。

: 一笔交易的计算消耗上限

: 一个分块中所有交易的计算消耗上限，并且

这里，我们假设存在一种计算消耗的度量，类似以太坊中的gas。

由于交易和分块的计算消耗都存在硬限制，分块明显高于交易的计算消耗，简单贪心算法 1 将达到类似计算消耗的目标。形式上，令，当时。然后，除最后一个分块外，所有分块都将具有具有以下属性的计算消耗c。

。如果不是这种情况，即，算法 1 将向当前分块添加更多交易（第 6 行），因为交易的计算消耗上限为。

，由算法1 第6 行保证。

因此，除最后一个分块外，所有分块的计算消耗为c：

选择足够大的 nnn 保证除了最后一个分块之外的所有分块都具有相似的计算消耗。最后一个分块可能只包含一个交易。因此，它的计算消耗可以取任何值。与分块中任何其他分块的相反。由于以下原因，最后一个分块明显小于不会造成问题。例如，考虑一个节点参与网络

算法 1：将区块中的交易分成分块。该算法假定所有$ i$ 的计算消耗。

可以处理最多个区块的分块。对于，节点将需要具有处理每个区块最多 42 个分块的能力（如上所述）。因此，对于每个的区块，诚实的验证者将简单地检查整个区块。对于具有更多分块的区块，即使每个验证器都抽取分块的子集进行验证，工作负载在所有验证器上都是统一的。这是因为所有分块中的绝大多数具有相当可比的计算消耗，如等式（7）中得出的。

3.3.2 执行收据

如消息 3 所示，执行回执是一个签名的，它提供发送者的身份验证并保证消息的完整性。封装了执行节点对其中期和最终结果的承诺。具体来说，它包含对包含其结果的区块的引用，以及作为对结果状态的承诺(注释6)的。

消息 3：执行节点在计算出一个区块后向整个网络广播一个。

注释6，我们这里不指定 StateCommitment的细节。它可以是完整状态（对于成熟的系统来说可能太大了）。或者，StateCommitment可以是哈希算法的输出，例如 Etherum [25] 使用的 Merkle Patricia Trie。

考虑这样一种情况，执行节点如实计算了一个区块，但使用来自错误执行收据的计算状态作为输入。虽然节点的输出可能会传播错误，但重要的是将错误归因于最初引入它的恶意节点并罚没恶意节点。为了确保错误的可归属性，ExecutionResults 指定了他们建立在的计算结果。正如我们稍后将在 3.6 节中展示的那样，错误的计算结果将以压倒性的概率被拒绝。

最后，包含执行节点运行 Chunking 算法的结果（和）。此外，一个分块声明了计算的起始状态（）和分块中第一个交易的计算消耗（）

解决验证者困境

字段是一个 SPoCK 列表，它是根据计算分块的中间状态生成的。形式上，对于第 i 个分块，持有 SPoCK，证明从执行分块中获得的秘密知识。如 3.4.2 节所述，需要 SPoCK 来解决在Flow中的验证者困境。此外，它可以防止执行节点相互复制，假装它们的计算速度比实际情况要快。

鉴于有多个执行节点，很可能会为同一个区块发出多个执行收据。我们定义执行收据的一致性如下。

【定义 2】 执行收据的一致性属性。执行收据是一致的，当且仅当

它们的执行结果相同并且

它们的 SPoCKs 证明相同的机密知识

3.4 验证作用：检查执行结果

验证过程旨在从概率上保证计算结果的安全性（参见第 23 页，定理 2）。计算安全的一个关键方面是验证节点可验证地自行选择它们彼此独立检查的分块。这个过程在下面的部分中描述。在 3.4.2 节中，我们描述了如何验证所选块。

3.4.1 用于验证的自选块

算法 2 给出了验证节点自选其块的协议。虽然受到 Algorand 的随机排序 [26] 的启发，但它显着降低了复杂性。

算法2：随机选择分块进行后续验证。在第 6 行中，是上限算子。函数从输入list中抽取一个无需更换的简单随机样本。seed用于初始化伪随机数生成器。

具有以下关键属性。

可验证性。随机选择分块的种子在第 4-5 行生成。给定、验证者的公钥和证明 p，任何其他方都可以确认是根据协议生成的。此外，给定，任何人都可以重新计算验证者的预期分块分配。因此，分块选择协议是可验证的，并且偏离协议是可检测的、可归因的和可惩罚的。

独立性。每个验证者都在本地独立于所有其他验证者对其分块进行采样。

不可预测性。在不知道验证者的密钥 sk 的情况下，预测样本在计算上是不可行的。形式上，种子的计算可以被认为是一个可验证的随机函数[2]。

均匀性。验证者使用 Fisher-Yates 改组 [27, 28] 来自行选择它检查的块。 Fisher-Yates 算法的伪随机数生成器以加密哈希函数的输出为种子。种子的一致性和混洗算法的一致性共同保证了生成的分块选择的一致性。

推论 1

算法 2 对分块的子集进行采样，其中是区块中的分块数，而是每个验证节点要检查的分块的分数。所有验证者的选择概率均匀且独立同分布（i.i.d.）。如果没有验证节点的密钥，样本是不可预测的。

独立性和不可预测性对于系统的安全性至关重要。没有这些属性的选择协议可能会被恶意的执行节点滥用（详见 4.3 节）。

我们对分块进行独立验证的方法与传统的验收抽样理论 [24、29、30] 有相似之处，但由于我们的模型假设不同而有所不同。与测试物理项目的传统验收抽样相比，我们的数字块的相同副本可以由多个验证者并行检查。我们方法的部分新颖之处在于我们通过平行抽样提升了验收抽样模型。

3.4.2 验证分块

算法 3：验证分块。函数将交易 t 应用于计算状态 Λ$ 并返回一对值：结果状态（第一个返回值）和交易的计算消耗（第二个返回值）。如果条件为假，则 assert 语句会引发异常

验证协议被设计成自包含的，这意味着任何执行收据都可以被隔离验证。所有必需的数据都通过执行收据中的哈希指定。检查分块的正确性需要重新执行分块中的交易。验证协议的详细信息在算法 3 中给出。算法的输入和直接取自执行收据。和必须从执行节点获取并通过散列法检查以匹配执行收据（特别是：）或原始区块（特别是：）（注释7）。因此，验证过程中发现的错误可以归因于数据提供者并被削减。验证过程也被赋予了执行权，因为我们允许它请求对执行节点进行罚没。

注释7我们在这里使用术语“散列”来指代传统散列函数的一次性应用以及迭代散列方案，如 Merkle 树或 Merkle Patricia Trie。

消息 4：如果所有分配的分块都通过验证，验证节点向所有共识节点广播。

成功的验证过程会导致验证者向所有共识节点广播（消息 4）。重要的是要注意（特别是）证明的正确性。具体来说，在中，验证者签署的是，而不是执行收据。根据定义 2，多个一致的执行收据具有相同的执行结果。因此，它们的正确性同时由单个消息证明。这节省了通信带宽，因为对于几个执行节点通过发布一致的执行收据发布相同结果的常见情况，每个验证节点只发布一个。第二个重要的组成部分是，它证明验证节点完成了分配的验证任务。我们设计了这个协议组件来解决验证者困境 [22]。它可以防止验证者仅仅批准，押注执行节点的诚实，从而获得验证者没有做的工作的补偿。 VerificationProof.字段指定验证者通过运行（算法 2）选择的分块索引。如第 3.4.1 节（属性（1）可验证性）所述，符合协议的分块选择由证明，它保存由返回的 p 的值。列表 VerificationProof.Zs 包含每个分配的分块的验证证明。形式上，对于每个，持有一个 SPoCK。每个验证器对其独立检查的分块进行采样（属性（2））。此外，统计上每个分块都由更多节点检查（例如，如第 3.7 节中建议的那样，大约 40 个节点）因此，以压倒性的概率检查所有分块。（我们在定理 2 中形式化了这个论证）。

3.5 共识角色：封存计算结果

密封块的计算结果发生在区块本身已经完成之后。一旦计算结果作为执行收据广播，共识节点等待执行结果累积匹配的结果批准。只有在绝大多数验证者节点批准结果并且没有提交后（详见 4.1 节），共识节点才考虑密封。 BlockSeal的内容在消息 5 中给出。算法 4 指定了必须满足的完整条件集。算法 4 在我们的区块链中强制执行一个特定的结构，如图 4 所示。

一旦共识节点发现所有条件都有效，它将作为的一个元素合并到它提议的下一个区块中。所有诚实的共识节点都会在投票之前检查的有效性，作为验证区块的一部分。因此的有效性由 BFT 共识算法保证。此外，条件 (8) 保证在封存区块之前已收到任何。这产生了以下推论：

【推论 2】 给定一个具有部分同步网络条件的系统，其消息遍历时间受限制。仅当超过 2/3 个验证节点批准了并且没有提交并裁定错误的结果时，区块才会被密封

图 4：根据算法 4 的新 BlockSealBlockSealBlockSeal 的有效性条件。

消息 5：为了密封一个区块（使用哈希），共识节点将添加到他们最终确定的下一个块（字段）。字段是至少一个发布具有兼容的执行收据的执行节点的聚合签名。他们的只有在超过 2/3 个验证者节点签名时才有效。我们不是单独存储签名，而是在中存储聚合签名

算法 4：用于确定有效性的协议。图 4 说明了条件 (1) – (4)。

3.6 计算正确性证明

下面，我们在定理 1 中证明，即使存在适量的拜占庭参与者，Flow 的计算基础设施也能保证活跃性。此外，定理 2 证明了块计算是安全的，即密封区块中的结果状态以压倒性的概率是正确的。虽然安全性在网络条件下是无条件的，但活跃度需要部分同步的网络。

定理 1 计算活跃度

给定一个系统，其中

超过 2/3 个共识节点的股份由诚实的参与者控制；

至少一个诚实的执行节点；

超过 2/3 个验证节点的股份由诚实的参与者控制；

消息遍历时间受$Δt $限制的部分同步网络条件。

最终区块的计算和密封总会向前推进。

定理 1 的证明

假设共识算法活跃，新区块的最终确定总是在进行。

对于具有一个诚实执行节点的系统，至少有一个具有正确执行结果的执行收据。

每个诚实的验证者都会批准正确的。因此，将有至少 2/3 个验证节点的结果批准。

恶意验证者可能会通过提出 FaultyComputation-Challenge 来暂时延迟区块密封，这会触发算法 4 中的条件 (6)。然而，解决过程（详见 4.1 节）保证 FaultyComputationChallenge 最终得到裁决，恶意验证者被罚没（推论 3)。因此，恶意验证者无法通过条件（6）无限期地抑制封块甚至达到条件（7）。

因此，所有诚实的共识节点最终都会同意区块封印的有效性。

假设一个保证链质量（注释8）的共识算法，一个诚实的共识节点最终会提出一个区块并包含协议规定的区块封存。

鉴于有超过2/3 个诚实的共识节点，包含封存的区块最终将被最终确定（通过共识的活性）。

💡

注释8 形式上，区块链的链质量是诚实节点贡献的块数与恶意节点贡献的块数之比 [31]。

定理 2 计算安全

给定一个系统，该系统具有

部分同步的网络条件，消息遍历时间受的限制；

超过 2/3 个共识节点的股份由诚实的参与者控制；

所有验证节点都是平等的，其中超过 2/3 个是诚实的。设表示诚实验证节点的数量，表示每个验证者检查的块的分数。对于大，密封块中计算错误的概率受限于

这里，表示执行收据中的块数。

定理 2 指出计算错误的概率随着验证者的数量呈指数下降。

定理 2 的证明。考虑执行收据。

为简洁起见，我们将执行回执的分块表示为 L，即。不失一般性，我们将视为一个集合（而不是有序列表），因为此证明不依赖于 L$ 的元素的顺序。

令为执行回执中的分块总数，即，其中表示基数运算符。

让表示一个分块。

正如推论 1 中形式化的那样，每个诚实的验证者随机选择一个子集，其中通过执行（算法 2）。由于每个验证者通过 Fisher-Yates shuffle 选择分块，因此没有被选为第一个元素的分块是，并且没有被选为第二个元素的是，等等。因此, 分块没有被一个特定的验证者检查的概率是

设为未被任何诚实验证者检查的概率。

因为。因此，特定分块未被检查的概率随着验证者数量增加呈指数下降。图 5 将精确概率可视化为等式 (10) 中给出的的函数。所有分块都被至少一个诚实的验证者检查过的概率是。因此，块中任何块中的错误未被检测到的概率为

我们假设系统参数的选择使得以确保计算安全。因此，我们可以近似等式。 (12) 通过它在中的一阶泰勒级数。

将等式 (13) 和 (11) 代入 (12) 得到

从定理证明等式（8）。我们现在已经证明，执行收据中的错误块没有被诚实的验证者检查的概率受（14）的限制。此外，每个诚实的验证者都会通过提出来挑战分配给它检查的任何错误块（有关详细信息，请参见第 4.1 节）。推论 2 保证只有在没有提出正确的时才会密封块。因此，如果错误的区块没有被诚实的验证者检查，唯一可以用错误的密封区块的方法。因此，等式(14) 还限制了错误被密封的概率。

图 5：没有一个诚实的验证者检查特定块的概率。是每个验证者选择进行检查的分块的分数。该图说明了个诚实验证节点验证带有个分块的执行收据的概率。蓝色曲线显示了当验证者根据算法 2 中指定的 Fisher-Yates 对其分块进行采样时的依赖性，即从执行收据中采样分块而不进行替换。为了比较，我们展示了有放回的抽样。

3.7 验证节点上的计算负载

使用等式（8），我们可以计算每个验证者必须检查以实现特定所需的块的分数 η。对于满载的成熟系统，我们预计有 1000 个验证节点，每个区块最多包含个块。此外，我们保守假设只有 2/3 个验证节点是诚实的，即。

让恶意执行节点成功尝试将受损状态引入区块链的概率为为此，每个验证节点需要检查 32 个块，即执行的执行节点工作。为了将概率进一步降低到，验证者只需要执行执行节点工作的。这表明分布式和并行化计算结果的验证是有效的。此外，请注意，检查块可以并行执行。

4 攻击向量的缓解

下面，我们将讨论对 Flow 最严重的攻击。在这种情况下，我们想重申一下，作为网络状态的一部分，共识节点会维护质押余额（比较第 1.3 节）。因此，共识节点可以直接裁定和削减行为不端的节点。网络状态的结果更新发布在块中（消息 2 中的字段），无需涉及执行节点。

4.1 判断错误的计算结果

在 3.6 节的定理 2 中，我们已经证明错误的计算状态将被验证节点几乎确定地挑战。形式上，验证节点向共识节点提交错误计算挑战（FCC）以供裁决。我们首先介绍必要的符号，然后继续指定 FCC 的细节和处理它们的协议。

命名法（如图 6 所示）：对于具有个块的执行收据，字段包含 .对于, 表示计算索引为 iii 的块的起始状态。是块末尾的最终状态（在计算完所有交易之后）。为了表示各个交易之间的（临时）状态，我们相应地扩展了符号。让索引 i 处的块包含个事务。对于, 表示计算块内索引为 k 的交易的输入状态。因此，是块末尾的状态。

消息 6：验证节点将此消息发送给共识节点以挑战特定的执行回执（）。特定于其中一个分块的计算输出状态，其中 chunkIndex 是中从零开始的索引（比较消息 3）

请注意，同时用作索引处下一个块的起始状态。因此，以及和指的是相同的。引入不同的命名法只是为了便于标记。定义 3 消息 6 中指定的格式良好的错误计算质询 (FCC) 质询执行收据（由引用）的索引处的一个特定分块。它提供了列表

图 6：术语说明状态承诺（例如，哈希）表示为垂直线，并用 Λ 表示。粗线可视化起始状态对于块，以及最终状态。此外，是计算块内索引为 k 的交易的输入状态。

定义 4 Protocol for Adjudicating a Faulty Computation Result 假设有一个验证者节点正在检查索引处的分块，并且不同意结果状态。在下文中，我们将验证者的表示为，将执行节点的状态承诺表示为。

验证者向共识节点广播并带有

共识节点在他们的下一个最终区块中发布 FCC（消息 2 中的字段）

被挑战的执行节点有有限的时间向共识节点广播（消息 7）。使用可验证的延迟函数 [32] 来测量时间。

消息 7：被挑战的执行节点向共识节点广播。

如果执行节点没有响应，它就会被罚没。共识节点将在下一个区块中包含相应的通知（消息 2 中的字段），其中还包括的输出作为等待证明。在这种情况下，裁决以执行节点被削减而结束。

为了防止被削减，执行节点必须通过提交来披露块中的所有临时状态

到共识节点。如果执行节点发送，协议将继续下面的步骤 4。

共识节点现在逐元素比较双方的并找到第一个不匹配的。让第一个不匹配出现在索引处，即本质上，双方都同意，从状态开始，计算应该导致作为下一笔交易的输入状态。然而，他们在计算下一笔交易后的结果状态上存在分歧。

共识节点向任何一方请求状态。此外，共识节点通过解析区块中集合的文本，得到区块中索引为的交易，其输出有争议。

共识节点使用作为输入状态，计算分块中索引为的交易。共识节点现在将其本地计算的输出状态与, 和 , 进行比较。

任何一方发布的计算结果与共识节点计算的值不匹配，将被罚没。共识节点将在下一个区块中包含相应的通知（消息 2 中的字段）。

非正式地，定义 4 描述了一种协议，验证者节点可以通过该协议请求共识节点委员会重新计算验证者不同意其输出的特定交易。为避免被罚没，被挑战的执行节点必须提供共识节点重新计算相关交易所需的所有信息。然而，执行节点没有提供错误信息的余地，因为诚实的共识节点将根据先前发布的哈希承诺来验证正确性：

共识节点请求集合的交易文本。集合哈希以块的形式表示，允许验证集合文本。

共识节点请求双方同意的块中的最后一个中间状态。该状态的散列由验证者和被挑战的执行节点发布。这允许共识节点验证状态变量（例如，通过 Merkle 证明）。

此外，所描述的协议由所有诚实的共识节点执行。由此产生的罚没被包含在一个区块中，因此受到拜占庭容错共识的保护。假设绝大多数诚实的共识节点，可以保证行为不端的节点被削减。以下推论 3 形式化了这一见解。

推论 3

给定一个系统

超过 2/3 个共识节点的股份由诚实的参与者控制；

消息遍历时间受限制的部分同步网络条件。

以下成立。

如果一个诚实的Verifier 节点被分配去验证一个计算结果错误的分块，那么发出相应Execution Receipt 的Execution Node 将被罚没。

如果不诚实的Verifier 节点挑战正确的计算结果，Verifier 将被罚没。

4.2 解决丢失的集合

如消息 2 和 1 所示，一个区块通过哈希引用其集合，但不包含单个交易文本。交易文本由构建集合的收集器节点集群存储，仅当执行节点想要计算块的交易时才需要。因此，收集器节点集群可以保留交易文本以确保收集。虽然区块生产不受此攻击的影响，但区块执行会在无法访问所需交易文本的情况下停止。

当执行节点无法解析保证集合时，它会发出缺失集合挑战（MCC）。 MCC 是对保证丢失收集的收集器节点集群（消息 1，第 4 行）进行削减的请求。 MCC 直接提交给共识节点。

定义 5 解决丢失集合的协议

执行节点确定当前块中的交易文本不可用，如预期的那样。协议没有规定如何做出决定，但假设了明显的实现（询问担保人，等待响应，询问其他执行节点，等待响应）。

执行节点向所有收集器和共识节点广播 MCC。共识节点在下一个区块中记录挑战，但在这个阶段不以其他方式裁定挑战。

任何不是被挑战集群成员的诚实收集器节点向 κ 随机选择的担保人发送请求以提供丢失的收集器。如果请求得到答复，请求收集器节点会将结果转发给执行节点。

如果担保人未在合理的时间段 Δt 内作出回应，提出请求的收集器节点将签署一份缺失集合证明 (MCA)，包括相关集合的哈希值。时间是使用可验证的延迟函数 [32] 测量的，MCA 包含 VDF 的输出作为等待证明。 MCA 被广播到所有共识和执行节点。

诚实的质疑担保人将以完整的集合文本回应任何此类请求。

如果执行节点收到集合，它们将照常处理该块。否则，他们等待超过 $2/3 $个收集器节点提供 MCA。

适当的 MCA 必须包含在所有从区块中跳过一个或多个集合的执行收据中。

每个 MCC 将对每个执行节点和每个挑战的担保人进行小额罚没。即使 MCC 是通过找到 Collection 来解决的，这些参与者中的每一个都必须支付罚款，包括没有发起 MCC 的执行节点。这是为了防止以下边缘情况：

懒惰的保证只有在受到挑战时做出回应的懒惰：在挑战的担保人的情况下，即使在收藏得出的情况下，也没有动力要求担保人在不受到挑战的情况下做出回应。

来自拜占庭执行节点的虚假MCC：无罚款节点，可以通过不合理的MCC生成系统负载的零成本。

不要惩罚Messenger：所有执行节点都必须平等地罚款，以便没有拒绝成为第一个报告问题的执行节点。

如果密封了包含MCC的执行收据，则所有丢失收集的保证人均受到较大的削减罚款（等于运行收集器节点的最小含量要求）。

讨论

已解决的MCC的削减罚款应足够小，以至于它不会自动从网络中弹出收集器节点（通过将它们放置在最低含量阈值以下），但必须足够重要，可以说明解决一个问题的事实MCC非常昂贵。

解决MCC非常昂贵。每个收集器节点将向一个担保人请求收集，因此每个担保人都必须回应许多请求或被削减的风险。如果可用的话，每个执行节点将被收集的副本淹没。我们是根据理论运作的，如果MCC有很高的可能性正确解决（引理3），则伪造的MCC应该非常罕见，特别是由于所述的罚款。

如果大多数执行节点是拜占庭式的并提高了虚假的MCC，但是至少一个执行节点是诚实的，并且会生成完整的执行收据，则将密封正确的执行收据（假设收集器节点和共识节点的诚实超级劳动）。此外，提高虚假MCC的处决节点将被削减。

如果特定集合的大多数担保人都是拜占庭的，拒绝提供收集数据，但是至少有一个担保人是诚实的，则该集合将提供给诚实的执行节点并正确执行。

由100％执行恶意行动的100％执行节点可以通过不执行新块来阻止网络。然而，通过这种拒绝服务攻击，无法将错误的状态引入网络。

为了使攻击者获得将错误引入计算状态（具有不可忽略的概率）的能力，攻击者将需要控制100％执行节点的拜占庭分数和2个以上的验证器节点。

定理3 集合文本解析的活跃度

超过2/3的共识节点的股份由诚实的执行者控制；

超过2/3的收藏家节点的股份由诚实的执行者控制；

以及部分同步网络条件，具有界限的消息遍历时间。

可以配置该系统，以使任何保证的收集都可以使用接近1的概率可用。

定理 3 的证明

对于此证明，我们假设拜占庭节点最大程度地协作以防止集合被解析。除非有协议级别的保证，否则我们会考虑对拜占庭节点最有利的条件。让我们假设拜占庭节点成功阻止了集合的解析，即超过 2/3的收集器发出了 MCA。令

为收集器节点总数, 为诚实收集器的数量，以及̄为拜占庭收集器的数量；

生成缺失集合的收集器集群的大小， 集群中诚实收集器的数量，以及 集群中拜占庭收集器的数量；

缺失集合的担保人数量， 诚实担保人的数量，以及拜占庭担保人的数量。

我们考虑个收集器节点的系统配置，其中。在 Flow 中，集群是通过 Fisher-Yates 混洗将收集器随机划分为大小为的集群来创建的。因此，绘制具有 Byzantine 执行者的集群的概率由超几何分布给出

对于一个集合，至少需要担保人。拜占庭担保人的数量̄可以取中的任意值。集群中的拜占庭节点数量可能多于保证收集所需的数量，即。在这种情况下，我们假设只有最少需要的拜占庭节点数量才能保证收集最小化削减

由于每个诚实的保证人都会增加成功检索集合的概率，我们假设拜占庭节点仅涉及绝对最小数量的诚实节点以获得集合保证：

当一个不是担保人的诚实收集者收到 MCC 时，它会选择 κ 个担保人并向他们请求收集。我们假设只有诚实的担保人才会回答这样的请求。正确的节点在查询丢失的集合时没有收到任何答案的概率，即在 MCA 中发布，是

此外，每个不是集合担保人的拜占庭节点都会发布 MCA 以增加接受丢失集合挑战的机会。因此，有个来自拜占庭节点的 MCA。对于被视为丢失的集合，该协议要求收集器发送 MCA。因此，来自诚实节点的 MCA 的最低要求数量是

图 7：集合无法解析的最坏情况概率。该图显示了 P（接受 MCC）、等式 (25)、、和̄的数值

由于诚实节点独立联系担保人，每个诚实节点进行伯努利试验并发布概率为的 MCA。因此，r 个诚实节点发布 MCA 的概率服从二项分布

给定集群中拜占庭参与者的数量，系统接受 MCC 的最坏情况概率为

因此，接受 MCC 的总体概率是

图 7 说明了块丢失的最坏情况概率，即 MCC 根据等式 (25) 显示概率。

4.3 在由串通的验证节点检查的区块中放置错误

如果一个执行节点和多个验证节点串通，它们有能力在发布执行收据之前秘密确定哪些区块将被串通的验证节点检查。然而，第 3.4 节中定义的自分配方案独立于每个验证者，而且对于没有验证者私钥的任何人来说都是不可预测的。因此，诚实的验证者仍然会以统一的概率检查每个区块，独立于串通的验证者。

因此，如果恶意执行节点想要引入计算错误，则将错误放置在由串通验证者检查的块中没有任何优势。这一见解形式化为推论 4。

推论 4 ：给定一个具有部分同步网络条件的系统，消息遍历时间受$ Δt $限制。假设有一个恶意执行节点试图将计算错误引入块的其中一个区块中。拜占庭验证者的块选择不能增加成功概率。

致谢

我们感谢 Dan Boneh 进行了许多富有洞察力的讨论，感谢 Alex Bulkin、Karim Helmy、Chris Dixon、Jesse Walden、Ali Yahya、Ash Egan、Joey Krug、Arianna Simpson 以及 Lydia Hentschel 对早期草稿的评论。

参考文献

[1] Alexander Hentschel、Dieter Shirley、Layne Lafrance 和 Ross Nicoll。 Flow：分离共识和计算，2019 年。

[2] Silvio Micali、Salil Vadhan 和 Michael Rabin。可验证的随机函数。在第 40 届计算机科学基础年度研讨会论文集中，FOCS ’99，第 120 页–，华盛顿特区，美国，1999 年。IEEE 计算机协会。

[3] Timo Hanke、Mahnush Movahedi 和 Dominic Williams。 DFINITY技术概览系列，共识系统。 CoRR，abs/1805.04548，2018。

[4] Benedikt Bünz、Steven Goldfeder 和 Joseph Bonneau。以太坊中的延迟证明和随机性信标。 2017.

[5] Dan Boneh、Manu Drijvers 和 Gregory Neven。小型区块链的紧凑型多重签名。 In ASI-ACRYPT, 2018.

[6] Jae Kyun Kwon. Tendermint：无需挖矿的共识。 2014. https://github.com/cosmos/cosmos/tree/master/tendermint。

[7] 伊桑·布赫曼。 Tendermint：区块链时代的拜占庭容错，2016 年 6 月。

[8] Jae Kwon 和 Ethan Buchman。 Cosmos - 分布式账本网络。 2016. https://cosmos.network/cosmos-whitepaper.pdf。

[9] Guy Golan-Gueta、Ittai Abraham、Shelly Grossman、Dahlia Malkhi、Benny Pinkas、Michael K. Reiter、Dragos-Adrian Seredinchi、Orr Tamir 和 Alin Tomescu。 SBFT：一种可扩展的区块链去中心化信任基础设施。 CoRR，abs/1804.01626，2018。

[10] Ittai Abraham、Guy Gueta 和 Dahlia Malkhi。热填充线性、最佳弹性、单消息拜占庭容错魔鬼。 CoRR，abs/1803.05069，2018。

[11] J. H. Wensley、L. Lamport、J. Goldberg、M. W. Green、K. N. Levitt、P. M. Milliar-Smith、R. E. Shostak 和 C. B. Weinstock。教程：硬实时系统。 SIFT 章：飞机控制容错计算机的设计和分析，第 560-575 页。 IEEE 计算机协会出版社，美国加利福尼亚州洛斯阿拉米托斯，1989 年。

[12] M. Pease、R. Shostak 和 L. Lamport。在存在错误的情况下达成协议。 J. ACM, 27(2):228–234, April 1980.

[13] L. Lamport。弱拜占庭将军问题。 J. ACM, 30(3):668–676, July 1983.

[14] Heidi Howard。修订了分布式共识。博士论文，2018 年。https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-935.pdf。

[15] 辛西娅·德沃克、南希·林奇和拉里·斯托克迈尔。在存在部分同步的情况下达成共识。 J. ACM，35(2):288–323，1988 年 4 月。

[16] Michael J. Fischer、Nancy A. Lynch 和 Michael S. Paterson。不可能与一个错误的进程达成分布式共识。 J. ACM, 32(2):374–382, April 1985.

[17] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. HotStuff：具有线性和响应性的 BFT 共识。在 2019 年 ACM 分布式计算原理研讨会论文集中，PODC ’19，第 347–356 页，美国纽约州纽约市，2019 年。ACM。

[18] 弗拉德·赞菲尔。 Correct-By-Construction 共识协议的模板。 2017. https://github.com/ethereum/research/tree/master/papers/cbc-consensus。

[19] 弗拉德·赞菲尔。 Casper the Friendly Ghost：一个“通过构造纠正”区块链共识协议。 2017. https://github.com/ethereum/research/blob/master/papers/CasperTFG。

[20] Vlad Zamfir、Nate Rush、Aditya Asgaonkar 和 Georgios Piliouras。引入“最小 CBC Casper”共识协议系列。 2018. https://github.com/cbc-casper/cbc-casper-paper。

[21] Sarah Azouvi、Patrick McCorry 和 Sarah Meiklejohn。用 fantomette 押注区块链共识。 CoRR，abs/1805.06786，2018。

[22] Loi Luu、Jason Teutsch、Raghav Kulkarni 和 Prateek Saxena。揭秘共识计算机中的激励机制。在第 22 届 ACM SIGSAC 计算机和通信安全会议记录中，CCS '15，第 706–719 页，美国纽约州纽约市，2015 年。ACM。

[23] 谷歌。协议缓冲区。 https://developers.google.com/protocol-buffers/docs/proto。

[24] Håkan L. S. Younes 和 Reid G. Simmons。使用验收抽样对离散事件系统进行概率验证。 Ed Brinksma 和 Kim Guldstrand Larsen，编辑，计算机辅助验证，第 223–235 页，柏林，海德堡，2002 年。Springer Berlin Heidelberg。

[25] 以太坊基金会。帕特里夏树。 https://github.com/ethereum/wiki/wiki/Patricia-Tree。

[26] Yossi Gilad、Rotem Hemo、Silvio Micali、Georgios Vlachos 和 Nickolai Zeldovich。 Algorand：扩展加密货币的拜占庭协议。在第 26 届操作系统原理研讨会论文集中，SOSP ’17，第 51-68 页，美国纽约州纽约市，2017 年。ACM。

[27] 罗纳德 A. 费舍尔和弗兰克。耶茨。生物、农业和医学研究的统计表/已故的 Ronald A. Fisher 爵士和 Frank Yates 着。朗文 [Harlow]，第 6 版。修订和扩大。版，1974。

[28] Donald E. Knuth。计算机编程艺术，第 2 卷：半数值算法。 Addison-Wesley，波士顿，第三版，1997。

[29] G. Barrie Wetherill。验收抽样：基本思想，第 12-43 页。 Springer US，波士顿，马萨诸塞州，1977 年。

[30] E.G.先令和院长纽鲍尔。质量控制中的验收抽样。 CRC Press，2017。

[31] Juan Garay、Aggelos Kiayias 和 Nikos Leonardos。比特币骨干协议：分析与应用。 Elisabeth Oswald 和 Marc Fischlin，编辑，Advances in Cryptology - EUROCRYPT 2015，第 281–310 页，柏林，海德堡，2015 年。Springer Berlin Heidelberg。

[32] Dan Boneh、Joseph Bonneau、Benedikt Bünz 和 Ben Fisch。可验证的延迟函数。 In Advances in Cryptology – CRYPTO 2018 - 第 38 届年度国际密码学会议，2018 年，论文集，计算机科学讲义（包括人工智能子系列讲义和生物信息学讲义），第 757-788 页。施普林格出版社，1 2018。