Repository: celestiaorg/nmt
Pull request #116 (2023-03-01 00:01:47)

feat:  check the namespace ID range of the leafHash in an absence proof to ensure soundness
## Overview

Addresses the issue set out in #115.

## 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


codecov[bot]: # [Codecov](https://codecov.io/gh/celestiaorg/nmt/pull/116?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) Report
> Merging [#116](https://codecov.io/gh/celestiaorg/nmt/pull/116?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) (299efc2) into [master](https://codecov.io/gh/celestiaorg/nmt/commit/4276d172f18c87ebdd18da0cc4b758f0dd164118?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) (4276d17) will **decrease** coverage by `0.41%`.
> The diff coverage is `33.33%`.

```diff
@@            Coverage Diff             @@
##           master     #116      +/-   ##
==========================================
- Coverage   96.31%   95.90%   -0.41%     
==========================================
  Files           6        6              
  Lines         461      464       +3     
==========================================
+ Hits          444      445       +1     
- Misses         11       12       +1     
- Partials        6        7       +1     
```


| [Impacted Files](https://codecov.io/gh/celestiaorg/nmt/pull/116?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) | Coverage Δ | |
|---|---|---|
| [proof.go](https://codecov.io/gh/celestiaorg/nmt/pull/116?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg#diff-cHJvb2YuZ28=) | `94.73% <33.33%> (-2.01%)` | :arrow_down: |

Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg)


Patch:
diff --git a/nmt.go b/nmt.go
index b6bb2c4..fc96906 100644
--- a/nmt.go
+++ b/nmt.go
@@ -333,9 +333,8 @@ func (n *NamespacedMerkleTree) GetWithProof(nID namespace.ID) ([][]byte, Proof,
 }
 
 // calculateAbsenceIndex returns the index of a leaf of the tree that 1) its
-// namespace ID is the largest namespace ID less than nid and 2) the namespace
-// ID of the leaf to the left of it is smaller than the nid 3) the namespace ID
-// of the leaf to the right of it is larger than nid.
+// namespace ID is the smallest namespace ID larger than nID and 2) the
+// namespace ID of the leaf to the left of it is smaller than the nID.
 func (n *NamespacedMerkleTree) calculateAbsenceIndex(nID namespace.ID) int {
 	nidSize := n.treeHasher.NamespaceSize()
 	var prevLeaf []byte
diff --git a/proof.go b/proof.go
index 6b42c2b..0d6d7e3 100644
--- a/proof.go
+++ b/proof.go
@@ -143,6 +143,13 @@ func (proof Proof) VerifyNamespace(h hash.Hash, nID namespace.ID, data [][]byte,
 	nIDLen := nID.Size()
 	if proof.IsOfAbsence() {
 		gotLeafHashes = append(gotLeafHashes, proof.leafHash)
+		// conduct some sanity checks:
+		leafMinNID := namespace.ID(proof.leafHash[:nIDLen])
+		if !nID.Less(leafMinNID) {
+			// leafHash.minNID  must be greater than nID
+			return false
+		}
+
 	} else {
 		// collect leaf hashes from provided data and do some sanity checks:
 		hashLeafFunc := nth.HashLeaf
diff --git a/spec/nmt.md b/spec/nmt.md
index f3f7f9b..f2fc012 100644
--- a/spec/nmt.md
+++ b/spec/nmt.md
@@ -126,9 +126,10 @@ As an example, the namespace proof for `nID = 0` for the NMT of Figure 1 (which
 
 ### Verification of NMT Absence Proof
 
-An NMT absence proof is deemed valid if 
-1) The verification of Merkle inclusion proof of the returned leaf is valid.  
-2) It satisfies the proof completeness as explained in the [Verification of NMT Inclusion Proof](#verification-of-nmt-inclusion-proof).
+An NMT absence proof is deemed valid if it meets the following:
+1) The minimum namespace ID of the leaf in the proof is greater than the queried `nID`. 
+2) The verification of Merkle inclusion proof of the returned leaf is valid.  
+3) It satisfies the proof completeness as explained in the [Verification of NMT Inclusion Proof](#verification-of-nmt-inclusion-proof).
 Note that hash of the leaf does not have to be verified against the underlying message.
 
 ### Verification of Empty NMT proof


Test patch:
diff --git a/proof_test.go b/proof_test.go
index 65b7ca7..8a29276 100644
--- a/proof_test.go
+++ b/proof_test.go
@@ -83,6 +83,14 @@ func TestProof_VerifyNamespace_False(t *testing.T) {
 	}
 	pushedZeroNs := n.Get([]byte{0, 0, 0})
 	pushedLastNs := n.Get([]byte{0, 0, 8})
+
+	// an invalid absence proof for an existing namespace ID (2) in the constructed tree
+	leafIndex := 3
+	inclusionProofOfLeafIndex := rangeProof(t, n, leafIndex, leafIndex+1)
+	n.computeLeafHashesIfNecessary()
+	leafHash := n.leafHashes[leafIndex] // the only data item with namespace ID = 2 in the constructed tree is at index 3
+	invalidAbsenceProof := NewAbsenceProof(leafIndex, leafIndex+1, inclusionProofOfLeafIndex, leafHash, false)
+
 	tests := []struct {
 		name  string
 		proof Proof
@@ -134,6 +142,11 @@ func TestProof_VerifyNamespace_False(t *testing.T) {
 			args{[]byte{0, 0, 0}, pushedZeroNs[:len(pushedZeroNs)-2], n.Root()},
 			false,
 		},
+		{
+			"invalid absence proof of an existing nid", invalidAbsenceProof,
+			args{[]byte{0, 0, 2}, [][]byte{}, n.Root()},
+			false,
+		},
 	}
 	for _, tt := range tests {
 		t.Run(tt.name, func(t *testing.T) {