Hi 游客

更多精彩,请登录!

比特池塘 区块链前沿 正文

拜占庭容错(BFT)技术详解

wxf2017
453 0 0
拜占庭将军问题
* y/ _; t9 `0 n! M1 c" C0 |, C, s9 ?% |
    BFT技术的由来源于一个叫拜占庭将军问题。
; m* f' {- `8 m9 x# y5 @0 [% w' |8 \
    拜占庭位于如今的土耳其的伊斯坦布尔,是东罗马帝国的首都,由于当时拜占庭罗马帝国国土辽阔,每支军队的驻地分隔很远,将军们只能靠信使传递消息。发生战争时,将军们必须制订统一的行动计划。然而,这些将军中有叛徒,叛徒希望通过影响统一行动计划的制定与传播,破坏忠诚的将军们一致的行动计划。因此,将军们必须有一个预定的方法协议,使所有忠诚的将军能够达成一致,而且少数几个叛徒不能使忠诚的将军做出错误的计划。也就是说,拜占庭将军问题的实质就是要寻找一个方法,使得将军们能在一个有叛徒的非信任环境中建立对战斗计划的共识,拜占庭问题就此形成。2 ~; y3 D* L; Y/ c: o4 X! v
: z$ s7 W2 M7 d3 Y: S; U8 P( p( D
    拜占庭将军问题(ByzantineGeneralsProblem),首先由LeslieLamport与另外两人在1982年提出,很简单的故事模型,却困扰了计算机科学家们数十年。5 b5 i  J; Y  ~% p

" d& B" }* _: r3 j" S    我们将拜占庭将军问题简化一下,所有忠诚的将军都能够让别的将军接收到自己的真实意图,并最终一致行动;而形式化的要求就是,“一致性”与“正确性”。& Q: c& n/ E  }

9 l+ {9 W2 A- Y6 @& V+ o1 C( C    一致性:每个忠诚的将军必须收到相同的命令值vi(vi是第i个将军的命令)
  o, j+ o5 g, g# w6 s" p! k1 e+ f. u! G1 I' ~6 a9 Q
    正确性:如果第i个将军是忠诚的,那么他发送的命令和每个忠诚将军收到的vi相同。$ l6 m" [9 t1 x% O$ u1 J% a

7 |5 h  [% V1 U4 n    Lamport对拜占庭将军的问题的研究表明,当n>3m时,即叛徒的个数m小于将军总数的n的1/3时,通过口头同步通信(假设通信是可靠的),可以构造同时满足“一致性”和“正确性”的解决方法,即将军们可以达成一致的命令。
9 i$ k/ B. F! w' d5 y4 w  R; K7 ]5 C1 a1 f( j. r3 z
    拜占庭容错理论算法% s: o0 \7 f/ g5 r/ J+ Y
% p' ?4 P, g. u/ S4 U# x9 X
    拜占庭容错系统,英文全称是ByzantineFaultTolerance,是一种理论上解决拜占庭问题的方法,并非实用,不过基于BFT理论延伸出了其他共识机制。
  Y2 B. V+ r) u" Q3 t9 o9 ^  ?+ X, ~# _
    区块链网络的记账共识和拜占庭将军的问题是相似的。参与共识记账的每一个节点相当于将军,节点之间的消息传递相当于信使,某些节点可能由于各种原因而产生错误的信息传递给其他节点。通常这些发生故障的节点被称为拜占庭节点,而正常的节点即为非拜占庭节点。6 K' U+ ]$ E9 {+ [" L) L* h* W6 V4 t
+ a9 F: U1 \5 E1 s! R+ S: ~' o
    假设分布式系统拥有n台节点,并假设整个系统拜占庭节点不超过m台(n≥3m+1),拜占庭容错系统需要满足如下两个条件:
% v+ Z( o9 b( k8 n+ h; Z3 a
+ |4 {# F- f- }7 A# j    所有非拜占庭节点使用相同的输入信息,产生同样的结果。在区块链系统中,可以理解为,随机数相同、区块算法相同、原账本相同的时候,计算结果相同。
3 _, R4 V5 X; o, R0 Q; }4 Z" @6 Q. \) L2 U. o+ Q
    如果输入的信息正确,那么所有非拜占庭节点必须接收这个消息,并计算相应的结果。在区块链系统中,可以理解为,非拜占庭节点需要对客户的请求进行计算并生成区块。: g& S, T( w1 w% r# [
- ^. ^; J3 X0 |
    另外,拜占庭容错系统需要达成如下两个指标:3 x' d  G) o9 M1 a$ c. a! E

& Y6 }) i2 ~6 S( j    安全性:任何已经完成的请求都不会被更改,它可以在以后请求看到。在区块链系统中,可以理解为,已经生成的账本不可篡改,并且可以被节点随时查看。
& b: J) ?3 V& V' D! e9 h  f' o/ @" z' ]* a3 F  U
    活性:可以接受并且执行非拜占庭客户端的请求,不会被任何因素影响而导致非拜占庭客户端的请求不能执行。在区块链系统中,可以理解为,系统需要持续生成区块,为用户记账,这主要靠挖矿的激励机制来保证。' {6 N4 r8 b7 [/ A6 Y( i! C4 ~& T
; N& H- r6 U/ w/ e* I9 z5 e2 T' f0 ^
    在分析拜占庭问题的时候,假设信道是可信的。拓展开来,在拜占庭容错系统,普遍采用的假设条件包括:
0 L4 D3 m- }3 }0 ~4 V) u" n6 T* o% G" P4 Y& }# q6 ~
    拜占庭节点的行为可以是任意的,拜占庭节点之间可以共谋;" r# w( m$ g5 Q  E1 N

' j* S' b0 k: e- ~' \" L7 j    节点之间的错误是不相关的;, G! m; H, y' V+ |; ~0 h7 C

- A7 D& K; }6 D0 f8 V9 r* [    节点之间通过异步网络连接,网络中的消息可能丢失、乱序并延时到达,但大部分协议假设消息在有限的时间里能传达到目的地;
- h: O0 R3 g- l+ b) Q
8 w3 N3 d* r2 z0 m# A2 ]8 O5 B    节点之间传递的信息,第三方可以嗅探到,但是不能篡改、伪造信息的内容和破坏信息的完整性。
( `' X4 R6 [0 ]% l7 y( Q+ N- M. }; ^# L8 ?/ {
    拜占庭容错技术,是一类分布式计算领域的容错技术。名称拜占庭是一个泛指,它代表着计算机领域,在这个领域内会有很多问题,如硬件错误、网络拥堵或中断以及遭到恶意攻击等等,造成计算机网络可能出现的混乱。BFT技术就是为了使混乱状态达到一致性。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

wxf2017 初中生
  • 粉丝

    0

  • 关注

    0

  • 主题

    27