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

ruvector_mincut/certificate/
mod.rs
