编辑“共识机制（Consensus Mechanism）”

分布式计算和多智能体系统的一个基本问题是在存在大量故障进程的情况下实现整体系统可靠性。这通常需要协调进程以达成共识，或就计算过程中需要的数据值达成一致。共识的示例应用包括就以何种顺序提交哪些事务到数据库达成一致、状态机复制和原子广播。需要共识的现实世界应用包括云计算、时钟同步、PageRank、意见形成、智能电网、状态估计、无人机控制（以及一般来说多个机器人/智能体）、负载平衡、区块链等。

== 起源 ==
共识这个词是拉丁语，意思是“一致，和睦”，源自拉丁语 consentire，意思是“共同感受”。名词共识可以表示普遍接受的意见——“普遍同意或一致；和谐”、“多数意见”——或共识决策过程的结果。本文指的是过程和结果（例如“通过共识决定”和“达成共识”）。

由于加密货币多数采用去中心化的区块链设计，节点是各处分散且平行的，所以必须设计一套制度，来维护系统的运作顺序与公平性，统一区块链的版本，并奖励提供资源维护区块链的使用者，以及惩罚恶意的危害者。这样的制度，必须依赖某种方式来证明，是由谁取得了一个区块链的打包权（或称记账权），并且可以获取打包这一个区块的奖励；又或者是谁意图进行危害，就会获得一定的惩罚，这就是共识机制。

== 共识协议 ==
Leslie Lamport提出的Paxos共识算法及其变体如Raft，广泛应用于分布式和云计算系统。这些算法通常是同步的，依赖于选出的领导者来推动进度，并且只能容忍崩溃故障，不能容忍拜占庭故障。

Garay和Berman提出的Phase King算法是一个能够容忍拜占庭故障的多项式时间二元共识协议的例子。该算法在同步消息传递模型中解决共识问题，有n个进程和最多f个故障，前提是n > 4f。在Phase King算法中，有f+1个阶段，每个阶段有2轮。每个进程跟踪其首选输出（最初等于进程自己的输入值）。在每个阶段的第一轮，每个进程将自己的首选值广播给所有其他进程。然后，它接收来自所有进程的值，并确定哪个值是多数值及其计数。在阶段的第二轮，其ID与当前阶段号匹配的进程被指定为该阶段的国王。国王广播它在第一轮观察到的多数值，并作为决胜票。然后，每个进程更新其首选值，如下所示。如果进程在第一轮观察到的多数值的计数大于n/2 + f，则进程将其偏好更改为该多数值；否则，它使用阶段国王的值。在f+1个阶段结束时，进程输出其首选值。

Google实现了一个名为Chubby的分布式锁服务库。Chubby将锁信息保存在小的文件中，这些文件存储在复制数据库中，以实现高可用性，以应对故障。该数据库是在基于Paxos共识算法的容错日志层之上实现的。在这种方案中，Chubby客户端与Paxos主服务器通信以访问/更新复制日志；即读写文件。

许多点对点在线实时策略游戏使用修改后的锁步协议作为共识协议，以管理游戏中的玩家之间的游戏状态。每个游戏动作都会产生一个游戏状态增量，该增量广播给游戏中的所有其他玩家，以及总游戏状态的哈希值。每个玩家通过将增量应用于自己的游戏状态并比较游戏状态哈希来验证更改。如果哈希不匹配，则投出投票，游戏状态处于少数的玩家会被断开连接并从游戏中移除（称为不同步）。

另一种著名的方法称为MSR型算法，已广泛应用于从计算机科学到控制理论的各个领域。

=== 无需许可的共识协议 ===
比特币使用工作量证明（Proof-of-Work，PoW）机制，通过难度调整函数和重组函数来实现其开放式点对点网络中的无许可共识。为了扩展比特币的区块链或分布式账本，矿工试图解决一个密码学难题，其中找到解决方案的概率与每秒哈希计算量成正比。第一个解决此类难题的节点将他们提出的下一个交易块版本添加到账本中，并最终被所有其他节点接受。由于网络中的任何节点都可以尝试解决工作量证明问题，因此原则上 Sybil 攻击是不可行的，除非攻击者拥有超过网络 50% 的计算资源。

其他加密货币（如以太坊、NEO、STRATIS 等）使用权益证明（Proof-of-Stake，PoS）机制，节点根据其质押的加密货币数量来竞争添加区块和获得奖励。PoS 的一个优势是比 PoW 系统消耗的能源更少。例如，比特币挖矿（2018 年）估计消耗的不可再生能源与整个捷克共和国或约旦国家相当，而以太坊（最大的 PoS 网络）的总能耗仅略低于 205 个美国家庭的平均能耗<ref>[https://www.vox.com/2019/6/18/18642645/bitcoin-energy-price-renewable-china Bitcoin mining: a report finds the network mostly runs on renewables] | Vox</ref>。

一些加密货币，如瑞波币，使用验证节点系统来验证账本。瑞波币使用的这种系统称为瑞波协议共识算法（RPCA），分轮工作：

# 每个服务器编译一份有效的候选交易列表；
# 每个服务器合并来自其唯一节点列表（UNL）的所有候选者并对其真实性进行投票；
# 通过最低阈值的交易进入下一轮；
# 最终轮需要 80% 的同意。

无许可共识协议中使用的其他参与规则，如权威证明（Proof-of-Authority，PoA）、空间证明（Proof-of-Space）、烧毁证明（Proof-of-Burn）或时间证明（Proof-of-Elapsed-Time），旨在设置进入壁垒并抵制 Sybil 攻击。

与上述无许可参与规则（奖励参与者与其对某种行动或资源的投资金额成比例）相反，人格证明（Proof-of-Personhood）协议旨在为每个真实的人类参与者提供恰好一个单位的投票权，而不管其经济投资如何。实现人格证明的每人一票共识权分配的提议方法包括物理化名聚会、社交网络、匿名政府颁发的身份和生物识别<ref>[https://link.springer.com/chapter/10.1007/978-3-030-60975-7_24 Genuine Personal Identifiers and Mutual Sureties for Sybil-Resilient Community Growth] | SpringerLink</ref>。
{| class="wikitable"
|+类型对比
!特性
!PoW
!PoS
!DPoS
!PoA
|-
|能耗
|高
|低
|低
|低
|-
|去中心化程度
|高
|中
|较低
|低
|-
|安全性
|极高
|较高
|较高
|较低
|-
|交易速度
|极慢
|快
|很快
|极快
|-
|复杂性
|中
|高
|高
|低
|-
|代表项目
|比特币、莱特币
|以太坊 2.0、Cardano
|EOS、TRON
|VeChain、Ripple
|}

== 常见的共识机制 ==

* 工作量证明（Proof-of-Work，PoW），典型案例：[[比特币（BTC）|比特币]]
* 权益证明（Proof-of-Stake，PoS，又译持有量证明），典型案例：[[以太坊（ETH）|以太坊]]
* 股份授权证明（Delegated-Proof-of-Stake，DPoS），典型案例：[[EOS]]
* 容量证明（Proof-of-space，PoSpace，又称 Proof-of-Capacity，PoC），典型案例：[[Filecoin]]
* Paxos算法
* Raft
* PBFT
* LibraBFT（Byzantine fault-tolerance）：Libra上使用。

== 参考链接 ==
<references />