mithril_stm/protocol/aggregate_signature/
basic_verifier.rs

1use anyhow::{Context, anyhow};
2use std::collections::{BTreeMap, HashMap, HashSet};
3
4use crate::{
5    AggregationError, Index, Parameters, RegisteredParty, SingleSignature,
6    SingleSignatureWithRegisteredParty, Stake, StmResult,
7    membership_commitment::MerkleTreeLeaf,
8    signature_scheme::{BlsSignature, BlsVerificationKey},
9};
10
11/// Full node verifier including the list of eligible signers and the total stake of the system.
12pub struct BasicVerifier {
13    /// List of registered parties.
14    pub eligible_parties: Vec<RegisteredParty>,
15    /// Total stake of registered parties.
16    pub total_stake: Stake,
17}
18
19impl BasicVerifier {
20    /// Setup a basic verifier for given list of signers.
21    ///     * Collect the unique signers in a hash set,
22    ///     * Calculate the total stake of the eligible signers,
23    ///     * Sort the eligible signers.
24    pub fn new(public_signers: &[(BlsVerificationKey, Stake)]) -> Self {
25        let mut total_stake: Stake = 0;
26        let mut unique_parties = HashSet::new();
27        for signer in public_signers.iter() {
28            let (res, overflow) = total_stake.overflowing_add(signer.1);
29            if overflow {
30                panic!("Total stake overflow");
31            }
32            total_stake = res;
33            unique_parties.insert(MerkleTreeLeaf(signer.0, signer.1));
34        }
35
36        let mut eligible_parties: Vec<_> = unique_parties.into_iter().collect();
37        eligible_parties.sort_unstable();
38        BasicVerifier {
39            eligible_parties,
40            total_stake,
41        }
42    }
43
44    /// Setup a basic verifier for given list of signers.
45    ///     * Collect the unique signers in a hash set,
46    ///     * Calculate the total stake of the eligible signers,
47    ///     * Sort the eligible signers.
48    #[deprecated(since = "0.5.0", note = "Use `new` instead")]
49    pub fn setup(public_signers: &[(BlsVerificationKey, Stake)]) -> Self {
50        Self::new(public_signers)
51    }
52
53    /// Preliminary verification that checks whether indices are unique and the quorum is achieved.
54    pub(crate) fn preliminary_verify(
55        total_stake: &Stake,
56        signatures: &[SingleSignatureWithRegisteredParty],
57        parameters: &Parameters,
58        msg: &[u8],
59    ) -> StmResult<()> {
60        let mut nr_indices = 0;
61        let mut unique_indices = HashSet::new();
62
63        for sig_reg in signatures {
64            sig_reg
65                .sig
66                .check_indices(parameters, &sig_reg.reg_party.1, msg, total_stake)
67                .with_context(|| "Preliminary verification for basic verifier failed.")?;
68            for &index in &sig_reg.sig.indexes {
69                unique_indices.insert(index);
70                nr_indices += 1;
71            }
72        }
73
74        if nr_indices != unique_indices.len() {
75            return Err(anyhow!(AggregationError::IndexNotUnique));
76        }
77        if (nr_indices as u64) < parameters.k {
78            return Err(anyhow!(AggregationError::NotEnoughSignatures(
79                nr_indices as u64,
80                parameters.k
81            )));
82        }
83
84        Ok(())
85    }
86
87    /// Given a slice of `sig_reg_list`, this function returns a new list of `sig_reg_list` with only valid indices.
88    /// In case of conflict (having several signatures for the same index)
89    /// it selects the smallest signature (i.e. takes the signature with the smallest scalar).
90    /// The function selects at least `self.k` indexes.
91    ///  # Error
92    /// If there is no sufficient signatures, then the function fails.
93    // todo: We need to agree on a criteria to dedup (by default we use a BTreeMap that guarantees keys order)
94    // todo: not good, because it only removes index if there is a conflict (see benches)
95    pub fn select_valid_signatures_for_k_indices(
96        total_stake: &Stake,
97        params: &Parameters,
98        msg: &[u8],
99        sigs: &[SingleSignatureWithRegisteredParty],
100    ) -> StmResult<Vec<SingleSignatureWithRegisteredParty>> {
101        let mut sig_by_index: BTreeMap<Index, &SingleSignatureWithRegisteredParty> =
102            BTreeMap::new();
103        let mut removal_idx_by_vk: HashMap<&SingleSignatureWithRegisteredParty, Vec<Index>> =
104            HashMap::new();
105
106        for sig_reg in sigs.iter() {
107            if sig_reg
108                .sig
109                .basic_verify(
110                    params,
111                    &sig_reg.reg_party.0,
112                    &sig_reg.reg_party.1,
113                    msg,
114                    total_stake,
115                )
116                .is_err()
117            {
118                continue;
119            }
120            for index in sig_reg.sig.indexes.iter() {
121                let mut insert_this_sig = false;
122                if let Some(&previous_sig) = sig_by_index.get(index) {
123                    let sig_to_remove_index = if sig_reg.sig.sigma < previous_sig.sig.sigma {
124                        insert_this_sig = true;
125                        previous_sig
126                    } else {
127                        sig_reg
128                    };
129
130                    if let Some(indexes) = removal_idx_by_vk.get_mut(sig_to_remove_index) {
131                        indexes.push(*index);
132                    } else {
133                        removal_idx_by_vk.insert(sig_to_remove_index, vec![*index]);
134                    }
135                } else {
136                    insert_this_sig = true;
137                }
138
139                if insert_this_sig {
140                    sig_by_index.insert(*index, sig_reg);
141                }
142            }
143        }
144
145        let mut dedup_sigs: HashSet<SingleSignatureWithRegisteredParty> = HashSet::new();
146        let mut count: u64 = 0;
147
148        for (_, &sig_reg) in sig_by_index.iter() {
149            if dedup_sigs.contains(sig_reg) {
150                continue;
151            }
152            let mut deduped_sig = sig_reg.clone();
153            if let Some(indexes) = removal_idx_by_vk.get(sig_reg) {
154                deduped_sig.sig.indexes = deduped_sig
155                    .sig
156                    .indexes
157                    .clone()
158                    .into_iter()
159                    .filter(|i| !indexes.contains(i))
160                    .collect();
161            }
162
163            let size: Result<u64, _> = deduped_sig.sig.indexes.len().try_into();
164            if let Ok(size) = size {
165                if dedup_sigs.contains(&deduped_sig) {
166                    panic!("Should not reach!");
167                }
168                dedup_sigs.insert(deduped_sig);
169                count += size;
170
171                if count >= params.k {
172                    return Ok(dedup_sigs.into_iter().collect());
173                }
174            }
175        }
176        Err(anyhow!(AggregationError::NotEnoughSignatures(
177            count, params.k
178        )))
179    }
180
181    /// Given a slice of `sig_reg_list`, this function returns a new list of `sig_reg_list` with only valid indices.
182    /// In case of conflict (having several signatures for the same index)
183    /// it selects the smallest signature (i.e. takes the signature with the smallest scalar).
184    /// The function selects at least `self.k` indexes.
185    ///  # Error
186    /// If there is no sufficient signatures, then the function fails.
187    // todo: We need to agree on a criteria to dedup (by default we use a BTreeMap that guarantees keys order)
188    // todo: not good, because it only removes index if there is a conflict (see benches)
189    #[deprecated(
190        since = "0.5.0",
191        note = "Use `select_valid_signatures_for_k_indices` instead"
192    )]
193    pub fn dedup_sigs_for_indices(
194        total_stake: &Stake,
195        params: &Parameters,
196        msg: &[u8],
197        sigs: &[SingleSignatureWithRegisteredParty],
198    ) -> StmResult<Vec<SingleSignatureWithRegisteredParty>> {
199        Self::select_valid_signatures_for_k_indices(total_stake, params, msg, sigs)
200    }
201
202    /// Collect and return `Vec<BlsSignature>, Vec<BlsVerificationKey>` which will be used
203    /// by the aggregate verification.
204    pub(crate) fn collect_signatures_verification_keys(
205        sig_reg_list: &[SingleSignatureWithRegisteredParty],
206    ) -> (Vec<BlsSignature>, Vec<BlsVerificationKey>) {
207        let sigs = sig_reg_list
208            .iter()
209            .map(|sig_reg| sig_reg.sig.sigma)
210            .collect::<Vec<BlsSignature>>();
211        let vks = sig_reg_list
212            .iter()
213            .map(|sig_reg| sig_reg.reg_party.0)
214            .collect::<Vec<BlsVerificationKey>>();
215
216        (sigs, vks)
217    }
218
219    /// Core verification
220    ///
221    /// Verify a list of signatures with respect to given message with given parameters.
222    pub fn verify(
223        &self,
224        signatures: &[SingleSignature],
225        parameters: &Parameters,
226        msg: &[u8],
227    ) -> StmResult<()> {
228        let sig_reg_list = signatures
229            .iter()
230            .map(|sig| SingleSignatureWithRegisteredParty {
231                sig: sig.clone(),
232                reg_party: self.eligible_parties[sig.signer_index as usize],
233            })
234            .collect::<Vec<SingleSignatureWithRegisteredParty>>();
235
236        let unique_sigs = Self::select_valid_signatures_for_k_indices(
237            &self.total_stake,
238            parameters,
239            msg,
240            &sig_reg_list,
241        )
242        .with_context(|| "Basic verification failed during selection of unique k indices.")?;
243
244        Self::preliminary_verify(&self.total_stake, &unique_sigs, parameters, msg)?;
245
246        let (sigs, vks) = Self::collect_signatures_verification_keys(&unique_sigs);
247
248        BlsSignature::verify_aggregate(msg.to_vec().as_slice(), &vks, &sigs).with_context(
249            || "Basic verifier failed during BLS aggregate signature verification.",
250        )?;
251
252        Ok(())
253    }
254}
mithril_stm/protocol/aggregate_signature/basic_verifier.rs

mithril_stm/protocol/aggregate_signature/
basic_verifier.rs
