双重支付问题和拜占庭将军问题

双重支付问题(也叫双花)是重复多次使用相同的比特币的行为。

如:有一个坏人A,他用1000块钱找B买了一个手机,同时通过技术手段又用这相同的1000块钱找C买了一个电脑,这两笔支付都被确认,后面的矿工添加区块的速度不同,导致两笔交易生成的区块链有长有短,而后来的人基本会选择长的那条区块链继续记账,短的那条没有人承认了,而A却从中获利免费的手机或电脑。

拜占庭将军问题(Byzantine failures),是由莱斯利·兰伯特提出的点对点通信中的基本问题,主要反映分布式系统数据一致性问题——各节点如何在不可靠信道中达成共识?

拜占庭位于如今的土耳其的伊斯坦布尔,是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔,为了达到防御目的,每个军队都分隔很远,将军与将军之间只能靠信差传消息。在战争的时候,拜占庭军队内所有将军和副官必须达成一致的共识,决定是否有赢的机会才去攻打敌人的阵营。

但是,在军队内有可能存有叛徒和敌军的间谍,左右将军们的决定又扰乱整体军队的秩序。在进行共识时,结果并不代表大多数人的意见。叛徒可以任意行动以达到以下目标:欺骗某些将军采取进攻行动;促成一个不是所有将军都同意的决定,如当将军们不希望进攻时促成进攻行动;或者迷惑某些将军,使他们无法做出决定。如果叛徒达到了这些目的之一,则任何攻击行动的结果都是注定要失败的,只有完全达成一致的努力才能获得胜利。

这时候,在已知有成员谋反的情况下,其余忠诚的将军在不受叛徒的影响下如何达成一致的协议,拜占庭问题就此形成。

“拜占庭将军问题”延伸到互联网生活中来,其内涵可概括为:在互联网大背景下,当需要与不熟悉的对方进行价值交换活动时,人们如何才能防止不会被其中的恶意破坏者欺骗、迷惑从而作出错误的决策。进一步将“拜占庭将军问题”延伸到技术领域中来,其内涵可概括为:在缺少可信任的中央节点和可信任的通道的情况下,分布在网络中的各个节点应如何达成共识。

仅拿比特币世界来说,我们可以将每一个比特币交易账号看作一个将军,这些账号分布在世界各地,无法聚在一起,很可能会有恶意账号,账号之间的沟通也很可能因为机器坏了、网络断了、黑客攻击等受到破坏,并且有关账号是不是要支付、具体支付多少的讨论也会浪费很多时间。

区块链轻而易举地解决了这一问题,它为信息发送加入了成本,降低了信息传递的速率,而且加入了一个随机元素使得在一定时间内只有一个将军可以广播信息。这里所说的成本就是区块链系统中基于随机哈希算法的“工作量证明”。哈希算法所做的事情就是计算获得的输入,得到遗传64位的随机数字和字母的字符串 [6] 

区块链系统计算的输入数据是指节点发送的当前时间点的整个总账。当前计算机的算力使其可以实时计算出单个哈希值,但是区块链系统只接受前13个字符是0的哈希值结果作为“工作量证明”。而前13个字符是0的哈希值是非常罕见的,需要整个网络花费10分钟的时间才在数以亿计的数据中找到一个。在一个有效的哈希值被计算出来之前,网络中已经生产了无数个无效值,这就是降低信息传递速率并使得整个系统成功运行的“工作量证明” [6] 

在拜占庭将军问题中,第一个广播信息的将军就是第一个发现有效哈希值的计算机,只要其他将军接收到并验证通过了这个有效哈希值和附着在上面的信息,他们就只能使用新的信息更新他们的总账复制,然后重新计算哈希值。下一个计算出有效哈希值的将军就可以将自己再次更新的信息附着在有效哈希值上广播给大家。然后哈希计算竞赛从一个新的开始点重新开始。由于网络信息的持续同步,所有网络上的计算机都使用着同一版本的总账 [6] 

比特币区块链系统找到有效哈希值的时间间隔为10分钟,这是算法设置好的。算法难度每隔两周调整一次就是为了保证这10分钟的间隔,不能多也不能少。每隔10分钟,总账的信息就会在区块链更新并在全网同步一次。因此分散的交易记录是在所有网络上的计算机之间进行对账和同步的 [6] 

当个人用户在区块链系统发起一笔交易的时候,他们会使用私钥和公钥为这笔交易签名,而内嵌在比特币系统的标准公钥则承担了加密工具的角色,对应在拜占庭将军问题中,加密工具就是用于签名和验证消息的印章 [6] 

因此,哈希算法对信息传递速率的限制加上加密工具使得区块链构成了一个无须信任的数据交互系统。在区块链上,一系列的交易、时间约定、域名记录、政治投票系统或者任何其他需要建立分布式协议的地方,参与者都可以达成一致 [6] 

中本聪在比特币中创造性的引入了“工作量证明(POW : Proof of Work)”来解决这个问题,有兴趣可进一步阅读工作量证明

通过工作量证明就增加了发送信息的成本,降低节点发送消息速率,这样就以保证在一个时间只有一个节点(或是很少)在进行广播,同时在广播时会附上自己的签名。

这个过程就像一位将军A在向其他的将军(B、C、D…)发起一个进攻提议一样,将军B、C、D…看到将军A签过名的进攻提议书,如果是诚实的将军就会立刻同意进攻提议,而不会发起自己新的进攻提议。

以上就是比特币网络中是单个区块(账本)达成共识的方法(取得一致性)。

理解了单个区块取得一致性的方法,那么整个区块链(总账本)如果达成一致也好理解。

我们稍微把将军问题改一下:假设攻下一个城堡需要多次的进攻,每次进攻的提议必须基于之前最多次数的胜利进攻下提出的(只有这样敌方已有损失最大,我方进攻胜利的可能性就更大),这样约定之后,将军A在收到进攻提议时,就会检查一下这个提议是不是基于最多的胜利提出的,如果不是(基于最多的胜利)将军A就不会同意这样的提议,如果是的,将军A就会把这次提议记下来。

这就是比特币网络最长链选择

经济学分析

工作量证明其实相当于提高了做叛徒(发布虚假区块)的成本,在工作量证明下,只有第一个完成证明的节点才能广播区块,竞争难度非常大,需要很高的算力,如果不成功其算力就白白的耗费了(算力是需要成本的),如果有这样的算力作为诚实的节点,同样也可以获得很大的收益(这就是矿工所作的工作),这也实际就不会有做叛徒的动机,整个系统也因此而更稳定。

很多人批评工作量证明造成巨大的电力浪费,促使人们去探索新的解决一致性(共识)问题的机制:权益证明机制(POS: Proof of Stake)是一个代表。在拜占庭将军问题的角度来看,它同样提高了做叛徒的成本,因为账户需要首先持有大量余额才能有更多的几率广播区块,POS不是本文重点,以后在讲。

共识算法的核心就是解决拜占庭将军问题(分布式网络一致性问题)。

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