Go 上的默克尔树：泛型和证明

Go语言中的默克尔树：泛型实现与包含性证明

在拥有数百万条记录的系统（如区块链）中，验证特定元素的存在通常需要传输整个数据集。默克尔树解决了这个问题：不再需要百万笔交易，只需O(log N)个哈希值——对于一百万个元素，大约只需20个。该结构构建为二叉树，每个节点对其子节点进行哈希运算，根节点则汇总整个集合。

示例：交易A、B、C、D。直接对整个集合进行哈希运算要求客户端拥有所有数据以进行验证。在树中，客户端接收相邻哈希值：H(B)、H(CD)——并独立地从叶子A到根节点重建根哈希。

基础接口与节点类型

从支持泛型的树节点接口开始：

type Node[T any] interface {
    String() string
    StringIndent(level int) string
    AddChild(Node[T])
    GetBytes() []byte
    GetChildren() []Node[T]
}

叶子存储值及其哈希。为了序列化任意类型的值，使用CBOR——一种确定性格式（RFC 8949），不同于JSON中映射键顺序不稳定的情况。

type Leaf[T any] struct {
    Value     T
    ValueHash []byte
}

func NewLeaf[T](value T, hash hash.Hash) (*Leaf[T], error) {
    hashedValue, err := valueToHash(value, hash)
    if err != nil {
        return nil, err
    }
    return &Leaf[T]{Value: value, ValueHash: hashedValue}, nil
}

func valueToHash(value any, hash hash.Hash) ([]byte, error) {
    encoded, err := cbor.Marshal(value)
    if err != nil {
        return nil, err
    }
    hash.Reset()
    hash.Write(encoded)
    return hash.Sum(nil), nil
}

二进制节点聚合左右子节点：

type BinaryNode[T any] struct {
    Value []byte
    Right Node[T]
    Left  Node[T]
}

使用哈希函数工厂构建树

树由一个结构管理，该结构包含一个用于创建干净哈希实例的工厂——hash.Hash具有状态，因此传递一个函数：

type BinaryTree[T any] struct {
    newHash func() hash.Hash
}

func NewBinaryTree[T](newHash func() hash.Hash) *BinaryTree[T] {
    return &BinaryTree[T]{newHash: newHash}
}

// 用法
tree := NewBinaryTree[string](newHash)

构建过程：叶子哈希值，内部节点哈希子节点哈希值的连接。H(AB) = SHA256(H(A) + H(B))。根节点是整个树的最终哈希值。

默克尔证明：生成与验证

包含性证明是关键机制。客户端知道目标哈希（H(A)）和根哈希。服务器提供从叶子到根路径上的相邻哈希值。

生成算法

• 从根节点开始，下降到目标叶子。
• 在每一层，保存兄弟节点（左或右，不在路径上）的哈希值。
• 证明是这些哈希值的列表。

从下到上验证：

• 从H(A)开始。
• 依次与邻居哈希值进行哈希运算，交替左右侧。
• 到达根节点——匹配则确认包含性。

对于2^20个元素（一百万），证明是20个哈希值，每个32字节，约640字节。

优势与应用

• 对数复杂度：证明为O(log N)，适合SPV客户端。
• 最小流量：比特币SPV无需完整区块（500+ GB）即可验证交易。

应用：

• 比特币：区块头中的交易根。
• 以太坊：状态树、交易树、收据树。
• Git：提交中的树对象。
• IPFS：内容哈希作为分块的根。
• 证书透明度：审计SSL证书日志。

关键要点

• 默克尔树以O(log N)复杂度证明包含性，无需泄露其他数据。
• 在Go中使用泛型确保类型安全；CBOR用于任意值的确定性哈希。
• 哈希函数工厂防止hash.Hash状态导致的竞态条件。
• 证明从叶子到根路径上的兄弟哈希值生成。
• 适用于分布式系统：区块链、P2P存储。

— Editorial Team