共识协议Bullshark学习

Dora Dōjo
1

Hacker Dōjo Workshop：
研究种类：Bullshark
资助金额：200 usdt
Bounty链接：Hacker Dōjo|课题研究：共识协议Bullshark | Bounties | DoraHacks
创作者：0x7ac61a
赏金发布：0xe72861196db120997a3c8b931ed78dbcb0caa9d4994e3a8571c2001fe89a19fb
本项目由Hacker Dōjo资助，文章转载请联系
Telegram: @HackerDojo0
WeChat: @HackerDojo0
E-mail: hackerdojo0@gmail.com

一、Overview

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

交易生命周期：

image
image1244×534 17.6 KB

  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. 已经被验证的区块的证书，共享给下一轮节点用于创建新的区块

    image
    image1096×762 60.3 KB

三、Bullshark共识

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

DAG构建

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

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

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

    image
    image1128×880 66.2 KB

接受到一个顶点

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

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

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

image
image1356×982 244 KB

  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

image
image1268×642 101 KB

  • 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节点能成功提交：

image
image1228×640 82 KB

提交流程的伪代码，在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节点。

image
image1064×1268 244 KB

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

Commit Leader

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

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

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

image
image1012×244 40.9 KB

Partially synchronous Commit

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

image
image1434×586 101 KB

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

image
image1338×628 128 KB

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

image
image1486×646 162 KB

每一轮合法的选票数量：

image
image1542×312 77.8 KB

当前可以提交的leader

image
image1450×1036 210 KB

四、改进

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

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

image
image1456×540 108 KB

五、测试与性能

benchmark测试，在narwhal/benchmark中：

image
image1172×1174 97.9 KB

测试：

image
image1158×848 92.8 KB

六、总结

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

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

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

关于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

2 Likes
2

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