摘要：区块链拜占庭将军问题详解『壹』区块链---共识算法PoW算法是一种防止分布式服务资源被滥用、拒绝服务攻击的机制。它要求节点进行适量消耗时间和资源的复杂运...

区块链拜占庭将军问题详解

『壹』 区块链 --- 共识算法

PoW算法是一种防止分布式服务资源被滥用、拒绝服务攻击的机制。它要求节点进行适量消耗时间和资源的复杂运算，并且其运算结果能被其他节点快速验算，以耗用时间、能源做担保，以确保服务与资源被真正的需求所使用。

PoW算法中最基本的技术原理是使用哈希算法。假设求哈希值Hash(r)，若原始数据为r（raw），则运算结果为R（Result）。

R = Hash(r)

哈希函数Hash()的特性是，对于任意输入值r，得出结果R，并且无法从R反推回r。当输入的原始数据r变动1比特时，其结果R值完全改变。在比特币的PoW算法中，引入算法难度d和随机值n，得到以下公式：

Rd = Hash(r+n)

该公式要求在填入随机值n的情况下，计算结果Rd的前d字节必须为0。由于哈希函数结果的未知性，每个矿工都要做大量运算之后，才能得出正确结果，而算出结果广播给全网之后，其他节点只需要进行一次哈希运算即可校验。PoW算法就是采用这种方式让计算消耗资源，而校验仅需一次。

PoS算法要求节点验证者必须质押一定的资金才有挖矿打包资格，并且区域链系统在选定打包节点时使用随机的方式，当节点质押的资金越多时，其被选定打包区块的概率越大。

POS模式下，每个币每天产生1币龄，比如你持有100个币，总共持有了30天，那么，此时你的币龄就为3000。这个时候，如果你验证了一个POS区块，你的币龄就会被清空为0，同时从区块中获得相对应的数字货币利息。

节点通过PoS算法出块的过程如下：普通的节点要成为出块节点，首先要进行资产的质押，当轮到自己出块时，打包区块，然后向全网广播，其他验证节点将会校验区块的合法性。

DPoS算法和PoS算法相似，也采用股份和权益质押。

但不同的是，DPoS算法采用委托质押的方式，类似于用全民选举代表的方式选出N个超级节点记账出块。

选民把自己的选票投给某个节点，如果某个节点当选记账节点，那么该记账节点往往在获取出块奖励后，可以采用任意方式来回报自己的选民。

这N个记账节点将轮流出块，并且节点之间相互监督，如果其作恶，那么会被扣除质押金。

通过信任少量的诚信节点，可以去除区块签名过程中不必要的步骤，提高了交易的速度。
 

拜占庭问题：

拜占庭是古代东罗马帝国的首都，为了防御在每块封地都驻扎一支由单个将军带领的军队，将军之间只能靠信差传递消息。在战争时，所有将军必须达成共识，决定是否共同开战。

但是，在军队内可能有叛徒，这些人将影响将军们达成共识。拜占庭将军问题是指在已知有将军是叛徒的情况下，剩余的将军如何达成一致决策的问题。

BFT：

BFT即拜占庭容错，拜占庭容错技术是一类分布式计算领域的容错技术。拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或中断以及遭到恶意攻击等原因，计算机和网络可能出现不可预料的行为。拜占庭容错技术被设计用来处理这些异常行为，并满足所要解决的问题的规范要求。

拜占庭容错系统 ：

发生故障的节点被称为 拜占庭节点 ，而正常的节点即为 非拜占庭节点 。

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

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

PBFT即实用拜占庭容错算法，解决了原始拜占庭容错算法效率不高的问题，算法的时间复杂度是O(n^2)，使得在实际系统应用中可以解决拜占庭容错问题
 

PBFT是一种状态机副本复制算法，所有的副本在一个视图（view）轮换的过程中操作，主节点通过视图编号以及节点数集合来确定，即：主节点 p = v mod |R|。v：视图编号，|R|节点个数，p：主节点编号。

PBFT算法的共识过程如下：客户端（Client）发起消息请求（request），并广播转发至每一个副本节点（Replica），由其中一个主节点（Leader）发起提案消息pre-prepare，并广播。其他节点获取原始消息，在校验完成后发送prepare消息。每个节点收到2f+1个prepare消息，即认为已经准备完毕，并发送commit消息。当节点收到2f+1个commit消息，客户端收到f+1个相同的reply消息时，说明客户端发起的请求已经达成全网共识。

具体流程如下 ：

客户端c向主节点p发送<REQUEST, o, t, c>请求。o: 请求的具体操作，t: 请求时客户端追加的时间戳，c：客户端标识。REQUEST: 包含消息内容m，以及消息摘要d(m)。客户端对请求进行签名。

主节点收到客户端的请求，需要进行以下交验：

a. 客户端请求消息签名是否正确。

非法请求丢弃。正确请求，分配一个编号n，编号n主要用于对客户端的请求进行排序。然后广播一条<<PRE-PREPARE, v, n, d>, m>消息给其他副本节点。v：视图编号，d客户端消息摘要，m消息内容。<PRE-PREPARE, v, n, d>进行主节点签名。n是要在某一个范围区间内的[h, H]，具体原因参见 垃圾回收 章节。

副本节点i收到主节点的PRE-PREPARE消息，需要进行以下交验：

a. 主节点PRE-PREPARE消息签名是否正确。

b. 当前副本节点是否已经收到了一条在同一v下并且编号也是n，但是签名不同的PRE-PREPARE信息。

c. d与m的摘要是否一致。

d. n是否在区间[h, H]内。

非法请求丢弃。正确请求，副本节点i向其他节点包括主节点发送一条<PREPARE, v, n, d, i>消息, v, n, d, m与上述PRE-PREPARE消息内容相同，i是当前副本节点编号。<PREPARE, v, n, d, i>进行副本节点i的签名。记录PRE-PREPARE和PREPARE消息到log中，用于View Change过程中恢复未完成的请求操作。

主节点和副本节点收到PREPARE消息，需要进行以下交验：

a. 副本节点PREPARE消息签名是否正确。

b. 当前副本节点是否已经收到了同一视图v下的n。

c. n是否在区间[h, H]内。

d. d是否和当前已收到PRE-PPREPARE中的d相同

非法请求丢弃。如果副本节点i收到了2f+1个验证通过的PREPARE消息，则向其他节点包括主节点发送一条<COMMIT, v, n, d, i>消息，v, n, d, i与上述PREPARE消息内容相同。<COMMIT, v, n, d, i>进行副本节点i的签名。记录COMMIT消息到日志中，用于View Change过程中恢复未完成的请求操作。记录其他副本节点发送的PREPARE消息到log中。

主节点和副本节点收到COMMIT消息，需要进行以下交验：

a. 副本节点COMMIT消息签名是否正确。

b. 当前副本节点是否已经收到了同一视图v下的n。

c. d与m的摘要是否一致。

d. n是否在区间[h, H]内。

非法请求丢弃。如果副本节点i收到了2f+1个验证通过的COMMIT消息，说明当前网络中的大部分节点已经达成共识，运行客户端的请求操作o，并返回<REPLY, v, t, c, i, r>给客户端，r：是请求操作结果，客户端如果收到f+1个相同的REPLY消息，说明客户端发起的请求已经达成全网共识，否则客户端需要判断是否重新发送请求给主节点。记录其他副本节点发送的COMMIT消息到log中。
 

如果主节点作恶，它可能会给不同的请求编上相同的序号，或者不去分配序号，或者让相邻的序号不连续。备份节点应当有职责来主动检查这些序号的合法性。

如果主节点掉线或者作恶不广播客户端的请求，客户端设置超时机制，超时的话，向所有副本节点广播请求消息。副本节点检测出主节点作恶或者下线，发起View Change协议。

View Change协议 ：

副本节点向其他节点广播<VIEW-CHANGE, v+1, n, C , P , i>消息。n是最新的stable checkpoint的编号， C 是 2f+1验证过的CheckPoint消息集合， P 是当前副本节点未完成的请求的PRE-PREPARE和PREPARE消息集合。

当主节点p = v + 1 mod |R|收到 2f 个有效的VIEW-CHANGE消息后，向其他节点广播<NEW-VIEW, v+1, V , O >消息。 V 是有效的VIEW-CHANGE消息集合。 O 是主节点重新发起的未经完成的PRE-PREPARE消息集合。PRE-PREPARE消息集合的选取规则：

副本节点收到主节点的NEW-VIEW消息，验证有效性，有效的话，进入v+1状态，并且开始 O 中的PRE-PREPARE消息处理流程。
 

在上述算法流程中，为了确保在View Change的过程中，能够恢复先前的请求，每一个副本节点都记录一些消息到本地的log中，当执行请求后副本节点需要把之前该请求的记录消息清除掉。

最简单的做法是在Reply消息后，再执行一次当前状态的共识同步，这样做的成本比较高，因此可以在执行完多条请求K（例如：100条）后执行一次状态同步。这个状态同步消息就是CheckPoint消息。

副本节点i发送<CheckPoint, n, d, i>给其他节点，n是当前节点所保留的最后一个视图请求编号，d是对当前状态的一个摘要，该CheckPoint消息记录到log中。如果副本节点i收到了2f+1个验证过的CheckPoint消息，则清除先前日志中的消息，并以n作为当前一个stable checkpoint。

这是理想情况，实际上当副本节点i向其他节点发出CheckPoint消息后，其他节点还没有完成K条请求，所以不会立即对i的请求作出响应，它还会按照自己的节奏，向前行进，但此时发出的CheckPoint并未形成stable。

为了防止i的处理请求过快，设置一个上文提到的 高低水位区间[h, H] 来解决这个问题。低水位h等于上一个stable checkpoint的编号，高水位H = h + L，其中L是我们指定的数值，等于checkpoint周期处理请求数K的整数倍，可以设置为L = 2K。当副本节点i处理请求超过高水位H时，此时就会停止脚步，等待stable checkpoint发生变化，再继续前进。
 

在区块链场景中，一般适合于对强一致性有要求的私有链和联盟链场景。例如，在IBM主导的区块链超级账本项目中，PBFT是一个可选的共识协议。在Hyperledger的Fabric项目中，共识模块被设计成可插拔的模块，支持像PBFT、Raft等共识算法。
 

Raft基于领导者驱动的共识模型，其中将选举一位杰出的领导者(Leader)，而该Leader将完全负责管理集群，Leader负责管理Raft集群的所有节点之间的复制日志。
 

下图中，将在启动过程中选择集群的Leader（S1），并为来自客户端的所有命令/请求提供服务。 Raft集群中的所有节点都维护一个分布式日志（复制日志）以存储和提交由客户端发出的命令（日志条目）。 Leader接受来自客户端的日志条目，并在Raft集群中的所有关注者（S2，S3，S4，S5）之间复制它们。

在Raft集群中，需要满足最少数量的节点才能提供预期的级别共识保证， 这也称为法定人数。 在Raft集群中执行操作所需的最少投票数为 (N / 2 +1) ，其中N是组中成员总数，即 投票至少超过一半 ，这也就是为什么集群节点通常为奇数的原因。 因此，在上面的示例中，我们至少需要3个节点才能具有共识保证。

如果法定仲裁节点由于任何原因不可用，也就是投票没有超过半数，则此次协商没有达成一致，并且无法提交新日志。

数据存储：Tidb/TiKV

日志：阿里巴巴的 DLedger

服务发现：Consul& etcd

集群调度：HashiCorp Nomad
 

只能容纳故障节点(CFT)，不容纳作恶节点

顺序投票，只能串行apply，因此高并发场景下性能差
 

Raft通过解决围绕Leader选举的三个主要子问题，管理分布式日志和算法的安全性功能来解决分布式共识问题。

当我们启动一个新的Raft集群或某个领导者不可用时，将通过集群中所有成员节点之间协商来选举一个新的领导者。 因此，在给定的实例中，Raft集群的节点可以处于以下任何状态: 追随者(Follower)，候选人(Candidate)或领导者(Leader)。

系统刚开始启动的时候，所有节点都是follower，在一段时间内如果它们没有收到Leader的心跳信号，follower就会转化为Candidate；

如果某个Candidate节点收到大多数节点的票，则这个Candidate就可以转化为Leader，其余的Candidate节点都会回到Follower状态；

一旦一个Leader发现系统中存在一个Leader节点比自己拥有更高的任期(Term)，它就会转换为Follower。

Raft使用基于心跳的RPC机制来检测何时开始新的选举。 在正常期间， Leader 会定期向所有可用的 Follower 发送心跳消息（实际中可能把日志和心跳一起发过去）。 因此，其他节点以 Follower 状态启动，只要它从当前 Leader 那里收到周期性的心跳，就一直保持在 Follower 状态。

当 Follower 达到其超时时间时，它将通过以下方式启动选举程序：

根据 Candidate 从集群中其他节点收到的响应，可以得出选举的三个结果。

共识算法的实现一般是基于复制状态机（Replicated state machines），何为 复制状态机 ：

简单来说： 相同的初识状态 + 相同的输入 = 相同的结束状态 。不同节点要以相同且确定性的函数来处理输入，而不要引入一下不确定的值，比如本地时间等。使用replicated log是一个很不错的注意，log具有持久化、保序的特点，是大多数分布式系统的基石。

有了Leader之后，客户端所有并发的请求可以在Leader这边形成一个有序的日志（状态）序列，以此来表示这些请求的先后处理顺序。Leader然后将自己的日志序列发送Follower，保持整个系统的全局一致性。注意并不是强一致性，而是 最终一致性 。

日志由有序编号（log index）的日志条目组成。每个日志条目包含它被创建时的任期号（term），和日志中包含的数据组成，日志包含的数据可以为任何类型，从简单类型到区块链的区块。每个日志条目可以用[ term, index, data]序列对表示，其中term表示任期， index表示索引号，data表示日志数据。

Leader 尝试在集群中的大多数节点上执行复制命令。 如果复制成功，则将命令提交给集群，并将响应发送回客户端。类似两阶段提交(2PC)，不过与2PC的区别在于，leader只需要超过一半节点同意（处于工作状态）即可。

leader 、 follower 都可能crash，那么 follower 维护的日志与 leader 相比可能出现以下情况

当出现了leader与follower不一致的情况，leader强制follower复制自己的log， Leader会从后往前试 ，每次AppendEntries失败后尝试前一个日志条目（递减nextIndex值）， 直到成功找到每个Follower的日志一致位置点（基于上述的两条保证），然后向后逐条覆盖Followers在该位置之后的条目 。所以丢失的或者多出来的条目可能会持续多个任期。
 

要求候选人的日志至少与其他节点一样最新。如果不是，则跟随者节点将不投票给候选者。

意味着每个提交的条目都必须存在于这些服务器中的至少一个中。如果候选人的日志至少与该多数日志中的其他日志一样最新，则它将保存所有已提交的条目，避免了日志回滚事件的发生。

即任一任期内最多一个leader被选出。这一点非常重要，在一个复制集中任何时刻只能有一个leader。系统中同时有多余一个leader，被称之为脑裂（brain split），这是非常严重的问题，会导致数据的覆盖丢失。在raft中，两点保证了这个属性：

因此， 某一任期内一定只有一个leader 。
 

当集群中节点的状态发生变化（集群配置发生变化）时，系统容易受到系统故障。 因此，为防止这种情况，Raft使用了一种称为两阶段的方法来更改集群成员身份。 因此，在这种方法中，集群在实现新的成员身份配置之前首先更改为中间状态（称为联合共识）。 联合共识使系统即使在配置之间进行转换时也可用于响应客户端请求，它的主要目的是提升分布式系统的可用性。

『贰』 区块链的技术原理是什么

区块链技术涉及的关键点包括：去中心化（册芦陪Decentralized）、去信任（Trustless）、集体维护（Collectivelymaintain）、可靠数据库（ReliableDatabase）、时间戳（Timestamp）、非对称加密（AsymmetricCryptography）等。

区块链技术重新定义了网络中信用的生成方式：在系统中，参与者无需了解其他人的背景资料，也不需要借助第三方机构的担保或保证，区块链技术保障了系统对价值转移的活动进行记录、传输、存储，其最后的结果一定是可信的。

(2)区块链拜占庭将军问题详解扩展阅读

区块链技术原理的来源可归纳为一个数学问题：拜占庭将军问题。拜占庭将军问题延伸到互联网生活中来，其内涵可概括为：在互联网大背景下，当需要与不熟悉的对手方进行价值交换活动时，人们如何才能防止不会被其中的恶意破坏者欺骗、迷惑从而做出错误的决策。

进一步将拜占庭将军问题延伸到技术领域中来，其内涵可概括为：在缺少可信任州蠢的中央节点和可信任的通道的情况哗此下，分布在网络中的各个节点应如何达成共识。区块链技术解决了闻名已久的拜占庭将军问题——它提供了一种无需信任单个节点、还能创建共识网络的方法。

『叁』 三. 区块链系统的核心之一-分布式共识机制

        拜占庭将军问题（Byzantine Generals Problem），是由莱斯利·兰波特在其同名论文中提出的分布式对等网络通信容错问题。

        在分布式计算中，不同的计算机通过通讯交换信息达成共识而按照同一套协作策略行动。但有时候，系统中的成员计算机可能出错而发送错误的信息，用于传递信息的通讯网络也可能导致信息损坏，使得网络中不同的成员关于全体协作的策略得出不同结论，从而破坏系统一致性。这个难题被称为“拜占庭容错”，或者“两军问题”。

        拜占庭假设是对现实世界的模型化。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。拜占庭容错协议要求能够解决由于硬件错误、网络拥塞或断开以及遭到恶意攻击，其他计算机和网络可能出现不可预料的行为而带来的各种问题。并且拜占庭容错协议还要满足所要解决的问题要求的规范。

        在拜占庭时代有一个墙高壁厚的城邦——拜占庭，高墙之内存放在世人无法想象多的财富。拜占庭被其他10个城邦所环绕，这10个城邦也很富饶，但和拜占庭相比就有天壤之别了。

        拜占庭的十个邻居都觊觎它的财富，并希望侵略并占领它。但是，拜占庭的防御非常强大，任何单个城邦的入侵行动都会失败，而入侵者的军队也会被歼灭，使得该城邦自身遭到其他互相觊觎对方的九个城邦的入侵和劫掠。

        拜占庭的防御很强，十个城邦中要有一半以上同时进攻才能攻破它。也就是说，如果有六个或者以上的相邻城邦一起进攻，他们就会成功并获得拜占庭的财富。然而，如果其中有一个或者更多城邦背叛了其他城邦，答应一起入侵但在其他城邦进攻的时候又不干了，也就导致只有五支或者更少的城邦的军队在同时进攻，那么所有的进攻城邦的军队都会被歼灭，并随后被其他的（包括背叛他们的那（几）个）城邦所入侵和劫掠。

        这是一个由许多不互相信任的城邦构成的一个网络。城邦们必须一起努力以完成共同的使命。而且，各个城邦之间通讯和协调的唯一途径是通过信使骑马在城邦之间传递信息。城邦的决策者们无法聚集在一个地方开个会（所有的城邦的决策者都不互相信任自己的安全会在自己的城堡或者军队范围之外能够得到保障）。

        城邦的决策者可以在任意时间以任意频率派出任意数量的信使到任意的对方。每条信息都包含如下的内容：“我城邦将在某一天的某个时间发动进攻，你城邦愿意加入吗？”。如果收信城邦同意了，该城邦就会在原信上附上一份签名了的或盖了图章的（以就是验证了的）回应然送回发信城邦。然后，再把新合并了的信息的拷贝一一发送给其他八个城邦，要求他们也如此这样做。最后的目标是，通过在原始信息链上盖上他们所有十个城邦的决策者的图章，让他们在时间上达成共识。最后的结果是，会有一个盖有十个同意同一时间发动进攻的图章信息包，和一些被抛弃了的包含部分但不是全部图章的信息包。

        在这个过程中首先出现了第一个问题，就是如果每个城邦向其他九个城邦派出一名信使，那么就是十个城邦每个派出了九名信使，也就是在任何一个时间又总计90次的传输，并且每个城市分别收到九个信息，可能每一封都写着不同的进攻时间。

        在这个过程中还有第二个问题，就是部分城邦会答应超过一个的攻击时间，故意背叛进攻发起人，所以他们将重新广播超过一条（甚至许许多多条）的信息包，由此产生许多甚至无数的足以淹没一切的杂音。

        有了以上两个问题，整个网络系统可能迅速变质，并演变成不可信的信息和攻击时间相互矛盾的纠结体。

         拜占庭假设是对现实网络世界的一种模型化。在现实网络世界中由于硬件错误、网络拥塞或断开以及遭到恶意攻击，网络可能出现许许多多不可预料的行为。拜占庭容错协议必须处理这些失效，并且还要使这些协议满足所要解决的问题所要求的规范。

        对于拜占庭将军问题中本聪的区块链给出了比较圆满的解决方案。也就是比较圆满的解决了上述的两个问题。

        拜占庭将军问题的第一个问题从本质上来讲就是时间和空间的障碍导致信息的不准确和不及时。

        区块链对于第一个问题的解决方案是利用分布式存储技术和比特流技术（BT技术，一种新型的点对点传输技术，具有节点同时作为客户端和服务器端和没有中心服务器等特点），将整个网络系统内的所有交易信息汇总为一个统一的，分布式存储的，近乎实时同步更新的电子总账。统一的分布式共同账本就解决了空间障碍问题；而近乎同步进行的，实时的，持续的对所有账本备份的更新、对账则解决了时间障碍问题。

        这个过程较具体一点的描述大概是将区块链系统内所有的交易活动的记录数据统一于一种标准化的总帐上；区块链系统的每一个节点都会保存一份总帐的备份；所有总帐的备份都是在实时的，持续的更新、对账、以及同步着。区块链系统的每一个节点能在这本总帐里记上添加记录；每一笔新添加的记录都会实时的广播到区块链系统内；所以在每一个节点上的每一份总帐的备份都是几乎同时更新的，并且所有的总帐的备份保持着同步。

        拜占庭将军问题的第二个问题从本质上来讲就是关于信息过量问题和信息干扰问题。信息过量和信息干扰问题导致决策延迟，甚至决策系统崩溃而无法决策。

        区块链对于第二个问题的解决方案是区块链系统的任何一个节点在发送每一笔新添加的记录时需要附带一条额外的信息。对区块链系统的任何一个节点来说这条额外的信息的获得都是有成本的，并且只能有一个节点可以获得。这样就解决了区块链系统的任何一个节点新添加额外信息时的信息多且乱而无法达成一致的问题。在这里，区块链系统的任何一个节点获得那条附带的额外的信息的过程就是著名的工作量证明机制。

        共识机制主要解决区块链系统的数据如何记录和如何保存的问题。工作量证明机制就是要求区块链系统的节点通过做一定难度的工作得出一个结果的过程。

        区块链系统中某节点生成了一笔新的交易记录，并且该节点将这笔新的交易记录向全网广播。全网各个节点收到这个交易记录并与其他所有准备打包进区块的交易记录共同组成交易记录列表。在列表内先对所有交易进行两两的哈希计算；再对以获得的哈希值进行哈希计算获得Merkle树和Merkle树的根值；把Merkle树的根值及其他相关字段组装成区块头。

        各个节点将区块头的80字节数据加上一个不停的变更的区块头随机数一起进行不停的哈希运算（实际上这是一个双重哈希运算）；不停的将哈希运算结果值与当前网络的目标值做对比，直到哈希运算结果值小于目标值，就获得了符合要求的哈希值，工作量证明也就完成了。

         分布式的区块链系统是一个动态变化的系统（硬件的运算速度的增长，节点参与网络的程度的变化）。系统的不断变化必然带来系统的算力的不断变化。而算力的变化又会导致通过消耗算力（工作）来获得符合要求的哈希值的速度的不同。最终的结果会是区块链的增长速度会有巨大的不同。这是一个很大的问题。为了解决这个问题，区块链系统自动根据算力的变化对工作难度进行调整。也就是采用移动平均目标的方法来确定，难度控制为每小时生成区块的速度为某一个预定的平均数。

        在区块链系统中一个符合要求的哈希值是由N个前导零构成，零的个数取决于网络的难度值。为了使区块的形成时间控制在大约十分钟左右，区块链系统采用了固定工作难度的难度算法。难度值每2016个区块调整一次零的个数。

        新的难度值是根据前2015个区块（理论上应该是2016个区块，由于当初程序编写时的失误造成了用2015而不是2016）的出块时间来计算。

        难度 = 目标值 * 前2015个区块生成所用的时间 / 1209600 （两周的秒钟数）

        这样通过规定的算法，区块链系统就保证所有节点计算出的难度值都一致，区块的形成时间大约一致在十分钟左右。

      （1）结果不可控制。其依赖机器进行哈希函数的运算来获得结果；计算结果是一个随机数；没有人能直接控制计算的结果。

      （2）计算具有对称性。就是结果的获得和结果的验收需要的工作量是不同的。计算出结果所需要的工作量远远大于验收结果所需要的工作量。

      （3）计算的难度自动控制。为了使区块的形成时间控制在大约十分钟左右，区块链系统自动控制了每一个符合要求的哈希获得为大约在十分钟左右。

         第一，方法简单易行。

        第二，系统达成共识容易，节点间不需要太多的信息交换。

        第三，系统比较牢固可靠，任何破坏系统的企图都需要投入大到得不偿失的成本。

        第一，消耗大量的算力，也就是浪费能源和其他资源。

        第二，区块的确认时间比较长，并且难以缩短。

        第三，新创立的区块链非常容易受到算力攻击。

        第四，容易产生区块链分叉，稳定的区块链需要多个确认，并且这种状况可能不断持续下去。

        第五，算力的逐渐集中导致与去中心化的系统设计基础的冲突日益明显。

        权益证明机制是一种工作量证明机制的替代方法，试图解决工作量计算浪费的问题.目前其成功的应用是点点币区块链系统。

        权益证明不要求区块链系统的节点完成一定数量的计算工作，而是要求区块链系统的节点对某些数量的钱展示所有权。

        权益证明机制首先应用于点点币区块链系统中。

        点点币区块链系统的区块生成时，节点需要构造一个“钱币权益”交易，即把自己的一些钱币和预先设定的奖励发给自己。进行哈希计算时，哈希值的计算只同交易输入、一些附加的固定数据以及当前时间（是一个表示自1970年1月1日距离当前时刻的秒数的正数）有关。然后，根据类似工作量证明的要求来检查这个哈希值是否正确。

        点点币区块链系统的权益证明机制除了设定了哈希计算难度与交易输入的“币龄”成反比外，其与工作量证明机制非常类似。其中，币龄的定义为交易输入大小和它存在时间的乘积。权益证明机制中哈希值只和时间和固定的数据有关，因而没有办法通过多完成工作来快速获取它。

       每个点点币区块链系统的交易的输出都有一定的几率来产生有效的正比于币龄和交易货币数量的工作。

        第一，缩短了共识达成的时间。

        第二，不再需要大量消耗能源。

        第一，还是需要哈希计算。

        第二，所有的确认都只是一个概率上的表达，而不是一个确定性的事情，有可能受到其他攻击影响。

        授权股份证明机制类似于权益证明机制，是比特股BitShares采用的区块链公识算法。授权股份证明机制是民主选举和轮流执政相结合方式来确定区块的产生。

        授权股份证明机制是先由节点选举若干代理人，由代理人验证和记账。其他方面和权益证明机制相似。

        每个节点按其持股比例拥有相应的影响力，51%节点投票的结果将是不可逆且有约束力的。为达到及时而高效的方法达到51%批准的目标。每个节点可以将其投票权授予一名节点。获票数最多的前100位节点按既定时间表轮流产生区块。每名节点分配到一个时间段来生产区块。

        所有的节点将收到等同于一个平均水平的区块所含交易费的10%作为报酬。

         第一，大幅缩小参与验证和记账节点的数量，

         第二，可以快速实现共识验证。

         主要缺点就是仍然无法摆脱对代币的依赖。

        在分布式计算上，不同的计算机透过讯息交换，尝试达成共识；但有时候，系统上协调计算或成员计算机可能因系统错误并交换错的讯息，导致影响最终的系统一致性。

        拜占庭将军问题就根据错误计算机的数量，寻找可能的解决办法，这无法找到一个绝对的答案，但只可以用来验证一个机制的有效程度。

        而拜占庭问题的可能解决方法为：

        在 N ≥ 3F + 1 的情况下一致性是可能解决。其中，N为计算机总数，F为有问题计算机总数。信息在计算机间互相交换后，各计算机列出所有得到的信息，以大多数的结果作为解决办法。

         第一，系统运转可以摆脱对代币的依赖，共识各节点由业务的参与方或者监管方组成，安全性与稳定性由业务相关方保证。

         第二，共识的时延大约在2到5秒钟。

         第三，共识效率高，可满足高频交易量的需求。

         第一，当有1/3或以上记账人停止工作后，系统将无法提供服务；

         第二，当有1/3或以上记账人联合作恶，可能系统会出现会留下密码学证据的分叉。

        小蚁改良了实用拜占庭容错机制。该机制是由权益来选出记账人，然后记账人之间通过拜占庭容错算法来达成共识。

        此算法在PBFT基础上进行了以下改进：

        第一，将C/S架构的请求响应模式，改进为适合P2P网络的对等节点模式；

        第二，将静态的共识参与节点改进为可动态进入、退出的动态共识参与节点；

        第三，为共识参与节点的产生设计了一套基于持有权益比例的投票机制，通过投票决定共识参与节点（记账节点）；

        第四，在区块链中引入数字证书，解决了投票中对记账节点真实身份的认证问题。

        第一，专业化的记账人；

        第二，可以容忍任何类型的错误；

        第三，记账由多人协同完成，每一个区块都有最终性，不会分产生区块链分叉；

        第四，算法的可靠性有严格的数学证明来保证；

        第一，当有1/3或以上记账人停止工作后，区块链系统将无法提供服务；

        第二，当有1/3或以上记账人联合作恶，且其它所有的记账人被恰好分割为两个网络孤岛时，恶意记账人可以使区块链系统出现分叉，但是会留下密码学证据；

         瑞波共识机制是全体节点选取出特殊节点组成特殊节点列表，由特殊节点列表内的节点达成共识。

         初始特殊节点列表就像一个俱乐部，要接纳一个新成员，必须由51%的该俱乐部会员投票通过。共识遵循这核心成员的51%权力，外部人员则没有影响力。波共识机制将股东们与其投票权隔开，并因此比其他系统更中心化。

        瑞波共识机制参与共识形成的只有特殊节点，大大的减少了共识形成的时间。在实践中，瑞波区块链系统达成共识需要3-6秒钟，远远快于比特币区块链系统的10分钟。同时瑞波区块链系统对并发交易的处理达到每秒数万笔，而比特币区块链系统只有每秒7笔。

瑞波共识机制处理节点意见分歧的方式也是不同的。瑞波的信任节点对于新区块的创造进行协商的时间是区块链更新前。先协商，达成共识后再对区块链进行更新。

由于瑞波共识机制的共识是由特殊节点达成的，普通节点并不需要维护一个完整的历史账本。各个节点可以根据自己的业务需要选择同步同步完整的历史账本或者任意最近几步的账本。这也意味着对存储空间和网络流量需求的减少。

瑞波共识机制取消了挖坑的发行货币机制，采用了原生货币（1000亿枚）的方式发币，从而大量的避免了挖矿的天量能耗。

『肆』 区块链技术的六大核心算法

区块链技术的六大核心算法
区块链核心算法一：拜占庭协定
拜占庭的故事大概是这么说的：拜占庭帝国拥有巨大的财富，周围10个邻邦垂诞已久，但拜占庭高墙耸立，固若金汤，没有一个单独的邻邦能够成功入侵。任何单个邻邦入侵的都会失败，同时也有可能自身被其他9个邻邦入侵。拜占庭帝国防御能力如此之强，至少要有十个邻邦中的一半以上同时进攻，才有可能攻破。然而，如果其中的一个或者几个邻邦本身答应好一起进攻，但实际过程出现背叛，那么入侵者可能都会被歼灭。于是每一方都小心行事，不敢轻易相信邻国。这就是拜占庭将军问题。
在这个分布式网络里：每个将军都有一份实时与其他将军同步的消息账本。账本里有每个将军的签名都是可以验证身份的。如果有哪些消息不一致，可以知道消息不一致的是哪些将军。尽管有消息不一致的，只要超过半数同意进攻，少数服从多数，共识达成。
由此，在一个分布式的系统中，尽管有坏人，坏人可以做任意事情(不受protocol限制)，比如不响应、发送错误信息、对不同节点发送不同决定、不同错误节点联合起来干坏事等等。但是，只要大多数人是好人，就完全有可能去中心化地实现共识
区块链核心算法二：非对称加密技术
在上述拜占庭协定中，如果10个将军中的几个同时发起消息，势必会造成系统的混乱，造成各说各的攻击时间方案，行动难以一致。谁都可以发起进攻的信息，但由谁来发出呢?其实这只要加入一个成本就可以了，即：一段时间内只有一个节点可以传播信息。当某个节点发出统一进攻的消息后，各个节点收到发起者的消息必须签名盖章，确认各自的身份。
在如今看来，非对称加密技术完全可以解决这个签名问题。非对称加密算法的加密和解密使用不同的两个密钥.这两个密钥就是我们经常听到的”公钥”和”私钥”。公钥和私钥一般成对出现, 如果消息使用公钥加密,那么需要该公钥对应的私钥才能解密; 同样，如果消息使用私钥加密,那么需要该私钥对应的公钥才能解密。
区块链核心算法三：容错问题
我们假设在此网络中，消息可能会丢失、损坏、延迟、重复发送，并且接受的顺序与发送的顺序不一致。此外，节点的行为可以是任意的：可以随时加入、退出网络，可以丢弃消息、伪造消息、停止工作等，还可能发生各种人为或非人为的故障。我们的算法对由共识节点组成的共识系统，提供的容错能力，这种容错能力同时包含安全性和可用性，并适用于任何网络环境。
区块链核心算法四：Paxos 算法(一致性算法)
Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。节点通信存在两种模型：共享内存和消息传递。Paxos算法就是一种基于消息传递模型的一致性算法。
区块链核心算法五：共识机制
区块链共识算法主要是工作量证明和权益证明。拿比特币来说，其实从技术角度来看可以把PoW看做重复使用的Hashcash，生成工作量证明在概率上来说是一个随机的过程。开采新的机密货币，生成区块时，必须得到所有参与者的同意，那矿工必须得到区块中所有数据的PoW工作证明。与此同时矿工还要时时观察调整这项工作的难度，因为对网络要求是平均每10分钟生成一个区块。
区块链核心算法六：分布式存储
分布式存储是一种数据存储技术，通过网络使用每台机器上的磁盘空间，并将这些分散的存储资源构成一个虚拟的存储设备，数据分散的存储在网络中的各个角落。所以，分布式存储技术并不是每台电脑都存放完整的数据，而是把数据切割后存放在不同的电脑里。就像存放100个鸡蛋，不是放在同一个篮子里，而是分开放在不同的地方，加起来的总和是100个。

『伍』 拜占庭容错和PBFT共识算法

实用的拜占庭容错算法
BFT 是区块链共识算法中，需要解决的一个核心问题。比特币的POW，eos的dpos，以及共识算法pos，这些公链算法，解决的是共识节点众多情况下的bft问题。

拜占庭将军问题。也称为拜占庭容错。
用来描述分布式系统一致性问题。

背景如下：
拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。这10支军队在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队（一半以上）同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们才能保证有多于6支军队在同一时间一起发起进攻，从而赢取战斗？

单从上面的说明可能无法理解这个问题的复杂性，我们来简单分析一下：

先看在没有叛徒情况下，假如一个将军A提一个进攻提议（如：明日下午1点进攻，你愿意加入吗？）由通信兵通信分别告诉其他的将军，如果幸运中的幸运，他收到了其他6位将军以上的同意，发起进攻。如果不幸，其他的将军也在此时发出不同的进攻提议（如：明日下午2点、3点进攻，你愿意加入吗？），由于时间上的差异，不同的将军收到（并认可）的进攻提议可能是不一样的，这是可能出现A提议有3个支持者，B提议有4个支持者，C提议有2个支持者等等。

再加一点复杂性，在有叛徒情况下，一个叛徒会向不同的将军发出不同的进攻提议（通知A明日下午1点进攻， 通知B明日下午2点进攻等等），一个叛徒也会可能同意多个进攻提议（即同意下午1点进攻又同意下午2点进攻）。

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

使用密码学算法保证节点之间的消息传送是不可篡改的， 通过下面的算法我们可以保证A将军收到B将军发来的消息确实是B将军本人的真实请求 。

我们采用的是哈希函数（散列算法）SHA256 -- 从数据（byte）值中创建独一无二的hash值，并压缩成摘要，将数据格式固定下来。通过这个摘要与个人私钥生成Digital Signature 和个人公钥Public-key certificate，接收方验证签名和摘要，如果是通过验证，即证明摘要内容没有经过篡改。

pbft容忍无效或者恶意节点数量 e 。为了保证整个系统可以正常运作，需要有2f+1个正常节点，系统的总结点数为 ：3f+1。即pbft算法容忍小于1/3的恶意或者无效节点。 原因见节点作恶的极端情况

pbft是一种状态机副本复制算法，所有副本在一个view轮换过程中操作，哪些是主节点（进攻的提议者的大将军们，轮流当）通过view中其他节点（其他将军）赋予的编号和节点数集合来确定，即：主节点p=v mod |R| 。 v：view编号，|R|节点个数，p：主节点编号。 关于状态机复制算法、view change的意义（主要是防止主节点作恶），主节点详见论文。

基于拜占庭将军问题，PBFT算法一致性的确保主要分为这三个阶段：预准备（pre-prepare）、准备(prepare)和确认(commit)。流程如下图所示：

[图片上传失败...(image-e3329d-1562488133052)]

首先解释一下上面各个符号表达的意思：

下面结合上图，详细说一下PBFT的步骤：

根据上述流程，在 N ≥ 3F + 1 的情况下一致性是可能解决， N为总计算机数，F为有问题的计算机总数 。

下面所有的校验流程略去对消息内容、签名和身份的验证，即已经保证了节点之间消息传播是不可篡改的

上述算法中，比较重要的一个点是view change，为了能恢复之前的请求，每一个副本节点收到消息之后或者发送消息的时候都会记录消息到本地的log记录中。当执行请求后，副本节点需要把之前该请求的记录消息清除掉。最简单的做法是在reply消息后，在执行一次当前状态的共识同步，但是为了节省资源，一般在多条请求K后执行一次状态同步。这个状态同步就是checkpoint消息。

为了节省内存，系统需要一种将日志中的 无异议消息记录 删除的机制。为了保证系统的安全性，副本节点在删除自己的消息日志前，需要确保至少 f+1 个正常副本节点执行了消息对应的请求，并且可以在视图变更时向其他副本节点证明。另外，如果一些副本节点错过部分消息，但是这些消息已经被所有正常副本节点删除了，这就需要通过 传输部分或者全部服务状态实现该副本节点的同步 。因此，副本节点同样需要证明状态的正确性。

在每一个操作执行后都生成这样的证明是非常消耗资源的。因此，证明过程只有在请求序号可以被某个常数（比如100）整除的时候才会周期性地进行。我们将这些请求执行后得到的状态称作 检查点（checkpoint） ，并且将具有证明的检查点称作 稳定检查点（stable checkpoint） 。

上述情况是理想情况，实际上当副本节点i向其他节点发出checkpoint消息之后，其他节点还没有完成K条请求的相互共识，所以不会立即对i的请求作出响应。其他节点会按照自己的处理步骤和顺序，向前行进和共识。但是此时i发出的checkpoint没有形成stable，为了防止i太快，超过自己太多，于是被便会设置一个高水位H=h+L，其中L就是我们指定允许的高度差，等于checkpoint周期处理数K的整数倍，可以设置为L=2K。当副本节点i处理请求超过高水位H时，副本节点即使接受到请求也会视为非法请求。等待stable checkpoint发生变化，再继续向前推进处理。

如果主节点作恶，它可能会给不同的请求编上相同的序号，或者不去分配序号，或者让相邻请求的序号不连续。备份节点（备份主节点）应当有职责来主动检查这些序号的合法性。如果主节点掉线或者作恶不广播客户端的请求，客户端设置超时机制，超时的话，向所有副本节点广播请求消息。副本节点检测出主节点或者下线，发起view change流程。

我们在上面讲到，当网络中有F台有问题的计算机时，至少需要3F+1台计算机才能保证一致性问题的解决，我们在这里讨论一下原因。

我们可以考虑：由于有F个节点为故障或被攻击的节点，故我们只能从N-F个节点中进行判断。但是由于异步传输，故当收到N-F个消息后，并不能确定后面是否有新的消息。（有可能是目前收到的N-F个节点的消息中存在被攻击的节点发来的消息，而好的节点的消息由于异步传输还没有被收到。）

我们考虑最坏的情况，即剩下F个都是好的节点，收到的中有F个被攻击的节点，故我们需要使得收到的中好节点的数量 (N-F)-F 大于被攻击节点的数量 F ，于是有 N-2F>F ，即 N>3F ，所以N的最小整数为 N=3F+1 。

pbft是需要参与认证的节点进行的。所以一个完整的共识算法包括DPOS+PBFT。其速度是可以达到1500tps左右的。

参考文献：

https://mathpretty.com/9602.html

https://blog.csdn.net/jfkidear/article/details/81275974

Practical Byzantine Fault Tolerance

Miguel Castro and Barbara Liskov Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139 castro,liskov @lcs .mit.e

https://www.jianshu.com/p/fb5edf031afd 部分论文翻译

『陆』 《币圈笔记》第377期：拜占庭问题

19年06月06日，祝六六大顺。

我们以前常看到以太坊拜占庭分叉，这个拜占庭又是什么意思呢？

拜占庭位于如今的土耳其的伊斯坦布尔，是东罗马帝国的首都。

由于当时拜占庭罗马帝国国土辽阔，为了达到防御目的，每个军队都离得很远，将军与将军之间只能靠信差传消息。在战争期间，拜占庭军队内所有将军必须达成一致共识，全体都决定认同有赢的机会才能去攻打敌人的阵营。

但是，在军队内有可能存有叛徒和敌军的间谍，他们可能影响将军们的决定、甚至某个将军自己就是叛徒。那么，在已知有成员谋反的情况下，其余忠诚的将军如何在不受叛徒的影响下达成一致的协议，拜占庭问题就此形成。

对区块链有认识的读者们可以看出来，拜占庭将军问题其实是一个协议问题：由于叛徒可以任意行动以达到以下目标：欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定；或迷惑某些将军，使他们无法做出决定。如果叛徒达到了这些目的之一，则任何攻击行动的结果都是注定要失败的。

所谓拜占庭失效指一方向另一方发送消息，另一方没有收到，或者收到了错误的信息的情形。

这些错误被统称为“崩溃失效”和“发送与遗漏式失效”。当拜占庭失效发生时，系统可能会做出任何不可预料的反应！

以太坊以前那个拜占庭硬分叉，为什么叫拜占庭？笔者认为该阶段旨在用技术算法解决历史上的难题，以便区块链网络在受到干扰的情况下依然能够达成共识。人家说艺术来源于生活，那么这一灵感来源于真实历史事件，读史使人明智。

『柒』 区块链技术开发到底是什么原理

狭义来讲，区块链是一种按照时间顺序将数据区块以顺序相连的方式组合成的一种链式数据结构， 并以密码学方式保证的不可篡改和不可伪造的分布式账本。

广义来讲，区块链技术是利用块链式数据结构来验证与存储数据、利用分布式节点共识算法来生成和更新数据、利用密码学的方式保证数据传输和访问的安全、利用由自动化脚本代码组成的智能合约来编程和操作数据的一种全新的分布式基础架构与计算方式。

工作原理

区块链系统由数据层、网络层、共识层、激励层、合约层和应用层组成。 其中，数据层封装了底层数据区块以及相关的数据加密和时间戳等基础数据和基本算法;网络层则包括分布式组网机制、数据传播机制和数据验证机制等;共识层主要封装网络节点的各类共识算法;激励层将经济因素集成到区块链技术体系中来，主要包括经济激励的发行机制和分配机制等;合约层主要封装各类脚本、算法和智能合约，是区块链可编程特性的基础;应用层则封装了区块链的各种应用场景和案例。该模型中，基于时间戳的链式区块结构、分布式节点的共识机制、基于共识算力的经济激励和灵活可编程的智能合约是区块链技术最具代表性的创新点。

『捌』 如何理解拜占庭将军问题

拜占庭将军问题（以下简称“共识问题”）的正式表述是：如何在一个不基于信任的分布式网络中就信息达成共识？这个表述听起来有些晦涩，但其本质并不复杂，下面的例子与共识问题虽然并不完全一致，但却有助于我们的理解[9]。 想象一下在遥远的拜占庭时代，有一个富饶的城邦，金银珠宝绫罗绸缎应有尽有，它的领主哆啦A梦独享着这一切奢华与荣耀。而在城邦的外围，四位拜占庭将军大雄、胖虎、小夫和静香都觊觎着哆啦A梦的财富，于是他们决定联手攻占哆啦A梦的城邦。根据双方的实力对比，必须有超过半数的将军同时发起进攻方能克敌制胜，因此获胜条件就是四人中至少三个人可以就进攻时间达成一致。那么四位将军的胜算有多少呢？ 这个问题的答案就要取决于四个人的合作方式了，如果是集中式系统，有一个盟主，比如胖虎（相当于中央服务器），那么他们的胜利是毫无悬念的，因为就进攻时间达成一致非常简单，只要胖虎召集大雄、小夫和静香开个会讨论一下就可以了，即使大家意见有分歧胖虎也可以在最后予以定夺。下面让我们回到拜占庭将军问题的假设里，在不基于信任的分布式网络中，四位将军的胜算又如何呢？ ? 首先由于四位将军之间缺乏信任，因此聚到小黑屋里开个密谋会的可能性被排除了（一旦在小黑屋里被胖虎绑架了怎么办？）；其次由于没有盟主，四个人的意见都会被同等的看重。在这种情况下，四位将军只能通过信使在各自营地之间传递消息，来商定进攻时间了。比如大雄觉得早上6点是发动进攻的好时机，他就会派信使将自己的意见告诉胖虎、小夫和静香，与此同时，胖虎可能认为晚上9点发动突袭更好，小夫更喜欢下午3点出击，而静香希望是上午10点，他们三人也会在同一时间派出自己的信使。这样一来，在第一轮通信结束后，四位将军每个人都有了四个可供选择的进攻时间，他们各自要在下一轮通信中把自己选定的时间告知另外三人。由于四个人的决策都是独立做出的，因此最终的选择结果就有256种可能，而只有当三人以上都恰好选择了同一时间的时候，共识才被达成，而这样的结果才64种，也就是说达成共识的概率仅为1/4。这还只是四位将军的情况，如果将军的人数是10人，100人，1000人呢？我们稍加计算就可以发现随着人数的增加，达成共识的希望会变得越来越渺茫。 把上面例子中的将军换成计算机网络中的节点，把信使换成节点之间的通信，把进攻时间换成需要达成共识的信息，你就可以理解共识问题所描述的困境了。达成共识的能力对于一个支付系统来说重要性不言而喻，如果你给家里汇了一笔钱买车，第二天去银行核实的时候柜台告诉你“关于你汇了多少钱的问题，我们的系统里有三个版本的记录”，这样的银行你显然是不敢把钱存进去的。在比特币出现之前共识问题是很难被完美解决的，要保证达成共识就需要采用集中式系统（除非节点满足特定条件），要想去中心化共识就无法保证。那么区块链技术又是如何解决这一难题的呢？

『玖』 拜占庭将军很忙—《区块链思维》第21块

无论在链圈，还是在币圈混，经常听到一个名词“拜占庭将军问题”。

到底拜占庭是啥，拜占庭将军怎么啦，到处都被提及，这位将军好忙啊！

先说拜占庭这个地方。很久很久以前的欧洲，建立在比中世纪还古老的时期，历史上就是东罗马帝国，跨越了千年的历史期盼。

扯远了，回到正题，什么是拜占庭将军问题。

拜占庭这个地方异常坚固，同时被十个独立邻邦环伺，分别有一位将军，单独攻城必败，只有一半以上的将军同时攻打才能破城。

十位将军为了协调一致，在那个古老的时代，累死传令兵，要么飞鸽传书（那时的欧洲比中国落后，好像没有这个高速通信手段）。十位将军相互通信一次就需要90次传信，每位将军都有各自的攻城计划，要想达成统一就需要往复传递不知道多少次。

我们可以假设一个场景，一个桌子上坐着十位将军，每个人各自说着自己的想法，同时听其他九位的说法，但是信息的传递不是实时的，有快有慢，有早有晚。想明白了吗？也就是说，这十位将军如果想达成一致，理论上有可能，实际上他们的有生之年都实现不了，难怪拜占庭帝国经历了千年也没有被这十位将军攻破。

中本聪这个神人，利用互联网信息传递的及时性特点，引入时间戳可以明确知道“谁先说、谁后说”的特性，创造性地加入挖矿机制（就是用计算机算随机数满足一定难度才算成功）比拼各位将军的智商来决定谁做本次进攻的统帅，使用非对称加密保证信息传输的安全性等等手段融合到比特币中，用实例说明自己破解了这个历史难题“拜占庭将军问题”。从而向世人证明解决60亿人口的互信问题是有去中心化解决方案地。

币圈和链圈的朋友很焦虑的另一个关键问题就是：这个圈子概念太TM多。除了这个“拜占庭将军问题”，还有一个“拜占庭容错”，这是什么鬼？这两个是一样的吗？这两个是故意有一个被写错了吗？还是说我的智商税没交够？其实，你都说对了。

“拜占庭将军问题”假设所有十个将军都是好的，都想攻破拜占庭，只是达成共识很难，比特币提供了好人达成共识的方案。

“拜占庭容错”是说十个将军可以很好地达成共识。但是，如果其中出了坏人，怎么解决？

如果十个将军中出现了坏人（叫叛徒也行），进攻计划是否会永远无法达成共识呢？

“拜占庭容错”告诉大家，是可以达成地，并且，还能找出这些“叛徒”是谁。只是，10个将军中叛徒的数量不能超过3个，超出了就无法“容错”，也找不出这些叛徒是谁。对应的公式就是：3n+1。其中3n+1是将军总数（区块链的账本/矿机总数），n是能够“容错”的“叛徒”（恶意记错账）总数。

对于十个将军来说，最多容忍三个叛徒，多了就彻底没戏啦。为了比特币的容错能力越来越强，就需要更多的节点，这样才能容忍并找出更多的叛徒。懂了吧。

小结一下：拜占庭将军问题是假设都是好人前提下如何达成共识，拜占庭容错就是全网最多能够容忍多少叛徒并且能找出他们。

请交智商税到如下地址：

国税BTC到Kcash：

地税ETH及各种原生Token到 Imtoken：

不交税的，祝你做“韭菜”一切顺利 :D

『拾』 拜占庭问题

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

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

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

在拜占庭问题中，最重要的point就是： 所有将军如何达成一致攻打拜占庭的共识 ，这当中，可能出现的情况举例如下：

用一个模型解释一下：

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

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

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

可以看得出， 只要叛徒的数量大于或等于1/3，拜占庭问题不可解

从技术上理解， 拜占庭将军问题是分布式系统容错性问题 。加密货币建立在P2P网络之上，是典型的分布式系统，类比一下， 将军就是P2P网络中的节点，信使就是节点之间的通信，进攻还是撤退的决定就是需要达成的共识 。 如果某台独立的节点计算机拓机、掉线或攻击网络搞破坏，整个系统就要停止运行，那这样的系统将非常脆弱，所以容许部分节点出错或搞破坏而不影响整个系统运行是必要的 ， 这就需要算法理论上的支撑，保证分布式系统在一定量的错误节点存在的情况下，仍然保持一致性和可用性 。

而且，拜占庭将军与两军问题不同，前者假定信差没有问题，只是将军出现了叛变等问题；后者研究信差的通信问题。

终极解决方案到了——

如果 10个将军中的几个同时发起消息，势必会造成系统的混乱，造成各说各的攻击时间方案，行动难以一致 。

谁都可以发起进攻的信息，但由谁来发出呢？中本聪巧妙地在个系统加入了 发送信息的成本 ，即：

它加入的 成本就是”工作量“ —— 节点必须完成一个计算工作才能向各城邦传播消息 ，当然，谁第一个完成工作，谁才能传播消息。（这也是 工作量证明机制的意义：以检验结果的方式证明你过去所做过了多少工作 ）

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

中本聪在设计比特币时，它采用了一种工作量证明机制叫哈希现金，在一个交易块这要找到一个随机数，计算机只能用穷举法来找到这个随机数，可以说，能不能找到全靠运气，所以对于各个节点来说，这个世界上，只有随机才是真正的公平，实现随机的最好办法是使用数学，所有的将军在寻找共识的过程，借助了大家都认可的数学逻辑。

当然了， 凭什么要义务进行计算工作，那么肯定要有一个激励机制 ：比特币的奖励机制是每打包一个块，目前是奖励25个比特币，而拜占庭将军问题的奖励机制可以是瓜分拜占庭获得的利益。

在这个分布式网络里：

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

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

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

注：区块链学习新人，若有不正确的地方，望指出