比特家 > 名词 > 正文

名词解析丨拜占庭容错算法

拜占庭容错算法是理解区块链怎样达成共识的核心。

拜占庭将军问题是 (Byzantine Generals Problem)Leslie Lamport 1982 年发表的论文中提出用来描述分布式系统一致性问题的经典故事型案例。
比特币的共识机制就是由拜占庭将军问题衍生出来的。
这个故事大概如下:
拜占庭位于如今的土耳其的伊斯坦布尔,是东罗马帝国的首都。在当时拜占庭帝国非常强大,征战多年侵吞了很多小国家,所以地域广阔。在拜占庭帝国的周边有10个小国家,他们不堪忍受帝国的欺压,决定奋起反抗,大家一起出兵讨伐拜占庭帝国。可是每个国家的兵力与帝国相比实力相差悬殊,最少需要6个国家的将军带兵同时进攻才能取得胜利。他们之间距离相隔很远,只能依靠骑兵传递信息来统一进攻的时间。可是这里边也会有叛变的将军,他们会故意给出错误的信息。
那么问题来了,要怎么才能让忠诚的将军能够在进攻时间上达成一致并且能取得胜利?
为了得出一个普遍的结论,我们延伸假设总共有n个将军,叛徒将军有m个。
Lamport 证明了在将军总数大于3m+1 ,背叛者为m 或者更少时,即n>3m+1时,忠诚的将军可以达成命令上的一致。
例如n=10,m=3。能够满足上式10≥3×3+1。就意味着10位将军里的叛徒将军最多不能超过三个,忠诚的将军能够在进攻时间上达成一致决定,取得胜利。
Lamport这个问题里的将军就代表系统中的每个节点,其中叛徒将军即代表系统中的作恶节点,作恶节点会尽量不让系统达成一致性的意见。但经过算法上的证明,只要满足上式,好的节点是可以在系统中达成共识的。
这就是Byzantine Fault Tolerant (BFT) 算法。它能够容忍系统中有错误节点和错误信息的存在,只要在一定数量范围内,一致性终将达成。
拜占庭将军问题解决的过程相当困难,之所以难度这么大就是因为每个节点可以在不花费代价的情况下提出建议,提案成本相当低。
比特币中的共识机制POW就在BTF算法之上增加了提案成本,恶意节点传递的错误信息花费了巨大的算力但却不能得到回报,这有效地打击了恶意节点兴趣。

关于拜占庭,名词解析,区块链的相关新闻

区块链入门很简单 看这5份白皮书就懂了

一句话记住市值前100的加密货币

小白问答 | 区块链为什么需要跨链技术?

名词解析 | 什么是分片?

从尼克萨博被自动售货机“砸中” 到智能合约

主流货币

货币市值最高 24H涨幅最高

主流钱包

币信钱包 轻钱包 教程下载
Jaxx 轻钱包 教程下载
比特派 轻钱包 教程下载
IMTOKEN 轻钱包 教程下载
MyEtherWallet 网页钱包 教程下载

主流交易所

中文 人民币 交易方式
OKEX 币币法币
OTCBTC 币币法币
币安 币币法币
BitMEX 币币法币
火币Pro 币币法币