-
Notifications
You must be signed in to change notification settings - Fork 278
/
share_splitting.go
143 lines (126 loc) · 4.95 KB
/
share_splitting.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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
package shares
import (
"errors"
"fmt"
"sort"
"github.com/celestiaorg/celestia-app/pkg/appconsts"
coretypes "github.com/tendermint/tendermint/types"
"golang.org/x/exp/maps"
)
var (
ErrIncorrectNumberOfIndexes = errors.New(
"number of indexes is not identical to the number of blobs",
)
ErrUnexpectedFirstBlobShareIndex = errors.New(
"the first blob started at an unexpected index",
)
)
// Split converts block data into encoded shares, optionally using share indexes
// that are encoded as wrapped transactions. Most use cases out of this package
// should use these share indexes and therefore set useShareIndexes to true.
func Split(data coretypes.Data, useShareIndexes bool) ([]Share, error) {
if data.SquareSize == 0 || !isPowerOf2(data.SquareSize) {
return nil, fmt.Errorf("square size is not a power of two: %d", data.SquareSize)
}
wantShareCount := int(data.SquareSize * data.SquareSize)
currentShareCount := 0
txShares, pfbTxShares, _ := SplitTxs(data.Txs)
currentShareCount += len(txShares) + len(pfbTxShares)
// blobIndexes will be nil if we are working with a list of txs that do not
// have a blob index. This preserves backwards compatibility with old blocks
// that do not follow the non-interactive defaults
blobIndexes := ExtractShareIndexes(data.Txs)
sort.Slice(blobIndexes, func(i, j int) bool { return blobIndexes[i] < blobIndexes[j] })
var padding []Share
if len(data.Blobs) > 0 {
blobShareStart, _ := NextMultipleOfBlobMinSquareSize(
currentShareCount,
SparseSharesNeeded(uint32(len(data.Blobs[0].Data))),
int(data.SquareSize),
)
// force blobSharesStart to be the first share index
if len(blobIndexes) != 0 && useShareIndexes {
blobShareStart = int(blobIndexes[0])
}
padding = NamespacePaddingShares(appconsts.ReservedPaddingNamespaceID, blobShareStart-currentShareCount)
}
currentShareCount += len(padding)
if blobIndexes != nil && int(blobIndexes[0]) < currentShareCount {
return nil, ErrUnexpectedFirstBlobShareIndex
}
blobShares, err := SplitBlobs(currentShareCount, blobIndexes, data.Blobs, useShareIndexes)
if err != nil {
return nil, err
}
currentShareCount += len(blobShares)
tailShares := TailPaddingShares(wantShareCount - currentShareCount)
shares := make([]Share, 0, data.SquareSize*data.SquareSize)
shares = append(append(append(append(append(
shares,
txShares...),
pfbTxShares...),
padding...),
blobShares...),
tailShares...)
return shares, nil
}
// ExtractShareIndexes iterates over the transactions and extracts the share
// indexes from wrapped transactions. It returns nil if the transactions are
// from an old block that did not have share indexes in the wrapped txs.
func ExtractShareIndexes(txs coretypes.Txs) []uint32 {
var shareIndexes []uint32
for _, rawTx := range txs {
if indexWrappedTxs, isIndexWrapped := coretypes.UnmarshalIndexWrapper(rawTx); isIndexWrapped {
// Since share index == 0 is invalid, it indicates that we are
// attempting to extract share indexes from txs that do not have any
// due to them being old. here we return nil to indicate that we are
// attempting to extract indexes from a block that doesn't support
// it. It checks for 0 because if there is a message in the block,
// then there must also be a tx, which will take up at least one
// share.
if len(indexWrappedTxs.ShareIndexes) == 0 {
return nil
}
shareIndexes = append(shareIndexes, indexWrappedTxs.ShareIndexes...)
}
}
return shareIndexes
}
func SplitTxs(txs coretypes.Txs) (txShares []Share, pfbShares []Share, shareRanges map[coretypes.TxKey]ShareRange) {
txWriter := NewCompactShareSplitter(appconsts.TxNamespaceID, appconsts.ShareVersionZero)
pfbTxWriter := NewCompactShareSplitter(appconsts.PayForBlobNamespaceID, appconsts.ShareVersionZero)
for _, tx := range txs {
if _, isIndexWrapper := coretypes.UnmarshalIndexWrapper(tx); isIndexWrapper {
pfbTxWriter.WriteTx(tx)
} else {
txWriter.WriteTx(tx)
}
}
txShares, txMap := txWriter.Export(0)
pfbShares, pfbMap := pfbTxWriter.Export(len(txShares))
return txShares, pfbShares, mergeMaps(txMap, pfbMap)
}
func SplitBlobs(cursor int, indexes []uint32, blobs []coretypes.Blob, useShareIndexes bool) ([]Share, error) {
if useShareIndexes && len(indexes) != len(blobs) {
return nil, ErrIncorrectNumberOfIndexes
}
writer := NewSparseShareSplitter()
for i, blob := range blobs {
if err := writer.Write(blob); err != nil {
return nil, err
}
if useShareIndexes && len(indexes) > i+1 {
paddedShareCount := int(indexes[i+1]) - (writer.Count() + cursor)
writer.WriteNamespacedPaddedShares(paddedShareCount)
}
}
return writer.Export(), nil
}
// mergeMaps merges two maps into a new map. If there are any duplicate keys,
// the value in the second map takes precedence.
func mergeMaps(mapOne, mapTwo map[coretypes.TxKey]ShareRange) map[coretypes.TxKey]ShareRange {
merged := make(map[coretypes.TxKey]ShareRange, len(mapOne)+len(mapTwo))
maps.Copy(merged, mapOne)
maps.Copy(merged, mapTwo)
return merged
}