mithril_stm/aggregate_signature/
basic_verifier.rs

1use std::collections::{BTreeMap, HashMap, HashSet};
2
3use crate::bls_multi_signature::{BlsSignature, BlsVerificationKey};
4use crate::key_registration::RegisteredParty;
5use crate::merkle_tree::MerkleTreeLeaf;
6use crate::{
7    AggregationError, CoreVerifierError, Index, Parameters, SingleSignature,
8    SingleSignatureWithRegisteredParty, Stake,
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.4.9", 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    ) -> Result<(), CoreVerifierError> {
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            for &index in &sig_reg.sig.indexes {
68                unique_indices.insert(index);
69                nr_indices += 1;
70            }
71        }
72
73        if nr_indices != unique_indices.len() {
74            return Err(CoreVerifierError::IndexNotUnique);
75        }
76        if (nr_indices as u64) < parameters.k {
77            return Err(CoreVerifierError::NoQuorum(nr_indices as u64, parameters.k));
78        }
79
80        Ok(())
81    }
82
83    /// Given a slice of `sig_reg_list`, this function returns a new list of `sig_reg_list` with only valid indices.
84    /// In case of conflict (having several signatures for the same index)
85    /// it selects the smallest signature (i.e. takes the signature with the smallest scalar).
86    /// The function selects at least `self.k` indexes.
87    ///  # Error
88    /// If there is no sufficient signatures, then the function fails.
89    // todo: We need to agree on a criteria to dedup (by default we use a BTreeMap that guarantees keys order)
90    // todo: not good, because it only removes index if there is a conflict (see benches)
91    pub fn select_valid_signatures_for_k_indices(
92        total_stake: &Stake,
93        params: &Parameters,
94        msg: &[u8],
95        sigs: &[SingleSignatureWithRegisteredParty],
96    ) -> Result<Vec<SingleSignatureWithRegisteredParty>, AggregationError> {
97        let mut sig_by_index: BTreeMap<Index, &SingleSignatureWithRegisteredParty> =
98            BTreeMap::new();
99        let mut removal_idx_by_vk: HashMap<&SingleSignatureWithRegisteredParty, Vec<Index>> =
100            HashMap::new();
101
102        for sig_reg in sigs.iter() {
103            if sig_reg
104                .sig
105                .basic_verify(
106                    params,
107                    &sig_reg.reg_party.0,
108                    &sig_reg.reg_party.1,
109                    msg,
110                    total_stake,
111                )
112                .is_err()
113            {
114                continue;
115            }
116            for index in sig_reg.sig.indexes.iter() {
117                let mut insert_this_sig = false;
118                if let Some(&previous_sig) = sig_by_index.get(index) {
119                    let sig_to_remove_index = if sig_reg.sig.sigma < previous_sig.sig.sigma {
120                        insert_this_sig = true;
121                        previous_sig
122                    } else {
123                        sig_reg
124                    };
125
126                    if let Some(indexes) = removal_idx_by_vk.get_mut(sig_to_remove_index) {
127                        indexes.push(*index);
128                    } else {
129                        removal_idx_by_vk.insert(sig_to_remove_index, vec![*index]);
130                    }
131                } else {
132                    insert_this_sig = true;
133                }
134
135                if insert_this_sig {
136                    sig_by_index.insert(*index, sig_reg);
137                }
138            }
139        }
140
141        let mut dedup_sigs: HashSet<SingleSignatureWithRegisteredParty> = HashSet::new();
142        let mut count: u64 = 0;
143
144        for (_, &sig_reg) in sig_by_index.iter() {
145            if dedup_sigs.contains(sig_reg) {
146                continue;
147            }
148            let mut deduped_sig = sig_reg.clone();
149            if let Some(indexes) = removal_idx_by_vk.get(sig_reg) {
150                deduped_sig.sig.indexes = deduped_sig
151                    .sig
152                    .indexes
153                    .clone()
154                    .into_iter()
155                    .filter(|i| !indexes.contains(i))
156                    .collect();
157            }
158
159            let size: Result<u64, _> = deduped_sig.sig.indexes.len().try_into();
160            if let Ok(size) = size {
161                if dedup_sigs.contains(&deduped_sig) {
162                    panic!("Should not reach!");
163                }
164                dedup_sigs.insert(deduped_sig);
165                count += size;
166
167                if count >= params.k {
168                    return Ok(dedup_sigs.into_iter().collect());
169                }
170            }
171        }
172        Err(AggregationError::NotEnoughSignatures(count, params.k))
173    }
174
175    /// Given a slice of `sig_reg_list`, this function returns a new list of `sig_reg_list` with only valid indices.
176    /// In case of conflict (having several signatures for the same index)
177    /// it selects the smallest signature (i.e. takes the signature with the smallest scalar).
178    /// The function selects at least `self.k` indexes.
179    ///  # Error
180    /// If there is no sufficient signatures, then the function fails.
181    // todo: We need to agree on a criteria to dedup (by default we use a BTreeMap that guarantees keys order)
182    // todo: not good, because it only removes index if there is a conflict (see benches)
183    #[deprecated(
184        since = "0.4.9",
185        note = "Use `select_valid_signatures_for_k_indices` instead"
186    )]
187    pub fn dedup_sigs_for_indices(
188        total_stake: &Stake,
189        params: &Parameters,
190        msg: &[u8],
191        sigs: &[SingleSignatureWithRegisteredParty],
192    ) -> Result<Vec<SingleSignatureWithRegisteredParty>, AggregationError> {
193        Self::select_valid_signatures_for_k_indices(total_stake, params, msg, sigs)
194    }
195
196    /// Collect and return `Vec<BlsSignature>, Vec<BlsVerificationKey>` which will be used
197    /// by the aggregate verification.
198    pub(crate) fn collect_signatures_verification_keys(
199        sig_reg_list: &[SingleSignatureWithRegisteredParty],
200    ) -> (Vec<BlsSignature>, Vec<BlsVerificationKey>) {
201        let sigs = sig_reg_list
202            .iter()
203            .map(|sig_reg| sig_reg.sig.sigma)
204            .collect::<Vec<BlsSignature>>();
205        let vks = sig_reg_list
206            .iter()
207            .map(|sig_reg| sig_reg.reg_party.0)
208            .collect::<Vec<BlsVerificationKey>>();
209
210        (sigs, vks)
211    }
212
213    /// Core verification
214    ///
215    /// Verify a list of signatures with respect to given message with given parameters.
216    pub fn verify(
217        &self,
218        signatures: &[SingleSignature],
219        parameters: &Parameters,
220        msg: &[u8],
221    ) -> Result<(), CoreVerifierError> {
222        let sig_reg_list = signatures
223            .iter()
224            .map(|sig| SingleSignatureWithRegisteredParty {
225                sig: sig.clone(),
226                reg_party: self.eligible_parties[sig.signer_index as usize],
227            })
228            .collect::<Vec<SingleSignatureWithRegisteredParty>>();
229
230        let unique_sigs = Self::select_valid_signatures_for_k_indices(
231            &self.total_stake,
232            parameters,
233            msg,
234            &sig_reg_list,
235        )?;
236
237        Self::preliminary_verify(&self.total_stake, &unique_sigs, parameters, msg)?;
238
239        let (sigs, vks) = Self::collect_signatures_verification_keys(&unique_sigs);
240
241        BlsSignature::verify_aggregate(msg.to_vec().as_slice(), &vks, &sigs)?;
242
243        Ok(())
244    }
245}