pixel_sig/
threshold_sig.rs

1use rand::{CryptoRng, RngCore};
2
3use crate::keys::{Verkey, Sigkey, MasterSecret, ProofOfPossession, Keypair};
4use amcl_wrapper::field_elem::{FieldElement, FieldElementVector};
5use amcl_wrapper::group_elem::{GroupElement, GroupElementVector};
6use secret_sharing::polynomial::Polynomial;
7use secret_sharing::shamir_secret_sharing::get_shared_secret;
8use crate::{VerkeyGroup, SignatureGroup, VerkeyGroupVec, SignatureGroupVec};
9use std::collections::{HashMap, HashSet};
10use std::mem;
11use crate::errors::PixelError;
12use crate::signature::Signature;
13
14pub struct Signer {
15    pub id: usize,
16    pub sigkey_initial: Sigkey,
17    pub verkey: Verkey,
18    pub pop: ProofOfPossession,
19}
20
21/// Takes shares for secret and generate signing and verification keys
22fn keygen_from_shares<R: RngCore + CryptoRng>(
23    num_signers: usize,
24    mut master_secret_shares: HashMap<usize, FieldElement>,
25    rng: &mut R,
26    gen: &VerkeyGroup,
27    gens: &[SignatureGroup],
28) -> Result<Vec<Signer>, PixelError> {
29    let mut signers = vec![];
30
31    for i in 0..num_signers {
32        let id = i + 1;
33        let x_i = master_secret_shares.remove(&id).unwrap();
34        let master_secret = MasterSecret {value: x_i};
35        let verkey = Verkey::from_master_secret(&master_secret, gen);
36        let pop = Keypair::gen_pop(&verkey, &master_secret);
37        let sigkey_initial = Sigkey::initial_secret_key(
38            gen,
39            gens,
40            &master_secret,
41            rng,
42        )?;
43        mem::drop(master_secret);
44
45        signers.push(Signer {
46            id,
47            sigkey_initial,
48            verkey,
49            pop
50        })
51    }
52    Ok(signers)
53}
54
55/// USING TRUSTED THIRD PARTY ONLY FOR DEMONSTRATION, IN PRACTICE A DECENTRALIZED KEY GENERATION
56/// PROTOCOL WILL BE USED.
57/// Keygen done by trusted party using Shamir secret sharing. Creates signing and verification
58/// keys for each signer. The trusted party will know every signer's secret keys and the
59/// aggregate secret keys and can create signatures.
60/// Outputs 2 items, first is the shared secret and should be destroyed.
61/// The second contains the keys, 1 item corresponding to each signer.
62pub fn trusted_party_SSS_keygen<R: RngCore + CryptoRng>(
63    threshold: usize,
64    total: usize,
65    rng: &mut R,
66    gen: &VerkeyGroup,
67    gens: &[SignatureGroup],
68) -> Result<(FieldElement, Vec<Signer>), PixelError> {
69    let (secret_x, x_shares) = get_shared_secret(threshold, total);
70    Ok((secret_x, keygen_from_shares(total, x_shares, rng, gen, gens)?))
71}
72
73pub struct ThresholdScheme {}
74
75impl ThresholdScheme {
76    /// Combine at least `threshold` number of signatures to create a threshold signature
77    pub fn aggregate_sigs(threshold: usize, sigs: Vec<(usize, Signature)>) -> Signature {
78        assert!(sigs.len() >= threshold);
79
80        let mut sigma_1_bases = SignatureGroupVec::with_capacity(threshold);
81        let mut sigma_1_exps = FieldElementVector::with_capacity(threshold);
82        let mut sigma_2_bases = VerkeyGroupVec::with_capacity(threshold);
83        let mut sigma_2_exps = FieldElementVector::with_capacity(threshold);
84
85        let signer_ids = sigs
86            .iter()
87            .take(threshold)
88            .map(|(i, _)| *i)
89            .collect::<HashSet<usize>>();
90        for (id, sig) in sigs.into_iter().take(threshold) {
91            let l = Polynomial::lagrange_basis_at_0(signer_ids.clone(), id);
92            sigma_1_bases.push(sig.sigma_1.clone());
93            sigma_1_exps.push(l.clone());
94            sigma_2_bases.push(sig.sigma_2.clone());
95            sigma_2_exps.push(l);
96        }
97        // threshold signature = (\product( sig[i].sigma_1^l ), \product( sig[i].sigma_2^l )) for all i
98        Signature {
99            sigma_1: sigma_1_bases.multi_scalar_mul_const_time(sigma_1_exps.as_ref()).unwrap(),
100            sigma_2: sigma_2_bases.multi_scalar_mul_const_time(sigma_2_exps.as_ref()).unwrap(),
101        }
102    }
103
104    /// Create a verification key to verify a threshold signature. Such a key can be created
105    /// once and persisted to be used for any threshold signature
106    pub fn aggregate_vk(threshold: usize, keys: Vec<(usize, &Verkey)>) -> Verkey {
107        assert!(keys.len() >= threshold);
108
109        let mut vk_bases = VerkeyGroupVec::with_capacity(threshold);
110        let mut vk_exps = FieldElementVector::with_capacity(threshold);
111
112        let signer_ids = keys
113            .iter()
114            .take(threshold)
115            .map(|(i, _)| *i)
116            .collect::<HashSet<usize>>();
117        for (id, vk) in keys.into_iter().take(threshold) {
118            let l = Polynomial::lagrange_basis_at_0(signer_ids.clone(), id);
119            vk_bases.push(vk.value.clone());
120            vk_exps.push(l.clone());
121        }
122
123        // threshold verkey = vk_1^l_1 * vk_2^l_2 * ... vk_i^l_i for i in threshold
124
125        Verkey {
126            value: vk_bases.multi_scalar_mul_var_time(vk_exps.as_ref()).unwrap(),
127        }
128    }
129}
130
131#[cfg(test)]
132mod tests {
133    use super::*;
134
135    use rand::rngs::ThreadRng;
136    use crate::util::{GeneratorSet, calculate_l};
137    use crate::signature::Signature;
138    use crate::keys::{InMemorySigKeyDb, SigkeyManager};
139
140    fn check_threshold_key_gen(
141        threshold: usize,
142        secret_x: FieldElement,
143        signers: &[Signer],
144        gen: &VerkeyGroup,
145    ) {
146        let threshold_vk = ThresholdScheme::aggregate_vk(
147            threshold,
148            signers
149                .iter()
150                .take(threshold)
151                .map(|s| (s.id, &s.verkey))
152                .collect::<Vec<(usize, &Verkey)>>(),
153        );
154
155        let expected_vk = gen * &secret_x;
156        assert_eq!(expected_vk, threshold_vk.value);
157    }
158
159    fn check_threshold_key_gen_gaps_in_ids(
160        threshold: usize,
161        secret_x: FieldElement,
162        keys_to_aggr: Vec<(usize, &Verkey)>,
163        gen: &VerkeyGroup,
164    ) {
165        let threshold_vk = ThresholdScheme::aggregate_vk(threshold, keys_to_aggr);
166
167        let expected_vk = gen * &secret_x;
168        assert_eq!(expected_vk, threshold_vk.value);
169    }
170
171    fn check_signing_on_random_msgs(threshold: usize, signers: &[Signer], mut sigkey_dbs: Vec<InMemorySigKeyDb>, mut sk_managers: Vec<SigkeyManager>, T: u128, l: u8, gens: &GeneratorSet) {
172        let mut rng = rand::thread_rng();
173        for t in 1..=T {
174            let msg = FieldElement::random().to_bytes();
175            let mut sigs = vec![];
176            for i in 0..threshold {
177                let sk = sk_managers[i].get_current_key(&sigkey_dbs[i]).unwrap();
178                let sig = Signature::new(&msg, t, l, &gens, sk, &mut rng).unwrap();
179                assert!(sig.verify(&msg, t, l, gens, &signers[i].verkey).unwrap());
180                sigs.push((signers[i].id, sig));
181            }
182
183            let threshold_sig = ThresholdScheme::aggregate_sigs(threshold, sigs);
184
185            let threshold_vk = ThresholdScheme::aggregate_vk(
186                threshold,
187                signers
188                    .iter()
189                    .map(|s| (s.id, &s.verkey))
190                    .collect::<Vec<(usize, &Verkey)>>(),
191            );
192
193            assert!(threshold_sig.verify(&msg, t, l, gens, &threshold_vk).unwrap());
194            for i in 0..threshold {
195                sk_managers[i].simple_update(&gens, &mut rng, &mut sigkey_dbs[i]).unwrap();
196            }
197        }
198    }
199
200    #[test]
201    fn test_verkey_aggregation_shamir_secret_sharing_keygen() {
202        let mut rng = rand::thread_rng();
203        let T = 7;
204        let generators = GeneratorSet::new(T, "test_pixel").unwrap();
205        let threshold = 3;
206        let total = 5;
207
208        let (secret_x, signers) = trusted_party_SSS_keygen(threshold, total, &mut rng, &generators.0, &generators.1).unwrap();
209
210        check_threshold_key_gen(threshold, secret_x, &signers, &generators.0)
211    }
212
213    #[test]
214    fn test_verkey_aggregation_gaps_in_ids_shamir_secret_sharing_keygen() {
215        let mut rng = rand::thread_rng();
216        let T = 7;
217        let generators = GeneratorSet::new(T, "test_pixel").unwrap();
218        let threshold = 3;
219        let total = 5;
220
221        let (secret_x, signers) = trusted_party_SSS_keygen(threshold, total, &mut rng, &generators.0, &generators.1).unwrap();
222
223        let mut keys = vec![];
224        keys.push((signers[0].id, &signers[0].verkey));
225        keys.push((signers[2].id, &signers[2].verkey));
226        keys.push((signers[4].id, &signers[4].verkey));
227
228        check_threshold_key_gen_gaps_in_ids(threshold, secret_x, keys, &generators.0);
229    }
230
231    #[test]
232    fn test_sign_verify_shamir_secret_sharing_keygen() {
233        let mut rng = rand::thread_rng();
234        let T = 7;
235        let l = calculate_l(T).unwrap();
236        let generators = GeneratorSet::new(T, "test_pixel").unwrap();
237        let threshold = 3;
238        let total = 5;
239
240        let (secret_x, signers) = trusted_party_SSS_keygen(threshold, total, &mut rng, &generators.0, &generators.1).unwrap();
241
242        let mut sk_managers = Vec::<SigkeyManager>::new();
243        let mut sigkey_dbs = Vec::<InMemorySigKeyDb>::new();
244        for i in 0..total {
245            let mut db = InMemorySigKeyDb::new();
246            let sk_manager = SigkeyManager::new(T, l, signers[i].sigkey_initial.clone(), &mut db).unwrap();
247            sigkey_dbs.push(db);
248            sk_managers.push(sk_manager);
249        }
250        check_signing_on_random_msgs(threshold, &signers, sigkey_dbs, sk_managers, T, l, &generators)
251    }
252}
pixel_sig/threshold_sig.rs

pixel_sig/
threshold_sig.rs
