-
Notifications
You must be signed in to change notification settings - Fork 176
/
sealing_segment.go
395 lines (343 loc) · 14.7 KB
/
sealing_segment.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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
package flow
import (
"fmt"
)
const (
// expected length of a root sealing segment
rootSegmentBlocksLen = 1
// expected view of the block in a root sealing segment
rootSegmentBlockView = 0
)
// SealingSegment is the chain segment such that the last block (greatest
// height) is this snapshot's reference block and the first (least height)
// is the most recently sealed block as of this snapshot (ie. the block
// referenced by LatestSeal).
//
// In other words, the most recently incorporated seal as of the highest block
// references the lowest block. The highest block does not need to contain this
// seal.
//
// Example 1 - E seals A:
// A <- B <- C <- D <- E(SA)
// The above sealing segment's last block (E) has a seal for block A, which is
// the first block of the sealing segment.
//
// Example 2 - E contains no seals, but latest seal prior to E seals A:
// A <- B <- C <- D(SA) <- E
//
// Root sealing segments contain only one self-sealing block. All other sealing
// segments contain multiple blocks.
// The segment is in ascending height order.
//
// In addition to storing the blocks within the sealing segment, as defined above,
// the SealingSegment structure also stores any resources which are referenced
// by blocks in the segment, but not included in the payloads of blocks within
// the segment. In particular:
// - results referenced by receipts within segment payloads
// - results referenced by seals within segment payloads
// - seals which represent the latest state commitment as of a segment block
//
type SealingSegment struct {
// Blocks contains the chain segment blocks.
Blocks []*Block
// ExecutionResults contains any results which are referenced by receipts
// or seals in the sealing segment, but not included in any segment block
// payloads.
//
// Due to decoupling of execution receipts from execution results,
// it's possible that blocks from the sealing segment will be referring to
// execution results incorporated in blocks that aren't part of the segment.
ExecutionResults ExecutionResultList
// LatestSeals is a mapping from block ID to the ID of the latest seal
// incorporated as of that block.
LatestSeals map[Identifier]Identifier
// FirstSeal contains the latest seal as of the first block in the segment.
// It is needed for the `Commit` method of protocol snapshot to return the
// sealed state, when the first block contains no seal.
// If the first block in the segment contains seal, then this field is `nil`
FirstSeal *Seal
}
func (segment *SealingSegment) Highest() *Block {
return segment.Blocks[len(segment.Blocks)-1]
}
func (segment *SealingSegment) Lowest() *Block {
return segment.Blocks[0]
}
// FinalizedSeal returns the seal that seals the lowest block
// For a valid SealingSegment, it's guaranteed to be found
func (segment *SealingSegment) FinalizedSeal() (*Seal, error) {
seal, err := findFinalizedSeal(segment)
if err != nil {
return nil, err
}
// sanity check
if seal.BlockID != segment.Lowest().ID() {
return nil, fmt.Errorf("finalized seal should seal the lowest block %v, but actually is to seal %v",
segment.Lowest().ID(), seal.BlockID)
}
return seal, nil
}
func findFinalizedSeal(segment *SealingSegment) (*Seal, error) {
if isRootSegment(segment) {
return segment.FirstSeal, nil
}
return findLatestSealForLowestBlock(segment.Lowest().ID(), segment.Highest().ID(), segment.LatestSeals, segment.Blocks)
}
func isRootSegment(segment *SealingSegment) bool {
return len(segment.Blocks) == rootSegmentBlocksLen
}
// Validate validates the sealing segment structure and returns an error if
// the segment isn't valid. This is done by re-building the segment from scratch,
// re-using the validation logic already present in the SealingSegmentBuilder.
func (segment *SealingSegment) Validate() error {
// populate lookup of seals and results in the segment to satisfy builder
seals := make(map[Identifier]*Seal)
results := make(map[Identifier]*ExecutionResult)
if segment.FirstSeal != nil {
seals[segment.FirstSeal.ID()] = segment.FirstSeal
}
for _, result := range segment.ExecutionResults {
results[result.ID()] = result
}
for _, block := range segment.Blocks {
for _, result := range block.Payload.Results {
results[result.ID()] = result
}
for _, seal := range block.Payload.Seals {
seals[seal.ID()] = seal
}
}
getResult := func(resultID Identifier) (*ExecutionResult, error) {
result, ok := results[resultID]
if !ok {
return nil, fmt.Errorf("result (id=%x) not found in segment", resultID)
}
return result, nil
}
getSeal := func(blockID Identifier) (*Seal, error) {
sealID, ok := segment.LatestSeals[blockID]
if !ok {
return nil, fmt.Errorf("seal for block (id=%x) not found in segment", blockID)
}
seal, ok := seals[sealID]
if !ok {
return nil, fmt.Errorf("seal (id=%x) not found in segment at block %x", sealID, blockID)
}
return seal, nil
}
builder := NewSealingSegmentBuilder(getResult, getSeal)
for _, block := range segment.Blocks {
err := builder.AddBlock(block)
if err != nil {
return fmt.Errorf("invalid segment: %w", err)
}
}
_, err := builder.SealingSegment()
if err != nil {
return fmt.Errorf("invalid segment: %w", err)
}
return nil
}
var (
ErrSegmentMissingSeal = fmt.Errorf("sealing segment failed sanity check: missing seal referenced by segment")
ErrSegmentBlocksWrongLen = fmt.Errorf("sealing segment failed sanity check: non-root sealing segment must have at least 2 blocks")
ErrSegmentInvalidBlockHeight = fmt.Errorf("sealing segment failed sanity check: blocks must be in ascending order")
ErrSegmentResultLookup = fmt.Errorf("failed to lookup execution result")
ErrSegmentSealLookup = fmt.Errorf("failed to lookup seal")
ErrSegmentInvalidRootView = fmt.Errorf("invalid root sealing segment block view")
)
// GetResultFunc is a getter function for results by ID.
type GetResultFunc func(resultID Identifier) (*ExecutionResult, error)
// GetSealByBlockIDFunc is a getter function for seals by block ID, returning
// the latest seals incorporated as of the given block.
type GetSealByBlockIDFunc func(blockID Identifier) (*Seal, error)
// SealingSegmentBuilder is a utility for incrementally building a sealing segment.
type SealingSegmentBuilder struct {
// access to storage to read referenced by not included resources
resultLookup GetResultFunc
sealByBlockIDLookup GetSealByBlockIDFunc
// keep track of resources included in payloads
includedResults map[Identifier]struct{}
// resources to include in the sealing segment
blocks []*Block
results []*ExecutionResult
latestSeals map[Identifier]Identifier
firstSeal *Seal
}
// AddBlock appends a block to the sealing segment under construction.
func (builder *SealingSegmentBuilder) AddBlock(block *Block) error {
// sanity check: block should be 1 height higher than current highest
if !builder.isValidHeight(block) {
return fmt.Errorf("invalid block height (%d): %w", block.Header.Height, ErrSegmentInvalidBlockHeight)
}
blockID := block.ID()
// a block might contain receipts or seals that refer to results that are included in blocks
// whose height is below the first block of the segment.
// In order to include those missing results into the segment, we construct a list of those
// missing result IDs referenced by this block
missingResultIDs := make(map[Identifier]struct{})
// for the first (lowest) block, if it contains no seal, store the latest
// seal incorporated prior to the first block
if len(builder.blocks) == 0 {
if len(block.Payload.Seals) == 0 {
seal, err := builder.sealByBlockIDLookup(blockID)
if err != nil {
return fmt.Errorf("%w: %v", ErrSegmentSealLookup, err)
}
builder.firstSeal = seal
// add first seal result ID here, since it isn't in payload
missingResultIDs[seal.ResultID] = struct{}{}
}
}
// index the latest seal for this block
latestSeal, err := builder.sealByBlockIDLookup(blockID)
if err != nil {
return fmt.Errorf("%w: %v", ErrSegmentSealLookup, err)
}
builder.latestSeals[blockID] = latestSeal.ID()
// cache included results and seals
// they could be referenced in a future block in the segment
for _, result := range block.Payload.Results {
builder.includedResults[result.ID()] = struct{}{}
}
for _, receipt := range block.Payload.Receipts {
if _, ok := builder.includedResults[receipt.ResultID]; !ok {
missingResultIDs[receipt.ResultID] = struct{}{}
}
}
for _, seal := range block.Payload.Seals {
if _, ok := builder.includedResults[seal.ResultID]; !ok {
missingResultIDs[seal.ResultID] = struct{}{}
}
}
// add the missing results
for resultID := range missingResultIDs {
result, err := builder.resultLookup(resultID)
if err != nil {
return fmt.Errorf("%w: (%x) %v", ErrSegmentResultLookup, resultID, err)
}
builder.addExecutionResult(result)
builder.includedResults[resultID] = struct{}{}
}
builder.blocks = append(builder.blocks, block)
return nil
}
// AddExecutionResult adds result to executionResults
func (builder *SealingSegmentBuilder) addExecutionResult(result *ExecutionResult) {
builder.results = append(builder.results, result)
}
// SealingSegment completes building the sealing segment, validating the segment
// constructed so far, and returning it as a SealingSegment if it is valid.
func (builder *SealingSegmentBuilder) SealingSegment() (*SealingSegment, error) {
if err := builder.validateSegment(); err != nil {
return nil, fmt.Errorf("failed to validate sealing segment: %w", err)
}
return &SealingSegment{
Blocks: builder.blocks,
ExecutionResults: builder.results,
LatestSeals: builder.latestSeals,
FirstSeal: builder.firstSeal,
}, nil
}
// isValidHeight returns true block is exactly 1 height higher than the current highest block in the segment
func (builder *SealingSegmentBuilder) isValidHeight(block *Block) bool {
if builder.highest() == nil {
return true
}
return block.Header.Height == builder.highest().Header.Height+1
}
// findLatestSealForLowestBlock finds the latest seal as of the highest block for the lowest block
// it returns the latest seal and no error if found
// it returns nil and error if not found
// NOTE: only applicable for non-root sealing segments containing multiple blocks,
// root sealing segments are checked by isValidRootSegment.
// A <- B <- C <- D(seal_A) ==> valid
// A <- B <- C <- D(seal_A) <- E() ==> valid
// A <- B <- C <- D(seal_A,seal_B) ==> invalid, because latest seal is B, but lowest block is A
// A <- B <- C <- D(seal_X,seal_A) ==> valid, because it's OK for block X to be unknown
// A <- B <- C <- D(seal_A) <- E(seal_B) ==> invalid, because latest seal is B, but lowest block is A
// A(seal_A) ==> invalid, because this is impossible for non-root sealing segments
func (builder *SealingSegmentBuilder) findLatestSealForLowestBlock() error {
_, err := findLatestSealForLowestBlock(builder.lowest().ID(), builder.highest().ID(), builder.latestSeals, builder.blocks)
return err
}
func findLatestSealForLowestBlock(lowestID, highestID Identifier, latestSeals map[Identifier]Identifier, blocks []*Block) (*Seal, error) {
// get the ID of the latest seal for highest block
latestSealID := latestSeals[highestID]
// find the seal within the block payloads
// NOTE: for non-root sealing segments, it is impossible for latestSeal to be builder.FirstSeal
for i := len(blocks) - 1; i >= 0; i-- {
block := blocks[i]
// look for latestSealID in the payload
for _, seal := range block.Payload.Seals {
// if we found the latest seal, confirm it seals lowest
if seal.ID() == latestSealID {
if seal.BlockID == lowestID {
return seal, nil
}
return nil, fmt.Errorf("invalid segment: segment contain seal for block %v, but doesn't match lowest block %v",
seal.BlockID, lowestID)
}
}
// the latest seal must be found in a block that has Seal when traversing blocks
// backwards from higher height to lower height.
// otherwise, the sealing segment is invalid
if len(block.Payload.Seals) > 0 {
return nil, fmt.Errorf("invalid segment: segment's last block contain seal %v, but doesn't match latestSealID: %v",
block.Payload.Seals[0].ID(), latestSealID)
}
}
return nil, fmt.Errorf("invalid segment: seal %v not found", latestSealID)
}
// isValidRootSegment will check that the block in the root segment has a view of 0.
func (builder *SealingSegmentBuilder) isValidRootSegment() bool {
return len(builder.blocks) == rootSegmentBlocksLen &&
builder.highest().Header.View == rootSegmentBlockView &&
len(builder.results) == rootSegmentBlocksLen && // root segment has only 1 result
builder.firstSeal != nil && // first seal is the root seal itself and must exist
builder.results[0].BlockID == builder.blocks[0].ID() && // root result matches the root block
builder.results[0].ID() == builder.firstSeal.ResultID && // root seal matches the root result
builder.results[0].BlockID == builder.firstSeal.BlockID // root seal seals the root block
}
// validateSegment will validate if builder satisfies conditions for a valid sealing segment.
func (builder *SealingSegmentBuilder) validateSegment() error {
// sealing cannot be empty
if len(builder.blocks) < 1 {
return fmt.Errorf("expect at least 2 blocks in a sealing segment or 1 block in the case of root segments, but actually got %v: %w", len(builder.blocks), ErrSegmentBlocksWrongLen)
}
// if root sealing segment skip seal sanity check
if len(builder.blocks) == 1 {
if !builder.isValidRootSegment() {
return fmt.Errorf("root sealing segment block has the wrong view got (%d) expected (%d): %w", builder.highest().Header.View, rootSegmentBlockView, ErrSegmentInvalidRootView)
}
return nil
}
// validate the latest seal is for the lowest block
err := builder.findLatestSealForLowestBlock()
if err != nil {
return fmt.Errorf("sealing segment missing seal lowest (%x) highest (%x) %v: %w", builder.lowest().ID(), builder.highest().ID(), err, ErrSegmentMissingSeal)
}
return nil
}
// highest returns the highest block in segment.
func (builder *SealingSegmentBuilder) highest() *Block {
if len(builder.blocks) == 0 {
return nil
}
return builder.blocks[len(builder.blocks)-1]
}
// lowest returns the lowest block in segment.
func (builder *SealingSegmentBuilder) lowest() *Block {
return builder.blocks[0]
}
// NewSealingSegmentBuilder returns *SealingSegmentBuilder
func NewSealingSegmentBuilder(resultLookup GetResultFunc, sealLookup GetSealByBlockIDFunc) *SealingSegmentBuilder {
return &SealingSegmentBuilder{
resultLookup: resultLookup,
sealByBlockIDLookup: sealLookup,
includedResults: make(map[Identifier]struct{}),
latestSeals: make(map[Identifier]Identifier),
blocks: make([]*Block, 0),
results: make(ExecutionResultList, 0),
}
}