THUBA研报｜下一代区块链共识机制研究
下一代区块链共识机制研究
区块链技术的兴起标志着去中心化和可信任的数字化经济体系的崭露头角。然而，当前区块链系统面临着诸多挑战，其中最为显著的是共识机制的性能和效率。随着区块链技术的迅速演进，业界和学术界开始致力于探索下一代区块链共识机制，以应对当前系统的局限性并推动区块链技术的更广泛应用。
在当前区块链技术的发展中，“不可能三角”经常被提及，即去中心化、安全性和可扩展性之间的权衡难题。传统的共识机制在追求其中一项目标的同时，通常会在其他方面出现妥协。例如，以比特币为代表的PoW(Proof of Work)系统在安全性和去中心化方面表现出色，但却牺牲了能源效率和扩展性。而一些PoS(Proof of Stake)或其改进系统可能追求更高的吞吐量，但可能降低了去中心化的程度。新一代共识机制旨在通过创新性的设计，寻求在这三个关键方面实现更为平衡的状态。
本文将介绍下一代区块链共识机制可能的一些发展趋势，并且分析一些项目作为应用案例辅助说明。
前置知识：区块链基础知识，POW与POS机制，基础数据结构，拜占庭容错问题。
Part1 随机共识
引入随机性是分布式安全领域中的一个重要思想，是在现实中打破理论瓶颈的重要手段。为了实现可扩展性，在区块链中使用随机方法来保证安全性和去中心化的概率无限趋近于1，可以从某种程度上突破区块链的不可能三角。但由于区块链上难以实现真正的随机数，故理论上随机共识会对安全性有一定的损害。
VRF(verifiable Random Function) 可验证随机函数
VRF是一种加密函数，用于基于给定数据生成伪随机数并且附上一份证明，其他的所有人都可以对其的真实性进行验证。VRF的关键特性如下：
可验证——VRF允许任何人验证生成的随机数的有效性，而无需知道生成随机数的具体计算过程。这种可验证性是VRF的关键特性之一。
随机——对于不知道随机种子或不持有生成者私钥的人来说，VRF输出的结果完全不可预测且概率均匀分布，难以破解规律。
不可伪造—— 生成的随机数在没有私钥的情况下是不可伪造的。即使知道一系列随机数，也难以通过逆向计算找到相应的输入。
抗抽取——VRF的设计目标是防止攻击者通过多次查询来抽取更多信息。即便攻击者多次查询VRF，他们也不能预测下一个输出的值。
VRF的实现细节涉及较多密码学知识，不是本文的重点，这里进行省略。
有了安全性和效率都足够高的VRF后，选举出块节点的过程就可以使用一种高效的随机函数来代替——使用VRF随机选取每个块的出块节点，并且其他节点可以进行验证。这种方法可以加速出块节点的选举过程，同时保证安全性和去中心化特性不被破坏。事实上，Algorand，Cardano，Polkadot等L1公链使用了VRF来进行出块节点的选举。
Avalanche——随机抽样共识
Avalanche（雪崩）提出了一种基于随机抽样的共识算法，核心思想来自于抽样投票。
Avalanche提出了一个协议族，一共由4个子协议构成， 这四个协议描述了完整协议一步一步构建的过程：
1. Slush 协议：是协议族的第一个协议，它通过简单状态小样本反复抽样来达成一致。红蓝色举例，节点一开始是无颜色状态，在收到交易之后，将自己的颜色更新为交易中所携带的颜色，并且在网络中均匀随机的挑选一组小的常数样本k，发起询问。非彩色节点在接受到询问时，将会用询问颜色作为响应颜色，已经有颜色的节点，只能用当前颜色作为回应色。每次询问节点收集了k个节点的回应，发现有大于或等于a个节点都是相同的颜色，a > k/2，并且自己的颜色和他们的颜色不相同，那么就会翻转自己的颜色。重新回到询问节点，在进行询问一次。一共有m轮，最后节点在时间m结束时决定最终颜色。它是一个非拜占庭协议（Non-byzanting protocol），即无法在受到恶意节点攻击时保持稳定。
2. Snowflake 协议：在slush基础上增加了一个counter，为每一个节点增加了一个counter是用来记录该节点当前节点颜色的可信程度。它可以对最小状态做出很强的保证。每个节点计算器存储了网络连续样本和该节点显示相同颜色的次数。当counter达到b（一个安全参数）值，则节点接受当前颜色。Snowflake及以下两个协议是拜占庭协议（Byzanting protocol），可以对恶意攻击节点做出一定的防御。
3.Snowball 协议：对第二个协议做了改进，添加了更持久的可信度标识，提高了协议安全性和共识结果的可靠性，更难被攻击，更通用化，主要功能是增加可信度，每次询问成功，颜色可信度增加，而当节点颜色可信度低于询问的颜色可信度，节点颜色将会翻转。
4. Avalanche 协议 ：整个协议的终极版本，在snowball的基础上添加了动态，仅限添加（append-only）的DAG（有向无环图）结构来进行交易。
通过每次小规模的反复随机抽样，Avalanche协议能够迅速收敛到最终一致状态，从而实现可扩展性。同时，由于随机抽样的随机性和反复性，Avalanche保证安全的概率无限趋近于1。另外，Avalanche是无leader共识，故去中心化特性也天然满足。
Part2 新型区块结构
区块链从被最初提出到现在的主流项目里，一直是一条“链”状的结构，这是为了方便确认区块的正确顺序，但链状结构也带来了性能和扩展性的局限。
为了打破链状结构带来的局限，基于DAG（有向无环图）的“区块图”被提出。在这种结构中，所有区块被连接成一个有向无环图，这种结构带来了可扩展性的提升，区块之间可以被并发地提出。
上文提出的Avalanche协议正是基于这种思想，在Avalanche中，X-链（交易链）最初时使用的是基于DAG的Avalanche共识，而C-链（合约链）和P-链（平台链）使用的是基于链的Snowman共识，这样做的目的是因为Avalanche的DAG共识没有很好的兼容智能合约。2023年3月，由于一些兼容性和安全的问题，X链的共识机制迁移到了Snowman++共识，是Avalanche共识的链上优化版。从此，Avalanche各个子网的共识机制改为一致的链式共识。
Conflux——“树图”共识
Conflux共识协议提出了一种新的共识结构——“树图”，这种结构能极大提高传统区块链网络的吞吐量，并且没有损失安全性和去中心化特性。Conflux的提出者宣称Conflux可以打破区块链不可能三角，是第一个同时具备安全性，去中心化，高吞吐量，快速确认性质的区块链。
Conflux中的新型共识算法基于“树图”的数据结构。不同于传统的“区块链”，在这个数据结构中，每个区块看作一个点，而每个点会向其他已经生成的入度为0的点连一条有向边，从而所有区块之间构成一个DAG。另外，在这个DAG中，定义了一条从创世区块到目前区块的“枢纽链“。每个区块在加入时，都会找到目前的枢纽链的最后一个区块，并作为自己的父节点。而只考虑父子关系所构成的边，所有区块形成一颗以创世区块为根节点的树。在传统区块链结构中，并发产生的区块会被当作分叉，然后通过最长链原则或者GHOST原则产生一条链，其他块会被丢弃。而通过”树图“结构，并发产生的区块不会被浪费，Conflux区块链的性能得到了较大的提升。
针对安全性问题，提出了“自适应权重”的机制。每个区块都会被赋予一个权重，这个权重用来确定枢纽链，枢纽链被定义为从根开始，子节点总权重最大的那个节点。若整个系统正常运行，则每个新的块都具有相等的权重1，当出现攻击或者系统迟迟难以收敛到稳定块时，则对应的新块则会有1/h的概率是h（较大的数），否则是0。这样的话，会有一个争议块被选中成为权重非常大的块，接下来的诚实区块都会沿着这个区块继续生成。
同时，Conflux提出了延迟执行的策略，及不会马上执行新块中的交易，以保证同一笔交易不会在最终确认前被反复执行。另外，在底层实现上使用了Link-cut-tree的数据结构来维护“树图”，从而将复杂度从线性降至了log级别。进一步提高了效率。
分片
分片机制是一种用于提高区块链网络扩展性和吞吐量的方法。在传统的区块链中，每个节点都需要处理整个网络上的所有交易和区块，这导致了一些性能上的瓶颈。分片技术通过将整个区块链网络划分成小块（分片），每个分片相对独立地处理一部分交易，从而提高整个网络的性能和吞吐量。相对于改变区块的连接结构，分片技术旨在对区块链横向扩展，即形成多条并行运行的区块链。在理论上，分片机制可以实现区块链的无限扩容，所以，分片技术被一些人称为“区块链的最后一块拼图”。
针对分片技术的研究非常火热，从2016年ELASTICO第一次提出分片的理论，到2018年提出了被广泛参考和应用的OmniLedger，针对分片技术的研究迅速变得十分火热。近三年来，有超过20篇相关的研究在计算机领域的顶级会议上发表。同时，业界也有很多区块链将分片作为自己的扩容目标，其中最有影响力的当然是以太坊。
以太坊将实现分片技术作为ETH2.0升级的最后一步。目前，以太坊已完成向ETH2.0的合并，信标链已上线，预计将在不久的2024年完成分片链的上线。
在以太坊分片的初始方案中，以太坊从原本的一条主链被设计为了最多 64 条分片链，通过增加多条新链的方式来实现扩容。每条分片链负责处理以太坊的数据并交给信标链，信标链则负责整个以太坊的协调，每一条分片链的出块节点和委员会都是由信标链来随机分配。信标链和分片链之间通过交联 (crosslinks) 来进行实现链接——信标链的区块会给同区块的分片区块一个哈希值，然后这个分片区块带着这个哈希值给到下一个信标区块。
由于这种方案具有实现上的困难性，以及安全问题较多，以太坊基于“rollup”的思路提出了一种称为“DankSharding”的新型分片方案，这种新方案可以在不大量增加节点负担且保证去中心化和安全性的同时解决可扩展性问题，且对于攻击者大大增加了攻击难度。关于“DankSharding”的详细内容，可以参考V神的科普文章。
Part3 拜占庭混合共识
拜占庭共识容错算法早在区块链提出之前就已经有人进行了一定的研究，1982年，计算机科学家、图灵奖获得者Lamport提出了拜占庭将军问题。其描述了一种不同个体之间在无法信任对方的场景下，如何达成一致的问题。1999年，第一个能够在实际场景下解决此问题的算法——PBFT（Practical Byzantine Fault Tolerance）被提出，很多联盟链底层使用的正是这个共识算法。
随着区块链的火热，研究拜占庭共识容错的浪潮又被掀起，近些年来发展迅速，并被用于一些项目中。拜占庭共识容错算法相对于POS等区块链传统共识来说具有吞吐量高、交易确认速度快等优势。将两者进行混合使用以结合两者的优势这一思路已经被广泛研究与应用。不仅仅是联盟链，一些新型的公链，如Libra, Aptos, Sui均使用了学术界的较新的研究成果来优化自己的共识机制。
Algorand——BA*
在“随机共识”这一章节中，简述了Algorand的出块节点随机选举过程。接下来介绍确定共识节点和出块节点之后的共识过程，Algorand使用了一种特殊的拜占庭共识容错算法——BA*，是经典算法PBFT的改进。BA*由三步组成：
第一步：Block Proposal，所有节点检查自己是不是“潜在出块者”（potential leader），如果是，则生成自己的区块并广播。为了加速这一过程，”潜在出块者“会同时广播一个长度更小的“优先级信息”以及他的证明。
第二步：Reduction，不同的诚实节点因为网络延迟等因素，会收集到不同优先级的区块，其所观察到的最高优先级区块可能不同。因此，它们传入共识算法的区块也会不同。因此在做最后的共识之前，先在全网对哪个区块的优先级最高这一问题进行投票并达成共识，将多个潜在的区块收敛为至多1个非空区块。
第三步：BinaryBA*，对Reduction过程收敛的区块进行多次投票，最后确认一个1或者0的值表示是否同意此区块。在网络状况良好的情况下在第一步即可达成最终共识。若网络出现问题或者受到恶意节点的干扰，则不断进行共识投票，直到达成最终的稳定结束状态条件。
由于参与共识的群组较少，而且在网络中的消息传递量也大大减少了，故Algorand实现了较大的性能突破和良好的可扩展性。
在满足拜占庭节点不超过1/3总节点的前提下，Algorand的论文中详细介绍了BA*算法的正确性——不会对错误的区块达成一致共识，以及概率活性——全网达成共识的期望轮数为3轮，对应的步骤为11步。由于证明较为复杂，出于篇幅考虑在此省略。
Part4 总结
下一代区块链共识机制的研究日益受到关注，以应对当前区块链系统中共识机制性能和效率的挑战。在区块链不可能三角的限制下，传统共识机制在追求其中两个目标时通常会在剩下一个方面产生妥协，而下一代的共识，志在突破此限制以追求三个方面的平衡。
本文从随机共识、新型区块结构和拜占庭混合共识三个方面总结了前人在追求下一代共识机制中作出的努力，其各有优势和不足。区块链诞生以及有15个年头，要想走向家喻户晓地大规模应用，一个优秀的共识机制是不可或缺的。而如何突破已有的瓶颈，彻底突破区块链不可能三角的限制，可能还需要一些更加“天才”的想法。
推荐阅读文章：
A Decentralized Blockchain with High Throughput and Fast Confirmation
Algorand: Scaling Byzantine Agreements for Cryptocurrencies
EIP-4844: Proto-Danksharding
HotStuff: BFT Consensus with Linearity and Responsiveness
Omniledger: A secure, scale-out, decentralized ledger via sharding.
Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies
--END--