Repository: celestiaorg/nmt (go)

Issue:
Check ordering of namespace among child nodes in HashNode function
This [testCase](https://github.com/celestiaorg/nmt/blob/4276d172f18c87ebdd18da0cc4b758f0dd164118/hasher_test.go#L93-L101) submits children nodes with invalid namespace ordering to HashNode function. The left child node has minNs larger than the maxNs of the same node, and in addition to that leftMinNs is even larger then the rightMinNs. The test will pass because HashNode function panics (in [validateSiblingsNamespaceOrder](https://github.com/celestiaorg/nmt/blob/4276d172f18c87ebdd18da0cc4b758f0dd164118/hasher.go#L177-L194)) only if the rightMinNs is less than leftMaxNs.

Evan if the before mentioned test case is totally invalid based on the fact that the Push function will guarantee that the namespace ids will be ordered, it raises two questions or two paths for this issue:

1.  Should this test case be removed?
2. Should [validateSiblingsNamespaceOrder](https://github.com/celestiaorg/nmt/blob/4276d172f18c87ebdd18da0cc4b758f0dd164118/hasher.go#L177-L194) check the ordering of leftMinNs, leftMaxNs, rightMinNs and rightMaxNs among children nodes?

I would suggest that the 'validateSiblingsNamespaceOrder' checks the ordering of the children namespaces just to be more robust, but the decisions is on the development team.

Pull request description:
feat: verifies the namespace order for each tree node
## Overview
Closes #129.

## 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 3806ba1..cba17a9 100644
--- a/hasher.go
+++ b/hasher.go
@@ -17,9 +17,10 @@ const (
 var _ hash.Hash = (*Hasher)(nil)
 
 var (
-	ErrUnorderedSiblings = errors.New("NMT sibling nodes should be ordered lexicographically by namespace IDs")
-	ErrInvalidNodeLen    = errors.New("invalid NMT node size")
-	ErrInvalidLeafLen    = errors.New("invalid NMT leaf size")
+	ErrUnorderedSiblings         = errors.New("NMT sibling nodes should be ordered lexicographically by namespace IDs")
+	ErrInvalidNodeLen            = errors.New("invalid NMT node size")
+	ErrInvalidLeafLen            = errors.New("invalid NMT leaf size")
+	ErrInvalidNodeNamespaceOrder = errors.New("invalid NMT node namespace order")
 )
 
 type Hasher struct {
@@ -201,6 +202,12 @@ func (n *Hasher) ValidateNodeFormat(node []byte) (err error) {
 	if nodeLen != expectedNodeLen {
 		return fmt.Errorf("%w: got: %v, want %v", ErrInvalidNodeLen, nodeLen, expectedNodeLen)
 	}
+	// check the namespace order
+	minNID := namespace.ID(MinNamespace(node, n.NamespaceSize()))
+	maxNID := namespace.ID(MaxNamespace(node, n.NamespaceSize()))
+	if maxNID.Less(minNID) {
+		return fmt.Errorf("%w: max namespace ID %d is less than min namespace ID %d ", ErrInvalidNodeNamespaceOrder, maxNID, minNID)
+	}
 	return nil
 }
 


Test patch:
diff --git a/hasher_test.go b/hasher_test.go
index 0a7ed6d..9800b44 100644
--- a/hasher_test.go
+++ b/hasher_test.go
@@ -100,18 +100,6 @@ func Test_namespacedTreeHasher_HashNode(t *testing.T) {
 					concat([]byte{0, 0, 0, 0}, randHash),
 					concat([]byte{0, 0, 1, 1}, randHash))),
 		},
-		// XXX: can this happen in practice? or is this an invalid state?
-		{
-			"leftmin>rightmin && leftmax<rightmax", 2,
-			children{
-				concat([]byte{1, 1, 0, 0}, randHash),
-				concat([]byte{0, 0, 0, 1}, randHash),
-			},
-			concat([]byte{0, 0, 0, 1}, // minNID||maxNID
-				sum(crypto.SHA256, []byte{NodePrefix}, // Hash(NodePrefix||left||right)
-					concat([]byte{1, 1, 0, 0}, randHash),
-					concat([]byte{0, 0, 0, 1}, randHash))),
-		},
 	}
 	for _, tt := range tests {
 		t.Run(tt.name, func(t *testing.T) {
@@ -221,7 +209,8 @@ func TestNamespaceHasherSum(t *testing.T) {
 	}
 }
 
-func TestHashNode_ChildrenNamespaceRange(t *testing.T) {
+// TestHashNode verifies the HashNode function for scenarios where it is expected to produce errors, as well as those where it is not.
+func TestHashNode_Error(t *testing.T) {
 	// create a dummy hash to use as the digest of the left and right child
 	randHash := createByteSlice(sha256.Size, 0x01)
 	type children struct {
@@ -237,7 +226,7 @@ func TestHashNode_ChildrenNamespaceRange(t *testing.T) {
 		errType  error
 	}{
 		{
-			"left.maxNs>right.minNs", 2,
+			"unordered siblings: left.maxNs>right.minNs", 2,
 			children{
 				concat([]byte{0, 0, 1, 1}, randHash),
 				concat([]byte{0, 0, 1, 1}, randHash),
@@ -246,7 +235,7 @@ func TestHashNode_ChildrenNamespaceRange(t *testing.T) {
 			ErrUnorderedSiblings,
 		},
 		{
-			"left.maxNs=right.minNs", 2,
+			"ordered siblings: left.maxNs=right.minNs", 2,
 			children{
 				concat([]byte{0, 0, 1, 1}, randHash),
 				concat([]byte{1, 1, 2, 2}, randHash),
@@ -255,7 +244,7 @@ func TestHashNode_ChildrenNamespaceRange(t *testing.T) {
 			nil,
 		},
 		{
-			"left.maxNs<right.minNs", 2,
+			"ordered siblings: left.maxNs<right.minNs", 2,
 			children{
 				concat([]byte{0, 0, 1, 1}, randHash),
 				concat([]byte{2, 2, 3, 3}, randHash),
@@ -263,6 +252,24 @@ func TestHashNode_ChildrenNamespaceRange(t *testing.T) {
 			false,
 			nil,
 		},
+		{
+			"invalid left sibling format: left.minNs>left.maxNs", 2,
+			children{
+				concat([]byte{2, 2, 0, 0}, randHash),
+				concat([]byte{1, 1, 4, 4}, randHash),
+			},
+			true,
+			ErrInvalidNodeNamespaceOrder,
+		},
+		{
+			"invalid right sibling format: right.minNs>right.maxNs", 2,
+			children{
+				concat([]byte{0, 0, 1, 1}, randHash),
+				concat([]byte{4, 4, 1, 1}, randHash),
+			},
+			true,
+			ErrInvalidNodeNamespaceOrder,
+		},
 	}
 	for _, tt := range tests {
 		t.Run(tt.name, func(t *testing.T) {
@@ -276,7 +283,7 @@ func TestHashNode_ChildrenNamespaceRange(t *testing.T) {
 	}
 }
 
-func TestValidateSiblingsNamespaceOrder(t *testing.T) {
+func TestValidateSiblings(t *testing.T) {
 	// create a dummy hash to use as the digest of the left and right child
 	randHash := createByteSlice(sha256.Size, 0x01)
 
@@ -375,6 +382,33 @@ func TestValidateNodeFormat(t *testing.T) {
 			true,
 			ErrInvalidNodeLen,
 		},
+		{
+			"invalid node: minNS > maxNs",
+			2,
+			[]byte{3, 3},
+			[]byte{1, 1},
+			concat(hashValue),
+			true,
+			ErrInvalidNodeNamespaceOrder,
+		},
+		{
+			"valid node: minNs = maxNs",
+			2,
+			minNID,
+			minNID,
+			concat(hashValue),
+			false,
+			nil,
+		},
+		{
+			"valid node: minNs < maxNs",
+			2,
+			minNID,
+			maxNID,
+			concat(hashValue),
+			false,
+			nil,
+		},
 	}
 
 	for _, tt := range tests {
@@ -735,3 +769,73 @@ func Test_MustHashLeaf_Panic(t *testing.T) {
 		})
 	}
 }
+
+func TestMax(t *testing.T) {
+	tt := []struct {
+		name     string
+		ns       []byte
+		ns2      []byte
+		expected []byte
+	}{
+		{
+			"First argument is larger",
+			[]byte{1, 2, 3},
+			[]byte{1, 2},
+			[]byte{1, 2, 3},
+		},
+		{
+			"Second argument is larger",
+			[]byte{1, 2},
+			[]byte{1, 2, 3},
+			[]byte{1, 2, 3},
+		},
+		{
+			"Arguments are equal",
+			[]byte{1, 2, 3},
+			[]byte{1, 2, 3},
+			[]byte{1, 2, 3},
+		},
+	}
+
+	for _, ts := range tt {
+		t.Run(ts.name, func(t *testing.T) {
+			maxResult := max(ts.ns, ts.ns2)
+			assert.Equal(t, ts.expected, maxResult)
+		})
+	}
+}
+
+func TestMin(t *testing.T) {
+	tt := []struct {
+		name     string
+		ns       []byte
+		ns2      []byte
+		expected []byte
+	}{
+		{
+			"First argument is smaller",
+			[]byte{1, 2},
+			[]byte{1, 2, 3},
+			[]byte{1, 2},
+		},
+		{
+			"Second argument is smaller",
+			[]byte{1, 2, 3},
+			[]byte{1, 2},
+			[]byte{1, 2},
+		},
+		{
+			"Arguments are equal",
+			[]byte{1, 2, 3},
+			[]byte{1, 2, 3},
+			[]byte{1, 2, 3},
+		},
+	}
+
+	for _, ts := range tt {
+		t.Run(ts.name, func(t *testing.T) {
+			minResult := min(ts.ns, ts.ns2)
+			assert.Equal(t, ts.expected, minResult)
+		})
+	}
+}
diff --git a/proof_test.go b/proof_test.go
index da5c371..a85b93e 100644
--- a/proof_test.go
+++ b/proof_test.go
@@ -286,13 +286,17 @@ func TestVerifyLeafHashes_Err(t *testing.T) {
 	root, err := nmt.Root()
 	require.NoError(t, err)
 
+	// shrink the size of the root so that the root hash is invalid.
+	corruptRoot := root[:len(root)-1]
+
 	// create an NMT proof
 	nID5 := namespace.ID{5, 5}
 	proof5, err := nmt.ProveNamespace(nID5)
 	require.NoError(t, err)
 	// corrupt the leafHash so that the proof verification fails during the root computation.
 	// note that the leaf at index 4 has the namespace ID of 5.
-	leafHash5 := nmt.leafHashes[4][:nmt.NamespaceSize()]
+	leafHash5 := nmt.leafHashes[4]
+	corruptLeafHash5 := leafHash5[:nmt.NamespaceSize()]
 
 	// corrupt the leafHash: replace its namespace ID with a different one.
 	nID3 := createByteSlice(nameIDSize, 3)
@@ -339,7 +343,8 @@ func TestVerifyLeafHashes_Err(t *testing.T) {
 		root               []byte
 		wantErr            bool
 	}{
-		{"wrong leafHash: not namespaced", proof5, hasher, true, nID5, [][]byte{leafHash5}, root, true},
+		{"corrupt root", proof5, hasher, true, nID5, [][]byte{leafHash5}, corruptRoot, true},
+		{"wrong leafHash: not namespaced", proof5, hasher, true, nID5, [][]byte{corruptLeafHash5}, root, true},
 		{"wrong leafHash: smaller namespace", proof5, hasher, true, nID5, [][]byte{leafHash5SmallerNID}, root, true},
 		{"wong leafHash: bigger namespace", proof5, hasher, true, nID5, [][]byte{leafHash5BiggerNID}, root, true},
 		{"wrong proof.nodes: the last node has an incorrect format", proof4InvalidNodes, hasher, false, nID4, [][]byte{leafHash4}, root, true},
@@ -507,8 +512,8 @@ func TestVerifyNamespace_False(t *testing.T) {
 		args   args
 		result bool
 	}{
-		{"nID size of proof < nID size of VerifyNamespace's nmt hasher", proof4_1, args{hasher, nid4_2, [][]byte{leaf}, root2}, false},
-		{"nID size of proof > nID size of VerifyNamespace's nmt hasher", proof4_2, args{hasher, nid4_1, [][]byte{leaf}, root1}, false},
+		{"nID size of proof.nodes < nID size of VerifyNamespace's nmt hasher", proof4_1, args{hasher, nid4_2, [][]byte{leaf}, root2}, false},
+		{"nID size of proof.nodes > nID size of VerifyNamespace's nmt hasher", proof4_2, args{hasher, nid4_1, [][]byte{leaf}, root1}, false},
 		{"nID size of root < nID size of VerifyNamespace's nmt hasher", proof4_2, args{hasher, nid4_2, [][]byte{leaf}, root1}, false},
 		{"nID size of root > nID size of VerifyNamespace's nmt hasher", proof4_1, args{hasher, nid4_1, [][]byte{leaf}, root2}, false},
 		{"nID size of proof.leafHash < nID size of VerifyNamespace's nmt hasher", absenceProof9_2, args{hasher, nid9_2, [][]byte{}, root2}, false},