Skip to main content

wsts/
taproot.rs

1use crate::{
2    common::Signature,
3    compute,
4    curve::{
5        field,
6        point::{Point, G},
7        scalar::Scalar,
8    },
9};
10
11/// A SchnorrProof in BIP-340 format
12#[allow(non_snake_case)]
13#[derive(Clone, Debug, PartialEq, Eq)]
14pub struct SchnorrProof {
15    /// The schnorr public commitment (FROST Signature R)
16    pub r: field::Element,
17    /// The schnorr response (FROST Signature z)
18    pub s: Scalar,
19}
20
21impl SchnorrProof {
22    /// Construct a BIP-340 schnorr proof from a FROST signature
23    pub fn new(sig: &Signature) -> Self {
24        Self {
25            r: sig.R.x(),
26            s: sig.z,
27        }
28    }
29
30    /// Verify a BIP-340 schnorr proof
31    #[allow(non_snake_case)]
32    pub fn verify(&self, public_key: &field::Element, msg: &[u8]) -> bool {
33        let Ok(Y) = Point::lift_x(public_key) else {
34            return false;
35        };
36        let Ok(R) = Point::lift_x(&self.r) else {
37            return false;
38        };
39        let c = compute::challenge(&Y, &R, msg);
40        let Rp = self.s * G - c * Y;
41
42        Rp.has_even_y() && Rp.x() == self.r
43    }
44
45    /// Serialize this proof into a 64-byte buffer
46    pub fn to_bytes(&self) -> [u8; 64] {
47        let mut bytes = [0u8; 64];
48
49        bytes[0..32].copy_from_slice(&self.r.to_bytes());
50        bytes[32..64].copy_from_slice(&self.s.to_bytes());
51
52        bytes
53    }
54}
55
56impl From<[u8; 64]> for SchnorrProof {
57    fn from(bytes: [u8; 64]) -> Self {
58        let mut r_bytes = [0u8; 32];
59        let mut s_bytes = [0u8; 32];
60
61        r_bytes.copy_from_slice(&bytes[0..32]);
62        s_bytes.copy_from_slice(&bytes[32..64]);
63
64        Self {
65            r: field::Element::from(r_bytes),
66            s: Scalar::from(s_bytes),
67        }
68    }
69}
70
71/// Helper functions for tests
72#[cfg(any(test, feature = "testing"))]
73pub mod test_helpers {
74    use super::*;
75    use crate::{
76        common::{PolyCommitment, PublicNonce, SignatureShare},
77        errors::DkgError,
78        traits,
79    };
80
81    use hashbrown::HashMap;
82    use rand_core::{CryptoRng, RngCore};
83
84    /// Run a distributed key generation round
85    #[allow(non_snake_case)]
86    pub fn dkg<RNG: RngCore + CryptoRng, Signer: traits::Signer>(
87        signers: &mut [Signer],
88        rng: &mut RNG,
89    ) -> Result<HashMap<u32, PolyCommitment>, HashMap<u32, DkgError>> {
90        let ctx = 0u64.to_be_bytes();
91        let polys: HashMap<u32, PolyCommitment> = signers
92            .iter()
93            .flat_map(|s| s.get_poly_commitments(&ctx, rng))
94            .map(|comm| (comm.id.id.get_u32(), comm))
95            .collect();
96
97        let mut private_shares = HashMap::new();
98        for signer in signers.iter() {
99            for (signer_id, signer_shares) in signer.get_shares() {
100                private_shares.insert(signer_id, signer_shares);
101            }
102        }
103
104        let mut secret_errors = HashMap::new();
105        for signer in signers.iter_mut() {
106            if let Err(signer_secret_errors) = signer.compute_secrets(&private_shares, &polys, &ctx)
107            {
108                secret_errors.extend(signer_secret_errors);
109            }
110        }
111
112        if secret_errors.is_empty() {
113            Ok(polys)
114        } else {
115            Err(secret_errors)
116        }
117    }
118
119    fn sign_params<RNG: RngCore + CryptoRng, Signer: traits::Signer>(
120        signers: &mut [Signer],
121        rng: &mut RNG,
122    ) -> (Vec<u32>, Vec<u32>, Vec<PublicNonce>) {
123        let secret_key = Scalar::random(rng);
124        let signer_ids: Vec<u32> = signers.iter().map(|s| s.get_id()).collect();
125        let key_ids: Vec<u32> = signers.iter().flat_map(|s| s.get_key_ids()).collect();
126        let nonces: Vec<PublicNonce> = signers
127            .iter_mut()
128            .flat_map(|s| s.gen_nonces(&secret_key, rng))
129            .collect();
130
131        (signer_ids, key_ids, nonces)
132    }
133
134    /// Run a signing round for the passed `msg`
135    pub fn sign<RNG: RngCore + CryptoRng, Signer: traits::Signer>(
136        msg: &[u8],
137        signers: &mut [Signer],
138        rng: &mut RNG,
139        merkle_root: Option<[u8; 32]>,
140    ) -> (Vec<PublicNonce>, Vec<SignatureShare>) {
141        let (signer_ids, key_ids, nonces) = sign_params(signers, rng);
142        let shares = signers
143            .iter()
144            .flat_map(|s| s.sign_taproot(msg, &signer_ids, &key_ids, &nonces, merkle_root))
145            .collect();
146
147        (nonces, shares)
148    }
149
150    /// Run a signing round for the passed `msg`
151    pub fn sign_schnorr<RNG: RngCore + CryptoRng, Signer: traits::Signer>(
152        msg: &[u8],
153        signers: &mut [Signer],
154        rng: &mut RNG,
155    ) -> (Vec<PublicNonce>, Vec<SignatureShare>) {
156        let (signer_ids, key_ids, nonces) = sign_params(signers, rng);
157        let shares = signers
158            .iter()
159            .flat_map(|s| s.sign_schnorr(msg, &signer_ids, &key_ids, &nonces))
160            .collect();
161
162        (nonces, shares)
163    }
164}
165
166#[cfg(test)]
167mod test {
168    use super::{test_helpers, Point, Scalar, SchnorrProof, G};
169
170    #[cfg(feature = "with_v1")]
171    use crate::v1;
172    use crate::{compute, traits::Aggregator, traits::Signer, util::create_rng, v2};
173
174    #[test]
175    #[allow(non_snake_case)]
176    fn key_tweaks() {
177        let mut rng = create_rng();
178        let r = Scalar::random(&mut rng);
179        let R = r * G;
180        let rp = if R.has_even_y() { r } else { -r };
181        let mut d = Scalar::random(&mut rng);
182        let mut P = d * G;
183        let msg = "sign me";
184        let c = compute::challenge(&P, &R, msg.as_bytes());
185
186        println!("P.has_even_y {}", P.has_even_y());
187        println!("R.has_even_y {}", R.has_even_y());
188
189        let s = r - c * d;
190        assert!(R == s * G + c * P);
191
192        while P.has_even_y() {
193            d = Scalar::random(&mut rng);
194            P = d * G;
195        }
196
197        println!("P.has_even_y {}", P.has_even_y());
198        let c = compute::challenge(&P, &R, msg.as_bytes());
199        let s = r - c * d;
200        assert!(R == s * G + c * P);
201
202        assert!(!P.has_even_y());
203        assert_eq!(d * G, P);
204
205        let s = rp + c * (-d);
206        assert!(Point::lift_x(&R.x()).unwrap() == s * G - c * Point::lift_x(&P.x()).unwrap());
207
208        let proof = SchnorrProof { r: R.x(), s };
209        {
210            let Pp = Point::lift_x(&P.x()).unwrap();
211            assert!(Pp == (-d) * G);
212            let R = Point::lift_x(&proof.r).unwrap();
213            let e = compute::challenge(&P, &R, msg.as_bytes());
214            let Rp = proof.s * G - e * Pp;
215            assert!(Rp.has_even_y());
216            assert_eq!(Rp.x(), proof.r);
217        }
218        assert!(proof.verify(&P.x(), msg.as_bytes()));
219
220        let Q = Point::lift_x(&P.x()).unwrap();
221        let c = compute::challenge(&Q, &R, msg.as_bytes());
222        println!("Q.has_even_y {}", Q.has_even_y());
223
224        assert!(Q != P);
225        assert!(d * G != Q);
226
227        let e = -d;
228
229        assert!(e * G == Q);
230
231        let s = r + c * e;
232        assert!(R == s * G - c * Q);
233
234        let s = rp + c * e;
235        let proof = SchnorrProof { r: R.x(), s };
236        assert!(proof.verify(&Q.x(), msg.as_bytes()));
237
238        {
239            let P = Point::lift_x(&Q.x()).unwrap();
240            let R = Point::lift_x(&proof.r).unwrap();
241            let e = compute::challenge(&Q, &R, msg.as_bytes());
242            let Rp = proof.s * G - e * P;
243            assert!(Rp.has_even_y());
244            assert_eq!(Rp.x(), proof.r);
245        }
246
247        let S = compute::tweaked_public_key(&P, None);
248        println!("S.has_even_y {}", S.has_even_y());
249        let t = compute::tweak(&P, None);
250        let d = if !P.has_even_y() { -d + t } else { d + t };
251        assert!((d * G).x() == S.x());
252        assert!((d * G) == S);
253
254        let c = compute::challenge(&S, &R, msg.as_bytes());
255        let s = r - c * d;
256        assert!(R == s * G + c * S);
257
258        let d = if !S.has_even_y() { -d } else { d };
259
260        let s = rp + c * d;
261        let proof = SchnorrProof { r: R.x(), s };
262        {
263            let P = Point::lift_x(&S.x()).unwrap();
264            let R = Point::lift_x(&proof.r).unwrap();
265            let e = compute::challenge(&S, &R, msg.as_bytes());
266            let Rp = proof.s * G - e * P;
267            assert!(Rp.has_even_y());
268            assert_eq!(Rp.x(), proof.r);
269        }
270        assert!(proof.verify(&S.x(), msg.as_bytes()));
271
272        let T = compute::tweaked_public_key(&Q, None);
273        println!("T.has_even_y {}", T.has_even_y());
274        let t = compute::tweak(&Q, None);
275        let e = if !Q.has_even_y() { -e + t } else { e + t };
276        assert!((e * G).x() == T.x());
277        assert!((e * G) == T);
278
279        let c = compute::challenge(&T, &R, msg.as_bytes());
280        let s = r - c * e;
281        assert!(R == s * G + c * T);
282
283        let e = if !T.has_even_y() { -e } else { e };
284
285        let s = rp + c * e;
286        let schnorr_proof = SchnorrProof { r: R.x(), s };
287        assert!(schnorr_proof.verify(&T.x(), msg.as_bytes()));
288    }
289
290    #[test]
291    #[allow(non_snake_case)]
292    #[cfg(feature = "with_v1")]
293    fn taproot_sign_verify_v1_with_merkle_root() {
294        let script = "OP_1".as_bytes();
295        let merkle_root = compute::merkle_root(script);
296
297        taproot_sign_verify_v1(Some(merkle_root));
298    }
299
300    #[test]
301    #[allow(non_snake_case)]
302    #[cfg(feature = "with_v1")]
303    fn taproot_sign_verify_v1_no_merkle_root() {
304        taproot_sign_verify_v1(None);
305    }
306
307    #[allow(non_snake_case)]
308    #[cfg(feature = "with_v1")]
309    fn taproot_sign_verify_v1(merkle_root: Option<[u8; 32]>) {
310        let mut rng = create_rng();
311
312        // First create and verify a frost signature
313        let msg = "It was many and many a year ago".as_bytes();
314        let N: u32 = 10;
315        let T: u32 = 7;
316        let signer_ids: Vec<Vec<u32>> = [
317            [1, 2, 3].to_vec(),
318            [4, 5].to_vec(),
319            [6, 7, 8].to_vec(),
320            [9, 10].to_vec(),
321        ]
322        .to_vec();
323        let mut signers: Vec<v1::Signer> = signer_ids
324            .iter()
325            .enumerate()
326            .map(|(id, ids)| v1::Signer::new(id.try_into().unwrap(), ids, N, T, &mut rng))
327            .collect();
328
329        let polys = match test_helpers::dkg(&mut signers, &mut rng) {
330            Ok(polys) => polys,
331            Err(secret_errors) => {
332                panic!("Got secret errors from DKG: {secret_errors:?}");
333            }
334        };
335
336        let mut S = [signers[0].clone(), signers[1].clone(), signers[3].clone()].to_vec();
337        let mut sig_agg = v1::Aggregator::new(N, T);
338        sig_agg.init(&polys).expect("aggregator init failed");
339        let aggregate_public_key = sig_agg.poly[0];
340        println!(
341            "sign_verify:  agg_pubkey    {}",
342            hex::encode(sig_agg.poly[0].compress().as_bytes())
343        );
344        println!("sign_verify:  agg_pubkey.x  {}", sig_agg.poly[0].x());
345        let tweaked_public_key = compute::tweaked_public_key(&aggregate_public_key, merkle_root);
346        println!(
347            "sign_verify: tweaked_key    {}",
348            hex::encode(tweaked_public_key.compress().as_bytes())
349        );
350        println!("sign_verify: tweaked_key.x  {}", tweaked_public_key.x());
351        let (nonces, sig_shares) = test_helpers::sign(msg, &mut S, &mut rng, merkle_root);
352        let proof = match sig_agg.sign_taproot(msg, &nonces, &sig_shares, &[], merkle_root) {
353            Err(e) => panic!("Aggregator sign failed: {e:?}"),
354            Ok(proof) => proof,
355        };
356
357        // now ser/de the proof
358        let proof_bytes = proof.to_bytes();
359        let proof_deser = SchnorrProof::from(proof_bytes);
360
361        assert_eq!(proof, proof_deser);
362        assert!(proof_deser.verify(&tweaked_public_key.x(), msg));
363    }
364
365    #[test]
366    #[allow(non_snake_case)]
367    fn taproot_sign_verify_v2_with_merkle_root() {
368        let script = "OP_1".as_bytes();
369        let merkle_root = compute::merkle_root(script);
370
371        taproot_sign_verify_v2(Some(merkle_root));
372    }
373
374    #[test]
375    #[allow(non_snake_case)]
376    fn taproot_sign_verify_v2_no_merkle_root() {
377        taproot_sign_verify_v2(None);
378    }
379
380    #[allow(non_snake_case)]
381    fn taproot_sign_verify_v2(merkle_root: Option<[u8; 32]>) {
382        let mut rng = create_rng();
383
384        // First create and verify a frost signature
385        let msg = "It was many and many a year ago".as_bytes();
386        let Nk: u32 = 10;
387        let Np: u32 = 4;
388        let T: u32 = 7;
389        let signer_ids: Vec<Vec<u32>> = [
390            [1, 2, 3].to_vec(),
391            [4, 5].to_vec(),
392            [6, 7, 8].to_vec(),
393            [9, 10].to_vec(),
394        ]
395        .to_vec();
396        let mut signers: Vec<v2::Signer> = signer_ids
397            .iter()
398            .enumerate()
399            .map(|(id, ids)| v2::Signer::new(id.try_into().unwrap(), ids, Np, Nk, T, &mut rng))
400            .collect();
401
402        let polys = match test_helpers::dkg(&mut signers, &mut rng) {
403            Ok(polys) => polys,
404            Err(secret_errors) => {
405                panic!("Got secret errors from DKG: {secret_errors:?}")
406            }
407        };
408
409        let mut S = [signers[0].clone(), signers[1].clone(), signers[3].clone()].to_vec();
410        let key_ids = S.iter().flat_map(|s| s.get_key_ids()).collect::<Vec<u32>>();
411        let mut sig_agg = v2::Aggregator::new(Nk, T);
412        sig_agg.init(&polys).expect("aggregator init failed");
413        let tweaked_public_key = compute::tweaked_public_key(&sig_agg.poly[0], merkle_root);
414        let (nonces, sig_shares) = test_helpers::sign(msg, &mut S, &mut rng, merkle_root);
415        let proof = match sig_agg.sign_taproot(msg, &nonces, &sig_shares, &key_ids, merkle_root) {
416            Err(e) => panic!("Aggregator sign failed: {e:?}"),
417            Ok(proof) => proof,
418        };
419
420        // now ser/de the proof
421        let proof_bytes = proof.to_bytes();
422        let proof_deser = SchnorrProof::from(proof_bytes);
423
424        assert_eq!(proof, proof_deser);
425        assert!(proof_deser.verify(&tweaked_public_key.x(), msg));
426    }
427}