Aptos共识与Block-STM笔记

0x7ac61a · December 15, 2022, 11:29am

Hacker Dōjo Workshop：
Bounty链接：Hacker Dōjo|课题研究：Aptos共识与交易并行执行 | Bounties | DoraHacks
创作者：@0x7ac61a
本项目由Hacker Dōjo资助，文章转载请联系
Telegram: @HackerDojo0
WeChat: @HackerDojo0

Aptos Block中能够执行每秒超160k条交易，为了实现高吞吐量和低延迟，Aptos 区块链在交易处理的关键阶段采用流水线和模块化方法。具体来说，交易传播、区块元数据排序、并行交易执行、批量存储和账本认证都同时运行。这种方法充分利用了所有可用的物理资源，提高了硬件效率，并实现了高度并行执行。

共识机制

Aptos中的共识机制AptosBFT源于DiemBFT，是基于Hotstuff共识修改而来的协议。Hotstuff则是一个BFT类共识协议。

许多BFT解决方案都是围绕其核心的两阶段范式建立的。其实用性在于一个稳定的领导者可以在短短两轮的消息交换中驱动一个共识决定。

第一阶段通过形成一个由（n-f）票组成的法定人数证书（QC）来保证提案的唯一性。
第二阶段保证下一个领导者能够说服副本投票给一个安全的提案。

但遗憾的是基于两阶段范式的视图改变很容易出现错误，考虑基于两阶段提交的算法流程：

客户端将自己的请求转发给主节点
之后主节点构造pre-prepare消息，并将其转发给其他的从节点
从节点验证pre-prepare消息，验证通过则发送prepare消息到其他节点
当一个节点收到2f+1个相同的prepare消息，则此消息在该节点prepared，之后执行

主要的问题可以理解为，当一个从节点收到2f+1个相同的prepare消息时，并不意味着2f+1个诚实节点与它具有相同的视图。考虑一种存在恶意节点的情况：

主节点在编号为n的操作给其中的f+1个诚实的从节点发送了m，给其他f个诚实的从节点发送了消息m’
之后进入prepare阶段，收到消息m的节点（f+1）会给m投票。假设有f个作恶节点只向M中的部分节点发送了投票消息m，这样M中的一部分节点M1能够提交消息m，剩下的部分始终无法收集2f+1个投票，也就无法提交消息m（这个时候安全性已经被破坏了）
已经提交的节点认为自己收集到了2f+1个投票，但实际上并没有2f+1个节点，甚至可以是少于f+1个节点对消息进行了提交

同时PBFT是最早的可以实用的拜占庭容错共识算法，该算法最大的短板是ViewChange时的消息复杂性，每当需要在共识节点中切换Leader时，都需要大量的消息O(n^3)，这是很复杂的。

Hotstuff

HotStuff提出了一个三阶段投票的BFT类共识协议，通过在投票过程中引入门限签名实现了O(n) 的消息验证复杂度。门限签名即每一轮的共识投票消息，都是各个共识节点发送给Leader节点，由Leader将这些消息签名组合成一个再广播，这样极大的较少了系统中消息量，从O(n^2)减到了O(n)。

HotStuff是基于View的的共识协议，View表示一个共识单元，共识过程是由一个接一个的View组成。在一个View中，存在一个确定Leader来主导共识协议，并经过三阶段投票达成共识，然后切换到下一个View继续进行共识。假如遇到异常状况，某个View超时未能达成共识，也是切换到下一个View继续进行共识。

HotStuff还采用了链式确认，我们认可一个区块，实际上也是对于该区块父区块的认可。在链式的HotStuff中，可以将区块的确认放在下一个区块中，只要一个区块后面产生了三个连续区块，那么就说明该区块经过了三轮投票确认，就可以最终敲定了。

Hotstuff的特点：

线性视图的改变：任何正确的Leader一旦被指定，只需发送O(n)的消息来驱动一个共识决定。
快速的响应：任何正确的Leader一旦被指定，只需要等待前n-f个回应来保证它的提案能够有进展。

背景：

我们考虑一个由固定的n=3f+1个副本组成的系统，以i∈[n]作为索引，其中[n]={1, . . ,n}. 一组F⊂[n]的最多f=|F|复制是拜占庭式的故障，其余的是正确的。

Basic Hotstuff

Basic Hotstuff分为三个阶段，prepare、precommit与commit。

Prepare阶段

每个View开始时，新的Leader收集由(n−f)个副本节点发送的NEW-VIEW消息，New-View消息由一个副本在过渡到viewNumber时发送，并携带该副本收到的最高prepareQC。prepareQC可以看做是对于某个区块(n−f)个节点的投票集合，共识过程中第一轮投票达成的证据。

Leader会对这些消息进行处理并选择一个分支，Leader从收到的NewView消息中选取高度最高的preparedQC作为highQC。因为highQC是(n - f)个副本中最高的，所以不会有比它更高的区块得到确认。因此由highQC.node领导的分支被认为是是安全的。

Leader使用createLeaf方法用一个新的proposal来扩展highQC.node的尾部。该方法创建一个新的叶子节点作为子节点，并将父节点的摘要嵌入子节点中。Leader节点会在highQC所在的安全分支来创建一个新的区块，并广播proposal，proposal中包含了新的区块和highQC，其中highQC作为proposal的安全性验证。

其他节点（replica）一旦收到当前View对应Leader的prepare消息，Replica会根据会safeNode-predicate规则检查Proposal是否合法。如果Proposal合法，Replica会向Leader发送一个Prepare-vote（根据自己私钥对Proposal的签名）。

Replica对于Proposal的验证遵循如下的规则:

Proposal消息中的区块是从本机lockQC的区块扩展产生（即m.block是lockQC.block的子孙区块）
为了保证liveness, 除了上一条之外，当Proposal.highQC高于本地lockQC中的view_number时也会接收该proposal。

伪代码如图：

Precommit阶段

Leader发出proposal消息以后，等待(n−f)个节点对于该proposal的签名，集齐签名后会将这些签名组合成一个新的签名，以生成prepare-QC保存在本地，prepare-QC可以表明有(n−f)个节点对相应的proposal进行了签名确认，然后将其放入PRE-COMMIT消息中广播给Replica节点。

一个副本以Pre-Commit投票的方式回应领导者，该预承诺投票具有提案的签名摘要。

在HotStuff中引入了阈值签名方案，Replica利用各自的私钥份额签名，由Leader收集签名，Replica只需要将签名消息发送给Leader就可以。Leader将Replica的签名组装后，广播给Replica。这样HotStuff的一轮投票每个Replica只需要验证一次签名。

Commit阶段

commit阶段与precommit阶段类似，也是Leader先收集(n-f)个precommit-vote，然后将其组合为precommit-QC,并将其放在COMMIT消息中广播。

当Leader收到当前Proposal的（n-f）个precommit-vote时，会将这些投票组合成precommit-QC，然后将其放入COMMIT消息中广播。

当replica收到leader的PRE-COMMIT消息时，将自己将本地的lockQC更新成收到的precommitQC，并且回复一个vote。

Decide阶段

当Leader收到了n-f个commit-vote投票时，将他们组合成commitQC，广播DECIDE消息。

当Replica收到COMMIT消息时，会对其签名commit-vote，然后回复给leader。在此时，replica锁定在precommitQC上。

Replica收到DECIDE消息中的commitQC后，认为当前proposal是一个确定的消息，然后执行已经确定的分支上的tx。Viewnumber加1，开始新的阶段。

最终进入下一个视图

进入下一个试图，节点开始发送New-View消息给Leader。

Safety、Liveness和Complexity

Safety

安全性性证明：同一个View下，不会对冲突的区块，产生相同类型的QC

证明思路：反证法，假如在同一个view下，产生了相同类型的QC，而且最多存在f个作恶节点，那么就会有一个诚实节点双投了，这与前提假设矛盾。

Lemma1：对于任意两个有效的qc1、qc2，假如qc1.type==qc2.type，且qc1.block与qc2.block冲突，那么必然有qc1.viewNumber!=qc2.viewNumber.

证明（反证法）：假设qc1.viewNumber==qc2.viewNumber，那么在相同的view中，有2f+1个replica对qc1.block进行签名投票，同样有2f+1对qc2.block投票，这样的话，就存在一个正常节点在算法流程中投了针对某个消息投了两票，这与算法流程冲突。

安全性证明：正常Replica不会commit冲突的区块

定理2： 如果w和b是冲突的节点，那么它们不可能同时被两个正确的副本分别提交

反证法，假如正常节点提交了冲突的区块，我们追踪到最早出现的冲突区块的位置，则这个冲突的位置肯定与两条safety规则相矛盾。

根据Lemma1，在相同的view下，正常的replica不会对冲突的区块产生commitQC，所以不会commit冲突的区块。
下面证明在不同的view下，正常的replica也不会对冲突的区块产生commit

证明（反证法）：假设viewNumber在v1和v2时（v1 < v2），commit了冲突的区块，即存在commitQC_1 = {block1, v1}, commitQC_2={block2, v2}，且block1与block2冲突。为了简化证明，我们同时假设commitQC_2是commit_1之后的第一个commitQC。在v1和v2之间,肯定存在一个最小的v_s(v1 < v_s <= v2)，使得v_s下存在有效的prepareQC_s{block_s, v_s},其中block_s与block1冲突。当含有block_s的prepare被广播后，节点会对该消息做safety验证，由于block_s与block1冲突，所以显然，不符合safety规则1。

假如block_s.parent.viewNumber > block_1.viewNumber，那么显然block_s.parent与block_1冲突，所以block_s.parent是更早的与block1冲突的，这与v_s最小矛盾。

有2f+1个节点对于block_s的prepare消息投了票,那么这些节点在收到Prepare_s时,会进行safeNode验证,正常情况下,由于block_s与block1冲突,那么正常节点不会投出prepare_vote票,故而根本不会产生prepareQC_s, v_s根本不会存在。这与上述假定冲突,因此在不同的view下,不可能对相同的block产生commit。

Liveness

Lemma 3： 如果一个正确的replica被锁定，使得lockedQC = precommitQC，那么至少有f+1个正确的副本投票给与lockedQC匹配的prepareQC。

证明：假设副本r被lock在precommitQC上。那么，在prepare阶段有n-f票投给了匹配的prepareQC，其中至少有f+1票是来自正确的副本。

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

证明：从一个New-View开始，领导者收集n-f个New-View消息，并在广播prepare messsage之前计算它的highQC。假设在所有的replica中（包括领导者本身），保持最高的锁是lockedQC = precommitQC。根据Lemma 3我们知道至少有f+1个正确的副本投票选出了与pre-commitQC相匹配的prepareQC，并且已经在他们的new-view消息中把它们发送给了领导者。

因此，领导者必须在这些新视图消息中至少选择一个匹配的prepareQC，并在其prepare消息中使用它作为highQC。根据假设，所有正确的副本在他们的视图中都是同步的，并且领导者是无故障的。因此所有正确的副本将在prepare阶段投票，因为在safeNode中，为了保证liveness, 当Proposal.highQC高于本地lockQC中的view_number时也会接收该proposal。然后，在Leader为这个视图组建了一个有效的prepareQC之后，所有的副本将在接下来的所有阶段进行投票，从而导致一个新的决定。在GST之后，这些阶段完成的持续时间Tf是有边界的，因为没有明确的等待∆时间的步骤，而且safeNode中的逻辑会被用来在三阶段范式的帮助下覆盖一个过时的锁。

Complexity

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

Chained Hotstuff

在Basic hotStuff中，三阶段投票每一阶段无非都是发出消息然后收集投票，那么可以使用如下的方式简化协议。

在Prepare阶段的投票由当前view对应的leader1收集，集齐后生成prepareQC。然后将prepareQC发送到下一个view的leader2那里，leader2基于prepareQC开始新的prepare阶段，这是leader2的prepare阶段，同时也是leader1的precommit阶段。以此类推，leader2产生新的prepareQC,然后发送给下一个view的leader3，leader3开始自己的prepare阶段，同时也是leader1的commit阶段、leader2的precommit阶段。

协议简化为如下过程：

Leader节点：

等待NewView消息，然后发出Proposal
发出Proposal后，等待其他节点的投票
向下一个Leader发出NewView消息

非Leader节点：

等待来自Leader的Proposal消息
收到Leader的Proposal消息后，检查消息中的QC，更新本地的prepareQC、lockedQC等变量，发出投票
向下一Leader发出NewView消息

正常情况下，每个View中都有一个区块产生并集齐签名，但有时不会有新的区块产生。为了保持区块高度与viewNumber的一致，hotStuff中引入了Dummy block的概念。假如在一个View中，不能达成共识，那么就在为该View添加一个Dummy block。

Pacemaker

把hotstuff抽象成一个事件驱动的协议，可以将liveness相关的功能抽离出来，成为单独的pacemaker模块。safety与liveness在实现上解耦，safety是协议的核心保证安全性，liveness则由pacemaker保证。

safety：

liveness：

值得注意的是，即使一个坏的Pacemaker任意调用onPropose或任性地选择一个父节点和一个QC，并且在任何调度延迟，安全也总是有保障的。

Block-STM

Block-STM：一个智能合约并行执行引擎，围绕着软件事务性内存的原则建立的（Software Transactional Memory）。Transaction组成block，每个block的执行都需要具有相同的结果。

Block-STM的输入是一个交易块（Block），其中包含n个预设了顺序的交易，tx1<tx2<…<txn，问题的定义是执行区块并产生最终状态，相当于按顺序执行tx1,tx2,…,txn每个txj在txj+1开始前执行完成的状态。

在Block-STM中，每个交易可能会被执行几次，我们把交易的第i次执行的执行称为交易的incarnation i。对于交易的每个incarnation，Block-STM会维护一个读集和一个写集，读集合包含了读取的内存位置和对应的版本，写集描述了写入的位置，(memory location, value)对。

在一个交易的一次执行之后，需要通过Validate，Validate会重新读取读取集并比较观察到的版本。

Thread logic

run()过程与Scheduler模块接口由一个循环组成，让调用线程持续执行exectuion和validate任务。线程在第9行寻找一个新的任务，并根据它的类型分配一个适当的处理程序，即第5行的函数try_execute用EXECUTION_TASK，第7行的函数needs_reexecution用于VALIDATION_TASK（成功的验证不会改变状态，而失败的验证意味着交易需要重新执行）。这两个函数都接受一个交易版本（交易索引和incarnation）作为输入。一个try_execute函数的调用可能会返回一个新的验证任务给调用者，而一个needs_reexecution函数的调用可能会返回一个新的执行任务。

执行task：一个执行任务的处理是try_execute过程处理。首先在第12行调用一个VM.execute函数，一个成功的虚拟机的执行会返回一个写集，由内存位置和它们的更新值构成，这些值被第18行的记录函数调用应用到MVMemory上。VM.execute还捕获并返回一个读集，其中包括读取的所有内存位置，读集也被传递给第18行的MVMemory.record调用，并且存储在MVMemory中，以便后续的验证。

第19行的Scheduler.finish_execution安排了所需的验证任务。当一个新的位置没有被写入时，write_new_location变量被设置为false，只需要验证事务本身就足够了。

事务txj的虚拟机执行可能会观察到对较低的事务txk的读取依赖，其预设顺序是k<j。例如txk向txj读取的位置写入数据，但是当txk的执行在txj的读取之前中止，就可能会发生这种情况。在这种情况下，阻塞事务的索引𝑘被作为vm_result.blocking_txn_idx返回，这是第12行中输出的一部分。

第14行调用了Scheduler.add_dependency。当txk在添加依赖性之前被重新执行时，如果dependency被解决了，在第15行中，执行任务被立即重试。

验证task：

第22行的avalidate_read_set调用获得了执行txn_idx所记录的最后一个读集，并检查重读读集中的每个内存位置是否仍然产生相同的值。如果交易执行被中止，那么第25行的convert_writes_to_estimates(txn_idx)被调用，它在共享内存数据结构中用特殊的ESTIMATE标记当前交易写入的内容。并在第26行的Scheduler.finish_validation调用中对更高的事务重新加入验证。

VM Module

对于每一个交易都有一个读集合和一个写集合，用于后续的并行执行判断，构成规则如下：

当tx试图读取一个位置时：当一个事务试图将一个值写入一个位置时，（location，value）对被添加到写集中
当一个tx试图读取一个位置时：如果该位置已经在写集中，那么虚拟机就会在第85行读取相应的值（是该tx自己写入的），否则将执行MVMemory.read，如果它返回NOT_FOUND，则VM直接从存储空间读取该值并记录(location，⊥)在读集中。如果 MVMemory.read 返回 READ_ERROR，那么 VM执行停止，并将错误和阻塞事务索引（依赖关系）返回给调用者。如果它返回OK，则 VM 从 MVMemory 读取结果值，并在在读集中记录位置和版本。

Example

依赖性估计

Block-STM不会预先计算依赖，而是对于每一个交易Block-STM会将一个abort的交易执行的写集视为对下一个实例的写集的估计，加上多版本的数据结构和交易预设的顺序，通过检测潜在的依赖来有效的降低交易abort的概率。

当一个incarnation由于验证失败而被中止时，多版本数据结构中对应于其写入集的条目被替换成一个特殊的 ESTIMATE 标记。这意味着下一个incarnation估计会写到同一个内存位置。特别是只要事务txj读到由较低的事务txk写入的标记为 ESTIMATE 的值，它就会立即中止。

Collaborative scheduler（协作式调度器）

返回条件：V和E都空并且没有其他task正在执行，return

下一个task：有最小tx index的交易，在V和E中

执行task：执行下一个交易，如果读到了一个被标记为Estimate的值，那么交易执行abort（终止）并添加回E，否则
如果有一个写入的内存位置，而tx的前一个完成的incarnation没有写入，则为所有的事务≥𝑡𝑥创建验证任务，这些事务目前不在𝐸或正在执行，并将其添加到V
否则只为tx创建一个validation task并将其添加到V
验证task：验证交易，如果success就continue，否则abort
将（多版本的数据结构中）由交易（未通过验证）写入的每个值都标记为Estimate
为所有目前不在𝐸或正在执行的>𝑡x交易创建验证任务，并将其添加到V
为交易𝑡x创建一个执行任务和一个递增的数字，并将其添加到E中。

在这个例子中tx4依赖于tx2，

在stage1，因为没有Validation task，所以线程们并行执行tx1，tx2，tx3
在stage2，线程们并行的验证tx1，tx2，tx3；tx2的验证失败了而tx1，tx3的验证成功了。tx2执行失败是因为tx2读的内存可能被tx1修改过，tx2的执行被中止，它的每一次写入都被标记为多版本数据结构中的Estimate，tx2被添加回E中，同时tx3被重新加入V中，以防止tx2对tx3产生潜在的影响。
在stage3，tx2和tx4开始执行，同时tx3被验证。然而tx4由于读取了一个被标记为estimate的值，所以tx4没法执行，换做E中的下一个交易tx5执行。𝑡𝑥4被记录为𝑡𝑥2的依赖关系，并在𝑡𝑥2的执行结束后被添加到E。在tx2和tx5都执行结束后，被加入验证中。在这个例子中，tx2并没有修改新的存储，tx3不依赖于tx2，因此新的对tx3的验证就不需要了。
在stage4中，tx2和tx5被成功验证，tx4开始执行。在这个位置，tx1，tx2，tx3不会再被重新执行了，因为他们不再出现在V或者E中。由于tx4写入了一个新的内存位置，因此tx5需要再加入V去重新验证。
在stage5，tx4和tx5被验证，tx6被执行。

预设的序列化顺序决定了事务必须按顺序提交，所以对一个交易的成功验证并不能保证它可以被提交。因为区块中较早的事务的中止和重新执行可能会使交易的读集无效，从而需要重新执行。因此，当一个交易中止时，所有较高的交易需要被安排重新验证。由于交易必须按顺序提交，BlockSTM调度器会优先处理与低索引交易相关的任务（验证和执行）。

当一个交易txk读取到了一个被写操作标记为ESTIMATE的值时，就说明txk遇到了一个依赖。为了便于表述，在上述描述中，一个事务在遇到依赖关系时立即被添加回𝐸。然而，正如第3节所解释的，Block-STM实现了一个稍微复杂的机制。事务𝑡𝑥𝑘首先被单独记录为𝑡𝑥𝑗的依赖关系，并且只有在𝑡𝑥𝑗的下一个化身完成时（即依赖关系被解决时）才被添加回𝐸。

完成validation并不意味着可以安全的提交，但是失败的validation意味着需要重新执行。

Optimistic validation

一个交易可能会写入一个内存，这个内存之前被一个序号更高的交易读过，这就是为什么在1a中当一个交易完成时，需要为更高序号的交易创建验证。

当一个交易只写入内存中的一个子集时，Block-STM只对这个交易加入验证，这是有效的，因为2a，因为所有的写入在前一个交易执行的时候已经被标记为ESTIMATE并且标记验证失败了。并且乐观的对大于当前交易的交易加入validate，终止导致在2(b)中为更高的事务乐观地创建验证任务。执行这些任务的线程已经可以检测到由于内存位置的估计标记而导致的验证失败，而不是等待后续的incarnation完成。