What are the benefits of IgnoreMaxNamespace?

[rootulp]

Context

nmt/nmt.go

Lines 33 to 40 in 4276d17

	// The "IgnoreMaxNamespace" flag influences the calculation of the namespace
	// ID range for intermediate nodes in the tree. This flag signals that, when
	// determining the upper limit of the namespace ID range for a tree node,
	// the maximum possible namespace ID (equivalent to "NamespaceIDSize" bytes
	// of 0xFF, or 2^NamespaceIDSize-1) should be omitted if feasible. For a
	// more in-depth understanding of this field, refer to the "HashNode" method
	// in the "Hasher.
	IgnoreMaxNamespace bool

Candidates

It appears to reduce the range of an NMT root. Does the reduction in range of an NMT root benefit light clients? Since celestia light clients download the data availability header which contains all row roots, it knows the range of namespaces for each row so it can determine an upper bound for the range of row 2 by looking at the minimum namespace ID of row 3 (even if IgnoreMaxNamespace=false).

One other benefit: does IgnoreMaxNamespace=true reduce the size of an NMT proof by one node?

Questions

Is it necessary to support this feature?

[liamsi]

We also discussed of putting this feature into the wrapper as it is kinda confusing without the use-case/Celestia context. That said, it would make the wrapper probably even more complex and confusing too though.

[evan-forbes]

Since celestia light clients download the data availability header which contains all row roots, it knows the range of namespaces for each row so it can determine an upper bound for the range of row 2 by looking at the minimum namespace ID of row 3

afaiu, this is true, but would make the proving more complex. I'm not really sure of the tradeoff space here.

[rootulp]

Two benefits described by @liamsi

1. Proofs have one fewer node
2. The row roots of a data square in celestia-app are ordered lexicographically

1 is an optimization and 2 doesn't seem like a requirement so it may be possible to remove the IgnoreMaxNamespace feature from nmt and not add it to the nmt_wrapper

[rootulp]

@staheri14 mentioned that the Proofs returned by the NMT assume this feature is enabled so if we remove the IgnoreMaxNamespace feature, we need to confirm that proofs still work.

[rootulp]

FWIW this feature appears to have been added in 8a5e167 which doesn't list a rationale or motivating issue.

[rootulp]

Issues that become obsolete if we remove this feature:

1. IgnoreMaxNS leads to false computing maxNs #148
2. The updateMinMaxID method disregards the IgnoreMaxNamespace semantic #159

[rootulp]

No longer a candidate because celestia-node assumes the EDS row roots are constructed with IgnoreMaxNamespace=true so that it can efficiently find which row roots that correspond to a set of namespaced rows.

In other words, downstream consumers of this library make use of this option.