use tape_crypto::Hash;
use tape_crypto::merkle::{empty_subtree_root, hash_pair, MerkleError, MerkleTree};
use crate::track::archive::{TrackArchive, TRACK_TREE_HEIGHT};
use crate::track::types::{CompressedTrack, CompressedTrackProof};
use crate::types::TrackNumber;
#[derive(Clone, Debug, PartialEq)]
pub struct ArchiveMirror {
base_number: TrackNumber,
base_index: u64,
base_subtrees: [Hash; TRACK_TREE_HEIGHT],
tree: MerkleTree<TRACK_TREE_HEIGHT>,
next_number: TrackNumber,
tracks: Vec<CompressedTrack>,
levels: Vec<Vec<Hash>>,
}
impl ArchiveMirror {
pub fn new(archive: &TrackArchive) -> Self {
let mut tree = archive.tree;
tree.ensure_initialized();
Self {
base_number: archive.next_number(),
base_index: tree.next_index,
base_subtrees: tree.filled_subtrees,
tree,
next_number: archive.next_number(),
tracks: Vec::new(),
levels: vec![Vec::new(); TRACK_TREE_HEIGHT],
}
}
pub fn append(&mut self, track: &CompressedTrack) -> Result<(), MerkleError> {
if track.track_number != self.next_number {
return Err(MerkleError::InvalidIndex);
}
let leaf = track.get_hash();
let leaf_index = self.tree.add_leaf_hash(leaf)?;
self.tracks.push(*track);
self.next_number.increment();
self.levels[0].push(leaf);
self.refresh_path(leaf_index);
Ok(())
}
pub fn proof_for(
&self,
track_number: TrackNumber,
) -> Result<CompressedTrackProof, MerkleError> {
let offset = self.offset_of(track_number)?;
let state = self.tracks[offset];
let leaf_index = self.leaf_index(offset);
let mut proof = [Hash::default(); TRACK_TREE_HEIGHT];
for (level, sibling) in proof.iter_mut().enumerate() {
let sibling_index = (leaf_index >> level) ^ 1;
*sibling = self.node_hash(level, sibling_index);
}
Ok(CompressedTrackProof { state, proof })
}
pub fn apply_certified(
&mut self,
track_number: TrackNumber,
updated: &CompressedTrack,
) -> Result<(), MerkleError> {
let proof = self.proof_for(track_number)?;
self.apply_certified_with_proof(track_number, updated, &proof)
}
pub fn apply_certified_with_proof(
&mut self,
track_number: TrackNumber,
updated: &CompressedTrack,
proof: &CompressedTrackProof,
) -> Result<(), MerkleError> {
let offset = self.offset_of(track_number)?;
let current = self.tracks[offset];
let unchanged = CompressedTrack {
state: current.state,
..*updated
};
if unchanged != current {
return Err(MerkleError::InvalidIndex);
}
let leaf = updated.get_hash();
let leaf_index = self.leaf_index(offset);
self.tree.update_leaf_hash(
leaf_index,
&proof.proof,
current.get_hash(),
leaf,
)?;
self.tracks[offset] = *updated;
self.levels[0][offset] = leaf;
self.refresh_path(leaf_index);
Ok(())
}
pub fn root(&self) -> Hash {
self.tree.root()
}
pub fn next_number(&self) -> TrackNumber {
self.next_number
}
pub fn is_empty(&self) -> bool {
self.base_number == self.next_number
}
pub fn covers(&self, track_number: TrackNumber) -> bool {
self.offset_of(track_number).is_ok()
}
fn offset_of(&self, track_number: TrackNumber) -> Result<usize, MerkleError> {
if track_number < self.base_number || track_number >= self.next_number {
return Err(MerkleError::InvalidIndex);
}
Ok((track_number.as_u64() - self.base_number.as_u64()) as usize)
}
fn leaf_index(&self, offset: usize) -> u64 {
self.base_index + offset as u64
}
fn node_hash(&self, level: usize, node_index: u64) -> Hash {
let start = node_index << level;
let end = start + (1u64 << level);
let base = self.base_index;
if start >= self.tree.next_index {
return empty_subtree_root(level);
}
if end <= base {
return self.base_subtrees[level];
}
self.levels[level][(node_index - (base >> level)) as usize]
}
fn refresh_path(&mut self, leaf_index: u64) {
let base = self.base_index;
for level in 1..TRACK_TREE_HEIGHT {
let node_index = leaf_index >> level;
let value = hash_pair(
self.node_hash(level - 1, node_index << 1),
self.node_hash(level - 1, (node_index << 1) | 1),
);
let position = (node_index - (base >> level)) as usize;
let nodes = &mut self.levels[level];
if position == nodes.len() {
nodes.push(value);
} else {
nodes[position] = value;
}
}
}
}
#[cfg(test)]
mod tests {
use bytemuck::Zeroable;
use tape_crypto::address::Address;
use tape_crypto::hash::hashv;
use crate::spooler::VirtualGroup;
use crate::track::types::{TrackFlags, TrackKind, TrackState};
use crate::types::{StorageUnits, TapeNumber};
use super::*;
fn tape_address() -> Address {
Address::from([7u8; 32])
}
fn registered(track_number: TrackNumber) -> CompressedTrack {
CompressedTrack {
tape: tape_address(),
tape_number: TapeNumber(1),
track_number,
key: hashv(&[b"key", &track_number.pack()]),
kind: TrackKind::Coded.into(),
state: TrackState::Registered.into(),
flags: TrackFlags::NONE,
size: StorageUnits(1024),
group: VirtualGroup(3),
value_hash: hashv(&[b"registered", &track_number.pack()]),
}
}
fn certified(track: &CompressedTrack) -> CompressedTrack {
let mut updated = *track;
updated.state = TrackState::Certified.into();
updated
}
fn assert_lockstep(archive: &TrackArchive, mirror: &ArchiveMirror) {
assert_eq!(mirror.root(), archive.tree.root());
assert_eq!(mirror.next_number(), archive.next_number());
for track in &mirror.tracks {
let proof = mirror
.proof_for(track.track_number)
.expect("proof for mirrored track");
assert_eq!(proof.state, *track);
archive.verify(&proof).expect("archive accepts proof");
let position = archive.position(track.track_number).expect("track has a position");
proof
.verify(&mirror.tree, position)
.expect("mirror accepts proof");
}
}
fn cleared_at(start: u64) -> TrackArchive {
let mut archive = TrackArchive::zeroed();
archive.next_number = TrackNumber(start);
archive
}
fn append_both(
archive: &mut TrackArchive,
mirror: &mut ArchiveMirror,
track: &CompressedTrack,
) {
archive.append(track).expect("archive append");
mirror.append(track).expect("mirror append");
}
fn certify_both(
archive: &mut TrackArchive,
mirror: &mut ArchiveMirror,
track: &CompressedTrack,
) {
let updated = certified(track);
let proof = mirror.proof_for(track.track_number).expect("certify proof");
archive.update(&proof, &updated).expect("archive update");
mirror
.apply_certified(track.track_number, &updated)
.expect("mirror update");
}
#[test]
fn seeded_offsets() {
for pre_count in 0..=17u64 {
let mut archive = TrackArchive::zeroed();
for number in 0..pre_count {
archive
.append(®istered(TrackNumber(number)))
.expect("pre-seed append");
}
let mut mirror = ArchiveMirror::new(&archive);
for number in pre_count..pre_count + 5 {
let track = registered(TrackNumber(number));
append_both(&mut archive, &mut mirror, &track);
assert_lockstep(&archive, &mirror);
}
}
}
#[test]
fn cleared_tree() {
const START: u64 = 41;
for pre_count in 0..=17u64 {
let mut archive = cleared_at(START);
for number in START..START + pre_count {
archive
.append(®istered(TrackNumber(number)))
.expect("pre-seed append");
}
let mut mirror = ArchiveMirror::new(&archive);
let mut appended = Vec::new();
for number in START + pre_count..START + pre_count + 5 {
let track = registered(TrackNumber(number));
append_both(&mut archive, &mut mirror, &track);
appended.push(track);
assert_lockstep(&archive, &mirror);
}
for track in &appended {
certify_both(&mut archive, &mut mirror, track);
assert_lockstep(&archive, &mirror);
}
assert!(!mirror.covers(TrackNumber(START + pre_count).prev()));
}
}
#[test]
fn interleaved_certifies() {
let mut archive = TrackArchive::zeroed();
for number in 0..3 {
archive
.append(®istered(TrackNumber(number)))
.expect("pre-seed append");
}
let mut mirror = ArchiveMirror::new(&archive);
let mut appended = Vec::new();
for number in 3..9u64 {
let track = registered(TrackNumber(number));
append_both(&mut archive, &mut mirror, &track);
appended.push(track);
assert_lockstep(&archive, &mirror);
if appended.len() >= 2 {
let target = appended[appended.len() - 2];
certify_both(&mut archive, &mut mirror, &target);
assert_lockstep(&archive, &mirror);
}
}
let last = appended[appended.len() - 1];
certify_both(&mut archive, &mut mirror, &last);
assert_lockstep(&archive, &mirror);
}
#[test]
fn late_proof() {
let mut archive = TrackArchive::zeroed();
let mut mirror = ArchiveMirror::new(&archive);
for number in 0..8u64 {
append_both(&mut archive, &mut mirror, ®istered(TrackNumber(number)));
}
let proof = mirror.proof_for(TrackNumber(0)).expect("late proof");
archive.verify(&proof).expect("archive accepts late proof");
}
#[test]
fn unmirrored_track() {
let mut archive = TrackArchive::zeroed();
for number in 0..2 {
archive
.append(®istered(TrackNumber(number)))
.expect("pre-seed append");
}
let mut mirror = ArchiveMirror::new(&archive);
append_both(&mut archive, &mut mirror, ®istered(TrackNumber(2)));
assert_eq!(
mirror.proof_for(TrackNumber(1)),
Err(MerkleError::InvalidIndex)
);
assert_eq!(
mirror.proof_for(TrackNumber(3)),
Err(MerkleError::InvalidIndex)
);
}
#[test]
fn wrong_number() {
let archive = TrackArchive::zeroed();
let mut mirror = ArchiveMirror::new(&archive);
let result = mirror.append(®istered(TrackNumber(1)));
assert_eq!(result, Err(MerkleError::InvalidIndex));
}
#[test]
fn empty_mirror() {
let mut archive = TrackArchive::zeroed();
archive
.append(®istered(TrackNumber(0)))
.expect("pre-seed append");
let mut mirror = ArchiveMirror::new(&archive);
assert!(mirror.is_empty());
mirror
.append(®istered(TrackNumber(1)))
.expect("mirror append");
assert!(!mirror.is_empty());
}
#[test]
fn covered_range() {
let mut archive = TrackArchive::zeroed();
archive
.append(®istered(TrackNumber(0)))
.expect("pre-seed append");
let mut mirror = ArchiveMirror::new(&archive);
append_both(&mut archive, &mut mirror, ®istered(TrackNumber(1)));
assert!(!mirror.covers(TrackNumber(0)));
assert!(mirror.covers(TrackNumber(1)));
assert!(!mirror.covers(TrackNumber(2)));
}
#[test]
fn identity_mismatch() {
let mut archive = TrackArchive::zeroed();
let mut mirror = ArchiveMirror::new(&archive);
let track = registered(TrackNumber(0));
append_both(&mut archive, &mut mirror, &track);
let mut updated = certified(&track);
updated.key = hashv(&[b"other"]);
assert_eq!(
mirror.apply_certified(track.track_number, &updated),
Err(MerkleError::InvalidIndex)
);
}
}