Paste_Image.png
【TED】对未来产生影响最大的科技

何为拜占庭将军问题

问题由来

拜占庭将军问题（Byzantine failures）是由莱斯利·兰伯特在1982年提出的点对点通信中的基本问题。作为分布式系统的先锋科学家，兰伯特当时为NASA建立可靠稳定的航天计算机系统的过程中遇到的容错性问题，就此而编出的拜占庭将军问题，他因为在分布式系统做出的杰出贡献而获得2013年图领奖——计算机界的诺贝尔奖。

问题描述

拜占庭帝国国土辽阔，当攻打敌人的时候，每个军队都分隔很远，将军之间只能靠信使传消息。
在战争的时候，拜占庭军队内所有将军必须达成一致的共识，决定是否去攻打敌人的阵营。但是，军队可能有叛徒和敌军间谍，左右将军们的决定，扰乱军队的秩序，使达成的共识并不代表大多数人的意见。这时，在已知有间谍的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，就是拜占庭将军问题。将军之间的联络通过信使，在这个问题中信使不会被截获（信道可靠）

问题的可解性

1. 叛徒数大于或等于1/3，拜占庭问题不可解
   如果有三位将军，一个司令俩副官，如果其中一个副官是叛徒。当司令发出进攻命令时，副官2可能告诉副官1，他收到的是“撤退”的命令。这时副官1收到一个“进攻”，一个“撤退”，而无所适从。
   如果司令是叛徒。他告诉副官1“进攻”，告诉副官2“撤退”。当副官2告诉副官1，他收到“撤退”命令时，副官1由于收到了司令“进攻”的命令，而无法与副官2保持一致。
   正由于上述原因，在三模冗余系统中，如果有拜占庭故障，即叛徒数等于1/3，拜占庭问题不可解
2. 用口头信息，如果叛徒数少于1/3，拜占庭问题可解。
   这里说“少于1/3”表明，要对付一个叛徒，至少要用四模冗余。在四模中有一个叛徒，叛徒数是少于1/3的。所谓口头信息，是指满足三个条件：
   ①被发送的消息都能够被正确的投递
   ②接收者知道是谁发的（司令还是副官）
   ③沉默（不发信息）可以被检测
   需要注意的是口头协议并不会告知消息的上一个来源是谁。算法的中心思想很简单，就是司令把命令发给每一副官，各副官又将收到的司令的命令转告给其他副官，递归下去，最后用多数表决。
   如果司令是忠诚的，他送一个命令v给所有副官。
   若副官3是叛徒，当他转告给副官2时命令可能变成x。但副官2收到{v, v, x}，多数表决以后仍为v，忠诚的副官可达成一致。
   如果司令是叛徒，他发给副官们的命令可能互不相同，为x, y, z。当副官们互相转告司令发来的信息时，他们会发现，他们收到的都是{x,y,z}，因而也取得了一致。
3. 书面协议
   口头协议的缺点是消息不能追本溯源，这使得口头协议必须在四模冗余的情况下才能保证正确。但是，若能引入一种方法让消息能够追本溯源，情况会不会有所改变呢？这就是书面协议引入的灵感。
   我们在口头协议之上添加一个条件，使之成为书面协议
   （a）司令签名不可伪造，一旦被篡改即可发现，而叛徒的签名可被其他叛徒伪造；（b）任何人都可以验证签名的可靠性。
   书面协议的本质就是引入了签名系统，接收者收到信息后，签上自己的名字后再发给别人，这使得所有消息都可追本溯源。这一优势，大大节省了成本，他化解了口头协议中1/3要求，只要采用了书面协议，忠诚的将军就可以达到一致。这个效果是惊人的，相较之下口头协议则明显有一些缺陷,如递归复杂度等。其实书面协议的原理我也没太懂，记住结论就好xd，即加上签名可以形成一个消息链，能加快达成一致性计算且放宽条件。
4. 在现实环境中书面协议任然存在问题
   在理想环境下书面协议可以很快得到唯一正确的结论。
   但是在现实环境中书面协议面临两个问题
   1）没考虑传输信息的延迟时间，书面协议的签名体系难以实现
   2）签名消息记录的保存难以摆脱一个中心化机构而独立存在。

问题的真正解决

真正解决这一难题的是名叫“中本聪”的人。
这个人就是大名鼎鼎的“比特币”的发明者，比特币圈内的人都知道中本聪是一个“隐匿者”，一个爱收集火车模型的黑客天才。在正式宣告了比特币的诞生之后，中本聪彻底销声匿迹。
他是如何解决的呢，我用一个老司机开车的模型来解释。

一群喜欢开车的小伙伴希望选出老司机带领大家一起开车。
限制条件是
1）他们必须在一个限定的时间内选出老司机带领大家去开车，否则就会被警察叔叔发现。
2）他们在规定时间内只能选出一个老司机，否则同一时刻选出了两个老司机大家就不知道跟着哪个老司机开了。
怎么解决在同一时刻选出一个老司机呢，中本聪使用一个区块链来解决这个问题。

工作量证明链（PoW）

工作量证明，简单理解就是一份证明，用来确认做过一定量的工作。为什么要用工作量证明？因为，监测工作过程通常极为低效，而对工作结果的认证则是一种非常高效的方式。比如他们在规定时间内大家都去靠一个老司机证，一看到这个证就知道他是老司机了，而不用让他开一把车测试一下。

任何一个想做老司机的人都用自己的计算机通过各种输入求解一个哈希散列，这个哈希散列是一个压缩的信息，里面包含了已经拿到老司机证的名单等信息。由于这个计算比较困难，一般至少10分钟才能产生答案。比如某时刻一个司机计算出了666这个结果，于是他拿到了老司机证，然后他把自己的名字放入老司机证名单里，这时下一个老司机证可能就变成了777，于是他把这个消息向所有老司机传播，每个收到消息的司机就开始重新计算，由于计算至少要十分钟，所以可能5分钟内所有司机都收到新的老司机名单的输入，下一个10分钟内又会产生一个777的老司机。大家就可以根据这个老司机名单来一个个的带大家愉快的开车了。

区块链：一句话解释区块链就是一个去中心化的信任机制。

再详细点：区块链是指通过去中心化和去信任的方式集体维护一个可靠数据库的技术方案。

再多说一点：区块链技术就指一种全民参与记账的方式。所有的系统背后都有一个数据库，你可以把数据库看成是就是一个大账本。那么谁来记这个账本就变得很重要。目前就是谁的系统谁来记账，微信的账本就是腾讯在记，淘宝的账本就是阿里在记。但现在区块链系统中，系统中的每个人都可以有机会参与记账。在一定时间段内如果有任何数据变化，系统中每个人都可以来进行记账，系统会评判这段时间内记账最快最好的人(老司机)，把他记录的内容写到账本（老司机名单），并将这段时间内账本内容发给系统内所有的其他人进行备份。这样系统中的每个人都了一本完整的账本。这种方式，我们就称它为区块链技术。

区块链解决了三大痛点

1. 去中心：多个中心化的系统，使得系统风险下降。没有中心的本质就是人人都是中心。
2. 安全：区块链可以解决安全传输问题，解决信息化联网去中心化信任问题，构建出价值互联网，颠覆社会组织与生产方式。
3. 信任：由于区块链内每个节点掌握各个节点信息，系统内交易批准取决于所有节点共识性原则，规则对于所有节点公平且强制，并且，随着交易增多，每个节点内同步更新的链条愈发变长，愈发难以被篡改。这个真的很赞！

区块链技术的应用价值

1. 金融领域就是区块链很好的应用。比特币成功背后的核心概念是一个用以维持一本全球性的总账的去中心化协议，它被叫做区块链。区块链记录着比特币地址之间的交易，追踪着每一个比特币转手的举动。这样的追踪确保了没有人可以双花（double-spend）一个币，因为总账使得一名用户是否发送出了比他挣得的更多的比特币变得太明显。比特币追踪的特别方式，也使得交易记录不可被变更；一旦一笔比特币交易被处理并收录进了区块链，攻击者就很难逆转那笔交易了，所以商户可以在有信心交易不会被逆转的情况下发出货物。
2. 在未来，的确还有可能出现这样的情况，我们将不再使用现金买东西，也完全重新颠覆事物所有权的概念。即使互联网已经通过各种方式在各方面改变了我们的生活，但是从来没有一种方法能够真正的，在没有中心化权威机构的承认下，让你“拥有”某些数字产品。
3. 中心化有各种弊端，比如安全性容易受到破坏，世界不断有黑客攻破数据中心的报道。中心化处理成本高，如政府等中心机构高成本却做不好事情。又比如超级计算机资源昂贵，用无视低成本客户端代替中心超级计算机可以省去资源成本。
4. “区块链”让万物真正互联！
   比如，一台洗衣机。如果没有洗衣粉，会自动通过传感器、点对点的加密通讯协议，把洗衣粉自动给你送过来加上。洗衣机可能会有一个数字钱包，洗衣粉送来之后，洗衣机就自动把钱付给对方，所以机器与机器之间通过数字钱包就可以做金融交易
5. 广义上讲去中心就是人人生来平等的哲学意义。这个世界目前是不平等的，穷富两级分化很严重。英国脱欧等正在发生的事情说明此思想正在变革着世界。
6. 类似滴滴、Uber、膜拜、airbnb等共享经济的思想已经在改变世界了，只不过他们不是真正的共享，如果建立在区块链技术上，完全可以没有这些平台同样获得相同的服务。

区块链现在面临的问题

目前区块链还处于非常早期的阶段，不仅尚未形成统一的技术标准，而且各种技术方案还在快速发展中，主要还停留在原型设计阶段。这既是后发国家的挑战，也是机会。

因为没有实践经验，所以做区块链带来的成本和带来的收益没有可靠的验证。以区块链首先涉足的金融领域为例。之前传统的基础设施投入已经超过数万亿，要建立一套全新的金融架构和基础设施是需要有实际数据相支撑的。我们需要第一个吃螃蟹的人。
最后一个问题是产业变革和技术变革时期，任何领域的共性问题：区块链行业极其缺乏人才，缺少大量既了解区块链，又了解具体行业的人才，跨界的高级人才越来越重要。