celestiaorg / celestiaorg/rsmt2d
Public API extension proposal
- Dominant language
- Go
- Stars
- 169
- Forks
- 87
- Avg merge
- 8h 9m
- Merged PRs (30d)
- 7
Description
## Motivation and Proposal
Currently, our block data retrieving strategy is this:
1. [Choose and request some random leaves](https://github.com/lazyledger/lazyledger-core/blob/master/p2p/ipld/read.go#L42) - a quarter of all leaves.
2. Wait until only that specific quarter is received.
3. Force repairment.
The main drawback of the flow is that it does not use all the available leaves and instead optimistically relies only on a subjective random set of leaves. Instead, fetching block's data should try to retrieve all the leaves and repair block data on the go. This way, we would still fetch the same quarter, but naturally selected by network conditions and practical leaves availability on known peers/network.
So the flow will change to:
1. Request all the leaves
2. On every retrieved leaf check if we have enough for repair or wait for more.
3. Execute repair and cancel the ongoing request.
Ideally, we should support custom fetching/repairing strategies similar to [those](https://github.com/Wondertan/go-ipfs-recovery/blob/master/strategy.go#L5), but for now, we can aim to support the most efficient one. However, to accomplish this we likely need to update the rsmt2d library API.
## Implementation
> Note: leaf == share
In case we agree that the proposed flow is a go, we can think of ways to implements it. The biggest issue for fetching/retrieving logic implementation is to know "if we have enough leaves". This can be accomplished through:
* Implementing a similar 2D bitmask like the one in the repo and parts of crossword solving logic. But that's a logic duplication and overhead as two places in code are doing the same.
* Calling `RepairExtendedDataSquare` after every new leaf retrieval. This is an overhead as it's a quite expensive operation due to sanity checks with lots of allocations in square flattening and etc.
* Changing rsmt2d API to allow a user(fetching logic) to fill empty ExtenendDataSqaure leaf by leaf and to understand if that's enough for repair. This option does not require any custom logic on the user side and encapsulates it on the rsmt2d side allowing lib dev to squeeze max performance.
## New methods/funcs
```go
// EmptyExtendedDataSqaure creates an empty data square.
func EmptyExtendedDataSqaure(rowRoots, colRoots [][]byte, rsmt2d.Codec, TreeConstructorFn) *ExtendedDataSquare
// FillShare fills both erasure and data share at the specific coordinate.
// Returns true if has enough shares for repair.
// Concurrently unsafe.
func (eds *ExtendedDataSquare) FillShare(row, col uint32, data []byte) (bool, error)
// Repair attempts to repair an incomplete extended data square.
// Concurrently unsafe.
func (eds *ExtendedDataSquare() Repair() error
```
Contributor guide
Research direction
Start with the fetching flow in p2p/ipld/read.go and compare the linked recovery strategy.go with rsmt2d's current ExtendedDataSquare behavior. Evaluate the proposed EmptyExtendedDataSquare, FillShare, and Repair API and resolve the implementation trade-offs with maintainers. Done means an agreed API and compatible implementation for incremental retrieval and repair.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go
- Domain
- distributed-systems
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100