ruvector_mincut/certificate/
mod.rs

1//! Certificate system for cut verification
2//!
3//! Provides provable certificates that a minimum cut is correct.
4//! Each certificate includes:
5//! - The witnesses that define the cut
6//! - The LocalKCut responses that prove no smaller cut exists
7//! - A proof structure for verification
8
9use crate::graph::{EdgeId, VertexId};
10use crate::instance::WitnessHandle;
11use crate::time_compat::PortableTimestamp;
12use serde::{Deserialize, Serialize};
13
14pub mod audit;
15
16pub use audit::{AuditData, AuditEntry, AuditEntryType, AuditLogger};
17
18/// Witness summary for serialization
19#[derive(Debug, Clone, Serialize, Deserialize)]
20pub struct WitnessSummary {
21    /// Seed vertex
22    pub seed: u64,
23    /// Boundary size
24    pub boundary: u64,
25    /// Number of vertices in the cut
26    pub cardinality: u64,
27}
28
29/// A certificate proving a minimum cut value
30#[derive(Debug, Clone, Serialize, Deserialize)]
31pub struct CutCertificate {
32    /// The witnesses (candidate cuts) that were maintained (non-serializable)
33    #[serde(skip)]
34    pub witnesses: Vec<WitnessHandle>,
35    /// Witness summaries for serialization
36    pub witness_summaries: Vec<WitnessSummary>,
37    /// LocalKCut responses that prove no smaller cut exists
38    pub localkcut_responses: Vec<LocalKCutResponse>,
39    /// Index of the best witness (smallest boundary)
40    pub best_witness_idx: Option<usize>,
41    /// Timestamp when certificate was created (seconds since UNIX epoch)
42    pub timestamp: u64,
43    /// Certificate version for compatibility
44    pub version: u32,
45}
46
47/// A response from the LocalKCut oracle
48#[derive(Debug, Clone, Serialize, Deserialize)]
49pub struct LocalKCutResponse {
50    /// The query that was made
51    pub query: CertLocalKCutQuery,
52    /// The result returned
53    pub result: LocalKCutResultSummary,
54    /// Timestamp of the query
55    pub timestamp: u64,
56    /// Optional provenance (which update triggered this)
57    pub trigger: Option<UpdateTrigger>,
58}
59
60impl LocalKCutResponse {
61    /// Create a new LocalKCut response
62    pub fn new(
63        query: CertLocalKCutQuery,
64        result: LocalKCutResultSummary,
65        timestamp: u64,
66        trigger: Option<UpdateTrigger>,
67    ) -> Self {
68        Self {
69            query,
70            result,
71            timestamp,
72            trigger,
73        }
74    }
75}
76
77/// A query to the LocalKCut oracle (certificate version)
78#[derive(Debug, Clone, Serialize, Deserialize)]
79pub struct CertLocalKCutQuery {
80    /// Seed vertices for the search
81    pub seed_vertices: Vec<VertexId>,
82    /// Budget k for cut size
83    pub budget_k: u64,
84    /// Search radius
85    pub radius: usize,
86}
87
88impl CertLocalKCutQuery {
89    /// Create a new LocalKCut query
90    pub fn new(seed_vertices: Vec<VertexId>, budget_k: u64, radius: usize) -> Self {
91        Self {
92            seed_vertices,
93            budget_k,
94            radius,
95        }
96    }
97}
98
99/// Summary of LocalKCut result
100#[derive(Debug, Clone, Serialize, Deserialize)]
101pub enum LocalKCutResultSummary {
102    /// Found a cut within the budget
103    Found {
104        /// The cut value found
105        cut_value: u64,
106        /// Hash of the witness for verification
107        witness_hash: u64,
108    },
109    /// No cut found in the local neighborhood
110    NoneInLocality,
111}
112
113/// Trigger for an update operation
114#[derive(Debug, Clone, Serialize, Deserialize)]
115pub struct UpdateTrigger {
116    /// Type of update (insert or delete)
117    pub update_type: UpdateType,
118    /// Edge ID involved
119    pub edge_id: EdgeId,
120    /// Endpoints of the edge
121    pub endpoints: (VertexId, VertexId),
122    /// Timestamp of the update
123    pub time: u64,
124}
125
126impl UpdateTrigger {
127    /// Create a new update trigger
128    pub fn new(
129        update_type: UpdateType,
130        edge_id: EdgeId,
131        endpoints: (VertexId, VertexId),
132        time: u64,
133    ) -> Self {
134        Self {
135            update_type,
136            edge_id,
137            endpoints,
138            time,
139        }
140    }
141}
142
143/// Type of graph update
144#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
145pub enum UpdateType {
146    /// Edge insertion
147    Insert,
148    /// Edge deletion
149    Delete,
150}
151
152/// Current certificate version
153pub const CERTIFICATE_VERSION: u32 = 1;
154
155impl CutCertificate {
156    /// Create a new empty certificate
157    pub fn new() -> Self {
158        Self {
159            witnesses: Vec::new(),
160            witness_summaries: Vec::new(),
161            localkcut_responses: Vec::new(),
162            best_witness_idx: None,
163            timestamp: PortableTimestamp::now().as_secs(),
164            version: CERTIFICATE_VERSION,
165        }
166    }
167
168    /// Create a certificate with initial witnesses
169    pub fn with_witnesses(witnesses: Vec<WitnessHandle>) -> Self {
170        let mut cert = Self::new();
171        let summaries: Vec<WitnessSummary> = witnesses
172            .iter()
173            .map(|w| WitnessSummary {
174                seed: w.seed(),
175                boundary: w.boundary_size(),
176                cardinality: w.cardinality(),
177            })
178            .collect();
179        cert.witnesses = witnesses;
180        cert.witness_summaries = summaries;
181        cert
182    }
183
184    /// Add a LocalKCut response to the certificate
185    pub fn add_response(&mut self, response: LocalKCutResponse) {
186        self.localkcut_responses.push(response);
187    }
188
189    /// Update the best witness
190    pub fn set_best_witness(&mut self, idx: usize, witness: WitnessHandle) {
191        let summary = WitnessSummary {
192            seed: witness.seed(),
193            boundary: witness.boundary_size(),
194            cardinality: witness.cardinality(),
195        };
196
197        if idx < self.witnesses.len() {
198            self.witnesses[idx] = witness;
199            self.witness_summaries[idx] = summary;
200            self.best_witness_idx = Some(idx);
201        } else {
202            self.witnesses.push(witness);
203            self.witness_summaries.push(summary);
204            self.best_witness_idx = Some(self.witnesses.len() - 1);
205        }
206    }
207
208    /// Verify the certificate is internally consistent
209    pub fn verify(&self) -> Result<(), CertificateError> {
210        // Check version compatibility
211        if self.version > CERTIFICATE_VERSION {
212            return Err(CertificateError::IncompatibleVersion {
213                found: self.version,
214                expected: CERTIFICATE_VERSION,
215            });
216        }
217
218        // Check if we have at least one witness summary (for deserialized certs)
219        // or witness (for in-memory certs)
220        if self.witnesses.is_empty() && self.witness_summaries.is_empty() {
221            return Err(CertificateError::NoWitness);
222        }
223
224        // Verify best witness index is valid
225        if let Some(idx) = self.best_witness_idx {
226            let max_idx = self.witnesses.len().max(self.witness_summaries.len());
227            if max_idx > 0 && idx >= max_idx {
228                return Err(CertificateError::InvalidWitnessIndex {
229                    index: idx,
230                    max: max_idx - 1,
231                });
232            }
233        }
234
235        // Verify consistency of LocalKCut responses
236        for response in &self.localkcut_responses {
237            if response.query.budget_k == 0 {
238                return Err(CertificateError::InvalidQuery {
239                    reason: "Budget k must be positive".to_string(),
240                });
241            }
242        }
243
244        Ok(())
245    }
246
247    /// Get the certified minimum cut value
248    pub fn certified_value(&self) -> Option<u64> {
249        self.best_witness_idx
250            .and_then(|idx| self.witnesses.get(idx).map(|w| w.boundary_size()))
251    }
252
253    /// Get the best witness
254    pub fn best_witness(&self) -> Option<&WitnessHandle> {
255        self.best_witness_idx
256            .and_then(|idx| self.witnesses.get(idx))
257    }
258
259    /// Export to JSON for external verification
260    pub fn to_json(&self) -> Result<String, CertificateError> {
261        serde_json::to_string_pretty(self)
262            .map_err(|e| CertificateError::SerializationError(e.to_string()))
263    }
264
265    /// Import from JSON
266    pub fn from_json(json: &str) -> Result<Self, CertificateError> {
267        serde_json::from_str(json)
268            .map_err(|e| CertificateError::DeserializationError(e.to_string()))
269    }
270
271    /// Get number of witnesses
272    pub fn num_witnesses(&self) -> usize {
273        self.witnesses.len()
274    }
275
276    /// Get number of LocalKCut responses
277    pub fn num_responses(&self) -> usize {
278        self.localkcut_responses.len()
279    }
280
281    /// Get all witnesses
282    pub fn witnesses(&self) -> &[WitnessHandle] {
283        &self.witnesses
284    }
285
286    /// Get all LocalKCut responses
287    pub fn responses(&self) -> &[LocalKCutResponse] {
288        &self.localkcut_responses
289    }
290}
291
292impl Default for CutCertificate {
293    fn default() -> Self {
294        Self::new()
295    }
296}
297
298/// Errors that can occur during certificate operations
299#[derive(Debug, Clone, PartialEq, Eq)]
300pub enum CertificateError {
301    /// No witness available in certificate
302    NoWitness,
303    /// Inconsistent boundary calculation
304    InconsistentBoundary {
305        /// Expected boundary value
306        expected: u64,
307        /// Actual boundary value
308        actual: u64,
309    },
310    /// Missing LocalKCut proof for a required operation
311    MissingLocalKCutProof {
312        /// Description of missing proof
313        operation: String,
314    },
315    /// Invalid witness index
316    InvalidWitnessIndex {
317        /// The invalid index
318        index: usize,
319        /// Maximum valid index
320        max: usize,
321    },
322    /// Invalid query parameters
323    InvalidQuery {
324        /// Reason for invalidity
325        reason: String,
326    },
327    /// Incompatible certificate version
328    IncompatibleVersion {
329        /// Version found in certificate
330        found: u32,
331        /// Expected version
332        expected: u32,
333    },
334    /// Serialization error
335    SerializationError(String),
336    /// Deserialization error
337    DeserializationError(String),
338}
339
340impl std::fmt::Display for CertificateError {
341    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
342        match self {
343            Self::NoWitness => write!(f, "No witness available in certificate"),
344            Self::InconsistentBoundary { expected, actual } => {
345                write!(
346                    f,
347                    "Inconsistent boundary: expected {}, got {}",
348                    expected, actual
349                )
350            }
351            Self::MissingLocalKCutProof { operation } => {
352                write!(f, "Missing LocalKCut proof for operation: {}", operation)
353            }
354            Self::InvalidWitnessIndex { index, max } => {
355                write!(f, "Invalid witness index {} (max: {})", index, max)
356            }
357            Self::InvalidQuery { reason } => {
358                write!(f, "Invalid query: {}", reason)
359            }
360            Self::IncompatibleVersion { found, expected } => {
361                write!(
362                    f,
363                    "Incompatible version: found {}, expected {}",
364                    found, expected
365                )
366            }
367            Self::SerializationError(msg) => {
368                write!(f, "Serialization error: {}", msg)
369            }
370            Self::DeserializationError(msg) => {
371                write!(f, "Deserialization error: {}", msg)
372            }
373        }
374    }
375}
376
377impl std::error::Error for CertificateError {}
378
379#[cfg(test)]
380mod tests {
381    use super::*;
382    use roaring::RoaringBitmap;
383
384    #[test]
385    fn test_new_certificate() {
386        let cert = CutCertificate::new();
387        assert_eq!(cert.num_witnesses(), 0);
388        assert_eq!(cert.num_responses(), 0);
389        assert_eq!(cert.version, CERTIFICATE_VERSION);
390        assert!(cert.best_witness_idx.is_none());
391    }
392
393    #[test]
394    fn test_add_witness() {
395        let mut cert = CutCertificate::new();
396        let witness = WitnessHandle::new(1, RoaringBitmap::from_iter([1, 2, 3]), 5);
397
398        cert.set_best_witness(0, witness.clone());
399        assert_eq!(cert.num_witnesses(), 1);
400        assert_eq!(cert.best_witness_idx, Some(0));
401        assert_eq!(cert.certified_value(), Some(5));
402    }
403
404    #[test]
405    fn test_add_response() {
406        let mut cert = CutCertificate::new();
407        let query = CertLocalKCutQuery::new(vec![1, 2], 10, 5);
408        let result = LocalKCutResultSummary::Found {
409            cut_value: 5,
410            witness_hash: 12345,
411        };
412        let response = LocalKCutResponse::new(query, result, 100, None);
413
414        cert.add_response(response);
415        assert_eq!(cert.num_responses(), 1);
416    }
417
418    #[test]
419    fn test_verify_empty() {
420        let cert = CutCertificate::new();
421        assert!(matches!(cert.verify(), Err(CertificateError::NoWitness)));
422    }
423
424    #[test]
425    fn test_verify_valid() {
426        let mut cert = CutCertificate::new();
427        let witness = WitnessHandle::new(1, RoaringBitmap::from_iter([1, 2]), 3);
428        cert.set_best_witness(0, witness);
429
430        assert!(cert.verify().is_ok());
431    }
432
433    #[test]
434    fn test_verify_invalid_index() {
435        let mut cert = CutCertificate::new();
436        // Add a witness so the certificate is not empty
437        let witness = WitnessHandle::new(1, RoaringBitmap::from_iter([1, 2]), 5);
438        cert.set_best_witness(0, witness);
439        // Now set an invalid index
440        cert.best_witness_idx = Some(5);
441
442        let result = cert.verify();
443        assert!(matches!(
444            result,
445            Err(CertificateError::InvalidWitnessIndex { .. })
446        ));
447    }
448
449    #[test]
450    fn test_json_roundtrip() {
451        let mut cert = CutCertificate::new();
452        let witness = WitnessHandle::new(1, RoaringBitmap::from_iter([1, 2, 3]), 5);
453        cert.set_best_witness(0, witness);
454
455        let query = CertLocalKCutQuery::new(vec![1], 5, 2);
456        let result = LocalKCutResultSummary::Found {
457            cut_value: 3,
458            witness_hash: 999,
459        };
460        let response = LocalKCutResponse::new(query, result, 100, None);
461        cert.add_response(response);
462
463        let json = cert.to_json().unwrap();
464        let cert2 = CutCertificate::from_json(&json).unwrap();
465
466        // Witnesses are not serialized, only summaries
467        assert_eq!(cert2.witness_summaries.len(), 1);
468        assert_eq!(cert2.num_responses(), 1);
469        assert_eq!(cert2.version, cert.version);
470    }
471
472    #[test]
473    fn test_best_witness() {
474        let mut cert = CutCertificate::new();
475        let witness1 = WitnessHandle::new(1, RoaringBitmap::from_iter([1, 2]), 10);
476        let witness2 = WitnessHandle::new(2, RoaringBitmap::from_iter([2, 3, 4]), 5);
477
478        cert.set_best_witness(0, witness1);
479        cert.set_best_witness(1, witness2);
480
481        let best = cert.best_witness().unwrap();
482        assert_eq!(best.boundary_size(), 5);
483    }
484
485    #[test]
486    fn test_update_trigger() {
487        let trigger = UpdateTrigger::new(UpdateType::Insert, 123, (1, 2), 1000);
488        assert_eq!(trigger.update_type, UpdateType::Insert);
489        assert_eq!(trigger.edge_id, 123);
490        assert_eq!(trigger.endpoints, (1, 2));
491        assert_eq!(trigger.time, 1000);
492    }
493
494    #[test]
495    fn test_local_kcut_query() {
496        let query = CertLocalKCutQuery::new(vec![1, 2, 3], 10, 5);
497        assert_eq!(query.seed_vertices.len(), 3);
498        assert_eq!(query.budget_k, 10);
499        assert_eq!(query.radius, 5);
500    }
501
502    #[test]
503    fn test_local_kcut_response() {
504        let query = CertLocalKCutQuery::new(vec![1], 5, 2);
505        let result = LocalKCutResultSummary::Found {
506            cut_value: 3,
507            witness_hash: 999,
508        };
509        let response = LocalKCutResponse::new(query, result, 500, None);
510
511        assert_eq!(response.timestamp, 500);
512        assert!(response.trigger.is_none());
513    }
514
515    #[test]
516    fn test_certificate_error_display() {
517        let err = CertificateError::NoWitness;
518        assert!(err.to_string().contains("No witness"));
519
520        let err = CertificateError::InvalidWitnessIndex { index: 5, max: 3 };
521        assert!(err.to_string().contains("Invalid witness index"));
522    }
523}
ruvector_mincut/certificate/mod.rs

ruvector_mincut/certificate/
mod.rs
