他乡之客

副标题

摘要

关键词

NDN网络中的区块链技术：详细调查

摘要

​ 随着大规模的新应用和在线服务的出现，互联网的未来设计将有新的要求和影响，如兼容移动性、可扩展性、可靠性和安全性。命名数据网络（NDN）是最有前途的未来互联网架构范式，它专注于内容驱动的通信。与传统的IP网络不同，基于内容的命名数据网络（NDN）可以快速检索和传输内容。区块链技术已被广泛用于去中心化的支付、资产管理、医疗保健和云计算等。区块链提供了一个去中心化的分布式解决方案，在不可靠的网络中保持一致和可靠的记录，而不需要中心化的权威。然而，==区块链技术在IP上仍有一些严重的问题，如缺乏分层访问的效率。在NDN上使用区块链技术解决了这些问题，提供了一个去中心化的系统并简化了架构。==在本文中，我们首次对区块链技术在NDN中的应用进行了详细而全面的调查。最后，还讨论了一些研究挑战和关键问题。

关键词

NDN ，ICN ， Internet ，Named Data Networks ，Blockchain technology

副标题

副标题

副标题

透过区块链看拜占庭容错共识

摘要

​ 我们提出了HotStuff，一个基于leader节点的拜占庭问题(Byzantine fault-tolerant replication protocal， BFT)的部分同步(partially synchronous)模型。一旦网络进入同步状态，HotStuff算法将允许一个正确的leader节点以实际（相对于最大）网络延迟的频率（速度）推动协议达成共识依照某个频率（如最大网络延迟）发起共识，这一特性被称为响应性（responsiveness），并且通信复杂度与复制(replica)数量呈线性关系。据我们所知，HotStuff是第一个表现出这些综合特性的部分同步BFT复制协议。HotStuff是围绕着一个新颖的框架建立的，它在经典的BFT基础和区块链之间形成了一个桥梁。它允许其他已知的协议（DLS、PBFT、Tendermint、Casper）和我们的协议在一个共同的框架中表达。

​ 我们在一个有100多个副本的网络上部署HotStuff，实现了与BFT-MaRt相当的吞吐量和延迟，同时在leader故障切换期间拥有线性的网络通信次数（与之相对的，BFTSMaRt算法相同的功能需要使用$O(n^3)$次网络通信）。

介绍

​ 拜占庭容错(Byzantine fault tolerance, BFT)指的是一个计算网络在其副本节点遭遇任意错误（如拜占庭错误）时，如何保证关键的网络操作能够得以执行。在状态机复制（SMR）的背景下[35, 47]，整个系统提供了一个可复制的服务，该服务可以被镜像部署到网络的N个副本中。一个BFT-SMR协议用来保证没有出错的副本能够以统一的顺序执行一系列由客户端提交的指令，即使存在一些拜占庭节点尝试阻止网络达成共识。在一轮共识中，算法保证由n-f个未出错的副本能够独立的执行客户端指令，并产生该指令下相同且唯一的结果。正如常见的那样，我们在这里关注的是部分同步通信模型（Partially Synchronous Communication Model）[25]，即在某个未知的全局稳定时间（Global Stabilazation TimeGST）之后，信息传输的已知约束∆成立。在这个模型中，需要n≥3f+1的非故障复制体以相同的顺序对相同的命令达成一致（例如，[12]），并且只有在GST之后才能确定性地确保进展[27]。

​ ==当BFT SMR协议最初被构想出来时，典型的目标系统规模是n=4或n=7，部署在局域网上。然而，由于拜占庭容错在区块链中的应用，人们对其重新产生了兴趣，现在需要能够扩展到更大n的解决方案。==与无权限区块链（例如支持比特币的区块链）相比，所谓的有权限区块链涉及一组复制体，它们共同维护一个有序的命令分类账，或者说，这些副本支持了网络的SMR特性。尽管它们具有许可的性质，但设想了数百甚至数千个复制体的数量（例如，[42，30]）。此外，将它们部署到广域网络需要设置∆以适应更高的通信延迟变化。

​ **拓展性挑战（The scaling challenge）。**自从PBFT[20]（部分同步模型中第一个实用的BFT复制解决方案）问世以来，许多BFT解决方案都是围绕其核心的两阶段范式建立的。其实用性在于，一个稳定的leader节点可以在短短两轮的消息交换中驱动一个共识决定。第一阶段通过让一个副本获得包含 n−f 个投票的法定人数证书(Quorum Certificate, QC)，进而保证提议的唯一性。第二阶段则保证leader节点可以说服其他副本去向一个安全的提议投票。

​ 为新的leader节点收集信息以及向副本发送提案的过程，称之为视图转换(view change)，是整个网络的核心操作。不幸的是，基于两阶段范式的视图改变远不是那么简单[38]，容易出错[4]，甚至对于中等规模的系统也会产生巨大的通信费用。

它要求新的leader从(n - f)个副本中传递信息，每个副本报告自己的最高已知QC。即使只计算认证器（数字签名或消息认证码），在PBFT中，传达一个新提案的通信次数为$O(n^3)$个认证器，==该算法的一个变体，通过阈值数字签名(Threshold Digital Signatures)，将多个认证器组合成一个的算法能有效优化耗时，不过即便如此依旧有 O(n2) 的时间复杂度。（例如[18, 30]）==在PBFT中，如果在达成单一共识决定之前，发生$O(n)$个视图变化，那么传输的认证器总数为$O(n^4)$($n^3*n$)，即使有阈值签名也是$O(n^3)$。这一扩展挑战不仅困扰着PBFT，也困扰着此后开发的许多其他协议，例如Prime[9]、Zyzzyva[34]、Upright[22]、BFT-MaRt[13]、700BFT[11]和SBFT[30]。

​ HotStuff围绕着一个三阶段的核心，允许新leader简单地挑选它所知道的最高QC。它引入了第二个阶段，允许复制体在该阶段投票后 “改变主意”，根本不需要leader证明。因此同时降低了时间复杂度以及换leader协议的复杂度。最后，在几乎完成所有阶段的共识后，HotStuff能够很简单的并行化，以保证便捷的leader循环。

​ 据我们所知，在区块链领域只有如Tendermint[15, 16]和Casper[17]这样的BFT协议，遵循这样一个简单的leader制度。然而，这些系统是围绕同步核心建立的，其中提案是在预先确定的时间间隔内提出的，必须适应在广域点对点gossip网络上传播信息所需的最坏情况。这样做，他们放弃了大多数实用的BFT-SMR解决方案（包括上面列出的那些）的一个标志，即乐观的响应性[42]。非正式地，响应性要求非故障leader一旦被指定，就能在仅取决于实际消息延迟的时间内推动协议达成共识，与任何已知的消息传输延迟的上限无关[10]。==对我们的模型来说，更合适的是乐观的响应性，它只要求在特殊的（希望是常见的）情况下–这里是在达成GST之后–有响应性。==无论乐观与否，像Tendermint/Casper这样的设计是不可能有响应性的。问题的关键在于，可能存在一个具有最高质量控制的诚实的副本，但leader并不知道它。我们可以建立这样的场景，使进展卡死（详细的无生境场景见第4.4节）。==事实上，如果不能在关键的协议步骤中加入必要的延迟，就会导致完全失去有效性，这在一些现有的部署中已经有所报道，==例如，见[3, 2, 19] 。

​ **我们的贡献。**据我们所知，我们提出了第一个BFT-SMR协议，称为HotStuff，以实现以下两个特性。

​ 线性视图变换复杂度:在达到GST时限之后，任何正确的leader一旦被指定，只需发送O(n)个副本认证,就可以提出一个公式决策。这包括leader被替换的情况。因此，在大量leader崩溃的最坏情况下，GST之后达成共识的通信成本是O(n2)个认证者。

​ **乐观的回应性。**在达到GST时限之后，任何正确的leader，一旦被指定，只需要等待前n-f个回应，以保证它能创造一个能取得进展的提案。这包括leader被替换的情况。

​ HotStuff的另一个特点是，新的leader推动协议达成共识的成本不高于当前leader节点人的成本。因此，HotStuff支持leader的频繁继任，有人认为这在区块链背景下对确保链的质量很有用[28]。

​ ==HotStuff通过在每个视图中增加一个阶段来实现这些特性，这是以延迟的小代价换取leader替换协议的大大简化。==这种交换只产生了实际的网络延迟，在实践中通常远远小于∆。因此，我们希望这种增加的延迟比以前的协议所产生的延迟要小得多，这些协议放弃了响应性以实现线性的视图更换。此外，由于我们在第5节中介绍的有效管道，吞吐量也不会受到影响。

​ 除了理论上的贡献，HotStuff还提供了对一般BFT复制的理解和实践中的协议实例化的见解（见第6节）。

• 一个运行在图上的BFT复现框架。 通过投票和规则提交保障的安全性。 活跃性是通过Pacemaker提供的，支持向图添加新的副本。

• 在该框架下实现已知协议（DLS、PBFT、Tendmint和Casper），以及我们自己的HotStuff协议。

  HotStuff的另一个优点是非常简单，由于其机制本身就是非常经济性的：只包含两种消息的类别，以及一个简单地规则用于决定副本相互之间如何对待。安全性是通过投票和提交规则来保证的，而活跃性则需要Pacemaker机制，该机制与安全机制是完全独立的。同时，他允许通过少量的变化实现几种已知的协议(DLS, PBDF, Tendermint和Casper)。这种灵活性来源于其对于图上节点的操作，在现代区块链和传统的BFT基础间架设了一个桥梁。

​ 我们描述了HotStuff的原型实现和初步评估。在一个有一百多个副本的网络上部署，HotStuff实现了与BFT-MaRt等成熟系统相当的吞吐量和延迟，有时甚至超过了BFT-MaRt，其代码复杂度远远超过了HotStuff。我们进一步证明，HotStuff的通信足迹在面对频繁的leader更换时保持不变，而BFT-MaRt则随着复制数量的增加而呈二次方增长。

区块链HotStuff共识协议论文翻译-Introduction

2.相关工作

Markdown 增加文献引用

​ Lamport等人[37]将面对拜占庭失败时达成共识的问题表述为拜占庭将军问题，他们还创造了 "拜占庭失败 "一词。第一个同步解决方案是由Pease等人[43]给出的，后来由Dolev和Strong[24]改进。改进后的协议具有$O(n^3)$的通信复杂度，Dolev和Reischuk[23]证明这是最佳的。Katz和Koo[32]给出了一个使用随机性的基于leader的同步协议，显示了一个具有(n - 1)/2弹性的预期恒定回合解决方案。

​ 同时，在异步设置中，Fischer等人[27]表明，在异步设置中，面对单个故障，该问题是无法确定解决的。此外，Ben-Or[12]证明了任何异步解决方案的（n - 1）/3弹性约束。设计了两种方法来规避这种不可能性。一个是由Ben[12]提出的基于随机化的做法，使用持续随机的“虚拟硬币”翻转，直到恰好收敛到共识状态。后续的工作使用加密方法来共享一个不可预测的“硬币”，将复杂度降低到可预期的恒定回合，以及复杂度 O(n3) 的通信开销[18]。

​ 第二种方法依赖于部分同步，最早由Dwork, Lynch, and Stockmeyer (DLS) [25]展示。该协议在异步期间保持安全，而在系统变得同步之后，DLS保证终止。一旦保持同步，DLS就会产生O(n4)的总通信量和O(n)的每个决策回合。

​ 状态机复制的核心是依靠共识来安排客户请求的顺序，以便正确的复制体按照这个顺序执行它们。在SMR中反复出现的对共识的需求导致Lamport设计了Paxos[36]，这是一个运行古老管道的协议，其中一个稳定的leader以线性通信和一次往返的方式驱动决策。类似的重点促使Castro和Liskov[20, 21]开发了一个名为PBFT的基于leader的拜占庭SMR协议，其稳定的leader需要O(n2)次通信和每次决策的两次往返，而leader替换协议产生了O(n3)次通信。PBFT已经被部署在几个系统中，包括BFTSMaRt[13]。Kotla等人在名为Zyzzyva[34]的协议中为PBFT引入了一条乐观的线性路径，该协议被用于几个系统中，例如Upright[22]和Byzcoin[33]。乐观的路径具有线性复杂度，而leader替换协议仍然是O（n3）。Abraham等人[4]后来在Zyzzyva中暴露了一个安全漏洞，并提出了xes[5，30]。另一方面，为了同时降低协议本身的复杂性，Song等人提出了Bosco[49]，这是一个简单的单步协议，在乐观路径上具有低延迟，需要5f+1个副本。SBFT[30]引入了一个O(n2)的通信视图改变协议，支持一个稳定的leader协议，具有乐观的线性，一个往返的决定。它通过利用两种方法降低了通信复杂性：Reiter[45]的基于收集器的通信范式，以及Cachin等人[18]通过协议投票的阈值加密法进行签名组合。

​ 状态复制机(SMR)通过其核心的共识机制对客户端请求进行排序，以达到确定性的执行结果。这种SMR反复出现的需求，让Lamport设计出了Paxos协议[36]，该协议提供了一个高效的流水线，在这个流水线上，一个稳定的leader节点可以在一轮通信中，使用线性的通信开销来广播决策。Castro和Liskov[20, 21]也实现了相似的需求，他们提供了一个高效的基于leader节点的拜占庭SMR协议，该协议名字叫做PBFT。在PBFT中，一个稳定的leader节点需要 O(n2) 的通信开销和两轮通信来完成一次决策广播，同时，倘若leader节点需要更替，则需要花费 O(n3) 的通信开销。PBFT被部署在了多个系统中，其中就包括BFTSMaRt[13]。Kotla等研究者则在PBFT基础上，引入了一个乐观的线性路径(optimistic linear path)，并得到了Zyzzyva协议[34]，该协议也被部署在了Upright、Byzcoin等系统中。乐观路径拥有线性的复杂度，但leader节点的更替仍然需要 O(n3) 的时间复杂度。Abraham等人随机表示Zyzzyva协议存在安全漏洞，并提交了修正方案。改修正方案还有效地减小了协议自身的复杂度。Song等人提出了Bosco协议，这是一个建议的单阶段协议，在乐观路径上拥有较低的延迟。该协议要求 5f+1 个副本节点。SBFT协议引入了一个能够在 O(n2) 通信复杂度下，实现view-change的协议，并且支持一个稳定的leader节点实现乐观的线性、单轮决策。协议利用两种方法来降低通信复杂度，Reiter提出的一个机遇收集者(collector)的通信机制，以及Cachin等人提出的通过门限密码(threshold crptography)对协议投票以实现部分签名合并的算法。

​ Ramasamy等人提出了一个采用随机化的基于leader节点的拜占庭SMR协议[44]，Miller等人开发了一个名为HoneyBadgerBFT的无leader节点变体[39]。这些随机拜占庭解决方案的核心是采用随机异步拜占庭共识，其最好的已知通信复杂度为O(n3)（见上文），通过分批摊销成本。然而，最近，基于这篇HotStuff论文中的想法，向PODC’19[8]提交的一份并行文件进一步将通信复杂度提高到O(n2)。

​ 比特币的核心是一个被称为中本聪的协议[40]，这是一个同步协议，只有概率性的安全保证，没有真实性（见[28，41，6]中的分析）。它在参与者未知的无许可模式下运行，并通过工作证明保持弹性。如上所述，最近的区块链解决方案以各种方式将工作证明解决方案与经典的BFT解决方案混合起来[26, 33, 7, 17, 29, 31, 42]。这些混合的解决方案中，都需要解决轮流领导的问题，这为HotStuff提供了设计动机。

3.模型

​ 我们考虑一个由$n=3f+1$个副本组成的系统，以$i∈[n]$为索引，其中$[n]={1, . . . , n}$. 一组$F⊂[n]$的最多$f = |F|$的复制是拜占庭式的故障，其余的是正确的。我们通常会把拜占庭副本称为由对手协调，对手会了解这些副本所持有的所有内部状态（包括它们的加密密钥，见下文）。

​ 网络通信是点对点的、经过验证的和可靠的：一个正确的复制体从另一个正确的复制体收到一个消息，当且仅当后者向前者发送该消息。当我们提到 "广播 "时，它涉及到广播者，如果正确的话，向所有副本，包括它自己，发送相同的点对点信息。我们采用Dwork等人[25]的部分同步模型，其中有一个已知的边界$\Delta$和一个未知的全球稳定时间（GST），这样在GST之后，两个正确的副本之间的所有传输都在时间∆内到达。我们的协议将始终确保安全，并将保证在GST之后的一定时间内取得进展。(在GST之前保证进度是不可能的[27]。)在实践中，如果系统在GST之后足够长的时间内保持稳定（即，如果消息在∆时间内到达），我们的协议将保证进度，尽管假设它永远这样做是为了简化讨论。

​ 密码学原理。HotStuff使用了阈值签名[48, 18, 14]。在一个(k, n)阈值签名方案中，有一个由所有副本持有的单一公钥，而n个副本中的每一个都持有一个不同的私钥。第i个副本可以使用其私钥对消息m贡献一个部分签名$\rho_i \leftarrow \operatorname{tsign}_i(m)$。部分签名$\left\{\rho_i\right\}_{i \in I}$ ，其中|I| = k，每个ρi ← tsigni(m)，可以用来对m产生数字签名σ← tcombine(m, {ρi}i∈I )，任何其他副本可以使用公钥和函数tverify验证该签名。我们要求，如果ρi ← tsigni(m)对于每个i∈I，|I| = k，并且如果σ← tcombine(m, {ρi}i∈I )，那么tverify(m, σ)返回真。然而，考虑到对神谕{tsigni(-)}i∈[n]/F的访问，对手在严格少于k-f的这些神谕上查询tsigni(m)，产生消息m的签名σ的概率可以忽略不计（即，使tverify(m, σ)返回真）。在本文中，我们使用k=2f+1的阈值。同样，我们通常会在协议描述中隐含对tverify的调用。

​ 我们还需要一个加密哈希函数h（也称为消息摘要函数），它将一个任意长度的输入映射到一个固定长度的输出。哈希函数必须是抗碰撞的[46]，这非正式地要求对手产生h(m)=h(m′)的输入m和m′的概率是可以忽略的。因此，h(m)可以作为协议中唯一输入m的识别器。

复杂度测量。 我们关心的复杂度是认证器复杂度，具体来说就是在所有副本i∈[n]上，副本i在GST后达成共识决定的协议中收到的认证器数量之和。(同样，在GST之前，在最坏的情况下可能根本无法达成共识决定[27]）。这里，一个认证器是一个部分签名或一个签名。认证器复杂度是通信复杂度的一个有用的衡量标准，原因有几个。首先，像比特复杂度，也不像消息复杂度，它隐藏了关于传输拓扑结构的不必要的细节。例如，携带一个认证器的n个消息与携带n个认证器的一个消息计数相同。第二，认证器复杂度比比特复杂度更适合捕捉像我们这样反复达成共识的协议中的成本，其中每个共识决定（或在通往该共识决定的路上提出的每个观点）都由一个单调增加的计数器识别。也就是说，因为这样的计数器是无限增加的，所以发送这样的计数器的协议的位复杂度是不能被约束的。第三，由于在实践中，产生或验证数字签名的加密操作以及产生或结合部分签名的加密操作通常是使用它们的协议中计算最密集的操作，认证器的复杂性也提供了对协议计算负担的洞察力。

4. 基本hotstuff

HotStuff解决了状态机复制（SMR）问题。SMR的核心是一个决定客户不断增长的命令请求日志的协议。一组状态机复制体按照顺序一致地应用命令。客户端向所有的复制体发送命令请求，并等待其中（f+1）个复制体的回应。在大多数情况下，我们在讨论中省略了客户端，并将有关客户端请求的编号和去重的问题交给标准文献。

​ 基本HotStuff解决方案在算法2中提出。该协议在一个连续的视图中工作，其编号为单调增加的视图编号。每个viewNumber都有一个唯一的专用leader节点，为所有人所知。每个副本都将一棵悬而未决的命令树作为其本地数据结构。每个树节点都包含一个提议的命令（或一批），与协议相关的元数据，以及一个父级链接。一个给定节点所带领的分支是通过访问父链接从该节点一直到树根的路径。在协议期间，一个单调增长的分支成为承诺。为了成为承诺，提出分支的特定视图的leader必须在准备、预承诺和承诺三个阶段从（n - f ）个副本的法定人数中收集投票。

​ 该协议的一个关键成分是对leader提案的(n - f )票数的集合，被称为法定人数证书（简称 “QC”）。QC与一个特定的节点和一个视图编号相关联。tcombine工具采用了一个阈值签名方案，以产生一个(n - f )签名的投票表示，作为一个单一的认证器。

​ 下面我们将分阶段对协议逻辑进行操作性描述，然后在算法2中进行精确的规范，并以安全性、有效性和复杂性的论证来结束本节。

4.1阶段

​ 准备阶段。新leader的协议从收集（n - f ）个副本的新视图消息开始。新视图消息由一个副本在过渡到viewNumber（包括第一个视图）时发送，并携带该副本收到的最高prepareQC（如果没有，则为⊥），如下所述。

​ leader节点对这些消息进行处理，以选择一个分支，该分支具有形成prepareQC的最高前视图。leader节点在新视图信息中选择具有最高视图的prepareQC，表示为highQC。因为highQC是(n - f )个副本中最高的，没有更高的视图可以达成提交决定。因此，由highQC.nodeleader节点的分支是安全的。

​ 在职leader可以省略收集新视点信息来选择安全分支，他可以简单地选择自己的最高prepareQC作为highQC。我们将这一优化推迟到第6节，在这一节中只描述一个单一的、不结盟的leader协议。请注意，与类似PBFT的协议不同，在leader协议中包括这一步骤是直接的，而且无论在什么情况下，它都会产生与协议中所有其他阶段相同的线性开销。

​ leader节点使用createLeaf方法用一个新的提议来扩展highQC.node的尾部。该方法创建一个新的叶子节点作为子节点，并将父节点的摘要嵌入子节点中。然后，leader在准备消息中向所有其他副本发送新节点。为了安全起见，该提议带有高QC。

​ 在收到leader发出的当前视图的准备消息后，副本r使用安全节点谓词来决定是否接受它。如果它被接受，复制体就向leader发送一个带有部分签名（由tsignr产生）的提案的准备投票。

​ safeNode谓词。safeNode谓词是该协议的一个核心要素。它检查携带QC论证m.justify的提议消息m，并确定m.node是否可以安全接受。接受提议的安全规则是m.node的分支从当前锁定的节点延伸到锁定的QC.node。另一方面，有效性规则是，如果m.justify的视图高于当前锁定的QC .node，复制体将接受m。只要两个规则中的任何一个成立，该谓词就是真的。

​ 预承诺阶段。当leader收到针对当前提案curProposal的(n - f )张准备票时，它将其合并为prepareQC。leader节点在预承诺消息中广播prepareQC。一个副本以预承诺投票的方式回应leader，该预承诺投票具有提案的签名摘要。

​ 提交阶段。提交阶段与预提交阶段类似。当leader收到(n - f )张预提交投票时，它将这些投票合并成一个precommitQC，并在提交消息中进行广播；复制体以提交投票来回应它。重要的是，在这一点上，一个复制体通过将其锁定的QC设置为precommitQC而被锁定（算法2的第25行）。这对保护提案的安全至关重要，因为它可能成为一个共识决定。

**决定阶段。**当leader收到(n - f )张提交票时，它将它们合并成一个commitQC。一旦leader集合了一个commitQC，它就会将其作为一个decide消息发送给所有其他的副本。收到决定消息后，复制体认为commitQC中包含的提议是一个承诺的决定，并执行承诺分支中的命令。复制体增加viewNumber并开始下一个视图。

**nextView的中断。**在所有阶段，副本在视图viewNumber处等待消息，等待的时间由辅助的nextView(viewNumber )工具决定。如果nextView(viewNumber )中断等待，副本也会增加viewNumber并开始下一个视图。

4.2数据结构

**信息。**协议中的消息m有一组固定的elds，使用算法1中的Msg()工具进行填充。m自动带有curView，即发送者的当前视图编号。每个消息都有一个m.type∈ {new-view, prepare, pre-commit, commit, decide}。m.node包含一个提议节点（提议分支的叶子节点）。有一个可选的eld m.justify。leader节点总是使用这个字段来携带不同阶段的QC。复制体在new-view消息中使用它来携带最高的prepareQC。在副本角色中发送的每条消息都包含一个部分签名m.partialSig，由发送者在〈m.type, m.viewNumber , m.node〉上签名，该签名被添加到voteMsg()工具中。

**法定人数证书。**一个关于元组〈type, viewNumber , node〉的Quorum Certicate（QC）是一个数据类型，它结合了由（n - f）个副本签署的同一元组的签名集合。给定一个QC qc，我们用qc.type, qc.viewNumber , qc.node来指代原始元组的匹配字段。

树和分支。每个命令都被包裹在一个节点中，该节点还包含一个父节点链接，该链接可以是父节点的哈希摘要。我们省略了伪代码中的实现细节。在协议中，一个副本只有在节点leader节点的分支已经在其本地树中之后才会传递消息。在实践中，落后的接收者可以通过从其他副本中获取缺失的节点来追赶。为了简洁起见，这些细节也从伪代码中省略了。如果两个分支都不是另一个分支的延伸，那么这两个分支就是相互矛盾的。如果两个节点所leader节点的分支是相互矛盾的，那么这两个节点就是相互矛盾的。

**簿记变量。**复制体使用额外的本地变量来保存协议状态：(i) viewNumber，最初为1，通过完成决策或下一个View中断而增加；(ii) lock quorum certicate locked QC，最初为⊥，存储复制体投票提交的最高QC；以及(iii) prepareQC，最初为⊥，存储复制体投票预提交的最高QC。此外，为了递增地执行已提交的命令日志，复制体维护其分支已被执行的最高节点。为了简洁起见，下面省略了这一点。

4.3协议规范

​ 算法2中给出的协议被描述为一个迭代的逐个视图的循环。在每个视图中，一个复制体根据其角色连续执行各个阶段，描述为连续的 "作为 "块。一个副本可以有一个以上的角色。例如，一个leader也是一个（正常的）副本。角色间的作为块的执行可以同时进行。每个as块的执行都是原子性的。nextView的中断中止了任何as块中的所有操作，并跳转到 "Final "块。

4.4安全，活性和复杂性

安全性。我们首先认为，如果tverify(〈qc.type, qc.viewNumber , qc.node〉, qc.sig)为真，则法定人数证书qc为有效。

推理1。对于任何有效的qc1, qc2，其中qc1.type = qc2.type并且qc1.node与qc2.node冲突，我们有qc1.viewNumber 6= qc2.viewNumber 。

证明。为了显示矛盾，假设qc1.viewNumber = qc2.viewNumber = v。因为一个有效的QC只能在有n - f = 2f + 1票（即部分签名）的情况下形成，必须有一个正确的复制品在v的同一阶段投票两次。

定理2. 如果w和b是对立的节点，那么它们不可能同时被承诺，各自被一个正确的副本承诺。

证明。我们通过矛盾法来证明这一重要定理。让qc1表示一个有效的commitQC（即qc1.type = commit），这样qc1.node = w；qc2表示一个有效的commitQC，这样qc2.node = b。根据定理1，v1 6= v2.假设v1 < v2.

​ 我们现在用vs表示比v1高的最低视图，对于它有一个有效的prepareQC，qcs（即qcs.type = prepare），其中qcs.viewNumber = vs，并且qcs.node与w一致。

E(prepareQC ) :=(v1 < prepareQC .viewNumber ≤ v2) ∧ (prepareQC .node conicts with w).

现在我们可以设置第一个开关点qcs。

qcs := arg min prepare QC {prepareQC .viewNumber | prepareQC is valid ∧ E(prepareQC )} .

请注意，根据假设，这样的qcs必须存在；例如，qcs可能是在视图v2中形成的prepareQC。

​ 在发送部分结果tsignr(〈qc1.type, qc1.viewNumber , qc1.node〉)的正确副本中，让r成为第一个贡献tsignr(〈qcs.type, qcs.viewNumber , qcs.node〉的副本；这样的r一定存在，因为否则qc1.sig和qcs.sig之一不可能被创建。在视图v1期间，副本r在算法2的第25行将其锁定的QC更新为w上的precommitQC。由于vs的最小化，在qcs形成之前，复制体r在w所带领的分支上的锁没有被改变。否则，r一定看到了其他的prepareQC，而且视图较低，因为第17行在第25行之前，与最小性相矛盾。现在考虑复制体r在视图vs的准备阶段对safeNode的调用，消息m携带m.node = qcs.node。根据假设，m.node与锁定的QC.node相冲突，因此算法1第26行的disjunct为假。此外，m.justify.viewNumber > v1将违反vs的最小化原则，因此算法1第27行的disjunct也是假的。因此，safeNode必须返回false，并且r不能对视图vs中的矛盾分支投准备票，这是一个矛盾。

​ 有效性。在上一节中，有两个函数没有提到：leader和nextView。它们的命名不会影响到协议的安全性，但它们确实关系到有效性。在给出它们的候选名称之前，我们首先表明，在GST之后，有一个有约束的持续时间Tf，如果在Tf期间所有正确的复制都留在视图v中，并且视图v的leader是正确的，那么就会达成一个决定。下面我们说，如果qc1和qc2是有效的，qc1.node = qc2.node，并且qc1.viewNumber = qc2.viewNumber，则qc1和qc2是匹配的。

​ 推理3. 如果一个正确的副本被锁定，使得锁定的QC=预提交的QC，那么至少有f+1个正确的副本投票给一些与锁定的QC匹配的prepareQC。

​ 证明。假设副本r被锁定在precommitQC上。那么，在准备阶段（算法2的第10行），有（n-f）票投给了匹配的prepareQC，其中至少有f+1票是来自正确的副本。

​ 定理4. 在GST之后，存在一个有界的时间段Tf，如果在Tf期间所有正确的复制都留在视图v中，并且视图v的leader是正确的，那么就会达成一个决定。

​ 证明。从一个新视图开始，leader收集(n - f )个新视图消息，并在广播prepare messsage之前计算它的highQC。假设在所有的副本中（包括leader本身），保持最高的锁是锁定的QC = precommitQC ∗。根据定理3，我们知道至少有f+1个正确的副本投票选出了与precommitQC ∗相匹配的prepareQC，并且已经在他们的new-view消息中把它们发送给了leader。因此，leader必须在这些新视图消息中至少有一个学到匹配的prepareQC ∗，并在其prepare消息中使用它作为highQC。根据假设，所有正确的副本在他们的视图中都是同步的，并且leader是无故障的。因此，所有正确的复制体都会在准备阶段投票，因为在safeNode中，算法1第27行的条件是满足的（即使消息中的节点与复制体的陈旧锁定的QC.节点相冲突，因此第26行不是）。然后，在leader为这个视图组装了一个有效的prepareQC之后，所有的副本将在接下来的所有阶段进行投票，导致一个新的决定。在GST之后，这些阶段完成的持续时间Tf是有边界的长度。

​ 该协议是乐观响应的，因为没有明确的 "等待-∆"步骤，而且safeNode中的逻辑分离被用来在三阶段范式的帮助下覆盖一个过时的锁。

​ 我们现在为leader和nextView提供了简单的结构，以确保在GST之后，最终会达到一个视图，其中leader是正确的，所有正确的副本在Tf时间内保持在这个视图中。对于leader来说，它成功地返回了一些从视图编号到副本的确定性映射，最终在所有的副本中轮换。nextView的一个可能的解决方案是利用一个保持超时时间间隔的指数型退避机制。然后在进入每个视图时设置一个定时器。当定时器熄灭而没有做出任何决定时，复制体将间隔时间加倍，并调用nextView来推进视图。由于每次的时间间隔都会翻倍，所有正确的副本的等待时间间隔最终会有至少Tf的共同重叠，在此期间，leader可以驱动一个决定。

​ **两相的无生气。**我们现在展示了一个 "两阶段 "HotStuff的先天非决定性情景。这解释了在Casper和Tendermint中引入同步延迟的必要性，因此也解释了放弃（乐观的）响应性的必要性。

​ 在两阶段的HotStuff变体中，我们省略预提交阶段，直接进行提交。当一个副本在prepareQC上投票时，它就会被锁定。假设在视图v中，一个leader提出了b。它完成了准备阶段，一些副本rv对prepareQC进行了投票，比如qc，使得qc.node = b。一个异步的网络调度导致其余的副本在没有收到qc的情况下移动到视图v+1。

​ 我们现在无休止地重复下面的单视图记录。我们从视图v+1开始，只有rv持有系统中最高的prepareQC（即qc）。新的leaderl从2f + 1个副本中收集新的视图信息，不包括rv。其中最高的prepareQC，qc′，拥有视图v-1，b′=qc′.节点与b冲突。然后，l提出了扩展b′的b′，2个诚实的复制体以投票方式回应，但是rv拒绝了它，因为它被锁在qc上，b′与b冲突，而且qc′比qc低。最终，有2个复制体放弃了，转到了下一个视图。就在这时，一个有问题的副本回应了我的提议，然后我提出了一个prepareQC（v+1，b′′），一个副本，比如说rv+1，投票给它，并锁定在它上面。

​ 复杂性。在HotStuff的每个阶段，只有leader向所有副本进行广播，而副本则以部分签名的方式回应发送者一次，以证明投票。在leader的信息中，QC由之前收集的(n - f )票数证明组成，它可以由一个阈值签名来编码。在一个副本的回应中，来自该副本的部分签名是唯一的认证者。因此，在每个阶段，总共有O(n)个认证器被收到。由于阶段的数量是恒定的，每个视图的总体复杂度是O(n)。

5.链式的hotstuff

​ 一个基本的HotStuffleader需要三个阶段来提交一个提案。这些阶段除了从副本中收集投票外，并不做 "有用 "的工作，而且它们都非常相似。在Chained HotStuff中，我们改进了Basic HotStuff协议的实用性，同时也大大简化了它。我们的想法是在每个准备阶段改变视图，因此每个提案都有自己的视图。这就减少了消息类型的数量，并允许对决策进行流水线处理。在Casper[1]中提出了一个类似的减少消息类型的方法。

图1：链式HotStuff是一种流水线式的基本HotStuff，其中一个QC可以同时服务于不同阶段。

图2：视图v4、v5、v6的节点形成了一个三链。视图v8的节点在Chained HotStuff中不构成有效的One-Chain（但在第6节的算法中放松后，它是一个有效的One-Chain）。

​ 更具体地说，在Chained HotStuff中，准备阶段的投票被leader收集到一个通用的QC中。然后，genericQC被转发给下一个视图的leader，本质上是将下一个阶段的责任委托给下一个leader，而这个阶段本来是预提交的。然而，下一个leader实际上并没有进行预承诺阶段，而是启动了一个新的准备阶段并增加了自己的提议。视图v+1的准备阶段同时作为视图v的预提交阶段。视图v+2的准备阶段同时作为视图v+1的预提交阶段和视图v的提交阶段。

​ 图1描述了嵌入链式HotStuff提案链中的基本HotStuff协议阶段的流水线。Chained HotStuff的视图v1、v2、v3作为v1中提议的cmd1的准备、预提交和提交基本HotStuff阶段，该命令在v4结束时被提交。 视图v2、v3、v4作为v2中提议的cmd2的三个基本HotStuff阶段，它在v5结束时被提交。 这些阶段产生的其他提议以类似方式继续管道，并以虚线框表示。在图1中，单箭头表示节点b的b.parenteld，双箭头表示b.justify.node。

​ 因此，在Chained HotStuff中只有两种类型的消息，一种是新视图消息，一种是通用阶段通用消息。通用QC在所有的逻辑流水线阶段都有作用。接下来，我们将解释管道中的机制，以照顾锁定和提交，这只发生在Basic HotStuff的提交和决定阶段。

​ 虚设节点。某个视图viewNumber中的leader节点所使用的通用QC可能不会直接引用前一个视图（viewNumber-1）的提议。原因是前一个视图的leader节点未能获得QC，要么是因为有相互矛盾的提议，要么是因为良性崩溃。为了简化树形结构，createLeaf用空白节点扩展了genericQC .node，直到提议视图的高度（节点分支上的父链接数），因此视图编号等同于节点高度。因此，嵌入节点b中的QC可能并不指它的父节点，也就是说，b.justify.node可能不等于b.parent（图2中的最后一个节点）。

​ 一链、二链和三链。当一个节点b∗携带一个指向直接父节点的QC，即b∗.justify.node = b∗.parent，我们就说它形成了一个One-Chain。用b′′＝b∗.justify.node表示。如果节点b∗除了形成一个一链之外，b′′.justify.node = b′′.parent，则形成一个二链。如果b′′形成一个二链，它就形成一个三链。

​ 看一下链b = b′.justify.node, b′ = b′′.justify.node, b′′ = b∗.justify.node，祖先的差距可能发生在任何一个节点。这些情况类似于Basic HotStuff的leader未能完成三个阶段中的任何一个，被nextView打断到下一个视图。

​ 如果b∗形成了一个单链，那么b′′的准备阶段就成功了。因此，当一个副本为b∗投票时，它应该记住genericQC ← b∗.justify。我们注意到，即使在One-Chain不直接的情况下，更新genericQC也是安全的，只要它比当前的genericQC高。在第6节描述的实现代码中，我们确实在这种情况下更新了genericQC。

​ 如果b∗形成了一个双链，那么b′的预提交阶段就成功了。因此，副本应该更新锁定的QC← b′′.justify。我们再次指出，即使在二链不直接的情况下，锁也可以被更新–安全不会被破坏–事实上，这在第6节的实现代码中已经给出。

​ 最后，如果b∗形成了一个三链，那么b的提交阶段就成功了，b就成了一个承诺的决策。

​ 算法3显示了链式HotStuff的伪代码。附录A中的定理5所给出的安全性证明与Basic HotStuff的类似。我们要求有效节点中的QC指的是其祖先。为简洁起见，我们假设该约束总是成立，并在代码中省略检查。

6.实施

​ HotStuff是一个实用的协议，用于构建古老的SMR系统。由于其简单性，我们可以很容易地将算法3变成一个事件驱动式的规范，它几乎就像一个原型实现的代码骨架。

​ 如算法4所示，该代码被进一步简化和泛化，从本体中提取出有效性机制，放入一个名为Pacemaker的模块。在通用阶段结束时，下一个leader总是等待一个通用的QC，然后开始它的统治，而不是把这个逻辑委托给Pacemaker。一个稳定的leader可以跳过这个步骤，在多个高度上精简提案。

​ 此外，我们放宽了保持最高通用QC和锁定QC的直接父约束，同时仍然保留了有效节点中的QC总是指其祖先的要求。正确性的证明与Chained HotStuff相似，我们也将其推迟到[50]的附录中。

​ 它还保持一个常数b0，即所有正确的副本都知道的同一个创世节点。为了引导，b0包含了一个硬编码的QC，block、bexec、bleaf都被初始化为b0，qchigh包含b0的QC。

​ 起搏器。起搏器是一种保证在GST之后取得进展的机制。它通过两种成分实现这一目标。

​ 第一种是 “同步化”，将所有正确的复制体和唯一的leader带到一个共同的高度，并保持足够长的时间。文献[25, 20, 15]中通常的同步机制是让复制体增加它们在更大高度上花费的∆的数量，直到取得进展。确定性地选举leader的一个常见方法是使用轮流leader方案，其中所有正确的副本保持预先设定的leader时间表，并在leader被降级时轮流到下一个。

​ 其次，起搏器需要为leader提供一种方法来选择一个将被正确的副本所支持的提议。如算法5所示，在视图改变后，在onReceiveNewView中，新的leader通过onNextSyncView收集复制体发送的新视图消息，以发现最高的QC，满足onReceiveProposal中第二部分条件的有效性（算法4的第18行）。然而，在同一视图中，现任leader节点将把新节点链到自己最后提议的叶子的末端，这里不需要新视图消息。基于一些应用特有的启发式方法（例如，等到之前提议的节点获得QC），现任leader会调用onBeat来提议一个携带命令的新节点来执行。

​ 值得注意的是，即使一个坏的起搏器任意调用onPropose，或者任性地选择一个父类和一个QC，并且在任何调度延迟的情况下，安全性总是得到保证的。因此，仅由算法4保证的安全性与算法5的任何潜在实例化的有效性完全脱钩。

两阶段的HotStuff变体。为了进一步证明HotStuff框架的灵活性，算法6显示了HotStuff的两阶段变体。只有更新程序受到影响，达成提交决定需要双链，而单链则决定锁。如上所述（第4.4节），这种两阶段变体失去了优化响应性，与Tendermint/Casper类似。它的好处是阶段更少，同时可以通过在Pacemaker中加入一个基于最大网络延迟的等待来解决失效性问题。进一步的讨论见第7.3节。

7.单链和双链

​ 在本节中，我们研究了横跨拜占庭容错领域四十年研究的四种BFT复制协议，将它们投射到类似于Chained HotStuff的连锁框架中。

​ 图3提供了我们所考虑的ve协议的提交规则的鸟瞰图，包括HotStuff。

​ 简而言之，DLS[25]中的提交规则是一链式的，只允许一个节点被自己的leader提交。PBFT[20]、Tendermint[15, 16]和Casper[17]的提交规则几乎相同，都是双链的。它们的不同之处在于它们引入的有效性机制，PBFT有二次大小的leader “证明”（没有线性），Tendermint和Casper在每个leader提议之前引入一个强制性的∆延迟（没有优化响应性）。HotStuff使用三链规则，并且有一个没有延迟的线性leader协议。

7.1DLS

​ 最简单的提交规则是一链式的。这个规则以Dwork, Lynch, and Stockmeyer (DLS)为模型，是第一个已知的异步拜占庭共识解决方案，如图3（a）所示。一个副本在DLS中被锁定在它投票支持的最高节点上。

​ 不幸的是，如果在某个高度，一个leader含糊其辞，而两个正确的复制品在该高度被锁定在相互矛盾的提案上，那么这个规则将很容易导致僵局。放弃任何一个锁都是不安全的，除非有2f+1表示他们没有投票给锁定的值。

​ 事实上，在 DLS 中，只有每个高度的leader自己可以通过一链式提交规则达成提交决定。因此，只有leader本身在犹豫不决的情况下才会受到伤害。如果2f+1个副本没有投票支持，或者有相互矛盾的提议（由leader签署），那么副本可以放弃一个锁。在DLS的每个高度结束时发生的解锁协议被证明是相当复杂和昂贵的。再加上一个事实，即只有一个高度的leader可以决定，在最好的情况下，没有故障发生，网络是及时的，DLS需要n个leader轮换，以及O(n4)消息传输，每一个决定。虽然它在展示一个安全的异步协议方面有了新的突破，但DLS并不是作为一个实用的解决方案而设计的。

7.2pbft

​ 以PBFT为模型，一个更实用的Appraoch使用双链提交规则，见图3（b）。当一个副本投票给一个形成一链的节点时，它就被锁定在该节点上。由于每个节点都有一个QC，所以在同一高度上的相互矛盾的One-Chain是不可能的，因此可以避免DLS的死锁情况。

​ 然而，如果一个副本拥有比其他副本更高的锁，即使leader收集了n-f个副本的信息，也可能不知道它的情况。这可能会阻止leader无休止地达成决定，纯粹是由于调度的原因。为了得到 “解锁”，PBFT通过携带由2f+1个副本组成的最高一链的证明来解锁所有副本。这个证明是相当复杂的，如下所述。

​ 原始的PBFT已经开源[20]，并在一些后续工作中采用[13, 34]，leader证明包含一组从n-f个副本中收集的信息，报告每个成员投票支持的最高一链。每个One-Chain都包含一个QC，因此总的通信成本是O(n3)。利用来自[45, 18]的签名组合方法，SBFT[30]通过将每个QC变成一个单一的值，将这个成本降低到O(n2)。

​ 在[21]中的PBFT变体中，leader证明只包含leader从法定人数中收集到的最高一链一次。它还包括法定人数中每个成员的一个签名值，证明它没有投票给更高的一链。广播这个证明会产生通信复杂度O(n2)。请注意，虽然QC上的签名可以合并成一个单一的值，但整个证明不能减少到恒定的大小，因为来自法定人数中不同成员的消息可能有不同的值。

​ 在这两个变体中，一个正确的复制品即使比leader的证明具有更高的一链，也会被解锁。因此，一个正确的leader可以在同步期间强制接受其提议，并且保证了有效性。每个leader的替换成本是二次通信。

7.3 Tendermint和Casper

​ Tendermint有一个与PBFT相同的双链提交规则，而Casper有一个双链规则，其中叶子不需要有QC来指导父本。也就是说，在Casper中，图3（c,d）分别描述了Tendermint和Casper的提交规则。

​ 在这两种方法中，leader只需将它所知道的最高的One-Chain与它的提议一起发送。如果一个副本从leader那里收到更高的一链，它就会解锁一链。

​ 然而，由于正确的副本可能不会为leader的节点投票，为了保证进展，新的leader必须通过等待最大的网络延迟来获得最高的One-Chain。否则，如果leader只等待前n-f个信息来开始一个新的高度，就没有进展保证。leader延迟在Tendermint和Casper中都是固有的，目的是为了提供灵活性。

​ 这个简单的leader协议体现了leader协议的通信复杂性的线性飞跃，HotStuff借用了这个协议。正如上面已经提到的，QC可以通过使用阈值签名来捕获一个单一的值，因此leader可以以线性通信复杂度收集和传播最高的One-Chain。然而，至关重要的是，由于额外的QC步骤，HotStuff不要求leader等待最大的网络延迟。

8.评价

我们将HotStuff作为一个库来实现，大约有4K行的C++代码。最明显的是，伪代码中规定的核心共识逻辑只消耗了大约200行。在这一节中，我们将首先通过与最先进的系统BFT-MaRt[13]的比较来检查基线吞吐量和延迟。然后，我们将关注视图变化的消息成本，以了解我们在这种情况下的优势。

8.1 设置

​ 我们在亚马逊EC2上使用c5.4xlarge实例进行了实验。每个实例有16个vCPU，由英特尔至强白金8000处理器支持。所有核心的CPU时钟速度都达到了3.4GHz。我们在单个虚拟机实例上运行每个副本，因此大量使用线程的BFT-MaRt被允许利用每个副本的16个核心，就像他们最初的评估[13]一样。iperf测量的最大TCP带宽约为每秒1.2千兆字节。我们在任何运行中都没有对带宽进行节制。两台机器之间的网络延迟小于1毫秒。

​ 我们的HotStuff原型实现在投票和法定人数证书中都使用secp256k1作为所有数字签名。BFT-MaRt在正常运行期间对消息中的MAC（消息验证码）使用hmac-sha1，在视图变化期间除了MAC之外还使用数字签名。

​ HotStuff的所有结果都反映了客户端的端到端测量。对于BFT-MaRt，我们使用了BFT-MaRt网站（https://github.com/bft-smart/library）上的微基准程序ToughputLatencyServer和ToughputLatencyClient。客户端程序测量端到端的延迟，但不测量吞吐量，而服务器端程序同时测量吞吐量和延迟。我们使用了服务器的吞吐量结果和客户端的延时结果。

8.2 基础性能

​ 我们首先测量了其他BFT复制系统评估中常见的吞吐量和延时。我们在一个能容忍单一故障的集合中运行4个副本，即f=1，同时改变操作请求率直到系统饱和。这个基准使用了空的（零大小）操作请求和响应，并且没有触发视图变化；我们在下面扩展到其他设置。虽然我们的响应式HotStuff是三阶段的，但我们也运行其两阶段的变体作为额外的基线，因为BFT-MaRt基线只有两个阶段。

图4：不同的批处理规模选择下的吞吐量与延迟，4个副本，0/0有效载荷。

图5：在不同的有效载荷大小选择下，吞吐量与延迟的关系，4个副本，批次大小为400。

​ 图4描述了两个系统的三种批处理规模：100、400和800，不过由于这些系统有不同的批处理方案，这些数字对每个系统的意义略有不同。BFT-MaRt为每个操作驱动一个单独的共识决策，并对来自多个共识协议的消息进行批处理。因此，它有一个典型的L型延迟/吞吐量性能曲线。HotStuff在每个节点批处理多个操作，并以这种方式减轻了每个决策的数字签名成本。然而，每批操作超过400次，批处理所产生的延迟就会高于加密的成本。尽管存在这些差异，三相（“HS3-”）和两相（“HS2-”）HotStuff在所有三种批处理规模下都取得了与BFT-MaRt（“BS-”）相当的延迟性能，而其最大吞吐量明显优于BFT-MaRt。

​ 对于100和400的批处理量，最低延迟的HotStuff点提供的延迟和吞吐量优于BFT-MaRT在其最高吞吐量下可同时实现的延迟和吞吐量，同时会产生少量的延迟增加。这种增加部分是由于HotStuff采用的批处理策略。它需要另外三个完整的批处理（在两阶段的变体中是两个）来达成对一个批次的决定。我们的实验保持了较高的未决请求数量，但批处理规模越大，批处理管道所需的时间就越长。实际部署可以进一步优化，以使批处理规模适应未完成操作的数量。

图5描述了0/0、128/128和1024/1024三种客户端请求/回复的有效载荷大小（以字节为单位），分别表示为 “p0”、"p128 "和 “p1024”。在所有的有效载荷大小中，三相和两相HotStuff的吞吐量都超过了BFTSMaRt，而延迟相似或相当。

​ 注意BFT-MaRt使用基于对称加密的MAC，比HotStuff使用的数字签名中的非对称加密快几个数量级，而且与BFT-MaRt使用的两相PBFT变体相比，三相HotStuff的往返次数更多。 但HotStuff仍然能够实现可比的延迟和高得多的吞吐量。下面我们将在更具挑战性的情况下评估这两个系统，HotStuff的性能优势将变得更加明显。

8.3 可扩展性

​ 为了评估HotStuff在不同维度上的可扩展性，我们进行了三个实验。对于基线，我们使用零尺寸的请求/响应有效载荷，同时改变副本的数量。第二次评估用128字节和1024字节的请求/响应有效载荷重复基线实验。第三项测试重复了基线（空的有效载荷），同时引入了副本之间的网络延迟，这些网络延迟均匀分布在5ms±0.5ms或10ms±1.0ms，用NetEm实现（见https://www.linux.org/docs/man8/tc-netem.html）。对于每个数据点，我们用相同的设置重复运行了多次，并显示了误差条以表示所有运行的标准偏差。

​ 图6a（吞吐量）和图6b（延迟）中描述了第一种设置。三相和两相HotStuff都显示出持续优于BFT-MaRt的吞吐量，而它们的延迟仍可与具有优雅降级的BFTSMaRt相比。当n<32时，性能的扩展性比BFT-MaRt好。这是因为我们目前仍然使用secp256k1签名列表来进行QC。在未来，我们计划通过使用快速阈值签名方案来减少HotStuff的加密计算开销。

​ 图7a（吞吐量）和图7b（延迟）中用 "p128 "或 "p1024 "表示有效载荷大小为128或1024字节的第二个设置。由于其二次带宽成本，对于合理的大（1024字节）有效载荷大小，BFT-SMaRt的吞吐量比HotStuff差。

​ 第三种设置在图8a（吞吐量）和图8b（延迟）中显示为 "5ms "或 “10ms”。同样，由于BFT-MaRt中通信的使用量较大，HotStuff在这两种情况下的表现始终优于BFT-MaRt。

8.4 视图变化

​ 为了评估leader替换的通信复杂性，我们计算了在BFT-MaRt的视图变化协议中进行的MAC或签名验证的数量。我们的评估策略如下。我们在BFT-MaRt中每隔一千次决策就注入一次视图变化。我们对BFT-MaRt的源代码进行了检测

​ 代码来计算接收和处理视图变化协议中的信息时的验证次数。除了通信复杂性之外，这种测量还强调了与传输这些验证值相关的加密计算负荷。

​ 图9a和图9b显示了每次视图变化所处理的额外验证器（分别为MAC和签名）的数量，其中 "额外 "被认为是那些如果leader节点保持稳定就不会发送的验证器。请注意，HotStuff没有 "额外 "的认证器，因为无论leader是否保持不变，认证器的数量都是一样的。这两张图显示，BFT-MaRt使用了立方数的MAC和二次数的签名。HotStuff不需要额外的认证器来改变视图，所以从图中省略了。

​ 评估leader替换的实时性能是很棘手的。首先，BFT-MaRt在触发频繁的视图变化时卡住了；我们的认证器计数基准必须在系统卡住之前尽可能多地对成功的视图变化进行平均，重复实验多次。第二，leader替换的实际耗时高度依赖于超时参数和leader选举机制。因此，不可能提供一个有意义的比较。

9 结论

​ 自从PBFT–部分同步模型中第一个实用的BFT复制解决方案问世以来，许多BFT解决方案都是围绕其核心的两阶段范式建立的。第一阶段通过QC保证提案的唯一性。第二阶段保证新的leader能够说服复制体投票支持一个安全的提案。这需要leader从(n-f)个副本中传递信息，每个副本报告自己的最高QC或投票。一代又一代的两阶段工作因此在leader更换时遭遇了二次通信瓶颈。

​ HotStuff围绕着一个三阶段的核心，允许新的leader简单地挑选它所知道的最高QC。这减轻了上述复杂性，同时也大大简化了leader替换协议。在（几乎）规范了各个阶段之后，HotStuff的流水线就非常容易了，而且可以经常轮换leader节点。

附录

链式HotStuff的安全证明

定理5。让b和w是两个对立的节点。那么它们不能同时被一个诚实的副本承诺。证明。我们通过矛盾法来证明这个定理。通过类似于Lemma 1的论证，b和w必须在不同的视图中。假设在一个ectuion中，b通过QC三链b, b′, b′′, b∗在某个诚实的副本中被承诺，同样地，w通过QC三链w, w′, w′′, w∗在某个诚实的副本中被承诺。由于b, b′, b′′, w, w′, w′′中的每一个都得到了它的QC，那么，我们假设b是在比w′′高的视图中创建的，即b′.justify.viewNumber > w∗.justify.viewNumber ，如图11所示。现在我们用vs表示高于vw′′=w∗.justify.viewNumber的最低视图，其中有一个qcs，使qcs.node与w相冲突。形式上，我们对任何qc下达以下谓语。

​ E(qc) :=(vw′′ < qc.viewNumber ≤ vb) ∧ (qc.node conicts with w) 。我们现在可以设置第一个切换点qcs：qcs := arg min qc {qc.viewNumber | qc is valid ∧ E(qc)}。

​ 根据假设，这样的qcs存在，例如，qcs可以是b′.justify。让r表示w∗.justify和qcs的交集中的一个正确副本。根据qcs最小化的假设，在qcs形成之前，r对w的锁不会被改变。现在考虑r在视图vs中调用safeNode，消息m携带一个有争议的节点m.node = qcs.node。根据假设，锁的条件（算法1的第26行）是假的。另一方面，该协议要求t = m.node.justify.node是qcs.node的祖先。根据qcs的最小性，m.node.justify.viewNumber≤vw′′。由于qcs.node与w冲突，t不能是w、w′或w′′。那么，m.node.justify.viewNumber < w′.justify.viewNumber ，所以另一半的disjunct也是假的。因此，r不会投票给qcs.node，与r的假设相矛盾。

​ 有效性论证几乎与Basic HotStuff相同，只是我们必须假设在GST之后，连续两个leader节点是正确的，以保证决策。为了简洁起见，我们省略了这一点。

B 实施的安全证明

伪码 6. 假设b和w是两个相互矛盾的节点，使得b.height = w.height，那么它们就不能同时拥有有效的法定人数证书。证明。假设他们可以，那么b和w都得到了2f+1票，其中至少有f+1个诚实的副本为每个节点投票，那么一定有一个诚实的副本为两个节点投票，这是不可能的，因为b和w的高度是一样的。符号1. 对于任何节点b，让"←"表示父关系，即b.parent ← b.让"∗ ←"表示祖先关系，即父关系的反演闭合。那么，两个节点b，w是矛盾的，如果b ∗ ←w∧w ∗ ← b。让"⇐"表示QC所指的节点，即b.justify.node ⇐ b。让b和w是两个相互矛盾的节点。那么它们不可能同时被一个诚实的复制品承诺。证明。我们通过矛盾法来证明这个重要的定理。让b和w是两个处于不同高度的冲突节点。假设在执行过程中，b通过QC三链b(⇐ ∧ ← )b′(⇐ ∧ ←)b′′ ⇐ b∗在某个诚实的副本中成为承诺。同样地，通过QC三链w(⇐ ∧ ← )w′(⇐ ∧ ←)w′ ⇐ w∗，w在某个诚实的副本中成为承诺。根据定理1，由于每个节点b, b′, b′′, w, w′, w′′都有QC，那么，我们假设b.height > w′′.height，如图11所示。现在我们用qcs来表示高度小于w′′.height的节点的QC，该节点与w相冲突。E(qc) := (w′′.height < qc.node.height ≤ b.height) ∧ (qc.node conicts with w) 我们现在可以设置第一个转换点qcs: qcs := arg min qc {qc.node.height | qc is valid ∧ E(qc)}。根据假设，这样的qcs存在，例如，qcs可以是b′.justify。让r表示w∗.justify和qcs相交处的一个正确副本。根据qcs最小化的假设，在qcs形成之前，r对w的锁不会被改变。现在考虑对onReceiveProposal的调用，该消息携带一个有争议的节点bnew，这样bnew=qcs.node。根据假设，锁的条件（算法4的第17行）是假的。另一方面，协议要求t = bnew .justify.node是bnew的祖先。 根据qcs的最小性，t.高度≤w′′.高度。由于qcs.node与w相冲突，t不能是w、w′或w′′。那么，t.height<w.height，所以另一半的disjunct也是假的。因此，r不会投票给bnew，与r的假设相矛盾。 定理8。假设cmd 1和cmd 2是任意两个命令，其中cmd 1在cmd 2之前被某个诚实的副本执行，那么任何执行cmd 2的诚实副本都必须在cmd 2之前执行cmd 1。证明。用w表示携带cmd1的节点，b携带cmd2的节点。从Lemma 6可以看出，承诺的节点处于不同的高度。在不丧失一般性的情况下，假设w.height<b.height。w和b的提交是由更新中的onCommit(w′)和onCommit(b′)触发的，其中w ∗ ← w′，b ∗ ← b′。根据Lemma 7，w′一定不会与b′冲突，所以w不会与b冲突。然后w ∗ ← b，当任何诚实的副本执行b时，它一定会通过onCommit的递归逻辑首先执行w。

B.1 备注 为了深入了解HotStuff设计中的权衡，我们解释了为什么某些约束对于安全是必要的。

为什么是单调的vheight？假设我们改变投票规则，使副本不需要单调地投票，只要它不对每个高度投票超过一次。削弱后的约束会破坏安全性。例如，一个副本可以先为b投票，然后为w投票。在了解b′，b′′之前，它首先交付w′，w′′，假设锁在w上，并为w′′投票。当它最终交付b′′时，它将ip到bleader节点的分支，因为它有资格被锁定，而且b比w高。最后，副本也将投票给b′′，导致w和b的提交。直接父约束被用来确保证明中使用的等价物b.height>w′′.height，在Lemma 6的帮助下。假设我们不执行提交规则，所以提交约束被弱化为w ∗ ← w′ ∗ ← w′，而不是w ← w′ ← w′（对b也一样）。考虑一下w′.height < b.height < b′.height < w′′.height < b′′.height的情况。有可能，一个副本可以先投票给w′′，然后发现b′′，切换到b的分支，但这已经太晚了，因为w可能已经提交了。

关键词

副标题

摘要

关键词

在6G中以信息为中心的随处连接VR/AR的大规模物联网：一种拟议的缓存共识方法

摘要

现有的 海量物联网的发展不仅带来了丰富的硬件资源，也带来了数据管理难、资源运行难、效率低等问题。

6G网络可以解决 不仅可以提供更快的数据传输速率，更多的设备连接，还可以带来无处不在的虚拟现实/增强现实（VR/AR）服务。在6G时代，大规模的物联网设备将产生VR/AR服务和资源需求，网络也将面临前所未有的压力来应对无处不在的VR/AR需求。

针对上述问题

1. 提出了适合6G大规模VR/AR内容分发的以信息为中心的大规模物联网（IC-MIoT），以提高IC-MIoT的效率，充分保障用户的服务质量（QoS）。
   1. 介绍了IC-MIoT节点的区块链，并提出了一种新的共识机制Proof-of-Cache-Offloading（PoCO）。
   2. 提出了一个使用区块链支持的IC-MIoT用于VR/AR的架构。大量的物联网资源被充分整合和调度，以支持大规模的VR/AR应用和IC-MIoT。
   3. 为支持区块链的缓存卸载制定了Stackelberg博弈模型和缓存索引选择和计算算法。分析和性能模拟结果表明了所提方案的优越性和有效性。

关键词

6G, blockchain, information-centric network (ICN), massive IoT.

副标题

摘要

关键词

区块链； 信息中心网络；分片；声誉；共识；

副标题