commonware_consensus/simplex/
prover.rs

1use super::{
2    encoder::{
3        finalize_namespace, notarize_namespace, nullify_message, nullify_namespace,
4        proposal_message,
5    },
6    wire, View,
7};
8use crate::Proof;
9use bytes::{Buf, BufMut};
10use commonware_cryptography::Scheme;
11use commonware_utils::{Array, SizedSerialize};
12use std::{collections::HashSet, marker::PhantomData};
13
14/// Encode and decode proofs of activity.
15///
16/// We don't use protobuf for proof encoding because we expect external parties
17/// to decode proofs in constrained environments where protobuf may not be implemented.
18#[derive(Clone)]
19pub struct Prover<C: Scheme, D: Array> {
20    notarize_namespace: Vec<u8>,
21    nullify_namespace: Vec<u8>,
22    finalize_namespace: Vec<u8>,
23
24    _crypto: PhantomData<C>,
25    _digest: PhantomData<D>,
26}
27
28impl<C: Scheme, D: Array> Prover<C, D> {
29    /// Create a new prover with the given signing `namespace`.
30    pub fn new(namespace: &[u8]) -> Self {
31        Self {
32            notarize_namespace: notarize_namespace(namespace),
33            nullify_namespace: nullify_namespace(namespace),
34            finalize_namespace: finalize_namespace(namespace),
35
36            _crypto: PhantomData,
37            _digest: PhantomData,
38        }
39    }
40
41    /// Serialize a proposal proof.
42    pub fn serialize_proposal(
43        proposal: &wire::Proposal,
44        public_key: &C::PublicKey,
45        signature: &C::Signature,
46    ) -> Proof {
47        // Setup proof
48        let len = u64::SERIALIZED_LEN
49            + u64::SERIALIZED_LEN
50            + D::SERIALIZED_LEN
51            + C::PublicKey::SERIALIZED_LEN
52            + C::Signature::SERIALIZED_LEN;
53
54        // Encode proof
55        let mut proof = Vec::with_capacity(len);
56        proof.put_u64(proposal.view);
57        proof.put_u64(proposal.parent);
58        proof.extend_from_slice(&proposal.payload);
59        proof.extend_from_slice(public_key);
60        proof.extend_from_slice(signature);
61        proof.into()
62    }
63
64    /// Deserialize a proposal proof.
65    fn deserialize_proposal(
66        &self,
67        mut proof: Proof,
68        check_sig: bool,
69        namespace: &[u8],
70    ) -> Option<(View, View, D, C::PublicKey)> {
71        // Ensure proof is big enough
72        if proof.len()
73            != u64::SERIALIZED_LEN
74                + u64::SERIALIZED_LEN
75                + D::SERIALIZED_LEN
76                + C::PublicKey::SERIALIZED_LEN
77                + C::Signature::SERIALIZED_LEN
78        {
79            return None;
80        }
81
82        // Decode proof
83        let view = proof.get_u64();
84        let parent = proof.get_u64();
85        let payload = D::read_from(&mut proof).ok()?;
86        let public_key = C::PublicKey::read_from(&mut proof).ok()?;
87        let signature = C::Signature::read_from(&mut proof).ok()?;
88
89        // Verify signature
90        let proposal_message = proposal_message(view, parent, &payload);
91        if check_sig && !C::verify(Some(namespace), &proposal_message, &public_key, &signature) {
92            return None;
93        }
94
95        Some((view, parent, payload, public_key))
96    }
97
98    /// Serialize an aggregation proof.
99    pub fn serialize_aggregation(
100        proposal: &wire::Proposal,
101        signatures: Vec<(&C::PublicKey, C::Signature)>,
102    ) -> Proof {
103        // Setup proof
104        let len = u64::SERIALIZED_LEN
105            + u64::SERIALIZED_LEN
106            + D::SERIALIZED_LEN
107            + u32::SERIALIZED_LEN
108            + signatures.len() * (C::PublicKey::SERIALIZED_LEN + C::Signature::SERIALIZED_LEN);
109
110        // Encode proof
111        let mut proof = Vec::with_capacity(len);
112        proof.put_u64(proposal.view);
113        proof.put_u64(proposal.parent);
114        proof.extend_from_slice(&proposal.payload);
115        proof.put_u32(signatures.len() as u32);
116        for (public_key, signature) in signatures {
117            proof.extend_from_slice(public_key);
118            proof.extend_from_slice(&signature);
119        }
120        proof.into()
121    }
122
123    /// Deserialize an aggregation proof.
124    fn deserialize_aggregation(
125        &self,
126        mut proof: Proof,
127        max: u32,
128        check_sigs: bool,
129        namespace: &[u8],
130    ) -> Option<(View, View, D, Vec<C::PublicKey>)> {
131        // Ensure proof prefix is big enough
132        let len =
133            u64::SERIALIZED_LEN + u64::SERIALIZED_LEN + D::SERIALIZED_LEN + u32::SERIALIZED_LEN;
134        if proof.len() < len {
135            return None;
136        }
137
138        // Decode proof prefix
139        let view = proof.get_u64();
140        let parent = proof.get_u64();
141        let payload = D::read_from(&mut proof).ok()?;
142        let count = proof.get_u32();
143        if count > max {
144            return None;
145        }
146        let count = count as usize;
147        let message = proposal_message(view, parent, &payload);
148
149        // Check for integer overflow in size calculation
150        let item_size = C::PublicKey::SERIALIZED_LEN.checked_add(C::Signature::SERIALIZED_LEN)?;
151        let total_size = count.checked_mul(item_size)?;
152        if proof.remaining() != total_size {
153            return None;
154        }
155
156        // Decode signatures
157        let mut seen = HashSet::with_capacity(count);
158        for _ in 0..count {
159            // Check if already saw public key
160            let public_key = C::PublicKey::read_from(&mut proof).ok()?;
161            if seen.contains(&public_key) {
162                return None;
163            }
164            seen.insert(public_key.clone());
165
166            // Read signature
167            let signature = C::Signature::read_from(&mut proof).ok()?;
168
169            // Verify signature
170            if check_sigs && !C::verify(Some(namespace), &message, &public_key, &signature) {
171                return None;
172            }
173        }
174        Some((view, parent, payload, seen.into_iter().collect()))
175    }
176
177    /// Deserialize a notarize proof.
178    pub fn deserialize_notarize(
179        &self,
180        proof: Proof,
181        check_sig: bool,
182    ) -> Option<(View, View, D, C::PublicKey)> {
183        self.deserialize_proposal(proof, check_sig, &self.notarize_namespace)
184    }
185
186    /// Deserialize a notarization proof.
187    pub fn deserialize_notarization(
188        &self,
189        proof: Proof,
190        max: u32,
191        check_sigs: bool,
192    ) -> Option<(View, View, D, Vec<C::PublicKey>)> {
193        self.deserialize_aggregation(proof, max, check_sigs, &self.notarize_namespace)
194    }
195
196    /// Deserialize a finalize proof.
197    pub fn deserialize_finalize(
198        &self,
199        proof: Proof,
200        check_sig: bool,
201    ) -> Option<(View, View, D, C::PublicKey)> {
202        self.deserialize_proposal(proof, check_sig, &self.finalize_namespace)
203    }
204
205    /// Deserialize a finalization proof.
206    pub fn deserialize_finalization(
207        &self,
208        proof: Proof,
209        max: u32,
210        check_sigs: bool,
211    ) -> Option<(View, View, D, Vec<C::PublicKey>)> {
212        self.deserialize_aggregation(proof, max, check_sigs, &self.finalize_namespace)
213    }
214
215    #[allow(clippy::too_many_arguments)]
216    pub fn serialize_conflicting_proposal(
217        view: View,
218        public_key: &C::PublicKey,
219        parent_1: View,
220        payload_1: &D,
221        signature_1: &C::Signature,
222        parent_2: View,
223        payload_2: &D,
224        signature_2: &C::Signature,
225    ) -> Proof {
226        // Setup proof
227        let len = u64::SERIALIZED_LEN
228            + C::PublicKey::SERIALIZED_LEN
229            + u64::SERIALIZED_LEN
230            + D::SERIALIZED_LEN
231            + C::Signature::SERIALIZED_LEN
232            + u64::SERIALIZED_LEN
233            + D::SERIALIZED_LEN
234            + C::Signature::SERIALIZED_LEN;
235
236        // Encode proof
237        let mut proof = Vec::with_capacity(len);
238        proof.put_u64(view);
239        proof.extend_from_slice(public_key);
240        proof.put_u64(parent_1);
241        proof.extend_from_slice(payload_1);
242        proof.extend_from_slice(signature_1);
243        proof.put_u64(parent_2);
244        proof.extend_from_slice(payload_2);
245        proof.extend_from_slice(signature_2);
246        proof.into()
247    }
248
249    fn deserialize_conflicting_proposal(
250        &self,
251        mut proof: Proof,
252        check_sig: bool,
253        namespace: &[u8],
254    ) -> Option<(C::PublicKey, View)> {
255        // Ensure proof is big enough
256        let len = u64::SERIALIZED_LEN
257            + C::PublicKey::SERIALIZED_LEN
258            + u64::SERIALIZED_LEN
259            + D::SERIALIZED_LEN
260            + C::Signature::SERIALIZED_LEN
261            + u64::SERIALIZED_LEN
262            + D::SERIALIZED_LEN
263            + C::Signature::SERIALIZED_LEN;
264        if proof.len() != len {
265            return None;
266        }
267
268        // Decode proof
269        let view = proof.get_u64();
270        let public_key = C::PublicKey::read_from(&mut proof).ok()?;
271        let parent_1 = proof.get_u64();
272        let payload_1 = D::read_from(&mut proof).ok()?;
273        let signature_1 = C::Signature::read_from(&mut proof).ok()?;
274        let parent_2 = proof.get_u64();
275        let payload_2 = D::read_from(&mut proof).ok()?;
276        let signature_2 = C::Signature::read_from(&mut proof).ok()?;
277
278        // Verify signatures
279        if check_sig {
280            let proposal_message_1 = proposal_message(view, parent_1, &payload_1);
281            let proposal_message_2 = proposal_message(view, parent_2, &payload_2);
282            if !C::verify(
283                Some(namespace),
284                &proposal_message_1,
285                &public_key,
286                &signature_1,
287            ) || !C::verify(
288                Some(namespace),
289                &proposal_message_2,
290                &public_key,
291                &signature_2,
292            ) {
293                return None;
294            }
295        }
296        Some((public_key, view))
297    }
298
299    /// Serialize a conflicting notarize proof.
300    #[allow(clippy::too_many_arguments)]
301    pub fn serialize_conflicting_notarize(
302        view: View,
303        public_key: &C::PublicKey,
304        parent_1: View,
305        payload_1: &D,
306        signature_1: &C::Signature,
307        parent_2: View,
308        payload_2: &D,
309        signature_2: &C::Signature,
310    ) -> Proof {
311        Self::serialize_conflicting_proposal(
312            view,
313            public_key,
314            parent_1,
315            payload_1,
316            signature_1,
317            parent_2,
318            payload_2,
319            signature_2,
320        )
321    }
322
323    /// Deserialize a conflicting notarization proof.
324    pub fn deserialize_conflicting_notarize(
325        &self,
326        proof: Proof,
327        check_sig: bool,
328    ) -> Option<(C::PublicKey, View)> {
329        self.deserialize_conflicting_proposal(proof, check_sig, &self.notarize_namespace)
330    }
331
332    /// Serialize a conflicting finalize proof.
333    #[allow(clippy::too_many_arguments)]
334    pub fn serialize_conflicting_finalize(
335        view: View,
336        public_key: &C::PublicKey,
337        parent_1: View,
338        payload_1: &D,
339        signature_1: &C::Signature,
340        parent_2: View,
341        payload_2: &D,
342        signature_2: &C::Signature,
343    ) -> Proof {
344        Self::serialize_conflicting_proposal(
345            view,
346            public_key,
347            parent_1,
348            payload_1,
349            signature_1,
350            parent_2,
351            payload_2,
352            signature_2,
353        )
354    }
355
356    /// Deserialize a conflicting finalization proof.
357    pub fn deserialize_conflicting_finalize(
358        &self,
359        proof: Proof,
360        check_sig: bool,
361    ) -> Option<(C::PublicKey, View)> {
362        self.deserialize_conflicting_proposal(proof, check_sig, &self.finalize_namespace)
363    }
364
365    /// Serialize a conflicting nullify and finalize proof.
366    pub fn serialize_nullify_finalize(
367        view: View,
368        public_key: &C::PublicKey,
369        parent: View,
370        payload: &D,
371        signature_finalize: &C::Signature,
372        signature_null: &C::Signature,
373    ) -> Proof {
374        // Setup proof
375        let len = u64::SERIALIZED_LEN
376            + C::PublicKey::SERIALIZED_LEN
377            + u64::SERIALIZED_LEN
378            + D::SERIALIZED_LEN
379            + C::Signature::SERIALIZED_LEN
380            + C::Signature::SERIALIZED_LEN;
381
382        // Encode proof
383        let mut proof = Vec::with_capacity(len);
384        proof.put_u64(view);
385        proof.extend_from_slice(public_key);
386        proof.put_u64(parent);
387        proof.extend_from_slice(payload);
388        proof.extend_from_slice(signature_finalize);
389        proof.extend_from_slice(signature_null);
390        proof.into()
391    }
392
393    /// Deserialize a conflicting nullify and finalize proof.
394    pub fn deserialize_nullify_finalize(
395        &self,
396        mut proof: Proof,
397        check_sig: bool,
398    ) -> Option<(C::PublicKey, View)> {
399        // Ensure proof is big enough
400        let len = u64::SERIALIZED_LEN
401            + C::PublicKey::SERIALIZED_LEN
402            + u64::SERIALIZED_LEN
403            + D::SERIALIZED_LEN
404            + C::Signature::SERIALIZED_LEN
405            + C::Signature::SERIALIZED_LEN;
406        if proof.len() != len {
407            return None;
408        }
409
410        // Decode proof
411        let view = proof.get_u64();
412        let public_key = C::PublicKey::read_from(&mut proof).ok()?;
413        let parent = proof.get_u64();
414        let payload = D::read_from(&mut proof).ok()?;
415        let signature_finalize = C::Signature::read_from(&mut proof).ok()?;
416        let signature_null = C::Signature::read_from(&mut proof).ok()?;
417
418        // Verify signatures
419        if check_sig {
420            let finalize_message = proposal_message(view, parent, &payload);
421            let null_message = nullify_message(view);
422            if !C::verify(
423                Some(&self.finalize_namespace),
424                &finalize_message,
425                &public_key,
426                &signature_finalize,
427            ) || !C::verify(
428                Some(&self.nullify_namespace),
429                &null_message,
430                &public_key,
431                &signature_null,
432            ) {
433                return None;
434            }
435        }
436        Some((public_key, view))
437    }
438}
439
440#[cfg(test)]
441mod tests {
442    use super::*;
443    use commonware_cryptography::{sha256::Digest as Sha256Digest, Ed25519, Hasher, Sha256};
444    use rand::SeedableRng;
445
446    fn test_digest(value: u8) -> Sha256Digest {
447        let mut hasher = Sha256::new();
448        hasher.update(&[value]);
449        hasher.finalize()
450    }
451
452    #[test]
453    fn test_deserialize_aggregation_empty() {
454        // Create a proof with no signers
455        let prover = Prover::<Ed25519, Sha256Digest>::new(b"test");
456        let mut proof = Vec::new();
457        proof.put_u64(1); // view
458        proof.put_u64(0); // parent
459        proof.extend_from_slice(&test_digest(0)); // payload
460        proof.put_u32(0); // count of 0 signatures is valid
461
462        // Verify that the proof is accepted
463        let result =
464            prover.deserialize_aggregation(proof.into(), 10, false, &prover.notarize_namespace);
465        assert!(result.is_some());
466    }
467
468    #[test]
469    fn test_deserialize_aggregation_short_header() {
470        // Create a proof with incorrect signers
471        let mut proof = Vec::new();
472        proof.put_u64(1); // view
473        proof.put_u64(0); // parent
474        proof.extend_from_slice(&test_digest(0)); // payload
475
476        // Verify that the proof is rejected
477        let prover = Prover::<Ed25519, Sha256Digest>::new(b"test");
478        let result = prover.deserialize_aggregation(
479            proof.into(),
480            u32::MAX, // Allow any count to test overflow protection
481            false,
482            &prover.notarize_namespace,
483        );
484        assert!(result.is_none());
485    }
486
487    #[test]
488    fn test_deserialize_aggregation_malicious_count() {
489        // Create a proof with incorrect signers
490        let mut proof = Vec::new();
491        proof.put_u64(1); // view
492        proof.put_u64(0); // parent
493        proof.extend_from_slice(&test_digest(0)); // payload
494        proof.put_u32(100);
495
496        // Verify that the proof is rejected
497        let prover = Prover::<Ed25519, Sha256Digest>::new(b"test");
498        let result = prover.deserialize_aggregation(
499            proof.into(),
500            u32::MAX, // Allow any count to test overflow protection
501            false,
502            &prover.notarize_namespace,
503        );
504        assert!(result.is_none());
505    }
506
507    #[test]
508    fn test_deserialize_aggregation() {
509        // Verify correctness with and without checking signatures
510        for checked in [true, false] {
511            // Create a proposal to sign
512            let (view, parent, payload) = (1, 0, test_digest(0));
513            let proposal = wire::Proposal {
514                view,
515                parent,
516                payload: payload.to_vec(),
517            };
518            let message = proposal_message(view, parent, &payload);
519
520            // Sign the message with 3 different signers
521            const NAMESPACE: &[u8] = b"test";
522            let mut rng = rand::rngs::StdRng::seed_from_u64(0);
523            let mut signers: Vec<_> = (0..3).map(|_| Ed25519::new(&mut rng)).collect();
524            let pub_keys = signers
525                .iter()
526                .map(|signer| signer.public_key())
527                .collect::<Vec<_>>();
528            let sigs = signers
529                .iter_mut()
530                .map(|signer| signer.sign(Some(NAMESPACE), &message))
531                .collect::<Vec<_>>();
532            let keys_and_sigs = pub_keys.iter().zip(sigs).collect();
533
534            // Should be able to deserialize the serialized proof
535            let proof =
536                Prover::<Ed25519, Sha256Digest>::serialize_aggregation(&proposal, keys_and_sigs);
537            let prover = Prover::<Ed25519, Sha256Digest>::new(NAMESPACE);
538            let result = prover.deserialize_aggregation(proof, u32::MAX, checked, NAMESPACE);
539
540            // Deserialized proof should match the content of the original proof
541            let (view, parent, payload, signers) = result.expect("unable to deserialize proof");
542            assert_eq!(view, proposal.view);
543            assert_eq!(parent, proposal.parent);
544            assert_eq!(payload.as_ref(), &proposal.payload);
545            assert_eq!(signers.len(), 3);
546            for public_key in pub_keys.iter() {
547                assert!(signers.contains(public_key));
548            }
549        }
550    }
551}
commonware_consensus/simplex/prover.rs

commonware_consensus/simplex/
prover.rs
