Support for proof generation in rust

[seunlanlege]

This lib lacks support for generating proofs in rust, which will be required in order to generate ibc packet proofs from a substrate runtime

[ethanfrey]

Hi @seunlanlege I assume you are working on the project @jackzampolin told me about? It would be great to get more info on the project here as well as there are a few groups working to extend ics23 for different chains and I think a more visibility helps collaboration.

That said, the reason there is no generation logic in Rust is the same that there is no generation logic in Go. ics23 provides both a standard format into which various Merkle proofs can be combines as well as logic to verify them, regardless of which chain they are from. This means that you can update your Merkle store without requiring all counterparty chains to first update their codebase. Something we will see with the Cosmos SMT update.

For proof generation, I have made separate libraries for each Merkle tree I wish to generate from. For example https://github.com/confio/ics23-iavl imports both this repo as well as https://github.com/cosmos/iavl and generates ics23-compatible proofs from said store. I would propose making a ics23-substrate repo that imports the substrate libs as needed and converts the proofs into this format.

That can be done server side (in a substrate crate) or client side. The client side would need to parse out the native Merkle proof format from substrate and convert it to this ics23 format. It would be simpler for relayers if you can do it server side, but may not be possible to implement in substate (I don't know this, you are the expert here). If it is too difficult server side, then just try writing a client-side binary in Rust, pulling in any needed substate crates.

[ethanfrey]

@roysc has been working on SMT proofs for another SMT implementation (in Golang) here #57

You may need these features in order to properly implement the Substate one and I suggest reaching out to him (on that issue) to share experiences with SMTs

[seunlanlege]

Thanks for the detailed response @ethanfrey but this brings us back to the original issue which is.

paritytech/trie doesn't support proofs of non-membership. So what does a merkle proof of non-membership look like?

[ethanfrey]

@AdityaSripal is working on that.

Or changing the IBC protocol so it can handle stores that only provide membership proofs.

Maybe he can add something or @roysc who is working on proofs for another SMT implementation

[AdityaSripal]

Hi yes, we're working to add support for timeouts without absence proofs: cosmos/ibc#620

The above details the current approach which will only require membership proofs to implement the full IBC protocol. The spec will probably be finalized within the next month. From a proof construction standpoint, there is no work necessary. Just provide the ability to generate membership proofs and the new protocol will be able to handle it.

Note that it will take time for this to reach currently deployed implementations so it would be useful to understand your timelines and when this is expected to be used in the wild

[ethanfrey]

Thanks for the detailed response @ethanfrey but this brings us back to the original issue which is.

paritytech/trie doesn't support proofs of non-membership. So what does a merkle proof of non-membership look like?

Maybe you (or better Parity) can fix that upstream?

A proof of non-membership is consists generally of 2 proofs of membership. One proof being lower than the requested key, the other higher than the requested key. And a proof that there are no keys between those two. (This analyses the shape of the trie - that there are no non-empty paths between them)

Even as they hash the keys before storing in the trie, we can hash the key to find the desired location and provide two hashes which are adjacent and surround this desired key, proving it cannot be in the trie

[seunlanlege]

A proof of non-membership is consists generally of 2 proofs of membership. One proof being lower than the requested key, the other higher than the requested key.

This part i understand, but its also possible to produce proofs that fool the verifier since the verifier doesn't know the order of the original items in the trie.

And a proof that there are no keys between those two. (This analyses the shape of the trie - that there are no non-empty paths between them)

You'll have to explain a bit more how this is to be achieved

[ethanfrey]

This part i understand, but its also possible to produce proofs that fool the verifier since the verifier doesn't know the order of the original items in the trie.

This is what ics23 takes care of :)

[ethanfrey]

The Spec definitions can used to define the shape of the hashing function for a large varieties of trees and tries. (But not Ethereum's Patricia trie which may encode the leaf node of multiple leafs and inner nodes in the final section... it has no stable structure).

They have gotten this to work to define an SMT in Go #57, with some additions to the adjacency checks (which I need to re-review and merge). That PR should be a good guideline to look at Parity's SMT implementation