bitcoin/util/
contracthash.rs

1// Rust Bitcoin Library
2// Written in 2015 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//! Pay-to-contract-hash support
16//!
17//! See Appendix A of the Blockstream sidechains whitepaper
18//! at http://blockstream.com/sidechains.pdf for details of
19//! what this does.
20
21use secp256k1::{self, Secp256k1};
22use secp256k1::key::{PublicKey, SecretKey};
23use bitcoin_hashes::{hash160, sha256, Hash, HashEngine, Hmac, HmacEngine};
24use blockdata::{opcodes, script};
25
26use std::{error, fmt};
27
28use network::constants::Network;
29use util::address;
30
31/// Encoding of "pubkey here" in script; from Bitcoin Core `src/script/script.h`
32static PUBKEY: u8 = 0xFE;
33
34/// A contract-hash error
35#[derive(Debug, PartialEq, Eq, Clone)]
36pub enum Error {
37    /// Contract hashed to an out-of-range value (this is basically impossible
38    /// and much more likely suggests memory corruption or hardware failure)
39    BadTweak(secp256k1::Error),
40    /// Other secp256k1 related error
41    Secp(secp256k1::Error),
42    /// Script parsing error
43    Script(script::Error),
44    /// Encountered an uncompressed key in a script we were deserializing. The
45    /// reserialization will compress it which might be surprising so we call
46    /// this an error.
47    UncompressedKey,
48    /// Expected a public key when deserializing a script, but we got something else.
49    ExpectedKey,
50    /// Expected some sort of CHECKSIG operator when deserializing a script, but
51    /// we got something else.
52    ExpectedChecksig,
53    /// Did not have enough keys to instantiate a script template
54    TooFewKeys(usize),
55    /// Had too many keys; template does not match key list
56    TooManyKeys(usize)
57}
58
59impl fmt::Display for Error {
60    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
61        match *self {
62            Error::BadTweak(ref e) |
63            Error::Secp(ref e) => fmt::Display::fmt(&e, f),
64            Error::Script(ref e) => fmt::Display::fmt(&e, f),
65            Error::UncompressedKey => f.write_str("encountered uncompressed secp public key"),
66            Error::ExpectedKey => f.write_str("expected key when deserializing script"),
67            Error::ExpectedChecksig => f.write_str("expected OP_*CHECKSIG* when deserializing script"),
68            Error::TooFewKeys(n) => write!(f, "got {} keys, which was not enough", n),
69            Error::TooManyKeys(n) => write!(f, "got {} keys, which was too many", n)
70        }
71    }
72}
73
74impl error::Error for Error {
75    fn cause(&self) -> Option<&error::Error> {
76        match *self {
77            Error::BadTweak(ref e) |
78            Error::Secp(ref e) => Some(e),
79            Error::Script(ref e) => Some(e),
80            _ => None
81        }
82    }
83
84    fn description(&self) -> &'static str {
85        match *self {
86            Error::BadTweak(_) => "bad public key tweak",
87            Error::Secp(_) => "libsecp256k1 error",
88            Error::Script(_) => "script error",
89            Error::UncompressedKey => "encountered uncompressed secp public key",
90            Error::ExpectedKey => "expected key when deserializing script",
91            Error::ExpectedChecksig => "expected OP_*CHECKSIG* when deserializing script",
92            Error::TooFewKeys(_) => "too few keys for template",
93            Error::TooManyKeys(_) => "too many keys for template"
94        }
95    }
96}
97
98/// An element of a script template
99#[derive(Copy, Clone, PartialEq, Eq, Debug)]
100enum TemplateElement {
101    Op(opcodes::All),
102    Key
103}
104
105/// A script template
106#[derive(Clone, PartialEq, Eq, Debug)]
107pub struct Template(Vec<TemplateElement>);
108
109impl Template {
110    /// Instantiate a template
111    pub fn to_script(&self, keys: &[PublicKey]) -> Result<script::Script, Error> {
112        let mut key_index = 0;
113        let mut ret = script::Builder::new();
114        for elem in &self.0 {
115            ret = match *elem {
116                TemplateElement::Op(opcode) => ret.push_opcode(opcode),
117                TemplateElement::Key => {
118                    if key_index == keys.len() {
119                        return Err(Error::TooFewKeys(key_index));
120                    }
121                    key_index += 1;
122                    ret.push_slice(&keys[key_index - 1].serialize()[..])
123                }
124            }
125        }
126        if key_index == keys.len() {
127            Ok(ret.into_script())
128        } else {
129            Err(Error::TooManyKeys(keys.len()))
130        }
131    }
132
133    /// Returns the number of keys this template requires to instantiate
134    pub fn required_keys(&self) -> usize {
135        self.0.iter().filter(|e| **e == TemplateElement::Key).count()
136    }
137
138    /// If the first push in the template is a number, return this number. For the
139    /// common case of standard multisig templates, such a number will exist and
140    /// will represent the number of signatures that are required for the script
141    /// to pass.
142    pub fn first_push_as_number(&self) -> Option<usize> {
143        if !self.0.is_empty() {
144            if let TemplateElement::Op(op) = self.0[0] {
145                if let opcodes::Class::PushNum(n) = op.classify() {
146                    if n >= 0 {
147                        return Some(n as usize);
148                    }
149                }
150            }
151        }
152        None
153    }
154}
155
156impl<'a> From<&'a [u8]> for Template {
157    fn from(slice: &'a [u8]) -> Template {
158        Template(slice.iter().map(|&byte| {
159            if byte == PUBKEY {
160                TemplateElement::Key
161            } else {
162                TemplateElement::Op(opcodes::All::from(byte))
163            }
164        }).collect())
165    }
166}
167
168/// Tweak keys using some arbitrary data
169pub fn tweak_keys<C: secp256k1::Verification>(secp: &Secp256k1<C>, keys: &[PublicKey], contract: &[u8]) -> Result<Vec<PublicKey>, Error> {
170    let mut ret = Vec::with_capacity(keys.len());
171    for mut key in keys.iter().cloned() {
172        let mut hmac_engine: HmacEngine<sha256::Hash> = HmacEngine::new(&key.serialize());
173        hmac_engine.input(contract);
174        let hmac_result: Hmac<sha256::Hash> = Hmac::from_engine(hmac_engine);
175        let hmac_sk = SecretKey::from_slice(&hmac_result[..]).map_err(Error::BadTweak)?;
176        key.add_exp_assign(secp, &hmac_sk[..]).map_err(Error::Secp)?;
177        ret.push(key);
178    }
179    Ok(ret)
180}
181
182/// Compute a tweak from some given data for the given public key
183pub fn compute_tweak(pk: &PublicKey, contract: &[u8]) -> Result<SecretKey, Error> {
184    let mut hmac_engine: HmacEngine<sha256::Hash> = HmacEngine::new(&pk.serialize());
185    hmac_engine.input(contract);
186    let hmac_result: Hmac<sha256::Hash> = Hmac::from_engine(hmac_engine);
187    SecretKey::from_slice(&hmac_result[..]).map_err(Error::BadTweak)
188}
189
190/// Tweak a secret key using some arbitrary data (calls `compute_tweak` internally)
191pub fn tweak_secret_key<C: secp256k1::Signing>(secp: &Secp256k1<C>, key: &SecretKey, contract: &[u8]) -> Result<SecretKey, Error> {
192    // Compute public key
193    let pk = PublicKey::from_secret_key(secp, &key);
194    // Compute tweak
195    let hmac_sk = compute_tweak(&pk, contract)?;
196    // Execute the tweak
197    let mut key = *key;
198    key.add_assign(&hmac_sk[..]).map_err(Error::Secp)?;
199    // Return
200    Ok(key)
201}
202
203/// Takes a contract, template and key set and runs through all the steps
204pub fn create_address<C: secp256k1::Verification>(secp: &Secp256k1<C>,
205                      network: Network,
206                      contract: &[u8],
207                      keys: &[PublicKey],
208                      template: &Template)
209                      -> Result<address::Address, Error> {
210    let keys = tweak_keys(secp, keys, contract)?;
211    let script = template.to_script(&keys)?;
212    Ok(address::Address {
213        network: network,
214        payload: address::Payload::ScriptHash(
215            hash160::Hash::hash(&script[..])
216        )
217    })
218}
219
220/// Extract the keys and template from a completed script
221pub fn untemplate(script: &script::Script) -> Result<(Template, Vec<PublicKey>), Error> {
222    let mut ret = script::Builder::new();
223    let mut retkeys = vec![];
224
225    #[derive(Copy, Clone, PartialEq, Eq)]
226    enum Mode {
227        SeekingKeys,
228        CopyingKeys,
229        SeekingCheckMulti
230    }
231
232    let mut mode = Mode::SeekingKeys;
233    for instruction in script.iter(false) {
234        match instruction {
235            script::Instruction::PushBytes(data) => {
236                let n = data.len();
237                ret = match PublicKey::from_slice(data) {
238                    Ok(key) => {
239                        if n == 65 { return Err(Error::UncompressedKey); }
240                        if mode == Mode::SeekingCheckMulti { return Err(Error::ExpectedChecksig); }
241                        retkeys.push(key);
242                        mode = Mode::CopyingKeys;
243                        ret.push_opcode(opcodes::All::from(PUBKEY))
244                    }
245                    Err(_) => {
246                        // Arbitrary pushes are only allowed before we've found any keys.
247                        // Otherwise we have to wait for a N CHECKSIG pair.
248                        match mode {
249                            Mode::SeekingKeys => { ret.push_slice(data) }
250                            Mode::CopyingKeys => { return Err(Error::ExpectedKey); },
251                            Mode::SeekingCheckMulti => { return Err(Error::ExpectedChecksig); }
252                        }
253                    }
254                }
255            }
256            script::Instruction::Op(op) => {
257                match op.classify() {
258                    // CHECKSIG should only come after a list of keys
259                    opcodes::Class::Ordinary(opcodes::Ordinary::OP_CHECKSIG) |
260                    opcodes::Class::Ordinary(opcodes::Ordinary::OP_CHECKSIGVERIFY) => {
261                        if mode == Mode::SeekingKeys { return Err(Error::ExpectedKey); }
262                        mode = Mode::SeekingKeys;
263                    }
264                    // CHECKMULTISIG should only come after a number
265                    opcodes::Class::Ordinary(opcodes::Ordinary::OP_CHECKMULTISIG) |
266                    opcodes::Class::Ordinary(opcodes::Ordinary::OP_CHECKMULTISIGVERIFY) => {
267                        if mode == Mode::SeekingKeys { return Err(Error::ExpectedKey); }
268                        if mode == Mode::CopyingKeys { return Err(Error::ExpectedKey); }
269                        mode = Mode::SeekingKeys;
270                    }
271                    // Numbers after keys mean we expect a CHECKMULTISIG.
272                    opcodes::Class::PushNum(_) => {
273                        if mode == Mode::SeekingCheckMulti { return Err(Error::ExpectedChecksig); }
274                        if mode == Mode::CopyingKeys { mode = Mode::SeekingCheckMulti; }
275                    }
276                    // All other opcodes do nothing
277                    _ => {}
278                }
279                ret = ret.push_opcode(op);
280            }
281            script::Instruction::Error(e) => { return Err(Error::Script(e)); }
282        }
283    }
284    Ok((Template::from(&ret[..]), retkeys))
285}
286
287#[cfg(test)]
288mod tests {
289    use secp256k1::Secp256k1;
290    use secp256k1::key::PublicKey;
291    use hex::decode as hex_decode;
292    use rand::thread_rng;
293
294    use blockdata::script::Script;
295    use network::constants::Network;
296
297    use super::*;
298
299    macro_rules! hex (($hex:expr) => (hex_decode($hex).unwrap()));
300    macro_rules! hex_key (($hex:expr) => (PublicKey::from_slice(&hex!($hex)).unwrap()));
301    macro_rules! alpha_template(() => (Template::from(&hex!("55fefefefefefefe57AE")[..])));
302    macro_rules! alpha_keys(() => (
303        &[hex_key!("0269992fb441ae56968e5b77d46a3e53b69f136444ae65a94041fc937bdb28d933"),
304          hex_key!("021df31471281d4478df85bfce08a10aab82601dca949a79950f8ddf7002bd915a"),
305          hex_key!("02174c82021492c2c6dfcbfa4187d10d38bed06afb7fdcd72c880179fddd641ea1"),
306          hex_key!("033f96e43d72c33327b6a4631ccaa6ea07f0b106c88b9dc71c9000bb6044d5e88a"),
307          hex_key!("0313d8748790f2a86fb524579b46ce3c68fedd58d2a738716249a9f7d5458a15c2"),
308          hex_key!("030b632eeb079eb83648886122a04c7bf6d98ab5dfb94cf353ee3e9382a4c2fab0"),
309          hex_key!("02fb54a7fcaa73c307cfd70f3fa66a2e4247a71858ca731396343ad30c7c4009ce")]
310    ));
311
312    #[test]
313    fn sanity() {
314        let secp = Secp256k1::new();
315        let keys = alpha_keys!();
316        // This is the first withdraw ever, in alpha a94f95cc47b444c10449c0eed51d895e4970560c4a1a9d15d46124858abc3afe
317        let contract = hex!("5032534894ffbf32c1f1c0d3089b27c98fd991d5d7329ebd7d711223e2cde5a9417a1fa3e852c576");
318
319        let addr = create_address(&secp, Network::Testnet, &contract, keys, &alpha_template!()).unwrap();
320        assert_eq!(addr.to_string(), "2N3zXjbwdTcPsJiy8sUK9FhWJhqQCxA8Jjr".to_owned());
321    }
322
323    #[test]
324    fn script() {
325        let alpha_keys = alpha_keys!();
326        let alpha_template = alpha_template!();
327
328        let alpha_redeem = Script::from(hex!("55210269992fb441ae56968e5b77d46a3e53b69f136444ae65a94041fc937bdb28d93321021df31471281d4478df85bfce08a10aab82601dca949a79950f8ddf7002bd915a2102174c82021492c2c6dfcbfa4187d10d38bed06afb7fdcd72c880179fddd641ea121033f96e43d72c33327b6a4631ccaa6ea07f0b106c88b9dc71c9000bb6044d5e88a210313d8748790f2a86fb524579b46ce3c68fedd58d2a738716249a9f7d5458a15c221030b632eeb079eb83648886122a04c7bf6d98ab5dfb94cf353ee3e9382a4c2fab02102fb54a7fcaa73c307cfd70f3fa66a2e4247a71858ca731396343ad30c7c4009ce57ae"));
329        let (template, keys) = untemplate(&alpha_redeem).unwrap();
330
331        assert_eq!(keys, alpha_keys);
332        assert_eq!(template, alpha_template);
333    }
334
335    #[test]
336    fn tweak_secret() {
337        let secp = Secp256k1::new();
338        let (sk1, pk1) = secp.generate_keypair(&mut thread_rng());
339        let (sk2, pk2) = secp.generate_keypair(&mut thread_rng());
340        let (sk3, pk3) = secp.generate_keypair(&mut thread_rng());
341
342        let pks = [pk1, pk2, pk3];
343        let contract = b"if bottle mt dont remembr drink wont pay";
344
345        // Directly compute tweaks on pubkeys
346        let tweaked_pks = tweak_keys(&secp, &pks, &contract[..]).unwrap();
347        // Compute tweaks on secret keys
348        let tweaked_pk1 = PublicKey::from_secret_key(&secp, &tweak_secret_key(&secp, &sk1, &contract[..]).unwrap());
349        let tweaked_pk2 = PublicKey::from_secret_key(&secp, &tweak_secret_key(&secp, &sk2, &contract[..]).unwrap());
350        let tweaked_pk3 = PublicKey::from_secret_key(&secp, &tweak_secret_key(&secp, &sk3, &contract[..]).unwrap());
351        // Check equality
352        assert_eq!(tweaked_pks[0], tweaked_pk1);
353        assert_eq!(tweaked_pks[1], tweaked_pk2);
354        assert_eq!(tweaked_pks[2], tweaked_pk3);
355    }
356
357    #[test]
358    fn bad_key_number() {
359        let alpha_keys = alpha_keys!();
360        let template_short = Template::from(&hex!("55fefefefefefe57AE")[..]);
361        let template_long = Template::from(&hex!("55fefefefefefefefe57AE")[..]);
362        let template = Template::from(&hex!("55fefefefefefefe57AE")[..]);
363
364        assert_eq!(template_short.required_keys(), 6);
365        assert_eq!(template_long.required_keys(), 8);
366        assert_eq!(template.required_keys(), 7);
367        assert_eq!(template_short.to_script(alpha_keys), Err(Error::TooManyKeys(7)));
368        assert_eq!(template_long.to_script(alpha_keys), Err(Error::TooFewKeys(7)));
369        assert!(template.to_script(alpha_keys).is_ok());
370    }
371}
372
373
bitcoin/util/contracthash.rs

bitcoin/util/
contracthash.rs
