共识算法与拜占庭将军问题

1 共识机制

  • 共识机制，即多个个体达成一致的机制。
  • 共识机制可以根据达成共识的个体，分为算法共识和决策共识。

算法共识致力于研究复杂的网络环境下，去中心化的网络如何达成一致的问题，本质是多个机器达成共识。决策共识目的是帮助人达成一致，在分布式人工智能领域较为常见。区块链中共识算法属于前者，目的在于在多个节点中记录同样的账本。

  • 区块链中共识机制要求满足两个性质：一致性，即不同的节点记录的数据必须相同；有效性，节点记录的数据格式和内容必须满足区块链规则。
  • 共识机制面对场景多种多样，共识机制的设计也多种多样，然而共识机制的本质始终相同，即消耗资源以换取信任。因此，共识机制的评判标准可以总结为“消耗多少资源，换取多少节点的信任，换取 信任的程度，换取信任的速度，换取是否需要前提条件”，即资源消耗问题、节点扩展性问题、安全性问题、效率问题以及开放性问题。不同的场景中对以上问题的注重程度不同，因此所适用的共识机制不同。

2 共识算法

区块链有三大类型：私链、联盟链及公链，各有其相应的共识算法。
公有链的任何节点都是向任何人开放的，每个人都可以参与到这个区块链中进行计算，而且任何人都可以下载获得完整区块链数据(全部账本)。不仅需要考虑网络中存在故障节点，还需要考虑作恶节点，并且节点可以很自由的加入或者退出，不需要严格的验证和审核。（PoW、PoS、DPoS）
联盟链是指有若干机构或组织共同参与管理的区块链，他们各自运行着一个或多个节点，之中的数据只允许系统内不同的机构进行读取和发送交易，并且共同记录交易数据。联盟链并不是完全去中心化的理论上联盟之间可以联合起来修改区块链数据。除了需要考虑集群中存在故障节点，还需要考虑集群中存在作恶节点。每个新加入的节点都是需要验证和审核的。（PBFT）
私有链指写入权限完全在一个组织手里的区块链，所有参与到这个区块链中的节点都会被严格控制。一般是不考虑集群中存在作恶节点，只考虑因为系统或者网络原因导致的故障节点。（Raft）

2.1 PoW算法

PoW(Proof Of Work)工作量证明。PoW是指一方提交已知难以计算但易于验证的计算结果，而其他人都能够通过验证这个结果确信提交方为了求得结果已完成了大量的计算。

通俗的来说，在PoW共识机制中，挖矿是指利用有计算能力的设备来进行哈希计算，这个计算的过程就是工作量，通过不断的计算来得出一个合理的哈希值，这就是所谓的解题。当有人或者节点得出了这一个合理的哈希值，那么他就可以获得记账权，记录区块链上的交易记录，这个记录就是产出区块，获得记账权就会得到一定量比特币的奖励。

2.2 PoS算法

PoS（Proof of Stake）权益证明。由系统中具有最高权益而非最高算力的节点获得区块记账权。权益体现为节点对特定数量货币的所有权，称为币龄。币龄是区块链的一个重要的概念，即每笔交易的金额（币）乘以 这笔交易的币在账上留存的时间（天）。

例如当前全网的目标是4369，A矿工的输入的币龄是15，那么A矿工的目标值为65535，换算成十六进制就是0xFFFF，完整的哈希长度假设是8位，也就是0x0000FFFF。
而B矿工比较有钱，他输入的币龄是240，那么B矿工的目标值就是0x000FFFFF。你如果仔细观察肯定会发现，相比A矿工的目标值，B直接少了一个零。即如下：
A 矿工 Hash( block_header ) < 0x0000FFFF
B 矿工 Hash( block_header ) < 0x000FFFFF
　　所以B矿工获得记账权的概率肯定要比A高。

2.3 DPoS算法

DPoS（Delegated Proof of Stake）授权股份证明。通过实施去中心化的民主方式，每个币相当于一张选票，持有币的人可以根据自己持有币的数量来将自己的若干选票投给自己信任的受托人。系统会选出获得投票数量最多的N个人作为系统受托人，他们的工作是签署（生产）区块，且在每个区块被签署之前，必须先验证前一个区块已经被受信任节点签署。

2.4 PBFT算法

PBFT(Practical Byzantine Fault Tolerance)实用拜占庭容错。其为基于消息传递的一致性算法，算法经过三个阶段达成一致性。拜占庭容错能够容纳将近1/3的错误节点误差。

假设节点总数为3f+1，f为拜赞庭错误节点：
1.当节点发现leader作恶时，通过算法选举其他的replica为leader。
2.leader通过pre-prepare消息把它选择的value广播给其他replica节点，其他的replica节点如果接受则发送prepare，如果失败则不发送。
3.一旦2f个节点接受prepare消息，则节点发送commit消息。
4.当2f+1个节点接受commit消息后，代表该value值被确定。

如何理解？通过一个例子来说明。

A.其中C为发送请求端，0123为服务端，3为宕机的服务端。
B.Request阶段：请求端C发送请求到服务端0。
C.Pre-Prepare阶段：服务端0收到C的请求后进行广播，扩散至123。
D.Prepare阶段：服务端123收到后记录并再次广播，1->023，2->013，3因为宕机无法广播。
E.Commit阶段：0123节点在Prepare阶段，若收到超过一定数量的相同请求，则进入Commit阶段，广播Commit请求。
F.Reply阶段：0123节点在Commit阶段，若收到超过一定数量的相同请求，则对C进行反馈。

2.5 Raft算法

  • Raft是一个用于管理日志一致性的协议。它将分布式一致性分解为多个子问题：Leader选举（Leader election）、日志复制（Log replication）、安全性（Safety）、日志压缩（Log compaction）等。

  • Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选人（Candidate）。

    Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。
Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。
Candidate：Leader选举过程中的临时角色。

  • Term即任期。用连续的数字进行表示。每一个任期的开始都是一次选举（election），一个或多个候选人会试图成为领导人。如果一个候选人赢得了选举，它就会在该任期的剩余时间担任领导人。在某些情况下，选票会被瓜分，有可能没有选出领导人，那么，将会开始另一个任期，并且立刻开始下一次选举。Raft 算法保证在给定的一个任期最多只有一个领导人。

  • RPC即程过程调用。服务器节点间的通信时使用。

    RequestVote RPC：候选人在选举期间发起。
AppendEntries RPC：领导人发起的一种心跳机制，复制日志也在该命令中完成。
InstallSnapshot RPC: 领导者使用该RPC来发送快照给太落后的追随者。

如何选举？

(1)Raft 使用心跳（heartbeat）触发Leader选举。当服务器启动时，初始化为Follower。Leader向所有Followers周期性发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat，就会等待一段随机的时间后发起一次Leader选举。

(2)每一个follower都有一个时钟，是一个随机的值，表示的是follower等待成为leader的时间，谁的时钟先跑完，则发起leader选举。Follower将其当前term加一然后转换为Candidate。它首先给自己投票并且给集群中的其他服务器发送RequestVote RPC。

  赢得了多数的选票，成功选举为Leader。
  收到了Leader的消息，表示有其它服务器已经抢先当选了Leader。
  没有服务器赢得多数的选票，Leader选举失败，等待选举时间超时后发起下一次选举。

Leader选举的限制：能被选举成为Leader的节点，一定包含了所有已经提交的日志条目。

日志复制（保证数据一致性）

Leader选出后，就开始接收客户端的请求。Leader把请求作为日志条目（Log entries）加入到它的日志中，然后并行的向其他服务器发起 AppendEntries RPC复制日志条目。当这条日志被复制到大多数服务器上，Leader将这条日志应用到它的状态机并向客户端返回执行结果。

安全性保证

拥有最新的已提交的log entry的Follower才有资格成为leader。
Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志，旧term日志的提交要等到提交当前term的日志来间接提交。

日志压缩

在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。Raft采用对整个系统进行snapshot来解决，snapshot之前的日志都可以丢弃（以前的数据已经落盘了）。每个副本独立的对自己的系统状态进行snapshot，并且只能对已经提交的日志记录进行snapshot。

成员变更

Raft解决方法是每次成员变更只允许增加或删除一个成员（如果要变更多个成员，连续变更多次）。【参考：解读Raft（四 成员变更）】

3 拜占庭将军问题

拜占庭将军问题由莱斯利·兰伯特提出的点对点通信中的基本问题，主要是用于分析在分布式节点传输信息时如何保持数据的一致，即共识这个问题。

「拜占庭将军问题」来源于这样一个场景：
拜占庭帝国的军队正在围攻一座城市。这支军队被分成了多支小分队，驻扎在城市周围的不同方位，每支小分队由一个将军领导。这些将军们彼此之间只能依靠信使传递消息（无法聚在一起开个会）。每个将军在观察自己方位的敌情以后，会给出一个各自的行动建议（比如进攻、撤退或按兵不动），但最终的需要将军们达成一致的作战计划并共同执行，否则就会被敌人各个击破。但是，这些将军中可能有叛徒，他们会尝试阻止其他忠诚的将军达成一致的作战计划。

这就是拜占庭将军的「问题」：只能依靠通信相互交流，又不知道谁是叛徒，怎么能不受叛徒们的影响，让这些忠诚的将军快速的达到一致的作战计划呢？很显然，将这一场景套用到计算机系统中也是非常适用的：在一个分布式系统中，针对每个运算，每台独立的机器也需要最终达成一致的结果。但每台计算机之间也只能依靠网络通信（显然它们无法聚在一起开会），每台计算机都有出错的可能（被攻击，或故障），从而变成「叛徒」干扰正常的计算机达成一致。

  • PBFT算法的提出主要是为了解决拜占庭将军问题
  • 工作量证明其实相当于提高了做叛徒（发布虚假区块）的成本，在工作量证明下，只有第一个完成证明的节点才能广播区块，竞争难度非常大，需要很高的算力，如果不成功其算力就白白的耗费了（算力是需要成本的），用这样的算力作为诚实的节点，同样也可以获得很大的收益（这就是矿工的工作），这也不会产生做叛徒的动机，整个系统也因此而更稳定。很多人批评工作量证明造成巨大的电力浪费，这促使人们去探索新的解决一致性（共识）问题的机制：权益证明机制（PoS）则是一个代表。在拜占庭将军问题的角度来看，它同样提高了做叛徒的成本，因为账户持有的余额越多则获得记账权的几率就越大，而一旦发现作假就会没收账户余额。DPoS是权益证明的一种改进版本，共识过程不再需要所有参与节点进行验证，而是委托部分代表来进行，很大程度上提高了共识效率。共识算法的核心就是解决拜占庭将军问题（分布式网络一致性问题），提高作假成本，从而保证超过51%的节点都是诚实节点，达到共同维护区块链账本的结果。
  • Paxos和Raft是另外两种经典的共识算法，准确的说应该是分布性一致算法，它们都是为了解决非拜占庭问题下实现分布式系统数据一致性的问题（主要防范节点故障，而非节点作恶）。这个过程如同选举一样，参选者需要说服大多数选民(服务器)投票给他，一旦选定后就跟随其操作。

参考资料

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/20199321zjy/p/12860470.html