共识协议Bullshark学习

Hacker Dōjo Workshop:
研究种类:Bullshark
资助金额:200 usdt
Bounty链接:https://dorahacks.io/zh/daobounty/81
创作者:0x7ac61a
本项目由Hacker Dōjo资助,文章转载请联系
Telegram: @HackerDojo0
WeChat: @HackerDojo0
E-mail: hackerdojo0@gmail.com


一、Overview

Bullshark提出了一个十分简单且高效的协议,能够在50个诚实方的情况下实现了125k TPS和2秒的延迟。

交易生命周期:

  1. 来自Client的交易首先被提交到Narwhal Mempool中

  2. Narwhal Mempool接收来自Client的交易并生成DAG

  3. 基于这个DAG,Tusk和Bullshark分别规定了区块顺序提交的规则

  4. 当交易顺序被确定并在各个validator节点间达成共识后,可以提交到state machine中进行执行

二、Narwhal与DAG回顾

  1. 在第r轮时,每个validator收集来自Client的交易并打包成区块

  2. 在生成第r轮区块时需要满足两个条件

  3. 该集合需要包含 r-1 轮中至少2f+1个证书

  4. 经过2f+1的验证

  5. 已经被验证的区块的证书,共享给下一轮节点用于创建新的区块

三、Bullshark共识

考虑一个P2P的消息传输场景中存在n=3f+1个节点,其中可以动态的存在f个恶意节点。

DAG构建

和DAGRider类似,在Bullshark中,两个DAG节点间的连接分为weak edge和strong edge。

  • Strong edge:在每一轮至少包含与上一轮相连的2f+1个强边

  • Weak edge:一个顶点至多包含f个与round<r-1相连的弱边

接受到一个顶点

当DAG接收到一个顶点时会首先查看是否合法:

  1. 检查source与round是广播的vertix中记录的(合法的)

  2. 这个顶点需要有至少2f+1个strong edges

  1. 检查这个vertix是否能够加入到DAG中(try_add_to_dag)

  2. 要求只有当被该节点引用的节点都被记录时,该节点才能被加入DAG中

  3. 一旦当前round已经交付了超过2f+1个节点,可以立即进入下一个round

  4. 如果是每个wave的第一或第三轮是存在leader节点的,尝试获取当前的steady leader,同时在第二或第四轮中是没有leader产生的。

Wave与Leader的选择

在完成DAG构建后需要规定wave与每一个wave中可能被提交的leader。

在Bullshark中存在两种leader:

  • steady-state leader

  • fallback leader

在一个wave中存在三个leader,SA1与SB1为steady-state leader,F1为fallback leader

  • round2:P1发现2f+1个节点都投票给了S1A,P1可以提交S1A

  • round4:P1发现只有一票投给了S1B,P1不能提交S1B,且P1在wave2中的投票类型变成了fallback类型

  • round5:P1在round5也收到了round4中其他2f+1个节点,发现他们也都没提交S1B,所以P1能够确定其他节点在round5也是fallback vote。同时S2A和S2B都失去了提交机会

  • round8:P1发现有2f+1票投给了F2,在提交F2之前尝试去提交S1B,但是由于S1B不满足提交规则,所以P1提交F2

在每一个wave中各个验证着所提交的leader为同一类型。因为当v1成为

当2f+1节点成为steady节点,最多有f个节点为fallback,因此没有fallback节点能成功提交:

提交流程的伪代码,在try_ordering函数中,对于处于wave中的第一轮来说,存在两个可能的leader,需要判断当前提交的是fallback leader还是steady leader。

round%4==1时,尝试提交上一轮的steayd/fallback leader,并确认自己在本轮的状态。

在上一轮中如果存在2f+1个节点处于fallback状态并且这2f+1个节点都与当前节点存在强边,或上一轮中存在2f+1个节点在均处于steady状态并与当前待提交节点存在2f+1个强边,则在本轮验证者节点处于steady状态,否则本轮验证者节点需要处于fallback状态(也就是前一轮存在失败的提交)。

在每一个wave的round1时,决定的是上一个wave第二个steady节点的提交,或是上一个wave中round1 fallback节点的提交。

round%4==3时,仅需要提交第一轮的steady节点。

注意:这里使用2f+1作为vote的数量,区别于Tusk,是因为Bullshark不光要确定该leader是可以提交的,同时还要确定大多数(>=2f+1)个节点都在下一个wave中处于同一种提交状态。

Commit Leader

在提交时,我们已经能够确定在当前回合,至少2f+1个节点和我们处在同一种投票类型下。

commit的作用是在已经确定能够提交当前节点的状况下,向前递归地提交上一轮暂时未能提交的节点。

当上一轮leader已经能够被其他节点提交时,它满足的条件是至少有2f+1个vote,且至少2f+1个节点处在同一种情况,所以对于当前验证着来说,它的局部视角至少存在f+1个vote。

Partially synchronous Commit

Bullshark对共识协议进行了简化,更易于代码实现,是目前在Sui共识机制中实现的版本。(200行代码)

在提交一个节点的同时对应的去找过去的节点是否能够提交,没有任何vote的节点可以直接略过:

当存在能够回溯到的leader节点时,将其加入到leader中进行提交,对应实现的源码位置:narwhal/consensus/src/bullshark.rs#L148->narwhal/consensus/src/utils.rs#L11

每一轮合法的选票数量:

当前可以提交的leader

四、改进

在文章[1]中作者描述了一个对Bullshark的改进。

作者引入了逻辑DAG的概念,将各个与Leader节点相连的节点构成逻辑时间,在逻辑DAG中计算提交,可以加快提交Leader达成共识的效率。

五、测试与性能

benchmark测试,在narwhal/benchmark中:

测试:

六、总结

Bullshark是基于Narwhal Mempool的共识协议,相比于Hotstuff能够具有更高的吞吐量,并在Tusk的基础上进行改进,降低了出块轮次的延迟,同时实现起来更为简单。

Bullshark中定义了两种提交模式,steady和fallback模式,在steady模式下因为leader节点缓慢或其他原因,会使验证着节点进入fallback投票模式。

Bullshark还有一些进一步地理论上的改进,例如逻辑DAG与物理DAG的分离,用于提升效率。


关于我们
: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介绍并联系我们hackerdojo0@gmail.com。

3 Likes

I think it’s a very interesting topic!!! Thanks for your presentation!