Alert Source Discuss
Standards Track: Interface

EIP-4881: 存款合约快照接口

建立用于传输存款梅克尔树快照的格式和端点

Authors Mark Mackey (@ethDreamer)
Created 2021-01-29

Table of Contents

摘要

本 EIP 定义了一种标准格式，用于在弱主观性同步期间以压缩形式传输存款合约梅克尔树。这允许新同步的共识客户端比下载所有历史存款更快地重建存款树。所提出的格式还允许客户端修剪不再需要完全参与共识的存款（参见存款最终确定流程）。

动机

为了重建存款梅克尔树，大多数客户端实现都需要信标节点下载并存储自存款合约启动以来的每个存款日志。然而，这种方法要求信标节点存储比参与共识所需的更多的存款。此外，这导致新节点的同步时间增加，这在弱主观性同步期间尤其明显。这种简单的方法也阻止了从完整节点中修剪历史合约日志，这是在限制状态增长的背景下经常讨论的前景。

规范

共识客户端可以继续以他们选择的任何方式实现存款梅克尔树。但是，当将树传输到新同步的节点时，客户端必须使用以下格式：

class DepositTreeSnapshot:
    finalized: List[Hash32, DEPOSIT_CONTRACT_DEPTH]
    deposit_root: Hash32
    deposit_count: uint64
    execution_block_hash: Hash32
    execution_block_height: uint64

其中 finalized 是一个可变长度列表（最大大小为 DEPOSIT_CONTRACT_DEPTH），包含存款最终确定流程部分中定义的哈希值。字段 deposit_root、deposit_count 和 execution_block_hash 存储与快照对应的 Eth1Data 对象相同的信息，并且 execution_block_height 是哈希值为 execution_block_hash 的执行块的高度。共识客户端必须通过信标节点 API 端点提供此结构：

/eth/v1/beacon/deposit_snapshot

存款最终确定流程

在存款处理期间，信标链要求提交存款以及到存款根的梅克尔路径。每个存款都需要执行一次。当存款已由信标链处理并且满足存款最终确定条件时，沿到存款根的路径上的许多哈希将不再需要用于构建链上的梅克尔证明。可以修剪这些不必要的哈希以节省空间。下图说明了在此过程下存款梅克尔树的演变，以及相应的 DepositTreeSnapshot，随着添加新存款和较旧的存款变为最终确定：

deposit tree evolution

原理

选择此规范中的格式是为了同时实现多个目标：

  1. 启用存款合约梅克尔树的重建，而无需完整节点存储所有历史合约日志
  2. 避免要求共识节点保留比完全参与共识所需的更多存款
  3. 实现的简易性（参见参考实现部分）
  4. 提高弱主观性同步的速度
  5. 与此机制的现有实现兼容（参见讨论）

提议的 DepositTreeSnapshot 结构包括 execution_block_hash 和 execution_block_height，以方便共识节点实现者。虽然严格来说只需要其中一个字段，但不同的客户端可能已经围绕其中一个设计了他们的区块缓存逻辑。仅发送其中一个字段将迫使一些共识客户端查询执行引擎以获取其他信息，但由于这发生在新的同步共识节点的上下文中，因此执行引擎很可能不会同步，尤其是在合并后。deposit_root 字段也不是绝对必要的，但通过包含它，新同步的共识节点可以廉价地针对自身验证任何收到的快照（参见参考实现中的 calculate_root() 方法）。

为什么不直接从存款合约重建树？

存款合约只能在链的头部提供树。由于信标链对存款合约的视图落后于执行链 ETH1_FOLLOW_DISTANCE，因此几乎总是有尚未包含在链中的存款，需要从比头部存在的树的早期版本构建证明。

为什么不从信标链中的存款重建树？

原则上，节点可以从弱主观性检查点开始向后扫描链，以找到合适的Deposit，然后从中提取树的最右侧分支。节点还需要从相应的 BeaconState 中的 Eth1Data 中提取从中开始同步新存款的 execution_block_hash。由于以下几个原因，这种方法不太理想：

  • 由于找到合适的存款进行锚定的边缘情况更加难以实现（需要最新尚未包含的存款的最右侧分支）
  • 这将使回填信标区块成为重建存款树的要求，因此也成为区块生产的要求
  • 这本质上比从弱主观性检查点获取此信息要慢

向后兼容性

此提案完全向后兼容。

测试用例

测试用例包含在 test_cases.yaml 中。每个用例的结构如下：

class DepositTestCase:
    deposit_data: DepositData     # 这些都是存款合约 deposit() 函数的输入
    deposit_data_root: Hash32     # 此存款的树哈希根（为方便起见计算）
    eth1_data: Eth1Data           # 可用于在推送此存款后最终确定树的 Eth1Data 对象
    block_height: uint64          # 具有此 Eth1Data 的执行区块的高度
    snapshot: DepositTreeSnapshot # 如果在此存款后最终确定树，则生成的 DepositTreeSnapshot 对象

此 EIP 还包括用于测试的其他文件：

如果将这些文件下载到同一目录，则可以通过在该目录中执行 pytest 来运行测试用例。

参考实现

此实现缺少完整的错误检查，并且针对可读性进行了优化，而不是效率。如果 tree 是一个 DepositTree，则可以通过调用 tree.get_snapshot() 来获得 DepositTreeSnapshot，并且可以通过调用 DepositTree.from_snapshot() 从快照中恢复树的新实例。有关何时可以通过调用 tree.finalize() 来修剪树的讨论，请参见存款最终确定条件部分。

在此实现中，针对早期版本的树生成存款证明相对较快；只需使用 copy = DepositTree.from_snapshot(tree.get_snapshot()) 创建已最终确定树的副本，然后使用 copy.push_leaf(deposit) 将剩余存款附加到所需的计数。然后可以使用 copy.get_proof(index) 获得证明。

from __future__ import annotations
from typing import List, Optional, Tuple
from dataclasses import dataclass
from abc import ABC,abstractmethod
from eip_4881 import DEPOSIT_CONTRACT_DEPTH,Hash32,sha256,to_le_bytes,zerohashes

@dataclass
class DepositTreeSnapshot:
    finalized: List[Hash32, DEPOSIT_CONTRACT_DEPTH]
    deposit_root: Hash32
    deposit_count: uint64
    execution_block_hash: Hash32
    execution_block_height: uint64

    def calculate_root(self) -> Hash32:
        size = self.deposit_count
        index = len(self.finalized)
        root = zerohashes[0]
        for level in range(0, DEPOSIT_CONTRACT_DEPTH):
            if (size & 1) == 1:
                index -= 1
                root = sha256(self.finalized[index] + root)
            else:
                root = sha256(root + zerohashes[level])
            size >>= 1
        return sha256(root + to_le_bytes(self.deposit_count))
    def from_tree_parts(finalized: List[Hash32],
                        deposit_count: uint64,
                        execution_block: Tuple[Hash32, uint64]) -> DepositTreeSnapshot:
        snapshot = DepositTreeSnapshot(
            finalized, zerohashes[0], deposit_count, execution_block[0], execution_block[1])
        # A real implementation should store the deposit_root from the eth1_data passed to
        # DepositTree.finalize() instead of relying on calculate_root() here. This allows
        # 真正的实现应该存储传递给 DepositTree.finalize() 的 eth1_data 中的 deposit_root，而不是依赖于此处的 calculate_root()。这允许
        # the snapshot to be validated using calculate_root().
        # 使用 calculate_root() 验证快照。
        snapshot.deposit_root = snapshot.calculate_root()
        return snapshot

@dataclass
class DepositTree:
    tree: MerkleTree
    mix_in_length: uint
    finalized_execution_block: Optional[Tuple[Hash32, uint64]]
    def new() -> DepositTree:
        merkle = MerkleTree.create([], DEPOSIT_CONTRACT_DEPTH)
        return DepositTree(merkle, 0, None)
    def get_snapshot(self) -> DepositTreeSnapshot:
        assert(self.finalized_execution_block is not None)
        finalized = []
        deposit_count = self.tree.get_finalized(finalized)
        return DepositTreeSnapshot.from_tree_parts(
            finalized, deposit_count, self.finalized_execution_block)
    def from_snapshot(snapshot: DepositTreeSnapshot) -> DepositTree:
        # decent validation check on the snapshot
        # 对快照进行不错的验证检查
        assert(snapshot.deposit_root == snapshot.calculate_root())
        finalized_execution_block = (snapshot.execution_block_hash, snapshot.execution_block_height)
        tree = MerkleTree.from_snapshot_parts(
            snapshot.finalized, snapshot.deposit_count, DEPOSIT_CONTRACT_DEPTH)
        return DepositTree(tree, snapshot.deposit_count, finalized_execution_block)
    def finalize(self, eth1_data: Eth1Data, execution_block_height: uint64):
        self.finalized_execution_block = (eth1_data.block_hash, execution_block_height)
        self.tree.finalize(eth1_data.deposit_count, DEPOSIT_CONTRACT_DEPTH)
    def get_proof(self, index: uint) -> Tuple[Hash32, List[Hash32]]:
        assert(self.mix_in_length > 0)
        # ensure index > finalized deposit index
        # 确保索引 > 最终确定的存款索引
        assert(index > self.tree.get_finalized([]) - 1)
        leaf, proof = self.tree.generate_proof(index, DEPOSIT_CONTRACT_DEPTH)
        proof.append(to_le_bytes(self.mix_in_length))
        return leaf, proof
    def get_root(self) -> Hash32:
        return sha256(self.tree.get_root() + to_le_bytes(self.mix_in_length))
    def push_leaf(self, leaf: Hash32):
        self.mix_in_length += 1
        self.tree = self.tree.push_leaf(leaf, DEPOSIT_CONTRACT_DEPTH)

class MerkleTree():
    @abstractmethod
    def get_root(self) -> Hash32:
        pass
    @abstractmethod
    def is_full(self) -> bool:
        pass
    @abstractmethod
    def push_leaf(self, leaf: Hash32, level: uint) -> MerkleTree:
        pass
    @abstractmethod
    def finalize(self, deposits_to_finalize: uint, level: uint) -> MerkleTree:
        pass
    @abstractmethod
    def get_finalized(self, result: List[Hash32]) -> uint:
        # returns the number of finalized deposits in the tree
        # 返回树中最终确定的存款数量
        # while populating result with the finalized hashes
        # 同时使用最终确定的哈希填充结果
        pass
    def create(leaves: List[Hash32], depth: uint) -> MerkleTree:
        if not(leaves):
            return Zero(depth)
        if not(depth):
            return Leaf(leaves[0])
        split = min(2**(depth - 1), len(leaves))
        left = MerkleTree.create(leaves[0:split], depth - 1)
        right = MerkleTree.create(leaves[split:], depth - 1)
        return Node(left, right)
    def from_snapshot_parts(finalized: List[Hash32], deposits: uint, level: uint) -> MerkleTree:
        if not(finalized) or not(deposits):
            # empty tree
            # 空树
            return Zero(level)
        if deposits == 2**level:
            return Finalized(deposits, finalized[0])
        left_subtree = 2**(level - 1)
        if deposits <= left_subtree:
            left = MerkleTree.from_snapshot_parts(finalized, deposits, level - 1)
            right = Zero(level - 1)
            return Node(left, right)
        else:
            left = Finalized(left_subtree, finalized[0])
            right = MerkleTree.from_snapshot_parts(finalized[1:], deposits - left_subtree, level - 1)
            return Node(left, right)
    def generate_proof(self, index: uint, depth: uint) -> Tuple[Hash32, List[Hash32]]:
        proof = []
        node = self
        while depth > 0:
            ith_bit = (index >> (depth - 1)) & 0x1
            if ith_bit == 1:
                proof.append(node.left.get_root())
                node = node.right
            else:
                proof.append(node.right.get_root())
                node = node.left
            depth -= 1
        proof.reverse()
        return node.get_root(), proof

@dataclass
class Finalized(MerkleTree):
    deposit_count: uint
    hash: Hash32
    def get_root(self) -> Hash32:
        return self.hash
    def is_full(self) -> bool:
        return True
    def finalize(self, deposits_to_finalize: uint, level: uint) -> MerkleTree:
        return self
    def get_finalized(self, result: List[Hash32]) -> uint:
        result.append(self.hash)
        return self.deposit_count

@dataclass
class Leaf(MerkleTree):
    hash: Hash32
    def get_root(self) -> Hash32:
        return self.hash
    def is_full(self) -> bool:
        return True
    def finalize(self, deposits_to_finalize: uint, level: uint) -> MerkleTree:
        return Finalized(1, self.hash)
    def get_finalized(self, result: List[Hash32]) -> uint:
        return 0

@dataclass
class Node(MerkleTree):
    left: MerkleTree
    right: MerkleTree
    def get_root(self) -> Hash32:
        return sha256(self.left.get_root() + self.right.get_root())
    def is_full(self) -> bool:
        return self.right.is_full()
    def push_leaf(self, leaf: Hash32, level: uint) -> MerkleTree:
        if not(self.left.is_full()):
            self.left = self.left.push_leaf(leaf, level - 1)
        else:
            self.right = self.right.push_leaf(leaf, level - 1)
        return self
    def finalize(self, deposits_to_finalize: uint, level: uint) -> MerkleTree:
        deposits = 2**level
        if deposits <= deposits_to_finalize:
            return Finalized(deposits, self.get_root())
        self.left = self.left.finalize(deposits_to_finalize, level - 1)
        if deposits_to_finalize > deposits / 2:
            remaining = deposits_to_finalize - deposits / 2
            self.right = self.right.finalize(remaining, level - 1)
        return self
    def get_finalized(self, result: List[Hash32]) -> uint:
        return self.left.get_finalized(result) + self.right.get_finalized(result)

@dataclass
class Zero(MerkleTree):
    n: uint64
    def get_root(self) -> Hash32:
        if self.n == DEPOSIT_CONTRACT_DEPTH:
            # Handle the entirely empty tree case. This is included for
            # 处理完全空树的情况。 包含此项是为了
            # consistency/clarity as the zerohashes array is typically
            # 一致性/清晰起见，因为 zerohashes 数组通常
            # only defined from 0 to DEPOSIT_CONTRACT_DEPTH - 1.
            # 仅定义为从 0 到 DEPOSIT_CONTRACT_DEPTH - 1。
            return sha256(zerohashes[self.n - 1] + zerohashes[self.n - 1])
        return zerohashes[self.n]
    def is_full(self) -> bool:
        return False
    def push_leaf(self, leaf: Hash32, level: uint) -> MerkleTree:
        return MerkleTree.create([leaf], level)
    def get_finalized(self, result: List[Hash32]) -> uint:
        return 0

安全考虑

依赖弱主观性同步

由于远程攻击，即将到来的 PoS 切换将要求新同步的节点依赖有效的弱主观性检查点。此提案依赖于弱主观性假设，即客户端不会使用无效的 WS 检查点进行引导。

存款最终确定条件

必须注意不要发送包含尚未完全包含在最终确定检查点中的存款的快照。令 state 为链中给定区块的 BeaconState。在正常操作下，存储在 state.eth1_data 中的 Eth1Data 每 EPOCHS_PER_ETH1_VOTING_PERIOD 个 epoch 替换一次。因此，存款树的最终确定以 state.eth1_data 的增量进行。令 eth1data 为某个 Eth1Data。必须满足以下两个条件才能认为 eth1data 已最终确定：

  1. 存在一个最终确定的检查点，其中对应的 state 具有 state.eth1_data == eth1data
  2. 存在一个最终确定的检查点，其中对应的 state 具有 state.eth1_deposit_index >= eth1data.deposit_count

当满足这些条件时，可以通过调用 tree.finalize(eth1data, execution_block_height) 在参考实现中修剪树

版权

在 CC0 下放弃版权及相关权利。

Citation

Please cite this document as:

Mark Mackey (@ethDreamer), "EIP-4881: 存款合约快照接口," Ethereum Improvement Proposals, no. 4881, January 2021. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-4881.