Consensus algorithms
本文最后更新于 2024-10-17，本文发布时间距今超过 90 天, 文章内容可能已经过时。最新内容请以官方内容为准
Consensus Algorithms
在区块链中，共识算法是区块链的关键组件之一。它确定区块链的账本是否准确，并确保所有节点都拥有相同的状态。
1. Proof of Work (PoW)
原理:
PoW 是区块链技术中最著名的共识机制之一，最初由比特币采用。在这个系统中，矿工（网络中的节点）通过解决一个数学难题来竞争创建新的区块。这个过程需要大量的计算资源，因此被称为“工作量证明”。一旦某个矿工成功解决了这个问题，他们就会向网络广播他们的解决方案，并且如果其他矿工验证了这个解决方案的有效性，那么这个新区块就会被添加到区块链上。这种机制通过确保攻击者需要拥有超过 50% 的网络算力才能篡改交易记录，从而提高了系统的安全性。
例子: 比特币、以太坊（在转向 Proof of Stake 之前）
优点：
- 安全性高：高度去中心化，攻击成本极高。
- 成熟稳定：经过长时间的实践验证，如比特币。
缺点：
- 能耗高：需要大量的计算资源，导致高能耗。
- 交易速度慢：区块生成时间较长，不适合高频交易
代码示例 (Python):
import hashlib
import time
def proof_of_work(last_proof):
proof = 0
while valid_proof(last_proof, proof) is False:
proof += 1
return proof
def valid_proof(last_proof, proof):
guess = f'{last_proof}{proof}'.encode()
guess_hash = hashlib.sha256(guess).hexdigest()
return guess_hash[:4] == "0000"
# 示例
last_proof = 100
start_time = time.time()
proof = proof_of_work(last_proof)
end_time = time.time()
print(f"Proof found: {proof} in {end_time - start_time} seconds")
2. Proof of Stake (PoS)
原理:
PoS 是一种旨在减少 PoW 高能耗的替代方案。在这种机制下，创建新区块的权利取决于用户持有的代币数量和年龄。通常，用户会锁定一定数量的代币作为抵押，然后根据他们的股份比例被选为下一个区块的创建者。这种方法减少了对计算能力的需求，因为没有复杂的数学问题需要解决。
例子: 以太坊 2.0、Cardano
优点：
- 能耗低：不需要大量的计算资源，更加环保。
- 交易速度快：通常比 PoW 快，适合高频交易。
缺点：
- 中心化风险：持有大量代币的节点可能控制网络。
- “无利害关系”问题：投票者可能不在乎网络的安全性。
代码示例 (Python):
import random
class Node:
def __init__(self, name, stake):
self.name = name
self.stake = stake
def select_block_creator(nodes):
total_stake = sum(node.stake for node in nodes)
target = random.randint(1, total_stake)
current_stake = 0
for node in nodes:
current_stake += node.stake
if current_stake >= target:
return node
# 示例
nodes = [
Node('Node1', 1000),
Node('Node2', 500),
Node('Node3', 750)
]
block_creator = select_block_creator(nodes)
print(f"The selected node for block creation is {block_creator.name}")
3. Delegated Proof of Stake (DPoS)
原理:
DPoS 可视为 PoS 的一种变体，它引入了一个选举过程，其中代币持有者投票选出一组代表来管理网络。这些代表负责创建区块并维护网络的安全。与 PoS 不同的是，DPoS 允许更快的交易确认时间和更高的可扩展性，因为它减少了参与共识过程的节点数量。
例子: EOS、Tron
优点：
- 更快的交易确认：通过减少参与共识过程的节点数量，可以更快地确认交易。
- 民主化：代币持有者可以投票选出代表，增加透明度
缺点：
- 中心化风险：少数代表可能控制网络
- 代表性问题：代表可能不代表所有代币持有者的利益
代码示例 (Python):
class Delegate:
def __init__(self, name, votes):
self.name = name
self.votes = votes
def select_delegates(nodes, num_delegates):
sorted_nodes = sorted(nodes, key=lambda x: x.votes, reverse=True)
return sorted_nodes[:num_delegates]
# 示例
nodes = [
Delegate('Delegate1', 10000),
Delegate('Delegate2', 5000),
Delegate('Delegate3', 7500),
Delegate('Delegate4', 2000)
]
delegates = select_delegates(nodes, 3)
print("Selected delegates:", [d.name for d in delegates])
4. Proof of Authority (PoA)
原理:
PoA 是一种基于身份的共识机制，适用于私有或联盟链。在这种模式下，网络的验证者不是匿名的，而是经过验证的真实实体。这些实体通过其良好的声誉来保证网络的安全性和可靠性。由于参与者的身份已知，因此不需要像 PoW 那样的大量计算来达成共识。
例子： POA Network
优点：
- 高效：无需大量计算，交易确认速度快。
- 信任基础：基于已知和可信的身份，增加安全性
缺点：
- 中心化：依赖于少数已知实体，容易受到攻击
- 适用范围有限：主要适用于私有链或联盟链
代码示例 (Python):
class Authority:
def __init__(self, name, is_valid):
self.name = name
self.is_valid = is_valid
def validate_authority(authorities):
valid_authorities = [auth for auth in authorities if auth.is_valid]
return valid_authorities
# 示例
authorities = [
Authority('Authority1', True),
Authority('Authority2', False),
Authority('Authority3', True)
]
valid_authorities = validate_authority(authorities)
print("Valid authorities:", [a.name for a in valid_authorities])
5. Paxos
原理:
Paxos 是一种用于分布式系统中实现一致性决策的协议。它的目标是在可能发生故障的环境中达成多数同意。Paxos 包括两个主要阶段：准备阶段和接受阶段。在准备阶段，提议者尝试获得大多数接受者的承诺；在接受阶段，提议者发送一个带有特定值的请求，如果大多数接受者同意，则该值被采纳。
例子： 广泛应用于数据库复制、云服务等分布式系统中
优点：
- 强一致性：保证数据的一致性，适用于关键任务系统。
- 广泛适用：适用于多种分布式系统。
缺点：
- 复杂性高：实现和理解较为复杂。
- 性能瓶颈：在高并发场景下可能表现不佳
代码示例 (Python):
class PaxosNode:
def __init__(self, id):
self.id = id
self.promised_id = None
self.accepted_value = None
def prepare(self, proposal_id):
if self.promised_id is None or proposal_id > self.promised_id:
self.promised_id = proposal_id
return (True, self.accepted_value)
return (False, None)
def accept(self, proposal_id, value):
if self.promised_id is None or proposal_id >= self.promised_id:
self.accepted_value = value
return True
return False
# 示例
nodes = [PaxosNode(i) for i in range(3)]
proposal_id = 1
value = "value1"
# Prepare phase
promises = [node.prepare(proposal_id) for node in nodes]
if all(promise[0] for promise in promises):
accepted_values = [promise[1] for promise in promises if promise[1] is not None]
if accepted_values:
value = max(accepted_values)
# Accept phase
accepts = [node.accept(proposal_id, value) for node in nodes]
if all(accepts):
print(f"Value {value} accepted by all nodes")
else:
print("Failed to reach consensus")
6. Raft
原理:
Raft 是 Paxos 的一个替代方案，设计上更加简单易懂。Raft 通过选举领导者来简化了一致性问题。领导者负责处理所有的客户端请求，并将日志条目复制给其他服务器。当领导者失败时，系统会通过选举产生新的领导者。
例子： Etcd、Consul
优点：
- 易于理解和实现：相比 Paxos 更简单。
- 高效：通过选举领导者简化了一致性问题
缺点：
- 单点故障：领导者故障可能导致系统停顿。
- 扩展性有限：适用于较小规模的集群。
代码示例 (Python):
class RaftNode:
def __init__(self, id):
self.id = id
self.current_term = 0
self.voted_for = None
self.log = []
self.commit_index = 0
self.last_applied = 0
self.next_index = {}
self.match_index = {}
def request_vote(self, term, candidate_id):
if term < self.current_term:
return False
if self.voted_for is None or self.voted_for == candidate_id:
self.voted_for = candidate_id
self.current_term = term
return True
return False
def append_entries(self, term, leader_id, prev_log_index, prev_log_term, entries, leader_commit):
if term < self.current_term:
return False
if prev_log_index >= len(self.log) or self.log[prev_log_index]['term'] != prev_log_term:
return False
self.log = self.log[:prev_log_index + 1] + entries
if leader_commit > self.commit_index:
self.commit_index = min(leader_commit, len(self.log) - 1)
self.current_term = term
self.voted_for = None
return True
# 示例
nodes = [RaftNode(i) for i in range(3)]
leader = nodes[0]
follower1 = nodes[1]
follower2 = nodes[2]
# Request vote
vote_granted = follower1.request_vote(1, leader.id)
if vote_granted:
print(f"Follower {follower1.id} granted vote to leader {leader.id}")
# Append entries
entries = [{'term': 1, 'command': 'set x 1'}]
success = follower1.append_entries(1, leader.id, 0, 0, entries, 1)
if success:
print(f"Follower {follower1.id} appended entries from leader {leader.id}")
7. Practical Byzantine Fault Tolerance (PBFT)
原理:
PBFT 是一种能够容忍拜占庭错误的共识算法，适用于部分节点可能行为异常的场景。它通过多轮投票来达成共识，每个节点都必须验证来自其他节点的消息，只有当大部分节点达成一致时，交易才会被确认。这种方法可以在保持高性能的同时提供强一致性保障。
例子: Hyperledger Fabric
优点：
- 高安全性：能够容忍拜占庭错误，适用于安全要求高的场景。
- 低延迟：通过多轮投票快速达成共识
缺点：
- 扩展性差：节点数量增加时性能显著下降。
- 复杂性高：实现和维护较为复杂。
代码示例 (Python):
class PBFTNode:
def __init__(self, id):
self.id = id
self.view = 0
self.primary = None
self.pre_prepare = {}
self.prepare = {}
self.commit = {}
def pre_prepare(self, view, seq, msg):
if self.primary is not None and self.primary != self.id:
return False
self.pre_prepare[(view, seq)] = msg
return True
def prepare(self, view, seq, msg):
if (view, seq) not in self.pre_prepare or self.pre_prepare[(view, seq)] != msg:
return False
self.prepare[(view, seq)] = msg
if len(self.prepare[(view, seq)]) > 2 * len(nodes) // 3:
self.commit[(view, seq)] = msg
return True
return False
def commit(self, view, seq, msg):
if (view, seq) not in self.prepare or self.prepare[(view, seq)] != msg:
return False
self.commit[(view, seq)] = msg
return True
# 示例
nodes = [PBFTNode(i) for i in range(4)]
primary = nodes[0]
backup1 = nodes[1]
backup2 = nodes[2]
backup3 = nodes[3]
# Pre-prepare
msg = "message"
pre_prepare_success = primary.pre_prepare(0, 1, msg)
if pre_prepare_success:
print(f"Primary {primary.id} pre-prepared message")
# Prepare
prepare_success1 = backup1.prepare(0, 1, msg)
prepare_success2 = backup2.prepare(0, 1, msg)
prepare_success3 = backup3.prepare(0, 1, msg)
if prepare_success1 and prepare_success2 and prepare_success3:
print(f"Backups prepared message")
# Commit
commit_success1 = backup1.commit(0, 1, msg)
commit_success2 = backup2.commit(0, 1, msg)
commit_success3 = backup3.commit(0, 1, msg)
if commit_success1 and commit_success2 and commit_success3:
print(f"Backups committed message")
8. Byzantine Fault Tolerance (BFT)
原理:
BFT 是一类算法，旨在即使在网络中存在恶意节点的情况下也能达成共识。PBFT 是 BFT 的一种具体实现。BFT 要求至少三分之二以上的节点是诚实的，以便能够正确地完成任务。
例子: Ripple、Stellar
优点：
- 高安全性：能够容忍恶意节点，适用于安全要求高的场景。
- 广泛适用：适用于多种分布式系统。
缺点：
- 性能瓶颈：在高并发场景下可能表现不佳。
- 复杂性高：实现和维护较为复杂。
代码示例 (Python):
class BFTNode:
def __init__(self, id):
self.id = id
self.quorum = 2 * len(nodes) // 3 + 1
self.votes = {}
def vote(self, msg):
if msg not in self.votes:
self.votes[msg] = 0
self.votes[msg] += 1
if self.votes[msg] >= self.quorum:
return True
return False
# 示例
nodes = [BFTNode(i) for i in range(4)]
node1 = nodes[0]
node2 = nodes[1]
node3 = nodes[2]
node4 = nodes[3]
# Vote
msg = "message"
vote_success1 = node1.vote(msg)
vote_success2 = node2.vote(msg)
vote_success3 = node3.vote(msg)
vote_success4 = node4.vote(msg)
if vote_success1 and vote_success2 and vote_success3 and vote_success4:
print(f"Quorum reached for message: {msg}")
9. Fabric-PBFT
原理:
这是 Hyperledger Fabric 中使用的一个共识插件，基于 PBFT 算法。Fabric-PBFT 提供了一种高效的方法来确保在分布式账本上的交易达成共识，特别适合于企业级应用场景。
例子: Hyperledger Fabric
优点：
- 高安全性：继承了 PBFT 的优点，适用于企业级应用。
- 灵活：可以与其他共识算法结合使用。
缺点：
- 扩展性差：节点数量增加时性能显著下降。
- 复杂性高：实现和维护较为复杂。
代码示例 (Python):
class FabricPBFTNode:
def __init__(self, id):
self.id = id
self.view = 0
self.primary = None
self.pre_prepare = {}
self.prepare = {}
self.commit = {}
def pre_prepare(self, view, seq, msg):
if self.primary is not None and self.primary != self.id:
return False
self.pre_prepare[(view, seq)] = msg
return True
def prepare(self, view, seq, msg):
if (view, seq) not in self.pre_prepare or self.pre_prepare[(view, seq)] != msg:
return False
self.prepare[(view, seq)] = msg
if len(self.prepare[(view, seq)]) > 2 * len(nodes) // 3:
self.commit[(view, seq)] = msg
return True
return False
def commit(self, view, seq, msg):
if (view, seq) not in self.prepare or self.prepare[(view, seq)] != msg:
return False
self.commit[(view, seq)] = msg
return True
# 示例
nodes = [FabricPBFTNode(i) for i in range(4)]
primary = nodes[0]
backup1 = nodes[1]
backup2 = nodes[2]
backup3 = nodes[3]
# Pre-prepare
msg = "message"
pre_prepare_success = primary.pre_prepare(0, 1, msg)
if pre_prepare_success:
print(f"Primary {primary.id} pre-prepared message")
# Prepare
prepare_success1 = backup1.prepare(0, 1, msg)
prepare_success2 = backup2.prepare(0, 1, msg)
prepare_success3 = backup3.prepare(0, 1, msg)
if prepare_success1 and prepare_success2 and prepare_success3:
print(f"Backups prepared message")
# Commit
commit_success1 = backup1.commit(0, 1, msg)
commit_success2 = backup2.commit(0, 1, msg)
commit_success3 = backup3.commit(0, 1, msg)
if commit_success1 and commit_success2 and commit_success3:
print(f"Backups committed message")
10. Tendermint-BFT
原理:
Tendermint 是一个安全的、高效的 BFT 共识引擎，它可以为任何应用程序提供一致性。Tendermint 使用了一个类似于 PBFT 的两阶段提交过程，但是优化了性能，使得它能够支持高吞吐量的应用程序。
例子: Cosmos Network
优点：
- 高性能：优化后的 BFT 算法，支持高吞吐量。
- 低延迟：快速达成共识，适用于高频交易。
缺点：
- 复杂性高：实现和维护较为复杂。
- 中心化风险：依赖于一组固定的验证者。
代码示例 (Python):
class TendermintNode:
def __init__(self, id):
self.id = id
self.round = 0
self.proposal = None
self.locked_value = None
self.quorum = 2 * len(nodes) // 3 + 1
self.votes = {}
def propose(self, value):
self.proposal = value
return value
def pre_vote(self, value):
if value not in self.votes:
self.votes[value] = 0
self.votes[value] += 1
if self.votes[value] >= self.quorum:
self.locked_value = value
return True
return False
def pre_commit(self, value):
if value != self.locked_value:
return False
if value not in self.votes:
self.votes[value] = 0
self.votes[value] += 1
if self.votes[value] >= self.quorum:
return True
return False
def commit(self, value):
if value != self.locked_value:
return False
return True
# 示例
nodes = [TendermintNode(i) for i in range(4)]
node1 = nodes[0]
node2 = nodes[1]
node3 = nodes[2]
node4 = nodes[3]
# Propose
proposal = node1.propose("message")
# Pre-vote
pre_vote_success1 = node1.pre_vote(proposal)
pre_vote_success2 = node2.pre_vote(proposal)
pre_vote_success3 = node3.pre_vote(proposal)
pre_vote_success4 = node4.pre_vote(proposal)
if pre_vote_success1 and pre_vote_success2 and pre_vote_success3 and pre_vote_success4:
print(f"Quorum reached for pre-vote")
# Pre-commit
pre_commit_success1 = node1.pre_commit(proposal)
pre_commit_success2 = node2.pre_commit(proposal)
pre_commit_success3 = node3.pre_commit(proposal)
pre_commit_success4 = node4.pre_commit(proposal)
if pre_commit_success1 and pre_commit_success2 and pre_commit_success3 and pre_commit_success4:
print(f"Quorum reached for pre-commit")
# Commit
commit_success1 = node1.commit(proposal)
commit_success2 = node2.commit(proposal)
commit_success3 = node3.commit(proposal)
commit_success4 = node4.commit(proposal)
if commit_success1 and commit_success2 and commit_success3 and commit_success4:
print(f"Quorum reached for commit")
11. HotStuff-BFT
原理:
HotStuff 是一种优化的 BFT 共识协议，设计用于提高效率和降低延迟。它通过引入“领导轮换”机制，使得网络能够在保持安全性的前提下快速前进。HotStuff 支持异步网络环境下的快速最终性。
例子： Libra（现在的 Diem）项目曾计划使用 HotStuff
优点：
- 高效：通过领导轮换机制提高性能。
- 低延迟：快速达成共识，适用于高频交易。
缺点：
- 复杂性高：实现和维护较为复杂。
- 中心化风险：依赖于一组固定的验证者。
代码示例 (Python):
class HotStuffNode:
def __init__(self, id):
self.id = id
self.view = 0
self.leader = None
self.proposal = None
self.quorum = 2 * len(nodes) // 3 + 1
self.votes = {}
def propose(self, value):
self.proposal = value
return value
def pre_vote(self, value):
if value not in self.votes:
self.votes[value] = 0
self.votes[value] += 1
if self.votes[value] >= self.quorum:
return True
return False
def commit(self, value):
if value not in self.votes:
self.votes[value] = 0
self.votes[value] += 1
if self.votes[value] >= self.quorum:
return True
return False
# 示例
nodes = [HotStuffNode(i) for i in range(4)]
leader = nodes[0]
follower1 = nodes[1]
follower2 = nodes[2]
follower3 = nodes[3]
# Propose
proposal = leader.propose("message")
# Pre-vote
pre_vote_success1 = follower1.pre_vote(proposal)
pre_vote_success2 = follower2.pre_vote(proposal)
pre_vote_success3 = follower3.pre_vote(proposal)
if pre_vote_success1 and pre_vote_success2 and pre_vote_success3:
print(f"Quorum reached for pre-vote")
# Commit
commit_success1 = follower1.commit(proposal)
commit_success2 = follower2.commit(proposal)
commit_success3 = follower3.commit(proposal)
if commit_success1 and commit_success2 and commit_success3:
print(f"Quorum reached for commit")
12. Avalanche-PBFT
原理:
Avalanche 是一种新的共识家族，不同于传统的链式结构，它采用了基于投票的随机抽样技术。Avalanche 可以在保证安全性和活跃性的同时实现极高的吞吐量和低延迟。Avalanche-PBFT 是 Avalanche 框架下的一个实现，它结合了 Avalanche 的随机抽样技术和 PBFT 的一致性协议。
例子： Avalanche 区块链平台
优点：
- 高性能：极高的吞吐量和低延迟。
- 安全性高：通过随机抽样技术增强安全性。
缺点：
- 复杂性高：实现和维护较为复杂。
- 适用范围有限：主要适用于特定的区块链应用场景。
代码示例 (Python):
import random
class AvalancheNode:
def __init__(self, id):
self.id = id
self.quorum = 2 * len(nodes) // 3 + 1
self.votes = {}
def sample_and_vote(self, value):
sample = random.sample(nodes, 3)
for node in sample:
node.receive_vote(value)
def receive_vote(self, value):
if value not in self.votes:
self.votes[value] = 0
self.votes[value] += 1
if self.votes[value] >= self.quorum:
return True
return False
# 示例
nodes = [AvalancheNode(i) for i in range(4)]
node1 = nodes[0]
node2 = nodes[1]
node3 = nodes[2]
node4 = nodes[3]
# Sample and vote
value = "message"
node1.sample_and_vote(value)
node2.sample_and_vote(value)
node3.sample_and_vote(value)
node4.sample_and_vote(value)
# Check quorum
quorum_reached1 = node1.receive_vote(value)
quorum_reached2 = node2.receive_vote(value)
quorum_reached3 = node3.receive_vote(value)
quorum_reached4 = node4.receive_vote(value)
if quorum_reached1 and quorum_reached2 and quorum_reached3 and quorum_reached4:
print(f"Quorum reached for message: {value}")
本文是原创文章，采用 CC BY-NC-ND 4.0 协议，完整转载请注明来自 Unic
阅读建议
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果
