区块链中的共识算法概述

Abstract

共识算法是区块链技术的核心，能够让分布式网络中的节点在去中心化的环境下对共享账本的状态达成一致。它们确保了交易在复杂网络条件下的完整性和一致性，即便面对恶意行为也能维持系统的正常运行。本文概述了几种主流的共识算法，包括比特币（BTC）使用的工作量证明（PoW）、以太坊（ETH）2.0 采用的权益证明（PoS）、以及在分布式系统中具有重要地位的拜占庭容错（BFT）和崩溃容错（CFT）算法。

1 Introduction (引言)

区块链的共识算法是一种分布式节点之间达成一致的机制。在区块链网络中，众多节点（可以是计算机、服务器等设备）共同维护一个分布式账本。由于这些节点可能分布在不同的地理位置，由不同的主体控制，并且网络环境复杂多变，所以需要一种方法来确保所有节点对于账本的内容（如交易的顺序、有效性等）能够达成统一的认识，共识算法就是用于解决这个问题的技术手段。

在本文中我们将对若干种主流的共识算法进行概述，包括比特币 (BTC) 使用的最经典的工作量证明 (PoW)，以太坊 (ETH) 2.0 使用的权益证明 (PoS)，还有在分布式系统容错领域发挥关键作用的拜占庭容错（BFT）类和崩溃容错（CFT）类共识算法。

2 Proof of Work (PoW)

工作量证明是一种应对服务与资源滥用，或是拒绝服务攻击的经济对策。通过要求用户进行一些耗时适当的计算操作，并且答案可以被服务方快速验算防止舞弊，来拉高恶意攻击的成本。

在区块链中工作量证明最常用的技术原理是散列 (hash) 操作。由于散列函数的特性，几乎无法通过散列值 $$
h(s)
$$
反推回 $$
s
$$
，并且 $$
s
$$
只需要变更一个 bit，散列值就会产生非常大的变化。因此，我们能够对散列值设定特定要求。在此基础上，让用户持续在待散列数据的末尾添加数字，随后进行哈希运算以穷举所有可能，直至获取到符合要求的散列值为止。

在 BTC 中 PoW 对散列值的要求是首部有$$
difficulty
$$
个 0，BTC 通过动态控制$$
difficulty

$$
的大小来控制新的区块产生的速度大概为 10 分钟一个。这样即便随着时间的推移挖矿设备的算力提升，新的区块产生的时间间隔也是一定的。

import hashlib


def proof_of_work(data, difficulty):
    x = 0
    prefix = "0" * difficulty
    while True:
        input_str = data + str(x)
        hash_result = hashlib.sha256(input_str.encode()).hexdigest()
        if hash_result.startswith(prefix):
            print(hash_result)
            print(input_str)
            return x
        x += 1

在 BTC 中，PoW 将攻击者的攻击成本与算力挂钩。想要通过攻击整个网络来获利，首先必须在链上选择一笔已经确认的交易，试图将其修改为对自己有利的状态，例如将已经支付给某个地址的比特币重新转移到自己控制的地址。然后利用其强大的算力，开始在包含自己准备的双花或篡改交易的区块上进行挖矿，而不继续在诚实节点正在工作的最长链上挖矿。由于攻击者算力优势，其有更高概率比诚实节点更快地找到新区块，从而形成一条分叉链。分叉链会被广播给其他节点，如果分叉链比当前诚实节点的最长链要更长，被广播到的节点就会回滚原本诚实节点区块链上的所有操作，选择在这条分叉链上继续计算 PoW。

这个操作可以实现的前提是攻击者拥有整个网络 50% 以上的算力，这几乎是一件不可能的事情。即便攻击者真的拥有如此庞大的算力，相信挖矿带来的收益也是超过通过摧毁整个网络的信用所获的收益的。

3 Proof of Stake (PoS)

股权证明是一种证明节点已经将货币质押到网络中的方法，如果节点的行为不诚实，可能会遭到罚款。相应的，整个网络通过加权随机来选择当前链上开辟最新区块的矿工，持有越多股权的节点越容易被选中。

由于不同链对 PoS 的实现细节都有所不同，这里以 ETH 2.0 的实现为例。每个想要参与网络维护的节点需要质押至少 32 ETH 到网络才可以成为验证者。在 PoW 中，开辟新区块的间隔时间由难度决定，而在 PoS 中出块时间是固定的（ETH 是每 6 分钟）。需要开辟新的区块时网络根据质押的 ETH 数量加权随机选择一个节点作为矿工，由于随机种子由上个区块的哈希值决定，所以网络上的所有节点进行的随机操作都可以得到相同的结果，所以这个选择过程也是去中心化的。

当节点发现自己被选作矿工，该节点将负责创建一个新块并将其发送到网络上的其他节点。这个操作将被其他节点验证，因为其他的节点也可以算出是否是这个节点成为了矿工。如果验证未通过则会投票达成共识对不诚实节点进行惩罚（减少质押的 ETH，多次不诚实的行为可能导致节点被逐出网络），反之如果通过验证，作为奖励，矿工节点质押的 ETH 数量将会得到增加。

在网络中的所有节点都诚实并且网络状况良好的情况下，链的头部只会有一个新区块，并且所有节点都会对此进行证明。然而，由于网络延迟或当前的矿工模棱两可（即在单个时隙内向不同节点发送多个不同的区块，是一种不诚信的行为），不同节点可能对链的头部区块有不同的看法。因此节点需要一种算法来就选择哪一条链这点达成共识。以太坊 PoS 中使用的算法称为 LMD-GHOST，它选择具有最大历史证明权重（即过去区块的矿工质押的ETH数量总和最多的链）的链。

与 PoW 一样，PoS 仍然存在 51% 攻击的威胁，但对攻击者来说风险更大。攻击者需要质押超过总量 50% 的 ETH。然后他们可以确保他们的链是积累证明最多的链，使自己的链成为主链。不过在 PoS 中诚实节点可以更灵活的发起反击，例如诚实节点可以决定继续在少数链上挖矿并忽略攻击者的链。

总体而言，PoS 跟 PoW 相比不需要通过浪费大量算力来计算数学难题来达成共识，挖矿行为更加经济环保，减少能源浪费。并且质押使得挖矿门槛降低，进而使得更多人可以参与，促进去中心化。然而，PoS 使得富有的节点相比贫穷的节点有更多机会获得更多资源，使得富有者恒富有，造成马太效应。并且 PoS 协议实现起来也不如 PoW 一般简单明了。

字数不够的话可以介绍下 DPoS

4 Byzantine Fault Tolerance (BFT)

拜占庭容错（BFT）本身并不是一种共识机制，而是共识机制可能具备的一种特性。它是一个系统抵御 “拜占庭故障” 的能力，即系统组件以任意方式发生故障的情况。这个术语源自拜占庭将军问题（Byzantine Generals’ Problem），用来说明在分布式网络中达成共识所面临的挑战。在这个场景中，拜占庭军队的几个师在计划围攻的城市外扎营。将军们必须就作战计划达成一致，但只能通过信使进行交流，而信使可能会背叛他们，而将军中也可能会出现叛徒。因此问题的核心是要找到一种算法，确保在叛徒占绝对少数的情况下，将军们无论叛徒的行为如何，都能达成一致。PoW 和 PoS 都在某种程度上实现了拜占庭容错这个特性（完全实现 BFT 已经在数学上被证明为不可能）。

而所谓 BFT 共识机制的工作原理是要求网络中一定比例的节点在交易被添加到区块链之前达成共识。这确保了即使某些节点存在恶意行为或故障，也无法影响网络的整体共识。BFT 共识机制在区块链网络中尤为重要，因为它提供了高度的安全性和可靠性。

PBFT (Practical Byzantine Fault Tolerance) 算法是目前最常用的一种 BFT 共识机制实现。要解决拜占庭将军问题，符合直觉的想法就是利用一轮或多轮的投票以获得多数共识。然而，由谁来发起投票？投几次票？PBFT 的创新在于三阶段投票的设计，分为 Pre-prepare, Prepare, Commit 三个 phase。

在 PBFT 中有一个主导者（Primary）和多个验证者（Validator）。节点们遵循轮替制来轮流担任主导者，以防止某个有问题的节点一直担任主导者。主导者分成不同代，主导者的代数可以称为视域（View）。

在 Pre-prepare phase 中，主导者负责接收客户端的进攻/撤退命令；由主导者负责发起提议：内容包含进攻或撤退的决策（Message），第几代（View），第几次进攻（Sequence Number）；主导者发送附有自己签名的“就位”讯息给其他验证者。验证者收到“就位”讯息后决定是否接受提议，如果赞成提议则向网络中的所有节点广播自己签名的“预备”讯息，发出“预备”讯息的节点进入 Prepare phase。

各节点如果收到占整个网络 3 / 4 以上的“预备”讯息，则该节点进入 Prepared 状态，节点收到的“预备”讯息的集合统称为“已预备证明”（Prepared Certificate）。Prepared 的节点若决定执行，则发送附有签名的“执行”讯息给所有节点；若决定不执行则不发送任何讯息。发出“执行”讯息的节点进入 Commit 阶段。各节点若收到占整个网络 3 / 4 以上的“执行”讯息，则执行讯息内容，这也代表该提议取得了共识。执行讯息后的节点进入 Commited 状态并将执行结果回报给客户端。回报后的节点结束本回合，等待下一个提议的到来。

以上共识的形成非常依赖忠诚的主导者，万一主导者是叛徒呢？为了避免不提案的主导者瘫痪所有行动，节点们需要一个轮替机制，也就是视域变换（view-change）: 每个节点从收到“预备”讯息后开始计时，转为 “已执行” 状态结束计时。如果在计时后一定时间内未执行讯息，则该节点可以发送“变换”讯息，讯息内容包含新的代数(+1)以及其他重要讯息。如果主导者未提案，则每个诚实的验证者最终都会因为超时而发出变换讯息。

若轮替到的新主导者收到 3 / 4 以上的“变换”讯息，则新主导者可以发送“新域”(new-view)讯息，讯息内容包含新代数，所有具有“已预备证明”且尚未被执行的“就位”讯息，以及其他重要信息。接下来由新主导者负责接收客户端的命令。

PBFT 是一个许可制的，基于领袖的，基于通讯的，安全性重于活跃性的共识协议。

许可制: PBFT 需要让节点能够知晓彼此的讯息和精确掌握节点的数量，而比特币这种基于中本共识（Nakamoto Consensus）的区块链则属于对任何人都开放的非许可制。
基于领袖: PBFT 中尽管所有节点轮流坐庄，但仍然需要有一个领袖节点。
基于通讯: PBFT 的安全性奠基于3阶段投票，虽然不必如 PoW 般消耗大量资源，但是数量庞大的通讯也造成可拓展性的瓶颈——网络大小始终被网络带宽条件限制。
安全性重于活跃性：PBFT 几乎不可能出现分叉，相对的，区块链则是活跃性重于安全性，具有复数个分叉的情况也比较常见，需要进行一定数量区块的确认才能保证其不再分叉的概率足够大。

综合 PBFT 上述的特性：许可制，过高的通讯成本，我们无法在 PBFT 上建立一个完全去中心化的并且实用的加密货币。不过在一些 PoS 区块链系统的共识阶段，会借鉴 PBFT 的部分思想。当节点被选中根据其权益来进行记账（创建新区块）时，为了确保该区块内容在网络中的一致性，会采用类似 PBFT 的消息传递机制。

5 Paxos (CFT)

Paxos 和 Raft 之后学 MIT 6.824 会详细过一遍

CFT（Crash Fault Tolerance）类共识算法是一类分布式系统中的共识算法，主要用于处理系统中节点可能出现崩溃故障（Crash Fault）的情况。它确保在部分节点崩溃的条件下，系统仍然能够正确地达成共识，继续运行并保持数据的一致性。与 BFT 不同的地方在于，该算法假设网络中的全部节点都为诚实节点，不需要考虑恶意节点带来的影响。

Paxos 是一种经典的 CFT 类共识算法，由 Leslie Lamport 在 1990 年代提出，用于在分布式系统中实现一致性。它通过投票的方式，在提议者（Proposers）、接受者（Acceptors）和学习者（Learners）之间协调决策，确保在存在节点故障的情况下，多个节点对某一决策（如值或状态）达成一致。

算法的运行分为三个阶段。在准备阶段，提议者首先生成一个唯一的提案编号（Proposal Number），并向所有接受者发送“Prepare”请求。接受者收到请求后，如果编号大于它之前承诺过的编号，则承诺不再接受编号小于当前提案编号的任何提案，并返回其已接受过的提案（如果有）。在提议阶段，提议者在收到大多数接受者的响应后，从中选取编号最大的提案值作为新的提案值，并向所有接受者发送“Accept”请求。接受者如果认为提案编号合法，则接受该提案并广播确认消息。在提交阶段，当提议者收到大多数接受者的确认后，提案被认为达成共识，并通知学习者。学习者更新自己的状态，完成提案的提交。

Paxos 算法能够容忍少数节点的崩溃，只要大多数节点仍在线，系统即可继续运行。同时，Paxos 保证在任何情况下最多只有一个提案被接受，从而确保了决策的一致性。在网络稳定的情况下，提案最终会被提交，满足活跃性。然而，Paxos 算法实现起来较为复杂，特别是在涉及节点故障和网络分区时。其多轮次的消息通信机制会导致性能瓶颈，在节点数量较多时，通信开销和延迟显著增加。此外，由于算法依赖大多数节点的响应，扩展到非常大的网络规模时，难以有效适应高并发场景。

为了应对 Paxos 的复杂性和性能问题，提出了多种改进方案。例如，Multi-Paxos 通过固定一个提议者来减少通信开销，适合高频决策的场景。Fast Paxos 则在降低通信轮次方面进行了优化，但需要更严格的网络条件支持。Raft 是另一种被广泛采用的替代算法，它简化了 Paxos 的设计，使其更易于理解和实现，同时保持了 Paxos 的一致性和容错特性。这些改进使 Paxos 的思想在分布式系统中得到了广泛应用。

6 Conclusion (总结)

区块链共识算法作为分布式系统的重要组成部分，决定了网络的安全性、去中心化程度以及性能表现。未来，随着区块链技术的不断发展，新的共识算法将继续涌现，进一步平衡安全性、效率和去中心化之间的矛盾。例如，混合共识（Hybrid Consensus）结合多种共识算法的优点，试图适应更广泛的应用场景。此外，零知识证明、跨链互操作性等技术的引入，也为共识机制的创新提供了更多可能性。

总的来说，共识算法的演进不仅推动了区块链技术的发展，还对分布式系统领域产生了深远影响。在未来的研究和应用中，探索更加高效、安全且公平的共识机制仍将是一个重要的方向。

参考论文

Practical Byzantine Fault Tolerance
- 介绍了实用拜占庭容错算法 PBFT，该算法在存在恶意节点的情况下，能使各节点达成一致，容忍度最大为总节点的 2/3，是分布式计算领域经典的容错技术，为区块链共识算法的研究和发展奠定了基础.
Bitcoin: A Peer-to-Peer Electronic Cash System
- 中本聪提出的比特币白皮书，其中介绍的工作量证明 PoW 共识算法是区块链领域首个被广泛应用的共识机制，通过计算难度来协调节点竞争，解决了分布式系统中的双花问题，推动了区块链技术的发展.
  - 中文翻译
Proof of Stake: How I Learned to Love Weak Subjectivity
- 阐述了权益证明 PoS 共识算法，以节点的权益代替计算资源来决定记账权，相比 PoW 更节能环保，有效减少了资源浪费，对推动区块链共识机制的创新和发展具有重要意义.
Paxos Made Simple
- 《Paxos Made Simple》中文翻译:Paxos 如此简单
  - 在这篇论文中，Lamport 提出了 Paxos 算法，该算法是 CFT 类共识算法中的经典之作，其核心是通过多轮的消息传递和投票来达成节点之间的共识，以解决分布式系统中的一致性问题。
Proof-of-stake (PoS) | ethereum.org
zh.wikipedia.org
Byzantine fault