小白学习区块链之拜占庭将军的问题
Hi5
发表于 2022-11-17 14:52:26
55
0
0
看到这个词语时,我曾经一度认为有一位名叫拜占庭的将军带领着一支庞大的军队打仗时遇到了难题,但查阅了一些资料后,发现实际上并没有拜占庭将军,也没有这场战争,完全是计算机专家假想出的问题。
拜占庭这个专有名词取自于拜占庭帝国,又叫东罗马帝国,其军事力量很强大,地处现今欧洲的土耳其国家。
莱斯利·兰伯特(LeslieLamport),是微软研究院的首席研究员,曾获得2013年图灵奖——计算机界的诺贝尔奖。这家伙觉得故事让问题变得受欢迎,因此他在提出观点和问题时常用故事背景吸引眼球,拜占庭将军的故事就是兰伯特在研究分布式系统容错性的时候编出的一个故事。$ T' z! N" E5 i
9 H7 m" v; [& d
拜占庭将军问题描述
" k# i: N: a; X ?: v" {" s; H
论文中的原文:
8 t! [; I2 [+ s8 h y+ H
WeimaginethatseveraldivisionsoftheByzantinearmyarecampedoutsideanenemycity,eachdivisioncommandedbyitsowngeneral.Thegeneralscancommunicatewithoneanotheronlybymessenger.Afterobservingtheenemy,theymustdecideuponacommonplanofaction.However,someofthegeneralsmaybetraitors,tryingtopreventtheloyalgeneralsfromreachingagreement.0 j0 j7 V* R$ q( R5 A" F R4 s( y
; Z/ _6 f; i$ L. W6 F5 P' y
关于拜占庭将军问题,一个简易的非正式描述如下:
拜占庭帝国想要进攻一个强大的敌人,为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国,但也足以抵御5支常规拜占庭军队的同时袭击。基于一些原因,这10支军队不能集合在一起单点突破,必须在分开的包围状态下同时攻击。
他们任一支军队单独进攻都毫无胜算,除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周,依靠通信兵相互通信来协商进攻意向及进攻时间。
3 F) P s) h( D' Y) J; r" z% r8 U
这个问题的简洁描述:这些将军离得很远,不能每遇到一个问题,就聚到一起开会商量对策,耽误时机,拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商,达成共识,执行共同的作战计划,来取得战争的胜利?2 Q% ~8 k8 c# n# K( d
+ w+ B, K2 ]2 X; W$ W/ }; _& n
这就是著名的拜占庭将军问题。* B. X% u. i% X3 |) S
" k. U ^9 Y. O6 H6 a% ~4 P
拜占庭将军问题包含着两军问题,国内大量解释拜占庭将军问题的文章将两者混为一谈,这两个问题看起来的确有点相似,但是问题的前提和研究方向都截然不同。
, S) [ S; ?2 F, E& v; G
两军问题的难点:
$ ]7 C# W% @2 l4 ~ K& Y
·他们不确定他们中是否有叛徒,叛徒可能擅自变更进攻意向或者进攻时间。- G. ?3 M+ d; T, w+ x3 K, a* t% b
3 V& x0 q! A! X4 y9 q8 s$ ^
·信使在传递消息时可能会把信弄丢
·信息可能会被敌国截获
: D, W8 I; L" y: k7 U, K
·无法确定消息是否真的来自某位将军
8 }3 ?$ T2 g6 z: b4 g- `' L
因此,拜占庭将军问题的场景,是建立在信兵可以正确的传达信息的基础上的,即信道绝对可信。两军问题的探讨更多是真假信道的实质。
5 X& d* K: |+ D: I- J" M" N& B% s: a
区块链的解决方案
6 i H! s `8 Q" N N1 d
把军队想像成计算机节点,把信使想像成计算机间的网络通讯,攻占敌军就是写入一个大家公认的区块记录。7 Y8 K' d0 }1 D" Q$ L) j* n8 _
区块链技术在发送信息中加入了成本,降低了信息传递的速率,并采用了工作量证明(PoW),即一个节点必须经过大量尝试性计算才能得出一个结果,而其它节点只需极少的时间就能证明其真伪,这样能够减少垃圾消息、假消息在节点间传播的状况。
挖矿节点把一段时间内的交易信息打包成一个区块,盖上时间戳,与上一个区块衔接在一起,每个区块都包含了上一个区块的索引(哈希值),然后再写入新的信息,从而形成新的区块,首尾相连,最终形成了区块链。
j( f1 x' Y0 Y% f
用工作量证明、公钥加密等技术,使比特币网络从一个去中心化的不可信网络变为可信网络,使所有参与者可以在某些事情上达成一致,使价值传递成为了可能。1 [8 [( ^4 O$ W9 m4 L2 y4 O5 ]
: T) O$ s! @: C0 z; }, U" q6 k
如果10个将军中的几个同时发起消息,势必会造成系统的混乱,造成各说各的攻击时间方案,行动难以一致。
中本聪巧妙地在个系统加入了发送信息的成本,即:一段时间内只有一个节点可以传播信息。
它加入的成本就是”工作量“——节点必须完成一个计算工作才能向各城邦传播消息,当然,谁第一个完成工作,谁才能传播消息。
( l$ p1 G% z3 y5 z3 O
当某个节点发出统一进攻的消息后,各个节点收到发起者的消息必须签名盖章,确认各自的身份。中本聪在这里引用现代加密技术为这个信息签名。
加密、非加密解决签名问题
5 C7 e f4 G/ U( K! T: k: c
·消息传送的私密性( }9 ~1 t: K8 g; ]( c
! t' q6 ]6 N* |. H* c4 T
·能够确认身份
! a8 h1 t' i' ~# m7 G1 g) r
·签名不可伪造、篡改
& S8 n: U2 n6 o& D! G8 a
由此,一个不可信的分布式网络变成了一个可信的网络,所有的参与者可以在某件事在达成一致。
使用消息加密技术、以及公平的工作量证明机制,创建了一组所有将军都认可的协议,这套协议的出现,拜占庭将军问题也就完美的得到了解决。
成为第一个吐槽的人