拜占庭将军问题2 c% @. d( R5 B+ q1 _

, p1 R% r: ]+ n' J9 l/ h$ D' g  A    BFT技术的由来源于一个叫拜占庭将军问题。1 Y/ @% d! v7 N/ `' C
% o5 p7 v0 m" D) r% X! l3 Q3 o' d
    拜占庭位于如今的土耳其的伊斯坦布尔，是东罗马帝国的首都，由于当时拜占庭罗马帝国国土辽阔，每支军队的驻地分隔很远，将军们只能靠信使传递消息。发生战争时，将军们必须制订统一的行动计划。然而，这些将军中有叛徒，叛徒希望通过影响统一行动计划的制定与传播，破坏忠诚的将军们一致的行动计划。因此，将军们必须有一个预定的方法协议，使所有忠诚的将军能够达成一致，而且少数几个叛徒不能使忠诚的将军做出错误的计划。也就是说，拜占庭将军问题的实质就是要寻找一个方法，使得将军们能在一个有叛徒的非信任环境中建立对战斗计划的共识，拜占庭问题就此形成。
. X3 ^+ s# |" m6 N4 Y, C* K9 e- v% V
7 L8 g! R9 \8 g% m1 R$ K8 h    拜占庭将军问题（ByzantineGeneralsProblem），首先由LeslieLamport与另外两人在1982年提出，很简单的故事模型，却困扰了计算机科学家们数十年。8 d6 R( t) |2 |4 z+ ~

# D, X5 Q" H! y/ w$ E    我们将拜占庭将军问题简化一下，所有忠诚的将军都能够让别的将军接收到自己的真实意图，并最终一致行动；而形式化的要求就是，“一致性”与“正确性”。6 [- L+ I. ~( C$ W' \1 q
* p& n! k+ P% O4 A3 h0 k& F( b
    一致性：每个忠诚的将军必须收到相同的命令值vi（vi是第i个将军的命令）
% f- y5 @3 N# `7 [4 Y6 _& \' k4 b
    正确性：如果第i个将军是忠诚的，那么他发送的命令和每个忠诚将军收到的vi相同。: a* S/ f! b* S. e3 m1 I9 b! d6 i
8 k' W8 F' O3 ?8 |' t+ E4 z
    Lamport对拜占庭将军的问题的研究表明，当n>3m时，即叛徒的个数m小于将军总数的n的1/3时，通过口头同步通信（假设通信是可靠的），可以构造同时满足“一致性”和“正确性”的解决方法，即将军们可以达成一致的命令。
. t- i2 Q- g+ Z1 O( s4 U5 k+ @8 B
4 v) N0 _) D6 B+ _1 r- T; ^! t$ ]$ A  p    拜占庭容错理论算法
1 e' t8 n# J5 w6 B8 J4 Z) p" k$ b' J
    拜占庭容错系统，英文全称是ByzantineFaultTolerance，是一种理论上解决拜占庭问题的方法，并非实用，不过基于BFT理论延伸出了其他共识机制。# {! D+ X$ @( N) R6 j: B4 v

6 N" m1 s8 m* a    区块链网络的记账共识和拜占庭将军的问题是相似的。参与共识记账的每一个节点相当于将军，节点之间的消息传递相当于信使，某些节点可能由于各种原因而产生错误的信息传递给其他节点。通常这些发生故障的节点被称为拜占庭节点，而正常的节点即为非拜占庭节点。
. L' L4 m( y+ y, N0 i+ P; X9 }4 f) ]0 C$ i; X3 G7 t9 }' q
    假设分布式系统拥有n台节点，并假设整个系统拜占庭节点不超过m台（n≥3m+1），拜占庭容错系统需要满足如下两个条件：
. ^+ e: K) @; Y" J. b
9 P' f; ~2 v3 M* b2 m# i" V% f. C2 L    所有非拜占庭节点使用相同的输入信息，产生同样的结果。在区块链系统中，可以理解为，随机数相同、区块算法相同、原账本相同的时候，计算结果相同。
4 G7 Y" A* d) s" U* G* ?5 D& u, @, _7 t6 H- y
    如果输入的信息正确，那么所有非拜占庭节点必须接收这个消息，并计算相应的结果。在区块链系统中，可以理解为，非拜占庭节点需要对客户的请求进行计算并生成区块。
9 H: Q- T+ {2 x. Q
- j2 g: |+ U. H+ X& Y    另外，拜占庭容错系统需要达成如下两个指标：
( D+ T% j* O) U$ ~- C
# N% E/ w8 c, j2 ?  U% l3 ~$ k    安全性：任何已经完成的请求都不会被更改，它可以在以后请求看到。在区块链系统中，可以理解为，已经生成的账本不可篡改，并且可以被节点随时查看。
% B( f  g9 m3 d% I* E# r, t
- |0 ^( `" m* o" [    活性：可以接受并且执行非拜占庭客户端的请求，不会被任何因素影响而导致非拜占庭客户端的请求不能执行。在区块链系统中，可以理解为，系统需要持续生成区块，为用户记账，这主要靠挖矿的激励机制来保证。1 k/ g8 \- A! y! ^
8 |: ~0 o3 N  N$ o
    在分析拜占庭问题的时候，假设信道是可信的。拓展开来，在拜占庭容错系统，普遍采用的假设条件包括：" k0 l% H0 f7 ?% J' U. _9 }

7 E0 z' }7 k% A# Y8 x4 j) M( S2 M3 M    拜占庭节点的行为可以是任意的，拜占庭节点之间可以共谋；
/ s& H' Z, A  J2 I  r
/ a! V8 U4 ~- g1 H7 r5 x9 Q    节点之间的错误是不相关的；
; [  v' C5 u& e& a* {3 k1 ]; G( ^* V) j+ ?
    节点之间通过异步网络连接，网络中的消息可能丢失、乱序并延时到达，但大部分协议假设消息在有限的时间里能传达到目的地；
) O) l# N( N! J& V* b9 e- ]( K% A2 G* r1 c8 J* r
    节点之间传递的信息，第三方可以嗅探到，但是不能篡改、伪造信息的内容和破坏信息的完整性。/ a! g* Q. M0 ]
+ q! `- ?8 Y$ Z9 F4 H; w! U
    拜占庭容错技术，是一类分布式计算领域的容错技术。名称拜占庭是一个泛指，它代表着计算机领域，在这个领域内会有很多问题，如硬件错误、网络拥堵或中断以及遭到恶意攻击等等，造成计算机网络可能出现的混乱。BFT技术就是为了使混乱状态达到一致性。