Hi Guest

More contents, please log on!

Bitmere.com 区块链前沿 Content

拜占庭容错(BFT)技术详解

wxf2017
27 0 0
拜占庭将军问题

    BFT技术的由来源于一个叫拜占庭将军问题。

    拜占庭位于如今的土耳其的伊斯坦布尔,是东罗马帝国的首都,由于当时拜占庭罗马帝国国土辽阔,每支军队的驻地分隔很远,将军们只能靠信使传递消息。发生战争时,将军们必须制订统一的行动计划。然而,这些将军中有叛徒,叛徒希望通过影响统一行动计划的制定与传播,破坏忠诚的将军们一致的行动计划。因此,将军们必须有一个预定的方法协议,使所有忠诚的将军能够达成一致,而且少数几个叛徒不能使忠诚的将军做出错误的计划。也就是说,拜占庭将军问题的实质就是要寻找一个方法,使得将军们能在一个有叛徒的非信任环境中建立对战斗计划的共识,拜占庭问题就此形成。

    拜占庭将军问题(ByzantineGeneralsProblem),首先由LeslieLamport与另外两人在1982年提出,很简单的故事模型,却困扰了计算机科学家们数十年。

    我们将拜占庭将军问题简化一下,所有忠诚的将军都能够让别的将军接收到自己的真实意图,并最终一致行动;而形式化的要求就是,“一致性”与“正确性”。

    一致性:每个忠诚的将军必须收到相同的命令值vi(vi是第i个将军的命令)

    正确性:如果第i个将军是忠诚的,那么他发送的命令和每个忠诚将军收到的vi相同。

    Lamport对拜占庭将军的问题的研究表明,当n>3m时,即叛徒的个数m小于将军总数的n的1/3时,通过口头同步通信(假设通信是可靠的),可以构造同时满足“一致性”和“正确性”的解决方法,即将军们可以达成一致的命令。

    拜占庭容错理论算法

    拜占庭容错系统,英文全称是ByzantineFaultTolerance,是一种理论上解决拜占庭问题的方法,并非实用,不过基于BFT理论延伸出了其他共识机制。

    区块链网络的记账共识和拜占庭将军的问题是相似的。参与共识记账的每一个节点相当于将军,节点之间的消息传递相当于信使,某些节点可能由于各种原因而产生错误的信息传递给其他节点。通常这些发生故障的节点被称为拜占庭节点,而正常的节点即为非拜占庭节点。

    假设分布式系统拥有n台节点,并假设整个系统拜占庭节点不超过m台(n≥3m+1),拜占庭容错系统需要满足如下两个条件:

    所有非拜占庭节点使用相同的输入信息,产生同样的结果。在区块链系统中,可以理解为,随机数相同、区块算法相同、原账本相同的时候,计算结果相同。

    如果输入的信息正确,那么所有非拜占庭节点必须接收这个消息,并计算相应的结果。在区块链系统中,可以理解为,非拜占庭节点需要对客户的请求进行计算并生成区块。

    另外,拜占庭容错系统需要达成如下两个指标:

    安全性:任何已经完成的请求都不会被更改,它可以在以后请求看到。在区块链系统中,可以理解为,已经生成的账本不可篡改,并且可以被节点随时查看。

    活性:可以接受并且执行非拜占庭客户端的请求,不会被任何因素影响而导致非拜占庭客户端的请求不能执行。在区块链系统中,可以理解为,系统需要持续生成区块,为用户记账,这主要靠挖矿的激励机制来保证。

    在分析拜占庭问题的时候,假设信道是可信的。拓展开来,在拜占庭容错系统,普遍采用的假设条件包括:

    拜占庭节点的行为可以是任意的,拜占庭节点之间可以共谋;

    节点之间的错误是不相关的;

    节点之间通过异步网络连接,网络中的消息可能丢失、乱序并延时到达,但大部分协议假设消息在有限的时间里能传达到目的地;

    节点之间传递的信息,第三方可以嗅探到,但是不能篡改、伪造信息的内容和破坏信息的完整性。

    拜占庭容错技术,是一类分布式计算领域的容错技术。名称拜占庭是一个泛指,它代表着计算机领域,在这个领域内会有很多问题,如硬件错误、网络拥堵或中断以及遭到恶意攻击等等,造成计算机网络可能出现的混乱。BFT技术就是为了使混乱状态达到一致性。
BitMere.com is Information release platform,just provides information storage space services.
The opinions expressed are solely those of the author,Does not constitute advice, please treat with caution.
You have to log in before you can reply Login | 立即注册

Points Rules

Write the first review

wxf2017 初中生
  • Follow

    0

  • Following

    0

  • Articles

    21

币圈江左盟
Promoted