Proof Format Qs Thread

[notbdu]

We're currently working on additional IBC light client implementations @ Polymer. Starting a thread here for general questions about the proof format to help us better understand the impl details so we can add addtional proof specs in the future.

[notbdu]

Is it correct that Prefix/Suffix can be generalized for > 2 child nodes?

For example we could support any N number of child nodes:

prefix = variable length prefix || child nodes left of path key
suffix = child nodes right of path key

Node hash being -> h(prefix || path key || suffix).

[notbdu]

For the base16 modified merkle trie used by parity, each node has up to 16 children. Go parity/trie impl here for reference.

It looks like the following would be appended to the prefix bytes:
https://github.com/ChainSafe/gossamer/blob/08e97038189f5f6faf28847e7d51328fd2cb653b/internal/trie/node/branch_encode.go#L88-L115

The blake2b hashes of the children are then appended. I'm assuming we'd leave a slot for the path key in the step definition we're currently on.

Node hashes are 32 bytes. Although it has up to 16 children per branch node, it looks like nil child nodes are not encoded.
https://github.com/ChainSafe/gossamer/blob/08e97038189f5f6faf28847e7d51328fd2cb653b/internal/trie/node/branch_encode.go#L249-L251

Wouldn't this throw off the padding logic as it indexes based on child size (32 bytes)?

[AdityaSripal]

I don't believe the ProofSpec is limited to 2 children since you can define a custom ordering in the InnerSpec:
https://github.com/confio/ics23/blob/b99c94329e/proofs.proto#L181

Node hashes are 32 bytes. Although it has up to 16 children per branch node, it looks like nil child nodes are not encoded.

ICS23 allows you to specify what an empty child node will look like: https://github.com/confio/ics23/blob/b99c94329e/proofs.proto#L186

pinging @ethanfrey to verify my answers and provide details on the prefixing logic

[ethanfrey]

Is it correct that Prefix/Suffix can be generalized for > 2 child nodes?

Yes this is the idea. And there is some logic added in recent PRs that iterate over them. (The fact that the byte order of the children may not represent the lexicographical ordering of their keys is an annoying one and added to try to make things work well for @mappum with merk.rs). I actually wonder if it may be easier to assert this ordering and have merk.rs change the proof format?

[ethanfrey]

It looks like the following would be appended to the prefix bytes:
https://github.com/ChainSafe/gossamer/blob/08e97038189f5f6faf28847e7d51328fd2cb653b/internal/trie/node/branch_encode.go#L88-L115

The blake2b hashes of the children are then appended. I'm assuming we'd leave a slot for the path key in the step definition we're currently on.

Yeah, that section and the child keys left of the one you are proving are in the Prefix. All child keys right of the one you prove are in the suffix.

I took a look at
https://github.com/ChainSafe/gossamer/blob/08e97038189f5f6faf28847e7d51328fd2cb653b/internal/trie/node/branch.go#L14-L31 and notice there is Key and Value in each node as well as children.

This means the node may be both a leaf and an inner node? Is that true?
My understanding of Merkle tries is that they would pre-hash the key so that every branch was the same length (32 bytes) and nodes are strictly leaf or inner

[ethanfrey]

Node hashes are 32 bytes. Although it has up to 16 children per branch node, it looks like nil child nodes are not encoded.
https://github.com/ChainSafe/gossamer/blob/08e97038189f5f6faf28847e7d51328fd2cb653b/internal/trie/node/branch_encode.go#L249-L251

Wouldn't this throw off the padding logic as it indexes based on child size (32 bytes)?

🤦 this is the same sort of over-optimisation that made the Ethereum Patricia Trie un-encodable. They may include a leaf node as one item, but if there are only 2 children on the level above, it will include an inner node and a leaf.

ics23 has a relatively simple state non-turing complete machine that was designed to work for a number of cases I found. When there is a bitmap that must be parsed and understood to decipher the following items, then this becomes impossible to represent without custom Go code.

I am starting to believe that while most Merkle trees could produce an ics23 compatible proof, they choose not to.

There are 2 choices:

(1) allow clients to define custom Go code for the state rather than ics23 spec. This will require all counterparties to include this custom code and slow down rollout, but maybe this is worth it.
(2) change the proof format. It is possible to generate an ics23-compatible proof from the linked trie. However, it would produce different root hashes.

[notbdu]

Would it make sense to type switch at a higher level over different types of tree structures -> proof types? E.g. generic merkle/verkle etc.

Every non generalizable structure could be an additional type switch? For the parity/eth trie impls, maybe the type switching could be done within an extended proof spec with special ops depending on the merkle type?

We're looking into adding a verkle tree to the cosmos sdk and are currently doing the following as hack in the meantime. Also, seems like verkle proofs can support both existence/non-existence proofs combined into multiproofs so no need to differentiate between the proof types?
https://github.com/polymerdao/ics23/pull/1/files
https://github.com/polymerdao/ics23/pull/2/files

[notbdu]

Looks like the octopus network guys also hitting the same issue with generalizing the hexary patricia merkle trie on the parity side.

#80