Bystack的高TPS共识算法

共识算法是分布式系统保证节点数据状态一致性的方法，在区块链的共识算法分POW(工作量证明)和POS(权益证明)两大类。第一类POW模式是在公链项目中运用的最广泛应用的共识算法，比特币长达10年的运行已充分证明POW的安全性与稳定性。POW的特性是将去中心化与安全性发挥到了极致,但却牺牲了性能。 如比特币的峰值TPS为3.87， 平均每笔交易被打包入块需要10分钟;比原链的峰值TPS为36.32，平均每笔交易被打包入块需要2.5分钟。第二类的POS模式是由通过算法来选择出块共识节点，多用于联盟链和一些追求高TPS的新公链项目中。POS的特性是通过支持更小的出块间隔来达到最优的性能，但却牺牲了部分的安全性与去中心化。

Bystack是一个基于主侧链架构的区块链BaaS平台，将区块链分为Layer1和Layer2两层。

Layer1既比原链的主链，由POW算法保证最高级别的资产安全与去中心化。Layer1的TPS问题则通过跨链技术将资产转移到Layer2上来解决.

侧链（既Layer2）使用创新的BBFT共识算法使单条侧链的TPS达到20000以上，多条侧链配合可使TPS线性增长。

在未达到节点带宽与性能瓶颈的前提下，TPS = 区块交易数 *每秒确认的区块数。由于区块可以容纳的最大交易数可以通过简单的修改代码参数实现，所以提高每秒确认的区块数就成了提高TPS的关键方式。如比原链的每个区块最大可容纳5500笔左右的交易，在主链上因为平均每150秒出一个块的POW特性所以TPS是36.32.但上在侧链如将每秒进入最终确认的区块数提高到5个则可轻易的将TPS达到25000以上。

DPOS的问题

传统的DPOS共识算法如EOS已经完全可以做到支持每秒2个区块的出块速度，但却有一个等待最终确认的问题。
因为一个传统的DPOS区块获得最终确认的依据是所有超级节点都在此块之后出过至少一个子块。这意味着假设有21个超级节点，每个节点每轮出6个块，平均每个出块时间为0.5秒。那么一个区块获得最终确认的时间需要60秒。

BFT的问题

基于BFT的POS因为BFT的特性所有每个块在产出之后可以得到快速的最终确认，但是却难以获得较高的TPS.
原因是BFT每个区块分为三个状态，产生，预最终状态与最终确认状态。
状态的改变是依靠收集到2/3节点的签名，而签名产生的效率依赖网络的延迟。假设部分超级节点在美国，部分在中国那么通信的延迟大约为200毫秒。
那一个区块从产生到最终确认至少需要600毫秒的限制。所以在BFT的共识算法中网络延迟成为了高TPS的瓶颈。

DPOS BBFT共识算法

Bystack的共识算法是基于DPOS和BBFT算法特性的全新混合共识算法,
通过将出块与BBFT签名异步进行的模式使得算法同时具有高TPS与快速最终确认的特性。在BBFT共识算法由全网用户投票选出n个共识节点进行出块。共识节轮流成为出块节点，当成为出块节点的共识节点将会以s秒一个块的速度连续出m个区块。当区块产生之后将直接广播至全网，
但出块节点不会等待获取2/3的其他共识节点签名而是继续在当前块的基础上出下一个块。此时当前区块已是合法区块但是未获得最终确认，类似于比特币未获得6个块确认存在回滚的可能性。当其他共识节点收到区块并且验证通过之后将会对区块进行签名并广播到全网，当一个区块获得超过2/3的签名时就进入了最终确认状态。

TPS

实现高TPS的核心点是每个共识节点连续出m个区块。因为当每个节点只出一个块的话那么下一个共识节点出块需要等待上一个共识节点出的块，这里就需要考虑一个网络延迟带来的问题。如果把出块间隔设置小于网络延迟的，那会有大概率共识节点在出块时未收到上一个块造成分叉的状态。但当m设为一个稍大的数则可以将tps提升到带宽与节点性能的极限。
假设当m=20,
当下一个共识节点出块时因为网络延迟未收到最后1个块但却收到了之前的19个块，节点会接在上一轮第19个块之后出块。区块链会进入瞬间的分叉状态但会根据最长链原则在2个块之后全网状态统一。虽然损失了1个区块的TPS,
但任保证了出块间隔小于网络延迟情况下的高出块率。

异步BFT

在BBFT的设计中出块与与共识节点的BFT签名是并行进行来抵消因网络延迟收集BFT签名对出块效率的影响。但不同于经典BFT算法中有产生，预最终状态与最终确认三个状态，
BBFT根据区块链的特性改造使算法只有一个最终确认状态。
但添加了两个额外的限制条件：第一个是当一个共识节点对相同高度的两个不同区块进行签名既发生欺诈；第二个是当一个共识节点对相同时间的两个不同区块进行签名既发生欺诈。通过这种方式的改造减少了共识节点之间的通信次数，从而降低了区块获得最终确认所花费的时间。同时BBFT还有区块获得直接确认与间接确认两种。第一种直接确认既区块获得了超过2/3的共识节点签名。第二种间接确认是一个区块未获得2/3的共识节点签名，但其子块获得了超过2/3共识节点的签名，BBFT则会认为此区块间接的获得了最终确认的状态。

容灾容错

1. 支持只剩单共识节点存活的情况下支撑整个网络的运行到下一轮共识节点替换，但出块速度会下降为正常情况的1/n.用户可在此期间更改投票替换超级节点，在下一轮共识节点替换时网络既恢复正常状态。
2. 支持1/3的共识节点作恶的情况下网络正常运行，当超过1/3的共识节点作恶区块将长时间不能进入最终确认功能直至网络运行到下一轮共识节点被替换。当超过1/2的共识节点作恶，恶意节点将控制网络。

BBFT共识出块情景分析

以下案例假设 n = 5, m = 3, s = 1，区块高度 = 100，时间戳为= 1557148900, 

轮到3号共识节点准备出第一个块

完美状态 

1. 3号节点出高度为101， 时间戳为155714890区块A，广播至全网
2. 区块A得到超过2/3的节点确认，进入最终确认状态
3. 3号节点出高度为102， 时间戳为155714891区块B，广播至全网
4. 区块B得到超过2/3的节点确认，进入最终确认状态
5. 3号节点出高度为103， 时间戳为155714892区块C，广播至全网
6. 区块C得到超过2/3的节点确认，进入最终确认状态
7. 4号节点成功收到区块A, B, C并都处于最终状态，在此链的基础上继续连续出
8. 4号节点出高度为104， 时间戳为155714893区块D，广播至全网

达到毫秒级最终确认，无回滚发生, 只有在网络延迟低与共识节点稳定的时候产生

理想状态

1. 3号节点出高度为101， 时间戳为155714890区块A，广播至全网
2. 3号节点出高度为102， 时间戳为155714891区块B，广播至全网
3. 区块A得到超过2/3的节点确认，进入最终确认状态
4. 3号节点出高度为103， 时间戳为155714892区块C，广播至全网
5. 区块B得到超过2/3的节点确认，进入最终确认状态
6. 4号节点成功收到区块A, B, C但只有A,
   B处于最终确认状态，在此链的基础上继续连续出块
7. 4号节点出高度为104， 时间戳为155714893区块D，广播至全网
8. 区块C得到超过2/3的节点确认，进入最终确认状态

达到秒级最终确认，无回滚发生，但因收集共识节点对区块的确认签名，导致最终确认的延迟。
但由于所有区块已成功传递到下一个出块共识节点，所以不影响出块

出块共识节点异常状态

1. 时间戳为155714890， 无新块产生
2. 时间戳为155714891， 无新块产生
3. 时间戳为155714892， 无新块产生
4. 4号节点未收到任何区块，轮到挖矿后出高度为101，
   时间戳为155714893区块A广播至全网
5. 区块A得到超过2/3的节点确认，进入最终确认状态

达到秒级最终确认，无回滚发生，因共识节点down机导致全网3秒内无节点出块。造成的影响是减慢了全网的出块速度，当单节点长期down机需要等待下一次投票时重新选出新一轮的共识节点可修复

网络延迟异常1

1. 3号节点出高度为101， 时间戳为155714890区块A，广播至全网
2. 区块A得到超过2/3的节点确认，进入最终确认状态
3. 3号节点出高度为102， 时间戳为155714891区块B，广播至全网
4. 区块B得到超过2/3的节点确认，进入最终确认状态
5. 3号节点出高度为103， 时间戳为155714892区块C，广播至全网
6. 区块C得到超过2/3的节点确认，进入最终确认状态
7. 4号节点成功收到区块A, B但C区块由于延迟问题暂未收到
8. 4号节点出高度为103， 时间戳为155714893区块D，广播至全网
9. 由于2/3的共识节点已最终确认区块C, D无法获得最终确认
10. 4号节点收到区块C与C的最终确认信息， 回滚区块D, 切换链至区块C
11. 4号节点出高度为104， 时间戳为155714894区块E，广播至全网
12. 区块E得到超过2/3的节点确认，进入最终确认状态

达到秒级最终确认，有回滚在所有没收到区块C的节点中发生，造成的影响是减慢了1个块的出块速度

网络延迟异常2

1. 3号节点出高度为101， 时间戳为155714890区块A，广播至全网
2. 区块A得到超过2/3的节点确认，进入最终确认状态
3. 3号节点出高度为102， 时间戳为155714891区块B，广播至全网
4. 区块B得到超过2/3的节点确认，进入最终确认状态
5. 3号节点出高度为103， 时间戳为155714892区块C，广播至全网
6. 4号节点成功收到区块A, B但C区块由于延迟问题暂未收到
7. 4号节点出高度为103， 时间戳为155714893区块D，广播至全网
8. 区块D得到超过2/3的节点确认，进入最终确认状态
9. 3号节点收到区块D与D的最终确认信息， 回滚区块C, 切换链至区块D
10. 4号节点出高度为104， 时间戳为155714894区块E，广播至全网
11. 区块E得到超过2/3的节点确认，进入最终确认状态

达到秒级最终确认，有回滚在所有认同区块C的节点中发生，造成的影响是减慢了1个块的出块速度

网络延迟异常3 

1. 3号节点出高度为101， 时间戳为155714890区块A，广播至全网
2. 区块A得到超过2/3的节点确认，进入最终确认状态
3. 3号节点出高度为102， 时间戳为155714891区块B，广播至全网
4. 区块B得到超过2/3的节点确认，进入最终确认状态
5. 3号节点出高度为103， 时间戳为155714892区块C，广播至全网
6. 4号节点成功收到区块A, B但C区块由于延迟问题暂未收到
7. 4号节点出高度为103， 时间戳为155714893区块D，广播至全网
8. 区块D得到超过2/3的节点确认，进入最终确认状态
9. 3号节点收到区块D与D的最终确认信息， 回滚区块C, 切换链至区块D
10. 4号节点出高度为104， 时间戳为155714894区块E，广播至全网
11. 区块E得到超过2/3的节点确认，进入最终确认状态

达到秒级最终确认，有回滚在所有认同区块C的节点中发生，造成的影响是减慢了1个块的出块速度

网络延迟异常4 

1. 3号节点出高度为101， 时间戳为155714890区块A，广播至全网
2. 区块A得到超过2/3的节点确认，进入最终确认状态
3. 3号节点出高度为102， 时间戳为155714891区块B，广播至全网
4. 区块B得到超过2/3的节点确认，进入最终确认状态
5. 3号节点出高度为103， 时间戳为155714892区块C，广播至全网
6. 4号节点成功收到区块A, B但C区块由于延迟问题暂未收到
7. 4号节点出高度为103， 时间戳为155714893区块D，广播至全网
8. 区块C, D各获得50%的共识节点投票，网络进入分叉状态
9. 4号节点出高度为104， 时间戳为155714894区块E，广播至全网
10. 区块E得到超过2/3的节点确认，进入最终确认状态
11. 4号节点出高度为105， 时间戳为155714895区块E，广播至全网

达到秒级最终确认(极端情况分钟级发生概率和比特币回滚6区块差不多)，有回滚在所有认同区块C的节点中发生，造成的影响是减慢了1个块的出块速度.
此异常情况的极限状态是两条链各站约50%的算力并且发生持续竞争，直到稍占共识优势的链先进入了了最终确认状态。

参数对网络的影响

1.共识节点的个数其实代表了区块链网络的容错率，n越大则单点故障对网络造成的影响越小。但n的数量增大会导致BFT对区块签名数量要求的增加，会消耗更多的资源与延缓区块进入最终确认状态所需要的时间

2.每个节点连续出块的个数是为了在考虑到网络延迟的情况下仍可以保证高速出块的方法。
当连续出块个数足够时出块时间理论上可达毫秒级。核心点就是当下一个出块共识节点有网络延迟未收到最后的3个区块，但之前的m-3个区已收到，可在m-3基础上继续出块。但m过大会导致单共识节点故障时长时间不出块

3.出块间隔时间明面上是高tps的保证，理论上当出块间隔为200毫秒时比Bytom的tps可达25000。但s设置的过小可能导致区块最终确认时间的延长。

论文链接：https://github.com/bystackcom/BBFT