mithril_stm/
stm.rs

1//! Top-level API for Mithril Stake-based Threshold Multisignature scheme.
2//! See figure 6 of [the paper](https://eprint.iacr.org/2021/916) for most of the
3//! protocol.
4//!
5//! What follows is a simple example showing the usage of STM.
6//!
7//! ```rust
8//! # fn main() -> Result<(), Box<dyn std::error::Error>> {
9//! use blake2::{Blake2b, digest::consts::U32};
10//! use mithril_stm::key_reg::KeyReg; // Import key registration functionality
11//! use mithril_stm::stm::{StmClerk, StmInitializer, StmParameters, StmSig, StmSigner};
12//! use mithril_stm::AggregationError;
13//! use rayon::prelude::*; // We use par_iter to speed things up
14//!
15//! use rand_chacha::ChaCha20Rng;
16//! use rand_core::{RngCore, SeedableRng};
17//!
18//! let nparties = 4; // Use a small number of parties for this example
19//! type D = Blake2b<U32>; // Setting the hash function for convenience
20//!
21//! let mut rng = ChaCha20Rng::from_seed([0u8; 32]); // create and initialize rng
22//! let mut msg = [0u8; 16]; // setting an arbitrary message
23//! rng.fill_bytes(&mut msg);
24//!
25//! // In the following, we will have 4 parties try to sign `msg`, then aggregate and
26//! // verify those signatures.
27//!
28//! //////////////////////////
29//! // initialization phase //
30//! //////////////////////////
31//!
32//! // Set low parameters for testing
33//! // XXX: not for production
34//! let params = StmParameters {
35//!     m: 100, // Security parameter XXX: not for production
36//!     k: 2, // Quorum parameter XXX: not for production
37//!     phi_f: 0.2, // Lottery parameter XXX: not for production
38//! };
39//!
40//! // Generate some arbitrary stake for each party
41//! // Stake is an integer.
42//! // Total stake of all parties is total stake in the system.
43//! let stakes = (0..nparties)
44//!     .into_iter()
45//!     .map(|_| 1 + (rng.next_u64() % 9999))
46//!     .collect::<Vec<_>>();
47//!
48//! // Create a new key registry from the parties and their stake
49//! let mut key_reg = KeyReg::init();
50//!
51//! // For each party, crate a StmInitializer.
52//! // This struct can create keys for the party.
53//! let mut ps: Vec<StmInitializer> = Vec::with_capacity(nparties);
54//! for stake in stakes {
55//!     // Create keys for this party
56//!     let p = StmInitializer::setup(params, stake, &mut rng);
57//!     // Register keys with the KeyReg service
58//!     key_reg
59//!         .register(p.stake, p.verification_key())
60//!         .unwrap();
61//!     ps.push(p);
62//! }
63//!
64//! // Close the key registration.
65//! let closed_reg = key_reg.close();
66//!
67//! // Finalize the StmInitializer and turn it into a StmSigner, which can execute the
68//! // rest of the protocol.
69//! let ps = ps
70//!     .into_par_iter()
71//!     .map(|p| p.new_signer(closed_reg.clone()).unwrap())
72//!     .collect::<Vec<StmSigner<D>>>();
73//!
74//! /////////////////////
75//! // operation phase //
76//! /////////////////////
77//!
78//! // Next, each party tries to sign the message for each index available.
79//! // We collect the successful signatures into a vec.
80//! let sigs = ps
81//!     .par_iter()
82//!     .filter_map(|p| {
83//!         return p.sign(&msg);
84//!     })
85//!     .collect::<Vec<StmSig>>();
86//!
87//! // StmClerk can aggregate and verify signatures.
88//! let clerk = StmClerk::from_signer(&ps[0]);
89//!
90//! // Aggregate and verify the signatures
91//! let msig = clerk.aggregate(&sigs, &msg);
92//! match msig {
93//!     Ok(aggr) => {
94//!         println!("Aggregate ok");
95//!         assert!(aggr
96//!             .verify(&msg, &clerk.compute_avk(), &params)
97//!             .is_ok());
98//!     }
99//!     Err(AggregationError::NotEnoughSignatures(n, k)) => {
100//!         println!("Not enough signatures");
101//!         assert!(n < params.k && k == params.k)
102//!     }
103//!     Err(_) => unreachable!(),
104//! }
105//! # Ok(())
106//! # }
107//! ```
108
109use crate::eligibility_check::ev_lt_phi;
110use crate::error::{
111    AggregationError, CoreVerifierError, RegisterError, StmAggregateSignatureError,
112    StmSignatureError,
113};
114use crate::key_reg::{ClosedKeyReg, RegParty};
115use crate::merkle_tree::{BatchPath, MTLeaf, MerkleTreeCommitmentBatchCompat};
116use crate::multi_sig::{Signature, SigningKey, VerificationKey, VerificationKeyPoP};
117use blake2::digest::{Digest, FixedOutput};
118use rand_core::{CryptoRng, RngCore};
119use serde::ser::SerializeTuple;
120use serde::{Deserialize, Serialize, Serializer};
121use std::cmp::Ordering;
122use std::collections::{BTreeMap, HashMap, HashSet};
123use std::convert::{From, TryFrom, TryInto};
124use std::hash::{Hash, Hasher};
125
126/// The quantity of stake held by a party, represented as a `u64`.
127pub type Stake = u64;
128
129/// Quorum index for signatures.
130/// An aggregate signature (`StmMultiSig`) must have at least `k` unique indices.
131pub type Index = u64;
132
133/// Wrapper of the MultiSignature Verification key with proof of possession
134pub type StmVerificationKeyPoP = VerificationKeyPoP;
135
136/// Wrapper of the MultiSignature Verification key
137pub type StmVerificationKey = VerificationKey;
138
139/// Used to set protocol parameters.
140// todo: this is the criteria to consider parameters valid:
141// Let A = max assumed adversarial stake
142// Let a = A / max_stake
143// Let p = φ(a)  // f needs tuning, something close to 0.2 is reasonable
144// Then, we're secure if SUM[from i=k to i=m] Binomial(i successes, m experiments, p chance of success) <= 2^-100 or thereabouts.
145// The latter turns to 1 - BinomialCDF(k-1,m,p)
146#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
147pub struct StmParameters {
148    /// Security parameter, upper bound on indices.
149    pub m: u64,
150    /// Quorum parameter.
151    pub k: u64,
152    /// `f` in phi(w) = 1 - (1 - f)^w, where w is the stake of a participant..
153    pub phi_f: f64,
154}
155
156impl StmParameters {
157    /// Convert to bytes
158    /// # Layout
159    /// * Security parameter, `m` (as u64)
160    /// * Quorum parameter, `k` (as u64)
161    /// * Phi f, as (f64)
162    pub fn to_bytes(&self) -> [u8; 24] {
163        let mut out = [0; 24];
164        out[..8].copy_from_slice(&self.m.to_be_bytes());
165        out[8..16].copy_from_slice(&self.k.to_be_bytes());
166        out[16..].copy_from_slice(&self.phi_f.to_be_bytes());
167        out
168    }
169
170    /// Extract the `StmParameters` from a byte slice.
171    /// # Error
172    /// The function fails if the given string of bytes is not of required size.
173    pub fn from_bytes(bytes: &[u8]) -> Result<Self, RegisterError> {
174        if bytes.len() != 24 {
175            return Err(RegisterError::SerializationError);
176        }
177
178        let mut u64_bytes = [0u8; 8];
179        u64_bytes.copy_from_slice(&bytes[..8]);
180        let m = u64::from_be_bytes(u64_bytes);
181        u64_bytes.copy_from_slice(&bytes[8..16]);
182        let k = u64::from_be_bytes(u64_bytes);
183        u64_bytes.copy_from_slice(&bytes[16..]);
184        let phi_f = f64::from_be_bytes(u64_bytes);
185
186        Ok(Self { m, k, phi_f })
187    }
188}
189
190/// Initializer for `StmSigner`.
191/// This is the data that is used during the key registration procedure.
192/// Once the latter is finished, this instance is consumed into an `StmSigner`.
193#[derive(Debug, Clone, Serialize, Deserialize)]
194pub struct StmInitializer {
195    /// This participant's stake.
196    pub stake: Stake,
197    /// Current protocol instantiation parameters.
198    pub params: StmParameters,
199    /// Secret key.
200    pub(crate) sk: SigningKey,
201    /// Verification (public) key + proof of possession.
202    pub(crate) pk: StmVerificationKeyPoP,
203}
204
205impl StmInitializer {
206    /// Builds an `StmInitializer` that is ready to register with the key registration service.
207    /// This function generates the signing and verification key with a PoP, and initialises the structure.
208    pub fn setup<R: RngCore + CryptoRng>(params: StmParameters, stake: Stake, rng: &mut R) -> Self {
209        let sk = SigningKey::gen(rng);
210        let pk = StmVerificationKeyPoP::from(&sk);
211        Self {
212            stake,
213            params,
214            sk,
215            pk,
216        }
217    }
218
219    /// Extract the verification key.
220    pub fn verification_key(&self) -> StmVerificationKeyPoP {
221        self.pk
222    }
223
224    /// Build the `avk` for the given list of parties.
225    ///
226    /// Note that if this StmInitializer was modified *between* the last call to `register`,
227    /// then the resulting `StmSigner` may not be able to produce valid signatures.
228    ///
229    /// Returns an `StmSigner` specialized to
230    /// * this `StmSigner`'s ID and current stake
231    /// * this `StmSigner`'s parameter valuation
232    /// * the `avk` as built from the current registered parties (according to the registration service)
233    /// * the current total stake (according to the registration service)
234    /// # Error
235    /// This function fails if the initializer is not registered.
236    pub fn new_signer<D: Digest + Clone>(
237        self,
238        closed_reg: ClosedKeyReg<D>,
239    ) -> Result<StmSigner<D>, RegisterError> {
240        let mut my_index = None;
241        for (i, rp) in closed_reg.reg_parties.iter().enumerate() {
242            if rp.0 == self.pk.vk {
243                my_index = Some(i as u64);
244                break;
245            }
246        }
247        if my_index.is_none() {
248            return Err(RegisterError::UnregisteredInitializer);
249        }
250
251        Ok(StmSigner {
252            signer_index: my_index.unwrap(),
253            stake: self.stake,
254            params: self.params,
255            sk: self.sk,
256            vk: self.pk.vk,
257            closed_reg: Some(closed_reg),
258        })
259    }
260
261    /// Creates a new core signer that does not include closed registration.
262    /// Takes `eligible_parties` as a parameter and determines the signer's index in the parties.
263    /// `eligible_parties` is verified and trusted which is only run by a full-node
264    /// that has already verified the parties.
265    pub fn new_core_signer<D: Digest + Clone>(
266        self,
267        eligible_parties: &[RegParty],
268    ) -> Option<StmSigner<D>> {
269        let mut parties = eligible_parties.to_vec();
270        parties.sort_unstable();
271        let mut my_index = None;
272        for (i, rp) in parties.iter().enumerate() {
273            if rp.0 == self.pk.vk {
274                my_index = Some(i as u64);
275                break;
276            }
277        }
278        if let Some(index) = my_index {
279            Some(StmSigner {
280                signer_index: index,
281                stake: self.stake,
282                params: self.params,
283                sk: self.sk,
284                vk: self.pk.vk,
285                closed_reg: None,
286            })
287        } else {
288            None
289        }
290    }
291
292    /// Convert to bytes
293    /// # Layout
294    /// * Stake (u64)
295    /// * Params
296    /// * Secret Key
297    /// * Public key (including PoP)
298    pub fn to_bytes(&self) -> [u8; 256] {
299        let mut out = [0u8; 256];
300        out[..8].copy_from_slice(&self.stake.to_be_bytes());
301        out[8..32].copy_from_slice(&self.params.to_bytes());
302        out[32..64].copy_from_slice(&self.sk.to_bytes());
303        out[64..].copy_from_slice(&self.pk.to_bytes());
304        out
305    }
306
307    /// Convert a slice of bytes to an `StmInitializer`
308    /// # Error
309    /// The function fails if the given string of bytes is not of required size.
310    pub fn from_bytes(bytes: &[u8]) -> Result<StmInitializer, RegisterError> {
311        let mut u64_bytes = [0u8; 8];
312        u64_bytes.copy_from_slice(&bytes[..8]);
313        let stake = u64::from_be_bytes(u64_bytes);
314        let params = StmParameters::from_bytes(&bytes[8..32])?;
315        let sk = SigningKey::from_bytes(&bytes[32..])?;
316        let pk = StmVerificationKeyPoP::from_bytes(&bytes[64..])?;
317
318        Ok(Self {
319            stake,
320            params,
321            sk,
322            pk,
323        })
324    }
325}
326
327/// Participant in the protocol can sign messages.
328/// * If the signer has `closed_reg`, then it can generate Stm certificate.
329///     * This kind of signer can only be generated out of an `StmInitializer` and a `ClosedKeyReg`.
330///     * This ensures that a `MerkleTree` root is not computed before all participants have registered.
331/// * If the signer does not have `closed_reg`, then it is a core signer.
332///     * This kind of signer cannot participate certificate generation.
333///     * Signature generated can be verified by a full node verifier (core verifier).
334#[derive(Debug, Clone)]
335pub struct StmSigner<D: Digest> {
336    signer_index: u64,
337    stake: Stake,
338    params: StmParameters,
339    sk: SigningKey,
340    vk: StmVerificationKey,
341    closed_reg: Option<ClosedKeyReg<D>>,
342}
343
344impl<D: Clone + Digest + FixedOutput> StmSigner<D> {
345    /// This function produces a signature following the description of Section 2.4.
346    /// Once the signature is produced, this function checks whether any index in `[0,..,self.params.m]`
347    /// wins the lottery by evaluating the dense mapping.
348    /// It records all the winning indexes in `Self.indexes`.
349    /// If it wins at least one lottery, it stores the signer's merkle tree index. The proof of membership
350    /// will be handled by the aggregator.
351    pub fn sign(&self, msg: &[u8]) -> Option<StmSig> {
352        let closed_reg = self.closed_reg.as_ref().expect("Closed registration not found! Cannot produce StmSignatures. Use core_sign to produce core signatures (not valid for an StmCertificate).");
353        let msgp = closed_reg
354            .merkle_tree
355            .to_commitment_batch_compat()
356            .concat_with_msg(msg);
357        let signature = self.core_sign(&msgp, closed_reg.total_stake)?;
358
359        Some(StmSig {
360            sigma: signature.sigma,
361            signer_index: self.signer_index,
362            indexes: signature.indexes,
363        })
364    }
365
366    /// Extract the verification key.
367    pub fn verification_key(&self) -> StmVerificationKey {
368        self.vk
369    }
370
371    /// Extract stake from the signer.
372    pub fn get_stake(&self) -> Stake {
373        self.stake
374    }
375
376    /// A core signature generated without closed registration.
377    /// The core signature can be verified by core verifier.
378    /// Once the signature is produced, this function checks whether any index in `[0,..,self.params.m]`
379    /// wins the lottery by evaluating the dense mapping.
380    /// It records all the winning indexes in `Self.indexes`.
381    pub fn core_sign(&self, msg: &[u8], total_stake: Stake) -> Option<StmSig> {
382        let sigma = self.sk.sign(msg);
383
384        let indexes = self.check_lottery(msg, &sigma, total_stake);
385        if !indexes.is_empty() {
386            Some(StmSig {
387                sigma,
388                indexes,
389                signer_index: self.signer_index,
390            })
391        } else {
392            None
393        }
394    }
395
396    /// Collects and returns the winning indices.
397    pub fn check_lottery(&self, msg: &[u8], sigma: &Signature, total_stake: Stake) -> Vec<u64> {
398        let mut indexes = Vec::new();
399        for index in 0..self.params.m {
400            if ev_lt_phi(
401                self.params.phi_f,
402                sigma.eval(msg, index),
403                self.stake,
404                total_stake,
405            ) {
406                indexes.push(index);
407            }
408        }
409        indexes
410    }
411}
412
413/// Stm aggregate key (batch compatible), which contains the merkle tree commitment and the total stake of the system.
414/// Batch Compat Merkle tree commitment includes the number of leaves in the tree in order to obtain batch path.
415#[derive(Debug, Clone, Serialize, Deserialize)]
416#[serde(bound(
417    serialize = "BatchPath<D>: Serialize",
418    deserialize = "BatchPath<D>: Deserialize<'de>"
419))]
420pub struct StmAggrVerificationKey<D: Clone + Digest + FixedOutput> {
421    mt_commitment: MerkleTreeCommitmentBatchCompat<D>,
422    total_stake: Stake,
423}
424
425impl<D: Digest + Clone + FixedOutput> PartialEq for StmAggrVerificationKey<D> {
426    fn eq(&self, other: &Self) -> bool {
427        self.mt_commitment == other.mt_commitment && self.total_stake == other.total_stake
428    }
429}
430
431impl<D: Digest + Clone + FixedOutput> Eq for StmAggrVerificationKey<D> {}
432
433impl<D: Clone + Digest + FixedOutput> From<&ClosedKeyReg<D>> for StmAggrVerificationKey<D> {
434    fn from(reg: &ClosedKeyReg<D>) -> Self {
435        Self {
436            mt_commitment: reg.merkle_tree.to_commitment_batch_compat(),
437            total_stake: reg.total_stake,
438        }
439    }
440}
441
442/// Signature created by a single party who has won the lottery.
443#[derive(Debug, Clone, Serialize, Deserialize)]
444pub struct StmSig {
445    /// The signature from the underlying MSP scheme.
446    pub sigma: Signature,
447    /// The index(es) for which the signature is valid
448    pub indexes: Vec<Index>,
449    /// Merkle tree index of the signer.
450    pub signer_index: Index,
451}
452
453impl StmSig {
454    /// Verify an stm signature by checking that the lottery was won, the merkle path is correct,
455    /// the indexes are in the desired range and the underlying multi signature validates.
456    pub fn verify<D: Clone + Digest + FixedOutput>(
457        &self,
458        params: &StmParameters,
459        pk: &StmVerificationKey,
460        stake: &Stake,
461        avk: &StmAggrVerificationKey<D>,
462        msg: &[u8],
463    ) -> Result<(), StmSignatureError> {
464        let msgp = avk.mt_commitment.concat_with_msg(msg);
465        self.verify_core(params, pk, stake, &msgp, &avk.total_stake)?;
466        Ok(())
467    }
468
469    /// Verify that all indices of a signature are valid.
470    pub(crate) fn check_indices(
471        &self,
472        params: &StmParameters,
473        stake: &Stake,
474        msg: &[u8],
475        total_stake: &Stake,
476    ) -> Result<(), StmSignatureError> {
477        for &index in &self.indexes {
478            if index > params.m {
479                return Err(StmSignatureError::IndexBoundFailed(index, params.m));
480            }
481
482            let ev = self.sigma.eval(msg, index);
483
484            if !ev_lt_phi(params.phi_f, ev, *stake, *total_stake) {
485                return Err(StmSignatureError::LotteryLost);
486            }
487        }
488
489        Ok(())
490    }
491
492    /// Convert an `StmSig` into bytes
493    ///
494    /// # Layout
495    /// * Stake
496    /// * Number of valid indexes (as u64)
497    /// * Indexes of the signature
498    /// * Public Key
499    /// * Signature
500    /// * Merkle index of the signer.
501    pub fn to_bytes(&self) -> Vec<u8> {
502        let mut output = Vec::new();
503        output.extend_from_slice(&(self.indexes.len() as u64).to_be_bytes());
504
505        for index in &self.indexes {
506            output.extend_from_slice(&index.to_be_bytes());
507        }
508
509        output.extend_from_slice(&self.sigma.to_bytes());
510
511        output.extend_from_slice(&self.signer_index.to_be_bytes());
512        output
513    }
514
515    /// Extract a batch compatible `StmSig` from a byte slice.
516    pub fn from_bytes<D: Clone + Digest + FixedOutput>(
517        bytes: &[u8],
518    ) -> Result<StmSig, StmSignatureError> {
519        let mut u64_bytes = [0u8; 8];
520
521        u64_bytes.copy_from_slice(&bytes[0..8]);
522        let nr_indexes = u64::from_be_bytes(u64_bytes) as usize;
523
524        let mut indexes = Vec::new();
525        for i in 0..nr_indexes {
526            u64_bytes.copy_from_slice(&bytes[8 + i * 8..16 + i * 8]);
527            indexes.push(u64::from_be_bytes(u64_bytes));
528        }
529
530        let offset = 8 + nr_indexes * 8;
531        let sigma = Signature::from_bytes(&bytes[offset..offset + 48])?;
532
533        u64_bytes.copy_from_slice(&bytes[offset + 48..offset + 56]);
534        let signer_index = u64::from_be_bytes(u64_bytes);
535
536        Ok(StmSig {
537            sigma,
538            indexes,
539            signer_index,
540        })
541    }
542
543    /// Compare two `StmSig` by their signers' merkle tree indexes.
544    pub fn cmp_stm_sig(&self, other: &Self) -> Ordering {
545        self.signer_index.cmp(&other.signer_index)
546    }
547
548    /// Verify a core signature by checking that the lottery was won,
549    /// the indexes are in the desired range and the underlying multi signature validates.
550    pub fn verify_core(
551        &self,
552        params: &StmParameters,
553        pk: &StmVerificationKey,
554        stake: &Stake,
555        msg: &[u8],
556        total_stake: &Stake,
557    ) -> Result<(), StmSignatureError> {
558        self.sigma.verify(msg, pk)?;
559        self.check_indices(params, stake, msg, total_stake)?;
560
561        Ok(())
562    }
563}
564
565impl Hash for StmSig {
566    fn hash<H: Hasher>(&self, state: &mut H) {
567        Hash::hash_slice(&self.sigma.to_bytes(), state)
568    }
569}
570
571impl PartialEq for StmSig {
572    fn eq(&self, other: &Self) -> bool {
573        self.sigma == other.sigma
574    }
575}
576
577impl Eq for StmSig {}
578
579impl PartialOrd for StmSig {
580    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
581        Some(std::cmp::Ord::cmp(self, other))
582    }
583}
584
585impl Ord for StmSig {
586    fn cmp(&self, other: &Self) -> Ordering {
587        self.cmp_stm_sig(other)
588    }
589}
590
591/// Signature with its registered party.
592#[derive(Debug, Clone, Hash, Deserialize, Eq, PartialEq, Ord, PartialOrd)]
593pub struct StmSigRegParty {
594    /// Stm signature
595    pub sig: StmSig,
596    /// Registered party
597    pub reg_party: RegParty,
598}
599
600impl StmSigRegParty {
601    /// Convert StmSigRegParty to bytes
602    /// # Layout
603    /// * RegParty
604    /// * Signature
605    pub fn to_bytes(&self) -> Vec<u8> {
606        let mut out = Vec::new();
607        out.extend_from_slice(&self.reg_party.to_bytes());
608        out.extend_from_slice(&self.sig.to_bytes());
609
610        out
611    }
612    ///Extract a `StmSigRegParty` from a byte slice.
613    pub fn from_bytes<D: Digest + Clone + FixedOutput>(
614        bytes: &[u8],
615    ) -> Result<StmSigRegParty, StmSignatureError> {
616        let reg_party = RegParty::from_bytes(&bytes[0..104])?;
617        let sig = StmSig::from_bytes::<D>(&bytes[104..])?;
618
619        Ok(StmSigRegParty { sig, reg_party })
620    }
621}
622
623impl Serialize for StmSigRegParty {
624    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
625    where
626        S: Serializer,
627    {
628        let mut tuple = serializer.serialize_tuple(2)?;
629        tuple.serialize_element(&self.sig)?;
630        tuple.serialize_element(&self.reg_party)?;
631        tuple.end()
632    }
633}
634
635/// `StmClerk` can verify and aggregate `StmSig`s and verify `StmMultiSig`s.
636/// Clerks can only be generated with the registration closed.
637/// This avoids that a Merkle Tree is computed before all parties have registered.
638#[derive(Debug, Clone)]
639pub struct StmClerk<D: Clone + Digest> {
640    pub(crate) closed_reg: ClosedKeyReg<D>,
641    pub(crate) params: StmParameters,
642}
643
644impl<D: Digest + Clone + FixedOutput> StmClerk<D> {
645    /// Create a new `Clerk` from a closed registration instance.
646    pub fn from_registration(params: &StmParameters, closed_reg: &ClosedKeyReg<D>) -> Self {
647        Self {
648            params: *params,
649            closed_reg: closed_reg.clone(),
650        }
651    }
652
653    /// Create a Clerk from a signer.
654    pub fn from_signer(signer: &StmSigner<D>) -> Self {
655        let closed_reg = signer
656            .closed_reg
657            .clone()
658            .expect("Core signer does not include closed registration. StmClerk, and so, the Stm certificate cannot be built without closed registration!");
659
660        Self {
661            params: signer.params,
662            closed_reg,
663        }
664    }
665
666    /// Aggregate a set of signatures for their corresponding indices.
667    ///
668    /// This function first deduplicates the repeated signatures, and if there are enough signatures, it collects the merkle tree indexes of unique signatures.
669    /// The list of merkle tree indexes is used to create a batch proof, to prove that all signatures are from eligible signers.
670    ///
671    /// It returns an instance of `StmAggrSig`.
672    pub fn aggregate(
673        &self,
674        sigs: &[StmSig],
675        msg: &[u8],
676    ) -> Result<StmAggrSig<D>, AggregationError> {
677        let sig_reg_list = sigs
678            .iter()
679            .map(|sig| StmSigRegParty {
680                sig: sig.clone(),
681                reg_party: self.closed_reg.reg_parties[sig.signer_index as usize],
682            })
683            .collect::<Vec<StmSigRegParty>>();
684
685        let avk = StmAggrVerificationKey::from(&self.closed_reg);
686        let msgp = avk.mt_commitment.concat_with_msg(msg);
687        let mut unique_sigs = CoreVerifier::dedup_sigs_for_indices(
688            &self.closed_reg.total_stake,
689            &self.params,
690            &msgp,
691            &sig_reg_list,
692        )?;
693
694        unique_sigs.sort_unstable();
695
696        let mt_index_list = unique_sigs
697            .iter()
698            .map(|sig_reg| sig_reg.sig.signer_index as usize)
699            .collect::<Vec<usize>>();
700
701        let batch_proof = self.closed_reg.merkle_tree.get_batched_path(mt_index_list);
702
703        Ok(StmAggrSig {
704            signatures: unique_sigs,
705            batch_proof,
706        })
707    }
708
709    /// Compute the `StmAggrVerificationKey` related to the used registration.
710    pub fn compute_avk(&self) -> StmAggrVerificationKey<D> {
711        StmAggrVerificationKey::from(&self.closed_reg)
712    }
713
714    /// Get the (VK, stake) of a party given its index.
715    pub fn get_reg_party(&self, party_index: &Index) -> Option<(StmVerificationKey, Stake)> {
716        self.closed_reg
717            .reg_parties
718            .get(*party_index as usize)
719            .map(|&r| r.into())
720    }
721}
722
723/// `StmMultiSig` uses the "concatenation" proving system (as described in Section 4.3 of the original paper.)
724/// This means that the aggregated signature contains a vector with all individual signatures.
725/// BatchPath is also a part of the aggregate signature which covers path for all signatures.
726#[derive(Debug, Clone, Serialize, Deserialize)]
727#[serde(bound(
728    serialize = "BatchPath<D>: Serialize",
729    deserialize = "BatchPath<D>: Deserialize<'de>"
730))]
731pub struct StmAggrSig<D: Clone + Digest + FixedOutput> {
732    pub(crate) signatures: Vec<StmSigRegParty>,
733    /// The list of unique merkle tree nodes that covers path for all signatures.
734    pub batch_proof: BatchPath<D>,
735}
736
737impl<D: Clone + Digest + FixedOutput + Send + Sync> StmAggrSig<D> {
738    /// Verify all checks from signatures, except for the signature verification itself.
739    ///
740    /// Indices and quorum are checked by `CoreVerifier::preliminary_verify` with `msgp`.
741    /// It collects leaves from signatures and checks the batch proof.
742    /// After batch proof is checked, it collects and returns the signatures and
743    /// verification keys to be used by aggregate verification.
744    fn preliminary_verify(
745        &self,
746        msg: &[u8],
747        avk: &StmAggrVerificationKey<D>,
748        parameters: &StmParameters,
749    ) -> Result<(Vec<Signature>, Vec<VerificationKey>), StmAggregateSignatureError<D>> {
750        let msgp = avk.mt_commitment.concat_with_msg(msg);
751        CoreVerifier::preliminary_verify(&avk.total_stake, &self.signatures, parameters, &msgp)?;
752
753        let leaves = self
754            .signatures
755            .iter()
756            .map(|r| r.reg_party)
757            .collect::<Vec<RegParty>>();
758
759        avk.mt_commitment.check(&leaves, &self.batch_proof)?;
760
761        Ok(CoreVerifier::collect_sigs_vks(&self.signatures))
762    }
763
764    /// Verify aggregate signature, by checking that
765    /// * each signature contains only valid indices,
766    /// * the lottery is indeed won by each one of them,
767    /// * the merkle tree path is valid,
768    /// * the aggregate signature validates with respect to the aggregate verification key
769    ///   (aggregation is computed using functions `MSP.BKey` and `MSP.BSig` as described in Section 2.4 of the paper).
770    pub fn verify(
771        &self,
772        msg: &[u8],
773        avk: &StmAggrVerificationKey<D>,
774        parameters: &StmParameters,
775    ) -> Result<(), StmAggregateSignatureError<D>> {
776        let msgp = avk.mt_commitment.concat_with_msg(msg);
777        let (sigs, vks) = self.preliminary_verify(msg, avk, parameters)?;
778
779        Signature::verify_aggregate(msgp.as_slice(), &vks, &sigs)?;
780        Ok(())
781    }
782
783    /// Batch verify a set of signatures, with different messages and avks.
784    #[cfg(feature = "batch-verify-aggregates")]
785    pub fn batch_verify(
786        stm_signatures: &[Self],
787        msgs: &[Vec<u8>],
788        avks: &[StmAggrVerificationKey<D>],
789        parameters: &[StmParameters],
790    ) -> Result<(), StmAggregateSignatureError<D>> {
791        let batch_size = stm_signatures.len();
792        assert_eq!(
793            batch_size,
794            msgs.len(),
795            "Number of messages should correspond to size of the batch"
796        );
797        assert_eq!(
798            batch_size,
799            avks.len(),
800            "Number of avks should correspond to size of the batch"
801        );
802        assert_eq!(
803            batch_size,
804            parameters.len(),
805            "Number of parameters should correspond to size of the batch"
806        );
807
808        let mut aggr_sigs = Vec::with_capacity(batch_size);
809        let mut aggr_vks = Vec::with_capacity(batch_size);
810        for (idx, sig_group) in stm_signatures.iter().enumerate() {
811            sig_group.preliminary_verify(&msgs[idx], &avks[idx], &parameters[idx])?;
812            let grouped_sigs: Vec<Signature> = sig_group
813                .signatures
814                .iter()
815                .map(|sig_reg| sig_reg.sig.sigma)
816                .collect();
817            let grouped_vks: Vec<VerificationKey> = sig_group
818                .signatures
819                .iter()
820                .map(|sig_reg| sig_reg.reg_party.0)
821                .collect();
822
823            let (aggr_vk, aggr_sig) = Signature::aggregate(&grouped_vks, &grouped_sigs).unwrap();
824            aggr_sigs.push(aggr_sig);
825            aggr_vks.push(aggr_vk);
826        }
827
828        let concat_msgs: Vec<Vec<u8>> = msgs
829            .iter()
830            .zip(avks.iter())
831            .map(|(msg, avk)| avk.mt_commitment.concat_with_msg(msg))
832            .collect();
833
834        Signature::batch_verify_aggregates(&concat_msgs, &aggr_vks, &aggr_sigs)?;
835        Ok(())
836    }
837
838    /// Convert multi signature to bytes
839    /// # Layout
840    /// * Number of the pairs of Signatures and Registered Parties (SigRegParty) (as u64)
841    /// * Size of a pair of Signature and Registered Party
842    /// * Pairs of Signatures and Registered Parties
843    /// * Batch proof
844    pub fn to_bytes(&self) -> Vec<u8> {
845        let mut out = Vec::new();
846        out.extend_from_slice(&u64::try_from(self.signatures.len()).unwrap().to_be_bytes());
847        out.extend_from_slice(
848            &u64::try_from(self.signatures[0].to_bytes().len())
849                .unwrap()
850                .to_be_bytes(),
851        );
852        for sig_reg in &self.signatures {
853            out.extend_from_slice(&sig_reg.to_bytes());
854        }
855        let proof = &self.batch_proof;
856        out.extend_from_slice(&proof.to_bytes());
857
858        out
859    }
860
861    ///Extract a `StmAggrSig` from a byte slice.
862    pub fn from_bytes(bytes: &[u8]) -> Result<StmAggrSig<D>, StmAggregateSignatureError<D>> {
863        let mut u64_bytes = [0u8; 8];
864
865        u64_bytes.copy_from_slice(&bytes[..8]);
866        let size = usize::try_from(u64::from_be_bytes(u64_bytes))
867            .map_err(|_| StmAggregateSignatureError::SerializationError)?;
868
869        u64_bytes.copy_from_slice(&bytes[8..16]);
870        let sig_reg_size = usize::try_from(u64::from_be_bytes(u64_bytes))
871            .map_err(|_| StmAggregateSignatureError::SerializationError)?;
872
873        let mut sig_reg_list = Vec::with_capacity(size);
874        for i in 0..size {
875            let sig_reg = StmSigRegParty::from_bytes::<D>(
876                &bytes[16 + (sig_reg_size * i)..16 + (sig_reg_size * (i + 1))],
877            )?;
878            sig_reg_list.push(sig_reg);
879        }
880
881        let offset = 16 + sig_reg_size * size;
882        let batch_proof = BatchPath::from_bytes(&bytes[offset..])?;
883
884        Ok(StmAggrSig {
885            signatures: sig_reg_list,
886            batch_proof,
887        })
888    }
889}
890
891/// Full node verifier including the list of eligible signers and the total stake of the system.
892pub struct CoreVerifier {
893    /// List of registered parties.
894    pub eligible_parties: Vec<RegParty>,
895    /// Total stake of registered parties.
896    pub total_stake: Stake,
897}
898
899impl CoreVerifier {
900    /// Setup a core verifier for given list of signers.
901    ///     * Collect the unique signers in a hash set,
902    ///     * Calculate the total stake of the eligible signers,
903    ///     * Sort the eligible signers.
904    pub fn setup(public_signers: &[(VerificationKey, Stake)]) -> Self {
905        let mut total_stake: Stake = 0;
906        let mut unique_parties = HashSet::new();
907        for signer in public_signers.iter() {
908            let (res, overflow) = total_stake.overflowing_add(signer.1);
909            if overflow {
910                panic!("Total stake overflow");
911            }
912            total_stake = res;
913            unique_parties.insert(MTLeaf(signer.0, signer.1));
914        }
915
916        let mut eligible_parties: Vec<_> = unique_parties.into_iter().collect();
917        eligible_parties.sort_unstable();
918        CoreVerifier {
919            eligible_parties,
920            total_stake,
921        }
922    }
923
924    /// Preliminary verification that checks whether indices are unique and the quorum is achieved.
925    fn preliminary_verify(
926        total_stake: &Stake,
927        signatures: &[StmSigRegParty],
928        parameters: &StmParameters,
929        msg: &[u8],
930    ) -> Result<(), CoreVerifierError> {
931        let mut nr_indices = 0;
932        let mut unique_indices = HashSet::new();
933
934        for sig_reg in signatures {
935            sig_reg
936                .sig
937                .check_indices(parameters, &sig_reg.reg_party.1, msg, total_stake)?;
938            for &index in &sig_reg.sig.indexes {
939                unique_indices.insert(index);
940                nr_indices += 1;
941            }
942        }
943
944        if nr_indices != unique_indices.len() {
945            return Err(CoreVerifierError::IndexNotUnique);
946        }
947        if (nr_indices as u64) < parameters.k {
948            return Err(CoreVerifierError::NoQuorum(nr_indices as u64, parameters.k));
949        }
950
951        Ok(())
952    }
953
954    /// Given a slice of `sig_reg_list`, this function returns a new list of `sig_reg_list` with only valid indices.
955    /// In case of conflict (having several signatures for the same index)
956    /// it selects the smallest signature (i.e. takes the signature with the smallest scalar).
957    /// The function selects at least `self.k` indexes.
958    ///  # Error
959    /// If there is no sufficient signatures, then the function fails.
960    // todo: We need to agree on a criteria to dedup (by default we use a BTreeMap that guarantees keys order)
961    // todo: not good, because it only removes index if there is a conflict (see benches)
962    pub fn dedup_sigs_for_indices(
963        total_stake: &Stake,
964        params: &StmParameters,
965        msg: &[u8],
966        sigs: &[StmSigRegParty],
967    ) -> Result<Vec<StmSigRegParty>, AggregationError> {
968        let mut sig_by_index: BTreeMap<Index, &StmSigRegParty> = BTreeMap::new();
969        let mut removal_idx_by_vk: HashMap<&StmSigRegParty, Vec<Index>> = HashMap::new();
970
971        for sig_reg in sigs.iter() {
972            if sig_reg
973                .sig
974                .verify_core(
975                    params,
976                    &sig_reg.reg_party.0,
977                    &sig_reg.reg_party.1,
978                    msg,
979                    total_stake,
980                )
981                .is_err()
982            {
983                continue;
984            }
985            for index in sig_reg.sig.indexes.iter() {
986                let mut insert_this_sig = false;
987                if let Some(&previous_sig) = sig_by_index.get(index) {
988                    let sig_to_remove_index = if sig_reg.sig.sigma < previous_sig.sig.sigma {
989                        insert_this_sig = true;
990                        previous_sig
991                    } else {
992                        sig_reg
993                    };
994
995                    if let Some(indexes) = removal_idx_by_vk.get_mut(sig_to_remove_index) {
996                        indexes.push(*index);
997                    } else {
998                        removal_idx_by_vk.insert(sig_to_remove_index, vec![*index]);
999                    }
1000                } else {
1001                    insert_this_sig = true;
1002                }
1003
1004                if insert_this_sig {
1005                    sig_by_index.insert(*index, sig_reg);
1006                }
1007            }
1008        }
1009
1010        let mut dedup_sigs: HashSet<StmSigRegParty> = HashSet::new();
1011        let mut count: u64 = 0;
1012
1013        for (_, &sig_reg) in sig_by_index.iter() {
1014            if dedup_sigs.contains(sig_reg) {
1015                continue;
1016            }
1017            let mut deduped_sig = sig_reg.clone();
1018            if let Some(indexes) = removal_idx_by_vk.get(sig_reg) {
1019                deduped_sig.sig.indexes = deduped_sig
1020                    .sig
1021                    .indexes
1022                    .clone()
1023                    .into_iter()
1024                    .filter(|i| !indexes.contains(i))
1025                    .collect();
1026            }
1027
1028            let size: Result<u64, _> = deduped_sig.sig.indexes.len().try_into();
1029            if let Ok(size) = size {
1030                if dedup_sigs.contains(&deduped_sig) {
1031                    panic!("Should not reach!");
1032                }
1033                dedup_sigs.insert(deduped_sig);
1034                count += size;
1035
1036                if count >= params.k {
1037                    return Ok(dedup_sigs.into_iter().collect());
1038                }
1039            }
1040        }
1041
1042        Err(AggregationError::NotEnoughSignatures(count, params.k))
1043    }
1044
1045    /// Collect and return `Vec<Signature>, Vec<VerificationKey>` which will be used
1046    /// by the aggregate verification.
1047    fn collect_sigs_vks(sig_reg_list: &[StmSigRegParty]) -> (Vec<Signature>, Vec<VerificationKey>) {
1048        let sigs = sig_reg_list
1049            .iter()
1050            .map(|sig_reg| sig_reg.sig.sigma)
1051            .collect::<Vec<Signature>>();
1052        let vks = sig_reg_list
1053            .iter()
1054            .map(|sig_reg| sig_reg.reg_party.0)
1055            .collect::<Vec<VerificationKey>>();
1056
1057        (sigs, vks)
1058    }
1059
1060    /// Core verification
1061    ///
1062    /// Verify a list of signatures with respect to given message with given parameters.
1063    pub fn verify(
1064        &self,
1065        signatures: &[StmSig],
1066        parameters: &StmParameters,
1067        msg: &[u8],
1068    ) -> Result<(), CoreVerifierError> {
1069        let sig_reg_list = signatures
1070            .iter()
1071            .map(|sig| StmSigRegParty {
1072                sig: sig.clone(),
1073                reg_party: self.eligible_parties[sig.signer_index as usize],
1074            })
1075            .collect::<Vec<StmSigRegParty>>();
1076
1077        let unique_sigs =
1078            Self::dedup_sigs_for_indices(&self.total_stake, parameters, msg, &sig_reg_list)?;
1079
1080        Self::preliminary_verify(&self.total_stake, &unique_sigs, parameters, msg)?;
1081
1082        let (sigs, vks) = Self::collect_sigs_vks(&unique_sigs);
1083
1084        Signature::verify_aggregate(msg.to_vec().as_slice(), &vks, &sigs)?;
1085
1086        Ok(())
1087    }
1088}
1089
1090#[cfg(test)]
1091mod tests {
1092    use super::*;
1093    use crate::key_reg::*;
1094    use bincode;
1095    use blake2::{digest::consts::U32, Blake2b};
1096    use proptest::collection::{hash_map, vec};
1097    use proptest::prelude::*;
1098    use proptest::test_runner::{RngAlgorithm::ChaCha, TestRng};
1099    use std::collections::{HashMap, HashSet};
1100
1101    use rand_chacha::ChaCha20Rng;
1102    use rand_core::SeedableRng;
1103
1104    type Sig = StmAggrSig<D>;
1105    type D = Blake2b<U32>;
1106
1107    fn setup_equal_parties(params: StmParameters, nparties: usize) -> Vec<StmSigner<D>> {
1108        let stake = vec![1; nparties];
1109        setup_parties(params, stake)
1110    }
1111
1112    fn setup_parties(params: StmParameters, stake: Vec<Stake>) -> Vec<StmSigner<D>> {
1113        let mut kr = KeyReg::init();
1114        let mut trng = TestRng::deterministic_rng(ChaCha);
1115        let mut rng = ChaCha20Rng::from_seed(trng.gen());
1116
1117        #[allow(clippy::needless_collect)]
1118        let ps = stake
1119            .into_iter()
1120            .map(|stake| {
1121                let p = StmInitializer::setup(params, stake, &mut rng);
1122                kr.register(stake, p.pk).unwrap();
1123                p
1124            })
1125            .collect::<Vec<_>>();
1126        let closed_reg = kr.close();
1127        ps.into_iter()
1128            .map(|p| p.new_signer(closed_reg.clone()).unwrap())
1129            .collect()
1130    }
1131
1132    /// Generate a vector of stakes that should sum to `honest_stake`
1133    /// when ignoring the indices in `adversaries`
1134    fn arb_honest_for_adversaries(
1135        num_parties: usize,
1136        honest_stake: Stake,
1137        adversaries: HashMap<usize, Stake>,
1138    ) -> impl Strategy<Value = Vec<Stake>> {
1139        vec(1..honest_stake, num_parties).prop_map(move |parties| {
1140            let honest_sum = parties.iter().enumerate().fold(0, |acc, (i, s)| {
1141                if !adversaries.contains_key(&i) {
1142                    acc + s
1143                } else {
1144                    acc
1145                }
1146            });
1147
1148            parties
1149                .iter()
1150                .enumerate()
1151                .map(|(i, s)| {
1152                    if let Some(a) = adversaries.get(&i) {
1153                        *a
1154                    } else {
1155                        (*s * honest_stake) / honest_sum
1156                    }
1157                })
1158                .collect()
1159        })
1160    }
1161
1162    /// Generate a vector of `num_parties` stakes summing to `num_parties * total_stake`,
1163    /// plus a subset S of 0..num_parties such that the sum of the stakes at indices
1164    /// in S is adversary_stake * N
1165    fn arb_parties_with_adversaries(
1166        num_parties: usize,
1167        num_adversaries: usize,
1168        total_stake: Stake,
1169        adversary_stake: Stake,
1170    ) -> impl Strategy<Value = (HashSet<usize>, Vec<Stake>)> {
1171        hash_map(0..num_parties, 1..total_stake, num_adversaries).prop_flat_map(
1172            move |adversaries| {
1173                let adversary_sum: Stake = adversaries.values().sum();
1174                let adversaries_normed = adversaries
1175                    .iter()
1176                    .map(|(a, stake)| (*a, (stake * adversary_stake) / adversary_sum))
1177                    .collect();
1178
1179                let adversaries = adversaries.into_keys().collect();
1180                (
1181                    Just(adversaries),
1182                    arb_honest_for_adversaries(
1183                        num_parties,
1184                        total_stake - adversary_stake,
1185                        adversaries_normed,
1186                    ),
1187                )
1188            },
1189        )
1190    }
1191
1192    fn find_signatures(msg: &[u8], ps: &[StmSigner<D>], is: &[usize]) -> Vec<StmSig> {
1193        let mut sigs = Vec::new();
1194        for i in is {
1195            if let Some(sig) = ps[*i].sign(msg) {
1196                sigs.push(sig);
1197            }
1198        }
1199        sigs
1200    }
1201
1202    /// Pick N between min and max, and then
1203    /// generate a vector of N stakes summing to N * tstake,
1204    /// plus a subset S of 0..N such that the sum of the stakes at indices
1205    /// in S is astake * N
1206    fn arb_parties_adversary_stake(
1207        min: usize,
1208        max: usize,
1209        tstake: Stake,
1210        astake: Stake,
1211    ) -> impl Strategy<Value = (HashSet<usize>, Vec<Stake>)> {
1212        (min..max)
1213            .prop_flat_map(|n| (Just(n), 1..=n / 2))
1214            .prop_flat_map(move |(n, nadv)| {
1215                arb_parties_with_adversaries(n, nadv, tstake * n as Stake, astake * n as Stake)
1216            })
1217    }
1218
1219    #[derive(Debug)]
1220    struct ProofTest {
1221        msig: Result<Sig, AggregationError>,
1222        clerk: StmClerk<D>,
1223        msg: [u8; 16],
1224    }
1225    /// Run the protocol up to aggregation. This will produce a valid aggregation of signatures.
1226    /// The following tests mutate this aggregation so that the proof is no longer valid.
1227    fn arb_proof_setup(max_parties: usize) -> impl Strategy<Value = ProofTest> {
1228        any::<[u8; 16]>().prop_flat_map(move |msg| {
1229            (2..max_parties).prop_map(move |n| {
1230                let params = StmParameters {
1231                    m: 5,
1232                    k: 5,
1233                    phi_f: 1.0,
1234                };
1235                let ps = setup_equal_parties(params, n);
1236                let clerk = StmClerk::from_signer(&ps[0]);
1237
1238                let all_ps: Vec<usize> = (0..n).collect();
1239                let sigs = find_signatures(&msg, &ps, &all_ps);
1240
1241                let msig = clerk.aggregate(&sigs, &msg);
1242                ProofTest { msig, clerk, msg }
1243            })
1244        })
1245    }
1246
1247    fn with_proof_mod<F>(mut tc: ProofTest, f: F)
1248    where
1249        F: Fn(&mut Sig, &mut StmClerk<D>, &mut [u8; 16]),
1250    {
1251        match tc.msig {
1252            Ok(mut aggr) => {
1253                f(&mut aggr, &mut tc.clerk, &mut tc.msg);
1254                assert!(aggr
1255                    .verify(&tc.msg, &tc.clerk.compute_avk(), &tc.clerk.params)
1256                    .is_err())
1257            }
1258            Err(e) => unreachable!("Reached an unexpected error: {:?}", e),
1259        }
1260    }
1261
1262    proptest! {
1263        #![proptest_config(ProptestConfig::with_cases(50))]
1264
1265        #[test]
1266        /// Test that `dedup_sigs_for_indices` only takes valid signatures.
1267        fn test_dedup(msg in any::<[u8; 16]>()) {
1268            let false_msg = [1u8; 20];
1269            let params = StmParameters { m: 1, k: 1, phi_f: 1.0 };
1270            let ps = setup_equal_parties(params, 1);
1271            let clerk = StmClerk::from_signer(&ps[0]);
1272            let avk = clerk.compute_avk();
1273            let mut sigs = Vec::with_capacity(2);
1274
1275            if let Some(sig) = ps[0].sign(&false_msg) {
1276                sigs.push(sig);
1277            }
1278
1279            if let Some(sig) = ps[0].sign(&msg) {
1280                sigs.push(sig);
1281            }
1282
1283            let sig_reg_list = sigs
1284            .iter()
1285            .map(|sig| StmSigRegParty {
1286                sig: sig.clone(),
1287                reg_party: clerk.closed_reg.reg_parties[sig.signer_index as usize],
1288            })
1289            .collect::<Vec<StmSigRegParty>>();
1290
1291            let msgp = avk.mt_commitment.concat_with_msg(&msg);
1292            let dedup_result = CoreVerifier::dedup_sigs_for_indices(
1293                &clerk.closed_reg.total_stake,
1294                &params,
1295                &msgp,
1296                &sig_reg_list,
1297            );
1298            assert!(dedup_result.is_ok(), "dedup failure {dedup_result:?}");
1299            for passed_sigs in dedup_result.unwrap() {
1300                let verify_result = passed_sigs.sig.verify(&params, &ps[0].vk, &ps[0].stake, &avk, &msg);
1301                assert!(verify_result.is_ok(), "verify {verify_result:?}");
1302            }
1303        }
1304    }
1305
1306    proptest! {
1307        #![proptest_config(ProptestConfig::with_cases(50))]
1308
1309        #[test]
1310        /// Test that when a quorum is found, the aggregate signature can be verified by anyone with
1311        /// access to the avk and the parameters.
1312        fn test_aggregate_sig(nparties in 2_usize..30,
1313                              m in 10_u64..20,
1314                              k in 1_u64..5,
1315                              msg in any::<[u8;16]>()) {
1316            let params = StmParameters { m, k, phi_f: 0.2 };
1317            let ps = setup_equal_parties(params, nparties);
1318            let clerk = StmClerk::from_signer(&ps[0]);
1319
1320            let all_ps: Vec<usize> = (0..nparties).collect();
1321            let sigs = find_signatures(&msg, &ps, &all_ps);
1322            let msig = clerk.aggregate(&sigs, &msg);
1323
1324            match msig {
1325                Ok(aggr) => {
1326                    let verify_result = aggr.verify(&msg, &clerk.compute_avk(), &params);
1327                    assert!(verify_result.is_ok(), "Verification failed: {verify_result:?}");
1328                }
1329                Err(AggregationError::NotEnoughSignatures(n, k)) =>
1330                    assert!(n < params.k || k == params.k),
1331                Err(AggregationError::UsizeConversionInvalid) =>
1332                    unreachable!()
1333            }
1334        }
1335
1336        #[test]
1337        /// Test that batch verification of certificates works
1338        fn batch_verify(nparties in 2_usize..30,
1339                              m in 10_u64..20,
1340                              k in 1_u64..4,
1341                              seed in any::<[u8;32]>(),
1342                              batch_size in 2..10,
1343        ) {
1344            let mut rng = ChaCha20Rng::from_seed(seed);
1345            let mut aggr_avks = Vec::new();
1346            let mut aggr_stms = Vec::new();
1347            let mut batch_msgs = Vec::new();
1348            let mut batch_params = Vec::new();
1349            for _ in 0..batch_size {
1350                let mut msg = [0u8; 32];
1351                rng.fill_bytes(&mut msg);
1352                let params = StmParameters { m, k, phi_f: 0.95 };
1353                let ps = setup_equal_parties(params, nparties);
1354                let clerk = StmClerk::from_signer(&ps[0]);
1355
1356                let all_ps: Vec<usize> = (0..nparties).collect();
1357                let sigs = find_signatures(&msg, &ps, &all_ps);
1358                let msig = clerk.aggregate(&sigs, &msg);
1359
1360                match msig {
1361                    Ok(aggr) => {
1362                        aggr_avks.push(clerk.compute_avk());
1363                        aggr_stms.push(aggr);
1364                        batch_msgs.push(msg.to_vec());
1365                        batch_params.push(params);
1366                    }
1367                    Err(AggregationError::NotEnoughSignatures(_n, _k)) => {
1368                        assert!(sigs.len() < params.k as usize)
1369                    }
1370                    Err(AggregationError::UsizeConversionInvalid) => unreachable!(),
1371                }
1372            }
1373
1374            assert!(StmAggrSig::batch_verify(&aggr_stms, &batch_msgs, &aggr_avks, &batch_params).is_ok());
1375
1376            let mut msg = [0u8; 32];
1377            rng.fill_bytes(&mut msg);
1378            let params = StmParameters { m, k, phi_f: 0.8 };
1379            let ps = setup_equal_parties(params, nparties);
1380            let clerk = StmClerk::from_signer(&ps[0]);
1381
1382            let all_ps: Vec<usize> = (0..nparties).collect();
1383            let sigs = find_signatures(&msg, &ps, &all_ps);
1384            let fake_msig = clerk.aggregate(&sigs, &msg);
1385
1386            aggr_stms[0] = fake_msig.unwrap();
1387            assert!(StmAggrSig::batch_verify(&aggr_stms, &batch_msgs, &aggr_avks, &batch_params).is_err());
1388        }
1389    }
1390
1391    proptest! {
1392        #[test]
1393        /// Test that when a party creates a signature it can be verified
1394        fn test_sig(msg in any::<[u8;16]>()) {
1395            let params = StmParameters { m: 1, k: 1, phi_f: 0.2 };
1396            let ps = setup_equal_parties(params, 1);
1397            let clerk = StmClerk::from_signer(&ps[0]);
1398            let avk = clerk.compute_avk();
1399
1400            if let Some(sig) = ps[0].sign(&msg) {
1401                assert!(sig.verify(&params, &ps[0].vk, &ps[0].stake, &avk, &msg).is_ok());
1402            }
1403        }
1404    }
1405
1406    proptest! {
1407        #![proptest_config(ProptestConfig::with_cases(10))]
1408        #[test]
1409        fn test_parameters_serialize_deserialize(m in any::<u64>(), k in any::<u64>(), phi_f in any::<f64>()) {
1410            let params = StmParameters { m, k, phi_f };
1411
1412            let bytes = params.to_bytes();
1413            let deserialised = StmParameters::from_bytes(&bytes);
1414            assert!(deserialised.is_ok())
1415        }
1416
1417        #[test]
1418        fn test_initializer_serialize_deserialize(seed in any::<[u8;32]>()) {
1419            let mut rng = ChaCha20Rng::from_seed(seed);
1420            let params = StmParameters { m: 1, k: 1, phi_f: 1.0 };
1421            let stake = rng.next_u64();
1422            let initializer = StmInitializer::setup(params, stake, &mut rng);
1423
1424            let bytes = initializer.to_bytes();
1425            assert!(StmInitializer::from_bytes(&bytes).is_ok());
1426
1427            let bytes = bincode::serialize(&initializer).unwrap();
1428            assert!(bincode::deserialize::<StmInitializer>(&bytes).is_ok())
1429        }
1430
1431        #[test]
1432        fn test_sig_serialize_deserialize(msg in any::<[u8;16]>()) {
1433            let params = StmParameters { m: 1, k: 1, phi_f: 0.2 };
1434            let ps = setup_equal_parties(params, 1);
1435            let clerk = StmClerk::from_signer(&ps[0]);
1436            let avk = clerk.compute_avk();
1437
1438            if let Some(sig) = ps[0].sign(&msg) {
1439                let bytes = sig.to_bytes();
1440                let sig_deser = StmSig::from_bytes::<D>(&bytes).unwrap();
1441                assert!(sig_deser.verify(&params, &ps[0].vk, &ps[0].stake, &avk, &msg).is_ok());
1442
1443                let encoded = bincode::serialize(&sig).unwrap();
1444                let decoded: StmSig = bincode::deserialize(&encoded).unwrap();
1445                assert!(decoded.verify(&params, &ps[0].vk, &ps[0].stake, &avk, &msg).is_ok());
1446            }
1447        }
1448
1449        #[test]
1450        fn test_multisig_serialize_deserialize(nparties in 2_usize..10,
1451                                          msg in any::<[u8;16]>()) {
1452            let params = StmParameters { m: 10, k: 5, phi_f: 1.0 };
1453            let ps = setup_equal_parties(params, nparties);
1454            let clerk = StmClerk::from_signer(&ps[0]);
1455
1456            let all_ps: Vec<usize> = (0..nparties).collect();
1457            let sigs = find_signatures(&msg, &ps, &all_ps);
1458            let msig = clerk.aggregate(&sigs, &msg);
1459            if let Ok(aggr) = msig {
1460                    let bytes: Vec<u8> = aggr.to_bytes();
1461                    let aggr2 = StmAggrSig::from_bytes(&bytes).unwrap();
1462                    assert!(aggr2.verify(&msg, &clerk.compute_avk(), &params).is_ok());
1463
1464                    let encoded = bincode::serialize(&aggr).unwrap();
1465                    let decoded: StmAggrSig::<D> = bincode::deserialize(&encoded).unwrap();
1466                    assert!(decoded.verify(&msg, &clerk.compute_avk(), &params).is_ok());
1467            }
1468        }
1469    }
1470
1471    proptest! {
1472        #![proptest_config(ProptestConfig::with_cases(10))]
1473
1474        #[test]
1475        /// Test that when the adversaries do not hold sufficient stake, they can not form a quorum
1476        fn test_adversary_quorum(
1477            (adversaries, parties) in arb_parties_adversary_stake(8, 30, 16, 4),
1478            msg in any::<[u8;16]>(),
1479        ) {
1480            // Test sanity check:
1481            // Check that the adversarial party has less than 40% of the total stake.
1482            let (good, bad) = parties.iter().enumerate().fold((0,0), |(acc1, acc2), (i, st)| {
1483                if adversaries.contains(&i) {
1484                    (acc1, acc2 + *st)
1485                } else {
1486                    (acc1 + *st, acc2)
1487                }
1488            });
1489            assert!(bad as f64 / ((good + bad) as f64) < 0.4);
1490
1491            let params = StmParameters { m: 2642, k: 357, phi_f: 0.2 }; // From Table 1
1492            let ps = setup_parties(params, parties);
1493
1494            let sigs =  find_signatures(&msg, &ps, &adversaries.into_iter().collect::<Vec<_>>());
1495
1496            assert!(sigs.len() < params.k as usize);
1497
1498            let clerk = StmClerk::from_signer(&ps[0]);
1499
1500            let msig = clerk.aggregate(&sigs, &msg);
1501            match msig {
1502                Err(AggregationError::NotEnoughSignatures(n, k)) =>
1503                    assert!(n < params.k && params.k == k),
1504                _ =>
1505                    unreachable!(),
1506            }
1507        }
1508    }
1509
1510    proptest! {
1511        // Each of the tests below corresponds to falsifying a conjunct in the
1512        // definition of a valid signature
1513        #[test]
1514        fn test_invalid_proof_quorum(tc in arb_proof_setup(10)) {
1515            with_proof_mod(tc, |_aggr, clerk, _msg| {
1516                clerk.params.k += 7;
1517            })
1518        }
1519        // todo: fn test_invalid_proof_individual_sig
1520        #[test]
1521        fn test_invalid_proof_index_bound(tc in arb_proof_setup(10)) {
1522            with_proof_mod(tc, |_aggr, clerk, _msg| {
1523                clerk.params.m = 1;
1524            })
1525        }
1526        #[test]
1527        fn test_invalid_proof_index_unique(tc in arb_proof_setup(10)) {
1528            with_proof_mod(tc, |aggr, clerk, _msg| {
1529                for sig_reg in aggr.signatures.iter_mut() {
1530                    for index in sig_reg.sig.indexes.iter_mut() {
1531                       *index %= clerk.params.k - 1
1532                    }
1533                }
1534            })
1535        }
1536        #[test]
1537        fn test_invalid_proof_path(tc in arb_proof_setup(10)) {
1538            with_proof_mod(tc, |aggr, _, _msg| {
1539                let p = aggr.batch_proof.clone();
1540                let mut index_list = p.indices.clone();
1541                let values = p.values;
1542                let batch_proof = {
1543                    index_list[0] += 1;
1544                    BatchPath {
1545                        values,
1546                        indices: index_list,
1547                        hasher: Default::default()
1548                    }
1549                };
1550                aggr.batch_proof = batch_proof;
1551            })
1552        }
1553    }
1554
1555    // ---------------------------------------------------------------------
1556    // Core verifier
1557    // ---------------------------------------------------------------------
1558    fn setup_equal_core_parties(
1559        params: StmParameters,
1560        nparties: usize,
1561    ) -> (Vec<StmInitializer>, Vec<(VerificationKey, Stake)>) {
1562        let stake = vec![1; nparties];
1563        setup_core_parties(params, stake)
1564    }
1565
1566    fn setup_core_parties(
1567        params: StmParameters,
1568        stake: Vec<Stake>,
1569    ) -> (Vec<StmInitializer>, Vec<(VerificationKey, Stake)>) {
1570        let mut trng = TestRng::deterministic_rng(ChaCha);
1571        let mut rng = ChaCha20Rng::from_seed(trng.gen());
1572
1573        let ps = stake
1574            .into_iter()
1575            .map(|stake| StmInitializer::setup(params, stake, &mut rng))
1576            .collect::<Vec<StmInitializer>>();
1577
1578        let public_signers = ps
1579            .iter()
1580            .map(|s| (s.pk.vk, s.stake))
1581            .collect::<Vec<(VerificationKey, Stake)>>();
1582
1583        (ps, public_signers)
1584    }
1585
1586    fn find_core_signatures(
1587        msg: &[u8],
1588        ps: &[StmSigner<D>],
1589        total_stake: Stake,
1590        is: &[usize],
1591    ) -> Vec<StmSig> {
1592        let mut sigs = Vec::new();
1593        for i in is {
1594            if let Some(sig) = ps[*i].core_sign(msg, total_stake) {
1595                sigs.push(sig);
1596            }
1597        }
1598        sigs
1599    }
1600
1601    proptest! {
1602        #![proptest_config(ProptestConfig::with_cases(50))]
1603
1604        #[test]
1605        fn test_core_verifier(nparties in 2_usize..30,
1606                              m in 10_u64..20,
1607                              k in 1_u64..5,
1608                              msg in any::<[u8;16]>()) {
1609
1610            let params = StmParameters { m, k, phi_f: 0.2 };
1611            let (initializers, public_signers) = setup_equal_core_parties(params, nparties);
1612            let all_ps: Vec<usize> = (0..nparties).collect();
1613
1614            let core_verifier = CoreVerifier::setup(&public_signers);
1615
1616            let signers = initializers
1617                .into_iter()
1618                .filter_map(|s| s.new_core_signer(&core_verifier.eligible_parties))
1619                .collect::<Vec<StmSigner<D>>>();
1620
1621            let signatures = find_core_signatures(&msg, &signers, core_verifier.total_stake, &all_ps);
1622
1623            let verify_result = core_verifier.verify(&signatures, &params, &msg);
1624
1625            match verify_result{
1626                Ok(_) => {
1627                    assert!(verify_result.is_ok(), "Verification failed: {verify_result:?}");
1628                }
1629                Err(CoreVerifierError::NoQuorum(nr_indices, _k)) => {
1630                    assert!((nr_indices) < params.k);
1631                }
1632                Err(CoreVerifierError::IndexNotUnique) => unreachable!(),
1633                _ => unreachable!(),
1634            }
1635        }
1636
1637        #[test]
1638        fn test_total_stake_core_verifier(nparties in 2_usize..30,
1639                              m in 10_u64..20,
1640                              k in 1_u64..5,) {
1641            let params = StmParameters { m, k, phi_f: 0.2 };
1642            let (_initializers, public_signers) = setup_equal_core_parties(params, nparties);
1643            let core_verifier = CoreVerifier::setup(&public_signers);
1644            assert_eq!(nparties as u64, core_verifier.total_stake, "Total stake expected: {}, got: {}.", nparties, core_verifier.total_stake);
1645        }
1646    }
1647}