区块链 PBFT 拜占庭将军问题

了解比特币或者区块链的朋友,可能都听说过拜占庭将军问题。那么,究竟什么是拜占庭将军问题呢?我们一起来探讨一下。

什么是拜占庭将军问题

也被称为“拜占庭容错”、“拜占庭将军问题”。 拜占庭将军问题(Byzantine Generals Problem),首先由Leslie Lamport与另外两人在1982年提出,很简单的故事模型,却困扰了计算机科学家们数十年。

故事大概是这样的:

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

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

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

在这个故事里,各邻国最致命的问题是:所有将军如何能达成共识去攻打拜占庭帝国。

在当时达成共识并非简单的事,有些将军心机叵测,一旦将军中出现叛徒,可能会出现各种问题:

  • 叛徒怂恿其他将军
  • 叛徒故意传播虚假进攻时间,迷惑其他将军

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

针对拜占庭问题的深入研究,科学家们得出一个结论:如果叛徒的数量大于或等于1/3,拜占庭问题不可解

大致可以这么理解:

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

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

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

当然,只要叛徒数小于1/3,问题还是可解的。

叛徒发送前后不一致的进攻提议,被称为“拜占庭错误”,而能够处理拜占庭错误的这种容错性称为「Byzantine fault tolerance」,简称为BFT。

区块链技术是怎么解决这个问题的:

在上面的故事中谁都可以发起进攻的信息,但由谁来发出呢?中本聪巧妙地在个系统加入了发送信息的成本,即:一段时间内只有一个节点可以传播信息。

中本聪在比特币中创造性的引入了“工作量证明(POW : Proof of Work)”来解决这个问题。

节点必须完成一个计算工作才能向各城邦传播消息,当然,谁第一个完成工作,谁才能传播消息。

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

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

  • 消息传送的私密性
  • 消息传送的私密性
  • 签名不可伪造、篡改

非对称加密算法的加密和解密使用不同的两个密钥.这两个密钥就是我们经常听到的”公开密钥”(公钥)和”私有密钥”(私钥).

公钥和私钥一般成对出现, 如果消息使用公钥加密,那么需要该公钥对应的私钥才能解密; 同样,如果消息使用私钥加密,那么需要该私钥对应的公钥才能解密.

非对称加密的作用是:保护消息内容, 并且让消息接收方确定发送方的身份.

比如,将军A想给将军B发送消息,为防止消息泄露,将军A只需要使用B的公钥对信息加密,而B的公钥是公开的,B只需要用只有他自己知道的私钥解密即可。

将军B想要在信件上声明自己的身份,他可以自己写一段”签名文本“,然后用私钥签名,并广播出去,所有人可以根据B的公钥来验证该签名,确定是B的身份。

由此,一个不可信的分布式网络变成了一个可信的网络,所有的参与者可以在某件事在达成一致。

只有第一个完成证明的节点才能广播区块,竞争难度非常大,需要很高的算力,如果不成功其算力就白白的耗费了(算力是需要成本的),有人说挖矿浪费了巨大的社会资源,但建立信任的成本可不是0,挖矿是维护比特币网络可靠性的最好办法。

在拜占庭的系统里,加入工作量证明,其实就是简单粗暴地引入了一个条件:大家都别忙着发起消息,先来做题,谁先把题做出来,谁就有资格第一个发起消息。

这个题必须是绝对公平的,中本聪在设计比特币时,它采用了一种工作量证明机制叫哈希现金,在一个交易块这要找到一个随机数,计算机只能用穷举法来找到这个随机数。

如果不同的将军先后解出了题,各自先后向这个网络发布消息,于是各个节点都会收到来自不同节点发起的进攻或者不进攻的消息,那怎么办的?只有时间最早的发起者才是有效的。中本聪巧妙的设计了一个时间戳的东西,为每个将军在解好题的时间(出块时间)盖上时间印章。

将军们那又凭什么要一起做工作量证明呢?中本聪也完全可以设置一个奖励机制,比特币的奖励机制是每打包一个块,目前是奖励12.5个比特币(四年减一次半),当然,拜占庭将军问题的奖励机制可以是瓜分拜占庭获得的利益。

那么,如果有出现背叛怎么办?

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

由此,在一个分布式的系统中,尽管有坏人,坏人可以做任意事情(不受protocol限制),比如不响应、发送错误信息、对不同节点发送不同决定、不同错误节点联合起来干坏事等等。但是,只要大多数人是好人,就完全有可能去中心化地实现共识。

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

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

到这里也可以知道了,基于互联网的区块链技术,它克服了口头协议与书面协议的种种缺点,使用消息加密技术、以及公平的工作量证明机制,创建了一组所有将军都认可的协议,这套协议的出现,拜占庭将军问题也就完美的得到了解决。

© 版权声明
THE END
喜欢就支持一下吧
点赞0
分享