拜占庭容错(BFT)技术详解「科普」
虹桥大宝剑
发表于 2022-12-14 04:16:00
115
0
0
4 ^# j/ f2 h4 t
拜占庭将军问题
4 K+ x% s7 e( X9 D
BFT技术的由来源于一个叫拜占庭将军问题。" e9 ^# ]2 x* J. D/ D( A
4 T+ C, ~6 ?- ~, w# V4 I6 B8 h0 N8 U6 }
拜占庭位于如今的土耳其的伊斯坦布尔,是东罗马帝国的首都,由于当时拜占庭罗马帝国国土辽阔,每支军队的驻地分隔很远,将军们只能靠信使传递消息。发生战争时,将军们必须制订统一的行动计划。然而,这些将军中有叛徒,叛徒希望通过影响统一行动计划的制定与传播,破坏忠诚的将军们一致的行动计划。因此,将军们必须有一个预定的方法协议,使所有忠诚的将军能够达成一致,而且少数几个叛徒不能使忠诚的将军做出错误的计划。也就是说,拜占庭将军问题的实质就是要寻找一个方法,使得将军们能在一个有叛徒的非信任环境中建立对战斗计划的共识,拜占庭问题就此形成。
1 L) V6 p) h5 V/ y7 F
拜占庭将军问题(Byzantine Generals Problem),首先由Leslie Lamport与另外两人在1982年提出,很简单的故事模型,却困扰了计算机科学家们数十年。( h- c: i- c. N- ^3 B) @" K
我们将拜占庭将军问题简化一下,所有忠诚的将军都能够让别的将军接收到自己的真实意图,并最终一致行动;而形式化的要求就是,“一致性”与“正确性”。6 F& r, i& H; ^. X! q
; ^4 L, O$ @8 b l/ D E; V, U. T
一致性:每个忠诚的将军必须收到相同的命令值vi(vi是第i个将军的命令); e( E9 E/ _; G' y
4 r+ O4 q' v5 y( J5 J
正确性:如果第i个将军是忠诚的,那么他发送的命令和每个忠诚将军收到的vi相同。% k H. z7 X3 f; o8 a7 e
Lamport对拜占庭将军的问题的研究表明,当n > 3m时,即叛徒的个数m小于将军总数的n的1/3时,通过口头同步通信(假设通信是可靠的),可以构造同时满足“一致性”和“正确性”的解决方法,即将军们可以达成一致的命令。" U4 _/ [% g* R+ j
! ? v/ O3 K! K c6 a
拜占庭容错理论算法) c1 ?& l1 G( W5 ]
拜占庭容错系统,英文全称是Byzantine Fault Tolerance,是一种理论上解决拜占庭问题的方法,并非实用,不过基于BFT理论延伸出了其他共识机制。( T* H1 p8 J8 ^/ l
% z. y* o% Z% v8 P% P" a1 U
区块链网络的记账共识和拜占庭将军的问题是相似的。参与共识记账的每一个节点相当于将军,节点之间的消息传递相当于信使,某些节点可能由于各种原因而产生错误的信息传递给其他节点。通常这些发生故障的节点被称为拜占庭节点,而正常的节点即为非拜占庭节点。
8 e- D5 t0 P" ~: m
假设分布式系统拥有n台节点,并假设整个系统拜占庭节点不超过m台(n≥3m+1),拜占庭容错系统需要满足如下两个条件:/ t; ?2 R$ n5 S) M. v
u$ u" H2 T2 w+ L2 I& [8 C
所有非拜占庭节点使用相同的输入信息,产生同样的结果。在区块链bbcaijing.cn系统中,可以理解为,随机数相同、区块算法相同、原账本相同的时候,计算结果相同。( @/ J: z" f( w7 e U z# P/ J
5 [8 v9 \9 b- l; W1 W) H8 _. I- z2 B
如果输入的信息正确,那么所有非拜占庭节点必须接收这个消息,并计算相应的结果。在区块链系统中,可以理解为,非拜占庭节点需要对客户的请求进行计算并生成区块。% [4 p8 H" }1 T7 J3 q' t% @- V
另外,拜占庭容错系统需要达成如下两个指标:8 H6 U8 h0 Q5 S2 j0 p& J
安全性:任何已经完成的请求都不会被更改,它可以在以后请求看到。在区块链系统中,可以理解为,已经生成的账本不可篡改,并且可以被节点随时查看。
活性:可以接受并且执行非拜占庭客户端的请求,不会被任何因素影响而导致非拜占庭客户端的请求不能执行。在区块链系统中,可以理解为,系统需要持续生成区块,为用户记账,这主要靠挖矿的激励机制来保证。
! I8 r. U# I% k% C& Q5 G
在分析拜占庭问题的时候,假设信道是可信的。拓展开来,在拜占庭容错系统,普遍采用的假设条件包括:$ V( [; G3 X( D3 T/ O8 Q
拜占庭节点的行为可以是任意的,拜占庭节点之间可以共谋;
0 }/ S* R6 v% ~$ Y
节点之间的错误是不相关的;
3 c$ W3 V6 R& {) {% D* H6 X
节点之间通过异步网络连接,网络中的消息可能丢失、乱序并延时到达,但大部分协议假设消息在有限的时间里能传达到目的地;, j7 x1 Z2 ^7 U \5 T& a0 Y: @
节点之间传递的信息,第三方可以嗅探到,但是不能篡改、伪造信息的内容和破坏信息的完整性。
成为第一个吐槽的人