拜占庭将军问题区块链 拜占庭将军问题是区块链比特币的最重要的核心问题

一、【区块链】拜占庭问题及算法

拜占庭问题及算法

一、什么是拜占庭将军问题？

拜占庭将军问题（Byzantine Generals' Problem）是在10世纪80年代提出的一个假想问题。当时拜占庭是东罗马帝国的首都，罗马帝国物资富饶，兵强马壮，但每支军队的驻地分隔很远，将军们只能靠信使来传递消息。在发生战争时，将军们必须制定统一的行动计划，然而这些将军当中有叛徒，叛徒希望通过影响统一行动计划的制定与传播，来破坏忠诚将军们的行动计划。因此，将军们必须有一个预定的方法协议，使所有忠诚的将军能够达成一致，而且少数几个叛徒不能够使忠诚的将军做出错误的决策。

拜占庭将军问题的核心在于：在一个明知有叛徒的非信任环境中，如何使将军们建立对战计划的共识，即如何可以不带任何条件的相信彼此。

在区块链网络中，拜占庭将军问题对应的是网络节点需要就系统的当前状态达成共识。这意味着分布式网络中的大多数参与者必须同意并执行相同的操作，以避免失败。其中有运行正常的服务器（类似于忠诚的拜占庭将军），还有故障的服务器或有破坏者的服务器（类似于叛变的拜占庭将军）。

二、拜占庭将军问题解决方案

针对拜占庭问题的深入研究，可以得出一个结论：如果叛徒的数量大于或等于1/3，拜占庭问题不可解。

科学家们提出了两种主要解决方案：口头信息方案和书面协议方案。

解决方案一：用口头信息

口头信息指的是将军们派人用口信传达消息。其特点包括：

每个被发送的消息都能够被正确投递；

信息接受者知道消息是谁发的；

沉默（不发消息）可以被检测。

在这种方案中，每个节点都是信息的转达者。一轮下来，每个节点手上都会有来自其他所有节点的信息（进攻或者撤退）。如果有叛徒，那信息可能不一致。此时，采取少数服从多数的原则进行决策，即如果有一半以上的人说进攻，那么采取进攻行动。

但口头协议的缺点在于，它不会告知消息的上一个来源是谁，即消息不可追根溯源，出现信息不一致也很难找到叛徒在哪。

解决方案二：用书面协议

书面协议相比口头协议，增加了签名技术这一隐含条件：

将军们能够使用签名技术，签名不可伪造，一旦篡改即可发现；

同时任何人都可以验证签名的可靠性；

书面协议相比口头协议，所有的消息都是有记录的，解决了追根溯源的问题。

然而，书面协议在现实中仍然可能面临各种问题，如物理距离导致信息传输延迟、真正可信的签名体系难以实现、签名消息记录的保存难以摆脱中心化的机构等。

三、拜占庭容错算法

拜占庭容错（Byzantine Fault Tolerance, BFT）算法是由拜占庭将军问题衍生出来的共识算法。其核心是在正常的节点之间形成网络状态的共识，即使某些节点之间沟通失败或者存在恶意行为，拜占庭容错系统也能够继续运行。

拜占庭容错共识算法有3种版本，每种版本都具有各自的优缺点：

实用拜占庭容错（PBFT，Practical Byzantine Fault Tolerance）

优点：高速、可扩展。

缺点：通常用于私有网络和许可网络。

采用者：Hyperledger Fabric、Ripple。

PBFT是首个解决拜占庭将军问题的方案，已被Hyperledger Fabric采用。它使用了较少的预选定节点数（少于20个），因此运行非常高效。其优点是高交易通量和吞吐量，但不足之处在于它是中心化的，并用于许可网络。PBFT假设区块链上总的节点数是3f+1个，那么网络中可以容忍整个网络中最多f个节点出现拜占庭错误而不影响正确的共识。

联邦拜占庭协议（FBA，Federated Byzantine Agreement）

优点：吞吐量高、低交易开销和网络扩展性好。

采用者：Stellar。

FBA的通用理念是每个拜占庭将军负责自身的链，消息一旦到来，通过排序建立事实。在Stellar中，任何人都可以成为验证者，需要用户选择去相信哪个验证者。FBA比PBFT的去中心化程度更高，但牺牲了一定的性能。

授权拜占庭容错算法（dBFT，Delegated Byzantine Fault Tolerance）

优点：快速、可扩展。

缺点：可能存在多个根链。

采用者：Neo。

dBFT是一种支持通过代理投票实现大规模参与共识的拜占庭容错共识算法。在Neo中，令牌持有者可以通过投票选取其支持的bookkeeper。之后，选定的bookkeeper组采用BFT算法达成共识，并生成新区块。dBFT可为具有n个共识节点的共识系统提供f=n−1/3的容错。这种容错也涵盖了安全性和可用性，不受将军和拜占庭错误影响，并且适合任何网络环境。dBFT具有很好的最终性（finality），这意味着一旦最终确认，区块将不可分叉，交易将不可再撤销或是回滚。

综上所述，拜占庭问题及算法是分布式系统中一个重要的研究领域，它涉及到如何在存在恶意节点的情况下达成共识。通过不同的解决方案和共识算法，可以在一定程度上解决拜占庭问题，确保分布式系统的可靠性和安全性。

二、拜占庭将军很忙—《区块链思维》第21块

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

请交智商税到如下地址：

国税BTC到Kcash：179L7takj4GvWJk4WZfDivdgPyg5Gc5BRJ

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

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

三、区块链 拜占庭将军问题 笔记2-理解 Quorum 概念

区块链拜占庭将军问题笔记2-理解 Quorum概念

Quorum概念解析

在分布式系统中，尤其是在区块链技术中，Quorum（法定人数）是一个核心概念，它用于确保数据的一致性和可靠性。本文将从Alex和Bob的交互场景出发，深入探讨Quorum的概念及其在分布式状态更新和查询中的应用。

一、问题背景与抽象中心化版本：数据储存在中心节点（如Bank）上，Client（如Alex）通过写入操作更新数据，另一Client（如Bob）通过查询操作获取数据状态。分布式版本：数据分布在多个replicas（副本）上，目标是通过某种协议确保所有replicas的数据状态一致。二、从理想情况出发

在理想情况下，即所有节点都正常工作且通信无阻碍时，最简单的方法是同时告诉所有replicas执行写入操作w，并同时更新状态。然而，由于网络延迟、节点故障等现实因素，每次都与所有节点取得联系变得困难。因此，需要找到一种更高效的方法，即只确认部分节点执行了操作，这就是Quorum机制的核心思想。

三、Quorum概念详解

Quorum机制通过计数的判断方式来确定操作的有效性。在节点总数为n的网络中：

Alex视角：Alex要求网络执行操作w，并等待一个replicas子群α（α为Quorum子集）反馈相同消息，表示状态从INIT变更为A。如果满足数量（num_α）相同这两个条件，Alex认为协议结束。Bob视角：Bob发出查询请求r，等待一个子群β（β为另一Quorum子集）反馈相同消息，表示状态为X。如果满足数量（num_β）相同这两个条件，Bob认为协议结束。

关键在于找到num_α、num_β和总数n之间的直接关系，确保当Alex和Bob接收到的反馈满足“相同”要求时，X必然只能为A。

四、确定数量关系

考虑两种情况：

情况①：num_α+ num_β≤ n。在这种情况下，子群α和β的节点数加起来小于总的节点数，可能两个子群没有交集。这意味着不存在节点同时参与了Alex要求的w操作和Bob要求的r操作。因此，Bob可能收到错误的“我的状态为X”的反馈，X可能为原始的INIT，导致数据不一致。情况②：num_α+ num_β> n。在这种情况下，子群α和β的节点数加起来大于总的节点数，两个子集无论如何都会存在交集。这意味着存在至少一个节点同时参与了Alex要求的w操作和Bob要求的r操作。这个处于交集的节点因为执行了w操作，状态从INIT变为了A，又因为执行了r操作，反馈给Bob它执行完w后的状态。因此，Bob收到的相同“我的状态为X”的反馈中，X必然只能为A。

这里的num_α和num_β就是Quorum Size，即确保操作有效性的最小节点数。

五、交集是关键

Gifford所指出的“两次操作直接节点必须有一个交集”，是保证分布式系统数据一致性的一个最低条件之一。只要保证每次操作都有交集，总会有一个节点同时参与了本次操作和上次操作，从而确保操作链条的连续性，避免数据错误。

六、总结

Quorum机制是分布式系统中确保数据一致性和可靠性的重要手段。通过合理设置Quorum Size，可以在不牺牲太多性能的情况下，有效应对节点故障和网络延迟等挑战。在区块链技术中，Quorum机制更是扮演着至关重要的角色，它确保了区块链网络的去中心化、安全性和可扩展性。

（注：此图片为示意图，用于辅助理解Quorum概念，并非具体数学公式或数据。）

在下一篇文章中，我们将进一步探讨应用Quorum在CFT（Crash Fault Tolerance，崩溃容错）与BFT（Byzantine Fault Tolerance，拜占庭容错）后，对Quorum Size的影响。