首先声明，这里只是单纯的知识分享，很多内容均来源于网络上的文章，有些来源已记载，有的可能没注意；此外，我自己也写了很多，所以具体哪些是我哪些是外部来源已然混乱…… 总之，把这当成一个学习文档来看就好！这是我在学习各公链时收集整理而成的。整理、理解以及写作不易，如果对你有帮助，可以右上角关注下twitter，我会在那里即时更新动态。
对了，这些内容皆为我在MatrixDAO做infra研究时整理的初稿（只会放扩容和共识算法这两部分的初稿，之后会等DAO发布后才会贴上），部分内容存在一些错误，但我觉得对新手来说完全够用了（毕竟区块链行业的更新迭代太快了）。经过review和修改后的版本暂时没有发布，如果发布了我再把链接贴在这里。
部分原理普及
分布式帐本系统
区块链技术是一种依赖于算法实现高信任度的分布式记账技术，区块链网络中的各个节点通过共识机制达成对网络中交易的共识确认。
在区块链诞生以前，人类记录复杂商业活动中的资金流动依靠于复式记账法，经过几百年的更新优化，复式记账法已经成为现代会计学的基础。“复式”的意思为，任意一笔经纪业务都需要用相等的金额在两个或以上相关账户中进行登记，由此可以更为全面反映经纪业务的全貌，并且方便检查账户记录的准确性。
但复式记账法存在一些问题：
1、账本由单一记账人维护，账本的正确性与不可篡改性由记账人的声誉或资产担保，而这种担保往往是不可靠的。当造假/作恶能带来巨大利益时，记账人倾向于通过造假来牟利。
2、经济业务与记账规则纷繁庞杂，记账人不免漏记、误记。
3、发生经济联系的业务双方账本不一致时，无法追溯真实业务。
为了解决这些信任问题，需要专业机构对账目进行审计，这会带来额外成本，并且无法根除这些问题。而由分散的节点存储数据、由参与交易的各方共同维护同一个账本的记账方式，则可以避免以上问题，这就是分布式账本。
随着技术与市场需求的发展，分布式账本的概念开始延伸，其功能不再局限于单纯的“记账”，而是扩展为一个可以“增添记录”的数据结构，这种“增添记录”的行为导致了系统“状态”的改变。通过维护这样一个共同的数据结构，所有节点（分布式系统的一个工作单元称为节点）都共享了其安全性与便利性。
这对分布式账本系统提出了更高的要求：
1、任意节点都能够存储账本（或者至少一部分），以随时检验账本的正确性。
2、任意节点均只能将被认可/校验的记录加入账本，防止记录被恶意篡改；
3、记录一旦被公认加入账本，便无法再行修改；
4、减少消息丢失，降低消息延迟；
密码学的引入，为解决这些问题做出了很大的帮助。
私钥与非对称加密
A给B转账，需要A的签名，如何保证签名的合法性（即，该签名的确由A签出）？
A必须拥有一个独一无二的标识，而“私钥”，承担了这一角色。
私钥是一串256位的二进制随机数，通常会被转换为十六进制。也就是说，私钥的总量有2^256之多，这是一个极大的数字，理论上来说，凭现代计算机的能力暂时无法利用枚举的方式来猜出一个人的私钥。这保证了私钥的安全性。
从应用角度，私钥作为持有者独一无二的身份标识，其必须在不泄露的前提下能向其他人证明这一点。这就引出了非对称加密算法。非对称加密算法大多是由哈希函数实现的，哈希函数是一类函数的统称，需要满足以下条件：
- 输入可为任意大小的字符串，输出为固定大小；
- 能进行有效计算，即给定输入，能在合理时间范围内输出；
- 无法从输出值反推出入值；
- 防哈希碰撞，即不存在简单的方法找到输出结果相同的另一个输入值；
- 谜题友好性，即除了随机猜测，没有更好的方法求解目标函数；
通过私钥生成公钥，但由于非对称加密，已知公钥无法得出私钥。公钥与私钥的不同特性可以在消息的广播与签名中发挥了不同作用。
举例来说，A给B发消息，希望网络中其他人知道的确是由A发出消息但却又无法得知消息内容（称为“广播”），便可以将消息用B的公钥加密并用自己的私钥签名。用B的公钥加密的作用是，网络中所有人都能够收到加密后的消息，但只有B可以用自己的私钥解密，获取消息内容。用自己的私钥签名是因为，网络中其他人都是已知A的公钥的，因此大家可以用A的公钥验证A的确是消息的发出者（签名人）。
交易可能会被重复广播。为了解决这个问题，每一笔交易都需要附带一个独一无二的编号，这个编号就是该笔交易的哈希值。重复的广播如果哈希值相同，就意味着这是同一笔交易。
区块内容
区块链可以看作是由链式连接的区块组成的，每个区块可分为区块头和区块体，区块头的内容包括：版本号、前一区块hash、随机数、时间戳、merkle根、目标难度。
各内容的作用如下：
| 作用 | |
|---|---|
| 版本号 | 表示本区块遵守的验证规则 |
| 前一区块hash | 使用SHA256算法对父区块头进行二次哈希计算得到，可以明确、唯一标识父区块 |
| 随机数 | 根据目标难度随机设定，以保证符合条件的哈希值生成过程不受操控 |
| 时间戳 | 证明区块生产时间；每个时间戳的hash值都会被纳入上一个时间戳，形成链 |
| merkle根 | 将原始交易数据的hash值进行组合，形成唯一的根节点 |
| 目标难度 | 该区块工作量证明算法的难度目标 |
区块体则包含了需要打包进区块中进行确认的交易数据，如图：
一个区块所包含的数据内容
区块高度与哈希值
区块高度，指的是区块的编号，也就是一个区块与创世区块之间的块数。创世区块是一条区块链上的第一个区块，要注意的是，创世区块的区块高度是0，而不是1。我们查询某个区块信息的时候，除了通过它的哈希，还可以通过它的区块高度进行查询。
区块高度是区块的标识符。区块有两个标识符，一是区块头的哈希值，二是区块高度。区块头的哈希值是通过SHA-256算法对区块头进行二次哈希计算而得到的数字。区块哈希值可以唯一、明确地“标识”一个区块，并且任何节点通过简单地对区块头进行哈希计算都可以独立地获取该区块哈希值。
而区块高度是指该区块在区块链中的位置。区块高度并不是唯一的“标识”符。虽然一个单一的区块总是会有一个明确的、固定的区块高度，但反过来却并不成立，一个区块高度并不总是识别一个单一的区块。两个或两个以上的区块可能有相同的区块高度，在区块链里争夺同一位置。
需要注意的是，在【私钥与非对称加密】部分所提及的哈希值，是针对单笔交易而言，可以作为单笔交易唯一的“标识符”。一个区块内可以包含多笔交易，这些交易的哈希值将会组成merkle树，merkle根将被放入区块头中。对区块头进行哈希计算，才能得到整个区块的哈希值，二者是不同的。
账本工作流程（以BTC为例）
假设A要使用比特币网络发起一笔转账交易，将会有以下步骤：
①A在钱包中用私钥对自己的比特币签名，转账给B（发起一次交易）；
②交易信息在网络各个节点中广播；
③节点们将这笔交易打包进候选区块，开始进行哈希计算（PoW），以赢取记账权；
④某个节点最快，获取了记账权，生成新区块，同时向全网广播；
⑤各节点认可，并以该区块为最新区块继续进行记账；六个区块过后，该交易将会被区块链永久储存；
在比特币中，实际采用UTXO(unspent transaction outputs)模型来实现转账。以上述A转账给B为例，假设A拥有1个比特币，这其实意味着前一个交易将1个比特币输入A的地址，但并没有输出；A转账1个比特币给B实际意味着，对这笔交易进行签名，将其输出地址设置为B。
UTXO实际上是一个状态转换系统，每一个比特币区块链中的交易都是一个状态转换函数，ETH也使用了类似的设计逻辑。UTXO的一个好处是无需核查一个地址的所有历史交易，对于任意交易，只需沿着该交易逐级向上核查即可。
如果某个货币的最新交易已经被足够多的区块覆盖，早先的交易就可以被丢弃以节省磁盘空间。交易被写进merkle树，由于只有根节点被纳入区块的哈希值，老的区块可以通过剪除树枝的方式被压缩，如下图：
用户只需要拥有一个最长工作量证明链的区块头副本，就可以通过向其他网路节点查询进行确认，只要诚实节点控制着网络，这种简化的验证就是可靠的。而如果被恶意节点控制了51%以上的算力，网络安全性就会受到威胁，这就是著名的51%攻击。
区块链架构
学术论文研究中，通常将区块链架构分为三层，其中，layer0为数据传输层，layer1为链上的底层账本，layer2为应用扩展层。
而在工程应用领域，区块链架构可分为六层，自下而上为数据层、网络层、共识层、激励层、合约层、应用层。早期比特币系统上不设合约层。
- 数据层。区块链最底层的数据结构，从创世区块起，到与不断新增的区块一起构成的链式结构，里面封装了目标哈希、时间戳、公钥私钥、交易信息等数据。节点间通过共识算法来维护数据层数据的一致性，通过非对称加密和哈希算法来保证数据的不可篡改和可追溯性。
- 网络层。区块链的分布式网络系统，本质上是一个P2P网络，网络中所有资源和服务被分配在各个节点中，由节点去共同维护网络。当一个节点生产出新的区块时，会以广播形式告知其他节点，收到信息的节点会对该区块进行验证，再基于该区块生产新的区块。由此，节点们保持联系、共同维护整个区块链账本。
- 共识层。通过网络中所有节点一致认可的统共识算法机制来维护及更新区块链账本。不同区块链将根据自身的特点与需求设计不同的共识机制，包括工作量证明（PoW）、权益证明（PoS）委托权益证明（DPoS）等。
- 激励层。激励层建立了一套激励机制，给予节点参与生产区块（挖矿）、验证交易信息等行为予奖励，同时惩罚作恶节点，以激励全网节点共同参与区块链的建设维护，并保证其安全性与可靠性。
- 合约层。合约层包括各种算法与智能合约，是区块链可编程的基础。智能合约将代码嵌入到系统中，设置约束条件，无需第三方背书即可实现实时操作。
- 应用层。基于区块链的数据层、网络层、共识层、激励层、合约层建立的各种应用，是区块链技术落地的一层。
将区块链分层结构与OSI模型、TCP/IP体系4层模型对比：
来源：火币区块链研究院
最大的变化在于两点：
（1）区块链设计了基于分布式系统的共识算法，利用密码学设计广播与验证机制实现共识，以进行信息传递；
（2）除去信息传递，基于共识层与激励层的设计，区块链可以实现价值传递；
注：关于区块链架构分层不同角度具有不同说法，本文选取技术角度的主流观点。
随着区块链技术研究的深入，以及应用场景的不断拓宽，传统的区块链架构也在不断发生着变化，例如在联盟链与私有链中，由于并不需要代币机制去激励矿工出块进行维护，因此它们是不具有激励层。
区块链扩容
1、扩容的必要性
（1）区块链扩容的“三难困境”
“三难困境”由vitalik提出，用于解释区块链旨在拥有的三个属性：可扩展性、去中心化和安全性，在目前的技术水平下，我们至多只能实现其中的两个。三个属性的含义分别为：
- 可扩展性意味着区块链可以处理大量事务，以每秒事务数 (TPS) 衡量。
- 去中心化意味着区块链由世界各地的许多“去信任”节点运行——而不是由一小群集中的“受信任”节点运行。
- 安全性意味着即使网络中一定百分比的节点是恶意的，区块链也能抵抗攻击。
（2）交易需求的提升使区块链拥堵
BTC区块大小的上限为1MB，每10分钟左右产生一个区块，TPS（Transactions Per Second，每秒事务处理量）约为3.5（理论TPS可达到7）；ETH单个区块大小约20KB，每15s左右生产一个区块，TPS约15。当待处理交易数超过tps承载上限时，便会产生网络拥堵。交易签名被广播后，交易将进入矿工的待打包交易池，矿工将优先打包支付gas更高的交易，进而导致“飙gas大战”。用户将不得不为在拥堵期间需要确认的交易支付极高的成本。
（3）为什么不能单纯地提高区块容量/出块频率？
在传统的区块链设计中，**每笔交易都需要网络中全节点处理和验证，**区块体积越大，扩散至整个网络所需要的时间就越多；更高的传播用时或者更短的出块间隔时间都意味着孤块、分叉概率上升，即一个新的区块尚未充分全网广播前，另一个矿工就有可能已经产出另一个区块。
此外，大区块要求更高的存储及带宽成本，普通节点陆续退出，导致算力中心化、安全性降低。
2、扩容途径
根据对区块链架构的主流观点，可将其分为三大层：layer0负责数据传输，layer1是公链的基础协议，包含数据层、网络层、共识层、激励层，layer2是应用生态。而对应的扩容改进方案也可以分为第0层扩容、第1层扩容和第2层扩容。
第0层扩容通过改变区块链底层数据传输协议提升可扩展性；第1层扩容通过改变公链基础协议如区块数据结构、共识机制、激励措施等提升扩展性；第2层扩容不改变公链基本协议，在应用层通过链下方式提升可扩展性。
（1）第0层扩容
第0层扩容通过优化区块链底层数据传输协议提升区块链可扩展性，主要方式有覆盖网络和快速UDP互联网连接协议。
-
覆盖网络
矿工通过使用中继网络来加快数据传播，进而缩短区块传播时间。中继网络的节点具有低延迟和高带宽的特点，分布在全球各地，矿工可以连接到离他们最近的中继节点，这比P2P网络要快许多。
在中继网络基础上提出了BDN(Blockchain Distribution Network)。在保证去中心化与安全性的基础上，BDN可以综合考虑网络状况、节点负载等情况，为用户分配最高效的服务节点。 -
QUIC(Quick UDP Internet Connection)
UDP即User Datagram Protocol，可以提供一种无需建立连接就可以发送封装的IP数据包的方法。QUIC整合了TCP协议的可靠性和UDP协议的高效性，加快了数据传输速度，例如在Harmony区块链中即应用了QUIC协议。
（2）第1层扩容
第1层扩容，即链上（On-Chain）扩容，通过优化、改进公链基本协议提升扩展性。分别针对数据层、网络层和共识层提出改进方案。
-
数据层改进方案
1、通过增加区块容量，使得单个区块包含的交易数量增加。从理论上说，在平均区块间隔固定的情况下，网络TPS上限与区块大小成正比。但由于节点处理能力、算力中心化等问题，区块的大小不能无节制随意扩大。
2、隔离见证。被打包进区块的交易数据包括数字签名和其他交易信息，其中数字签名占据全部交易数据60-70%的空间，但其仅在验证阶段需要，用以验证交易真实合法。隔离见证则将数字签名单独拿出来放入新的数据结构，既不影响数据完整性，也提升了单个区块所能容纳的交易数量，变相扩大了区块大小。
3、频率扩容指提高区块生成频率，从而增加单位时间内生成区块的数量。实现方式主要有两种：（1）降低出块难度，以缩短出块时间间隔。但这会增加孤块出现的频率，造成计算资源浪费；同时由于节点间需要进行更多通信，也增加了网络带宽的压力。（2）将选举记账节点与打包区块的流程分开，每个epoch选出一个leader节点，由leader节点生成主块。主块不包含具体的交易数据，而包含对上一个区块的引用、时间、公钥以及nonce等可以证明自己是leader节点的信息；具体的交易信息则由微块记录，由于无需消耗算力，生成速度会变得很快。缺点是容易引发网络阻塞，且容易受到51%攻击。
4、DAG（有向无环图）。在DAG中，从一个节点沿任意方向出发，无法回到原点（无环）。DAG设计可以使得每笔新的交易都可以单独作为区块提交，只需验证在其之前的任意数个区块即可；数据的记录存储是并行的，打破传统设计中链式串行存储结构。DAG可以有效避免因网络延迟和数据同步造成的时间浪费，具有良好的高并发性能，但有可能会受到双花攻击、影子链攻击。
-
网络层改进方案
当前网络层的扩容方案主要是分片技术（sharding），它借鉴数据库的分片思想，在网络层将节点进行分片，每个分片网络各自进行共识，并行的处理交易，以此来提升区块链的吞吐量。
根据分片对象不同，可将分片技术分为网络分片、交易分片、状态分片。
网络分片即将整个区块链网络划分为多个子网络，一个子网络为一个分片。
交易分片在网络分片的基础上，将全网交易划分到不到分片中，并行验证交易数据。
状态分片在网络分片基础上，每个分片仅存储部分账本信息，提升了系统效率。相比于交易分片，状态分片能从本质上解决区块链性能扩展问题，但实现难度大，且具有一定的安全风险。
网络分片是分片的第一步，其带来一个不可忽视的问题：子网络（分片）的验证节点数量远低于分片前的整体，这种算力稀释容易造成针对单个分片的集中攻击；分片间也需要克服双花攻击、跨链交易原子性、跨片交易DDoS攻击等。
-
共识层改进方案
包括拜占庭容错（BFT，Byzantine Fault Tolerance）类共识、非BFT类共识和混合共识（Hybird Consensus）。
（1）BFT类共识。BFT类共识下，参与者通过投票决定共识内容直接达成共识。BFT共识下，达成一致的共识不会被丢弃，因此BFT的响应时间明显优于非BFT类共识。BFT类共识的主要问题在于网络规模、容错率等方面。
（2）非BFT类共识。通过降低共识算法复杂度和减少传播节点数量等方式减少验证时间、传播时间及形成共识时间，能够显著提升处理效率。
PoS，相比于PoW，以权益（持有通证数量×通证持有时间）代替算力决定区块记账权，减少了PoW工作量证明过程的能源消耗，在一定程度上解决了可扩展性问题。但是又带来了马太效应、记账激励、无利害关系攻击（Nothing-at-Stake attack）等新的问题。
DPoS（Delegeted Proof of Stake，委托权益证明）。DPoS在PoS的基础上将记账人的角色专业化，通证持有人通过权益选出多个授权代表，授权代表轮流记账。这种共识下效率得到了明显提升，但是牺牲了非中心化。
（3）混合共识。混合共识指结合了多种方式的共识机制，如Casper采用了PoW+PoS，EOS采用了DPoS+BFT。
关于共识机制的具体内容之后的文章将详细介绍。
（3）第2层扩容
第2层扩容，也叫链下扩容，它不改变区块链的基本协议，将执行层从主网中剥离开来，通过链下改进提升扩展性。
区块链上的“计算”又称为“状态生成”，在一般的计算模型里，不存在信任和安全问题，只需生成计算结果就好，不需要验证；但区块链除了计算出交易结果，还需要对其进行验证。通过Layer2协议，区块链事务的“状态生成”可以独立于Layer1之外进行，因此这些协议也可以称为“链下”扩容方案。链下扩容方案设计的核心就是链下数据的正确及安全地传回链上。
链下扩容的安全性（状态验证）由链上支持 ，具体技术方案包括状态通道、链下计算、侧链等。
-
状态通道（state channel）
状态通道的思路是将部分交易转移到链下，只将通道开启和关闭时的状态记录在区块链上。状态通道内的交易视为结算，在链下实现；需要脱离状态通道进行交易时视作清算，链上实现。区块链将由结算平台转变为清算平台，当交易双方无异议时可以很快完成清算，实现即时终结性（Instant Finality）。
状态通道可以显著降低区块链上的交易数量，间接提升交易处理能力并降低交易手续费。同时由于交易均发生于状态通道，并不进行广播，具有很好的隐私性。但状态通道比较依赖交易方的在线，如果参与方之一无法在质疑时间内做出有效回应，清算将会被强制执行；掉线者可以选择雇佣他人保存状态副本，以维护自己的权益。
利用状态通道交易的流程一般为：
①交易方在链上锁定一定量的资产，在区块链上记录并开辟状态通道；
②在通道内进行相互交易和状态更新（链下）；
③当任一方想要关闭通道时，提交最终状态到区块链上进行清算。若另一方有异议，可通过提交带有时间戳的最新状态进行链上申诉；欺诈行为若被坐实，将被没收抵押物。
采用状态通道的方案包括：闪电网络（Lighting Network）、雷电网络（Raiden Network）。关于状态通道需要解决的主要技术难题见这里。
-
链下计算（off-chain computation）
链下计算最初针对以太坊提出，由于以太坊存在Gas Limit，计算量大的交易消耗gas多，将导致链上拥堵，链下计算的思路是将复杂的交易放到链下执行，结果提交回链上，链上只作数据验证，以此间接提升区块链处理交易的速度，但是也要保证高水准的隐私性和安全性。实现的方法有三类：
第一类是链下TEE计算(TEE, Trusted Execution Environment)。将链下的计算放在可信执行环境中进行，TEE提供基于硬件的计算安全性，Intel芯片的SGX和ARM芯片的TrustZone都可以用于链下TEE计算。
第二类是链下安全多方计算。通过安全多方计算来实现数据可用不可见，类似TEE提供硬件的加密安全，安全多方计算提供基于密码学的软件安全，比如混淆电路、秘密共享、同态加密这些算法，可以实现在各方均不知道完整数据的情况下，通过联合它们对部分数据的计算结果，得到最终结果。
第三类是采用激励机制，处理计算任务的求解者和检验结果的验证者，完成相应职责可获得奖励，反之受到惩罚。
对于链下求解者的工作将存在验证机制，如果存在欺诈行为，将没收欺诈者的押金；如果不存在欺诈，质疑者将为由此消耗的资源支付一定费用。
-
侧链（side-chain）
侧链是一个独立的链，通过主链资产的双向锚定进行数据交互。侧链依赖于主链，但是独立于主链处理事务，根据主侧链间资产锁定与解锁方式的不同，可以分为四种模式：
（1）托管模式。有单一托管和联盟托管两种，单一托管是选取主链上的单一中间方作为资产锁定与解锁的管理者，联盟托管则是选取多个托管方组成联盟，采用多重签名的方式对侧链进行资产管理。托管模式实现简单，不需要改变链的基础协议，但是增加了人为参与的中心化风险。
（2）简单支付验证模式。将主链资产锁定到一个地址中，生成SPV证明（简单支付验证,Simplified Payment Verification, 来证明一个交易确实已经在区块链中发生过），用于主侧链间信息的相互验证，也就是SPV证明作为托管方管理主侧链资产。但是，采用SPV证明进行资产锁定的同时，也是对主链进行了临时的软分叉操作，解锁时，主链的软分叉结束，又对侧链进行了软分叉，给主侧链带来了安全风险。
（3）驱动链模式。将矿工作为托管方，验证主侧链间的数据交互，受利益驱动的矿工作为公正的托管方，监管主侧链资产的锁定与解锁需求，这个模式与SPV模式一样，会带来软分叉的安全风险。
（4）混合模式。主链和侧链使用不同的解锁方法，例如在侧链上使用SPV模式，在主链网络上则使用驱动链模式。同样，混合模式也需要对主链进行软分叉。
-
侧链/链下（广义）
侧链锚定了主链的资产，而如果将其用于计算，向主链传递交易数据与结果，可以算作另一个分类，可以根据数据可用性与验证机制进行如下分类：
① plasma
比较知名的侧链方案如plasma。Plasma侧链拥有和主链不同的共识机制，也可以有不同的节点为它提供共识。它的核心原理在于，链上会存在一个名为“Operator”的角色机制，会定期将plasma链上的状态生成merkle树，并将其根哈希传递给主链进行记录和验证。
如此，主链只需验证最终的根哈希，便可确定资产转移的有效性。但由于plasma只向主链提交状态转移的结果，不提交具体的交易数据，便无法通过主链的安全性对这些交易数据进行验证，这导致plasma侧链的“数据不可用”，安全性难以保障。
② rollup
在plasma方案的基础上，rollup方案增加了交易数据的提交，同时最大限度对提交数据进行优化，在大大提高了安全性的同时尽可能保障交易速度。rollup是目前较为主流的layer2扩容方案，知名rollup方案包括zk rollup、optimistic rollup，具体将在下节详述。
③ validium
Validium运行方式类似于ZK rollup，不同之处在于数据被保存在链下，相对也就能实现更高的可扩展性。同时由于公众无法访问交易数据，也提高了隐私性。
由于交易数据不发布在链上，用户无法看到自己的资金，所以有必要采用额外的信任假设，用户必须信任中继器，以便在需要时可以访问数据。StarkWare早期使用validium，他们设计了一个数据可用性委员会（DAC），其会存储所有链下数据，并在紧急情况下变为公开可访问，减少用户对中继器的依赖：由于其仍使用zkp，所以不存在广播不正确状态的危险；用户必须信任的只是信息的及时性。
Validium解决方案建立在zkr基础之上，如果扩展解决方案的有效性证明套件越来越受欢迎，其势头会不断提高。使用Validium解决方案的项目包括DeversiFi、ZKSwap（支付、交易平台）、Sorare（足球NFT游戏）和Immutable X。
④ volition
volition混合了zk rollup链上记载数据、validium链下记载数据的特性，允许用户在每次交易时自行选择将数据存储至链上或者是链下。
3、Rollup方案
rollup与状态通道、侧链等同为layer2解决方案，其与plasma较为相似，在链下处理交易而将更新发布到layer1。不同的是，plasma只发布merkle根，而rollup仍会发布交易数据。通过将这些交易数据上链，任何人都可以检测欺诈、并且不必担心数据可用性问题。
然而，由于选择发布交易数据，rollup所能带来的扩展性是有限的。为了尽可能在保证数据可用性的前提下发送最小容量的数据，optimistic rollup和ZK rollup采用了不同的方案。
（1）rollup原理
rollup方案将会在主链上创建一个rollup合约，用以维护rollup层的当前状态。rollup合约使用“stateRoot”来跟踪rollup层交易，其由一个键值对映射组成，其中键是地址，值是账户。每个账户最多有四条属性：账户余额、随机数、代码、存储。
当rollup层发生状态更改时，这些交易将批量发送到主链上的rollup合约，该批次将包括批量事务的压缩数据和一个更新的stateRoot，该stateRoot表示该批次事务处理后的数据。rollup合约将检查前一个stateRoot与当前stateRoot是否匹配，如果匹配，将切换到新的stateRoot。
rollup层的交易数据实际上是作为”calldata”参数发布到rollup合约的，而“calldata”传递的参数根本不会存储在ETH的状态中，这可以避免很多gas费用，实现了rollup方案降低费用的目的。
通过对rollup原理的分析可以看出，rollup方案可以保证交易数据发布到主链之后的安全性，可是如何保证交易数据被发布到主链之前就不是欺诈性的呢？现行的rollup方案针对这个问题给出了不同的解决办法。
（2）optimistic rollup
optimistic rollup实际上是一种事后验证机制，在rollup层将数据提交至主链上时，其并没有验证交易是否正确执行，也就是说，这种方案“乐观”假设每一个提交交易数据的节点都是诚实的，不会发布欺诈性数据。
为了保证这种“乐观”假设，optimistic rollup要求任何将批次事务发布到主链的人都必须存入保证金，一旦它们存在恶意行为，保证金将被罚没。如果有人发现节点向rollup合约发布了无效交易数据，他们可以生成“欺诈证明”（提交欺诈证明的一方也需缴纳保证金，以避免网络因大量无效提交而过载），内容包括：
- “预状态”的证明，即在交易之前的状态；
- “后状态”的证明，即应用交易后的状态；
- 在状态转换期间应用的交易证明；
欺诈证明将被发送至主链上的rollup合约，rollup合约将验证该欺诈证明并将交易逻辑应用于“预状态”，并将结果与“后状态”进行比较，如果存在不匹配，则证明发布该批次事务的人没有正确应用交易逻辑，智能合约将会还原该批次的交易以及之后的所有批次。
（3）zk rollup
与optimistic rollup方案不同，zk rollup方案从一开始就不信任提交交易数据的节点是否诚实，而是通过零知识证明技术，在不泄露数据本身的情况下，生成数据是否存在的证明，这个被称为ZK-SNARK的加密证明将证明stateRoot是执行该批次事务的正确结果。ZK-SNARK证明将在交易数据提交至rollup合约中时一同提交。
-
ZK-SNARK技术简介
zk-SNARK是“zero knowledge Succinct Non-interactive ARgument of Knowledge”的缩写，这一长串名字的主体是“argument of knowledge”，即“知情证明”，也就是掌握某事内幕的证据。修饰主体名词的定语由三部分组成，代表了此技术要解决的三个问题，分别是：
1、zero knowledge：零知识，即在证明的过程中不透露任何内情；
2、succinct：简洁的，主要是指验证过程不涉及大量数据传输以及验证算法简单；
3、non-interactive：即提供证明者与验证者之间尽量做到无交互。
zk-SNARK通常简称为“零知识证明”，简而言之，即验证者只能验证信息而无法知道信息的具体内容。zk-SNARK证明依赖于证明者和验证者之间的初始可信设置，这意味着构建零知识证明和私人交易都需要一组公共参数。这在一定程度上是中心化的。
-
ZK-STARK技术简介
zk-SNARK代表零知识简洁非交互式知识论证，zk-STARK则代表零知识可扩展透明知识论证。
SNARK与STARK技术最大的不同在于，SNARK依赖椭圆曲线来保证安全性，而STARK依赖散列函数来保证安全，使用散列函数意味着量子抗性。从技术上讲，zk-STARK不需要初始可信设置，因为通过抗碰撞哈希函数，它们依赖于更简洁的加密技术。这种方法还排除了zk-SNARK的数论假设，这些假设在计算上很昂贵，并且理论上容易受到量子计算机的攻击。
zk-STARK提供成本更低、更快实现的主要原因之一是，其计算量增加，证明者和验证者之间的通信量保持不变。相比之下，在zk-SNARK中，所需的计算量越多，双方来回发送消息的次数就越多。因此，zk-SNARK的整体数据量要远远大于zk-STARK证明中的数据量。
以下是ZK-SNARK与ZK-STARK的具体对比：
https://blog.csdn.net/szuwaterbrother/article/details/124656730
（4）optimistic rollup与zk rollup方案的对比
① 成本。考虑主链上发布新批次事务的gas成本，zk rollup更高，因为需要多发布ZK-SNARK证明；考虑链上每笔交易的gas成本，optimistic rollup成本更高，因为必须发布足够的交易数据以验证欺诈证明，而zk rollup的ZK-SNARK证明已经足以验证数据正确性；考虑链下计算成本，zk rollup更高，ZK-SNARK计算成本高出数十甚至数百倍。（但是考虑到链下gas远低于ETH，这并不产生太大影响）
-
layer2 gas组成
以Arbitrum为例，其gas由四部分组成，包括 L1 固定成本（Fixed Cost）、L1 调用数据支付的费用（L1 Calldata Paid）、L2 计算费用（L2 Computational Paid）、 L2 存储费用。
其中，L1 Fixed Cost指批次事务提交至rollup合约发生的费用，交易数越多平摊下来越少；L1 Calldata Paid是calldata调用的费用；L2 storage fee则是二层存储费用；L2 computational paid是按用户使用的计算单位付费的。
L2 Computational Paid = L2 Compulational Used *ArbGas price
ArbGas类似于主网gas，拥堵时会自动上涨。
值得一提的是，vitalik曾提出过一种新的交易格式（blob-carrying transactions），将使得calldata调用数据的成本降至大约为零，这将会降低二者的费用。
② 速度。在optimistic rollup中，用户必须等待约一周才能提取他们的资产，因为在提取资产前，交易数据需要经过欺诈证明的验证；而zk rollup由于所有的状态均已即时得到验证，所以用户只需等待数分钟即可提款。
③ 应用速度。optimistic rollup将会更快实现并应用，工程师们已经构建了一个与EVM兼容的虚拟机，称为OVM；而zk rollup与EVM不兼容，使用ZK-SNARK证明通用EVM执行比证明简单计算困难很多，需要更长时间的开发与技术更新，比如starknet引入的cairo语言，作为ETH上的图灵完备ZK验证器以验证通用计算智能合约。
④ 可扩展性。zk rollup更具可扩展性，因为其数据有效性证明仅需ZK-SNARK，而optimistic rollup则需要在交易数据中包括状态、数字签名等，以便欺诈证明的进行，这将会占用大量存储空间。
⑤ 安全性。optimistic rollup依靠激励机制来保证数据可用性，然而激励机制并不总是会生效，当个体具有足够的作恶动机时，他们完全可以放弃自己的保证金而选择提交无效数据；相对来说，zk rollup使用密码学，从数学原理的底层避免了这一情况。
（5）rollup方案的缺陷
尽管rollup方案存在诸多优势，却也有难以解决的问题，包括：
① 可扩展性具有上限。rollup方案本质上是将交易（执行层）转移至链下，而将交易数据与结果提交至链上，以在保证数据可用性的前提下实现扩容。但交易数据的存储本身仍然受到ETH存储容量的限制。由于ETH区块gas限制为1250万，每字节存储在链上的数据成本约16gas，可以估计每个区块可存储的最大字节数约78万；假设所有交易均是最为简单的转账，且不考虑其他数据成本（比如链上验证ZK-SNARK），每块可包含的交易数上限约65000个，除以平均出块时间，在极理想状况下的tps上限约5000。这并非一个很高的上限（作为对比，visa的tps是该值的10倍以上），一旦交易需求超过该上限，rollup方案仍然面临ETH拥堵与飙gas的困境。
② 不同的rollup方案共同在ETH上运行，将会存在流动性割裂、可组合性降低的问题，需要有跨rollup通信的协议来弥补。
③ 中心化问题。目前大多数rollup方案为了更快的迭代，使用一个中心化的“定序器”节点向主链提交批次事务，在未来，定序器节点的权力需要像公链一样通过共识机制分散，例如PoS、DPoS等。
（6）目前使用rollup方案的项目/团队
Optimism：optimistic rollup方案。与arb的主要区别在于，采用单轮欺诈证明，仲裁使用EVM链上进行，这使得争议解决过程更简单，但也限制了layer2交易的gas使用上限。
Arbitrum：optimistic rollup方案。arbitrum则使用多轮欺诈证明，通过二分法找到引起分歧的区块，然后在链上执行操作即可，缺陷是完成欺诈证明的速度很慢（大约一周）并且需要提款人在线配合。
starkware：zk rollup方案。开发基于cairo语言，没有做EVM兼容；运作以starkware公司为核心。
zksync：zk rollup方案。项目完全开源，且专注于EVM兼容。
polygon hermez：zk rollup方案。hermezh通过拍卖机制选举协调者（区块打包者），以带来交易上的高效。hermez同时结合了STARK与SNARK方案，即在链下生成STARK证明，再用SNARK在链上验证STARK证明的有效性。hermez也在开发自己的zkEVM。
polygon zero：zk rollup方案，前身是Mir。开发了一种基于ZK-SNARK的递归证明系统plonky2，将允许构建具可扩展性的zkEVM。
polygon miden：zk rollup方案。使用STARK方案构建Miden VM，旨在解决rollup很难支持任意逻辑与交易的挑战，提高验证所有链下交易的能力。
aztec：zk rollup方案。以隐私为重点方向。
immutable x：volition方案。
区块链扩容-总结
公链出于去中心化与网络安全性的考虑，限制了区块间隔时间和区块大小，使得其在有限时间内只能处理有限数量的交易；而由于应用前景的拓展，对高并发的公链性能需求正日益提升。这使得扩容成为了公链架构改进的重要方向。
其中，layer0扩容专注于优化网络底层数据传输；layer1扩容，又称链上扩容，包括数据层改进方案、共识层改进方案和网络层改进方案，基本思路是增加区块大小或减少区块验证传播时间和形成共识时间；layer2扩容，又称链下扩容，主要有状态通道、侧链、链下计算，思路均为将部分链上交易转移到链下执行，减轻链上处理压力，提升整体效率。
扩容方案对比如下表：
| 扩容方案 | 方案类别 | 改进层级 | 方案说明 | 优势 | 劣势 |
|---|---|---|---|---|---|
| 网络协议改进 | layer0 | / | 底层网络传输协议的改进 | 不影响整体架构 | 技术难度高、实现周期长 |
| 增加区块容量 | layer1（链上） | 数据层 | 增加区块容量 | 不损害安全性、快速实施 | 损害去中心化、节点承载增加 |
| 隔离见证 | layer1（链上） | 数据层 | 隔离数字签名，简洁增加区块容量 | 不损害安全性、快速实施 | 扩容提升有限 |
| 频率扩容 | layer1（链上） | 数据层 | 提高区块生成频率 | 快速实施 | 增加带宽压力、安全性降低 |
| DAG | layer1（链上） | 数据层 | 变链式结构为网状结构，提高并发 | 高并发 | 双花攻击、影子链攻击 |
| 分片 | layer1（链上） | 网络层 | 网络分片，并行处理交易 | 高并发、有机会实现无限扩容 | 单个分片安全性降低 |
| 共识机制更新 | layer1（链上） | 共识层 | 改善投票方法、减少传播节点等 | 好的机制可以提升效率容错率等 | 机制设计复杂、效果不确定 |
| 状态通道 | layer2（链下） | / | 部分交易转移至状态通道 | 提升效率、降低费用、隐私性 | 依赖于交易双方即时在线 |
| 链下计算 | layer2（链下） | / | 复杂交易链下计算 | 提升交易速度、隐私性、安全性 | 技术要求高 |
| 侧链 | layer2（链下） | / | 交易转移至侧链，提交状态交易结果 | 提升效率、降低费用、共享安全 | 难以避免恶意数据 |
| rollup | layer2（链下） | / | 不仅提交结果，还提交交易数据 | 安全、数据可用性验证 | 可扩展性有限 |
共识机制的起源
拜占庭将军问题
早期的计算机应用大多为单体架构，即单个处理器就能够承接所有计算任务，只需将自己收到的任务按序执行、提交并返回即可。随着爆发式增长的数据处理需求，分布式系统架构出现，一系列处理器/节点可通过消息交互的形式协同处理一系列事务。
这引入了分布式一致性问题：当某些节点出现异常时，如何保证整个分布式系统对外的表现保持一致？“异常”包括宕机、网络问题等良性错误，也可能出现伪造消息等恶意错误（通常称为“拜占庭错误”）。
关于分布式系统中存在有恶意节点的情况，需要引入一个经典模型——拜占庭将军问题。拜占庭将军问题可以简述为：
拜占庭军队派出10支军队包围一个强大的敌人，任意一支军队单独进攻都毫无胜算，除非至少6支军队（一半以上）同时袭击才能获得胜利。这10支军队分散在敌人周围，依靠通信兵传递军令来协商进攻意向及进攻时间。困扰这10支军队的问题是，他们不确定他们之中是否有叛徒，叛徒可能恶意传播错误的消息，以影响最终的结果。这些军队如何保证获得战争的胜利？
拜占庭将军问题的核心就是解决两个问题：1、如何保证/协调将军们的军令是一致的？2、如何防止叛徒传播错误的军令？
1描述的就是分布式系统如何解决各节点间的状态同步问题；2则是要解决恶意节点干扰网络运行的问题。
举例来说，10名将军中存在有8名诚实将军，其中4名支持进攻，4名要求撤退；另外2名叛徒可以向支持进攻的将军表态支持进攻，向支持撤退的将军表态支持撤退，由此8名城市将军均误以为自己获得了多数投票（一半以上），却做出了不一致的决定。
由此，要解决拜占庭将军问题，一个必须的约束条件是——对于任意诚实节点，他们看到的其余节点的决定必须是一样的。也就是说，叛徒无法同时向不同节点传递不同的消息，每个节点所预期的投票结果都是一致的。
根据是否容忍拜占庭错误，共识算法可以分为两类：
（1）**CFT（Crash Fault Tolerance）**类，即非拜占庭容错共识算法。仅能够容忍宕机、网络延迟等良性错误。
（2）BFT（Byzantine Fault Tolerance）类，即拜占庭容错共识算法。除了容忍良性错误，还能够容忍任意类型的恶意攻击。
异步模型
在通信模型中，定义了不同消息延迟对于分布式系统的限制能力。一共有三种：同步模型（Synchronous model）、异步模型（Asynchronous model）、部分同步模型（Partial Synchronous model）。
其中，同步模型假设所有节点之间的消息通信都存在一个已知的延迟上限，并且不同节点处理事务的相对速度差值存在一个已知上限。在异步模型中，上述假设不存在，其更符合现实的互联网环境。部分同步模型则假设存在有一个全局稳定时钟，通过这样一个时序假设，系统可以恢复到同步状态。
相比于同步模型，异步模型假设节点在本地对消息的处理时间远短于消息的延迟，采用基于事件的控制流程：“当收到来自节点i的消息时开始执行某操作”。
FLP不可能原理与CAP理论
假设一个不存在良性错误的分布式系统，节点发出一个简单的提案：只在0和1中取值，是否存在一个算法使得系统在异步模型下能够达成狭义共识呢？在1985年Fischer&Lynch&Patterson发表的论文中证明了这种算法是不可能存在的（具体见这里）。
FLP给出了一个重要结论，在一个异步通信网络中，只要存在一个故障节点，就不存在一种完美的共识算法来达成共识。FLP不可能原理从理论上指出，完全的异步模型难以设计出一致性共识算法，因此后续出现的共识算法大多会在某些方面做出妥协，例如选择部分同步模型，允许存在一定时间的异步网络状态，该期间无法达成共识，但只要网络恢复到同步状态就可以立即完成共识。
CAP理论则在2000年由Eric Brewer提出，并由Seth Gilbert和Nancy Lynch于2002年证明。CAP指出，一个分布式系统至多只能同时满足如下三种特性中的两种：
- 一致性（Consistency）：所有节点在同一时间的数据完全一致。一致性通常是并发读写时才会出现的问题。
- 可用性（Availability）：用户访问数据时，系统可以在正常响应时间返回结果。可用性关系到分布式系统的数据冗余、负载均衡等。
- 分区容错性（Partition tolerance）：在系统遇到节点或者分区故障时，仍然能够对外提供满足一致性和可用性的服务。
区块链共识机制的设计，就是希望尽可能实现CAP之间的完美平衡。以BTC的PoW共识机制为例，其保证了可用性与分区容错性，但并没有完全放弃一致性。通过工作量证明，最先破解算法难题的矿工获得记账权，生产出最新区块；而根据“最长链原则”，最新区块所串起的链会被所有矿工公认，记录不同结果的节点会被更新状态，这种经过有限时间达到系统状态一致的性质，称为“最终一致性”。
共识算法的通用模型
区块链的节点一般分为生产数据的普通节点，以及复杂对普通节点生成的数据进行验证、打包、更新上链的矿工节点。两类节点会有交集：矿工节点通常会全体参与共识竞争过程，在特定节点中也会选举代表节点以代替它们参与共识过程并竞争记账权。
共识过程按照轮次重复执行，每一轮共识过程一般重新选择该轮的记账节点。共识过程可以分为“选举”（Leader election）和“记账”两部分，而“记账”又可以分为生产区块（Block generation）、验证（Data validation）、上链（Chain updation）三个阶段。
区块链共识算法可以根据其容错类型、部署方式、一致性程度等多个维度加以分类。例如，根据容错类型，可以分为BFT、CFT类；根据部署方式，可以分为公有链共识、联盟链共识、私有链共识；根据一致性程度可分为强一致性和弱一致性等。本文依据选举策略进行分类：
（1）证明类，即“proof of X”。矿工节点需要在每一轮共识过程中证明自己的某种特性，以竞争记账权。例如PoW基于矿工算力，PoS则基于权益。
（2）投票选举类。即矿工在每一轮公式过程中通过投票选举的方式选出当前轮次的记账节点。
（3）随机类。矿工节点根据某种随机方式直接确定每轮共识过程的记账节点。
（4）混合类。采用以上三类的混合体来选择记账节点。
下图与下表列出了一些早期共识算法的衍变。随着区块链技术的发展、新兴公链不断在共识算法上做出创新，简单的分类已难以对共识算法做出一个全面的概括。
区块链共识算法的发展现状与展望，2020
基础共识算法介绍
区块链基于分布式账本系统而设计，区块链的共识机制，可以理解为为了更好地实现分布式系统的一致性目标而产生的一系列流程与规则。区块链的共识机制的设计目的，就是为了更好地满足这些要求，尽可能同时满足区块链的安全性、便捷性与实用性。
目前共识算法的设计主要有两大方向。第一类是直接达成共识，以BFT为典型，每轮共识流程中都先依照规则确定一个主节点/记账节点，由该节点负责区块生产；同时，要打包进区块中的内容将由网络中节点进行投票确认，通过一系列的流程验证内容并投票通过后，内容将被打包进区块之中。第二类是间接达成共识，以proof of x类为典型，满足“x-based proof”条件的节点均可参与区块生产，在此基础上，再通过一些规则来确定最终一致的区块。
本节将介绍POS、POW、BFT这三类最典型的共识算法，现行区块链基本采用这三类共识算法的变体或混合形式。除此之外，DAG作为非链式结构，仍具备作为共识算法发展的潜力；POH等创新算法也将作出介绍。
Proof of Work
典型的PoW区块链是BTC。在BTC网络中，一笔交易是一个特殊的数据结构，包含了若干个输入和输出，输出是一个包含了UTXO（未使用的交易输出）与其使用条件的列表。输入则包含对之前一个UTXO的引用，以及能够证明交易创建者满足该输出使用条件的有效签名（用以证明UTXO中BTC的所有权）。BTC并不记录某个地址对应的BTC余额。
当一个地址要发布一笔交易时，它会向BTC整个网络中的节点广播该条交易，此交易会被标记为“unconfirmed”；当收到一条交易广播时，节点就会把该交易加入自己的内存池（mempool）。
PoW的一轮共识过程开始于节点针对“哪些unconfirmed的交易应被确认”发出提案。每个节点的mempool不同，提案确认的交易也不同，以谁为准呢？共识过程来到了“选举”环节，proof of work通过竞争算力的方式来解决这个问题。
所有节点都将计算这样一个谜题——在区块的前面加上一个随机数nonce，计算整个区块的哈希值，谜底便是使区块哈希值小于特定的目标值的那个随机数。最快解出谜底的节点获得记账权，进入记账阶段。
激励矿工们争夺记账权的原因在于每个区块中所包含的新“挖”出的BTC（这也是BTC唯一的发行方式）。在BTC的每个区块中，都包含有一个coinbase交易（币基交易），这笔交易仅包含一个名义上的输入，不指向此前任何一笔未确认的输出，输出的总金额即是当前打包一个区块所能获得的奖励。
记账完成后，节点将最新挖掘的区块广播出去，其他节点收到广播后将停止解谜、打包该最新区块并清理本地内存池，以删除与被打包区块冲突的交易。
Proof of Stake
2012年，Sunny King和Scott Nadal首次提出用PoS代替PoW的倡议，并创造了“staking”这一专有名词。peercoin于同年发布，成为第一个基于 PoS+PoW 混合共识的代币，用PoW共识分配代币，用PoS共识验证交易。
在基于PoS共识的区块链网络中，所有成为“验证者”的节点都能够获得生产区块的权利，其概率取决于拥有“权益”的多少。
早期的PoS面临着“nothing at stake”问题，当网络出现分叉时，由于生产区块未做限制，节点的最佳策略是在所有的分叉上进行生产，这导致无法达成最终一致性（在PoW中，不同分叉的投票是互斥的，矿工有激励选择最长链）。
2014年1月，vitalik在《Slasher：A Punitive Proof-of-Stake Algorithm》中提出了slasher机制，参与区块生产的节点需要抵押一定的保证金，恶意节点发起攻击不仅会损失可能的利息收入，还会损失抵押的保证金。
基于区块生产过程的不同，可以将PoS分为两类：
（1）Chain-based Proof of Stake
类似PoW生产区块的原理，算法每隔一定的时间内根据节点持有的权益随机选择一个节点负责生产区块，这个区块必须附加在一个合法区块之后，当分叉产生时，通过共识算法规定的规则选择一条链作为共识链。
（2）BFT-style Proof of Stake
算法每隔一定的时间内根据节点持有的权益随机选择节点发布一个区块，但这个区块是否合法、能被附加到共识链之后需要得到一定比例的验证者投票确认。
根据权益对共识的影响程度分类，可以分为三类：
（1）纯粹PoS，权益影响到区块生产者的选择、经济激励分配。
（2）混合PoS，权益影响到网络最终性的确认、经济激励分配。
（3）DPoS，权益可用于选举超级节点。
相比于PoW引入算力为攻击行为制造门槛、为网络提供安全性，PoS则依靠网络中通证的价值与惩罚机制预防攻击行为。PoS机制在通证初始分配合理的情况下能够保证不弱于PoW的经济学安全性（经济学安全性指，攻击者获得的收益低于其付出的代价，则不会发动攻击）。
但需要注意的是，如果一些拥有大量通证的节点形成卡特尔联盟，总抵押金超过51%，就可以对链上治理、区块生产等拥有绝对的话语权。
在PoS基础上，产生了DPoS（Delegated Proof-of-Stake，委托权益证明机制），让每一个持有通证的节点进行投票，产生超级节点代为行使区块生产等职责。DPoS可以大幅缩小参与验证及记账节点的数量，提高速度；但也不可避免造成中心化、治理变质等问题。
在DPoS的基础上，EOS使用了一种DPoS-BFT的混合共识机制，通过通证投票选举BP（Block Producer，出块者），再用BFT类算法在BP间形成共识。EOS有21名BP，通过BFT的三阶段协议，区块得到15个确认即可达成一致。
pBFT
如前所述，BFT算法除了容忍良性错误，还能够容忍任意类型的恶意攻击，解决的是通信过程可靠但节点可能故障的情况下如何达成共识的问题。
在BFT系统中，通常称发生故障的节点为拜占庭节点，正常节点为非拜占庭节点。通常假设一个n节点的BFT系统有m个拜占庭节点，它们之间满足n>3m。
【n>3m的基本逻辑：诚实节点总数为n-m，但这部分诚实节点收到的消息有可能是由m个作恶节点冒充的，因此正确的消息是n-2m个，需要满足n-2m>m】
pBFT全称实用拜占庭容错算法（Practical Byzantine Fault Tolerance），在1999年由Castro和Liskov提出。pBFT算法中，至多可以容忍不超过系统全部节点数量三分之一的拜占庭节点背叛，即只要存在超过三分之二的诚实节点，共识算法就可以顺利运行。
pBFT中节点有两种角色，主节点（primary）和副本节点（backups），主节点通常在每一轮共识过程开始时随机选取或者轮流担任，用于接收消息并向所有副本节点进行广播并负责出块，以提高通信效率。整个pBFT系统中所有节点所位于的同一配置环境称为视图（view），会随主节点的切换而切换。
pBFT通常需要运行三类基本协议，包括一致性协议、检查点协议和视图更换协议。一致性协议解决节点如何达成共识的问题，检查点协议则用于确定副本节点是否已对状态的正确性进行了证明，视图更换协议用于随主节点的更换而更换视图。
基本过程如下：
①由客户端向主节点发送请求以调用服务器操作；
②主节点向备份节点广播该请求；
③副本节点执行该请求并回复到客户端；
④客户端收到来自不同副本节点的结果；
事实上，在主节点收到客户端请求后，将会启动三阶段协议来广播该请求，分别为”pre-prepare预准备阶段“、”prepare准备阶段“、”commit确认阶段“。如下图所示：
在commit阶段，全部节点依照签名检查收到的prepare消息，若其数量超过2m，则认为系统达成一致，将对全部节点广播commit消息。
>>Tendermint
cosmos所采用的tendermint核心模块可以看作一种pBFT变体，其采用PoS+BFT结合的方式，首先由PoS确定验证者（被称为round-robin）：
tendermint没有采用经典POS中随质押按概率随机选择验证者的方式，而是采用了一个确定性的规则。如图为例，网络中三个节点A、B、C，分别质押了1、2、3个代币，首轮共识选质押最多的C做验证者；第二轮，C的投票权重变成了3-(1+2)=0，而A、B由于上轮未被选中，投票权重分别累积为2和4，则此轮选B为验证者；以此类推。
这种方式在验证者的投票权重分配上较为灵活，不同应用可以有不同的验证者权重要求；但劣势在于容易被攻击，因为恶意节点很容易预测下一个验证者节点是谁。
在选出验证者后，验证者可以提案以开始投票。之后便是类似于BFT三阶段协议的投票过程，但tendermint要求必须超过2/3投票权力确认的precommit确认才能提交区块。
FBA(Federated Byzantine Agreement)
FBA是另一种解决拜占庭将军问题的算法，它通过在子网内部形成信任（即federal），将子网作为整体视为网络节点的方式来进行网络通信。
基于FBA设计的共识机制包括RPCA（ripple）、SCP（stellar）等，通过对二者的简要介绍，我们可以尝试类比它与pBFT的不同。
>>RPCA
在RPCA中，节点分为验证节点和不参与共识过程的非验证节点。验证节点是被服务节点加入信任列表的节点。服务节点由ripple基金会选出，并且拥有自己的信任节点列表（UNL, Unique Node List），在共识过程中，服务节点只接受来自UNL的投票，并且信任它们不会联合作弊。这样服务节点以及它的UNL就组成一个“联邦”，在其内部可以按一定的规则达成共识。
RPCA共识机制分两阶段进行：形成交易集的共识以及形成新区块的共识。在一轮共识开始后，每个节点监听网络中的需要确认的交易，将其放到一个交易候选集中。服务节点对自己UNL节点的候选集做并集，并且对每一个交易在UNL中投票表决，最终得到80%投票的交易会被放入交易集中，不满足条件的交易会被丢弃或重新放入候选集。
形成交易集后，每一个节点开始将交易集打包为新的区块并计算区块Hash，广播到网络中。服务节点接收到来自UNL广播的Hash值，若计算出比例最高的Hash值占比超过80%，则说明该Hash对应的区块成为最新的共识。网络的容错能力为1/5。
>>SCP
恒星共识机制与RPCA类似，但节点可以自由地选择要加入的“联邦”，无需中心化的组织预先选出“服务节点”。在SCP机制中，把一系列信任节点的集合称为”法定体“。
SCP的共识过程同样可以分为三阶段，pre-prepare阶段、promise阶段和commit阶段。在pre-prepare阶段，节点和它的法定体交换信息；进入到promise阶段，阶段将根据它所在法定体内大多数节点的信息判断自己是否确认信息，确认后会给其他节点发送”confirm prepare“广播；在最后的commit阶段，节点会向全网广播AcceptCommit的消息，让全网每个节点间达成共识（ConfirmCommit）。
可以看到，FBA相较于pBFT，前者节点可以自由加入或退出”联邦“，而后者的节点则在每轮共识机制前预先确定，FBA相对来说去中心化程度更高，相应的，也就牺牲了一定的性能。
BFT类算法除去pBFT和FBA，还有一类被称作dBFT。dBFT类似于DPoS的思路，普通用户基于持有权益的比例投票决定记账节点，每轮共识在这些记账节点中随机推选一名发言人拟定方案，其余记账节点则依BFT算法表态，超过2/3同意则共识达成。
BFT类与PoX类算法对比
BFT和PoX都是在存在拜占庭节点的分布式对等网络中达成共识的算法。二者对比如下：
①从参与共识的节点规模来说：在n个节点组成的网络中，BFT类算法完成一轮共识所需的时间复杂度为O(n^2)，因此网络的规模有一定的限制。共识过程开始需要在节点中选出“主节点”发出提案，因此需要维护一个可信任的节点身份列表，可扩展性较低。大规模的网络通常采用联邦拜占庭协议或代理投票共识，中心化程度较高。采用PoX类共识的网络中所有节点都根据其拥有的某种资源来竞争记账权，理论上可以实现较低的中心化程度以及相对较高的扩展性。
②从选择记账节点的角度来说：BFT类共识是轮流更换“主节点”发出区块提案，所有节点直接对区块进行投票表决，称为直接达成共识，不存在严格意义的记账节点。PoX类共识通过固定的规则先选出记账节点，由记账节点决定区块的内容，再通过一定规则对可能出现的分叉链进行选择，称为间接达成共识。
③从共识的最终性来说：
BFT类共识在区块被记录到区块链历史上之后，不会发生重组或分叉。而PoX类共识即使在没有恶意节点的情况下，也有发生分叉的可能性，需要通过一定的规则对链达成共识。PoX共识通常需要一定的区块确认，牺牲交易效率以保证非中心化的共识一致性。
④从共识的激励层来说：BFT类共识没有挖矿过程，可以没有激励机制。而PoX类共识需要激励机制来约束记账节点不会作出破坏区块链的行为，并增加恶意节点发动攻击的成本。
⑤从网络的实际性能来说：BFT类共识由于直接达成共识，因此响应时间（指一笔交易从广播到得到确认的时间）快，交易承载力高。PoX类共识由于客观的区块容量、出块速度、网络通信延迟的限制，为了保证网络安全性，只能牺牲交易承载力与响应时间。而相比BFT，PoX的优势在于扩展性和非中心化程度。
DAG
无论是CFT还是BFT共识算法，节点所维护的账本都是一个由区块组成的哈希链表，是单向、线性的每个区块都只能作为唯一一个区块的父区块，并且其自身也只能有唯一的父区块。
DAG（Directed Acyclic Graph，有向无环图）作为计算机科学领域中常用的数据结构，也被应用到了区块链领域。”有向“意味着任意两点之间的联系是单向的，”无环“则意味着从任意顶点出发无法经过有向的矢量回到该点。在DAG中，区块之间的联系不再是单向、线性的，它们之间可以以一种”网“的形式发生联系，例如，A块是B块的父块，同时也可以是B块父块的父块。
DAG与有向树的区别在于每个顶点可以指向之前的多个顶点；与有向图的区别在于”无环“
我们可以引入分叉系数k来指代网络可以允许的分叉个数，当k=0时，网络不允许分叉，这就是区块链的主链。而由区块链分叉形成的叔块是不被添加到主链之上的。对DAG而言，k则一定大于0，所以可以把DAG看成区块链结构的一个拓展，链式结构则是一种特殊简化的DAG结构。
允许分叉意味着，网络中节点可以在同一时间记录不同信息，出块速度可以超过广播速度。这导致了DAG高并发、弱同步的特点。DAG固然可以利用多线程大大提高交易处理效率，然而异步通讯又会带来不一致性、冗余等问题。这种允许分叉的异步记账网络需要什么样的共识算法呢？
（1）spectre协议
SPECTRE通过区块间的投票来排除冲突的交易，如图：
source: Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar，《SPECTRE:Serialization of Proof-of-work Events: Confifirming Transactions viaRecursive Elections》
区块X里记录的交易信息是交易x先于交易y发生，记为x<y ；区块Y里记录的交易信息是交易y先于交易x发生，记为y<x，这两个交易相互冲突。在X或Y之前的区块称为X或Y的过去区块，之后则成为未来区块。在投票过程中，过去区块会分别统计自己对应的未来区块的投票，然后跟投给投票较多的选项。
spectre可以类比为”最长链共识“在DAG结构下的拓展，直观来看，越接近未来区块部分区域占比越高的交易信息更容易获得最终投票确认。这种方式可以有效防止双花攻击，如图：
source: Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar，《SPECTRE:Serialization of Proof-of-work Events: Confifirming Transactions viaRecursive Elections》
阶段I中，恶意节点生产了区块Y，并快速引用区块Y生产了13、14两个区块；从阶段I结束的时间节点来看，区块4会投票给y<x；阶段II中，攻击者秘密生产区块，希望等y<x被纳入账本后再释放这些秘密交易以达到”双花“目的；但只要网络中诚实节点更多，高并发的区块生产总会出现更多区块投票给x<y，即使攻击者上传秘密区块，网络中投票给y<x的区块仍然占大多数。
spectre可以有效排除冲突交易，抵御攻击，但却无法集成智能合约功能。这是因为DAG结构与传统区块链结构不同，每一个区块并非一定要等前一个区块被确认后才能记录入账本，spectre协议下的区块缺乏时序性，这意味着它是图灵不完备的。
（2）phantom协议
phantom在spectre的基础上做出了改进，它可以对整个账本做一个线性排序，进而满足了智能合约网络对账本时序性的要求。
双花攻击、审查攻击等恶意攻击，有一个共同特点，为了攻击成功后回滚到自己想要的交易，恶意节点生产的区块与诚实节点的区块之间连接程度很低。基于这一特征，phantom通过判断不同区块间的连通度进行投票。
source: Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar，PHANTOM and GHOSTDAG A Scalable Generalization of Nakamoto Consensus
以图示DAG举例，对于节点G而言，其过去与未来区块包括ACDJ，补集为BFIEHK，与MSC_k交集为BFI三点，不大于k值（为了平衡性能与安全，DAG中一般把分叉系数k设为3），则G可以被计入账本；同理，H则不能。
由此过滤一遍，便可以找到所有被判断为诚实的区块，这个子集被称为最大的k-cluster子集，写作MSC_k（蓝色区域）；对MSC_k进行拓扑排序，便可以得到子集内区块排列，再把恶意节点排在之后，即可得到DAG的一个线性排序。
最初的MSC_k由GHOSTDAG算法确定，基本原理是根据连通度打分，挑出总分最大的区块组成主链，这些区块组成最初的子集，剩余区块则依次投票选出。
（3）IOTA
IOTA被认为是第一个采用DAG结构的区块链项目，它主要着眼于解决物联网发展中的小额支付问题。传统区块链如BTC/ETH，每次交易无论数额多少都需要支付gas费，且矿工需要消耗大量资源完成记账；IOTA取消了区块打包的过程，因此交易也无需再支付手续费。
IOTA针对这种特殊的账本形式发明了tangle协议：tangle中每笔新产生的交易需要引用之前的两笔交易来验证确认。随着时间推移，与一笔交易相关联的交易将越来越多，攻击者发动攻击的成本将越来越大。
tangle为每笔交易设计了一个”权重“，权重大小与记录该笔交易的节点所投入的工作量相关；直接和间接引用该交易的其他交易，将其权重相加后再加该交易自身的权重，即可得到该交易的累计权重。一笔交易的累计权重越高，意味着该笔交易被越多的交易引用并验证过，其可靠性就越高。
为了防止节点直接引用一些旧交易，导致新交易迟迟无法确认，tangle规定累计权重越高的交易越有可能被过去节点选中确认。
tangle协议存在有以下问题：
①由于一笔交易仅需引用两笔交易即可得到确认，这意味着34%的算力即可篡改账本，网络安全性较低。
②项目依赖于一个中心化节点coordinator来检查全网防止”双花“。
③没有矿工激励意味着缺乏交易活跃度，难以鼓励更多节点参与。
④tangle不支持交易排序，因此目前IOTA目前不支持智能合约。
（4）Avalanche-X
Avalanche是三条链架构，其中合约链C链与负责协调验证者验证交易信息的平台链P链使用snowman共识协议，仍是链式结构；负责资产管理的X链采用的则是avalanche共识协议。
X链的共识形成主要分为四个阶段，Slush、Snowflake、Snowball以及最后Snowball+DAG结合形成的Avalanche共识协议。
（1）slush：基于gossip协议的简单重复抽样
gossip协议解决消息在分布式网络中传播的问题，BTC也是用gossip协议来广播交易和区块信息的。在slush协议中，网络中每个节点对待一条广播消息具有三种状态：相信、不信与不确定，他们需要不断向其他节点进行重复子采样。被采样的节点将返回它们信或者不信的结果，采样节点选择采样结果中的多数结果。连续几次采样结果一致时，节点才会改变自己的状态（亚稳态），如此，最终所有节点均会就该消息达成一致。
（2）snow flake：记录节点历史达成共识的次数
为了防止恶意节点故意把自己调整为相反状态，导致采样节点无法完成正确确认，snowflake在slush协议的基础上加了一层”计数器“。如果采样结果与上一轮不同，则计数器重置为0；相同则+1。当最终连续采样一致的次数大于某个限值后完成状态的确认。
（3）snowball：为snow flake加入置信度，衡量节点历史验证的质量
在加入snowflake后，仍然存在作恶节点频繁调整状态，导致采样节点一直重复采样，拖慢共识达成速度。为此，snowball为snowflake引入了置信度，采样节点单次采样与之前不同并不会直接改变状态或者把计数器归零，而是降低置信度，最终通过置信度的数值来确定是否改变状态。
（4）为snowball引入DAG结构
avalanche共识通过DAG结构提升交易效率与安全性，而基于avalanche共识改造的snowman共识则对交易进行了线性排序，以方便智能合约的引入。
avalanche存在的问题：
① 重复随机采样确定的共识仍然是概率性共识而非确定性共识；
② avalanche支持节点的自由加入与退出，如果不跟踪这些节点的状态，被随机抽样选中时可能节点已经推出了，会导致一种不安全的共识状态；
③ 重复随机抽样依赖于大量节点支持；
solana: POH
solana缩短出块及共识通讯的时间主要基于三大方面：高效利用网络带宽、减少节点间通讯次数、提高节点处理事务的速度。其基于POS与类pBFT共识（Tower Consensus）算法，引入独创的POH（proof of history）机制。
在时间间隔的设计上，POH包含epoch（纪元）和slot两大单位，每个slot约0.40.8秒，相当于一个区块的时间间隔，而每个Epoch周期包含43.2万个Slot，约24天。
Solana的节点分为两类：Leader（出块者）和Validator（验证者）。每个新的Epoch周期开始时，Solana网络会按照各节点的质押权重进行抽选，组成一个出块者Leader轮换名单，“钦定”了未来不同时刻的出块者。在整个Epoch（2~4天）内，出块者会按照名单指定的次序进行轮换，每过4个Slot（出块周期），Leader节点就会进行一次变更。没有当选Leader的全节点会成为Validator。
正是由于提前公开了未来的出块节点（这与最初的tendermint协议类似），共识过程得到了极大的简化，成为了提升solana高tps的关键，但也为系统的安全性埋下了隐患。leader易受DDOS攻击，如果连续多个leader出现故障，网络容易宕机；另外，用户提前知道leader，有可能提前进行贿赂。
对于主流POS或者PBF算法而言，leader大多遵循一套规则选定，即使事先生成leader列表，也并不会公开，这使得节点间互不信任，合法出块者必须具有相关证明。生产、传播与验证这些proof会浪费带宽资源，并产生额外的工作量。
- solana出块流程
- 用户发起交易后，会被客户端直接转发给Leader节点，或者先被普通节点接收，再立刻转发给Leader；
- 出块者Leader接收网络内全部的待处理交易，一边执行，一边给交易指令排序，制成交易序列（类似区块）。每隔一段时间，Leader会把排好的交易序列发送给Validator验证节点；
- Validator按照交易序列（区块）给定的顺序执行交易，产生相应的状态信息State（执行交易会改变节点的状态，比如改变某些账户的余额）；
- 每发送N个交易序列，Leader会定期公开本地的状态State，Validator会将其与自己的State作对比，给出“肯定”或“否定”的投票；
- 如果在规定时间内，Leader收集到占全网 2/3质押权重 的节点们给出的肯定票，则此前发布的交易序列和状态State就被敲定，“检查点”通过，相当于区块完成最终确认；
由于leader会定期向validator发送交易序列（solana实际上将公式投票作为一种交易事件来处理），这些信息会大量占用区块空间。目前节点投票的交易信息占据solana tps的70%以上。这意味着solana如果需要在未来提高自己的去中心化程度，让更多节点参与投票，投票交易占据tps的比例还会增加。
*非投票交易占比；source: https://analytics.solscan.io/ *
Solana公开leader列表有一个重要的目的——配合其gulf stream机制。该机制下，普通节点不再运行大容量的交易池，一个节点收到用户的待处理交易后，只需交给leader，这可以使得leader尽快接收交易请求，再打包成交易序列一次性分发出去。但由于普通节点无法高效拦截垃圾交易，容易导致leader节点宕机。
-
Turbine传输协议
leader在收到交易请求后，会为每笔交易都加上一个序列号（用于排序，代替了传统区块链的数据结构），之后leader会把交易序列切成X个不同碎片，分别发送给质押资产最多的X个validator，由validator之间自行同步、拼凑完整的交易序列。一般来说，X越多，数据分发与同步效率也越高，tps提升也就越显著。
由于节点质押越多，越先收到交易，也就会率先给出投票，而solana的投票与传统BFT一致，2/3以上即可确认。这意味着大节点完全可以通过抢跑而撇开其他节点。
-
全局时钟与POH
Solana设计了一个递归计算的SHA256函数，即X_n=SHA256(X_{n-1})。通过该递归计算可以得到一个X_1、X_2、X_3……的序列，并且在给定递归算法的前提下，该系列具有连续性和唯一性，且是可被验证的。交易序列可以被插进这个序列，例如T1事件，如果插入在X3和X4之间，那么原来的公式变成：X_4=SHA256(X_3+T_1)，由此，交易也可以被排序。
在这样的设计下，造假者如果想替换序列，比如将X_2替换为X_2‘，则需要把X_2之后的序列全部替换，这是极其困难的。
这种独创的序列可以用于交易的计时排序，成为solana网络中的“全局时钟”。按照原本的设计，默认200万次哈希计算对应现实世界的1秒，solana自定义了一个“tick”用于表示全局时钟的进行，160tick对应1秒，而一个slot周期包含64次tick。节点可以根据POH序列判断一个slot的起始点、下一个leader何时出现等。夹在slot起始点之间的交易序列则被划分为一个区块。
从这个角度来看，solana与op/Arb也有相似之处：通过哈希计算确定一个不可篡改的交易序列，由leader（sequencer）将序列发布给验证节点。
相对来说，solana允许节点从POH序列的任意位置验证、多个节点并行验证不同的POH片段，更为灵活高效。
Polkadot混合共识
Polkadot设计了中继链（relay-chain）负责共享安全、平行链（parachain）和转接桥（bridges）负责各种实用功能的架构，致力于实现各链之间协同工作、消息互通的互操作性。中继链拥有全局可依赖的数据结构，进行信息的验证和公式确认，支配整个生态系统的共识、治理与消息路由。而在中继链的基础之上，可以继续连接中继链，实现连续扩容。
polka使用混合共识，包括NPOS、BABE、GRANDPA。
在polkadot网络中，DOT持有者拥有提名/投票的权利，被称为nominator。Nominator通过投票选出250-1000个validator，作为中继链的全节点，将会通过随机分组被指定给不同的平行链。validator将会接收来自collector打包的区块并进行有效性验证，并用GRANDPA中做最终确认。
-
NPOS：选举验证者
polkadot将选举验证者集合的问题抽象为：m个选民对n个候选者，选出最终t个为当选者。nominator只负责投票，对于具体stake分配没有决定权，这将由NPOS（Nominated Proof of Stake）算法决定。NPOS着重于权益的公平分发，以保证验证者的质押数量存在平衡，提高网络安全性。
右边的选举结果安全性更高
-
BABE：生产区块
BABE（Blind Assignment for Blockchain Extension）是在验证节点之间运行并确定新块生产者的区块生成机制。在polka中每个slot约6秒，每个slot时间段，BABE会通过一个随机函数（VRF）选择一个leader出块。具体过程是，每个节点通过运算VRF函数获得一个数值，如果该值小于网络中预先规定的阈值，该节点则认为自己是当前slot的leader，进而开始出块。
这可能造成两种情况，一种是没有leader产生，此时polka将按照规定确定leader；一种是出现多个leader，此时polka允许多个节点出块，而把最终区块的确认交由GRANDPA确定。
-
GRANDPA：区块确认
GRANDPA用于区块确认，具体流程为：
- 一个主节点广播之前一轮确认后的区块高度；
- 每个节点都广播他们认为可以被确认的最高的区块（pre-vote）；
- 每个节点对收到的广播中区块集进行计算，算出他们认为的能被确认的最高区块，并将结果广播出去（pre-commit）；
- 节点收到超过2/3的pre-commit消息能够确认区块后则形成commit消息；
为了防止pre-vote过程中作恶节点投票两个区块导致分叉，polkadot使用了Account Safety方式来，即在出现分叉的commit信息时，每个节点都会询问其他节点收到的pre-vote信息，进而找出恶意节点，其将被永远踢出共识网络。
由于GRANDPA可以同时对多个区块进行确认，所以虽然需要二次确认以保证网络的最终一致性，但仍然可以保持较高的效率。
NEAR: TPoS+NightShade+DoomSlug
NEAR采用TPOS（Thresholded Proof-of-Stake）共识机制，使用名为NightShade的分片设计，以及DoomSlug区块生成机制。
-
TPoS
TPOS阈值权益证明是POS的变体，验证者无需比拼质押量来争夺下一个区块的记账权，而是通过一种选举机制选出验证者。有意愿的竞拍者将签署一个交易，声明自己愿意质押NEAR代币的数量，接下来每隔12小时会决定一个成为验证者的最低质押量阈值，而声明超过该阈值的质押者有机会被选为验证者，被选中的概率与其质押量成正比。
-
NightShade
分片的思路一般是把所有节点分组，每个节点不再参与全部交易的验证，而是仅验证一部分。分片可以提高tps，但相应的，安全性也会随之下降。对此，大部分分片方案的应对思路是随机分配验证者，只需让恶意节点不在同一分片链上，他们间就无法合谋。
NightShade采用一条独立的信标链（Beacon chain）来管理分片，与传统的将主链节点分片不同，NEAR将单个区块分片，其交易列表按照分片数量被分为多个chunks（每个分片都有一个出块者负责生成chunk），每个chunk对应一个分片，分片验证者只需下载和验证分片的chunk而无需下载整个块。
在NightShade协议中，有两类角色：出块者和验证者。系统在任何时候都有w个出块者和wv个验证者，由于系统采用POS，两类角色都会质押一定的token作为不遵守协议时的惩罚。
设系统包含n个分片，一个出块者会被分配到s个分片上，那么每个分片会有s*w/n个出块者。同一分片上的出块者会轮流出块，假设每个分片有2个出块者，则意味着每个出块者每隔2个块就要生产一次chunk。
在此基础上，为了满足跨分片交易，NightShade在发起跨分片交易时，首先在一个分片上执行交易，该笔交易随后被打包在分片的chunk里，当chunk被打包到块中时，会生成一个收据交易；验证者将这个收据交易发送到下一个需要更新的分片上执行。
-
挑战证明
在分片链中，恶意节点只需腐化一个分片中2/3以上的验证者就可以生成非法状态。
NightShade通过隐藏具体验证者来降低验证者被腐化的可能性，但攻击者仍能通过广播来倡议验证者进行合谋。为此，NightShade设计了挑战机制，任何参与者检测到一个chunk包含非法状态时，都可以提供一个证明对chunk的出块者进行惩罚，同时获取奖励。诚实的验证者可以监控合谋消息，即使合谋成功，也可以立即发送挑战。
NightShade要求在chunk中保存每一个交易执行后分片状态的merkle root，这样挑战者只要找到第一个非法的状态，并从前一个状态进行验证就可以证明chunk是非法的。
-
擦除码
同一个分片上的节点还可以共谋作恶，只发布chunk header而不发布完整的chunk内容，因为主链只会对chunk做确认而不会对其验证。如果这些chunk包含了非法状态，即使有诚实节点对其产生怀疑，也无法生成挑战证明，因为chunk内容没有发布。
NightShade为此引入擦除码，擦除码允许在一部分数据不可见时仍能恢复整个区块。chunk的出块者在生成chunk时必须同时生成擦除码，擦除码同时被分割为w份碎片，每个碎片都会被计算，然后相关信息将通过onepart发送给所有出块者。
此时，出块者需要收到块中所有chunks的onepart消息，才能请求重新构建chunks。如果无法获取某个chunk的onepart消息，或者无法成功构建chunks，则停止处理该块。反之，则说明chunks的完整内容的确被发布了。
最后，NightShade引入了动态重新分片，网络和分片数量将随着用户需求的增加而扩展。这允许高吞吐量，同时保持成本可控。
-
-
DoomSlug
Doomslug让一组参与者轮流生产和广播区块，一旦参与者收到高度为h的区块，就会向分配到下一个高度的h+1的参与者发送对该区块的背书；如果在一定时间后，分配给h+1的参与者没有生产区块，则由向其发送背书的参与者向分配给h+2的参与者发送另一条消息，表明其建议在h+1跳过区块。
一旦参与者得到超过一半的其他参与者的认可或者跳过消息，就可以生成他们的块。通常认为，一旦高度为h+1的区块产生，且高度为h的区块具有“doomslug终结性”（除非至少有一个区块生产者被削减，否则是不可逆的），则高度为h-1的区块具有完整的BFT最终性。
灰色为提议的块，蓝色为具BFT终结性的块，黄色为doomslug终结性的块
通常来说，tendermint/hotstuff等BFT类共识算法，需要经过两轮通信以达到最终性；doomslug并未改善完全BFT最终性的延迟（仍然需要两轮通信），但第一轮通信后，区块已经具有了doomslug最终性。这使得doomslug可以将吞吐量提高到两倍。同时，即使有50%的区块生产者不在线，依然可以完成区块生产。
共识算法-总结
本文介绍了POS、POW、BFT等主流共识算法，也介绍了DAG、POH这些另辟蹊径的创新共识算法。在最后提到的polkadot与NEAR区块链中，可以看到，它们均是对选举验证者、区块生产、区块最终确认这三个过程中开发了更适合自己的算法，尽管各自取了不同的算法名称，但核心基础与目的均是一致的。例如，polkadot选举验证者的算法均是基于POS算法的改进，polkadot用于一致性确认的GRANDPA基于BFT的三阶段协议，NEAR的DoomSlug算法则提出了自己的“DoomSlug一致性”概念。
以下是现有区块链的共识算法对比（仅列出大类）：
| PoW | PoS | BFT | DAG | POH | |
|---|---|---|---|---|---|
| 是否容忍拜占庭错误 | 是 | 是 | 是 | 是 | 是 |
| 形成共识的方式 | 间接形成 | 间接形成 | 直接形成 | 直接对交易形成共识 | 直接形成（与BFT一致） |
| 时序性 | 对区块头哈希计算 | 对区块头哈希计算 | 对区块头哈希计算 | phantom协议 | SHA-256确定交易序列 |
| 选举验证者 | 比拼算力 | 基于节点质押权益 | 随机或轮流选取主节点 | / | 提前确定leader名单 |
| 区块生产 | 解密即可出块 | 由验证者出块 | 由主节点出块 | / | 由leader定期发送 |
| 一致性确认 | 最早即最终 | 广播验证 | 三阶段协议 | 例如雪崩的重复抽样，不支持强一致 | 与BFT一致 |
| 并发性 | / | / | cBFT在做并发优化 | 并行生产区块 | 允许并行计算 |
预计在未来，仍有更多新的共识算法出现，其中大部分将是基于已有算法模型的变体与混合，其余算法中，有的可能会继续克服DAG面临的一致性等难题，有的可能会汲取POH的优势去解决扩展与去中心化的问题，甚至会有完全创新的算法横空出世。
公链作为区块链生态发展的基础，唯有在维持去中心化与安全性的前提下，不断突破现有区块链低性能的瓶颈，才能更利于行业发展。而更完善的共识算法的设计，将成为其中的核心问题。
参考资料
Whitepaper of Bitcoin
比特币区块的组成
UTXO：未使用的交易输出，比特币核心概念之一
区块链的层级结构（什么是区块链的Layer0/1/2）
区块链架构有哪些？
区块链扩展性技术总结
扩容，解决区块链的阿克琉斯之踵
分片：分而治之，无限扩展
状态通道：链下交互链上清算，两条腿走路
第0层扩容，区块链扩容明日之星
链下计算，尚在征途的扩容良方
Rollup 生态速览：Optimistic Rollup 和 zk Rollup 之外还有哪些新型设计？
详解 zk, zkVM, zkEVM 及其未来
Delphi Digital深度报告: 区块链扩容的终局
规范的以太坊汇总解读
为什么单片式L1区块链是「死胡同」？
理解Rollup：对于Arbitrum与Optimism争论的解决方案
理解零知识证明算法Zk-stark 与 Zk-snark
一文读懂 StarkWare：dYdX 和 Immutable 背后的 L2 方案
详解Polygon全栈zk扩容方案：Hermez、Nightfall、Miden和 Zero
一文了解当前 Rollup 生态，除了Optimistic 和ZK Rollup，还有这些 Rollup
读懂StarkNet、Layer3及须关注的StarkNet上的项目
主流区块链共识机制的简介与比较
坎坷的“共识机制”之路
PoS共识机制及设计哲学
从十大共识机制看加密经济的发展与未来
区块链共识算法的发展现状与展望
Consensus Algorithms： The Root Of The Blockchain Technology
Proof of Stake: How I Learned to Love Weak Subjectivity
全面拆解AVAX：从共识到子网、动态与项目分享
PBFT（实用拜占庭容错算法）原理及代码分析（go语言）
详解实用拜占庭协议Pbft（一)
从区块链到DAG（二）--DAG的基本结构
从区块链到DAG（三）--DAG共识之SPECTRE协议
从区块链到DAG（四）--DAG共识之PHANTOM协议
Avalanche链及其共识介绍
Messari深度解析：为什么NEAR会占据公链一席之地
The World Computer Should Be Logically Centralized
The Separation of Time and State
Solana扩容机制分析：牺牲可用性换取高效率的极端尝试
Proof of History: A Clock for Blockchain
8 Innovations that Make Solana the First Web-Scale Blockchain
简评三个基于VRF的共识算法
Polkadot系列｜混合共识详解
波卡运行原理系列（三）组件字典
波卡的 NPoS 机制是如何运作的？
了解夜影协议：突破限制的NEAR分片设计
Doomslug vs PBFT, Tendermint, and Hotstuff
评论区