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

ruvector_mincut/certificate/
mod.rs
