1简介

1.1架构概述

1.2 设计原则

• 可检测：网络中任何诚实的参与者都可以检测到确定性故障并向所有其他诚实节点证明该故障。证明只需要要求其他诚实节点重做错误的部分。

• 可归属：出于性能原因，Flow 中的许多任务都是随机分配给一组节点的。虽然出于安全原因分配是随机的，但它基于可验证随机函数 (VRF) [6]。因此，检测到的任何故障也可以找到相关任务的负责节点。

• 可惩罚：参与 Flow 网络的每个节点都必须投入股份，当检测到的故障归属于该节点时，该股份将被罚没。通过罚没，可靠地惩罚错误是可能的，因为确定性过程中的所有错误都是可检测的（注释1）和可归属的。

• 可恢复：Flow 协议包含用于结果验证和解决潜在挑战的特定元素。这些元素作为对抗恶意节点向系统注入故障的尝试的对策。成功注入此类故障的概率可以忽略不计。

1.2.1安全性和活跃性

1.3 假设

• 共识和身份验证
• 参与系统的所有节点都是彼此已知的。
• 每个节点都通过其不可伪造的数字签名进行身份验证。
• 为了降低计算成本并保持系统的可持续性，Flow 的共识协议基于权益证明 (PoS)。

• 参与网络
• Flow 区块链的演变由固定间隔（注释2）组成，称为纪元(epochs)。
• 要参与网络，节点必须在具体的纪元中为该角色提供最低要求的股份
• Flow 节点可以参与多个纪元。

• 随机源
• Flow 需要一个可靠的随机源来为其伪随机数生成器提供种子。
• 随机性来源使每个种子都无法被任何单个节点预测，种子本身以完全去中心化的方式生成和发布。
• 在 Flow 中，我们使用分布式随机信标 (DRB) 协议 [9] 来生成完全分散的、可靠的随机源。

• 密码学原语
• Flow 需要一个可聚合的非交互式签名方案，例如 BLS [10]。

• 网络模型
• Flow 在部分同步网络上运行，消息遍历时间受 限制，节点的相关处理时钟受限制。
• Flow 使用拜占庭容错消息路由系统，以高概率保证消息传递。

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

• 诚实股份比例
• Flow 要求来自收集节点、共识节点和验证节点的2/3 以上的股份由诚实的参与者控制（每个节点角色独立统计）。我们将拥有超过 2/3 股份的一组节点称为绝大多数。绝对多数的诚实节点有可能保证 Flow 协议的安全性。

1.4 Flow的角色

1.4.1 收集者角色

1. 外部客户端将他们的交易提交给收集器节点。

2. 收集器节点收到提交的、格式正确（注释3）的交易后，收集器节点将其广播给集群的其余节点。
💡
注释3 正如我们在本文后面详述的那样，格式正确的交易已正确填写所有必填字段，并包含来自 Flow 的质押账户的有效签名

3. 一个集群的收集器节点将收到的这批交易打包到所谓的集合collections中。该集合的哈希引用会提交给共识节点，后续将被包含在区块中。

4. 收集器节点的每个集群一次生成一个集合。在当前的收集被关闭并发送到共识节点后，开始新的收集。

1.4.2 共识角色

1.4.3 执行角色

1.4.4 验证角色

1.5 状态、抵押和罚没

• 状态
Flow 区块链中有两种状态，称为执行状态和协议状态。这些状态中的每一种类型都是独立维护和更新的。两种状态都表示为键值存储。执行状态由执行节点维护和更新，而协议状态由共识节点维护和更新。
执行状态包含寄存器值，这些值通过交易执行修改。尽管系统执行状态的更新是由执行节点完成的，但更新的完整性由 Flow 的验证过程 [5] 控制。
另一方面，协议状态跟踪与系统相关的功能，包括所有质押节点、它们的角色、公钥、网络地址和质押数量。当节点被罚没、通过质押加入系统或通过取消质押离开系统时，协议状态会更新。共识节点直接将协议状态更新作为它们生成的区块的一部分发布。协议状态的完整性由共识协议保证。我们在本文的第 4 节中详细说明了受共识协议影响的协议状态的更新。

• 质押
Flow 中的节点需要存入一些质押才能运行角色。这需要节点提交质押交易。下一个纪元的质押交易发生在当前纪元的指定截止日期之前。一旦执行节点处理了质押交易，质押将从节点的账户余额中提取，并明确记录在执行收据中。在共识节点密封包含此质押交易的区块后，它们会更新受此质押交易影响的协议状态，并在持有封存的区块中发布相应的质押更新。质押节点通过区块奖励和交易费用得到补偿，所有角色都需要最低质押才能正式参与该角色。

• 罚没
Flow 的任何质押节点都可以检测到不当行为并找到那个提交该行为的质押节点。在检测到不当行为并中找到其归属后，节点会向故障节点发出罚没挑战。罚没挑战是由于不当行为和偏离协议而要求罚没抵押节点的请求，罚没挑战被提交给共识节点。作为负责更新协议状态的系统的唯一实体，共识节点裁定罚没挑战并相应地调整故障节点的协议状态（即抵押余额）。根据裁决结果，节点的协议状态（即权益）可能会在一个纪元内被罚没。罚没更新在后续区块中公布，并且在所有诚实节点处理包含相应权益更新的区块后立即对所有诚实节点生效。

2 预备知识

2.1 对抗模型

我们将诚实节点（即非拜占庭节点）表示为遵循 Flow 协议描述的节点。如果节点在任意点偏离 Flow 的任何协议，我们将其称为拜占庭节点。我们还假设质押节点对消息和查询的无响应是一种拜占庭行为。

定义 2.1 有效投票

在一组节点之间的共识过程中，我们将节点的有效投票视为对共识提案投赞成票的节点的总质押的比例。该比例将代表该组中节点的全部权益。
对于 Collector Role、Consensus Role 和 Verification Role，我们假设每个角色累积的 stake 中有以上属于诚实节点，其余为拜占庭节点所有。例如，收集器节点超过 2/32/32/3 的股份属于诚实节点，而其总股份中不到 属于拜占庭节点。

2.2 HotStuff

HotStuff [11, 12] 是一种分布式拜占庭容错（BFT）共识算法。在本小节中，我们对基本的 HotStuff 协议进行了总结。然而，为了简洁起见，我们列出了 HotStuff 提案中提出的优化改进，并请感兴趣的读者参考 [12]。
HotStuff 假设节点是保存相同共享复制数据（例如，区块链分类帐）的状态机，并旨在就复制数据的下一个状态（例如，要包含在其中的交易集）的转换达成共识，形成下一个区块）。 HotStuff 在部分同步的网络条件下运行。如果少于三分之一的共识节点的总权益由拜占庭参与者控制，那就是安全的。

---

该协议按轮次进行，即每个节点有一个本地计数器，节点要么达成共识或要么超时。为了活跃度，节点在每次由于超时而移动到新一轮时将其超时间隔加倍。在每一轮中，一个唯一的共识节点承担领导者的角色。节点可以通过在轮数上本地调用确定性函数来始终如一地识别每一轮的领导者。领导者通过准备、预提交和提交的三阶段提交协议推进共识。每轮的共识以领导者的区块提议开始，以就提议达成共识或超时结束。
在 Flow 中，我们假设从 HotStuff 的一个阶段移动到另一个阶段需要至少的有效投票赞成领导者的提议。领导者收集并汇总选票，并将汇总的签名广播到整个系统，作为进入下一阶段的证明。因此，每个节点可以通过确认至少有个有效投票来跟踪和验证每个阶段的共识进度的正确性。

---

HotStuff 协议的正确性通过安全性和活跃性定理 [12] 得到正式证明。安全性意味着所有诚实的节点最终将以相同的顺序提交相同的状态转换（即区块）。 HotStuff 的活跃性保证在经过全局同步时间后，有一个有限的时间间隔，使诚实的领导者能够推进这一轮以达成共识。
此外，HotStuff 提供了最终确定性deterministic finality。也就是说，该协议保证在提交的状态转换链中不会出现分叉。这实质上意味着复制状态转换的规范链（例如，区块的分类帐）仅充当附加链。因此，与许多现有的共识协议（包括比特币的工作量证明（PoW））相比，HotStuff（注释5） 中不会发生链重组。
💡
注释5 前提是拜占庭参与者控制的权益严格小于 1/3
与现有的基于 BFT 领导者的共识算法相比，使用 HotStuff 的优势包括 ：
• 有 n 个节点参与共识，HotStuff 的通信复杂度为 ，这使得故障或无响应领导者的切换相对容易。
• 领导者的提议失败或超时有可能被下一轮领导者恢复。
• 安全性高于活跃性，即无论底层同步模型如何，都保证 HotStuff 的安全性。但是，为了保证协议的活跃性和向前推进，应该传递全局同步时间。
• 在部分同步网络条件下运行的能力。
• 它具有所谓的响应特性，即诚实的领导者在受消息传输延迟（即）限制的时间内将协议推进到共识。
• 它具有最终确定性。

2.3 分布式随机信标 DRB

在 Flow 中，我们利用节点子集中的分布式随机信标 (DRB) 协议 [9] 以完全去中心化的方式生成无偏见且可验证的随机源。无偏见的意思是任何敌对方都不能操纵随机源使其达到所需的分布。可验证性的意思是一旦随机源被确定，它就可以针对协议的正确执行进行验证。作为一种去中心化协议，DRB 作为一种交互式多方协议在节点子集之间协同执行。
在 Flow 中，我们将 DRB 视为由三个多项式时间协议组成的两阶段协议：Setup、RandomGenerato和 Verify。
1. DRB 的第一阶段：参与者之间只发生一次的设置阶段。
2. DRB 的第二阶段：随机生成阶段，这是一个重复的操作，即在系统的生命周期内可能会发生很多次。每次参与者进入随机生成阶段时，他们都会生成一个随机字符串，表示为随机源。
在本文中，我们将 DRB 随机生成阶段的每一次执行称为一个 DRB 轮次。
• ：
• 是一个概率去中心化协议
• 输入：表示第个参与方，表示系统的安全参数
• 输出：参与方的私钥，即，以及一个公共验证向量，即。
• ：
• 是一个确定性的去中心化协议，各方协作生成一个新的随机源
• 输入：对于该协议中的每个参与方，输入是该方的私钥（即 ）和一个原型区块（即）
• 输出：该协议的输出是新的随机源，即
• ：
• 是一种确定性协议，由 DRB 的任何外部或内部方在本地执行
• 输入：生成的随机源（即 ）、其关联的原型区块（即 ）和 DRB 的公共验证向量（即 ）
• 输出：确定性地验证协议执行的正确性
DRB 还提供以下属性：
• 不可预测性：在新一轮 DRB 执行之前，对于每个概率多项式时间预测器 A，存在一个可忽略的函数 ，使得：
,其中 ：
• 是第 次执行 DRB 的输出
• 是与关联的原型块
换句话说，将所有生成的熵及其相关的原型区块提供给预测器 ，它无法在执行前预测下一轮的输出，除非系统安全参数的概率可忽略不计。
• 可验证性：给定一轮生成的随机源、其相应的原型区块以及协议的一些公共元数据，协议的任何外部方都可以验证生成的随机源。

2.3.1 DRB 随机生成阶段（阈值签名）

DRB 的主要思想是基于确定性和唯一的非交互式阈值签名协议。 BLS 签名原语 [10] 提供了所有这些必需的属性。阈值签名是称为 的四种多项式时间算法的元组。
• 用作阶段， 需要各方运行交互式且相对较慢的协议。允许使用 生成重复签名而无需显式重建它，从而保护其机密性；
• 元组）用作阶段，是非交互式且相对低成本的操作。
BLS 签名有n个参与方，表示为集合 。并由两个参数标识： 和。阈值签名表示，只要方的集合中有t个参与方以去中心化的方式使用分布式密钥在消息上协作生成聚合签名，就能完成阈值签名。
阈值签名使任何实体都能够根据分布式密钥有效地验证 $m $上的有效签名。验证仅通过验证聚合签名来完成，不需要个人签名。
• ：
• 是一种概率性多项式时间算法，在接收到安全参数时，它会隐式生成一个密钥 ，尽管是由各方共同生成的，但它仍然是秘密的并且没有明确计算。并将各个密钥份额分配给第个参与方，即。
• 此外，生成一个公共验证向量。使各方能够恢复彼此的公钥份额。
• 第 方的公钥，我们指的是与关联的公钥 。 还包含参与方组的公钥，即与关联的 。
• ：是一种确定性多项式时间算法，由每一方单独执行。在收到消息 和第方的私钥（即）后， 在消息 上生成一个归属于第方的签名 。通常也称为第方的阈值签名份额。 Sign 与 BLS 签名方案中定义的签名函数相同。
• ：是一种确定性多项式时间算法，可由系统内部或外部的任何实体执行。在收到不同的阈值签名份额和相应的不同方列表后，组合所有签名份额并恢复组签名，即。在同一消息m上具有多于个各方签名份额的任意组合，生成一个组签名 ，该组签名归属于组密钥，即。
• ：是一种确定性多项式时间算法，可由参与方组内部或外部的任何实体执行。在消息 上接收到恢复的阈值签名（即 ）时，如果签名是使用组密钥（即 ）生成的，则返回 True，否则返回 False。 Verify 与 BLS 签名方案中定义的签名函数相同。
协议 1
显示了特定原型区块的 DRB 随机生成轮次，即。为了生成新的随机源，每个节点 计算并广播 上的阈值签名份额。在原型区块上收到至少个不同的阈值签名份额 后，任何一方都可以使用函数将签名聚合恢复到一个阈值中签名。如果签名 的格式正确，则可以根据组 G 的公钥对其进行验证，即。此 DRB 随机生成轮次的随机性来源是 。的确定性哈希摘要用于在当前回合中为伪随机生成器提供种子。



在 Flow 中，我们使用 [13] 作为 DRB 的底层阈值签名方案，它是非交互的并提供唯一签名。所谓非交互式的意思是协议是由单轮通信建模的。唯一性是 BLS 方案的一个继承属性，它意味着每对都存在一个唯一的聚合阈值签名。因此，聚合的阈值签名是确定性的，并且始终相同，无论同一消息上收集的阈值签名份额的子集如何。非交互特性是为了改进 DRB 协议在多个执行实例（即轮次）上的通信复杂性。唯一性对于保证独立于阈值签名份额子集的一致随机性来源至关重要，即，个阈值签名份额的每个有效子集都会产生相同的聚合阈值签名。

2.3.2 DRB 设置阶段（分布式密钥生成）

分布式随机信标（DRB）设置阶段是为门限签名协议生成密钥。如Protocol 2所示，Flow中DRB的建立阶段主要是门限签名的函数。在此阶段，组的各方协作执行分布式密钥生成协议 () [14] 作为 函数的去中心化实现。 隐式生成一个组密钥 。结果，每一方 都会收到公共验证向量 及其个人私钥 。密钥 是使用所有参与方以无偏方式提供的熵生成的。它对所有参与者都是未知的，尽管它可以被接收到超过份密钥的任何一方重建。
Flow 中实现的 是 Pedersen 协议的变体，称为 Joint-Feldman [14] 协议。它是一种基于离散对数的协议，主要由 可验证秘密共享 () 协议的 次并行执行组成，每一方都在一个实例中充当领导者。虽然已经证明 协议不能保证密钥 的均匀分布，但 Flow 中 的安全性是基于离散对数问题的难度，不会因分布偏差而减弱。
协议 2



2.4 Flow中的分布式随机信标设置

为了准备 DRBDRBDRB 协议密钥，我们假设 DRBDRBDRB 的设置阶段在每个 epoch 发生一次。在设置阶段，nsn_sns**** 个共识节点的协议选择子集共同执行 DRB 设置协议。通过执行设置协议，每个节点$ i$ 生成其用于阈值签名的 DRB 私钥 $sk_i $以及公共验证向量 VGV_GVG。如第 2.3 节所述，$(n, t) $是门限签名方案的参数。破坏最多 ttt 方的对手无法伪造有效的阈值签名。还要求至少有 $t+1 $方诚实行事，以保证协议的活跃性。为了以高概率满足这两个属性，即不可伪造性和活性，我们计算 t 如下。



在 Flow 中，为确保在安全参数（即 ）下，大概率保证系统的不可伪造性和活跃性，设置 DRB 委员会节点数量足够小，以保持 DRB 的相对于复杂操作的执行效率。

3 集合形成

3.1 概述

在Flow中，集合形成（Collection formation）表示从用户代理向收集器节点提交交易开始，到收集器节点向共识器节点提交保证集合结束的过程。收集器节点被划分为集群。每个交易都根据其交易哈希分配到某个集群。用户代理向负责集群中的某些收集器节点提交交易。收到交易后，集群内的收集器节点会在彼此之间广播交易。集群内的收集器节点不断地就正在构建的集合中包含的交易集形成共识。作为共识的结果，集合会随着时间的推移而增长。一旦满足两个条件之一：集合大小达到阈值或预定义的时间跨度已过，集合将关闭并提交给共识节点以包含在一个区块中。

3.2 集群形成

在 Flow 架构中，股份是节点责任的衡量标准。特别是对于收集器节点，处理提交的交易的工作量问责以及因此获得的补偿和他们在每笔已处理交易上的质押存款成正比。为了使所有收集器节点承担同等的责任，我们需要一种设置，其中所有收集器节点对于每笔已处理交易的质押保证金都是相似的。在这种设置下，收集器节点会在处理提交的交易时，在它们之间产生均衡的工作负载分配，可以阻止收集器节点的非均匀权益分配和工作负载不均匀。
尽管我们的收集器节点原则是平等的，但用户代理有权将他们的交易提交给他们选择的任意收集器节点，这会导致工作负载及其相关奖励的偏向分布。随着时间的推移，用户代理可能会与收集器节点建立关系，例如运行收集器节点提供的客户端软件，提交给提供更好服务质量的收集器节点等。然而，这导致收集器节点上的负载分布不均，并降低了系统的去中心化。例如，一个收集器节点可能会提供比其他收集器节点高得多的利用率，吸引更多的奖励，并从根本上剥夺其他收集器节点的收入。
为了使所有收集者的每笔已处理交易的押金都具有可比性，Flow 引入了集群的概念。几个收集器节点被分组到同一个集群中，以收集和处理同一组交易。换句话说，不存在一个交易池，每个收集器节点都可以从该交易池任意选择要处理的交易，而是使用随机源在每个交易和收集器节点集群之间进行单向确定性分配。收集器节点的集群在每个纪元开始时完成，例如每周一次。
表示系统中收集器节点的数量；表示集群数量，即收集器节点被随机划分为个集群。
两个不同集群的大小最多相差一个节点。并且该分配算法是可验证的，即每个节点都能够离线运行集群化算法，并与其他每个节点实现相同的集群分配。这样用户代理能够有效地将其签名的交易映射到负责处理该交易的收集器节点集群。
集群的分配由运行集群分配算法的每个收集器节点完成，如算法 3.1 所示。
该算法的输入是：
• 所有收集器节点的公钥列表
• 集群数量
• 由分布式随机信标生成的随机源
该算法的输出是，它是从收集器节点的公钥到它们分配的集群的映射，即对于每个 ，元素 是收集器节点分配的集群 ID。
集群化是通过从随机源导出种子来完成的，用于收集器节点的集群分类（算法 3.1，第 1 行）。种子以确定性方式导出，并具有与相同的熵。然后，Fisher-Yates洗牌算法 [15] 在收到种子和收集器节点公钥列表后，使用派生的种子将 转换为收集器节点公钥的伪随机排列，用 表示。请注意，由于是的排列，因此它与具有相同的基数，即 （算法 3.1，第 2 行）。
一旦确定了排列，聚类算法就会将收集器节点划分为个集群。它通过将前个收集器节点放到编号 0 的集群中，将第二个个收集器节点放到编号 1 的集群中，类似地，将大小为的收集器节点的第个序列放到到编号中。是每个集群的大小，并确定为



（算法 3.1，第 3-10 行）。
如果收集器节点的数量是集群数量的倍数，聚类算法根据它们在排列 中的位置将收集器节点分层为 c个大小的集群k。如果收集器节点的数量不是集群数量的倍数，则基于第 3-10 行的聚类会导致一些收集器节点剩余（具体而言，剩余的 Collector Node 数量将小于c）。在那种情况下，聚类算法不会创建额外的集群来容纳剩余的。它通过将剩余的第 i 个收集器节点添加到第 i 个集群。这种情况下剩余的大小是 。算法 3.1 具有 的渐近时间和内存复杂度，并且不会给系统带来通信开销。



3.3 交易提交

清单 1 表示用户代理提交给收集器节点的Flow交易结构。



清单 1：用户代理将交易广播到指定集群的多个收集器节点
在这个清单中，
• 对应的是交易的内容。交易的内容操纵 Flow 的执行状态，并需要承担相应的交易费用。
• 对应于支付交易费用（例如 gas 费用）的账户创建的签名。
• 交易的 对应于执行状态所有者的签名，它授予交易操作其可执行状态的权限。交易可能操纵可执行状态的几个部分，因此可能需要多个可执行状态所有者的签名。
• 指向前一个区块的哈希值，用于提供交易处理的截止日期。每个提交的交易都必须在有限的区块窗口内处理，例如 指向的区块与交易出现的区块之间的区块高度差异应小于预定义参数。例如，假设交易的窗口大小为 10 个区块，并且交易指向其 中高度为 1000 的区块。这意味着交易只能在高度为 1001 和 1010 的区块之间处理，否则交易无效。
令 表示 的散列，解析为无符号整数。为了提交该交易，用户代理负责指定收集器节点集群。计算方法如等式（2）所示完成，其中对应于系统中的集群数。哈希 的交易应该提交到的集群的索引是:



在 Flow 中，通过执行上面的算法 3.1，可以很容易地以确定性方式计算收集器节点属于哪个集群。因此，用户代理同样可以使用算法 3.1 和等式（2）有效地将其签名的交易映射到收集器节点的集群。交易提交由用户代理将其签名的交易发送到具有由等式（2）驱动的索引的集群来完成。将交易发送到集群的意思是发送到属于该集群的至少一个收集器节点。然而，为了在存在拜占庭收集器节点以及（网络）故障时实现容错，用户代理可以将相同的交易发送到指定集群的多个收集器节点。
在 Flow 中，我们将用户代理提交其交易所需的收集器节点数量交给用户决定。有的用户可能更愿意将所有或仅其重要交易发送到整个集群，而另一些用户可能更愿意仅将其提交到指定集群的单个节点。从用户代理接收到交易后，收集器节点根据等式（2）检查交易是否提交到正确的集群，以及交易是否格式正确。如果交易包含清单 1 所示的所有字段以及 Flow 注册帐户的有效和 ，则该交易是格式良好的。如果交易格式正确并且已提交到正确的集群，则收集器节点会将已签名的交易广播到整个集群。

3.4 形成集合

在 Flow 中，术语 是指一个或多个签名交易哈希的有序列表。收集器节点通过就交易哈希的有序列表达成共识来形成集合。如第 2.2 节所述，Flow 使用 HotStuff [11, 12] 作为共识协议。然而，任何具有确定性最终性的拜占庭容错共识协议都适用于该架构。在每一轮共识中，被选中的领导者要么恢复上一轮未完成或超时的提议，要么提出新的提议。提议要么将已签名交易的哈希列表附加到当前集合，要么关闭当前集合并开始一个新的空集合。对于共识的每个阶段，需要对领导者的消息进行至少次有效投票。收集器节点要投票赞成追加提案，必须满足以下所有条件：
• 收集器节点已收到所有已签名的交易，其哈希值反映在追加提案中。
• 附加提案中表示的每个交易哈希值都应该格式正确，并且至少由同一集群的一个收集器节点签名。
• 将提案中的交易附加到集合中不应导致重复交易。
• 当前正在构建的集合与收集器节点的集群已经保证的任何其他集合之间不应存在公共交易。
一旦消息具有的最小有效投票数 ，领导者就会聚合与个人投票相关的签名，从而将共识过程推进到下一阶段。这样，每个单独的收集器节点都可以以完全去中心化的方式验证共识过程的正确性。
最初，在每个收集器节点中创建一个新的空集合作为共享复制状态。在就附加操作达成共识后，已签名交易的哈希值将附加到集合中。一旦集合大小达到协议的预定义阈值，后续轮次的非拜占庭领导者就会提议关闭集合。关闭集合的共识是通过遵循 HotStuff 协议完成的。



保证集合Guaranteed Collection 的结构如清单 2 所示，其中 是封闭集合的哈希散列。 是已经生成集合并达成共识并关闭它的集群的 id（参见算法 3.1）。 持有保证集合的收集器节点的聚合签名。
为了使 被视为有效，应至少包含收集器集群的 个有效投票。我们将参与制作保证集合的每个集合节点称为该集合的担保人。通过签名一个集合，担保人证明了以下内容：
• 集合中的所有交易都是格式正确的。
• 他们将存储整个集合，包括所有交易的完整脚本。
在 Flow 中，我们将保证集合视为不可变数据结构。保证集合由保证人广播到所有共识节点，用于后续打包到一个区块中

3.5 活跃性

我们在介绍集合形成过程的安全性定理之前引入引理3.1，并直接将其作为集合形成过程安全性证明的一部分。
引理 3.1
给定一个由集群中的一组担保人生成的保证集合，如果该集合具有以下条件，则在系统中始终可用且可恢复：
• 网络模型：部分同步网络，消息遍历时间受限制，节点的相对处理时钟受限制
• 消息传递：一种容错消息路由功能，可保证消息的高概率传递
• 权益分配：所有收集器节点均等权益
• 诚实行为：诚实的参与者遵循指定的协议，并在系统中始终保持其可用性和响应能力
• 诚实下界：有保证的集合至少有一个诚实的担保人，
引理 3.1 的证明：如第 3.4 节所述，保证集合的担保人维护其原始副本，并且仅将作为 Guaranteed Collection 呈现的集合引用广播给共识节点。换句话说，一个保证集合应该被复制到它的所有保证者上，即签署它的收集器节点。假设保证集合的原始内容不可恢复。这意味着至少会发生以下情况之一：
• 集合的担保人均不可用或没有回应。
• 与集合保证人之间的消息传递受到攻击，例如路由攻击。
• 与集合担保人之间的消息传递没有时间限制。
• 集合担保人的处理时钟没有时间限制。
遵循诚实下界假设，在担保人中至少存在一个诚实的收集器节点，没有收集的担保人响应或可用与引理的诚实行为假设相矛盾，该引理说明诚实的必要性
参与者保持他们的可用性和响应能力。让有关保证人的消息传递受到攻击与该引理关于保证消息传递到保证人和从保证人传递的消息传递假设相矛盾。对保证人的处理时钟或与保证人之间的消息传递没有限制与引理的网络模型假设相矛盾。因此，我们得出结论，在引理 3.1 的假设下，只要存在至少一个有保证的集合的诚实担保人，集合就仍然可用、可访问和可恢复。
定理 3.2
（集合文本的可用性）给定一个具有以下属性的系统，存在 Flow 的配置，其中每个保证集合都有很高的概率可用：
• 网络模型：部分同步网络，消息遍历时间受约束，节点的相关处理时钟受约束。假定每个节点都具有针对网络攻击（例如拒绝服务攻击）的适当防御和保护。
• 消息传递：一种容错消息路由功能，可保证消息以高概率传递
• 权益分配：平等权益的收集器节点
• 拜占庭分数：超过个收集器节点的权益由诚实的参与者控制
• 诚实行为：诚实的参与者遵循指定的协议，并随着时间的推移在系统中保持其可用性和响应能力
定理 3.2 的证明：在我们之前的白皮书 [5] 中，我们已经表明，通过让，这些节点中的是拜占庭的，以及我们典型的个节点的集群大小，具有的概率拜占庭集群的可能性很小。
尽管 Flow 为维护集合的可用性而进行了主动的架构设置，但 Flow 还引入了一种反应机制（即 Missing Collection Challenge 注释6）来确认和罚没归属于丢失集合的拜占庭参与者 [5]。
💡
注释6 [5] 中对 Missing Collection Challenge 的分析（特别是其中的定理 3 证明）比此处提供的证明更广泛。在这里，我们假设一个诚实的执行者会在提出 Missing Collection Challenge 之前努力但没有成功地向所有担保人查询所需的集合。 [5] 中的分析还涵盖了懒惰或拖钓请求者的情况，如果被查询的子集没有响应，它可能会查询保证人的子集并提出挑战。
定理 3.3
（集合形成的活跃性）给定一个具有以下属性的系统，集合形成始终在推进中：
• 网络模型：部分同步网络，消息遍历时间受约束，节点的相对处理时钟受约束 6 缺失集合的分析[5] 中的挑战（特别是其中的定理 3 证明）比此处提供的证明更广泛。在这里，我们假设一个诚实的执行者会在提出 Missing Collection Challenge 之前努力但没有成功地向所有担保人查询所需的集合。 [5] 中的分析还涵盖了懒惰或拖钓请求者的情况，如果被查询的子集没有响应，它可能会查询保证人的子集并提出挑战。
• 消息传递：一种容错消息路由功能，保证消息以高概率传递 。
• 权益分配：平等权益的收集器节点 。
• 拜占庭分数：超过个收集器节点的权益由诚实的参与者控制 。
• 诚实行为：诚实的参与者遵循指定的协议，并随着时间的推移保持其在系统中的可用性和响应性。
定理 3.3 的证明：反证法，假设存在一个未知的时间点，对于该时间点，本节中描述的集合形成过程在所有时间点停止工作。通过停止收集形成，我们的意思是一旦过去，绝对没有任何收集器节点集群形成单个收集。这意味着至少以下情况之一适用于经过的系统，这会导致没有一个集群能够就关闭其收集达成共识：
• 每个集群中少于个收集器节点是诚实的。
• 向每个集群的至少个收集器节点的消息传递受到攻击，例如路由攻击。
• 与每个集群中至少个收集器节点的子集之间的消息传递没有时间限制。
• 每个集群的至少个收集器节点的处理时钟没有时间限制。
遵循定理的诚实行为和权益分配假设，少于个诚实的收集器节点与定理的拜占庭分数假设相矛盾。同样，将消息传递妥协到每个集群上至少个收集器节点的一小部分与定理的消息传递假设相矛盾。最后，对每个集群中至少个收集器节点的消息传递时间或处理时间没有限制与定理的网络模型假设相矛盾。因此，我们得出结论，只要定理的假设成立，集合形成就会进行。
值得一提的是，如前所述，我们认为拜占庭集群很少见。这样的集群可能旨在通过忽略所有提交给该集群的事务来损害系统的活跃性。然而，在检测到用户代理对活跃性的攻击时，代理可能会简单地尝试通过更改其交易的某些元数据来切换其交易的相应集群，例如，更改交易的 （参见清单 1）。这个微小的变化会导致交易的集群分配发生变化，因此它可以被路由到一个（非拜占庭）集群（见等式（2）），并因此被处理以包含在一个集合中。

4 区块形成

4.1 概述

区块形成是由共识节点执行以形成新区块的连续过程。区块形成过程有多个目的：
• 对新提交的保证集合中的交易顺序达成一致。
• 通过连续发布区块并确定一个纪元的长度来衡量经过的时间。
• 发布链中先前区块的封存。一个区块的结果一旦被共识节点最终确定，将由执行节点执行，并且执行结果被验证节点审批（更多细节见[5]），就可以密封了。
• 公布罚没挑战和各自的裁决结果。
• 发布协议状态更新，即 （罚没）、（抵押） 和 （撤回抵押）。每当节点的权益发生变化时，共识节点都会将此更新包含在他们的下一个区块中。
• 提供随机源（更多细节参见第2.3 节）。
万一没有新的保证集合，共识节点将继续使用一组空集合来形成区块。换句话说，区块形成过程永远不会被阻塞。
区块形成过程利用我们在第 2.2 节中描述的基础回合共识协议。
在 Flow 中，我们区分 和（适当的），它们在下面的 4.2 节中正式定义。 BFT 共识算法生成并最终确定 。 和（适当的） 之间的唯一区别是 ProtoBlockProtoBlockProtoBlock** 不包含任何随机源**。 Flow 中的各种过程都需要 中的随机源，包括在交易执行期间确定性地生成伪随机数，将收集器分配到集群等。因此，由于缺乏随机性的来源，无法被共识节点以外的节点处理。
BFT 共识协议生成 后，分布式随机信标 (DRB) 节点对 进行签名。他们对 的阈值签名是区块的随机源。
加上 DRB 的签名一起构成了（适当的）。虽然随机信标由一组共识节点运行，但生成随机性并不是共识过程的一部分。相反，在后续步骤中添加随机源以生成适当的区块。

4.2 数据结构

BFT 共识算法工作在 层面。在每一轮中，都会选出一个共识节点作为主要节点，其主要任务是为上一个 ProtoBlock 收集签名并提议下一个 。一旦 被提出，共识节点投票决定将其包含在最终链中。清单 3 中指定了格式良好的 的结构。我们在下面提供了 的各个字段的定义



清单 3：Flow 的原型区块结构
• 指向该区块在链上的直接前一个哈希值。通过指向前一个区块形成区块链。
• 对应于区块在链中的当前索引。形式上，区块链形成一棵以区块为顶点的树。区块的高度是树中相应顶点的深度。
• 是此区块引入的新保证集合的有序列表。如第 3 节所述，有保证的集合包括集合中交易的哈希值，但不包括交易本身。交易文本由保证收集的收集器节点存储，并根据要求由它们提供。
• 是对先前区块的已验证执行结果的哈希承诺列表。在从验证节点向共识节点提交至少个区块结果批准的有效投票后，密封区块就会发生，没有任何挑战待决。
• 是已提交给共识节点进行裁决的新罚没挑战的列表。任何抵押节点都可以向 Flow 网络中的另一个节点提交 slashing 挑战。例如，验证节点可以对执行节点的计算结果提交罚没挑战。
• 包含对作为执行此区块的结果的系统更新协议状态的密码学承诺。在 Flow 中，所有质押节点都遵循最近完成的区块来更新他们对系统的看法并发挥他们的作用。此外，在区块中发布此信息还充当系统状态更改的公共公告板。
• 包含投票赞成该区块的共识节点的聚合签名。
格式良好的区块的结构如清单 4 所示。它包含对所有必要信息的承诺，以便以确定的方式进行交易计算和演化协议状态。但是，从数据的角度来看， 并不是独立的。例如，虽然包括执行状态的加密散列，但不包括状态数据本身。这意味着任何人都可以使用区块中的哈希值（以及必须与实际数据一起提供的 证明）。
本质上， 只是 的包装器，它将 添加到区块中。形式上，随机源是来自 DRB 节点的重构阈值签名（有关详细信息，请参见第 2.3 节）。



4.3 区块形成过程

Flow 要求所有共识节点在响应事件时遵循相同的协议。我们用 表示的共识节点，来描述块形成过程的步骤。共识节点可以持有两个独立的密钥：
• 用于抵押。
• 如果共识节点是 DRB 的成员，它有第二个密钥 ，用于生成节点的阈值签名份额。
对于 Flow 网络中的节点 this，其角色、质押公钥、当前质押金额和节点的网络 IP 地址对所有其他节点都是已知的。此外，如果节点是 DRB 委员会的成员，那么它的公钥 也是公开的。

4.3.1 区块提议

遵循 Flow 的底层共识协议，使用概率但可验证的协议，共识节点被选为主要节点，概率与其权益成正比。被选为本轮主节点的共识节点必须提议下一个 。它包括有保证的集合、区块封印、罚没挑战、协议状态更新以及更新后对协议状态的承诺。随后，它将提议的 广播给所有其他共识节点。作为一种安全措施，底层共识协议有一个计时器来检测主节点的故障。如果主节点在这段时间内没有生成区块，则共识节点进入下一轮。
如前所述，如果没有可用的保证集合，主节点应该生成一个，其中包含一个空的保证集合列表（即 ），但仍包括潜在的块密封、协议状态更新、挑战、裁决等。值得注意的是，共识节点仅使用并决定集合哈希的顺序，而不是完整的集合文本。因此，他们不需要检查集合的交易，除非执行结果受到质疑 [5]

4.3.2 区块提案评估和投票

在主节点广播其ProtoBlockProtoBlockProtoBlock 后，其余共识节点评估提案并投票。如果每个共识节点批准提议的 ProtoBlock，则遵循本轮的共识步骤（参见第 2.2 节）。每个共识节点都运行协议 3，并且只有在满足所有列出的条件时才会投票支持 ProtoBlock。在协议 3 中，我们将当前的共识节点表示为“thisthisthis”。
Protocol 3 Flow 共识协议
Input： 提议的ProtoBlockProtoBlockProtoBlock: pb
Procedure ：
检查这些条件：
1. 的提议者是本轮选定的主节点， 由该节点签名。
2. pb 扩展了已知的区块链并且是创世块的后代（没有丢失块）。
3. pb是可以根据共识协议的规则进行安全投票的。
4. 包含一组新的保证集合或为空。
5. this已经在中收到了所有保证的集合。
6. 中的所有保证集合都经过身份验证（如 3.4 节中所定义）。
7. this已经在中收到了所有区块密封。
8. 中的所有区块封装根据[5]中的条件都是有效的。
9. this已经收到并验证了中的所有 罚没 挑战。
10. 将 pb 中列出的协议状态更新应用于父块的最终协议状态（由 引用）。
验证生成的协议状态是否与块中的承诺相匹配。如果所有这些条件都满足，则投票支持。

---

4.3.3 完成一个 ProtoBlock

共识节点签署一个 ProtoBlock 以表明他们的批准。在 Flow 当前的架构中，我们实现了 HotStuff，这是一种具有确定性最终性的 BFT 共识算法。然而，在不失一般性的情况下，任何其他 BFT 且具有确定性终结性的共识算法都是合适的。在 HotStuff 中，当在其之上构建了三个 ProtoBlock时，一个 ProtoBlock就被最终确定。为了在 ProtoBlock之上构建，HotStuff 需要来自共识节点的超过 2/3个有效投票。 HotStuff 协议的安全性保证永远不会有两个或更多的竞争块被最终确定。

4.3.4 随机源附件

在 Flow 中，可靠且可验证的随机性对于系统的拜占庭容错至关重要。 Flow 节点使用 的 字段来为多个伪随机数生成器提供种子。为了提供可靠的随机源，Flow 的 DRB 紧跟 Dfinity 的提议 [9]。协议 4 指定了为 生成随机源的步骤。
参与共识节点遵循两步程序来计算给定区块的 。
首先，他们签署 的散列并与其他 DRB 节点共享他们的签名。
其次，一个 DRB 节点等待来自其他 DRB 成员的签名份额。
在 的哈希上拥有超过 ttt 个不同的阈值签名份额后，每个 DRB 节点都可以在 ProtoBlock的哈希上恢复完整的阈值签名。阈值签名是区块随机性的来源，其摘要用于为伪随机生成器提供种子。一旦随机源准备就绪，DRB 节点就会向整个网络广播（适当的）Block。在协议 4 中，我们将当前的共识节点表示为“this”。
Protocol 4 ：Flow DRB步骤
Input： A ProtoBlock： pb
Procedure：
1. 第 1 步：签署原型区块
2. 广播到所有 DRB 节点
2. 第 2 步：等待个不同的阈值签名份额
1. 参见第 2.3 节）
2. 创建区块 b，其中 和
3. 将 b 广播到整个网络

4.4 协议状态更新

对于每个区块，人们可以将协议状态视为键值字典。协议状态中的密钥对应于节点的公共质押密钥 。相应的字典值存储节点的所有属性。质押节点的相关属性包括节点的角色、质押金额及其 DRB 密钥（如果适用）。
Flow 维护其协议状态的方式类似于以太坊处理其状态的方式：
• 协议状态直接由共识节点维护（与以太坊中的矿工相比）。
• 在区块中的所有协议状态更新都已应用后，每个区块都包含对结果协议状态的承诺。
区块协议状态的更改会传播到该区块的子块。因此，协议状态是相对于基本区块评估的相对概念。例如，有两个连续的区块 $A $和 BBB，其中 BBB 是 $A $的直接子块，从区块 AAA 到 BBB 的转换时，必须评估协议状态更新的正确性。如果链的未最终确认部分有分叉，分叉中的协议状态可能不同。
一个节点的协议状态可能会因为 slashing、staking 和 unstaking 而改变。任何抵押节点都可以向另一个节点提交 slashing 挑战。罚没挑战由共识节点裁决，节点的协议状态可能会相应改变。对于每个纪元，都有一个特定的区块高度（即协议确定的参数），在该高度之前，下一个纪元的所有新质押请求都必须作为交易提交。我们设想，在成熟的 Flow 中，这个区块高度被设置为使得质押期在新纪元之前大约一天（大约 80 000 个区块）结束。
为了进行质押，参与者提交包括其公共质押密钥的质押交易。一旦质押交易包含在一个区块中并由执行节点执行，通知就会嵌入到相应的执行收据中。执行结果封存时，共识节点会相应更新质押节点的协议状态。
对于取消质押，节点提交由其质押密钥签名的交易。一旦一个取消质押的交易在一个纪元期间被包含在一个区块中，它就会释放相关节点在下一个纪元的协议状态。未抵押节点的已释放权益被有效地保留，即它可以被罚没但不会返回到未抵押节点的帐户。在至少一个纪元的等待期后，质押返回到未质押节点。这样做的原因有两个。首先，检测和裁定协议违规可能需要一些时间。因此，需要一些延迟以确保有足够的时间在退还其股份之前罚没行为不端的节点。其次，为了防止远程攻击，其中节点取消质押，然后追溯行为不当，例如，共识节点签署替代的区块链进行分叉。

4.5 裁定罚没挑战

共识节点裁定罚没挑战并相应地更新协议状态。在收到来自节点（“挑战者”）针对被挑战节点的罚没挑战时，共识节点将其包含在一个区块中。这样做是为了在区块链中嵌入罚没挑战的官方记录。如果挑战包含完整的证明，共识节点会立即对其进行裁决。否则，他们等待被挑战的节点做出相应的回复。如果被挑战的节点在超时时间内没有回复，它会立即被罚没。否则，如果被挑战方以裁决挑战所需的数据作为回应，共识节点将处理数据并罚没任何有错误的人（即挑战者或被挑战节点）。在这两种情况下，共识节点都会在下一个区块中发布裁决结果以及协议状态更新。更新的结果会影响节点的权益。

4.6 正确性证明

HotStuff [11, 12] 是 Flow 共识协议的核心。Flow 仅对区块的有效性提出一些额外要求，HotStuff 协议对此不可知。因此，Flow 的共识协议的安全性来自于 HotStuff 的安全性。我们在以下推论 4.0.1 中形式化了这一见解。
推论 4.0.1（安全性）给定一个系统：
• 网络模型：部分同步网络，消息遍历时间受 $Δt 限制，节点的相对处理时钟受 φt $限制
• 消息传递：容错消息路由功能保证消息传递的概率接近 1
• 拜占庭分数：超过 2/3 的共识节点的股份由诚实的参与者控制
• 诚实的行为：诚实的参与者遵循指定的协议，并随着时间的推移保持其在系统中的可用性和响应性
• 共识协议：共识节点遵循 HotStuff ，这是一个具有确定性最终性的 BFT 共识协议
在这些先决条件下，协议 3 可以安全地抵抗拜占庭节点的任意行为。具体来说，拜占庭参与者不能通过故意发布或投票给错误的区块来引入错误。
此外，共识协议 3 具有确定性的终结性。 HotStuff [11, 12] 是一种通用的 BFT 共识协议，它与区块中包含的有效负载无关。换句话说，只要诚实的主节点有能力始终提出一个区块，区块有效负载的详细结构以及相应的有效性要求，就不会影响 HotStuff 的活跃性。
在 Flow 的共识协议 3 中，对于主节点必须放入区块中的内容量没有硬性要求。一个诚实的 主节点 只会包含有效的内容，或者提出一个空块。因此，Flow 的共识协议 3 的活跃性也直接来自 HotStuff，如以下推论 4.0.2 所述。
推论 4.0.2（活性）给定一个系统：
• 网络模型：部分同步网络，消息遍历时间受 $Δt $限制，节点的相对处理时钟受限制
• 消息传递：容错消息路由功能保证消息传递的概率接近 1
• 拜占庭分数：超过 2/3 的共识节点的股份由诚实的参与者控制
• 诚实的行为：诚实的参与者遵循指定的协议，并保持其可用性和响应能力随着时间的推移系统
• 共识协议：共识节点仅在根据 HotStuff 共识协议的规则是安全的情况下才对 ProtoBlocks 进行投票
在这些先决条件下，协议 3 是有效的，即协议将继续确定有效区块。

5 执行

执行节点遵循共识节点发布的新区块。保守的 （注释7） 执行节点只处理最终确定的区块，以避免在未最终确定的区块上浪费资源，这些区块可能会在以后被放弃。虽然只有共识节点积极参与共识，但所有其他节点仍然根据 BFT 共识协议的标准自行验证区块是否已最终确定。
💡
注释7 Flow 协议允许执行节点计算未最终确定的区块。这可能允许执行节点在专门奖励执行速度的激励模型中获得更多收入。然而，这样一个乐观的执行节点冒着为后来被放弃的计算块投入资源的风险。此外，与最终确定的区块相比，拜占庭容错共识算法不保证未最终确定的区块提案的有效性。因此，乐观的执行节点必须保护自己免受处理无效区块的影响

5.1 概述

如图 3 所示，在 Flow 中，当共识节点广播下一个区块已完成的证据时，执行过程被触发。在执行节点广播它们的执行收据后表示执行完成。执行节点负责接收最终区块，执行其交易，并更新系统的执行状态。在此过程中，每个执行节点执行以下步骤：
• 从相关集群中检索出现在最终区块中的每个交易集合。
• 根据最终区块中的规范顺序执行交易并更新系统的执行状态
• 为区块构建执行收据，即对区块执行结果的加密承诺
• 将执行收据广播给验证节点和共识节点。
我们将在本节的其余部分详细说明每一个步骤中，为了简单起见，我们从单个执行节点的角度来描述这个过程。在实时系统中，执行节点彼此完全独立运行并并行执行协议。



图 3：交易从收集到执行的生命周期。黄色六边形表示 Flow 管道中各个阶段的开始，例如区块封存（即交易收集）。箭头显示节点之间的角色间消息交换。绿色矩形对应于广播事件，其中一条消息被传播到所有被抵押的节点。为了简单起见，图中表示交易生命周期的正常流程，忽略了与裁决罚没挑战相关的消息交换

5.2 集合检索

一个保证集合只包含它所代表的交易集的哈希值，但不包含交易本身的全部内容。如第 3 节所述，签署保证集合的收集器节点还负责根据请求将交易全部内容发送给其他节点。
一旦执行节点自己确认一个区块已经完成（见第 4 节），它会向每个集群询问它们各自的集合文本，以便它可以开始按顺序处理交易。如果负责的担保人不提供保证集合，则节点可以向担保人发出 。挑战直接提交给共识节点。
在第三篇 Flow 技术论文 [5] 中详细讨论了。当执行节点检索保证集合的交易时，它会重建集合的哈希值以验证交易数据是否与保证集合一致。如果验证成功，则认为集合已成功恢复。

5.3 区块执行

当满足以下条件时，执行节点计算最终区块 bbb：
• b的前一个区块（由 引用的区块）的执行结果可从执行节点本身或另一个执行节点获得。
• 中的所有保证集合都已成功恢复。或者，执行节点有一个 ，这允许它跳过丢失的集合（细节在第三篇 Flow 技术论文 [5] 中有详细讨论）。
一旦执行节点执行完成区块，它就会向验证节点和共识节点广播执行收据。
清单 5 显示了执行收据的消息格式。 执行收据除了执行节点的签名外，还有两种数据结构：执行结果（字段）和（字段ZsZsZs）。我们将在以下第 5.3.1 和 5.3.2 节中详细介绍其中的每一个。



清单 5：Flow 中执行收据的结构。它由两个主要数据结构组成：一个 ExecutionResult 和一个或多个 SPoCK(s)

5.3.1 执行结果

区块$ b$ 的执行结果表示执行节点对计算区块 bbb 的中间和最终状态的承诺。如清单 6 所示，一个区块的执行结果包含：
• 区块哈希 ()
• 对前一个执行结果的哈希引用 ()
• 一个或多个分块 ()
• 以及执行这个区块后对系统最终执行状态的承诺（）
充当执行区块的开始执行状态的承诺。它允许将执行错误追溯到最初引入它的参与者。图 4 显示了这种情况的示例。值得注意的是，这个执行结果的链接序列可以称为“链”，但我们避免使用这个词，以免与共识节点维护的主要“区块链”混淆。
此外，如清单 6 所示，每个执行结果都有一个对其关联的区块的哈希引用。但是，为了简单起见，我们跳过了图 4 中区块引用的包含。一旦验证节点将计算故障归因于执行节点，它就会针对故障执行节点发出故障计算挑战（FCC）。我们的另一份白皮书 [5] 详细介绍了执行结果的验证和 FCC 的裁定。



图 4：执行结果的 previousExecutionResultHash字段可以识别并罚没最初向系统注入错误的恶意执行节点，而不是惩罚只传播错误的诚实执行节点。在这个图中，灰色的矩形代表正确的执行结果，红色的代表错误的执行结果。箭头对应于 previousExecutionResultHash 引用，即箭头右侧的执行结果从左侧的结果中获取其初始执行状态。诚实的执行节点-3产生的Execution Result中的错误归因于恶意的执行节点-2最初将它们注入到自己的Execution Result中。也就是说，执行结果的previousExecutionResultHash提供了一个归因链，使验证节点能够追溯错误，并识别并削减最初引入错误的恶意执行节点2，而不是惩罚诚实的执行节点3，只传播了错误。
执行结果由一个或多个分块组成。分块是划分区块计算的过程，这样生成的分块可以由许多验证节点以分布式和并行化的方式进行验证。一个区块的交易的执行被分成一组分块。分块是根据交易的计算消耗进行的，并且以一种方式进行，即分块的交易的整体计算消耗彼此相似并且不超过系统范围的阈值。
分块计算消耗的同质性是针对计算密集型分块中注入故障的安全对策。换句话说，如果分块的计算消耗是异构的，计算量较大的分块的验证节点可能无法在与这些分块相关联的实际区块密封之前完成验证[5]。这使得恶意执行节点能够通过将计算错误注入计算量大的分块来攻击系统的完整性，这些分块很可能被排除在验证之外。
分块的结构如清单 6 所示，其中：
• 表示分块执行前对系统执行状态的哈希承诺。
• startingTransactionCC和 startingTransactionIndex 是计算的消耗和分块的第一个交易的索引。
• 表示分块的整体计算消耗。分块约定是：。



清单 6：执行结果的结构和Folw中的分块

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

SPoCK 是 Flow 针对执行节点相互复制执行结果而不是自己计算块的对策。此外， 用于防止验证节点盲目批准执行结果而不进行验证工作。 在 [5] 中有详细说明，但为了本文的目的，理解 是密码学承诺就足够了，它是作为验证过程的一部分生成的，以表明验证节点已完成其工作。本质上， 是对单个分块的执行跟踪的承诺。字段 是 的列表，其中 是第 i 个分块的 。值得强调的是，可以通过仅执行第 i 个分块来生成。

5.3.3 执行算法

算法 5.1 表示执行节点为执行区块单独调用的 BlockExecution算法。该算法的输入是一个已准备好执行的最终区块 b、先前执行收据 herprev的哈希值，以及区块b执行前系统的执行状态，即 。算法的输出是一个执行b区块的收据，用表示。算法调用如下
执行节点按照规范顺序处理区块$ b$ 引用的交易。如图 5 所示，对于与区块 bbb 相关联的原型区块（protoBlock），交易的规范顺序是通过首先按照它们在原型区块中出现的相同顺序对其保证集合进行排序来实现的，然后对于每个集合，对其交易进行排序与集合引用的顺序相同。第一个集合的第一个交易和最后一个集合的最后一个交易分别是基于规范排序的块$ b $的第一个和最后一个交易。



图 5：红色显示具有交易的原型区块中交易的规范顺序。规范顺序为 1 和 的交易分别是原型区块顺序执行顺序中的第一个和最后一个交易。箭头对应于包含关系，即一个原型区块包含多个保证集合。虚线箭头对应于引用关系，即每个保证集合都包含对多个交易集合的引用。
执行节点通过函数解析与区块 关联的交易的规范顺序。
每个交易 的执行都是通过函数来完成的，其中 是区块 b 中遵循其规范顺序的第i 个交易。在接收到系统的当前执行状态 Λ 和交易文本 后，执行函数返回结果执行状态、的计算消耗，即 τ ，执行的 SPoCK，即（算法 5.1 , 第 9 行）。通过聚合自当前分块开始以来已执行交易的总计算消耗来跟踪当前分块的计算消耗（算法 5.1，第 22 行）。
对于每个交易，执行节点在添加交易时会检查当前分块的总计算消耗是否会超过阈值 。如果不满足阈值，则交易被视为当前分块的一部分，并且当前分块的 SPoCK（即 ）由 执行的 SPoCK 跟踪更新（算法 5.1，第 23 行）。否则，如果在当前分块中包含交易 之后达到了阈值 ，则执行节点关闭当前分块而不包含 。因此，交易被视为下一个分块的第一个交易。
为了在不需要撤销交易的情况下排除交易，算法通过跟踪执行状态。
关闭当前分块是通过为分块的起始状态生成一个承诺来完成的，该状态由 跟踪，并将分块属性转换为消息结构。
开始状态的承诺由 Flow 的身份验证状态证明系统生成，该系统提供三个确定性多项式时间函数：
为给定的状态快照返回一个可验证的哈希承诺 。形式上，Flow 的执行状态 由键值对组成。键可以被认为是内存地址，值是内存内容。由于只有一小部分状态值（即键值对）在分块中被触及，因此将完整状态传输到验证节点会效率低下。相反，执行节点仅传输检查其计算所需的键值对。
执行节点还提供一个证明，让验证节点检查接收到的键值对是否与分块中的状态承诺一致。执行节点通过运行 生成这些证明。这里，表示状态元素的键，表示相应的值。执行节点将发送给验证节点。
验证节点接收者可以通过执行 来验证这些值确实来自所需的状态。
一旦对当前分块的起始状态的承诺就绪， 就会创建一个新的 消息数据（参见清单 6）。生成的分块被附加到列表中，该列表包含正在执行的区块的分块。生成的分块的 存储在列表中，该列表包含区块的分块的 。
一旦当前分块关闭，算法通过重新初始化保持当前分块属性的变量移动到下一个分块（算法 5.1，第 12-21 行）。跟踪当前分块的第一个交易的计算消耗。
一旦区块 bb的所有交易都按照它们的规范顺序执行并创建了相应的分块， 从区块的哈希值（）创建一个执行收据（），前一个执行收据的哈希值（） 区块 b的所有分块列表（C），区块 b执行后系统的执行状态（），以及各自的。区块 的执行由每个执行节点单独向整个系统广播 后结束。



5.4 正确性证明

为了完整性，我们包括以下安全定理 5.1。有关详细信息和形式证明，请读者参考 [5]。
定理 5.1（安全性）给定一个系统：
• 网络模型：部分同步网络，消息遍历时间受限制，节点的相对处理时钟受限制
• 消息传递：容错消息路由功能，它保证以高概率传递消息
• 诚实行为：诚实的行为者遵循指定的协议并随着时间的推移保持其在系统中的可用性和响应性
• 拜占庭分数：至少一个诚实的执行节点
即使除了一个执行节点之外的所有执行节点都是拜占庭并发布相同的错误结果，错误结果未被封存的概率大于 。根据其系统参数，Flow 可以调整为。系统参数是：区块中的分块数和分块/区块的分数(每个验证节点检查)。
假设系统中至少有一个诚实的执行节点，每个区块都会发布一份有效的执行收据。由于 HotStuff 保证了区块形成的活跃性，因此也保证了执行回执生成的活跃性。
我们在下面的推论 5.1.1 中形式化了这个陈述。
推论 5.1.1（活性）给定一个系统：
• 网络模型：部分同步网络，消息遍历时间受限制，节点的相对处理时钟受限制 •
• 消息传递：容错消息路由确保消息以高概率传递的功能
• 诚实行为：诚实的行为者遵循指定的协议，并随着时间的推移保持其在系统中的可用性和响应性
• 拜占庭分数：至少一个诚实的执行节点
保证活动区块执行作为诚实的执行节点遵循指定的算法并最终为输入区块生成执行收据

6 缓解攻击向量

6.1 拜占庭集群

在成熟的 Flow 中，我们设想集群将由 20-80 个随机选择的收集器节点组成。虽然对具有太多拜占庭节点的集群进行采样的概率很小，但不幸的是它不可忽略。拜占庭集群可能会通过在其保证集合中注入错误交易来攻击系统的完整性。它还可能通过保留保证集合的文本来攻击系统的活跃性，以防止执行节点计算块。前者对系统完整性的攻击是遵循 Flow 的可检测性和可归因性设计原则来减轻的，即包含畸形交易的集合的保证人被罚没。后一种对集合可用性的攻击通过引入 Missing Collection Challenges（详见 [5]）得到缓解。这个挑战是对最初保证丢失集合可用性的收集器节点的罚没请求。挑战直接提交给共识节点进行裁决。

6.2 错误的计算结果

恶意的执行节点可能会发布错误的执行收据。然而，我们在[5]中正式证明错误的执行结果被验证节点以压倒性的概率检测和挑战。在检测到此类错误执行结果后，验证节点向共识节点提交针对错误执行节点的罚没挑战（更多详细信息，请参见 [5]）。

感谢

Karim Helmy 对我们的技术论文的持续支持和反馈。

参考文献

1. [1] Kyle Croman、Christian Decker、Ittay Eyal、Adem Efe Gencer、Ari Juels、Ahmed Kosba、Andrew Miller、Prateek Saxena、Elaine Shi、Emin G ̈un Sirer、Dawn Song 和 Roger Wattenhofer。关于扩展去中心化区块链。在 Jeremy Clark、Sarah Meiklejohn、Peter Y.A. Ryan、Dan Wallach、Michael Brenner 和 Kurt Rohloff，编辑，金融密码学和数据安全，第 106-125 页，柏林，海德堡，2016 年。Springer Berlin Heidelberg。
2. [2] 英国广播公司新闻。 Cryptokitties 热潮减慢了以太坊上的交易。 2017. https://www.bbc.com/news/technology-42237162。
3. [3] 理查德·丹尼斯和朱尔斯·帕格纳·迪斯。对比特币和以太坊的可扩展性的分析，第 619-627 页。 2019 年 01 日。
4. [4] 雪莉·迪特尔·亨切尔、亚历山大和莱恩·拉弗朗斯。 Flow：分离共识和计算。 2019.
5. [5] Alexander Hentschel、Dieter Shirley、Layne Lafrance 和 Maor Zamski。流程：分离共识和计算——执行验证。 arXiv 预印本 arXiv:1909.05832, 2019.
6. [6] Silvio Micali、Salil Vadhan 和 Michael Rabin。可验证的随机函数。在第 40 届计算机科学基础年度研讨会论文集中，FOCS ’99，第 120 页–，华盛顿特区，美国，1999 年。IEEE 计算机协会。
7. [7] 莱斯利·兰波特。证明多进程程序的正确性。 IEEE 软件工程交易，(2)：125–143，1977。
8. [8] Ethan Heilman、Alison Kendler、Aviv Zohar 和 Sharon Goldberg。对比特币点对点网络的 Eclipse 攻击。第 24 届 {USENIX} 安全研讨会（{USENIX} 安全 15），第 129–144 页，2015 年。
9. [9] Timo Hanke、Mahnush Movahedi 和 Dominic Williams。 Dfinity 技术概览系列，共识系统。 arXiv 预印本 arXiv:1805.04548, 2018.
10. [10] Dan Boneh、Ben Lynn 和 Hovav Shacham。来自 weil 配对的简短签名。 Advances in Cryptology ASIACRYPT 2001，第 514–532 页，2001。
11. [11] Maofan Yin、Dahlia Malkhi、Michael K. Reiter、Guy Golan Gueta 和 Ittai Abraham。 HotStuff：具有线性和响应性的 BFT 共识。在 2019 年 ACM 分布式计算原理研讨会论文集中，PODC ’19，第 347–356 页，美国纽约州纽约市，2019 年。ACM。
12. [12] Maofan Yin、Dahlia Malkhi、Michael K Reiter、Guy Golan Gueta 和 Ittai Abraham。 HotStuff：区块链视角下的 BFT 共识。 arXiv 预印本 1803.05069v6，2019。论文第 6 版。
13. [13] Alexandra Boldyreva。基于gap-diffie-hellman-group签名方案的门限签名、多重签名和盲签名。在国际公钥密码学研讨会上，第 31-46 页。 Springer, 2003.
14. [14] Rosario Gennaro、Stanislaw Jarecki、Hugo Krawczyk 和 Tal Rabin。基于离散日志的密码系统的安全分布式密钥生成。在密码技术理论和应用国际会议上，第 295-310 页。 Springer, 1999.
15. [15] Ronald A Fisher 和 Frank Yates。生物、农业和医学研究的统计表。奥利弗和博伊德有限公司，伦敦，194