⚠️ Draft Standards Track: ERC

ERC-7585: MixHash 和公共数据存储证明

一种在 Merkle 树上进行最小值选择的存储证明设计

Authors	Liu Zhicong (@waterflier), William Entriken (@fulldecent), Wei Qiushi (@weiqiushi), Si Changjun (@photosssa)
Created	2023-12-27
Discussion Link	https://ethereum-magicians.org/t/erc-7585-mixhash-and-public-data-storage-proofs/17707
Requires	EIP-165, EIP-721, EIP-1155

摘要
动机
规范
理由
向后兼容性
测试用例
参考实现
安全考虑
版权

摘要

本提案介绍了一种在 Merkle 树上进行“最小值选择”存储证明的设计。该设计包含两个主要组成部分：

一种名为 MixHash 的哈希算法，旨在取代常用的 Keccak256 和 SHA256 算法。
公共数据存储证明。这使得任何人都可以向公共网络提交证明，验证他们拥有 MixHash 标记的特定公共数据的副本。

此外，该提案讨论了此设计在各种场景中的实际实现，并提出了一些对 ERC-721 和 ERC-1155 标准的改进建议。

动机

ERC-721 和 ERC-1155 标准广泛应用于 NFT 领域。然而，当前的标准没有提供验证公共数据存在的机制。这是许多应用程序（如去中心化数据市场、去中心化数据存储和去中心化数据预言机）开发的主要障碍。

规范

本文档中关键词“必须 (MUST)”，“禁止 (MUST NOT)”，“需要 (REQUIRED)”，“应该 (SHALL)”，“不应该 (SHALL NOT)”，“推荐 (SHOULD)”，“不推荐 (SHOULD NOT)”，“可以 (MAY)”和“可选 (OPTIONAL)”按照 RFC 2119 和 RFC 8174 中的描述进行解释。

MixHash

MixHash 是一种包含数据长度信息的 Merkle 树根哈希值。其结构如下：

     +-----------256 bits MixHash-----------+
High |-2-|----62----|----------192----------| Low

2   bits: 哈希算法选择，其中 0b00 表示 SHA256，0b10 表示 Keccak256。(0b01, 0b11 保留)
62  bits: 文件大小。因此，MixHash 可以支持高达 2^62-1 的文件大小。
192 bits: 指定哈希算法构建的 Merkel 根节点值的低 192 位。

给定一个文件，我们可以通过以下定义的步骤构建 MixHash：

文件必须 (MUST) 分割成 1KB 的块。如果需要，必须 (MUST) 在最后一个块的末尾填充零。
计算每个块的哈希值，低 128 位是 Merkle 树叶子节点值。
构建 Merkle 树，根节点哈希算法为 256 位，其他节点使用 256 位哈希结果的低 128 位。
返回哈希类型、文件大小和 Merkle 树根节点哈希的低 192 位的组合。

MixHash 保留 256 位的长度，因此用 MixHash 替换广泛使用的 Keccak256 和 SHA256 不会产生额外的成本。虽然将文件长度包含在较高的 62 位中在一定程度上损害了安全性，但 192 位的哈希长度已经足以防御哈希冲突。

以下是生成 Mixhash 的伪代码：

def generateMixHash(blockHeight,hashType,file):
    chunk_hash_array = []
    for chunk in file:
        if len(chunk) < 1024:
            chunk = chunk + b'\x00' * (1024-len(chunk))
        chunk_hash_array.append(getChunkHash(chunk,hashType))
    merkle_tree_root = getMerkleTreeRoot(chunk_hash_array,hash_type)
    return mix_hash(hash_type, len(file), merkle_tree_root)

公共数据存储证明

当 MixHash 用于标识一段公共数据时，任何人都可以构建存储证明来证明自己拥有该数据的副本。以下是使用公共数据存储证明的典型过程：

有资格提交存储证明以获取奖励的用户称为供应商 (Suppliers)。
供应商根据高度为 h 的区块准备数据 D（MixHash 为 mix_hash_d）的存储证明。用于证明的 256 位 nonce 值从此块派生（通常直接使用块的哈希值）。
为了生成正确的存储证明，供应商需要遍历 D 的每个 1KB 块，以找到最佳叶子节点 m。这是通过尝试将 nonce 值附加到每个块的末尾以最小化新的 Merkle 树根哈希来完成的。确定 m 后，提取 m 的路径 m_path 和叶子节点值 m_leaf_data。
供应商使用 {mix_hash_d, h, m, m_path, m_leaf_data} 构建数据 D 在区块时间为 h 时的存储证明，并将其提交到公共网络。
公共网络可以根据 mix_hash_d 验证 m、m_path 和 m_leaf_data 的正确性：验证 m 确实是 D 的一个块。证明的及时性可以通过 h 来验证。通过正确性和及时性检查后，公共网络根据 nonce 值和现有证明信息计算 proof_result_m，并保存它。
公共网络没有足够的信息来验证证明的最优性，但是拥有完整数据集的其他供应商可以提交更好的 {mix_hash_d, h, better_m, better_m_path, better_m_leaf_data} 来挑战发布的存储证明。
公共网络可以通过比较 proof_result_m 和 proof_result_better_m 来确定挑战是否成功。成功的挑战表明旧的存储证明是伪造的。如果在一定的时间范围内没有人挑战发布的存储证明，则可以从博弈论的角度认为它是正确的。
为了支持健康的竞争，公共网络应该设计一个适当的经济模型，奖励提供正确存储证明的用户，并惩罚提交虚假证明的用户。

在了解上述过程后，让我们使用 Pseudocode 更精确地描述存储证明的生成和验证。

# generate proof off chain
# 链下生成证明
def generateProof(mixHash, blockHeight,file) 
    nonce = getNonce(blockHeight)
    hash_type = getHashType(mixHash)
    chunk_hash_array = buildChunkHashArray(file,hash_type)

    min_index = 0
    min_merkle_tree_root = MAX_UINT256
    min_chunk = None

    m_index = 0
    for chunk in file:
      new_chunk = chunk + nonce
      chunk_hash_array[m_index] = getChunkHash(new_chunk,hash_type)
      merkle_tree_root = getMerkleTreeRoot(chunk_hash_array,hash_type)
      chunk_hash_array[m_index] = getChunkHash(chunk,hash_type)
      if (merkle_tree_root < min_merkle_tree_root):
        min_merkle_tree_root = merkle_tree_root
        min_index = m_index
        min_chunk = chunk
      m_index = m_index + 1

// verify on chain
// 在链上验证
function verifyDataProof(mixHash, blockHeight, m_index, m_path, m_leaf_data) {
    if(current_block_height - blockHeight > MAX_BLOCK_DISTANCE) {
       revert("proof expired");
    }
    hash_type = getHashType(mixHash);
    merkle_tree_root = getMerkleTreeRootFromPath(m_path,m_leaf_data,hash_type);
    if(low192(merkle_tree_root) != low192(mixHash)) {
       revert("invalid proof");
    }

    nonce = getNonce(blockHeight);
    proof_result = getMerkleTreeRootFromPath(m_path,m_leaf_data.append(nonce),hash_type);
    last_proof_result,last_prover = getProofResult(mixHash, blockHeight);
    if(proof_result < last_proof_result) {
      emit ProofPunish(last_prover);
      updateProofResult(mixHash, blockHeight, proof_result, msg.sender);
    } 
}

为了尽可能地减小存储证明的大小，我们优化了 getMerkleTreeRoot 的实现：除了 RootHash 之外，其他节点的哈希值都截断为较低的 128 位。这种方法有效地将完整 Merkle 树的哈希值压缩到其大小的一半。完整的实现细节可以在后续的参考实现部分找到。

防御数据源攻击

从上面描述的过程中可以看出，构建公共数据存储证明的核心是基于在特定时刻生成的公共、非重复的 nonce 值。它需要在指定的时间内遍历文件的全部内容才能构建正确的证明。如果没有限制，此过程很容易受到外部数据源攻击：供应商不将数据存储在本地，而是在构建存储证明时通过网络请求获取数据。我们的设计如何防止此类攻击？

时间限制响应：供应商必须在指定的时间内提交存储证明。在像以太坊这样的典型公共网络上，区块时间约为 15 秒。典型的最大区块间隔可能是 2 (MAX_BLOCK_DISTANCE = 2)，这意味着供应商必须在 30 秒内完成存储证明的构建和提交。这种持续时间不足以让大多数数据源完成传输，因此供应商必须在本地存储数据才能有机会在分配的时间内构建存储证明。
经济博弈论：基于公共数据存储证明的经济模型通常会奖励第一个提交正确存储证明的供应商。这意味着，从博弈论的角度来看，使用外部数据源构建存储证明的固有延迟会降低成功提交的可能性。从经济上讲，它不如在本地存储数据所产生的预期收益更有利可图。经济模型激励供应商在本地存储数据。

防御数据源攻击的成功率

使用结合区块间隔限制和优先提交的策略通常可以有效地防御外部数据源攻击。这种方法的有效性主要取决于从本地存储读取文件和从网络检索文件之间的速度差异。我们可以使用以下公式定义防御外部数据源攻击的成功率 R：

R = (TNetwork - TLocal) / AvgProofTime

AvgProofTime 越大，防御数据源攻击的成功率就越低。目前，影响 AvgProofTime 的最重要因素是链上交易的平均时间。例如，在 BTC 网络中，2 个区块的时间约为 20 分钟。由于 AvgProofTime 如此之大，成功率 R 迅速下降，使得数据源攻击更有可能成功。我们可以引入动态可调的 PoW (Proof of Work) 机制来进一步防御数据源攻击。此修改修改公式如下：

R = (TNetwork - TLocal) / (AvgProofTime-AvgPoWTime)

随着 PoW (Proof of Work) 概念的引入，提交存储证明的策略变为：在指定时间内构建和提交存储证明，同时努力完成尽可能多的 PoW 计算。在有效的证明时间窗口中，具有更多 PoW 计算量的存储证明占优势。这种机制可以有效地防御外部数据源攻击，尤其是在 AvgProofTime 较大时。

将 PoW 机制集成到公共数据存储证明的设计中并不复杂。一个简单的实现可以将第二步修改为：

2. 为了生成正确的存储证明，供应商需要遍历 D 的所有 1KB 块以找到最佳叶子节点 `m`。 该方法涉及尝试将 nonce 和自构建的噪声值附加到每个块的末尾，以最小化新的 Merkle 树根哈希，并根据 PoW 难度要求，确保构建的 `proof_result_m` 的最后 x 位为零。 确定 `m` 和噪声后，提取 `m` 的路径 `m_path` 和叶子节点值 `m_leaf_data`。

根据上述修改调整的 Pseudocode 如下：

# generate proof with PoW off chain
# 使用 PoW 链下生成证明
POW_DIFFICULTY = 16
def generateProofWithPow(mixHash, blockHeight,file) 
  nonce = getNonce(blockHeight)
  hash_type = getHashType(mixHash)
  chunk_hash_array = buildChunkHashArray(file,hash_type)

  min_index = 0
  min_merkle_tree_root = MAX_UINT256
  min_chunk = None

  m_index = 0
  noise = 0
  while True:
    for chunk in file:
      new_chunk = chunk + nonce + noise
      chunk_hash_array[m_index] = getChunkHash(new_chunk,hash_type)
      merkle_tree_root = getMerkleTreeRoot(chunk_hash_array,hash_type)
      chunk_hash_array[m_index] = getChunkHash(chunk,hash_type)
      if (merkle_tree_root < min_merkle_tree_root):
        min_merkle_tree_root = merkle_tree_root
        min_index = m_index
        min_chunk = chunk
      m_index = m_index + 1
    if(last_zero_bits(min_merkle_tree_root) >= POW_DIFFICULTY):
      break
    noise = noise + 1
    
  m_path = getMerkleTreePath(chunk_hash_array, min_index)
  return storage_proof(mixHash, blockHeight, min_index, m_path, min_chunk,noise) 

应用这种机制会增加生成存储证明的成本，这偏离了我们最初减少公共数据广泛有效存储的意图。此外，严重依赖基于 PoW 的经济模型可能会让在 PoW 方面具有显著优势的供应商（通过专用硬件）扰乱游戏的基本参与性质，从而减少公共数据的广泛分布。因此，建议除非绝对必要，否则不要启用 PoW 机制。

局限性

本文讨论的存储证明不适合存储非常小的文件，因为小型文件本身难以防御外部数据源攻击。
公共数据存储证明不能解决数据是否真正公开的问题。因此，在特定场景中验证 MixHash 的公共性质非常重要（这通常并不容易）。允许供应商提交任何 MixHash 的存储证明并获得奖励会导致这样一种情况：供应商创建只有他们拥有的数据，并利用它通过构建的攻击来获得奖励，最终导致整个生态系统的崩溃。

ERC 扩展建议：通过 MixHash 跟踪高价值公共数据

我们可以使用现有的以太坊生态系统来确认 MixHash 是否为公共数据并跟踪其价值。对于任何与非结构化数据相关的合约，都可以实现 ERCPublicDataOwner 接口。此接口确定特定 MixHash 是否与当前合约关联，并尝试返回与 MixHash 对应的所有者地址。此外，对于现有且被广泛认可的 NFT 生态系统，我们建议新的 ERC-721 和 ERC-1155 合约实现一个新的扩展接口 ERC721MixHashVerify。此接口可以显式地将 NFT 与 MixHash 相关联。具体接口定义如下：

/// @title ERCPublicDataOwner Standard, query Owner of the specified MixHash
//  @title ERCPublicDataOwner 标准，查询指定 MixHash 的所有者
///  Note: the ERC-165 identifier for this interface is <ERC-Number>.
//  注意：此接口的 ERC-165 标识符是 <ERC-Number>。
interface ERCPublicDataOwner {
    /**
        @notice Queries Owner of public data determined by Mixhash
        // @notice 查询由 Mixhash 确定的公共数据的所有者
        @param  mixHash    Mixhash you want to query
        // @param 您要查询的 mixHash
        @return            If it is an identified public data, return the Owner address, otherwise 0x0 will be returned
        // @return 如果它是已识别的公共数据，则返回所有者地址，否则将返回 0x0
    */
    function getPublicDataOwner(bytes32 mixHash) external view returns (address);
}

ERC721MixHashVerfiy 扩展对于 ERC-721 智能合约或 ERC-1155 智能合约是可选的 (OPTIONAL)。此扩展可以帮助建立指定的 NFT 和 MixHash 之间的关系。

/// @title ERC721MixHashVerfiy Extension, optional extension
//  @title ERC721MixHashVerfiy 扩展，可选扩展
///  Note: the ERC-165 identifier for this interface is <ERC-Number>.
//  注意：此接口的 ERC-165 标识符是 <ERC-Number>。
interface ERC721MixHashVerfiy{
    /**
        @notice Is the tokenId of the NFT is the Mixhash?
        // @notice NFT 的 tokenId 是否为 Mixhash？
        @return           True if the tokenId is MixHash, false if not
        // @return 如果 tokenId 是 MixHash，则为 True，否则为 False
    */
    function tokenIdIsMixHash() external view returns (bool); 
    
    /**
        @notice Queries NFT's MixHash
        // @notice 查询 NFT 的 MixHash
        @param  _tokenId  NFT to be querying
        // @param 要查询的 NFT
        @return           The target NFT corresponds to MixHash, if it is not Mixhash, it returns 0x0
        // @return 目标 NFT 对应于 MixHash，如果不是 Mixhash，则返回 0x0
    */
    function tokenDataHash(uint256 _tokenId) external view returns (bytes32);
}

理由

长期以来，存储证明（通常称为时空证明）一直是人们感兴趣的主题，并且存在许多实现和相关项目。

与基于零知识证明的现有副本证明相比，我们的存储证明基于“纳什共识”，其核心原则是： a. 公共网络（链上）无法验证证明的最优性，但依赖于经济博弈论。这大大降低了构建和验证的成本。 b. 没有价值的数据通常缺乏博弈价值，并且自然地从系统中消除。没有对难以捉摸的永久存储的承诺。
它可以完全通过智能合约实现（尽管当前参考实现的 GAS 成本有点高），从而将存储证明与经济模型分开。
对于公共数据，我们不严格防御女巫攻击。女巫攻击是指供应商使用多个身份来承诺存储数据 D 的多个副本（例如，n 个副本），而实际上存储的副本较少（例如只有一个副本），但提供 n 个存储证明，从而成功进行攻击。严格防止女巫攻击实际上意味着对数据存储附加更多的额外成本。我们的存储证明的核心是通过存储证明和不同的经济模型的结合来增加公共数据副本存在的可能性，而不是需要严格定义存在多少个副本。因此，从公共数据存储证明的设计角度来看，我们不需要防御女巫攻击。

向后兼容性

使用 HashType 允许存储证明与 EVM 兼容的公共区块链系统以及类 BTC 公共区块链系统兼容。实际上，MixHash 可以成为一种新的跨链价值锚定：它可以跟踪由 MixHash 表示的相同数据在不同公共区块链网络上的价值（使用不同的模型），从而实现跨链价值的聚合。考虑到向后兼容性的需要，我们将 MixHash 的默认 HashType 设置为 SHA256。还有两类 HashType 尚未使用，为未来扩展留下了充足的空间。

测试用例

PublicDataProofDemo 包含使用 Hardhat 编写的测试用例。

参考实现

PublicDataProof Demo

一个标准的参考实现

DMC 公共数据铭文

基于公共数据存储认证，在 ETH 网络和 BTC 铭文网络上设计了一个完整的经济模型和游戏玩法

了解更多背景和现有尝试

DMC 主链
CYFS

安全考虑

此存储证明围绕公共数据展开。在演示存储证明时，通常涉及将数据的 1KB 段发送到公共网络。因此，请不要将本文提出的存储证明设计用于私有数据。

MixHash 的设计可以支持私有文件的存储证明，但这需要在原始数据的处理和存储证明的构建中进行一些调整。关于私有文件存储证明设计的详细讨论超出了本文的范围。实际上，参考实现部分中提到的一些项目同时使用了公共数据存储证明和私有数据存储证明。

版权

在 CC0 下放弃版权及相关权利。

Citation

Please cite this document as:

Liu Zhicong (@waterflier), William Entriken (@fulldecent), Wei Qiushi (@weiqiushi), Si Changjun (@photosssa), "ERC-7585: MixHash 和公共数据存储证明 [DRAFT]," Ethereum Improvement Proposals, no. 7585, December 2023. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-7585.