mithril_stm/aggregate_signature/
basic_verifier.rs1use 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
11pub struct BasicVerifier {
13 pub eligible_parties: Vec<RegisteredParty>,
15 pub total_stake: Stake,
17}
18
19impl BasicVerifier {
20 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 #[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 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 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 #[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 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 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}