Merkle化和哈希根树 - 深入探讨以太坊中的SSZ Merkle化

  • thogiti
  • 发布于 2024-05-03 23:42
  • 阅读 137

文章详细探讨了以太坊共识机制中Merkleization的过程和重要性。内容涵盖了Merkle树的构建、性能优势、轻客户端支持及其在以太坊中确保共享状态的作用。此外，文章例举了详细的代码实例和图示，说明了如何对SSZ对象进行Merkle化，并明确了每一步的操作和目的。

在以太坊的共识机制中，所有参与节点就系统状态的一致性和高效性达成共识是至关重要的。简单序列化（Simple Serialize, SSZ）框架通过Merkle化作为这个过程的辅助，该过程将序列化数据转化为Merkle树结构。此维基页面讨论了Merkle化的复杂性及其在以可伸缩和安全的方式中确保节点间共享状态的重要性。

术语和方法

  • Merkle化： 指构建Merkle树并派生其根。
  • 哈希树根（Hash Tree Root）： Merkle化的一种特定应用，用于计算复杂SSZ容器的根哈希。

Merkle化的必要性

密码学哈希函数通过为Beacon状态生成紧凑、唯一的数据集表示提供了解决方案。通过对Beacon链的序列化状态进行哈希，节点可以迅速且高效地通过交换这些小的哈希输出来比较状态。

Merkle化过程

Merkle化涉及将序列化数据分解为32字节块，这些块作为Merkle树的叶子。这些块然后成对组合、一起哈希，并在树上传递此过程，直到派生出一个单一哈希——Merkle根。这个根哈希作为整个数据集的唯一指纹。关键步骤如下：

  • 分块（Chunking）： 将序列化数据分成32字节块。
  • 树构建（Tree Construction）： 将块配对，并哈希每对以形成下一层的树。重复此步骤，直到只剩下一个哈希：Merkle根。
  • 填充（Padding）： 如果块的数量不是2的幂，则添加额外的零值块以完善树，确保树保持平衡。

Merkle化的好处

  • 性能效率： 虽然树需要对大约两倍于原始数据量的内容进行哈希，但缓存机制可以存储不经常更改的子树的根。这显著减少了计算开销，因为只有更改的数据部分需要重新哈希。
  • 轻客户端支持： Merkle树结构支持创建Merkle证明——小块数据，证明特定部分的状态的包含和完整性，而无需获得整个数据集。这一特性对于资源有限的轻客户端来说至关重要，它们依赖这些证明与以太坊安全地交互。

Merkle树结构和哈希

Merkle树结构的组织方式是每两个相邻的叶节点一起被哈希以生成一个父节点，这个配对和哈希向上继续进行，直到在顶部获得一个单一的哈希：

graph TD;
    HTR[哈希树根]
    HL12[叶子1和叶子2的哈希]
    HL34[叶子3和叶子4的哈希]
    L1[叶子1]
    L2[叶子2]
    L3[叶子3]
    L4[叶子4]

    HTR --> HL12
    HTR --> HL34
    HL12 --> L1
    HL12 --> L2
    HL34 --> L3
    HL34 --> L4

图：Merkle树结构。

在某些情况下，叶子的分布可能需要更复杂的树，每个分支的深度不同，尤其是当某些节点（如包含多个元素的容器）需要额外深度时。

广义索引

为了便于在树中直接引用和验证，为每个节点（叶子和内部节点）分配了一个广义索引。该索引来自节点在树中的位置：

graph TD;
    1((1 / 深度 0))
    2((2 / 深度 1))
    3((3 / 深度 1))
    4((4 / 深度 2))
    5((5 / 深度 2))
    6((6 / 深度 2))
    7((7 / 深度 2))

    1 --> 2
    1 --> 3
    2 --> 4
    2 --> 5
    3 --> 6
    3 --> 7

图：Merkle树的广义索引和深度级别。

  • 根索引： 1（深度 = 0）
  • 后续层级： $2^{depth} + index$，其中index是该深度的节点的零索引位置。

使用广义索引的多重证明

使用广义索引的多重证明提供了一种高效的方法，以便在Merkle树中验证特定元素，而不需要知道整个树结构。这个概念在以太坊和密码应用中至关重要，因为数据完整性和验证速度至关重要。让我们通过一个例子逐步理解多重证明的工作原理：

理解结构

  • Merkle树层级分布，树中的每个节点都是一个叶子节点（包含实际数据）或内部节点（包含其子节点的哈希）。
  • 广义索引以数值形式表示树中每个节点的位置，计算方式为 $2^{depth} + index$，从根节点开始（索引为1）。

示例的树布局

  • 树的结构如下，其中*表示生成索引9的元素所需节点：
graph TD;
    1(("1*"))---2(("2"));
    1---3(("3*"));
    2---4(("4"));
    2---5(("5*"));
    3---6(("6"));
    3---7(("7"));
    4---8(("8*"));
    4---9(("9*"));
    5---10(("10"));
    5---11(("11"));
    6---12(("12"));
    6---13(("13"));
    7---14(("14"));
    7---15(("15"));

    classDef root fill:#f96;
    classDef proof fill:#bbf;
    classDef leaf fill:#faa;

    class 1 root;
    class 2,5,8,9 proof;

图：Merkle树布局

确定所需节点

  • 识别所需哈希： 要验证索引9的数据，你需要索引8、9、5、3和1的哈希。
  • 成对哈希： 组合索引8和9的哈希以计算相应的父节点的哈希，应该是hash(4)。
  • 进一步的哈希组合：
    • hash(4)将与索引5的哈希结合，以生成其父节点的哈希，hash(2)。
    • 此结果与索引3的哈希组合，向上推进到下一个层级。
  • 最终验证： 上一步的组合结果将与来自相反分支的根（索引3）一起哈希，以生成最终的树根(hash 1)。
  • 完整性检查： 如果计算出的根与已知的好根(hash 1)匹配，则索引9的数据被验证为准确。如果数据不正确，生成的根会有所不同，表明发生了错误或篡改。

共识规范中有帮助函数来计算多重证明和广义索引。可在此处查看。

计算哈希树根

SSZ对象的哈希树根是递归计算的。对于基本类型和基本类型的集合，数据打包为块并直接进行Merkle化。对于复合类型（如容器），过程涉及对每个组成部分的树根进行哈希。在以下部分中，我们将看到工作示例以理解这个过程。

打包和分块

打包和分块是在Merkle化背景下的关键概念，尤其是涉及到用于Beacon链的SSZ时。以下是打包和分块的工作方式：

序列化数据

  • 序列化涉及将数据结构（基本类型、列表、向量或位列表/位向量）根据SSZ序列化规则转换为线性字节数组。
  • 每个元素基于其类型进行序列化。

序列化的填充

  • 序列化后，字节数组可能无法完美对齐至32字节块的大小，该大小在Merkle树中使用。
  • 填充被添加到序列化的数据中，以扩展最后的部分为一个完整的32字节块。该填充由零字节（0x00）组成。

分为块

  • 填充的序列化数据被分割成多个32字节段或“块”。
  • 这些块是用于Merkle化过程的基本单元。

填充为完整的二叉树

  • 前一步得到的块的数量可能不是2的幂，而这是形成平衡二叉树（完整二叉树）所需要的。
  • 根据需要添加额外的零块（完全由零字节填充的块），以使总数达到最近的2的幂。
  • 这确保生成的Merkle树是完整和平衡的，便于高效的密码学操作。

应用Merkle化过程

  • 在块准备好后，它们被排布为二叉Merkle树的叶子。
  • Merkle化便通过对成对的块进行逐层哈希，直到只留下一个哈希。这个最终的哈希被称为Merkle根。

实际示例： 假设我们有一个需要打包和分块的整数列表：

  • 整数： [10, 20, 30, 40]（假设每个整数占用8字节）。
  • 序列化数据： 由这些整数创建的连续字节数组。
  • 填充： 如果总序列化长度不是32的倍数，将添加填充字节。
  • 块： 数据被分为32字节块。
  • 树的零填充： 如果块的数量不是2的幂，则附加额外的零填充块。
  • Merkle化： 这些块随后被用作Merkle树中的叶子，以计算根。

混合长度

混合长度是Merkle化过程中的关键步骤，尤其是在处理列表和向量时。此步骤确保最终的哈希树根准确反映数据的内容和结构，包括其长度。让我们具体看看这一概念如何应用以及为什么它很重要。

混合长度的目的

混合长度确保两个具有相似内容但不同长度的不同列表或向量生成不同的哈希树根。这一点至关重要，因为如果不将长度纳入哈希中，则两个列表——一个比另一个长，但在较短列表的长度之前相同——在仅哈希内容的情况下会生成相同的哈希树根。这可能导致潜在的安全漏洞和数据验证过程中的不一致性。

混合长度的示例

以下示例说明，在不包含列表长度的情况下，a_root_hash和b_root_hash的Merkle根哈希保持相同，尽管它们代表不同长度的两个列表。然而，当长度被纳入时，Merkle根哈希a_mix_len_root_hash与a_root_hash和b_root_hash都不同。这一区别在处理不同长度的列表或向量时至关重要。

>>> from eth2spec.utils.ssz.ssz_typing import uint256, List
>>> from eth2spec.utils.merkle_minimal import merkleize_chunks
>>> a = List[uint256, 4](33652, 59750, 92360)
>>> a_len = a.length()
>>> a = List[uint256, 4](33652, 59750, 92360).encode_bytes()
>>> b = List[uint256, 4](33652, 59750, 92360, 0).encode_bytes()
>>> a_root_hash = merkleize_chunks([a[0:32], a[32:64], a[64:96]])
>>> b_root_hash = merkleize_chunks([b[0:32], b[32:64], b[64:96], b[96:128]])
>>> a_mix_len_root_hash = merkleize_chunks([merkleize_chunks([a[0:32], a[32:64], a[64:96]]), a_len.to_bytes(32, 'little')])
>>> print('a_root_hash = ', a_root_hash)
a_root_hash =  0x3effe553b6091b1982a6850fd2a788943363e6f879ff796057503b76802edd9d
>>> print('b_root_hash = ', b_root_hash)
b_root_hash =  0x3effe553b6091b1982a6850fd2a788943363e6f879ff796057503b76802edd9d
>>> print('a_mix_len_root_hash = ', a_mix_len_root_hash)
a_mix_len_root_hash =  0xeca15347139a6ad6e7eabfbcfd3eb3bf463af2a8194c94aef742eadfcc3f1912
>>>

SSZ Merkle化中的摘要和扩展

在以太坊的权益证明（PoS）中，摘要和扩展的概念对于高效管理状态数据至关重要。摘要提供了数据结构的紧凑表示，封装了基本的验证信息，而无需完整细节。另一方面，扩展则提供完全的数据集，以便进行彻底处理或在需要详细信息时使用。以下是它们的好处：

  • 效率和速度： 通过使用摘要，验证者可以迅速验证状态更改或有效验证交易，而无需处理整个数据集。这种方法显著加速验证，并减少计算开销。
  • 减少数据负荷： 摘要减少存储和传输的数据量，节省带宽和存储资源。这对具有限制的节点（如轻客户端）特别有利，轻客户端依赖摘要来维持操作效率。
  • 安全性提升： 包含在摘要中的密码学哈希确保数据的完整性，使得能够在不访问完整数据集的情况下进行安全可靠的验证过程。
  • 示例：
    • BeaconBlock和BeaconBlockHeader： BeaconBlockHeader容器充当摘要，允许节点快速验证区块的完整性，而不需要从BeaconBlock容器中获取完整的区块数据。BeaconBlock是扩展。
    • 提案者削减： 验证者使用区块摘要有效识别和处理冲突的区块提案，促进迅速和准确的削减决定。

基本类型的Merkle化

让我们通过示例了解基本类型的Merkle化。下面是一个简单的Merkle树，我们将跟随Merkle化过程以获取Merkle根哈希。

graph TD;
    A["A"] --> HAB["H(A + B)"]
    B["B"] --> HAB
    C["C"] -->  HCD["H(C + D)"]
    D["D"] --> HCD
    HAB --> HROOT["根: H(H(A+B) + H(C+D))"]
    HCD --> HROOT

图：示例Merkle树。

在上面的Merkle树中，树的叶子是四个数据块A、B、C和D。

  • 定义数据：
    • 在此示例中，我们涉及到四个基本数据项：A、B、C和D。它们被概念化为数字（分别为10、20、30和40），并将以32字节块的形式表示在Merkle树中。
  • 数据转换为32字节块：
    • 每个数据项使用SSZ类型系统中的uint256类型序列化为32字节格式。序列化涉及到将数据转换为一致且填充的格式，以确保每个项目的长度为32字节。
  • 配对并哈希叶子：
    • 接下来，将这些序列化的数据块成对连接并进行哈希。
  • 哈希结果形成根：
    • 最终，上一步的哈希（ab和cd）将连接并哈希，以形成Merkle根。
  • 输出Merkle根：
    • 将Merkle根转换为十六进制字符串以便阅读。

这个最终的Merkle根是数据A、B、C和D的独特表示。对输入数据的任何更改将导致不同的Merkle根，显示出哈希函数对输入数据的敏感性。这一特性对于确保以太坊中的数据完整性至关重要。

>>> from eth2spec.utils.ssz.ssz_typing import uint256
>>> from eth2spec.utils.hash_function import hash
>>> a = uint256(10).to_bytes(length = 32, byteorder='little')
>>> b = uint256(20).to_bytes(length = 32, byteorder='little')
>>> c = uint256(30).to_bytes(length = 32, byteorder='little')
>>> d = uint256(40).to_bytes(length = 32, byteorder='little')
>>> ab = hash(a + b)
>>> cd = hash(c + d)
>>> abcd = hash(ab + cd)
>>> abcd.hex()
'1e3bd033dcaa8b7e8fa116cdd0469615b29b09642ed1cb5b4a8ea949fc7eee03'

复合类型的Merkle化

在本节中，我们学习如何对IndexedAttestation复合类型进行Merkle化，通过详细示例来说明这一过程。此示例清晰展示了Merkle化过程应用于复合、列表和向量类型的具体实例。同时展示了摘要和扩展如何有效地通过这一过程得以体现。

定义和结构

IndexedAttestation 是一个复合类型，结构如下：

class IndexedAttestation(Container):
    attesting_indices: List[ValidatorIndex, MAX_VALIDATORS_PER_COMMITTEE]
    data: AttestationData
    signature: BLSSignature

IndexedAttestation由三个主要组件组成：

  • attesting_indices: 一个ValidatorIndex列表，表示正在进行证明的验证者。
  • data: 一个AttestationData容器，保存与证明相关的各种数据。
  • signature: 一个BLSSignature，其为证明的签名。

Merkle化过程

IndexedAttestation的Merkle化涉及到计算每个组件的哈希树根并合并这些根以形成整个容器的哈希树根。

Merkle化attesting_indices：

  • 序列化和填充： 首先对索引列表进行序列化。考虑到该列表的潜在长度（最多到MAX_VALIDATORS_PER_COMMITTEE），通常需要填充以对齐32字节块，以进行哈希。
  • 哈希： 使用merkleize_chunks函数对序列化数据进行哈希，该函数处理填充并构建多层的Merkle树。
  • 混合长度： 由于SSZ中的列表可以长短不一但具有相同的类型结构，还需要对列表长度进行哈希（混合进）以确保不同大小列表的哈希具有唯一表示。
attesting_indices_root = merkleize_chunks(
           [
               merkleize_chunks([a.attesting_indices.encode_bytes() + bytearray(8)], 512),
               a.attesting_indices.length().to_bytes(32, 'little')
           ])

Merkle化data (AttestationData)：

  • 处理嵌套结构： AttestationData本身包含多个字段（如slot、index、beacon_block_root、source和target），每个字段被单独序列化并Merkle化。
  • 合并哈希： 这些字段的哈希被合并以产生AttestationData的根哈希。
data_root = merkleize_chunks(
    [
        a.data.slot.to_bytes(32, 'little'),
        a.data.index.to_bytes(32, 'little'),
        a.data.beacon_block_root,
        merkleize_chunks([a.data.source.epoch.to_bytes(32, 'little'), a.data.source.root]),
        merkleize_chunks([a.data.target.epoch.to_bytes(32, 'little'), a.data.target.root]),
    ])

Merkle化签名：

  • 简单哈希： BLSSignature是一个固定长度的字段，直接哈希为三个32字节块，然后进行Merkle化以得到签名的根。
signature_root = merkleize_chunks([a.signature[0:32], a.signature[32:64], a.signature[64:96]])

组合组件根：

  • 然后，计算出的每个组件的根将被组合，以计算整个IndexedAttestation容器的哈希树根。 
    indexed_attestation_root = merkleize_chunks([attesting_indices_root, data_root, signature_root])

最终根的验证：

  • IndexedAttestation有效实现Merkle化，确保数据结构中的任何部分更改都反映在最终根哈希中，从而为检测差异并确保网络中所有节点数据一致性提供了强有力的机制。
assert a.hash_tree_root() == indexed_attestation_root

现在，你可以可视化IndexedAttestation的Merkle化的全貌：

merkleization of IndexedAttestation

以下是完整的有效代码：

from eth2spec.capella import mainnet
from eth2spec.capella.mainnet import *
from eth2spec.utils.ssz.ssz_typing import *
from eth2spec.utils.merkle_minimal import merkleize_chunks

## 初始化一个IndexedAttestation类型
a = IndexedAttestation(
    attesting_indices = [33652, 59750, 92360],
    data = AttestationData(
        slot = 3080829,
        index = 9,
        beacon_block_root = '0x4f4250c05956f5c2b87129cf7372f14dd576fc152543bf7042e963196b843fe6',
        source = Checkpoint (
            epoch = 96274,
            root = '0xd24639f2e661bc1adcbe7157280776cf76670fff0fee0691f146ab827f4f1ade'
        ),
        target = Checkpoint(
            epoch = 96275,
            root = '0x9bcd31881817ddeab686f878c8619d664e8bfa4f8948707cba5bc25c8d74915d'
        )
    ),
    signature = '0xaaf504503ff15ae86723c906b4b6bac91ad728e4431aea3be2e8e3acc888d8af'
                + '5dffbbcf53b234ea8e3fde67fbb09120027335ec63cf23f0213cc439e8d1b856'
                + 'c2ddfc1a78ed3326fb9b4fe333af4ad3702159dbf9caeb1a4633b752991ac437'
)

## 容器的根是其字段根阵列的Merkle化。
## 这是IndexedAttestation。
assert(a.hash_tree_root() == merkleize_chunks(
    [
        a.attesting_indices.hash_tree_root(),
        a.data.hash_tree_root(),
        a.signature.hash_tree_root()
    ]))

## 列表序列化，然后（虚拟）填充至其完整的块数后再进行Merkle化。
## 最后，其实际长度通过进一步的哈希/记录混合在一起。
assert(a.attesting_indices.hash_tree_root() ==
       merkleize_chunks(
           [
               merkleize_chunks([a.attesting_indices.encode_bytes() + bytearray(8)], 512),
               a.attesting_indices.length().to_bytes(32, 'little')
           ]))

## 容器的根是其字段根阵列的Merkle化。
## 这是AttestationData。
assert(a.data.hash_tree_root() == merkleize_chunks(
    [
        a.data.slot.hash_tree_root(),
        a.data.index.hash_tree_root(),
        a.data.beacon_block_root.hash_tree_root(),
        a.data.source.hash_tree_root(),
        a.data.target.hash_tree_root()
    ]))

## 通过“手动”计算其字段的根来扩展上述AttestationData根。
assert(a.data.hash_tree_root() == merkleize_chunks(
    [
        a.data.slot.to_bytes(32, 'little'),
        a.data.index.to_bytes(32, 'little'),
        a.data.beacon_block_root,
        merkleize_chunks([a.data.source.epoch.to_bytes(32, 'little'), a.data.source.root]),
        merkleize_chunks([a.data.target.epoch.to_bytes(32, 'little'), a.data.target.root]),
    ]))

## 签名类型具有简单的Merkle化。
assert(a.signature.hash_tree_root() ==
       merkleize_chunks([a.signature[0:32], a.signature[32:64], a.signature[64:96]]))

## 将所有内容拆分后，我们得到了IndexedAttestation的“手动”Merkle化。
assert(a.hash_tree_root() == merkleize_chunks(
    [
        # a.attesting_indices.hash_tree_root()
        merkleize_chunks(
            [
                merkleize_chunks([a.attesting_indices.encode_bytes() + bytearray(8)], 512),
                a.attesting_indices.length().to_bytes(32, 'little')
            ]),
        # a.data.hash_tree_root()
        merkleize_chunks(
            [
                a.data.slot.to_bytes(32, 'little'),
                a.data.index.to_bytes(32, 'little'),
                a.data.beacon_block_root,
                merkleize_chunks([a.data.source.epoch.to_bytes(32, 'little'), a.data.source.root]),
                merkleize_chunks([a.data.target.epoch.to_bytes(32, 'little'), a.data.target.root]),
            ]),
        # a.signature.hash_tree_root()
        merkleize_chunks([a.signature[0:32], a.signature[32:64], a.signature[64:96]])
    ]))

print("成功！")

你可以按照运行规范中的说明执行上述代码。

资源

  • 原文链接： github.com/thogiti/thogi...
  • 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～
点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ，好文好收益，欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
thogiti
thogiti
https://thogiti.github.io/

thogiti

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！