-
Notifications
You must be signed in to change notification settings - Fork 899
/
retriever_quadrant.go
102 lines (92 loc) · 2.86 KB
/
retriever_quadrant.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
package eds
import (
"math/rand"
"time"
"github.com/ipfs/go-cid"
"github.com/celestiaorg/celestia-app/pkg/da"
"github.com/celestiaorg/rsmt2d"
"github.com/celestiaorg/celestia-node/share/ipld"
)
const (
// there are always 4 quadrants
numQuadrants = 4
// blockTime equals to the time with which new blocks are produced in the network.
// TODO(@Wondertan): Here we assume that the block time is a minute, but
// block time is a network wide variable/param that has to be taken from
// a proper place
blockTime = time.Minute
)
// RetrieveQuadrantTimeout defines how much time Retriever waits before
// starting to retrieve another quadrant.
//
// NOTE:
// - The whole data square must be retrieved in less than block time.
// - We have 4 quadrants from two sources(rows, cols) which equals to 8 in total.
var RetrieveQuadrantTimeout = blockTime / numQuadrants * 2
type quadrant struct {
// slice of roots to get shares from
roots []cid.Cid
// Example coordinates(x;y) of each quadrant when fetching from column roots
// ------ -------
// | Q0 | | Q1 |
// |(0;0)| |(1;0)|
// ------ -------
// | Q2 | | Q3 |
// |(0;1)| |(1;1)|
// ------ -------
x, y int
// source defines the axis(Row or Col) to fetch the quadrant from
source rsmt2d.Axis
}
// newQuadrants constructs a slice of quadrants from DAHeader.
// There are always 4 quadrants per each source (row and col), so 8 in total.
// The ordering of quadrants is random.
func newQuadrants(dah *da.DataAvailabilityHeader) []*quadrant {
// combine all the roots into one slice, so they can be easily accessible by index
daRoots := [][][]byte{
dah.RowRoots,
dah.ColumnRoots,
}
// create a quadrant slice for each source(row;col)
sources := [][]*quadrant{
make([]*quadrant, numQuadrants),
make([]*quadrant, numQuadrants),
}
for source, quadrants := range sources {
size, qsize := len(daRoots[source]), len(daRoots[source])/2
roots := make([]cid.Cid, size)
for i, root := range daRoots[source] {
roots[i] = ipld.MustCidFromNamespacedSha256(root)
}
for i := range quadrants {
// convert quadrant 1D into into 2D coordinates
x, y := i%2, i/2
quadrants[i] = &quadrant{
roots: roots[qsize*y : qsize*(y+1)],
x: x,
y: y,
source: rsmt2d.Axis(source),
}
}
}
quadrants := make([]*quadrant, 0, numQuadrants*2)
for _, qs := range sources {
quadrants = append(quadrants, qs...)
}
// shuffle quadrants to be fetched in random order
rand.Shuffle(len(quadrants), func(i, j int) { quadrants[i], quadrants[j] = quadrants[j], quadrants[i] })
return quadrants
}
// pos calculates position of a share in a data square.
func (q *quadrant) pos(rootIdx, cellIdx int) (int, int) {
cellIdx += len(q.roots) * q.x
rootIdx += len(q.roots) * q.y
switch q.source {
case rsmt2d.Row:
return rootIdx, cellIdx
case rsmt2d.Col:
return cellIdx, rootIdx
default:
panic("unknown axis")
}
}