Narwhal and Tusk共识协议笔记

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
本项目由Hacker Dōjo资助,文章转载请联系
Telegram: @HackerDojo0
WeChat: @HackerDojo0
E-mail: hackerdojo0@gmail.com


一、Overwiew

整体流程:

  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组成。

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

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

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

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

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中的每个顶点,每条消息都包含一组事务以及一组对先前消息的引用。

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

Narwhal Mempool

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

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

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

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

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

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

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

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

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

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

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

Certificate Block结构:

三、异步共识机制

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

背景研究

HotStuff

HotStuff的三阶段提交:

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的安全性验证。

第一段:对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瓶颈仍然存在:

### DAGRider

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

顶点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。

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

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轮可以提交一个块

四、优势

五、总结

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

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


关于我们
:small_orange_diamond:Hacker Dōjo是由Hacker共建的加密、Web3前沿技术开源知识社区。Dōjo会以直播/音频/文字等形式定期组织分享session,内容包括Web3领域前沿技术论文解读、技术研讨、工作坊等。欢迎在Hacker Dōjo社区讨论、学习和交流。加入Dōjo的Hacker可以提出自己的学习期望,主动提案自己擅长的技术话题,由Dōjo组织分享。同时,Hacker Dōjo推出Web3前沿课题研究计划,定期选题,由hacker进行研究和讲解,并以bounty形式奖励研究贡献者。
合作事项
:small_orange_diamond:认领Bounty:DoraHacks
:small_orange_diamond:转载文章:请保留Hacker Dōjo Workshop介绍并联系我们。

1 Like

I think these are nice diagrams!

1 Like

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

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

1 Like

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

1 Like