elements_miniscript/extensions/
arith.rs

1//! Miniscript Arithmetic expressions:
2//! Note that this fragment is only supported for Tapscript context
3use std::convert::TryInto;
4use std::str::FromStr;
5use std::{cmp, error, fmt};
6
7use bitcoin::key::XOnlyPublicKey;
8use bitcoin_miniscript::MiniscriptKey;
9use elements::opcodes::all::*;
10use elements::sighash::Prevouts;
11use elements::{opcodes, script, secp256k1_zkp as secp256k1, SchnorrSig, Transaction};
12
13use super::param::{ExtParamTranslator, TranslateExtParam};
14use super::{CovExtArgs, CsfsKey, ExtParam, FromTokenIterError, IdxExpr, ParseableExt, TxEnv};
15use crate::expression::{FromTree, Tree};
16use crate::extensions::check_sig_price_oracle_1;
17use crate::miniscript::context::ScriptContextError;
18use crate::miniscript::lex::{Token as Tk, TokenIter};
19use crate::miniscript::limits::MAX_STANDARD_P2WSH_STACK_ITEM_SIZE;
20use crate::miniscript::satisfy::{Satisfaction, Witness};
21use crate::miniscript::types::extra_props::{OpLimits, TimelockInfo};
22use crate::miniscript::types::{Base, Correctness, Dissat, ExtData, Input, Malleability};
23use crate::{
24    expression, interpreter, miniscript, script_num_size, Error, Extension, Satisfier, ToPublicKey,
25    TranslateExt,
26};
27
28/// Enum representing arithmetic operations with transaction amounts.
29/// Every variant of this enum pushes a single singed 64 bit BE number on stack top.
30/// All of introspection opcodes explicitly assert the amount is explicit.
31///
32/// This will abort when
33///     - Any of operations are on confidential amounts. The Null case is automatically
34///       converted to explicit zero.
35///     - Supplied index is out of bounds.
36///     - Any of the operations overflow. Refer to tapscript opcodes spec for overflow specification
37///     - In extreme cases, when recursive operations exceed 400 depth
38#[derive(Debug, Eq, PartialEq, Ord, PartialOrd, Hash, Clone)]
39pub enum ExprInner<T: ExtParam> {
40    /* leaf fragments/terminals */
41    /// A constant i64 value
42    /// Minimal push of this `<i64>`
43    Const(i64),
44    /// Value under the current executing input
45    /// `INSPECTCURRENTINPUTINDEX INPSECTINPUTVALUE <1> EQUALVERIFY`
46    CurrInputIdx,
47    /// Explicit amount at the given input index
48    /// `i INPSECTINPUTVALUE <1> EQUALVERIFY`
49    Input(IdxExpr),
50    /// Explicit amount at the given output index
51    /// `i INPSECTOUTPUTVALUE <1> EQUALVERIFY`
52    Output(IdxExpr),
53    /// Explicit issuance amount at this input index
54    /// `i OP_INSPECTINPUTISSUANCE DROP DROP <1> EQUALVERIFY NIP NIP`
55    // NIP drops the second to top stack item
56    // issuance stack after push where the right is stack top
57    // [<inflation keys> <inflation_pref> <value> <value_pref> <entropy> <blindingnonce>]
58    InputIssue(IdxExpr),
59    /// Explicit re-issuance amount at this input index
60    /// `i OP_INSPECTINPUTISSUANCE DROP DROP DROP DROP <1> EQUALVERIFY`
61    // issuance stack after push where the right is stack top
62    // [<inflation keys> <inflation_pref> <value> <value_pref> <entropy> <blindingnonce>]
63    InputReIssue(IdxExpr),
64
65    /* Two children */
66    /// Add two Arith expressions.
67    /// `[X] [Y] ADD64 <1> EQUALVERIFY`
68    Add(Box<Expr<T>>, Box<Expr<T>>),
69    /// Subtract (X-Y)
70    /// `[X] [Y] SUB64 <1> EQUALVERIFY`
71    Sub(Box<Expr<T>>, Box<Expr<T>>),
72    /// Multiply two Expr expressions. (a*b)
73    /// `[X] [Y] MUL64 <1> EQUALVERIFY`
74    Mul(Box<Expr<T>>, Box<Expr<T>>),
75    /// Divide two Expr expressions. (a//b)
76    /// The division operation pushes the quotient(a//b) such that the remainder a%b
77    /// (must be non-negative and less than |b|).
78    /// `[X] [Y] DIV64 <1> EQUALVERIFY NIP`
79    Div(Box<Expr<T>>, Box<Expr<T>>),
80    /// Modulo operation (a % b)
81    /// The division operation the remainder a%b (must be non-negative and less than |b|).
82    /// `[X] [Y] DIV64 <1> EQUALVERIFY DROP`
83    Mod(Box<Expr<T>>, Box<Expr<T>>),
84    /// BitWise And (a & b)
85    /// `[X] [Y] AND` (cannot fail)
86    BitAnd(Box<Expr<T>>, Box<Expr<T>>),
87    /// BitWise or (a | b)
88    /// `[X] [Y] OR` (cannot fail)
89    BitOr(Box<Expr<T>>, Box<Expr<T>>),
90    /// BitWise or (a ^ b)
91    /// `[X] [Y] XOR` (cannot fail)
92    Xor(Box<Expr<T>>, Box<Expr<T>>),
93    /* One child*/
94    /// BitWise invert (!a)
95    /// `[X] INVERT` (cannot fail)
96    Invert(Box<Expr<T>>),
97    /// Negate -a
98    /// `[X] NEG64 <1> EQUALVERIFY`
99    Negate(Box<Expr<T>>),
100
101    /// Push the price as LE64 signed from oracle.
102    /// `2DUP TOALTSTACK <T> OP_GREATERTHANEQ VERIFY CAT SHA256 <K> CHECKSIGFROMSTACKVERIFY OP_FROMATLSTACK`
103    /// The fragment checks that the input timestamp is less than time at which the price was signed with
104    /// the given oracle key. The asset of which price is being checked is implicitly decided by the
105    /// public key
106    PriceOracle1(T, u64),
107    /// Same as [`Self::PriceOracle1`] but wrapped in an `TOALTSTACK` and `FROMALTSTACK` and SWAP
108    /// `TOALTSTACK 2DUP TOALTSTACK <T> OP_GREATERTHANEQ VERIFY CAT SHA256 <K> CHECKSIGFROMSTACKVERIFY OP_FROMATLSTACK FROMALTSTACK SWAP`
109    /// We need to swap at the end to make sure that the price pushed by this fragment is on top of the stack
110    /// In regular miniscript, all operations are commutative, but here some operations like sub and div are not and hence
111    /// we need to maintain the exact order of operations.
112    PriceOracle1W(T, u64),
113}
114
115/// An iterator over [`ExprInner`] that yields the terminal nodes
116/// in the expression tree.
117#[derive(Debug, Clone)]
118pub struct ExprIter<'a, T: ExtParam> {
119    stack: Vec<&'a ExprInner<T>>,
120}
121
122impl<'a, T: ExtParam> Iterator for ExprIter<'a, T> {
123    type Item = &'a ExprInner<T>;
124
125    fn next(&mut self) -> Option<Self::Item> {
126        while let Some(expr) = self.stack.pop() {
127            match expr {
128                ExprInner::Const(_)
129                | ExprInner::CurrInputIdx
130                | ExprInner::Input(_)
131                | ExprInner::Output(_)
132                | ExprInner::InputIssue(_)
133                | ExprInner::InputReIssue(_)
134                | ExprInner::PriceOracle1(_, _)
135                | ExprInner::PriceOracle1W(_, _) => return Some(expr),
136                ExprInner::Add(a, b)
137                | ExprInner::Sub(a, b)
138                | ExprInner::Mul(a, b)
139                | ExprInner::Div(a, b)
140                | ExprInner::Mod(a, b)
141                | ExprInner::BitAnd(a, b)
142                | ExprInner::BitOr(a, b)
143                | ExprInner::Xor(a, b) => {
144                    self.stack.push(b.as_inner());
145                    self.stack.push(a.as_inner());
146                }
147                ExprInner::Invert(a) | ExprInner::Negate(a) => {
148                    self.stack.push(a.as_inner());
149                }
150            }
151        }
152        None
153    }
154}
155
156/// [`ExprInner`] with some values cached
157#[derive(Eq, PartialEq, Ord, PartialOrd, Hash, Clone)]
158pub struct Expr<T: ExtParam> {
159    /// The actual inner expression
160    inner: ExprInner<T>,
161    /// The cached script size
162    script_size: usize,
163    /// depth of expression thunk/tree
164    depth: usize,
165}
166
167impl<T: ExtParam> Expr<T> {
168    /// Obtains the inner
169    pub fn into_inner(self) -> ExprInner<T> {
170        self.inner
171    }
172
173    /// Obtains the reference to inner
174    pub fn as_inner(&self) -> &ExprInner<T> {
175        &self.inner
176    }
177
178    /// Obtains the script size
179    pub fn script_size(&self) -> usize {
180        self.script_size
181    }
182
183    /// Obtains the depth of this expression thunk
184    pub fn depth(&self) -> usize {
185        self.depth
186    }
187
188    /// Creates [`Expr`] from [`ExprInner`]
189    pub fn from_inner(inner: ExprInner<T>) -> Self {
190        let (script_size, depth) = match &inner {
191            ExprInner::Const(_c) => (8 + 1, 0),
192            ExprInner::CurrInputIdx => (4, 0), // INSPECTCURRENTINPUTINDEX INPSECTINPUTVALUE <1> EQUALVERIFY
193            ExprInner::Input(i) => (
194                i.script_size() + 3, // i INPSECTINPUTVALUE <1> EQUALVERIFY
195                0,
196            ),
197            ExprInner::Output(i) => (
198                i.script_size() + 3, // i INPSECTOUTPUTVALUE <1> EQUALVERIFY
199                0,
200            ),
201            ExprInner::InputIssue(i) => (
202                i.script_size() + 7, // i OP_INSPECTINPUTISSUANCE DROP DROP <1> EQUALVERIFY NIP NIP
203                0,
204            ),
205            ExprInner::InputReIssue(i) => (
206                i.script_size() + 7, // i OP_INSPECTINPUTISSUANCE DROP DROP DROP DROP <1> EQUALVERIFY
207                0,
208            ),
209            ExprInner::Add(x, y) => (
210                x.script_size + y.script_size + 3, // [X] [Y] ADD64 <1> EQUALVERIFY
211                cmp::max(x.depth, y.depth),
212            ),
213            ExprInner::Sub(x, y) => (
214                x.script_size + y.script_size + 3, // [X] [Y] SUB64 <1> EQUALVERIFY
215                cmp::max(x.depth, y.depth),
216            ),
217            ExprInner::Mul(x, y) => (
218                x.script_size + y.script_size + 3, // [X] [Y] MUL64 <1> EQUALVERIFY
219                cmp::max(x.depth, y.depth),
220            ),
221            ExprInner::Div(x, y) => (
222                x.script_size + y.script_size + 4, // [X] [Y] DIV64 <1> EQUALVERIFY NIP
223                cmp::max(x.depth, y.depth),
224            ),
225            ExprInner::Mod(x, y) => (
226                x.script_size + y.script_size + 4, // [X] [Y] DIV64 <1> EQUALVERIFY DROP
227                cmp::max(x.depth, y.depth),
228            ),
229            ExprInner::BitAnd(x, y) => (
230                x.script_size + y.script_size + 1, // [X] [Y] AND
231                cmp::max(x.depth, y.depth),
232            ),
233            ExprInner::BitOr(x, y) => (
234                x.script_size + y.script_size + 1, // [X] [Y] OR
235                cmp::max(x.depth, y.depth),
236            ),
237            ExprInner::Xor(x, y) => (
238                x.script_size + y.script_size + 1, // [X] [Y] XOR
239                cmp::max(x.depth, y.depth),
240            ),
241            ExprInner::Invert(x) => (
242                x.script_size + 1, // [X] INVERT
243                x.depth + 1,
244            ),
245            ExprInner::Negate(x) => (
246                x.script_size + 3, // [X] NEG64 <1> EQUALVERIFY
247                x.depth + 1,
248            ),
249            ExprInner::PriceOracle1(_pk, _time) => (
250                (32 + 1) // 32 byte key + push
251                + (8 + 1) // 8 byte time push
252                + 8, // opcodes,
253                0,
254            ),
255            ExprInner::PriceOracle1W(_pk, _time) => (
256                (32 + 1) // 32 byte key + push
257                + (8 + 1) // 8 byte time push
258                + 11, // opcodes,
259                0,
260            ),
261        };
262        Self {
263            inner,
264            script_size,
265            depth,
266        }
267    }
268
269    /// Obtains an iterator over terminals nodes
270    pub fn iter_terminals(&self) -> impl Iterator<Item = &ExprInner<T>> {
271        ExprIter {
272            stack: vec![&self.inner],
273        }
274    }
275}
276
277/// Type Check errors in [`Expr`]
278#[derive(Debug, Clone, PartialEq, Eq)]
279pub enum TypeError {
280    /// PriceOracle1W is the first element in the expression
281    PriceOracle1WFirst,
282    /// PriceOracle1 is *not* the first element in the expression
283    PriceOracle1Missing,
284}
285
286impl std::fmt::Display for TypeError {
287    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
288        match self {
289            TypeError::PriceOracle1WFirst => {
290                write!(f, "PriceOracle1W is the first element in the expression")
291            }
292            TypeError::PriceOracle1Missing => write!(
293                f,
294                "PriceOracle1 is *not* the first element in the expression"
295            ),
296        }
297    }
298}
299
300impl std::error::Error for TypeError {}
301
302impl Expr<CovExtArgs> {
303    /// Evaluate this expression
304    fn eval(&self, env: &TxEnv, s: &mut interpreter::Stack) -> Result<i64, EvalError> {
305        match &self.inner {
306            ExprInner::Const(c) => Ok(*c),
307            ExprInner::CurrInputIdx => {
308                if env.idx >= env.spent_utxos.len() {
309                    return Err(EvalError::UtxoIndexOutOfBounds(
310                        env.idx,
311                        env.spent_utxos.len(),
312                    ));
313                }
314                env.spent_utxos[env.idx]
315                    .value
316                    .explicit()
317                    .map(|x| x as i64) // safe conversion bitcoin values from u64 to i64 because 21 mil
318                    .ok_or(EvalError::NonExplicitInput(env.idx))
319            }
320            ExprInner::Input(i) => {
321                let i = i.eval(env)?;
322                if i >= env.spent_utxos.len() {
323                    return Err(EvalError::UtxoIndexOutOfBounds(i, env.spent_utxos.len()));
324                }
325                env.spent_utxos[i]
326                    .value
327                    .explicit()
328                    .map(|x| x as i64) // safe conversion bitcoin values from u64 to i64 because 21 mil
329                    .ok_or(EvalError::NonExplicitInput(i))
330            }
331            ExprInner::Output(i) => {
332                let i = i.eval(env)?;
333                if i >= env.tx.output.len() {
334                    return Err(EvalError::OutputIndexOutOfBounds(i, env.tx.output.len()));
335                }
336                env.tx.output[i]
337                    .value
338                    .explicit()
339                    .map(|x| x as i64) // safe conversion bitcoin values from u64 to i64 because 21 mil
340                    .ok_or(EvalError::NonExplicitOutput(i))
341            }
342            ExprInner::InputIssue(i) => {
343                let i = i.eval(env)?;
344                if i >= env.tx.input.len() {
345                    return Err(EvalError::InputIndexOutOfBounds(i, env.tx.input.len()));
346                }
347                env.tx.input[i]
348                    .asset_issuance
349                    .amount
350                    .explicit()
351                    .map(|x| x as i64) // safe conversion bitcoin values from u64 to i64 because 21 mil
352                    .ok_or(EvalError::NonExplicitInputIssuance(i))
353            }
354            ExprInner::InputReIssue(i) => {
355                let i = i.eval(env)?;
356                if i >= env.tx.input.len() {
357                    return Err(EvalError::InputIndexOutOfBounds(i, env.tx.input.len()));
358                }
359                env.tx.input[i]
360                    .asset_issuance
361                    .inflation_keys
362                    .explicit()
363                    .map(|x| x as i64) // safe conversion bitcoin values from u64 to i64 because 21 mil
364                    .ok_or(EvalError::NonExplicitInputReIssuance(i))
365            }
366            ExprInner::Add(x, y) => {
367                let x = x.eval(env, s)?;
368                let y = y.eval(env, s)?;
369                x.checked_add(y).ok_or(EvalError::AddOverflow(x, y))
370            }
371            ExprInner::Sub(x, y) => {
372                let x = x.eval(env, s)?;
373                let y = y.eval(env, s)?;
374                x.checked_sub(y).ok_or(EvalError::SubOverflow(x, y))
375            }
376            ExprInner::Mul(x, y) => {
377                let x = x.eval(env, s)?;
378                let y = y.eval(env, s)?;
379                x.checked_mul(y).ok_or(EvalError::MulOverflow(x, y))
380            }
381            ExprInner::Div(x, y) => {
382                let x = x.eval(env, s)?;
383                let y = y.eval(env, s)?;
384                x.checked_div_euclid(y).ok_or(EvalError::DivOverflow(x, y))
385            }
386            ExprInner::Mod(x, y) => {
387                let x = x.eval(env, s)?;
388                let y = y.eval(env, s)?;
389                x.checked_rem_euclid(y).ok_or(EvalError::ModOverflow(x, y))
390            }
391            ExprInner::BitAnd(x, y) => {
392                let x = x.eval(env, s)?;
393                let y = y.eval(env, s)?;
394                Ok(x & y)
395            }
396            ExprInner::BitOr(x, y) => {
397                let x = x.eval(env, s)?;
398                let y = y.eval(env, s)?;
399                Ok(x | y)
400            }
401            ExprInner::Xor(x, y) => {
402                let x = x.eval(env, s)?;
403                let y = y.eval(env, s)?;
404                Ok(x ^ y)
405            }
406            ExprInner::Invert(x) => {
407                let x = x.eval(env, s)?;
408                Ok(!x)
409            }
410            ExprInner::Negate(x) => {
411                let x = x.eval(env, s)?;
412                x.checked_neg().ok_or(EvalError::NegOverflow(x))
413            }
414            ExprInner::PriceOracle1(pk, timestamp) | ExprInner::PriceOracle1W(pk, timestamp) => {
415                let x_only_pk = if let CovExtArgs::XOnlyKey(pk) = pk {
416                    pk.0
417                } else {
418                    unreachable!("Construction ensures that Param is only of type XOnlyKey")
419                };
420                let price = s.pop().ok_or(EvalError::MissingPrice)?;
421                let price = price.try_push().map_err(|_| EvalError::Price8BytePush)?;
422                let price_u64 =
423                    u64::from_le_bytes(price.try_into().map_err(|_| EvalError::Price8BytePush)?);
424
425                let time_signed = s.pop().ok_or(EvalError::MissingTimestamp)?;
426                let time_signed = time_signed
427                    .try_push()
428                    .map_err(|_| EvalError::Timstamp8BytePush)?;
429                let time_signed_u64 = u64::from_le_bytes(
430                    time_signed
431                        .try_into()
432                        .map_err(|_| EvalError::Timstamp8BytePush)?,
433                );
434                let sig = s.pop().ok_or(EvalError::MissingOracleSignature)?;
435                let schnorr_sig_sl = sig.try_push().map_err(|_| EvalError::MalformedSig)?;
436                let schnorr_sig = secp256k1::schnorr::Signature::from_slice(schnorr_sig_sl)
437                    .map_err(|_| EvalError::MalformedSig)?;
438                let secp = secp256k1::Secp256k1::verification_only();
439
440                if *timestamp < time_signed_u64 {
441                    return Err(EvalError::TimestampInFuture);
442                }
443
444                if check_sig_price_oracle_1(&secp, &schnorr_sig, &x_only_pk, *timestamp, price_u64)
445                {
446                    let price_i64 =
447                        u64::try_into(price_u64).map_err(|_| EvalError::PriceOverflow)?;
448                    Ok(price_i64)
449                } else {
450                    Err(EvalError::InvalidSignature)
451                }
452            }
453        }
454    }
455
456    /// Evaluate this expression
457    fn satisfy<Pk: MiniscriptKey + ToPublicKey>(
458        &self,
459        env: &TxEnv,
460        s: &dyn Satisfier<Pk>,
461    ) -> Result<(i64, Satisfaction), EvalError> {
462        match &self.inner {
463            ExprInner::Const(c) => Ok((*c, Satisfaction::empty())),
464            ExprInner::CurrInputIdx => {
465                if env.idx >= env.spent_utxos.len() {
466                    return Err(EvalError::UtxoIndexOutOfBounds(
467                        env.idx,
468                        env.spent_utxos.len(),
469                    ));
470                }
471                let res = env.spent_utxos[env.idx]
472                    .value
473                    .explicit()
474                    .map(|x| x as i64) // safe conversion bitcoin values from u64 to i64 because 21 mil
475                    .ok_or(EvalError::NonExplicitInput(env.idx))?;
476                Ok((res, Satisfaction::empty()))
477            }
478            ExprInner::Input(i) => {
479                let i = i.eval(env)?;
480                if i >= env.spent_utxos.len() {
481                    return Err(EvalError::UtxoIndexOutOfBounds(i, env.spent_utxos.len()));
482                }
483                let res = env.spent_utxos[i]
484                    .value
485                    .explicit()
486                    .map(|x| x as i64) // safe conversion bitcoin values from u64 to i64 because 21 mil
487                    .ok_or(EvalError::NonExplicitInput(i))?;
488                Ok((res, Satisfaction::empty()))
489            }
490            ExprInner::Output(i) => {
491                let i = i.eval(env)?;
492                if i >= env.tx.output.len() {
493                    return Err(EvalError::OutputIndexOutOfBounds(i, env.tx.output.len()));
494                }
495                let res = env.tx.output[i]
496                    .value
497                    .explicit()
498                    .map(|x| x as i64) // safe conversion bitcoin values from u64 to i64 because 21 mil
499                    .ok_or(EvalError::NonExplicitOutput(i))?;
500                Ok((res, Satisfaction::empty()))
501            }
502            ExprInner::InputIssue(i) => {
503                let i = i.eval(env)?;
504                if i >= env.tx.input.len() {
505                    return Err(EvalError::InputIndexOutOfBounds(i, env.tx.input.len()));
506                }
507                let res = env.tx.input[i]
508                    .asset_issuance
509                    .amount
510                    .explicit()
511                    .map(|x| x as i64) // safe conversion bitcoin values from u64 to i64 because 21 mil
512                    .ok_or(EvalError::NonExplicitInputIssuance(i))?;
513                Ok((res, Satisfaction::empty()))
514            }
515            ExprInner::InputReIssue(i) => {
516                let i = i.eval(env)?;
517                if i >= env.tx.input.len() {
518                    return Err(EvalError::InputIndexOutOfBounds(i, env.tx.input.len()));
519                }
520                let res = env.tx.input[i]
521                    .asset_issuance
522                    .inflation_keys
523                    .explicit()
524                    .map(|x| x as i64) // safe conversion bitcoin values from u64 to i64 because 21 mil
525                    .ok_or(EvalError::NonExplicitInputReIssuance(i))?;
526                Ok((res, Satisfaction::empty()))
527            }
528            ExprInner::Add(x, y) => {
529                let (x, sat_x) = x.satisfy(env, s)?;
530                let (y, sat_y) = y.satisfy(env, s)?;
531                let res = x.checked_add(y).ok_or(EvalError::AddOverflow(x, y))?;
532                let sat = Satisfaction::combine(sat_y, sat_x);
533                Ok((res, sat))
534            }
535            ExprInner::Sub(x, y) => {
536                let (x, sat_x) = x.satisfy(env, s)?;
537                let (y, sat_y) = y.satisfy(env, s)?;
538                let res = x.checked_sub(y).ok_or(EvalError::SubOverflow(x, y))?;
539                let sat = Satisfaction::combine(sat_y, sat_x);
540                Ok((res, sat))
541            }
542            ExprInner::Mul(x, y) => {
543                let (x, sat_x) = x.satisfy(env, s)?;
544                let (y, sat_y) = y.satisfy(env, s)?;
545                let res = x.checked_mul(y).ok_or(EvalError::MulOverflow(x, y))?;
546                let sat = Satisfaction::combine(sat_y, sat_x);
547                Ok((res, sat))
548            }
549            ExprInner::Div(x, y) => {
550                let (x, sat_x) = x.satisfy(env, s)?;
551                let (y, sat_y) = y.satisfy(env, s)?;
552                let res = x
553                    .checked_div_euclid(y)
554                    .ok_or(EvalError::DivOverflow(x, y))?;
555                let sat = Satisfaction::combine(sat_y, sat_x);
556                Ok((res, sat))
557            }
558            ExprInner::Mod(x, y) => {
559                let (x, sat_x) = x.satisfy(env, s)?;
560                let (y, sat_y) = y.satisfy(env, s)?;
561                let res = x
562                    .checked_rem_euclid(y)
563                    .ok_or(EvalError::ModOverflow(x, y))?;
564                let sat = Satisfaction::combine(sat_y, sat_x);
565                Ok((res, sat))
566            }
567            ExprInner::BitAnd(x, y) => {
568                let (x, sat_x) = x.satisfy(env, s)?;
569                let (y, sat_y) = y.satisfy(env, s)?;
570                let sat = Satisfaction::combine(sat_y, sat_x);
571                Ok((x & y, sat))
572            }
573            ExprInner::BitOr(x, y) => {
574                let (x, sat_x) = x.satisfy(env, s)?;
575                let (y, sat_y) = y.satisfy(env, s)?;
576                let sat = Satisfaction::combine(sat_y, sat_x);
577                Ok((x | y, sat))
578            }
579            ExprInner::Xor(x, y) => {
580                let (x, sat_x) = x.satisfy(env, s)?;
581                let (y, sat_y) = y.satisfy(env, s)?;
582                let sat = Satisfaction::combine(sat_y, sat_x);
583                Ok((x ^ y, sat))
584            }
585            ExprInner::Invert(x) => {
586                let (x, sat_x) = x.satisfy(env, s)?;
587                Ok((!x, sat_x))
588            }
589            ExprInner::Negate(x) => {
590                let (x, sat_x) = x.satisfy(env, s)?;
591                let res = x.checked_neg().ok_or(EvalError::NegOverflow(x))?;
592                Ok((res, sat_x))
593            }
594            ExprInner::PriceOracle1(pk, time) | ExprInner::PriceOracle1W(pk, time) => {
595                let pk = if let CovExtArgs::XOnlyKey(xpk) = pk {
596                    xpk.0
597                } else {
598                    unreachable!("PriceOracle1 constructed with only xonly key")
599                };
600                match s.lookup_price_oracle_sig(&pk, *time) {
601                    Some((sig, price, time)) => {
602                        let wit = Witness::Stack(vec![
603                            sig.as_ref().to_vec(),
604                            time.to_le_bytes().to_vec(),
605                            price.to_le_bytes().to_vec(),
606                        ]);
607                        let sat = Satisfaction {
608                            stack: wit,
609                            has_sig: false, // Even though this has sig, it is not a signature over the tx and the tx is still malleable
610                        };
611                        Ok((price, sat))
612                    }
613                    None => Err(EvalError::MissingOracleSignature),
614                }
615            }
616        }
617    }
618
619    /// Push this script to builder
620    fn push_to_builder(&self, builder: script::Builder) -> script::Builder {
621        match &self.inner {
622            ExprInner::Const(c) => builder.push_slice(&c.to_le_bytes()),
623            ExprInner::CurrInputIdx => builder
624                .push_opcode(OP_PUSHCURRENTINPUTINDEX)
625                .push_opcode(OP_INSPECTINPUTVALUE)
626                .push_int(1)
627                .push_opcode(OP_EQUALVERIFY),
628            ExprInner::Input(i) => i
629                .push_to_builder(builder)
630                .push_opcode(OP_INSPECTINPUTVALUE)
631                .push_int(1)
632                .push_opcode(OP_EQUALVERIFY),
633            ExprInner::Output(i) => i
634                .push_to_builder(builder)
635                .push_opcode(OP_INSPECTOUTPUTVALUE)
636                .push_int(1)
637                .push_opcode(OP_EQUALVERIFY),
638            ExprInner::InputIssue(i) => i
639                .push_to_builder(builder)
640                .push_opcode(OP_INSPECTINPUTISSUANCE)
641                .push_opcode(OP_DROP)
642                .push_opcode(OP_DROP)
643                .push_int(1)
644                .push_opcode(OP_EQUALVERIFY)
645                .push_opcode(OP_NIP)
646                .push_opcode(OP_NIP),
647            ExprInner::InputReIssue(i) => i
648                .push_to_builder(builder)
649                .push_opcode(OP_INSPECTINPUTISSUANCE)
650                .push_opcode(OP_DROP)
651                .push_opcode(OP_DROP)
652                .push_opcode(OP_DROP)
653                .push_opcode(OP_DROP)
654                .push_int(1)
655                .push_opcode(OP_EQUALVERIFY),
656            ExprInner::Add(x, y) => {
657                let builder = x.push_to_builder(builder);
658                let builder = y.push_to_builder(builder);
659                builder
660                    .push_opcode(OP_ADD64)
661                    .push_int(1)
662                    .push_opcode(OP_EQUALVERIFY)
663            }
664            ExprInner::Sub(x, y) => {
665                let builder = x.push_to_builder(builder);
666                let builder = y.push_to_builder(builder);
667                builder
668                    .push_opcode(OP_SUB64)
669                    .push_int(1)
670                    .push_opcode(OP_EQUALVERIFY)
671            }
672            ExprInner::Mul(x, y) => {
673                let builder = x.push_to_builder(builder);
674                let builder = y.push_to_builder(builder);
675                builder
676                    .push_opcode(OP_MUL64)
677                    .push_int(1)
678                    .push_opcode(OP_EQUALVERIFY)
679            }
680            ExprInner::Div(x, y) => {
681                let builder = x.push_to_builder(builder);
682                let builder = y.push_to_builder(builder);
683                builder
684                    .push_opcode(OP_DIV64)
685                    .push_int(1)
686                    .push_opcode(OP_EQUALVERIFY)
687                    .push_opcode(OP_NIP)
688            }
689            ExprInner::Mod(x, y) => {
690                let builder = x.push_to_builder(builder);
691                let builder = y.push_to_builder(builder);
692                builder
693                    .push_opcode(OP_DIV64)
694                    .push_int(1)
695                    .push_opcode(OP_EQUALVERIFY)
696                    .push_opcode(OP_DROP)
697            }
698            ExprInner::BitAnd(x, y) => {
699                let builder = x.push_to_builder(builder);
700                let builder = y.push_to_builder(builder);
701                builder.push_opcode(OP_AND)
702            }
703            ExprInner::BitOr(x, y) => {
704                let builder = x.push_to_builder(builder);
705                let builder = y.push_to_builder(builder);
706                builder.push_opcode(OP_OR)
707            }
708            ExprInner::Xor(x, y) => {
709                let builder = x.push_to_builder(builder);
710                let builder = y.push_to_builder(builder);
711                builder.push_opcode(OP_XOR)
712            }
713            ExprInner::Invert(x) => x.push_to_builder(builder).push_opcode(OP_INVERT),
714            ExprInner::Negate(x) => x
715                .push_to_builder(builder)
716                .push_opcode(OP_NEG64)
717                .push_int(1)
718                .push_opcode(OP_EQUALVERIFY),
719            ExprInner::PriceOracle1(pk, t) => {
720                let xpk = if let CovExtArgs::XOnlyKey(xpk) = pk {
721                    xpk.0
722                } else {
723                    unreachable!("PriceOracle1 constructor ensures that CovExtArgs is XOnlyKey");
724                };
725                // `2DUP TOALTSTACK <T> OP_GREATERTHANEQ VERIFY CAT SHA256 <K> CHECKSIGFROMSTACKVERIFY OP_FROMATLSTACK`
726                builder
727                    .push_opcode(OP_2DUP)
728                    .push_opcode(OP_TOALTSTACK)
729                    .push_slice(&t.to_le_bytes())
730                    .push_opcode(OP_GREATERTHANOREQUAL64)
731                    .push_opcode(OP_VERIFY)
732                    .push_opcode(OP_CAT)
733                    .push_opcode(OP_SHA256)
734                    .push_slice(&xpk.serialize())
735                    .push_opcode(OP_CHECKSIGFROMSTACKVERIFY)
736                    .push_opcode(OP_FROMALTSTACK)
737            }
738            ExprInner::PriceOracle1W(pk, t) => {
739                let xpk = if let CovExtArgs::XOnlyKey(xpk) = pk {
740                    xpk.0
741                } else {
742                    unreachable!("PriceOracle1 constructor ensures that CovExtArgs is XOnlyKey");
743                };
744                // `2DUP TOALTSTACK <T> OP_GREATERTHANEQ VERIFY CAT SHA256 <K> CHECKSIGFROMSTACKVERIFY OP_FROMATLSTACK OP_SWAP`
745                builder
746                    .push_opcode(OP_TOALTSTACK)
747                    .push_opcode(OP_2DUP)
748                    .push_opcode(OP_TOALTSTACK)
749                    .push_slice(&t.to_le_bytes())
750                    .push_opcode(OP_GREATERTHANOREQUAL64)
751                    .push_opcode(OP_VERIFY)
752                    .push_opcode(OP_CAT)
753                    .push_opcode(OP_SHA256)
754                    .push_slice(&xpk.serialize())
755                    .push_opcode(OP_CHECKSIGFROMSTACKVERIFY)
756                    .push_opcode(OP_FROMALTSTACK)
757                    .push_opcode(OP_FROMALTSTACK)
758                    .push_opcode(OP_SWAP)
759            }
760        }
761    }
762
763    /// Returns (self, start_pos) parsed reversed form tokens starting with index end_pos
764    /// Expression is parsed from tokens[start:end_pos]
765    fn from_tokens(tokens: &[Tk], end_pos: usize) -> Option<(Self, usize)> {
766        let tks = tokens;
767        let e = end_pos; // short abbreviations for succinct readable code
768                         //
769                         // The order of arms if else is critical to the code logic. Arms are sorted
770                         // in order of the tokens required to check and early return with checked_sub?.
771                         // In other words, If the tokens array is not sufficient length to parse ith
772                         // arm of if statement, it tokens array cannot parse any jth arm with j > i.
773                         // This significantly cleans up the code as it does not require nested else if.
774                         // But care must be taken when introducing new arms.
775        if let Some(Tk::Bytes8(bytes)) = tks.get(e.checked_sub(1)?) {
776            let mut le_bytes = [0u8; 8];
777            le_bytes.copy_from_slice(bytes);
778            let expr = Expr::from_inner(ExprInner::Const(i64::from_le_bytes(le_bytes)));
779            Some((expr, e - 1))
780        } else if let Some(Tk::Invert) = tks.get(e.checked_sub(1)?) {
781            let (x, end_pos) = Self::from_tokens(tokens, e - 1)?;
782            let expr = Expr::from_inner(ExprInner::Invert(Box::new(x)));
783            Some((expr, end_pos))
784        } else if let Some(Tk::And) = tks.get(e.checked_sub(1)?) {
785            let (y, end_pos) = Self::from_tokens(tokens, e - 1)?;
786            let (x, end_pos) = Self::from_tokens(tokens, end_pos)?;
787            let expr = Expr::from_inner(ExprInner::BitAnd(Box::new(x), Box::new(y)));
788            Some((expr, end_pos))
789        } else if let Some(Tk::Or) = tks.get(e.checked_sub(1)?) {
790            let (y, end_pos) = Self::from_tokens(tokens, e - 1)?;
791            let (x, end_pos) = Self::from_tokens(tokens, end_pos)?;
792            let expr = Expr::from_inner(ExprInner::BitOr(Box::new(x), Box::new(y)));
793            Some((expr, end_pos))
794        } else if let Some(Tk::Xor) = tks.get(e.checked_sub(1)?) {
795            let (y, end_pos) = Self::from_tokens(tokens, e - 1)?;
796            let (x, end_pos) = Self::from_tokens(tokens, end_pos)?;
797            let expr = Expr::from_inner(ExprInner::Xor(Box::new(x), Box::new(y)));
798            Some((expr, end_pos))
799        } else if let Some(&[Tk::Neg64, Tk::Num(1), Tk::Equal, Tk::Verify]) =
800            tks.get(e.checked_sub(4)?..e)
801        {
802            let (x, end_pos) = Self::from_tokens(tokens, e - 4)?;
803            let expr = Expr::from_inner(ExprInner::Negate(Box::new(x)));
804            Some((expr, end_pos))
805        } else if let Some(&[Tk::Add64, Tk::Num(1), Tk::Equal, Tk::Verify]) =
806            tks.get(e.checked_sub(4)?..e)
807        {
808            let (y, end_pos) = Self::from_tokens(tokens, e - 4)?;
809            let (x, end_pos) = Self::from_tokens(tokens, end_pos)?;
810            let expr = Expr::from_inner(ExprInner::Add(Box::new(x), Box::new(y)));
811            Some((expr, end_pos))
812        } else if let Some(&[Tk::Sub64, Tk::Num(1), Tk::Equal, Tk::Verify]) =
813            tks.get(e.checked_sub(4)?..e)
814        {
815            let (y, end_pos) = Self::from_tokens(tokens, e - 4)?;
816            let (x, end_pos) = Self::from_tokens(tokens, end_pos)?;
817            let expr = Expr::from_inner(ExprInner::Sub(Box::new(x), Box::new(y)));
818            Some((expr, end_pos))
819        } else if let Some(&[Tk::Mul64, Tk::Num(1), Tk::Equal, Tk::Verify]) =
820            tks.get(e.checked_sub(4)?..e)
821        {
822            let (y, end_pos) = Self::from_tokens(tokens, e - 4)?;
823            let (x, end_pos) = Self::from_tokens(tokens, end_pos)?;
824            let expr = Expr::from_inner(ExprInner::Mul(Box::new(x), Box::new(y)));
825            Some((expr, end_pos))
826        } else if let Some(&[Tk::CurrInp, Tk::InpValue, Tk::Num(1), Tk::Equal, Tk::Verify]) =
827            tks.get(e.checked_sub(5)?..e)
828        {
829            Some((Expr::from_inner(ExprInner::CurrInputIdx), e - 5))
830        } else if let Some(&[Tk::Div64, Tk::Num(1), Tk::Equal, Tk::Verify, Tk::Nip]) =
831            tks.get(e.checked_sub(5)?..e)
832        {
833            let (y, end_pos) = Self::from_tokens(tokens, e - 5)?;
834            let (x, end_pos) = Self::from_tokens(tokens, end_pos)?;
835            let expr = Expr::from_inner(ExprInner::Div(Box::new(x), Box::new(y)));
836            Some((expr, end_pos))
837        } else if let Some(&[Tk::Div64, Tk::Num(1), Tk::Equal, Tk::Verify, Tk::Drop]) =
838            tks.get(e.checked_sub(5)?..e)
839        {
840            let (y, end_pos) = Self::from_tokens(tokens, e - 5)?;
841            let (x, end_pos) = Self::from_tokens(tokens, end_pos)?;
842            let expr = Expr::from_inner(ExprInner::Mod(Box::new(x), Box::new(y)));
843            Some((expr, end_pos))
844        } else if let Some(&[Tk::InpValue, Tk::Num(1), Tk::Equal, Tk::Verify]) =
845            tks.get(e.checked_sub(4)?..e)
846        {
847            let (i, e) = IdxExpr::from_tokens(tks, e - 4)?;
848            Some((Expr::from_inner(ExprInner::Input(i)), e))
849        } else if let Some(&[Tk::OutValue, Tk::Num(1), Tk::Equal, Tk::Verify]) =
850            tks.get(e.checked_sub(4)?..e)
851        {
852            let (i, e) = IdxExpr::from_tokens(tks, e - 4)?;
853            Some((Expr::from_inner(ExprInner::Output(i)), e))
854        } else if let Some(
855            &[Tk::InpIssue, Tk::Drop, Tk::Drop, Tk::Num(1), Tk::Equal, Tk::Verify, Tk::Nip, Tk::Nip],
856        ) = tks.get(e.checked_sub(8)?..e)
857        {
858            let (i, e) = IdxExpr::from_tokens(tks, e - 8)?;
859            Some((Expr::from_inner(ExprInner::InputIssue(i)), e))
860        } else if let Some(
861            &[Tk::InpIssue, Tk::Drop, Tk::Drop, Tk::Drop, Tk::Drop, Tk::Num(1), Tk::Equal, Tk::Verify],
862        ) = tks.get(e.checked_sub(8)?..e)
863        {
864            let (i, e) = IdxExpr::from_tokens(tks, e - 8)?;
865            Some((Expr::from_inner(ExprInner::InputReIssue(i)), e))
866        } else if let Some(
867            &[Tk::Dup2, Tk::ToAltStack, Tk::Bytes8(time), Tk::Geq64, Tk::Verify, Tk::Cat, Tk::Sha256, Tk::Bytes32(xpk), Tk::CheckSigFromStackVerify, Tk::FromAltStack],
868        ) = tks.get(e.checked_sub(10)?..e)
869        {
870            let time = u64::from_le_bytes(time.try_into().expect("8 bytes"));
871            let xpk = XOnlyPublicKey::from_slice(xpk).ok()?;
872            let key = CovExtArgs::csfs_key(xpk);
873            let expr = Expr::from_inner(ExprInner::PriceOracle1(key, time));
874            Some((expr, e - 10))
875        } else if let Some(
876            &[Tk::ToAltStack, Tk::Dup2, Tk::ToAltStack, Tk::Bytes8(time), Tk::Geq64, Tk::Verify, Tk::Cat, Tk::Sha256, Tk::Bytes32(xpk), Tk::CheckSigFromStackVerify, Tk::FromAltStack, Tk::FromAltStack, Tk::Swap],
877        ) = tks.get(e.checked_sub(13)?..e)
878        {
879            let time = u64::from_le_bytes(time.try_into().expect("8 bytes"));
880            let xpk = XOnlyPublicKey::from_slice(xpk).ok()?;
881            let key = CovExtArgs::csfs_key(xpk);
882            let expr = Expr::from_inner(ExprInner::PriceOracle1W(key, time));
883            Some((expr, e - 13))
884        } else {
885            None
886        }
887    }
888}
889
890/// Miniscript Fragment containing arith expressions
891/// Expr cannot be directly used a miniscript fragment because it pushes a 64 bit
892/// value on stack. Two expressions can be combined with Arith to something is
893/// of Base type B to be used in miniscript expressions
894///
895/// This struct represents unchecked arith expressions that could be invalid.
896/// As of now, [`Expr`] can be invalid only if
897///     - PriceOracle1 is not the first leaf in the tree
898///     - PriceOracle1W is the first leaf in the tree
899#[derive(Eq, PartialEq, Ord, PartialOrd, Hash, Clone, Debug)]
900pub enum ArithInner<T: ExtParam> {
901    /// Eq
902    /// `[X] [Y] EQUAL`
903    Eq(Expr<T>, Expr<T>),
904    /// Lt
905    /// `[X] [Y] LESSTHAN`
906    Lt(Expr<T>, Expr<T>),
907    /// Leq
908    /// `[X] [Y] LESSTHANOREQUAL`
909    Leq(Expr<T>, Expr<T>),
910    /// Gt
911    /// `[X] [Y] GREATERTHAN`
912    Gt(Expr<T>, Expr<T>),
913    /// Geq
914    /// `[X] [Y] GREATERTHANOREQUAL`
915    Geq(Expr<T>, Expr<T>),
916}
917
918/// Wrapper around [`ArithInner`] that ensures that the expression is valid.
919/// See [`ArithInner`] for more details.
920///
921/// Note that the library allows construction of unchecked [`Expr], but
922/// [`Arith`] is always checked.
923#[derive(Eq, PartialEq, Ord, PartialOrd, Hash, Clone)]
924pub struct Arith<T: ExtParam> {
925    /// The underlying expression
926    expr: ArithInner<T>,
927}
928
929impl<T: ExtParam> Arith<T> {
930    /// Create a new Arith expression. This is the only constructor
931    pub fn new(expr: ArithInner<T>) -> Result<Self, TypeError> {
932        {
933            // Borrow checker scope
934            let (a, b) = match &expr {
935                ArithInner::Eq(ref a, ref b)
936                | ArithInner::Lt(ref a, ref b)
937                | ArithInner::Leq(ref a, ref b)
938                | ArithInner::Gt(ref a, ref b)
939                | ArithInner::Geq(ref a, ref b) => (a, b),
940            };
941            let mut iter = a.iter_terminals();
942            if let Some(ExprInner::PriceOracle1W(_, _)) = iter.next() {
943                return Err(TypeError::PriceOracle1WFirst);
944            }
945            // Note iter here has consumed the first element
946            if iter.any(|x| matches!(x, ExprInner::PriceOracle1(..))) {
947                return Err(TypeError::PriceOracle1Missing);
948            }
949            // All the elements in b should be PriceOracle1W
950            if b.iter_terminals()
951                .any(|x| matches!(x, ExprInner::PriceOracle1(..)))
952            {
953                return Err(TypeError::PriceOracle1Missing);
954            }
955        }
956        Ok(Arith { expr })
957    }
958
959    /// Obtains the inner expression
960    pub fn inner(&self) -> &ArithInner<T> {
961        &self.expr
962    }
963}
964
965impl<T: ExtParam> Arith<T> {
966    /// Obtains the depth of this expression
967    pub fn depth(&self) -> usize {
968        match &self.expr {
969            ArithInner::Eq(x, y)
970            | ArithInner::Lt(x, y)
971            | ArithInner::Leq(x, y)
972            | ArithInner::Gt(x, y)
973            | ArithInner::Geq(x, y) => cmp::max(x.depth, y.depth),
974        }
975    }
976
977    /// Obtains the script size
978    pub fn script_size(&self) -> usize {
979        match &self.expr {
980            ArithInner::Eq(x, y)
981            | ArithInner::Lt(x, y)
982            | ArithInner::Leq(x, y)
983            | ArithInner::Gt(x, y)
984            | ArithInner::Geq(x, y) => x.script_size + y.script_size + 1,
985        }
986    }
987}
988
989impl Arith<CovExtArgs> {
990    /// Evaluate this expression with context given transaction and spent utxos
991    pub fn eval(&self, env: &TxEnv, s: &mut interpreter::Stack) -> Result<bool, EvalError> {
992        let res = match &self.expr {
993            ArithInner::Eq(x, y) => x.eval(env, s)? == y.eval(env, s)?,
994            ArithInner::Lt(x, y) => x.eval(env, s)? < y.eval(env, s)?,
995            ArithInner::Leq(x, y) => x.eval(env, s)? <= y.eval(env, s)?,
996            ArithInner::Gt(x, y) => x.eval(env, s)? > y.eval(env, s)?,
997            ArithInner::Geq(x, y) => x.eval(env, s)? >= y.eval(env, s)?,
998        };
999        Ok(res)
1000    }
1001
1002    /// Internal satisfaction helper for Arith.
1003    /// This allows us to cleanly write code that we can use "?" for early
1004    /// returns.
1005    /// The trait implementation of satisfy just calls this function with unwrap_or
1006    /// impossible.
1007    pub fn satisfy_helper<Pk: ToPublicKey>(
1008        &self,
1009        env: &TxEnv,
1010        sat: &dyn Satisfier<Pk>,
1011    ) -> Result<Satisfaction, EvalError> {
1012        let (res, sat_a, sat_b) = match &self.expr {
1013            ArithInner::Eq(a, b) => {
1014                let (a, sat_a) = a.satisfy(env, sat)?;
1015                let (b, sat_b) = b.satisfy(env, sat)?;
1016                (a == b, sat_a, sat_b)
1017            }
1018            ArithInner::Lt(a, b) => {
1019                let (a, sat_a) = a.satisfy(env, sat)?;
1020                let (b, sat_b) = b.satisfy(env, sat)?;
1021                (a < b, sat_a, sat_b)
1022            }
1023            ArithInner::Leq(a, b) => {
1024                let (a, sat_a) = a.satisfy(env, sat)?;
1025                let (b, sat_b) = b.satisfy(env, sat)?;
1026                (a <= b, sat_a, sat_b)
1027            }
1028            ArithInner::Gt(a, b) => {
1029                let (a, sat_a) = a.satisfy(env, sat)?;
1030                let (b, sat_b) = b.satisfy(env, sat)?;
1031                (a > b, sat_a, sat_b)
1032            }
1033            ArithInner::Geq(a, b) => {
1034                let (a, sat_a) = a.satisfy(env, sat)?;
1035                let (b, sat_b) = b.satisfy(env, sat)?;
1036                (a >= b, sat_a, sat_b)
1037            }
1038        };
1039        if res {
1040            Ok(Satisfaction::combine(sat_b, sat_a))
1041        } else {
1042            Ok(Satisfaction::impossible())
1043        }
1044    }
1045
1046    /// Push this script to builder
1047    pub fn push_to_builder(&self, builder: script::Builder) -> script::Builder {
1048        match &self.expr {
1049            ArithInner::Eq(x, y) => {
1050                let builder = x.push_to_builder(builder);
1051                let builder = y.push_to_builder(builder);
1052                builder.push_opcode(OP_EQUAL)
1053            }
1054            ArithInner::Lt(x, y) => {
1055                let builder = x.push_to_builder(builder);
1056                let builder = y.push_to_builder(builder);
1057                builder.push_opcode(OP_LESSTHAN64)
1058            }
1059            ArithInner::Leq(x, y) => {
1060                let builder = x.push_to_builder(builder);
1061                let builder = y.push_to_builder(builder);
1062                builder.push_opcode(OP_LESSTHANOREQUAL64)
1063            }
1064            ArithInner::Gt(x, y) => {
1065                let builder = x.push_to_builder(builder);
1066                let builder = y.push_to_builder(builder);
1067                builder.push_opcode(OP_GREATERTHAN64)
1068            }
1069            ArithInner::Geq(x, y) => {
1070                let builder = x.push_to_builder(builder);
1071                let builder = y.push_to_builder(builder);
1072                builder.push_opcode(OP_GREATERTHANOREQUAL64)
1073            }
1074        }
1075    }
1076
1077    /// Parse from [elements::Script]
1078    /// Parsing cannot roundtrip because of associative properties, similar to and_v
1079    /// mul(mul(a,b),c) == mul(a,mul(b,c))
1080    ///
1081    /// Returns the tokens consumed if it is possible for the object to the parsed
1082    /// tokens parsing reverse starting from index ind
1083    fn from_tokens(tokens: &[Tk]) -> Option<(Self, usize)> {
1084        let last_opcode = tokens.last()?;
1085        let (y, pos) = Expr::from_tokens(tokens, tokens.len() - 1)?;
1086        let (x, pos) = Expr::from_tokens(tokens, pos)?;
1087        let (inner, pos) = match last_opcode {
1088            Tk::Equal => (ArithInner::Eq(x, y), pos),
1089            Tk::Le64 => (ArithInner::Lt(x, y), pos),
1090            Tk::Leq64 => (ArithInner::Leq(x, y), pos),
1091            Tk::Ge64 => (ArithInner::Gt(x, y), pos),
1092            Tk::Geq64 => (ArithInner::Geq(x, y), pos),
1093            _ => return None,
1094        };
1095        Some((Arith::new(inner).ok()?, pos))
1096    }
1097}
1098
1099impl<T: ExtParam> fmt::Display for Expr<T> {
1100    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1101        match &self.inner {
1102            ExprInner::Const(c) => write!(f, "{}", c),
1103            ExprInner::CurrInputIdx => write!(f, "curr_inp_v"),
1104            ExprInner::Input(i) => write!(f, "inp_v({})", i),
1105            ExprInner::Output(i) => write!(f, "out_v({})", i),
1106            ExprInner::InputIssue(i) => write!(f, "inp_issue_v({})", i),
1107            ExprInner::InputReIssue(i) => write!(f, "inp_reissue_v({})", i),
1108            ExprInner::Add(x, y) => write!(f, "add({},{})", x, y),
1109            ExprInner::Sub(x, y) => write!(f, "sub({},{})", x, y),
1110            ExprInner::Mul(x, y) => write!(f, "mul({},{})", x, y),
1111            ExprInner::Div(x, y) => write!(f, "div({},{})", x, y),
1112            ExprInner::Mod(x, y) => write!(f, "mod({},{})", x, y),
1113            ExprInner::BitAnd(x, y) => write!(f, "bitand({},{})", x, y), // Use 'bit' prefix to clearly separate from miniscript And/OR
1114            ExprInner::BitOr(x, y) => write!(f, "bitor({},{})", x, y),
1115            ExprInner::Xor(x, y) => write!(f, "bitxor({},{})", x, y),
1116            ExprInner::Invert(x) => write!(f, "bitinv({})", x),
1117            ExprInner::Negate(x) => write!(f, "neg({})", x),
1118            ExprInner::PriceOracle1(pk, t) => write!(f, "price_oracle1({},{})", pk, t),
1119            ExprInner::PriceOracle1W(pk, t) => write!(f, "price_oracle1_w({},{})", pk, t), // same syntax
1120        }
1121    }
1122}
1123
1124impl<T: ExtParam> fmt::Debug for Expr<T> {
1125    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1126        match &self.inner {
1127            ExprInner::Const(c) => write!(f, "{:?}", c),
1128            ExprInner::CurrInputIdx => write!(f, "curr_inp_v"),
1129            ExprInner::Input(i) => write!(f, "inp_v({:?})", i),
1130            ExprInner::Output(i) => write!(f, "out_v({:?})", i),
1131            ExprInner::InputIssue(i) => write!(f, "inp_issue_v({:?})", i),
1132            ExprInner::InputReIssue(i) => write!(f, "inp_reissue_v({:?})", i),
1133            ExprInner::Add(x, y) => write!(f, "add({:?},{:?})", x, y),
1134            ExprInner::Sub(x, y) => write!(f, "sub({:?},{:?})", x, y),
1135            ExprInner::Mul(x, y) => write!(f, "mul({:?},{:?})", x, y),
1136            ExprInner::Div(x, y) => write!(f, "div({:?},{:?})", x, y),
1137            ExprInner::Mod(x, y) => write!(f, "mod({:?},{:?})", x, y),
1138            ExprInner::BitAnd(x, y) => write!(f, "bitand({:?},{:?})", x, y), // Use 'bit' prefix to clearly separate from miniscript And/OR
1139            ExprInner::BitOr(x, y) => write!(f, "bitor({:?},{:?})", x, y),
1140            ExprInner::Xor(x, y) => write!(f, "bitxor({:?},{:?})", x, y),
1141            ExprInner::Invert(x) => write!(f, "bitinv({:?})", x),
1142            ExprInner::Negate(x) => write!(f, "neg({:?})", x),
1143            ExprInner::PriceOracle1(pk, t) => write!(f, "price_oracle1({:?},{:?})", pk, t),
1144            ExprInner::PriceOracle1W(pk, t) => write!(f, "price_oracle1_w({:?},{:?})", pk, t), // same syntax as price_oracle1
1145        }
1146    }
1147}
1148
1149impl<T: ExtParam> FromStr for Expr<T> {
1150    type Err = Error;
1151
1152    fn from_str(s: &str) -> Result<Self, Self::Err> {
1153        let top = expression::Tree::from_str(s)?;
1154        Self::from_tree(&top)
1155    }
1156}
1157
1158impl<T: ExtParam> FromTree for Box<Expr<T>> {
1159    fn from_tree(top: &expression::Tree<'_>) -> Result<Self, Error> {
1160        expression::FromTree::from_tree(top).map(Box::new)
1161    }
1162}
1163
1164impl<T: ExtParam> FromTree for Expr<T> {
1165    fn from_tree(top: &expression::Tree<'_>) -> Result<Self, Error> {
1166        fn unary<F, T: ExtParam>(top: &expression::Tree<'_>, frag: F) -> Result<Expr<T>, Error>
1167        where
1168            F: FnOnce(Box<Expr<T>>) -> ExprInner<T>,
1169        {
1170            let l: Expr<T> = FromTree::from_tree(&top.args[0])?;
1171            Ok(Expr::from_inner(frag(Box::new(l))))
1172        }
1173
1174        fn binary<F, T: ExtParam>(top: &expression::Tree<'_>, frag: F) -> Result<Expr<T>, Error>
1175        where
1176            F: FnOnce(Box<Expr<T>>, Box<Expr<T>>) -> ExprInner<T>,
1177        {
1178            let l: Expr<T> = FromTree::from_tree(&top.args[0])?;
1179            let r: Expr<T> = FromTree::from_tree(&top.args[1])?;
1180            Ok(Expr::from_inner(frag(Box::new(l), Box::new(r))))
1181        }
1182        match (top.name, top.args.len()) {
1183            ("inp_v", 1) => Ok(Expr::from_inner(expression::unary(top, ExprInner::Input)?)),
1184            ("curr_inp_v", 0) => Ok(Expr::from_inner(ExprInner::CurrInputIdx)),
1185            ("out_v", 1) => Ok(Expr::from_inner(expression::unary(top, ExprInner::Output)?)),
1186            ("inp_issue_v", 1) => Ok(Expr::from_inner(expression::unary(
1187                top,
1188                ExprInner::InputIssue,
1189            )?)),
1190            ("inp_reissue_v", 1) => Ok(Expr::from_inner(expression::unary(
1191                top,
1192                ExprInner::InputReIssue,
1193            )?)),
1194            ("price_oracle1", 2) | ("price_oracle1_w", 2) => {
1195                if !top.args[0].args.is_empty() || !top.args[1].args.is_empty() {
1196                    return Err(Error::Unexpected(String::from(
1197                        "price_oracle1 expects 2 terminal arguments",
1198                    )));
1199                }
1200                let pk = T::arg_from_str(top.args[0].name, top.name, 0)?;
1201                let t: u64 = expression::parse_num::<u64>(top.args[1].name)?;
1202                if top.name == "price_oracle1" {
1203                    Ok(Expr::from_inner(ExprInner::PriceOracle1(pk, t)))
1204                } else {
1205                    Ok(Expr::from_inner(ExprInner::PriceOracle1W(pk, t)))
1206                }
1207            }
1208            ("add", 2) => binary(top, ExprInner::Add),
1209            ("sub", 2) => binary(top, ExprInner::Sub),
1210            ("mul", 2) => binary(top, ExprInner::Mul),
1211            ("div", 2) => binary(top, ExprInner::Div),
1212            ("mod", 2) => binary(top, ExprInner::Mod),
1213            ("bitand", 2) => binary(top, ExprInner::BitAnd),
1214            ("bitor", 2) => binary(top, ExprInner::BitOr),
1215            ("bitxor", 2) => binary(top, ExprInner::Xor),
1216            ("bitinv", 1) => unary(top, ExprInner::Invert),
1217            ("neg", 1) => unary(top, ExprInner::Negate),
1218            (_num, 0) => {
1219                Ok(Expr {
1220                    inner: expression::terminal(top, expression::parse_num::<i64>)
1221                        .map(ExprInner::Const)?,
1222                    script_size: 8 + 1, // 8 byte push
1223                    depth: 0,
1224                })
1225            }
1226            _ => Err(Error::Unexpected(format!(
1227                "{}({} args) while parsing Extension",
1228                top.name,
1229                top.args.len(),
1230            ))),
1231        }
1232    }
1233}
1234
1235impl<T: ExtParam> FromStr for ArithInner<T> {
1236    type Err = Error;
1237
1238    fn from_str(s: &str) -> Result<Self, Self::Err> {
1239        let top = expression::Tree::from_str(s)?;
1240        Self::from_tree(&top)
1241    }
1242}
1243
1244impl<T: ExtParam> FromStr for Arith<T> {
1245    type Err = Error;
1246
1247    fn from_str(s: &str) -> Result<Self, Self::Err> {
1248        let inner = ArithInner::from_str(s)?;
1249        Arith::new(inner).map_err(|_| Error::Unexpected(String::from("Arith::new")))
1250    }
1251}
1252
1253impl<T: ExtParam> FromTree for Box<ArithInner<T>> {
1254    fn from_tree(top: &expression::Tree<'_>) -> Result<Self, Error> {
1255        ArithInner::from_tree(top).map(Box::new)
1256    }
1257}
1258
1259impl<T: ExtParam> FromTree for ArithInner<T> {
1260    fn from_tree(top: &expression::Tree<'_>) -> Result<Self, Error> {
1261        match (top.name, top.args.len()) {
1262            // Disambiguiate with num64_eq to avoid confusion with asset_eq
1263            ("num64_eq", 2) => expression::binary(top, ArithInner::Eq),
1264            ("num64_geq", 2) => expression::binary(top, ArithInner::Geq),
1265            ("num64_gt", 2) => expression::binary(top, ArithInner::Gt),
1266            ("num64_lt", 2) => expression::binary(top, ArithInner::Lt),
1267            ("num64_leq", 2) => expression::binary(top, ArithInner::Leq),
1268            _ => Err(Error::Unexpected(format!(
1269                "{}({} args) while parsing Extension",
1270                top.name,
1271                top.args.len(),
1272            ))),
1273        }
1274    }
1275}
1276
1277impl<T: ExtParam> fmt::Display for Arith<T> {
1278    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1279        match &self.expr {
1280            ArithInner::Eq(x, y) => write!(f, "num64_eq({},{})", x, y),
1281            ArithInner::Leq(x, y) => write!(f, "num64_leq({},{})", x, y),
1282            ArithInner::Lt(x, y) => write!(f, "num64_lt({},{})", x, y),
1283            ArithInner::Geq(x, y) => write!(f, "num64_geq({},{})", x, y),
1284            ArithInner::Gt(x, y) => write!(f, "num64_gt({},{})", x, y),
1285        }
1286    }
1287}
1288
1289impl<T: ExtParam> fmt::Debug for Arith<T> {
1290    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1291        match &self.expr {
1292            ArithInner::Eq(x, y) => write!(f, "num64_eq({:?},{:?})", x, y),
1293            ArithInner::Leq(x, y) => write!(f, "num64_leq({:?},{:?})", x, y),
1294            ArithInner::Lt(x, y) => write!(f, "num64_lt({:?},{:?})", x, y),
1295            ArithInner::Geq(x, y) => write!(f, "num64_geq({:?},{:?})", x, y),
1296            ArithInner::Gt(x, y) => write!(f, "num64_gt({:?},{:?})", x, y),
1297        }
1298    }
1299}
1300
1301impl<T: ExtParam> Extension for Arith<T> {
1302    fn corr_prop(&self) -> Correctness {
1303        Correctness {
1304            base: Base::B,
1305            input: Input::Zero,    // No input from stack
1306            dissatisfiable: false, // No dissatisfactions from stack
1307            unit: true,
1308        }
1309    }
1310
1311    fn mall_prop(&self) -> Malleability {
1312        Malleability {
1313            dissat: Dissat::None, // No dissatisfactions from stack inputs
1314            safe: false,          // Unsafe as a top fragment
1315            non_malleable: true, // There can exist multiple satisfactions for expressions. inp_v(0) = out_v(0), but
1316                                 // we only deal with script satisfactions here.
1317        }
1318    }
1319
1320    fn extra_prop(&self) -> ExtData {
1321        ExtData {
1322            pk_cost: self.script_size(), // 1 opcodes, 1 key push, msg, 1 msg push
1323            has_free_verify: false,
1324            stack_elem_count_sat: Some(0),
1325            stack_elem_count_dissat: Some(0),
1326            max_sat_size: Some((0, 0)),
1327            max_dissat_size: Some((0, 0)),
1328            timelock_info: TimelockInfo::default(),
1329            exec_stack_elem_count_sat: Some(self.depth()),
1330            exec_stack_elem_count_dissat: Some(self.depth()),
1331            ops: OpLimits {
1332                // Opcodes are really not relevant in tapscript as BIP342 removes all rules on them
1333                // So, don't make any effort in trying to compute and cache them.
1334                count: 0,
1335                sat: Some(0),
1336                nsat: Some(0),
1337            },
1338        }
1339    }
1340
1341    fn script_size(&self) -> usize {
1342        self.script_size()
1343    }
1344
1345    fn segwit_ctx_checks(&self) -> Result<(), miniscript::context::ScriptContextError> {
1346        // New opcodes only supported in taproot context
1347        Err(ScriptContextError::ExtensionError(
1348            "Arith opcodes only available in Taproot".to_string(),
1349        ))
1350    }
1351
1352    fn from_name_tree(
1353        name: &str,
1354        children: &[expression::Tree<'_>],
1355    ) -> Result<Self, FromTokenIterError> {
1356        let tree = Tree {
1357            name,
1358            args: children.to_vec(), // Cloning two references here, it is possible to avoid the to_vec() here,
1359                                     // but it requires lot of refactor.
1360        };
1361        let inner = ArithInner::from_tree(&tree).map_err(|_| FromTokenIterError)?;
1362        Arith::new(inner).map_err(|_e| FromTokenIterError)
1363    }
1364}
1365
1366impl ParseableExt for Arith<CovExtArgs> {
1367    fn satisfy<Pk, S>(&self, sat: &S) -> Satisfaction
1368    where
1369        Pk: ToPublicKey,
1370        S: Satisfier<Pk>,
1371    {
1372        let (tx, utxos, curr_idx) = match (
1373            sat.lookup_tx(),
1374            sat.lookup_spent_utxos(),
1375            sat.lookup_curr_inp(),
1376        ) {
1377            (Some(tx), Some(utxos), Some(curr_idx)) => (tx, utxos, curr_idx),
1378            _ => return Satisfaction::impossible(),
1379        };
1380        let env = match TxEnv::new(tx, utxos, curr_idx) {
1381            Some(env) => env,
1382            None => return Satisfaction::impossible(),
1383        };
1384        self.satisfy_helper(&env, sat)
1385            .unwrap_or(Satisfaction::empty())
1386    }
1387
1388    fn dissatisfy<Pk, S>(&self, _sat: &S) -> Satisfaction
1389    where
1390        Pk: ToPublicKey,
1391        S: Satisfier<Pk>,
1392    {
1393        // Impossible
1394        Satisfaction::impossible()
1395    }
1396
1397    fn push_to_builder(&self, builder: elements::script::Builder) -> elements::script::Builder {
1398        self.push_to_builder(builder)
1399    }
1400
1401    fn from_token_iter(tokens: &mut TokenIter<'_>) -> Result<Self, FromTokenIterError> {
1402        let len = tokens.len();
1403        match Self::from_tokens(tokens.as_inner_mut()) {
1404            Some((res, last_pos)) => {
1405                tokens.advance(len - last_pos).ok_or(FromTokenIterError)?;
1406                Ok(res)
1407            }
1408            None => Err(FromTokenIterError),
1409        }
1410    }
1411
1412    fn evaluate(
1413        &self,
1414        stack: &mut interpreter::Stack,
1415        txenv: Option<&TxEnv>,
1416    ) -> Result<bool, interpreter::Error> {
1417        let txenv = txenv
1418            .as_ref()
1419            .ok_or(interpreter::Error::ArithError(EvalError::TxEnvNotPresent))?;
1420
1421        match self.eval(txenv, stack) {
1422            Ok(true) => {
1423                stack.push(interpreter::Element::Satisfied);
1424                Ok(true)
1425            }
1426            Ok(false) => {
1427                stack.push(interpreter::Element::Dissatisfied);
1428                Ok(false)
1429            }
1430            Err(e) => Err(interpreter::Error::ArithError(e)),
1431        }
1432    }
1433}
1434
1435/// Evaluation Errors
1436#[derive(Debug, Eq, PartialEq, Ord, PartialOrd, Hash, Clone)]
1437pub enum EvalError {
1438    /// Transaction and utxos not supplied in interpreter
1439    TxEnvNotPresent,
1440    /// Utxo index out of bounds (index, uxtos.len())
1441    UtxoIndexOutOfBounds(usize, usize),
1442    /// Input at index must be explicit
1443    NonExplicitInput(usize),
1444    /// Output index out of bounds (index, tx.outputs.len())
1445    OutputIndexOutOfBounds(usize, usize),
1446    /// Output at index must be explicit
1447    NonExplicitOutput(usize),
1448    /// Output index out of bounds (index, tx.inputs.len())
1449    InputIndexOutOfBounds(usize, usize),
1450    /// Input issuance at index must be explicit
1451    NonExplicitInputIssuance(usize),
1452    /// Input reissuance at index must be explicit
1453    NonExplicitInputReIssuance(usize),
1454    /// Addition overflow
1455    AddOverflow(i64, i64),
1456    /// Addition overflow
1457    SubOverflow(i64, i64),
1458    /// Sub overflow
1459    MulOverflow(i64, i64),
1460    /// Mul overflow
1461    DivOverflow(i64, i64),
1462    /// Mod overflow
1463    ModOverflow(i64, i64),
1464    /// Neg overflow
1465    NegOverflow(i64),
1466    /// Missing price
1467    MissingPrice,
1468    /// Price 8 byte push
1469    Price8BytePush,
1470    /// Missing timestamp
1471    MissingTimestamp,
1472    /// Timestamp 8 byte push
1473    Timstamp8BytePush,
1474    /// Missing Oracle signature
1475    MissingOracleSignature,
1476    /// Missing Oracle pubkey
1477    MalformedSig,
1478    /// Timestamp in future
1479    TimestampInFuture,
1480    /// Invalid oracle signature
1481    InvalidSignature,
1482    /// Price overflow
1483    PriceOverflow,
1484}
1485
1486impl error::Error for EvalError {}
1487
1488impl fmt::Display for EvalError {
1489    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1490        match self {
1491            EvalError::UtxoIndexOutOfBounds(i, len) => {
1492                write!(f, "Utxo index {} out of bounds {}", i, len)
1493            }
1494            EvalError::NonExplicitInput(i) => write!(f, "Non explicit input {}", i),
1495            EvalError::OutputIndexOutOfBounds(i, len) => {
1496                write!(f, "Output index {} out of bounds {}", i, len)
1497            }
1498            EvalError::NonExplicitOutput(i) => {
1499                write!(f, "Non explicit output amount at index {}", i)
1500            }
1501            EvalError::InputIndexOutOfBounds(i, len) => {
1502                write!(f, "Input index {} out of bounds {}", i, len)
1503            }
1504            EvalError::NonExplicitInputIssuance(i) => {
1505                write!(f, "Non explicit input issuance amount at index {}", i)
1506            }
1507            EvalError::NonExplicitInputReIssuance(i) => {
1508                write!(f, "Non explicit input reissuance amount at index {}", i)
1509            }
1510            EvalError::AddOverflow(x, y) => write!(f, "Add overflow {} {}", x, y),
1511            EvalError::SubOverflow(x, y) => write!(f, "Sub overflow {} {}", x, y),
1512            EvalError::MulOverflow(x, y) => write!(f, "Mul overflow {} {}", x, y),
1513            EvalError::DivOverflow(x, y) => write!(f, "Div overflow {} {}", x, y),
1514            EvalError::ModOverflow(x, y) => write!(f, "Mod overflow {} {}", x, y),
1515            EvalError::NegOverflow(x) => write!(f, "Neg overflow {}", x),
1516            EvalError::TxEnvNotPresent => write!(
1517                f,
1518                "Transaction must be supplied to extension to arithmetic evaluation"
1519            ),
1520            EvalError::MissingPrice => write!(f, "Missing price"),
1521            EvalError::Price8BytePush => write!(f, "Price 8 byte push"),
1522            EvalError::MissingTimestamp => write!(f, "Missing timestamp"),
1523            EvalError::Timstamp8BytePush => write!(f, "Timestamp 8 byte push"),
1524            EvalError::MissingOracleSignature => write!(f, "Missing price oracle signature"),
1525            EvalError::MalformedSig => write!(f, "Malformed price oracle signature"),
1526            EvalError::TimestampInFuture => write!(f, "Oracle Timestamp in future"),
1527            EvalError::InvalidSignature => write!(f, "Invalid price oracle signature"),
1528            EvalError::PriceOverflow => write!(f, "Price overflow (must be 64 bit integer)"),
1529        }
1530    }
1531}
1532
1533impl<PArg, QArg> TranslateExtParam<PArg, QArg> for Arith<PArg>
1534where
1535    PArg: ExtParam,
1536    QArg: ExtParam,
1537{
1538    type Output = Arith<QArg>;
1539
1540    fn translate_ext<T, E>(&self, t: &mut T) -> Result<Self::Output, E>
1541    where
1542        T: ExtParamTranslator<PArg, QArg, E>,
1543    {
1544        let res = match &self.expr {
1545            ArithInner::Eq(a, b) => ArithInner::Eq(a.translate_ext(t)?, b.translate_ext(t)?),
1546            ArithInner::Lt(a, b) => ArithInner::Lt(a.translate_ext(t)?, b.translate_ext(t)?),
1547            ArithInner::Leq(a, b) => ArithInner::Leq(a.translate_ext(t)?, b.translate_ext(t)?),
1548            ArithInner::Gt(a, b) => ArithInner::Gt(a.translate_ext(t)?, b.translate_ext(t)?),
1549            ArithInner::Geq(a, b) => ArithInner::Geq(a.translate_ext(t)?, b.translate_ext(t)?),
1550        };
1551        Ok(Arith::new(res).expect("Type check must succeed"))
1552    }
1553}
1554
1555impl<PArg, QArg> TranslateExtParam<PArg, QArg> for Expr<PArg>
1556where
1557    PArg: ExtParam,
1558    QArg: ExtParam,
1559{
1560    type Output = Expr<QArg>;
1561
1562    fn translate_ext<T, E>(&self, t: &mut T) -> Result<Self::Output, E>
1563    where
1564        T: ExtParamTranslator<PArg, QArg, E>,
1565    {
1566        match &self.inner {
1567            ExprInner::Const(c) => Ok(Expr::from_inner(ExprInner::Const(*c))),
1568            ExprInner::CurrInputIdx => Ok(Expr::from_inner(ExprInner::CurrInputIdx)),
1569            ExprInner::Input(i) => Ok(Expr::from_inner(ExprInner::Input(i.clone()))),
1570            ExprInner::Output(i) => Ok(Expr::from_inner(ExprInner::Output(i.clone()))),
1571            ExprInner::InputIssue(i) => Ok(Expr::from_inner(ExprInner::InputIssue(i.clone()))),
1572            ExprInner::InputReIssue(i) => Ok(Expr::from_inner(ExprInner::InputReIssue(i.clone()))),
1573            ExprInner::Add(a, b) => Ok(Expr::from_inner(ExprInner::Add(
1574                Box::new(a.translate_ext(t)?),
1575                Box::new(b.translate_ext(t)?),
1576            ))),
1577            ExprInner::Sub(a, b) => Ok(Expr::from_inner(ExprInner::Sub(
1578                Box::new(a.translate_ext(t)?),
1579                Box::new(b.translate_ext(t)?),
1580            ))),
1581            ExprInner::Mul(a, b) => Ok(Expr::from_inner(ExprInner::Mul(
1582                Box::new(a.translate_ext(t)?),
1583                Box::new(b.translate_ext(t)?),
1584            ))),
1585            ExprInner::Div(a, b) => Ok(Expr::from_inner(ExprInner::Div(
1586                Box::new(a.translate_ext(t)?),
1587                Box::new(b.translate_ext(t)?),
1588            ))),
1589            ExprInner::Mod(a, b) => Ok(Expr::from_inner(ExprInner::Mod(
1590                Box::new(a.translate_ext(t)?),
1591                Box::new(b.translate_ext(t)?),
1592            ))),
1593            ExprInner::BitAnd(a, b) => Ok(Expr::from_inner(ExprInner::BitAnd(
1594                Box::new(a.translate_ext(t)?),
1595                Box::new(b.translate_ext(t)?),
1596            ))),
1597            ExprInner::BitOr(a, b) => Ok(Expr::from_inner(ExprInner::BitOr(
1598                Box::new(a.translate_ext(t)?),
1599                Box::new(b.translate_ext(t)?),
1600            ))),
1601            ExprInner::Xor(a, b) => Ok(Expr::from_inner(ExprInner::Xor(
1602                Box::new(a.translate_ext(t)?),
1603                Box::new(b.translate_ext(t)?),
1604            ))),
1605            ExprInner::Invert(a) => Ok(Expr::from_inner(ExprInner::Invert(Box::new(
1606                a.translate_ext(t)?,
1607            )))),
1608            ExprInner::Negate(a) => Ok(Expr::from_inner(ExprInner::Negate(Box::new(
1609                a.translate_ext(t)?,
1610            )))),
1611            ExprInner::PriceOracle1(pk, time) => {
1612                Ok(Expr::from_inner(ExprInner::PriceOracle1(t.ext(pk)?, *time)))
1613            }
1614            ExprInner::PriceOracle1W(pk, time) => Ok(Expr::from_inner(ExprInner::PriceOracle1W(
1615                t.ext(pk)?,
1616                *time,
1617            ))),
1618        }
1619    }
1620}
1621
1622#[cfg(test)]
1623mod tests {
1624    use bitcoin::hashes::Hash;
1625    use bitcoin::key::XOnlyPublicKey;
1626
1627    use super::*;
1628    use crate::extensions::check_sig_price_oracle_1;
1629    use crate::test_utils::{StrExtTranslator, StrXOnlyKeyTranslator};
1630    use crate::{CovenantExt, Miniscript, Segwitv0, Tap, TranslatePk};
1631
1632    #[test]
1633    fn test_index_ops_with_arith() {
1634        // index ops tests with different index types
1635        _arith_parse("num64_eq(out_v(idx_sub(5,curr_idx)),inp_v(idx_add(0,curr_idx)))");
1636        _arith_parse("num64_eq(out_v(idx_mul(5,curr_idx)),inp_v(idx_div(0,curr_idx)))");
1637
1638        _arith_parse(
1639            "num64_eq(inp_issue_v(idx_sub(5,curr_idx)),inp_reissue_v(idx_add(0,curr_idx)))",
1640        );
1641        _arith_parse(
1642            "num64_eq(inp_issue_v(idx_sub(5,curr_idx)),inp_reissue_v(idx_add(0,curr_idx)))",
1643        );
1644    }
1645
1646    #[test]
1647    fn arith_parse() {
1648        _arith_parse("num64_geq(sub(mul(1,0),mul(0,curr_inp_v)),0)");
1649        _arith_parse("num64_gt(curr_inp_v,mul(1,out_v(0)))");
1650        // This does not test the evaluation
1651        _arith_parse("num64_eq(8,8)");
1652        _arith_parse("num64_gt(9223372036854775807,9223372036854775806)"); // 2**63-1
1653
1654        // negatives and comparisons
1655        _arith_parse("num64_eq(-8,-8)"); // negative nums
1656        _arith_parse("num64_gt(-8,-9)");
1657        _arith_parse("num64_geq(-8,-8)");
1658        _arith_parse("num64_leq(-8,-7)");
1659        _arith_parse("num64_lt(-8,-7)");
1660
1661        // test terminals parsing
1662        _arith_parse("num64_eq(inp_v(0),100)");
1663        _arith_parse("num64_eq(out_v(0),100)");
1664        _arith_parse("num64_eq(inp_issue_v(0),100)");
1665        _arith_parse("num64_eq(inp_reissue_v(0),100)");
1666        _arith_parse("num64_eq(inp_v(0),out_v(0))");
1667        _arith_parse("num64_eq(inp_issue_v(1),inp_reissue_v(1))");
1668
1669        // test combinator
1670        _arith_parse("num64_eq(add(4,3),mul(1,7))");
1671        _arith_parse("num64_eq(sub(3,3),div(0,9))");
1672        _arith_parse("num64_eq(mod(9,3),0)");
1673        _arith_parse("num64_eq(bitand(0,134),0)");
1674        _arith_parse("num64_eq(bitor(1,3),3)");
1675        _arith_parse("num64_eq(bitxor(1,3),2)");
1676        _arith_parse("num64_eq(bitinv(0),-9223372036854775808)");
1677        _arith_parse("num64_eq(neg(1),-1)");
1678
1679        // test some misc combinations with other miniscript fragments
1680        _arith_parse("and_v(v:pk(K),num64_gt(8,7))");
1681        _arith_parse(
1682            "and_v(v:pk(K),num64_eq(mul(inp_v(0),out_v(1)),sub(add(3,inp_issue_v(1)),-9)))",
1683        );
1684
1685        // test price oracles
1686        _arith_parse("num64_eq(price_oracle1(K,123213),28004)");
1687        _arith_parse("num64_eq(price_oracle1(K,123213),price_oracle1_w(K,4318743))");
1688        _arith_parse(
1689            "and_v(v:pk(K),num64_eq(mul(inp_v(0),out_v(1)),sub(add(3,inp_issue_v(1)),price_oracle1_w(K,123213))))",
1690        );
1691        _arith_parse("and_v(v:pk(X2),num64_eq(add(price_oracle1(K,1),0),50000))");
1692    }
1693
1694    fn _arith_parse(s: &str) {
1695        type MsExtStr = Miniscript<String, Tap, CovenantExt<String>>;
1696        type MsExt = Miniscript<XOnlyPublicKey, Tap, CovenantExt<CovExtArgs>>;
1697        type MsExtSegwitv0 = Miniscript<String, Segwitv0, CovenantExt<String>>;
1698
1699        // Make sure that parsing this errors in segwit context
1700        assert!(MsExtSegwitv0::from_str_insane(s).is_err());
1701
1702        let ms = MsExtStr::from_str_insane(s).unwrap();
1703        // test string rtt
1704        assert_eq!(ms.to_string(), s);
1705        let mut t = StrXOnlyKeyTranslator::default();
1706        let mut ext_t = StrExtTranslator::default();
1707        ext_t.ext_map.insert(
1708            String::from("K"),
1709            CovExtArgs::csfs_key(
1710                XOnlyPublicKey::from_str(
1711                    "c304c3b5805eecff054c319c545dc6ac2ad44eb70f79dd9570e284c5a62c0f9e",
1712                )
1713                .unwrap(),
1714            ),
1715        );
1716        // use crate::extensions::param::TranslateExtParam;
1717        let ms = ms.translate_pk(&mut t).unwrap();
1718        let ms = TranslateExt::translate_ext(&ms, &mut ext_t).unwrap();
1719        // script rtt
1720        assert_eq!(ms, MsExt::parse_insane(&ms.encode()).unwrap());
1721    }
1722
1723    #[test]
1724    fn test_fuji_fixed_signs() {
1725        // Test Vector obtained from curl queries
1726        let sig = elements::secp256k1_zkp::schnorr::Signature::from_str("8fc6e217b0e1d3481855cdb97cfe333999d4cf48b9f58b4f299ad86fd768a345e97a953d6efa1ca5971f18810deedcfddc4c2bd4e8f9d1431c1ad6ebafa013a9").unwrap();
1727        let pk = elements::secp256k1_zkp::XOnlyPublicKey::from_str(
1728            "c304c3b5805eecff054c319c545dc6ac2ad44eb70f79dd9570e284c5a62c0f9e",
1729        )
1730        .unwrap();
1731
1732        let timestamp: u64 = 1679531858733;
1733        let price: u64 = 27365;
1734        let secp = elements::secp256k1_zkp::Secp256k1::new();
1735        assert!(check_sig_price_oracle_1(&secp, &sig, &pk, timestamp, price))
1736    }
1737}
elements_miniscript/extensions/arith.rs

elements_miniscript/extensions/
arith.rs
