wsts/
common.rs

1use core::{
2    fmt::{Debug, Display, Formatter, Result as FmtResult},
3    ops::{Add, Mul},
4};
5use hashbrown::HashMap;
6use num_traits::{One, Zero};
7use rand_core::{CryptoRng, RngCore};
8use serde::{Deserialize, Serialize};
9use sha2::{Digest, Sha256};
10use std::fmt;
11
12use crate::{
13    compute::challenge,
14    curve::{
15        point::{Point, G},
16        scalar::Scalar,
17        traits::MultiMult,
18    },
19    schnorr::ID,
20    util::hash_to_scalar,
21};
22
23/// A merkle root is a 256 bit hash
24pub type MerkleRoot = [u8; 32];
25
26#[derive(Clone, Debug, Deserialize, Serialize, PartialEq)]
27/// A commitment to a polynonial, with a Schnorr proof of ownership bound to the ID
28pub struct PolyCommitment {
29    /// The party ID with a schnorr proof
30    pub id: ID,
31    /// The public polynomial which commits to the secret polynomial
32    pub poly: Vec<Point>,
33}
34
35impl PolyCommitment {
36    /// Verify the wrapped schnorr ID
37    pub fn verify(&self, ctx: &[u8]) -> bool {
38        !self.poly.is_empty() && self.id.verify(&self.poly[0], ctx)
39    }
40}
41
42impl Display for PolyCommitment {
43    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
44        write!(f, "{}", self.id.id)?;
45        for p in &self.poly {
46            write!(f, " {p}")?;
47        }
48        Ok(())
49    }
50}
51
52#[derive(Clone, Eq, PartialEq, Deserialize, Serialize)]
53/// A composite private nonce used as a random commitment in the protocol
54pub struct Nonce {
55    /// The first committed value
56    pub d: Scalar,
57    /// The second committed value
58    pub e: Scalar,
59}
60
61impl fmt::Debug for Nonce {
62    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
63        f.debug_struct("Nonce").finish_non_exhaustive()
64    }
65}
66
67impl Nonce {
68    /// Construct a random nonce
69    pub fn random<RNG: RngCore + CryptoRng>(secret_key: &Scalar, rng: &mut RNG) -> Self {
70        Self {
71            d: Self::gen(secret_key, rng),
72            e: Self::gen(secret_key, rng),
73        }
74    }
75
76    /// Use the IETF nonce generation function from section 4.1 of
77    ///   https://datatracker.ietf.org/doc/rfc9591
78    fn gen<RNG: RngCore + CryptoRng>(secret_key: &Scalar, rng: &mut RNG) -> Scalar {
79        let mut bytes: [u8; 32] = [0; 32];
80        rng.fill_bytes(&mut bytes);
81
82        let mut hasher = Sha256::new();
83
84        hasher.update(bytes);
85        hasher.update(secret_key.to_bytes());
86
87        hash_to_scalar(&mut hasher)
88    }
89
90    /// Check that the nonces are not zero since that can lead to attacks
91    pub fn is_valid(&self) -> bool {
92        !self.is_zero() && !self.is_one()
93    }
94}
95
96impl Zero for Nonce {
97    fn zero() -> Self {
98        Self {
99            d: Scalar::zero(),
100            e: Scalar::zero(),
101        }
102    }
103
104    fn is_zero(&self) -> bool {
105        self.d == Scalar::zero() && self.e == Scalar::zero()
106    }
107}
108
109impl One for Nonce {
110    fn one() -> Self {
111        Self {
112            d: Scalar::one(),
113            e: Scalar::one(),
114        }
115    }
116
117    fn set_one(&mut self) {
118        self.d = Scalar::one();
119        self.e = Scalar::one();
120    }
121
122    fn is_one(&self) -> bool {
123        self.d == Scalar::one() && self.e == Scalar::one()
124    }
125}
126
127impl Add for Nonce {
128    type Output = Self;
129
130    fn add(self, other: Self) -> Self {
131        Self {
132            d: self.d + other.d,
133            e: self.e + other.e,
134        }
135    }
136}
137
138impl Mul for Nonce {
139    type Output = Self;
140
141    fn mul(self, other: Self) -> Self {
142        Self {
143            d: self.d * other.d,
144            e: self.e * other.e,
145        }
146    }
147}
148
149#[derive(Clone, Debug, Eq, PartialEq, Deserialize, Serialize)]
150#[allow(non_snake_case)]
151/// A commitment to the private nonce
152pub struct PublicNonce {
153    /// A commitment to the private nonce's first value
154    pub D: Point,
155    /// A commitment to the private nonce's second value
156    pub E: Point,
157}
158
159impl PublicNonce {
160    /// Check that the nonces are not zero since that can lead to attacks
161    pub fn is_valid(&self) -> bool {
162        self.D != Point::identity() && self.E != Point::identity() && self.D != G && self.E != G
163    }
164}
165
166impl Display for PublicNonce {
167    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
168        write!(f, "{} {}", &self.D, &self.E)
169    }
170}
171
172impl From<Nonce> for PublicNonce {
173    fn from(nonce: Nonce) -> Self {
174        Self {
175            D: nonce.d * G,
176            E: nonce.e * G,
177        }
178    }
179}
180
181impl From<&Nonce> for PublicNonce {
182    fn from(nonce: &Nonce) -> Self {
183        Self {
184            D: nonce.d * G,
185            E: nonce.e * G,
186        }
187    }
188}
189
190impl Add for PublicNonce {
191    type Output = Self;
192
193    fn add(self, other: Self) -> Self {
194        Self {
195            D: self.D + other.E,
196            E: self.E + other.E,
197        }
198    }
199}
200
201impl Zero for PublicNonce {
202    fn zero() -> Self {
203        Self::from(Nonce::zero())
204    }
205
206    fn is_zero(&self) -> bool {
207        self.D == Point::identity() && self.E == Point::identity()
208    }
209}
210
211#[derive(Clone, Deserialize, Serialize, PartialEq)]
212/// A share of the party signature with related values
213pub struct SignatureShare {
214    /// The ID of the party
215    pub id: u32,
216    /// The party signature
217    pub z_i: Scalar,
218    /// The key IDs of the party
219    pub key_ids: Vec<u32>,
220}
221
222impl Debug for SignatureShare {
223    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
224        f.debug_struct("SignatureShare")
225            .field("id", &self.id)
226            .field("z_i", &self.z_i.to_string())
227            .field("key_ids", &self.key_ids)
228            .finish()
229    }
230}
231
232#[allow(non_snake_case)]
233/// An aggregated group signature
234#[derive(Clone, Debug, PartialEq, Deserialize, Serialize)]
235pub struct Signature {
236    /// The sum of the public nonces with commitments to the signed message
237    pub R: Point,
238    /// The sum of the party signatures
239    pub z: Scalar,
240}
241
242impl Signature {
243    #[allow(non_snake_case)]
244    /// Verify the aggregated group signature
245    pub fn verify(&self, public_key: &Point, msg: &[u8]) -> bool {
246        let c = challenge(public_key, &self.R, msg);
247        let R = &self.z * G + (-c) * public_key;
248
249        R == self.R
250    }
251}
252
253#[allow(non_snake_case)]
254/// A Chaum-Pedersen proof that (G, A=a*G, B=b*G, K=(a*b)*G) is a DH tuple
255#[derive(Clone, Debug, PartialEq, Deserialize, Serialize)]
256pub struct TupleProof {
257    /// R = r*G for a random scalar r
258    pub R: Point,
259    /// rB = r*B
260    pub rB: Point,
261    /// z = r + a*s where s = H(G,A,B,K,R) as per Fiat-Shamir
262    pub z: Scalar,
263}
264
265impl TupleProof {
266    #[allow(non_snake_case)]
267    /// Construct a Chaum-Pedersen proof that (G, A, B, K) is a DH tuple
268    pub fn new<RNG: RngCore + CryptoRng>(
269        a: &Scalar,
270        A: &Point,
271        B: &Point,
272        K: &Point,
273        rng: &mut RNG,
274    ) -> Self {
275        let r = Scalar::random(rng);
276        let R = r * G;
277        let rB = r * B;
278        let s = Self::challenge(A, B, K, &R, &rB);
279
280        Self {
281            R,
282            rB,
283            z: r + a * s,
284        }
285    }
286
287    #[allow(non_snake_case)]
288    /// Verify the proof using the transcript and public parameters
289    pub fn verify(&self, A: &Point, B: &Point, K: &Point) -> bool {
290        let s = Self::challenge(A, B, K, &self.R, &self.rB);
291
292        (self.z * G == self.R + s * A) && (self.z * B == self.rB + s * K)
293    }
294
295    #[allow(non_snake_case)]
296    fn challenge(A: &Point, B: &Point, K: &Point, R: &Point, rB: &Point) -> Scalar {
297        let mut hasher = Sha256::new();
298
299        hasher.update("TUPLE_PROOF/".as_bytes());
300        hasher.update(A.compress().as_bytes());
301        hasher.update(B.compress().as_bytes());
302        hasher.update(K.compress().as_bytes());
303        hasher.update(R.compress().as_bytes());
304        hasher.update(rB.compress().as_bytes());
305
306        hash_to_scalar(&mut hasher)
307    }
308}
309
310/// Check that the passed `signer_id` is valid
311pub fn validate_signer_id(signer_id: u32, num_signers: u32) -> bool {
312    signer_id < num_signers
313}
314
315/// Check that the passed `key_id` is valid
316pub fn validate_key_id(key_id: u32, num_keys: u32) -> bool {
317    key_id > 0 && key_id <= num_keys
318}
319
320/// Check that the PolyCommitment is properly signed and has the correct degree polynomial
321pub fn check_public_shares(poly_comm: &PolyCommitment, threshold: usize, ctx: &[u8]) -> bool {
322    poly_comm.poly.len() == threshold && poly_comm.verify(ctx)
323}
324
325/// An implementation of p256k1's MultiMult trait that allows fast checking of DKG private shares
326/// We convert a set of checked polynomial evaluations into a single giant multimult
327/// These evaluations take the form of s * G == \Sum{k=0}{T+1}(a_k * x^k) where the a vals are the coeffs of the polys
328/// There is 1 share per poly, N polys, and each poly is degree T-1 (so T coeffs)
329/// First we evaluate each poly, then we subtract each s * G
330pub struct CheckPrivateShares {
331    /// number of keys
332    n: u32,
333    /// threshold, where the degree of each poly is (t-1)
334    t: u32,
335    /// Powers of x, where x is the receiving key ID
336    powers: Vec<Scalar>,
337    /// Negated DKG private shares for the receiving key ID, indexed by sending key ID
338    pub neg_shares: HashMap<u32, Scalar>,
339    /// Polynomial commitments for each key ID
340    polys: HashMap<u32, PolyCommitment>,
341}
342
343impl CheckPrivateShares {
344    /// Construct a new CheckPrivateShares object
345    pub fn new(
346        id: Scalar,
347        shares: &HashMap<u32, Scalar>,
348        polys: HashMap<u32, PolyCommitment>,
349    ) -> Self {
350        let mut l: usize = 0;
351        if let Some((_id, comm)) = (&polys).into_iter().next() {
352            l = comm.poly.len();
353        }
354        let n: u32 = shares.len().try_into().unwrap();
355        let t: u32 = l.try_into().unwrap();
356        let x = id;
357        let mut powers = Vec::with_capacity(l);
358        let mut pow = Scalar::one();
359
360        for _ in 0..t {
361            powers.push(pow);
362            pow *= &x;
363        }
364
365        let mut neg_shares = HashMap::with_capacity(polys.len());
366        for (i, s) in shares.iter() {
367            neg_shares.insert(*i, -s);
368        }
369
370        Self {
371            n,
372            t,
373            powers,
374            neg_shares,
375            polys,
376        }
377    }
378}
379
380impl MultiMult for CheckPrivateShares {
381    /// The first n*t scalars will be powers, the last n will be the negation of shares
382    fn get_scalar(&self, i: usize) -> &Scalar {
383        let h: u32 = i.try_into().unwrap();
384        let u: usize = self.t.try_into().unwrap();
385        if h < self.n * self.t {
386            &self.powers[i % u]
387        } else {
388            &self.neg_shares[&(h - (self.t * self.n) + 1)]
389        }
390    }
391
392    /// The first n*t points will be poly coeffs, the last n will be G
393    fn get_point(&self, i: usize) -> &Point {
394        let h: u32 = i.try_into().unwrap();
395        let u: usize = self.t.try_into().unwrap();
396        if h < self.n * self.t {
397            let j = i / u;
398            let k = i % u;
399
400            &self.polys[&((j + 1) as u32)].poly[k]
401        } else {
402            &G
403        }
404    }
405
406    fn get_size(&self) -> usize {
407        ((self.t + 1) * self.n).try_into().unwrap()
408    }
409}
410
411/// Helper functions for tests
412pub mod test_helpers {
413    /// Generate a set of `k` vectors which divide `n` IDs evenly
414    pub fn gen_signer_ids(n: u32, k: u32) -> Vec<Vec<u32>> {
415        let mut ids = Vec::new();
416        let m = n / k;
417
418        for i in 0..k {
419            let mut pids = Vec::new();
420            for j in 1..m + 1 {
421                pids.push(i * m + j);
422            }
423            ids.push(pids);
424        }
425
426        ids
427    }
428}
429
430#[cfg(test)]
431/// Test module for common functionality
432pub mod test {
433    use super::*;
434    use crate::{compute, util::create_rng, vss::VSS};
435
436    use rand::prelude::*;
437    use rand_chacha::ChaCha8Rng;
438
439    #[test]
440    #[allow(non_snake_case)]
441    fn tuple_proof() {
442        let mut rng = create_rng();
443        let a = Scalar::random(&mut rng);
444        let b = Scalar::random(&mut rng);
445        let c = Scalar::random(&mut rng);
446
447        let A = Point::from(a);
448        let B = Point::from(b);
449
450        let K = a * B;
451        let tuple_proof = TupleProof::new(&a, &A, &B, &K, &mut rng);
452        assert!(tuple_proof.verify(&A, &B, &K));
453        assert!(!tuple_proof.verify(&B, &A, &K));
454
455        let tuple_proof = TupleProof::new(&b, &A, &B, &K, &mut rng);
456        assert!(!tuple_proof.verify(&A, &B, &K));
457        assert!(!tuple_proof.verify(&B, &A, &K));
458
459        let K = b * A;
460        let tuple_proof = TupleProof::new(&b, &B, &A, &K, &mut rng);
461        assert!(tuple_proof.verify(&B, &A, &K));
462        assert!(!tuple_proof.verify(&A, &B, &K));
463
464        let tuple_proof = TupleProof::new(&a, &B, &A, &K, &mut rng);
465        assert!(!tuple_proof.verify(&B, &A, &K));
466        assert!(!tuple_proof.verify(&A, &B, &K));
467
468        let K = c * A;
469        let tuple_proof = TupleProof::new(&a, &A, &B, &K, &mut rng);
470        assert!(!tuple_proof.verify(&A, &B, &K));
471        assert!(!tuple_proof.verify(&B, &A, &K));
472
473        // try forging a proof by setting rB = z * B - s * K for a random K, with z from a real proof
474        let k = Scalar::random(&mut rng);
475        let K_fake = k * G;
476        let r = Scalar::random(&mut rng);
477        let R = r * G;
478        let rB = r * B;
479        let s = TupleProof::challenge(&A, &B, &K_fake, &R, &rB);
480        let z = r + a * s;
481        let rB_fake = z * B - s * K_fake;
482        let forged_proof = TupleProof { R, rB: rB_fake, z };
483        assert!(!forged_proof.verify(&A, &B, &K_fake));
484    }
485
486    #[test]
487    /// Generating a nonce prior to IETF standard required two 32 byte random fills,
488    /// each of which is directly used as the data buffer for a Scalar (then reduxced).
489    /// Now it requires passing a secret_key, and combining that with a 32-byte random fill
490    ///
491    /// So a reasonable test would be to call the seeded RNG two times to construct
492    /// Scalars, reseed, then compare the output of Nonce::generation.  If none of those
493    /// scalars match the nonce (d,e) values then we have succeeded in scrambling more.
494    fn nonce_generation() {
495        let mut rng = ChaCha8Rng::seed_from_u64(2);
496        let secret_key = Scalar::random(&mut rng);
497        let test_scalars = (0..2)
498            .map(|_| Scalar::random(&mut rng))
499            .collect::<Vec<Scalar>>();
500
501        let mut rng = ChaCha8Rng::seed_from_u64(2);
502        let nonce = Nonce::random(&secret_key, &mut rng);
503
504        for scalar in test_scalars {
505            assert_ne!(scalar, nonce.d);
506            assert_ne!(scalar, nonce.e);
507        }
508    }
509
510    #[test]
511    fn can_check_public_shares() {
512        let mut rng = create_rng();
513        let threshold = 10;
514        let signer_id = 1u32;
515        let ctx = [0u8; 32];
516        let poly = VSS::random_poly(threshold - 1, &mut rng);
517        let comm = PolyCommitment {
518            id: ID::new(&compute::id(signer_id), &poly.data()[0], &ctx, &mut rng),
519            poly: (0..poly.data().len())
520                .map(|i| &poly.data()[i] * G)
521                .collect(),
522        };
523
524        assert!(check_public_shares(
525            &comm,
526            threshold.try_into().unwrap(),
527            &ctx
528        ));
529        let comm = PolyCommitment {
530            poly: Vec::new(),
531            ..comm
532        };
533        assert!(!check_public_shares(
534            &comm,
535            threshold.try_into().unwrap(),
536            &ctx
537        ));
538        assert!(!comm.verify(&ctx));
539    }
540}
wsts/common.rs

wsts/
common.rs
