Bystack 的高 TPS 共识算法

本贴最后更新于 1767 天前,其中的信息可能已经时异事殊

共识算法是分布式系统保证节点数据状态一致性的方法,在区块链的共识算法分 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,广播至全网

  1. 区块 B 得到超过 2/3 的节点确认,进入最终确认状态

5.  3 号节点出高度为 103, 时间戳为 155714892 区块 C,广播至全网

  1. 区块 C 得到超过 2/3 的节点确认,进入最终确认状态

  2. 4 号节点成功收到区块 A, B, C 并都处于最终状态,在此链的基础上继续连续出

  3. 4 号节点出高度为 104, 时间戳为 155714893 区块 D,广播至全网


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

理想状态

  1. 3 号节点出高度为 101, 时间戳为 155714890 区块 A,广播至全网

  2. 3 号节点出高度为 102, 时间戳为 155714891 区块 B,广播至全网

  3. 区块 A 得到超过 2/3 的节点确认,进入最终确认状态

4.  3 号节点出高度为 103, 时间戳为 155714892 区块 C,广播至全网

  1. 区块 B 得到超过 2/3 的节点确认,进入最终确认状态

  2. 4 号节点成功收到区块 A, B, C 但只有 A,
    B 处于最终确认状态,在此链的基础上继续连续出块

  3. 4 号节点出高度为 104, 时间戳为 155714893 区块 D,广播至全网

  4. 区块 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,广播至全网

  1. 区块 B 得到超过 2/3 的节点确认,进入最终确认状态

5.  3 号节点出高度为 103, 时间戳为 155714892 区块 C,广播至全网

  1. 区块 C 得到超过 2/3 的节点确认,进入最终确认状态

  2. 4 号节点成功收到区块 A, B 但 C 区块由于延迟问题暂未收到

  3. 4 号节点出高度为 103, 时间戳为 155714893 区块 D,广播至全网

  4. 由于 2/3 的共识节点已最终确认区块 C, D 无法获得最终确认

  5. 4 号节点收到区块 C 与 C 的最终确认信息, 回滚区块 D, 切换链至区块 C

  6. 4 号节点出高度为 104, 时间戳为 155714894 区块 E,广播至全网

  7. 区块 E 得到超过 2/3 的节点确认,进入最终确认状态


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

网络延迟异常 2

  1. 3 号节点出高度为 101, 时间戳为 155714890 区块 A,广播至全网

  2. 区块 A 得到超过 2/3 的节点确认,进入最终确认状态

3.  3 号节点出高度为 102, 时间戳为 155714891 区块 B,广播至全网

  1. 区块 B 得到超过 2/3 的节点确认,进入最终确认状态

5.  3 号节点出高度为 103, 时间戳为 155714892 区块 C,广播至全网

  1. 4 号节点成功收到区块 A, B 但 C 区块由于延迟问题暂未收到

  2. 4 号节点出高度为 103, 时间戳为 155714893 区块 D,广播至全网

  3. 区块 D 得到超过 2/3 的节点确认,进入最终确认状态

  4. 3 号节点收到区块 D 与 D 的最终确认信息, 回滚区块 C, 切换链至区块 D

  5. 4 号节点出高度为 104, 时间戳为 155714894 区块 E,广播至全网

  6. 区块 E 得到超过 2/3 的节点确认,进入最终确认状态


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

网络延迟异常 3 

  1. 3 号节点出高度为 101, 时间戳为 155714890 区块 A,广播至全网

  2. 区块 A 得到超过 2/3 的节点确认,进入最终确认状态

3.  3 号节点出高度为 102, 时间戳为 155714891 区块 B,广播至全网

  1. 区块 B 得到超过 2/3 的节点确认,进入最终确认状态

5.  3 号节点出高度为 103, 时间戳为 155714892 区块 C,广播至全网

  1. 4 号节点成功收到区块 A, B 但 C 区块由于延迟问题暂未收到

  2. 4 号节点出高度为 103, 时间戳为 155714893 区块 D,广播至全网

  3. 区块 D 得到超过 2/3 的节点确认,进入最终确认状态

  4. 3 号节点收到区块 D 与 D 的最终确认信息, 回滚区块 C, 切换链至区块 D

  5. 4 号节点出高度为 104, 时间戳为 155714894 区块 E,广播至全网

  6. 区块 E 得到超过 2/3 的节点确认,进入最终确认状态


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

网络延迟异常 4 

  1. 3 号节点出高度为 101, 时间戳为 155714890 区块 A,广播至全网

  2. 区块 A 得到超过 2/3 的节点确认,进入最终确认状态

3.  3 号节点出高度为 102, 时间戳为 155714891 区块 B,广播至全网

  1. 区块 B 得到超过 2/3 的节点确认,进入最终确认状态

5.  3 号节点出高度为 103, 时间戳为 155714892 区块 C,广播至全网

  1. 4 号节点成功收到区块 A, B 但 C 区块由于延迟问题暂未收到

  2. 4 号节点出高度为 103, 时间戳为 155714893 区块 D,广播至全网

  3. 区块 C, D 各获得 50% 的共识节点投票,网络进入分叉状态

  4. 4 号节点出高度为 104, 时间戳为 155714894 区块 E,广播至全网

  5. 区块 E 得到超过 2/3 的节点确认,进入最终确认状态

  6. 4 号节点出高度为 105, 时间戳为 155714895 区块 E,广播至全网


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

参数对网络的影响

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

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

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

  • Bystack
    2 引用
  • 区块链

    区块链是分布式数据存储、点对点传输、共识机制、加密算法等计算机技术的新型应用模式。所谓共识机制是区块链系统中实现不同节点之间建立信任、获取权益的数学算法 。

    91 引用 • 751 回帖 • 5 关注
  • 共识
    3 引用 • 1 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...