sigma_fun/
ed25519.rs

1//! Proofs of knowledge of discrete logarithm on Edwards twist of curve25519 using  using [`curve25519-dalek`].
2//!
3//! **WARNING**: This does not check whether the points are in the prime-order subgroup. For the
4//! proof to be completely sound this needs to be checked by the verifier with [`is_torsion_free`].
5//! This code is mostly here to demonstrate that you can prove a secp256k1 and ed25519 public key
6//! have the same secret key for use in cross-chain atomic swaps between Bitcoin and Monero. If you
7//! are developing a cryptosystem from scratch you should use [`ristretto`] instead.
8//!
9//!
10//! [`curve25519-dalek`]: crate::ed25519::curve25519_dalek
11//! [`is_torsion_free`]: crate::ed25519::curve25519_dalek::edwards::EdwardsPoint::is_torsion_free
12//! [`ristretto`]: crate::ed25519::curve25519_dalek::ristretto
13use crate::{
14    rand_core::{CryptoRng, RngCore},
15    Sigma,
16};
17use core::marker::PhantomData;
18pub use curve25519_dalek;
19use curve25519_dalek::{constants::ED25519_BASEPOINT_TABLE, edwards::EdwardsPoint, scalar::Scalar};
20use digest::Update;
21use generic_array::{
22    typenum::{self, type_operators::IsLessOrEqual, U31},
23    ArrayLength, GenericArray,
24};
25
26/// Proves knowledge of `x` such that `A = x * B` for some `A` and `B` included in the statement.
27#[derive(Clone, Debug, Default, PartialEq)]
28pub struct DL<L> {
29    challenge_len: PhantomData<L>,
30}
31
32impl<L: ArrayLength<u8>> Sigma for DL<L>
33where
34    L: IsLessOrEqual<U31>,
35    <L as IsLessOrEqual<U31>>::Output: typenum::marker_traits::NonZero,
36{
37    type Witness = Scalar;
38    type Statement = (EdwardsPoint, EdwardsPoint);
39    type AnnounceSecret = Scalar;
40    type Announcement = EdwardsPoint;
41    type Response = Scalar;
42    type ChallengeLength = L;
43
44    fn respond(
45        &self,
46        witness: &Self::Witness,
47        _statement: &Self::Statement,
48        announce_secret: Self::AnnounceSecret,
49        _announce: &Self::Announcement,
50        challenge: &GenericArray<u8, Self::ChallengeLength>,
51    ) -> Self::Response {
52        let challenge = normalize_challenge(challenge);
53        announce_secret + challenge * witness
54    }
55
56    fn announce(
57        &self,
58        statement: &Self::Statement,
59        announce_secret: &Self::AnnounceSecret,
60    ) -> Self::Announcement {
61        let G = &statement.0;
62        announce_secret * G
63    }
64
65    fn gen_announce_secret<Rng: CryptoRng + RngCore>(
66        &self,
67        _witness: &Self::Witness,
68        rng: &mut Rng,
69    ) -> Self::AnnounceSecret {
70        Scalar::random(rng)
71    }
72
73    fn sample_response<Rng: CryptoRng + RngCore>(&self, rng: &mut Rng) -> Self::Response {
74        Scalar::random(rng)
75    }
76
77    fn implied_announcement(
78        &self,
79        statement: &Self::Statement,
80        challenge: &GenericArray<u8, Self::ChallengeLength>,
81        response: &Self::Response,
82    ) -> Option<Self::Announcement> {
83        let (G, X) = statement;
84        let challenge = normalize_challenge(challenge);
85        Some(response * G - challenge * X)
86    }
87
88    fn hash_statement<H: Update>(&self, hash: &mut H, statement: &Self::Statement) {
89        hash.update(statement.0.compress().as_bytes());
90        hash.update(statement.1.compress().as_bytes());
91    }
92
93    fn hash_announcement<H: Update>(&self, hash: &mut H, announcement: &Self::Announcement) {
94        hash.update(announcement.compress().as_bytes())
95    }
96
97    fn hash_witness<H: Update>(&self, hash: &mut H, witness: &Self::Witness) {
98        hash.update(witness.to_bytes().as_ref())
99    }
100}
101
102/// Proves knowledge of `x` such that `A = x * G` for some `A` included in the statement.
103/// `G` is the standard basepoint used in the ed25519 signature scheme and is not included in the statement.
104#[derive(Clone, Debug, Default, PartialEq)]
105pub struct DLG<L> {
106    challenge_len: PhantomData<L>,
107}
108
109impl<L: ArrayLength<u8>> Sigma for DLG<L>
110where
111    L: IsLessOrEqual<U31>,
112    <L as IsLessOrEqual<U31>>::Output: typenum::marker_traits::NonZero,
113{
114    type Witness = Scalar;
115    type Statement = EdwardsPoint;
116    type AnnounceSecret = Scalar;
117    type Announcement = EdwardsPoint;
118    type Response = Scalar;
119    type ChallengeLength = L;
120
121    fn respond(
122        &self,
123        witness: &Self::Witness,
124        _statement: &Self::Statement,
125        announce_secret: Self::AnnounceSecret,
126        _announce: &Self::Announcement,
127        challenge: &GenericArray<u8, Self::ChallengeLength>,
128    ) -> Self::Response {
129        let challenge = normalize_challenge(challenge);
130        announce_secret + challenge * witness
131    }
132
133    fn announce(
134        &self,
135        _statement: &Self::Statement,
136        announce_secret: &Self::AnnounceSecret,
137    ) -> Self::Announcement {
138        let G = &ED25519_BASEPOINT_TABLE;
139        announce_secret * G
140    }
141
142    fn gen_announce_secret<Rng: CryptoRng + RngCore>(
143        &self,
144        _witness: &Self::Witness,
145        rng: &mut Rng,
146    ) -> Self::AnnounceSecret {
147        Scalar::random(rng)
148    }
149
150    fn sample_response<Rng: CryptoRng + RngCore>(&self, rng: &mut Rng) -> Self::Response {
151        Scalar::random(rng)
152    }
153
154    fn implied_announcement(
155        &self,
156        statement: &Self::Statement,
157        challenge: &GenericArray<u8, Self::ChallengeLength>,
158        response: &Self::Response,
159    ) -> Option<Self::Announcement> {
160        let X = statement;
161        let challenge = normalize_challenge(challenge);
162        Some(EdwardsPoint::vartime_double_scalar_mul_basepoint(
163            &-challenge,
164            X,
165            response,
166        ))
167    }
168
169    fn hash_statement<H: Update>(&self, hash: &mut H, statement: &Self::Statement) {
170        hash.update(statement.compress().as_bytes());
171    }
172
173    fn hash_announcement<H: Update>(&self, hash: &mut H, announcement: &Self::Announcement) {
174        hash.update(announcement.compress().as_bytes())
175    }
176
177    fn hash_witness<H: Update>(&self, hash: &mut H, witness: &Self::Witness) {
178        hash.update(witness.to_bytes().as_ref())
179    }
180}
181
182fn normalize_challenge<L: ArrayLength<u8>>(challenge: &GenericArray<u8, L>) -> Scalar {
183    let mut challenge_bytes = [0u8; 32];
184    challenge_bytes[..challenge.len()].copy_from_slice(challenge.as_slice());
185    Scalar::from_canonical_bytes(challenge_bytes)
186        .expect("this function is only passed 31 byte arrays at most")
187}
188
189impl<L> crate::Writable for DL<L> {
190    fn write_to<W: core::fmt::Write>(&self, w: &mut W) -> core::fmt::Result {
191        write!(w, "DL(ed25519)")
192    }
193}
194
195impl<L> crate::Writable for DLG<L> {
196    fn write_to<W: core::fmt::Write>(&self, w: &mut W) -> core::fmt::Result {
197        write!(w, "DLG(ed25519)")
198    }
199}
200
201crate::impl_display!(DL<L>);
202crate::impl_display!(DLG<L>);
203
204#[cfg(test)]
205#[allow(missing_docs)]
206pub mod test {
207    use super::*;
208    use crate::FiatShamir;
209    use ::proptest::prelude::*;
210    use sha2::Sha256;
211
212    prop_compose! {
213        pub fn ed25519_scalar()(
214            bytes in any::<[u8; 32]>(),
215        ) -> Scalar {
216            Scalar::from_bytes_mod_order(bytes)
217        }
218    }
219
220    prop_compose! {
221        pub fn ed25519_point()(
222            x in ed25519_scalar(),
223        ) -> EdwardsPoint {
224            &x * &ED25519_BASEPOINT_TABLE
225        }
226    }
227
228    type Transcript = crate::HashTranscript<Sha256, rand_chacha::ChaCha20Rng>;
229
230    proptest! {
231        #[test]
232        fn ed25519_dlg(
233            x in ed25519_scalar(),
234        ) {
235            let G = &ED25519_BASEPOINT_TABLE;
236            let xG = &x * G;
237            let proof_system = FiatShamir::<DLG<U31>, Transcript>::default();
238            let proof = proof_system.prove(&x, &xG, Some(&mut rand::thread_rng()));
239            assert!(proof_system.verify(&xG, &proof));
240        }
241    }
242
243    proptest! {
244        #[test]
245        fn ed25519_dl(
246            x in ed25519_scalar(),
247        ) {
248            let G = &Scalar::random(&mut rand::thread_rng()) * &ED25519_BASEPOINT_TABLE;
249            let xG = x * G;
250            let proof_system = FiatShamir::<DL<U31>, Transcript>::default();
251            let proof = proof_system.prove(&x, &(G, xG), Some(&mut rand::thread_rng()));
252            assert!(proof_system.verify(&(G, xG), &proof));
253        }
254    }
255}
sigma_fun/ed25519.rs

sigma_fun/
ed25519.rs
