在了解了 HotStuff 之后，我开始关注 DAG-Based BFT 共识，从而了解了 Narwhal and Tusk，这是 Sui 使用的共识协议，它声称对传统的 BFT 共识有巨大的性能提升，论文中大致描述如下：

Narwhal Hotstuff 在广域网可以实现 130k tps, 普通 Hotstuff 只能是 1.8k, Narwhal Tusk 为 160k tps。而之所以用 Tusk 替代 HotStuff 主要解决 HotStuff 在 Unhappy path 下交易确认延迟增大的问题。

本文不会对 Narwhal and Tusk 做过多细节描述，更多的是依据论文以及源码，对 Narwhal and Tusk 的设计思路和底层逻辑进行思考，换句话说，我想知道 Narwhal and Tusk 的设计思路，而不仅仅是对这两个协议的原理介绍。文章分为两篇，Part1 介绍 Narwhal，Part2 介绍 Tusk。

首先要明白的是，Narwhal 并不是一个共识协议，而是一个交易池协议（Mempool protocol）。

对其他文章感兴趣欢迎访问我的个人博客

BFT 共识的性能瓶颈

Narwhal and Tusk 达到了 20w+ TPS 的原因在于 Narwhal 将 BFT 的交易排序过程和共识过程实现了解耦。

这句话网上到处都是，但什么叫交易排序和共识解耦，为什么解耦之后会令共识吞吐量大幅上升？

从 PBFT，Tendermint 到 HotStuff，随着 BFT 共识的不断演进，系统可以达到数千 TPS，比如 HotStuff 的吞吐量基本在 2-3k TPS，很难再有突破。下面是 HotStuff 的共识过程，这不是本文的重点，感兴趣可见 HotStuff 工程与实现，里面有十分详细的介绍。

整个共识过程就是让全网所有的节点对同一个状态达成一致，这个状态是通过对一个区块中一批交易执行后获得的，且这批交易需要按照一定顺序排列。所以每个节点在尝试对一个提案进行验证和计算之前，其实是有下面两个前提的：

• 所有节点的交易池都应该有对应交易，否则无法执行该交易。
• 所有节点对提案中交易的顺序是认可的。

对于一些主流的共识算法，交易顺序的共识已经包含在了区块的共识过程当中，比如比特币就是挖到矿的矿工才有权打包交易并决定顺序，收到该区块的节点直接同步交易并无条件的认可该顺序。再比如 HotStuff 中，Leader 根据自己的规则决定提案中交易的顺序，而 Validator 无条件认可这个交易顺序，只需要保证该交易是本地存在的。

所以，对一个提案的共识是需要这两个前序步骤的：

• 交易内容的传播与同步。
• 交易顺序的传播与协商。

这两个过程可以耦合在一起，也可以分开进行，比如，如果将 Proposal 结构定义为下面这样，那么意味着交易数据本身需要随着共识消息进行传播。

type Proposal struct {
    View int // 视图号
    Txs []Tx // 一定顺序的交易数据
}

或者在有些方案中，这些交易数据在此之前已经通过 Gossip 协议在 Validators 之间完成了传播，共识提案中只需要包含交易的顺序信息即可，各节点收到提案之后在本地交易池中取得实际的交易数据进行计算，这样 Proposal 应该这样定义：

type Proposal struct {
    View int   // 视图号
    Txs []Hash // 一定顺序的交易哈希
}

然而无论使用上面哪种方式，即使仅包含交易的哈希值，提案的体积也是很大的，而提案的体积越大，它在网络中传播的过程也就越慢，这成为 BFT 共识效率的瓶颈。这是因为对于部分同步共识协议来说， 只能是一个提案接一个提案地串行进行共识，保证不同区块可以组成唯一的一条链状结构，是全局有序的。

举个例子。

假设一个城市中有一家连锁书店，它有多个门店，所有门店都会持续收到新书，现在要保证所有门店的书以及书在书架中的摆放位置都是一样的。

我们假设所有门店都有了需要摆放的书，只是不知道要按什么顺序摆到书架上，此时传统 BFT 的做法就是门店 A 作为旗舰店（Proposer）决定书在书架中的摆放顺序，它将第一个书架中书的摆放顺序写在纸上（交易的哈希值），并让快递把这些纸送给其他门店。其他门店收到后经过验证，就根据纸上的写法一一对应的把书放在了书架 1，然后让快递员回复旗舰店自己摆好了（完成共识并提交）。旗舰店收到所有门店的消息后很满意，开始决定书架 2 的顺序，之后不断重复上述过程，如下图。

这个例子中能够看到两个问题：

• 虽然只是一些记录了顺序的纸（交易的哈希），也是很多的，拖慢了快递员送达的时间。
• 当摆好了书架 1 之后旗舰店才开始决定书架 2 的摆放顺序并通知其他门店，而书架 1 的共识过程是很复杂的，需要经历多轮沟通。

由于交易顺序的沟通是同步的，这占用了大量时间，这本质上是因为交易顺序的沟通与共识消息耦合了。

仔细想想这完全没有必要，书架排放顺序（交易顺序）的沟通，完全可以和书架摆放命令（共识）并行进行，比如一边负责把书架 1、2、3 的顺序依次广播出去，另一边从本地获取这个顺序，然后依次进行摆放。如下图：

上图中，书架摆放顺序的传播与实际摆放过程是并行进行的，旗舰店将三个书架的摆放顺序依次同步给其他门店并达成一致。同时，依次对三个书架进行摆放，这就完成了交易顺序的传播与共识过程解耦。

而因为共识过程涉及签名验签、交易执行等过程本身十分耗时，而交易顺序同步涉及大量数据传输本身也十分耗时，解耦避免了两者互相阻塞，并发进行大大提高了系统的吞吐能力。此时，提案的结构中不再包含任何交易的信息，因此提案消息非常的小，而交易数据以及交易顺序预先已经传播完成，这就是为什么说，交易顺序与共识解耦，提高了整个系统的吞吐能力。此时共识的 Proposal 结构简化成了这样。

type Proposal struct {
    View view // 视图号
}

这基本不消耗什么带宽。因此，传统 BFT 的吞吐量的瓶颈并不在共识协议本身，而是在交易顺序的一致性机制上，按照上述思路，我们尝试将交易顺序的协商过程从共识模块迁移到了交易池中，并把这个新的交易池协议称为 Narwhal。

Narwhal 不是一个共识协议，而是一个交易池协议。传统的 Mempool 只是管理交易的容器，负责交易内容的同步，交易顺序的协商部分却扔给了共识层，而恰恰是这部分内容成为了 BFT 类共识区块链的性能瓶颈，同时不同 Vaildator 交易池之间交易内容同步缓慢也造成了共识过程的阻塞，而 Narwhal 用以下方法解决上述问题：

• 使用并发 + DAG 策略在 Mempool 中实现了交易顺序的高效协商。
• 使用 primary + workers 节点扩展架构实现了交易内容的快速同步。

下文会进一步解释。

Narwhal 的设计逻辑

Double Transmission 问题

对于传统的 Mempool 交易池，一个交易被客户端发送给 Validator 后会通过 Gossip 的方式传播给其他 Validators，而共识提案中又会打包一遍这些交易，从而重复占用了带宽，这称为 double transmission 问题。即使在共识提案中打包的是交易们的哈希值，仍然无法避免 TPS 较高时占用 Leader 节点较高的带宽，这使得 Leader 的带宽成为瓶颈。

A transaction submitted to one validator is gossiped to all others. This leads to fine-grained double transmissions: most transactions are shared first by the Mempool, and then the miner/leader creates a block that re-shares them.

Double transmission 的根本原因是即使 Mempool 已经完成了交易内容的同步，仍需要对交易顺序进行协商。既然我们不希望这样，那么是否可以在 Mempool 传播交易内容时顺便完成对这批交易顺序的协商，这就是 Narwhal 的基本思路。

为此 Narwhal 将一批交易打包成了一个 Block，为了与共识层的 Block 进行区别，下文称之为 Mempool Block。与共识提案类似，Mempool Block 中不仅包含了这批交易的内容，理所应当的也包含了交易的顺序信息。这样在 Mempool 协议中就同时实现了交易同步和交易顺序的协商，避免共识层重复打包交易。

多链并行共识

BFT 类共识算法的一个问题是，它只有一条区块链在串行增长，而一个新区块的共识需要等待一个 Leader 节点打包并发布提案，在 Leader 发布提案期间，其他的 Validators 能做的只有等待，这样既浪费了时间，又闲置了资源。换句话说，由于只有一条链，所以一个 View 只能有一个 Leader，这注定是个串行的过程。而即使交易顺序的协商放在了 Mempool 协议中进行，也是相同的串行过程。

下图中展示了一个 4 节点的区块链网络，每个节点负责接收客户端发来的交易，并在 Mempool 中实现交易的同步，之后通过共识协议完成区块的串行提交。但由于每个区块对应单一 Leader，该 Leader 成为性能瓶颈。

解决 Leader 阻塞的问题就是多条链并行出块，比如某个视图进行共识时，Node1 对于链 1 可能不是 Leader，但它在链 X 上就可以是 Leader 负责打包提案。这样资源的占用平均分配给了所有的节点，并行出块也极大提升了网络的吞吐能力。

然而多条链并行出块方案中，需要定义一个规则，来确定某个交易应该分配到哪条链。

一种很直观方法是，我们定义并发链的数量，比如 $N$，然后根据交易的哈希值取模平均分配到 $N$ 条链上。如下图。图中，每个节点的状态中包含了 $N$ 条链，当某节点接收到一个交易后，需要先在 Validators 当中完成交易的同步，之后尝试对交易进行打包并共识，只不过该交易会通过某个确定的规则分配到对应的链进行共识。此时多条链同时出块，系统状态就很难阻塞在单一的 Leader 节点之上。

那么 $N$ 是多少比较合适？

我们发现既然每个 Validator 在 Gossip 之前都会自己收到一批交易，那么不让按照 Validator 区分交易所在的链。即假设 ValidatorSet 中有 $X$个节点，则总共有 $X$ 条链并行出块，而每条链上的区块永远只由对应的 Validator 打包发布，这样如果我们将实际的交易数据放入 Block 中，甚至连交易同步过程也可以省略。换句话说，一条链中的区块包含的交易都是对应 Validator 率先接受的交易，而发布区块的过程本身就是同步交易的过程，如下图。

图中，每个节点在收到各自的交易后，并不会像前面的方案一样进行 Gossip 同步，而是直接由各个 Validator 负责出块并广播该区块，收到其他节点发来的区块后保存到本地等待共识层进行共识，同时该区块也起到了交易同步的作用。

多链全局顺序的保证

读者可能已经发现问题，多条链并行的方案虽然可以极大的提升每个节点的资源利用，显著地提高吞吐能力，但是多条链之间会存在一致性问题。比如，Bob 发给 Alice 1 个 token，之后 Alice 又发送了 1 个 token 给 Tom，如果这两个交易被分配到了两条不同的链上，那么如何保证某一时刻不同节点的系统状态一致？有的节点可能先执行了 Bob -> Alice 交易，有的节点却先执行了 Alice -> Tom 交易，但如果 Alice 一开始余额为 0，就会造成部分节点执行失败，全局状态无法达成一致的问题。

这就要用到 DAG，DAG 可以解决并行出块策略下，如何确定区块全局顺序的问题。基本思路是，每个区块发布时不仅仅要包含自己这条链的父区块，还需要包含其他链的父区块，如下图。每个区块在 Mempool 协议中构造时，都会引用前面至少 $2f+1$ 的区块，从而实现了一个区块中包含了整个 DAG 的全局信息，为区块之间添加了因果联系。之后我们根据 DAG 区块之间的引用关系，就能够从多条并行的区块链中共识出一个全局认可的区块顺序。

DAG 确定全局顺序的原理这里不做讨论，只需要知道如下两点：

• DAG 的本质是每个区块汇报当前图的样子信息，而不仅仅是父区块。
• 要解决的问题不再是从分叉中选择一条 Canonical 链，而是给一个 DAG 上的区块做全局排序。

Mempool block 的有效性与泛洪攻击

截至目前，我们确定了使用 Mempool block 打包交易直接进行交易同步与交易顺序协商的策略，之后共识层只需要指定要共识的 Mempool block 然后从本地获取它的数据就行了。换句话说，待共识的提案需要提前准备在 Mempool 中，一旦节点发现本地缺少某个 Mempool block，就会从邻居节点同步。

问题来了，只要涉及到区块的同步就要考虑该区块是否有效，否则恶意 Leader 随意驱使其他 Validator 同步自己构建的区块，即使这些区块是恶意的。

类似于 HotStuff 的 QC 机制，一个 Mempool block 的有效性可以由 $2f+1$ 个节点签名保证。当一个 Validator 打包一个 Mempool block 并广播给其他 Validators 时，其余 Validators 需要对该 Mempool block 验证并签名，当凑足 Quorum 签名后即可为该 Mempool block 生成 Certificate 证明其有效性，只有拥有 Certificate 的 Mempool block 可以被其他 Validators 下载。

即使保证了 Mempool block 有效，一个高性能的 Validator 仍然可以凭借其性能优势而快速增长 DAG 中自己的那条链，强迫其他节点大量下载自己发布的区块，造成泛洪攻击。

解决这个问题需要协调所有节点打包 Mempool Block 的节奏，为此 Narwhal 设计了轮次（Round）概念，当 Round-1 满足一定条件时才能以对 Round 轮次进行区块打包。具体来说，打包一个新的 Mempool block 需要引用 Round-1 中 $2f+1$ 个 Certificate，即，本轮的 Mempool block 必须拥有足够的 parents，否则将视为无效。下图展示了一个 4 节点网络中某一个 Validator 的 DAG 状态。

图中，round1 打包的区块均引用了至少 3 个 round0 的 QC（引用了 QC 等同于和其对应的区块建立了因果联系），然后广播给其余 Validators，收到 $2f+1$ 投票后即为本轮 round1 的区块生成了 QC，再在 round2 通过 Mempool Block 下发给所有节点。

下图展示了 4 节点网络的全局视角下 Mempool 消息在节点之间传递的过程，灰色虚线框代表该节点当前的 Mempool 状态。

CPU 和带宽瓶颈

至此，我们使用了每个 Validator 一条链的方案提升了共识的吞吐性能，同时使用了 DAG 保证了多链的全局顺序，并通过将交易顺序放置在 Mempool block 中解决了交易数据的 double transmission 问题。然而：

• 如果交易量的进一步升高，Validator 使用 Mempool block 同步交易数据时，带宽将成为了进一步突破性能上限的瓶颈。
• 基于 DAG 全局排序的多链并行方案下，BFT 共识会消耗大量的 CPU 资源。

下面具体对这两个问题进行解释。

虽然 Mempool block 作为载体可以避免传统交易同步与顺序协商造成的带宽重复占用问题，但随着交易量越来越多，Mempool block 必将使带宽成为新的性能瓶颈，这是由于一台机器带宽存在上限。

另外，我们在 Shardora 链的开发过程中同样使用过多链并行的共识方案，发现会消耗大量 CPU 资源。这种消耗主要来自于并发下更加频繁的签名验签行为，实测一台 8 核 CPU 的服务器运行 4 个节点并全功率压测的情况下，也就能支持 2～3 条链的并行出块，那就更别提 Narwhal 是一个 Validator 一条链了，单台服务器的 CPU 会被快速耗尽。基于这两点，Narwhal and Tusk 论文中提到了 Scale-out 设计，从某种角度来说也是不得已的事情，不得不想办法解决。

为解决 CPU 占用以及带宽瓶颈的问题，Validator 不应当限制在一台机器上，Narwhal 将一个 Validator 拆分成了多个 worker 节点和一个 primary 节点：

• worker 节点：负责收集交易，打包成 batch（一批交易），并进行 Validator 之间的交易内容同步。
• primary 节点：负责打包 worker 输出的 batch，通过 narwhal 协议产生 DAG，使得系统对交易排序达成共识。

将 Validator 进一步拆解后 Narwhal 协议的示意图如下。图中，每个 Validator 均包含一个 primary 节点和多个 worker 节点，worker 节点数量可以横向扩展。worker 节点负责接受客户端发来的交易数据，然后绕过 primary 节点直接在不同 Validators 的 worker 节点之间进行传播，由于 worker 节点可以水平扩展，因此带宽不是问题。之后 worker 将大量交易聚合并打包成 batch 发送给 primary，batch 是个哈希值，由 primary 负责广播 Mempool block 并构建 DAG。

需要注意的是，此时的 Mempool 由于 worker 可以横向扩展，交易的同步不再成为性能瓶颈，因此 Mempool block 不需要负担交易同步的职责，而是只包含 batch 哈希值即可，这么做使得 Mempool block 占用更少的 primary 节点带宽。论文声称，需要 10000+ worker 才能让 primary 工作量等于 worker，primary 很难成为瓶颈。修改后，交易传播过程如下图所示，其中虚线箭头代表 Mempool block 中不再包含交易数据，而是交易的哈希值。

这便是 Narwhal 协议的最终形态。

Narwhal 与共识层

Narwhal + HotStuff

Narwhal 作为一个交易池协议，可以很方便接入现有的 BFT 共识，比如 HotStuff。接入后，HotStuff 的每个视图共识时，Proposer 不再广播包含交易的区块，而是直接从本地 DAG 交易池中获取要打包的交易，因为此时 Narwhal 交易池协议已经完成了交易内容和交易顺序的同步，HotStuff 只需要从本地获取某个轮次待共识的交易即可。下面是 Narwhal 和 HotStuff 的配合过程。

下图展示了 Narwhal Mempool 和 HotStuff Consensus 的配合过程，两者完全解耦，上面部分是 Narwhal 交易池协议，下面部分是 HotStuff 共识过程。图中有 4 个 Validators，它们之间使用 Narwhal 协议不断的同步自己的 Mempool blocks，形成一个 DAG，一旦某个轮次有 $2f+1$ 个 Mempool blocks 获得了 Certificate，就可以进入下一轮，而拥有了 Certificate 的 Mempool block 就会被视为合法，其中的交易和顺序信息也就可以被 HotStuff 共识层获取了。

比如在下图的 R1 轮次中，A1、B1、C1 三个 Mempool block 拿到了 Certificate，因此 HotStuff 在对应轮次共识时，Validator A 被选为 Leader，那么该提案中打包交易就来源于 A1、B1、C1，只不过由于所有 Validators 已经拥有这些交易了，该打包不需要 Leader 进行，而是各个 Validator 自己进行即可。

Mempool block 实现

Narwhal 交易池负责打包 Mempool block，在源码中称为 Header，这和 HotStuff 共识层打包区块概念是不同的。之所以要引入 Mempool block 是因为使用 Block 可以更高效的同步交易并打包顺序信息，Mempool block 中包含了本 Validator (worker 节点) 收到的交易 batches（客户端发来的），以及与上一轮 Mempool blocks 的因果关系。Header 结构体定义如下。

pub struct Header { // 即 Mempool block
    pub author: PublicKey,
    pub round: Round,
    pub payload: BTreeMap<Digest, WorkerId>, // 本 Validator 的打包的交易
    pub parents: BTreeSet<Digest>, // 与上一轮 Mempool Blocks 的关系
    pub id: Digest,
    pub signature: Signature,
}

这里需要再次说明的是，Mempool block 与 HotStuff block 不是一个东西，前者只会打包本 Validator 直接从 Client 处收到的交易，因此同一个 Narwhal Round 中不同 Validator 发布的所有 Mempool blocks 构成了当前轮次整个系统收到的客户端交易，同一个轮次中不同 Mempool block 中的交易理论上是不重叠的。源代码中，一个 primary 节点有两个 txs batch 的来源，一个是 tx_our_digests 通道接收从 Client 发送而来的交易，另一个是 tx_others_digests 通道接收其他 Validators 同步而来的交易，前者会最终被 make_header 函数调用用于产生 Mempool block，而后者只是存储下来。

而 HotStuff block 是当前要共识的提案，其中包含了在本轮次中所有 Certificate 中的全部交易累加。

发布 Mempool block

一个 Validator 在某一轮次发起一个新的 Mempool block 需要满足以下任意一个条件：

• 上一轮产生 Quorum 个 Certificates，并且积压的 batch 达到打包标准。
• 上一轮产生 Quorum 个 Certificates，并且达到打包的时间上限。

其实就是在满足上轮产生足够 Certificates 的前提下进行一个 Group Commit 逻辑，凑够交易或超时都会产生新一轮的 Mempool block。源码如下：

async fn make_header(&mut self) {
    // 新建 header.
    let header = Header::new(
        self.name,
        self.round,
        self.digests.drain(..).collect(),
        self.last_parents.drain(..).collect(),
        &mut self.signature_service,
    ).await;

    ...

    // 广播 header
    self.tx_core
        .send(header)
        .await
        .expect("Failed to send header");
}


pub async fn run(&mut self) {
    loop {
        let enough_parents = !self.last_parents.is_empty();
        let enough_digests = self.payload_size >= self.header_size;
        let timer_expired = timer.is_elapsed();
        
        // 当前一个轮次拥有了足够的 parents 时才会创建新的 header
        if (timer_expired || enough_digests) && enough_parents {
            self.make_header().await;
            self.payload_size = 0;
        }

        tokio::select! {
            Some((parents, round)) = self.rx_core.recv() => {
                if round < self.round {
                    continue;
                }

                // 更新轮次
                self.round = round + 1;
                self.last_parents = parents;
            }
            ...
        }
    }
}

产生 Certificate

Validators 收到其他 Validator 广播而来的 Header 后需要进行验证。验证规则如下：

• 必须包含 Creator 合法签名。
• Mempool block 轮次与当前 Validator 所在轮次一致。
• 必须包含前一轮 $2f+1$ 个区块的 Certificate 引用，除非是创世 Mempool block。
• 每个 Validator 在每轮只能认证其他 Validators 发送的第一个区块，多余的区块被视为非法。

完成验证后 Validator 对该 Mempool block 进行投票，一旦获得 $2f+1$，Mempool block 就会成为 Certificate（或者是拥有 Certificate）。因此可以认为 Certificate 就是一批已经排好序并得到认可的交易，至于交易执行后的状态一致性还是需要共识层去实现。

共识层 Proposal Message 的简化

在有了 Narwhal 的加持之后，Proposal Message 中仅包含 round, qc, tc，不需要再包含交易信息，因此 Leader 在构建 Proposal Message 时不需要构造 Block，Block 是 Validator 收到 Proposal Message 后自行构建的。下面代码中 Validator 收到 Proposal Message 之后会调用 make_block 创建区块。

// self.leader 即为 leader 节点发送而来的 Proposal Message
if let Some((round, qc, tc)) = self.leader.take() {
    // Make a new block.
    // leader 的 proposal message 只包括 round, qc, tc, 每个 validator 自己构建 bloc
    self.make_block(round, qc, tc).await;

    ...
}

async fn make_block(&mut self, round: Round, qc: QC, tc: Option<TC>) {
    let block = Block::new(
        qc,
        tc,
        self.name,
        round,
        // buffer 中获取 mempool 已有的 Certificates，从中获取交易
        self.buffer.drain(..).collect(), 
        self.signature_service.clone(),
    )
    ...
}

总结

Narwhal 是一个交易池协议，它解决了 BFT 共识中由于交易同步和交易顺序协商造成的性能瓶颈。从而大幅度提升了系统吞吐量。

• Narwhal 通过 Mempool block 构成 DAG 实现了交易顺序的并行协商，相当于实现了多条链的并行共识并保证了一致性。
• 共识的提案消息基本不占用带宽，交易内容与顺序本地已经准备就绪，并保证一致和可靠。
• Validator 拆分为 primary 和 workers 节点，交易内容的同步性能大幅提升，其中 worker 负责交易内容的同步，primary 负责构建 DAG。

推荐阅读

• DAG结构下的区块链性能提升[上海交通大学]-哔哩哔哩
• BFT on a DAG
• DAG Meets BFT - The Next Generation of BFT Consensus
• Narwhal and Tusk 论文
• 内存池协议Narwhal和共识协议Tusk-哔哩哔哩
• Narwhal and Tusk 源代码