forked from ava-labs/avalanchego
-
Notifications
You must be signed in to change notification settings - Fork 4
/
windower.go
286 lines (249 loc) · 7.65 KB
/
windower.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
// Copyright (C) 2019-2024, Ava Labs, Inc. All rights reserved.
// See the file LICENSE for licensing terms.
package proposer
import (
"context"
"errors"
"fmt"
"math/bits"
"time"
"gonum.org/v1/gonum/mathext/prng"
"github.com/MetalBlockchain/metalgo/ids"
"github.com/MetalBlockchain/metalgo/snow/validators"
"github.com/MetalBlockchain/metalgo/utils"
"github.com/MetalBlockchain/metalgo/utils/math"
"github.com/MetalBlockchain/metalgo/utils/sampler"
"github.com/MetalBlockchain/metalgo/utils/wrappers"
)
// Proposer list constants
const (
WindowDuration = 5 * time.Second
MaxVerifyWindows = 6
MaxVerifyDelay = MaxVerifyWindows * WindowDuration // 30 seconds
MaxBuildWindows = 60
MaxBuildDelay = MaxBuildWindows * WindowDuration // 5 minutes
MaxLookAheadSlots = 720
MaxLookAheadWindow = MaxLookAheadSlots * WindowDuration // 1 hour
)
var (
_ Windower = (*windower)(nil)
ErrAnyoneCanPropose = errors.New("anyone can propose")
)
type Windower interface {
// Proposers returns the proposer list for building a block at [blockHeight]
// when the validator set is defined at [pChainHeight]. The list is returned
// in order. The minimum delay of a validator is the index they appear times
// [WindowDuration].
Proposers(
ctx context.Context,
blockHeight,
pChainHeight uint64,
maxWindows int,
) ([]ids.NodeID, error)
// Delay returns the amount of time that [validatorID] must wait before
// building a block at [blockHeight] when the validator set is defined at
// [pChainHeight].
Delay(
ctx context.Context,
blockHeight,
pChainHeight uint64,
validatorID ids.NodeID,
maxWindows int,
) (time.Duration, error)
// In the Post-Durango windowing scheme, every validator active at
// [pChainHeight] gets specific slots it can propose in (instead of being
// able to propose from a given time on as it happens Pre-Durango).
// [ExpectedProposer] calculates which nodeID is scheduled to propose a
// block of height [blockHeight] at [slot].
// If no validators are currently available, [ErrAnyoneCanPropose] is
// returned.
ExpectedProposer(
ctx context.Context,
blockHeight,
pChainHeight,
slot uint64,
) (ids.NodeID, error)
// In the Post-Durango windowing scheme, every validator active at
// [pChainHeight] gets specific slots it can propose in (instead of being
// able to propose from a given time on as it happens Pre-Durango).
// [MinDelayForProposer] specifies how long [nodeID] needs to wait for its
// slot to start. Delay is specified as starting from slot zero start.
// (which is parent timestamp). For efficiency reasons, we cap the slot
// search to [MaxLookAheadSlots].
// If no validators are currently available, [ErrAnyoneCanPropose] is
// returned.
MinDelayForProposer(
ctx context.Context,
blockHeight,
pChainHeight uint64,
nodeID ids.NodeID,
startSlot uint64,
) (time.Duration, error)
}
// windower interfaces with P-Chain and it is responsible for calculating the
// delay for the block submission window of a given validator
type windower struct {
state validators.State
subnetID ids.ID
chainSource uint64
}
func New(state validators.State, subnetID, chainID ids.ID) Windower {
w := wrappers.Packer{Bytes: chainID[:]}
return &windower{
state: state,
subnetID: subnetID,
chainSource: w.UnpackLong(),
}
}
func (w *windower) Proposers(ctx context.Context, blockHeight, pChainHeight uint64, maxWindows int) ([]ids.NodeID, error) {
// Note: The 32-bit prng is used here for legacy reasons. All other usages
// of a prng in this file should use the 64-bit version.
source := prng.NewMT19937()
sampler, validators, err := w.makeSampler(ctx, pChainHeight, source)
if err != nil {
return nil, err
}
var totalWeight uint64
for _, validator := range validators {
totalWeight, err = math.Add64(totalWeight, validator.weight)
if err != nil {
return nil, err
}
}
source.Seed(w.chainSource ^ blockHeight)
numToSample := int(min(uint64(maxWindows), totalWeight))
indices, err := sampler.Sample(numToSample)
if err != nil {
return nil, err
}
nodeIDs := make([]ids.NodeID, numToSample)
for i, index := range indices {
nodeIDs[i] = validators[index].id
}
return nodeIDs, nil
}
func (w *windower) Delay(ctx context.Context, blockHeight, pChainHeight uint64, validatorID ids.NodeID, maxWindows int) (time.Duration, error) {
if validatorID == ids.EmptyNodeID {
return time.Duration(maxWindows) * WindowDuration, nil
}
proposers, err := w.Proposers(ctx, blockHeight, pChainHeight, maxWindows)
if err != nil {
return 0, err
}
delay := time.Duration(0)
for _, nodeID := range proposers {
if nodeID == validatorID {
return delay, nil
}
delay += WindowDuration
}
return delay, nil
}
func (w *windower) ExpectedProposer(
ctx context.Context,
blockHeight,
pChainHeight,
slot uint64,
) (ids.NodeID, error) {
source := prng.NewMT19937_64()
sampler, validators, err := w.makeSampler(ctx, pChainHeight, source)
if err != nil {
return ids.EmptyNodeID, err
}
if len(validators) == 0 {
return ids.EmptyNodeID, ErrAnyoneCanPropose
}
return w.expectedProposer(
validators,
source,
sampler,
blockHeight,
slot,
)
}
func (w *windower) MinDelayForProposer(
ctx context.Context,
blockHeight,
pChainHeight uint64,
nodeID ids.NodeID,
startSlot uint64,
) (time.Duration, error) {
source := prng.NewMT19937_64()
sampler, validators, err := w.makeSampler(ctx, pChainHeight, source)
if err != nil {
return 0, err
}
if len(validators) == 0 {
return 0, ErrAnyoneCanPropose
}
maxSlot := startSlot + MaxLookAheadSlots
for slot := startSlot; slot < maxSlot; slot++ {
expectedNodeID, err := w.expectedProposer(
validators,
source,
sampler,
blockHeight,
slot,
)
if err != nil {
return 0, err
}
if expectedNodeID == nodeID {
return time.Duration(slot) * WindowDuration, nil
}
}
// no slots scheduled for the max window we inspect. Return max delay
return time.Duration(maxSlot) * WindowDuration, nil
}
func (w *windower) makeSampler(
ctx context.Context,
pChainHeight uint64,
source sampler.Source,
) (sampler.WeightedWithoutReplacement, []validatorData, error) {
// Get the canconical representation of the validator set at the provided
// p-chain height.
validatorsMap, err := w.state.GetValidatorSet(ctx, pChainHeight, w.subnetID)
if err != nil {
return nil, nil, err
}
validators := make([]validatorData, 0, len(validatorsMap))
for k, v := range validatorsMap {
validators = append(validators, validatorData{
id: k,
weight: v.Weight,
})
}
// Note: validators are sorted by ID. Sorting by weight would not create a
// canonically sorted list.
utils.Sort(validators)
weights := make([]uint64, len(validators))
for i, validator := range validators {
weights[i] = validator.weight
}
sampler := sampler.NewDeterministicWeightedWithoutReplacement(source)
return sampler, validators, sampler.Initialize(weights)
}
func (w *windower) expectedProposer(
validators []validatorData,
source *prng.MT19937_64,
sampler sampler.WeightedWithoutReplacement,
blockHeight,
slot uint64,
) (ids.NodeID, error) {
// Slot is reversed to utilize a different state space in the seed than the
// height. If the slot was not reversed the state space would collide;
// biasing the seed generation. For example, without reversing the slot
// height=0 and slot=1 would equal height=1 and slot=0.
source.Seed(w.chainSource ^ blockHeight ^ bits.Reverse64(slot))
indices, err := sampler.Sample(1)
if err != nil {
return ids.EmptyNodeID, fmt.Errorf("failed sampling proposers: %w", err)
}
return validators[indices[0]].id, nil
}
func TimeToSlot(start, now time.Time) uint64 {
if now.Before(start) {
return 0
}
return uint64(now.Sub(start) / WindowDuration)
}