holos_tda/
index_proof.rs

1//! Cold snapshots and warm deltas for versioned persistence indexes.
2//!
3//! A snapshot contains one complete interface tree. A delta contains only
4//! changed edge values and interface nodes absent from the preceding tree.
5//! The separate checker keeps the verified old tree and advances its root.
6
7mod wire;
8
9#[cfg(test)]
10mod tests;
11
12use std::collections::BTreeSet;
13use std::fmt;
14use std::sync::Arc;
15
16use crate::index::InterfaceNode;
17use crate::{Bar, CertificateLimits, ChangeColumn, InterfaceMode, PersistenceIndex};
18
19use wire::{encode_diagram, encode_header, encode_nodes, put_u64, put_usize};
20
21const SNAPSHOT_MAGIC: &[u8; 8] = b"HOLOSIP\0";
22const DELTA_MAGIC: &[u8; 8] = b"HOLOSDP\0";
23const VERSION: u16 = 4;
24const F64_BITS_CODEC: u8 = 1;
25
26/// Failure while producing or encoding an index proof.
27#[derive(Debug, Clone, PartialEq, Eq)]
28pub struct IndexProofError {
29    message: String,
30}
31
32impl IndexProofError {
33    fn new(message: impl Into<String>) -> Self {
34        Self {
35            message: message.into(),
36        }
37    }
38
39    /// Description of the violated producer rule.
40    pub fn message(&self) -> &str {
41        &self.message
42    }
43}
44
45impl fmt::Display for IndexProofError {
46    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
47        write!(formatter, "index proof: {}", self.message)
48    }
49}
50
51impl std::error::Error for IndexProofError {}
52
53/// Structural size of a cold snapshot or warm delta.
54#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
55pub struct IndexProofSummary {
56    /// Interface nodes carried by this record.
57    pub nodes: usize,
58    /// Carried nodes checked by separator composition.
59    pub composed_nodes: usize,
60    /// Carried nodes checked as relative filtered cores.
61    pub relative_nodes: usize,
62    /// Encoded relative-interface bytes carried by this record.
63    pub relative_bytes: usize,
64    /// Edge values changed by this record.
65    pub edge_changes: usize,
66    /// Edge-boundary change columns carried by this record.
67    pub edge_columns: usize,
68    /// Triangle-boundary change columns carried by this record.
69    pub triangle_columns: usize,
70    /// Change columns above the triangle boundary carried by this record.
71    pub higher_columns: usize,
72    /// Sparse change-of-basis terms carried by this record.
73    pub terms: usize,
74}
75
76#[derive(Debug, Clone)]
77struct ProofNode {
78    digest: [u8; 32],
79    vertices: Vec<usize>,
80    edge_positions: Vec<usize>,
81    separator: Vec<usize>,
82    protected_vertices: Vec<usize>,
83    children: Vec<[u8; 32]>,
84    mode: InterfaceMode,
85    graded_columns: Vec<Vec<ChangeColumn>>,
86    relative_artifact: Vec<u8>,
87    relative_column_counts: Vec<usize>,
88    relative_terms: usize,
89    diagram: Vec<Bar>,
90}
91
92impl ProofNode {
93    fn from_interface(
94        node: &InterfaceNode,
95        max_dim: usize,
96        limits: CertificateLimits,
97    ) -> Result<Self, IndexProofError> {
98        let graded_columns = node
99            .reduction()
100            .map(|reduction| reduction.graded_columns().to_vec())
101            .unwrap_or_else(|| vec![Vec::new(); max_dim + 1]);
102        let relative_artifact = node
103            .relative()
104            .map(|relative| relative.encode(limits))
105            .transpose()
106            .map_err(|error| IndexProofError::new(error.to_string()))?
107            .unwrap_or_default();
108        let relative_column_counts = node
109            .relative()
110            .map(|relative| relative.graded_columns().iter().map(Vec::len).collect())
111            .unwrap_or_default();
112        let relative_terms = node
113            .relative()
114            .map(|relative| {
115                relative
116                    .graded_columns()
117                    .iter()
118                    .flatten()
119                    .map(|column| column.terms.len())
120                    .sum()
121            })
122            .unwrap_or(0);
123        Ok(Self {
124            digest: node.digest,
125            vertices: node.vertices.clone(),
126            edge_positions: node.edge_positions.clone(),
127            separator: node.separator.clone(),
128            protected_vertices: node.protected_vertices.clone(),
129            children: node.children.iter().map(|child| child.digest).collect(),
130            mode: node.mode(),
131            graded_columns,
132            relative_artifact,
133            relative_column_counts,
134            relative_terms,
135            diagram: node.diagram().bars.clone(),
136        })
137    }
138
139    fn summary(&self, summary: &mut IndexProofSummary) {
140        summary.nodes += 1;
141        if self.mode != InterfaceMode::Materialized {
142            summary.composed_nodes += 1;
143        }
144        if self.mode == InterfaceMode::Relative {
145            summary.relative_nodes += 1;
146            summary.relative_bytes += self.relative_artifact.len();
147        }
148        summary.edge_columns += self.graded_columns.first().map_or(0, Vec::len);
149        summary.edge_columns += self.relative_column_counts.first().copied().unwrap_or(0);
150        summary.triangle_columns += self.graded_columns.get(1).map_or(0, Vec::len);
151        summary.triangle_columns += self.relative_column_counts.get(1).copied().unwrap_or(0);
152        summary.higher_columns += self
153            .graded_columns
154            .iter()
155            .skip(2)
156            .map(Vec::len)
157            .sum::<usize>();
158        summary.higher_columns += self.relative_column_counts.iter().skip(2).sum::<usize>();
159        summary.terms += self
160            .graded_columns
161            .iter()
162            .flatten()
163            .map(|column| column.terms.len())
164            .sum::<usize>();
165        summary.terms += self.relative_terms;
166    }
167}
168
169/// One complete persistence-index snapshot.
170#[derive(Debug, Clone)]
171pub struct IndexSnapshotProof {
172    max_dim: usize,
173    modulus: u32,
174    threshold: Option<f64>,
175    vertex_count: usize,
176    edges: Vec<(usize, usize, f64)>,
177    root: [u8; 32],
178    nodes: Vec<ProofNode>,
179    diagram: Vec<Bar>,
180}
181
182impl IndexSnapshotProof {
183    /// Capture the current index version.
184    pub fn from_index(index: &PersistenceIndex) -> Result<Self, IndexProofError> {
185        let mut nodes = Vec::new();
186        let mut seen = BTreeSet::new();
187        let excluded = BTreeSet::new();
188        collect_nodes(
189            index.root(),
190            index.params().max_dim,
191            index.certificate_limits(),
192            &excluded,
193            &mut seen,
194            &mut nodes,
195        )?;
196        Ok(Self {
197            max_dim: index.params().max_dim,
198            modulus: index.params().modulus,
199            threshold: index.params().threshold,
200            vertex_count: index.graph().len(),
201            edges: index.graph().edges().collect(),
202            root: index.version(),
203            nodes,
204            diagram: index.diagram().bars.clone(),
205        })
206    }
207
208    /// Root content identifier checked by a warm delta.
209    pub fn root(&self) -> &[u8; 32] {
210        &self.root
211    }
212
213    /// Structural size of this cold snapshot.
214    pub fn summary(&self) -> IndexProofSummary {
215        proof_summary(&self.nodes, 0)
216    }
217
218    /// Encode the canonical `HOLOSIP` version 4 snapshot.
219    pub fn encode(&self) -> Result<Vec<u8>, IndexProofError> {
220        let mut output = Vec::new();
221        output.extend_from_slice(SNAPSHOT_MAGIC);
222        encode_header(
223            &mut output,
224            self.max_dim,
225            self.modulus,
226            self.threshold,
227            self.vertex_count,
228        )?;
229        put_usize(&mut output, self.edges.len())?;
230        put_usize(&mut output, self.nodes.len())?;
231        put_usize(&mut output, self.diagram.len())?;
232        output.extend_from_slice(&self.root);
233        for &(u, v, value) in &self.edges {
234            put_usize(&mut output, u)?;
235            put_usize(&mut output, v)?;
236            put_u64(&mut output, value.to_bits());
237        }
238        encode_nodes(&mut output, &self.nodes)?;
239        encode_diagram(&mut output, &self.diagram)?;
240        Ok(output)
241    }
242}
243
244/// One stateful proof delta between indexes with the same envelope.
245#[derive(Debug, Clone)]
246pub struct IndexDeltaProof {
247    max_dim: usize,
248    modulus: u32,
249    threshold: Option<f64>,
250    vertex_count: usize,
251    edge_count: usize,
252    old_root: [u8; 32],
253    new_root: [u8; 32],
254    edge_changes: Vec<(usize, f64)>,
255    nodes: Vec<ProofNode>,
256    diagram: Vec<Bar>,
257}
258
259impl IndexDeltaProof {
260    /// Produce a warm proof delta between two versions of one envelope.
261    pub fn between(
262        old: &PersistenceIndex,
263        new: &PersistenceIndex,
264    ) -> Result<Self, IndexProofError> {
265        if old.params().max_dim != new.params().max_dim
266            || old.params().modulus != new.params().modulus
267            || old.params().threshold.map(f64::to_bits) != new.params().threshold.map(f64::to_bits)
268            || old.graph().len() != new.graph().len()
269            || old.topology() != new.topology()
270        {
271            return Err(IndexProofError::new(
272                "a proof delta requires one field, threshold, and listed-edge envelope",
273            ));
274        }
275        let edge_changes = old
276            .topology()
277            .iter()
278            .enumerate()
279            .filter_map(|(position, edge)| {
280                let old_value = old.graph().get(edge.u, edge.v);
281                let new_value = new.graph().get(edge.u, edge.v);
282                (old_value.to_bits() != new_value.to_bits()).then_some((position, new_value))
283            })
284            .collect();
285        let mut old_nodes = BTreeSet::new();
286        collect_digests(old.root(), &mut old_nodes);
287        let mut nodes = Vec::new();
288        let mut seen = BTreeSet::new();
289        collect_nodes(
290            new.root(),
291            new.params().max_dim,
292            new.certificate_limits(),
293            &old_nodes,
294            &mut seen,
295            &mut nodes,
296        )?;
297        Ok(Self {
298            max_dim: old.params().max_dim,
299            modulus: old.params().modulus,
300            threshold: old.params().threshold,
301            vertex_count: old.graph().len(),
302            edge_count: old.topology().len(),
303            old_root: old.version(),
304            new_root: new.version(),
305            edge_changes,
306            nodes,
307            diagram: new.diagram().bars.clone(),
308        })
309    }
310
311    /// Root required before this delta can be applied.
312    pub fn old_root(&self) -> &[u8; 32] {
313        &self.old_root
314    }
315
316    /// Root established after this delta is verified.
317    pub fn new_root(&self) -> &[u8; 32] {
318        &self.new_root
319    }
320
321    /// Structural size of this warm delta.
322    pub fn summary(&self) -> IndexProofSummary {
323        proof_summary(&self.nodes, self.edge_changes.len())
324    }
325
326    /// Encode the canonical `HOLOSDP` version 4 delta.
327    pub fn encode(&self) -> Result<Vec<u8>, IndexProofError> {
328        let mut output = Vec::new();
329        output.extend_from_slice(DELTA_MAGIC);
330        encode_header(
331            &mut output,
332            self.max_dim,
333            self.modulus,
334            self.threshold,
335            self.vertex_count,
336        )?;
337        put_usize(&mut output, self.edge_count)?;
338        put_usize(&mut output, self.edge_changes.len())?;
339        put_usize(&mut output, self.nodes.len())?;
340        put_usize(&mut output, self.diagram.len())?;
341        output.extend_from_slice(&self.old_root);
342        output.extend_from_slice(&self.new_root);
343        for &(position, value) in &self.edge_changes {
344            put_usize(&mut output, position)?;
345            put_u64(&mut output, value.to_bits());
346        }
347        encode_nodes(&mut output, &self.nodes)?;
348        encode_diagram(&mut output, &self.diagram)?;
349        Ok(output)
350    }
351}
352
353fn collect_nodes(
354    node: &Arc<InterfaceNode>,
355    max_dim: usize,
356    limits: CertificateLimits,
357    excluded: &BTreeSet<[u8; 32]>,
358    seen: &mut BTreeSet<[u8; 32]>,
359    output: &mut Vec<ProofNode>,
360) -> Result<(), IndexProofError> {
361    if excluded.contains(&node.digest) || !seen.insert(node.digest) {
362        return Ok(());
363    }
364    output.push(ProofNode::from_interface(node, max_dim, limits)?);
365    for child in &node.children {
366        collect_nodes(child, max_dim, limits, excluded, seen, output)?;
367    }
368    Ok(())
369}
370
371fn collect_digests(node: &Arc<InterfaceNode>, output: &mut BTreeSet<[u8; 32]>) {
372    if !output.insert(node.digest) {
373        return;
374    }
375    for child in &node.children {
376        collect_digests(child, output);
377    }
378}
379
380fn proof_summary(nodes: &[ProofNode], edge_changes: usize) -> IndexProofSummary {
381    let mut summary = IndexProofSummary {
382        edge_changes,
383        ..IndexProofSummary::default()
384    };
385    for node in nodes {
386        node.summary(&mut summary);
387    }
388    summary
389}
holos_tda/index_proof.rs

holos_tda/
index_proof.rs
