w3f_bls/
multi_pop_aggregator.rs

1//! ## Aggregation of BLS signatures using proofs-of-possession
2//!
3//! In this module, we provide the linear flavor of aggregate
4//! BLS signature in which the verifiers has previously checked
5//! proofs-of-possession for all public keys.  In other words,
6//! we simply add up the signatures because the previously checked
7//! proofs-of-possession for all signers prevent rogue key attacks.
8//! See the security arguments in The Power of Proofs-of-Possession:
9//! Securing Multiparty Signatures against Rogue-Key Attacks
10//! by Thomas Ristenpart and Scott Yilek at https://eprint.iacr.org/2007/264.pdf
11//!
12//! These proof-of-possession are simply self-signed certificates,
13//! so a BLS signature by each secret key on its own public key.
14//! Importantly, the message for this self-signed certificates
15//! must uniquely distinguish the public key for which the signature
16//! establishes a proof-of-possession.
17//! It follows that each proof-of-possession has a unique message,
18//! so distinct message aggregation is optimal for verifying them.
19//!
20//! In this vein, we note that aggregation under proofs-of-possession
21//! cannot improve performance when signers sign distinct messages,
22//! so proofs-of-possession help with aggregating votes in a concensus
23//! protocol, but should never be used for accounts on a block chain.
24//!
25//! We assume here that users provide their own data structure for
26//! proofs-of-poossession.  We provide more structure for users who
27//! one bit per vote in a concensus protocol:  
28//! You first verify the proofs-of-possession when building a data
29//! structure that holds the voters' keys.  You implement the
30//! `ProofsOfPossession` trait for this data strtcuture as well,
31//! so that the `BitPoPSignedMessage` type provides a signature
32//! data type with reasonable sanity checks.
33
34// Aside about proof-of-possession in the DLOG setting
35// https://twitter.com/btcVeg/status/1085490561082183681
36
37use core::borrow::Borrow; // BorrowMut
38use std::collections::HashMap;
39
40use ark_ff::Zero;
41
42use super::verifiers::verify_with_distinct_messages;
43use super::*;
44
45/// Batch or aggregate BLS signatures with attached messages and
46/// signers, for whom we previously checked proofs-of-possession.
47///
48/// In this type, we provide a high-risk low-level batching and
49/// aggregation mechanism that merely adds up signatures under the
50/// assumption that all required proofs-of-possession were previously
51/// checked.
52///
53/// We say a signing key has provided a proof-of-possession if the
54/// verifier remembers having checked some self-signed certificate
55/// by that key.  It's insecure to use this aggregation strategy
56/// without first cehcking proofs-of-possession.  In particular
57/// it is insecure to use this aggregation strategy when checking
58/// proofs-of-possession, and could not improve performance anyways.  
59/// Distinct message aggregation is always optimal for checking
60/// proofs-of-possession.  Please see the module level doumentation
61/// for additional discussion and notes on security.
62///
63/// We foresee this type primarily being used to batch several
64/// `BitPoPSignedMessage`s into one verification.  We do not track
65/// aggreggated public keys here, instead merging multiples signers
66/// public keys anytime they sign the same message, so this type
67/// essentially provides only fast batch verificartion.  
68/// In principle, our `add_*` methods suffice for building an actual
69/// aggregate signature type.  Yet, normally direct approaches like
70/// `BitPoPSignedMessage` work better for aggregation because
71/// the `ProofsOfPossession` trait tooling permits both enforce the
72/// proofs-of-possession and provide a compact serialization.
73/// We see no reason to support serialization for this type as present.
74//
75/// In principle, one might combine proof-of-possession with distinct
76/// message assumptions, or other aggregation strategies, when
77/// verifiers have only observed a subset of the proofs-of-possession,
78/// but this sounds complex or worse fragile.
79///
80// TODO: Implement gaussian elimination verification scheme.
81use single::PublicKey;
82/// ProofOfPossion trait which should be implemented by secret
83
84#[derive(Clone)]
85pub struct MultiMessageSignatureAggregatorAssumingPoP<E: EngineBLS> {
86    messages_n_publickeys: HashMap<Message, PublicKey<E>>,
87    signature: Signature<E>,
88}
89
90impl<E: EngineBLS> MultiMessageSignatureAggregatorAssumingPoP<E> {
91    pub fn new() -> MultiMessageSignatureAggregatorAssumingPoP<E> {
92        MultiMessageSignatureAggregatorAssumingPoP {
93            messages_n_publickeys: HashMap::new(),
94            signature: Signature(E::SignatureGroup::zero()),
95        }
96    }
97
98    /// Add only a `Signature<E>` to our internal signature.
99    ///
100    /// Useful for constructing an aggregate signature, but we
101    /// recommend instead using a custom types like `BitPoPSignedMessage`.
102    pub fn add_signature(&mut self, signature: &Signature<E>) {
103        self.signature.0 += &signature.0;
104    }
105
106    /// Add only a `Message` and `PublicKey<E>` to our internal data.
107    ///
108    /// Useful for constructing an aggregate signature, but we
109    /// recommend instead using a custom types like `BitPoPSignedMessage`.
110    pub fn add_message_n_publickey(&mut self, message: &Message, publickey: &PublicKey<E>) {
111        self.messages_n_publickeys
112            .entry(message.clone())
113            .and_modify(|pk0| pk0.0 += &publickey.0)
114            .or_insert(*publickey);
115    }
116
117    /// Aggregage BLS signatures assuming they have proofs-of-possession
118    pub fn aggregate<'a, S>(&mut self, signed: &'a S)
119    where
120        &'a S: Signed<E = E>,
121        <&'a S as Signed>::PKG: Borrow<PublicKey<E>>,
122    {
123        let signature = signed.signature();
124        for (message, pubickey) in signed.messages_and_publickeys() {
125            self.add_message_n_publickey(message.borrow(), pubickey.borrow());
126        }
127        self.add_signature(&signature);
128    }
129}
130
131impl<'a, E: EngineBLS> Signed for &'a MultiMessageSignatureAggregatorAssumingPoP<E> {
132    type E = E;
133
134    type M = &'a Message;
135    type PKG = &'a PublicKey<Self::E>;
136    type PKnM = ::std::collections::hash_map::Iter<'a, Message, PublicKey<E>>;
137
138    fn messages_and_publickeys(self) -> Self::PKnM {
139        self.messages_n_publickeys.iter()
140    }
141
142    fn signature(&self) -> Signature<E> {
143        self.signature
144    }
145
146    fn verify(self) -> bool {
147        // We have already aggregated distinct messages, so our distinct
148        // message verification code provides reasonable optimizations,
149        // except the public keys might not be normalized here.
150        // We foresee verification via gaussian elimination being faster,
151        // but requires affine keys or normalization.
152        verify_with_distinct_messages(self, true)
153        // TODO: verify_with_gaussian_elimination(self)
154    }
155}
156
157#[cfg(all(test, feature = "std"))]
158mod tests {
159
160    use crate::Keypair;
161    use crate::Message;
162    use crate::UsualBLS;
163    use rand::thread_rng;
164
165    use ark_bls12_381::Bls12_381;
166
167    use super::*;
168
169    #[test]
170    fn verify_aggregate_single_message_single_signer() {
171        let good = Message::new(b"ctx", b"test message");
172
173        let mut keypair =
174            Keypair::<UsualBLS<Bls12_381, ark_bls12_381::Config>>::generate(thread_rng());
175        let good_sig0 = keypair.sign(&good);
176        assert!(good_sig0.verify(&good, &keypair.public));
177    }
178
179    #[test]
180    fn verify_aggregate_single_message_multi_signers() {
181        let good = Message::new(b"ctx", b"test message");
182
183        let mut keypair0 =
184            Keypair::<UsualBLS<Bls12_381, ark_bls12_381::Config>>::generate(thread_rng());
185        let good_sig0 = keypair0.sign(&good);
186
187        let mut keypair1 =
188            Keypair::<UsualBLS<Bls12_381, ark_bls12_381::Config>>::generate(thread_rng());
189        let good_sig1 = keypair1.sign(&good);
190
191        let mut aggregated_sigs = MultiMessageSignatureAggregatorAssumingPoP::<
192            UsualBLS<Bls12_381, ark_bls12_381::Config>,
193        >::new();
194        aggregated_sigs.add_signature(&good_sig0);
195        aggregated_sigs.add_signature(&good_sig1);
196
197        aggregated_sigs.add_message_n_publickey(&good, &keypair0.public);
198        aggregated_sigs.add_message_n_publickey(&good, &keypair1.public);
199
200        assert!(
201            aggregated_sigs.verify() == true,
202            "good aggregated signature of a single message with multiple key does not verify"
203        );
204    }
205
206    #[test]
207    fn verify_aggregate_multi_messages_single_signer() {
208        let good0 = Message::new(b"ctx", b"Tab over Space");
209        let good1 = Message::new(b"ctx", b"Space over Tab");
210
211        let mut keypair =
212            Keypair::<UsualBLS<Bls12_381, ark_bls12_381::Config>>::generate(thread_rng());
213
214        let good_sig0 = keypair.sign(&good0);
215        let good_sig1 = keypair.sign(&good1);
216
217        let mut aggregated_sigs = MultiMessageSignatureAggregatorAssumingPoP::<
218            UsualBLS<Bls12_381, ark_bls12_381::Config>,
219        >::new();
220        aggregated_sigs.add_signature(&good_sig0);
221        aggregated_sigs.add_signature(&good_sig1);
222
223        aggregated_sigs.add_message_n_publickey(&good0, &keypair.public);
224        aggregated_sigs.add_message_n_publickey(&good1, &keypair.public);
225
226        assert!(
227            aggregated_sigs.verify() == true,
228            "good aggregated signature of multiple messages with a single key does not verify"
229        );
230    }
231
232    #[test]
233    fn verify_aggregate_multi_messages_multi_signers() {
234        let good0 = Message::new(b"ctx", b"in the beginning");
235        let good1 = Message::new(b"ctx", b"there was a flying spaghetti monster");
236
237        let mut keypair0 =
238            Keypair::<UsualBLS<Bls12_381, ark_bls12_381::Config>>::generate(thread_rng());
239        let good_sig0 = keypair0.sign(&good0);
240
241        let mut keypair1 =
242            Keypair::<UsualBLS<Bls12_381, ark_bls12_381::Config>>::generate(thread_rng());
243        let good_sig1 = keypair1.sign(&good1);
244
245        let mut aggregated_sigs = MultiMessageSignatureAggregatorAssumingPoP::<
246            UsualBLS<Bls12_381, ark_bls12_381::Config>,
247        >::new();
248        aggregated_sigs.add_signature(&good_sig0);
249        aggregated_sigs.add_signature(&good_sig1);
250
251        aggregated_sigs.add_message_n_publickey(&good0, &keypair0.public);
252        aggregated_sigs.add_message_n_publickey(&good1, &keypair1.public);
253
254        assert!(
255            aggregated_sigs.verify() == true,
256            "good aggregated signature of multiple messages with multiple keys does not verify"
257        );
258    }
259
260    #[test]
261    fn verify_aggregate_single_message_repetative_signers() {
262        let good = Message::new(b"ctx", b"test message");
263
264        let mut keypair =
265            Keypair::<UsualBLS<Bls12_381, ark_bls12_381::Config>>::generate(thread_rng());
266        let good_sig = keypair.sign(&good);
267
268        let mut aggregated_sigs = MultiMessageSignatureAggregatorAssumingPoP::<
269            UsualBLS<Bls12_381, ark_bls12_381::Config>,
270        >::new();
271        aggregated_sigs.add_signature(&good_sig);
272        aggregated_sigs.add_signature(&good_sig);
273
274        aggregated_sigs.add_message_n_publickey(&good, &keypair.public);
275        aggregated_sigs.add_message_n_publickey(&good, &keypair.public);
276
277        assert!(
278            aggregated_sigs.verify() == true,
279            "good aggregate of a repetitive signature does not verify"
280        );
281    }
282
283    #[test]
284    fn aggregate_of_signature_of_a_wrong_message_should_not_verify() {
285        let good0 = Message::new(b"ctx", b"Space over Tab");
286        let bad1 = Message::new(b"ctx", b"Tab over Space");
287
288        let mut keypair0 =
289            Keypair::<UsualBLS<Bls12_381, ark_bls12_381::Config>>::generate(thread_rng());
290        let good_sig0 = keypair0.sign(&good0);
291
292        let mut keypair1 =
293            Keypair::<UsualBLS<Bls12_381, ark_bls12_381::Config>>::generate(thread_rng());
294        let bad_sig1 = keypair1.sign(&bad1);
295
296        let mut aggregated_sigs = MultiMessageSignatureAggregatorAssumingPoP::<
297            UsualBLS<Bls12_381, ark_bls12_381::Config>,
298        >::new();
299        aggregated_sigs.add_signature(&good_sig0);
300        aggregated_sigs.add_signature(&bad_sig1);
301
302        aggregated_sigs.add_message_n_publickey(&good0, &keypair0.public);
303        aggregated_sigs.add_message_n_publickey(&good0, &keypair1.public);
304
305        assert!(
306            aggregated_sigs.verify() == false,
307            "aggregated signature of a wrong message should not verify"
308        );
309    }
310}
w3f_bls/multi_pop_aggregator.rs

w3f_bls/
multi_pop_aggregator.rs
