IgnoreMaxNS leads to false computing maxNs

[andrijamitrovic23]

@evan-forbes and @staheri14 Here is the description of the issue about computing maxNs with n.ignoreMaxNS set to true that we discussed about.

We are not sure what is the expected behavior when it comes to calculating maxNs with n.ignoreMaxNS set to true.
As we understand the expected behavior under these conditions is to choose a maxNs that is less than n.precomputedMaxNs if possible. If this is the case there might be an issue with computing maxNs here, which can lead to setting it to n.precomputedMaxNs even if it could be set to a namespaceId that is smaller than n.precomputedMaxNs .

If we assume the following:

• n.ignoreMaxNS = true
• leftMinNs != n.precomputedMaxNs
• rightMaxNs = n.precomputedMaxNs
• rightMinNs < n.precomputedMaxNs
• rightMinNs>leftMaxNs .

Than the maxNs will be set to n.precomputedMaxNs even if it should be set to rightMinNs because it is the largest namespaceId smaller than n.precomputedMaxNs.

Example with numbers (presented also in the image at the end):
Lets assume that following:

• precomputedMaxNs = 10
• ignoreMaxNS = true
• leftNode: left{minNs: 7; maxNs:8 }
• rightNode: right{minNs: 9; maxNs:10 }

Based on this logic in HashNode the minNs and `maxNs' for the node that is being calculated will take the following values:

• minNs = 7 (because it is the lowest value)
• maxNs = 10 or the precomputedMaxNs (because the else branch of the if statement will be executed and there 10 will obviously be chosen even if the right.minNs is larger then left.maxNs but not equal to precomputedMaxNs ).

This numerical example with the current behavior and the behavior we expect is graphically presented in the following image.

[andrijamitrovic23]

I have wrote a test for this case. The test is located in an forked nmt repo in the hasher_test.go file. It is named Test_IgnoreMaxNamespace_HashNode.

[ivan-gavran]

Also, as you mentioned in our online discussion, there seems to exist an assumption for usages of the libraries that

By construction, either both the min and max namespace IDs of a node will be PARITY_SHARE_NAMESPACE_ID, or neither will: if r.n_min is PARITY_SHARE_NAMESPACE_ID, so must r.n_max

(quoting from the outdated spec)

[staheri14]

Thank you for providing more details regarding the IgnoreMaxNS issue.
To simplify the code discussion, we may consider the following simplified version of the code snippet in here which would be:

maxNs := max(leftMaxNs, rightMaxNs)
if n.ignoreMaxNs {
	if n.precomputedMaxNs.Equal(rightMinNs) { // if the right child contains only parity shares
		maxNs = leftMaxNs
	}
}

Thus, as mentioned in this issue, the maxNs is always chosen from leftMaxNs or rightMaxNs but not any of the leftMinNs and rightMinNs.

I think, even if we were to fall back to leftMinNs and rightMinNs to choose the next available max value (when the ignoreMaxNs is true), neither leftMinNs nor rightMinNs will ever be chosen as the maximum value due to the nature of the data items that NMTs represent in Celestia. This is due to the fact that, by design, the minimum and maximum namespace IDs of a node will both be PARITY_SHARE_NAMESPACE_ID or neither will be (except for the root). It was also mentioned in this comment.

As such, the example provided in the issue description would not happen while constructing NMTs from Celestia block data.

However, to simplify the ignoreMaxNs logic and make it easier to understand and debug, we could allow the maximum value to be also chosen from leftMinNs and rightMinNs. My understanding is that adding this extra logic would not affect the namespace ID range in the NMTs constructed from Celestia block data. Nevertheless, to be more sure, this needs to be further tested and verified.

@evan-forbes @liamsi would like to know your thoughts as well.

[ivan-gavran]

Thanks, @staheri14 !
So, as it seems, there are two options.

The first one would be to explicitly mention the property that by design, the minimum and maximum namespace IDs of a node will both be PARITY_SHARE_NAMESPACE_ID or neither will be (except for the root) among the assumptions of the NMT library.
That would make it easier to understand what is happening in the code, and would also make sure that nobody uses the library in a different context where the property does not hold.

The second one, as you suggest, would be to not rely on that property at all by including rightMinNs in the calculation of the maximum (as this does not seem to be too much overhead and would keep the library a bit more general).

The preferred approach is perhaps connected to NMT issue 121, where a different assumption (the one about order between leaves) is discussed.

[evan-forbes]

the second option of simplifying ignoreMaxNs seems like a good option afaiu

[ivan-gavran]

Closed by the mirror issue celestiaorg/nmt#148