区块链共识算法

1、分布式系统案例：售票系统

分布式系统的共识算法

在一个分布式系统中，如何保证集群中的所有节点中的数据完全相同且能够对某个提案（proposal）达成一致是分布式系统正常工作的核心问题，而共识算法就是用来保证分布式系统一致性的方法。

2、区块链和共识算法的关系

数字货币->双花问题->线性账目（区块链）->共识

3、分布式系统一致性

强一致性：任何时刻保持一致

顺序一致性(Sequential Consistency)：Leslie Lamport1979年经典论文《How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs》中提出，是一种比较强的约束，保证所有进程看到的全局执行的顺序（total order）一致，且每个进程看自身的执行（total order）跟实际发生顺序一致。例如某进程先执行A，后执行B，则实际得到的全局结果中就应该为A在B前面，而不能反过来。同时所有其他进程在全局上也应该看到这个顺序。顺序一致性实际上限制了各进程内的偏序关系，但不在进程间按照物理时间进行全局排序。

线性一致性(Linearizability Consistency )：Maurice P.Herlihy与Jeannette M.Wing在1990年经典论文《Linearizability:A Correctness Condition for Concurrent Objects》中共同提出，在顺序一致性前提下加强了进程间的操作顺序。形成唯一的全局顺序（系统等价于是顺序执行，所有进程看到的所有操作的顺序都一致，并且跟实际发生顺序一致），是很强的原子性保证。但是比较难实现，目前基本上要么依赖于全局的时钟或锁，要么通过一些复杂算法实现，性能往往不高。

弱一致性：某一时刻保持一致

强一致性的系统往往比较难实现。很多时候，人们发现实际需求并没有那么强，可以适当放宽一致性要求，降低系统实现的难度。例如在一定约束下实现所谓最终一致性（Eventual Consistency），即总会存在一时刻（而不是立刻），系统达到一致的状态，这对于大部分的Web系统来说已经足够。这一类弱化的一致性，被笼统称为弱一致性（Weak Consistency）。

不能达成一致性的两种情况

我们假设通讯是可靠的。那么我们把照成不能达成一致性的故障情况分为两种：

1、节点只是故障状态，不存在恶意节点，那么我们称“非拜占庭错误”。

2、存在恶意节点的分布式网络，我们称为“拜占庭错误”。

我们区块链面临的一致性问题为“拜占庭将军问题”。

4、分布式系统的同步和异步

同步系统：消息不丢失且秒到

异步系统：消息有延误且可能丢失

5、非拜占庭错误的两种解决方案

1、PAXOS

核心思想：Paxos解决这一问题利用的是选举，少数服从多数的思想，只要2N+1个节点中，有N个以上同意了某个决定，则认为系统达到了一致，并且按照Paxos原则，最终理论上也达到一致，不会再改变。这样的话，客户端不必与所有服务器通信，选择与大部分通信即可；也无需服务器都全部处于工作状态，有一些服务器挂掉，只有保证半数以上存活着，整个过程也能持续下去。

2、Raft

相比paxos的优点是容易理解，容易实现。它强化了leader的地位，把整个协议可以清楚的分割成两部分，并利用日志的连续性做了一些简化。

（1）Leader在时，由Leader同步日志。

（2）Leader挂掉了，选一个新Leader选举算法。

6、拜占庭将军的解决方案

对于可以容忍拜占庭错误的算法：PBFT、中本聪共识（POW）、POS和DPOS四种算法。

1、PBFT：更加实用的拜占庭容错方法。早期的BFT的缺陷：1、假定是同步场景；2、性能太慢（超过100个节点则不可用）。

PBFT算法的核心理论是n>=3f+1 : n是系统中的总节点数，f是允许出现故障的节点数。换句话说，如果这个系统允许出现f个故障，那么这个系统必须包括n个节点，才能解决故障。

PBFT算法在区块链中的应用

步骤：

1.从全网节点选举出一个主节点（Leader），新区块由主节点负责生成；

2.Pre-Preare：每个节点把客户端发来的交易向全网广播，主节点0将从网络收集到需放在新区快内的多个交易排序后存入列表，并将该列表向全网广播，扩散至1 2 3；

3.Preepare：每个节点接收到交易列表后，根据排序模拟执行这些交易。所有交易执行完后，基于交易结果计算新区快的哈希摘要，并向全网广播，1->023, 2->013，3为宕机无法广播；

4.Commit：如果一个节点收到的2f(f为可容忍的拜占庭节点数)个其他节点发来的摘要都和自己相等，就向全网广播一条commit消息。

5.Reply：如果一个节点收到2f+1条commit的消息，即可提交新区块及其他交易到本地的区块链和状态数据库。

2、中本聪共识（POW）

POW：一组通过算法生成的数据，难于生成而易于验证。1993年由Cynthia Dwork and Moni NAOR提出。

比特币使用的Hashcash proof of work由Adan Back在1997年发明，用于防止垃圾邮件和拒绝服务器攻击。Hashcash proof of work被中本聪用于比特币的挖矿。挖矿的过程是选择一个节点作为区块链生产者。

3、POS共识

POS：最早是由网名为“QuantumMechanic”的网友在比特币论坛中提出。其核心思想为拥有币权的人可以进行选举，选举出来大家最终谁来生成区块。

Native POS的面临的问题：nothing_to_stake

就如桌上有十个文件，每个人会在一个文件上签名，最后选出签名最多的一个文件，谁在签名最多的文件上签名就给谁发币。但有些作弊的人，在十个文件上都签字，最终不管哪个文件签名最多，它都能拿到币，这就nothing_to_stake。

现在以太坊用的共识算法是CASPER，CASPER是改进版的POS。

CASPER算法 、Native POS、POW对无力攻击的解决办法：

Native POS：

POS链上产生了分叉，不投票什么也没有，在A分支上投票得到的利益是0.9，在B分支上投票获得的利益是0.1，如果在两个分支上都投票获得的利益=0.1+0.9=1。

POW:

pow链上产生了分叉，不投票什么也没有，在A分支上投票得到的利益是0.9，在B分支上投票获得的利益是0.1，如果在两个分支上都投票获得的利益=0.1/2+0.9/2=0.5，因为POW要分散算力。

CASPER：

CASPER链上产生了分叉，不投票什么也没有，在A分支上投票得到的利益是0.9，在B分支上投票获得的利益是0.1，如果在两个分支上都投票获得的利益=0.1+0.9 -5 = -4，两边都投票会扣取你的5个保证金。还有一种更严格的方法，虽然你没有在两个分支上都投票，但你只有在短的分支上投票就扣你5个保证金。

4、DPOS共识：Delegated Proof of Stake

DPOS由BM提出：由代币持有者选择见证人节点，由一组见证人通过round-robi的方式轮流产生区块。在15/21个人对一个区块进行签名，然后区块得到确认。

DPOS对Nothing_to_stake的应对方案：让生产者被淘汰。“Miners”are now generally public,known individuals rather than anonymous individuals.

为什么是15/21个人可以达到共识？(n-(n-1)/3) 所以(21-(21-1)/3)=15

DPOS的理念：由持有者进行投票，最大化的分散持有者的规模，最小化的代价来加固网络（无需挖矿），最大化网络性能（超级节点），最小化运行网络成本（EOS每年会曾发代币的5%平分给超级节点）。

而DPOS就像一个公司一样运行，股东选举出董事会，董事会成员轮流生成区块，验证通过后上链。区块生产者既没有创造无效的区块的权力，也没有改变社区共识的权利。