search

paritytech / polkadot-sdk

The Parity Polkadot Blockchain SDK
https://polkadot.network/
1.81k stars 661 forks source link

META: Parachains Reading Storage of One Another #855

Open shawntabrizi opened 2 years ago

shawntabrizi commented 2 years ago

Let this issue be a discussion thread for a question coming up more and more about enabling parachains to read state of one another, which can help facilitate XCM/XCMP and other cross chain messaging.

In general, for chains to effectively interoperate with one another, they must be able to send messages (XCM/XCMP), but also read state of other chains. For example, if Kilt acts as an identity / attestation chain, other parachains will want to be able to read which identities have which attestations, and use that information to improve the application experience they can provide.

I am definitely not an expert in this, but here are some ideas which may solve this problem, and can kickstart a conversation.

  1. XCM / XCMP

XCM/XCMP could provide a method for querying and returning data between parachains, but this would be very inefficient and also have problems related to the asynchronous nature of XCMP. Who knows how long it could take to get a response back, and who knows at that time if the response has data which is accurate.

Maybe this story changes once true parachain-to-parachain XCMP exists, but this seems like not a great solution while we still use HRMP.

  1. Substrate to Substrate Bridge

Our bridge infrastructure can allow two chains to verify the state on the other using merkle proofs.

Seems a bit crazy to create a bridge between parachains that are already connected to the same relay chain, but there are probably some tooling from within the bridges work that could be used here which will basically allow chains to provide verifiable proofs of storage items.

  1. Off-chain Workers

Chains could create a generalized off-chain worker to read the state of other parachains and report that information back to their chain in order to get the information they need.

At a high level, collators can be expected to run nodes of other parachains, or gain access to specific RPC endpoints where they can query the state of another chain. They may be able to provide a merkle proof of the data or use some kind of economic voting system (basic oracle stuff) to verify the data is correct. That data is then submitted directly to the parachain to be used for whatever runtime logic.

Are there other options? What is the current thinking on this?

xlc commented 2 years ago

I had some chat with Gav and his suggests to create a cross-chain state oracle for most of the queries.

The parachain have access to relaychain state root. It is possible to build a proof to for relaychain state value with state root. Relaychain state includes header of all the parachain. It is possible to build a proof of a parachain state from relaychain state root.

So we just need a pallet that is able to take a location, block number, storage key, storage value, a proof, and the pallet can access and verify the state of a parachain at a particular relaychain block.

The submitter can be an off chain worker or just a separate relayer. It could totally be a js library in frontend dApp. When user want to send tx to a parachain that needs to access some other parachain state, the frotnend can read the data from the other chain, and build tx to include the proof alone with the rest of the transaction parameter.

Related: https://github.com/paritytech/polkadot-sdk/issues/82

rphmeier commented 2 years ago

The parachain have access to relaychain state root. It is possible to build a proof to for relaychain state value with state root. Relaychain state includes header of all the parachain. It is possible to build a proof of a parachain state from relaychain state root.

This is the way; XCMP should be used for value transfers or when the merkle proofs get too heavy in the PoV. Otherwise, reading storage is all that's needed.

bkchr commented 2 years ago

The parachain have access to relaychain state root. It is possible to build a proof to for relaychain state value with state root. Relaychain state includes header of all the parachain. It is possible to build a proof of a parachain state from relaychain state root.

How will that work? I mean when you want to send a transaction that it can only be valid for one relay chain block and the corresponding parachain block. Currently you would have enough time, but in the future with asynchronous backing etc that gets even harder, especially to predict the relay chain block that the next parachain block will be build on. So, will we include something like the mmr pallet on the relay chain so that we can proof on any block that a given relay chain block was part of the chain? However, that just made me realize that we already store the last x (I think 1024? or even more) relay chain block hashes. So yeah, we actually don't need mmr for that because we already store enough relay chain block hashes for this to be useful.

shawntabrizi commented 2 years ago

I only worry that these proofs can end up pretty big, especially since we need to include first a proof of the relay chain state, and then the parachain state. Are there any back of the envelope calculations on what the average proof size may be for the balance of a user on another chain?

rphmeier commented 2 years ago

How will that work? I mean when you want to send a transaction that it can only be valid for one relay chain block and the corresponding parachain block.

It's not like you have to hit a moving target per se. You know what relay-parent you'll author a block against. Or you can use the relay-parent of the parent block.

Are there any back of the envelope calculations on what the average proof size may be for the balance of a user on another chain?

Amortized, it should take up about as much space in the PoV as a balance lookup for an account on the home chain.

bkchr commented 2 years ago

It's not like you have to hit a moving target per se. You know what relay-parent you'll author a block against. Or you can use the relay-parent of the parent block.

Ahh you want to let the collator do this. I had assumed that the user already includes all the required data in its transaction.

ferrell-code commented 2 years ago

Aren't you hitting a moving target, To my understanding collators can't be building the proof because they would need access to the state of other chains to create the necessary proof?

They can only verify that the proof is valid using the matching relay-chain state root (maybe storing trailing historical relay-chain state roots in collators would be of use)

bkchr commented 2 years ago

Hmm yeah, I mean we could find out about the current latest parachain head by letting the collator reading the relay chain state, but that wouldn't help with reading the parachain state. We could also make the collator read the parachain state, but this is going to explode in latency directly in our face.

crystalin commented 2 years ago

I don't see how we could guarantee consistency (receiving most recent value) for parachain state, specially with async backing where a parachain block won't have that 1-1 relay-block dependency.

I'm not sure however if consistency is a required feature for accessing another parachain state. In the way I imagined XCM for more complex scenarios, the interaction between the parachains would have to include a "lock" mechanism on the property the parachain is relying on, to ensure consistency while being async.

bkchr commented 2 years ago

With async backing where you have much more time to produce a block this issue will be fairly easy to solve. You are still building against a particular relay chain block. Then we could just implement the direct reading from the other parachain as part of the block building. While I'm still not sure that would be such a great idea, because it may introduces a lot of complexity.

crystalin commented 2 years ago

With async backing where you have much more time to produce a block this issue will be fairly easy to solve. You are still building against a particular relay chain block.

Yes but this is not consistent with the parachain state anymore. Exemple (not very realistic but to explain the idea):

I want to send an XCM from parachain A to parachain B locking account B1 tokens. Let's pretend for this scenario that I want to read the number of token that is available from B1 before creating the XCM which contains the number of tokens to lock. If parachain A reads the state of parachain B at relay block paritytech/cumulus#444 and sends it, there is a chance that when parachain B is going to receive it and execute it, it would be already on relay block paritytech/cumulus#446 and the B1 account might have changed since. (This is a problem of XCM and not directly of reading parachain state, but it shows that you can't have consistency with the state you are reading)

bkchr commented 2 years ago

Okay yeah that is right, but that is some completely different problem. I would also not say that this is a XCM problem, I more see this as a typical problem of async systems. There is nothing you can do against that.

crystalin commented 2 years ago

Yes, so I'm not sure what is the benefit of reading another parachain state if it isn't consistent. Do you have a use case where it is useful to do so ? I'm having trouble finding one.

xlc commented 2 years ago

The state consistency issue is a solved problem. There is no such guarantee on any modern multi server software solution so we use locks or various patterns to workaround this.

A simple example, how bridge on another other EVM chains (wormhole, chain bridge, etc) works by relaying deposit event. You will know the balance of the bridging contract was incremented by this amount with this event. The future event doesn't void the guarantee.

It is simply impossible to have atomic multi chain operations but that's fine. Web2 is still functional with async operations.

rphmeier commented 2 years ago

Aren't you hitting a moving target, To my understanding collators can't be building the proof because they would need access to the state of other chains to create the necessary proof?

Collators should be able to create short relay-chain ancestry proofs, which means that state proofs against any recent relay chain block should be includable in the parachain block.

Polkadot-Forum commented 1 year ago

This issue has been mentioned on Polkadot Forum. There might be relevant details there:

https://forum.polkadot.network/t/interchain-proof-oracle-network/653/1

arrudagates commented 1 year ago

Hey, is there recent progress being made towards this idea, or is it still under brainstorming phase?

Polkadot-Forum commented 1 year ago

This issue has been mentioned on Polkadot Forum. There might be relevant details there:

https://forum.polkadot.network/t/state-proof-based-parachain-parachain-messaging/2214/2