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: celestiaorg/nmt#3 (comment)

[liamsi]

ref: celestiaorg/celestia-core#307 (comment)