Repository: celestiaorg/nmt (go)

Issue:
ValidateNode does not check the exact size of the non-leaf nodes
# Problem
In an NMT, non-leaf nodes all have a particular size that is `2*namespace size + hash output size`. 
The `ValidateNode` should take into account this size and validate nodes' size accordingly. However, this is not the case in the current implementation. 


# Acceptance Criteria
Incorporate the exact size check to the `ValidateNode` method together with proper unit tests. 

Pull request description:
feat!: checks the exact size of the node in HashNode
## Overview
Closes #153 (part of https://github.com/celestiaorg/nmt/issues/173)

## 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 0c2bf59..da9488d 100644
--- a/hasher.go
+++ b/hasher.go
@@ -194,12 +194,12 @@ func (n *Hasher) MustHashLeaf(ndata []byte) []byte {
 }
 
 // ValidateNodeFormat checks whether the supplied node conforms to the
-// namespaced hash format and returns an error if it does not. Specifically, it returns ErrInvalidNodeLen if the length of the node is less than the 2*namespace length which indicates it does not match the namespaced hash format.
+// namespaced hash format and returns ErrInvalidNodeLen if not.
 func (n *Hasher) ValidateNodeFormat(node []byte) (err error) {
-	totalNamespaceLen := 2 * n.NamespaceLen
+	expectedNodeLen := n.Size()
 	nodeLen := len(node)
-	if nodeLen < int(totalNamespaceLen) {
-		return fmt.Errorf("%w: got: %v, want >= %v", ErrInvalidNodeLen, nodeLen, totalNamespaceLen)
+	if nodeLen != expectedNodeLen {
+		return fmt.Errorf("%w: got: %v, want %v", ErrInvalidNodeLen, nodeLen, expectedNodeLen)
 	}
 	return nil
 }


Test patch:
diff --git a/hasher_test.go b/hasher_test.go
index 9c9a703..ea15df0 100644
--- a/hasher_test.go
+++ b/hasher_test.go
@@ -1,6 +1,7 @@
 package nmt
 
 import (
+	"bytes"
 	"crypto"
 	"crypto/sha256"
 	"errors"
@@ -64,7 +65,8 @@ func Test_namespacedTreeHasher_HashLeaf(t *testing.T) {
 }
 
 func Test_namespacedTreeHasher_HashNode(t *testing.T) {
-	sum(crypto.SHA256, []byte{NodePrefix}, []byte{0, 0, 0, 0}, []byte{1, 1, 1, 1})
+	// create a dummy hash to use as the digest of the left and right child
+	randHash := createByteSlice(crypto.SHA256.Size(), 0x01)
 	type children struct {
 		l []byte
 		r []byte
@@ -78,28 +80,37 @@ func Test_namespacedTreeHasher_HashNode(t *testing.T) {
 	}{
 		{
 			"leftmin<rightmin && leftmax<rightmax", 2,
-			children{[]byte{0, 0, 0, 0}, []byte{1, 1, 1, 1}},
-			append(
-				[]byte{0, 0, 1, 1},
-				sum(crypto.SHA256, []byte{NodePrefix}, []byte{0, 0, 0, 0}, []byte{1, 1, 1, 1})...,
-			),
+			children{
+				concat([]byte{0, 0, 0, 0}, randHash),
+				concat([]byte{1, 1, 1, 1}, randHash),
+			},
+			concat([]byte{0, 0, 1, 1}, // minNID||maxNID
+				sum(crypto.SHA256, []byte{NodePrefix}, // Hash(NodePrefix||left||right)
+					concat([]byte{0, 0, 0, 0}, randHash),
+					concat([]byte{1, 1, 1, 1}, randHash))),
 		},
 		{
 			"leftmin==rightmin && leftmax<rightmax", 2,
-			children{[]byte{0, 0, 0, 0}, []byte{0, 0, 1, 1}},
-			append(
-				[]byte{0, 0, 1, 1},
-				sum(crypto.SHA256, []byte{NodePrefix}, []byte{0, 0, 0, 0}, []byte{0, 0, 1, 1})...,
-			),
+			children{
+				concat([]byte{0, 0, 0, 0}, randHash),
+				concat([]byte{0, 0, 1, 1}, randHash),
+			},
+			concat([]byte{0, 0, 1, 1}, // minNID||maxNID
+				sum(crypto.SHA256, []byte{NodePrefix}, // Hash(NodePrefix||left||right)
+					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{[]byte{1, 1, 0, 0}, []byte{0, 0, 0, 1}},
-			append(
-				[]byte{0, 0, 0, 1},
-				sum(crypto.SHA256, []byte{NodePrefix}, []byte{1, 1, 0, 0}, []byte{0, 0, 0, 1})...,
-			),
+			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 {
@@ -124,6 +135,21 @@ func sum(hash crypto.Hash, data ...[]byte) []byte {
 	return h.Sum(nil)
 }
 
+// concat concatenates the given byte slices.
+func concat(data ...[]byte) []byte {
+	var result []byte
+	for _, d := range data {
+		result = append(result, d...)
+	}
+
+	return result
+}
+
+// createByteSlice returns a byte slice of length n with all bytes set to b.
+func createByteSlice(n int, b byte) []byte {
+	return bytes.Repeat([]byte{b}, n)
+}
+
 func TestNamespaceHasherWrite(t *testing.T) {
 	tt := []struct {
 		name         string
@@ -196,6 +222,8 @@ func TestNamespaceHasherSum(t *testing.T) {
 }
 
 func TestHashNode_ChildrenNamespaceRange(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 {
 		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
@@ -210,19 +238,28 @@ func TestHashNode_ChildrenNamespaceRange(t *testing.T) {
 	}{
 		{
 			"left.maxNs>right.minNs", 2,
-			children{[]byte{0, 0, 1, 1}, []byte{0, 0, 1, 1}},
+			children{
+				concat([]byte{0, 0, 1, 1}, randHash),
+				concat([]byte{0, 0, 1, 1}, randHash),
+			},
 			true, // this test case should emit an error since in an ordered NMT, left.maxNs cannot be greater than right.minNs
 			ErrUnorderedSiblings,
 		},
 		{
 			"left.maxNs=right.minNs", 2,
-			children{[]byte{0, 0, 1, 1}, []byte{1, 1, 2, 2}},
+			children{
+				concat([]byte{0, 0, 1, 1}, randHash),
+				concat([]byte{1, 1, 2, 2}, randHash),
+			},
 			false,
 			nil,
 		},
 		{
 			"left.maxNs<right.minNs", 2,
-			children{[]byte{0, 0, 1, 1}, []byte{2, 2, 3, 3}},
+			children{
+				concat([]byte{0, 0, 1, 1}, randHash),
+				concat([]byte{2, 2, 3, 3}, randHash),
+			},
 			false,
 			nil,
 		},
@@ -277,6 +314,9 @@ func TestValidateSiblingsNamespaceOrder(t *testing.T) {
 }
 
 func TestValidateNodeFormat(t *testing.T) {
+	hashValue := createByteSlice(sha256.Size, 0x01)
+	minNID := createByteSlice(2, 0x00)
+	maxNID := createByteSlice(2, 0x01)
 	tests := []struct {
 		name    string
 		nIDLen  namespace.IDSize
@@ -286,21 +326,39 @@ func TestValidateNodeFormat(t *testing.T) {
 		wantErr bool
 		errType error
 	}{
-		{ // valid node
+		{
 			"valid node",
 			2,
-			[]byte{0, 0},
-			[]byte{1, 1},
-			[]byte{1, 2, 3, 4},
+			minNID,
+			maxNID,
+			hashValue,
 			false,
 			nil,
 		},
-		{ // mismatched namespace size
-			"invalid node: length",
+		{
+			"invalid node: length < 2 * namespace size",
 			2,
-			[]byte{0},
-			[]byte{1},
-			[]byte{0},
+			minNID,
+			[]byte{},
+			[]byte{},
+			true,
+			ErrInvalidNodeLen,
+		},
+		{
+			"invalid node: length < 2 * namespace Size + hash size",
+			2,
+			minNID,
+			maxNID,
+			[]byte{},
+			true,
+			ErrInvalidNodeLen,
+		},
+		{
+			"invalid node: length > 2 * namespace size + hash size",
+			2,
+			minNID,
+			maxNID,
+			concat(hashValue, []byte{1}),
 			true,
 			ErrInvalidNodeLen,
 		},
@@ -415,6 +473,8 @@ func TestHashLeafWithIsNamespacedData(t *testing.T) {
 
 // TestHashNode_ErrorsCheck checks that the HashNode emits error only on invalid inputs. It also checks whether the returned error types are correct.
 func TestHashNode_ErrorsCheck(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 {
 		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
@@ -429,31 +489,46 @@ func TestHashNode_ErrorsCheck(t *testing.T) {
 	}{
 		{
 			"left.maxNs<right.minNs", 2,
-			children{[]byte{0, 0, 1, 1}, []byte{2, 2, 3, 3}},
+			children{
+				concat([]byte{0, 0, 1, 1}, randHash),
+				concat([]byte{2, 2, 3, 3}, randHash),
+			},
 			false,
 			nil,
 		},
 		{
 			"left.maxNs=right.minNs", 2,
-			children{[]byte{0, 0, 1, 1}, []byte{1, 1, 2, 2}},
+			children{
+				concat([]byte{0, 0, 1, 1}, randHash),
+				concat([]byte{1, 1, 2, 2}, randHash),
+			},
 			false,
 			nil,
 		},
 		{
 			"left.maxNs>right.minNs", 2,
-			children{[]byte{0, 0, 1, 1}, []byte{0, 0, 1, 1}},
+			children{
+				concat([]byte{0, 0, 1, 1}, randHash),
+				concat([]byte{0, 0, 1, 1}, randHash),
+			},
 			true,
 			ErrUnorderedSiblings,
 		},
 		{
-			"len(left)<NamespaceLen", 2,
-			children{[]byte{0, 0, 1}, []byte{2, 2, 3, 3}},
+			"len(left)<hasher.Size", 2,
+			children{
+				[]byte{0, 0, 1},
+				concat([]byte{2, 2, 3, 3}, randHash),
+			},
 			true,
 			ErrInvalidNodeLen,
 		},
 		{
-			"len(right)<NamespaceLen", 2,
-			children{[]byte{0, 0, 1, 1}, []byte{2, 2, 3}},
+			"len(right)<hasher.Size", 2,
+			children{
+				concat([]byte{0, 0, 1, 1}, randHash),
+				[]byte{2, 2, 3},
+			},
 			true,
 			ErrInvalidNodeLen,
 		},
@@ -560,6 +635,8 @@ func TestSum_Err(t *testing.T) {
 
 // TestValidateNodes checks that the ValidateNodes method only emits error on invalid inputs. It also checks whether the returned error types are correct.
 func TestValidateNodes(t *testing.T) {
+	// create a dummy hash to use as the digest of the left and right child
+	randHash := createByteSlice(sha256.Size, 0x01)
 	tests := []struct {
 		name    string
 		nIDLen  namespace.IDSize
@@ -571,24 +648,24 @@ func TestValidateNodes(t *testing.T) {
 		{
 			"left.maxNs<right.minNs",
 			2,
-			[]byte{0, 0, 1, 1},
-			[]byte{2, 2, 3, 3},
+			concat([]byte{0, 0, 1, 1}, randHash),
+			concat([]byte{2, 2, 3, 3}, randHash),
 			false,
 			nil,
 		},
 		{
 			"left.maxNs=right.minNs",
 			2,
-			[]byte{0, 0, 1, 1},
-			[]byte{1, 1, 2, 2},
+			concat([]byte{0, 0, 1, 1}, randHash),
+			concat([]byte{1, 1, 2, 2}, randHash),
 			false,
 			nil,
 		},
 		{
 			"left.maxNs>right.minNs",
 			2,
-			[]byte{0, 0, 1, 1},
-			[]byte{0, 0, 1, 1},
+			concat([]byte{0, 0, 1, 1}, randHash),
+			concat([]byte{0, 0, 1, 1}, randHash),
 			true,
 			ErrUnorderedSiblings,
 		},
@@ -596,13 +673,13 @@ func TestValidateNodes(t *testing.T) {
 			"len(left)<NamespaceLen",
 			2,
 			[]byte{0, 0, 1},
-			[]byte{2, 2, 3, 3},
+			concat([]byte{2, 2, 3, 3}, randHash),
 			true,
 			ErrInvalidNodeLen,
 		},
 		{
 			"len(right)<NamespaceLen", 2,
-			[]byte{0, 0, 1, 1},
+			concat([]byte{0, 0, 1, 1}, randHash),
 			[]byte{2, 2, 3},
 			true,
 			ErrInvalidNodeLen,