区块链学习笔记(2)——拜占庭将军问题与共识机制

一、拜占庭将军问题

拜占庭将军问题(Byzantine failures),是由莱斯利·兰伯特提出的点对点通信中的基本问题。含义是在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。因此对一致性的研究一般假设信道是可靠的,或不存在本问题。——摘自《百度百科》

1、起源

拜占庭帝国即中世纪的土耳其,拥有巨大的财富,周围10个邻邦垂诞已久,但拜占庭高墙耸立,固若金汤,没有一个单独的邻邦能够成功入侵。任何单个邻邦入侵的都会失败,同时也有可能自身被其他9个邻邦入侵。拜占庭帝国防御能力如此之强,至少要有十个邻邦中的一半以上同时进攻,才有可能攻破,也就是说,如果6个或者更多的邻邦一起发起进攻,就会成功并获取拜占庭的财富。然而,如果其中一个或者更多的邻邦发起背叛,答应一起入侵但在其他人进攻的时候又不干了,会导致只有5个或者更少的军队在同时进攻,那么所有的进攻军队都会被歼灭,并随后被其他邻邦所劫掠。因此,这是一个由互不信任的各个邻邦构成的分布式网络,每一方都小心行事,因为稍有不慎,就会给自已带来灾难。为了获取拜占庭的巨额财富,这些邻邦分散在拜占庭的周围,依靠士兵互相通信来协商进攻意向和进攻时间。——摘自《区块链,从数字货币到信用社会》

拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题,即消息传递的信道绝无问题。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以,在研究拜占庭将军问题的时候,已经假定了信道是没有问题的。==(联系CAP理论)==

拜占庭将军问题要解决的就是在一个互不信任的分布式环境下,如何就某一件事情达成共识。

2、解决方法
  • 口头协议算法

要求每个被发送的消息都能正确投递,信息接受者知道信息发送者的身份,知道缺少的消息信息。
口头协议的算法很简单,如果其中一个节点,比如1发布消息出去,2-10都接受到1的消息,然后2-10也分别转告给其他的节点,每个节点都是信息的转达者,一轮下来,每个节点手上都会有10个信息(进攻或者撤退),有叛徒的话,那信息可能有进攻或者不进攻的不一致消息。每个人相当于手里有一本消息的账本,该怎么决策呢?如果有一半以上的人说进攻,那么采取进攻行动就是能成功的,所以这时即便有叛徒,只要听大部分人的,少数服从多数来行动即是有利的。

这种口头协议的算法也存在明显的缺点:口头协议并不会告知消息的上一个来源是谁,也就是消息不可追根溯源,出现信息不一致也很难找到叛徒在哪。

  • 书面协议算法

可以假设10个国家,每个国家都可以派人向各个国家派信,比如一起约定“某天早上六点,大家一起进攻拜占庭,同意就签个字”。收到信的国家如果同意的话,就可以在原信上签名盖章。该算法要求签名不可伪造,一旦被篡改即可发现,同事任何人都可以验证该签名的可靠性。书面协议相比口头协议,所有的消息都是有记录的,解决了追根溯源的问题。
但是书面协议算法也不能完全解决拜占庭将军问题,因为该算法没有考虑信息传输延时、其签名体系难以实现且签名消息记录的保存难以摆脱中心化机构。

  • 终极解决方案:区块链技术

那么区块链技术是怎么解决这个问题的呢,它为发送信息加入了成本,降低了信息传递的速率,并加入了一个随机数以保证在一段时间内只有一个矿工可以进行传播。它加入的成本就是“工作量”,区块链矿工必须完成一个随机哈希算法的计算工作量才能向各个城邦传播消息。就相当于之前是每个城邦都可以发送进攻的消息,容易造成各说各的,难以达成共识,现在城邦想要发送信息的前提是证明你的工作量,谁第一个完成,谁才能传播消息。

二、共识机制

当前主流的共识机制包括:工作量证明、权益证明、股份授权证明等。

1、工作量证明

PoW(Proof of Work),即工作证明,通常是指在给定的约束下,求解一个特定难度的数学问题,谁解的速度快,谁就获得记账权。以比特币为例,工作量证明是矿工在处理交易数据(对数据也是进行哈希)的同时不断的进行哈希计算,求得一位前23位为0的哈希值,这个值成为nonce黄金数。当全网有一位矿工哈希出nonce时,他就会把自己打包的区块公布出去,其他节点收到区块验证区块后就会一致性认为这个区块接到了区块链上,就继续进行下一个区块的打包和哈希计算。在这个过程中,中本聪大神是通过算力的比拼牺牲了一部分最终一致性(因为会有分叉的产生)并且需要等待多个确认,但是这种简单暴力的方法却保证了整个区块链系统的合法性,而且把区块链系统的健壮性提升到极致,就算全网只剩下一个节点运行,这个区块链系统还是会继续运行下去。最后POW也充分提高了区块链系统的安全性,依靠51%攻击理论去破坏区块链系统是只有政府或者疯子才会采取的方法。

优点

  • 完全去中心化
  • 节点自由进出,容易实现
  • 破坏系统花费的成本巨大

缺点

  • 能源浪费,在挖矿的过程中需要耗费大量的硬件、电力成本
  • 出块时间较慢
  • 容易产生分叉

顺便提一点,关于怎么处理分叉的问题,如果有两个节点同时广播不同版本的新区块,那么其他节点在接收到该区块的时间上会存在先后差异,它们将在先收到的区块基础上进行工作,但也会保留另一个链条,以防后者变成更长的链条。当其中的一个链条被证实为较长的一条,那么在另一分支链条上工作的节点将会转换阵营,开始在较长的链条上工作。

有一个很直观的超市付款的例子,可以说明为何这种经济博弈模式会确保系统中最长链的唯一性。

假定超市只有一个出口,付款时需要排成一队,可能有人不守规矩要插队。超市管理员会检查队伍,认为最长的一条队伍是合法的,并让不合法的分叉队伍重新排队。新到来的人只要足够理智,就会自觉选择最长的队伍进行排队。这是因为,看到多条链的参与者往往认为目前越长的链具备越大的胜出可能性,从而更倾向于选择长的链。

2、权益证明

PoS(Proof of Stake),即股权证明,简单来说,PoS就是一个根据持有货币的量和时间来进行利息发放和区块产生的机制。在这种模式下,有一个名词叫币天,比如,每个币每天产生1币天,如果持有100个币,总共持有了30天,那么此时的币天就为3000。这个时候,如果发现了一个新的PoS区块,币天就会被清空为0。每被清空365币天,将会从区块中获得0.05个币的利息。

3、股份授权证明

DPoS(Delegated Proof of Stake),即股份授权证明,比特股的DPoS机制,中文名叫做股份授权证明机制(又称受托人机制),它的原理是让每一个持有比特股的人进行投票,由此产生101位代表,我们可以将其理解为101个超级节点或者矿池,而这101个超级节点彼此的权利是完全相等的。从某种角度来看,DPOS有点像是议会制度或人民代表大会制度。如果代表不能履行他们的职责(当轮到他们时,没能生成区块),他们会被除名,网络会选出新的超级节点来取代他们。

优点

  • 出块时间快,性能高
  • 更少的分叉

缺点

  • 不是完全的去中心化,实际权力掌握在受托人手中
如果您觉得有帮助到您,不妨考虑请作者喝杯咖啡鼓励一下。