use core::ops::Range;
use tape_crypto::Hash;
use tape_crypto::merkle::{create_proof_from_level, fold_level, hash_leaves, root_from_leaf_hashes};
use crate::types::{GroupIndex, SpoolIndex};
pub const MAX_GROUP_SIZE: usize = 20;
pub const SLICE_TREE_HEIGHT: usize = 5;
pub const SUB_LEAF_BYTES: usize = 1024;
pub const SUB_TREE_HEIGHT: usize = 16;
#[inline]
pub fn sub_leaf_count(slice_len: usize) -> usize {
slice_len.div_ceil(SUB_LEAF_BYTES)
}
pub fn sub_leaf_hashes(slice: &[u8]) -> Vec<Hash> {
hash_leaves(&slice.chunks(SUB_LEAF_BYTES).collect::<Vec<_>>())
}
pub const SAMPLE_WINDOW_HEIGHT: usize = 8;
pub const SAMPLE_WINDOW_LEAVES: usize = 1 << SAMPLE_WINDOW_HEIGHT;
pub const SAMPLE_WINDOW_BYTES: usize = SAMPLE_WINDOW_LEAVES * SUB_LEAF_BYTES;
pub fn slice_sidecar(slice: &[u8]) -> Option<Vec<Hash>> {
if sub_leaf_count(slice.len()) > 1 << SUB_TREE_HEIGHT {
return None;
}
Some(fold_level(&sub_leaf_hashes(slice), 0, SAMPLE_WINDOW_HEIGHT))
}
pub fn slice_root_from_sidecar(sidecar: &[Hash]) -> Hash {
if sidecar.is_empty() {
return root_from_leaf_hashes::<SUB_TREE_HEIGHT>(&[]);
}
fold_level(sidecar, SAMPLE_WINDOW_HEIGHT, SUB_TREE_HEIGHT - SAMPLE_WINDOW_HEIGHT)[0]
}
pub fn window_root(window: &[u8]) -> Hash {
fold_level(&sub_leaf_hashes(window), 0, SAMPLE_WINDOW_HEIGHT)
.first()
.copied()
.unwrap_or_default()
}
pub fn sample_window(sub_leaf: usize, slice_len: usize) -> Range<usize> {
let window = sample_window_range(sub_leaf);
window.start..window.end.min(slice_len)
}
pub fn sample_window_range(sub_leaf: usize) -> Range<usize> {
let start = (sub_leaf / SAMPLE_WINDOW_LEAVES) * SAMPLE_WINDOW_BYTES;
start..start + SAMPLE_WINDOW_BYTES
}
pub fn prove_sub_leaf_windowed(
sidecar: &[Hash],
window: &[u8],
sub_leaf: usize,
) -> Option<Vec<Hash>> {
let within = sub_leaf % SAMPLE_WINDOW_LEAVES;
let node = sub_leaf / SAMPLE_WINDOW_LEAVES;
let mut path =
create_proof_from_level(&sub_leaf_hashes(window), within, 0, SAMPLE_WINDOW_HEIGHT).ok()?;
path.extend(
create_proof_from_level(
sidecar,
node,
SAMPLE_WINDOW_HEIGHT,
SUB_TREE_HEIGHT - SAMPLE_WINDOW_HEIGHT,
)
.ok()?,
);
Some(path)
}
pub fn slice_root(slice: &[u8]) -> Option<Hash> {
if sub_leaf_count(slice.len()) > 1 << SUB_TREE_HEIGHT {
return None;
}
Some(root_from_leaf_hashes::<SUB_TREE_HEIGHT>(&sub_leaf_hashes(slice)))
}
#[inline]
pub fn leaf_position(spool: SpoolIndex) -> SpoolIndex {
SpoolIndex(spool.as_u64() % MAX_GROUP_SIZE as u64)
}
#[inline]
pub fn group_start(group: GroupIndex) -> SpoolIndex {
group.base_spool()
}
#[inline]
pub fn spool_for_slice(group: GroupIndex, slice_in_group: usize) -> SpoolIndex {
group.spool_at(slice_in_group)
}
#[inline]
pub fn slice_for_spool(group: GroupIndex, spool: SpoolIndex) -> Option<usize> {
group.position_of(spool)
}
#[inline]
pub fn spool_in_group(spool: SpoolIndex, group: GroupIndex) -> bool {
group.contains(spool)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_spool_group_size() {
assert_eq!(MAX_GROUP_SIZE, 20);
}
#[test]
fn leaf_position_wraps() {
assert_eq!(leaf_position(SpoolIndex(0)), SpoolIndex(0));
assert_eq!(leaf_position(SpoolIndex(19)), SpoolIndex(19));
assert_eq!(leaf_position(SpoolIndex(20)), SpoolIndex(0));
assert_eq!(leaf_position(SpoolIndex(137)), SpoolIndex(17));
for spool in [0u64, 1, 20, 137, 999] {
let spool = SpoolIndex(spool);
let position = leaf_position(spool);
assert!(position.as_usize() < MAX_GROUP_SIZE);
assert_eq!(
GroupIndex::containing(spool).position_of(spool),
Some(position.as_usize())
);
}
}
fn slice_of(leaves: usize, tail: usize) -> Vec<u8> {
let mut state: u64 = 0x9E37_79B9_7F4A_7C15;
(0..leaves * SUB_LEAF_BYTES + tail)
.map(|_| {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
(state >> 24) as u8
})
.collect()
}
#[test]
fn sidecar_path() {
for (leaves, tail) in [(1usize, 0usize), (1, 5), (255, 0), (256, 0), (257, 0), (900, 33)] {
let slice = slice_of(leaves, tail);
let sidecar = slice_sidecar(&slice).expect("within capacity");
let hashes = sub_leaf_hashes(&slice);
let total = sub_leaf_count(slice.len());
for sub_leaf in [0, total / 3, total.saturating_sub(1)] {
let full = tape_crypto::merkle::create_proof_from_leaf_hashes::<SUB_TREE_HEIGHT>(
&hashes, sub_leaf,
)
.expect("full proof");
let windowed = prove_sub_leaf_windowed(
&sidecar,
&slice[sample_window(sub_leaf, slice.len())],
sub_leaf,
)
.expect("windowed proof");
assert_eq!(windowed, full, "leaves {leaves} tail {tail} leaf {sub_leaf}");
}
}
}
#[test]
fn folded_root() {
for (leaves, tail) in [(0usize, 0usize), (0, 9), (1, 0), (255, 0), (256, 0), (900, 33)] {
let slice = slice_of(leaves, tail);
let sidecar = slice_sidecar(&slice).expect("within capacity");
assert_eq!(
slice_root_from_sidecar(&sidecar),
slice_root(&slice).expect("within capacity"),
"leaves {leaves} tail {tail}"
);
}
}
#[test]
fn sidecar_size() {
let slice = slice_of(900, 0);
let sidecar = slice_sidecar(&slice).expect("within capacity");
assert_eq!(sidecar.len(), 900usize.div_ceil(SAMPLE_WINDOW_LEAVES));
assert!(sidecar.len() * Hash::LEN * 1_000 < slice.len());
}
#[test]
fn window_bounds() {
let slice_len = 900 * SUB_LEAF_BYTES + 7;
for sub_leaf in [0usize, 255, 256, 899] {
let window = sample_window(sub_leaf, slice_len);
let leaf_start = sub_leaf * SUB_LEAF_BYTES;
assert!(window.contains(&leaf_start));
assert!(window.end <= slice_len);
assert_eq!(window.start % SAMPLE_WINDOW_BYTES, 0);
}
}
#[test]
fn test_sub_leaf_count_rounds_up() {
assert_eq!(sub_leaf_count(0), 0);
assert_eq!(sub_leaf_count(1), 1);
assert_eq!(sub_leaf_count(SUB_LEAF_BYTES), 1);
assert_eq!(sub_leaf_count(SUB_LEAF_BYTES + 1), 2);
}
#[test]
fn test_slice_root_matches_leaf_hashes() {
let slice: Vec<u8> = (0..SUB_LEAF_BYTES * 2 + 7).map(|b| b as u8).collect();
let hashes = sub_leaf_hashes(&slice);
assert_eq!(hashes.len(), sub_leaf_count(slice.len()));
assert_eq!(
slice_root(&slice),
Some(tape_crypto::merkle::root_from_leaf_hashes::<SUB_TREE_HEIGHT>(&hashes))
);
}
#[test]
fn test_slice_root_bounded_by_tree_capacity() {
let capacity = SUB_LEAF_BYTES << SUB_TREE_HEIGHT;
assert!(slice_root(&vec![0u8; capacity]).is_some());
assert!(slice_root(&vec![0u8; capacity + 1]).is_none());
}
#[test]
fn test_capacity_is_one_whole_track() {
const MAX_TRACK_BYTES: usize = 64 * 1024 * 1024;
assert_eq!(SUB_LEAF_BYTES << SUB_TREE_HEIGHT, MAX_TRACK_BYTES);
}
#[test]
fn test_group_start() {
assert_eq!(group_start(GroupIndex(0)), SpoolIndex(0));
assert_eq!(group_start(GroupIndex(1)), SpoolIndex(20));
assert_eq!(group_start(GroupIndex(49)), SpoolIndex(980));
}
#[test]
fn test_spool_for_slice() {
assert_eq!(spool_for_slice(GroupIndex(0), 0), SpoolIndex(0));
assert_eq!(spool_for_slice(GroupIndex(0), 19), SpoolIndex(19));
assert_eq!(spool_for_slice(GroupIndex(1), 0), SpoolIndex(20));
assert_eq!(spool_for_slice(GroupIndex(49), 19), SpoolIndex(999));
}
#[test]
fn test_spool_in_group() {
assert!(spool_in_group(SpoolIndex(0), GroupIndex(0)));
assert!(spool_in_group(SpoolIndex(19), GroupIndex(0)));
assert!(!spool_in_group(SpoolIndex(20), GroupIndex(0)));
assert!(spool_in_group(SpoolIndex(20), GroupIndex(1)));
assert!(spool_in_group(SpoolIndex(999), GroupIndex(49)));
}
#[test]
fn test_slice_for_spool() {
assert_eq!(slice_for_spool(GroupIndex(0), SpoolIndex(0)), Some(0));
assert_eq!(slice_for_spool(GroupIndex(0), SpoolIndex(19)), Some(19));
assert_eq!(slice_for_spool(GroupIndex(1), SpoolIndex(20)), Some(0));
assert_eq!(slice_for_spool(GroupIndex(1), SpoolIndex(39)), Some(19));
assert_eq!(slice_for_spool(GroupIndex(0), SpoolIndex(20)), None);
}
}