EIP-7736: Verkle 树中叶级状态过期

简单的状态过期方案，其中仅过期“扩展和后缀树”。

摘要

向 verkle 树扩展节点添加“更新纪元”。当某个纪元到期时，可以删除扩展节点及其后缀节点。

一种带有简单 verkle 证明的新交易类型支付了重新激活扩展和后缀节点以及更新纪元计数器的成本。

动机

先前实现状态过期的尝试因复杂性迅速增加而停滞，需要在以太坊结构（地址空间扩展、oil、多棵树等）中进行大量更改。 本提案提供了一种更简单但并非详尽的状态过期方法：仅删除叶节点，并保持树的其余部分完整。这消除了对用户和开发者体验不利的方法的需求。

规范

本文档中的关键词“必须”、“禁止”、“需要”、“应该”、“不应该”、“推荐”、“不推荐”、“可以”和“可选”应按照 RFC 2119 和 RFC 8174 中的描述进行解释。

常量

对 verkle 树的更改

添加一个名为 current_epoch 的积分变量。它在分叉之前初始化为 INITIAL_EPOCH_COUNTER，并包含当前的纪元编号。

向扩展节点添加一个新的 last_epoch 字段：

def extension_and_suffix_tree(stem: bytes31, values: Dict[byte, bytes32], last_epoch: int) -> int:
    sub_leaves = [0] * 512
    for suffix, value in values.items():
        sub_leaves[2 * suffix] = int.from_bytes(value[:16], 'little') + 2**128
        sub_leaves[2 * suffix + 1] = int.from_bytes(value[16:], 'little')
    C1 = compute_commitment_root(sub_leaves[:256])
    C2 = compute_commitment_root(sub_leaves[256:])
    return compute_commitment_root([1, # Extension marker 扩展标记
                                    int.from_bytes(stem, "little"),
                                    group_to_scalar_field(C1),
                                    group_to_scalar_field(C2),
                                    last_epoch] + # Added in this EIP 在此 EIP 中添加
                                    [0] * 251)

以下规则被添加到树更新操作中：

• 对于树的读取或写入事件，检查 current_epoch < last_epoch + NUM_ACTIVE_EPOCHS。
  • 如果这是 true，则继续写入/读取
  • 否则，恢复。
• 每次为此扩展节点处理 write 事件时，last_epoch 都会使用 current_epoch 的值进行更新。

过期

在区块处理开始时，在执行交易之前，运行 check_epoch_end：

def check_epoch_end(block):
    if block.timestamp >= FORK_TIME + current_epoch * EPOCH_LENGTH:
        current_epoch = current_epoch + 1
        schedule_epiry(current_epoch-NUM_ACTIVE_EPOCHS)

由客户端实现者决定 schedule_expiry 函数的行为。

需要为过期保留的数据：

• stem 值，以便可以插入兄弟节点
• 节点 C 的承诺

该数据被称为此扩展和后缀节点的 keepsake（纪念品）。

注意：除非客户端能够恢复区块以防重组，否则实际删除可能不会在纪元的第一个区块最终确定之前发生。

复活

复活交易定义如下：

RESURRECT_TX_TYPE|ssz(Vector[stem,last_epoch,values])

其中：

• stem 用于在树中查找位置，以便可以重新创建节点；
• last_epoch 和 values 是已删除的项目；

在验证开始时，使用 EIP-4762 中定义的常量收取费用：

def resurrect_gas_cost(values) -> int:
    return WITNESS_BRANCH_COST + 
            SUBTREE_EDIT_COST +
            sum(WITNESS_CHUNK_COST + CHUNK_EDIT_COST + CHUNK_FILL_COST for i in values)

支付 gas 费用后，验证过程开始：

def validate_subtrees(tree, tx, current_epoch) -> bool:
    # The tx is a SSZ payload 该 tx 是一个 SSZ 负载
    subtrees = deserialize_ssz(tx[1:])
    if subtrees == None:
        return false
    
    # Process all subtrees in the transaction 处理交易中的所有子树
    for subtree in subtrees:
        ok = validate_subtree(tree, subtree.stem, subtree.values, subtree.last_epoch, current_epoch)
        if not ok:
            return false
        
    return true

def validate_subtree(tree, stem, values, last_epoch, current_epoch) -> bool:
    # Compute the commitment to the expired 计算对过期的承诺
    # tree, get the 获取
    expired_C = extension_and_suffix_tree(stem, values, last_epoch)
    expired = tree.get_keepsake(stem)
    if keepsake.C != expired_C:
        return false

    # Replace the keepsake with the resurrected 用复活的替换纪念品
    # extension-and-suffix tree. 扩展和后缀树。
    new_C = extension_and_suffix_tree(stem, values, current_epoch)
    return tree.resurrect_subtree(stem, new_C, values, current_epoch) == None

其中，如果成功，resurrect_subtree 将返回 None，否则返回错误。

理由

与之前的状态到期提案相比，这种方法具有简单性的优势：

• 无需地址空间扩展 (ASE)
• 它只使用一棵树，而不是每纪元多棵树
• 更小的复活动证明，因为只需提供数据即可复活。
• 明确的 gas 成本
• 仅过期“冷”数据，“热”数据集保持活动状态
• 它是向前兼容的，因为 ASE 或多棵树仍然是可能的。
• current_epoch 的求幂/加法计算每纪元只需支付一次，因此可以快速摊销。

虽然它没有删除 所有 数据，但它删除了 大部分 数据，即值和子承诺，同时保留了轻松插入兄弟节点的能力。

它也比复活单个叶子更昂贵，这是为简化付出的代价。

只有写入才更新复活计数器的原因是，对复活计数器的任何更新都具有写入的效果。这样做意味着：

• 将读取的成本增加到写入的成本。这将比 EIP-4762 中增加的 gas 成本更多。
• 实际上以读取的成本进行写入。这既会削弱状态到期，又可能会增加 DOS 向量。

向后兼容性

此提案与 verkle 向后兼容，因为默认情况下，EIP-6800 中第 4 个（索引从 0 开始）评估点的值设置为 0，这是 INITIAL_EPOCH_COUNTER 的值。

测试用例

待办事项

参考实现

待办事项

安全注意事项

需要讨论。

版权

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

Citation

Please cite this document as:

Guillaume Ballet (@gballet), Wei Han Ng (@weiihann), "EIP-7736: Verkle 树中叶级状态过期 [DRAFT]," Ethereum Improvement Proposals, no. 7736, July 2024. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-7736.