Define how to shard the chain data for partial nodes

[liamsi]

Summary

Quoting celestiaorg/celestia-node#1133:

Partial storage nodes are nodes that only store some of the blocks in the blockchain, and can be queried by any other nodes (including light clients and other partial nodes) to download data from parts of the chain.

This issue is about the question on how to structure the data sharding part. This will then inform how DAS light clients will actually discover the storage nodes that have the data they are sampling.

Context

For our MVP we took a naive unstructured approach: partial nodes can just store whatever shares they want or download and even the nodes that sample re-announce that they have these shares and serve those. Theoretically this is really appealing: assuming that there are enough light clients in the network this means that everyone can reconstruct the block by finding them. It turns out that relying on this property only is not practical as announcing to a DHT on share-level takes too long and is too granular. Hence, we want a more structured approach where the partial nodes store part of the chain (whole blocks instead of a part of each block).

Details

Two proposals where made in celestiaorg/celestia-node#1133. We need to decide on a concrete approach and spec it out. This can be broken up in two tasks which are highly related:

• Decide on how to shard the data / the chain
• Define a protocol how DAS nodes can discover / find the nodes which have the data they are looking for