Verification logic does not ensure lexicographical ordering

[liamsi]

The NMT guarantees lexicographical ordering and hence generated proofs follow this ordering as well. The verification logic does not enforce this though currently. This might not be a big deal as verification would fail if ordering is different though it makes it harder to reason about this and it is obviously better to enforce ordering there too.

@musalbas suggested to enforce ordering in the hasher directly. While it might seem better to follow the current pattern and fail much earlier (when adding data to the tree and not only later when hashing/creating the root), having the ordering enforced while hashing is better from a consistency perspective. it would also immediately resolve the ordering guarantee during verification as well.

[liamsi]

The only downside I can think of, when incorporating the ordering into the hasher, is that it will have to happen on every inner node (instead of currently every leaf only), which will make proving and verification slower (probs negligible but should be confirmed in a benchmark too).

Not really a downside but sth to keep in mind is that the hasher will need to return an error. This might affect other parts of the API as well.

[liamsi]

Note that the hasher is also exposed directly and indpependently of an NMT here:

nmt/hasher.go

Lines 22 to 54 in 7d31915

	// Sha256Namespace8FlaggedLeaf uses sha256 as a base-hasher, 8 bytes
	// for the namespace IDs and ignores the maximum possible namespace.
	//
	// Sha256Namespace8FlaggedLeaf(namespacedData) results in:
	// ns(rawData) || ns(rawData) || sha256(LeafPrefix || rawData),
	// where rawData is the leaf's data minus the namespace.ID prefix
	// (namely namespacedData[NamespaceLen:]).
	//
	// Note that different from other cryptographic hash functions, this here
	// makes assumptions on the input:
	// len(namespacedData) >= DefaultNamespaceIDLen has to hold,
	// as the first DefaultNamespaceIDLen bytes are interpreted as the namespace ID).
	// If the input does not fulfil this, we will panic.
	// The output will be of length 2*DefaultNamespaceIDLen+sha256.Size = 48 bytes.
	func Sha256Namespace8FlaggedLeaf(namespacedData []byte) []byte {
	return defaultHasher.HashLeaf(namespacedData)
	}
	// Sha256Namespace8FlaggedInner hashes inner nodes to:
	// minNID || maxNID || sha256(NodePrefix || leftRight), where leftRight consists of the full
	// left and right child node bytes, including their respective min and max namespace IDs.
	// Hence, the input has to be of size:
	// 48 = 32 + 8 + 8 = sha256.Size + 2*DefaultNamespaceIDLen bytes.
	// If the input does not fulfil this, we will panic.
	// The output will also be of length 2*DefaultNamespaceIDLen+sha256.Size = 48 bytes.
	func Sha256Namespace8FlaggedInner(leftRight []byte) []byte {
	const flagLen = DefaultNamespaceIDLen * 2
	sha256Len := defaultHasher.Size()
	left := leftRight[:flagLen+sha256Len]
	right := leftRight[flagLen+sha256Len:]
	return defaultHasher.HashNode(left, right)
	}

We should remove this code (looks like celestia-node is the only user of it and even that is about to change here . If we keep these functions there we actually must enforce the ordering in the hasher as otherwise this part of the public API can be misused.

[liamsi]

closing in favour of #95 (more actionable)