MIP-8

## 摘要

我们通过向状态模型添加页面抽象，引入了关键局部性到梅克尔帕特里夏树，使得能够进行页面级访问，并为加载页面内的任何槽提供温暖的 `SLOAD`/`SSTORE` 成本。

## 动机

EVM 将存储抽象为 32 字节的 `{slot, value}` 对。这种模型的燃气调度与梅克尔帕特里夏树的承诺方案相关，因为树是基于这些对进行操作的。这造成了一个两难局面：将 MPT 映射到磁盘会导致访问 32 字节槽需要加载整个 4KB 页面，而独立优化物理磁盘布局则使承诺层绑定于原始的基于槽的定价模型。

在这两种情况下，低效性都通过应用层和状态层传播。在应用层，高级语言如 Solidity 在映射布局时严重依赖 `keccak256` 哈希。这导致相关数据被分配到伪随机的存储位置。在状态层，MPT 在承诺之前对键进行哈希，因此顺序槽更新会修改树的离散区域。这些因素导致逻辑上连续的槽分散在离散的页面中，导致相关数据被计为独立的磁盘读取。

为了解决这个问题，我们向状态模型引入了页面抽象。页面是固定大小的 EVM 槽的连续组。页面成为磁盘 I/O 和 MPT 承诺的原子单位。一旦加载了页面，对该页面内槽的后续 `SLOAD` 和 `SSTORE` 操作将被视为温暖的。然后，树承诺 `{page_index, page}` 对。

标准的 EVM 执行语义和与现有燃气定价的向后兼容性得以保留。Solidity 中的常见存储模式自然受益于页面预热。例如，映射到结构体的操作受益，因为一旦映射条目被解析，结构体的内部字段占据连续的存储槽。这保留了现有智能合约开发的最佳实践，同时激励连续存储分组。

## 规范

我们引入以下符号：   

- 存储 `槽` 是 32 字节的值。
- EVM `字` 是 32 字节的值，如以太坊黄皮书中定义。
- EVM `页` 是 4096 字节，由 128 个字组成。 

对于给定的槽，我们通过去掉键的低 7 位来确定其分组。这将键空间分层，并让我们将页定义为 128 个 EVM 字的连续向量。每个键映射到 `(page_index, offset_within_page)`，其中一页存储 128 个连续的 EVM 字。槽到页信息的映射函数定义如下：

- `page_index(slot) = slot >> 7`
- `offset(slot) = slot & 0x7F`

### 页承诺函数

BLAKE3 支持以 1024 字节叶子粒度的包含证明，因为它在内部构建了一个基于 1024 字节块的梅克尔树。然而，单字的高效包含证明并不原生支持。 

为了恢复这一属性，我们定义了一个承诺函数，该函数通过使用 BLAKE3 构建诱导子树来计算 4096 字节页的 32 字节梅克尔根。这个承诺函数称为诱导子树梅克尔承诺（ISMC），仅对占用状态进行承诺。

设 `P` 为 4096 字节的页。请注意以下几点：

1. BLAKE3 压缩函数在 64 字节块上操作。
2. 页被划分为 64 对叶子，每个叶子由两个 32 字节的字组成。通过 64 位位图跟踪对叶子的占用情况，而承诺使用 128 位槽位图。
3. 内部节点形成一个由对叶子的占用情况决定的诱导子树，拓扑上完全绕过空分支。单例被向上携带而无需进行空哈希操作。
4. 承诺分为两个阶段：
    1. **合并阶段**：对占用的对叶子进行自下而上的归约。这捕获了页中所有活动数据的有效载荷。
    2. **封闭阶段**：结果子树根与 128 位槽位图一起进行哈希。这唯一地将数据绑定到确切的几何位置，并防止空间冲突。
5. 执行和证明大小与占用情况成比例。**合并阶段**的成本恰好是 `k - 1` 次压缩，其中 `k` 是活动对的数量。

结果根是 **页承诺**。下面展示了该承诺的伪代码实现。有关此承诺函数的完整细分，请参阅题为《通过诱导子树的梅克尔承诺》的论文。

**参考实现**

```text
Function ISMC_Commit(page, slot_bitmap):
    // 输入：
    // page: 4096 字节数组（64 对 64 字节）
    // slot_bitmap: 128 位整数，表示确切的 32 字节字的占用情况
    
    // 假设页非空
    Assert slot_bitmap != 0

    // 将 128 位槽位图转换为 64 位对位图（如果对中的任一字是活动的，则为 1）
    pair_bitmap = reduce_to_pair_bitmap(slot_bitmap)

    // 域分离的叶子 IV。一次性从常量 32 字节
    // 域字符串派生，并用于将每个活动对叶子压缩为 32
    // 字节，将叶子域与父域分开。
    PAIR_LEAF_DOMAIN = "ultra_merkle_pair_leaf_domain___"   // 32 字节
    LEAF_IV = BLAKE3_compress(state=IV,
                              block=PAIR_LEAF_DOMAIN || zeros(32),
                              block_len=64,
                              counter=0,
                              flags=DERIVE_KEY_MATERIAL)
    
    // --- 阶段 1：数据合并阶段 ---
    active_nodes = []
```

MIP-8: 页面化存储状态

==== MARKDOWN TO TRANSLATE ====
```
// 提取仅占用的配对叶子（绕过空分支）
    对于 i 从 0 到 63：
        如果 pair_bitmap 中的第 i 位被设置：
            pair_data = page[i * 64 : (i + 1) * 64]
            // 通过一次裸压缩将每个 64 字节的配对叶子减少到 32 字节
            // 使用 LEAF_IV 和 DERIVE_KEY_MATERIAL。
            leaf_hash = BLAKE3_compress(LEAF_IV, pair_data,
                                        block_len=64, counter=0,
                                        flags=DERIVE_KEY_MATERIAL)
            active_nodes.append({ index: i, value: leaf_hash })
            
    // 自下而上的减少 
    对于 level 从 0 到 5：
        next_level_nodes = []
        i = 0
        
        当 i < length(active_nodes) 时：
            current_node = active_nodes[i]
            
            // 检查活动节点中是否存在右兄弟
            如果 i + 1 < length(active_nodes)：
                next_node = active_nodes[i + 1]
                
                // 如果两个节点在下一级共享相同的父节点，则它们是兄弟
                如果 (current_node.index >> (level + 1)) == (next_node.index >> (level + 1))：
                    // 使用一次裸压缩（而不是完整的
                    // BLAKE3_Hash 管道）将两个 32 字节的子节点哈希到一个新的 32 字节
                    // 父节点，使用 CHUNK_START|CHUNK_END。
                    parent_value = BLAKE3_compress(IV,
                                                   current_node.value || next_node.value,
                                                   block_len=64, counter=0,
                                                   flags=CHUNK_START | CHUNK_END)
                    next_level_nodes.append({ index: current_node.index, value: parent_value })
                    i += 2
                    continue
            
            // 单例情况：不进行哈希直接向上
            next_level_nodes.append(current_node)
            i += 1
            
        active_nodes = next_level_nodes
        
        // 提前退出：树已完全减少为单个根
        如果 length(active_nodes) == 1：
            break
            
    subtree_root = active_nodes[0].value
    
    // --- 阶段 2：结构密封阶段 ---
    // 将子树根唯一绑定到确切的几何布局
    slot_bitmap_le_16B = to_little_endian_bytes(slot_bitmap, 16)
    seal_payload = concatenate(slot_bitmap_le_16B, subtree_root)  // 16 字节 + 32 字节
    page_commitment = BLAKE3_Hash(seal_payload)  // 无密钥
    
    返回 page_commitment
```
==== END ====

### 包含证明

直观上，ISMC 可以被视为一个嵌入的 Merkle 树，用于证明 4096 字节页面的确切状态。给定一个页面承诺，我们可以有效地证明该页面内任何特定 32 字节单词的包含性。

为了构建特定单词的包含证明，验证者必须能够使用合并计划重新计算页面承诺。因此，ISMC 包含证明由两个组件组成：

1. 128 位槽位位图：用于确定性地重建树的几何形状并证明单词的确切空间索引。
2. 兄弟哈希：从目标单词路由到在诱导合并计划下的子树根所需的最小兄弟哈希集。

包含证明的大小严格与页面的占用率相关，而不是其物理大小。设 `k` 为活动叶子的数量；最大树深度为 6。沿叶子路径的兄弟哈希数量最多为 `min(k - 1, 6)`。因此，单词的最坏情况包含证明大小严格限制为 `min(k - 1, 6) * 32 字节 + 16 字节`。

### Merkle-Patricia Trie 的叶子

Merkle Patricia Trie 提交 `{page_index_i: page_commit(page_i)}` 对，其中 `page_commit(page_i)` 是对页面内容的 32 字节承诺。

该 Trie 有以下修改：

1. **哈希函数**：Keccak。
2. **叶子值**：对于每个 `page_index`，相应的叶子值是 32 字节页面承诺的 **RLP 字符串框架**，即 `RLP_encode_string(page_commit(page_i))` = `0xa0 || page_commit(page_i)`（33 字节）。MPT 叶子节点在构建叶子 RLP 时对该字节字符串进行 RLP 编码，匹配标准 MPT 存储叶子嵌套 RLP 编码的 `U256` 值的方式。
3. **叶子位置**：每个 `page_index` 唯一确定从 MPT 根到其叶子的路径。该路径的计算方式与标准 MPT 完全相同，使用 `page_index` 作为键。
4. **Trie 结构**：MPT 结构其他方面保持不变：分支、扩展和叶子节点遵循标准 MPT 规则。
5. **按需计算**：每个存储叶子的值恰好为 32 字节，因此 `page_commit(page)` 可以根据页面内容在需要时重新计算。无需额外的存储布局更改。
6. **Merkle 证明**：页面承诺的 Merkle 证明与标准 MPT 保持不变。这样的证明仅证明特定页面已被承诺。

因此，任何单个单词的包含证明由两个组件组成：该单词在其页面承诺中的包含证明，以及页面承诺在 MPT 中的包含证明。总证明大小是这些组件的总和。

## 燃料成本

我们假设以下内容：

1. 让 `read_accessed_pages` 是当前交易中访问的读取页面集合；
2. 让 `write_accessed_pages` 是当前交易中访问的写入页面集合；
3. 让 `p = page_index(s)`。
4. `BASE_COST` 是 100 燃料；
5. `LOAD_COST` 是 8000 燃料；
6. `WRITE_COST` 是 2800 燃料；
7. `STATE_GROWTH_COST` 是 17000 燃料。


### SLOAD 燃料计划

我们将 `SLOAD` 成本定义为以下页面的成本：

```python
# 页面被缓存，则收取基础成本。
if p in read_accessed_pages: 
    gas_deducted += BASE_COST
# 页面未被缓存，则收取加载成本。
else: 
    gas_deducted += LOAD_COST + BASE_COST
    read_accessed_pages.append(p)
```

### SSTORE 燃料计划

`SSTORE` 成本可以根据 I/O 成本和状态转换成本进行分层。I/O 成本在页面粒度级别上定义，而状态转换成本则在与页面相关的 `SSTORE` 粒度上定义。然而，I/O 仍然会考虑所处理的数据是冷数据还是热数据。

最后，与传统的 `SSTORE` 一样，我们对页面应用 `LOAD_COST` 以检查初始值。

### 写入成本

让 `P0` 是给定 `SSTORE` 的页面 `p` 的初始值，让 `P1` 是 `SSTORE` 之后页面 `p` 的终值。在写入成本之前，应用加载成本以获取页面的初始值 `P0`。

以下是将页面写入硬件的 I/O 成本。

```python
# 页面 I/O 成本


# 在所有情况下扣除 `BASE_COST`。
gas_deducted += BASE_COST

# 扣除 `LOAD_COST` 以从数据库获取初始状态 P0
if p not in read_accessed_pages: 
    gas_deducted += LOAD_COST
    read_accessed_pages.append(p)

# 此 SSTORE 的页面未发生变化
if P0 == P1:
    gas_deducted += 0

# 此 SSTORE 的页面发生了变化
else:
	# 页面已收取写入费用
	if p in write_accessed_pages:
        gas_deducted += 0

	# 页面仅收取第一次写入费用
	else:
        gas_deducted += WRITE_COST

        # 页面已收取写入成本
        write_accessed_pages.append(p)

        # 实例化状态增长计数器
        current_state_growth[p] = 0
        net_state_growth[p] = 0  
        
    
```
### 状态转换成本

`SSTORE` 成本的其余部分是基于状态增长的净效应计算的。只有当交易增加页面的净状态时，才会扣除状态增长成本。如果创建了一个插槽以替换同一页面中先前清除的插槽，则增长费用将被绕过。这是为了确保剩余的燃料是单调递减的，与当前燃料模型的假设一致。这些成本是按页面定义的；没有跨页面的补贴。
```python
# 状态转换成本

# 如果页面状态增加，则将其添加到当前状态计数器增长中
if v_current == 0 and v_new != 0:
	current_state_growth[p] += 1
	
# 如果页面状态减少，则从状态增长计数器中减去
elif v_current != 0 and v_new == 0:
    current_state_growth[p] -= 1
    
# 如果净状态增长增加，则收取状态增长费用
if current_state_growth[p] > net_state_growth[p] :
	  gas_deducted += STATE_GROWTH_COST
	  net_state_growth[p]  = current_state_growth[p]
```

在执行过程中，如果调用回滚，则计数器 `current_state_growth` 和 `net_state_growth` 以及集合 `read_accessed_pages` 和 `write_accessed_pages` 必须恢复到该调用之前的值，以保持价格一致性。

## 理由

在页面边界对齐的连续块中分配存储的合约在经济上是最优的，受益于较低的 gas 成本和高效的包含证明。由于页面承诺执行和证明大小与活动对的数量成比例，架构本质上与 EVM 的存储模式对齐：

1. **随机稀疏状态**：两个随机哈希键在同一页面内碰撞的概率约为 1 in 2<sup>249</sup>。因此，标准映射槽很可能是其页面中唯一被填充的元素，并且其页面承诺可以在没有兄弟哈希的情况下重建。当前基于映射的状态的证明大小在位图开销之外保持稳定。
2. **连续状态**：当一个页面包含一个密集打包的连续字集合时，多字包含只需要数据块外边界的兄弟哈希。这使得每个字的证明大小摊销，从而使连续多字包含证明在位图开销之外更加高效。
3. **摊销稀疏读取**：当一个页面随机稀疏填充时，单字包含证明在页面内会产生小的、有界的开销。在均匀分布下，预期的证明大小以 `O(log k)` 的方式对数增长。

选择 BLAKE3 是因为其哈希速度、适合 zk 证明生成和 BAO 构造。这允许在标准情况下和证明生成中更快的梅克尔化。将 BLAKE3 应用于整个梅克尔树还通过 BAO 构造启用了字节码包含证明。

## 向后兼容性

在此更新下，EVM 语义保持不变。