celestiaorg/nmt

ValidateInclusion function can panic if it is called with an invalid nid

Closed this issue · 1 comments

If the ValidateInclusion function is called with an nID which size is not equal to the namespace size of the proof.nodes, the function could panic.

If this happened, the the nth hasher will be constructed with a different namespace size than the one that the proof was calculated with. This could lead to a panic in verifyLeafHashes function within the HashNode at this panic. Panic ocures because validateSiblingsNamespaceOrder could return an ErrUnorderedSiblings error because:

	leftMaxNs := namespace.ID(left[n.NamespaceLen:totalNamespaceLen])
	rightMinNs := namespace.ID(right[:n.NamespaceLen])

one of the leftMaxNs or rightMinNs is wrongly sliced due to different namespace sizes at their construction and thus parsed so that the following check is true and error is returned:

	if rightMinNs.Less(leftMaxNs) {
		return fmt.Errorf("%w: the maximum namespace of the left child %x is greater than the min namespace of the right child %x", ErrUnorderedSiblings, leftMaxNs, rightMinNs)
	}

Simple check like this one in the VerifyNamespace should be enough.

I have created a test for this issue. The test has such input data that leads to the mentioned panic. Test is a part of the following PR: #156

I have just noticed (because I have created a PR for the test on the most recent commit on master) that trough error handling that was introduced after the commit that we are reviewing this panic will not happen due to error propagation. But it is still wise do do the suggested check at the beginning of the VerifyInclusion function because it will save a lot of time and resources by skipping the proof verification.

And what is more important is that the error (ErrUnorderedSiblings) that is returned is highly misleading. The wrong slicing and parsing those slices as namespace ids lead to this error, but this is not the real problem.