hash_based_signatures/signature/
stateless_merkle.rs

1use crate::signature::q_indexed_signature::{QIndexedSignature, QIndexedSignatureScheme};
2use crate::signature::winternitz::d::D;
3use crate::signature::{HashType, SignatureScheme};
4use crate::utils::{hash, hmac, string_to_hash};
5use anyhow::Result;
6use data_encoding::HEXLOWER;
7use rand::Rng;
8use rand_chacha::rand_core::SeedableRng;
9use rand_chacha::ChaCha20Rng;
10use serde::{Deserialize, Serialize};
11use std::fmt::{Debug, Formatter};
12
13#[derive(Serialize, Deserialize)]
14pub struct StatelessMerklePrivateKey {
15    pub seed_hex: String,
16    pub width: usize,
17    pub depth: usize,
18    pub d: u64,
19    // This can be derived from the seed, but might be useful for someone who inspects the JSON
20    pub public_key: String,
21}
22
23/// Stateless Merkle signatures, as described in Section 14.6.3
24/// in the [textbook](http://toc.cryptobook.us/) by Boneh & Shoup.
25///
26/// Builds a tree of depth `depth` and width `q`. For each signature,
27/// a pseudo-random path is selected.
28/// Then, the signature contains a series of q-indexed signatures,
29/// each signing the public key of the next one. The leaf node signs
30/// the hash of the message.
31///
32/// # Examples
33///
34/// ```
35/// use hash_based_signatures::signature::stateless_merkle::StatelessMerkleSignatureScheme;
36/// use hash_based_signatures::signature::SignatureScheme;
37/// use hash_based_signatures::signature::winternitz::d::D;
38///
39/// let mut signature_scheme = StatelessMerkleSignatureScheme::new([0; 32], 16, 5, D::new(255));
40/// let signature0 = signature_scheme.sign([0u8; 32]);
41/// let signature1 = signature_scheme.sign([1u8; 32]);
42///
43/// assert!(StatelessMerkleSignatureScheme::verify(
44///     signature_scheme.public_key(),
45///     [0u8; 32],
46///     &signature0
47/// ));
48/// assert!(StatelessMerkleSignatureScheme::verify(
49///     signature_scheme.public_key(),
50///     [1u8; 32],
51///     &signature1
52/// ));
53/// assert!(!StatelessMerkleSignatureScheme::verify(
54///     signature_scheme.public_key(),
55///     [2u8; 32],
56///     &signature1
57/// ));
58/// ```
59pub struct StatelessMerkleSignatureScheme {
60    seed: HashType,
61    seed_prf_key: HashType,
62    path_prf_key: HashType,
63    root_signature: QIndexedSignatureScheme,
64    q: usize,
65    depth: usize,
66    d: D,
67}
68
69#[derive(PartialEq, Serialize, Deserialize)]
70pub struct StatelessMerkleSignature {
71    public_key_signatures: Vec<(HashType, QIndexedSignature)>,
72    message_signature: QIndexedSignature,
73}
74
75impl Debug for StatelessMerkleSignature {
76    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
77        let mut result = String::from("Stateless signature:\n");
78        for (message, signature) in &self.public_key_signatures {
79            result += &format!(
80                "- ({}, {})\n",
81                signature.proof.index,
82                HEXLOWER.encode(message)
83            );
84        }
85        result += &format!(
86            "- ({}, <hashed message>)\n",
87            self.message_signature.proof.index,
88        );
89        write!(f, "{}", result)
90    }
91}
92
93impl StatelessMerkleSignatureScheme {
94    /// Instantiates the new stateless Merkle signature scheme as a tree with width `q` and depth `depth`.
95    ///
96    /// The resulting tree will have `q**depth` leafs. Because the scheme is broken if the same leaf is
97    /// chosen for two different messages, the expected number of signed messages should not exceed
98    /// `sqrt(q**depth)`.
99    ///
100    /// # Panics
101    ///
102    /// Panics if `q` is not a power of two.
103    pub fn new(seed: HashType, q: usize, depth: usize, d: D) -> Self {
104        // Derive keys by using HMAC as a PRF
105        let root_seed = hmac(&seed, &[0]);
106        let seed_prf_key = hmac(&seed, &[1]);
107        let path_prf_key = hmac(&seed, &[2]);
108        Self {
109            seed,
110            root_signature: QIndexedSignatureScheme::new(q, root_seed, d),
111            seed_prf_key,
112            path_prf_key,
113            q,
114            depth,
115            d,
116        }
117    }
118
119    pub fn from_private_key(key: &StatelessMerklePrivateKey) -> Result<Self> {
120        Ok(Self::new(
121            string_to_hash(&key.seed_hex),
122            key.width,
123            key.depth,
124            D::try_from(key.d)?,
125        ))
126    }
127
128    pub fn private_key(&self) -> StatelessMerklePrivateKey {
129        StatelessMerklePrivateKey {
130            seed_hex: HEXLOWER.encode(&self.seed),
131            public_key: HEXLOWER.encode(&self.public_key()),
132            width: self.q,
133            depth: self.depth,
134            d: self.d.d,
135        }
136    }
137
138    fn signature_scheme(&self, path: &[usize]) -> QIndexedSignatureScheme {
139        if path.len() == 0 {
140            self.root_signature.clone()
141        } else {
142            let path_bytes: Vec<u8> = path.iter().map(|x| x.to_be_bytes()).flatten().collect();
143            let seed = hmac(&self.seed_prf_key, &path_bytes);
144            QIndexedSignatureScheme::new(self.q, seed, self.d)
145        }
146    }
147}
148
149impl SignatureScheme<HashType, HashType, StatelessMerkleSignature>
150    for StatelessMerkleSignatureScheme
151{
152    fn public_key(&self) -> HashType {
153        self.root_signature.public_key()
154    }
155
156    fn sign(&mut self, message: HashType) -> StatelessMerkleSignature {
157        // Generate pseudo-random path, using hmac(path_prf_key, message) as the seed
158        let mut rng = ChaCha20Rng::from_seed(hmac(&self.path_prf_key, &message));
159        let path: Vec<usize> = (0..self.depth).map(|_| rng.gen_range(0..self.q)).collect();
160
161        let mut public_key_signatures = Vec::with_capacity(self.depth);
162        let mut current_signing_scheme = self.root_signature.clone();
163        for (path_index, signature_index) in path.iter().enumerate() {
164            // Internal node, instantiate next indexed signature and sign its public key
165            let next_signature_scheme = self.signature_scheme(&path[..path_index + 1]);
166            let one_time_signature =
167                current_signing_scheme.sign((*signature_index, next_signature_scheme.public_key()));
168
169            public_key_signatures.push((next_signature_scheme.public_key(), one_time_signature));
170            current_signing_scheme = next_signature_scheme;
171        }
172
173        // Even though the message might be a hash already, hash it again to prevent extension attacks:
174        // Otherwise an adversary could create his own q-indexed public key, trick the signer to
175        // sign it and then extend the signature to sign arbitrary messages.
176        let hashed_message = hash(&message);
177
178        // Leaf node, sign message
179        let message_signature =
180            current_signing_scheme.sign((*path.last().unwrap(), hashed_message));
181
182        StatelessMerkleSignature {
183            public_key_signatures,
184            message_signature,
185        }
186    }
187
188    fn verify(pk: HashType, message: HashType, signature: &StatelessMerkleSignature) -> bool {
189        let mut current_public_key = pk;
190
191        // Verify public keys along path
192        for (public_key, one_time_signature) in &signature.public_key_signatures {
193            if !QIndexedSignatureScheme::verify(
194                current_public_key,
195                (one_time_signature.proof.index, *public_key),
196                one_time_signature,
197            ) {
198                return false;
199            }
200            current_public_key = *public_key;
201        }
202
203        // Verify message signature
204        QIndexedSignatureScheme::verify(
205            current_public_key,
206            (signature.message_signature.proof.index, hash(&message)),
207            &signature.message_signature,
208        )
209    }
210}
211
212#[cfg(test)]
213mod tests {
214    use crate::signature::stateless_merkle::StatelessMerkleSignatureScheme;
215    use crate::signature::winternitz::d::D;
216    use crate::signature::SignatureScheme;
217
218    fn get_signature_scheme() -> StatelessMerkleSignatureScheme {
219        let seed = [0u8; 32];
220        StatelessMerkleSignatureScheme::new(seed, 16, 5, D::new(255))
221    }
222
223    #[test]
224    fn test_correct_signature() {
225        let mut signature_scheme = get_signature_scheme();
226        let signature = signature_scheme.sign([1u8; 32]);
227        assert!(StatelessMerkleSignatureScheme::verify(
228            signature_scheme.public_key(),
229            [1u8; 32],
230            &signature
231        ))
232    }
233
234    #[test]
235    fn is_deterministic() {
236        let mut signature_scheme = get_signature_scheme();
237        let signature1 = signature_scheme.sign([1u8; 32]);
238        let signature2 = signature_scheme.sign([1u8; 32]);
239        assert_eq!(signature1, signature2)
240    }
241
242    #[test]
243    fn test_incorrect_signature() {
244        let mut signature_scheme = get_signature_scheme();
245        let signature = signature_scheme.sign([1u8; 32]);
246        assert!(!StatelessMerkleSignatureScheme::verify(
247            signature_scheme.public_key(),
248            [2u8; 32],
249            &signature
250        ))
251    }
252}
hash_based_signatures/signature/stateless_merkle.rs

hash_based_signatures/signature/
stateless_merkle.rs
