diem_crypto/
multi_bls.rs

1// Copyright 2021 Conflux Foundation. All rights reserved.
2// Conflux is free software and distributed under GNU General Public License.
3// See http://www.gnu.org/licenses/
4
5use crate::{
6    bls::{
7        BLSPrivateKey, BLSPublicKey, BLSSignature, BLS_PRIVATE_KEY_LENGTH,
8        BLS_PUBLIC_KEY_LENGTH,
9    },
10    hash::{CryptoHash, CryptoHasher},
11    traits::*,
12    CryptoMaterialError, PrivateKey, PublicKey, Signature, SigningKey, Uniform,
13    ValidCryptoMaterial, ValidCryptoMaterialStringExt, VerifyingKey,
14};
15use anyhow::{anyhow, Result};
16pub use bls_signatures::{
17    aggregate, hash as bls_hash, PrivateKey as RawPrivateKey,
18    PublicKey as RawPublicKey, Serialize as BLSSerialize,
19    Signature as RawSignature,
20};
21use core::convert::TryFrom;
22use diem_crypto_derive::{
23    DeserializeKey, SerializeKey, SilentDebug, SilentDisplay,
24};
25use mirai_annotations::*;
26use rand::Rng;
27use serde::Serialize;
28use std::fmt;
29
30const MAX_NUM_OF_KEYS: usize = 300;
31const BITMAP_NUM_OF_BYTES: usize = 40;
32
33/// Vector of private keys in the multi-key BLS structure.
34#[derive(
35    DeserializeKey, Eq, PartialEq, SilentDisplay, SilentDebug, SerializeKey,
36)]
37pub struct MultiBLSPrivateKey {
38    private_keys: Vec<BLSPrivateKey>,
39}
40
41#[cfg(feature = "assert-private-keys-not-cloneable")]
42static_assertions::assert_not_impl_any!(MultiBLSPrivateKey: Clone);
43
44/// Vector of public keys in the multi-key BLS structure.
45#[derive(Clone, DeserializeKey, Eq, PartialEq, SerializeKey)]
46pub struct MultiBLSPublicKey {
47    public_keys: Vec<BLSPublicKey>,
48}
49
50#[cfg(mirai)]
51use crate::tags::ValidatedPublicKeyTag;
52#[cfg(not(mirai))]
53struct ValidatedPublicKeyTag {}
54
55/// Multi BLS signature wrapper
56#[derive(DeserializeKey, Clone, SerializeKey, PartialEq)]
57pub struct MultiBLSSignature {
58    bitmap: [u8; BITMAP_NUM_OF_BYTES],
59    signature: RawSignature,
60}
61
62impl MultiBLSPrivateKey {
63    /// Construct a new MultiBLSPrivateKey.
64    pub fn new(
65        private_keys: Vec<BLSPrivateKey>,
66    ) -> std::result::Result<Self, CryptoMaterialError> {
67        Ok(MultiBLSPrivateKey { private_keys })
68    }
69
70    /// Serialize a MultiBLSPrivateKey.
71    pub fn to_bytes(&self) -> Vec<u8> { to_bytes(&self.private_keys) }
72}
73
74impl MultiBLSPublicKey {
75    /// Construct a new MultiBLSPublicKey.
76    pub fn new(public_keys: Vec<BLSPublicKey>) -> Self {
77        MultiBLSPublicKey { public_keys }
78    }
79
80    /// Getter public_keys
81    pub fn public_keys(&self) -> &Vec<BLSPublicKey> { &self.public_keys }
82
83    /// Serialize a MultiBLSPublicKey.
84    pub fn to_bytes(&self) -> Vec<u8> { to_bytes(&self.public_keys) }
85}
86
87///////////////////////
88// PrivateKey Traits //
89///////////////////////
90
91/// Convenient method to create a MultiBLSPrivateKey from a single
92/// BLSPrivateKey.
93impl From<&BLSPrivateKey> for MultiBLSPrivateKey {
94    fn from(bls_private_key: &BLSPrivateKey) -> Self {
95        MultiBLSPrivateKey {
96            private_keys: vec![BLSPrivateKey::try_from(
97                &bls_private_key.to_bytes()[..],
98            )
99            .unwrap()],
100        }
101    }
102}
103
104impl PrivateKey for MultiBLSPrivateKey {
105    type PublicKeyMaterial = MultiBLSPublicKey;
106}
107
108impl SigningKey for MultiBLSPrivateKey {
109    type SignatureMaterial = MultiBLSSignature;
110    type VerifyingKeyMaterial = MultiBLSPublicKey;
111
112    fn sign<T: CryptoHash + Serialize>(
113        &self, message: &T,
114    ) -> MultiBLSSignature {
115        let signatures: Vec<RawSignature> = self
116            .private_keys
117            .iter()
118            .enumerate()
119            .map(|(_, item)| item.sign(message).raw())
120            .collect();
121
122        MultiBLSSignature {
123            bitmap: [255; BITMAP_NUM_OF_BYTES],
124            signature: aggregate(&signatures).unwrap(),
125        }
126    }
127
128    #[cfg(any(test, feature = "fuzzing"))]
129    fn sign_arbitrary_message(&self, message: &[u8]) -> MultiBLSSignature {
130        let signatures: Vec<RawSignature> = self
131            .private_keys
132            .iter()
133            .enumerate()
134            .map(|(_, item)| item.sign_arbitrary_message(message).raw())
135            .collect();
136
137        MultiBLSSignature {
138            bitmap: [255; BITMAP_NUM_OF_BYTES],
139            signature: aggregate(&signatures).unwrap(),
140        }
141    }
142}
143
144// Generating a random K out-of N key for testing.
145impl Uniform for MultiBLSPrivateKey {
146    fn generate<R>(rng: &mut R) -> Self
147    where R: ::rand::RngCore + ::rand::CryptoRng {
148        let num_of_keys = rng.gen_range(1..=MAX_NUM_OF_KEYS);
149        let mut private_keys: Vec<BLSPrivateKey> =
150            Vec::with_capacity(num_of_keys);
151        for _ in 0..num_of_keys {
152            private_keys
153                .push(BLSPrivateKey::from(RawPrivateKey::generate(rng)));
154        }
155        MultiBLSPrivateKey { private_keys }
156    }
157}
158
159impl TryFrom<&[u8]> for MultiBLSPrivateKey {
160    type Error = CryptoMaterialError;
161
162    /// Deserialize an BLSPrivateKey. This method will also check for key
163    /// and threshold validity.
164    fn try_from(
165        bytes: &[u8],
166    ) -> std::result::Result<MultiBLSPrivateKey, CryptoMaterialError> {
167        if bytes.is_empty() {
168            return Err(CryptoMaterialError::WrongLengthError);
169        }
170
171        let private_keys: Result<Vec<BLSPrivateKey>, _> = bytes
172            .chunks_exact(BLS_PRIVATE_KEY_LENGTH)
173            .map(BLSPrivateKey::try_from)
174            .collect();
175
176        private_keys.map(|private_keys| MultiBLSPrivateKey { private_keys })
177    }
178}
179
180impl Length for MultiBLSPrivateKey {
181    fn length(&self) -> usize {
182        self.private_keys.len() * BLS_PRIVATE_KEY_LENGTH
183    }
184}
185
186impl ValidCryptoMaterial for MultiBLSPrivateKey {
187    fn to_bytes(&self) -> Vec<u8> { self.to_bytes() }
188}
189
190impl Genesis for MultiBLSPrivateKey {
191    fn genesis() -> Self {
192        let mut buf = [0u8; BLS_PRIVATE_KEY_LENGTH];
193        buf[BLS_PRIVATE_KEY_LENGTH - 1] = 1u8;
194        MultiBLSPrivateKey {
195            private_keys: vec![BLSPrivateKey::try_from(buf.as_ref()).unwrap()],
196        }
197    }
198}
199
200//////////////////////
201// PublicKey Traits //
202//////////////////////
203
204/// Convenient method to create a MultiBLSPublicKey from a single
205/// BLSPublicKey.
206impl From<BLSPublicKey> for MultiBLSPublicKey {
207    fn from(ed_public_key: BLSPublicKey) -> Self {
208        MultiBLSPublicKey {
209            public_keys: vec![ed_public_key],
210        }
211    }
212}
213
214/// Implementing From<&PrivateKey<...>> allows to derive a public key in a more
215/// elegant fashion.
216impl From<&MultiBLSPrivateKey> for MultiBLSPublicKey {
217    fn from(private_key: &MultiBLSPrivateKey) -> Self {
218        let public_keys = private_key
219            .private_keys
220            .iter()
221            .map(PrivateKey::public_key)
222            .collect();
223        MultiBLSPublicKey { public_keys }
224    }
225}
226
227/// We deduce PublicKey from this.
228impl PublicKey for MultiBLSPublicKey {
229    type PrivateKeyMaterial = MultiBLSPrivateKey;
230}
231
232#[allow(clippy::derived_hash_with_manual_eq)]
233impl std::hash::Hash for MultiBLSPublicKey {
234    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
235        let encoded_pubkey = self.to_bytes();
236        state.write(&encoded_pubkey);
237    }
238}
239
240impl TryFrom<&[u8]> for MultiBLSPublicKey {
241    type Error = CryptoMaterialError;
242
243    /// Deserialize a MultiBLSPublicKey. This method will also check for key
244    /// and threshold validity, and will only deserialize keys that are safe
245    /// against small subgroup attacks.
246    fn try_from(
247        bytes: &[u8],
248    ) -> std::result::Result<MultiBLSPublicKey, CryptoMaterialError> {
249        if bytes.is_empty() {
250            return Err(CryptoMaterialError::WrongLengthError);
251        }
252        let public_keys: Result<Vec<BLSPublicKey>, _> = bytes
253            .chunks_exact(BLS_PUBLIC_KEY_LENGTH)
254            .map(BLSPublicKey::try_from)
255            .collect();
256        public_keys.map(|public_keys| {
257            let public_key = MultiBLSPublicKey { public_keys };
258            add_tag!(&public_key, ValidatedPublicKeyTag);
259            public_key
260        })
261    }
262}
263
264/// We deduce VerifyingKey from pointing to the signature material
265/// we get the ability to do `pubkey.validate(msg, signature)`
266impl VerifyingKey for MultiBLSPublicKey {
267    type SignatureMaterial = MultiBLSSignature;
268    type SigningKeyMaterial = MultiBLSPrivateKey;
269}
270
271impl fmt::Display for MultiBLSPublicKey {
272    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
273        write!(f, "{}", hex::encode(&self.to_bytes()))
274    }
275}
276
277impl fmt::Debug for MultiBLSPublicKey {
278    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
279        write!(f, "MultiBLSPublicKey({})", self)
280    }
281}
282
283impl Length for MultiBLSPublicKey {
284    fn length(&self) -> usize { self.public_keys.len() * BLS_PUBLIC_KEY_LENGTH }
285}
286
287impl ValidCryptoMaterial for MultiBLSPublicKey {
288    fn to_bytes(&self) -> Vec<u8> { self.to_bytes() }
289}
290
291impl MultiBLSSignature {
292    /// This method will also sort signatures based on index.
293    pub fn new(
294        signatures: Vec<(BLSSignature, usize)>,
295    ) -> std::result::Result<Self, CryptoMaterialError> {
296        let num_of_sigs = signatures.len();
297        if num_of_sigs == 0 || num_of_sigs > MAX_NUM_OF_KEYS {
298            return Err(CryptoMaterialError::ValidationError);
299        }
300        let mut bitmap = [0u8; BITMAP_NUM_OF_BYTES];
301        let (sigs, indexes): (Vec<_>, Vec<_>) =
302            signatures.iter().cloned().unzip();
303        for i in indexes {
304            if i >= MAX_NUM_OF_KEYS {
305                return Err(CryptoMaterialError::ValidationError);
306            }
307            if bitmap_get_bit(bitmap, i) {
308                return Err(CryptoMaterialError::BitVecError(
309                    "Duplicate signature index".to_string(),
310                ));
311            } else {
312                bitmap_set_bit(&mut bitmap, i as usize);
313            }
314        }
315
316        let raw_signatures: Vec<RawSignature> =
317            sigs.into_iter().map(|sig| sig.raw()).collect();
318        let signature = match aggregate(&raw_signatures) {
319            Ok(signature) => Ok(signature),
320            Err(_) => Err(CryptoMaterialError::AggregateError),
321        }?;
322        Ok(Self { bitmap, signature })
323    }
324
325    /// Getter raw signature.
326    pub fn raw(&self) -> &RawSignature { &self.signature }
327
328    /// to bytes
329    pub fn to_bytes(&self) -> Vec<u8> {
330        let mut bytes: Vec<u8> = vec![];
331        bytes.extend(&self.bitmap[..]);
332        bytes.extend(&self.signature.as_bytes()[..]);
333        bytes
334    }
335
336    /// Get the actual signer set of the signature. `all_signers` is all
337    /// possible signers aligned with the internal bitmap.
338    pub fn get_signers<T: Clone>(&self, all_signers: &[T]) -> Result<Vec<T>> {
339        let mut signers = Vec::with_capacity(all_signers.len());
340        if let Some(last_bit_index) = bitmap_last_set_bit(self.bitmap) {
341            if last_bit_index as usize >= all_signers.len() {
342                return Err(anyhow!(
343                    "{}",
344                    CryptoMaterialError::BitVecError(
345                        "Signature index is out of range".to_string()
346                    )
347                ));
348            }
349        }
350        if all_signers.len() > self.bitmap.len() * 8 {
351            return Err(anyhow!(
352                "{}",
353                CryptoMaterialError::BitVecError(
354                    "signer index is out of range".to_string()
355                )
356            ));
357        }
358        for i in 0..all_signers.len() {
359            if bitmap_get_bit(self.bitmap, i) {
360                signers.push(all_signers[i].clone());
361            }
362        }
363        Ok(signers)
364    }
365}
366
367//////////////////////
368// Signature Traits //
369//////////////////////
370
371impl Eq for MultiBLSSignature {}
372
373impl TryFrom<&[u8]> for MultiBLSSignature {
374    type Error = CryptoMaterialError;
375
376    /// Deserialize a MultiBLSSignature. This method will also check for
377    /// malleable signatures and bitmap validity.
378    fn try_from(
379        bytes: &[u8],
380    ) -> std::result::Result<MultiBLSSignature, CryptoMaterialError> {
381        if bytes.len() < BITMAP_NUM_OF_BYTES {
382            return Err(CryptoMaterialError::DeserializationError);
383        }
384        let mut bitmap = [0u8; BITMAP_NUM_OF_BYTES];
385        for i in 0..BITMAP_NUM_OF_BYTES {
386            bitmap[i] = bytes[i];
387        }
388        let signature =
389            match RawSignature::from_bytes(&bytes[BITMAP_NUM_OF_BYTES..]) {
390                Ok(signature) => signature,
391                Err(_) => {
392                    return Err(CryptoMaterialError::DeserializationError)
393                }
394            };
395        Ok(Self { bitmap, signature })
396    }
397}
398
399#[allow(clippy::derived_hash_with_manual_eq)]
400impl std::hash::Hash for MultiBLSSignature {
401    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
402        let encoded_signature = self.to_bytes();
403        state.write(&encoded_signature);
404    }
405}
406
407impl fmt::Display for MultiBLSSignature {
408    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
409        write!(f, "{}", hex::encode(&self.to_bytes()[..]))
410    }
411}
412
413impl fmt::Debug for MultiBLSSignature {
414    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
415        write!(f, "MultiBLSSignature({})", self)
416    }
417}
418
419impl ValidCryptoMaterial for MultiBLSSignature {
420    fn to_bytes(&self) -> Vec<u8> { self.to_bytes() }
421}
422
423impl Signature for MultiBLSSignature {
424    type SigningKeyMaterial = MultiBLSPrivateKey;
425    type VerifyingKeyMaterial = MultiBLSPublicKey;
426
427    fn verify<T: CryptoHash + Serialize>(
428        &self, message: &T, public_key: &MultiBLSPublicKey,
429    ) -> Result<()> {
430        // Public keys should be validated to be safe against small subgroup
431        // attacks, etc.
432        precondition!(has_tag!(public_key, ValidatedPublicKeyTag));
433        let mut bytes = <T as CryptoHash>::Hasher::seed().to_vec();
434        bcs::serialize_into(&mut bytes, &message)
435            .map_err(|_| CryptoMaterialError::SerializationError)?;
436        Self::verify_arbitrary_msg(self, &bytes, public_key)
437    }
438
439    /// Checks that `self` is valid for an arbitrary &[u8] `message` using
440    /// `public_key`. Outside of this crate, this particular function should
441    /// only be used for native signature verification in Move.
442    fn verify_arbitrary_msg(
443        &self, message: &[u8], public_key: &MultiBLSPublicKey,
444    ) -> Result<()> {
445        precondition!(has_tag!(public_key, ValidatedPublicKeyTag));
446        match bitmap_last_set_bit(self.bitmap) {
447            Some(last_bit)
448                if last_bit as usize <= public_key.public_keys().len() =>
449            {
450                ()
451            }
452            _ => {
453                return Err(anyhow!(
454                    "{}",
455                    CryptoMaterialError::BitVecError(
456                        "Signature index is out of range".to_string()
457                    )
458                ))
459            }
460        };
461
462        let mut raw_public_keys: Vec<RawPublicKey> = vec![];
463        for i in 0..public_key.public_keys().len() {
464            if bitmap_get_bit(self.bitmap, i) {
465                raw_public_keys.push(public_key.public_keys()[i].clone().raw())
466            }
467        }
468        match bls_signatures::verify_same_message(
469            &self.signature,
470            message,
471            &raw_public_keys,
472        ) {
473            true => Ok(()),
474            false => Err(anyhow!("Invalid BLS signature!")),
475        }
476    }
477}
478
479impl From<BLSSignature> for MultiBLSSignature {
480    fn from(bls_signature: BLSSignature) -> Self {
481        let mut bitmap = [0u8; BITMAP_NUM_OF_BYTES];
482        bitmap[0] = 1;
483        MultiBLSSignature {
484            bitmap,
485            signature: bls_signature.raw(),
486        }
487    }
488}
489
490//////////////////////
491// Helper functions //
492//////////////////////
493
494// Helper function required to MultiBLS keys to_bytes to add the threshold.
495fn to_bytes<T: ValidCryptoMaterial>(keys: &[T]) -> Vec<u8> {
496    let bytes: Vec<u8> = keys
497        .iter()
498        .flat_map(ValidCryptoMaterial::to_bytes)
499        .collect();
500    bytes
501}
502
503fn bitmap_set_bit(input: &mut [u8; BITMAP_NUM_OF_BYTES], index: usize) {
504    let bucket = index / 8;
505    // It's always invoked with index < 32, thus there is no need to check
506    // range.
507    let bucket_pos = index - (bucket * 8);
508    input[bucket] |= 128 >> bucket_pos as u8;
509}
510
511// Helper method to get the input's bit at index.
512fn bitmap_get_bit(input: [u8; BITMAP_NUM_OF_BYTES], index: usize) -> bool {
513    let bucket = index / 8;
514    // It's always invoked with index < 32, thus there is no need to check
515    // range.
516    let bucket_pos = index - (bucket * 8);
517    (input[bucket] & (128 >> bucket_pos as u8)) != 0
518}
519
520// Find the last set bit.
521fn bitmap_last_set_bit(input: [u8; BITMAP_NUM_OF_BYTES]) -> Option<u8> {
522    input
523        .iter()
524        .rev()
525        .enumerate()
526        .find(|(_, byte)| byte != &&0u8)
527        .map(|(i, byte)| {
528            (8 * (BITMAP_NUM_OF_BYTES - i) - byte.trailing_zeros() as usize - 1)
529                as u8
530        })
531}
532
533#[test]
534fn bitmap_tests() {
535    let mut bitmap = [0u8; BITMAP_NUM_OF_BYTES];
536    bitmap[0] = 0b0100_0000u8;
537    bitmap[1] = 0b1111_1111u8;
538    bitmap[3] = 0b1000_0000u8;
539    assert!(!bitmap_get_bit(bitmap, 0));
540    assert!(bitmap_get_bit(bitmap, 1));
541    for i in 8..16 {
542        assert!(bitmap_get_bit(bitmap, i));
543    }
544    for i in 16..24 {
545        assert!(!bitmap_get_bit(bitmap, i));
546    }
547    assert!(bitmap_get_bit(bitmap, 24));
548    assert!(!bitmap_get_bit(bitmap, 31));
549    assert_eq!(bitmap_last_set_bit(bitmap), Some(24));
550
551    bitmap_set_bit(&mut bitmap, 30);
552    assert!(bitmap_get_bit(bitmap, 30));
553    assert_eq!(bitmap_last_set_bit(bitmap), Some(30));
554}
diem_crypto/multi_bls.rs

diem_crypto/
multi_bls.rs
