Repository: celestiaorg/nmt (go)

Issue:
Assumption that leaves are ordered is not used consistently
There is an assumption that leaves of NMTs are ordered by their namespace ids.

However, this assumption is not used.
For instance, [here](https://github.com/celestiaorg/nmt/blob/4276d172f18c87ebdd18da0cc4b758f0dd164118/spec/nmt.md?plain=1#L38) the spec takes `min(l.minNs, r.minNs)`, where `l.minNs` would suffice. Similarly, [here](https://github.com/celestiaorg/nmt/blob/4276d172f18c87ebdd18da0cc4b758f0dd164118/hasher.go#L255) in the code the same thing happens. On the other hand, the assumption is used in the function [CalculateAbsenceIndex](https://github.com/celestiaorg/nmt/blob/4276d172f18c87ebdd18da0cc4b758f0dd164118/nmt.go#L355-L355), when finding the appropriate leaf for the absence proof.

As this seems to be an important assumption, it would probably make the code and the spec clearer if it were consistently used.

Pull request:
feat: ensures consistent use of the assumption that NMT nodes are ordered ascendingly
## Overview
Closes #121 and #148.
Please refer to this [PR](https://github.com/celestiaorg/nmt/pull/193) to compare the new and old version of namsespacre range calculation for a parent node in the `HashNode()`.

## Checklist

- [x] New and updated code has appropriate documentation
- [x] New and updated code has new and/or updated testing
- [x] Required CI checks are passing
- [x] Visual proof for any user facing features like CLI or documentation updates
- [x] Linked issues closed with keywords


Patch:
diff --git a/hasher.go b/hasher.go
index f8d425e..f12c92b 100644
--- a/hasher.go
+++ b/hasher.go
@@ -256,12 +256,9 @@ func (n *Hasher) ValidateNodes(left, right []byte) error {
 // right.maxNID) || H(NodePrefix, left, right)`. `res` refers to the return
 // value of the HashNode. However, if the `ignoreMaxNs` property of the Hasher
 // is set to true, the calculation of the namespace ID range of the node
-// slightly changes. In this case, when setting the upper range, the maximum
-// possible namespace ID (i.e., 2^NamespaceIDSize-1) should be ignored if
-// possible. This is achieved by taking the maximum value among only those namespace
-// IDs available in the range of its left and right children that are not
-// equal to the maximum possible namespace ID value. If all the namespace IDs are equal
-// to the maximum possible value, then the maximum possible value is used.
+// slightly changes. Let MAXNID be the maximum possible namespace ID value i.e., 2^NamespaceIDSize-1.
+// If the namespace range of the right child is start=end=MAXNID, indicating that it represents the root of a subtree whose leaves all have the namespace ID of `MAXNID`, then exclude the right child from the namespace range calculation. Instead,
+// assign the namespace range of the left child as the parent's namespace range.
 func (n *Hasher) HashNode(left, right []byte) ([]byte, error) {
 	// validate the inputs
 	if err := n.ValidateNodes(left, right); err != nil {
@@ -271,21 +268,11 @@ func (n *Hasher) HashNode(left, right []byte) ([]byte, error) {
 	h := n.baseHasher
 	h.Reset()
 
-	// the actual hash result of the children got extended (or flagged) by their
-	// children's minNs || maxNs; hence the flagLen = 2 * NamespaceLen:
-	flagLen := 2 * n.NamespaceLen
-	leftMinNs, leftMaxNs := left[:n.NamespaceLen], left[n.NamespaceLen:flagLen]
-	rightMinNs, rightMaxNs := right[:n.NamespaceLen], right[n.NamespaceLen:flagLen]
-
-	minNs := min(leftMinNs, rightMinNs)
-	var maxNs []byte
-	if n.ignoreMaxNs && n.precomputedMaxNs.Equal(leftMinNs) {
-		maxNs = n.precomputedMaxNs
-	} else if n.ignoreMaxNs && n.precomputedMaxNs.Equal(rightMinNs) {
-		maxNs = leftMaxNs
-	} else {
-		maxNs = max(leftMaxNs, rightMaxNs)
-	}
+	leftMinNs, leftMaxNs := MinNamespace(left, n.NamespaceLen), MaxNamespace(left, n.NamespaceLen)
+	rightMinNs, rightMaxNs := MinNamespace(right, n.NamespaceLen), MaxNamespace(right, n.NamespaceLen)
+
+	// compute the namespace range of the parent node
+	minNs, maxNs := computeNsRange(leftMinNs, leftMaxNs, rightMinNs, rightMaxNs, n.ignoreMaxNs, n.precomputedMaxNs)
 
 	res := make([]byte, 0)
 	res = append(res, minNs...)
@@ -316,3 +303,13 @@ func min(ns []byte, ns2 []byte) []byte {
 	}
 	return ns2
 }
+
+// computeNsRange computes the namespace range of the parent node based on the namespace ranges of its left and right children.
+func computeNsRange(leftMinNs, leftMaxNs, rightMinNs, rightMaxNs []byte, ignoreMaxNs bool, precomputedMaxNs namespace.ID) (minNs []byte, maxNs []byte) {
+	minNs = leftMinNs
+	maxNs = rightMaxNs
+	if ignoreMaxNs && bytes.Equal(precomputedMaxNs, rightMinNs) {
+		maxNs = leftMaxNs
+	}
+	return minNs, maxNs
+}


Test patch:
diff --git a/hasher_test.go b/hasher_test.go
index 9800b44..e884752 100644
--- a/hasher_test.go
+++ b/hasher_test.go
@@ -839,3 +839,111 @@ func TestMin(t *testing.T) {
 		})
 	}
 }
+
+// TestComputeNsRange tests the ComputeRange function.
+func TestComputeNsRange(t *testing.T) {
+	nIDSize := 1
+	precomputedMaxNs := bytes.Repeat([]byte{0xFF}, nIDSize)
+
+	testCases := []struct {
+		leftMinNs, leftMaxNs, rightMinNs, rightMaxNs, expectedMinNs, expectedMaxNs []byte
+		ignoreMaxNs                                                                bool
+	}{
+		{
+			ignoreMaxNs:   true,
+			leftMinNs:     precomputedMaxNs,
+			leftMaxNs:     precomputedMaxNs,
+			rightMinNs:    precomputedMaxNs,
+			rightMaxNs:    precomputedMaxNs,
+			expectedMinNs: precomputedMaxNs,
+			expectedMaxNs: precomputedMaxNs,
+		},
+		{
+			ignoreMaxNs:   true,
+			leftMinNs:     []byte{0x00},
+			leftMaxNs:     precomputedMaxNs,
+			rightMinNs:    precomputedMaxNs,
+			rightMaxNs:    precomputedMaxNs,
+			expectedMinNs: []byte{0x00},
+			expectedMaxNs: precomputedMaxNs,
+		},
+		{
+			ignoreMaxNs:   true,
+			leftMinNs:     []byte{0x00},
+			leftMaxNs:     []byte{0x01},
+			rightMinNs:    precomputedMaxNs,
+			rightMaxNs:    precomputedMaxNs,
+			expectedMinNs: []byte{0x00},
+			expectedMaxNs: []byte{0x01},
+		},
+		{
+			ignoreMaxNs:   true,
+			leftMinNs:     []byte{0x00},
+			leftMaxNs:     []byte{0x01},
+			rightMinNs:    []byte{0x02},
+			rightMaxNs:    precomputedMaxNs,
+			expectedMinNs: []byte{0x00},
+			expectedMaxNs: precomputedMaxNs,
+		},
+		{
+			ignoreMaxNs:   true,
+			leftMinNs:     []byte{0x00},
+			leftMaxNs:     []byte{0x01},
+			rightMinNs:    []byte{0x02},
+			rightMaxNs:    []byte{0x03},
+			expectedMinNs: []byte{0x00},
+			expectedMaxNs: []byte{0x03},
+		},
+		{
+			ignoreMaxNs:   false,
+			leftMinNs:     precomputedMaxNs,
+			leftMaxNs:     precomputedMaxNs,
+			rightMinNs:    precomputedMaxNs,
+			rightMaxNs:    precomputedMaxNs,
+			expectedMinNs: precomputedMaxNs,
+			expectedMaxNs: precomputedMaxNs,
+		},
+		{
+			ignoreMaxNs:   false,
+			leftMinNs:     []byte{0x00},
+			leftMaxNs:     precomputedMaxNs,
+			rightMinNs:    precomputedMaxNs,
+			rightMaxNs:    precomputedMaxNs,
+			expectedMinNs: []byte{0x00},
+			expectedMaxNs: precomputedMaxNs,
+		},
+		{
+			ignoreMaxNs:   false,
+			leftMinNs:     []byte{0x00},
+			leftMaxNs:     []byte{0x01},
+			rightMinNs:    precomputedMaxNs,
+			rightMaxNs:    precomputedMaxNs,
+			expectedMinNs: []byte{0x00},
+			expectedMaxNs: precomputedMaxNs,
+		},
+		{
+			ignoreMaxNs:   false,
+			leftMinNs:     []byte{0x00},
+			leftMaxNs:     []byte{0x01},
+			rightMinNs:    []byte{0x02},
+			rightMaxNs:    precomputedMaxNs,
+			expectedMinNs: []byte{0x00},
+			expectedMaxNs: precomputedMaxNs,
+		},
+		{
+			ignoreMaxNs:   false,
+			leftMinNs:     []byte{0x00},
+			leftMaxNs:     []byte{0x01},
+			rightMinNs:    []byte{0x02},
+			rightMaxNs:    []byte{0x03},
+			expectedMinNs: []byte{0x00},
+			expectedMaxNs: []byte{0x03},
+		},
+	}
+
+	for _, tc := range testCases {
+		minNs, maxNs := computeNsRange(tc.leftMinNs, tc.leftMaxNs, tc.rightMinNs, tc.rightMaxNs, tc.ignoreMaxNs, precomputedMaxNs)
+		assert.True(t, bytes.Equal(tc.expectedMinNs, minNs))
+		assert.True(t, bytes.Equal(tc.expectedMaxNs, maxNs))
+	}
+}