ERC-7585 MixHash and proof of storage for public data (MixHash and Public Data Storage Proofs)
Draft · Other · created 2023-12-27
Defines MixHash, a 256-bit identifier that summarizes a file as a Merkle tree while also encoding its size, and presents a storage proof scheme by which the public network can prove that a copy of that file is actually being held.
Why it is needed
ERC-721 and ERC-1155 are widely used for NFTs, but they have no mechanism to confirm that the public data a token points to actually exists and is being stored. Without a way to verify on-chain who holds a copy of a given file, it is hard to build applications such as decentralized data markets, decentralized data storage, and decentralized data oracles. This proposal identifies public data with MixHash, a 256-bit hash that can be dropped directly into the slot normally occupied by the widely used Keccak256 or SHA256, and lets anyone submit proof that they hold a copy of the data using a value derived from a block at a specific point in time. Rather than having the network directly verify whether a proof is optimal, false proofs are filtered out through an economic game in which other participants holding the same data can challenge with a better proof. This raises the probability that copies of public data remain widely distributed without requiring expensive zero-knowledge proofs.
What to implement
function getPublicDataOwner(bytes32 mixHash) external view returns (address);: Returns the owner address if the queried MixHash is public data known to this contract, otherwise returns 0x0.function tokenIdIsMixHash() external view returns (bool);: Returns whether the tokenId of this NFT contract is itself the MixHash.function tokenDataHash(uint256 _tokenId) external view returns (bytes32);: Returns the MixHash corresponding to the specified NFT, or 0x0 if there is none.
In depth
The bit structure of MixHash
MixHash is 256 bits. The upper 2 bits select the hash algorithm, where 0b00 is SHA256 and 0b10 is Keccak256, while 0b01 and 0b11 are reserved. The next 62 bits hold the file size, supporting up to 2^62-1 bytes. The lower 192 bits are the lower 192 bits of the Merkle root node value produced with the specified hash algorithm. A file must be split into 1KB chunks, with the final chunk zero-padded. The lower 128 bits of each chunk's hash become a leaf of the Merkle tree, and non-root intermediate nodes also use only the lower 128 bits of the 256-bit hash result. Because the total length is 256 bits, it can be dropped into the existing Keccak256 or SHA256 slot at no extra cost, and while encoding length in the upper 62 bits sacrifices some security, the proposal explains that a 192-bit hash is sufficient to resist collisions.
Minimum-value storage proof selection and on-chain verification
The supplier appends a nonce derived from block height h (typically the block hash) to the end of each chunk, finds the leaf m that produces the smallest new Merkle root, and submits the extracted path m_path and leaf value m_leaf_data. The on-chain verification function verifyDataProof rejects the proof as expired if the difference between the current block and h exceeds MAX_BLOCK_DISTANCE, and checks whether the lower 192 bits of the root reconstructed from the path match the MixHash. It then computes proof_result with the nonce appended, and if the result is smaller than the existing one, it emits a ProofPunish event flagging the previous submitter for a penalty and updates the result. The network cannot directly verify the optimality of a proof and instead relies on challenges from other suppliers who know of a better proof. To reduce proof size, hashes of non-root nodes are truncated to their lower 128 bits, compressing the Merkle tree hashes to half size.
Defending against external data source attacks
Two mechanisms prevent sourcing attacks, in which data is not stored locally but instead fetched over the network at the moment a proof is generated. First, a time limit. In an Ethereum-like network with a block time of about 15 seconds, setting MAX_BLOCK_DISTANCE = 2 means a proof must be generated and submitted within 30 seconds, which most external sources cannot complete a transfer within. Second, an economic game. Under a model that rewards the supplier who first submits a correct proof, the delay from an external source lowers the probability of success, making it less profitable than local storage. The defense success rate is defined as R = (TNetwork - TLocal) / AvgProofTime, and the success rate decreases as AvgProofTime grows.
Optional proof-of-work reinforcement and its cost
In environments like the BTC network, where two blocks take about 20 minutes and AvgProofTime is large, sourcing attacks become easier to succeed. In this case, a dynamically adjusted proof of work (PoW) can be added, changing the formula to R = (TNetwork - TLocal) / (AvgProofTime - AvgPoWTime). The implementation appends a nonce along with a self-generated noise value to the end of each chunk, minimizing the Merkle root while making the last x bits of proof_result_m zero according to the PoW difficulty requirement, and the example code uses POW_DIFFICULTY = 16. Within the valid time window, the proof with more PoW computation wins. However, since this raises the cost of generating a proof and can favor suppliers with dedicated hardware in a way that undermines the participation structure and reduces broad distribution of the data, it is recommended not to enable this unless truly necessary.
Limitations: small files and verifying publicness
Two limitations are stated explicitly. First, this is not suitable for very small files, since sourcing attacks are inherently hard to prevent for small files. Second, the storage proof does not address whether the data is actually public. Therefore the publicness of a MixHash must be verified separately for a given scenario, which the proposal acknowledges is not an easy task. If storage proofs for any arbitrary MixHash were rewarded, suppliers could fabricate data that only they hold to collect rewards, an attack that could ultimately collapse the entire ecosystem.
ERC-721 and ERC-1155 extension interfaces
Two interfaces are proposed to confirm whether a MixHash is public data and to track its value within the existing Ethereum ecosystem. Contracts handling unstructured data can implement ERCPublicDataOwner, where getPublicDataOwner(bytes32 mixHash) returns the owner address if the given MixHash is public data associated with that contract, or 0x0 otherwise. For the NFT ecosystem, an optional extension, ERC721MixHashVerfiy, is proposed for new ERC-721 and ERC-1155 contracts. tokenIdIsMixHash() indicates whether the tokenId itself is the MixHash, and tokenDataHash(uint256 _tokenId) returns the MixHash corresponding to that NFT. Both interfaces are meant to use ERC-165 identifiers, but the source text leaves the numbers as placeholders.
Design rationale: Nash equilibrium and non-defense against Sybil attacks
Unlike zero-knowledge proof based replication proofs, this design is based on 'Nash Consensus.' Rather than verifying the optimality of proofs on-chain, it relies on an economic game to significantly lower construction and verification costs, and since worthless data also has no game value, it naturally gets weeded out, so permanent storage is not guaranteed. Proof of storage can be implemented with smart contracts alone, separate from the economic model (the current reference implementation's gas cost is somewhat high). Also, for public data, it does not strictly prevent Sybil attacks where one provider pretends to store multiple copies under multiple identities, because the goal is not to count copies exactly but to raise the probability that copies exist. Thanks to HashType, it is compatible with both EVM-family and BTC-family chains; the default HashType is SHA256, and MixHash is seen as a potential value anchor across chains.
A proposal still in Draft status
This proposal was created in December 2023 and is in Draft status. The content may change or progress may stall, so it is advisable to check the latest original text and discussion threads before implementation.
Things to watch out for
- Do not use for private data: During the proof of storage process, 1KB chunks of data are frequently sent to the public network. Therefore, the storage proof design in this document should not be used for private data.
- Private file proofs require a separate design: The MixHash design itself can also support proof of storage for private files, but it requires adjustments to how the original data is handled and how proofs are constructed, and that design is outside the scope of this document.