Blockchain Interoperability (Part 2): Storage Proof — Powering New Cross-Chain Use Cases

In our previous post, which would be actionable, we discussed the role of consensus proof of this emerging method of trust minimization in facilitating the bridge between blockchains.

In this article, we’ll explore proof of storage, which takes the concept of trust minimization verification and extends it to transactions in older historical blocks. The ability to verify past transactions and user activity in this way unlocks a large number of cross-chain use cases.

In our previous post, we introduced Proof of Consensus — a trust-minimising approach to bridging funds across blockchains. Since bridge users usually want to see transactions happen immediately at the most recent moment, consensus proving is very useful because they constantly check the latest state of the blockchain as it operates.

This concept of trust minimization bridging can also be applied in another direction, which is going back to the past and using zero-knowledge proofs to verify transactions and data in old blocks. These “historical storage proofs” support a diverse range of cross-chain use cases, and in this article we’ll cover these use cases, how they work, and the actors built in this space.

Retrieve historical data

There are many uses for historical blockchain data. It can be used to prove asset ownership, user behavior, and transaction history, and then input these into on-chain smart contracts or applications. At the time of writing, more than 18 million blocks have been written to Ethereum. Smart contracts can only access the most recent 256 blocks (or data within the last 30 minutes), so “historical data” refers to anything other than the last 256 blocks.

Today, in order to access historical data, protocols often query archive node providers, i.e. third parties such as Infura, Alchemy, or other indexers. That means trusting and relying on them and their data.

Historical data

This data can, however, be relaxed in a more trust-minimized fashion, through the use of storage proofs.

Historical data

However, this data can be retrieved in a more trust-minimized manner by using storage proofs.

Proof of storage is a zero-knowledge proof that allows the verification of historical data stored on the blockchain. More specifically, proof of storage can be used to prove the existence of a specific state in a particular block in the past. This approach doesn’t require trust in third parties or oracles; instead, its trust is built into the storage proof.

How can storage proofs help verify that some data exists in older historical blocks? This requires verifying two things:

• The first step is to check whether a specific block is part of the blockchain’s regulatory history, that is, the block is a valid part of the history of the source chain
• The second step is to check whether specific data is part of the block, that is, a piece of information (such as a specific transaction) is part of the block (this can be proven by Merkle including proof)

After receiving and verifying the proof, the recipient (such as a smart contract on the target chain) believes in the validity of the data and can execute the corresponding set of instructions. The concept can be extended even further: additional off-chain computations can be run with validated data, then another zero-knowledge proof is generated to prove the data and computation.

Simply put, proof of storage supports retrieval of data on the historical chain in a way that minimizes trust. This is important because, as we outlined in our first post, we’re seeing web3 become a more multi-chain and multi-tiered space over the next few years. The emergence of multiple layer 1 protocols, rollups, and application chains means that users’ on-chain activity may be scattered across multiple chains. This further emphasizes the need for trust-minimising interoperability solutions that maintain the composability of user assets, identities, and transaction history across multiple domains. This is a problem that proof of storage can help solve.

What are the use cases for proof of storage?

Proof of storage allows smart contracts to check any historical transactions or data as a prerequisite. This makes cross-chain app design more flexible.

First, storing proofs can prove any historical data on the source blockchain, such as

1. Account balance and token ownership
2. User trading activity or static state
3. The historical price of an asset transaction over a specified time period
4. Cross-chain liquidity pool real-time asset balance

Proof can then be sent to the target chain to unlock the range of cross-chain use cases:

1. Enables users to vote on governance proposals on lower cost layer 2 agreements
2. Allowing NFT holders to receive new NFT mints or community benefits on a new chain
3. Reward users based on their history and interactions with specific dApps (e.g. through airdrops)
4. Loans that offer custom interest rates based on the user’s overall transaction and credit history
5. Trigger account recovery for dormant accounts
6. Calculating the history of futures swaps TWAP
7. Calculate more accurate AMM swap prices based on multi-chain liquidity pools

Essentially, storage proofs allow apps to query and port users’ on-chain activity and history across multiple chains for input into a smart contract or application on another chain.

Storage proof use cases

Let’s take a detailed example to understand how storage proof works.

How Storage Proof Works: Detailed Examples

Assume “X,” which is a DeFi protocol with tokens on Ethereum. A governance proposal is about to be put forward, and they want to promote on-chain voting on lower cost target chains. Users can only vote if they hold X tokens on Ethereum at a specific point in time (we call it a “snapshot”), such as block #17 ,000,000

How is voting currently done on the chain?

The current approach is to query the archive node to get the full list of eligible token holders at block #17 ,000,000. The DAO administrator then stores that list in a smart contract on the target chain to determine who can vote. There are a few limitations to this approach:

1. The list of voters can be very long, and every snapshot changes, making it expensive to store and update each voting proposal on-chain;
2. There is an implicit trust in the archive node provider and the data it provides;
3. The members managing the DAO must be trusted not to tamper with the voter list

How does proof of storage solve this problem?

As we explained in article 2, expensive calculations can be transferred to zero-knowledge proofs off-chain.

The zk attestor will generate a concise proof and send it to the target chain for verification. For the above DAO voter eligibility examples, the following are:

1. The attestor generates a zero-knowledge proof that block #17 ,000,000 is part of Ethereum’s history (as in the first step* above).
2. After proving the validity of the block, we can use Merkle to include proof that the user held DAO tokens when the block was finalized (as in step 2 above*)

Verify historical data to enable cross-chain voting

The proof is then sent to a smart contract on the target chain for verification. If the verification is successful, then the smart contract on the layer 2 protocol allows users to vote.

This approach solved a few issues. It doesn’t require:

Trust the archive node provider;

1. let the agreement maintain expensive on-chain voter lists;
2. For users to transfer assets to the chain of purpose

What settings are required for proof of storage?

So far, we’ve abstracted some of the intricacies of storage proofs. However, using them also requires careful initial setup by the service provider to ensure they can be used without trusting the provider. Two things are generated and stored on-chain during this process:

1. Full chain zero-knowledge proof (“zk promise”): The service provider groups all historical blocks on the source chain into continuous fixed-size “blocks” (using Merkle trees) and generates zero-knowledge proofs for each block, which are used to verify the groupings. These proofs are then recursively combined until a final zero-knowledge proof is obtained, a “zk promise” to the entire chain. This proves that the provider has correctly indexed the entire history of the chain.

The “zk promise” explains the entire history of Ethereum

• **Merkle Mountain Range: ** The provider also stores the Keccak Merkle roots of the source chain’s block hashes (blocks) grouped together in an on-chain data structure called Merkle Mountain Range (MMR). This data structure is used because it is easy to query and update, and allows providers to effectively prove that a given block exists in the chain’s history. MMR is created using a Keccak256 hash, Poseidon hash, or both. Poseidon hashes are more zero-knowledge friendly and support computation of historical data. The validity of the data and computation can later be proven through zero-knowledge.

Merkel Mountain Range (MMR) illustration

As new blocks are added to the source chain, service providers regularly (such as hourly or daily) update the “zk commitment” and MMR to keep up with the pace of the chain. This is done so that the past block is always linked to one of the 256 blocks currently accessible from EVM. This ensures that the historical data is linked to one of the blocks currently available on Ethereum.

In the image below, we’ve detailed how to complete the setup:

In summary, the following shows how to use proof of storage once the setup is complete in the context of the DAO voting example we covered earlier:

1. Service providers create and store “zk promises” for the entire chain (i.e. Ethereum history) and MMR on the target chain
2. The provider allows applications to query historical data on-chain or off-chain through an API
3. A voting dApp on the goal chain sends a query to the provider’s smart contract to find out if the user holds DAO tokens on block #17 ,000,000 on Ethereum

The provider will check two things:

1. The queried block is part of Ethereum’s regulatory history (first step above); the provider then generates zero-knowledge proof of the block’s content via Merkle Mountain Range
2. The user holds DAO tokens in block #17 ,000,000 (step 2 above); the provider then generates another zero-knowledge proof that the user holds DAO tokens within the block
3. The provider aggregates the proof generated above into a zero-knowledge proof
4. The aggregated ZK proof is then sent back to the voting dApp smart contract on the target chain to verify the ZK proof and allow the user to vote once the verification is successful.

Team building in this field

Some participants are constructing smart contracts that allow smart contracts to access data on historical chains in a way that minimizes trust.

Currently, Axiom is running on Ethereum and is committed to providing smart contracts on Ethereum and accessing historical Ethereum data through zk-based storage proofs. The team is also enhancing off-chain computational capabilities based on historical data and using zero knowledge to prove the accuracy of these data and calculations.

Relic Protocol provides a technical approach similar to Axiom, and the protocol runs on Ethereum and zkSync Era. Relic uses Merkle inclusion proofs to prove data inclusion (as opposed to Axiom’s method of proving Merkle inclusion in zero knowledge).

Herodotus is working to provide historical data on Ethereum for layer 2 protocols. The test implementation is now available on Starknet and zkSync Era. With funding from the OP Foundation, we think we know where the Herodotus team is heading next.

Lagrange Labs Labs has introduced fully updatable proof through its recent ZK MapReduce (ZKMR) innovation. It uses a new vector promise called Recproofs to extend the concept of updatability to data computation.

Teams working on storage certification

epilogue

In this article, we’ve described how proof of storage can support the verification of data on the historical chain without trusting third parties. This makes them a valuable tool for on-chain composition and cross-chain interoperability.

As Total Locked Value (TVL) continues to migrate from Ethereum to the Tier 2 ecosystem, we anticipate the emergence of more expressive applications that utilize historical on-chain data through storage proofs.

While zero-knowledge technology is becoming faster and cheaper, continuously generating storage proofs to keep up with the costs associated with being on-chain is still a challenge. The profitability of such services will depend on the volume of queries generated by the query application.

Despite the challenges, the importance of proof of consensus and proof of storage supported by zero-knowledge technology cannot be overstated. We look forward to seeing how these technologies will be used to build a multi-chain future with minimal trust.

Disclaimer：

1. This article is reprinted from [mirror]. All copyrights belong to the original author [Jacob, Hitesh, Ji Hao]. If there are objections to this reprint, please contact the Gate Learn team（[email protected]）, and they will handle it promptly.
2. Liability Disclaimer: The views and opinions expressed in this article are solely those of the author and do not constitute any investment advice.
3. Translations of the article into other languages are done by the Gate Learn team. Unless mentioned, copying, distributing, or plagiarizing the translated articles is prohibited.