mithril_stm/aggregate_signature/
core_verifier.rs

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

mithril_stm/aggregate_signature/
core_verifier.rs
