Spec more Merkle proofs format

[adlerjohn]

47 cleaned up a number of issues around Merkle tree specs. Additional proof formats still need to be defined

• [ ] Merkle multiproofs
• [ ] Exclusion proof for Sparse Merkle tree (rather, inclusion proof of empty leaf)
• [ ] Range proof for NMT

[liamsi]

Regarding the range proof format for the NMT, here is how I think they should look like:

// Proof represents proof of a namespace.ID in an NMT.
// In case this proof proves the absence of a namespace.ID
// in a tree it also contains the leaf hashes of the range
// where that namespace would be.
type Proof struct {
    // Start index of this proof.
    Start int
    // End index of this proof.
    End int
    // Nodes that together with the corresponding leaf values
    // can be used to recompute the root and verify this proof.
    Nodes [][]byte
    // LeafHashes are nil if the namespace is present in the NMT.
    // In case the namespace to be proved is in the min/max range of
    // the tree but absent, this will contain the leaf hashes
    // necessary to verify the proof of absence.
    LeafHashes [][]byte
}

These probably should not be ints and for nodes as well as leafHashes we might want to use a type alias (or even a struct that captures min, max, and the actual digest).

This is a good description how to construct range proofs: https://gitlab.com/NebulousLabs/merkletree/-/blob/master/range.go#L197-256 My understanding is that we always have one range only though.

Note that to prove absence we need to provide the leafHashes too.

[musalbas]

I assume that Nodes are the subtree roots?

[liamsi]

Yes, exactly. I think the name is appropriate because each subtree root is also a node in the tree, hence proof.Nodes(). proof.SubtreeRoots() would also be good.

[liamsi]

Note that to prove absence we need to provide the leafHashes too.

Don't we always just need a single leaf to prove absence of a namespace?

Explanation: https://github.com/lazyledger/nmt/pull/3#discussion_r464431192

[liamsi]

ref: https://github.com/lazyledger/lazyledger-core/issues/307#issuecomment-830673091