Repository: celestiaorg/nmt (go)

Issue:
overlap between empty proofs and absence proofs
## Problem
 In NMTs, an empty `proof` is defined as a proof that satisfies two conditions: (1) it contains an empty range i.e., `proof.start == proof.end`, and (2) its `nodes` field is empty. However, currently, we do not check whether `proof.leafHash == 0`. This can lead to situations where a proof can be treated as both an absence proof and an empty proof, depending on the order of operations (depends on which type is checked first). Specifically, a proof that satisfies conditions (1) and (2) but has a non-empty `leafHash` will pass both [`IsEmptyProof()`](https://github.com/celestiaorg/nmt/blob/34cf84ca83cd7596504a2e809083b82b5775bcfe/proof.go#L110) and [`IsOfAbsence()`](https://github.com/celestiaorg/nmt/blob/34cf84ca83cd7596504a2e809083b82b5775bcfe/proof.go#L68) checks.

The following test demonstrates this inconsistency:
```go
	// create an NMT with 8 sequentially namespaced leaves, numbered from 1 to 8.
	tree := exampleNMT(1, 1, 2, 3, 4, 5, 6, 7, 8)
	root, err := tree.Root()
	assert.NoError(t, err)
	dummyValue := createByteSlice(tree.treeHasher.Size(), 0x01)
	// this proof is neither a well-formed absence proof nor a well-formed empty proof
	proof := Proof{start: 1, end: 1, leafHash: dummyValue, nodes: [][]byte{}}
	assert.True(t, proof.IsOfAbsence())  // this check passes while proof is not a well-formed absence proof, this result is misleading
	assert.True(t, proof.IsEmptyProof()) // this check passes while proof is not a well-formed empty proof, this result is misleading

	// the proof is not a proper empty proof, yet it can be used as a valid empty proof
	isVerified := proof.VerifyNamespace(tree.treeHasher.baseHasher, []byte{10}, [][]byte{}, root)
	assert.True(t, isVerified)
```

Pull request:
feat!: add an additional constraint of empty leafHash field to the empty proof definition
## Overview
Closes #181
The updates made by this PR will result in a breaking change, as empty proofs with a non-empty `leafHash` field will no longer be considered valid. This means that their verification through `VerifyNamespace` will fail.
Example:
```go
nIDSize := 1
tree := exampleNMT(nIDSize, 1, 2, 3, 4)
root, err := tree.Root()
require.NoError(t, err)
hasher := 
proof := Proof{
		start:    0,
		end:      0,
		nodes:    nil,
		leafHash: tree.leafHashes[0],
	}

res := proof.VerifyNamespace(tree.treeHasher.baseHasher, []byte{0}, [][]byte{}, root)
require.True(res) // this is false with the changes in this PR, however, previously, it was true
```

## 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/proof.go b/proof.go
index 6fb8aee..bc9c179 100644
--- a/proof.go
+++ b/proof.go
@@ -108,7 +108,7 @@ func NewAbsenceProof(proofStart, proofEnd int, proofNodes [][]byte, leafHash []b
 
 // IsEmptyProof checks whether the proof corresponds to an empty proof as defined in NMT specifications https://github.com/celestiaorg/nmt/blob/master/docs/spec/nmt.md.
 func (proof Proof) IsEmptyProof() bool {
-	return proof.start == proof.end && len(proof.nodes) == 0
+	return proof.start == proof.end && len(proof.nodes) == 0 && len(proof.leafHash) == 0
 }
 
 // VerifyNamespace verifies a whole namespace, i.e. 1) it verifies inclusion of


Test patch:
diff --git a/proof_test.go b/proof_test.go
index a85b93e..820df5b 100644
--- a/proof_test.go
+++ b/proof_test.go
@@ -22,36 +22,24 @@ func TestVerifyNamespace_EmptyProof(t *testing.T) {
 	require.NoError(t, err)
 
 	// build a proof for an NID that is outside the namespace range of the tree
-	// start = end = 0, nodes = empty
+	// start = end = 0, nodes = empty, leafHash = empty
 	nID0 := []byte{0}
-	validEmptyProofZeroRange, err := tree.ProveNamespace(nID0)
+	validEmptyProof, err := tree.ProveNamespace(nID0)
 	require.NoError(t, err)
 
-	// build a proof for an NID that is outside the namespace range of the tree
-	// start = end = 1, nodes = nil
-	validEmptyProofNonZeroRange, err := tree.ProveNamespace(nID0)
-	require.NoError(t, err)
-	// modify the proof range to be non-zero, it should still be valid
-	validEmptyProofNonZeroRange.start = 1
-	validEmptyProofNonZeroRange.end = 1
-
-	// build a proof for an NID that is within the namespace range of the tree
-	// start = end = 0, nodes = non-empty
+	// build a proof for an NID that is within the namespace range of the tree, then corrupt it to have a zero range
+	// start = end = 0, nodes = non-empty, leafHash = empty
 	nID1 := []byte{1}
-	zeroRangeOnlyProof, err := tree.ProveNamespace(nID1)
+	invalidEmptyProof, err := tree.ProveNamespace(nID1)
 	require.NoError(t, err)
 	// modify the proof to contain a zero range
-	zeroRangeOnlyProof.start = 0
-	zeroRangeOnlyProof.end = 0
+	invalidEmptyProof.start = 0
+	invalidEmptyProof.end = 0
 
-	// build a proof for an NID that is within the namespace range of the tree
-	// start = 0, end = 1, nodes = empty
-	emptyNodesOnlyProof, err := tree.ProveNamespace(nID1)
-	require.NoError(t, err)
-	// modify the proof nodes to be empty
-	emptyNodesOnlyProof.nodes = [][]byte{}
+	// root of an empty tree
+	emptyRoot := tree.treeHasher.EmptyRoot()
+	hasher := tree.treeHasher.baseHasher
 
-	hasher := sha256.New()
 	type args struct {
 		proof  Proof
 		hasher hash.Hash
@@ -66,12 +54,18 @@ func TestVerifyNamespace_EmptyProof(t *testing.T) {
 		want              bool
 		isValidEmptyProof bool
 	}{
-		{"valid empty proof  with (start == end) == 0 and empty leaves", args{validEmptyProofZeroRange, hasher, nID0, [][]byte{}, root}, true, true},
-		{"valid empty proof with (start == end) != 0 and empty leaves", args{validEmptyProofNonZeroRange, hasher, nID0, [][]byte{}, root}, true, true},
-		{"valid empty proof  with (start == end) == 0 and non-empty leaves", args{validEmptyProofZeroRange, hasher, nID0, [][]byte{{1}}, root}, false, true},
-		{"valid empty proof with (start == end) != 0 and non-empty leaves", args{validEmptyProofNonZeroRange, hasher, nID0, [][]byte{{1}}, root}, false, true},
-		{"invalid empty proof: start == end == 0, nodes == non-empty", args{zeroRangeOnlyProof, hasher, nID1, [][]byte{}, root}, false, false},
-		{"invalid empty proof:  start == 0, end == 1, nodes == empty", args{emptyNodesOnlyProof, hasher, nID1, [][]byte{}, root}, false, false},
+		// in the following tests, proof should always contain an empty range
+
+		// test cases for a non-empty tree hence non-empty root
+		{"valid empty proof & empty leaves & nID not in range", args{validEmptyProof, hasher, nID0, [][]byte{}, root}, true, true},
+		{"invalid empty proof & empty leaves & nID in range", args{invalidEmptyProof, hasher, nID1, [][]byte{}, root}, false, false},
+		{"valid empty proof & non-empty leaves & nID not in range", args{validEmptyProof, hasher, nID0, [][]byte{{1}}, root}, false, true},
+		{"valid empty proof & empty leaves & nID in range", args{validEmptyProof, hasher, nID1, [][]byte{}, root}, false, true},
+
+		// test cases for an empty tree hence empty root
+		{"valid empty proof & empty leaves & nID not in range ", args{validEmptyProof, hasher, nID0, [][]byte{}, emptyRoot}, true, true},
+		{"invalid empty proof & empty leaves & nID in range", args{invalidEmptyProof, hasher, nID1, [][]byte{}, emptyRoot}, false, false},
+		{"valid empty proof & non-empty leaves & nID not in range", args{validEmptyProof, hasher, nID0, [][]byte{{1}}, emptyRoot}, false, true},
 	}
 	for _, tt := range tests {
 		t.Run(tt.name, func(t *testing.T) {
@@ -578,3 +572,98 @@ func TestVerifyLeafHashes_False(t *testing.T) {
 		})
 	}
 }
+
+func TestIsEmptyProof(t *testing.T) {
+	tests := []struct {
+		name     string
+		proof    Proof
+		expected bool
+	}{
+		{
+			name: "valid empty proof",
+			proof: Proof{
+				leafHash: nil,
+				nodes:    nil,
+				start:    1,
+				end:      1,
+			},
+			expected: true,
+		},
+		{
+			name: "invalid empty proof - start != end",
+			proof: Proof{
+				leafHash: nil,
+				nodes:    nil,
+				start:    0,
+				end:      1,
+			},
+			expected: false,
+		},
+		{
+			name: "invalid empty proof - non-empty nodes",
+			proof: Proof{
+				leafHash: nil,
+				nodes:    [][]byte{{0x01}},
+				start:    1,
+				end:      1,
+			},
+			expected: false,
+		},
+		{
+			name: "invalid absence proof - non-empty leafHash",
+			proof: Proof{
+				leafHash: []byte{0x01},
+				nodes:    nil,
+				start:    1,
+				end:      1,
+			},
+			expected: false,
+		},
+	}
+
+	for _, test := range tests {
+		t.Run(test.name, func(t *testing.T) {
+			result := test.proof.IsEmptyProof()
+			assert.Equal(t, test.expected, result)
+		})
+	}
+}
+
+// TestIsEmptyProofOverlapAbsenceProof ensures there is no overlap between empty proofs and absence proofs.
+func TestIsEmptyProofOverlapAbsenceProof(t *testing.T) {
+	tests := []struct {
+		name  string
+		proof Proof
+	}{
+		{
+			name: "valid empty proof",
+			proof: Proof{
+				leafHash: nil,
+				nodes:    nil,
+				start:    1,
+				end:      1,
+			},
+		},
+		{
+			name: "valid absence proof",
+			proof: Proof{
+				leafHash: []byte{0x01, 0x02, 0x03},
+				nodes:    nil,
+				start:    1,
+				end:      1,
+			},
+		},
+	}
+	for _, test := range tests {
+		t.Run(test.name, func(t *testing.T) {
+			result := test.proof.IsEmptyProof()
+			absenceResult := test.proof.IsOfAbsence()
+			if result {
+				assert.False(t, absenceResult)
+			}
+			if absenceResult {
+				assert.False(t, result)
+			}
+		})
+	}
+}