Namespace proof soundness can fail if leafHash namespace range isn't checked against queried namespace ID

[staheri14]

Problem

This issue was identified as part of #110 and celestiaorg/celestia-app#1296.
We must ensure that the supplied leafHash in an absence proof falls within the correct range of the namespace ID by verifying that nID<leafHash.minNID where nID is the queried namespace ID (more specifically, nID should not overlap with the leafHash range of namespace IDs). This step is crucial to the verification process because it confirms that the leafHash node is the correct one -- i.e., the one with the smallest namespace ID greater than the queried nID. Without this verification, the proof's soundness cannot be guaranteed.

In the example below, the wrongProof proves the absence of namespace ID =2 while this namespace ID is actually present in the tree.

	nID := namespace.ID{2}
	// create a tree with 4 leaves, variables names match the figure above
	n := New(sha256.New(), NamespaceIDSize(1))
	d0 := append([]byte{0}, []byte("data0")...)
	d1 := append([]byte{2}, []byte("data1")...)
	d2 := append([]byte{3}, []byte("data2")...)
	d3 := append([]byte{4}, []byte("data3")...)

	n.Push(d0)
	n.Push(d1)
	n.Push(d2)
	n.Push(d3)

	// this will populate n.leafHashes with the hash of d0...d3
	n.computeLeafHashesIfNecessary()

	root := n.Root()
	hash2 := n.computeRoot(2, 4)
	leaf0 := n.leafHashes[0]
	leaf1 := n.leafHashes[1]

	// attack scenario: create a partial proof  that proves absence of nID=2
	wrongProof := Proof{start: 1, end: 2, leafHash: leaf1, nodes: [][]byte{leaf0, hash2}}
	// run VerifyNamespace for the fabricated absence proof and see if it can pass
	if wrongProof.VerifyNamespace(sha256.New(), nID, nil, root) {
		fmt.Println("wrong proof is successfully verified") // this will be executed
	} else {
		fmt.Println("verification of the wrong proof failed")
	}

[staheri14]

Closing this issue as it is addressed by #116.