IPLD/NMT improvements

[Wondertan]

Right now, we store/exchange on the network redundant data that brings no benefits, and we should fix this together during BlockSync Overhaul:

• Remove prepended one byte from each NMT IPLD node body(here and here)
  • It is possible to indirectly get the NMT Node type without serializing it. We can look at the number of links and the data size to determine its type(leaf or non-leaf). Look here for an example.
• Remove additional NMT IPLD node per each leaf
  • Each nmtLeafNode links to an additional IPLD Node, while it should keep that body inside itself
  • This is needed to reduce one roundtrip for DASing operation and, in general, reduce the size of each block

[evan-forbes]

This sounds good, but I have some questions

It is possible to get NMT Node type indirectly, without serializing the type itself. WE can look at the amount of links.

would we have to know square size for that?

It is possible to get Namespace for each share encoded in inner non-leaf nodes of the NMT tree.

I think I'm missing something here. Mind elaborating on this a bit more? What if some non-leaf nodes, along with their respective leaf nodes, can't be found?

[liamsi]

Referencing this here as it is highly related: #244 (comment)

[liamsi]

And this: #244 (comment)

[Wondertan]

@liamsi, I made a separate issue out of this. Even though they are related, your comments deserve a separate issue.

[Wondertan]

#464 relies on the fact that our NMT tree looks like:

---X
-X---X
X-X-X-X
X-X-X-X

While one of the points of this issue is to make the tree look like this:

---X
-X---X
X-X-X-X

So once we fix this issue, we should also fix #464

[adlerjohn]

8 bytes additional Namespace for each share via NMT wrapper
Can be avoided if we enable once

Why can't it be avoided today? Storage format is an implementation detail. So long as you can losslessly convert between formats, it doesn't matter what it's stored as.

[liamsi]

@adlerjohn you are right. It can be avoided today. See celestiaorg/nmt#55 (comment)

[Wondertan]

@adlerjohn, it can be avoided. My understanding was that we have to store everything we commit to via nmt.Push, but I missed that we can avoid storing some pieces of shares on the fly via Visitor in nmt and add them on the fly as well. However, as pointed out in the linked nmt issue, this is somewhat hacky, and, actually, a leaky abstraction that should be avoided ideally.

[Bidon15]

Grooming 12/07/2022:

• if we are fine with the current stack, we need to have this implemented before Incentivized Testnet

[Wondertan]

We need this before incentivized testnet.

[Wondertan]

The description is now up to date