拜占庭将军问题和区块链

① 区块链企业服务主要解决的问题是什么

人人链区块链服务，让用户在弹性、开放的云端上能够快速构建自己的 IT基础设施和区块链服务。使用 BaaS 可以极大降低您实现区块链底层技术的成本，简化区块链构建和运维工作，同时面对各行业领域场景，满足用户个性化需求，一站式快速交付定制 BaaS。

② 数字货币双花 拜占庭将军是什么意思

拜占庭将军问题在我看来是提出了一个错误模型。即错误节点可以做任意事情（不受protocol限制），比如不响应、发送错误信息、对不同节点发送不同决定、不同错误节点联合起来干坏事等等。总之就是说，没有节点会出现比这更严重的错误。

很显然，拜占庭错误是overly pessimistic的模型，因为这种错误实际环境中比较少见。那么为什么要研究这个模型呢看其中最简单的一个原因是，如果某个一致性算法能够保证在系统出现f个拜占庭错误时保持系统一致，那么这个算法也就能够保证在出现f个任意其他错误的时候也保持系统一致。

错误模型有上限，肯定也就有一个下限（overly optimistic，没有比它还要弱的模型）。这个下限就是‘fail-stop’模型。这个模型的假设是：当一个节点出错，这个节点会停止运行，并且其他所有节点都知道这个节点发生了错误。用同样的逻辑，如果某个一致性算法不能保证在系统出现f个错误的时候保持一致，那么这个算法也就没法处理其他f个任意其他问题。

应用这些错误模型，可以对不同算法进行比较，也可以对具体算法的cost进行讨论。

③ 拜占庭将军问题的起源

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

④ 如何理解拜占庭将军问题

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

⑤ 公证区块链是什么

区块链技术原理的来源可归纳为一个数学问题：拜占庭将军问题。拜占庭将军问题延伸到互联网生活中来，其内涵可概括为：在互联网大背景下，当需要与不熟悉的对手方进行价值交换活动时，人们如何才能防止不会被其中的恶意破坏者欺骗、迷惑从而做出错误的决策。进一步将拜占庭将军问题延伸到技术领域中来，其内涵可概括为：在缺少可信任的中央节点和可信任的通道的情况下，分布在网络中的各个节点应如何达成共识。区块链技术解决了闻名已久的拜占庭将军问题——它提供了一种无需信任单个节点、还能创建共识网络的方法。

⑥ 如何理解拜占庭将军问题

关于拜占庭将军问题，一个简易的非正式描述如下：
拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。
这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。
基于一些原因，这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时攻击。
他们任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭击才能攻下敌国。
他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。
困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。
在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗 。
这就是著名的拜占庭将军问题。
应该明确的是，拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道绝无问。
Lamport已经证明了在消息可能丢失的不可靠信道上试通过消息传递的方式达到一致性是不可能的。
所以，在研究拜占庭将军问题的时候，已经假定了信道是没有问题的，并在这个前提下，去做一致性和容错性相关研究。

⑦ 拜占庭将军问题的解决算法

拜占庭问题的最初描述是：n 个将军被分隔在不同的地方，忠诚的将军希望通过某种协议达成某个命令的一致（比如一起进攻或者一起后退）。但其中一些背叛的将军会通过发送错误的消息阻挠忠诚的将军达成命令上的一致。Lamport 证明了在将军总数大于3m ，背叛者为m 或者更少时，忠诚的将军可以达成命令上的一致。
为了保证上面的需求，必须满足下面两个条件：
1. 每两个忠诚的将军必须收到相同的值 v(i)（v(i)是第i 个将军的命令）
2. 如果第i 个将军是忠诚的，那么他发送的命令和每个忠诚将军收到的v(i)相同
为了简化以上模型，我们使用一个将军发送命令给多个副官的形式来证明，发送命令的将军称为发令者，接收命令的将军为副官，那么上面的两个条件可以表述为：
IC1. 所有忠诚的副官遵守相同的命令
IC2. 如果发出命令的将军是忠诚的，那么所有忠诚的副官遵守司令（发出命令的将军）的命令
特别提示：发送命令的每次只有一个将军，将其命令发送给n-1 个副官。m 代表叛国者的个数，因为将军总数为n，所以副官总数为n-1 个。IC2 中副官遵守实际上是指忠诚的将军能够正确收到忠诚将军的命令消息。 通过口头消息传递达到一致，如果有m 个叛国将军，则将军们的总数必须为3m+1 个以上。下面是口头消息传递过程中默认的一些条件：
A1. 每个被发送的消息都能够被正确的投递
A2. 信息接收者知道是谁发送的消息
A3. 能够知道缺少的消息
A1 和A2 假设了两个将军之间通信没有干扰，既不会有背叛者阻碍消息的发送（截断）也不会有背叛者伪造消息的情况（伪造）。即是每个将军都可以无误地将自己的消息发送给其他每个将军。（下一节中可以不需要这个必要条件）
我们定义口头消息算法OM(m) 。对于所有的非负整数m ，每个发令者通过OM(M) 算法发送命令给n-1 个副官。下面将说明OM(m) 算法在最多有m 个背叛者且总将军数为3m+1 或者更多的情况下可以解决拜占庭将军问题。（考虑到网络应用实际环境，原文使用了收到值代替收到命令，本文不做修改）
算法定义一个函数：majority(com1,com2,…,comn)等于多数派命令。
OM(0)算法
（1）发令者将他的命令发送给每个副官。
（2）每个副官采用他从发令者得到的命令，或者默认使用撤退命令，如果没有收到任何命令。
OM(m)算法
（1）发令者将他的命令发送给每个副官。
（2）对于每个i ，vi 是每个副官i 从发令者收到的命令，如果没有收到命令则为撤退命令。副官i 在OM(m-1) 中作为发令者将vi 发送给另外n-2 个副官。
（3）对于每个i，并且j eq i，vj 是副官i 从第（2）步中的副官j 发送过来的命令（使用OM(m-1)算法），如果没有收到第（2）步中的副官j 的命令则默认为撤退命令。最后副官i 使用majority(v1,…,vn-1)得到命令。
接下来实际的考虑一个n=4，m=1 的情况：
1. 当副官D是背叛者
第一步发令者A执行算法OM(1)将自己的命令发送给三个副官B，C，D，三个副官都正确地收到了命令。
第二步每个收到命令的副官都作为发令者执行算法OM(0)，将自己收到的命令转发给其余副官，因为副官D是背叛者，所以他给副官B和C传递的消息可能会是假消息。副官B和C分别根据majority 函数来决定命令。
这样背叛的副官D 同理也干扰不了发令者的决定。下面看看如果发令者是背叛者。
2. 发令者是背叛者，其余副官为忠诚的
第一步：发令者A向副官B，C，D发送了不同的命令，实际情况中是一个攻击者向不同方发送了不一致的值（例如，0或1）企图扰乱副官做出一致决定。
第二步：副官收到命令后，摇身一变为发令者执行OM(0) 向所有的副官发送命令，每个副官通过多数表决算法仍可以达成一致的命令。
文章接着就证明了OM(m)算法对任意m 都是可以满足，首先引入一个引理（归纳法证明）：
引理1：对于任意m 和k ，如果有超过2k+m 个将军和最多k 个背叛者，那么算法OM(m) 满足IC2 （回顾下IC2 指的是，如果将军是忠诚的，所有的副官遵守将军命令）。
证明：当m=0 的时候，OM(0) 在将军是忠诚的时候满足IC2。当m>0 时，首先将军将命令传递给 n-1 个副官，然后每个副官对n-1 个将军执行OM(m-1) 算法。因为假设了n>2k+m（引理中有将军数大于2k+m），所以 n-1 > 2k+(m-1) >= 2k（即每一轮中副官总数不小于背叛者的两倍），这样每轮OM(m-k) 算法中忠诚的副官收到的命令都是majority(v1,v2,...,v(n-1))，其中忠诚副官发送的命令大于或者等于一半。
接着解决拜占庭将军问题。
定理1：对于任意m，如果有超过3m 个将军和最多m 个背叛者，算法OM(m) 满足条件IC1 和条件IC2。
证明：通过m 的归纳法证明，我们通过假设OM(m-1) 成立来证明OM(m) m>0。首先考虑发送命令的将军是忠诚的。那么将引理中k 设为m 则OM(m) 满足IC2 ，IC1 在发令将军是忠诚的情况下也满足。
接着考虑m 个背叛者中有一个是发令者，那最多就只有m-1 个副官是背叛者了，又因为有3m 个将军，所以副官的总数超过3m-1，且有3m-1>3(m-1) 。因此通过归纳法假设 OM(m-1) 满足IC1 和IC2（最多3(m-1) 个将军和最多m-1 个背叛者）。那么任意两个忠诚的副官j 在OM(m-1) 获得相同命令vj，那么在OM(m) 算法中每个忠诚的副官都会收到(v1,v2,...,v(n-1))，可知满足条件IC1 和IC2。
看完这段证明其实我也挺糊涂的~~~~，画了张图来看看lamport 是怎么证明的：
签名消息在除了满足口头消息A1-A3 三点要求外还应该满足下面A4：
A4 （a）签名不可被伪造，一旦被篡改即可发现
（b）任何人都可以验证将军签名的可靠性
下面定义一个类似于上面majority() 函数的choice() 来决定副官的选择：1.当集合V 只包含了一个元素v ，那么choice(V)=v ；2. choice(o)=RETREAT。
有了上面A4 和choice() 基础我们给出SM(m) 方法：
SM(m) 算法
初始化Vi=空集合
（1）将军签署命令并发给每个副官
（2）对于每个副官i ：
（A）如果副官i 从发令者收到v:0 的消息，且还没有收到其他命令序列，那么：
（i）使Vi 为{v}
（ii）发送v:0:i 给其他所有副官
（B）如果副官i 收到消息v:0:j1:...:jk 且v 不在集合Vi 中则
（i）添加v 到Vi
（ii）如果k<m ，那么发送v:0:j1:...:jk:i 给每个不在j1,..,jk 中的副官
（3）对于每个副官i ，当不再收到消息，则遵守命令choive(Vi)
算法的几点说明：
算法第三步并没有说明副官如何判断没有新的消息，可以通过两个解决方法：一是要求每个副官收到消息后要么签名转发该消息，要么发送一个通知他将不发送这个消息；二是设置一个超时时间，如果在该时间段还没有收到消息，则认为不再收到消息。
算法SM(m) 中，让副官签名是确认其收到了该消息（有点像来了份文件给每个领导批阅）。在SM(1) 中副官收到消息就不用签字了，因为不用转发给其他副官。
定理2：对于任意m，最多只有m 个背叛者情况下，算法SM(m) 解决拜占庭将军问题
Proof：首先证明IC2，如果发令者是忠诚的，那么所有的副官一定收到相同的命令，因为签名无法篡改，且IC1 也就满足了。证明IC1 只用考虑发令者是背叛者的情况（重新回顾下IC1 是指所有忠诚的副官执行相同的命令），IC1 要求两个忠诚的副官（i，j）必须收到相同的命令集合Vi、Vj，也就是Vi 中每个v 都在Vj 中。会存在两种情况，其一当副官i 收到v 命令的序列后，加入到Vi，并将其发送给副官j ，j 将命令v 保存；其二副官i 收到命令v:0:j1:...:jk:i，其中有jr=j，所以 由A4 可知副官j 也收到了该命令。如果没有，则有：
k<m。这种情况下，i 发送信息v:0:j1:...:jk:i 给副官j ，那么j 一定收到v 。（这点感觉和上面有重复）
k=m。发令者是背叛者，最多只有m-1 个副官是背叛者。因此，最少有一个序列j1,...,jm是忠诚的。那么j 一定收到这个忠诚的副官序列发来的值v ，所以副官j 收到v 。
证明完毕。

⑧ 理论上区块链怎么解决拜占庭将军问题

拜占庭将军问题（以下简称“共识问题”）的正式表述是：如何在一个不基于信任的分布式网络中就信息达成共识？这个表述听起来有些晦涩，但其本质并不复杂，下面的例子与共识问题虽然并不完全一致，但却有助于我们的理解[9]。

想象一下在遥远的拜占庭时代，有一个富饶的城邦，金银珠宝绫罗绸缎应有尽有，它的领主哆啦A梦独享着这一切奢华与荣耀。而在城邦的外围，四位拜占庭将军大雄、胖虎、小夫和静香都觊觎着哆啦A梦的财富，于是他们决定联手攻占哆啦A梦的城邦。根据双方的实力对比，必须有超过半数的将军同时发起进攻方能克敌制胜，因此获胜条件就是四人中至少三个人可以就进攻时间达成一致。那么四位将军的胜算有多少呢？

这个问题的答案就要取决于四个人的合作方式了，如果是集中式系统，有一个盟主，比如胖虎（相当于中央服务器），那么他们的胜利是毫无悬念的，因为就进攻时间达成一致非常简单，只要胖虎召集大雄、小夫和静香开个会讨论一下就可以了，即使大家意见有分歧胖虎也可以在最后予以定夺。下面让我们回到拜占庭将军问题的假设里，在不基于信任的分布式网络中，四位将军的胜算又如何呢？

?

首先由于四位将军之间缺乏信任，因此聚到小黑屋里开个密谋会的可能性被排除了（一旦在小黑屋里被胖虎绑架了怎么办？）；其次由于没有盟主，四个人的意见都会被同等的看重。在这种情况下，四位将军只能通过信使在各自营地之间传递消息，来商定进攻时间了。比如大雄觉得早上6点是发动进攻的好时机，他就会派信使将自己的意见告诉胖虎、小夫和静香，与此同时，胖虎可能认为晚上9点发动突袭更好，小夫更喜欢下午3点出击，而静香希望是上午10点，他们三人也会在同一时间派出自己的信使。这样一来，在第一轮通信结束后，四位将军每个人都有了四个可供选择的进攻时间，他们各自要在下一轮通信中把自己选定的时间告知另外三人。由于四个人的决策都是独立做出的，因此最终的选择结果就有256种可能，而只有当三人以上都恰好选择了同一时间的时候，共识才被达成，而这样的结果才64种，也就是说达成共识的概率仅为1/4。这还只是四位将军的情况，如果将军的人数是10人，100人，1000人呢？我们稍加计算就可以发现随着人数的增加，达成共识的希望会变得越来越渺茫。

把上面例子中的将军换成计算机网络中的节点，把信使换成节点之间的通信，把进攻时间换成需要达成共识的信息，你就可以理解共识问题所描述的困境了。达成共识的能力对于一个支付系统来说重要性不言而喻，如果你给家里汇了一笔钱买车，第二天去银行核实的时候柜台告诉你“关于你汇了多少钱的问题，我们的系统里有三个版本的记录”，这样的银行你显然是不敢把钱存进去的。在比特币出现之前共识问题是很难被完美解决的，要保证达成共识就需要采用集中式系统（除非节点满足特定条件），要想去中心化共识就无法保证。那么区块链技术又是如何解决这一难题的呢？（关注公众号weoption，回复“区块链”，可查看全文。）

⑨ 区块链共识机制，拜占庭将军问题是什么

POW完全依靠用经济激励的方式来大量增加记账参与者， 从而稀释作恶节点的比例， 或者说大幅增加作恶的成本， 做假账者需要控制或者贿赂更多的节点。这是一种简单粗暴的共识机制， 在算法上没有优化过，但是又非常可行， 现在体量最大的两条区块链， 比特币和以太坊都是用POW挖矿的方式。
POW虽然不是最优，但是现在最最切实可行的共识算法。例如比特币、莱特币、DECENT都是采用的POW证明机制。