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秒的延迟。
交易生命周期:
-
来自Client的交易首先被提交到Narwhal Mempool中
-
Narwhal Mempool接收来自Client的交易并生成DAG
-
基于这个DAG,Tusk和Bullshark分别规定了区块顺序提交的规则
-
当交易顺序被确定并在各个validator节点间达成共识后,可以提交到state machine中进行执行
二、Narwhal与DAG回顾
-
在第r轮时,每个validator收集来自Client的交易并打包成区块
-
在生成第r轮区块时需要满足两个条件
-
该集合需要包含 r-1 轮中至少2f+1个证书
-
经过2f+1的验证
-
已经被验证的区块的证书,共享给下一轮节点用于创建新的区块
三、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接收到一个顶点时会首先查看是否合法:
-
检查source与round是广播的vertix中记录的(合法的)
-
这个顶点需要有至少2f+1个strong edges
-
检查这个vertix是否能够加入到DAG中(try_add_to_dag)
-
要求只有当被该节点引用的节点都被记录时,该节点才能被加入DAG中
-
一旦当前round已经交付了超过2f+1个节点,可以立即进入下一个round
-
如果是每个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的分离,用于提升效率。
关于我们
Hacker Dōjo是由Hacker共建的加密、Web3前沿技术开源知识社区。Dōjo会以直播/音频/文字等形式定期组织分享session,内容包括Web3领域前沿技术论文解读、技术研讨、工作坊等。欢迎在Hacker Dōjo社区讨论、学习和交流。加入Dōjo的Hacker可以提出自己的学习期望,主动提案自己擅长的技术话题,由Dōjo组织分享。同时,Hacker Dōjo推出Web3前沿课题研究计划,定期选题,由hacker进行研究和讲解,并以bounty形式奖励研究贡献者。
合作事项
认领Bounty:DoraHacks
转载文章:请保留Hacker Dōjo Workshop介绍并联系我们hackerdojo0@gmail.com。