谈谈共识算法

谈谈共识算法

区块链装逼指南

最近开始疯狂补课，其实应该并入前一篇文章。把自己所学分享给大家。

先从一个思想实验开始，古代将军出兵作战，将军们需要彼此配合，派信使互相沟通，约定进军，回撤的时间和地点。那么问题来了，如果信使叛变了，被敌军收买或者胁迫了，提供的是假情报，怎么办？

那么，今天用情报学，密码学来说，这个可以做加密传输来解决，比如说，将军们出征前先彼此交换一个密码本，作为解密的关键文件，然后信使传递的是密文，信使也不知道真实内容，这样即使叛变或被收买，也无法生成合规的伪情报，很容易被发现。但我们这个条件再苛刻一些，假如连密码本都不可信了呢？将军们来自于天南地北，根本就没见过面，密码本都是信使传递的，这下怎么办？

好吧，答案揭晓，其实没办法。

如果彻底解决这个问题，在不可信的网络环境里建立可信的链接和信息交互，实话说，没有绝对的方案，但工程学的好处是，如果我们把容忍度放宽一点点，从概率来保障，那么，可能问题就会简单一点。

假设有多个信使，将军们通过多名信使彼此传递信息，如果我们认为，大部分信使都是可靠的，也就是说叛变的不占主要比例，当叛徒的存在低于某个特定比例时，那么就存在一种机制，可以找出叛徒，识别真实信息。

这个被称为拜占庭将军问题，是一个著名的共识算法的思想起源。

今天这篇文章不敢原创，节选网上的部分文字给大家，会附有有相关文章的原文链接

一致性问题

在分布式系统中，一致性(Consistency，早期也叫 Agreement)是指对于系统中的多个服务节点，给定一系列操作，在协议（往往通过某种共识算法）保障下，试图使得它们对处理结果达成某种程度的一致。

如果分布式系统能实现“一致”，对外就可以呈现为一个功能正常的，且性能和稳定性都要好很多的“虚处理节点”。

举个例子，某影视公司旗下有西单和中关村的两个电影院，都出售某电影票，票一共就一万张。那么，顾客到达某个电影院买票的时候，售票员该怎么决策是否该卖这张票，才能避免超售呢？当电影院个数更多的时候呢？

注意：一致性并不代表结果正确与否，而是系统对外呈现的状态一致与否，例如，所有节点都达成失败状态也是一种一致。

在实际的计算机集群系统（看似强大的计算机系统，很多地方都比人类世界要脆弱的多）中，存在如下的问题：

• 节点之间的网络通讯是不可靠的，包括任意延迟和内容故障；

• 节点的处理可能是错误的，甚至节点自身随时可能宕机；

• 同步调用会让系统变得不具备可扩展性。

要解决这些挑战，愿意动脑筋的读者可能会很快想出一些不错的思路。

为了简化理解，仍然以两个电影院一起卖票的例子。可能有如下的解决思路：

• 每次要卖一张票前打电话给另外一家电影院，确认下当前票数并没超售；

• 两家电影院提前约好，奇数小时内一家可以卖票，偶数小时内另外一家可以卖；

• 成立一个第三方的存票机构，票都放到他那里，每次卖票找他询问；

这些思路大致都是可行的。实际上，这些方法背后的思想，将可能引发不一致的并行操作进行串行化，就是现在计算机系统里处理分布式一致性问题的基础思路和唯一秘诀。只是因为计算机系统比较傻，需要考虑得更全面一些；而人们又希望计算机系统能工作的更快更稳定，所以算法需要设计得再精巧一些。

实际上，要保障系统满足不同程度的一致性，往往需要通过共识算法来达成。

共识算法解决的是对某个提案（Proposal），大家达成一致意见的过程。提案的含义在分布式系统中十分宽泛，如多个事件发生的顺序、某个键对应的值、谁是领导……等等，可以认为任何需要达成一致的信息都是一个提案。

注：实践中，一致性的结果往往还需要客户端的特殊支持，典型地通过访问足够多个服务节点来验证确保获取共识后结果。

实际上，如果分布式系统中各个节点都能保证以十分强大的性能（瞬间响应、高吞吐）无故障的运行，则实现共识过程并不复杂，简单通过多播过程投票即可。

很可惜的是，现实中这样“完美”的系统并不存在，如响应请求往往存在时延、网络会发生中断、节点会发生故障、甚至存在恶意节点故意要破坏系统。

一般地，把故障（不响应）的情况称为“非拜占庭错误”，恶意响应的情况称为“拜占庭错误”（对应节点为拜占庭节点）。

针对非拜占庭错误的情况，一般包括 Paxos、Raft 及其变种。

对于要能容忍拜占庭错误的情况，一般包括 PBFT 系列、PoW 系列算法等。从概率角度，PBFT 系列算法是确定的，一旦达成共识就不可逆转；而 PoW 系列算法则是不确定的，随着时间推移，被推翻的概率越来越小。

搞学术的人都喜欢对问题先确定一个界限，那么，这个问题的最坏界限在哪里呢？很不幸，一般情况下，分布式系统的共识问题无解。

当节点之间的通信网络自身不可靠情况下，很显然，无法确保实现共识。但好在，一个设计得当的网络可以在大概率上实现可靠的通信。

然而，即便在网络通信可靠情况下，一个可扩展的分布式系统的共识问题的下限是无解。

这个结论，被称为 FLP 不可能性 原理，可以看做分布式领域的“测不准原理”。

FLP 不可能性原理

FLP 不可能原理：在网络可靠，存在节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性算法。

提出该定理的论文是由 Fischer, Lynch 和 Patterson 三位作者于 1985 年发表，该论文后来获得了 Dijkstra（就是发明最短路径算法的那位）奖。

FLP 不可能原理实际上告诉人们，不要浪费时间去为异步分布式系统设计在任意场景下都能实现共识的算法。

科学告诉你什么是不可能的；工程则告诉你，付出一些代价，我可以把它变成可能。

这就是工程的魅力。

CAP 原理

CAP 原理最早由 Eric Brewer 在 2000 年，ACM 组织的一个研讨会上提出猜想，后来 Lynch 等人进行了证明。

该原理被认为是分布式系统领域的重要原理。

分布式计算系统不可能同时确保一致性（Consistency）、可用性（Availablity）和分区容忍性（Partition），设计中往往需要弱化对某个特性的保证。

• 一致性（Consistency）：任何操作应该都是原子的，发生在后面的事件能看到前面事件发生导致的结果，注意这里指的是强一致性；

• 可用性（Availablity）：在有限时间内，任何非失败节点都能应答请求；

• 分区容忍性（Partition）：网络可能发生分区，即节点之间的通信不可保障。

比较直观地理解，当网络可能出现分区时候，系统是无法同时保证一致性和可用性的。要么，节点收到请求后因为没有得到其他人的确认就不应答，要么节点只能应答非一致的结果。

好在大部分时候网络被认为是可靠的，因此系统可以提供一致可靠的服务；当网络不可靠时，系统要么牺牲掉一致性（大部分时候都是如此），要么牺牲掉可用性。

ACID 原则

即 Atomicity（原子性）、Consistency（一致性）、Isolation（隔离性）、Durability（持久性）。

ACID 原则描述了对分布式数据库的一致性需求，同时付出了可用性的代价。

• Atomicity：每次操作是原子的，要么成功，要么不执行；

• Consistency：数据库的状态是一致的，无中间状态；

• Isolation：各种操作彼此互相不影响；

• Durability：状态的改变是持久的，不会失效。

一个与之相对的原则是 BASE（Basic Availiability，Soft state，Eventually Consistency），牺牲掉对一致性的约束（最终一致性），来换取一定的可用性。

Paxos 与 Raft

Paxos 问题是指分布式的系统中存在故障（fault），但不存在恶意（corrupt）节点场景（即可能消息丢失或重复，但无错误消息）下的共识达成（Consensus）问题。因为最早是 Leslie Lamport 用 Paxon 岛的故事模型来进行描述而命名。

Paxos

1990 年由 Leslie Lamport 提出的 Paxos 共识算法，在工程角度实现了一种最大化保障分布式系统一致性（存在极小的概率无法实现一致）的机制。Paxos 被广泛应用在 Chubby、ZooKeeper 这样的系统中，Leslie Lamport 因此获得了 2013 年度图灵奖。

故事背景是古希腊 Paxon 岛上的多个法官在一个大厅内对一个议案进行表决，如何达成统一的结果。他们之间通过服务人员来传递纸条，但法官可能离开或进入大厅，服务人员可能偷懒去睡觉。

Paxos 是第一个被证明的共识算法，其原理基于 两阶段提交 并进行扩展。

作为现在共识算法设计的鼻祖，以最初论文的难懂（算法本身并不复杂）出名。算法中将节点分为三种类型：

• proposer：提出一个提案，等待大家批准为结案。往往是客户端担任该角色；

• acceptor：负责对提案进行投票。往往是服务端担任该角色；

• learner：被告知结案结果，并与之统一，不参与投票过程。可能为客户端或服务端。

并且，算法需要满足 safety 和 liveness 两方面的约束要求（实际上这两个基础属性是大部分分布式算法都该考虑的）：

• safety：保证决议结果是对的，无歧义的，不会出现错误情况。

  • 决议（value）只有在被 proposers 提出的 proposal 才能被最终批准；

  • 在一次执行实例中，只批准（chosen）一个最终决议，意味着多数接受（accept）的结果能成为决议；

• liveness：保证决议过程能在有限时间内完成。

  • 决议总会产生，并且 learners 能获得被批准（chosen）的决议。

基本过程包括 proposer 提出提案，先争取大多数 acceptor 的支持，超过一半支持时，则发送结案结果给所有人进行确认。一个潜在的问题是 proposer 在此过程中出现故障，可以通过超时机制来解决。极为凑巧的情况下，每次新的一轮提案的 proposer 都恰好故障，系统则永远无法达成一致（概率很小）。

Paxos 能保证在超过  的正常节点存在时，系统能达成共识。

Raft 算法是Paxos 算法的一种简化实现。

包括三种角色：leader、candidate 和 follower，其基本过程为：

• Leader 选举：每个 candidate 随机经过一定时间都会提出选举方案，最近阶段中得票最多者被选为 leader；

• 同步 log：leader 会找到系统中 log 最新的记录，并强制所有的 follower 来刷新到这个记录；

注：此处 log 并非是指日志消息，而是各种事件的发生记录。

拜占庭问题与算法

拜占庭问题更为广泛，讨论的是允许存在少数节点作恶（消息可能被伪造）场景下的一致性达成问题。拜占庭算法讨论的是最坏情况下的保障。

又叫拜占庭将军（Byzantine Generals Problem）问题，是 Leslie Lamport 1982 年提出用来解释一致性问题的一个虚构模型。拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（系统中的多个节点）需要通过信使来传递消息，达成某些一致的决定。但由于将军中可能存在叛徒（系统中节点出错），这些叛徒将努力向不同的将军发送不同的消息，试图会干扰一致性的达成。

拜占庭问题即为在此情况下，如何让忠诚的将军们能达成行动的一致。

对于拜占庭问题来说，假如节点总数为 N，叛变将军数为 F，则当  时，问题才有解，即 Byzantine Fault Tolerant (BFT) 算法。

新的解决思路

拜占庭问题之所以难解，在于任何时候系统中都可能存在多个提案（因为提案成本很低），并且要完成最终的一致性确认过程十分困难，容易受干扰。但是一旦确认，即为最终确认。

比特币的区块链网络在设计时提出了创新的 PoW（Proof of Work） 算法思路。一个是限制一段时间内整个网络中出现提案的个数（增加提案成本），另外一个是放宽对最终一致性确认的需求，约定好大家都确认并沿着已知最长的链进行拓宽。系统的最终确认是概率意义上的存在。这样，即便有人试图恶意破坏，也会付出很大的经济代价（付出超过系统一半的算力）。

后来的各种 PoX 系列算法，也都是沿着这个思路进行改进，采用经济上的惩罚来制约破坏者。

以上文字节选于 http://yeasy.github.io/ ，并对具体技术描述有大量删节。

作者是杨保华博士，目前是oracle中国区块链领域的首席架构师。

他发布的《区块链技术指南》这本书常有价值，机械工业出版社有线下出版，线上也有电子版本免费下载，有一定技术基础和对这个领域有兴趣的从业者，我强烈推荐深入阅读。而且线上版本有多个区块链开发架构安装和应用代码示例，对于快速启动区块链应用来说是有价值的。

下面是主流共识算法的另外一篇介绍引用

POW：Proof of Work，工作证明。

比特币在Block的生成过程中使用了POW机制，一个符合要求的Block Hash由N个前导零构成，零的个数取决于网络的难度值。要得到合理的Block Hash需要经过大量尝试计算，计算时间取决于机器的哈希运算速度。当某个节点提供出一个合理的Block Hash值，说明该节点确实经过了大量的尝试计算，当然，并不能得出计算次数的绝对值，因为寻找合理hash是一个概率事件。当节点拥有占全网n%的算力时，该节点即有n/100的概率找到Block Hash。

POS：Proof of Stake，股权证明。

POS：也称股权证明，类似于财产储存在银行，这种模式会根据你持有数字货币的量和时间，分配给你相应的利息。 
简单来说，就是一个根据你持有货币的量和时间，给你发利息的一个制度，在股权证明POS模式下，有一个名词叫币龄，每个币每天产生1币龄，比如你持有100个币，总共持有了30天，那么，此时你的币龄就为3000，这个时候，如果你发现了一个POS区块，你的币龄就会被清空为0。你每被清空365币龄，你将会从区块中获得0.05个币的利息(假定利息可理解为年利率5%)，那么在这个案例中，利息 = 3000 * 5% / 365 = 0.41个币，这下就很有意思了，持币有利息。

DPOS：Delegated Proof of Stake，委任权益证明

比特股的DPoS机制，中文名叫做股份授权证明机制（又称受托人机制），它的原理是让每一个持有比特股的人进行投票，由此产生101位代表 , 我们可以将其理解为101个超级节点或者矿池，而这101个超级节点彼此的权利是完全相等的。从某种角度来看，DPOS有点像是议会制度或人民代表大会制度。如果代表不能履行他们的职责（当轮到他们时，没能生成区块），他们会被除名，网络会选出新的超级节点来取代他们。DPOS的出现最主要还是因为矿机的产生，大量的算力在不了解也不关心比特币的人身上，类似演唱会的黄牛，大量囤票而丝毫不关心演唱会的内容。

PBFT：Practical Byzantine Fault Tolerance，实用拜占庭容错算法。见前文拜占庭容错算法介绍。 
PBFT是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。将所有的副本组成的集合使用大写字母R表示，使用0到|R|-1的整数表示每一个副本。为了描述方便，假设|R|=3f+1，这里f是有可能失效的副本的最大个数。尽管可以存在多于3f+1个副本，但是额外的副本除了降低性能之外不能提高可靠性。

以上主要是目前主流的共识算法。 

以上引用文字在知乎，csdn多处可见，所以我不确定原创在哪里，疑似为 http://blog.csdn.net/lsttoy/article/details/61624287 如有作者声明，我愿意提供更准确的原文链接。

下面是今天要特意分享的心得。

1、共识算法是在复杂网络环境，或者社会环境里，取得决策一致性的保障算法，从工程角度来说，也许所有的共识算法都不够完美，但是其概率保障依然是让人们可信赖的。

2、共识算法是人类智慧的结晶，多个图灵奖与此有关。而区块链技术的核心是共识算法。

3、区块链解决的共识问题有诸多实际应用场景，并且能极大减少当前金融系统及其他社会系统中的信用成本。发币只是诸多应用场景之一。

4、比特币基于POW共识算法，是共识算法中的一种，也正是因为这种共识算法需要计算力为证明，导致大量无谓的电费开销和能源消耗。但目前这种以计算力为证明的共识算法依然被认为是最公平的。

不依赖于计算力和矿池的共识算法是存在的，理论上也是可行的，也有一些区块链货币正在尝试使用，但目前来说，想要取代比特币，可能还任重道远。

5、经常有人问这个问题，为什么比特币这个现象如何突出，为什么人们会信赖一个虚拟货币，我以前解释过，重述一遍。从美国金融危机之后，强权政府失信，政府为货币背书的时代正在远去，这十年来，各国解决经济问题的手段，货币大幅度增发是常态，大幅度增发意味着什么？我们所持有的传统货币在高速贬值。那么算法共识，算法背书的时代正在来临，这是个大时代。区块链是一场革命，这一点毫无疑问，但我对比特币的未来一直心存疑虑，因为我觉得挖矿这个模式毕竟不是值得鼓励的。

此外，智能合约这事的想象力极大，应用场景极为广阔，撸猫只是很小的前奏。

6、我从不反对持有比特币或其他区块链货币，我反对的是炒币，投机短线，并把炒币当作区块链学习，这和赌博没区别。有评论说他炒币几个月赚了多少倍来反驳我，其实只是因为赶上了一波行情而已，在这波行情里，只要手里拿着币，傻子都有好几倍。

最后，为了与时俱进，我人生第一次开了比特币钱包

BTC钱包地址为：

1FHqiLzABhduss8A9HgayLzqE9xNeiFWbM

欢迎读者踊跃投喂，不过建议最大不要超过0.01BTC，好吧，其实也许多虑了。

至于这个地址字符串中间为什么有个gay，不要问我，我也不知道。

没有比特币的欢迎继续小程序投喂