bitcoin/util/
misc.rs

1// Rust Bitcoin Library
2// Written in 2014 by
3//     Andrew Poelstra <apoelstra@wpsoftware.net>
4//
5// To the extent possible under law, the author(s) have dedicated all
6// copyright and related and neighboring rights to this software to
7// the public domain worldwide. This software is distributed without
8// any warranty.
9//
10// You should have received a copy of the CC0 Public Domain Dedication
11// along with this software.
12// If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
13//
14
15//! Miscellaneous functions
16//!
17//! Various utility functions
18
19use hashes::{sha256d, Hash, HashEngine};
20
21use blockdata::opcodes;
22use consensus::{encode, Encodable};
23
24#[cfg(feature = "secp-recovery")]
25pub use self::message_signing::{MessageSignature, MessageSignatureError};
26
27/// The prefix for signed messages using Bitcoin's message signing protocol.
28pub const BITCOIN_SIGNED_MSG_PREFIX: &[u8] = b"\x18Bitcoin Signed Message:\n";
29
30#[cfg(feature = "secp-recovery")]
31mod message_signing {
32    use std::{error, fmt};
33
34    use hashes::sha256d;
35    use secp256k1;
36    use secp256k1::{RecoveryId, RecoverableSignature};
37
38    use util::key::PublicKey;
39    use util::address::{Address, AddressType};
40
41    /// An error used for dealing with Bitcoin Signed Messages.
42    #[derive(Debug, PartialEq, Eq)]
43    pub enum MessageSignatureError {
44        /// Signature is expected to be 65 bytes.
45        InvalidLength,
46        /// The signature is invalidly constructed.
47        InvalidEncoding(secp256k1::Error),
48        /// Invalid base64 encoding.
49        InvalidBase64,
50    }
51
52    impl fmt::Display for MessageSignatureError {
53        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
54            match *self {
55                MessageSignatureError::InvalidLength => write!(f, "length not 65 bytes"),
56                MessageSignatureError::InvalidEncoding(ref e) => write!(f, "invalid encoding: {}", e),
57                MessageSignatureError::InvalidBase64 => write!(f, "invalid base64"),
58            }
59        }
60    }
61
62    impl error::Error for MessageSignatureError {
63        fn cause(&self) -> Option<&dyn error::Error> {
64            match *self {
65                MessageSignatureError::InvalidEncoding(ref e) => Some(e),
66                _ => None,
67            }
68        }
69    }
70
71    #[doc(hidden)]
72    impl From<secp256k1::Error> for MessageSignatureError {
73        fn from(e: secp256k1::Error) -> MessageSignatureError {
74            MessageSignatureError::InvalidEncoding(e)
75        }
76    }
77
78    /// A signature on a Bitcoin Signed Message.
79    ///
80    /// In order to use the `to_base64` and `from_base64` methods, as well as the
81    /// `fmt::Display` and `str::FromStr` implementations, the `base64` feature
82    /// must be enabled.
83    #[derive(Copy, Clone, PartialEq, Eq, Debug)]
84    pub struct MessageSignature {
85        /// The inner recoverable signature.
86        pub signature: RecoverableSignature,
87        /// Whether or not this signature was created with a compressed key.
88        pub compressed: bool,
89    }
90
91    impl MessageSignature {
92        /// Create a new [MessageSignature].
93        pub fn new(signature: RecoverableSignature, compressed: bool) -> MessageSignature {
94            MessageSignature {
95                signature: signature,
96                compressed: compressed,
97            }
98        }
99
100        /// Serialize to bytes.
101        pub fn serialize(&self) -> [u8; 65] {
102            let (recid, raw) = self.signature.serialize_compact();
103            let mut serialized = [0u8; 65];
104            serialized[0] = 27;
105            serialized[0] += recid.to_i32() as u8;
106            if self.compressed {
107                serialized[0] += 4;
108            }
109            serialized[1..].copy_from_slice(&raw[..]);
110            serialized
111        }
112
113        /// Create from a byte slice.
114        pub fn from_slice(bytes: &[u8]) -> Result<MessageSignature, MessageSignatureError> {
115            if bytes.len() != 65 {
116                return Err(MessageSignatureError::InvalidLength);
117            }
118            // We just check this here so we can safely subtract further.
119            if bytes[0] < 27 {
120                return Err(MessageSignatureError::InvalidEncoding(secp256k1::Error::InvalidRecoveryId));
121            };
122            let recid = RecoveryId::from_i32(((bytes[0] - 27) & 0x03) as i32)?;
123            Ok(MessageSignature {
124                signature: RecoverableSignature::from_compact(&bytes[1..], recid)?,
125                compressed: ((bytes[0] - 27) & 0x04) != 0,
126            })
127        }
128
129        /// Attempt to recover a public key from the signature and the signed message.
130        ///
131        /// To get the message hash from a message, use [signed_msg_hash].
132        pub fn recover_pubkey(
133            &self,
134            secp_ctx: &secp256k1::Secp256k1,
135            msg_hash: sha256d::Hash
136        ) -> Result<PublicKey, secp256k1::Error> {
137            let msg = secp256k1::Message::from_slice(&msg_hash[..])?;
138            let pubkey = secp_ctx.recover(&msg, &self.signature)?;
139            Ok(PublicKey {
140                key: pubkey,
141                compressed: self.compressed,
142            })
143        }
144
145        /// Verify that the signature signs the message and was signed by the given address.
146        ///
147        /// To get the message hash from a message, use [signed_msg_hash].
148        pub fn is_signed_by_address(
149            &self,
150            secp_ctx: &secp256k1::Secp256k1,
151            address: &Address,
152            msg_hash: sha256d::Hash
153        ) -> Result<bool, secp256k1::Error> {
154            let pubkey = self.recover_pubkey(&secp_ctx, msg_hash)?;
155            Ok(match address.address_type() {
156                Some(AddressType::P2pkh) => {
157                    *address == Address::p2pkh(&pubkey, address.network)
158                }
159                Some(AddressType::P2sh) => false,
160                Some(AddressType::P2wpkh) => false,
161                Some(AddressType::P2wsh) => false,
162                None => false,
163            })
164        }
165
166        #[cfg(feature = "base64")]
167        /// Convert a signature from base64 encoding.
168        pub fn from_base64(s: &str) -> Result<MessageSignature, MessageSignatureError> {
169            let bytes = ::base64::decode(s).map_err(|_| MessageSignatureError::InvalidBase64)?;
170            MessageSignature::from_slice(&bytes)
171        }
172
173        #[cfg(feature = "base64")]
174        /// Convert to base64 encoding.
175        pub fn to_base64(&self) -> String {
176            ::base64::encode(&self.serialize()[..])
177        }
178    }
179
180    #[cfg(feature = "base64")]
181    impl fmt::Display for MessageSignature {
182        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
183            let bytes = self.serialize();
184            // This avoids the allocation of a String.
185            write!(f, "{}", ::base64::display::Base64Display::with_config(
186                    &bytes[..], ::base64::STANDARD))
187        }
188    }
189
190    #[cfg(feature = "base64")]
191    impl ::std::str::FromStr for MessageSignature {
192        type Err = MessageSignatureError;
193        fn from_str(s: &str) -> Result<MessageSignature, MessageSignatureError> {
194            MessageSignature::from_base64(s)
195        }
196    }
197}
198
199/// Search for `needle` in the vector `haystack` and remove every
200/// instance of it, returning the number of instances removed.
201/// Loops through the vector opcode by opcode, skipping pushed data.
202pub fn script_find_and_remove(haystack: &mut Vec<u8>, needle: &[u8]) -> usize {
203    if needle.len() > haystack.len() { return 0; }
204    if needle.is_empty() { return 0; }
205
206    let mut top = haystack.len() - needle.len();
207    let mut n_deleted = 0;
208
209    let mut i = 0;
210    while i <= top {
211        if &haystack[i..(i + needle.len())] == needle {
212            for j in i..top {
213                haystack.swap(j + needle.len(), j);
214            }
215            n_deleted += 1;
216            // This is ugly but prevents infinite loop in case of overflow
217            let overflow = top < needle.len();
218            top = top.wrapping_sub(needle.len());
219            if overflow { break; }
220        } else {
221            i += match opcodes::All::from((*haystack)[i]).classify() {
222                opcodes::Class::PushBytes(n) => n as usize + 1,
223                opcodes::Class::Ordinary(opcodes::Ordinary::OP_PUSHDATA1) => 2,
224                opcodes::Class::Ordinary(opcodes::Ordinary::OP_PUSHDATA2) => 3,
225                opcodes::Class::Ordinary(opcodes::Ordinary::OP_PUSHDATA4) => 5,
226                _ => 1
227            };
228        }
229    }
230    haystack.truncate(top.wrapping_add(needle.len()));
231    n_deleted
232}
233
234/// Hash message for signature using Bitcoin's message signing format.
235pub fn signed_msg_hash(msg: &str) -> sha256d::Hash {
236    let mut engine = sha256d::Hash::engine();
237    engine.input(BITCOIN_SIGNED_MSG_PREFIX);
238    let msg_len = encode::VarInt(msg.len() as u64);
239    msg_len.consensus_encode(&mut engine).unwrap();
240    engine.input(msg.as_bytes());
241    sha256d::Hash::from_engine(engine)
242}
243
244/// Helper function to convert hex nibble characters to their respective value
245#[inline]
246fn hex_val(c: u8) -> Result<u8, encode::Error> {
247    let res = match c {
248        b'0' ..= b'9' => c - '0' as u8,
249        b'a' ..= b'f' => c - 'a' as u8 + 10,
250        b'A' ..= b'F' => c - 'A' as u8 + 10,
251        _ => return Err(encode::Error::UnexpectedHexDigit(c as char)),
252    };
253    Ok(res)
254}
255
256/// Convert a hexadecimal-encoded string to its corresponding bytes
257pub fn hex_bytes(data: &str) -> Result<Vec<u8>, encode::Error> {
258    // This code is optimized to be as fast as possible without using unsafe or platform specific
259    // features. If you want to refactor it please make sure you don't introduce performance
260    // regressions (run the benchmark with `cargo bench --features unstable`).
261
262    // If the hex string has an uneven length fail early
263    if data.len() % 2 != 0 {
264        return Err(encode::Error::ParseFailed("hexstring of odd length"));
265    }
266
267    // Preallocate the uninitialized memory for the byte array
268    let mut res = Vec::with_capacity(data.len() / 2);
269
270    let mut hex_it = data.bytes();
271    loop {
272        // Get most significant nibble of current byte or end iteration
273        let msn = match hex_it.next() {
274            None => break,
275            Some(x) => x,
276        };
277
278        // Get least significant nibble of current byte
279        let lsn = match hex_it.next() {
280            None => unreachable!("len % 2 == 0"),
281            Some(x) => x,
282        };
283
284        // Convert bytes representing characters to their represented value and combine lsn and msn.
285        // The and_then and map are crucial for performance, in comparison to using ? and then
286        // using the results of that for the calculation it's nearly twice as fast. Using bit
287        // shifting and or instead of multiply and add on the other hand doesn't show a significant
288        // increase in performance.
289        match hex_val(msn).and_then(|msn_val| hex_val(lsn).map(|lsn_val| msn_val * 16 + lsn_val)) {
290            Ok(x) => res.push(x),
291            Err(e) => return Err(e),
292        }
293    }
294    Ok(res)
295}
296
297#[cfg(test)]
298mod tests {
299    use hashes::hex::ToHex;
300    use super::script_find_and_remove;
301    use super::signed_msg_hash;
302
303    #[test]
304    fn test_script_find_and_remove() {
305        let mut v = vec![101u8, 102, 103, 104, 102, 103, 104, 102, 103, 104, 105, 106, 107, 108, 109];
306
307        assert_eq!(script_find_and_remove(&mut v, &[]), 0);
308        assert_eq!(script_find_and_remove(&mut v, &[105, 105, 105]), 0);
309        assert_eq!(v, vec![101, 102, 103, 104, 102, 103, 104, 102, 103, 104, 105, 106, 107, 108, 109]);
310
311        assert_eq!(script_find_and_remove(&mut v, &[105, 106, 107]), 1);
312        assert_eq!(v, vec![101, 102, 103, 104, 102, 103, 104, 102, 103, 104, 108, 109]);
313
314        assert_eq!(script_find_and_remove(&mut v, &[104, 108, 109]), 1);
315        assert_eq!(v, vec![101, 102, 103, 104, 102, 103, 104, 102, 103]);
316
317        assert_eq!(script_find_and_remove(&mut v, &[101]), 1);
318        assert_eq!(v, vec![102, 103, 104, 102, 103, 104, 102, 103]);
319
320        assert_eq!(script_find_and_remove(&mut v, &[102]), 3);
321        assert_eq!(v, vec![103, 104, 103, 104, 103]);
322
323        assert_eq!(script_find_and_remove(&mut v, &[103, 104]), 2);
324        assert_eq!(v, vec![103]);
325
326        assert_eq!(script_find_and_remove(&mut v, &[105, 105, 5]), 0);
327        assert_eq!(script_find_and_remove(&mut v, &[105]), 0);
328        assert_eq!(script_find_and_remove(&mut v, &[103]), 1);
329        assert_eq!(v, Vec::<u8>::new());
330
331        assert_eq!(script_find_and_remove(&mut v, &[105, 105, 5]), 0);
332        assert_eq!(script_find_and_remove(&mut v, &[105]), 0);
333    }
334
335    #[test]
336    fn test_script_codesep_remove() {
337        let mut s = vec![33u8, 3, 132, 121, 160, 250, 153, 140, 211, 82, 89, 162, 239, 10, 122, 92, 104, 102, 44, 20, 116, 248, 140, 203, 109, 8, 167, 103, 123, 190, 199, 242, 32, 65, 173, 171, 33, 3, 132, 121, 160, 250, 153, 140, 211, 82, 89, 162, 239, 10, 122, 92, 104, 102, 44, 20, 116, 248, 140, 203, 109, 8, 167, 103, 123, 190, 199, 242, 32, 65, 173, 171, 81];
338        assert_eq!(script_find_and_remove(&mut s, &[171]), 2);
339        assert_eq!(s, vec![33, 3, 132, 121, 160, 250, 153, 140, 211, 82, 89, 162, 239, 10, 122, 92, 104, 102, 44, 20, 116, 248, 140, 203, 109, 8, 167, 103, 123, 190, 199, 242, 32, 65, 173, 33, 3, 132, 121, 160, 250, 153, 140, 211, 82, 89, 162, 239, 10, 122, 92, 104, 102, 44, 20, 116, 248, 140, 203, 109, 8, 167, 103, 123, 190, 199, 242, 32, 65, 173, 81]);
340    }
341
342    #[test]
343    fn test_signed_msg_hash() {
344        let hash = signed_msg_hash("test");
345        assert_eq!(hash.to_hex(), "a6f87fe6d58a032c320ff8d1541656f0282c2c7bfcc69d61af4c8e8ed528e49c");
346    }
347
348    #[test]
349    #[cfg(all(feature = "secp-recovery", feature = "base64"))]
350    fn test_message_signature() {
351        use std::str::FromStr;
352        use secp256k1;
353
354        let secp = secp256k1::Secp256k1::new();
355        let message = "rust-bitcoin MessageSignature test";
356        let msg_hash = super::signed_msg_hash(&message);
357        let msg = secp256k1::Message::from_slice(&msg_hash).unwrap();
358
359        let privkey = secp256k1::SecretKey::new(&mut secp256k1::rand::thread_rng());
360        let secp_sig = secp.sign_recoverable(&msg, &privkey);
361        let signature = super::MessageSignature {
362            signature: secp_sig,
363            compressed: true,
364        };
365
366        assert_eq!(signature.to_base64(), signature.to_string());
367        let signature2 = super::MessageSignature::from_str(&signature.to_string()).unwrap();
368        let pubkey = signature2.recover_pubkey(&secp, msg_hash).unwrap();
369        assert_eq!(pubkey.compressed, true);
370        assert_eq!(pubkey.key, secp256k1::PublicKey::from_secret_key(&secp, &privkey));
371
372        let p2pkh = ::Address::p2pkh(&pubkey, ::Network::Bitcoin);
373        assert_eq!(signature2.is_signed_by_address(&secp, &p2pkh, msg_hash), Ok(true));
374        let p2wpkh = ::Address::p2wpkh(&pubkey, ::Network::Bitcoin).unwrap();
375        assert_eq!(signature2.is_signed_by_address(&secp, &p2wpkh, msg_hash), Ok(false));
376        let p2shwpkh = ::Address::p2shwpkh(&pubkey, ::Network::Bitcoin).unwrap();
377        assert_eq!(signature2.is_signed_by_address(&secp, &p2shwpkh, msg_hash), Ok(false));
378    }
379}
380
bitcoin/util/misc.rs

bitcoin/util/
misc.rs
