共识协议Bullshark学习

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秒的延迟。

交易生命周期:

  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的分离,用于提升效率。


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

3 Likes

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