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::derive_hash_xor_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
337//////////////////////
338// Signature Traits //
339//////////////////////
340
341impl Eq for MultiBLSSignature {}
342
343impl TryFrom<&[u8]> for MultiBLSSignature {
344    type Error = CryptoMaterialError;
345
346    /// Deserialize a MultiBLSSignature. This method will also check for
347    /// malleable signatures and bitmap validity.
348    fn try_from(
349        bytes: &[u8],
350    ) -> std::result::Result<MultiBLSSignature, CryptoMaterialError> {
351        if bytes.len() < BITMAP_NUM_OF_BYTES {
352            return Err(CryptoMaterialError::DeserializationError);
353        }
354        let mut bitmap = [0u8; BITMAP_NUM_OF_BYTES];
355        for i in 0..BITMAP_NUM_OF_BYTES {
356            bitmap[i] = bytes[i];
357        }
358        let signature =
359            match RawSignature::from_bytes(&bytes[BITMAP_NUM_OF_BYTES..]) {
360                Ok(signature) => signature,
361                Err(_) => {
362                    return Err(CryptoMaterialError::DeserializationError)
363                }
364            };
365        Ok(Self { bitmap, signature })
366    }
367}
368
369#[allow(clippy::derive_hash_xor_eq)]
370impl std::hash::Hash for MultiBLSSignature {
371    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
372        let encoded_signature = self.to_bytes();
373        state.write(&encoded_signature);
374    }
375}
376
377impl fmt::Display for MultiBLSSignature {
378    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
379        write!(f, "{}", hex::encode(&self.to_bytes()[..]))
380    }
381}
382
383impl fmt::Debug for MultiBLSSignature {
384    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
385        write!(f, "MultiBLSSignature({})", self)
386    }
387}
388
389impl ValidCryptoMaterial for MultiBLSSignature {
390    fn to_bytes(&self) -> Vec<u8> { self.to_bytes() }
391}
392
393impl Signature for MultiBLSSignature {
394    type SigningKeyMaterial = MultiBLSPrivateKey;
395    type VerifyingKeyMaterial = MultiBLSPublicKey;
396
397    fn verify<T: CryptoHash + Serialize>(
398        &self, message: &T, public_key: &MultiBLSPublicKey,
399    ) -> Result<()> {
400        // Public keys should be validated to be safe against small subgroup
401        // attacks, etc.
402        precondition!(has_tag!(public_key, ValidatedPublicKeyTag));
403        let mut bytes = <T as CryptoHash>::Hasher::seed().to_vec();
404        bcs::serialize_into(&mut bytes, &message)
405            .map_err(|_| CryptoMaterialError::SerializationError)?;
406        Self::verify_arbitrary_msg(self, &bytes, public_key)
407    }
408
409    /// Checks that `self` is valid for an arbitrary &[u8] `message` using
410    /// `public_key`. Outside of this crate, this particular function should
411    /// only be used for native signature verification in Move.
412    fn verify_arbitrary_msg(
413        &self, message: &[u8], public_key: &MultiBLSPublicKey,
414    ) -> Result<()> {
415        precondition!(has_tag!(public_key, ValidatedPublicKeyTag));
416        match bitmap_last_set_bit(self.bitmap) {
417            Some(last_bit)
418                if last_bit as usize <= public_key.public_keys().len() =>
419            {
420                ()
421            }
422            _ => {
423                return Err(anyhow!(
424                    "{}",
425                    CryptoMaterialError::BitVecError(
426                        "Signature index is out of range".to_string()
427                    )
428                ))
429            }
430        };
431
432        let mut raw_public_keys: Vec<RawPublicKey> = vec![];
433        for i in 0..public_key.public_keys().len() {
434            if bitmap_get_bit(self.bitmap, i) {
435                raw_public_keys.push(public_key.public_keys()[i].clone().raw())
436            }
437        }
438        match bls_signatures::verify_same_message(
439            &self.signature,
440            message,
441            &raw_public_keys,
442        ) {
443            true => Ok(()),
444            false => Err(anyhow!("Invalid BLS signature!")),
445        }
446    }
447}
448
449impl From<BLSSignature> for MultiBLSSignature {
450    fn from(bls_signature: BLSSignature) -> Self {
451        let mut bitmap = [0u8; BITMAP_NUM_OF_BYTES];
452        bitmap[0] = 1;
453        MultiBLSSignature {
454            bitmap,
455            signature: bls_signature.raw(),
456        }
457    }
458}
459
460//////////////////////
461// Helper functions //
462//////////////////////
463
464// Helper function required to MultiBLS keys to_bytes to add the threshold.
465fn to_bytes<T: ValidCryptoMaterial>(keys: &[T]) -> Vec<u8> {
466    let bytes: Vec<u8> = keys
467        .iter()
468        .flat_map(ValidCryptoMaterial::to_bytes)
469        .collect();
470    bytes
471}
472
473fn bitmap_set_bit(input: &mut [u8; BITMAP_NUM_OF_BYTES], index: usize) {
474    let bucket = index / 8;
475    // It's always invoked with index < 32, thus there is no need to check
476    // range.
477    let bucket_pos = index - (bucket * 8);
478    input[bucket] |= 128 >> bucket_pos as u8;
479}
480
481// Helper method to get the input's bit at index.
482fn bitmap_get_bit(input: [u8; BITMAP_NUM_OF_BYTES], index: usize) -> bool {
483    let bucket = index / 8;
484    // It's always invoked with index < 32, thus there is no need to check
485    // range.
486    let bucket_pos = index - (bucket * 8);
487    (input[bucket] & (128 >> bucket_pos as u8)) != 0
488}
489
490// Find the last set bit.
491fn bitmap_last_set_bit(input: [u8; BITMAP_NUM_OF_BYTES]) -> Option<u8> {
492    input
493        .iter()
494        .rev()
495        .enumerate()
496        .find(|(_, byte)| byte != &&0u8)
497        .map(|(i, byte)| {
498            (8 * (BITMAP_NUM_OF_BYTES - i) - byte.trailing_zeros() as usize - 1)
499                as u8
500        })
501}
502
503#[test]
504fn bitmap_tests() {
505    let mut bitmap = [0u8; BITMAP_NUM_OF_BYTES];
506    bitmap[0] = 0b0100_0000u8;
507    bitmap[1] = 0b1111_1111u8;
508    bitmap[3] = 0b1000_0000u8;
509    assert!(!bitmap_get_bit(bitmap, 0));
510    assert!(bitmap_get_bit(bitmap, 1));
511    for i in 8..16 {
512        assert!(bitmap_get_bit(bitmap, i));
513    }
514    for i in 16..24 {
515        assert!(!bitmap_get_bit(bitmap, i));
516    }
517    assert!(bitmap_get_bit(bitmap, 24));
518    assert!(!bitmap_get_bit(bitmap, 31));
519    assert_eq!(bitmap_last_set_bit(bitmap), Some(24));
520
521    bitmap_set_bit(&mut bitmap, 30);
522    assert!(bitmap_get_bit(bitmap, 30));
523    assert_eq!(bitmap_last_set_bit(bitmap), Some(30));
524}
diem_crypto/multi_bls.rs

diem_crypto/
multi_bls.rs
