Narwhal and Tusk共识协议笔记

Dora Dōjo
1

Hacker Dōjo Workshop：
研究种类：Narwhal , A DAG-based Mempool and Tusk , Efficient BFT Consensus
资助金额：200 usdt
Bounty链接：Hacker Dōjo|课题研究：内存池协议Narwhal和共识协议Tusk | Bounties | DoraHacks
创作者：0x7ac61a
赏金发布：https://bscscan.com/tx/0x1b133de459fad690c3106aad19229d4b78a2f35f15d4c372499fd035315cdc3c
本项目由Hacker Dōjo资助，文章转载请联系
Telegram: @HackerDojo0
WeChat: @HackerDojo0
E-mail: hackerdojo0@gmail.com

一、Overwiew

image
image1530×574 57.8 KB

整体流程：

  1. Client提交transaction到Narwhal Mempool。（Narwhal Mempool由一组worker和一个primary组成）

  2. Mempool接收到的Transaction->以Certificate的形式进行广播

  3. 由worker将交易打包为Batch，worker将Batch的hash发送给primary

  4. primary上运行了mempool协议，primary接收来自worker的hash

  5. 生成certificate并广播/收集来自其他节点的certificate

  6. Mempool把收到Certificate组织为以Round为“时间粒度”的DAG，交给Tusk/Hotstuff的异步共识机制，并按照各自的共识规则选出Round中哪些区块是可以提交的。（注：这里不一定是每一个round都有区块提交）

  7. 基于Leader的共识协议：HotStuff

  8. 基于DAG的异步共识协议：DAGRider、Tusk

  9. 按照区块提交的顺序将排序后的交易传入StateMachine，把交易产生的改变在状态机中提交。

二、Narwhal

Overview

Narwhal Mempool由一组worker和一个primary组成。

image
image1536×680 58.6 KB

根据负载均衡机制，每个worker接收部分从Client发来的transaction并生成Batch。每个worker对生成的Batch求hash，并将结果提交给Primary。

对于不同validator节点上的worker，worker1生成的Batch会仅把消息发送给其他validator节点上的worker1，同理worker2生成的Batch会仅把消息发送给其他validator节点上的worker2。

引入worker机制，使得validator可以支持线性的扩展。

image
image1412×758 42.7 KB

Primary上运行了mempool协议，因为worker仅提交了32bytes的哈希给Primary，因此mempool协议是十分轻量级的。Primary Blocks 结构：

image
image1578×370 19.1 KB

Summary

This text will be hidden

这里i可以理解为Instance，每个validator每一轮产生的一个实例，在论文附录的证明中提到

背景研究

BFT共识在区块链的背景下，包含n个验证着，其中f个可能为恶意的验证者。这些验证者需要对一个无限增长的交易序列达成共识。

经典的基于BFT的共识算法（例如PBFT），需要一个Leader节点收集交易生成区块，广播并接收来自大家的投票，经过三个阶段的交互后（Pre-prepare、prepare、commit）最终对区块提交达成一致性共识。

基于DAG的BFT共识（例如HashGraph和Aleph）的想法是将网络通信层与共识逻辑分开。每个消息都包含一组交易以及一组对之前消息的引用，所有的消息一起形成一个不断增长的DAG。

这种网络通信与共识逻辑分离的协议带来的好处是，可以在每个节点异步地计算状态与提交区块，降低延迟与减少通信过程中的网络开销。

Hashgraph

在Hashgraph中，消息是DAG中的每个顶点，每条消息都包含一组事务以及一组对先前消息的引用。

image
image940×674 77.2 KB

因为在Hashgraph中消息包含了对先前消息的引用，这能够保证任何提交了Carol最上方顶点的验证者，在内存中都对Hashgraph中该顶点的历史消息有相同的记录。因此每个验证者可以独立它本地的DAG 视图，并在不需要发送额外消息的情况下对所有顶点进行排序。

Narwhal Mempool

前文提到worker会提交Batch的digest到Primary，收到digest的Primary需要引用前一轮的区块来生成新的区块。从创世区块开始一个Primary需要援引至少2f+1个前一轮的区块才能生成一个新的块。

生成的header被发送到其他所有节点，接收到block header的验证者验证区块并进行vote，当收集到超过2f+1数量的vote时可以生成证书并广播。

image
image1132×646 47.2 KB

每一轮的区块不会直接与上一轮的区块相连，而是引用了上一轮的certificate。从生成block header到广播certificate这个过程，构成了一个Round。

image
image1104×612 65.7 KB

重复上述的流程，round会继续向后延伸，于是我们就得到了一部分的DAG。

image
image1192×794 64 KB

validator判断一个区块是否合法并且投票给它的规则有四条：

  1. 区块包含来自creator的合法签名

  2. 是当前validator所在轮次r的区块

可以避免一个攻击者恶意出块并使自己总能保持在最长链的情况，即使这会导致一些落后的区块被validator抛弃

  1. 创世区块或者包含前轮2f+1个区块的certificate引用

  2. 每个validator在每轮只能认证其他validator发送的第一个区块

同时也是每个轮每一个validator都可以产生块并获取来自其他2f+1节点的认同

image
image1102×776 72 KB

Certificate Block结构：

image
image1540×276 12.3 KB

三、异步共识机制

从消息的产生到消息的最终提交，由于网络的异步特性，不同的验证者可能在某一时间点看到部分不相同的 DAG，关键的问题为如何保证所有验证者就相同提交顺序达成一致。

背景研究

HotStuff

HotStuff的三阶段提交：

image
image1620×684 120 KB

New-View->Prepare

每个View开始时，新的Leader收集由(n−f)个副本节点发送的New-View消息，每个New-View消息中包含了发送节点上高度最高的prepareQC(没有则设为空)。

prepareQC可以看做是对于某个区块(n−f)个节点的投票集合，共识过程中第一轮投票达成的证据

Leader从收到的New-View消息中，选取高度最高的preparedQC作为highQC，认为不会有高度高于highQC的区块得到确认，认为是一个安全分支。

Leader节点会在highQC所在的安全分支来创建一个新的区块，并广播proposal，proposal中包含了新的区块和highQC，其中highQC作为proposal的安全性验证。

image
image1520×612 69.8 KB

第一段：对Prepare进行投票

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

Leader发出Proposal消息后等待(n−f)个节点对于该Proposal的签名，集齐签名后会将这些签名组合成一个新的签名，以生成prepare-QC保存在本地，然后将其放入PRECOMMIT消息中广播给Replica节点。

第二段：对Precommit投票

当Replica收到Precommit消息时，会对其签名，然后回复给Leader。

Leader收集(n-f)个Precommit-vote，然后将其组合为Precommit-QC,并将其放在COMMIT消息中广播。

第三段：对Commit投票

当Replica收到COMMIT消息时，会对其签名Commit-vote，然后回复给Leader。

此时Replica锁定在precommitQC上，将本地的lockQC更新成收到的precommitQC.

从Replica发出precommit-vote到Leader集齐消息并发出commit消息，这个过程相当于pbft、tendermint中的第二轮投票。

Replica收到了commit消息，验证成功后，表示第二轮投票达成。此时Replica回复给Leader，并且保存precommitQC到lockedQC.

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

在HotStuff的场景中，Leader瓶颈仍然存在：

image
image1550×638 78.2 KB

### DAGRider

在DAGRider中的连接分为Strong Edge与Weak Edge：

image
image1472×528 88.6 KB

顶点v2和v3分别是由choos_leader(w)选出的wave2与wave3轮的leader。但由于r8中具有通往v2顶点的strong edge少于2f+1，因此在round8时v2不满足提交条件。然而由于round12中有2𝑓+1个顶点有通往v3的strong edge，因此v3符合提交规则。同时由于存在一条从v3到v2的strong edge，所以在wave3中先提交v2->v3。

image
image1520×616 119 KB

Tusk

Tusk的设计思想基于DAGRider进行了改进。在Tusk中每个wave包括3轮：

  1. 在round1，生成区块并广播他们

  2. 在round2，validator对区块进行vote（也就是引用他们）

  3. 在round3会选出一个random coin（也就是选择round1的出块leader）

  4. 选出round1中待提交的区块b，如果说round2中有f+1个区块引用了该区块，那么提交它

  5. 然后validator将b的历史因果顺序排序，直到遇到garbage collect过的轮次

由于validator可能获得不同的DAG局部视图，有些节点可能在本轮提交这个区块，另一些节点可能暂时不会

为了保证所有诚实的验证者最终提交相同顺序的Leader区块，当确认了某一个wave 𝑤中的candidate 𝑣时，需要递归直到上一个Leader提交节点的wave 𝑤′。对于在𝑤′和𝑤之间的每一个wave 𝑖，𝑣检查在candidate和wave 𝑖的Leader区块𝑏之间是否有一条路径。如果存在这样的路径，就在当前candidate之前提交𝑏，将candidate设为𝑏并继续递归。

例如在下图中，当round1中的Leader选出之后，L1并不能立即提交，因为在round2中没有对L1超过f+1个引用，当选举出L2时，L2被round4超过f+1个区块引用，L2存在一条路径通往L1，因此在L2会提交L1与L2

image
image1138×712 121 KB

DAG中的每一轮至少包2f+1个区块，每一个提交区块至少被下一轮f+1个块引用，我们可以得到一些结论：

  1. 如果一个诚实的validator在一个wave 𝑖中提交了一个Leader块𝑏，那么在未来的wave中，任何一个诚实的validator 𝑣所提交的Leader块𝑏′在𝑣的本地DAG中有一条通往𝑏的路径。

  2. 任何两个诚实的validator提交相同的Leader块序列

  3. 对于每一个wave 𝑤，在第一轮中至少有f+1个区块满足提交规则。

  4. 在意外情况下，Tusk最多7轮可以提交一个块

  5. 在随机的网络延迟下Tusk最多4.5轮可以提交一个块

四、优势

image
image1496×738 184 KB

五、总结

Narwhal与Tusk协议将交易传播的任务与对交易的排序分开，进而实现高性能的基于法定人数的BFT容错共识。Narwhal是一个mempool协议，用于高效的传播交易与将交易历史和因果进行存储，Narwal中每个validator还可以通过扩展worker实现性能扩展。

Tusk协议的理论起点是DAG-Rider，Tusk是基于DAG-Rider的改进版本，在一些常见的情况下降低延迟。Tusk中每个节点维护自己的DAG，但是使用一个共享的rand coin决定整体的交易提交顺序。

image
image1440×290 12 KB

关于Dorahacks
DoraHacks 是一个全球范围内的极客运动、全球黑客马拉松组织者，也是全球最活跃的多链 Web3 开发者平台之一。DoraHacks.io平台使得世界各地的Hacker和开源开发者可以参与黑客马拉松、Bounty、Grant、Grant DAO，以及公共物品质押等加密原生协议和基础设施进行协作并获得资助。到目前为止，DoraHacks 社区的 4000 多个项目已经获得了来自全球行业支持者超过 3000 万美元的资助。大量开源社区、DAO 和 超过50个主要区块链生态系统正在积极使用 Dora 的基础设施（DoraHacks.io）进行开源融资和社区治理。

关于Dorahacks DAO Bounty
Dorahacks DAO Bounty，为各类DAO和组织赋能！
Bounty计划为DAO和组织提供了一个强大的平台，通过社区激励的形式，发布问题，协调任务，鼓励用户积极参与。
作为Bounty发布者，您可以根据我们的指南，发布社区相关的悬赏任务，解决问题的同时，提升社区活跃度：How to publish a bounty and easily fund bounty hunters
作为赏金猎人，您可以在DAO Bounty计划中发挥自己的专长和能力，认领悬赏，解决问题，获得酬金：DAO Bounties | DoraHacks

关于Hacker Dōjō
Hacker Dōjō是由Hacker共建的加密、Web3前沿技术开源知识社区。Dōjō会以直播/音频/文字等形式定期组织分享session，内容包括Web3领域前沿技术论文解读、技术研讨、工作坊、技术领袖研讨会等。欢迎在Hacker Dōjo社区讨论、学习和交流：Dora Dōjo - Dora Community Forum

目前Hacker Dōjō已分享的主题有：

  • 密码学：基础专题（对称加密算法、哈希函数、群和公钥加密、数字签名和KZG承诺、零知识证明、非对称密码算法、分布式密码学）
  • 密码学：算法代码专题（Halo、Halo2、Plonk、Groth16、分布式密钥生成）
  • 密码学：抗量子计算破解算法专题
  • Layer1架构：Move系列、模块化公链、共识协议Bullshark、内存池协议Narwhal和共识协议Tusk、Aptos共识与交易并行执行
  • Layer2架构：zkSync研究、Layer2的支付通道扩容方法、Polygon Hermez、Optimism、StarkWare技术与生态梳理
  • IRS系列：Interest Rate Swap and DeFi Platforms、Interest Rate Swap and Perpetual Swap、The Future Dencentralized Interest Rate Swap
  • 量子计算系列：量子计算基础、Qiskit专题（Qiskit入门、Deutsch-Jozsa算法、Bernstein-Vazirani算法、Simon算法、量子卷积神经网络、量子傅里叶变换、量子相位）、Pennylane专题（利用变分量子电路拟合傅里叶级数）、实验法观测宏观量子叠加态
  • AIGC系列：ChatGPT比较语料评测、GPT-4论文解读

加入Dōjō的Hacker可以提出自己的学习期望，主动提案自己擅长的技术话题，由Dōjō组织分享。同时，Hacker Dōjō推出Web3前沿课题研究计划，定期选题，由Hacker进行研究和讲解，并以bounty形式奖励研究贡献者。欢迎各位Hacker认领Bounty：DAO Bounties | DoraHacks

联系我们：

Telegram: @DoraDojo0

WeChat: @HackerDojo0

E-mail: hackerdojo0@gmail.com

1 Like
2

I think these are nice diagrams!

1 Like
3

Reference：

  1. Narwhal and Tusk paper：[2105.11827] Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus
  2. Hotstuff paper：[1803.05069] HotStuff: BFT Consensus in the Lens of Blockchain
  3. Source code：GitHub - facebookresearch/narwhal: Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus.
  4. Narwhal, Bullshark, and Tusk, Sui's Consensus Engine | Sui Docs
1 Like
4

请教一下，Narwhal&Tusk的DAG是如何实现全序关系的

1 Like
5

每个节点都有自己的DAG子视图，节点产生round r轮block的时候需要收集其他节点r-1轮的block并加入到r轮block的引用，从而保证顺序关系。

1 Like
6

image

请问一下，确认提交的同一轮多个block顺序是怎么确认的？