什么是 AleoBFT?
BFT (Byzantine Fault Tolerance，拜占庭容错) 是一种在分布式系统中处理节点故障和恶意攻击的共识算法。它的目标是在节点故障和恶意攻击的情况下保证系统的安全性和可用性。BFT共识算法的基本思想是，通过选择一组节点来共同维护系统状态，并使用复杂的协议来保证节点之间的信息一致性和正确性，在节点之间达成共识之前，要求所有节点都对当前状态达成一致，从而保证系统的正确性和安全性。
但是，什么是AleoBFT呢？现在Aleo即将进入Testnet3 phase3，而phase3的主要目标就是启动PoS也就是测试Aleo的共识算法AleoBFT。在snarkOS仓库我们能看到一个新分支enter_bullshark，这个就是目前在开发中的AleoBFT。
分支名bullshark暴露了AleoBFT实际上就是基于sui的Narwhal&bullshark的共识算法实现的。
Narwhal & Bullshark
Narwhal 和 Bullshark 分别来自于两篇paper:
1. Narwhal & Tusk (EuroSys 2022 **Best paper award**) [G. Danezis, E. Kokoris-Kogias, A. Sonnino, A. Spiegelman]
2. Bullshark (To appear at CCS 2022) [A. Spiegelman, N. Giridharan, A. Sonnino, E. Kokoris-Kogias]
Narwhal & Tusk这篇paper启发式地将传统拜占庭容错的共识算法中事务传播和事物排序的处理分离开来，不仅使得validator能够线性扩展，以提高整个网络的吞吐量并降低延迟，还能提高可扩展性，将共识协议抽离产生Narwhal搭配其他共识算法的效果，比如论文中提到的Narwhal-Hotstuff。
Narwhal是一个DAG内存池抽象，它将整个validator网络抽象成一个DAG内存池（mempool），对于使用者屏蔽了所有关于节点传播和通信的实现细节，根据transaction client发送的请求生成DAG中Vertix或者说 a batch of transaction。
Tusk是Narwhal组件内部的一个共识协议，在Sui的实现中，要是没有指定外部的共识协议，那么就会启动internal consensus(Tusk/Bullshark).在当Narwhal生成了Vertix几轮之后，会通过Random Shared Coin（神奇的分布式密码学）为几个primary随机地选出一个leader，并且commit该轮次（round）该leader的Vertix。
Bullshark是Tusk的改进版，主要是改进了Tusk的公平性，在同步网络模型（synchronous model）情况下，能够确保所有诚实节点的transactions都能被打包进链上，并且降低了latency。在后文中的提到的共识协议都是指代的是Bullshark。
AleoBFT中的 DAG 是什么？
AleoBFT或者说Narwhal & Bullshark是一个基于DAG的共识算法，但是什么是DAG？DAG又在共识中起了什么作用？
首先DAG是有向无环图的缩写，在Narwhal中，每个Validator每轮都会尝试生成Vertix，每个Vertix都会和上一轮的Vertix相连。具体的执行过程如下：
1. 更新到当前Round
2. 每个Validator根据收到的transactions生成Block
3. 广播Block并且收集其他Validator的签名
4. 根据签名个数（num > 2f +1）生成Certificate并且通过BlockDigest引用自己生成的Block
5. 当前Round如果收集到大于2f+1个Certificate，强制进入下一个Round
这里（Block，Certificate）的二元组实际上就是一个DAG中的Vertix。如此循环往复，整个网络最终生成了一个有向无环图(DAG)。这样只要你拿到一个网络中的Vertix，你就可以通过边（Edge）去找到上一轮中的Parents Vertix，Parents Vertix又可以找到它的Parents Vertix。所以当整个网络对一个Vertix达成共识的时候，实际上是对于这个Vertix的所有因果关系都达成了共识，最终网络达到了一致性。
那么共识算法是怎么提交一个DAG中的Vertix以及它的因果关系的呢？
在Bullshark里，在偶数轮会通过神奇的分布式密码学，你可以认为用一个公平的全局硬币，选择出一个Leader，并把该轮次的该Leader的块当作锚点(待Commit的Vertix)，图中所有绿色标注的都是锚点。当一个Validtor成为Leader并锚定当前点（Vertix），它回去回溯去fetch所有与这个点（Vertix）有因果关系的未提交的点（当然在真正的实现中并不是所有），打包成一个子DAG。然后在下一轮也就是奇数轮中，对其进行投票，投票的规则就是如果这轮和上一轮的锚点有连边（Edge），那么即认为对其投票。票数超过f+1，则该锚点被提交。在下图中，锚点A1有一票，小于f+1所以在round1并没有被提交。到了round3，锚点A2有了三票，大于f+1，并且因为A1是在A2的因果关系中，所以A1，A2都会被提交。
当然这里为了简单地描述过程，许多细节并没有提到。比如GC（garbage collector）以及Weak Link的概念，这些东西的引入同样是降低了网络的延迟以及提升公平性。
代码解析
回到AleoBFT中最新的代码，因为sui已经对共识模块很好地做了抽象解耦，Aleo可以不需要太多的修改直接使用。在这里我们不考虑Narwhal里的具体细节，而是把它当作一个固定时间产生达成共识数据的黑盒。
Advance_to_next_block的整个流程如下：
1. Client发送交易给Validator的Worker节点；
2. Worker 聚合交易后将这笔聚合交易的 Digest发送给Validator；
3. Validator拿到Batch Digest在新一轮生成区块。
4. 把区块发送给其他Validators，最后得到一个2f+1个签名的 Certificate。
5. 如果此Validator 成为Leader, Validator调用process_certificate生成 CommittedSubDag array。
6. 根据CommitedSubDag，从内存池fetch_payload组成ConsensusOutput。
7. 根据外部实现的Executor Trait，来对Consensus Output进行处理，Aleo就是在这个地方嵌入状态机更新的逻辑的，ledger advance to next block。
8. 该Validator广播新区块，其他Validator检查后将新区块添加到Ledger中。
未来展望
目前AleoBFT的开发正在如火如荼地开发中，因为使用的是成熟的方案，所以应该不久之后就能加入到测试网中进行测试，在代码中也能发现大量官方团队测试的痕迹，例如许多测试代码以及测试的本地配置文件。但是也有许多必须解决的问题还没有看到代码，例如
1. 处理Client发送的交易的代码尚未完成；
2. 现在出块的逻辑都放在Validator上，对于Beacon节点后续怎么处理；
3. 将现有的代币融入到Narwhal的质押中；
4. 大量的稳定测试。
总的来说，共识模块的完成度距离真正的Phase 3已经不太遥远了。快的话（官方团队设计充分），1～2个星期应该就能在测试网看到共识启用，慢的话在1个月左右。
在最新的Sui官方推文中，我们可以知道Sui的共识算法能够惊人地达到300k的TPS以及480m的延迟。这让我们越发期待不仅同样使用了Narwhal & Bullshark算法以及ZK的Aleo，能够带来什么样的期待。要知道作为第一条真正意义上实现完全隐私的公链，Aleo的上线所能带来的宏伟叙事或许远超我们的想象。
