电脑基础 · 2023年3月23日

共识算法涉及的概念

通信复杂度

共识算法涉及的概念
大家可以发现网络消息数从O(NN)下降到O(N),但因为每个prepareQC包含2f + 1 签名,所以通信量复杂度还是O(NN)。

密码学的进步:包含2f + 1 签名信息的prepareQC,使用门限签名,使得占用空间降至O(1),整个通信量复杂度下降到O(N)

通信模型

通信模型定义了对手延迟消息的权力限制,有三种基本通信模型:同步模型、异步模型和部分同步模型。

  • 同步模型:假定最大的网络延时T,得设置比较大(min级别?)。因为实际情况,网络可以出问题,而解决问题可能几分钟,也可能几小时,甚至几天。

  • 异步模型: 网络时延无保证,网络是无法保证达成共识的,著名的FLP定理
    -半异步模型: partial synchronous model,上面两个模型的折中也叫部分同步,网络可能处于异步状态,但是GST(global stable time)后会进入同步状态
    大部分共识算法都是基于半同步模型,这也符合实际情况,可以参考下文。
    https://decentralizedthoughts.github.io/2019-06-01-2019-5-31-models/

响应性(Responsiveness)

一旦网络进入同步状态,好的leader以实际网络延时的速度,达成共识。
也叫做(Optimistic) Responsiveness乐观响应性,我觉得也比较直观。就是网络达到同步状态(GST)后,即解决了所有网络问题后,真正干完活所需的时间和实际网络延迟一致。类似于要搬1000块砖,现在砖也准备好了,人也吃饱喝足了,那么假定一分钟搬10块砖,100分钟就能搬完。
(Optimistic) Responsiveness After GST, any correct leader, once designated, needs to wait just for the first (n−f) responses to guarantee that it can create a proposal that will make progress. “As fast as the network propagates, on a good day”

安全性(safety)

坏事情永远不发生,即所有的好节点不可能提交(commit)相冲突的数据
注意区别密码学的security,这个概念其实和共识算法无关,区块链中的security是通过密码学保证。

活性(liveness)

只要系统网络进入同步状态,系统最终都能达成新共识。
区块链中就是链的高度会增长,不断出新块。

参考链接https://blog.csdn.net/wenyuanhust/article/details/125495449