比特币 - bips/bip-tap-ms-smt.mediawiki，位于Roasbeef/bips - Roasbeef

跳至内容

Roasbeef/ bips Public

forked from bitcoin/bips

• 通知 你必须登录才能更改通知设置
• Fork\ 23
• Star\ 64

折叠文件树

文件

bip-tap

在此仓库中搜索

/

bip-tap-ms-smt.mediawiki

复制路径

BlameMore 文件操作

BlameMore 文件操作

最近提交

guggero

和

Roasbeef

bip-tap-ms-smt: add ms-smt test vectors

2023年10月16日

5f0fbbd · 2023年10月16日

历史

历史

打开提交详情

查看此文件的提交历史。

323 行 (243 loc) · 11 KB

/

bip-tap-ms-smt.mediawiki

顶部

文件元数据和控制

• 预览

• 代码

• Blame

323 行 (243 loc) · 11 KB

Raw

复制原始文件

下载原始文件

轮廓

编辑和原始操作

 BIP: ???
  Layer: Applications
  Title: Merkle Sum Sparse Merkle Trees
  Author: Olaoluwa Osuntokun <laolu32@gmail.com>
  Comments-Summary: No comments yet.
  Comments-URI: https://git
  Status: Draft
  Type: Standards Track
  Created: 2021-12-10
  License: BSD-2-Clause

摘要

Permalink: 摘要

本文档描述了一种 Merkle Sum Sparse Merkle Tree (MS-SMT) 数据结构。 这是稀疏 Merkle 树的增强版本，其中包括 一个总和值，该值在内部分支哈希操作期间组合。 这种树允许有效的非包含证明，同时还支持 对无效 Merkle 总和承诺的有效故障证明。

版权

Permalink: 版权

本文档根据 2-clause BSD 许可证获得许可。

动机

Permalink: 动机

Taproot Assets 是一种 Taproot 原生资产覆盖协议。该协议没有将所有资产相关数据发布在链上的 OP_RETURN 输出中， 而是使用一系列锚定在 Taproot 脚本树中的承诺。 在处理唯一资产时，能够证明该资产的前任所有者（或卖方） 不再在其树中对其进行承诺非常重要。 此外，在进行多资产交换时，验证者需要能够 有效地验证是否没有创建新资产（通货膨胀检查）。 MS-SMT 支持非包含证明和非通货膨胀证明。

设计

Permalink: 设计

Merkle 总和树是在深度为 256 的 particia Merkle 树上模拟的 Merkalized 键值映射（因为我们使用 sha256 作为我们的哈希函数）。树的“基本” 状态是一棵具有 2^256 个叶子的 Merkle 树，存储着“空哈希”。 在此树中，可以提前计算每个级别的空叶和空内部节点的摘要。 空叶的“值”为零。

除了存储叶子/分支的哈希摘要之外，还沿着条目存储一个 8 字节的值， 使每个条目的长度为 40 字节。 因此，根哈希提交到叶子中所有条目的摘要，以及叶子集中所有“总和值”的总和。 当组合两个分支/叶子时，左叶子/分支和右叶子/分支的总和与节点的哈希摘要一起序列化。

当将新键插入树中时，在每个级别，键的第 i 位 用于向左或向右遍历树。由于这种遍历，每个 可能的键在叶子集中都有一个唯一的位置（位置方面）。 非包含证明是证明键的唯一位置处的值为空。

由于映射的性质，稀疏 Merkle 树是 历史 独立的 _意味着无论插入顺序如何，给定相同的键集_和值，始终会生成相同的根哈希。由于树的大小难以处理，因此使用一系列技术来维护内存中一组相关的分支和叶子，使用持久键值存储来存储树的相关唯一项。可以使用位图来压缩证明，以指示证明中的下一个节点是否是该级别的空哈希，或者是被证明的项目的父节点。

规范

Permalink: 规范

我们使用 sha256 作为我们的哈希函数，以及 8 字节的总和值。

构建空哈希映射

Permalink: 构建空哈希映射

所有级别的空哈希映射 empty_hashes 可以 提前预先计算，如下所示：

• 空叶的哈希值为 empty_hash_1 = sha256(nil, nil)
• 第二级空分支的哈希值为 empty_hash_2 = sha256(empty_hash_1, empty_hash_1)
• 等等...

我们将由此路径产生的映射 称为 empty_hash_map：

build_empty_hash_map() -> map[int][32]byte:

    empty_hash_map = make(map[int][32]byte)
    prior_level_hash = None
    for i in range(256):
        if prior_level_hash is None:
            prior_level_hash = sha256(nil, nil, 0)
            empty_hash_map[i] = prior_level_hash
            continue

        empty_hash_map[i] = sha256(prior_level_hash, prior_level_hash, 0)

    return empty_hash_map

=节点摘要计算

Permalink: =节点摘要计算

MS-SMT 树有两种类型的节点：叶节点和分支节点。

叶节点的摘要是叶节点的 sum_value （编码为大端整数）及其实际 value 的函数：

leaf_node_digest(leaf_node: MerkleSumLeaf) -> [32]byte:
    h = new_sha_writer()
    h.write_bytes(leaf_node.value)
    h.write_big_endian_int(leaf_node.sum_value)

    return h.bytes()

分支节点的摘要提交到其两个子节点的摘要（它们 可能是另一个分支或一个叶子），并且还提交到它们各自 sum_value 的 总和：

node_digest(node: Node) -> [32]byte
    match node:
        case MerkleSumLeaf:
            return leaf_node_digest(node)

        case MerkleSumBranch:
            return branch_node_digest(node)

branch_node_digest(left: Node, right: Node) -> [32]byte
    left_digest = node_digest(left)
    right_digest = node_digest(right)
    new_sum = left.sum_value() + right_sum_value()

    h = new_sha_writer()
    h.write_bytes(left_digest)
    h.write_bytes(right_digest)
    h.write_big_endian_int(new_sum)

    return h.bytes()

查找条目

Permalink: 查找条目

在树中查找条目需要基于 键本身的下一个位位置向下遍历树。 我们假设存在一个持久键值存储，该存储将节点的哈希映射到其子节点的左右摘要。

以下例程指定了查找算法：

lookup_item(key [32]byte, db KVStore) -> MerkleSumLeaf:

    root_hash, _ = db.fetch_root_hash()
    current_branch = root_hash

    value_hash, value_sum = None
    for i in range(256):
        if bit_index(i, key) == 0:
            current_branch, _ = db.get_children(current_branch)
        else:
            _, current_branch = db.get_children(current_branch)

    return MerkleSumLeaf(current_branch.hash, current_branch)

插入条目

Permalink: 插入条目

将条目插入树中需要遍历树，直到我们到达 叶子的位置，然后冒泡（哈希和求和）更改 一直到树。

insert_item(key [32]byte, value []byte, sum_value int64, db KVStore) -> None:
    root_hash, _ = db.fetch_root_hash()
    current_branch = root_hash

    insertion_path = []
    value_hash, value_sum = None
    for i in range(256):
        if bit_index(i, key) == 0:
            current_branch, sibling = db.get_children(current_branch)
            insertion_path.append(sibling)
        else:
            sibling, current_branch, = db.get_children(current_branch)
            insertion_path.append(sibling)

    db.insert(current_branch.parent_hash, MerkleSumLeaf(key, value, sum_value))

    for i in range(256):
       updated_sum = sum_value + inclusion_path[-1].value

       sibling_node = insertion_path[-1]
       if bit_index(i, key) == 0:
           updated_value = sha256(value, sibling_node.sum_value, updated_sum)

           db.insert(key=updated_value, value=(sibling_node, value))
        else:
           updated_value = sha256(insertion_path[-1].hash, value, updated_sum)

           db.insert(key=updated_value, value=(value, sibling_node))

       value = updated_value
       sum_value = updated_sum

       insertion_path.pop()

    return None

删除条目

Permalink: 删除条目

删除条目与插入相同，但是我们通过将其值设置为 空哈希来删除树中的条目。

delete_item(key [32]byte, db KVStore) -> None:
    return insert_item(key, nil, 0, db)

创建包含 & 非包含证明

Permalink: 创建包含 & 非包含证明

条目的包含证明证明该条目在树中找到，并且 具有一定的总和值。 非包含树证明相反：该条目未在树中找到。

生成包含或非包含证明需要向下遍历树 并获取所有兄弟哈希及其总和值：

gen_merkle_proof(key [32]byte, db KVStore) -> []MerkleSumNode
    root_hash, _ = db.fetch_root_hash()
    current_branch = root_hash

    proof_nodes = []
    value_hash, value_sum = None
    for i in range(256):
        if bit_index(i, key) == 0:
            current_branch, sibling = db.get_children(current_branch)
            proof_nodes.append(sibling)
        else:
            sibling, current_branch, = db.get_children(current_branch)
            proof_nodes.append(sibling)

    return proof_nodes

普通的证明始终是一系列 256 个 Merkle 总和元素。 但是，我们可以通过使用额外的位图来压缩证明，该位图指示证明内容是否是空哈希。

compress_merkle_proof(proof []MerkleSumNode) -> CompressedProof:
   compressed_proof = new_compressed_proof(
       compression_bits=new_bit_vector(256),
       proof=[]MerkleSumNode{},
   )

   for i, proof_node in proof:
       if proof_node == empty_hash_map[i]:
           compressed_proof.compression_bits.append(1)
        else:
           compressed_proof.proof.append(proof_node)

   return compressed_proof

验证包含 & 非包含证明

Permalink: 验证包含 & 非包含证明

为了验证证明，我们需要确认如果从证明开始， 如果我们对树进行哈希和求和，那么我们将最终得到相同的根哈希和总和值。

在验证证明之前，应首先解压缩证明：

decompress_merkle_proof(compressed_proof CompressedProof) -> []MerkleSumNode:
    proof = []MerkleSumNode{}

    for i in range(256):
        if compressed_proof.bit_at(index=i) == 1:
            proof.append(empty_hash_map[i])
        else:
            proof.append(compressed_proof.proof)
            compressed_proof = drop_1(compressed_proof.proof)

    return proof

解压缩证明后，我们通过对每个级别进行哈希和求和来验证证明。

verify_merkle_proof(proof []MerkleSumNode, root MerkleSumNode,
    key [32]byte, value []byte, value_sum int64) -> bool:

    for i in range(256):
        if bit_index(i, key) == 0:
            value = sha256(proof[-1-i], value, proof[1-i].sum, value_sum)
        else:
            value = sha256(value, proof[-1-i], value.sum, value_sum)

    return root.hash == value && root.sum == value_sum

缓存优化

Permalink: 缓存优化

TODO(roasbeef):

测试向量

Permalink: 测试向量

可以在此处找到 Merkle Sum Sparse Merkle Trees 的测试向量：

• MS-SMT 叶删除测试向量
• 树错误测试向量
• MS-SMT 证明测试向量
• MS-SMT 叶替换测试向量

测试向量由 Taproot Assets GitHub 仓库中的单元测试自动生成。

向后兼容性

Permalink: 向后兼容性

参考实现

Permalink: 参考实现

github.com/lightninglabs/taproot-assets/tree/main/mssmt

• 原文链接： github.com/Roasbeef/bips...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～