区块链原理 / 系统课时

编写简化 BFT 多轮投票状态机

编写简化 BFT 多轮投票状态机

用一个可直接运行的 Python 模拟器观察四名等权验证者在提议缺失、两阶段投票和超时换轮时的状态变化。第一轮因提议超时无法提交,第二轮即使一名验证者离线,仍能凭三票提交区块,并打印每个节点的状态以便验证。

学习目标

  • 用事件实现 PROPOSE、PREVOTE、PRECOMMIT、COMMIT 与超时换轮。
  • 正确区分区块投票、NIL 投票和超过三分之二的法定人数。
  • 注入提议丢失与验证者离线,核对每轮是否达到提交条件。

状态与投票门槛

固定一个待决定区块的高度 H=120。验证者 A、B、C、D 各拥有 1 票,总投票权为 4;严格超过三分之二需要至少 3 票。预投票与预提交分开计数,且只统计同一高度、同一轮次、同一候选值的票。NIL 表示此阶段不支持任何区块,不是可提交的区块名称。

在线节点从 PROPOSE 进入 PREVOTE,看到同值至少 3 张预投票后才预提交该区块;再次看到至少 3 张相同区块的预提交票,才能进入 COMMIT。提议迟迟未到时,节点预投票 NIL;某轮无法提交时超时切换到下一轮。

四验证者两轮 BFT 投票与状态迁移图

实现事件驱动的状态机

使用 Python 3.10 或更新版本,无需第三方依赖。event() 负责提议、离线、预投票、预提交与超时事件;run_round() 负责按顺序投递事件。这里用共享票箱模拟消息已送达所有在线节点,避免把网络并发与投票规则混在一起。

python
from collections import Counter
from dataclasses import dataclass

QUORUM = 3  # 4 个等权验证者,严格超过 2/3 需要 3 票

@dataclass
class Validator:
    name: str
    round: int = 0
    step: str = "PROPOSE"

class DemoBFT:
    def __init__(self):
        self.nodes = {n: Validator(n) for n in "ABCD"}
        self.round = 0
        self.height = 120  # 固定高度,成功后不展开新区块高度
        self.proposal = None
        self.prevotes = {}
        self.precommits = {}
        self.prevote_timed_out = False
        self.committed = None

    @staticmethod
    def quorum(votes):
        return next((value for value, count in Counter(votes.values()).items()
                     if count >= QUORUM), None)

    def event(self, kind, sender=None, value=None):
        # 教学模型统一统计已送达的选票,不模拟节点间消息延迟
        if kind == "PROPOSAL":
            assert self.proposal is None and value not in (None, "NIL")
            self.proposal = value
        elif kind == "TIMEOUT_PROPOSE":
            assert self.proposal is None
        elif kind == "OFFLINE":
            self.nodes[sender].step = "OFFLINE"
        elif kind == "PREVOTE":
            node = self.nodes[sender]
            assert node.step == "PROPOSE" and sender not in self.prevotes
            assert value == (self.proposal or "NIL")
            self.prevotes[sender] = value
            node.step = "PREVOTE"
        elif kind == "TIMEOUT_PREVOTE":
            assert self.quorum(self.prevotes) is None
            self.prevote_timed_out = True
        elif kind == "PRECOMMIT":
            node = self.nodes[sender]
            assert node.step == "PREVOTE" and sender not in self.precommits
            choice = self.quorum(self.prevotes)
            # 没有同值法定人数时,等到预投票超时才能投 NIL
            assert choice is not None or self.prevote_timed_out
            self.precommits[sender] = choice or "NIL"
            node.step = "PRECOMMIT"
        elif kind == "TIMEOUT_ROUND":
            assert self.quorum(self.precommits) in (None, "NIL")
            self.round += 1
            self.proposal = None
            self.prevotes.clear()
            self.precommits.clear()
            self.prevote_timed_out = False
            for node in self.nodes.values():
                node.round, node.step = self.round, "PROPOSE"
        else:
            raise ValueError(kind)

    def show(self, label, votes=None):
        states = " ".join(f"{n}:{self.nodes[n].step}" for n in "ABCD")
        counts = ""
        if votes is not None:
            counts = " [" + ",".join(
                f"{v}={c}" for v, c in Counter(votes.values()).items()
            ) + "]"
        print(f"R{self.round} {label}{counts} | {states}")

    def run_round(self, proposal, online):
        if proposal is None:
            self.event("TIMEOUT_PROPOSE")
            print(f"R{self.round} 提议超时")
        else:
            self.event("PROPOSAL", value=proposal)
            print(f"R{self.round} 收到提议 {proposal}")
        for name in "ABCD":
            if name not in online:
                self.event("OFFLINE", sender=name)
        for name in online:
            self.event("PREVOTE", sender=name, value=proposal or "NIL")
        self.show("预投票", self.prevotes)
        if self.quorum(self.prevotes) is None:
            self.event("TIMEOUT_PREVOTE")
        for name in online:
            self.event("PRECOMMIT", sender=name)
        self.show("预提交", self.precommits)
        winner = self.quorum(self.precommits)
        if winner not in (None, "NIL"):
            self.committed = winner
            for name in online:
                self.nodes[name].step = "COMMIT"
            print(f"R{self.round} 提交 {winner}({len(self.precommits)}/4 票)")
            self.show("结束")
        else:
            print(f"R{self.round} 未提交(预提交结果:{winner or '无同值法定人数'})")
            self.event("TIMEOUT_ROUND")
            self.show("超时换轮")

demo = DemoBFT()
demo.run_round(None, "ABCD")  # 第一轮提议缺失,所有人投 NIL
demo.run_round("X", "ABC")     # 第二轮 D 离线,3 票提交 X
print("最终区块:", demo.committed)

预期输出:

text
R0 提议超时
R0 预投票 [NIL=4] | A:PREVOTE B:PREVOTE C:PREVOTE D:PREVOTE
R0 预提交 [NIL=4] | A:PRECOMMIT B:PRECOMMIT C:PRECOMMIT D:PRECOMMIT
R0 未提交(预提交结果:NIL)
R1 超时换轮 | A:PROPOSE B:PROPOSE C:PROPOSE D:PROPOSE
R1 收到提议 X
R1 预投票 [X=3] | A:PREVOTE B:PREVOTE C:PREVOTE D:OFFLINE
R1 预提交 [X=3] | A:PRECOMMIT B:PRECOMMIT C:PRECOMMIT D:OFFLINE
R1 提交 X(3/4 票)
R1 结束 | A:COMMIT B:COMMIT C:COMMIT D:OFFLINE
最终区块: X

核对两轮的结果

轮次 故障与可用节点 预投票 预提交 判定
R0 提议超时;A、B、C、D 在线 NIL=4 NIL=4 不提交,超时进入 R1
R1 区块 X;A、B、C 在线,D 离线 X=3 X=3 提交 X,满足 3/4 门槛

R0 虽然收到了四张一致的预提交票,但它们投给的是 NIL,因此不能把空值当作已确认区块。R1 的 A、B、C 都进入 COMMIT,而 D 仍显示 OFFLINE;模型不假定离线节点已经得知最终结果。

改变故障条件验证边界

将主程序第二次调用中的在线集合从 "ABC" 改为 "AB",重新运行。两名在线验证者只能给 X 提供 2/4 张预投票,达不到 3 票门槛;触发 TIMEOUT_PREVOTE 后两者预提交 NIL,最终会输出 R1 未提交(预提交结果:无同值法定人数)、R2 超时换轮 和 最终区块: None。这验证了模型不会把简单多数 2/4 误判为 BFT 法定人数。

这个例子适合在添加真实网络或故障注入框架前,先检查三个可断言的性质:NIL 不可提交、有效提交必须有至少 3 票、无同值法定人数时只能等待或换轮。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

编写简化 BFT 多轮投票状态机

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通