共识算法

分布式共识算法可以分为CFT（Crash Fault Tolerance）与BFT（Byzantine Fault Tolerance）。

CFT

CFT算法如Paxos、Raft，只能容忍分布式节点中存在故障，不能容忍分布式节点中有节点作恶。适用于机器节点之间的通信，比如Raft，需要进行选主，如果选出的主发起恶意信息攻击，那么所有节点都会跟随主的propose去commit错误的信息；或者从节点控制伪造投票节点数量使自己在新term成为主节点恶意操控集群等。现在也有些改进的BFT On Raft、BFT On Paxos使得CFT也可以实现BFT的容忍级别。

BFT

BFT算法如PoW、PoS/dPoS、PoA、BFT/PBFT/dPBFT等，可以容忍节点故障同时也可以容忍部分节点作恶。当有节点作恶时只要存在一定数量的诚实节点，一样可以达到共识。BFT考虑与个人利益挂钩的情况，如果做一个不诚实的节点也就是拜占庭节点能够获取利益，那么总有人会去铤而走险用造假的方式来破坏系统。

PBFT/RBFT

PBFT：
分布式系统中考虑一个主节点与多个从节点，同时客户端会参与拜占庭容错模型中来。
v为当前视图，n为主节点分配的当前消息的请求序列号，D(m)为消息摘要，i为当前节点序列号。
pre-prepare
主节点收到来自客户端的请求时向所有从节点发送<pre-prepare,v,n,D(m)>，发起对一条消息的pre-prepare共识，通知从节点为该条消息做准备，此时从节点进入pre-prepared状态。
prepare
从节点对主节点propose的消息进行确认，从节点校验没有问题后主动向其他节点广播<prepare,v,n,D(m),i>，当当前节点接收到2f+1个来自其他节点的prepare消息，那么当前节点开始进入prepared状态。
commit
当前节点进入prepared状态后向其他节点广播<commit,v,n,i>消息，如果当前节点接收到2f+1个commit后说明已经达成共识使得序列号为n的消息m已经可以入库并向客户端返回commit。
view-change
1.当从节点发起提交后在timeout时间内没有接收到来自其他节点的提交消息
2.当从节点发起准备后在timeout时间内没有接收到来自其他节点的准备消息
3.从节点接收到了异常消息，如内容摘要与先前确认的不一致
此时从节点可认为主节点叛变，会发起视图变更、强制重新选主。
checkpoint
发送<checkpoint,n,D(m),i>检查集群状态是否已进入稳定状态，如稳定则可以触发垃圾回收，由于节点间交流信息也会占用存储空间，需要清除多余的消息。
RBFT在PBFT的基础上做了优化：优化消息数、添加集群动态增删节点的功能<addNode/deleteNode>等。主要的思路还是在PBFT的三阶段共识及视图变更选主。细节方面需要提及的是prepare阶段为了验证消息的准确性，会引入客户端对消息的数字签名，从节点会根据数字签名来判断消息是否有被篡改的情况；视图变更阶段也会灵敏的感受到系统中的异常从而及时变更止损。

拜占庭问题的两种解决方案

1.口信消息型拜占庭问题
通过多次广播数据来达成共识，只要大半的节点为诚信节点，经过每一次的传播消息的迭代一定能得出大部分的信息为真，少部分信息为假，此时忽略掉假的信息按照大多数信息结果进行抉择。要求为存在m个拜占庭节点时必须进行m+1轮协商，同时将军数必须大于3m+1。该方法迭代次数多，消息数量成指数级别增长，很难应用落地。
2.签名消息型拜占庭问题
签名意为有一对公钥和私钥，公钥加密的数据仅能由私钥进行解密，私钥加密的数据只能用公钥进行解密，私钥仅允许加密的人拥有，而公钥则是系统中公开的信息。现在某个客户端有一个加密的文件发送至网络中，网络中的节点需要校验该数据是否有被修改，于是他们分别用公钥对这个文件进行解密，如果解密成功，说明该文件确实是被客户端用私钥加密的源文件并未被修改，因为只有公钥能够解开私钥。
考虑一个班推选班长，以前是班里的同学各自思考是否考虑竞选，优先举手的同学作为候选班长，等待班里同学对其是否拥有当选班长的资格进行投票。此时就会出现同学根据其表面上资格（如时延、写库的日志数量多于其他节点）进行判断，而不了解他的实际为人，给了该候选班长作恶的可能性。现在通过签名算法的方式进化为可以成为候选班长的人携带了班主任的引荐书、家长的好评书等，选举过程变为先是全班同学中超过2/3的同学核对了引荐书的章印为真或好评书确实为家长的笔迹，此时就可以保证该候选班长实际为人确实不错，那么同学现在仅根据他当前的表现（是否拥有最多的日志index等）在纸上签下自己的名字认可其成为班长，最终当超过2/3的同学签名后表明候选班长竞选成功。
之前提到签名算法主要是私钥加密、公钥解密。此时引荐书和好评书为私钥加密的数据，每个同学都拥有公钥来验证引荐书或好评书是否为真（公钥可以理解为每个人都拥有印章验证能力，能印证引荐书上的章的真假）。如果大多数同学都解密成功，说明是老师本人亲手写的引荐书。可以看出签名算法需要引入外部的一些签名证明。由于数字签名比较消耗性能，现在大多使用消息验证码MAC、或者直接在硬件中实现加解密。

Shamir门限签名算法

该算法会引入(k-1)次多项式和拉格朗日插值定理，以及一个密钥随机数生成中心。
1.先生成一个随机数得到全局公钥为x，全局私钥为v。
2.随机生成一个(k-1)次多项式使得P(0)=x，从而得到P(i)=xi。也即每个节点i都可以拥有一个公钥的解xi，同时每个节点i也拥有一个不公开的私钥vi。
3.每个节点对同一个消息M(i)进行各自的私钥签名，并将消息流通出去。
4.其他节点接收到节点i的加密消息后用节点i的公钥进行解密，解密成功说明节点i已经确认过M(i)，那么其他节点就可以在自己的小本本上记下节点i已阅消息M(i)并表示赞同。
5.有一个节点汇总得到系统中已有t个节点确认过该消息后，计算这t个节点的完整签名，根据拉格朗日插值定理可以知道任意t个节点产生的完整签名是相同的。

可以看到该算法可以确认，在一个分布式系统中，t个节点已经确认过该条消息，从而避免了存在拜占庭节点对消息进行篡改捏造，影响全局判断。等下会介绍的Raft算法中存在消息RequestVote和AppendEntries，如果有节点对这些消息进行伪造，那么就会误导整个系统对错误的消息达成共识。引入大多数节点对这些消息的签名，也就是要求大多数节点都真真切切的确认过这些消息，只要大多数节点都是诚实节点，拥有准确的日志数据以及客户端的消息公钥，那么就可以确认来自客户端的消息是否被Leader节点修改，以及判断Leader节点是否是为民服务的诚实节点。

基于签名对CFT进行拜占庭容错的改进

Raft简述
在Raft的基础上也可以构建拜占庭容错的算法。
Raft有3种状态模型：Leader、Candidate、Follower。主要分为两步，Leader节点选举以及日志复制，其中包含两种消息RequestVote和AppendEntries。当Leader节点宕机时（Follower接收不到来自Leader的心跳），各个Follower开始进入随机选举超时时间，优先结束等待该时间的节点可以作为Candidate发起RequestVote消息要求Follower对其进行投票，此时投票数最多的Candidate当选Leader，Leader节点会发送AppendEntries消息到所有Follower节点，当AppendEntries消息仅为心跳时告知所有节点当前该节点是被选举出来的Leader节点，当AppendEntries消息为日志信息时告知Follower节点当前需复制该日志并对日志内容进行写库。当Leader收到超2/3的节点已经完成了写库，便会向客户端的发送commit信息表明该日志已写库，剩余1/3的节点可能因为网络差或者宕机导致没有进行响应，在故障修复后也会被Leader带动逐步的向Leader所含有的全部信息收敛。从而Leader带动Follower逐步达成共识，实现1/3的节点故障容错的能力。
传统Raft无法实现拜占庭容错在于恶意节点会伪造投票使其被选为主节点，一旦恶意节点为当前的主节点，那么其余节点都会去追随恶意节点的日志消息进行写库。如果想让Raft实现拜占庭容错首要解决的问题就是保证选举出来的主节点是诚实节点，同时主节点传播的消息也是诚实消息。
1.解决当选的主节点一定为诚信节点：
当选Leader节点的一个必要条件是获得了2/3节点的投票，拜占庭节点会为了占据Leader位置而伪造投票，此时可以利用上面提到的签名算法来让系统中大多数节点确认该节点的RequestVote消息。如果有节点认为其不可当选Leader，就不会对这个消息进行签名，当一定数量的节点都不对该消息进行签名，那么其就无法当选Leader。比如可以对比拜占庭节点中的日志与当前节点的日志，如果日志数据不对则说明是一个造假节点，则不对其进行投票的签名，而是转而向其他Candidate节点进行投票。Raft中本身就有一套验证一个节点是否有资格当选Leader节点的规则（如拥有较长日志Index的节点获胜等），当越来越多的节点纳入确认流程，总有办法识破拜占庭节点。
2.解决Leader节点广播的消息一定是准确的：
Leader节点如果在当选后起了歹心，开始利用自己是Leader的身份进行消息造假。此时分布式系统中各个节点要做的就是核验AppendEntries消息中数据的真假，此时需要客户端对自己提交的请求在达到Leader之前用客户端自己的私钥进行加密，同时公开公钥给各个节点。各节点对AppendEntries里客户端的请求数据进行解密，如果解密成功说明数据并未被Leader节点进行修改。
3…

关于区块链

区块链可以理解为一个去中心化的分布式数据库，是一个典型的拜占庭问题。
当某个客户端产生了一笔交易信息后，会使用加密算法进行交易的验证，之后将交易放入buffer中，在一段时间内产生的交易都存入buffer(也称作区块)中。
在区块大约为2M时将该区块广播给全网中的所有节点，其余节点接收到广播后，其上的矿工为了赚取打包该区块的gas收益，通过共识机制用自己的算力竞争打包资格，如果成功则向全网广播自己的证明结果及生成的区块信息，剩余节点不再执着于该区块，将新的区块信息链在当前链中，转而再去处理新的交易信息。
在区块链中主要就是通过交易验证和区块验证以提高作恶成本。通过HASH以及Merkle Tree能够快速验证交易信息是否被篡改。由于每一笔交易在区块链中都是公开信息，如果有节点想造假要么修改交易信息，要么修改区块信息。交易信息通过公钥私钥进行加密，只有当交易双方都通过验证此时该交易才会实际生成。一段时间内的交易都会存在一个buffer中，矿工要做的就是打包该buffer形成一个区块，然后将该区块广播给所有节点验证，其他节点验证成功后将该区块追加在自己的链后。如果矿工在在打包前修改了交易信息并且通过共识算法有资格打包该区块（比如凭空创造一条转账或者双花），都会被其他节点验证时发现（因为区块内容是公开信息，其他节点都可以根据区块内容进行加密判断HASH结果是否一致，如果一致则与自己的上一个区块的HASH值进行Merkle Tree的计算），就算一次两次未被验证出来，该造假也需要六次以后才会被所有节点接受，这就要求六次该区块都要连续修改区块信息隐藏之前的造假并且还需要连续得到打包的机会，这个概率通过概率论可以得出可能性几乎为0。
或者造假的矿工拼命打包使得自己成为当前区块链中最长的链时，其他节点会抛弃自己现有的链直接接纳当前最长的链，该成本也很高，在PoW下要求至少掌握51%以上的算力才可以成为最长链。在PoS下需要掌握大量的币龄（拥有的比特币*该币闲置的时间，每次打包成功后币龄降为0，用币龄兑换比特币gas费用）。
如果一次造假被发现就会被分叉出去不能再参与区块链的任何交易。可见通过高昂的造假成本以及花费大量精力与电力使得区块链的造假变难。后来的几次区块链比特币问题也基本都是在合约层面从区块链上层的钱包中利用漏洞进行欺骗。存在共识机制的公链基本没出过大问题。

参考文献：
[1]一种结合 BLS 签名的可拜占庭容错 Raft 算法