tari_script/
stack.rs

1// Copyright 2020. The Tari Project
2// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the
3// following conditions are met:
4// 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following
5// disclaimer.
6// 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the
7// following disclaimer in the documentation and/or other materials provided with the distribution.
8// 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote
9// products derived from this software without specific prior written permission.
10// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
11// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
12// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
13// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
14// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
15// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
16// USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
17
18use std::io;
19
20use borsh::{BorshDeserialize, BorshSerialize};
21use integer_encoding::{VarIntReader, VarIntWriter};
22use tari_crypto::{
23    compressed_commitment::CompressedCommitment,
24    compressed_key::CompressedKey,
25    ristretto::{RistrettoPublicKey, RistrettoSecretKey},
26};
27use tari_utilities::{
28    hex::{from_hex, to_hex, Hex, HexError},
29    ByteArray,
30};
31
32use crate::{
33    error::ScriptError,
34    op_codes::{HashValue, ScalarValue},
35    CheckSigSchnorrSignature,
36    CompressedCheckSigSchnorrSignature,
37};
38
39pub const MAX_STACK_SIZE: usize = 255;
40
41#[macro_export]
42macro_rules! inputs {
43    ($($input:expr),+) => {{
44        use $crate::{ExecutionStack, StackItem};
45
46        let items = vec![$(StackItem::from($input)),+];
47        ExecutionStack::new(items)
48    }}
49}
50
51macro_rules! stack_item_from {
52    ($from_type:ty => $variant:ident) => {
53        impl From<$from_type> for StackItem {
54            fn from(item: $from_type) -> Self {
55                StackItem::$variant(item)
56            }
57        }
58    };
59}
60
61pub const TYPE_NUMBER: u8 = 1;
62pub const TYPE_HASH: u8 = 2;
63pub const TYPE_COMMITMENT: u8 = 3;
64pub const TYPE_PUBKEY: u8 = 4;
65pub const TYPE_SIG: u8 = 5;
66pub const TYPE_SCALAR: u8 = 6;
67
68#[derive(Debug, Clone, PartialEq, Eq)]
69pub enum StackItem {
70    Number(i64),
71    Hash(HashValue),
72    Scalar(ScalarValue),
73    Commitment(CompressedCommitment<RistrettoPublicKey>),
74    PublicKey(CompressedKey<RistrettoPublicKey>),
75    Signature(CompressedCheckSigSchnorrSignature),
76}
77
78impl StackItem {
79    /// Convert an input item into its binary representation and append it to the array. The function returns the byte
80    /// slice that matches the item as a convenience
81    pub fn to_bytes<'a>(&self, array: &'a mut Vec<u8>) -> &'a [u8] {
82        let n = array.len();
83        match self {
84            StackItem::Number(v) => {
85                array.push(TYPE_NUMBER);
86                array.extend_from_slice(&v.to_le_bytes());
87            },
88            StackItem::Hash(h) => {
89                array.push(TYPE_HASH);
90                array.extend_from_slice(&h[..]);
91            },
92            StackItem::Commitment(c) => {
93                array.push(TYPE_COMMITMENT);
94                array.extend_from_slice(c.as_bytes());
95            },
96            StackItem::PublicKey(p) => {
97                array.push(TYPE_PUBKEY);
98                array.extend_from_slice(p.as_bytes());
99            },
100            StackItem::Signature(s) => {
101                array.push(TYPE_SIG);
102                array.extend_from_slice(s.get_compressed_public_nonce().as_bytes());
103                array.extend_from_slice(s.get_signature().as_bytes());
104            },
105            StackItem::Scalar(scalar) => {
106                array.push(TYPE_SCALAR);
107                array.extend_from_slice(scalar);
108            },
109        };
110        array.get(n..).expect("Length is always valid")
111    }
112
113    /// Take a byte slice and read the next stack item from it, including any associated data. `read_next` returns a
114    /// tuple of the deserialised item, and an updated slice that has the Opcode and data removed.
115    pub fn read_next(bytes: &[u8]) -> Option<(Self, &[u8])> {
116        let code = bytes.first()?;
117        let remaining = bytes.get(1..)?;
118        match *code {
119            TYPE_NUMBER => StackItem::b_to_number(remaining),
120            TYPE_HASH => StackItem::b_to_hash(remaining),
121            TYPE_COMMITMENT => StackItem::b_to_commitment(remaining),
122            TYPE_PUBKEY => StackItem::b_to_pubkey(remaining),
123            TYPE_SIG => StackItem::b_to_sig(remaining),
124            TYPE_SCALAR => StackItem::b_to_scalar(remaining),
125            _ => None,
126        }
127    }
128
129    fn b_to_number(b: &[u8]) -> Option<(Self, &[u8])> {
130        let mut arr = [0u8; 8];
131        arr.copy_from_slice(b.get(..8)?);
132        Some((StackItem::Number(i64::from_le_bytes(arr)), b.get(8..)?))
133    }
134
135    fn b_to_hash(b: &[u8]) -> Option<(Self, &[u8])> {
136        let mut arr = [0u8; 32];
137        arr.copy_from_slice(b.get(..32)?);
138        Some((StackItem::Hash(arr), b.get(32..)?))
139    }
140
141    fn b_to_scalar(b: &[u8]) -> Option<(Self, &[u8])> {
142        let mut arr = [0u8; 32];
143        arr.copy_from_slice(b.get(..32)?);
144        Some((StackItem::Scalar(arr), b.get(32..)?))
145    }
146
147    fn b_to_commitment(b: &[u8]) -> Option<(Self, &[u8])> {
148        let c = CompressedCommitment::from_canonical_bytes(b.get(..32)?).ok()?;
149        Some((StackItem::Commitment(c), b.get(32..)?))
150    }
151
152    fn b_to_pubkey(b: &[u8]) -> Option<(Self, &[u8])> {
153        let p = CompressedKey::from_canonical_bytes(b.get(..32)?).ok()?;
154        Some((StackItem::PublicKey(p), b.get(32..)?))
155    }
156
157    fn b_to_sig(b: &[u8]) -> Option<(Self, &[u8])> {
158        let r = RistrettoPublicKey::from_canonical_bytes(b.get(..32)?).ok()?;
159        let s = RistrettoSecretKey::from_canonical_bytes(b.get(32..64)?).ok()?;
160        let sig = CompressedCheckSigSchnorrSignature::new_from_schnorr(CheckSigSchnorrSignature::new(r, s));
161        Some((StackItem::Signature(sig), b.get(64..)?))
162    }
163}
164
165stack_item_from!(i64 => Number);
166stack_item_from!(CompressedCommitment<RistrettoPublicKey> => Commitment);
167stack_item_from!(CompressedKey<RistrettoPublicKey> => PublicKey);
168stack_item_from!(CompressedCheckSigSchnorrSignature => Signature);
169stack_item_from!(ScalarValue => Scalar);
170
171#[derive(Debug, Default, Clone, PartialEq, Eq)]
172pub struct ExecutionStack {
173    items: Vec<StackItem>,
174}
175
176impl BorshSerialize for ExecutionStack {
177    fn serialize<W: io::Write>(&self, writer: &mut W) -> io::Result<()> {
178        let bytes = self.to_bytes();
179        writer.write_varint(bytes.len())?;
180        for b in &bytes {
181            b.serialize(writer)?;
182        }
183        Ok(())
184    }
185}
186
187impl BorshDeserialize for ExecutionStack {
188    fn deserialize_reader<R>(reader: &mut R) -> Result<Self, io::Error>
189    where R: io::Read {
190        let len = reader.read_varint()?;
191        if len > MAX_STACK_SIZE {
192            return Err(io::Error::new(
193                io::ErrorKind::InvalidInput,
194                "Larger than max execution stack bytes".to_string(),
195            ));
196        }
197        let mut data = Vec::with_capacity(len);
198        for _ in 0..len {
199            data.push(u8::deserialize_reader(reader)?);
200        }
201        let stack = Self::from_bytes(data.as_slice())
202            .map_err(|e| io::Error::new(io::ErrorKind::InvalidInput, e.to_string()))?;
203        Ok(stack)
204    }
205}
206
207impl ExecutionStack {
208    /// Return a new `ExecutionStack` using the vector of [StackItem] in `items`
209    pub fn new(items: Vec<StackItem>) -> Self {
210        ExecutionStack { items }
211    }
212
213    /// Returns the number of entries in the execution stack
214    pub fn size(&self) -> usize {
215        self.items.len()
216    }
217
218    /// Returns a reference to the top entry in the stack without affecting the stack
219    pub fn peek(&self) -> Option<&StackItem> {
220        self.items.last()
221    }
222
223    /// Returns true if the stack is empty
224    pub fn is_empty(&self) -> bool {
225        self.items.is_empty()
226    }
227
228    /// Pops the top item in the stack. If the stack is not empty, `pop` returns the item, otherwise return `None` if
229    /// it is empty.
230    pub fn pop(&mut self) -> Option<StackItem> {
231        self.items.pop()
232    }
233
234    /// Pops the top item in the stack and applies TryFrom for the given generic type. If the stack is not empty, and is
235    /// a StackItem::Number, `pop_into_number` returns the parsed number. Returns an error if the stack is empty or if
236    /// the top item is a different variant.
237    pub fn pop_into_number<T: TryFrom<i64>>(&mut self) -> Result<T, ScriptError> {
238        let item = self.items.pop().ok_or(ScriptError::StackUnderflow)?;
239
240        let number = match item {
241            StackItem::Number(n) => T::try_from(n).map_err(|_| ScriptError::ValueExceedsBounds)?,
242            _ => return Err(ScriptError::InvalidInput),
243        };
244
245        Ok(number)
246    }
247
248    /// Pops n + 1 items from the stack. Checks if the last popped item matches any of the first n items. Returns an
249    /// error if all n + 1 items aren't of the same variant, or if there are not n + 1 items on the stack.
250    pub fn pop_n_plus_one_contains(&mut self, n: u8) -> Result<bool, ScriptError> {
251        let items = self.pop_num_items(n as usize)?;
252        let item = self.pop().ok_or(ScriptError::StackUnderflow)?;
253
254        // check that all popped items are of the same variant
255        // first count each variant
256        let counts = items.iter().fold([0; 6], counter);
257        // also check the n + 1 item
258        let counts = counter(counts, &item);
259
260        // then filter those with more than 0
261        let num_distinct_variants = counts.iter().filter(|&c| *c > 0).count();
262
263        if num_distinct_variants > 1 {
264            return Err(ScriptError::InvalidInput);
265        }
266
267        Ok(items.contains(&item))
268    }
269
270    /// Pops the top n items in the stack. If the stack has at least n items, `pop_num_items` returns the items in stack
271    /// order (ie. bottom first), otherwise returns an error.
272    pub fn pop_num_items(&mut self, num_items: usize) -> Result<Vec<StackItem>, ScriptError> {
273        let stack_size = self.size();
274
275        if stack_size < num_items {
276            Err(ScriptError::StackUnderflow)
277        } else {
278            let at = stack_size - num_items;
279            let items = self.items.split_off(at);
280
281            Ok(items)
282        }
283    }
284
285    /// Return a binary array representation of the input stack
286    pub fn to_bytes(&self) -> Vec<u8> {
287        self.items.iter().fold(Vec::new(), |mut bytes, item| {
288            item.to_bytes(&mut bytes);
289            bytes
290        })
291    }
292
293    pub fn from_bytes(bytes: &[u8]) -> Result<Self, ScriptError> {
294        let mut stack = ExecutionStack { items: Vec::new() };
295        let mut byte_str = bytes;
296        while !byte_str.is_empty() {
297            match StackItem::read_next(byte_str) {
298                Some((item, b)) => {
299                    stack.push(item)?;
300                    byte_str = b;
301                },
302                None => return Err(ScriptError::InvalidInput),
303            }
304        }
305        Ok(stack)
306    }
307
308    /// Pushes the item onto the top of the stack. This function will only error if the new stack size exceeds the
309    /// maximum allowed stack size, given by [MAX_STACK_SIZE]
310    pub fn push(&mut self, item: StackItem) -> Result<(), ScriptError> {
311        if self.size() >= MAX_STACK_SIZE {
312            return Err(ScriptError::StackOverflow);
313        }
314        self.items.push(item);
315        Ok(())
316    }
317
318    /// Pushes the top stack element down `depth` positions
319    pub(crate) fn push_down(&mut self, depth: usize) -> Result<(), ScriptError> {
320        let n = self.size();
321        if n < depth + 1 {
322            return Err(ScriptError::StackUnderflow);
323        }
324        if depth == 0 {
325            return Ok(());
326        }
327        let top = self.pop().unwrap();
328        self.items.insert(n - depth - 1, top);
329        Ok(())
330    }
331}
332
333impl Hex for ExecutionStack {
334    fn from_hex(hex: &str) -> Result<Self, HexError>
335    where Self: Sized {
336        let b = from_hex(hex)?;
337        ExecutionStack::from_bytes(&b).map_err(|_| HexError::HexConversionError {})
338    }
339
340    fn to_hex(&self) -> String {
341        to_hex(&self.to_bytes())
342    }
343}
344
345/// Utility function that given a count of `StackItem` variants, adds 1 for the given item.
346#[allow(clippy::many_single_char_names)]
347fn counter(values: [u8; 6], item: &StackItem) -> [u8; 6] {
348    let [n, h, c, p, s, z] = values;
349    #[allow(clippy::enum_glob_use)]
350    use StackItem::*;
351    match item {
352        Number(_) => {
353            let n = n + 1;
354            [n, h, c, p, s, z]
355        },
356        Hash(_) => {
357            let h = h + 1;
358            [n, h, c, p, s, z]
359        },
360        Commitment(_) => {
361            let c = c + 1;
362            [n, h, c, p, s, z]
363        },
364        PublicKey(_) => {
365            let p = p + 1;
366            [n, h, c, p, s, z]
367        },
368        Signature(_) => {
369            let s = s + 1;
370            [n, h, c, p, s, z]
371        },
372        Scalar(_) => {
373            let z = z + 1;
374            [n, h, c, p, s, z]
375        },
376    }
377}
378
379#[cfg(test)]
380mod test {
381    use blake2::Blake2b;
382    use borsh::{BorshDeserialize, BorshSerialize};
383    use digest::{consts::U32, Digest};
384    use rand::rngs::OsRng;
385    use tari_crypto::{
386        compressed_commitment::CompressedCommitment,
387        compressed_key::CompressedKey,
388        keys::SecretKey,
389        ristretto::{RistrettoPublicKey, RistrettoSecretKey},
390    };
391    use tari_utilities::{
392        hex::{from_hex, Hex},
393        message_format::MessageFormat,
394    };
395
396    use crate::{
397        op_codes::ScalarValue,
398        CheckSigSchnorrSignature,
399        CompressedCheckSigSchnorrSignature,
400        ExecutionStack,
401        HashValue,
402        StackItem,
403    };
404
405    #[test]
406    fn as_bytes_roundtrip() {
407        use crate::StackItem::{Number, PublicKey, Signature};
408        let k = RistrettoSecretKey::random(&mut rand::thread_rng());
409        let p = CompressedKey::<RistrettoPublicKey>::from_secret_key(&k);
410        let s = CompressedCheckSigSchnorrSignature::new_from_schnorr(
411            CheckSigSchnorrSignature::sign(&k, b"hi", &mut OsRng).unwrap(),
412        );
413        let items = vec![Number(5432), Number(21), Signature(s), PublicKey(p)];
414        let stack = ExecutionStack::new(items);
415        let bytes = stack.to_bytes();
416        let stack2 = ExecutionStack::from_bytes(&bytes).unwrap();
417        assert_eq!(stack, stack2);
418    }
419
420    #[test]
421    fn deserialisation() {
422        let k =
423            RistrettoSecretKey::from_hex("7212ac93ee205cdbbb57c4f0f815fbf8db25b4d04d3532e2262e31907d82c700").unwrap();
424        let r =
425            RistrettoSecretKey::from_hex("193ee873f3de511eda8ae387db6498f3d194d31a130a94cdf13dc5890ec1ad0f").unwrap();
426        let p = CompressedKey::<RistrettoPublicKey>::from_secret_key(&k);
427        let m = [1u8; 32];
428        let sig = CompressedCheckSigSchnorrSignature::new_from_schnorr(
429            CheckSigSchnorrSignature::sign_with_nonce_and_message(&k, r, m).unwrap(),
430        );
431        let inputs = inputs!(sig, p, m as HashValue);
432        assert_eq!(inputs.to_hex(),
433        "0500f7c695528c858cde76dab3076908e01228b6dbdd5f671bed1b03b89e170c31c6134be1c65544fa3f26c59903165f664db0dc364cbbaa4b35a9b33342cc01000456c0fa32558d6edc0916baa26b48e745de834571534ca253ea82435f08ebbc7c060101010101010101010101010101010101010101010101010101010101010101");
434    }
435
436    #[test]
437    fn serialisation() {
438        // let p =
439        //     RistrettoPublicKey::from_hex("56c0fa32558d6edc0916baa26b48e745de834571534ca253ea82435f08ebbc7c").
440        // unwrap(); let r =
441        //     RistrettoPublicKey::from_hex("00f7c695528c858cde76dab3076908e01228b6dbdd5f671bed1b03b89e170c31").
442        // unwrap(); let s =
443        //     RistrettoSecretKey::from_hex("6db1023d5c46d78a97da8eb6c5a37e00d5f2fee182dcb38c1b6c65e90a43c109").
444        // unwrap(); let sig = RistrettoSchnorr::new(r, s);
445        // let m: HashValue = Blake2b::<U32>::digest(b"Hello Tari Script").into();
446        // let inputs = inputs!(m, sig, p);
447        // eprintln!("to_hex(&m) = {:?}", tari_utilities::hex::to_hex(&m));
448        // eprintln!("inputs.to_hex() = {:?}", inputs.to_hex());
449
450        let s = "06fdf9fc345d2cdd8aff624a55f824c7c9ce3cc972e011b4e750e417a90ecc5da50500f7c695528c858cde76dab3076908e0122\
451        8b6dbdd5f671bed1b03b89e170c316db1023d5c46d78a97da8eb6c5a37e00d5f2fee182dcb38c1b6c65e90a43c1090456c0fa32558d6edc0916baa2\
452        6b48e745de834571534ca253ea82435f08ebbc7c";
453        let mut stack = ExecutionStack::from_hex(s).unwrap();
454        assert_eq!(stack.size(), 3);
455        if let Some(StackItem::PublicKey(p)) = stack.pop() {
456            assert_eq!(
457                p.to_hex(),
458                "56c0fa32558d6edc0916baa26b48e745de834571534ca253ea82435f08ebbc7c"
459            );
460        } else {
461            panic!("Expected pubkey")
462        }
463        if let Some(StackItem::Signature(s)) = stack.pop() {
464            assert_eq!(
465                s.get_compressed_public_nonce().to_hex(),
466                "00f7c695528c858cde76dab3076908e01228b6dbdd5f671bed1b03b89e170c31"
467            );
468            assert_eq!(
469                s.get_signature().to_hex(),
470                "6db1023d5c46d78a97da8eb6c5a37e00d5f2fee182dcb38c1b6c65e90a43c109"
471            );
472        } else {
473            panic!("Expected signature")
474        }
475        if let Some(StackItem::Scalar(s)) = stack.pop() {
476            assert_eq!(
477                s.as_slice(),
478                from_hex("fdf9fc345d2cdd8aff624a55f824c7c9ce3cc972e011b4e750e417a90ecc5da5").unwrap()
479            );
480        } else {
481            panic!("Expected scalar")
482        }
483    }
484
485    #[test]
486    fn serde_serialization_non_breaking() {
487        const SERDE_ENCODED_BYTES: &str = "ce0000000000000006fdf9fc345d2cdd8aff624a55f824c7c9ce3cc9\
488        72e011b4e750e417a90ecc5da50456c0fa32558d6edc0916baa26b48e745de834571534ca253ea82435f08ebbc\
489        7c0556c0fa32558d6edc0916baa26b48e745de834571534ca253ea82435f08ebbc7c6db1023d5c46d78a97da8eb\
490        6c5a37e00d5f2fee182dcb38c1b6c65e90a43c10906fdf9fc345d2cdd8aff624a55f824c7c9ce3cc972e011b4e7\
491        50e417a90ecc5da501d2040000000000000356c0fa32558d6edc0916baa26b48e745de834571534ca253ea82435\
492        f08ebbc7c";
493        let p = CompressedKey::<RistrettoPublicKey>::from_hex(
494            "56c0fa32558d6edc0916baa26b48e745de834571534ca253ea82435f08ebbc7c",
495        )
496        .unwrap();
497        let s =
498            RistrettoSecretKey::from_hex("6db1023d5c46d78a97da8eb6c5a37e00d5f2fee182dcb38c1b6c65e90a43c109").unwrap();
499        let sig = CompressedCheckSigSchnorrSignature::new(p.clone(), s);
500        let m: HashValue = Blake2b::<U32>::digest(b"Hello Tari Script").into();
501        let s: ScalarValue = m;
502        let commitment = CompressedCommitment::<RistrettoPublicKey>::from_compressed_key(p.clone());
503
504        // Includes all variants for StackItem
505        let mut expected_inputs = inputs!(s, p, sig, m, 1234, commitment);
506        let stack = ExecutionStack::from_binary(&from_hex(SERDE_ENCODED_BYTES).unwrap()).unwrap();
507
508        for (i, item) in stack.items.into_iter().enumerate().rev() {
509            assert_eq!(
510                item,
511                expected_inputs.pop().unwrap(),
512                "Stack items did not match at index {i}"
513            );
514        }
515
516        assert!(expected_inputs.is_empty());
517    }
518
519    #[test]
520    fn test_borsh_de_serialization() {
521        let s = "06fdf9fc345d2cdd8aff624a55f824c7c9ce3cc972e011b4e750e417a90ecc5da50500f7c695528c858cde76dab3076908e0122\
522        8b6dbdd5f671bed1b03b89e170c316db1023d5c46d78a97da8eb6c5a37e00d5f2fee182dcb38c1b6c65e90a43c1090456c0fa32558d6edc0916baa2\
523        6b48e745de834571534ca253ea82435f08ebbc7c";
524        let stack = ExecutionStack::from_hex(s).unwrap();
525        let mut buf = Vec::new();
526        stack.serialize(&mut buf).unwrap();
527        buf.extend_from_slice(&[1, 2, 3]);
528        let buf = &mut buf.as_slice();
529        assert_eq!(stack, ExecutionStack::deserialize(buf).unwrap());
530        assert_eq!(buf, &[1, 2, 3]);
531    }
532
533    #[test]
534    fn test_borsh_de_serialization_too_large() {
535        // We dont care about the actual stack here, just that its not too large on the varint size
536        // We lie about the size to try and get a mem panic, and say this stack is u64::max large.
537        let buf = vec![255, 255, 255, 255, 255, 255, 255, 255, 255, 1, 49, 8, 2, 5, 6];
538        let buf = &mut buf.as_slice();
539        assert!(ExecutionStack::deserialize(buf).is_err());
540    }
541}
tari_script/stack.rs

tari_script/
stack.rs
