bug(fraud/befp): nmt can't validate a befp with out of order shares

[vgonkivs]

While working on out of order unit test for BEFP I realized that we can't prove the inclusion of lexicographically unordered shares:

Assuming an honest full node receives the eds with size 4:

N5  N2  N3  N4
N1  N6  N7  N8
N9  N10 N11 N12
N13 N14 N15 N16

where N5 > N1. . Also, this condition means that N5 is the biggest namespace within the first row.
This will mean that during the reconstruction of the 1st quadrant, we can have ErrByzantineData for the first row or col. After getting this error from the rsmt2d, the node starts collecting proofs and creating the Bad Encoding Fraud Proof. BEFP consists of the bad shares + respective nmt proofs, so at some point, the verifier has to check whether these shares are committed to the data root or not. But the verification will be failed on this step with ErrInvalidNodeNamespaceOrder. As we could not prove the inclusion of the received shares, this FN will be blocked because it could not reconstruct the data square and could not prove the BEFP.

PS. I need to perform more testing, but I'm sure that the result will be the same as I've described above.
PS/2 Changing VerifyInclusion to VerifyLeafHashes won't help either

[musalbas]

Per this discussion, there is no need to prove the inclusion of lexicographically unordered shares. Is there any recent thinking that invalidates this?

[adlerjohn]

BEFP consists of the bad shares + respective nmt proofs, so at some point, the verifier has to check whether these shares are committed to the data root or not

I think this is where the incorrect assumption is: a BEFP consists of half of the shares of a row/col, not bad shares specifically. The bad shares (e.g. an out-of-order share) can be recovered. Indeed, if the invalid block is due to a out-of-order share, then the only way for a verifier to get that shares is through recovering it.

I'm not sure why the line https://github.com/celestiaorg/nmt/blob/9adb4090697dcf4d17a5ebb60dd042312fb27b68/proof.go#L418 is related to shares though. It looks like it only checks the root at that line?

[vgonkivs]

Is there any recent thinking that invalidates this?

No, I missed the thing that it's not possible to get proofs for out-of-order shares and we should not consider this as a bug.

https://github.com/celestiaorg/nmt/blob/9adb4090697dcf4d17a5ebb60dd042312fb27b68/proof.go#L418 is related to shares though. It looks like it only checks the root at that line?

It checks the min/max namespace id and finds that max namespace is less than the min namespace but the fact that we can't get proofs from the data root where shares are out of order proves that it's not possible to get here.

[vgonkivs]

Thanks for the help @musalbas and @adlerjohn. Closing this issue as not relevant anymore