tape-core 0.4.0

A decentralized object store using Solana.
Documentation
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
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
//! When a group's challenge rounds fire, derived from finalized epoch state.
//!
//! Round times sit on a fixed slot grid computed from the epoch, so every owner
//! reaches the same schedule with no coordination and nobody can move a round
//! nearer or further from its own convenience. Each round opens a short window of
//! slots and the first block produced in it seeds the round, so the request is
//! unpredictable and the answer is due while that branch is live. A candidate
//! that does not survive to finality voids its round, as does a window that
//! produces nothing. Neither counts against anybody.

use core::ops::Range;

use tape_crypto::hash::{Hash, hashv};

use crate::types::{RoundNumber, SlotNumber};

/// Domain tag separating the grid offset from every other hash in the protocol.
const GRID_DOMAIN: &[u8] = b"WHIRLWIND_GRID";

/// Solana slot time. Everything here counts in slots, so this only converts.
pub const SLOT_MS: u64 = 400;

/// Slots a round searches for its entropy block before it voids.
///
/// Wider means fewer void rounds and a longer round. At a 5% miss rate a span of
/// two voids about one round in four hundred, where one slot voids one in twenty.
pub const SPAN_SLOTS: u64 = 2;

/// Slots before a round's window that the sample set is cut at.
///
/// A round opens on a produced block, ahead of what any owner has applied, and
/// owners' frontiers sit a finality window back by differing amounts. Cutting at
/// the window would put writes in that gap on one owner's side and not another's.
/// Cutting behind it puts the whole gap on everyone's side.
///
/// Wide enough for finality plus the spread, which `AT_TIP_THRESHOLD_SLOTS`
/// bounds at five.
pub const SAMPLE_LOOKBACK_SLOTS: u64 = 64;

/// Slots after the entropy block by which a proof must arrive.
///
/// Sized to clear honest global propagation, not to catch a fetch. The measured
/// envelope reaches half a globally placed group in about 143 ms, and tightening
/// below one slot is not expressible on the slot clock anyway.
pub const PROOF_DEADLINE_SLOTS: u64 = 2;

/// Slots after production before signing opens, standing in for the cluster
/// supermajority that confirms the entropy block.
pub const CONFIRMATION_SLOTS: u64 = 1;

/// Slots the signature window stays open once confirmation has passed.
pub const ATTESTATION_WINDOW_SLOTS: u64 = 2;

/// Slots allowed for an aggregated certificate to reach the group.
pub const CERTIFICATE_GOSSIP_SLOTS: u64 = 1;

/// Cadence on an epoch long enough not to constrain it: the round width.
///
/// Finality does not bound this; settlement lags by `SETTLE_DEADLINE_SLOTS`.
pub const MAINNET_CADENCE_SLOTS: u64 = 7;

/// Epoch length below which the cap gives way to the round width.
///
/// The cap is there to hold the cost of rounds down across an epoch that runs
/// for hours, where a tighter cadence buys detection latency nobody is waiting
/// on. An epoch measured in minutes is a harness: it ends before the saving is
/// worth anything, and the rounds are the thing being watched. Set well clear
/// of the shortest deployed epoch, which is an hour.
pub const SHORT_EPOCH_SLOTS: u64 = 1_800;

/// Slots a round waits before calling its block lost.
///
/// Sized off TowerBFT rooting, measured at 31 here. It is a timeout for the
/// void case, not a claim about how fast any given chain roots.
pub const FINALITY_SLOTS: u64 = 32;

/// Slots a round waits on its entropy block before it is void.
pub const SETTLE_DEADLINE_SLOTS: u64 = FINALITY_SLOTS + 8;

/// Rounds a group may hold at once: the deadline at the tightest cadence, which
/// is the round width. A cap below that sheds rounds before they can root.
pub const MAX_PENDING_ROUNDS: usize = (SETTLE_DEADLINE_SLOTS / round_width_slots() + 3) as usize;

/// Rounds a spool that changed hands is not charged for.
///
/// A new owner holds none of what it was just handed and has to fetch it, so
/// the rounds straight after a boundary would charge it for data it never had a
/// chance to hold. Counted from the epoch's first round rather than from round
/// zero, since the grid's early positions fall in phases that do not challenge.
/// Bounded so an owner that never fetches is still caught.
pub const HANDOVER_GRACE_ROUNDS: u64 = 8;

/// Rounds an epoch needs before the eviction rule can engage inside it.
pub const TARGET_ROUNDS_PER_EPOCH: u64 = 4;

/// Slots from a round opening to its certificate having gossiped; no slot for
/// confirmation since nothing in the signing leg waits on it
pub const fn round_width_slots() -> u64 {
    let tail = if PROOF_DEADLINE_SLOTS > ATTESTATION_WINDOW_SLOTS {
        PROOF_DEADLINE_SLOTS
    } else {
        ATTESTATION_WINDOW_SLOTS
    };
    SPAN_SLOTS + tail + CERTIFICATE_GOSSIP_SLOTS
}

/// Slots between rounds for an epoch of the given length.
///
/// The cap holds detection latency steady on long epochs and gives way on the
/// short ones, the divide fits enough rounds into an epoch shorter still, and
/// the floor keeps rounds from overlapping. Derived rather than tabulated, so an
/// operator voting the epoch duration gets a correct cadence without anyone
/// editing a table.
pub fn cadence_for_epoch(epoch_slots: u64) -> u64 {
    let fitted = epoch_slots / TARGET_ROUNDS_PER_EPOCH;
    let cap = if epoch_slots < SHORT_EPOCH_SLOTS {
        round_width_slots()
    } else {
        MAINNET_CADENCE_SLOTS
    };
    cap.min(fitted).max(round_width_slots())
}

/// Rounds an epoch of this length holds at this cadence, before any shift.
fn rounds_in(epoch_slots: u64, interval_slots: u64) -> u64 {
    let width = round_width_slots();
    if epoch_slots < width {
        return 0;
    }
    (epoch_slots - width) / interval_slots + 1
}

/// Slots the grid may be shifted by without costing a round.
///
/// The rounds an epoch holds never divide its length exactly, and what is left
/// over is room the grid can move within. Shifting further would buy variation by
/// giving up a round, which is the wrong trade on a short epoch where there are
/// only a handful.
pub fn grid_slack(epoch_slots: u64, interval_slots: u64) -> u64 {
    let rounds = rounds_in(epoch_slots, interval_slots);
    if rounds == 0 {
        return 0;
    }

    let used = (rounds - 1) * interval_slots + round_width_slots();
    epoch_slots.saturating_sub(used)
}

/// Slots to shift a grid by, from the epoch nonce.
///
/// Any value within the slack is a valid placement, so the modulo bias across a
/// 64-bit draw is irrelevant here.
pub fn grid_offset(nonce: &Hash, slack: u64) -> u64 {
    let mut head = [0u8; 8];
    head.copy_from_slice(&hashv(&[GRID_DOMAIN, nonce.as_ref()]).as_ref()[..8]);
    u64::from_le_bytes(head) % (slack + 1)
}

/// A schedule that cannot fire a usable round.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum ScheduleError {
    /// Rounds would overlap their neighbours.
    RoundsOverlap { interval: u64, width: u64 },
    /// The epoch is too short to hold a single round.
    EpochTooShort { epoch_slots: u64, width: u64 },
}

/// One epoch's challenge grid.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Schedule {
    /// First slot of the epoch these rounds belong to.
    pub epoch_start_slot: SlotNumber,
    /// Slots the epoch spans.
    pub epoch_slots: u64,
    /// Slots between the start of one round and the start of the next.
    pub interval_slots: u64,
    /// Slots the whole grid is shifted by, derived from the epoch nonce.
    ///
    /// Without it every round sits at a fixed offset from the epoch start, so
    /// whichever round lands in a phase that does not challenge is lost in that
    /// position every single epoch. The nonce moves the grid instead, so the
    /// rounds an epoch loses vary. It is knowable the moment the epoch begins,
    /// which is fine: the schedule may be public, only the samples may not be.
    pub grid_offset: u64,
}

impl Schedule {
    /// The grid for an epoch, with the cadence derived from its length and the
    /// placement derived from its nonce.
    pub fn for_epoch(epoch_start_slot: SlotNumber, epoch_slots: u64, nonce: &Hash) -> Self {
        let interval_slots = cadence_for_epoch(epoch_slots);
        Self {
            epoch_start_slot,
            epoch_slots,
            interval_slots,
            grid_offset: grid_offset(nonce, grid_slack(epoch_slots, interval_slots)),
        }
    }

    /// Slot the grid's first round opens at.
    pub fn first_slot(&self) -> SlotNumber {
        SlotNumber(self.epoch_start_slot.as_u64() + self.grid_offset)
    }

    /// Reject a grid whose rounds would overlap or that holds no round at all.
    pub fn validate(&self) -> Result<(), ScheduleError> {
        let width = round_width_slots();
        if self.interval_slots < width {
            return Err(ScheduleError::RoundsOverlap {
                interval: self.interval_slots,
                width,
            });
        }
        if self.epoch_slots < width {
            return Err(ScheduleError::EpochTooShort {
                epoch_slots: self.epoch_slots,
                width,
            });
        }
        Ok(())
    }

    /// Rounds an epoch of the nominal duration holds.
    ///
    /// Used to size the cadence and to project cost. It is not a limit on the
    /// grid: an epoch that runs past its nominal length keeps challenging.
    pub fn rounds(&self) -> u64 {
        rounds_in(self.epoch_slots, self.interval_slots)
    }

    /// Slot the round's sample set is cut at.
    ///
    /// Behind the window by `SAMPLE_LOOKBACK_SLOTS`, so the cut falls inside
    /// the range every owner has applied rather than inside the gap between
    /// their frontiers.
    pub fn sample_cutoff(&self, round: RoundNumber) -> SlotNumber {
        SlotNumber(self.base_slot(round).as_u64().saturating_sub(SAMPLE_LOOKBACK_SLOTS))
    }

    /// First slot of a round's entropy window.
    pub fn base_slot(&self, round: RoundNumber) -> SlotNumber {
        SlotNumber(self.first_slot().as_u64() + round.as_u64() * self.interval_slots)
    }

    /// Slots a round searches for its entropy block.
    pub fn entropy_window(&self, round: RoundNumber) -> Range<u64> {
        let base = self.base_slot(round).as_u64();
        base..base + SPAN_SLOTS
    }

    /// Slot by which a proof must have arrived, counted from the entropy block.
    ///
    /// Sizes the round rather than gating a response: no observer rejects a late
    /// answer today, because a round settles on its block rooting and that is
    /// the bound a response actually runs against.
    pub fn deadline_slot(&self, entropy_slot: SlotNumber) -> SlotNumber {
        SlotNumber(entropy_slot.as_u64() + PROOF_DEADLINE_SLOTS)
    }

    /// The round whose entropy window covers this slot, if any.
    ///
    /// None between rounds, which is most of the grid: the window is two slots
    /// out of an interval of seven.
    ///
    /// Not bounded by `rounds()`. That count is what an epoch of the nominal
    /// duration holds, but an epoch ends when the committee advances it, not when
    /// its nominal length elapses, so one can run long. Capping here would stop
    /// challenging partway through exactly the epochs that ran longest.
    pub fn round_at(&self, slot: SlotNumber) -> Option<RoundNumber> {
        let offset = slot.as_u64().checked_sub(self.first_slot().as_u64())?;
        if offset % self.interval_slots >= SPAN_SLOTS {
            return None;
        }
        Some(RoundNumber(offset / self.interval_slots))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// Epoch durations in seconds, from the genesis presets.
    const MAINNET: u64 = 604_800;
    const DEVNET: u64 = 3_600;
    const LOCALNET: u64 = 100;
    const SIMNET: u64 = 20;

    fn epoch_slots(seconds: u64) -> u64 {
        seconds * 1_000 / SLOT_MS
    }

    fn nonce(byte: u8) -> Hash {
        Hash([byte; 32])
    }

    #[test]
    fn round_width() {
        assert_eq!(round_width_slots(), 5);
    }

    /// The deployed presets keep the cap; the harnesses run at the round width,
    /// which is as tight as a grid can be laid without rounds overlapping.
    #[test]
    fn preset_cadence() {
        let expected = [
            (MAINNET, 7u64, 216_000u64),
            (DEVNET, 7, 1_286),
            (LOCALNET, 5, 50),
            (SIMNET, 5, 10),
        ];

        for (seconds, interval, rounds) in expected {
            let slots = epoch_slots(seconds);
            let schedule = Schedule::for_epoch(SlotNumber(0), slots, &nonce(0));

            assert_eq!(schedule.interval_slots, interval, "{seconds}s interval");
            assert_eq!(schedule.rounds(), rounds, "{seconds}s rounds");
            assert!(schedule.validate().is_ok(), "{seconds}s invalid");
        }
    }

    #[test]
    fn shortest_epoch() {
        let schedule = Schedule::for_epoch(SlotNumber(0), epoch_slots(5), &nonce(0));
        assert_eq!(schedule.interval_slots, round_width_slots());
        assert_eq!(schedule.rounds(), 2);
        assert!(schedule.validate().is_ok());
    }

    #[test]
    fn epoch_too_short() {
        let schedule = Schedule::for_epoch(SlotNumber(0), 4, &nonce(0));
        assert_eq!(schedule.rounds(), 0);
        assert_eq!(
            schedule.validate(),
            Err(ScheduleError::EpochTooShort {
                epoch_slots: 4,
                width: round_width_slots(),
            })
        );
    }

    #[test]
    fn no_overlap() {
        let schedule = Schedule::for_epoch(SlotNumber(1_000), epoch_slots(SIMNET), &nonce(0));
        for round in 0..schedule.rounds() {
            let window = schedule.entropy_window(RoundNumber(round));
            let next = schedule.base_slot(RoundNumber(round + 1)).as_u64();

            assert!(window.start >= schedule.first_slot().as_u64());
            assert!(window.end + round_width_slots() - SPAN_SLOTS <= next);
        }
    }

    #[test]
    fn last_round_fits() {
        for (seconds, byte) in [
            (MAINNET, 0u8), (MAINNET, 200), (DEVNET, 3), (LOCALNET, 7),
            (SIMNET, 11), (10, 13), (200, 17),
        ] {
            let slots = epoch_slots(seconds);
            let schedule = Schedule::for_epoch(SlotNumber(0), slots, &nonce(byte));
            let Some(last) = schedule.rounds().checked_sub(1) else {
                continue;
            };

            let end = schedule.base_slot(RoundNumber(last)).as_u64()
                - schedule.epoch_start_slot.as_u64()
                + round_width_slots();
            assert!(end <= slots, "{seconds}s overruns by {}", end - slots);
        }
    }

    #[test]
    fn long_epoch() {
        let schedule = Schedule::for_epoch(SlotNumber(0), epoch_slots(SIMNET), &nonce(0));
        let nominal = schedule.rounds();

        assert_eq!(
            schedule.round_at(schedule.base_slot(RoundNumber(nominal))),
            Some(RoundNumber(nominal))
        );
        assert_eq!(
            schedule.round_at(schedule.base_slot(RoundNumber(nominal + 10))),
            Some(RoundNumber(nominal + 10))
        );
    }

    #[test]
    fn nonce_moves_grid() {
        // An epoch whose rounds do not divide it exactly. One that does leaves
        // no slack, and the grid then sits in the same place whatever the nonce.
        let slots = epoch_slots(MAINNET);
        let offsets: Vec<u64> = (0..8u8)
            .map(|byte| Schedule::for_epoch(SlotNumber(0), slots, &nonce(byte)).grid_offset)
            .collect();

        assert!(offsets.iter().all(|offset| *offset <= grid_slack(slots, MAINNET_CADENCE_SLOTS)));
        assert!(
            offsets.iter().collect::<std::collections::HashSet<_>>().len() > 1,
            "the grid sat in the same place for every nonce: {offsets:?}"
        );
    }

    #[test]
    fn nonce_is_pure() {
        let slots = epoch_slots(DEVNET);
        let once = Schedule::for_epoch(SlotNumber(77), slots, &nonce(9));
        let again = Schedule::for_epoch(SlotNumber(77), slots, &nonce(9));

        assert_eq!(once, again);
        assert_eq!(once.base_slot(RoundNumber(3)), again.base_slot(RoundNumber(3)));
    }

    #[test]
    fn grid_inside_epoch() {
        let slots = epoch_slots(SIMNET);
        for byte in 0..32u8 {
            let schedule = Schedule::for_epoch(SlotNumber(500), slots, &nonce(byte));
            assert!(schedule.first_slot().as_u64() >= 500);
            // Moving the grid must never cost a round.
            assert_eq!(
                schedule.rounds(),
                Schedule::for_epoch(SlotNumber(500), slots, &Hash([0; 32])).rounds()
            );
        }
    }

    #[test]
    fn slot_to_round() {
        let start = SlotNumber(9_000);
        let schedule = Schedule::for_epoch(start, epoch_slots(DEVNET), &nonce(0));

        for round in [0u64, 1, 30, schedule.rounds() + 5] {
            let window = schedule.entropy_window(RoundNumber(round));
            for slot in window.clone() {
                assert_eq!(schedule.round_at(SlotNumber(slot)), Some(RoundNumber(round)));
            }
            // The gap after a window belongs to no round.
            assert_eq!(schedule.round_at(SlotNumber(window.end)), None);
        }

        // Before the grid opens there is no round at all.
        assert_eq!(schedule.round_at(SlotNumber(schedule.first_slot().as_u64() - 1)), None);
    }
}