引言
共识机制作为区块链技术的核心，从根本上决定了整个系统的安全性、可用性和系统性能等
区块链概述
特点
- 去中心化：网络中没有可信第三方
- 去信任化：节点之间不需要彼此信任，通过共识机制达成对账本的一致认识
- 公开透明性：任何节点可以随时加入退出，可以获得区块链的历史账本数据，接收到新生成的区块
- 不可篡改性：区块链中的历史数据不能被非法篡改
- 匿名性：保护隐私数据
共识概述
决定参与节点以何种方式对某些特定的数据达成一致
分为经典的分布式共识机制和区块链共识机制
区块链共识机制：
授权共识：网络节点通过了PKI身份认证后才能参与后续共识机制
非授权共识：节点随时加入退出，节点数量动态变化，通过特定算法完成出块者选举、区块生成和节点验证、更新
区块链共识机制的基本流程
- 选举出块者：目前的出块者可以分为两种，一种是单一节点作为出块者，另一种是多个节点构成委员会，整个委员会作为出块者。选举过程中需要考虑女巫攻击，需要完成一定的任务或者条件才能够成为出块者。目前大多数采用Pow和Pos
- 生成区块：出块者将一段时间内网络中的交易打包放进当前区块中，为了使区块链成为链状结构，在其中包含其他内容。区块分为区块头和区块体。区块头包含了上个区块的哈希值、时间戳；区块体包含完整的交易数据。目前可以按照出块者与区块的对应关系将区块生成过程分为两类：一类是一对一关系，一个出块者对应一个区块；一对多关系意味着一个出块者在其任期期间能够生成多个区块，一般将一个出块者的任职时间称为一个时期(epoch)，每个任期由多轮组成，每轮生成一个区块
- 节点验证更新区块链：出块者生成区块后，将区块在网络中广播，收到区块的节点验证区块正确性并更新本地区块链。部分共识机制中节点需要验证区块交易合法性和出块者的身份合法性
评价标准
- 安全性：考虑敌手存在且操纵一定的网络资源和其他资源的情况下，诚实用户在不可信的网络环境下达成一致
- 交易吞吐率：区块链系统的交易处理速度，一般采用每秒钟处理交易的数量作为评判标准，一般受到区块产生间隔、区块大小和网络延时等因素的影响
- 可扩展性：网络处理交易的性能是否随着节点的增多而增强，网络处理能力的可增长性，一般采用分片来实现，每个分片并行处理网络内部的数据
- 交易确认时间：交易被提交至网络到最终被完全确认所需要的时间，完全确认是指交易被写入区块且大概率不会被篡改，以此作为凭证完成交易过程。比特币中大概为60分钟。确定性共识中交易确认时间降低
- 去中心化：区块链采用的共识机制没有可信第三方，区块由参与公式的节点共同决定，而不是集中在少数几个节点上，网络中的权力应当分散化而不是集中化，矿池一定程度上影响了比特币的去中心化
- 资源占用：节点间的通信复杂度和节点的计算复杂度
模型和定义
定义
- 状态机复制：存在一组节点且所有节点共同维护一个线性增长的日志，就日志内容达成一致
- 节点中存在一个主机。在可容忍的范围内，允许一定比例的节点出现故障或遭受敌手攻击。需要满足一致性和活性
- 一致性：满足诚实节点最终输出日志一致
- 活性：在一定时间内出现在所有诚实节点的日志中
- 常用于大型数据库的同步
- 快速响应特性：交易确认时间与网络真实时延有关，与网络时延上限无关
- 授权共识：授权网络中PKI存在且为每个节点实施身份认证。注册完成后，每个节点都能活着所有参与者节点数量和身份。运行共识机制，实现状态机复制，完成账本的生成和维护，并将账本以区块链的形式实现。
- 非授权共识：节点不需要身份认证，无身份认证，由于网络动态变化，节点无法获知所有参与者节点数量和身份；通过一定的共识机制实现状态机复制
- 公共账本：能够满足一致性和活性的可信公告牌，任何人都能在上面存放消息，任何人都能读账本；对状态机复制的延伸，保证了在非授权网络中公开透明、任何节点能够随时访问、添加信息。满足以下两个安全特性
- 持续性：诚实用户在某个位置上传了合法交易，则最终所有诚实用户的张本忠该位置一定存在该交易
- 活性：某个时间诚实用户上传了交易至公开账本，等待若干时间后，该交易一定出现在每个诚实用户账本中
- 共同前缀：$Q_{cp}$表示。任意两个诚实节点提交的节点在去掉末尾k个区块后一定具有前缀关系
链质量：安全参数$\mu \in \mathbb{R},k,k_0 \in \mathbb{N}$，任何城市节点P的链C中除去最新的$k_0$区块后，任意k个连续的区块中，恶意区块的比例不超过$\mu$
- 链质量属性是指连续的区块中必定有足够比例的区块由诚实用户产生
链增长：安全参数为$\tau \in \mathbb{R},s,r_0 \in \mathbb{N}$，对于任意轮r（r>$r_0$)，城市节点P在第r轮输出的区块链为$C_1$，在第$r+s$轮输出的区块链为链C_2，满足$|C_2|-|C_1|\geq \tau \cdot s$
- 弱一致性：根据出块者选举的方式，同一个时期可能有两个甚至以上合法的出块者，区块链可能出现分叉，但是很长一段时间后最终的区块链是确定的
- 强一致性：生成的区块是确定的，确定性共识方案。通过选择一个确定的委员会，再由委员会内部运行的分布式一致性算法生成新区块，每一轮的区块都是确定的，一般不会分叉
- 无分叉，节点无需花费大量算力
- 交易确认速度快，上传的交易写入区块中便可以确保合法性
- 前向安全性（forward security），只要区块被写入到区块链上，可以确保区块不会被篡改，将一直保持在链上
容错类型
拜占庭容错：分布式系统中发生了任意类型的错误，错误的节点少于一定比例都能保证可靠性
- PBFT BFT-Smart
- 联盟链、公链
非拜占庭容错：只能保证节点宕机等错误发生时系统的可靠性
- Paxos、Raft
- 私有链（没有恶意节点）
模型分类
网络模型
- 同步网络：诚实节点之间的消息按照轮来传播，在每一轮中诚实用户发出的消息能够在下一轮之前到达所有其他诚实用户。比较强的网络模型
- 部分同步网络：网络中的消息传输存在一定的上限$\Delta$，时延上限不能作为协议的参数使用，能够确保诚实用户发出的消息在$\Delta$时间后到达所有诚实用户；属于区块链协议分析中常用的网络模型
- 异步网络：敌手能够任意拖延诚实用户的消息或者打乱顺序，只需要保证最终诚实用户的消息能够到达彼此
腐化模型
腐化指敌手通过向目标节点发动攻击，获取目标节点的秘密信息，进而控制目标节点的输入输出消息，使其完全受到自身的控制
- 静态敌手：敌手只能在协议开始前选定其腐化的目标，一旦协议开始运行便不能腐化诚实节点。敌手控制的节点数量在协议运行期间不会改变
- $\tau-$温和敌手：敌手腐化一个节点需要一定的时间$\tau$，在该时间内节点仍然属于诚实节点。属于区块链协议分析中常用的腐化模型
- 适应性敌手：是指敌手能够根据协议运行过程中手机的信息，动态且适应性地对目标节点完成腐化
敌手模型
对敌手能够掌握的算力或财产占比做出一定的限制，一般用f代表敌手数量，n代表网络中节点总数，利用n与f的关系来刻画敌手模型
- $n=2f+1$：敌手算力占全网算力比例不超过1/2
- 比特币
- $n=3f+1$：PBFT等经典分布式共识机制要求敌手模型；一些混合共识也需要这样的约束
- $n=4f+1$：由于自私挖矿导致链质量下降，某些混合共识
经典分布式共识机制
在授权网络中，一组节点实现状态机复制。主要面向分布式数据库系统，Paxos针对网络中可能出现的崩溃节点；PBFT能够容忍一定的拜占庭错误节点。
根据网络模型可以分为：
- 部分同步网络分布式一致算法
- 异步网络分布式一致算法
- 同步网络分布式一致算法
部分同步网络分布式一致算法
Paxos
包含了主节点和备份节点的概念，允许多个主节点同时进行提议，赋予不同的等级；等级高的主节点的提议可以打断低等级的主节点提议（即使低等级的主节点已经得到了备份节点的承诺消息）。广泛应用于分布式系统中数据库的维护，只能对恶意节点容错，无法对拜占庭节点（恶意节点）实现容错
- 主节点向全网超过1/2的备份节点发送准备消息
- 备份节点验证消息合法性，通过后向主节点返回承诺信息
- 主节点收集足够多的承诺消息，组成承诺凭证，主节点向备份节点发送包含承诺凭证的accept消息
- 备份节点验证接受消息的合法性，通过后向主节点发送accepted消息
PBFT
$n=3f+1$，网络模型为部分同步网络
分布式共识达成过程：
- 请求：客户端上传请求消息m至网络中的节点，包括主节点和其他备份节点
- 预准备：主节点收到客户端上传的请求消息m，赋予消息序列号s，计算得到预准备消息$(pre-prepare,H(m),s,v)$
- 准备：备份节点收到主节点的预准备消息，验证$H(m)$的合法性，即对于视图v和序列号s来说，备份节点先前未收到其他消息。验证通过后，备份节点计算准备消息并广播。所有节点收集准备消息，大于2f+1则组成certificate发送
- 执行：
To do
继续阅读
需要补充学习的经典机制：Paxos PBFT
学习女巫攻击 DOUCEUR J R. The Sybil attack[C]. In: Peer-to-Peer Systems—IPTPS 2002. Springer Berlin Heidelberg, 2002: 251–260. [DOI: 10.1007/3-540-45748-8_24]