拜占庭将军与共识算法

  • R4y 
  • 未分类

随着自己慢慢对BlockChain的基本原理的深入了解,对区块链的基本原理也是慢慢的有了清晰的了解。对共识,PoW,的概念也是更加清晰了。所以以此文来总结一下

拜占庭将军问题

起源

首先什么是拜占庭将军(Byzantine failures)问题呢?这里引用一下百科:

拜占庭位于如今的土耳其的伊斯坦布尔,是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔,为了防御目的,因此每个军队都分隔很远,将军与将军之间只能靠信差传消息。 在战争的时候,拜占庭军队内所有将军和副官必需达成一致的共识,决定是否有赢的机会才去攻打敌人的阵营。但是,在军队内有可能存有叛徒和敌军的间谍,左右将军们的决定又扰乱整体军队的秩序。在进行共识时,结果并不代表大多数人的意见。这时候,在已知有成员谋反的情况下,其余忠诚的将军在不受叛徒的影响下如何达成一致的协议,拜占庭问题就此形成。

简单讲,就是一个军队中出了几个叛徒,我们怎么做,使得我们军队的意见表决的结果不会被这样叛徒改变。最终整个军队达成正确的共识。

区块链中

上面的就是拜占庭问题的起源,如果字多看着太麻烦,那么我们用自己的话简单的总结一下:

在我们的网络中存在着恶意节点,这些节点可能发送虚假的恶意消息,这样的节点我们就称之为拜占庭节点(Byzantine Node)。我们如何在网络存在着拜占庭节点的条件下保证我们整个区块链的所入链的区块依旧是正确的区块?也就是达成区块链共识,这样的问题就是我们区块链中的拜占庭将军问题。

实际上在区块链中,还有一类节点。他们可能出现故障(halting,crash),对外界的信息没有响应。这样的不会发出拜占庭信息的单点故障我们称之非拜占庭故障。

共识算法

在区块链里面,用于解决上述的问题的算法我们就称之共识算法(Consensus Algorithm)。

上面的节点分为拜占庭节点和 故障节点。所以我们的共识算法也是分为两大类:Crash Fault Tolerance(CFT)和 Byzantine Fault Tolerance(BFT)。我们直接翻译过来,这里就是故障容错 和 拜占庭容错

区块链上

了解了什么是共识算法之后,我们把它加在区块链上。像是比特币这样的公链(指的是人人可接入的区块链网络,类比于私链,联盟链)。由于其人人可接入的特性,当然导致了存在拜占庭节点的现象。可是我们的数据当然要保持绝对的正确,不能被拜占庭节点干扰。所以一个拜占庭容错的共识算法在比特币这一区块链体系下显得十分重要了!

一个简单的共识算法

这里贴上的代码是一个用Python实现一个简易的区块链的开源项目的代码节选。这代码就实现了一个十分简易的共识算法。项目地址在后面附上

这里随着段代码作一下分析。

def resolve_conflicts(self):"""这里是实现的一个简单的共识算法,这里是使用最长链来替换本地的链,实现区块链共识:return: True if our chain was replaced, False if not"""neighbours = self.nodesnew_chain = None# 找到我们自己的区块高度max_length = len(self.chain)# 获取并且验证我们在网络上得到的区块for node in neighbours:    response = requests.get(f'http://{node}/chain')        # 获取网络节点的完整链,    if response.status_code == 200:        length = response.json()['length']        # 得到区块高度        chain = response.json()['chain']        # 和当前的完整链        # 检查是否最长链,并且检验链的有效性        if length > max_length and self.valid_chain(chain):        # 最长链,并进行合法性检验            max_length = length                new_chain = chain#  如果有效且最长,我们替换我们的本地链if new_chain:    self.chain = new_chain    return Truereturn False

pyBlockChain项目地址(这个是笔者Fork的后面可能会自己拓展功能)

关于其具体的实现和分析可以笔者的之前的文章Py区块链源码笔记 (2)P2P网络


上面贴出的代码看上去十分简单,实际上也是十分简单。他意在在网络上站找到一个最长链,之后验证这个最长链的合法性(这点可以看看上面的文章的同一系列)。只要是合法的链,我们就直接替换掉我们的本地链。

可是这样的一个过程,到底是怎么解决区块链共识的问题呢?不就是要最长嘛,那我就编编编伪造一堆的虚假的区块数据让自己变得更长,那么不是轻轻松松在区块链实际翻云覆雨了,走上人生巅峰了??

真的有这么简单吗?答案不用说当然是否定的,我们伟大的Satoshi先生当然不会忽略这点。这样我们的一个新的名词就要因此而生了:

工作量证明(Proof of Work) 一般简写为PoW。


工作量证明的引入

前面讲到,如果是单单的最长链的替换,那么谁都可以编编编从而使得这个网络崩溃,这里的工作量证明(Proof of Work)机制,十分巧妙的解决了这个问题。PoW 是一种基于概率的共识算法

如果在链圈币圈混过的那么对挖矿这个词一定不会陌生,没错挖矿就是PoW!听着很奇怪?老套路去看看什么是挖矿/PoW把。

还是笔者之前写的文章,一样的是Pyhton的简单区块链

文章地址: Py区块链源码笔记 (1)挖矿


好,现在大家知道了什么是PoW了,那我们现在来看看这个共识到底是怎么实现的。刚刚说啥来着?我们需要找到网络中的最长链,那么我们就可以编对不对?现在一旦引入了PoW的机制,这样我们每个新的区块的产生是需要成本的,需要强大的Hash运算能力。所以我们编编编区块的这种想法是行不通的了

重点

那么我就自己计算嘛,自己编交易记录,自己计算自己把链编成可以吧?没错当然可以,不过现在体现比特币的去中心化的思想的时候就来了
记住,比特币是公链,在网络上的所有的人都可以参与挖矿,随着挖矿的人数越来越多,整个网络的运算能力在极大幅度的提高。

那么由于Hash是不存在启发式算法的,所以谁的运算能力强,谁的爆块概率就大,这是线性的!所以算力强的就有大几率变成最长的区块。

所以可以看见,如果真的有一个拜占庭节点,想伪造区块记录,那么要有个必须条件:他必须具有极为强大的算力,使得自己的链始终是全网最长的,因为只有最长的链才会被矿工认为是有效的链!那么我不具有极为强的算力,在网络上编造的任何的区块都会是无效的。这便是比特币网络上的拜占庭容错

51% Attack

任何的容错机制都会有他的容错率,我们的比特币也是不例外的。51% 攻击就是比特币系统目前可见的最大的威胁。

一提到对比特币的攻击,大部分人想到的就是51%攻击。所谓51%攻击,就是利用比特币使用算力作为竞争条件的特点,使用算力优势撤销自己已经发生的付款交易。如果有人掌握了50%以上的算力,他能够比其他人更快地找到开采区块需要的那个随机数,因此他实际上拥有了绝对哪个一区块的有效权利。

他能够:

  1. 修改自己的交易记录,这可以使他进行双重支付
  2. 阻止区块确认部分或者全部交易
  3. 阻止部分或全部矿工开采到任何有效的区块

但是他无法做到:

  1. 修改其他人的交易记录
  2. 阻止交易被发出去(交易会被发出,只是显示0个确认而已)
  3. 改变每个区块产生的比特币数量
  4. 凭空产生比特币
  5. 把不属于他的比特币发送给自己或其他人

历史上已经发生过了51%攻击的案例了!

25% 威胁

比特币的自私挖矿

后面的话

本来是想找到BTC代码较以分析的,发现。。。还是有点困难。只能作罢。写博文的同时自己也是慢慢熟悉了和了解了这样的一个系统的精妙之处。
博文显得比较粗浅,笔者也是初学者,只能从较感性的层面分析这个逻辑的原理。后面也许会有深入理解系列

留下点什么吧