1、共识机制
区块链采用去中心化的设计，节点是各处分散且平行的，所以必须设计一套制度，来维护系统的运作顺序与公平性，统一区块链的版本，并奖励提供资源维护区块链的使用者，以及惩罚恶意的危害者。这样的制度，必须依赖某种方式来证明，是由谁取得了一个区块链的打包权（或称记账权），并且可以获取打包这一个区块的奖励；又或者是谁意图进行危害，就会获得一定的惩罚，这就是共识机制。
共识算法是区块链项目的核心之一，每一个运行着的区块链都需要一个共识算法来保证出块的有效性和有序性。
在以太坊的官方源码中，有两个共识算法：clique和ethash，它们都位于以太坊项目的consensus目录下。clique目录下的代码实现的是PoA(权威证明，Proof of Authority)共识；在ethash目录下实现的是PoW(工作量证明，Proof of Work)共识。
在以太坊中clique仅在测试网络里使用，真实的以太坊主网还是使用PoW算法（ethash模块实现）。但在自己组成私有网络时，你可以自由选择使用clique还是ethash。
2、POA需要解决的主要问题
PoA的基本思想来源于现实世界：授权一定数量的“专家”，由这些人相互合作打包区块并对区块链进行维护，其它人则无权打包区块，并且普通人相信成为“专家”的人会努力维护区块链的正常秩序。
“专家”需要公开自己的身份。这也是PoA设计初衷的一部分：设计者认为每个人都是爱惜自己的声誉的，通过公开自己身份，专家会为了自己的声誉努力做正确的事，而不是作恶。
PoA共识中出块权掌握在部分“专家”手里，而普通人是无法参与的（无论你有多少算力、多少权益）。可见PoA共识牺牲了一部去中心化的特性，换来了一种可控性。
为了描述的一致性，我们将“专家”称为“签名者”，即有权生成新区块并签名的账号地址。
PoA的实现，必须要解决好这两个问题。
问题1：如何实现签名者的引进和踢出
PoA的第一个问题是需要解决签名者更换的问题。在PoA中，签名者必须保证多数情况下在线出块。然而随着项目的不断运行，不可能所有签名者都一直有资源、有意愿继续工作；另外偶尔签名者也会作恶，必须及时将作恶的人踢出。（作为对比，在PoW中，任何一个人都可以随时接入区块链网络并尝试出块，也可以随时退出网络）
问题2：如何控制出块时机
首先要明确的是，出块时机由两方面决定：一是出块时间；二是由谁出块。在PoA中，签名者之间是合作关系，大家“和和气气”，什么时间出块、由谁出都要按规则来，不能争不能抢。因此需要有良好的规则控制出块时机。（作为对比，在PoW中，出块时间根据历史出块记录动态调整；由谁出块是由算力决定的：算力越强，越能获得出块权。可见在PoW中签名者之间是竞争的关系，出块时机由能力确定）
下面我们看看clique是如何解决这些问题的。
3、clique的设计概要
clique模块的原作者在这篇文章里详细说明了clique的设计和背景。
为了表达清晰，我们需要提先说明几个原文中的数据和名词的定义：
（1）checkpoint: 一个特殊的block，它的高度是EPOCH_LENGTH的整数倍，block中不包含投票信息但包含当时所有的签名者列表
（2）SIGNER_COUNT: 某一时刻签名者的数量
（3）SIGNER_LIMIT: 连续的块的数量，在这些连续的块中，某一签名者最多只能签一个块；同时也是投票生效的票数的最小值
（4）BLOCK_PERIOD: 两个相邻的块的Time字段的最小差值，也是出块周期
（5）EPOCH_LENGTH: 两个checkpoint之间的block的数量。达到这个数量后会生成checkpoint以及清除当前所有未生效的投票信息
（6）DIFF_INTURN: 出块状态（difficulty）之一，此状态代表“按道理已经轮到我出块”
（7）DIFF_NOTURN: 出块状态（difficulty）之一，此状态代表“按道理还没轮到我出块”
以上信息的进一步解释：
epoch and checkpoint：
在clique中，有一个值叫做"epoch"。当一个block的高度恰好是"epoch"值的整数倍时，这个block便不会包含任何投票信息，而是包含了当前所有的签名者列表。这个block被叫做checkpoint。可以看出，checkpoint类似于一个“里程碑”，可以用来表示“到目前为止，有效的签名者都记录在我这里了”；而epoch就是设立里程碑的距离。
"epoch"的存在，是为了避免没有尽头的投票窗口，也是为了周期性的清除除旧的投票提案。更进一步地，在checkpoint中存在的签名者列表，可以让节点间基于中间某个checkpoint就可以同步到签名者列表，而不需要整个链上的数据。
Snapshot：
Snapshot对象是clique中比较重要的一个对象，它的作用是统计并保存链的某段高度区间的投票信息和签名者列表。这个统计区间是从某个checkpoint开始（包括genesis block），到某个更高高度的block。在Snapshot对象中用到了两个重要的结构体：Vote和Tally，我们先对它们进行一下说明，再来详细说一下Snapshot结构体。
Vote struct：
Vote代表的是一次投票的详细信息，包括谁给谁投的票、投的加入票还是踢出票等等。它的结构体定义如下：
type Vote struct {
Signer common.Address // 此次投票是由谁投的
Block uint64 // 此次投票是在哪个高度的block上投的
Address common.Address // 此次投票是投给谁的
Authorize bool // 这是一个加入票（申请被投人成为签名者）还是踢出票（申请将被投人踢出签名者列表）
}
Tally struct：
Tally结构体是对所有被投人的投票结果统计。注意它与Vote结构体的区别：Vote是投票过程的记录（如A给B投了一个授权票），而Tally是对结果的统计（类似于选班长唱票时计票员在黑板上画的“正”字）。Tally的定义如下：
type Tally struct {
Authorize bool // 这是加入票的统计还是踢出票的统计
Votes int // 目前为止累计的票数
}
如果只看这里你可能会意外这里并没有“针对谁进行的统计”的信息，这是因为Tally在Snapshot结构体是是作为map的一部分的，参看下面对Snapshot结构体字段的说明。
inturn and noturn：
前面说过，clique作为PoA的实现，挖矿的人之间是合作关系，因此需要有规则规定某一时刻应该由谁出块。在clique中，inturn状态代表的是“按道理轮到我出块了”，而noturn正好相反。
在代码中，inturn的值为diffInTurn，noturn的值为diffNoTurn。Header.Difficulty字段用来保存相应的值，它的计算方式非常简单，具体可以查看Snapshot.inturn方法，这里不再多说。
在Clique.Seal方法中，签名时会进行一定时间的等待。如果Header.Difficulty的值为diffNoTurn，则会比diffInTurn的块随机多等待一些时间，通过这种方式可以保证轮到出块的人可以优先出块。代码如下：
func (c *Clique) Seal(chain consensus.ChainReader, block *types.Block, results chan<- *types.Block, stop <-chan struct{}) error {
......
//计算正常的等待出块时间
delay := time.Unix(header.Time.Int64(), 0).Sub(time.Now()) // nolint: gosimple
if header.Difficulty.Cmp(diffNoTurn) == 0 {
//没有轮到我们出块，多等一会
// It's not our turn explicitly to sign, delay it a bit
wiggle := time.Duration(len(snap.Signers)/2+1) * wiggleTime
delay += time.Duration(rand.Int63n(int64(wiggle)))
log.Trace("Out-of-turn signing requested", "wiggle", common.PrettyDuration(wiggle))
}
......
}
clique中最重要的两个数据结构:
一是共识引擎的结构:
type Clique struct {
config *params.CliqueConfig // 系统配置参数
db ethdb.Database // 数据库: 用于存取检查点快照
recents *lru.ARCCache //保存最近block的快照, 加速reorgs
signatures *lru.ARCCache //保存最近block的签名, 加速挖矿
proposals map[common.Address]bool //当前signer提出的proposals列表
signer common.Address // signer地址
signFn SignerFn // 签名函数
lock sync.RWMutex // 读写锁
}
二是snapshot的结构:
type Snapshot struct {
config *params.CliqueConfig // 系统配置参数
sigcache *lru.ARCCache // 保存最近block的签名缓存,加速ecrecover
Number uint64 // 创建快照时的block号
Hash common.Hash // 创建快照时的block hash
Signers map[common.Address]struct{} // 此刻的授权的signers
Recents map[uint64]common.Address // 最近的一组signers, key=blockNumber
Votes []*Vote // 按时间顺序排列的投票列表
Tally map[common.Address]Tally // 当前的投票计数，以避免重新计算
}
除了这两个结构, 对block头的部分字段进行了复用定义, ethereum的block头定义:
type Header struct {
ParentHash common.Hash
UncleHash common.Hash
Coinbase common.Address
Root common.Hash
TxHash common.Hash
ReceiptHash common.Hash
Bloom Bloom
Difficulty *big.Int
Number *big.Int
GasLimit *big.Int
GasUsed *big.Int
Time *big.Int
Extra []byte
MixDigest common.Hash
Nonce BlockNonce
}
（1）创世块中的Extra字段包括:
- 32字节的前缀(extraVanity)
- 所有signer的地址
- 65字节的后缀(extraSeal): 保存signer的签名
（2）其他block的Extra字段只包括extraVanity和extraSeal
（3）Time字段表示产生block的时间间隔是:blockPeriod(15s)
（4）Nonce字段表示进行一个投票: 添加( nonceAuthVote: 0xffffffffffffffff )或者移除( nonceDropVote: 0x0000000000000000 )一个signer
（5）Coinbase字段存放 被投票 的地址
- 举个栗子: signerA的一个投票:加入signerB, 那么Coinbase存放B的地址
（6）Difficulty字段的值: 1-是 本block的签名者 (in turn), 2- 非本block的签名者 (out of turn)
4、clique如何解决问题
接下来我们看一下clique是如何解决上一节提到的两个问题的。
解决问题1：如何实现签名者的引进和踢出
clique中签名者的引进和踢出是通过已有签名者进行投票实现的，并且加入了更加详细的控制。
下面我们看一下clique中的投票规则：
（1）投票信息保存在block中。一个block只有一个投票信息，且只能在自己生成的block上保存。
（2）针对某个被投人的票数超过SIGNER_LIMIT时，投票结果立即生效。
（3）投票生效后，立即清除所有被投人是当前生效人的投票信息。如果投的是踢出票，则被投人之前投出的、但还未生效的投票全部失效。
（4）踢出一个签名者以后，可能会导致原来不通过的投票理论上可以通过。clique不特意处理这种情况，等待下次统计时再判断。
（5）发起一个投票后，客户端不会被立即清除投票信息，而是在之后每次出块时都会选一个继续投票。因为区块链中的有效区块有重新调整的可能性，所以不能认为投票生效了之后就会一直生效。
（6）无效的投票：被投票人不在当前签名者列表中但投的是踢出票，或被投票人在当前签名列表中但投的是引进票。
（7）为了使编码简单，无效的投票不会受到惩罚（其实我认为有些功能实现也依赖于无效的投票）。
（8）在每个EPOCH_LENGTH内，一个签名者给同一个账号地址重复投票时，会先将上次的投票信息清除，然后再统计本次的投票信息（如果本次为无效的投票不会恢复已经清除的上次投票信息）
（9）每个checkpoint不进行投票，而只是包含当前签名者列表信息。对于其它区块，可以用来携带投票信息。
上面重复投票的处理处理方式会产生两个结果（假设投票人是A，被投票人是B）：
（1）在当前EPOCH_LENGTH内，A给B只能投一票；
（2）在当前EPOCH_LENGTH内，如果给B的投票未生效（总票数未超过SIGNER_LIMIT）时A想把投给B的票撤消，那么A可以投一次跟之前相反的票。因为新的投票会导致旧的投票信息清除，而如果旧的投票是有效的则新的投票必定是无效的，因而也不会进入投票统计。
解决问题2：如何控制出块时机
前面我们说过，出块时机由两方面决定：一是出块时间；二是由谁出块。下面我们看看clique是如何解决这些问题的。
（1）出块时间：在clique中，出块时间是固定的，由BLOCK_PERIOD决定。
（2）由谁出块：clique中出块权的确定稍微复杂，具体规则为：
- 签名者在签名者列表中且在SIGNER_LIMIT内没出过块
- 如果签名者是DIFF_INTURN状态，则拥有较高出块权（等待出块时间到来，签名区块并立即广播出去）
- 如果签名者是DIFF_NOTURN状态，则拥有较低出块权（等待出块时间到来，再延迟一下（延迟时间为rand(SIGNER_COUNT * 500ms)）
可见出块权由两方面确定：一是最近是否出过块，如果出过则没有出块权；二是DIFF_INTURN / DIFF_NOTURN状态，IFF_INTURN拥有较高出块权。
理解这些规则以后，我们就可以自己实现一个PoA共识算法了。
5、工作流程
PoA的工作流程如下:
（1）在创世块中指定一组初始授权的signers, 所有地址 保存在创世块Extra字段中
（2）启动挖矿后, 该组signers开始对生成的block进行 签名并广播.
（3）签名结果 保存在区块头的Extra字段中
（4）Extra中更新当前高度已授权的 所有signers的地址 ,因为有新加入或踢出的signer
（5）每一高度都有一个signer处于IN-TURN状态, 其他signer处于OUT-OF-TURN状态, IN-TURN的signer签名的block会 立即广播 , OUT-OF-TURN的signer签名的block会 延时 一点随机时间后再广播, 保证IN-TURN的签名block有更高的优先级上链
（6）如果需要加入一个新的signer, signer通过API接口发起一个proposal, 该proposal通过复用区块头 Coinbase(新signer地址)和Nonce("0xffffffffffffffff") 字段广播给其他节点. 所有已授权的signers对该新的signer进行"加入"投票, 如果赞成票超过signers总数的50%, 表示同意加入
（7）如果需要踢出一个旧的signer, 所有已授权的signers对该旧的signer进行"踢出"投票, 如果赞成票超过signers总数的50%, 表示同意踢出
这张图里隐藏了Snapshot的功能。整个出块的功能主要由Prepare和Seal完成。在Prepare中准备一些与PoA相关的信息，在Seal中进行签名出块。需要特别注意的是，出块的时间是在Seal中控制的，而非miner中。
6、投票策略
因为blockchain可能会小范围重组(small reorgs), 常规的投票机制(cast-and-forget, 投票和忘记)可能不是最佳的，因为包含单个投票的block可能不会在最终的链上,会因为已有最新的block而被抛弃。
一个简单但有效的办法是对signers配置"提议(proposal)".例如 "add 0x...", "drop 0x...", 有多个并发的提议时, 签名代码"随机"选择一个提议注入到该签名者签名的block中,这样多个并发的提议和重组(reorgs)都可以保存在链上.
该列表可能在一定数量的block/epoch 之后过期，提案通过并不意味着它不会被重新调用，因此在提议通过时不应立即丢弃。
（1）加入和踢除新的signer的投票都是立即生效的,参与下一次投票计数
（2）加入和踢除都需要 超过当前signer总数的50% 的signer进行投票
（3）可以踢除自己(也需要超过50%投票)
（4）可以并行投票(A,B交叉对C,D进行投票), 只要最终投票数操作50%
（5）进入一个新的epoch, 所有之前的pending投票都作废, 重新开始统计投票
投票场景举例：
（1）ABCD, AB先分别踢除CD, C踢除D, 结果是剩下ABC
（2）ABCD, AB先分别踢除CD, C踢除D, B又投给C留下的票, 结果是剩下ABC
（3）ABCD, AB先分别踢除CD, C踢除D, 即使C投给自己留下的票, 结果是剩下AB
（4）ABCDE, ABC先分别加入F(成功,ABCDEF), BCDE踢除F(成功,ABCDE), DE加入F(失败,ABCDE), BCD踢除A(成功, BCDE), B加入F(此时BDE加入F,满足超过50%投票), 结果是剩下BCDEF。
参考文档：
（1）https://www.jianshu.com/p/2be997c4705a
（2）https://www.jianshu.com/p/7a979813d368
