use serde::{Deserialize, Serialize};
use tape_crypto::Address;
#[cfg(feature = "wincode")]
use wincode_derive::{SchemaRead, SchemaWrite};
use tape_crypto::hash::{Hash, hashv};
use crate::erasure::sub_leaf_count;
use crate::types::{EpochNumber, GroupIndex, RoundNumber, SpoolIndex, StorageUnits};
const ROUND_SEED_DOMAIN: &[u8] = b"WHIRLWIND_ROUND";
#[derive(Clone, Copy, Debug, Deserialize, Eq, PartialEq, Serialize)]
#[cfg_attr(feature = "wincode", derive(SchemaRead, SchemaWrite))]
pub enum EntryKind {
Coded { slice_len: StorageUnits },
Inline,
}
impl EntryKind {
pub fn leaves(&self) -> u64 {
match self {
EntryKind::Coded { slice_len } => sub_leaf_count(slice_len.as_usize()) as u64,
EntryKind::Inline => 1,
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct SampleEntry {
pub track: Address,
pub kind: EntryKind,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Sample {
pub track: Address,
pub leaf: SampleLeaf,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum SampleLeaf {
Coded { sub_leaf: usize },
Inline,
}
pub fn round_seed(
entropy: &Hash,
epoch: EpochNumber,
group: GroupIndex,
round: RoundNumber,
spool: SpoolIndex,
) -> Hash {
hashv(&[
ROUND_SEED_DOMAIN,
entropy.as_ref(),
&epoch.as_u64().to_le_bytes(),
&group.as_u64().to_le_bytes(),
&round.as_u64().to_le_bytes(),
&spool.as_u64().to_le_bytes(),
])
}
pub fn sort_entries(entries: &mut [SampleEntry]) {
entries.sort_unstable_by_key(|entry| entry.track);
}
pub fn sample_space(entries: &[SampleEntry]) -> u64 {
entries.iter().map(|entry| entry.kind.leaves()).sum()
}
pub fn draw(seed: &Hash, entries: &[SampleEntry]) -> Option<Sample> {
let total = sample_space(entries);
if total == 0 {
return None;
}
let mut head = [0u8; 8];
head.copy_from_slice(&seed.as_ref()[..8]);
let mut index = u64::from_le_bytes(head) % total;
for entry in entries {
let leaves = entry.kind.leaves();
if index < leaves {
return Some(Sample {
track: entry.track,
leaf: match entry.kind {
EntryKind::Coded { .. } => SampleLeaf::Coded {
sub_leaf: index as usize,
},
EntryKind::Inline => SampleLeaf::Inline,
},
});
}
index -= leaves;
}
None
}
#[cfg(test)]
mod tests {
use super::*;
use crate::erasure::SUB_LEAF_BYTES;
fn track(byte: u8) -> Address {
Address::from([byte; 32])
}
fn entry(byte: u8, leaves: usize) -> SampleEntry {
SampleEntry {
track: track(byte),
kind: EntryKind::Coded {
slice_len: StorageUnits::from_bytes((leaves * SUB_LEAF_BYTES) as u64),
},
}
}
fn inline_entry(byte: u8) -> SampleEntry {
SampleEntry {
track: track(byte),
kind: EntryKind::Inline,
}
}
fn seed_for(round: u64) -> Hash {
round_seed(
&hashv(&[b"entropy", &round.to_le_bytes()]),
EpochNumber(7),
GroupIndex(1),
RoundNumber(round),
SpoolIndex(3),
)
}
#[test]
fn seed_binds() {
let entropy = hashv(&[b"block"]);
let base = round_seed(&entropy, EpochNumber(1), GroupIndex(2), RoundNumber(3), SpoolIndex(4));
let variants = [
round_seed(&hashv(&[b"other"]), EpochNumber(1), GroupIndex(2), RoundNumber(3), SpoolIndex(4)),
round_seed(&entropy, EpochNumber(9), GroupIndex(2), RoundNumber(3), SpoolIndex(4)),
round_seed(&entropy, EpochNumber(1), GroupIndex(9), RoundNumber(3), SpoolIndex(4)),
round_seed(&entropy, EpochNumber(1), GroupIndex(2), RoundNumber(9), SpoolIndex(4)),
round_seed(&entropy, EpochNumber(1), GroupIndex(2), RoundNumber(3), SpoolIndex(9)),
];
for variant in variants {
assert_ne!(base, variant);
}
}
#[test]
fn empty_spool() {
assert!(draw(&seed_for(0), &[]).is_none());
assert!(draw(&seed_for(0), &[entry(1, 0)]).is_none());
}
#[test]
fn draw_in_range() {
let entries = [entry(1, 10), entry(2, 5), entry(3, 1)];
for round in 0..500u64 {
let sample = draw(&seed_for(round), &entries).expect("a drawn sample");
let held = entries.iter().find(|entry| entry.track == sample.track).expect("the drawn entry");
let SampleLeaf::Coded { sub_leaf } = sample.leaf else {
panic!("a coded entry drew an inline sample");
};
assert!(sub_leaf < held.kind.leaves() as usize);
}
}
#[test]
fn follows_entropy() {
let entries = [entry(1, 10), entry(2, 5)];
let asked: Vec<usize> = [1u8, 2, 3, 4]
.into_iter()
.map(|byte| {
let seed = round_seed(
&Hash::from([byte; 32]),
EpochNumber(7),
GroupIndex(1),
RoundNumber(5),
SpoolIndex(3),
);
match draw(&seed, &entries).expect("a drawn sample").leaf {
SampleLeaf::Coded { sub_leaf } => sub_leaf,
SampleLeaf::Inline => usize::MAX,
}
})
.collect();
assert!(asked.iter().any(|leaf| *leaf != asked[0]), "asked {asked:?}");
}
#[test]
fn inline_weighs_one() {
assert_eq!(sample_space(&[inline_entry(1)]), 1);
assert_eq!(sample_space(&[inline_entry(1), inline_entry(2)]), 2);
assert_eq!(sample_space(&[entry(3, 10), inline_entry(1)]), 11);
let drawn = draw(&seed_for(0), &[inline_entry(1)]).expect("a drawn sample");
assert_eq!(drawn.leaf, SampleLeaf::Inline);
assert_eq!(drawn.track, track(1));
}
#[test]
fn coded_outweighs_inline() {
let entries = [entry(1, 10), inline_entry(2)];
let mut coded = 0u32;
for round in 0..2_000u64 {
if draw(&seed_for(round), &entries).expect("a drawn sample").track == track(1) {
coded += 1;
}
}
let ratio = coded as f64 / (2_000 - coded) as f64;
assert!(ratio > 7.0 && ratio < 14.0, "ratio {ratio}");
}
#[test]
fn byte_weighted() {
let entries = [entry(1, 100), entry(2, 10)];
let mut hits = [0u32; 2];
for round in 0..4_000u64 {
let sample = draw(&seed_for(round), &entries).expect("a drawn sample");
hits[usize::from(sample.track == track(2))] += 1;
}
let ratio = hits[0] as f64 / hits[1] as f64;
assert!(ratio > 7.0 && ratio < 14.0, "ratio {ratio}");
}
#[test]
fn partial_leaf() {
let short = SampleEntry {
track: track(9),
kind: EntryKind::Coded {
slice_len: StorageUnits::from_bytes((SUB_LEAF_BYTES * 2 + 1) as u64),
},
};
assert_eq!(sample_space(&[short]), 3);
let mut saw_last = false;
for round in 0..200u64 {
if draw(&seed_for(round), &[short]).expect("a drawn sample").leaf
== (SampleLeaf::Coded { sub_leaf: 2 })
{
saw_last = true;
}
}
assert!(saw_last);
}
#[test]
fn entry_order() {
let mut forward = [entry(1, 10), entry(2, 10)];
let mut reversed = [entry(2, 10), entry(1, 10)];
let seed = seed_for(1);
assert_ne!(
draw(&seed, &forward),
draw(&seed, &reversed)
);
sort_entries(&mut forward);
sort_entries(&mut reversed);
assert_eq!(
draw(&seed, &forward),
draw(&seed, &reversed)
);
}
}