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。