aleph_bft_crypto/
signature.rs

1use crate::{Index, NodeCount, NodeIndex, NodeMap};
2use codec::{Codec, Decode, Encode};
3use log::warn;
4use std::{fmt::Debug, hash::Hash};
5
6/// The type used as a signature.
7///
8/// The Signature typically does not contain the index of the node who signed the data.
9pub trait Signature: Debug + Clone + Codec + Send + Sync + Eq + 'static {}
10
11impl<T: Debug + Clone + Codec + Send + Sync + Eq + 'static> Signature for T {}
12
13/// Abstraction of the signing data and verifying signatures.
14///
15/// A typical implementation of Keychain would be a collection of `N` public keys,
16/// an index `i` and a single private key corresponding to the public key number `i`.
17/// The meaning of sign is then to produce a signature `s` using the given private key,
18/// and `verify(msg, s, j)` is to verify whether the signature s under the message msg is
19/// correct with respect to the public key of the jth node.
20pub trait Keychain: Index + Clone + Send + Sync + 'static {
21    type Signature: Signature;
22
23    /// Returns the total number of known public keys.
24    fn node_count(&self) -> NodeCount;
25    /// Signs a message `msg`.
26    fn sign(&self, msg: &[u8]) -> Self::Signature;
27    /// Verifies whether a node with `index` correctly signed the message `msg`.
28    /// Should always return false for indices outside the node range.
29    fn verify(&self, msg: &[u8], sgn: &Self::Signature, index: NodeIndex) -> bool;
30}
31
32/// A type to which signatures can be aggregated.
33///
34/// Any signature can be added to multisignature.
35/// After adding sufficiently many signatures, the partial multisignature becomes a "complete"
36/// multisignature.
37/// Whether a multisignature is complete, can be verified with [`MultiKeychain::is_complete`] method.
38/// The signature and the index passed to the `add_signature` method are required to be valid.
39pub trait PartialMultisignature: Signature {
40    type Signature: Signature;
41    /// Adds the signature.
42    #[must_use = "consumes the original and returns the aggregated signature which should be used"]
43    fn add_signature(self, signature: &Self::Signature, index: NodeIndex) -> Self;
44}
45
46/// Extends Keychain with multisigning functionalities.
47///
48/// A single Signature can be raised to a Multisignature.
49/// Allows to verify whether a partial multisignature is complete (and valid).
50pub trait MultiKeychain: Keychain {
51    type PartialMultisignature: PartialMultisignature<Signature = Self::Signature>;
52    /// Transform a single signature to a multisignature consisting of the signature.
53    fn bootstrap_multi(
54        &self,
55        signature: &Self::Signature,
56        index: NodeIndex,
57    ) -> Self::PartialMultisignature;
58    /// Checks if enough signatures have beed added.
59    fn is_complete(&self, msg: &[u8], partial: &Self::PartialMultisignature) -> bool;
60}
61
62/// A set of signatures of a subset of nodes serving as a (partial) multisignature
63pub type SignatureSet<S> = NodeMap<S>;
64
65impl<S: Signature> PartialMultisignature for SignatureSet<S> {
66    type Signature = S;
67
68    #[must_use = "consumes the original and returns the aggregated signature which should be used"]
69    fn add_signature(mut self, signature: &Self::Signature, index: NodeIndex) -> Self {
70        self.insert(index, signature.clone());
71        self
72    }
73}
74
75/// Data which can be signed.
76///
77/// Signable data should provide a hash of type [`Self::Hash`] which is build from all parts of the
78/// data which should be signed. The type [`Self::Hash`] should implement [`AsRef<[u8]>`], and
79/// the bytes returned by `hash.as_ref()` are used by a [`MultiKeychain`] to sign the data.
80pub trait Signable {
81    type Hash: AsRef<[u8]>;
82    /// Return a hash for signing.
83    fn hash(&self) -> Self::Hash;
84}
85
86impl<T: AsRef<[u8]> + Clone> Signable for T {
87    type Hash = T;
88    fn hash(&self) -> Self::Hash {
89        self.clone()
90    }
91}
92
93/// A pair consisting of an instance of the `Signable` trait and an (arbitrary) signature.
94///
95/// The method `[UncheckedSigned::check]` can be used to upgrade this `struct` to
96/// `[Signed<T, K>]` which ensures that the signature matches the signed object.
97#[derive(Clone, Eq, PartialEq, Hash, Debug, Decode, Encode)]
98pub struct UncheckedSigned<T: Signable, S: Signature> {
99    signable: T,
100    signature: S,
101}
102
103impl<T: Signable, S: Signature> UncheckedSigned<T, S> {
104    pub fn as_signable(&self) -> &T {
105        &self.signable
106    }
107
108    pub fn into_signable(self) -> T {
109        self.signable
110    }
111
112    pub fn signature(&self) -> S {
113        self.signature.clone()
114    }
115}
116
117impl<T: Signable, S: Signature> UncheckedSigned<Indexed<T>, S> {
118    pub fn as_signable_strip_index(&self) -> &T {
119        &self.signable.signable
120    }
121}
122
123/// Error type returned when a verification of a signature fails.
124#[derive(Clone, Eq, PartialEq, Hash, Debug, Decode, Encode)]
125pub struct SignatureError<T: Signable, S: Signature> {
126    pub unchecked: UncheckedSigned<T, S>,
127}
128
129impl<T: Signable + Index, S: Signature> UncheckedSigned<T, S> {
130    /// Verifies whether the signature matches the key with the index as in the signed data.
131    pub fn check<K: Keychain<Signature = S>>(
132        self,
133        keychain: &K,
134    ) -> Result<Signed<T, K>, SignatureError<T, S>> {
135        let index = self.signable.index();
136        if !keychain.verify(self.signable.hash().as_ref(), &self.signature, index) {
137            return Err(SignatureError { unchecked: self });
138        }
139        Ok(Signed { unchecked: self })
140    }
141}
142
143impl<T: Signable + Index, S: Signature> Index for UncheckedSigned<T, S> {
144    fn index(&self) -> NodeIndex {
145        self.signable.index()
146    }
147}
148
149impl<T: Signable, S: PartialMultisignature> UncheckedSigned<T, S> {
150    /// Verifies whether the multisignature matches the signed data.
151    pub fn check_multi<MK: MultiKeychain<PartialMultisignature = S>>(
152        self,
153        keychain: &MK,
154    ) -> Result<Multisigned<T, MK>, SignatureError<T, S>> {
155        if !(keychain.is_complete(self.signable.hash().as_ref(), &self.signature)) {
156            return Err(SignatureError { unchecked: self });
157        }
158        Ok(Multisigned { unchecked: self })
159    }
160}
161
162impl<T: Signable, S: Signature> UncheckedSigned<Indexed<T>, S> {
163    fn strip_index(self) -> UncheckedSigned<T, S> {
164        UncheckedSigned {
165            signable: self.signable.strip_index(),
166            signature: self.signature,
167        }
168    }
169}
170
171impl<T: Signable, S: Signature> From<UncheckedSigned<Indexed<T>, S>> for UncheckedSigned<T, S> {
172    fn from(us: UncheckedSigned<Indexed<T>, S>) -> Self {
173        us.strip_index()
174    }
175}
176
177/// A correctly signed object of type `T`.
178#[derive(Eq, PartialEq, Hash, Debug, Decode, Encode)]
179pub struct Signed<T: Signable + Index, K: Keychain> {
180    unchecked: UncheckedSigned<T, K::Signature>,
181}
182
183impl<T: Signable + Clone + Index, K: Keychain> Clone for Signed<T, K> {
184    fn clone(&self) -> Self {
185        Signed {
186            unchecked: self.unchecked.clone(),
187        }
188    }
189}
190
191impl<T: Signable + Index, K: Keychain> Signed<T, K> {
192    /// Create a signed object from a signable. The index of `signable` must match the index of the `keychain`.
193    pub fn sign(signable: T, keychain: &K) -> Signed<T, K> {
194        assert_eq!(signable.index(), keychain.index());
195        let signature = keychain.sign(signable.hash().as_ref());
196        Signed {
197            unchecked: UncheckedSigned {
198                signable,
199                signature,
200            },
201        }
202    }
203
204    /// Get a reference to the signed object.
205    pub fn as_signable(&self) -> &T {
206        &self.unchecked.signable
207    }
208
209    pub fn into_signable(self) -> T {
210        self.unchecked.signable
211    }
212
213    pub fn into_unchecked(self) -> UncheckedSigned<T, K::Signature> {
214        self.unchecked
215    }
216}
217
218impl<T: Signable, K: Keychain> Signed<Indexed<T>, K> {
219    /// Create a signed object from a signable. The index is added based on the index of the `keychain`.
220    pub fn sign_with_index(signable: T, keychain: &K) -> Signed<Indexed<T>, K> {
221        Signed::sign(Indexed::new(signable, keychain.index()), keychain)
222    }
223}
224
225impl<T: Signable, MK: MultiKeychain> Signed<Indexed<T>, MK> {
226    /// Transform a singly signed object into a partially multisigned consisting of just the signed object.
227    /// Note that depending on the setup, it may yield a complete signature.
228    pub fn into_partially_multisigned(self, keychain: &MK) -> PartiallyMultisigned<T, MK> {
229        let multisignature =
230            keychain.bootstrap_multi(&self.unchecked.signature, self.unchecked.signable.index);
231        let unchecked = UncheckedSigned {
232            signable: self.unchecked.signable.strip_index(),
233            signature: multisignature,
234        };
235        if keychain.is_complete(unchecked.signable.hash().as_ref(), &unchecked.signature) {
236            PartiallyMultisigned::Complete {
237                multisigned: Multisigned { unchecked },
238            }
239        } else {
240            PartiallyMultisigned::Incomplete { unchecked }
241        }
242    }
243}
244
245impl<T: Signable + Index, K: Keychain> From<Signed<T, K>> for UncheckedSigned<T, K::Signature> {
246    fn from(signed: Signed<T, K>) -> Self {
247        signed.into_unchecked()
248    }
249}
250
251/// A pair consistsing of signable data and a [`NodeIndex`].
252///
253/// This is a wrapper used for signing data which does not implement the [`Index`] trait.
254/// If a node with an index `i` needs to sign some data `signable` which does not
255/// implement the [`Index`] trait, it should use the `Signed::sign_with_index` method which will
256/// use this wrapper transparently. Note that in the implementation of `Signable` for `Indexed<T>`,
257/// the hash is the hash of the underlying data `T`. Therefore, instances of the type
258/// [`Signed<Indexed<T>, MK>`] can be aggregated into `Multisigned<T, MK>`
259#[derive(Clone, Eq, PartialEq, Hash, Debug, Decode, Encode)]
260pub struct Indexed<T: Signable> {
261    signable: T,
262    index: NodeIndex,
263}
264
265impl<T: Signable> Indexed<T> {
266    fn new(signable: T, index: NodeIndex) -> Self {
267        Indexed { signable, index }
268    }
269
270    fn strip_index(self) -> T {
271        self.signable
272    }
273
274    pub fn as_signable(&self) -> &T {
275        &self.signable
276    }
277}
278
279impl<T: Signable> Signable for Indexed<T> {
280    type Hash = T::Hash;
281
282    fn hash(&self) -> Self::Hash {
283        self.signable.hash()
284    }
285}
286
287impl<T: Signable> Index for Indexed<T> {
288    fn index(&self) -> NodeIndex {
289        self.index
290    }
291}
292
293/// Signable data together with a complete multisignature.
294///
295/// An instance of `Multisigned<T: Signable, MK: MultiKeychain>` consists of a data of type `T`
296/// together with a multisignature which is valid and complete according to a multikeychain
297/// reference `MK`.
298#[derive(Eq, PartialEq, Hash, Debug, Decode, Encode)]
299pub struct Multisigned<T: Signable, MK: MultiKeychain> {
300    unchecked: UncheckedSigned<T, MK::PartialMultisignature>,
301}
302
303impl<T: Signable, MK: MultiKeychain> Multisigned<T, MK> {
304    /// Get a reference to the multisigned object.
305    pub fn as_signable(&self) -> &T {
306        &self.unchecked.signable
307    }
308
309    pub fn into_unchecked(self) -> UncheckedSigned<T, MK::PartialMultisignature> {
310        self.unchecked
311    }
312}
313
314impl<T: Signable, MK: MultiKeychain> From<Multisigned<T, MK>>
315    for UncheckedSigned<T, MK::PartialMultisignature>
316{
317    fn from(signed: Multisigned<T, MK>) -> Self {
318        signed.into_unchecked()
319    }
320}
321
322impl<T: Signable + Clone, MK: MultiKeychain> Clone for Multisigned<T, MK> {
323    fn clone(&self) -> Self {
324        Multisigned {
325            unchecked: self.unchecked.clone(),
326        }
327    }
328}
329
330/// Error resulting from multisignature being incomplete.
331///
332/// ### `Hash` derivation
333/// `PartiallyMultisigned` only conditionally implements `Hash`:
334/// ```rust
335/// # use std::hash::Hasher;
336/// # use aleph_bft_crypto::{MultiKeychain, PartiallyMultisigned, Signable};
337/// # trait Hash {};
338/// impl<'a, T: Hash + Signable, MK: Hash + MultiKeychain>
339///    Hash for PartiallyMultisigned<T, MK>
340/// where MK::PartialMultisignature: Hash {}
341/// ```
342/// i.e. Rust automatically adds `where MK::PartialMultisignature: Hash`.
343///
344/// This is a problem, since such `where` guard cannot be inferred for
345/// `IncompleteMultisignatureError` (because we do not use the associate type
346/// `MK::PartialMultisignature` of `MK` explicitly here).
347///
348/// The alternative solution could be to make `Signature: Hash` or add a phantom marker using
349/// `MK::PartialMultisignature` type.
350#[derive(Clone, Eq, PartialEq, Debug, Decode, Encode)]
351pub struct IncompleteMultisignatureError<T: Signable, MK: MultiKeychain> {
352    pub partial: PartiallyMultisigned<T, MK>,
353}
354
355/// Signable data together with a valid partial multisignature.
356///
357/// Instances of this type keep track whether the partial multisignautre is complete or not.
358/// If the multisignature is complete, you can get [`Multisigned`] by pattern matching
359/// against the variant [`PartiallyMultisigned::Complete`].
360#[derive(Clone, Eq, PartialEq, Hash, Debug, Decode, Encode)]
361pub enum PartiallyMultisigned<T: Signable, MK: MultiKeychain> {
362    Incomplete {
363        unchecked: UncheckedSigned<T, MK::PartialMultisignature>,
364    },
365    Complete {
366        multisigned: Multisigned<T, MK>,
367    },
368}
369
370impl<T: Signable, MK: MultiKeychain> PartiallyMultisigned<T, MK> {
371    /// Create a partially multisigned object.
372    pub fn sign(signable: T, keychain: &MK) -> PartiallyMultisigned<T, MK> {
373        Signed::sign_with_index(signable, keychain).into_partially_multisigned(keychain)
374    }
375
376    /// Chceck if the partial multisignature is complete.
377    pub fn is_complete(&self) -> bool {
378        match self {
379            PartiallyMultisigned::Incomplete { .. } => false,
380            PartiallyMultisigned::Complete { .. } => true,
381        }
382    }
383
384    /// Get a reference to the multisigned object.
385    pub fn as_signable(&self) -> &T {
386        match self {
387            PartiallyMultisigned::Incomplete { unchecked } => unchecked.as_signable(),
388            PartiallyMultisigned::Complete { multisigned } => multisigned.as_signable(),
389        }
390    }
391
392    /// Return the object that is being signed.
393    pub fn into_unchecked(self) -> UncheckedSigned<T, MK::PartialMultisignature> {
394        match self {
395            PartiallyMultisigned::Incomplete { unchecked } => unchecked,
396            PartiallyMultisigned::Complete { multisigned } => multisigned.unchecked,
397        }
398    }
399
400    /// Adds a signature and checks if multisignature is complete.
401    #[must_use = "consumes the original and returns the aggregated signature which should be used"]
402    pub fn add_signature(self, signed: Signed<Indexed<T>, MK>, keychain: &MK) -> Self {
403        if self.as_signable().hash().as_ref() != signed.as_signable().hash().as_ref() {
404            warn!(target: "AlephBFT-signed", "Tried to add a signature of a different object");
405            return self;
406        }
407        match self {
408            PartiallyMultisigned::Incomplete { mut unchecked } => {
409                unchecked.signature = unchecked
410                    .signature
411                    .add_signature(&signed.unchecked.signature, signed.unchecked.signable.index);
412                if keychain.is_complete(unchecked.signable.hash().as_ref(), &unchecked.signature) {
413                    PartiallyMultisigned::Complete {
414                        multisigned: Multisigned { unchecked },
415                    }
416                } else {
417                    PartiallyMultisigned::Incomplete { unchecked }
418                }
419            }
420            PartiallyMultisigned::Complete { .. } => self,
421        }
422    }
423}
424
425#[cfg(test)]
426mod tests {
427
428    use crate::{
429        Index, Keychain, MultiKeychain, NodeCount, NodeIndex, PartialMultisignature,
430        PartiallyMultisigned, Signable, SignatureSet, Signed,
431    };
432    use codec::{Decode, Encode};
433    use std::fmt::Debug;
434
435    /// Keychain wrapper which implements MultiKeychain such that a partial multisignature is a list of
436    /// signatures and a partial multisignature is considered complete if it contains more than 2N/3 signatures.
437    ///
438    /// Note: this way of multisigning is very inefficient, and should be used only for testing.
439    #[derive(Debug, Clone)]
440    struct DefaultMultiKeychain<K: Keychain> {
441        keychain: K,
442    }
443
444    impl<K: Keychain> DefaultMultiKeychain<K> {
445        // Create a new `DefaultMultiKeychain` using the provided `Keychain`.
446        fn new(keychain: K) -> Self {
447            DefaultMultiKeychain { keychain }
448        }
449    }
450
451    impl<K: Keychain> Index for DefaultMultiKeychain<K> {
452        fn index(&self) -> NodeIndex {
453            self.keychain.index()
454        }
455    }
456
457    impl<K: Keychain> Keychain for DefaultMultiKeychain<K> {
458        type Signature = K::Signature;
459
460        fn node_count(&self) -> NodeCount {
461            self.keychain.node_count()
462        }
463
464        fn sign(&self, msg: &[u8]) -> Self::Signature {
465            self.keychain.sign(msg)
466        }
467
468        fn verify(&self, msg: &[u8], sgn: &Self::Signature, index: NodeIndex) -> bool {
469            self.keychain.verify(msg, sgn, index)
470        }
471    }
472
473    impl<K: Keychain> MultiKeychain for DefaultMultiKeychain<K> {
474        type PartialMultisignature = SignatureSet<K::Signature>;
475
476        fn bootstrap_multi(
477            &self,
478            signature: &Self::Signature,
479            index: NodeIndex,
480        ) -> Self::PartialMultisignature {
481            SignatureSet::add_signature(
482                SignatureSet::with_size(self.node_count()),
483                signature,
484                index,
485            )
486        }
487
488        fn is_complete(&self, msg: &[u8], partial: &Self::PartialMultisignature) -> bool {
489            let signature_count = partial.iter().count();
490            if signature_count < self.node_count().consensus_threshold().0 {
491                return false;
492            }
493            partial
494                .iter()
495                .all(|(i, sgn)| self.keychain.verify(msg, sgn, i))
496        }
497    }
498
499    #[derive(Clone, Debug, Default, PartialEq, Eq)]
500    struct TestMessage {
501        msg: Vec<u8>,
502    }
503
504    impl Signable for TestMessage {
505        type Hash = Vec<u8>;
506        fn hash(&self) -> Self::Hash {
507            self.msg.clone()
508        }
509    }
510
511    fn test_message() -> TestMessage {
512        TestMessage {
513            msg: "Hello".as_bytes().to_vec(),
514        }
515    }
516
517    #[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
518    struct TestSignature {
519        msg: Vec<u8>,
520        index: NodeIndex,
521    }
522
523    #[derive(Clone, Debug)]
524    struct TestKeychain {
525        count: NodeCount,
526        index: NodeIndex,
527    }
528
529    impl TestKeychain {
530        fn new(count: NodeCount, index: NodeIndex) -> Self {
531            TestKeychain { count, index }
532        }
533    }
534
535    impl Index for TestKeychain {
536        fn index(&self) -> NodeIndex {
537            self.index
538        }
539    }
540
541    impl Keychain for TestKeychain {
542        type Signature = TestSignature;
543
544        fn node_count(&self) -> NodeCount {
545            self.count
546        }
547
548        fn sign(&self, msg: &[u8]) -> Self::Signature {
549            TestSignature {
550                msg: msg.to_vec(),
551                index: self.index,
552            }
553        }
554
555        fn verify(&self, msg: &[u8], sgn: &Self::Signature, index: NodeIndex) -> bool {
556            index == sgn.index && msg == sgn.msg
557        }
558    }
559
560    type TestMultiKeychain = DefaultMultiKeychain<TestKeychain>;
561
562    fn test_multi_keychain(node_count: NodeCount, index: NodeIndex) -> TestMultiKeychain {
563        let keychain = TestKeychain::new(node_count, index);
564        DefaultMultiKeychain::new(keychain)
565    }
566
567    #[test]
568    fn test_valid_signatures() {
569        let node_count: NodeCount = 7.into();
570        let keychains: Vec<TestMultiKeychain> = (0_usize..node_count.0)
571            .map(|i| test_multi_keychain(node_count, i.into()))
572            .collect();
573        for i in 0..node_count.0 {
574            for j in 0..node_count.0 {
575                let msg = test_message();
576                let signed_msg = Signed::sign_with_index(msg.clone(), &keychains[i]);
577                let unchecked_msg = signed_msg.into_unchecked();
578                assert!(
579                    unchecked_msg.check(&keychains[j]).is_ok(),
580                    "Signed message should be valid"
581                );
582            }
583        }
584    }
585
586    #[test]
587    fn test_invalid_signatures() {
588        let node_count: NodeCount = 1.into();
589        let index: NodeIndex = 0.into();
590        let keychain = test_multi_keychain(node_count, index);
591        let msg = test_message();
592        let signed_msg = Signed::sign_with_index(msg, &keychain);
593        let mut unchecked_msg = signed_msg.into_unchecked();
594        unchecked_msg.signature.index = 1.into();
595
596        assert!(
597            unchecked_msg.check(&keychain).is_err(),
598            "wrong index makes wrong signature"
599        );
600    }
601
602    #[test]
603    fn test_incomplete_multisignature() {
604        let msg = test_message();
605        let index: NodeIndex = 0.into();
606        let node_count: NodeCount = 2.into();
607        let keychain = test_multi_keychain(node_count, index);
608
609        let partial = PartiallyMultisigned::sign(msg, &keychain);
610        assert!(
611            !partial.is_complete(),
612            "One signature does not form a complete multisignature",
613        );
614    }
615
616    #[test]
617    fn test_multisignatures() {
618        let msg = test_message();
619        let node_count: NodeCount = 7.into();
620        let keychains: Vec<TestMultiKeychain> = (0..node_count.0)
621            .map(|i| test_multi_keychain(node_count, i.into()))
622            .collect();
623
624        let mut partial = PartiallyMultisigned::sign(msg.clone(), &keychains[0]);
625        for keychain in keychains.iter().skip(1).take(4) {
626            assert!(!partial.is_complete());
627            let signed = Signed::sign_with_index(msg.clone(), keychain);
628            partial = partial.add_signature(signed, keychain);
629        }
630        assert!(
631            partial.is_complete(),
632            "5 signatures should form a complete signature {:?}",
633            partial
634        );
635    }
636}
aleph_bft_crypto/signature.rs

aleph_bft_crypto/
signature.rs
