Repository: celestiaorg/nmt (go)

Issue:
feat: verify the range of the namespace IDs of left and right nodes in the Hasher 
# Problem
The [ `Hasher`](https://github.com/celestiaorg/nmt/blob/b04eea51d193f2fa33af6c017979a1516b6865ef/hasher.go#L155) implementation does not verify the range of namespace IDs in the left and right nodes with respect to each other, which is crucial for proper ordering of leaves based on their namespace IDs and for detecting invalidly constructed trees and proofs.

Quoting from Lazy Ledger paper:
> An adversarial consensus node may attempt to produce a block that contains a Merkle tree with children that are not ordered correctly. To prevent this, we can set a condition in nsHash such that there is no valid hash when leftMaxNs ≥ rightMinNs, and thus there would be no valid Merkle root for incorrectly ordered children

The issue was identified as part of https://github.com/celestiaorg/celestia-app/issues/1296
# Acceptance Criteria
- [ ] To modify the [`Hasher`](https://github.com/celestiaorg/nmt/blob/b04eea51d193f2fa33af6c017979a1516b6865ef/hasher.go#L155) implementation by incorporating this additional namespace ID range check for the supplied children nodes. Possibly, the `Hasher` can return an error for invalid inputs. Subsequent refactor needs to take place to properly consume this change.

Pull request description:
feat: verify the range of the namespace IDs of the children in the HashNode
## Overview
This PR closes #95. 
Inline with https://github.com/celestiaorg/celestia-app/issues/1296.

The implementation of this pull request does not exactly follow the original suggestion in the LazyLedge paper. Specifically, it does not treat `leftMaxNs = rightMinNs` as a violation of leaf ordering. The reason for this is that a namespace may span across multiple subtrees.
cc: @liamsi  

Quoting from the article:
> An adversarial consensus node may attempt to produce a block that contains a Merkle tree with children that are not ordered correctly. To prevent this, we can set a condition in nsHash such that there is no valid hash when **leftMaxNs ≥ rightMinNs**, and thus there would be no valid Merkle root for incorrectly ordered children

## 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 e3074ba..d87ded9 100644
--- a/hasher.go
+++ b/hasher.go
@@ -86,7 +86,9 @@ func (n *Hasher) Sum([]byte) []byte {
 	case NodePrefix:
 		flagLen := int(n.NamespaceLen) * 2
 		sha256Len := n.baseHasher.Size()
-		return n.HashNode(n.data[:flagLen+sha256Len], n.data[flagLen+sha256Len:])
+		leftChild := n.data[:flagLen+sha256Len]
+		rightChild := n.data[flagLen+sha256Len:]
+		return n.HashNode(leftChild, rightChild)
 	default:
 		panic("nmt node type wasn't set")
 	}
@@ -135,19 +137,23 @@ func (n *Hasher) HashLeaf(leaf []byte) []byte {
 
 // HashNode calculates a namespaced hash of a node using the supplied left and
 // right children. The input values, "left" and "right," are namespaced hash
-// values with the format "minNID || maxNID || hash." By default, the normal
-// namespace hash calculation is followed, which is "res = min(left.minNID,
-// right.minNID) || max(left.maxNID, 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 the namespace IDs available in the range of
-// its left and right children (i.e., max(left.minNID, left.maxNID ,
-// right.minNID, right.maxNID)), which is not equal to the maximum possible
-// namespace ID value. If such a namespace ID does not exist, the maximum NID is
-// calculated as normal, i.e., "res.maxNID = max(left.maxNID , right.maxNID).
+// values with the format "minNID || maxNID || hash." The HashNode function may
+// panic if the inputs provided are invalid, i.e., when left and right are not
+// in the namespaced hash format or when left.maxNID is greater than
+// right.minNID. To prevent panicking, it is advisable to check these criteria
+// before calling the HashNode function. By default, the normal namespace hash
+// calculation is followed, which is "res = min(left.minNID, right.minNID) ||
+// max(left.maxNID, 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 the namespace
+// IDs available in the range of its left and right children (i.e.,
+// max(left.minNID, left.maxNID , right.minNID, right.maxNID)), which is not
+// equal to the maximum possible namespace ID value. If such a namespace ID does
+// not exist, the maximum NID is calculated as normal, i.e., "res.maxNID =
+// max(left.maxNID , right.maxNID).
 func (n *Hasher) HashNode(left, right []byte) []byte {
 	h := n.baseHasher
 	h.Reset()
@@ -158,6 +164,13 @@ func (n *Hasher) HashNode(left, right []byte) []byte {
 	leftMinNs, leftMaxNs := left[:n.NamespaceLen], left[n.NamespaceLen:flagLen]
 	rightMinNs, rightMaxNs := right[:n.NamespaceLen], right[n.NamespaceLen:flagLen]
 
+	// check the namespace range of the left and right children
+	rightMinNID := namespace.ID(rightMinNs)
+	leftMaxNID := namespace.ID(leftMaxNs)
+	if rightMinNID.Less(leftMaxNID) {
+		panic("nodes are out of order: the maximum namespace of the left child is greater than the min namespace of the right child")
+	}
+
 	minNs := min(leftMinNs, rightMinNs)
 	var maxNs []byte
 	if n.ignoreMaxNs && n.precomputedMaxNs.Equal(leftMinNs) {


Test patch:
diff --git a/hasher_test.go b/hasher_test.go
index 1574068..6f025bc 100644
--- a/hasher_test.go
+++ b/hasher_test.go
@@ -89,14 +89,6 @@ func Test_namespacedTreeHasher_HashNode(t *testing.T) {
 				sum(crypto.SHA256, []byte{NodePrefix}, []byte{0, 0, 0, 0}, []byte{0, 0, 1, 1})...,
 			),
 		},
-		{
-			"leftmin==rightmin && leftmax>rightmax", 2,
-			children{[]byte{0, 0, 1, 1}, []byte{0, 0, 0, 1}},
-			append(
-				[]byte{0, 0, 1, 1},
-				sum(crypto.SHA256, []byte{NodePrefix}, []byte{0, 0, 1, 1}, []byte{0, 0, 0, 1})...,
-			),
-		},
 		// XXX: can this happen in practice? or is this an invalid state?
 		{
 			"leftmin>rightmin && leftmax<rightmax", 2,
@@ -197,3 +189,46 @@ func TestNamespaceHasherSum(t *testing.T) {
 		})
 	}
 }
+
+func TestHashNode_ChildrenNamespaceRange(t *testing.T) {
+	type children struct {
+		l []byte // namespace hash of the left child with the format of MinNs||MaxNs||h
+		r []byte // namespace hash of the right child with the format of MinNs||MaxNs||h
+	}
+
+	tests := []struct {
+		name      string
+		nidLen    namespace.IDSize
+		children  children
+		wantPanic bool // whether the test should panic or nor
+	}{
+		{
+			"left.maxNs>right.minNs", 2,
+			children{[]byte{0, 0, 1, 1}, []byte{0, 0, 1, 1}},
+			true, // this test case should panic since in an ordered NMT, left.maxNs cannot be greater than right.minNs
+		},
+		{
+			"left.maxNs=right.minNs", 2,
+			children{[]byte{0, 0, 1, 1}, []byte{1, 1, 2, 2}},
+			false,
+		},
+		{
+			"left.maxNs<right.minNs", 2,
+			children{[]byte{0, 0, 1, 1}, []byte{2, 2, 3, 3}},
+			false,
+		},
+	}
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			defer func() {
+				gotPanic := false
+				if r := recover(); r != nil { // here we check whether panic happened
+					gotPanic = true
+				}
+				assert.Equal(t, tt.wantPanic, gotPanic)
+			}()
+			n := NewNmtHasher(sha256.New(), tt.nidLen, false)
+			n.HashNode(tt.children.l, tt.children.r)
+		})
+	}
+}