Post

以太坊 PoS 共识协议详解(一):核心概念与 LMD GHOST

本文是介绍以太坊 PoS 共识协议的第一部分。主要包括对术语和核心概念的讲解,以及对 LMD GHOST 分叉选择规则的详细介绍。

术语及重要概念

节点和验证者

以太坊网络的主要参与者是节点 (Node)。节点的作用是验证共识并与其他节点形成通信骨干网。共识由验证者 (Validator) 形成。

“验证者”这一术语具有一定的误导性,验证者其实并不会验证任何东西,验证是由节点完成的。

每个验证者代表一笔初始的 32 ETH 的质押。验证者有自己的私钥,以及与其对应的公钥,代表其在协议中的身份。验证器附属于节点,单个节点可以托管零到数百甚至数千个验证者,附属于同一节点的验证者共享相同的全局视图。 1

权益见证与工作量见证的一个重要区别在于,在权益见证下验证者集是已知的,系统拥有在任意时刻期望处于活跃状态的公钥的完整列表。由此我们可以确定何时获得了参与者的多数票,并达成最终性。

Slot 和 Epoch

以太坊的权益见证共识中,时间是被精确控制的,这与工作量见证截然不同,后者只是尝试在平均水平上保持出块间隔不变,仅此而已。

图1 前 32 个 Slot 属于第 0 个 Epoch,创世块位于第 0 个 Slot

Slot(常译作“时隙”、“区块槽”)和 Epoch(常译作“时段”)是划分时间的两个主要概念,每个 Slot 为12秒,每个 Epoch 为 32 个 Slot,即 6.4 分钟。无论网络上情况如何,Slot 和 Epoch 都会保持节奏持续向前推进。

区块和见证

每个 Slot会选出一名验证者提议一个区块 (Block)。区块包含对信标状态的更新,其中包括提议者知道的见证 (Attestation) 以及带有以太坊用户交易的执行负载。提议者通过 Gossip 协议与整个网络共享其区块。

Slot 可以为空:因为区块提议者可能处于离线状态,或者提议了一个无效的区块,或者其区块随后被链重组 (Reorg) 剔除出链。

每个 Epoch 中,每个验证者都能以见证的形式分享一次自己的视图。见证包含用于 LMD GHOST 协议的链头投票以及用于 Casper FFG 协议的检查点投票。见证也会广播到整个网络。见证和区块一样,也可能由于各种原因丢失,并且协议可以在一定程度上容忍这种情况。粗略地说,随着见证者参与率的下降,共识的质量将会下降。 2

Epoch 的功能是分散处理所有这些见证的负载。通过见证,每个验证者都会将自己的全局视图告知其他每个验证者,如果所有操作都同时进行,可能带来巨量的网络流量和处理负载。将见证负载分散到一个 Epoch 的 32 个 Slot 中可以保持较低的资源使用率。在每个 Slot 中,仅由$ \frac{1}{32} $的验证者组成的委员会进行见证。

协议通过奖励和罚没系统激励验证者进行区块和见证的生产并确保其准确性,这一部分本文暂不深入探讨。

安全性和活性

在讨论共识机制时,经常会用到两个重要概念:安全性 (Safety) 和活性 (Liveness)。

用一句话概括安全性要求就是“永不发生坏事”。在区块链语境下,“坏事”可能是币的双花,或冲突检查点的最终化等。

分布式系统中安全性的一个重要方面是“一致性 (Consistency)”。也就是说,如果我们向不同的节点查询链的状态(如特定区块高度的账户余额),则无论我们询问哪个节点,都应该始终得到相同的答案。在一个安全的系统中,每个节点对链的历史都具有完全相同的视图,并且该视图永远不会改变。安全性意味着我们的分布式系统“像一个中心化实现一样原子地执行每一步操作”。根据 Vitalik 的中心化分类法,安全的系统在逻辑上是中心化的。

而同样用一句话概括活性就是“终会发生好事”。在区块链语境中,通常可以理解为链可以始终添加新块,永远不会陷入死锁状态。

也可以从“可用性 (Availability)”的角度出发理解活性:链是可用的,意味着如果我向诚实节点发送有效交易,最终交易一定会被包含在一个扩展链的区块中。

值得注意的是,CAP 定理证明了没有分布式系统可以同时满足:一致性,可用性和分区容错性。现实中,我们只能基于不可靠的 Internet 构建区块链,即分区容错性是必须成立的,这也就说明链的安全性和活性是难以两全的。以太坊共识协议在网络状况良好时能同时提供安全性和活性,但在运行不顺利的情况下优先考虑活性。在网络分区的情况下,分区两侧的节点都将继续产生区块,但最终性(安全属性)不再有保障。具体取决于各分区中的质押权益比例,可能只有一侧继续最终化,也可能双方都无法最终化。最终,除非分区问题得到解决,否则消极惩罚机制 (Inactivity Leak) 会使双方都将重新获得最终性,但同时也将导致共识的撕裂,两条链将最终化不同的历史记录,并且这两条链将永远保持独立,无法调和。

罚没

在工作量证明中,产生区块代价很高。这会激励矿工按照协议的目标正当行事,以确保其区块被包含。

而在权益见证中,创建区块和见证的成本近乎为零3,我们需要一种方法来防止攻击者利用这一点扰乱网络。这就是罚没 (Slashing) 的作用。对区块或见证有分歧行为的验证者会受到罚没,即被驱逐出验证者集并被没收部分质押金。这里的分歧行为的意思简单来说就是自相矛盾,例如为同一个 Slot 提议两个不同的区块,或做出两个相互冲突的见证等遵循协议的诚实验证者不会做出的行为。

Ghost in the Shell

了解术语和核心概念后,本节将概述以太坊的实际共识机制。

以太坊的权益证明共识协议实际上是两个独立的共识协议的组合,分别称为 LMD GHOSTCasper FFG,二者组合的协议有时被称为“Gasper”。

Gasper 中将两者结合,试图在活性和安全性方面获得两全其美的效果。从本质上讲,LMD GHOST 提供了逐区块的活性(保持链的运行),而 Casper FFG 提供了安全性(保护链免于长回滚)。LMD GHOST 允许我们不断地生成区块,但它存在分叉,因此在形式上并不安全。Casper FFG 修改了 LMD GHOST 的分叉选择规则,以期定期为链提供最终性。然而,如前所述,以太坊优先考虑活性。因此,在 Casper FFG 无法提供最终性的情况下,链仍然会通过 LMD GHOST 机制继续增长。

这种“拼凑”在一起的共识机制并不完美,但秉承以太坊的精神来看,这是一种可行的工程解决方案,在实践中能很好地达成目的。

历史

Gasper 的详细历史与其组件(LMD GHOST 和 Casper FFG)的发展紧密相关,我们将在后续文章中进行回顾。

在此要指出的是,Casper FFG 从来就不是设计成独立的共识机制。正如 Casper FFG 论文中所述:

“Casper the Friendly Finality Gadget” 是提案机制(提出区块的机制)之上的一个覆盖层。

因此,Casper FFG 之下还存在着一个底层的区块提议机制(说明存在底层共识机制)提供了某种“元共识”,赋予区块链最终性。

最初的计划是将 Casper FFG 作为权益证明覆盖层应用于以太坊的工作量证明共识之上。Casper FFG 将周期性地为链提供最终性(PoW 链缺少的属性)。旨在成为以太坊逐步淘汰工作量证明铺路,有了最终性保证,就可以减少工作量证明区块奖励,从而降低总哈希算力,为用权益证明取代挖矿做准备。到 2017 年底,EIP-1011(混合 Casper FFG)详细描述了架构,甚至还有一个测试网在 2017 年 12 月 31 日上线。然而以太坊虚拟机的有限带宽限制了 EIP-1011 可以支持的验证者集大小,进而导致最低质押额高达 1500 ETH,被认为是不可取的,因此该计划在 2018 年初被取代了。大约在同一时间,开发者们开始着手设计以太坊 2.0 协议。Casper FFG 的通用性使其在重新设计中得以被保留,作为新权益证明协议 LMD GHOST 的覆盖层,被采纳为以太坊 2.0 的一部分。

最终性小工具

前文提到 Casper FFG “覆盖”现有区块提议机制时,其含义是 Casper FFG 使用现有的区块树并以特定方式进行剪枝,通过使某些分支不可访问来修改底层区块树的分叉选择。

考虑下面这个由某种底层共识机制(无论是工作量证明还是权益证明中的 LMD GHOST)产生的区块树:

由三个分叉组成的任意区块树 区块 I、E 或 M 都可以是链头(块标签仅为方便起见,并不表示特定顺序)

在这种情况下,有三个候选头块,I、E 和 M。在工作量证明最长链规则下,必须选择块 M 作为链头,因为它具有最大的区块高度,或者说该分支积累了最大的工作量。在 LMD GHOST 下,仅凭此信息无法选择头块,我们需要查看其他验证者的投票才能做出选择。

问题在于从区块 J 到 M 的链可能来自攻击者。攻击者可能秘密挖矿了该链随后在 51% 攻击中揭示。PoW 节点别无选择,只能重组链以使 M 成为头块,这有利于攻击者的链并可能受到双花攻击。

Casper FFG 带来的价值在于赋予最终性。假设 Casper FFG 将区块 D 标记为最终化(这也会自动将区块 A、B 和 C 标记为最终化)。最终化会修改底层协议的分叉选择规则,因此任何包含与区块 D 竞争的区块(即不是 D 的子孙的区块)的分支都会被排除在外。相当于修剪分支来确保最终化的区块之前没有分叉。

与上面相同的区块树,但区块 D 已被最终化 Casper FFG 分叉选择规则指出,任何不包含区块 D 的链都会被忽略,因此头块明确是 E

本质上,Casper FFG 提供的最终性可以防止长重新(回滚)。任何最终化区块及最终化区块的祖先区块都将永远不会被回滚。在以太坊的 Casper FFG 实现中,“永远”被限定在“不销毁质押以太坊总量的三分之一”的条件下。这就是 PoS 链所提供的经济最终性

LMD-GHOST

在本节中,我们将单独探讨 LMD GHOST,忽略 Casper FFG 最终性叠加层。 与 Nakamoto 共识中的最长链规则一样,LMD GHOST 也是一种分叉选择规则,是共识机制的核心,有着自己的一套属性和权衡取舍。本文会先介绍其原理,后续文章将深入探讨可能存在的问题。

命名

LMD GHOST 这个名称由两个缩写词组成,”Latest Message Driven”(最新消息驱动)和 “Greedy Heaviest-Observed Sub-Tree”(贪婪最重观测子树)。

GHOST

GHOST 协议来自 Sompolinsky 和 Zohar 在 2013 年的一篇论文,该论文讨论了如何在比特币上安全地提高交易吞吐量。增加区块大小或缩短区块间隔会使区块链在延迟不受控的网络中(例如互联网)更容易分叉。分叉的链会发生更多重组,而重组会损害交易安全性。用 GHOST 分叉选择规则替换比特币最长链分叉选择规则被证明在存在延迟的条件下更加稳定,能使出块更加频繁。

GHOST 代表了 “Greedy Heaviest-Observed Sub-Tree”(贪婪最重观测子树),这也是对算法工作原理的描述,后文将详细解释。简而言之,GHOST 的分叉选择并不遵循最长链,而是遵循最重的子树。算法认识到对区块的投票不单是投给该区块的,而是隐含了对其所有祖先区块的投票,因此整个子树都应具有相关的权重。

LMD

以太坊权益证明中使用的 GHOST 协议已经扩展到能够处理见证。在工作量证明中,投票者是区块提议者。他们通过在其之上构建自己的区块来对分支进行投票。而在权益证明协议中,所有验证者都是投票者,每个验证者平均每 6.4 分钟通过发布见证来对其网络视图进行一次投票。因此,在 PoS 下,我们会拥有更多关于参与者网络视图的信息。

这就是“消息驱动”的含义,也就是 LMD 中的 MD。分叉选择不是由提议者添加的区块驱动的,而是由所有验证者发布的消息(见证、投票)驱动的。

“L” 代表 “latest”(最新):LMD GHOST 只考虑来自每个验证者的最新消息,即从该验证者收到的最近的见证。验证者所有早期的消息都会被丢弃,但其最新投票会被保留并无限期地具有权重。

原理

LMD GHOST 首先是一个分叉选择规则。给定一个区块树和一系列投票,LMD GHOST 会告诉节点应该将哪个区块视为链头,节点可以从该块一直回溯到创世块,获得线性的历史视图。这一选择基于节点接收到的消息(区块和见证)所形成的对链的本地视图。没有“上帝视图”,节点只能依赖其本地视图,该视图可能与其他节点的本地视图大不相同。重点在于是诚实的验证者会基于他们看到的链头来构建区块,并且会根据看到的链头投票。

对 LMD GHOST 原理的介绍将分两部分进行,首先说明 LMD 部分(最新消息),随后是 GHOST 部分(确定链头)。

最新消息

在此语境下,消息是指见证中的链头投票。

LMD GHOST 中的投票

在见证的 data 中,链头投票是 beacon_block_root 字段:

1
2
3
4
5
6
7
8
class AttestationData(Container):
    slot: Slot
    index: CommitteeIndex
    # LMD GHOST 投票
    beacon_block_root: Root
    # FFG 投票
    source: Checkpoint
    target: Checkpoint

每个诚实的验证者在每个 Epoch 恰好进行一次见证,其中包含对当时其视图中的最佳链头的投票。在每个 Epoch 内,验证者集会被分割,这样每个 Slot 只有$ \frac{1}{32} $的验证者进行见证。

节点通过两种方式接收见证:直接通过证明 Gossip 协议接收,以及间接地从区块内接收。

存储最新消息

无论通过何种方式接收见证,节点都会调用分叉选择规则的 on_attestation() handler。在继续之前,on_attestation() handler 会对见证执行一些基本的有效性检查:

  • 是否太旧?

    • 见证必须来自当前或前一个 Epoch。
  • 是否太新?

    • 见证必须不迟于上一个 Slot。
  • 是否知道该见证投票的区块 beacon_block_root

    • 必须收到过该区块。如果没有,尝试从对等点处获取。
  • 见证的签名是否正确?

    • 验证者对见证进行签名并对其负责。
  • 见证是否可罚没?

    • 必须忽略与其他见证冲突的见证。

通过检查后,见证将被放入节点的 Store 中(Store 是节点对链视图信息的存储库),这一步由 update_latest_messages() 完成。

1
2
3
4
5
6
7
def update_latest_messages(store: Store, attesting_indices: Sequence[ValidatorIndex], attestation: Attestation) -> None:
    target = attestation.data.target
    beacon_block_root = attestation.data.beacon_block_root
    non_equivocating_attesting_indices = [i for i in attesting_indices if i not in store.equivocating_indices]
    for i in non_equivocating_attesting_indices:
        if i not in store.latest_messages or target.epoch > store.latest_messages[i].epoch:
            store.latest_messages[i] = LatestMessage(epoch=target.epoch, root=beacon_block_root)

如果本地没有存储该验证者的链头投票,则存储该见证和验证者信息。如果本地已存有该验证者的链头投票,若该见证更新,则进行替换。随着时间的推移,节点的 Store 会建立起一个列表,其中包含所有接收过的每个验证者的最新投票。

请注意,节点只能存储在当前或前一个 Epoch 创建的投票,一旦投票进入 Store,就会无限期地被保留,并继续影响分叉选择,直到被替换为更新的投票为止。

确定链头

本质上,LMD GHOST 分叉选择规则即函数 GetHead(Store) → HeadBlock

如前所述,节点的 Store 就是其全局视图:节点接收到的所有可能影响分叉选择的相关信息。对于 LMD GHOST 算法而言, Store 中的相关部分如下:

  • 区块树,实质是一个区块列表。区块的父链接将其在逻辑上连成了一个树。
  • 来自验证者的最新消息(投票)列表。
  • 验证者的有效余额,为算法提供了所需的权重。

GHOST 算法的目标是从给定的区块树中选择单个叶块(即没有子孙块的区块)作为链头区块。

我们假设区块树中的所有区块都来自单个根区块。在纯 GHOST 算法中,根区块就是创世区块:根据定义,所有区块都来自创世区块。而在完整的共识实现中,根区块是最后一个已确认 (Justified) 的检查点区块。重点在于 GHOST 算法会从给定的区块开始,并会忽略所有不从该区块派生的区块。

获取权重

第一步要计算树中每个分支的“权重”。投票的权重是进行投票的验证者的有效余额,通常会是 32 ETH(最大有效余额),但也有可能更少。

$B_N$表示最新链头投票目标为区块$N$的验证者的有效余额之和,$W_N$表示以区块$N$为根的分支的权重

分支权重$W_x$ 和区块投票权重$B_x$之间有一些显而易见的联系:

  • 对于仅包含叶块的分支 $L$,$W_L = B_L$。
  • 分支的权重等于其根块的投票权重与所有子分支权重之和。因此,在上图中,$W_1 = B_1 + W_2 + W_3$。
  • 分支的权重是形成该分支的子树中所有区块投票权重之和。

由于投票的权重总是正的,因此根区块的权重最大,且等于树中所有区块投票权重之和。每个验证者最多只有一个最新消息(即一个投票),因此该权重上限为所有活跃验证者的总有效余额。

获取链头

计算出每个分支或子树的权重后,算法开始递归进行。给定一个区块,选择从中派生的最重分支。然后用该分支的根块重复该过程。如果两个或更多分支权重相等,选择根块哈希值最高的分支。最终算法输出一个叶块。

从 GHOST 这个名称可见,该算法:

  • 是贪婪的,即立刻获取观测到的最重分支,不会进一步查看;
  • 处理子树,分支的权重是子树中所有区块投票权重之和。

举例如下,图中包括:特定区块的投票权重(附加到每个区块的数字)和分支权重(块连线上的数字)。

  1. 根据存储器中的最新消息,我们计算树中每个区块的投票权重。

get_head()从区块树的根块 A 开始

  1. 根据每个区块的投票权重,计算每个分支或子树的权重。

get_weight() 函数应用于块时返回该块的子树及其所有后代的总权重

  1. 递归地遍历子树根块,始终选择权重最高的分支或子树。最终到达一个叶块,即算法选择的链头区块。

在块 A 时,分支 AC 最重 在块 C 时,分支 CE 最重 块 E 是叶块,因此是 GHOST 算法选出的链头区块 链为[A←C←E]

假如以 B 和 C 为根的子树权重相等,则选择 B 和 C 中哈希值更大的分支,这是完全随机的平局打破机制。

规范中实现以上功能的是 get_head(),它从根部向上遍历树,在每个分叉处取最重的分支。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def get_head(store: Store) -> Root:
    # Get filtered block tree that only includes viable branches
    blocks = get_filtered_block_tree(store)
    # Execute the LMD-GHOST fork choice
    head = store.justified_checkpoint.root
    while True:
        children = [
            root for root in blocks.keys()
            if blocks[root].parent_root == head
        ]
        if len(children) == 0:
            return head
        # Sort by latest attesting balance with ties broken lexicographically
        # Ties broken by favoring block with lexicographically higher root
        head = max(children, key=lambda root: (get_weight(store, root), root))

计算子树权重的是 get_weight()。实际的 get_weight()实现比上面介绍的更复杂一些,主要是因为 “proposer boost” 机制,这里暂不展开,后续文章将深入探讨。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def get_weight(store: Store, root: Root) -> Gwei:
    state = store.checkpoint_states[store.justified_checkpoint]
    unslashed_and_active_indices = [
        i for i in get_active_validator_indices(state, get_current_epoch(state))
        if not state.validators[i].slashed
    ]
    attestation_score = Gwei(sum(
        state.validators[i].effective_balance for i in unslashed_and_active_indices
        if (i in store.latest_messages
            and i not in store.equivocating_indices
            and get_ancestor(store, store.latest_messages[i].root, store.blocks[root].slot) == root)
    ))
    if store.proposer_boost_root == Root():
        # Return only attestation score if ``proposer_boost_root`` is not set
        return attestation_score

    # Calculate proposer score if ``proposer_boost_root`` is set
    proposer_score = Gwei(0)
    # Boost is applied if ``root`` is an ancestor of ``proposer_boost_root``
    if get_ancestor(store, store.proposer_boost_root, store.blocks[root].slot) == root:
        committee_weight = get_total_active_balance(state) // SLOTS_PER_EPOCH
        proposer_score = (committee_weight * PROPOSER_SCORE_BOOST) // 100
    return attestation_score + proposer_score

小结

了解了 GHOST 协议的工作原理后,可以更直观地看出其相较于最长链规则的优越性。分叉的出现表明块传播时间已经接近甚至超过了出块时间(Slot),因此并非所有验证者都能及时看到所有区块并进行见证。在这种情况下,需要利用可用的大量信息:对同一个父区块两个不同子区块的投票应该被理解为所有这些验证者都支持父区块的分支,仅对子区块存有分歧。GHOST 通过让子区块的投票为其所有祖先区块增加权重实现了这一点,选择时总会优先考虑验证者总支持最多的分支。而最长链规则会丢弃这些信息,一个分支即使只有少数验证者在处理也有可能胜出。

激励机制

加密经济系统保障自身安全的一种方式是“惩恶扬善”,即奖励正当行为并惩罚不良行为。在对 LMD GHOST 的实现中,提议者和验证者都会因正确找到链头而以不同的方式获得奖励。

区块提议者隐式地获得激励。如果不在最佳链头区块上构建,那么其区块很可能不会被包含在最终的规范链中,成为孤块,那么提议者将不会收到区块奖励。工作量证明中的矿工情况与之类似。

而当验证者进行了准确的链头投票,并且其见证在下个 Slot 的区块中被包含时,将直接获得奖励。理论上,完美运行的验证者能通过准确的链头投票获得其总协议激励的大约 22%。同时,提议者则被激励在区块中包含这样的证明。

这里投票“准确”的含义是投票与最终规范链中的内容一致。如果验证者的链头投票不准确,并不会受到惩罚。因为当链上压力较大,存在延迟和丢失的区块时,准确进行投票很困难,在这种情况下惩罚验证者是不公平的。

罚没机制

权益证明设计的一大突破之一是采用罚没机制来解决 “nothing at stake” 问题。

提议者罚没

当轮到某验证者在一个特定 Slot 中生成区块时,验证者应该运行分叉选择规则来决定基于哪个现有区块来构建自己的区块。其目标是根据自身拥有的信息,识别最有可能最终成为规范链的分叉,即正确验证者集将收敛到的那个分叉。

但与工作量证明不同,在权益证明下,验证者生成区块几乎没有成本。因此,最好的策略是为每个可能的链头都生成区块,其中有一个区块一定会成为最终规范链的一部分。

但这样的行为会延长分叉并阻止网络收敛到线性历史。用户可能无法确定哪个分叉是正确的,容易受到双花攻击。这就是 “nothing at stake” 问题。解决方案如前所述,是检测两个相互矛盾的区块并惩罚提议者。

提议者分歧行为不是在协议内部检测到的,而是依赖于第三方用 ProposerSlashing 对象的形式构建证明。

1
2
3
class ProposerSlashing(Container):
    signed_header_1: SignedBeaconBlockHeader
    signed_header_2: SignedBeaconBlockHeader

该证明仅包含两个签名区块头,足以证明提议者在同一 Slot 中签署了两个区块。后续的区块提议者会将该证明包含在区块中(并获得丰厚的奖励),协议会罚没违规验证者的质押金并将其从活动验证者集中踢出。

见证者罚没

当轮到某验证者发布见证时,验证者应该运行其分叉选择规则并投票给其视图中正确的链头区块。问题在于攻击者可以做出多个相互矛盾的见证来引发或延长分叉并阻止网络收敛到单个链。如果不罚没,那么这就会成为对投票错误错过奖励的对冲方式。

措施与上述相同:检测并罚没相互矛盾的见证(同一个验证者在同一个 Slot 中针对不同链头做出的见证)。

总结

本文首先介绍了以太坊 PoS 共识协议中重要的术语和概念,并深入讲解了分叉选择规则 LMD GHOST 的机制和原理。后续文章将继续介绍 Casper FFG,以及两者结合的 Gasper,并将探讨以太坊共识协议实现中存在问题及解决方法。


  1. 注意这一点有助于我们评估以太坊的去中心化程度。比如网络上有 500000 个活跃的验证者远不能代表网络有 500000 个独立的参与者。节点数量以及验证者在节点间分布情况,是更能衡量以太坊去中心化程度的指标。 

  2. Beaconcha.in 显示了每个 Epoch 的见证参与率(也叫投票参与率),这是衡量网络运行状况的一个很好的指标。参与率通常都超过了 99%,对大规模分布式共识协议来说是十分出色的水平。 

  3. 即常说的 “nothing at stake”(利益无关)问题。 

This post is licensed under CC BY 4.0 by the author.