ICS23: Add support for SHA-512/256 hash function

[kostko]

The current Merkle proof abstraction defined by ICS 23 (or at least the major Go and Rust implementations) and used for state commitment proofs does not seem to include support for the SHA-512/256 hash function (actually it seems that the supported hash functions are not actually part of the spec if I'm reading this right, so not sure where this should go).

The Oasis Protocol uses a custom merkelized binary patricia trie data structure instantiated with SHA-512/256 as the hash function so it would be great if we could see support for it in IBC. The change to support an additional hash function should be straightforward.

We may need other changes related to node encoding, but this is something that is orthogonal and needs further exploration.

[ethanfrey]

@kostko The supported hash functions are defined here: https://github.com/confio/ics23/blob/master/proofs.proto#L5-L13

The implementation to validate any proof in the ics23 format is also included in that repo. Note that the Cosmos IAVL tree uses SHA256 from this repo, so you are only discussing sha2-512 I believe.

You should be able to define a custom spec for your binary patricia trie. However, it requires a normal format. Ethereum's Patricia Trie which does arbitrary compression as well as variable encoding leafs as separate nodes are part of their parent based on length, proved impossible to include in the ics23 spec (it required tons of custom logic to verify). The Ethereum 2.0 SMT is much more regular and should be able to be proven by the current spec.

The first step is to find a document explaining exactly how one will validate a proof from Oasis's mkvs (I clicked the link above to the code and saw no docs).

[kostko]

The supported hash functions are defined here: https://github.com/confio/ics23/blob/master/proofs.proto#L5-L13

Right, but the text of the specification (in this repository) does not specify any of the supported hash functions. Are those implementation-specific details? To me it seems like these should be standardized otherwise interoperability is harder.

The implementation to validate any proof in the ics23 format is also included in that repo. Note that the Cosmos IAVL tree uses SHA256 from this repo, so you are only discussing sha2-512 I believe.

Yeah I know about IAVL and that it uses SHA256. We are using SHA-512/256 which is the truncated version of SHA-512 with its own IVs so you cannot just use SHA-512 (which is supported in the above implementation under enum tag 2).

You should be able to define a custom spec for your binary patricia trie. However, it requires a normal format.

Can you explain what you mean by a "normal format"? Is there some document explaining the Merkle proof abstraction you are using? Also this doesn't seem to be part of the specification of ICS 23, the specification actually is very high level and does not actually define anything except some abstract interface?

[ethanfrey]

We are using SHA-512/256 which is the truncated version of SHA-512 with its own IVs so you cannot just use SHA-512 (which is supported in the above implementation under enum tag 2).

I have never seen this algorithm before. Is it only used in your chain or are there standard docs? Can you provide links to stable Go, Rust, and Typescript implementations for it? If this is a standard, supported algorithm, I am happy to accept a PR adding it to the confio/ics23 repo.

Also this doesn't seem to be part of the specification of ICS 23, the specification actually is very high level and does not actually define anything except some abstract interface?

Yeah, I am not involved in that, but did write confio/ics23 quite some time ago. Just look at the specs we write there describing iavl tree and tendermint merkle proofs. It is a "config format" to define the steps needed to validate.

P.S. If you make an issue on confio/ics23 please mention me in it, I don't get notifications for other issues for some reason

[kostko]

I have never seen this algorithm before. Is it only used in your chain or are there standard docs? Can you provide links to stable Go, Rust, and Typescript implementations for it? If this is a standard, supported algorithm, I am happy to accept a PR adding it to the confio/ics23 repo.

Yes, this is a standard algorithm defined in the same standard that defines the SHA-2 family of hash functions (see FIPS 180-4). There are a number of implementations available, including in the Go standard library.

[kostko]

@ethanfrey I've opened cosmos/ics23#39 which adds SHA-512/256 hash op and implements the missing FIXED32_LITTLE length op.

[kostko]

Also can someone point to any Rust implementations of ICS-23? The ibc-rs repository only seems to have the types but I don't see any verification logic?

[ethanfrey]

The rust implementation is inside confio/ics23. As is the Go and TypeScript. They are all kept in the same repo to ensure they stay in sync.

[kostko]

The PR should have all the implementations now.