拜占庭问题

故事梗概

拜占庭帝国即中世纪的土耳其,拥有巨大的财富,周围10个邻邦垂诞已久,但拜占庭高墙耸立,固若金汤,没有一个单独的邻邦能够成功入侵。任何单个邻邦入侵的都会失败,同时也有可能自身被其他9个邻邦入侵。拜占庭帝国防御能力如此之强,至少要有十个邻邦中的一半以上同时进攻,才有可能攻破。

然而,如果其中的一个或者几个邻邦本身答应好一起进攻,但实际过程出现背叛,那么入侵者可能都会被歼灭。

于是每一方都小心行事,不敢轻易相信邻国。这就是拜占庭将军问题。

故事解剖

在拜占庭问题中,最重要的point就是:所有将军如何达成一致攻打拜占庭的共识,这当中,可能出现的情况举例如下:

  • 存在叛徒,欺骗其他将军自己将采取行动
  • 叛徒可能迷惑其他将军,使他们接受的消息不一致(传递消息的过程)

用一个模型解释一下:

假设只有3个人,A、B、C,三人中如果其中一个是叛徒。当A发出进攻命令时,B如果是叛徒,他可能告诉C,他收到的是“撤退”的命令。这时C收到一个“进攻”,一个“撤退“,于是C被信息迷惑,而无所适从。

如果A是叛徒。他告诉B“进攻”,告诉C“撤退”。当C告诉B,他收到“撤退”命令时,B由于收到了司令“进攻”的命令,而无法与C保持一致。

正由于上述原因,在只有三个角色的系统中,只要有一个是叛徒,即叛徒数等于1/3,拜占庭问题便不可解。

可以看得出,只要叛徒的数量大于或等于1/3,拜占庭问题不可解

再度解剖拜占庭问题

从技术上理解,拜占庭将军问题是分布式系统容错性问题。加密货币建立在P2P网络之上,是典型的分布式系统,类比一下,将军就是P2P网络中的节点,信使就是节点之间的通信,进攻还是撤退的决定就是需要达成的共识如果某台独立的节点计算机拓机、掉线或攻击网络搞破坏,整个系统就要停止运行,那这样的系统将非常脆弱,所以容许部分节点出错或搞破坏而不影响整个系统运行是必要的这就需要算法理论上的支撑,保证分布式系统在一定量的错误节点存在的情况下,仍然保持一致性和可用性

而且,拜占庭将军与两军问题不同,前者假定信差没有问题,只是将军出现了叛变等问题;后者研究信差的通信问题。

科学家们的解决方法

  • 口头信息(未了)

    即将军们派人用口信传递信息,其实际含义是指:

    • 每个被发送的消息均可被正确投递
    • 消息接受者知道消息是谁发的
    • 不发消息可被检测

    大白话就是,一个节点1发布消息,节点2-10都可以收到消息,其他节点类似,一轮下来,每个节点手上都会有10个信息(进攻或者撤退),这时候只要叛徒数目小于一半,那么

  • 书面协议

    10个国家,每个国家都可以派人向各个国家派信,比如一起约定“某天早上六点,大家一起进攻拜占庭,同意就签个字”。收到信的国家如果同意的话,就可以在原信上签名盖章。

    相比口头协议,实际说的是在这个多人的将军模型中加了了个隐含条件:

    • 将军们能够使用签名技术,签名不可伪造,一旦篡改即可发现。
    • 同时任何人都可以验证签名的可靠性。

    书面协议相比口头协议,所有的消息都是有记录的,解决了追根溯源的问题。

    但是,签名消息记录的保存难以摆脱中心化的机构。另外,倘若每个国家都各自向其他9个国家派出信使,在这个网络即需要90次的传输才能完成一轮信息交流,但是每个国家可能回馈不同的进攻时间,在这种异步通信的条件下,要能协商一致是个大问题。

区块链技术

终极解决方案到了——

如果10个将军中的几个同时发起消息,势必会造成系统的混乱,造成各说各的攻击时间方案,行动难以一致

谁都可以发起进攻的信息,但由谁来发出呢?中本聪巧妙地在个系统加入了发送信息的成本,即:

  1. 一段时间内只有一个节点可以传播信息

它加入的成本就是”工作量“——节点必须完成一个计算工作才能向各城邦传播消息,当然,谁第一个完成工作,谁才能传播消息。(这也是工作量证明机制的意义:以检验结果的方式证明你过去所做过了多少工作

  1. 比特币有一个算法难度,会
    根据全网算力自动调整,以保证网络一直需要花费10分钟来找到一个有效的哈希值,并产生一个新区块。

  2. 某个节点发出统一进攻的消息后,各个节点收到发起者的消息必须签名盖章,确认各自的身份。中本聪在这里引用现代加密技术为这个信息签名。

这种加密技术——非对称加密,完全可以解决古代难以解决的签名问题:

  • 消息传送的私密性
  • 能够确认身份
  • 签名不可伪造、篡改
  1. 通过区块链,使用一个共同账本。如果有一个叛徒(不诚实节点)修改了前面区块的信息,计划把钱全部划归自己所有,当它广播新区块的时候,其他节点如何通过验证?如果大家手里没有一份相同的账本,肯定无法验证,问题就会陷入僵局。基于P2P网络的BT技术是成熟的,同步一个总帐是很简单的事情。网络中的节点,在每个循环周期内都是同步的,这让每个节点(将军)做决策的时候就有了共同的基础

中本聪在设计比特币时,它采用了一种工作量证明机制叫哈希现金,在一个交易块这要找到一个随机数,计算机只能用穷举法来找到这个随机数,可以说,能不能找到全靠运气,所以对于各个节点来说,这个世界上,只有随机才是真正的公平,实现随机的最好办法是使用数学,所有的将军在寻找共识的过程,借助了大家都认可的数学逻辑。

当然了,凭什么要义务进行计算工作,那么肯定要有一个激励机制:比特币的奖励机制是每打包一个块,目前是奖励25个比特币,而拜占庭将军问题的奖励机制可以是瓜分拜占庭获得的利益。

如果又出现背叛怎么办?

在这个分布式网络里:

每个将军都有一份实时与其他将军同步的消息账本
账本里有每个将军的签名都是可以验证身份的。如果有哪些消息不一致,可以知道消息不一致的是哪些将军
尽管有消息不一致的,只要超过半数同意进攻,少数服从多数,共识达成(只要大多数是好人,那么就可以实现共识)。

区块链上的共识机制主要解决由谁来构造区块,以及如何维护区块链统一的问题。

拜占庭容错问题需要解决的也同样是谁来发起信息,如何实现信息的统一同步的问题。

注:区块链学习新人,若有不正确的地方,望指出

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 199,440评论 5 467
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 83,814评论 2 376
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 146,427评论 0 330
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 53,710评论 1 270
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 62,625评论 5 359
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,014评论 1 275
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,511评论 3 390
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,162评论 0 254
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,311评论 1 294
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,262评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,278评论 1 328
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,989评论 3 316
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,583评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,664评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,904评论 1 255
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,274评论 2 345
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 41,856评论 2 339

推荐阅读更多精彩内容