Flow白皮书1-共识和计算分离(译)

在这个理论证明中,我们证明了共识和计算的分离可以使得 PoS 区块链网络中的资源利用率显著提高。对于常规PoS网络,一个区块在下一个区块被提议之前完成,吞吐量受到一小部分最慢节点的限制。而共识和计算的分离显著地将计算负载从共识节点转移到最快的节点。定理1中表明,共识和计算分离不会牺牲网络的安全性

本文翻译自Flow白皮书1-共识和计算分离,不带有个人观点。也不构成任何投资建议。

摘要

现有区块链架构已经被证明吞吐量是受限的,这是其被广泛采用的最大障碍之一。为了应对这一挑战在尝试侧链或Layer2解决方案,包括比特币的闪电网络或以太坊的Plasma网络,它们可以脱离主链工作。解决这个问题的另一技术是分片,即将网络分解为许多相互连接的网络。但是这些扩容方法打破了ACID(原子性、一致性、隔离和持久性),增加了应用程序开发的成本和时间。 在本文中,我们介绍一种新颖的方法,我们将矿工分为两个不同的节点类型。具体来说,选择、排序工作和执行工作将相互独立。本文的重点将介绍共识和计算分离,并证明这种方法增加了吞吐量但不影响安全性。 与大多数现有方案相比,我们的方法通过分离共识和计算来实现扩展,即更好地利用资源。这种方法使智能合约的编程范式(事务操作原子性)得以保持并且未增加额外复杂度。我们进行模拟网络试验,试验采用相同的共识算法(具有轮换区块提议者的两步提交协议),区块计算要么在共识节点执行(传统架构)或委托给专门的执行节点(共识和计算分离架构)。共识和计算分离使我们的系统与传统系统相比,在不损失安全性和去中心的情况下吞吐量增加了56倍。

内容

  1. 介绍
  • 1.1 相关工作
  1. 架构概述
  2. 理论性能和安全分析
  • 3.1 共识节点的特殊作用
  1. 进一步的工作
  2. 结论

1 介绍

最初的比特币区块链使用称为Nakamoto共识的共识模型。它使用顺序模型,在该模型中节点构建、挖掘和验证一个块,节点们在此之上构建后续的块。虽然POW保障了区块链链的安全性,但相应的计算工作量限制了出块速率和交易吞吐量。这种架构已经被证明吞吐量是受限的,这是其被广泛采用的最大障碍之一。 消除工作量证明开销的主要方案是采用拜占庭容错(BFT) 共识算法。使用POW 的区块链需要巨大的计算量以及电能。相比之下,通过BFT确定区块共识是高效的,但需要一组绝大多数诚实的参与者。 将 BFT 共识与权益证明 (PoS)相结合,可以创建具有强大安全属性网络。在 PoS 下,所有参与节点都必须质押权益(token),如果违反协议规则,可以将其扣除。赋予每个节点的影响力与其质押数量成正比。此外,存入的权益具有防止 Sybil 攻击的额外好处。 PoS增加链的吞吐量,降低保证链安全性的开销。但即使采用POS增加性能,吞吐量的限制仍然是区块链被广泛采用的障碍。 在本文中,我们探索了一种提升PoS区块链吞吐量的新方法。尽管PoS区块链方案消除了工作量证明,但他们倾向于从上一代的工作量证明系统继承大部分架构。特别是,网络中的每个全节点都需要检查和执行每个提议的区块并更新他们的本地副本以保持状态一致。因为每笔交易都需要被所有全节点处理,向系统添加节点对吞吐量没有好处。反而,添加节点会降低大多数BFT共识协议的吞吐量,因为最终确定一个块的消息复杂度会随着共识节点的数量超线性增加(参见第3.1 了解详情)。因此,大多数 PoS 区块链必须在一个小的共识委员会(削弱安全性)或低出块率(降低吞吐量)之间权衡。 对于不愿妥协安全性或去中心化的网络,解决扩展问题的最常见方法是通过分片或将工作从主 链移走(例如Lightning或 Plasma网络)。不幸的是,这两种方法都将对访问分布在不同地方的状态产生限制。这些限制极大地增加了应用开发者(基于智能合约)的复杂度。 我们提议的Flow 架构通过从根本上改变区块链。 Flow 将交易的选择和排序与其执行分离 这样两个进程就可以并行运行。解耦可以显著提高交易量吞吐量(高于其他区块链架构),而不会破坏安全性或去中心程度。 传统的区块链架构需要对每个区块状态的更新结果进行确认,作为共识过程的一部分。因此,每个节点都必须在区块确定前进行状态更新计算。我们发现确定区块中交易顺序时才需要共识。一旦该顺序确定,计算结果是确定的。因此,共识部分的计算量将显著减少。一旦交易顺序确定后,就可以委托后续进程执行计算,而不影响系统的去中心化。 我们的主要工作是第3部分,在那里我们讨论和证明我们的中心定理,即可以在不影响安全性的情况下将大部分计算和通信负载与共识分开。 本文的重点是介绍共识和计算的分离,并证明这种方法可以增加吞吐量,同时具备强大的安全保证。围绕本文介绍设计的区块链需要指定各种附加机制包含:

  • 用于验证计算结果的完整方案。
  • 共识算法的细节。
  • 完善的奖励机制和惩罚机制来激励节点遵守规则。 这些主题的介绍和分析留给后续文章。

1.1 相关工作

图灵完备的区块链通常会对一个区块内的计算施加上限,例如以太坊的gas限制。这样的gas限制反过来又引入了吞吐量限制。施加gas限制的一个原因是为了避免验证者的困境。通过将gas限制设置得足够低,验证的时间投入与完成POW中设定的挖掘区块挑战相比,可以忽略不计。因此,gas限制确保执行验证工作不会给节点成功挖掘下一个区块带来影响。 对于PoS区块链,验证者的困境仍然存在。特别是对于高吞吐量的区块链,大量交易的验证会消耗大量的计算资源和时间。通过分离共识和计算,共识节点不再有验证计算结果正确性的验证者困境。块中的最大计算量(块的gas限制)不会受到共识节点的限制。但仍然需要为验证者解决计算问题。解决方案包括zkSnarks、Bulletproofs和TrueBit。对于 Flow,我们开发了专门的知识证明 (SPoCK) 来解决验证者的困境,在后续的文章中有详细描述。 将事务排序问题与计算结果的工作分开的概念之前已经在分布式数据库领域提出过。事务通过共识排序到日志中,每个节点可以独立处理事务。然而,这些系统设计用于维护良好的数据中心,无需担心拜占庭攻击。 在区块链领域,Ekiden论文描述了一个共识与计算分离的系统,其目标是保护隐私。该论文解释了Oasis区块链技术的一部分,并指出这种方法可以提高性能。但它没有量化性能提升效果以及没有证明这种方法构建的系统将能够保证安全性。

2 架构概述

Flow 架构建立在计算和共识分离的原则之上。网络中有专门角色:共识节点和执行节点。这2种节点类型的核心区别是解决客观问题还是主观问题。客观问题是那些有客观的正确答案。任何传统的数学计算都是客观的;你不需要权威或专家确认2+ 2 = 4的正确性。主观问题没有这样的确定性解决方案。大多数人类治理系统(“法律”)通常处理主观问题。在不同社会的不同时期,有关规则可能会非常不同。共识一词的定义意味着在主观问题上达成一致,没有单一的正确答案。 传统的区块链架构要求参与网络的节点同时解决主观问题和客观问题。在 Flow 中,共识节点负责处理所有主观问题,执行节点仅负责完全确定的、客观的问题。我们简要介绍共识节点和执行节点。

共识节点 共识节点通过交易数据形成区块。许多节点就提议区块达成一致需要拜占庭容错(BFT)共识算法,本文的结论适用于任何具有确定终局性的BFT共识算法。 在Flow中,一个块引用它包含的交易并定义它们的执行顺序。但不包含块中交易执行完成后的状态。因此,共识节点不需要维护计算状态或执行交易。 此外,共识节点裁定来自其他节点的惩罚请求,例如执行节点产生了错误的输出。

执行节点 当按照共识节点确定的顺序执行时,执行节点提供确定交易结果所需的原始计算能力。当执行节点的输出结果被验证是错误的时候可以要求惩罚他们。一旦它们被验证是正确的,他们将为区块链当前的状态提供证明。验证过程——错误的结果被拒绝(会惩罚产生错误结果的执行节点),正确的结果被接受(在网络中被共享)。

48ccb968e505463eb4fe2b4c637d2213.png

图 1:通过共识和执行节点的消息流概览。为简洁起见,仅显示正常操作期间的消息。惩罚请求被裁定期间交换的消息被省略

3 理论性能和安全分析

在本节中我们将进行理论推导,证明可以在不影响安全性的情况下将大部分计算和网络通信从共识节点分离。 Flow的设计确保在由执行节点引入的错误会具备四个关键属性: 可检测的:根据定义确定性过程具有客观正确的输出。因此,即使是网络中只有单个诚实节点也可以检测到确定性错误,并通过指出执行错误的部分来向其他诚实节点证明这个错误。 可追溯的:Flow 中所有确定性的输出必须被生成这个输出的节点进行身份签名。因此,已检测到的任何错误可以清楚地追溯到负责该输出的节点。 可惩罚的:Flow网络中的所有节点,包括执行节点和共识节点,必须进行权益(token)质押,如果被发现具有不利于正确共识达成或输出错误结果的行为,将对这些节点进行权益(token)扣除(因为每个行为都是可检测和可追溯的)。 可恢复:系统必须具有在检测到错误时撤销错误的方法。这将阻止节点进行收益大于被惩罚的恶意行为。 这样的设计一个重要特征是对于系统内部的每个操作都可以找到对应参与者负责。具体来说,除了共识节点之外的操作,从节点中选择一个子集负责执行,另外一个不相交的子集负责验证结果。下面简单介绍工作过程:

  • 执行组和验证组都是随机选择的。选择的节点使用可验证的随机函数,这样结果是确定性的。
  • 任一组中节点的被包含的概率与其质押的权益(token)成正比。这要求节点必须锁定大量权益(token),才可能具备影响系统的可能性。这会强化系统对女巫攻击的抵抗力。
  • 两个组内节点要求质押的权益(token)要足够高,这样每个组分到全是恶意节点的概率就非常小。
  • 只要任一组中至少有一个诚实节点,诚实节点就会检测到错误并标记。
  • 如果标记了错误,共识节点将进行裁定,确定是错误后,恶意节点将被惩罚,操作结果将被拒绝。

上述过程保证了恶意执行节点几乎可以肯定被惩罚。此外,恶意节点几乎不可能成功引入错误。 可能出现的一个问题是,为什么 Flow 具有独立的执行者组和验证者组而不是执行者来验证彼此的结果。我们通过这种分离解决验证者的困境。如果没有专门的验证者角色,执行者计算下一个块与验证(重新计算)之前块的结果之间存在利益冲突。在 Flow 中,这种困境通过专门的验证者得到缓解。关于验证协议的技术细节将在后续文章中介绍,其中包括了如何解决验证者不进行计算批准任何结果或验证者恶意标记正确的结果导致网络阻塞等问题。 以下定理介绍了Flow架构的安全保证并证明通过发布或批准错误结果将错误引入系统是经济的不可行。 定理 1(将工作委托给执行组和验证组从攻击成功的概率上看是安全的) 如果按照以下条件约束,则通过故意发布错误结果或验证通过错误结果将错误引入系统在经济上是不可行的。

  1. 操作委托给两组随机选择的节点:
  • (a) 一组执行者:该组的成员执行操作。
  • (b) 一组验证者:该组的成员验证执行的结果。
  1. 只要两组同时都选中全部是恶意节点的概率足够低,两个组的节点规模可以相对较小。
  2. 执行组在生成执行结果时,验证者组的节点对他们来说是不可知的。
  3. 共识节点
  • (a) 绝大多数节点对公布的结果做出了承诺,并且参与节点无异议
  • (b) 或裁定异议,确定故障节点(可归因),并惩罚它们。

需要强调的是,共识节点只需要检查是否有足够的节点执行并对其验证就足够了,他们不需要检测结果本身。定理1适用于任何具有确定终局性的BFT共识算法。

定理 1 的证明: 我们将证明定理1在符合以下条件时总是可以满足

  • 两组中至少有一组从由诚实节点占据多数的大量节点抽取的;
  • 恶意节点不能抑制诚实节点之间的通信,即,如果有一个诚实节点反对结果并证明其错误,错误节点将被惩罚。

具体来说,让我们考虑一组N个节点,我们希望从中随机抽取一个具有 n 个节点的子集。此外,我们假设最多有 M < N/3 个恶意节点。在下文中,我们将重点关注所有节点质押权益(token)均等的情况,即它们被包含概率是相同的。选中 m ≤ n 个恶意节点的概率由下式给出超几何分布

be39e0d41d9a43fa93ae429367a62c63.png

(译者注: (M m)可以认为等价于C(m, M)) 攻击成功的概率,P(successful attack),要求没有诚实节点,即全部选中恶意节点。因此 c96e1658d156445480320bf3527389e4.png

其中 Pn,N,M (n) 是正好全部选中恶意节点的概率

e914055c695c46e091a58211f311872e.png

(译者注:这里的存在一些公式,简单推导下 Pn,N,M(m)=C(m,M)C(n-m, N-M)/C(n, N),当m=n=k时 Pk,N,M=C(k,M)/C(k,N)=(M!/k! (M-k)!)/(N!/k! (N-k)!)= M!/N! (N-k)!/(M-k)! 这里的C(m,n)是大家都学习过的求组合方式,C(m,n)=n!/m! (n-m)!)

上式(4)表明,仅选中恶意节点的概率随着n的增加而严格单调递减。也就是说样本量n越大,只选中恶意节点概率越小。

节点通过发布错误结果或批准错误结果来故意攻击网络,我们假设存在奖励r,如果它的攻击成功,节点会收到这些奖励r。但是如果攻击被发现,该节点将被惩罚ξ。 攻击网络所产生的期望收入为

97982c5d2bd341fd828fca287a25cb44.png

为了使攻击在经济上可行,需要收入大于0 f1697ffbb8144a12823471ad6c581f1e.png

此外,式(4) 意味着 r/ξ 随着 n 的增加严格单调增加。当 n < N/2 时,r/ξ 随 n 呈指数增长。 式 (7) 的左侧 r/ξ 是安全性度量,因为它代表攻击系统的成本。举个例子,让我们考虑 N = 1000,M = 333,n = 10 的情况。为简单起见,假设对于发布或批准错误结果,该节点质押的全部权益(token)将被扣除。然后,为了攻击在经济上可行,成功奖励 r 需要是节点权益的 65343倍(译者注:由式7计算得来Pn,N,M=M!/N!(N-n)!/(M-n)!=333!/1000!990!/323!=(333...324)/(1000 ... 991) r/ξ=(1000 ... 991)/(333...324) - 1= 65343)。如果验证者每人质押 1000 美元,攻击者平均需要花费6530万美元覆盖质押被扣除的成本。当进一步增加n到 n = 20,攻击者需要花费 r/ξ = 5.2 * 10^9 倍质押权益(token)来发布错误结果。

总之,我们分析了将执行和验证委托给1个较多节点子集的结果。证明了通过发布或批准错误结果将错误引入系统在经济上是不可行的。这个结果适用于除共识节点外的其他节点。因此,共识节点只需要检查是否有足够的节点执行并对其验证就足够了,他们不需要检测结果本身。

定理1很关键,因为它允许我们:

  • 将大部分计算和通信负载与共识分开;
  • 根据不同的需求研制专业化的节点(而不是要求节点在所有方面都具有优秀的性能,达不到就降低网络吞吐量)

其他节点以小组的形式相互验证,而共识节点以及共识委员会内部完成验证。

3.1 共识节点的特殊作用

共识节点通过 BFT 共识算法确定事件的相对顺序。我们的结论适用于任何具有确定终局性的 BFT 共识算法,例如:HotStuff、Casper CBC或 Fantômette。

不同于其他节点的操作,共识节点在没有外部验证的情况下生成区块需要共识委员会的通过。区块的内容会被验证,如果发布的区块包含无效内容,共识节点将会被惩罚,但与其他操作不同(译者注:执行或验证)的是区块不会被重建。发布后外部各方可以检查最终确定的区块。但是,如果进行分叉攻击,双花攻击此时可能已经成功。为了提高整个系统的可恢复性,共识节点委员会应由尽可能多的质押节点组成。

对于一个简单的 BFT 算法,每个块的消息复杂度 η(所有 N 个节点发送的消息)为 O(N^2) 。更高级的协议实现O(Nlog N)或 O(cN),c是常量。整个共识委员会的总带宽负载 B[MB/s]为 B = β b * η β是整体网络阻塞率, b为消息大小 MB/s。 对于接收消息m并处理它的节点,增加延迟 L(m) = f(b) + process(m) 其中 f 表示接收 m 的网络传输时间, process(m) 表示处理 m 的计算时间。很明显,B 和 L 都很大程度影响共识算法的吞吐量。这高度依赖于选择的 BFT 协议,以及拓扑结构。其他因素包括延迟或带宽限制在底层网络硬件中。

目前,我们的目标是数千个节点的共识委员会。为了去中心化,应该是使得个人仍然可以运行节点并参与共识。因此,给定所需的网络阻塞率β和环境确定的函数 f,只有减小消息大小 b 或 process(m) 才能增加共识委员会中节点数量。

我们简要介绍如何同时减少 b 和 process(m)。各个过程的详细机制,请读者参考后续文章。

  • 我们将计算委托给专门的执行节点。消除了共识节点维护和计算状态的需要,这显著减小了process(m)。
  • 共识节点在正常运行期间不需要完整的交易数据。专门的收集器节点从外部客户端接收交易并将它们预打包成为集合。共识节点仅对集合引用(哈希)进行排序,这与处理单个交易数据相比,大大减少了消息大小b。

我们通过将我们的方法与 Vlad Zamfir提出的三角(译者注:这里三角是针对POS系统,因为要进行BFT投票所以低最终确定性延迟、低网络通信开销、多节点数量不能够同时满足,需要进行平衡)进行比较来结束本节(图2)。三角形表达了Zamfir对于POS系统的猜想。Flow通过将共识节点和执行节点进行拆分进行优化

  • 共识节点作为共识委员会。为了确保最终区块的安全性和快速生成,我们接受更高的通信开销(三角形左下角的角)。然而,不同于其他区块链,这种共识只决定一个区块内的交易顺序,而不是结果状态。该架构通过使用集合引用而不是完整的单个交易。进一步提高吞吐量并减少通信延迟,所有可能的计算都委托给其他节点类型。
  • 执行节点将解包并处理单个事务。在不涉及大量恶意节点情况下,收集器节点可以和执行节点直接完成无需共识节点。此外,任务可以由小组进行并行化处理,小组相互负责以确保正确的结果。只有恶意攻击期间,恶意行为才会报告给共识节点以进行裁定惩罚。

    e1cf51377b4b44839bf80616dd0aeded.png 图 2:Zamfir提出的三角;橙色代表共识节点;蓝色代表执行节点。

4 进一步的工作

围绕本文设计的区块链需要解决额外的问题,最值得注意的是验证计算输出的机制。一方面,拆分共识和计算工作提高了 Flow 的吞吐量。另一方面,必须关注计算结果状态的正确性,因为共识节点不会重复计算。 此外,在 Flow 中,区块不再包含状态的hash结果。因此,接收数据的节点无法基于已发布区块验证数据有效性。我们将在后续论文中介绍区块验证和保证计算结果的(称为块密封)技术细节。

5 结论

在这个理论证明中,我们证明了共识和计算的分离可以使得PoS区块链网络中的资源利用率显著提高。对于常规PoS网络,一个区块在下一个区块被提议之前完成,吞吐量受到一小部分最慢节点的限制。而共识和计算的分离显著地将计算负载从共识节点转移到最快的节点。定理1中表明,共识和计算分离不会牺牲网络的安全性。在简化的模型中,我们的模拟显示与共识节点包含共识和计算的架构相比,吞吐量增加了56倍。 作为以太坊,一种增加吞吐量的方式是设置算力要求。然而,这将使得新节点更加难以加入系统。在传统的工作量证明区块链中,大量计算资源集中在一小部分挖矿节点,而维护和更新状态在所有全节点上的计算量是一致的。 Flow 架构利用网络中自然的资源不平衡生态系统。少数具有海量计算和带宽能力的数据中心可以质押成为执行节点,以最有效地贡献其资源。相比之下,共识节点不存储或维护状态,因此可以在现有的个人设备上运行。

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2022-04-01 16:40
  • 阅读 ( 331 )
  • 学分 ( 1 )
  • 分类:公链

0 条评论

请先 登录 后评论
web3探索者
web3探索者

18 篇文章, 561 学分