concordium_base/eddsa_ed25519/
dlog_ed25519.rs

1//! This module provides the implementation of the `dlog` sigma protocol for
2//! curve25519 (cf. "Proof of Knowledge of Discrete Logarithm" Section 9.2.1,
3//! Bluepaper v1.2.5) which enables one to prove knowledge of the discrete
4//! logarithm without revealing it.
5use crate::{common::*, random_oracle::RandomOracle};
6use anyhow::bail;
7use curve25519_dalek::{
8    constants,
9    edwards::{CompressedEdwardsY, EdwardsPoint},
10    scalar::*,
11};
12use ed25519_dalek::*;
13use rand::*;
14use sha2::{Digest, Sha512};
15use thiserror::Error;
16
17#[derive(Clone, Copy, Debug, Eq, PartialEq, SerdeBase16Serialize)]
18pub struct Ed25519DlogProof {
19    challenge: Scalar,
20    response: Scalar,
21}
22
23impl Serial for Ed25519DlogProof {
24    fn serial<B: Buffer>(&self, out: &mut B) {
25        out.write_all(self.challenge.as_bytes())
26            .expect("Writing to buffer should succeed.");
27        out.write_all(self.response.as_bytes())
28            .expect("Writing to buffer should succeed.");
29    }
30}
31
32impl Deserial for Ed25519DlogProof {
33    fn deserial<R: ReadBytesExt>(source: &mut R) -> ParseResult<Self> {
34        let mut buf = [0; 32];
35        source.read_exact(&mut buf)?;
36        if let Some(challenge) = Scalar::from_canonical_bytes(buf).into() {
37            source.read_exact(&mut buf)?;
38            if let Some(response) = Scalar::from_canonical_bytes(buf).into() {
39                Ok(Ed25519DlogProof {
40                    challenge,
41                    response,
42                })
43            } else {
44                bail!("Not a valid response.")
45            }
46        } else {
47            bail!("Not a valid scalar.")
48        }
49    }
50}
51
52pub static PROOF_LENGTH: usize = 2 * 32;
53
54#[derive(Error, Debug)]
55pub enum PointDecodingError {
56    #[error("Not a valid edwards point.")]
57    NotOnCurve,
58    #[error("Not a scalar.")]
59    NotAScalar,
60}
61
62fn scalar_from_secret_key(secret_key: &impl AsRef<[u8]>) -> Scalar {
63    let mut h = Sha512::new();
64    // inspired by this https://docs.rs/ed25519-dalek/2.1.0/src/ed25519_dalek/hazmat.rs.html#61-76
65    let mut hash: [u8; 64] = [0u8; 64];
66    let mut scalar_bytes: [u8; 32] = [0u8; 32];
67    h.update(secret_key);
68    hash.copy_from_slice(h.finalize().as_slice());
69    scalar_bytes.copy_from_slice(&hash[..32]);
70
71    Scalar::from_bytes_mod_order(clamp_integer(scalar_bytes))
72}
73
74fn point_from_public_key(public_key: &VerifyingKey) -> Option<EdwardsPoint> {
75    let bytes = public_key.to_bytes();
76    let res = CompressedEdwardsY::from_slice(&bytes).ok()?;
77    res.decompress()
78}
79
80/// Construct a proof of knowledge of secret key.
81///
82/// The `public_key` and `secret_key` must be the ed25519 public and secret key
83/// pair. The reason this function is not stated with those types is that it is
84/// at present used both for proving ownership of normal signature keys, as well
85/// as for proving ownership of the VRF keys.
86/// The keys for the VRF protocol are physically the same, but they are defined
87/// in a different crate and thus have different types. This situation should be
88/// remedied to regain type safety when we have time to do it properly. This
89/// will probably mean some reorganization of the crates.
90pub fn prove_dlog_ed25519<R: Rng + CryptoRng>(
91    csprng: &mut R,
92    ro: &mut RandomOracle,
93    public_key: &impl Serial,
94    secret_key: &impl AsRef<[u8]>,
95) -> Ed25519DlogProof {
96    let secret = scalar_from_secret_key(secret_key);
97    // FIXME: Add base to the proof.
98    ro.append_message(b"dlog_ed25519", public_key);
99
100    let rand_scalar = Scalar::random(csprng);
101
102    let randomised_point = &rand_scalar * constants::ED25519_BASEPOINT_TABLE;
103
104    ro.append_message(b"randomised_point", &randomised_point.compress().to_bytes());
105    let challenge_bytes = ro.split().result();
106    // FIXME: Do the same as in other proofs in sigma_protocols in id.
107    let mut array = [0u8; 32];
108    array.copy_from_slice(challenge_bytes.as_ref());
109    let challenge = Scalar::from_bytes_mod_order(array);
110    Ed25519DlogProof {
111        challenge,
112        response: rand_scalar - challenge * secret,
113    }
114}
115
116pub fn verify_dlog_ed25519(
117    ro: &mut RandomOracle,
118    public_key: &VerifyingKey,
119    proof: &Ed25519DlogProof,
120) -> bool {
121    match point_from_public_key(public_key) {
122        None => false,
123        Some(public) => {
124            let randomised_point =
125                public * proof.challenge + &proof.response * constants::ED25519_BASEPOINT_TABLE;
126            ro.append_message(b"dlog_ed25519", public_key);
127            ro.append_message(b"randomised_point", &randomised_point.compress().to_bytes());
128
129            // FIXME: Should do the same as for normal dlog.
130            let challenge_bytes = ro.split().result();
131            // FIXME: Do the same as in other proofs in sigma_protocols in id.
132            let mut array = [0u8; 32];
133            array.copy_from_slice(challenge_bytes.as_ref());
134            let challenge = Scalar::from_bytes_mod_order(array);
135            challenge == proof.challenge
136        }
137    }
138}
139
140#[cfg(test)]
141mod tests {
142    use super::*;
143
144    fn generate_challenge_prefix<R: rand::Rng>(csprng: &mut R) -> Vec<u8> {
145        // length of the challenge
146        let l = csprng.gen_range(0..1000);
147        let mut challenge_prefix = vec![0; l];
148        for v in challenge_prefix.iter_mut() {
149            *v = csprng.gen();
150        }
151        challenge_prefix
152    }
153
154    #[test]
155    pub fn test_ed25519_dlog() {
156        let mut csprng = thread_rng();
157        for _ in 0..10000 {
158            let signing = SigningKey::generate(&mut csprng);
159            let secret = signing.to_bytes();
160            let public = signing.verifying_key();
161            let challenge_prefix = generate_challenge_prefix(&mut csprng);
162            let mut ro = RandomOracle::domain(&challenge_prefix);
163            let proof = prove_dlog_ed25519(&mut csprng, &mut ro.split(), &public, &secret);
164            assert!(verify_dlog_ed25519(&mut ro, &public, &proof));
165            let challenge_prefix_1 = generate_challenge_prefix(&mut csprng);
166            if verify_dlog_ed25519(
167                &mut RandomOracle::domain(&challenge_prefix_1),
168                &public,
169                &proof,
170            ) {
171                assert_eq!(challenge_prefix, challenge_prefix_1);
172            }
173        }
174    }
175
176    #[test]
177    pub fn test_ed25519_dlog_proof_serialization() {
178        let mut csprng = thread_rng();
179        for _ in 0..10000 {
180            let signing = SigningKey::generate(&mut csprng);
181            let secret = signing.to_bytes();
182            let signing = SigningKey::from_bytes(&secret);
183            let public = signing.verifying_key();
184            let challenge_prefix = generate_challenge_prefix(&mut csprng);
185            let proof = prove_dlog_ed25519(
186                &mut csprng,
187                &mut RandomOracle::domain(&challenge_prefix),
188                &public,
189                &secret,
190            );
191            let proof_des = serialize_deserialize(&proof);
192            assert_eq!(proof, proof_des.expect("Proof did not deserialize."));
193        }
194    }
195}
concordium_base/eddsa_ed25519/dlog_ed25519.rs

concordium_base/eddsa_ed25519/
dlog_ed25519.rs
