Merkle 证明格式

ethereum
发布于 2025-01-16 15:18
阅读 76

本文详细介绍了Merkle证明的格式，包括各种辅助函数和数据结构。文章中展示了如何生成Merkle树以及实现Merkle多重证明，并通过代码示例详细解释了各个函数的作用和实现原理，具有较高的技术深度和实用价值。

## Merkle 证明格式

### 目录

- [辅助函数](#辅助函数)
- [广义 Merkle 树索引](#广义-merkle-树索引)
- [SSZ 对象到索引](#ssz-对象到索引)
  - [广义索引的辅助方法](#广义索引的辅助方法)
    - [`concat_generalized_indices`](#concat_generalized_indices)
    - [`get_generalized_index_length`](#get_generalized_index_length)
    - [`get_generalized_index_bit`](#get_generalized_index_bit)
    - [`generalized_index_sibling`](#generalized_index_sibling)
    - [`generalized_index_child`](#generalized_index_child)
    - [`generalized_index_parent`](#generalized_index_parent)
- [Merkle 多重证明](#merkle-多重证明)

### 辅助函数

```python
def get_power_of_two_ceil(x: int) -> int:
    """
    获取给定输入的 2 的幂，如果输入不是 2 的幂则返回最接近的更高的 2 的幂。
    通常用于“我需要多少个节点来适应 x 个元素的底层树层？”
    示例：0->1, 1->1, 2->2, 3->4, 4->4, 5->8, 6->8, 7->8, 8->8, 9->16。
    """
    if x <= 1:
        return 1
    elif x == 2:
        return 2
    else:
        return 2 * get_power_of_two_ceil((x + 1) // 2)
```

```python
def get_power_of_two_floor(x: int) -> int:
    """
    获取给定输入的 2 的幂，如果输入不是 2 的幂则返回最接近的更低的 2 的幂。
    0 的情况是占位符，不用于与广义索引的数学运算。
    通常用于“哪一位 2 的幂组成了广义索引的根位？” 
    示例：0->1, 1->1, 2->2, 3->2, 4->4, 5->4, 6->4, 7->4, 8->8, 9->8
    """
    if x <= 1:
        return 1
    if x == 2:
        return x
    else:
        return 2 * get_power_of_two_floor(x // 2)
```

### 广义 Merkle 树索引

在二叉 Merkle 树中，我们将节点的“广义索引”定义为 `2**depth + index`。从视觉上看，它如下所示：

```
    1
 2     3
4 5   6 7
   ...
```

注意广义索引具有一个便利的属性，即节点 `k` 的两个子节点分别为 `2k` 和 `2k+1`，并且它等于通过此函数计算的 Merkle 树中节点的线性表示的位置：

```python
def merkle_tree(leaves: Sequence[Bytes32]) -> Sequence[Bytes32]:
    """
    返回通过广义索引表示的树节点数组：
    [0, 1, 2, 3, 4, 5, 6, 7]，其中每层是 2 的幂。0 索引被忽略。1 索引是根。
    结果的大小将是输入叶子节点填充底层的两倍。
    """
    bottom_length = get_power_of_two_ceil(len(leaves))
    o = [Bytes32()] * bottom_length + list(leaves) + [Bytes32()] * (bottom_length - len(leaves))
    for i in range(bottom_length - 1, 0, -1):
        o[i] = hash(o[i * 2] + o[i * 2 + 1])
    return o
```

我们在本文件中将自定义类型 `GeneralizedIndex` 定义为 Python 整数类型。它也可以表示为 Bitvector/Bitlist 对象。

我们将根据广义索引来定义 Merkle 证明。

### SSZ 对象到索引

我们可以描述任何 SSZ 对象的哈希树，根植于 `hash_tree_root(object)`，作为一个二叉 Merkle 树，其深度可能不同。例如，一个对象 `{x: bytes32, y: List[uint64]}` 看起来如下：

```
     root
    /    \
   x    y_root
        /    \
y_data_root  len(y)
    / \
   /\ /\
  .......
```

我们现在可以定义一个“路径”的概念，用于描述一个函数，该函数以 SSZ 对象为输入，并输出某个特定的（可能深度嵌套的）成员。例如，`foo -> foo.x` 是一条路径，`foo -> len(foo.y)` 和 `foo -> foo.y[5].w` 也是。同样，我们将路径描述为列表，可以有两种表示方式。在“人类可读的形式”中，它们分别为 `["x"]`、`["y", "__len__"]` 和 `["y", 5, "w"]`。在“编码形式”中，它们是 `uint64` 值的列表，在这些情况下（假设 `foo` 的字段顺序为 `x` 然后 `y`，并且 `w` 是 `y[i]` 的第一个字段）为 `[0]`、`[1, 2**64-1]`、`[1, 5, 0]`。我们定义 `SSZVariableName` 为成员变量名字符串，即路径表示为整数序列和 `SSZVariableName`。

```python
def item_length(typ: SSZType) -> int:
    """
    返回基本类型的字节数，或复合类型的 32（一个完整的哈希）。
    """
    if issubclass(typ, BasicValue):
        return typ.byte_len
    else:
        return 32
```

```python
def get_elem_type(typ: Union[BaseBytes, BaseList, Container],
                  index_or_variable_name: Union[int, SSZVariableName]) -> SSZType:
    """
    返回给定类型对象的具有给定索引或成员变量名称的元素类型（例如，对于 `x[7]` 的 `7`，
    对于 `x.foo` 的 `"foo"`）。
    """
    return typ.get_fields()[index_or_variable_name] if issubclass(typ, Container) else typ.elem_type
```

```python
def chunk_count(typ: SSZType) -> int:
    """
    返回在给定类型中表示顶层元素所需的哈希数量
    （例如 `x.foo` 或 `x[7]` 但不是 `x[7].bar` 或 `x.foo.baz`）。在所有除了基本类型列表/向量的情况下，
    这只是顶层元素的数量，因为每个元素都有一个哈希。对于基本类型的列表/向量，由于多个基本元素
    可以打包到一个 32 字节的块中，因此通常更少。
    """
    # typ.length 描述列表类型的限制，或向量类型的长度。
    if issubclass(typ, BasicValue):
        return 1
    elif issubclass(typ, Bits):
        return (typ.length + 255) // 256
    elif issubclass(typ, Elements):
        return (typ.length * item_length(typ.elem_type) + 31) // 32
    elif issubclass(typ, Container):
        return len(typ.get_fields())
    else:
        raise Exception(f"不支持类型: {typ}")
```

```python
def get_item_position(typ: SSZType, index_or_variable_name: Union[int, SSZVariableName]) -> Tuple[int, int, int]:
    """
    返回三个变量：
        (i) 表示给定元素在块中表示的索引；
        (ii) 块内的起始字节位置；
        (iii) 块内的结束字节位置。
    例如：对于一个 6 项的 uint64 值列表，index=2 将返回 (0, 16, 24)，index=5 将返回 (1, 8, 16)
    """
    if issubclass(typ, Elements):
        index = int(index_or_variable_name)
        start = index * item_length(typ.elem_type)
        return start // 32, start % 32, start % 32 + item_length(typ.elem_type)
    elif issubclass(typ, Container):
        variable_name = index_or_variable_name
        return typ.get_field_names().index(variable_name), 0, item_length(get_elem_type(typ, variable_name))
    else:
        raise Exception("仅支持列表/向量/容器")
```

```python
def get_generalized_index(typ: SSZType, *path: PyUnion[int, SSZVariableName]) -> GeneralizedIndex:
    """
    将路径（例如 `[7, "foo", 3]` 表示 `x[7].foo[3]`，
    `[12, "bar", "__len__"]` 表示 `len(x[12].bar)`）转换为表示其在 Merkle 树中的位置的广义索引。
    """
    root = GeneralizedIndex(1)
    for p in path:
        assert not issubclass(typ, BasicValue)  # 如果我们深入到一个基本类型，路径无法继续
        if p == '__len__':
            assert issubclass(typ, (List, ByteList))
            typ = uint64
            root = GeneralizedIndex(root * 2 + 1)
        else:
            pos, _, _ = get_item_position(typ, p)
            base_index = (GeneralizedIndex(2) if issubclass(typ, (List, ByteList)) else GeneralizedIndex(1))
            root = GeneralizedIndex(root * base_index * get_power_of_two_ceil(chunk_count(typ)) + pos)
            typ = get_elem_type(typ, p)
    return root
```

#### 广义索引的辅助方法

_使用说明：此部分以外的函数应仅使用此部分中的函数来操作广义索引。这是为了方便开发者实现具有不同于大整数的底层表示的广义索引。_

##### `concat_generalized_indices`

```python
def concat_generalized_indices(*indices: GeneralizedIndex) -> GeneralizedIndex:
    """
    给定广义索引 i1 用于 A -> B，i2 用于 B -> C .... i_n 用于 Y -> Z，返回
    A -> Z 的广义索引。
    """
    o = GeneralizedIndex(1)
    for i in indices:
        o = GeneralizedIndex(o * get_power_of_two_floor(i) + (i - get_power_of_two_floor(i)))
    return o
```

##### `get_generalized_index_length`

```python
def get_generalized_index_length(index: GeneralizedIndex) -> int:
    """
    返回由广义索引表示的路径的长度。
    """
    return int(log2(index))
```

##### `get_generalized_index_bit`

```python
def get_generalized_index_bit(index: GeneralizedIndex, position: int) -> bool:
    """
    返回广义索引的给定位。
    """
    return (index & (1 << position)) > 0
```

##### `generalized_index_sibling`

```python
def generalized_index_sibling(index: GeneralizedIndex) -> GeneralizedIndex:
    return GeneralizedIndex(index ^ 1)
```

##### `generalized_index_child`

```python
def generalized_index_child(index: GeneralizedIndex, right_side: bool) -> GeneralizedIndex:
    return GeneralizedIndex(index * 2 + right_side)
```

##### `generalized_index_parent`

```python
def generalized_index_parent(index: GeneralizedIndex) -> GeneralizedIndex:
    return GeneralizedIndex(index // 2)
```

### Merkle 多重证明

我们将 Merkle 多重证明定义为在 Merkle 树中所需的最小节点子集，以完全认证一组节点确实是具有特定根的某个 Merkle 树的一部分，位于一组特定的广义索引。例如，以下是一个包含位置 0、1、6 在 8 节点 Merkle 树中的多重证明（即广义索引 8、9、14）：

```
       .
   .       .
 .   *   *   .
x x . . . . x *
```

. 是未使用的节点，* 是已使用的节点，x 是我们试图证明的值。注意，尽管这是 3 个值的多重证明，但仅需 3 个辅助节点，这与证明单个值所需的数量相同。通常，效率增益不会如此极端，但相比单个 Merkle 证明，节省仍然显著。作为经验法则，对于 n 节点树中的 k 个节点的多重证明，大小为 `k * (n/k + log(n/k))`。

首先，我们提供一种计算给定广义索引的证明所需的辅助树节点的广义索引的方法：

```python
def get_branch_indices(tree_index: GeneralizedIndex) -> Sequence[GeneralizedIndex]:
    """
    获取从具有给定树索引的块到根的路径上姐妹块的广义索引。
    """
    o = [generalized_index_sibling(tree_index)]
    while o[-1] > 1:
        o.append(generalized_index_sibling(generalized_index_parent(o[-1])))
    return o[:-1]
```

```python
def get_path_indices(tree_index: GeneralizedIndex) -> Sequence[GeneralizedIndex]:
    """
    获取从具有给定树索引的块到根的路径上块的广义索引。
    """
    o = [tree_index]
    while o[-1] > 1:
        o.append(generalized_index_parent(o[-1]))
    return o[:-1]
```

```python
def get_helper_indices(indices: Sequence[GeneralizedIndex]) -> Sequence[GeneralizedIndex]:
    """
    获取证明具有给定广义索引的块所需的所有“额外”块的广义索引。
    注意，选择递减顺序是故意的，以确保与单项 Merkle 证明中的哈希顺序等价。
    """
    all_helper_indices: Set[GeneralizedIndex] = set()
    all_path_indices: Set[GeneralizedIndex] = set()
    for index in indices:
        all_helper_indices = all_helper_indices.union(set(get_branch_indices(index)))
        all_path_indices = all_path_indices.union(set(get_path_indices(index)))

return sorted(all_helper_indices.difference(all_path_indices), reverse=True)
```

现在我们提供 Merkle 证明验证函数。首先是单项证明：

```python
def calculate_merkle_root(leaf: Bytes32, proof: Sequence[Bytes32], index: GeneralizedIndex) -> Root:
    assert len(proof) == get_generalized_index_length(index)
    for i, h in enumerate(proof):
        if get_generalized_index_bit(index, i):
            leaf = hash(h + leaf)
        else:
            leaf = hash(leaf + h)
    return leaf
```

```python
def verify_merkle_proof(leaf: Bytes32, proof: Sequence[Bytes32], index: GeneralizedIndex, root: Root) -> bool:
    return calculate_merkle_root(leaf, proof, index) == root
```

现在是多项证明：

```python
def calculate_multi_merkle_root(leaves: Sequence[Bytes32],
                                proof: Sequence[Bytes32],
                                indices: Sequence[GeneralizedIndex]) -> Root:
    assert len(leaves) == len(indices)
    helper_indices = get_helper_indices(indices)
    assert len(proof) == len(helper_indices)
    objects = {
        **{index: node for index, node in zip(indices, leaves)},
        **{index: node for index, node in zip(helper_indices, proof)}
    }
    keys = sorted(objects.keys(), reverse=True)
    pos = 0
    while pos < len(keys):
        k = keys[pos]
        if k in objects and k ^ 1 in objects and k // 2 not in objects:
            objects[GeneralizedIndex(k // 2)] = hash(
                objects[GeneralizedIndex((k | 1) ^ 1)] +
                objects[GeneralizedIndex(k | 1)]
            )
            keys.append(GeneralizedIndex(k // 2))
        pos += 1
    return objects[GeneralizedIndex(1)]
```

```python
def verify_merkle_multiproof(leaves: Sequence[Bytes32],
                             proof: Sequence[Bytes32],
                             indices: Sequence[GeneralizedIndex],
                             root: Root) -> bool:
    return calculate_multi_merkle_root(leaves, proof, indices) == root
```

注意，单项证明是多项证明的特例；有效的单项证明在放入多项验证函数时会正确验证（只需将输入参数 `index -> [index]` 和 `leaf -> [leaf]` 进行自然的调整）。还需注意，`calculate_merkle_root` 和 `calculate_multi_merkle_root` 可以独立使用来计算更新叶子节点的证明的新 Merkle 根。

>- 原文链接： [github.com/ethereum/cons...](https://github.com/ethereum/consensus-specs/blob/dev/ssz/merkle-proofs.md)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

Merkle 证明格式

辅助函数

def get_power_of_two_ceil(x: int) -> int:
    """
    获取给定输入的 2 的幂，如果输入不是 2 的幂则返回最接近的更高的 2 的幂。
    通常用于“我需要多少个节点来适应 x 个元素的底层树层？”
    示例：0->1, 1->1, 2->2, 3->4, 4->4, 5->8, 6->8, 7->8, 8->8, 9->16。
    """
    if x &lt;= 1:
        return 1
    elif x == 2:
        return 2
    else:
        return 2 * get_power_of_two_ceil((x + 1) // 2)

def get_power_of_two_floor(x: int) -> int:
    """
    获取给定输入的 2 的幂，如果输入不是 2 的幂则返回最接近的更低的 2 的幂。
    0 的情况是占位符，不用于与广义索引的数学运算。
    通常用于“哪一位 2 的幂组成了广义索引的根位？” 
    示例：0->1, 1->1, 2->2, 3->2, 4->4, 5->4, 6->4, 7->4, 8->8, 9->8
    """
    if x &lt;= 1:
        return 1
    if x == 2:
        return x
    else:
        return 2 * get_power_of_two_floor(x // 2)

广义 Merkle 树索引

在二叉 Merkle 树中，我们将节点的“广义索引”定义为 2**depth + index。从视觉上看，它如下所示：

注意广义索引具有一个便利的属性，即节点 k 的两个子节点分别为 2k 和 2k+1，并且它等于通过此函数计算的 Merkle 树中节点的线性表示的位置：

def merkle_tree(leaves: Sequence[Bytes32]) -> Sequence[Bytes32]:
    """
    返回通过广义索引表示的树节点数组：
    [0, 1, 2, 3, 4, 5, 6, 7]，其中每层是 2 的幂。0 索引被忽略。1 索引是根。
    结果的大小将是输入叶子节点填充底层的两倍。
    """
    bottom_length = get_power_of_two_ceil(len(leaves))
    o = [Bytes32()] * bottom_length + list(leaves) + [Bytes32()] * (bottom_length - len(leaves))
    for i in range(bottom_length - 1, 0, -1):
        o[i] = hash(o[i * 2] + o[i * 2 + 1])
    return o

我们在本文件中将自定义类型 GeneralizedIndex 定义为 Python 整数类型。它也可以表示为 Bitvector/Bitlist 对象。

我们将根据广义索引来定义 Merkle 证明。

SSZ 对象到索引

我们可以描述任何 SSZ 对象的哈希树，根植于 hash_tree_root(object)，作为一个二叉 Merkle 树，其深度可能不同。例如，一个对象 {x: bytes32, y: List[uint64]} 看起来如下：

     root
    /    \
   x    y_root
        /    \
y_data_root  len(y)
    / \
   /\ /\
  .......

我们现在可以定义一个“路径”的概念，用于描述一个函数，该函数以 SSZ 对象为输入，并输出某个特定的（可能深度嵌套的）成员。例如，foo -> foo.x 是一条路径，foo -> len(foo.y) 和 foo -> foo.y[5].w 也是。同样，我们将路径描述为列表，可以有两种表示方式。在“人类可读的形式”中，它们分别为 ["x"]、["y", "__len__"] 和 ["y", 5, "w"]。在“编码形式”中，它们是 uint64 值的列表，在这些情况下（假设 foo 的字段顺序为 x 然后 y，并且 w 是 y[i] 的第一个字段）为 [0]、[1, 2**64-1]、[1, 5, 0]。我们定义 SSZVariableName 为成员变量名字符串，即路径表示为整数序列和 SSZVariableName。

def item_length(typ: SSZType) -> int:
    """
    返回基本类型的字节数，或复合类型的 32（一个完整的哈希）。
    """
    if issubclass(typ, BasicValue):
        return typ.byte_len
    else:
        return 32

def get_elem_type(typ: Union[BaseBytes, BaseList, Container],
                  index_or_variable_name: Union[int, SSZVariableName]) -> SSZType:
    """
    返回给定类型对象的具有给定索引或成员变量名称的元素类型（例如，对于 `x[7]` 的 `7`，
    对于 `x.foo` 的 `"foo"`）。
    """
    return typ.get_fields()[index_or_variable_name] if issubclass(typ, Container) else typ.elem_type

def chunk_count(typ: SSZType) -> int:
    """
    返回在给定类型中表示顶层元素所需的哈希数量
    （例如 `x.foo` 或 `x[7]` 但不是 `x[7].bar` 或 `x.foo.baz`）。在所有除了基本类型列表/向量的情况下，
    这只是顶层元素的数量，因为每个元素都有一个哈希。对于基本类型的列表/向量，由于多个基本元素
    可以打包到一个 32 字节的块中，因此通常更少。
    """
    # typ.length 描述列表类型的限制，或向量类型的长度。
    if issubclass(typ, BasicValue):
        return 1
    elif issubclass(typ, Bits):
        return (typ.length + 255) // 256
    elif issubclass(typ, Elements):
        return (typ.length * item_length(typ.elem_type) + 31) // 32
    elif issubclass(typ, Container):
        return len(typ.get_fields())
    else:
        raise Exception(f"不支持类型: {typ}")

def get_item_position(typ: SSZType, index_or_variable_name: Union[int, SSZVariableName]) -> Tuple[int, int, int]:
    """
    返回三个变量：
        (i) 表示给定元素在块中表示的索引；
        (ii) 块内的起始字节位置；
        (iii) 块内的结束字节位置。
    例如：对于一个 6 项的 uint64 值列表，index=2 将返回 (0, 16, 24)，index=5 将返回 (1, 8, 16)
    """
    if issubclass(typ, Elements):
        index = int(index_or_variable_name)
        start = index * item_length(typ.elem_type)
        return start // 32, start % 32, start % 32 + item_length(typ.elem_type)
    elif issubclass(typ, Container):
        variable_name = index_or_variable_name
        return typ.get_field_names().index(variable_name), 0, item_length(get_elem_type(typ, variable_name))
    else:
        raise Exception("仅支持列表/向量/容器")

def get_generalized_index(typ: SSZType, *path: PyUnion[int, SSZVariableName]) -> GeneralizedIndex:
    """
    将路径（例如 `[7, "foo", 3]` 表示 `x[7].foo[3]`，
    `[12, "bar", "__len__"]` 表示 `len(x[12].bar)`）转换为表示其在 Merkle 树中的位置的广义索引。
    """
    root = GeneralizedIndex(1)
    for p in path:
        assert not issubclass(typ, BasicValue)  # 如果我们深入到一个基本类型，路径无法继续
        if p == '__len__':
            assert issubclass(typ, (List, ByteList))
            typ = uint64
            root = GeneralizedIndex(root * 2 + 1)
        else:
            pos, _, _ = get_item_position(typ, p)
            base_index = (GeneralizedIndex(2) if issubclass(typ, (List, ByteList)) else GeneralizedIndex(1))
            root = GeneralizedIndex(root * base_index * get_power_of_two_ceil(chunk_count(typ)) + pos)
            typ = get_elem_type(typ, p)
    return root

广义索引的辅助方法

使用说明：此部分以外的函数应仅使用此部分中的函数来操作广义索引。这是为了方便开发者实现具有不同于大整数的底层表示的广义索引。

`concat_generalized_indices`

def concat_generalized_indices(*indices: GeneralizedIndex) -> GeneralizedIndex:
    """
    给定广义索引 i1 用于 A -> B，i2 用于 B -> C .... i_n 用于 Y -> Z，返回
    A -> Z 的广义索引。
    """
    o = GeneralizedIndex(1)
    for i in indices:
        o = GeneralizedIndex(o * get_power_of_two_floor(i) + (i - get_power_of_two_floor(i)))
    return o

`get_generalized_index_length`

def get_generalized_index_length(index: GeneralizedIndex) -> int:
    """
    返回由广义索引表示的路径的长度。
    """
    return int(log2(index))

`get_generalized_index_bit`

def get_generalized_index_bit(index: GeneralizedIndex, position: int) -> bool:
    """
    返回广义索引的给定位。
    """
    return (index & (1 &lt;&lt; position)) > 0

`generalized_index_sibling`

def generalized_index_sibling(index: GeneralizedIndex) -> GeneralizedIndex:
    return GeneralizedIndex(index ^ 1)

`generalized_index_child`

def generalized_index_child(index: GeneralizedIndex, right_side: bool) -> GeneralizedIndex:
    return GeneralizedIndex(index * 2 + right_side)

`generalized_index_parent`

def generalized_index_parent(index: GeneralizedIndex) -> GeneralizedIndex:
    return GeneralizedIndex(index // 2)

Merkle 多重证明

       .
   .       .
 .   *   *   .
x x . . . . x *

. 是未使用的节点，是已使用的节点，x 是我们试图证明的值。注意，尽管这是 3 个值的多重证明，但仅需 3 个辅助节点，这与证明单个值所需的数量相同。通常，效率增益不会如此极端，但相比单个 Merkle 证明，节省仍然显著。作为经验法则，对于 n 节点树中的 k 个节点的多重证明，大小为 `k (n/k + log(n/k))`。

首先，我们提供一种计算给定广义索引的证明所需的辅助树节点的广义索引的方法：

def get_branch_indices(tree_index: GeneralizedIndex) -> Sequence[GeneralizedIndex]:
    """
    获取从具有给定树索引的块到根的路径上姐妹块的广义索引。
    """
    o = [generalized_index_sibling(tree_index)]
    while o[-1] > 1:
        o.append(generalized_index_sibling(generalized_index_parent(o[-1])))
    return o[:-1]

def get_path_indices(tree_index: GeneralizedIndex) -> Sequence[GeneralizedIndex]:
    """
    获取从具有给定树索引的块到根的路径上块的广义索引。
    """
    o = [tree_index]
    while o[-1] > 1:
        o.append(generalized_index_parent(o[-1]))
    return o[:-1]

def get_helper_indices(indices: Sequence[GeneralizedIndex]) -> Sequence[GeneralizedIndex]:
    """
    获取证明具有给定广义索引的块所需的所有“额外”块的广义索引。
    注意，选择递减顺序是故意的，以确保与单项 Merkle 证明中的哈希顺序等价。
    """
    all_helper_indices: Set[GeneralizedIndex] = set()
    all_path_indices: Set[GeneralizedIndex] = set()
    for index in indices:
        all_helper_indices = all_helper_indices.union(set(get_branch_indices(index)))
        all_path_indices = all_path_indices.union(set(get_path_indices(index)))

    return sorted(all_helper_indices.difference(all_path_indices), reverse=True)

现在我们提供 Merkle 证明验证函数。首先是单项证明：

def calculate_merkle_root(leaf: Bytes32, proof: Sequence[Bytes32], index: GeneralizedIndex) -> Root:
    assert len(proof) == get_generalized_index_length(index)
    for i, h in enumerate(proof):
        if get_generalized_index_bit(index, i):
            leaf = hash(h + leaf)
        else:
            leaf = hash(leaf + h)
    return leaf

def verify_merkle_proof(leaf: Bytes32, proof: Sequence[Bytes32], index: GeneralizedIndex, root: Root) -> bool:
    return calculate_merkle_root(leaf, proof, index) == root

现在是多项证明：

def calculate_multi_merkle_root(leaves: Sequence[Bytes32],
                                proof: Sequence[Bytes32],
                                indices: Sequence[GeneralizedIndex]) -> Root:
    assert len(leaves) == len(indices)
    helper_indices = get_helper_indices(indices)
    assert len(proof) == len(helper_indices)
    objects = {
        **{index: node for index, node in zip(indices, leaves)},
        **{index: node for index, node in zip(helper_indices, proof)}
    }
    keys = sorted(objects.keys(), reverse=True)
    pos = 0
    while pos &lt; len(keys):
        k = keys[pos]
        if k in objects and k ^ 1 in objects and k // 2 not in objects:
            objects[GeneralizedIndex(k // 2)] = hash(
                objects[GeneralizedIndex((k | 1) ^ 1)] +
                objects[GeneralizedIndex(k | 1)]
            )
            keys.append(GeneralizedIndex(k // 2))
        pos += 1
    return objects[GeneralizedIndex(1)]

def verify_merkle_multiproof(leaves: Sequence[Bytes32],
                             proof: Sequence[Bytes32],
                             indices: Sequence[GeneralizedIndex],
                             root: Root) -> bool:
    return calculate_multi_merkle_root(leaves, proof, indices) == root

注意，单项证明是多项证明的特例；有效的单项证明在放入多项验证函数时会正确验证（只需将输入参数 index -> [index] 和 leaf -> [leaf] 进行自然的调整）。还需注意，calculate_merkle_root 和 calculate_multi_merkle_root 可以独立使用来计算更新叶子节点的证明的新 Merkle 根。

原文链接： github.com/ethereum/cons...

登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。

Merkle 证明格式

Merkle 证明格式

目录

辅助函数

广义 Merkle 树索引

SSZ 对象到索引

广义索引的辅助方法

`concat_generalized_indices`

`get_generalized_index_length`

`get_generalized_index_bit`

`generalized_index_sibling`

`generalized_index_child`

`generalized_index_parent`

Merkle 多重证明

0 条评论

文章目录