Cosmos-sdk: Specification for Lite Client Proofs

[jbibla]

• how do we want to handle proofs?
• might need some consolidate of proof types into a common interface

[ethanfrey]

I wanted to shore up sdk2 to some mvp that we could use for peggy (pretty minimal functionality needed). So, I tried to get a first version of this issue solved, but without proofs, using the Get functionality already exposed in KVStore.

I took a stab at query, but quickly got lost.
We have a path in the abci.reqQuery, which I would love to map to the store name.
path == "/main" -> main store
path == "/ibc" -> ibc store
etc...

I would try without proofs and height at first, just look up the substore and do a Get.
However, I discovered, there is no way to map a string to substore. As a design decision.

https://github.com/cosmos/cosmos-sdk/blob/sdk2/types/store.go#L179-L192
https://github.com/cosmos/cosmos-sdk/blob/sdk2/examples/basecoin/app/basecoin_app.go#L69-L73

So I need to build some other lookup on the app for string -> KeyStore which is accessible to query, even though MultiStore does just that? I'm just trying to get something super minimal to work with, let me know if you have an idea how to do this?

On another note, I was super happy to find make all and make test worked :slightly_smiling_face: Very nice

[ethanfrey]

For people who care about multi-level Merkle proofs, I have a spec from 3 months ago that could use feedback....

https://github.com/cosmos/cosmos-sdk/blob/feature/ibc/docs/spec/ibc/appendix.md#appendix-c-merkle-proof-formats

[ethanfrey]

Just ported from Google docs to markdown, so hopefully more accesible and more read.

[rigelrozanski]

@adrianbrink this is what we were talking about yesterday

[rigelrozanski]

Seems reasonable - I'd like more detailed clarity in this spec as well as a couple generic example proofs - but I have a thorough grasp as to what's going on here.
nice examples to run through:

• non-multistore single value proof
• non-multistore range value proof
• non-multistore range value but nothing is there proof
• multistore single value proof

Also I don't think we need proofs of ranges across stores at all

[ethanfrey]

There are no range proofs here. Only single value proofs.

Range proofs are a series of single value proofs.

I wanted to formalize them as a different type along with Alexis, but Jae was opposed, so we didn't invest more time on them. There is an implementation in iavl, as a slice of single proofs, and the validator just makes sure they are all adjacent.

[ethanfrey]

But, yes, I should give examples of the two (single-store and multistore) value proofs.

Proofs of non-existence are also a special case of a range proof for an empty range that includes the desired key (by showing adjacent proofs below and above the requested proof)

[adrianbrink]

I just read through the paragraph in the above link. It's a good description. I don't know yet how to provide feedback. I have to think about it some more.

https://github.com/cosmos/cosmos-sdk/blob/feature/ibc/docs/spec/ibc/protobuf/merkle.proto

This your proposed serialisation format, right?

[ethanfrey]

Yes.

You can see the existing proofs in tendermint/iavl. This is an attempt at a generalization.
It would be good if you could verify that patricia tree proofs could also be represented in this format.
Like converted without losing their verification power.

[rigelrozanski]

range proofs can be accomplished by providing the extents of the range, as well as any content (if it exists) and then hashing up the tree... so in this way range proofs are quite distinct from the individual proofs - this accomplishes proof of non-existence as well

[adrianbrink]

related #224 and #198

[cwgoes]

CC @mossid

[mossid]

1062 will close this

[jackzampolin]

@mossid Can you provide an update here? I know there is some tendermint and iavl work that bears on this.

[jackzampolin]

This is being handled by the tendermint team. Going to close this issue.

[rigelrozanski]

Hmmm is this truly the case? Half of the light client proofs need to exist _within_ the sdk right? Tendermint doesn't know how to unmarshal the app store, and to prove specific attributes about the state of the blockchain we need to prove more than just the app hash... we actually need to prove the a certain app-store key is a specific value, so ultimately the light client proofs are two fold, proof of the app-hash (tendermint) and proof value within the app-store (sdk)

[fedekunze]

closing this as this is now being handled on tendermint and ICS