区块链原理 / 系统课时

LMD-GHOST 如何选择链头

LMD-GHOST 如何选择链头

当 PoS 网络同时看到几条有效分叉时,不能只比较区块高度或某个叶子块的票数。这里用三名验证者、五个候选区块和一次新投票,算出 LMD-GHOST 的选链路径,并用 Python 验证链头为何切换。

学习目标

  • 区分验证者的最新有效投票与历史投票,理解子树权重如何累计。
  • 从已证明合理性的检查点出发,逐层找出最重子树的叶子。
  • 复现新投票替换旧投票后链头改变的过程,并识别与最终性的边界。

把分叉和最新投票整理成状态

LMD 是 Latest Message Driven:对每名验证者只保留其被规则接受的最新投票,而不是把同一人的多次投票不断累加。GHOST 是从根节点开始,在每一层选择观测到的最重子树,再沿该分支继续向下。

设 R 是当前已证明合理性(justified)的检查点,R 的子块为 A、B;A 下有 A1、A2;B 下有 B1。假设这些块均有效,且与已最终确认的检查点兼容。三个验证者的初始投票如下;权重采用教学单位,不对应主网实际有效余额。

验证者 权重 最新投票指向 投票目标纪元
v1 3 A1 100
v2 2 A2 100
v3 4 B1 100

子树权重等于最新投票落在该节点或其任意后代上的验证者权重之和。例如,v1 投给 A1,既支持 A1,也支持祖先 A;但在计算 A 的权重时,v1 只能计一次。这里忽略及时出块加权等生产规则,以便单独观察 LMD-GHOST。

逐层计算而不是寻找最重叶子

  1. 在 R 处比较两个直接子树:A 获得 v1 和 v2 的 3 + 2 = 5,B 获得 v3 的 4,因此先进入 A。
  2. 在 A 处比较 A1 和 A2:分别是 3 与 2,因此进入 A1。
  3. A1 没有子块,当前链头就是 A1,路径为 R → A → A1。

容易误判的地方是:B1 自身有 4 单位,而 A1 只有 3 单位。LMD-GHOST 不会直接挑全树票最多的叶子;它先在 R 比较 A 子树的 5 与 B 子树的 4,选定 A 后才在 A 内部比较。

现在 v1 在目标纪元 101 产生一张被接受的新票,改投 B1。旧的 A1 投票被替换,不再计权:A 只剩 v2 的 2,B 获得 v1 + v3 的 3 + 4 = 7。新路径成为 R → B → B1。区块树没变,变化的是各验证者最新票的归属。

新投票使 LMD-GHOST 在分叉树上改变链头

用 Python 重放两次选链

下面是可独立运行的 Python 3 示例。字典表示区块的父节点;投票记录采用“目标纪元、区块名”。supports 通过向上追溯父节点,判断一张票是否属于待计算的子树。

python
parent = {
    "R": None, "A": "R", "B": "R",
    "A1": "A", "A2": "A", "B1": "B",
}
balance = {"v1": 3, "v2": 2, "v3": 4}
latest = {
    "v1": (100, "A1"),
    "v2": (100, "A2"),
    "v3": (100, "B1"),
}

def supports(voted, subtree):
    while voted is not None:
        if voted == subtree:
            return True
        voted = parent[voted]
    return False

def weight(block):
    # 每个验证者只贡献一次当前最新票的权重
    return sum(
        balance[v] for v, (_, voted) in latest.items()
        if supports(voted, block)
    )

def get_head():
    node = "R"
    path = [node]
    while True:
        children = [b for b, p in parent.items() if p == node]
        if not children:
            return " -> ".join(path)
        # 演示时用名称打破平票;本例实际没有平票
        node = max(children, key=lambda b: (weight(b), b))
        path.append(node)

def show(stage):
    print(
        f"{stage}: A={weight('A')} B={weight('B')} "
        f"A1={weight('A1')} A2={weight('A2')} B1={weight('B1')}"
    )
    print("链头:", get_head())

show("旧票")
incoming = (101, "B1")
# 仅接受目标纪元比已记录投票更新的消息
if incoming[0] > latest["v1"][0]:
    latest["v1"] = incoming
show("新票")

预期输出:

text
旧票: A=5 B=4 A1=3 A2=2 B1=4
链头: R -> A -> A1
新票: A=2 B=7 A1=0 A2=2 B1=7
链头: R -> B -> B1

可修改 incoming 为 (99, "B1") 再运行:因为目标纪元较旧,投票不会覆盖,第二次链头仍是 A1。这说明“最新”不等于“最后收到”;以太坊规范的 latest_messages 更新依据之一是目标纪元递增,真实节点还须验证投票本身的合法性。

区分教学演算和真实网络规则

这份示例只实现选链的主干。真实以太坊共识客户端还需从 justified 检查点开始过滤不合格分支,排除不应计权的无效或重复投票者,使用验证者有效余额计权,并可能把及时提议区块的 proposer boost 加入权重。遇到完全相同的权重时,规范的选头过程以区块根的字典序作确定性决胜,而不是以演示名称比较。具体可对照以太坊共识规范的分叉选择定义。

最后要区分 链头(head) 与 最终确认(finality):本例中 A1 切到 B1 表示当前首选分支被改写,不等于已最终确认的检查点被回滚。LMD-GHOST 负责选择当前链头,Casper FFG 的检查点投票规则负责形成最终性;观察到链头改变时,应同时检查最新票、子树权重和 justified/finalized 检查点。

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

目录与阅读设置

阅读设置

17

记录一个想法

LMD-GHOST 如何选择链头

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

登录哪都通