Repository: celestiaorg/nmt (go)

Issue:
Bug: Proofs of Absence can be Forged
# Bug: Proofs of Absence can be Forged

## Problem
The namespaced merkle tree exposes a `VerifyNamespace` method whose documentation states that it "verifies that the namespace is complete and no leaf of that namespace was left out in the proof."

This API allow consumers to write code like the following:

```
proof, namespaceData := getUntrustedProofFor(namespaceId)
// check that the namespaceData was all returned
if proof.VerifyNamespace(sha256.New(), namespaceId, namespaceData, n.Root()) {
    process(namespaceData)
} else {
    return errors.New("prover lied about namespace data")
}
```
Unfortunately, this code is vulnerable. A malicious prover can falsely claim that the namespace is empty, and, as long as he also provides an empty proof, the claim will be accepted. 


## Test Case

A simple test case which reproduces the issue is as follows: 
```
func TestNMT_forgeNamespaceEmptinessProof(t *testing.T) {
	data := [][]byte{
		append(namespace.ID{0}, []byte("leaf_0")...),
		append(namespace.ID{0}, []byte("leaf_1")...),
		append(namespace.ID{1}, []byte("leaf_2")...),
		append(namespace.ID{1}, []byte("leaf_3")...)}
	// Init a tree with the namespace size as well as
	// the underlying hash function:
	tree := New(sha256.New(), NamespaceIDSize(1))
	for _, d := range data {
		if err := tree.Push(d); err != nil {
			panic(fmt.Sprintf("unexpected error: %v", err))
		}
	}

	root := tree.Root()
	actualLeaves := tree.Get(namespace.ID{0})
	if len(actualLeaves) == 0 {
		t.Fatalf("Get(namespace.ID{0}) should have returned two leaves but returned none.")
	}

	forgedProof := Proof{
		start:                   0,
		end:                     0,
		nodes:                   [][]byte{},
		leafHash:                []byte{},
		isMaxNamespaceIDIgnored: true,
	}

	forged_proof_succes := forgedProof.VerifyNamespace(sha256.New(), namespace.ID{0}, [][]byte{}, root)
	if forged_proof_succes {
		t.Fatalf("Successfully verified proof that non-empty namespace was empty")
	}
}
```

## Root Cause

This behavior is introduced by the following condition [here](https://github.com/celestiaorg/nmt/blob/95e8313eb788b46b30f3f85b20fd9a40bf68d432/proof.go#L107): 
```
// empty range, proof, and data: always checks out
if len(data) == 0 && isEmptyRange && len(proof.nodes) == 0 {
    return true
}
```

## Suggested Solution

Currently, the handling of empty range proofs is not well defined. I propose to reject all proofs that do not contain at least one node in either the `proof.nodes` or `data` arguments, unless the tree is the empty. (Without this special case, it's impossible to check range proofs against the empty tree). This will change the semantics of the NMT, causing some existing test cases to fail.



Pull request description:
Bug fix: reject forged proofs of absence. Fixes (#86)
- Reject empty "proofs" of absence, except in the special case where the root doesn't cover the namespace being proved
- Add test case to catch regression
- Add test case to ensure that the absence of the zero namespace can be proved against the empty tree

<!--
Please read and fill out this form before submitting your PR.

Please make sure you have reviewed our contributors guide before submitting your
first PR.
-->

closes #86

## Overview

<!-- 
Please provide an explanation of the PR, including the appropriate context,
background, goal, and rationale. If there is an issue with this information,
please provide a tl;dr and link the issue. 
-->

## Checklist

<!-- 
Please complete the checklist to ensure that the PR is ready to be reviewed.

IMPORTANT:
PRs should be left in Draft until the below checklist is completed.
-->

- [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 3147b19..1529af3 100644
--- a/proof.go
+++ b/proof.go
@@ -104,9 +104,14 @@ func (proof Proof) VerifyNamespace(h hash.Hash, nID namespace.ID, data [][]byte,
 	}
 
 	isEmptyRange := proof.start == proof.end
-	// empty range, proof, and data: always checks out
 	if len(data) == 0 && isEmptyRange && len(proof.nodes) == 0 {
-		return true
+		// empty proofs are always rejected unless nID is outside the range of namespaces covered by the root
+		// we special case the empty root, since it purports to cover the zero namespace but does not actually
+		// include any such nodes
+		if nID.Less(min) || max.Less(nID) || bytes.Equal(root, nth.EmptyRoot()) {
+			return true
+		}
+		return false
 	}
 	gotLeafHashes := make([][]byte, 0, len(data))
 	nIDLen := nID.Size()


Test patch:
diff --git a/nmt_test.go b/nmt_test.go
index aa6b2a4..4b7cec9 100644
--- a/nmt_test.go
+++ b/nmt_test.go
@@ -596,6 +596,58 @@ func TestNamespacedMerkleTree_calculateAbsenceIndex_Panic(t *testing.T) {
 	}
 }
 
+// This test checks for a regression of https://github.com/celestiaorg/nmt/issues/86
+func TestNMT_absenceProofOfZeroNamespace_InEmptyTree(t *testing.T) {
+	tree := New(sha256.New(), NamespaceIDSize(1))
+	root := tree.Root()
+	emptyleaves, proof, err := tree.GetWithProof(namespace.ID{0})
+	if err != nil {
+		t.Fatalf("GetWithProof()  could not get namespace{0}. err: %v ", err)
+	}
+	if len(emptyleaves) != 0 {
+		t.Fatalf("Get(namespace.ID{0}) should have returned no leaves but returned %v", emptyleaves)
+	}
+	if !proof.VerifyNamespace(sha256.New(), namespace.ID{0}, emptyleaves, root) {
+		t.Fatalf("Could not verify proof of absence of namespace zero in empty tree")
+	}
+}
+
+// This test checks for a regression of https://github.com/celestiaorg/nmt/issues/86
+func TestNMT_forgedNamespaceEmptinessProof(t *testing.T) {
+	data := [][]byte{
+		append(namespace.ID{1}, []byte("leaf_0")...),
+		append(namespace.ID{1}, []byte("leaf_1")...),
+		append(namespace.ID{2}, []byte("leaf_2")...),
+		append(namespace.ID{2}, []byte("leaf_3")...)}
+	// Init a tree with the namespace size as well as
+	// the underlying hash function:
+	tree := New(sha256.New(), NamespaceIDSize(1))
+	for _, d := range data {
+		if err := tree.Push(d); err != nil {
+			panic(fmt.Sprintf("unexpected error: %v", err))
+		}
+	}
+
+	root := tree.Root()
+	actualLeaves := tree.Get(namespace.ID{1})
+	if len(actualLeaves) == 0 {
+		t.Fatalf("Get(namespace.ID{1}) should have returned two leaves but returned none.")
+	}
+
+	forgedProof := Proof{
+		start:                   0,
+		end:                     0,
+		nodes:                   [][]byte{},
+		leafHash:                []byte{},
+		isMaxNamespaceIDIgnored: true,
+	}
+
+	forgedProofSuccess := forgedProof.VerifyNamespace(sha256.New(), namespace.ID{1}, [][]byte{}, root)
+	if forgedProofSuccess {
+		t.Fatalf("Successfully verified proof that non-empty namespace was empty")
+	}
+}
+
 func TestInvalidOptions(t *testing.T) {
 	shouldPanic(t, func() {
 		_ = New(sha256.New(), InitialCapacity(-1))