Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

overlap between empty proofs and absence proofs #181

Closed
staheri14 opened this issue Apr 24, 2023 · 0 comments · Fixed by #192
Closed

overlap between empty proofs and absence proofs #181

staheri14 opened this issue Apr 24, 2023 · 0 comments · Fixed by #192
Assignees
Labels
invalid This doesn't seem right

Comments

@staheri14
Copy link
Contributor

staheri14 commented Apr 24, 2023

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() and IsOfAbsence() checks.

The following test demonstrates this inconsistency:

	// 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)
@staheri14 staheri14 added the invalid This doesn't seem right label Apr 24, 2023
@staheri14 staheri14 self-assigned this Apr 25, 2023
staheri14 added a commit that referenced this issue May 8, 2023
…pty proof definition (#192)

## 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
invalid This doesn't seem right
Projects
None yet
1 participant