Spec more Merkle proofs format

[sync-by-unito]

#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

┆Issue is synchronized with this Asana task by Unito

[sync-by-unito]

➤ Ismail Khoffi commented:

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.

[sync-by-unito]

➤ Mustafa Al-Bassam commented:

I assume that Nodes are the subtree roots?

[sync-by-unito]

➤ Ismail Khoffi commented:

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.

[sync-by-unito]

➤ Ismail Khoffi commented:

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

[sync-by-unito]

➤ Ismail Khoffi commented:

ref: #307 (comment)