1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218

//! Distributed Key Generation (DKG), Resharing, Signatures, and Threshold Signatures over the BLS12-381 curve.
//!
//! # Features
//!
//! This crate has the following features:
//!
//! - `portable`: Enables `portable` feature on `blst` (<https://github.com/supranational/blst?tab=readme-ov-file#platform-and-language-compatibility>).
//!
//! # Benchmarks
//!
//! _The following benchmarks were collected on 8/23/24 on a MacBook Pro (M3 Pro, Nov 2023)._
//!
//! ```bash
//! cargo bench
//! ```
//!
//! ## DKG Recovery (Contributor)
//!
//! ```txt
//! conc=1 n=5 t=3          time:   [7.8876 µs 8.0956 µs 8.4308 µs]
//! conc=1 n=10 t=7         time:   [33.342 µs 33.436 µs 33.554 µs]
//! conc=1 n=20 t=13        time:   [121.14 µs 123.02 µs 125.79 µs]
//! conc=1 n=50 t=33        time:   [753.15 µs 761.27 µs 773.15 µs]
//! conc=1 n=100 t=67       time:   [3.0440 ms 3.5310 ms 4.3212 ms]
//! conc=1 n=250 t=167      time:   [19.164 ms 19.226 ms 19.295 ms]
//! conc=1 n=500 t=333      time:   [79.523 ms 80.812 ms 82.645 ms]
//! ```
//!
//! ## Reshare Recovery (Contributor)
//!
//! ```txt
//! conc=1 n=5 t=3          time:   [241.59 µs 253.86 µs 263.90 µs]
//! conc=2 n=5 t=3          time:   [175.10 µs 178.24 µs 184.16 µs]
//! conc=4 n=5 t=3          time:   [134.88 µs 144.18 µs 151.21 µs]
//! conc=8 n=5 t=3          time:   [174.37 µs 184.76 µs 192.81 µs]
//! conc=1 n=10 t=7         time:   [1.4708 ms 1.5347 ms 1.6063 ms]
//! conc=2 n=10 t=7         time:   [827.54 µs 908.99 µs 986.19 µs]
//! conc=4 n=10 t=7         time:   [484.35 µs 504.77 µs 535.10 µs]
//! conc=8 n=10 t=7         time:   [508.29 µs 606.27 µs 699.82 µs]
//! conc=1 n=20 t=13        time:   [5.0725 ms 5.0793 ms 5.0857 ms]
//! conc=2 n=20 t=13        time:   [2.8032 ms 2.8116 ms 2.8222 ms]
//! conc=4 n=20 t=13        time:   [1.6856 ms 1.6892 ms 1.6938 ms]
//! conc=8 n=20 t=13        time:   [1.0313 ms 1.1604 ms 1.2300 ms]
//! conc=1 n=50 t=33        time:   [37.000 ms 37.248 ms 37.937 ms]
//! conc=2 n=50 t=33        time:   [19.346 ms 19.642 ms 20.312 ms]
//! conc=4 n=50 t=33        time:   [10.533 ms 10.567 ms 10.614 ms]
//! conc=8 n=50 t=33        time:   [6.3829 ms 6.4347 ms 6.4721 ms]
//! conc=1 n=100 t=67       time:   [174.30 ms 175.16 ms 176.05 ms]
//! conc=2 n=100 t=67       time:   [89.835 ms 90.204 ms 90.599 ms]
//! conc=4 n=100 t=67       time:   [46.736 ms 47.123 ms 47.531 ms]
//! conc=8 n=100 t=67       time:   [29.193 ms 29.519 ms 29.870 ms]
//! conc=1 n=250 t=167      time:   [1.4814 s 1.4927 s 1.5062 s]
//! conc=2 n=250 t=167      time:   [751.83 ms 762.08 ms 780.29 ms]
//! conc=4 n=250 t=167      time:   [394.18 ms 397.18 ms 400.52 ms]
//! conc=8 n=250 t=167      time:   [239.81 ms 245.78 ms 252.11 ms]
//! conc=1 n=500 t=333      time:   [6.9914 s 7.0182 s 7.0452 s]
//! conc=2 n=500 t=333      time:   [3.5483 s 3.5575 s 3.5670 s]
//! conc=4 n=500 t=333      time:   [1.8668 s 1.8851 s 1.9025 s]
//! conc=8 n=500 t=333      time:   [1.1176 s 1.1355 s 1.1539 s]
//! ```
//!
//! ## Signature Generation
//!
//! ```txt
//! ns_len=9 msg_len=5      time:   [232.12 µs 233.63 µs 235.42 µs]
//! ```
//!
//! ## Signature Aggregation
//!
//! ```txt
//! n=5 t=3                 time:   [126.85 µs 128.50 µs 130.67 µs]
//! n=10 t=7                time:   [378.70 µs 386.74 µs 397.13 µs]
//! n=20 t=13               time:   [764.59 µs 777.71 µs 796.76 µs]
//! n=50 t=33               time:   [2.1320 ms 2.1399 ms 2.1547 ms]
//! n=100 t=67              time:   [5.0113 ms 5.0155 ms 5.0203 ms]
//! n=250 t=167             time:   [16.922 ms 16.929 ms 16.937 ms]
//! n=500 t=333             time:   [37.642 ms 37.676 ms 37.729 ms]
//! ```
//!
//! ## Signature Verification
//!
//! ```txt
//! ns_len=9 msg_len=5      time:   [980.92 µs 981.37 µs 981.88 µs]
//! ```

pub mod dkg;
pub mod primitives;
pub mod scheme;

#[cfg(test)]
mod tests {
    use super::*;
    use dkg::ops::generate_shares;
    use primitives::group::Private;
    use primitives::ops::{aggregate, partial_sign, partial_verify, verify};
    use primitives::poly::public;

    #[test]
    fn test_aggregate_signature() {
        let (n, t) = (5, 4);

        // Create the private key polynomial and evaluate it at `n`
        // points to generate the shares.
        //
        // If receiving a share from an untrusted party, the recipient
        // should verify the share is on the public polynomial.
        let (group, shares) = generate_shares(None, n, t);

        // Generate the partial signatures
        let msg = b"hello";
        let partials = shares
            .iter()
            .map(|s| partial_sign(s, &msg[..]))
            .collect::<Vec<_>>();

        // Each partial sig can be partially verified against the public polynomial
        partials.iter().for_each(|partial| {
            partial_verify(&group, &msg[..], partial).unwrap();
        });

        // Generate and verify the threshold sig
        let threshold_sig = aggregate(t, partials).unwrap();
        let threshold_pub = public(&group);
        verify(&threshold_pub, &msg[..], &threshold_sig).unwrap();
    }

    #[test]
    #[should_panic(expected = "NotEnoughPartialSignatures")]
    fn test_aggregate_signature_insufficient() {
        let (n, t) = (5, 4);

        // Create the private key polynomial and evaluate it at `n`
        // points to generate the shares
        let (group, shares) = generate_shares(None, n, t);

        // Only take t-1 shares
        let shares = shares.into_iter().take(t as usize - 1).collect::<Vec<_>>();

        // Generate the partial signatures
        let msg = b"hello";
        let partials = shares
            .iter()
            .map(|s| partial_sign(s, &msg[..]))
            .collect::<Vec<_>>();

        // Each partial sig can be partially verified against the public polynomial
        partials.iter().for_each(|partial| {
            partial_verify(&group, &msg[..], partial).unwrap();
        });

        // Generate and verify the threshold sig
        let threshold_sig = aggregate(t, partials).unwrap();
        let threshold_pub = public(&group);
        verify(&threshold_pub, &msg[..], &threshold_sig).unwrap();
    }

    #[test]
    #[should_panic(expected = "DuplicateEval")]
    fn test_aggregate_signature_insufficient_duplicates() {
        let (n, t) = (5, 4);

        // Create the private key polynomial and evaluate it at `n`
        // points to generate the shares
        let (group, shares) = generate_shares(None, n, t);

        // Only take t-1 shares
        let mut shares = shares.into_iter().take(t as usize - 1).collect::<Vec<_>>();
        shares.push(shares[0]);

        // Generate the partial signatures
        let msg = b"hello";
        let partials = shares
            .iter()
            .map(|s| partial_sign(s, &msg[..]))
            .collect::<Vec<_>>();

        // Each partial sig can be partially verified against the public polynomial
        partials.iter().for_each(|partial| {
            partial_verify(&group, &msg[..], partial).unwrap();
        });

        // Generate and verify the threshold sig
        let threshold_sig = aggregate(t, partials).unwrap();
        let threshold_pub = public(&group);
        verify(&threshold_pub, &msg[..], &threshold_sig).unwrap();
    }

    #[test]
    #[should_panic(expected = "InvalidSignature")]
    fn test_aggregate_signature_bad_share() {
        let (n, t) = (5, 4);

        // Create the private key polynomial and evaluate it at `n`
        // points to generate the shares
        let (group, mut shares) = generate_shares(None, n, t);

        // Corrupt a share
        let share = shares.get_mut(3).unwrap();
        share.private = Private::rand(&mut rand::thread_rng());

        // Generate the partial signatures
        let msg = b"hello";
        let partials = shares
            .iter()
            .map(|s| partial_sign(s, &msg[..]))
            .collect::<Vec<_>>();

        // Each partial sig can be partially verified against the public polynomial
        partials.iter().for_each(|partial| {
            partial_verify(&group, &msg[..], partial).unwrap();
        });

        // Generate and verify the threshold sig
        let threshold_sig = aggregate(t, partials).unwrap();
        let threshold_pub = public(&group);
        verify(&threshold_pub, &msg[..], &threshold_sig).unwrap();
    }
}