1. 首页
  2. 业界观点

官方首次公开:IOTA拥塞控制算法

官方首次公开:IOTA拥塞控制算法

这篇文章从技术上详细解释了IOTA 2.0协议(Coordicide)中使用的IOTA拥塞控制算法(ICCA)。我们通过它来澄清我们上一篇关于法力的文章中提出的可用性和法力之间的关系。 此外,我们意识到许多人渴望了解更多关于Coordicide的信息,来自IOTA领域的利益相关者都会从这些知识中受益。也就是说,本文所包含的信息并不是使用IOTA所需的 “必备知识”。此外,本文中讨论的所有方面都将成为我们完整规范的一部分。如果您有问题,请访问我们的Discord,与我们的开发人员和研究人员讨论。拥塞控制是Coordicide的一个重要而迷人的方面,所以我们希望您能喜欢这篇解释。

我们要特别感谢Bob Shorten和他在伦敦帝国理工学院的团队,感谢他们在共同开发这一重要算法方面所做的工作。他们的工作在开发这个重要组件和验证其行为方面发挥了重要作用。

有关详细解释,请参见我们关于此主题的第一篇文章,该文章已被接受在第七届IEEE/IFIP新兴分布式网络技术安全研讨会上发表。

什么是拥塞控制,为什么我们需要它?

在大多数DLT中,信息是通过一个称为gossiping(”八卦“广播)的过程在网络中转发的,参与的节点从一个邻居那里接收消息,然后将它们转发给其他邻居。当然,节点会收到许多信息,因此它们必须决定将其中哪些信息转发给邻居,以及以什么顺序转发。而这些就是拥塞控制算法所需要决定的。

当网络的流量超过它所能处理的范围时,就会发生拥塞。如果没有适当的拥塞控制,网络可能会变得过饱和并停止运行,因为节点可能会用超过单个节点所能处理的消息来”淹没“邻居。通过决定转发哪些消息,利用拥塞控制算法来防止这种过饱和。在非碎片化DLT中,这个问题特别严重,因为每个网络参与者(”节点”)必须处理所有有效的事务。因此,网络的总吞吐量(非正式地称为每秒交易量)最终受到可用资源的限制,如互联网连接、设备处理和存储能力。

然而,由于拥塞控制算法决定了哪些消息被广播,它实质上决定了谁可以访问网络;拥塞控制算法对用户体验有着深刻的影响。为了阐明 “Coordicide”,作者想解释一下IOTA 2.0协议(Coordicide)中会用到的ICCA。

随着互联网基础设施的发展,拥塞控制一直是一个非常古老的话题,人们对其进行了深入的研究。然而,与大多数网络不同,DLT有非常严格的要求,这使得拥塞控制成为一个特别难以解决的问题。特别是,必须满足以下要求(还有其他要求,我们在下面进一步详细说明,但这些是最重要的)。

  • 公平接入:网络接入必须与某些 “稀缺资源 “按合理的比例给予;
  • 抗攻击能力:恶意节点无法破坏网络;
  • 一致性:所有节点都需要将相同的消息写入其本地分类账。

区块链通过使用一些机制来选举领导者来开采区块,从而解决拥堵控制问题。由于领导者被选中的速度与他们所拥有的股权数量(POS)或哈希能力(POW)成正比,因此访问是公平的。由于访问权限只限于领导者,所以即使在攻击期间也不可能出现拥堵。最后,由于区块链有一个共识模块来选举领导者,所以实现了共识。限制对 “领导者 “的访问,使得PoS和PoW架构更容易,但也集中了访问。

由于IOTA使用的是DAG,而不是区块链,所以我们不能(也不想)使用任何形式的领袖选举过程。相反,ICCA使用一种叫”调度器”的机制,它选择 “预定 “的消息。被调度的消息被写入本地纠缠,并转发给节点的邻居。调度器以恒定的速度调度消息,从而确保没有任何邻居被淹没。

现在我们可以讨论一下ICCA是如何实现我们上面提到的三个关键要求,公平接入、抗攻击和一致性。首先,我们可以看到,在本地,每个节点根据法力值公平地调度流量。事实证明,这在全球范围内也是成立的,根据法力值公平地授予访问权。

其次,如果攻击者试图对网络进行垃圾处理会怎样?在本地,节点处理攻击者的消息的速度不会超过其允许的速度。所以攻击者的消息会堆积起来,他们的队列也会增长。所有的节点都会检测到这一点,并将攻击者从网络中驱逐出去。当然,我们还研究了许多其他的攻击方法,但调度器是很难欺骗的,所以该算法对攻击者的抵抗力相当强。

最后,由于调度器从来不会删除诚实的消息,所以算法确保这些消息最终会到达所有节点。如果攻击者被驱逐出网络,他们发出的消息会怎样?由于攻击者的行为是可以检测到的,所以大多数节点会在同一时刻放逐攻击者,确保账本几乎相同。然后,gossip协议有一个叫做固化的机制,可以纠正纠缠中的微小差异。

下面,随着对要求的深入分析,你会发现ICCA的更多技术概述。

对任何DLT的要求

有一些一般的要求,其中有几个是任何DLT拥塞控制算法成功的关键:一致性、公平访问、利用率、合理的延迟和抗攻击性。

一致性

一致性是指每个节点向分类账写入完全相同的消息。当网络拥挤时,节点可能不得不丢弃一些消息,导致不一致。ICCA的目标是将消息丢弃减少到最低限度,并通过固化请求修复剩余的不一致。没有这一点,就没有共识。

公平准入

由于可用的网络资源是有限的,因此必须以某种方式来控制访问(相当于吞吐量)。在DLT中,通常通过 “稀缺资源 “限制访问来保证这一点。许多DLT通过要求矿工做PoW,将能量作为一种稀缺资源。权益证明(POS)型的DLT通常使用令牌本身作为稀缺资源;而IOTA使用法力(参见我们的法力博文及其后续内容)。

公平访问意味着所有节点都应该获得公平的吞吐量份额。需要注意的是,这种访问必须与法力的数量成线性比例:如果给予的访问是次线性的–用更多的法力给予越来越少的访问–那么大的行为者就会把他们的法力分给更小的节点以获得不公平的访问。 如果它是超线性的,那么大的持有者就有优势了。这将激励节点集中资源,就像矿池一样。亚线型和超线型的访问分配一般来说都是不公平的,并且促进了可能会损害网络的长期行为。

利用率

需求才能充分发挥网络的潜力。

例如假设这样一个访问控制方法,每个节点的吞吐量由其法力百分比来限制,比如10%的法力允许用户最多使用10%的带宽。这将是公平的,但效率低下:事实上,如果说95%的法力是离线的,那么网络将以5%的容量运行。一个高效的拥塞控制机制必须有办法重新利用这些未使用的容量。

结合利用率和公平性是很复杂的。”我需要多少法力值用于X TPS “这个问题很难回答。但请记住,利用率是个好东西!没有它,网络将无法使用。

利用率和公平性一起构成了一个概念,叫做 “最大-最小公平性”。这是经典网络中的一个重要概念。中继互联网流量的路由器需要这些确切的属性(想象一下,如果你的本地路由器不具备这些属性,你的家庭互联网将无法使用)。

合理的延迟

所有诚实的用户都应该经历类似的延迟。延迟是指发出的消息传播到所有节点所需的时间。为了良好的用户体验和协议的稳定性,这个延迟必须很小。

用户体验应该不言而喻,没有人喜欢延迟。但是,对于协议的稳定性来说,如果不同的用户的延迟有很大的不同,那么就会引入不正当的激励机制来偏离算法。从博弈论的角度来看,惩罚恶意节点的延迟是好的,这也是为什么如果节点行为不端时延迟增加,那么它们就会因为自己的行为受到惩罚。

抗攻击性

即使攻击者试图破坏系统,上述这些特性也必须对诚实的节点成立。节点有动力去增加它们的访问量,降低它们的延迟。偏差应该是不可能的,或者是受到惩罚的。

IOTA拥塞控制算法(ICCA)

IOTA拥塞控制算法(ICCA)简化了交易过程,以最大限度地减少潜在拥塞的影响,并调节对账本的写入访问。ICCA通过它的三个部分来实现:调度器、速率设置器和黑名单。

调度器决定哪些交易被写入账本并被广播。速率设置器使用经典的AIMD算法来调整每个节点的速率。黑名单对攻击网络的节点进行排查。

这–据我们所知–是加密货币领域内发表的第一个非工作证明、基于DAG的拥堵控制算法。它是Coordicide最新颖的组件,也是IOTA 2.0协议的基石。

节点模型

官方首次公开:IOTA拥塞控制算法

从网络层,消息通过邻居的八卦到达,过滤重复和无效的消息,然后到达收件箱,在收件箱中按照发件节点ID排队。收件箱还接收由节点的速率设置器在本地创建的消息。黑名单监控收件箱的队列是否有恶意行为,调度器决定哪些消息可以离开收件箱。 消息被调度后,以下任务同时发生。

  • 消息会被八卦到所有邻居,但不是我们收到的那一个(反馈给网络层)。
  • 相关的应用(来自应用层)被调用来解析有效载荷。
  • 消息 “写 “到本地账本并被视为一个”tip“,通过FPC公司算法投票,再记入账本等。

调度器

在ICCA中,我们提出使用一个修改版的赤字循环罗宾调度器(Deficit Round Robin scheduler,简称DRRS)。除了这种调度器能够满足上述所有要求(即一致性、利用率、公平性和抗攻击性)之外,我们选择它是因为它的轻量级。例如,它是Linux内核高效处理非常多线程的默认选项。

调度器的工作原理是这样的:在收到消息后,它们会被放入收件箱中。每条消息都会根据其消耗资源的多少被分配一个 “工作分数”。较大的消息有较大的分数,因为它们使用更多的带宽。一个包含100个签名的事务的消息比一个只有一个签名的事务有更高的分数,因为它需要更多的资源来验证签名。本质上,调度器确保每秒消耗的资源数量最多。开发这个的研究人员和工程师可以完全自由地定义这个工作函数,以使算法适应IOTA网络的确切需求。

当接收到消息时,它们会按其发出节点排序,进入不同的队列。调度器访问每个队列,根据发布节点所持有的法力(IOTA中使用的 “稀缺资源”)来调度一些消息,然后进入下一个队列。如果一个队列是空的,则跳过它;然后调度器从其他队列中调度。通过这种方式,所有节点的消息处理速度都与他们的法力值成正比,除非他们的队列变空。

节点的收件箱被划分为多个队列,网络中的每个节点都有一个队列;一个DRRS调度器可以有效地处理数以万计的队列。然后,消息被放置在发出消息的节点的队列中。调度器以确定的顺序访问每个非空队列。每个队列都会给该节点分配一个叫做 “信用点数 “的数量。当调度器访问一个队列时,它会根据对应节点ID的法力值按比例增加一定的优先级值。然后,它对该节点队列中的消息进行调度。每调度一次消息并进一步处理,消息的 “工作分数 “就会被扣除信用点数。当N的队列中没有更多的消息可以被调度或者积分变成负数时,调度器就会进入下一个队列。

目前,我们以固定/最大预设率来调度消息。同时我们正在分析和研究不同的手段,让这个阈值变成动态的,因为分片会让网络自然扩展。

但是,如果攻击者或自私的节点不遵守调度规则会怎样呢?假设一个自私的节点决定只转发自己的交易。这将导致其在诚实节点的收件箱缓冲区的相应队列膨胀,并只对自己的事务产生大的延迟。同样的情况也发生在恶意节点上:只要诚实节点遵循赤字循环调度器,攻击者的交易就不会被转发。

速率设定器

节点如何知道它可以发出多少条消息?它使用速率设定器。根据这个队列长度,速率设置器使用AIMD算法来调节自己的事务生成速率。互联网中的路由器也使用类似的算法来调整流量。

一个节点可以监控自己队列的长度。当这个队列变得太长时,它就知道自己发出的消息太多。节点缓慢地增加自己的发布速度,直到它的队列变得太长。这时,节点会迅速降低它的发出率,以防止即将到来的拥堵。最终,这使得速率设定器根据当前的流量状况,趋近于一个公平的发行速率。

作为一个额外的好处,速率设置器确保遵循协议的节点发出的交易延迟很低。不遵循该算法的节点将淹没其队列并增加其延迟。这样,节点就会被激励使用速率设置器。

如果恶意节点不使用速率设置器会怎样?如果他们不在乎增加延迟,例如垃圾邮件攻击怎么办?以下部分包含我们设置的安全措施,这些措施会在攻击者损害一致性之前触发。

黑名单

如果节点不使用速率设置器会怎样?那么当他们的队列增长时,他们不会降低速率,所以他们的队列会继续增长。因为其他诚实节点的内存只有这么多,不能让任何队列无限增长。所以,ICCA有黑名单来限制队列的长度。根据法力,一个节点只会允许有一定数量的消息进入队列。当这个数量超过一定的阈值时,该节点就会被暂时列入黑名单,也就是说,在一段时间内不会再有该节点的其他交易加入到收件箱中。如果一个节点的队列开始爆炸,则该节点的新入站消息会被丢弃。

速率控制

攻击者可以试图用大量的垃圾邮件来淹没网络,直接试图让数百个节点同时超载。为了防止这种攻击,我们使用了一种叫做速率控制的机制作为阻断,它从物理上限制了一个节点可以发出的消息量。为此,我们使用自适应的PoW作为速率控制机制。对于诚实的节点,PoW的难度相对较低。但如果一个节点开始发垃圾邮件,难度就会成倍增加,从物理上阻止它们发出更多的消息。所以,这个机制可以防止系统完全超载。

尽管速率控制机制很有用,但它未必是必要的。ICCA有足够强大的潜力,因此这个模块很可能是多余的。然而,在Coordicide协议的第一个版本中,我们希望保证最大限度的保护,潜在的后续减少或删除任何PoW都被留作未来的优化。在GoShimmer试验网中,我们将研究自适应PoW速率控制和ICCA之间的相互作用。

零法力值信息

不幸的是,ICCA要求节点有一定的法力值来发布消息,因为0法力值的节点永远不会收到信用点数,而没有信用点数,他们的消息将不会被调度。这对于避免垃圾攻击很重要:如果没有它,低法力值节点可能会制造交易的突发事件,从而使网络拥挤,影响账本一致性。

我们可以提供各种方案来让零法力节点能够发出他们的交易。一种方式是通过一个水龙头(Faucet–一种可以免费申请获得一小部分mana的机制),任何节点都可以自愿将其未使用的法力值提供给愿意尝试网络的新人,无论他们心中有什么用例。另一种选择是使用法力市场,你可以根据自己的需要决定如何和何时租用法力。此外,另一种方法还包括购买代币,并通过将它们质押到节点上进行转让。

最后,我们正在研究一种方法,根据活跃法力的百分比和当前的交通状况,动态调整最低法力门槛。

在低拥堵时期,”经过验证的低法力值节点 “被允许发布他们的交易,并将由诚实的节点进行调度。”经过验证的低法力值节点 “是指满足以下两个条件的节点:一是其法力值小于最低法力值阈值;二是该节点最近进行了一次大的PoW。当拥堵程度较低时,那么诚实节点会暂时允许这些经过验证的低法力值节点进行调度。一旦拥堵变大,经过验证的低法力节点就不能发出他们的交易,他们必须等待低拥堵期。

本文原文非中文版本,由BruceX进行翻译,如若转载,请注明出处:http://www.iota.love/202103/explaining-the-iota-congestion-control-algorithm/