Repository: ergoplatform/sigma-rust (language: rust)

Issue:
Fix executeFromVar/executeFromReg
executeFromVar and executeFromReg execute Exprs from context vars/registers. This is implemented by replacing instances of DeserializeContext/DeserializeRegister nodes with exprs during deserialization. In sigma-rust however this is done during evaluation:
https://github.com/ergoplatform/sigma-rust/blob/e56e6faf0b835b2f54a247636a7be05871eeaf15/ergotree-interpreter/src/eval/deserialize_context.rs#L13-L42


Which makes recursion (and stack overflows) possible: 

```rust
    #[test]
    fn eval_recursive() {
        let expr: Expr = DeserializeContext {
            tpe: SType::SBoolean,
            id: 1,
        }
        .into();
        let ctx_ext = ContextExtension {
            values: [(1u8, expr.sigma_serialize_bytes().unwrap().into())]
                .iter()
                .cloned()
                .collect(),
        };
        assert!(try_eval_out_wo_ctx::<bool>(&expr, &ctx).unwrap());
    }
```

ExecuteFromVar's implementation should instead match sigmastate-interpreters, [Reference](https://github.com/ScorexFoundation/sigmastate-interpreter/blob/develop/interpreter/shared/src/main/scala/sigmastate/interpreter/Interpreter.scala#L149). DeserializeContext and DeserializeRegister should also not implement Evaluable


Discussion / hints:

Fix patch:
diff --git a/bindings/ergo-lib-c-core/src/context_extension.rs b/bindings/ergo-lib-c-core/src/context_extension.rs
index 8ca65836b..3b3bd2cbc 100644
--- a/bindings/ergo-lib-c-core/src/context_extension.rs
+++ b/bindings/ergo-lib-c-core/src/context_extension.rs
@@ -3,11 +3,11 @@ use crate::{
     util::{const_ptr_as_ref, mut_ptr_as_mut},
     Error,
 };
-use ergo_lib::ergotree_interpreter::sigma_protocol::prover;
+use ergo_lib::ergotree_ir::chain::context_extension;
 
 /// User-defined variables to be put into context
 #[derive(PartialEq, Eq, Debug, Clone)]
-pub struct ContextExtension(pub prover::ContextExtension);
+pub struct ContextExtension(pub context_extension::ContextExtension);
 pub type ContextExtensionPtr = *mut ContextExtension;
 pub type ConstContextExtensionPtr = *const ContextExtension;
 
@@ -17,7 +17,7 @@ pub unsafe fn context_extension_empty(
 ) -> Result<(), Error> {
     let context_extension_out = mut_ptr_as_mut(context_extension_out, "context_extension_out")?;
     *context_extension_out = Box::into_raw(Box::new(ContextExtension(
-        prover::ContextExtension::empty(),
+        context_extension::ContextExtension::empty(),
     )));
     Ok(())
 }
diff --git a/bindings/ergo-lib-wasm/src/context_extension.rs b/bindings/ergo-lib-wasm/src/context_extension.rs
index e2eeaf27f..a6128f519 100644
--- a/bindings/ergo-lib-wasm/src/context_extension.rs
+++ b/bindings/ergo-lib-wasm/src/context_extension.rs
@@ -10,16 +10,14 @@ use derive_more::{From, Into};
 /// User-defined variables to be put into context
 #[wasm_bindgen]
 #[derive(PartialEq, Eq, Debug, Clone, From, Into)]
-pub struct ContextExtension(
-    ergo_lib::ergotree_interpreter::sigma_protocol::prover::ContextExtension,
-);
+pub struct ContextExtension(ergo_lib::ergotree_ir::chain::context_extension::ContextExtension);
 
 #[wasm_bindgen]
 impl ContextExtension {
     /// Create new ContextExtension instance
     #[wasm_bindgen(constructor)]
     pub fn new() -> Self {
-        Self(ergo_lib::ergotree_interpreter::sigma_protocol::prover::ContextExtension::empty())
+        Self(ergo_lib::ergotree_ir::chain::context_extension::ContextExtension::empty())
     }
 
     /// Set the supplied pair in the ContextExtension
@@ -29,13 +27,11 @@ impl ContextExtension {
 
     /// Returns the number of elements in the collection
     pub fn len(&self) -> usize {
-        let wrapped: ergo_lib::ergotree_interpreter::sigma_protocol::prover::ContextExtension =
-            self.0.clone();
-        wrapped.values.len()
+        self.0.values.len()
     }
     /// get from map or fail if key is missing
     pub fn get(&self, key: u8) -> Result<Constant, JsValue> {
-        let wrapped: ergo_lib::ergotree_interpreter::sigma_protocol::prover::ContextExtension =
+        let wrapped: ergo_lib::ergotree_ir::chain::context_extension::ContextExtension =
             self.0.clone();
         Ok(wrapped
             .values
@@ -47,7 +43,7 @@ impl ContextExtension {
 
     /// Returns all keys in the map
     pub fn keys(&self) -> Vec<u8> {
-        let wrapped: ergo_lib::ergotree_interpreter::sigma_protocol::prover::ContextExtension =
+        let wrapped: ergo_lib::ergotree_ir::chain::context_extension::ContextExtension =
             self.0.clone();
         wrapped.values.keys().cloned().collect()
     }
diff --git a/ergo-chain-generation/src/chain_generation.rs b/ergo-chain-generation/src/chain_generation.rs
index 5e1d8e06d..eb00e088c 100644
--- a/ergo-chain-generation/src/chain_generation.rs
+++ b/ergo-chain-generation/src/chain_generation.rs
@@ -3,6 +3,7 @@
 
 use std::convert::TryFrom;
 
+use ergo_lib::ergotree_ir::chain::context_extension::ContextExtension;
 use ergo_lib::{
     chain::{
         ergo_box::box_builder::ErgoBoxCandidateBuilder,
@@ -12,10 +13,7 @@ use ergo_lib::{
 };
 use ergo_lib::{
     ergo_chain_types::ADDigest,
-    ergotree_interpreter::sigma_protocol::{
-        private_input::DlogProverInput,
-        prover::{ContextExtension, ProofBytes},
-    },
+    ergotree_interpreter::sigma_protocol::{private_input::DlogProverInput, prover::ProofBytes},
 };
 use ergo_lib::{
     ergo_chain_types::{blake2b256_hash, AutolykosSolution, Header, Votes},
diff --git a/ergo-lib/src/chain/json/context_extension.rs b/ergo-lib/src/chain/json/context_extension.rs
index 4b74f6233..fe2c85af5 100644
--- a/ergo-lib/src/chain/json/context_extension.rs
+++ b/ergo-lib/src/chain/json/context_extension.rs
@@ -1,4 +1,4 @@
-use ergotree_interpreter::sigma_protocol::prover::ContextExtension;
+use ergotree_ir::chain::context_extension::ContextExtension;
 use ergotree_ir::{mir::constant::Constant, serialization::SigmaSerializable};
 use indexmap::IndexMap;
 use serde::{ser::SerializeMap, Deserialize, Serialize};
diff --git a/ergo-lib/src/chain/transaction.rs b/ergo-lib/src/chain/transaction.rs
index 0beb6fe9a..c9d9ec24f 100644
--- a/ergo-lib/src/chain/transaction.rs
+++ b/ergo-lib/src/chain/transaction.rs
@@ -9,8 +9,6 @@ pub mod unsigned;
 
 use bounded_vec::BoundedVec;
 use ergo_chain_types::blake2b256_hash;
-use ergotree_interpreter::eval::context::Context;
-pub use ergotree_interpreter::eval::context::TxIoVec;
 use ergotree_interpreter::eval::env::Env;
 use ergotree_interpreter::eval::extract_sigma_boolean;
 use ergotree_interpreter::eval::EvalError;
@@ -20,6 +18,8 @@ use ergotree_interpreter::sigma_protocol::verifier::TestVerifier;
 use ergotree_interpreter::sigma_protocol::verifier::VerificationResult;
 use ergotree_interpreter::sigma_protocol::verifier::Verifier;
 use ergotree_interpreter::sigma_protocol::verifier::VerifierError;
+use ergotree_ir::chain::context::Context;
+pub use ergotree_ir::chain::context::TxIoVec;
 use ergotree_ir::chain::ergo_box::BoxId;
 use ergotree_ir::chain::ergo_box::ErgoBox;
 use ergotree_ir::chain::ergo_box::ErgoBoxCandidate;
diff --git a/ergo-lib/src/chain/transaction/ergo_transaction.rs b/ergo-lib/src/chain/transaction/ergo_transaction.rs
index fca824028..3da6db931 100644
--- a/ergo-lib/src/chain/transaction/ergo_transaction.rs
+++ b/ergo-lib/src/chain/transaction/ergo_transaction.rs
@@ -1,8 +1,6 @@
 //! Exposes common properties for signed and unsigned transactions
-use ergotree_interpreter::sigma_protocol::{
-    prover::ContextExtension,
-    verifier::{VerificationResult, VerifierError},
-};
+use ergotree_interpreter::sigma_protocol::verifier::{VerificationResult, VerifierError};
+use ergotree_ir::chain::context_extension::ContextExtension;
 use ergotree_ir::{
     chain::{
         ergo_box::{box_value::BoxValue, BoxId, ErgoBox},
diff --git a/ergo-lib/src/chain/transaction/input.rs b/ergo-lib/src/chain/transaction/input.rs
index d854f7f7f..21f194cc9 100644
--- a/ergo-lib/src/chain/transaction/input.rs
+++ b/ergo-lib/src/chain/transaction/input.rs
@@ -2,8 +2,8 @@
 
 pub mod prover_result;
 
-use ergotree_interpreter::sigma_protocol::prover::ContextExtension;
 use ergotree_interpreter::sigma_protocol::prover::ProofBytes;
+use ergotree_ir::chain::context_extension::ContextExtension;
 use ergotree_ir::chain::ergo_box::BoxId;
 use ergotree_ir::serialization::sigma_byte_reader::SigmaByteRead;
 use ergotree_ir::serialization::sigma_byte_writer::SigmaByteWrite;
diff --git a/ergo-lib/src/chain/transaction/input/prover_result.rs b/ergo-lib/src/chain/transaction/input/prover_result.rs
index 20f2b2699..6aa0be88d 100644
--- a/ergo-lib/src/chain/transaction/input/prover_result.rs
+++ b/ergo-lib/src/chain/transaction/input/prover_result.rs
@@ -1,7 +1,7 @@
 //! Proof generated by the prover in Sigma protocol
 
-use ergotree_interpreter::sigma_protocol::prover::ContextExtension;
 use ergotree_interpreter::sigma_protocol::prover::ProofBytes;
+use ergotree_ir::chain::context_extension::ContextExtension;
 use ergotree_ir::serialization::sigma_byte_reader::SigmaByteRead;
 use ergotree_ir::serialization::sigma_byte_writer::SigmaByteWrite;
 use ergotree_ir::serialization::SigmaParsingError;
diff --git a/ergo-lib/src/chain/transaction/input/prover_result/json.rs b/ergo-lib/src/chain/transaction/input/prover_result/json.rs
index 858cf5f8f..b9aae483a 100644
--- a/ergo-lib/src/chain/transaction/input/prover_result/json.rs
+++ b/ergo-lib/src/chain/transaction/input/prover_result/json.rs
@@ -1,7 +1,7 @@
 use std::str::FromStr;
 
 use crate::chain::json::context_extension::ContextExtensionSerde;
-use ergotree_interpreter::sigma_protocol::prover::ContextExtension;
+use ergotree_ir::chain::context_extension::ContextExtension;
 use serde::ser::SerializeStruct;
 use serde::Serialize;
 
diff --git a/ergo-lib/src/chain/transaction/reduced.rs b/ergo-lib/src/chain/transaction/reduced.rs
index b9d4e0d83..e77bb7c7a 100644
--- a/ergo-lib/src/chain/transaction/reduced.rs
+++ b/ergo-lib/src/chain/transaction/reduced.rs
@@ -2,8 +2,8 @@
 //! is augmented with ReducedInput which contains a script reduction result.
 
 use ergotree_interpreter::eval::reduce_to_crypto;
-use ergotree_interpreter::sigma_protocol::prover::ContextExtension;
 use ergotree_interpreter::sigma_protocol::prover::ProverError;
+use ergotree_ir::chain::context_extension::ContextExtension;
 use ergotree_ir::serialization::sigma_byte_reader::SigmaByteRead;
 use ergotree_ir::serialization::sigma_byte_writer::SigmaByteWrite;
 use ergotree_ir::serialization::SigmaParsingError;
@@ -78,12 +78,7 @@ pub fn reduce_tx(
             let input_box = tx_context
                 .get_input_box(&input.box_id)
                 .ok_or(TransactionContextError::InputBoxNotFound(idx))?;
-            let expr = input_box
-                .ergo_tree
-                .proposition()
-                .map_err(ProverError::ErgoTreeError)
-                .map_err(|e| TxSigningError::ProverError(e, idx))?;
-            let reduction_result = reduce_to_crypto(&expr, &ctx)
+            let reduction_result = reduce_to_crypto(&input_box.ergo_tree, &ctx)
                 .map_err(ProverError::EvalError)
                 .map_err(|e| TxSigningError::ProverError(e, idx))?;
             Ok(ReducedInput {
diff --git a/ergo-lib/src/chain/transaction/storage_rent.rs b/ergo-lib/src/chain/transaction/storage_rent.rs
index 8a7c469b6..b333fdb24 100644
--- a/ergo-lib/src/chain/transaction/storage_rent.rs
+++ b/ergo-lib/src/chain/transaction/storage_rent.rs
@@ -1,4 +1,5 @@
-use ergotree_interpreter::{eval::context::Context, sigma_protocol::prover::ProofBytes};
+use ergotree_interpreter::sigma_protocol::prover::ProofBytes;
+use ergotree_ir::chain::context::Context;
 use ergotree_ir::chain::ergo_box::ErgoBox;
 use ergotree_ir::{
     chain::ergo_box::RegisterId, mir::constant::TryExtractInto, serialization::SigmaSerializable,
diff --git a/ergo-lib/src/wallet/multi_sig.rs b/ergo-lib/src/wallet/multi_sig.rs
index ef464fd51..92513aea1 100644
--- a/ergo-lib/src/wallet/multi_sig.rs
+++ b/ergo-lib/src/wallet/multi_sig.rs
@@ -251,12 +251,7 @@ pub fn generate_commitments(
         let input_box = tx_context
             .get_input_box(&input.box_id)
             .ok_or(TransactionContextError::InputBoxNotFound(i))?;
-        let tree = input_box.ergo_tree.clone();
-        let exp = tree
-            .proposition()
-            .map_err(ProverError::ErgoTreeError)
-            .map_err(|e| TxSigningError::ProverError(e, i))?;
-        let reduction_result = reduce_to_crypto(&exp, &ctx)
+        let reduction_result = reduce_to_crypto(&input_box.ergo_tree, &ctx)
             .map_err(ProverError::EvalError)
             .map_err(|e| TxSigningError::ProverError(e, i))?;
 
@@ -280,12 +275,7 @@ pub fn extract_hints(
         let input_box = tx_context
             .get_input_box(&input.box_id)
             .ok_or(TransactionContextError::InputBoxNotFound(i))?;
-        let tree = input_box.ergo_tree.clone();
-        let exp = tree
-            .proposition()
-            .map_err(ProverError::ErgoTreeError)
-            .map_err(|e| TxSigningError::ProverError(e, i))?;
-        let reduction_result = reduce_to_crypto(&exp, &ctx)
+        let reduction_result = reduce_to_crypto(&input_box.ergo_tree, &ctx)
             .map_err(ProverError::EvalError)
             .map_err(|e| TxSigningError::ProverError(e, i))?;
         let sigma_tree = reduction_result.sigma_prop;
@@ -389,7 +379,6 @@ pub fn generate_commitments_for(
 mod tests {
     use super::*;
     use crate::chain::transaction::Transaction;
-    use crate::ergotree_interpreter::eval::context::Context;
     use crate::ergotree_interpreter::eval::reduce_to_crypto;
     use crate::ergotree_interpreter::sigma_protocol::private_input::{
         DlogProverInput, PrivateInput,
@@ -406,6 +395,7 @@ mod tests {
     use ergo_chain_types::Base16DecodedBytes;
     use ergotree_interpreter::sigma_protocol::private_input::DhTupleProverInput;
     use ergotree_interpreter::sigma_protocol::wscalar::Wscalar;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::atleast::Atleast;
     use ergotree_ir::mir::constant::{Constant, Literal};
     use ergotree_ir::mir::sigma_or::SigmaOr;
@@ -466,8 +456,7 @@ mod tests {
         let tree_m: ErgoTree = ErgoTree::sigma_parse_bytes(&bytes_m.0).unwrap();
 
         let contx = force_any_val::<Context>();
-        let exp = tree_m.proposition().unwrap();
-        let reduction_result = reduce_to_crypto(&exp, &contx).unwrap();
+        let reduction_result = reduce_to_crypto(&tree_m, &contx).unwrap();
         let sigma_tree = reduction_result.sigma_prop;
         let stx: Transaction = serde_json::from_str(signed_tx).unwrap();
         let test: ProofBytes = stx.inputs.first().clone().spending_proof.proof;
@@ -675,7 +664,7 @@ mod tests {
         .into();
         let tree_and = ErgoTree::try_from(expr.clone()).unwrap();
 
-        let cand = reduce_to_crypto(&expr, &ctx).unwrap().sigma_prop;
+        let cand = reduce_to_crypto(&tree_and, &ctx).unwrap().sigma_prop;
         let generate_for: Vec<SigmaBoolean> = vec![SigmaBoolean::ProofOfKnowledge(
             SigmaProofOfKnowledgeTree::ProveDlog(pk2),
         )];
@@ -747,7 +736,7 @@ mod tests {
 
         let tree_expr = ErgoTree::try_from(expr.clone()).unwrap();
 
-        let expr_reduced = reduce_to_crypto(&expr, &ctx).unwrap().sigma_prop;
+        let expr_reduced = reduce_to_crypto(&tree_expr, &ctx).unwrap().sigma_prop;
         let mut generate_for: Vec<SigmaBoolean> = vec![SigmaBoolean::ProofOfKnowledge(
             SigmaProofOfKnowledgeTree::ProveDlog(pk2),
         )];
@@ -882,7 +871,7 @@ mod tests {
         .into();
         let exp: Expr = SigmaAnd::new(vec![first_expr, second_expr]).unwrap().into();
         let tree = ErgoTree::try_from(exp.clone()).unwrap();
-        let ctree = reduce_to_crypto(&exp, &ctx).unwrap().sigma_prop;
+        let ctree = reduce_to_crypto(&tree, &ctx).unwrap().sigma_prop;
         let mut generate_for: Vec<SigmaBoolean> = vec![SigmaBoolean::ProofOfKnowledge(
             SigmaProofOfKnowledgeTree::ProveDlog(pk_alice.clone()),
         )];
@@ -993,7 +982,7 @@ mod tests {
 
         let tree_expr = ErgoTree::try_from(expr.clone()).unwrap();
 
-        let expr_reduced = reduce_to_crypto(&expr, &ctx).unwrap().sigma_prop;
+        let expr_reduced = reduce_to_crypto(&tree_expr, &ctx).unwrap().sigma_prop;
         let message = vec![0u8; 100];
 
         let hints_from_bob: HintsBag = generate_commitments_for(&expr_reduced, &[bob_pk.into()]);
@@ -1089,7 +1078,7 @@ mod tests {
 
         let tree_expr = ErgoTree::try_from(expr.clone()).unwrap();
 
-        let expr_reduced = reduce_to_crypto(&expr, &ctx).unwrap().sigma_prop;
+        let expr_reduced = reduce_to_crypto(&tree_expr, &ctx).unwrap().sigma_prop;
         let message = vec![0u8; 100];
 
         let bob_hints: HintsBag = generate_commitments_for(&expr_reduced, &[bob_pk.into()]);
@@ -1262,7 +1251,7 @@ mod tests {
         .into();
         let expr: Expr = Atleast::new(bound, input).unwrap().into();
         let tree_expr = ErgoTree::try_from(expr.clone()).unwrap();
-        let expr_reduced = reduce_to_crypto(&expr, &ctx).unwrap().sigma_prop;
+        let expr_reduced = reduce_to_crypto(&tree_expr, &ctx).unwrap().sigma_prop;
         let message = vec![0u8; 100];
 
         // only actors 1, 2, 3, 4, 5, 6, 7 are signing, others are simulated (see bag_one below)
diff --git a/ergo-lib/src/wallet/signing.rs b/ergo-lib/src/wallet/signing.rs
index a08663edc..28283f41c 100644
--- a/ergo-lib/src/wallet/signing.rs
+++ b/ergo-lib/src/wallet/signing.rs
@@ -14,11 +14,11 @@ use ergotree_ir::sigma_protocol::sigma_boolean::SigmaBoolean;
 
 use crate::chain::transaction::storage_rent::check_storage_rent_conditions;
 use crate::wallet::multi_sig::TransactionHintsBag;
-use ergotree_interpreter::eval::context::Context;
 use ergotree_interpreter::sigma_protocol::prover::ProofBytes;
 use ergotree_interpreter::sigma_protocol::prover::Prover;
 use ergotree_interpreter::sigma_protocol::prover::ProverError;
 use ergotree_interpreter::sigma_protocol::prover::ProverResult;
+use ergotree_ir::chain::context::Context;
 use thiserror::Error;
 
 pub use super::tx_context::TransactionContext;
@@ -260,10 +260,8 @@ pub fn sign_tx_input<'ctx>(
 #[allow(clippy::unwrap_used, clippy::panic)]
 mod tests {
     use super::*;
-    use ergotree_interpreter::eval::context::TxIoVec;
     use ergotree_interpreter::sigma_protocol::private_input::DlogProverInput;
     use ergotree_interpreter::sigma_protocol::private_input::PrivateInput;
-    use ergotree_interpreter::sigma_protocol::prover::ContextExtension;
     use ergotree_interpreter::sigma_protocol::prover::TestProver;
     use ergotree_interpreter::sigma_protocol::verifier::verify_signature;
     use ergotree_interpreter::sigma_protocol::verifier::TestVerifier;
@@ -271,6 +269,8 @@ mod tests {
     use ergotree_interpreter::sigma_protocol::verifier::VerifierError;
     use ergotree_ir::chain::address::AddressEncoder;
     use ergotree_ir::chain::address::NetworkPrefix;
+    use ergotree_ir::chain::context::TxIoVec;
+    use ergotree_ir::chain::context_extension::ContextExtension;
     use ergotree_ir::chain::ergo_box::box_value::BoxValue;
     use ergotree_ir::chain::ergo_box::ErgoBox;
     use ergotree_ir::chain::ergo_box::NonMandatoryRegisters;
diff --git a/ergo-lib/src/wallet/tx_builder.rs b/ergo-lib/src/wallet/tx_builder.rs
index 98160ec93..160ca279a 100644
--- a/ergo-lib/src/wallet/tx_builder.rs
+++ b/ergo-lib/src/wallet/tx_builder.rs
@@ -1,7 +1,7 @@
 //! Builder for an UnsignedTransaction
 
-use ergotree_interpreter::eval::context::TxIoVec;
-use ergotree_interpreter::sigma_protocol::prover::ContextExtension;
+use ergotree_ir::chain::context::TxIoVec;
+use ergotree_ir::chain::context_extension::ContextExtension;
 use ergotree_ir::chain::token::TokenAmount;
 use ergotree_ir::chain::token::TokenAmountError;
 use ergotree_ir::ergo_tree::ErgoTree;
diff --git a/ergo-lib/src/wallet/tx_context.rs b/ergo-lib/src/wallet/tx_context.rs
index 382d473cb..88b583c30 100644
--- a/ergo-lib/src/wallet/tx_context.rs
+++ b/ergo-lib/src/wallet/tx_context.rs
@@ -7,8 +7,8 @@ use crate::chain::ergo_state_context::ErgoStateContext;
 use crate::chain::transaction::ergo_transaction::{ErgoTransaction, TxValidationError};
 use crate::chain::transaction::{verify_tx_input_proof, Transaction, TransactionError};
 use crate::ergotree_ir::chain::ergo_box::BoxId;
-use ergotree_interpreter::eval::context::TxIoVec;
 use ergotree_interpreter::sigma_protocol::verifier::VerificationResult;
+use ergotree_ir::chain::context::TxIoVec;
 use ergotree_ir::chain::ergo_box::box_value::BoxValue;
 use ergotree_ir::chain::ergo_box::{BoxTokens, ErgoBox};
 use ergotree_ir::chain::token::{TokenAmount, TokenId};
@@ -288,8 +288,9 @@ pub enum TransactionContextError {
 mod test {
     use std::collections::HashMap;
 
-    use ergotree_interpreter::eval::context::TxIoVec;
-    use ergotree_interpreter::sigma_protocol::prover::{ContextExtension, ProofBytes};
+    use ergotree_interpreter::sigma_protocol::prover::ProofBytes;
+    use ergotree_ir::chain::context::TxIoVec;
+    use ergotree_ir::chain::context_extension::ContextExtension;
     use ergotree_ir::chain::ergo_box::arbitrary::ArbBoxParameters;
     use ergotree_ir::chain::ergo_box::box_value::BoxValue;
     use ergotree_ir::chain::ergo_box::{
diff --git a/ergo-p2p/src/message/handshake.rs b/ergo-p2p/src/message/handshake.rs
index 4a3821cea..290813b47 100644
--- a/ergo-p2p/src/message/handshake.rs
+++ b/ergo-p2p/src/message/handshake.rs
@@ -9,6 +9,8 @@ use crate::PeerSpec;
 /// peerSpec - general (declared) information about peer
 /// time     - handshake time
 pub struct Handshake {
+    /// Peer specification
     pub peer_spec: PeerSpec,
+    /// Handshake time
     pub time: SystemTime,
 }
diff --git a/ergotree-interpreter/src/eval.rs b/ergotree-interpreter/src/eval.rs
index 80eb1d597..d043ebdee 100644
--- a/ergotree-interpreter/src/eval.rs
+++ b/ergotree-interpreter/src/eval.rs
@@ -1,4 +1,5 @@
 //! Interpreter
+use ergotree_ir::ergo_tree::ErgoTree;
 use ergotree_ir::mir::constant::TryExtractInto;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaProp;
 use std::fmt::Display;
@@ -9,11 +10,9 @@ use ergotree_ir::sigma_protocol::sigma_boolean::SigmaBoolean;
 
 use ergotree_ir::types::smethod::SMethod;
 
-use self::context::Context;
 use self::env::Env;
+use ergotree_ir::chain::context::Context;
 
-/// Context(blockchain) for the interpreter
-pub mod context;
 /// Environment for
 pub mod env;
 
@@ -124,7 +123,7 @@ pub struct ReductionResult {
 }
 
 /// Evaluate the given expression by reducing it to SigmaBoolean value.
-pub fn reduce_to_crypto(expr: &Expr, ctx: &Context) -> Result<ReductionResult, EvalError> {
+pub fn reduce_to_crypto(tree: &ErgoTree, ctx: &Context) -> Result<ReductionResult, EvalError> {
     fn inner<'ctx>(expr: &'ctx Expr, ctx: &Context<'ctx>) -> Result<ReductionResult, EvalError> {
         let mut env_mut = Env::empty();
         expr.eval(&mut env_mut, ctx)
@@ -151,7 +150,13 @@ pub fn reduce_to_crypto(expr: &Expr, ctx: &Context) -> Result<ReductionResult, E
             })
     }
 
-    let res = inner(expr, ctx);
+    let expr = tree.proposition()?;
+    let expr = if tree.has_deserialize() {
+        expr.substitute_deserialize(ctx)?
+    } else {
+        expr
+    };
+    let res = inner(&expr, ctx);
     if let Ok(reduction) = res {
         if reduction.sigma_prop == SigmaBoolean::TrivialProp(false) {
             let (_, printed_expr_str) = expr
@@ -403,6 +408,15 @@ pub(crate) mod tests {
         })
     }
 
+    /// Eval expr, performing deserialize node substitution before evaluation
+    pub fn try_eval_with_deserialize<'ctx, T: TryExtractFrom<Value<'static>> + 'static>(
+        expr: &Expr,
+        ctx: &'ctx Context<'ctx>,
+    ) -> Result<T, EvalError> {
+        let expr = expr.clone().substitute_deserialize(ctx)?;
+        try_eval_out(&expr, ctx)
+    }
+
     // Evaluate with activated version (set block version to version + 1)
     pub fn try_eval_out_with_version<'ctx, T: TryExtractFrom<Value<'static>> + 'static>(
         expr: &Expr,
@@ -440,7 +454,7 @@ pub(crate) mod tests {
             right: Box::new(0i32.into()),
         }
         .into();
-        let block: Expr = Expr::BlockValue(
+        let block: ErgoTree = Expr::BlockValue(
             BlockValue {
                 items: vec![ValDef {
                     id: 1.into(),
@@ -450,7 +464,9 @@ pub(crate) mod tests {
                 result: Box::new(bin_op),
             }
             .into(),
-        );
+        )
+        .try_into()
+        .unwrap();
         let ctx = force_any_val::<Context>();
         let res = reduce_to_crypto(&block, &ctx).unwrap();
         assert!(res.sigma_prop == SigmaBoolean::TrivialProp(false));
diff --git a/ergotree-interpreter/src/eval/and.rs b/ergotree-interpreter/src/eval/and.rs
index 6be736e27..3cb82bd85 100644
--- a/ergotree-interpreter/src/eval/and.rs
+++ b/ergotree-interpreter/src/eval/and.rs
@@ -22,8 +22,8 @@ impl Evaluable for And {
 #[allow(clippy::panic)]
 #[cfg(test)]
 mod tests {
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
 
     use super::*;
 
diff --git a/ergotree-interpreter/src/eval/apply.rs b/ergotree-interpreter/src/eval/apply.rs
index e9bc71785..34020f43a 100644
--- a/ergotree-interpreter/src/eval/apply.rs
+++ b/ergotree-interpreter/src/eval/apply.rs
@@ -56,6 +56,7 @@ impl Evaluable for Apply {
 #[cfg(test)]
 #[allow(clippy::unwrap_used)]
 mod tests {
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::bin_op::BinOp;
     use ergotree_ir::mir::bin_op::RelationOp;
     use ergotree_ir::mir::block::BlockValue;
@@ -67,7 +68,6 @@ mod tests {
     use ergotree_ir::types::stype::SType;
     use sigma_test_util::force_any_val;
 
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
 
     use super::*;
diff --git a/ergotree-interpreter/src/eval/atleast.rs b/ergotree-interpreter/src/eval/atleast.rs
index 6d7d925e9..625f20ae4 100644
--- a/ergotree-interpreter/src/eval/atleast.rs
+++ b/ergotree-interpreter/src/eval/atleast.rs
@@ -69,8 +69,8 @@ mod tests {
     use ergotree_ir::sigma_protocol::sigma_boolean::SigmaConjecture;
     use ergotree_ir::types::stype::SType;
 
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
 
     use super::*;
 
diff --git a/ergotree-interpreter/src/eval/bin_op.rs b/ergotree-interpreter/src/eval/bin_op.rs
index 1344891b4..58de9d1bb 100644
--- a/ergotree-interpreter/src/eval/bin_op.rs
+++ b/ergotree-interpreter/src/eval/bin_op.rs
@@ -326,9 +326,9 @@ impl Evaluable for BinOp {
 #[allow(clippy::unwrap_used)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
     use crate::eval::tests::try_eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::constant::Constant;
     use ergotree_ir::mir::expr::Expr;
     use num_traits::Bounded;
diff --git a/ergotree-interpreter/src/eval/calc_blake2b256.rs b/ergotree-interpreter/src/eval/calc_blake2b256.rs
index a32820318..f8ce4a194 100644
--- a/ergotree-interpreter/src/eval/calc_blake2b256.rs
+++ b/ergotree-interpreter/src/eval/calc_blake2b256.rs
@@ -35,8 +35,8 @@ impl Evaluable for CalcBlake2b256 {
 #[allow(clippy::panic)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::expr::Expr;
     use proptest::prelude::*;
     use sigma_test_util::force_any_val;
diff --git a/ergotree-interpreter/src/eval/calc_sha256.rs b/ergotree-interpreter/src/eval/calc_sha256.rs
index c5f6fa749..e348aaacb 100644
--- a/ergotree-interpreter/src/eval/calc_sha256.rs
+++ b/ergotree-interpreter/src/eval/calc_sha256.rs
@@ -34,8 +34,8 @@ impl Evaluable for CalcSha256 {
 #[allow(clippy::panic)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::expr::Expr;
     use proptest::prelude::*;
     use sigma_test_util::force_any_val;
diff --git a/ergotree-interpreter/src/eval/coll_by_index.rs b/ergotree-interpreter/src/eval/coll_by_index.rs
index 59398333e..7d53d8b93 100644
--- a/ergotree-interpreter/src/eval/coll_by_index.rs
+++ b/ergotree-interpreter/src/eval/coll_by_index.rs
@@ -53,9 +53,9 @@ mod tests {
     use sigma_test_util::force_any_val;
 
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
     use crate::eval::tests::eval_out_wo_ctx;
+    use ergotree_ir::chain::context::Context;
 
     #[test]
     fn eval() {
diff --git a/ergotree-interpreter/src/eval/coll_filter.rs b/ergotree-interpreter/src/eval/coll_filter.rs
index faa8a0da8..7209d4b4f 100644
--- a/ergotree-interpreter/src/eval/coll_filter.rs
+++ b/ergotree-interpreter/src/eval/coll_filter.rs
@@ -86,8 +86,8 @@ impl Evaluable for Filter {
 #[cfg(test)]
 mod tests {
 
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
 
     use super::*;
 
diff --git a/ergotree-interpreter/src/eval/coll_fold.rs b/ergotree-interpreter/src/eval/coll_fold.rs
index c9820a7c8..69128b789 100644
--- a/ergotree-interpreter/src/eval/coll_fold.rs
+++ b/ergotree-interpreter/src/eval/coll_fold.rs
@@ -69,8 +69,8 @@ impl Evaluable for Fold {
 mod tests {
     use std::convert::TryInto;
 
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::bin_op::ArithOp;
     use ergotree_ir::mir::bin_op::BinOp;
     use ergotree_ir::mir::expr::Expr;
diff --git a/ergotree-interpreter/src/eval/coll_map.rs b/ergotree-interpreter/src/eval/coll_map.rs
index 4b1ccd311..62d576fe8 100644
--- a/ergotree-interpreter/src/eval/coll_map.rs
+++ b/ergotree-interpreter/src/eval/coll_map.rs
@@ -84,9 +84,9 @@ impl Evaluable for Map {
 #[cfg(test)]
 mod tests {
 
-    use crate::eval::context::Context;
-    use crate::eval::context::TxIoVec;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
+    use ergotree_ir::chain::context::TxIoVec;
     use ergotree_ir::mir::bin_op::ArithOp;
     use ergotree_ir::mir::bin_op::BinOp;
     use ergotree_ir::mir::expr::Expr;
diff --git a/ergotree-interpreter/src/eval/coll_size.rs b/ergotree-interpreter/src/eval/coll_size.rs
index 91650df3d..058deb92c 100644
--- a/ergotree-interpreter/src/eval/coll_size.rs
+++ b/ergotree-interpreter/src/eval/coll_size.rs
@@ -27,8 +27,8 @@ impl Evaluable for SizeOf {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::expr::Expr;
     use ergotree_ir::mir::global_vars::GlobalVars;
     use ergotree_ir::mir::unary_op::OneArgOpTryBuild;
diff --git a/ergotree-interpreter/src/eval/deserialize_context.rs b/ergotree-interpreter/src/eval/deserialize_context.rs
index 0d566f271..1e0799e72 100644
--- a/ergotree-interpreter/src/eval/deserialize_context.rs
+++ b/ergotree-interpreter/src/eval/deserialize_context.rs
@@ -1,66 +1,27 @@
-use ergotree_ir::mir::constant::TryExtractInto;
-use ergotree_ir::mir::deserialize_context::DeserializeContext;
-use ergotree_ir::mir::expr::Expr;
-use ergotree_ir::mir::value::Value;
-use ergotree_ir::serialization::SigmaSerializable;
-use ergotree_ir::types::stype::SType;
-
-use crate::eval::env::Env;
-use crate::eval::Context;
-use crate::eval::EvalError;
-use crate::eval::Evaluable;
-
-impl Evaluable for DeserializeContext {
-    fn eval<'ctx>(
-        &self,
-        env: &mut Env<'ctx>,
-        ctx: &Context<'ctx>,
-    ) -> Result<Value<'ctx>, EvalError> {
-        match ctx.extension.values.get(&self.id) {
-            Some(c) => {
-                let expected_tpe = SType::SColl(SType::SByte.into());
-                if c.tpe != expected_tpe {
-                    Err(EvalError::UnexpectedExpr(format!(
-                        "DeserializeContext: expected extension value {} with id {} to have type {:?} got {:?}",
-                        c, self.id, expected_tpe, c.tpe
-                    )))
-                } else {
-                    let bytes = c.v.clone().try_extract_into::<Vec<u8>>()?;
-                    let expr = Expr::sigma_parse_bytes(bytes.as_slice())?;
-                    if expr.tpe() != self.tpe {
-                        return Err(EvalError::UnexpectedExpr(format!("DeserializeContext: expected deserialized expr from extension value {} with id {} to have type {:?}, got {:?}", c, self.id, self.tpe, expr.tpe())));
-                    }
-                    expr.eval(env, ctx)
-                }
-            }
-            None => Err(EvalError::NotFound(format!(
-                "DeserializeContext: no value with id {} in context extension map {}",
-                self.id, ctx.extension
-            ))),
-        }
-    }
-}
-
 #[allow(clippy::unwrap_used)]
 #[cfg(test)]
 mod tests {
+    use ergotree_ir::ergo_tree::{ErgoTree, ErgoTreeHeader};
     use ergotree_ir::mir::constant::Constant;
+    use ergotree_ir::mir::deserialize_context::DeserializeContext;
+    use ergotree_ir::mir::expr::Expr;
     use ergotree_ir::mir::global_vars::GlobalVars;
+    use ergotree_ir::mir::value::Value;
+    use ergotree_ir::serialization::SigmaSerializable;
+    use ergotree_ir::types::stype::SType;
     use sigma_test_util::force_any_val;
 
-    use crate::eval::context::Context;
-    use crate::eval::tests::try_eval_out;
-    use crate::sigma_protocol::prover::ContextExtension;
-
-    use super::*;
+    use crate::eval::reduce_to_crypto;
+    use crate::eval::tests::try_eval_with_deserialize;
+    use ergotree_ir::chain::context::Context;
+    use ergotree_ir::chain::context_extension::ContextExtension;
 
     #[test]
     fn eval() {
-        let expr: Expr = DeserializeContext {
+        let expr: Expr = Expr::from(DeserializeContext {
             tpe: SType::SBoolean,
             id: 1,
-        }
-        .into();
+        });
         let inner_expr: Expr = true.into();
         let ctx_ext = ContextExtension {
             values: [(1u8, inner_expr.sigma_serialize_bytes().unwrap().into())]
@@ -69,7 +30,33 @@ mod tests {
                 .collect(),
         };
         let ctx = force_any_val::<Context>().with_extension(ctx_ext);
-        assert!(try_eval_out::<bool>(&expr, &ctx).unwrap());
+        assert!(try_eval_with_deserialize::<bool>(&expr, &ctx).unwrap());
+    }
+
+    // Verify that reduce_to_crypto performs deserialize substitution
+    #[test]
+    fn eval_reduction() {
+        let expr: Expr = Expr::from(DeserializeContext {
+            tpe: SType::SBoolean,
+            id: 1,
+        });
+        let inner_expr: Expr = true.into();
+        let ctx_ext = ContextExtension {
+            values: [(1u8, inner_expr.sigma_serialize_bytes().unwrap().into())]
+                .iter()
+                .cloned()
+                .collect(),
+        };
+        let ctx = force_any_val::<Context>().with_extension(ctx_ext);
+        assert_eq!(
+            reduce_to_crypto(
+                &ErgoTree::new(ErgoTreeHeader::v1(false), &expr).unwrap(),
+                &ctx,
+            )
+            .unwrap()
+            .sigma_prop,
+            true.into()
+        );
     }
 
     #[test]
@@ -80,7 +67,7 @@ mod tests {
         }
         .into();
         let ctx = force_any_val::<Context>().with_extension(ContextExtension::empty());
-        assert!(try_eval_out::<bool>(&expr, &ctx).is_err());
+        assert!(try_eval_with_deserialize::<bool>(&expr, &ctx).is_err());
     }
 
     #[test]
@@ -96,7 +83,7 @@ mod tests {
             values: [(1u8, ctx_ext_val)].iter().cloned().collect(),
         };
         let ctx = force_any_val::<Context>().with_extension(ctx_ext);
-        assert!(try_eval_out::<bool>(&expr, &ctx).is_err());
+        assert!(try_eval_with_deserialize::<bool>(&expr, &ctx).is_err());
     }
 
     #[test]
@@ -115,6 +102,24 @@ mod tests {
                 .collect(),
         };
         let ctx = force_any_val::<Context>().with_extension(ctx_ext);
-        assert!(try_eval_out::<Value>(&expr, &ctx).is_err());
+        assert!(try_eval_with_deserialize::<Value>(&expr, &ctx).is_err());
+    }
+
+    #[test]
+    fn eval_recursive() {
+        let expr: Expr = DeserializeContext {
+            tpe: SType::SBoolean,
+            id: 1,
+        }
+        .into();
+        let ctx_ext = ContextExtension {
+            values: [(1u8, expr.sigma_serialize_bytes().unwrap().into())]
+                .iter()
+                .cloned()
+                .collect(),
+        };
+        let ctx = force_any_val::<Context>().with_extension(ctx_ext);
+        // Evaluating executeFromVar(1) with ctx[1] being executeFromVar(1) should fail during evaluation
+        assert!(try_eval_with_deserialize::<bool>(&expr, &ctx).is_err());
     }
 }
diff --git a/ergotree-interpreter/src/eval/deserialize_register.rs b/ergotree-interpreter/src/eval/deserialize_register.rs
index ca1f68a00..3a038e523 100644
--- a/ergotree-interpreter/src/eval/deserialize_register.rs
+++ b/ergotree-interpreter/src/eval/deserialize_register.rs
@@ -1,98 +1,26 @@
-use std::convert::TryInto;
-
-use ergotree_ir::chain::ergo_box::RegisterId;
-use ergotree_ir::mir::constant::TryExtractInto;
-use ergotree_ir::mir::deserialize_register::DeserializeRegister;
-use ergotree_ir::mir::expr::Expr;
-use ergotree_ir::mir::value::Value;
-use ergotree_ir::serialization::SigmaSerializable;
-use ergotree_ir::types::stype::SType;
-
-use crate::eval::env::Env;
-use crate::eval::Context;
-use crate::eval::EvalError;
-use crate::eval::Evaluable;
-
-impl Evaluable for DeserializeRegister {
-    fn eval<'ctx>(
-        &self,
-        env: &mut Env<'ctx>,
-        ctx: &Context<'ctx>,
-    ) -> Result<Value<'ctx>, EvalError> {
-        let reg_id: RegisterId = self.reg.try_into().map_err(|e| {
-            EvalError::RegisterIdOutOfBounds(format!("register index is out of bounds: {:?} ", e))
-        })?;
-        match ctx.self_box.get_register(reg_id) {
-            Ok(Some(c)) => {
-                if c.tpe != SType::SColl(SType::SByte.into()) {
-                    Err(EvalError::UnexpectedExpr(format!(
-                        "DeserializeRegister: expected register {} value {} to have type SColl(SByte), got {:?}",
-                        reg_id, c, c.tpe
-                    )))
-                } else {
-                    let bytes = c.v.try_extract_into::<Vec<u8>>()?;
-                    let expr = Expr::sigma_parse_bytes(bytes.as_slice())?;
-                    if expr.tpe() != self.tpe {
-                        let pretty_expr = expr.to_string_pretty();
-                        Err(EvalError::UnexpectedExpr(format!("DeserializeRegister: expected register {reg_id} deserialized expr {pretty_expr} to have type {:?}, got {:?}", self.tpe, expr.tpe())))
-                    } else {
-                        expr.eval(env, ctx)
-                    }
-                }
-            }
-            Ok(None) => match &self.default {
-                Some(default_expr) => eval_default(&self.tpe, default_expr, env, ctx),
-                None => Err(EvalError::NotFound(format!(
-                    "DeserializeRegister: register {reg_id} is empty"
-                ))),
-            },
-            Err(e) => match &self.default {
-                Some(default_expr) => eval_default(&self.tpe, default_expr, env, ctx),
-                None => Err(EvalError::NotFound(format!(
-                    "DeserializeRegister: failed to get the register id {reg_id} with error: {e:?}"
-                ))),
-            },
-        }
-    }
-}
-
-fn eval_default<'ctx>(
-    deserialize_reg_tpe: &SType,
-    default_expr: &Expr,
-    env: &mut Env<'ctx>,
-    ctx: &Context<'ctx>,
-) -> Result<Value<'ctx>, EvalError> {
-    if &default_expr.tpe() != deserialize_reg_tpe {
-        Err(EvalError::UnexpectedExpr(format!(
-            "DeserializeRegister: expected default expr to have type {:?}, got {:?}",
-            deserialize_reg_tpe,
-            default_expr.tpe()
-        )))
-    } else {
-        default_expr.eval(env, ctx)
-    }
-}
-
 #[allow(clippy::unwrap_used)]
 #[cfg(feature = "arbitrary")]
 #[cfg(test)]
 mod tests {
 
     use ergotree_ir::chain::ergo_box::ErgoBox;
+    use ergotree_ir::chain::ergo_box::NonMandatoryRegisterId;
     use ergotree_ir::chain::ergo_box::NonMandatoryRegisters;
     use ergotree_ir::mir::bin_op::BinOp;
     use ergotree_ir::mir::bin_op::RelationOp;
     use ergotree_ir::mir::constant::Constant;
+    use ergotree_ir::mir::deserialize_register::DeserializeRegister;
     use ergotree_ir::mir::expr::Expr;
     use ergotree_ir::mir::global_vars::GlobalVars;
+    use ergotree_ir::mir::value::Value;
     use ergotree_ir::serialization::SigmaSerializable;
     use ergotree_ir::types::stype::SType;
     use sigma_test_util::force_any_val;
 
-    use crate::eval::context::Context;
     use crate::eval::tests::try_eval_out;
-
-    use super::*;
+    use crate::eval::tests::try_eval_with_deserialize;
+    use crate::eval::EvalError;
+    use ergotree_ir::chain::context::Context;
 
     fn make_ctx_with_self_box(self_box: ErgoBox) -> Context<'static> {
         let ctx = force_any_val::<Context>();
@@ -117,13 +45,13 @@ mod tests {
             .with_additional_registers(vec![reg_value].try_into().unwrap());
         // expected SBoolean
         let expr: Expr = DeserializeRegister {
-            reg: 4,
+            reg: NonMandatoryRegisterId::R4.into(),
             tpe: SType::SBoolean,
             default: None,
         }
         .into();
         let ctx = make_ctx_with_self_box(b);
-        assert!(try_eval_out::<bool>(&expr, &ctx).unwrap());
+        assert!(try_eval_with_deserialize::<bool>(&expr, &ctx).unwrap());
     }
 
     #[test]
@@ -132,7 +60,7 @@ mod tests {
             force_any_val::<ErgoBox>().with_additional_registers(NonMandatoryRegisters::empty());
         // no default provided
         let expr: Expr = DeserializeRegister {
-            reg: 5,
+            reg: NonMandatoryRegisterId::R5.into(),
             tpe: SType::SBoolean,
             default: None,
         }
@@ -142,23 +70,30 @@ mod tests {
 
         // default with wrong type provided
         let expr: Expr = DeserializeRegister {
-            reg: 5,
+            reg: NonMandatoryRegisterId::R5.into(),
             tpe: SType::SInt,
             default: Some(Box::new(true.into())),
         }
         .into();
         let ctx = make_ctx_with_self_box(b.clone());
-        assert!(try_eval_out::<i32>(&expr, &ctx).is_err());
-
+        assert!(matches!(
+            try_eval_with_deserialize::<i32>(&expr, &ctx),
+            Err(EvalError::SubstDeserializeError(
+                ergotree_ir::mir::expr::SubstDeserializeError::ExprTpeError {
+                    expected: _,
+                    actual: _
+                }
+            ))
+        ));
         // default provided
         let expr: Expr = DeserializeRegister {
-            reg: 5,
+            reg: NonMandatoryRegisterId::R5.into(),
             tpe: SType::SInt,
             default: Some(Box::new(1i32.into())),
         }
         .into();
         let ctx = make_ctx_with_self_box(b);
-        assert_eq!(try_eval_out::<i32>(&expr, &ctx).unwrap(), 1i32);
+        assert_eq!(try_eval_with_deserialize::<i32>(&expr, &ctx).unwrap(), 1i32);
     }
 
     #[test]
@@ -168,13 +103,16 @@ mod tests {
         let b = force_any_val::<ErgoBox>()
             .with_additional_registers(vec![reg_value].try_into().unwrap());
         let expr: Expr = DeserializeRegister {
-            reg: 4,
+            reg: NonMandatoryRegisterId::R4.into(),
             tpe: SType::SBoolean,
             default: None,
         }
         .into();
         let ctx = make_ctx_with_self_box(b);
-        assert!(try_eval_out::<Value>(&expr, &ctx).is_err());
+        assert!(matches!(
+            try_eval_with_deserialize::<Value>(&expr, &ctx),
+            Err(EvalError::SubstDeserializeError(_))
+        ));
     }
 
     #[test]
@@ -186,12 +124,20 @@ mod tests {
             .with_additional_registers(vec![reg_value].try_into().unwrap());
         // expected SBoolean
         let expr: Expr = DeserializeRegister {
-            reg: 4,
+            reg: NonMandatoryRegisterId::R4.into(),
             tpe: SType::SBoolean,
             default: None,
         }
         .into();
         let ctx = make_ctx_with_self_box(b);
-        assert!(try_eval_out::<bool>(&expr, &ctx).is_err());
+        assert!(matches!(
+            try_eval_with_deserialize::<bool>(&expr, &ctx),
+            Err(EvalError::SubstDeserializeError(
+                ergotree_ir::mir::expr::SubstDeserializeError::ExprTpeError {
+                    expected: _,
+                    actual: _
+                }
+            ))
+        ));
     }
 }
diff --git a/ergotree-interpreter/src/eval/error.rs b/ergotree-interpreter/src/eval/error.rs
index 224d90336..8e17cdbe9 100644
--- a/ergotree-interpreter/src/eval/error.rs
+++ b/ergotree-interpreter/src/eval/error.rs
@@ -1,3 +1,4 @@
+use ergotree_ir::mir::expr::SubstDeserializeError;
 use miette::miette;
 use miette::LabeledSpan;
 use std::fmt::Debug;
@@ -82,6 +83,9 @@ pub enum EvalError {
         /// Currently activated script version on network
         activated_version: u8,
     },
+    /// Deserialize substitution error, see [`ergotree_ir::mir::expr::Expr::substitute_deserialize`]
+    #[error("DeserializeRegister/DeserializeContext error: {0}")]
+    SubstDeserializeError(#[from] SubstDeserializeError),
 }
 
 /// Wrapped error with source span
@@ -215,10 +219,10 @@ mod tests {
     use ergotree_ir::types::stype::SType;
     use sigma_test_util::force_any_val;
 
-    use crate::eval::context::Context;
     use crate::eval::error::SpannedEvalError;
     use crate::eval::error::SpannedWithSourceEvalError;
     use crate::eval::tests::try_eval_out;
+    use ergotree_ir::chain::context::Context;
 
     fn check(expr: Expr, expected_tree: expect_test::Expect) {
         let mut w = PosTrackingWriter::new();
diff --git a/ergotree-interpreter/src/eval/exponentiate.rs b/ergotree-interpreter/src/eval/exponentiate.rs
index 0256cb571..c63462ccd 100644
--- a/ergotree-interpreter/src/eval/exponentiate.rs
+++ b/ergotree-interpreter/src/eval/exponentiate.rs
@@ -39,9 +39,9 @@ impl Evaluable for Exponentiate {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
     use crate::sigma_protocol::private_input::DlogProverInput;
+    use ergotree_ir::chain::context::Context;
 
     use ergo_chain_types::EcPoint;
     use ergotree_ir::bigint256::BigInt256;
diff --git a/ergotree-interpreter/src/eval/expr.rs b/ergotree-interpreter/src/eval/expr.rs
index 2ef42cbd4..b2a3d8a88 100644
--- a/ergotree-interpreter/src/eval/expr.rs
+++ b/ergotree-interpreter/src/eval/expr.rs
@@ -78,8 +78,12 @@ impl Evaluable for Expr {
             Expr::DecodePoint(op) => op.eval(env, ctx),
             Expr::SigmaAnd(op) => op.eval(env, ctx),
             Expr::SigmaOr(op) => op.eval(env, ctx),
-            Expr::DeserializeRegister(op) => op.eval(env, ctx),
-            Expr::DeserializeContext(op) => op.eval(env, ctx),
+            Expr::DeserializeRegister(_) => Err(EvalError::UnexpectedExpr(
+                "DeserializeRegister cannot be evaluated".to_string(),
+            )),
+            Expr::DeserializeContext(_) => Err(EvalError::UnexpectedExpr(
+                "DeserializeContext cannot be evaluated".to_string(),
+            )),
             Expr::GetVar(op) => op.eval(env, ctx),
             Expr::MultiplyGroup(op) => op.eval(env, ctx),
             Expr::Exponentiate(op) => op.eval(env, ctx),
diff --git a/ergotree-interpreter/src/eval/extract_amount.rs b/ergotree-interpreter/src/eval/extract_amount.rs
index f27fdca41..a6a287bce 100644
--- a/ergotree-interpreter/src/eval/extract_amount.rs
+++ b/ergotree-interpreter/src/eval/extract_amount.rs
@@ -27,8 +27,8 @@ impl Evaluable for ExtractAmount {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::expr::Expr;
     use ergotree_ir::mir::global_vars::GlobalVars;
     use sigma_test_util::force_any_val;
diff --git a/ergotree-interpreter/src/eval/extract_bytes.rs b/ergotree-interpreter/src/eval/extract_bytes.rs
index 01e9bc9ec..17a37137e 100644
--- a/ergotree-interpreter/src/eval/extract_bytes.rs
+++ b/ergotree-interpreter/src/eval/extract_bytes.rs
@@ -28,8 +28,8 @@ impl Evaluable for ExtractBytes {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::expr::Expr;
     use ergotree_ir::mir::global_vars::GlobalVars;
     use sigma_test_util::force_any_val;
diff --git a/ergotree-interpreter/src/eval/extract_bytes_with_no_ref.rs b/ergotree-interpreter/src/eval/extract_bytes_with_no_ref.rs
index 6de0c5944..a84874f06 100644
--- a/ergotree-interpreter/src/eval/extract_bytes_with_no_ref.rs
+++ b/ergotree-interpreter/src/eval/extract_bytes_with_no_ref.rs
@@ -27,8 +27,8 @@ impl Evaluable for ExtractBytesWithNoRef {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::expr::Expr;
     use ergotree_ir::mir::global_vars::GlobalVars;
     use sigma_test_util::force_any_val;
diff --git a/ergotree-interpreter/src/eval/extract_id.rs b/ergotree-interpreter/src/eval/extract_id.rs
index 2031ee6ca..5baaf5d01 100644
--- a/ergotree-interpreter/src/eval/extract_id.rs
+++ b/ergotree-interpreter/src/eval/extract_id.rs
@@ -30,8 +30,8 @@ impl Evaluable for ExtractId {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::expr::Expr;
     use ergotree_ir::mir::global_vars::GlobalVars;
     use sigma_test_util::force_any_val;
diff --git a/ergotree-interpreter/src/eval/extract_reg_as.rs b/ergotree-interpreter/src/eval/extract_reg_as.rs
index 404c0c894..05d93502f 100644
--- a/ergotree-interpreter/src/eval/extract_reg_as.rs
+++ b/ergotree-interpreter/src/eval/extract_reg_as.rs
@@ -49,8 +49,8 @@ impl Evaluable for ExtractRegisterAs {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::{eval_out, try_eval_out};
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::expr::Expr;
     use ergotree_ir::mir::global_vars::GlobalVars;
     use ergotree_ir::mir::option_get::OptionGet;
diff --git a/ergotree-interpreter/src/eval/extract_script_bytes.rs b/ergotree-interpreter/src/eval/extract_script_bytes.rs
index 4281ea7c4..3557ddee0 100644
--- a/ergotree-interpreter/src/eval/extract_script_bytes.rs
+++ b/ergotree-interpreter/src/eval/extract_script_bytes.rs
@@ -27,8 +27,8 @@ impl Evaluable for ExtractScriptBytes {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::expr::Expr;
     use ergotree_ir::mir::global_vars::GlobalVars;
     use sigma_test_util::force_any_val;
diff --git a/ergotree-interpreter/src/eval/get_var.rs b/ergotree-interpreter/src/eval/get_var.rs
index 0e5dfa5d5..5d6c866b1 100644
--- a/ergotree-interpreter/src/eval/get_var.rs
+++ b/ergotree-interpreter/src/eval/get_var.rs
@@ -24,8 +24,8 @@ impl Evaluable for GetVar {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::{eval_out, try_eval_out};
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::expr::Expr;
     use ergotree_ir::types::stype::SType;
     use sigma_test_util::force_any_val;
diff --git a/ergotree-interpreter/src/eval/global_vars.rs b/ergotree-interpreter/src/eval/global_vars.rs
index 964466305..c94e12f80 100644
--- a/ergotree-interpreter/src/eval/global_vars.rs
+++ b/ergotree-interpreter/src/eval/global_vars.rs
@@ -35,11 +35,11 @@ impl Evaluable for GlobalVars {
 #[cfg(test)]
 mod tests {
 
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
     use ergo_chain_types::EcPoint;
     use ergoscript_compiler::compiler::compile_expr;
     use ergoscript_compiler::script_env::ScriptEnv;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::chain::ergo_box::ErgoBox;
     use sigma_test_util::force_any_val;
 
diff --git a/ergotree-interpreter/src/eval/multiply_group.rs b/ergotree-interpreter/src/eval/multiply_group.rs
index 0f0311722..f79d54bb6 100644
--- a/ergotree-interpreter/src/eval/multiply_group.rs
+++ b/ergotree-interpreter/src/eval/multiply_group.rs
@@ -32,8 +32,8 @@ impl Evaluable for MultiplyGroup {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
 
     use ergo_chain_types::EcPoint;
     use ergotree_ir::mir::expr::Expr;
diff --git a/ergotree-interpreter/src/eval/option_get.rs b/ergotree-interpreter/src/eval/option_get.rs
index efd8b5ba1..3b872dd22 100644
--- a/ergotree-interpreter/src/eval/option_get.rs
+++ b/ergotree-interpreter/src/eval/option_get.rs
@@ -29,8 +29,8 @@ impl Evaluable for OptionGet {
 #[cfg(test)]
 mod tests {
     use super::OptionGet;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::expr::Expr;
     use ergotree_ir::mir::extract_reg_as::ExtractRegisterAs;
     use ergotree_ir::mir::global_vars::GlobalVars;
diff --git a/ergotree-interpreter/src/eval/option_get_or_else.rs b/ergotree-interpreter/src/eval/option_get_or_else.rs
index 66f1341aa..902eade3c 100644
--- a/ergotree-interpreter/src/eval/option_get_or_else.rs
+++ b/ergotree-interpreter/src/eval/option_get_or_else.rs
@@ -28,8 +28,8 @@ impl Evaluable for OptionGetOrElse {
 #[cfg(test)]
 mod tests {
     use super::OptionGetOrElse;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::constant::Constant;
     use ergotree_ir::mir::expr::Expr;
     use ergotree_ir::mir::extract_reg_as::ExtractRegisterAs;
diff --git a/ergotree-interpreter/src/eval/option_is_defined.rs b/ergotree-interpreter/src/eval/option_is_defined.rs
index 4fb69bed0..dfe237f2c 100644
--- a/ergotree-interpreter/src/eval/option_is_defined.rs
+++ b/ergotree-interpreter/src/eval/option_is_defined.rs
@@ -27,8 +27,8 @@ impl Evaluable for OptionIsDefined {
 #[cfg(test)]
 mod tests {
     use super::OptionIsDefined;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::expr::Expr;
     use ergotree_ir::mir::extract_reg_as::ExtractRegisterAs;
     use ergotree_ir::mir::global_vars::GlobalVars;
diff --git a/ergotree-interpreter/src/eval/or.rs b/ergotree-interpreter/src/eval/or.rs
index 289581943..349cb54a0 100644
--- a/ergotree-interpreter/src/eval/or.rs
+++ b/ergotree-interpreter/src/eval/or.rs
@@ -23,8 +23,8 @@ impl Evaluable for Or {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::expr::Expr;
     use proptest::collection;
     use proptest::prelude::*;
diff --git a/ergotree-interpreter/src/eval/property_call.rs b/ergotree-interpreter/src/eval/property_call.rs
index 9d60eb320..4b52f5052 100644
--- a/ergotree-interpreter/src/eval/property_call.rs
+++ b/ergotree-interpreter/src/eval/property_call.rs
@@ -22,8 +22,8 @@ impl Evaluable for PropertyCall {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::chain::ergo_box::ErgoBox;
     use ergotree_ir::mir::expr::Expr;
     use ergotree_ir::reference::Ref;
diff --git a/ergotree-interpreter/src/eval/sbox.rs b/ergotree-interpreter/src/eval/sbox.rs
index ea7e857a2..d53511c4c 100644
--- a/ergotree-interpreter/src/eval/sbox.rs
+++ b/ergotree-interpreter/src/eval/sbox.rs
@@ -91,9 +91,9 @@ mod tests {
     use ergotree_ir::types::stype_param::STypeVar;
     use sigma_test_util::force_any_val;
 
-    use crate::eval::context::Context;
     use crate::eval::tests::{eval_out, try_eval_out_with_version};
     use crate::eval::EvalError;
+    use ergotree_ir::chain::context::Context;
 
     #[test]
     fn eval_box_value() {
diff --git a/ergotree-interpreter/src/eval/scontext.rs b/ergotree-interpreter/src/eval/scontext.rs
index a74f434a7..5949d3f91 100644
--- a/ergotree-interpreter/src/eval/scontext.rs
+++ b/ergotree-interpreter/src/eval/scontext.rs
@@ -100,9 +100,9 @@ pub(crate) static MINER_PUBKEY_EVAL_FN: EvalFn = |_mc, _env, ctx, obj, _args| {
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used, clippy::expect_used)]
 mod tests {
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
     use ergo_chain_types::{Header, PreHeader};
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::chain::ergo_box::ErgoBox;
     use ergotree_ir::mir::avl_tree_data::{AvlTreeData, AvlTreeFlags};
     use ergotree_ir::mir::expr::Expr;
diff --git a/ergotree-interpreter/src/eval/sglobal.rs b/ergotree-interpreter/src/eval/sglobal.rs
index ceb248550..e01508659 100644
--- a/ergotree-interpreter/src/eval/sglobal.rs
+++ b/ergotree-interpreter/src/eval/sglobal.rs
@@ -62,8 +62,8 @@ mod tests {
     use ergotree_ir::mir::method_call::MethodCall;
     use ergotree_ir::mir::property_call::PropertyCall;
 
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::types::sglobal;
     use sigma_test_util::force_any_val;
 
diff --git a/ergotree-interpreter/src/eval/sheader.rs b/ergotree-interpreter/src/eval/sheader.rs
index 9fa363912..7a537b5f4 100644
--- a/ergotree-interpreter/src/eval/sheader.rs
+++ b/ergotree-interpreter/src/eval/sheader.rs
@@ -97,16 +97,14 @@ mod tests {
     use ergo_chain_types::{BlockId, Digest, Digest32, EcPoint, Votes};
     use ergotree_ir::{
         bigint256::BigInt256,
+        chain::context::Context,
         mir::{coll_by_index::ByIndex, expr::Expr, property_call::PropertyCall},
         types::{scontext, sheader, smethod::SMethod},
     };
     use sigma_test_util::force_any_val;
     use sigma_util::AsVecU8;
 
-    use crate::eval::{
-        context::Context,
-        tests::{eval_out, try_eval_out_wo_ctx},
-    };
+    use crate::eval::tests::{eval_out, try_eval_out_wo_ctx};
 
     // Index in Context.headers array
     const HEADER_INDEX: usize = 0;
diff --git a/ergotree-interpreter/src/eval/sigma_and.rs b/ergotree-interpreter/src/eval/sigma_and.rs
index 921ae86e8..9908e6f54 100644
--- a/ergotree-interpreter/src/eval/sigma_and.rs
+++ b/ergotree-interpreter/src/eval/sigma_and.rs
@@ -33,8 +33,8 @@ mod tests {
     use ergotree_ir::sigma_protocol::sigma_boolean::SigmaConjecture;
     use std::convert::TryInto;
 
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
 
     use super::*;
 
diff --git a/ergotree-interpreter/src/eval/sigma_or.rs b/ergotree-interpreter/src/eval/sigma_or.rs
index 94d91970f..dc15eb152 100644
--- a/ergotree-interpreter/src/eval/sigma_or.rs
+++ b/ergotree-interpreter/src/eval/sigma_or.rs
@@ -33,8 +33,8 @@ mod tests {
     use ergotree_ir::sigma_protocol::sigma_boolean::SigmaConjecture;
     use std::convert::TryInto;
 
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
 
     use super::*;
 
diff --git a/ergotree-interpreter/src/eval/spreheader.rs b/ergotree-interpreter/src/eval/spreheader.rs
index e38467cf5..4066ff3eb 100644
--- a/ergotree-interpreter/src/eval/spreheader.rs
+++ b/ergotree-interpreter/src/eval/spreheader.rs
@@ -54,10 +54,8 @@ mod tests {
     use sigma_test_util::force_any_val;
     use sigma_util::AsVecU8;
 
-    use crate::eval::{
-        context::Context,
-        tests::{eval_out, try_eval_out_wo_ctx},
-    };
+    use crate::eval::tests::{eval_out, try_eval_out_wo_ctx};
+    use ergotree_ir::chain::context::Context;
 
     fn create_get_preheader_property_expr(method: SMethod) -> Expr {
         let get_preheader_expr = create_get_preheader_expr();
diff --git a/ergotree-interpreter/src/eval/xor.rs b/ergotree-interpreter/src/eval/xor.rs
index ea07101a0..ea322a3ab 100644
--- a/ergotree-interpreter/src/eval/xor.rs
+++ b/ergotree-interpreter/src/eval/xor.rs
@@ -44,8 +44,8 @@ impl Evaluable for Xor {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::expr::Expr;
     use proptest::prelude::*;
     use sigma_test_util::force_any_val;
diff --git a/ergotree-interpreter/src/eval/xor_of.rs b/ergotree-interpreter/src/eval/xor_of.rs
index 5b70159f9..52ad3d2c1 100644
--- a/ergotree-interpreter/src/eval/xor_of.rs
+++ b/ergotree-interpreter/src/eval/xor_of.rs
@@ -23,8 +23,8 @@ impl Evaluable for XorOf {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::eval::context::Context;
     use crate::eval::tests::eval_out;
+    use ergotree_ir::chain::context::Context;
     use ergotree_ir::mir::expr::Expr;
     use proptest::collection;
     use proptest::prelude::*;
diff --git a/ergotree-interpreter/src/sigma_protocol/prover.rs b/ergotree-interpreter/src/sigma_protocol/prover.rs
index 4d5658308..b00a2de87 100644
--- a/ergotree-interpreter/src/sigma_protocol/prover.rs
+++ b/ergotree-interpreter/src/sigma_protocol/prover.rs
@@ -1,6 +1,5 @@
 //! Interpreter with enhanced functionality to prove statements.
 
-mod context_extension;
 mod prover_result;
 
 pub mod hint;
@@ -28,7 +27,6 @@ use gf2_192::gf2_192poly::Gf2_192PolyError;
 use gf2_192::Gf2_192Error;
 use std::convert::TryInto;
 
-pub use context_extension::*;
 use ergotree_ir::ergo_tree::ErgoTree;
 use ergotree_ir::ergo_tree::ErgoTreeError;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaConjecture;
@@ -53,8 +51,8 @@ use super::unproven_tree::UnprovenTree;
 use super::FirstProverMessage::FirstDhtProverMessage;
 use super::FirstProverMessage::FirstDlogProverMessage;
 
-use crate::eval::context::Context;
 use crate::eval::EvalError;
+use ergotree_ir::chain::context::Context;
 
 use crate::sigma_protocol::dht_protocol::SecondDhTupleProverMessage;
 use crate::sigma_protocol::dlog_protocol::SecondDlogProverMessage;
@@ -143,9 +141,8 @@ pub trait Prover {
         message: &[u8],
         hints_bag: &HintsBag,
     ) -> Result<ProverResult, ProverError> {
-        let expr = tree.proposition()?;
         let ctx_ext = ctx.extension.clone();
-        let reduction_result = reduce_to_crypto(&expr, ctx).map_err(ProverError::EvalError)?;
+        let reduction_result = reduce_to_crypto(tree, ctx).map_err(ProverError::EvalError)?;
         self.generate_proof(reduction_result.sigma_prop, message, hints_bag)
             .map(|p| ProverResult {
                 proof: p,
diff --git a/ergotree-interpreter/src/sigma_protocol/prover/prover_result.rs b/ergotree-interpreter/src/sigma_protocol/prover/prover_result.rs
index 596f73f7d..be47c51ea 100644
--- a/ergotree-interpreter/src/sigma_protocol/prover/prover_result.rs
+++ b/ergotree-interpreter/src/sigma_protocol/prover/prover_result.rs
@@ -1,11 +1,11 @@
 //! ProverResult
+use ergotree_ir::chain::context_extension::ContextExtension;
 use ergotree_ir::serialization::sigma_byte_reader::SigmaByteRead;
 use ergotree_ir::serialization::sigma_byte_writer::SigmaByteWrite;
 use ergotree_ir::serialization::SigmaParsingError;
 use ergotree_ir::serialization::SigmaSerializable;
 use ergotree_ir::serialization::SigmaSerializeResult;
 
-use super::ContextExtension;
 use std::convert::TryFrom;
 
 /// Serialized proof generated by ['Prover']
diff --git a/ergotree-interpreter/src/sigma_protocol/verifier.rs b/ergotree-interpreter/src/sigma_protocol/verifier.rs
index 5d2ba9c32..a08569369 100644
--- a/ergotree-interpreter/src/sigma_protocol/verifier.rs
+++ b/ergotree-interpreter/src/sigma_protocol/verifier.rs
@@ -13,10 +13,10 @@ use super::{
     unchecked_tree::{UncheckedLeaf, UncheckedSchnorr},
     SigmaBoolean, UncheckedTree,
 };
-use crate::eval::context::Context;
 use crate::eval::EvalError;
 use crate::eval::{reduce_to_crypto, ReductionDiagnosticInfo};
 use dlog_protocol::FirstDlogProverMessage;
+use ergotree_ir::chain::context::Context;
 use ergotree_ir::ergo_tree::ErgoTree;
 use ergotree_ir::ergo_tree::ErgoTreeError;
 
@@ -64,8 +64,7 @@ pub trait Verifier {
         proof: ProofBytes,
         message: &[u8],
     ) -> Result<VerificationResult, VerifierError> {
-        let expr = tree.proposition()?;
-        let reduction_result = reduce_to_crypto(&expr, ctx)?;
+        let reduction_result = reduce_to_crypto(tree, ctx)?;
         let res: bool = match reduction_result.sigma_prop {
             SigmaBoolean::TrivialProp(b) => b,
             sb => {
diff --git a/ergotree-ir/src/chain.rs b/ergotree-ir/src/chain.rs
index 5c3d826e0..11a2895c5 100644
--- a/ergotree-ir/src/chain.rs
+++ b/ergotree-ir/src/chain.rs
@@ -1,6 +1,8 @@
 //! On-chain types
 
 pub mod address;
+pub mod context;
+pub mod context_extension;
 pub mod ergo_box;
 #[cfg(feature = "json")]
 pub mod json;
diff --git a/ergotree-interpreter/src/eval/context.rs b/ergotree-ir/src/chain/context.rs
similarity index 96%
rename from ergotree-interpreter/src/eval/context.rs
rename to ergotree-ir/src/chain/context.rs
index 5858f4cb2..9162cbab1 100644
--- a/ergotree-interpreter/src/eval/context.rs
+++ b/ergotree-ir/src/chain/context.rs
@@ -1,7 +1,8 @@
-use crate::sigma_protocol::prover::ContextExtension;
+//! Context(blockchain) for the interpreter
+use crate::chain::context_extension::ContextExtension;
+use crate::chain::ergo_box::ErgoBox;
 use bounded_vec::BoundedVec;
 use ergo_chain_types::{Header, PreHeader};
-use ergotree_ir::chain::ergo_box::ErgoBox;
 
 /// BoundedVec type for Tx inputs, output_candidates and outputs
 pub type TxIoVec<T> = BoundedVec<T, 1, { i16::MAX as usize }>;
diff --git a/ergotree-interpreter/src/sigma_protocol/prover/context_extension.rs b/ergotree-ir/src/chain/context_extension.rs
similarity index 90%
rename from ergotree-interpreter/src/sigma_protocol/prover/context_extension.rs
rename to ergotree-ir/src/chain/context_extension.rs
index ed245147f..8197ee048 100644
--- a/ergotree-interpreter/src/sigma_protocol/prover/context_extension.rs
+++ b/ergotree-ir/src/chain/context_extension.rs
@@ -1,10 +1,10 @@
 //! ContextExtension type
-use ergotree_ir::mir::constant::Constant;
-use ergotree_ir::serialization::sigma_byte_reader::SigmaByteRead;
-use ergotree_ir::serialization::sigma_byte_writer::SigmaByteWrite;
-use ergotree_ir::serialization::SigmaParsingError;
-use ergotree_ir::serialization::SigmaSerializable;
-use ergotree_ir::serialization::SigmaSerializeResult;
+use crate::mir::constant::Constant;
+use crate::serialization::sigma_byte_reader::SigmaByteRead;
+use crate::serialization::sigma_byte_writer::SigmaByteWrite;
+use crate::serialization::SigmaParsingError;
+use crate::serialization::SigmaSerializable;
+use crate::serialization::SigmaSerializeResult;
 use indexmap::IndexMap;
 use std::convert::TryFrom;
 use std::fmt;
@@ -120,7 +120,7 @@ mod arbitrary {
 #[allow(clippy::panic)]
 mod tests {
     use super::*;
-    use ergotree_ir::serialization::sigma_serialize_roundtrip;
+    use crate::serialization::sigma_serialize_roundtrip;
     use proptest::prelude::*;
 
     proptest! {
diff --git a/ergotree-ir/src/chain/ergo_box/register/id.rs b/ergotree-ir/src/chain/ergo_box/register/id.rs
index 65355bdb4..85bf1cca3 100644
--- a/ergotree-ir/src/chain/ergo_box/register/id.rs
+++ b/ergotree-ir/src/chain/ergo_box/register/id.rs
@@ -54,6 +54,17 @@ impl TryFrom<u8> for RegisterId {
     }
 }
 
+impl From<RegisterId> for u8 {
+    fn from(value: RegisterId) -> Self {
+        match value {
+            RegisterId::MandatoryRegisterId(mandatory_register_id) => mandatory_register_id as u8,
+            RegisterId::NonMandatoryRegisterId(non_mandatory_register_id) => {
+                non_mandatory_register_id as u8
+            }
+        }
+    }
+}
+
 impl Display for RegisterId {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         match self {
@@ -65,6 +76,7 @@ impl Display for RegisterId {
 
 /// Register ids that every box have (box properties exposed as registers)
 #[derive(PartialEq, Eq, Debug, Clone, Copy, derive_more::Display)]
+#[repr(u8)]
 pub enum MandatoryRegisterId {
     /// Monetary value, in Ergo tokens
     R0 = 0,
diff --git a/ergotree-ir/src/ergo_tree.rs b/ergotree-ir/src/ergo_tree.rs
index d7fcaa086..7c7942a3e 100644
--- a/ergotree-ir/src/ergo_tree.rs
+++ b/ergotree-ir/src/ergo_tree.rs
@@ -18,17 +18,19 @@ use crate::serialization::constant_store::ConstantStore;
 use derive_more::From;
 use std::convert::TryFrom;
 use std::io;
+use std::sync::OnceLock;
 use thiserror::Error;
 
 mod tree_header;
 pub use tree_header::*;
 
 /// Parsed ErgoTree
-#[derive(PartialEq, Eq, Debug, Clone)]
+#[derive(Eq, Debug, Clone)]
 pub struct ParsedErgoTree {
     header: ErgoTreeHeader,
     constants: Vec<Constant>,
     root: Expr,
+    has_deserialize: OnceLock<bool>,
 }
 
 impl ParsedErgoTree {
@@ -63,6 +65,12 @@ impl ParsedErgoTree {
     }
 }
 
+impl PartialEq for ParsedErgoTree {
+    fn eq(&self, other: &Self) -> bool {
+        self.header == other.header && self.constants == other.constants && self.root == other.root
+    }
+}
+
 /// Errors on fail to set a new constant value
 #[derive(Error, PartialEq, Eq, Debug, Clone)]
 pub enum SetConstantError {
@@ -146,7 +154,11 @@ impl ErgoTree {
             vec![]
         };
         r.set_constant_store(ConstantStore::new(constants.clone()));
+        let was_deserialize = r.was_deserialize();
+        r.set_deserialize(false);
         let root = Expr::sigma_parse(r)?;
+        let has_deserialize = r.was_deserialize();
+        r.set_deserialize(was_deserialize);
         if root.tpe() != SType::SSigmaProp {
             return Err(ErgoTreeError::RootTpeError(root.tpe()));
         }
@@ -154,6 +166,7 @@ impl ErgoTree {
             header,
             constants,
             root,
+            has_deserialize: has_deserialize.into(),
         })
     }
 
@@ -195,12 +208,14 @@ impl ErgoTree {
                 header,
                 constants,
                 root: parsed_expr,
+                has_deserialize: OnceLock::new(),
             })
         } else {
             ErgoTree::Parsed(ParsedErgoTree {
                 header,
                 constants: Vec::new(),
                 root: expr.clone(),
+                has_deserialize: OnceLock::new(),
             })
         })
     }
@@ -211,28 +226,29 @@ impl ErgoTree {
     /// get Expr out of ErgoTree
     pub fn proposition(&self) -> Result<Expr, ErgoTreeError> {
         let tree = self.parsed_tree()?.clone();
+        let root = tree.root;
         // This tree has ConstantPlaceholder nodes instead of Constant nodes.
         // We need to substitute placeholders with constant values.
-        // So far the easiest way to do it is during deserialization (after the serialization)
-        let root = tree.root;
         if tree.header.is_constant_segregation() {
-            let mut data = Vec::new();
-            let constants = {
-                let cs = ConstantStore::new(tree.constants.clone());
-                let mut w = SigmaByteWriter::new(&mut data, Some(cs));
-                root.sigma_serialize(&mut w)?;
-                #[allow(clippy::unwrap_used)] // constant store is specified in SigmaByteWriter::new
-                w.constant_store.unwrap()
-            };
-            let cursor = Cursor::new(&mut data[..]);
-            let mut sr = SigmaByteReader::new_with_substitute_placeholders(cursor, constants);
-            let parsed_expr = Expr::sigma_parse(&mut sr)?;
-            Ok(parsed_expr)
+            Ok(root.substitute_constants(&tree.constants)?)
         } else {
             Ok(root)
         }
     }
 
+    /// Check if ErgoTree root has [`crate::mir::deserialize_context::DeserializeContext`] or [`crate::mir::deserialize_register::DeserializeRegister`] nodes
+    pub fn has_deserialize(&self) -> bool {
+        match self {
+            ErgoTree::Unparsed { .. } => false,
+            ErgoTree::Parsed(ParsedErgoTree {
+                header: _,
+                constants: _,
+                root,
+                has_deserialize,
+            }) => *has_deserialize.get_or_init(|| root.has_deserialize()),
+        }
+    }
+
     /// Prints with newlines
     pub fn debug_tree(&self) -> String {
         let tree = format!("{:#?}", self);
@@ -384,6 +400,7 @@ impl SigmaSerializable for ErgoTree {
                 header,
                 constants,
                 root,
+                has_deserialize: OnceLock::new(),
             }))
         }
     }
@@ -459,6 +476,7 @@ pub(crate) mod arbitrary {
 
 #[cfg(test)]
 #[cfg(feature = "arbitrary")]
+#[allow(clippy::unreachable)]
 #[allow(clippy::unwrap_used)]
 #[allow(clippy::panic)]
 #[allow(clippy::expect_used)]
@@ -466,7 +484,9 @@ mod tests {
     use super::*;
     use crate::chain::address::AddressEncoder;
     use crate::chain::address::NetworkPrefix;
+    use crate::mir::bool_to_sigma::BoolToSigmaProp;
     use crate::mir::constant::Literal;
+    use crate::mir::deserialize_context::DeserializeContext;
     use crate::sigma_protocol::sigma_boolean::SigmaProp;
     use proptest::prelude::*;
 
@@ -715,4 +735,36 @@ mod tests {
         let tree = ErgoTree::sigma_parse_bytes(&bytes).unwrap();
         tree.proposition().unwrap();
     }
+
+    fn has_deserialize(tree: ErgoTree) -> bool {
+        let ErgoTree::Parsed(ParsedErgoTree {
+            has_deserialize, ..
+        }) = ErgoTree::sigma_parse_bytes(&tree.sigma_serialize_bytes().unwrap()).unwrap()
+        else {
+            unreachable!();
+        };
+        *has_deserialize.get().unwrap()
+    }
+
+    #[test]
+    fn test_lazy_has_deserialize() {
+        let has_deserialize_expr: Expr = BoolToSigmaProp {
+            input: Box::new(
+                DeserializeContext {
+                    tpe: SType::SBoolean,
+                    id: 0,
+                }
+                .into(),
+            ),
+        }
+        .into();
+        let tree = ErgoTree::new(ErgoTreeHeader::v1(false), &has_deserialize_expr).unwrap();
+        assert!(has_deserialize(tree));
+        let no_deserialize_expr: Expr = BoolToSigmaProp {
+            input: Box::new(true.into()),
+        }
+        .into();
+        let tree = ErgoTree::new(ErgoTreeHeader::v1(false), &no_deserialize_expr).unwrap();
+        assert!(!has_deserialize(tree));
+    }
 }
diff --git a/ergotree-ir/src/lib.rs b/ergotree-ir/src/lib.rs
index 711a9a2d0..37e697db6 100644
--- a/ergotree-ir/src/lib.rs
+++ b/ergotree-ir/src/lib.rs
@@ -31,5 +31,7 @@ pub mod reference;
 pub mod serialization;
 pub mod sigma_protocol;
 pub mod source_span;
+#[macro_use]
+pub mod traversable;
 pub mod type_check;
 pub mod types;
diff --git a/ergotree-ir/src/mir/and.rs b/ergotree-ir/src/mir/and.rs
index e5c680bcb..10d41b65a 100644
--- a/ergotree-ir/src/mir/and.rs
+++ b/ergotree-ir/src/mir/and.rs
@@ -6,6 +6,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 use super::expr::Expr;
@@ -41,6 +42,8 @@ impl SigmaSerializable for And {
     }
 }
 
+impl_traversable_expr!(And, boxed input);
+
 /// Arbitrary impl
 #[cfg(feature = "arbitrary")]
 mod arbitrary {
diff --git a/ergotree-ir/src/mir/apply.rs b/ergotree-ir/src/mir/apply.rs
index 60ec67788..8660b45f4 100644
--- a/ergotree-ir/src/mir/apply.rs
+++ b/ergotree-ir/src/mir/apply.rs
@@ -6,6 +6,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 use super::expr::Expr;
@@ -71,6 +72,8 @@ impl SigmaSerializable for Apply {
     }
 }
 
+impl_traversable_expr!(Apply, boxed func, arr args);
+
 /// Arbitrary impl
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used)]
diff --git a/ergotree-ir/src/mir/atleast.rs b/ergotree-ir/src/mir/atleast.rs
index e3eb7f780..cf42750dd 100644
--- a/ergotree-ir/src/mir/atleast.rs
+++ b/ergotree-ir/src/mir/atleast.rs
@@ -5,6 +5,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 use super::expr::Expr;
@@ -65,6 +66,8 @@ impl SigmaSerializable for Atleast {
     }
 }
 
+impl_traversable_expr!(Atleast, boxed bound, boxed input);
+
 /// Arbitrary impl
 #[cfg(feature = "arbitrary")]
 mod arbitrary {
diff --git a/ergotree-ir/src/mir/bin_op.rs b/ergotree-ir/src/mir/bin_op.rs
index cc82e4d8c..3df3054a7 100644
--- a/ergotree-ir/src/mir/bin_op.rs
+++ b/ergotree-ir/src/mir/bin_op.rs
@@ -5,6 +5,7 @@ use std::fmt::Display;
 use super::expr::Expr;
 use crate::has_opcode::HasOpCode;
 use crate::serialization::op_code::OpCode;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 extern crate derive_more;
@@ -234,6 +235,8 @@ impl HasOpCode for BinOp {
     }
 }
 
+impl_traversable_expr!(BinOp, boxed left, boxed right);
+
 #[cfg(feature = "arbitrary")]
 /// Arbitrary impl
 mod arbitrary {
diff --git a/ergotree-ir/src/mir/bit_inversion.rs b/ergotree-ir/src/mir/bit_inversion.rs
index 8ae8f4e0e..2cedd892d 100644
--- a/ergotree-ir/src/mir/bit_inversion.rs
+++ b/ergotree-ir/src/mir/bit_inversion.rs
@@ -28,6 +28,9 @@ impl OneArgOp for BitInversion {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for BitInversion {
diff --git a/ergotree-ir/src/mir/block.rs b/ergotree-ir/src/mir/block.rs
index 186771970..6ecae13d2 100644
--- a/ergotree-ir/src/mir/block.rs
+++ b/ergotree-ir/src/mir/block.rs
@@ -8,6 +8,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 /** Block of statements ending with an expression
@@ -53,6 +54,8 @@ impl SigmaSerializable for BlockValue {
     }
 }
 
+impl_traversable_expr!(BlockValue, arr items, boxed result);
+
 /// Arbitrary impl
 #[cfg(feature = "arbitrary")]
 mod arbitrary {
diff --git a/ergotree-ir/src/mir/bool_to_sigma.rs b/ergotree-ir/src/mir/bool_to_sigma.rs
index 01e035d56..9a020632d 100644
--- a/ergotree-ir/src/mir/bool_to_sigma.rs
+++ b/ergotree-ir/src/mir/bool_to_sigma.rs
@@ -33,6 +33,9 @@ impl OneArgOp for BoolToSigmaProp {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for BoolToSigmaProp {
diff --git a/ergotree-ir/src/mir/byte_array_to_bigint.rs b/ergotree-ir/src/mir/byte_array_to_bigint.rs
index df4a0c7dc..bfcd774ad 100644
--- a/ergotree-ir/src/mir/byte_array_to_bigint.rs
+++ b/ergotree-ir/src/mir/byte_array_to_bigint.rs
@@ -32,6 +32,9 @@ impl OneArgOp for ByteArrayToBigInt {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for ByteArrayToBigInt {
diff --git a/ergotree-ir/src/mir/byte_array_to_long.rs b/ergotree-ir/src/mir/byte_array_to_long.rs
index 68e67b0a6..87029e66b 100644
--- a/ergotree-ir/src/mir/byte_array_to_long.rs
+++ b/ergotree-ir/src/mir/byte_array_to_long.rs
@@ -32,6 +32,9 @@ impl OneArgOp for ByteArrayToLong {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for ByteArrayToLong {
diff --git a/ergotree-ir/src/mir/calc_blake2b256.rs b/ergotree-ir/src/mir/calc_blake2b256.rs
index 20b6a4427..afb84f892 100644
--- a/ergotree-ir/src/mir/calc_blake2b256.rs
+++ b/ergotree-ir/src/mir/calc_blake2b256.rs
@@ -31,6 +31,9 @@ impl OneArgOp for CalcBlake2b256 {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for CalcBlake2b256 {
diff --git a/ergotree-ir/src/mir/calc_sha256.rs b/ergotree-ir/src/mir/calc_sha256.rs
index 2f43b80fe..d36897286 100644
--- a/ergotree-ir/src/mir/calc_sha256.rs
+++ b/ergotree-ir/src/mir/calc_sha256.rs
@@ -31,6 +31,9 @@ impl OneArgOp for CalcSha256 {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for CalcSha256 {
diff --git a/ergotree-ir/src/mir/coll_append.rs b/ergotree-ir/src/mir/coll_append.rs
index 390ca5373..8fc9bd8d7 100644
--- a/ergotree-ir/src/mir/coll_append.rs
+++ b/ergotree-ir/src/mir/coll_append.rs
@@ -4,6 +4,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 // use crate::types::stuple::STuple;
 use crate::types::stype::SType;
 
@@ -39,11 +40,11 @@ impl Append {
             }
             (_, SType::SColl(_)) => {
                 Err(InvalidArgumentError(format!(
-                    "Expected Append input param to be a collection; got input={:?}", input.tpe())))   
+                    "Expected Append input param to be a collection; got input={:?}", input.tpe())))
             },
             (_, _) => {
                 Err(InvalidArgumentError(format!(
-                    "Expected Append input and col_2 param to be a collection; got input={:?} col_2={:?}", input.tpe(), col_2.tpe())))   
+                    "Expected Append input and col_2 param to be a collection; got input={:?} col_2={:?}", input.tpe(), col_2.tpe())))
             }
         }
     }
@@ -75,6 +76,8 @@ impl SigmaSerializable for Append {
     }
 }
 
+impl_traversable_expr!(Append, boxed input, boxed col_2);
+
 #[cfg(test)]
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::panic)]
diff --git a/ergotree-ir/src/mir/coll_by_index.rs b/ergotree-ir/src/mir/coll_by_index.rs
index 836afd574..8cedfc7ba 100644
--- a/ergotree-ir/src/mir/coll_by_index.rs
+++ b/ergotree-ir/src/mir/coll_by_index.rs
@@ -6,6 +6,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 use super::expr::Expr;
@@ -88,6 +89,8 @@ impl SigmaSerializable for ByIndex {
     }
 }
 
+impl_traversable_expr!(ByIndex, boxed input, boxed index, opt default);
+
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used)]
 /// Arbitrary impl
diff --git a/ergotree-ir/src/mir/coll_exists.rs b/ergotree-ir/src/mir/coll_exists.rs
index 4092d3c44..b605181bf 100644
--- a/ergotree-ir/src/mir/coll_exists.rs
+++ b/ergotree-ir/src/mir/coll_exists.rs
@@ -9,6 +9,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 /// Tests whether a predicate holds for at least one element of this collection
@@ -74,6 +75,8 @@ impl SigmaSerializable for Exists {
     }
 }
 
+impl_traversable_expr!(Exists, boxed input, boxed condition);
+
 #[allow(clippy::unwrap_used)]
 #[cfg(feature = "arbitrary")]
 /// Arbitrary impl
diff --git a/ergotree-ir/src/mir/coll_filter.rs b/ergotree-ir/src/mir/coll_filter.rs
index 9b5e5f777..b245da250 100644
--- a/ergotree-ir/src/mir/coll_filter.rs
+++ b/ergotree-ir/src/mir/coll_filter.rs
@@ -9,6 +9,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 /// Selects all elements of the collection that satisfy the condition
@@ -74,6 +75,8 @@ impl SigmaSerializable for Filter {
     }
 }
 
+impl_traversable_expr!(Filter, boxed input, boxed condition);
+
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used)]
 /// Arbitrary impl
diff --git a/ergotree-ir/src/mir/coll_fold.rs b/ergotree-ir/src/mir/coll_fold.rs
index 15d2b8ba6..bd9f96f3c 100644
--- a/ergotree-ir/src/mir/coll_fold.rs
+++ b/ergotree-ir/src/mir/coll_fold.rs
@@ -4,6 +4,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stuple::STuple;
 use crate::types::stype::SType;
 
@@ -80,6 +81,8 @@ impl SigmaSerializable for Fold {
     }
 }
 
+impl_traversable_expr!(Fold, boxed input, boxed zero, boxed fold_op);
+
 #[cfg(test)]
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::panic)]
diff --git a/ergotree-ir/src/mir/coll_forall.rs b/ergotree-ir/src/mir/coll_forall.rs
index 75ea1cb4c..75f375525 100644
--- a/ergotree-ir/src/mir/coll_forall.rs
+++ b/ergotree-ir/src/mir/coll_forall.rs
@@ -9,6 +9,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 /// Tests whether a predicate holds for all elements of this collection.
@@ -74,6 +75,8 @@ impl SigmaSerializable for ForAll {
     }
 }
 
+impl_traversable_expr!(ForAll, boxed input, boxed condition);
+
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used)]
 /// Arbitrary impl
diff --git a/ergotree-ir/src/mir/coll_map.rs b/ergotree-ir/src/mir/coll_map.rs
index d252d40b5..42f3d85f7 100644
--- a/ergotree-ir/src/mir/coll_map.rs
+++ b/ergotree-ir/src/mir/coll_map.rs
@@ -4,6 +4,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::sfunc::SFunc;
 use crate::types::stype::SType;
 
@@ -75,6 +76,8 @@ impl SigmaSerializable for Map {
     }
 }
 
+impl_traversable_expr!(Map, boxed input, boxed mapper);
+
 #[cfg(feature = "arbitrary")]
 /// Arbitrary impl
 #[allow(clippy::unwrap_used)]
diff --git a/ergotree-ir/src/mir/coll_size.rs b/ergotree-ir/src/mir/coll_size.rs
index ef676b6e6..f837ee403 100644
--- a/ergotree-ir/src/mir/coll_size.rs
+++ b/ergotree-ir/src/mir/coll_size.rs
@@ -29,6 +29,9 @@ impl OneArgOp for SizeOf {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for SizeOf {
diff --git a/ergotree-ir/src/mir/coll_slice.rs b/ergotree-ir/src/mir/coll_slice.rs
index 2a5dc3bb3..3d2bc06e0 100644
--- a/ergotree-ir/src/mir/coll_slice.rs
+++ b/ergotree-ir/src/mir/coll_slice.rs
@@ -4,6 +4,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 use super::expr::Expr;
@@ -77,6 +78,8 @@ impl SigmaSerializable for Slice {
     }
 }
 
+impl_traversable_expr!(Slice, boxed input, boxed from, boxed until);
+
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used)]
 mod arbitrary {
diff --git a/ergotree-ir/src/mir/collection.rs b/ergotree-ir/src/mir/collection.rs
index 574a082bd..4b653f4f5 100644
--- a/ergotree-ir/src/mir/collection.rs
+++ b/ergotree-ir/src/mir/collection.rs
@@ -5,6 +5,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::Traversable;
 use crate::types::stype::SType;
 
 use super::constant::Constant;
@@ -77,6 +78,22 @@ impl HasOpCode for Collection {
     }
 }
 
+impl Traversable for Collection {
+    type Item = Expr;
+    fn children(&self) -> Box<dyn Iterator<Item = &Expr> + '_> {
+        match self {
+            Self::Exprs { elem_tpe: _, items } => Box::new(items.iter()),
+            Self::BoolConstants(_) => Box::new(std::iter::empty()),
+        }
+    }
+    fn children_mut(&mut self) -> Box<dyn Iterator<Item = &mut Expr> + '_> {
+        match self {
+            Self::Exprs { elem_tpe: _, items } => Box::new(items.iter_mut()),
+            Self::BoolConstants(_) => Box::new(std::iter::empty()),
+        }
+    }
+}
+
 pub(crate) fn coll_sigma_serialize<W: SigmaByteWrite>(
     coll: &Collection,
     w: &mut W,
diff --git a/ergotree-ir/src/mir/create_avl_tree.rs b/ergotree-ir/src/mir/create_avl_tree.rs
index 48678300c..0ef8feb8d 100644
--- a/ergotree-ir/src/mir/create_avl_tree.rs
+++ b/ergotree-ir/src/mir/create_avl_tree.rs
@@ -7,6 +7,7 @@ use crate::serialization::op_code::OpCode;
 use crate::serialization::sigma_byte_reader::SigmaByteRead;
 use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::{SigmaParsingError, SigmaSerializable, SigmaSerializeResult};
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 /// Creates an AVL tree
@@ -79,6 +80,8 @@ impl SigmaSerializable for CreateAvlTree {
     }
 }
 
+impl_traversable_expr!(CreateAvlTree, boxed flags, boxed digest, boxed key_length, opt value_length);
+
 #[allow(clippy::unwrap_used)]
 #[cfg(feature = "arbitrary")]
 /// Arbitrary impl
diff --git a/ergotree-ir/src/mir/create_prove_dh_tuple.rs b/ergotree-ir/src/mir/create_prove_dh_tuple.rs
index c2a20167d..3da6f8563 100644
--- a/ergotree-ir/src/mir/create_prove_dh_tuple.rs
+++ b/ergotree-ir/src/mir/create_prove_dh_tuple.rs
@@ -4,6 +4,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 use super::expr::Expr;
@@ -66,6 +67,8 @@ impl SigmaSerializable for CreateProveDhTuple {
     }
 }
 
+impl_traversable_expr!(CreateProveDhTuple, boxed g, boxed h, boxed u, boxed v);
+
 #[cfg(test)]
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used)]
diff --git a/ergotree-ir/src/mir/create_provedlog.rs b/ergotree-ir/src/mir/create_provedlog.rs
index f73f13820..f7828ca94 100644
--- a/ergotree-ir/src/mir/create_provedlog.rs
+++ b/ergotree-ir/src/mir/create_provedlog.rs
@@ -29,6 +29,9 @@ impl OneArgOp for CreateProveDlog {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for CreateProveDlog {
diff --git a/ergotree-ir/src/mir/decode_point.rs b/ergotree-ir/src/mir/decode_point.rs
index 31cc1750b..8db2d17ff 100644
--- a/ergotree-ir/src/mir/decode_point.rs
+++ b/ergotree-ir/src/mir/decode_point.rs
@@ -33,6 +33,9 @@ impl OneArgOp for DecodePoint {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for DecodePoint {
diff --git a/ergotree-ir/src/mir/deserialize_context.rs b/ergotree-ir/src/mir/deserialize_context.rs
index 4c668bebf..9a49ca0d3 100644
--- a/ergotree-ir/src/mir/deserialize_context.rs
+++ b/ergotree-ir/src/mir/deserialize_context.rs
@@ -7,8 +7,11 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
+use super::expr::Expr;
+
 /// Extracts context variable as `Coll[Byte]`, deserializes it to script and then executes
 /// this script in the current context. The original `Coll[Byte]` of the script is
 /// available as `getVar[Coll[Byte]](id)` On evaluation returns the result of the
@@ -39,12 +42,15 @@ impl SigmaSerializable for DeserializeContext {
     }
 
     fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SigmaParsingError> {
+        r.set_deserialize(true);
         let tpe = SType::sigma_parse(r)?;
         let id = r.get_u8()?;
         Ok(Self { tpe, id })
     }
 }
 
+impl_traversable_expr!(DeserializeContext);
+
 #[cfg(feature = "arbitrary")]
 /// Arbitrary impl
 mod arbitrary {
diff --git a/ergotree-ir/src/mir/deserialize_register.rs b/ergotree-ir/src/mir/deserialize_register.rs
index a751d4286..33ab5645f 100644
--- a/ergotree-ir/src/mir/deserialize_register.rs
+++ b/ergotree-ir/src/mir/deserialize_register.rs
@@ -1,6 +1,8 @@
 //! Extract register of SELF box as `Coll[Byte]`, deserialize it into Value and inline into executing script.
 
 use super::expr::Expr;
+use super::expr::InvalidArgumentError;
+use crate::chain::ergo_box::RegisterId;
 use crate::has_opcode::HasStaticOpCode;
 use crate::serialization::op_code::OpCode;
 use crate::serialization::sigma_byte_reader::SigmaByteRead;
@@ -8,19 +10,29 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 /// Extract register of SELF box as `Coll[Byte]`, deserialize and execute Expr out of it
 #[derive(PartialEq, Eq, Debug, Clone)]
 pub struct DeserializeRegister {
     /// Register number (0 .. =9 for R0-R9 registers)
-    pub reg: u8,
+    pub reg: RegisterId,
     /// Type of expression serialized in register
     pub tpe: SType,
     /// Default value (expression that would be executed if register is empty)
     pub default: Option<Box<Expr>>,
 }
+
 impl DeserializeRegister {
+    /// Create new object, returns an error if any of the requirements failed
+    pub fn new(
+        reg: RegisterId,
+        tpe: SType,
+        default: Option<Box<Expr>>,
+    ) -> Result<Self, InvalidArgumentError> {
+        Ok(Self { reg, tpe, default })
+    }
     /// Type
     pub fn tpe(&self) -> SType {
         self.tpe.clone()
@@ -33,20 +45,26 @@ impl HasStaticOpCode for DeserializeRegister {
 
 impl SigmaSerializable for DeserializeRegister {
     fn sigma_serialize<W: SigmaByteWrite>(&self, w: &mut W) -> SigmaSerializeResult {
-        w.put_u8(self.reg)?;
+        w.put_u8(self.reg.into())?;
         self.tpe.sigma_serialize(w)?;
         self.default.sigma_serialize(w)
     }
 
     fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SigmaParsingError> {
-        let reg = r.get_u8()?;
+        r.set_deserialize(true);
+        let reg = RegisterId::try_from(r.get_u8()?).map_err(|_| {
+            InvalidArgumentError("DeserializeRegister: register id out of bounds".to_string())
+        })?;
         let tpe = SType::sigma_parse(r)?;
         let default = Option::<Box<Expr>>::sigma_parse(r)?;
-        Ok(Self { reg, tpe, default })
+        Ok(Self::new(reg, tpe, default)?)
     }
 }
 
+impl_traversable_expr!(DeserializeRegister, opt default);
+
 #[cfg(feature = "arbitrary")]
+#[allow(clippy::unwrap_used)]
 /// Arbitrary impl
 mod arbitrary {
     use crate::mir::expr::arbitrary::ArbExprParams;
@@ -72,7 +90,11 @@ mod arbitrary {
                     .prop_map(Box::new),
                 ),
             )
-                .prop_map(|(reg, tpe, default)| Self { reg, tpe, default })
+                .prop_map(|(reg, tpe, default)| Self {
+                    reg: reg.try_into().unwrap(),
+                    tpe,
+                    default,
+                })
                 .boxed()
         }
     }
diff --git a/ergotree-ir/src/mir/downcast.rs b/ergotree-ir/src/mir/downcast.rs
index f3f3ec582..0b9a34e1c 100644
--- a/ergotree-ir/src/mir/downcast.rs
+++ b/ergotree-ir/src/mir/downcast.rs
@@ -8,6 +8,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 use crate::has_opcode::HasStaticOpCode;
@@ -67,6 +68,8 @@ impl SigmaSerializable for Downcast {
     }
 }
 
+impl_traversable_expr!(Downcast, boxed input);
+
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used)]
 /// Arbitrary impl
diff --git a/ergotree-ir/src/mir/exponentiate.rs b/ergotree-ir/src/mir/exponentiate.rs
index f53a545ad..a93cebc81 100644
--- a/ergotree-ir/src/mir/exponentiate.rs
+++ b/ergotree-ir/src/mir/exponentiate.rs
@@ -4,6 +4,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 use super::expr::Expr;
@@ -57,6 +58,8 @@ impl SigmaSerializable for Exponentiate {
     }
 }
 
+impl_traversable_expr!(Exponentiate, boxed left, boxed right);
+
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used)]
 mod arbitrary {
diff --git a/ergotree-ir/src/mir/expr.rs b/ergotree-ir/src/mir/expr.rs
index 3744af858..6e8a5f62b 100644
--- a/ergotree-ir/src/mir/expr.rs
+++ b/ergotree-ir/src/mir/expr.rs
@@ -1,11 +1,19 @@
 //! IR expression
 
+use std::convert::Infallible;
 use std::convert::TryFrom;
 use std::convert::TryInto;
 
+use crate::chain::context::Context;
+use crate::chain::ergo_box::RegisterId;
+use crate::chain::ergo_box::RegisterIdOutOfBounds;
+use crate::chain::ergo_box::RegisterValueError;
 use crate::pretty_printer::PosTrackingWriter;
 use crate::pretty_printer::Print;
+use crate::serialization::SigmaParsingError;
+use crate::serialization::SigmaSerializable;
 use crate::source_span::Spanned;
+use crate::traversable::Traversable;
 use crate::types::stype::LiftIntoSType;
 use crate::types::stype::SType;
 
@@ -33,6 +41,7 @@ use super::constant::ConstantPlaceholder;
 use super::constant::Literal;
 use super::constant::TryExtractFrom;
 use super::constant::TryExtractFromError;
+use super::constant::TryExtractInto;
 use super::create_avl_tree::CreateAvlTree;
 use super::create_provedlog::CreateProveDlog;
 use super::decode_point::DecodePoint;
@@ -325,6 +334,138 @@ impl Expr {
         }
     }
 
+    /// Rewrite tree bottom-up, matching nodes that satisfy `rule` and applying `subst` to them
+    pub fn rewrite_bu(&self, rule: impl Fn(&Expr) -> bool, subst: impl Fn(&mut Expr)) -> Self {
+        let mut new_root = self.clone();
+        Self::rewrite_bu_inner(&mut new_root, &rule, &|node| {
+            Ok::<_, Infallible>(subst(node))
+        })
+        .unwrap();
+        new_root
+    }
+
+    /// Attempt to rewrite tree, returning early if `subst` returns `Err(E)`
+    pub fn try_rewrite_bu<E>(
+        mut self,
+        rule: impl Fn(&Expr) -> bool,
+        subst: impl Fn(&mut Expr) -> Result<(), E>,
+    ) -> Result<Self, E> {
+        Self::rewrite_bu_inner(&mut self, &rule, &subst).map(|_| self)
+    }
+
+    fn rewrite_bu_inner<E>(
+        root: &mut Expr,
+        rule: &impl Fn(&Expr) -> bool,
+        subst: &impl Fn(&mut Expr) -> Result<(), E>,
+    ) -> Result<(), E> {
+        root.children_mut()
+            .try_for_each(|expr| Self::rewrite_bu_inner(expr, rule, subst))?;
+        if rule(root) {
+            subst(root)?;
+        }
+        Ok(())
+    }
+
+    /// Return an iterator over the [`Expr`]
+    /// The iterator performs a pre-order traversal
+    pub fn iter(&self) -> impl Iterator<Item = &Expr> {
+        struct ExprIterator<'a> {
+            stack: Vec<&'a Expr>,
+        }
+        impl<'a> Iterator for ExprIterator<'a> {
+            type Item = &'a Expr;
+
+            fn next(&mut self) -> Option<Self::Item> {
+                let cur = self.stack.pop()?;
+                for node in cur.children() {
+                    self.stack.push(node);
+                }
+                Some(cur)
+            }
+        }
+        ExprIterator { stack: vec![&self] }
+    }
+
+    /// Returns true if the [`Expr`] has deserialize nodes, see: [`DeserializeContext`] and [`DeserializeRegister`]
+    pub(crate) fn has_deserialize(&self) -> bool {
+        self.iter().any(|c| {
+            matches!(
+                c,
+                Expr::DeserializeContext(_) | Expr::DeserializeRegister(_)
+            )
+        })
+    }
+
+    /// Rewrite expr, replacing [`DeserializeContext`] and [`DeserializeRegister`] nodes with their respective context extension/register values
+    pub fn substitute_deserialize(self, ctx: &Context) -> Result<Self, SubstDeserializeError> {
+        self.try_rewrite_bu(
+            |expr| {
+                matches!(
+                    expr,
+                    Expr::DeserializeContext(_) | Expr::DeserializeRegister(_)
+                )
+            },
+            |expr| {
+                let (tpe, parsed_expr): (&mut SType, Expr) = match expr {
+                    Expr::DeserializeContext(DeserializeContext { tpe, id }) => {
+                        let vec = ctx
+                            .extension
+                            .values
+                            .get(&*id)
+                            .ok_or(SubstDeserializeError::ExtensionKeyNotFound(*id))?
+                            .clone()
+                            .try_extract_into::<Vec<u8>>()?;
+                        (tpe, Expr::sigma_parse_bytes(&vec)?)
+                    }
+                    Expr::DeserializeRegister(DeserializeRegister { reg, tpe, default }) => {
+                        let expr = ctx
+                            .self_box
+                            .get_register(*reg)?
+                            .map(|constant| -> Result<_, SubstDeserializeError> {
+                                Ok(Expr::sigma_parse_bytes(
+                                    &constant.try_extract_into::<Vec<u8>>()?,
+                                )?)
+                            })
+                            .transpose()?
+                            .or(default.as_deref().cloned());
+                        match expr {
+                            Some(expr) => (tpe, expr),
+                            None => return Ok(()), // When script in register is not found, and default is not defined, leave DeserializeRegisterNode unchanged, which will error on evaluation
+                        }
+                    }
+                    #[allow(clippy::unreachable)] // Rule is already checked in filter
+                    _ => unreachable!(),
+                };
+                if parsed_expr.tpe() != *tpe {
+                    return Err(SubstDeserializeError::ExprTpeError {
+                        expected: tpe.clone(),
+                        actual: parsed_expr.tpe(),
+                    });
+                }
+                *expr = parsed_expr;
+                Ok(())
+            },
+        )
+    }
+
+    /// Substitute [`ConstantPlaceholder`] nodes in `self` with [`Constant`]
+    /// Errors if a constant can not be found in `constants`
+    pub fn substitute_constants(self, constants: &[Constant]) -> Result<Self, SigmaParsingError> {
+        self.try_rewrite_bu::<SigmaParsingError>(
+            |expr| matches!(expr, Expr::ConstPlaceholder(_)),
+            |expr| {
+                if let Expr::ConstPlaceholder(ConstantPlaceholder { id, tpe: _ }) = expr {
+                    *expr = constants
+                        .get(*id as usize)
+                        .cloned()
+                        .map(Expr::from)
+                        .ok_or(SigmaParsingError::ConstantForPlaceholderNotFound(*id))?;
+                }
+                Ok(())
+            },
+        )
+    }
+
     /// Prints the tree with newlines
     pub fn debug_tree(&self) -> String {
         let tree = format!("{:#?}", self);
@@ -340,6 +481,151 @@ impl Expr {
     }
 }
 
+impl Traversable for Expr {
+    type Item = Expr;
+
+    fn children<'a>(&'a self) -> Box<dyn Iterator<Item = &Expr> + '_> {
+        match self {
+            Expr::Const(_) => Box::new(std::iter::empty()),
+            Expr::SubstConstants(op) => op.children(),
+            Expr::ByteArrayToLong(op) => op.children(),
+            Expr::ByteArrayToBigInt(op) => op.children(),
+            Expr::LongToByteArray(op) => op.children(),
+            Expr::CalcBlake2b256(op) => op.children(),
+            Expr::CalcSha256(op) => op.children(),
+            Expr::Fold(op) => op.children(),
+            Expr::ExtractRegisterAs(op) => op.children(),
+            Expr::GlobalVars(op) => op.children(),
+            Expr::MethodCall(op) => op.children(),
+            Expr::PropertyCall(op) => op.children(),
+            Expr::BinOp(op) => op.children(),
+            Expr::Global => Box::new(std::iter::empty()),
+            Expr::Context => Box::new(std::iter::empty()),
+            Expr::OptionGet(v) => v.children(),
+            Expr::Apply(op) => op.children(),
+            Expr::FuncValue(op) => op.children(),
+            Expr::ValUse(op) => op.children(),
+            Expr::BlockValue(op) => op.children(),
+            Expr::SelectField(op) => op.children(),
+            Expr::ExtractAmount(op) => op.children(),
+            Expr::ConstPlaceholder(_) => Box::new(std::iter::empty()),
+            Expr::Collection(op) => op.children(),
+            Expr::ValDef(op) => op.children(),
+            Expr::And(op) => op.children(),
+            Expr::Or(op) => op.children(),
+            Expr::Xor(op) => op.children(),
+            Expr::Atleast(op) => op.children(),
+            Expr::LogicalNot(op) => op.children(),
+            Expr::Map(op) => op.children(),
+            Expr::Filter(op) => op.children(),
+            Expr::BoolToSigmaProp(op) => op.children(),
+            Expr::Upcast(op) => op.children(),
+            Expr::Downcast(op) => op.children(),
+            Expr::If(op) => op.children(),
+            Expr::Append(op) => op.children(),
+            Expr::ByIndex(op) => op.children(),
+            Expr::ExtractScriptBytes(op) => op.children(),
+            Expr::SizeOf(op) => op.children(),
+            Expr::Slice(op) => op.children(),
+            Expr::CreateProveDlog(op) => op.children(),
+            Expr::CreateProveDhTuple(op) => op.children(),
+            Expr::ExtractCreationInfo(op) => op.children(),
+            Expr::Exists(op) => op.children(),
+            Expr::ExtractId(op) => op.children(),
+            Expr::SigmaPropBytes(op) => op.children(),
+            Expr::OptionIsDefined(op) => op.children(),
+            Expr::OptionGetOrElse(op) => op.children(),
+            Expr::Negation(op) => op.children(),
+            Expr::BitInversion(op) => op.children(),
+            Expr::ForAll(op) => op.children(),
+            Expr::Tuple(op) => op.children(),
+            Expr::DecodePoint(op) => op.children(),
+            Expr::SigmaAnd(op) => op.children(),
+            Expr::SigmaOr(op) => op.children(),
+            Expr::DeserializeRegister(op) => op.children(),
+            Expr::DeserializeContext(op) => op.children(),
+            Expr::GetVar(op) => op.children(),
+            Expr::MultiplyGroup(op) => op.children(),
+            Expr::Exponentiate(op) => op.children(),
+            Expr::XorOf(op) => op.children(),
+            Expr::ExtractBytes(op) => op.children(),
+            Expr::ExtractBytesWithNoRef(op) => op.children(),
+            Expr::TreeLookup(op) => op.children(),
+            Expr::CreateAvlTree(op) => op.children(),
+        }
+    }
+    fn children_mut<'a>(&'a mut self) -> Box<dyn Iterator<Item = &mut Expr> + '_> {
+        match self {
+            Expr::Const(_) => Box::new(std::iter::empty()),
+            Expr::SubstConstants(op) => op.children_mut(),
+            Expr::ByteArrayToLong(op) => op.children_mut(),
+            Expr::ByteArrayToBigInt(op) => op.children_mut(),
+            Expr::LongToByteArray(op) => op.children_mut(),
+            Expr::CalcBlake2b256(op) => op.children_mut(),
+            Expr::CalcSha256(op) => op.children_mut(),
+            Expr::Fold(op) => op.children_mut(),
+            Expr::ExtractRegisterAs(op) => op.children_mut(),
+            Expr::GlobalVars(op) => op.children_mut(),
+            Expr::MethodCall(op) => op.children_mut(),
+            Expr::PropertyCall(op) => op.children_mut(),
+            Expr::BinOp(op) => op.children_mut(),
+            Expr::Global => Box::new(std::iter::empty()),
+            Expr::Context => Box::new(std::iter::empty()),
+            Expr::OptionGet(v) => v.children_mut(),
+            Expr::Apply(op) => op.children_mut(),
+            Expr::FuncValue(op) => op.children_mut(),
+            Expr::ValUse(op) => op.children_mut(),
+            Expr::BlockValue(op) => op.children_mut(),
+            Expr::SelectField(op) => op.children_mut(),
+            Expr::ExtractAmount(op) => op.children_mut(),
+            Expr::ConstPlaceholder(_) => Box::new(std::iter::empty()),
+            Expr::Collection(op) => op.children_mut(),
+            Expr::ValDef(op) => op.children_mut(),
+            Expr::And(op) => op.children_mut(),
+            Expr::Or(op) => op.children_mut(),
+            Expr::Xor(op) => op.children_mut(),
+            Expr::Atleast(op) => op.children_mut(),
+            Expr::LogicalNot(op) => op.children_mut(),
+            Expr::Map(op) => op.children_mut(),
+            Expr::Filter(op) => op.children_mut(),
+            Expr::BoolToSigmaProp(op) => op.children_mut(),
+            Expr::Upcast(op) => op.children_mut(),
+            Expr::Downcast(op) => op.children_mut(),
+            Expr::If(op) => op.children_mut(),
+            Expr::Append(op) => op.children_mut(),
+            Expr::ByIndex(op) => op.children_mut(),
+            Expr::ExtractScriptBytes(op) => op.children_mut(),
+            Expr::SizeOf(op) => op.children_mut(),
+            Expr::Slice(op) => op.children_mut(),
+            Expr::CreateProveDlog(op) => op.children_mut(),
+            Expr::CreateProveDhTuple(op) => op.children_mut(),
+            Expr::ExtractCreationInfo(op) => op.children_mut(),
+            Expr::Exists(op) => op.children_mut(),
+            Expr::ExtractId(op) => op.children_mut(),
+            Expr::SigmaPropBytes(op) => op.children_mut(),
+            Expr::OptionIsDefined(op) => op.children_mut(),
+            Expr::OptionGetOrElse(op) => op.children_mut(),
+            Expr::Negation(op) => op.children_mut(),
+            Expr::BitInversion(op) => op.children_mut(),
+            Expr::ForAll(op) => op.children_mut(),
+            Expr::Tuple(op) => op.children_mut(),
+            Expr::DecodePoint(op) => op.children_mut(),
+            Expr::SigmaAnd(op) => op.children_mut(),
+            Expr::SigmaOr(op) => op.children_mut(),
+            Expr::DeserializeRegister(op) => op.children_mut(),
+            Expr::DeserializeContext(op) => op.children_mut(),
+            Expr::GetVar(op) => op.children_mut(),
+            Expr::MultiplyGroup(op) => op.children_mut(),
+            Expr::Exponentiate(op) => op.children_mut(),
+            Expr::XorOf(op) => op.children_mut(),
+            Expr::ExtractBytes(op) => op.children_mut(),
+            Expr::ExtractBytesWithNoRef(op) => op.children_mut(),
+            Expr::TreeLookup(op) => op.children_mut(),
+            Expr::CreateAvlTree(op) => op.children_mut(),
+        }
+    }
+}
+
 impl<T: Into<Literal> + LiftIntoSType> From<T> for Expr {
     fn from(t: T) -> Self {
         Expr::Const(Constant {
@@ -371,6 +657,25 @@ impl From<BoundedVecOutOfBounds> for InvalidArgumentError {
     }
 }
 
+#[derive(Error, Debug, Clone, PartialEq, Eq)]
+#[allow(missing_docs)]
+pub enum SubstDeserializeError {
+    #[error("TryExtractFromError: {0}")]
+    TryExtractFromError(#[from] TryExtractFromError),
+    #[error("Could not find context extension variable {0}")]
+    ExtensionKeyNotFound(u8),
+    #[error("executeFromReg: Register out of bounds {0}")]
+    InvalidRegister(#[from] RegisterIdOutOfBounds),
+    #[error("Register {0} does not exist")]
+    RegisterNotFound(RegisterId),
+    #[error("RegisterValueError: {0}")]
+    RegisterValueError(#[from] RegisterValueError),
+    #[error("Error while parsing Expr from bytes: {0}")]
+    ExprParsingError(#[from] SigmaParsingError),
+    #[error("Expected tpe {expected}, found {actual}")]
+    ExprTpeError { expected: SType, actual: SType },
+}
+
 impl<T: TryFrom<Expr>> TryExtractFrom<Expr> for T {
     fn try_extract_from(v: Expr) -> Result<Self, TryExtractFromError> {
         let res: Result<Self, TryExtractFromError> = v.clone().try_into().map_err(|_| {
diff --git a/ergotree-ir/src/mir/extract_amount.rs b/ergotree-ir/src/mir/extract_amount.rs
index 9b8166733..206d77fb4 100644
--- a/ergotree-ir/src/mir/extract_amount.rs
+++ b/ergotree-ir/src/mir/extract_amount.rs
@@ -29,6 +29,9 @@ impl OneArgOp for ExtractAmount {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for ExtractAmount {
diff --git a/ergotree-ir/src/mir/extract_bytes.rs b/ergotree-ir/src/mir/extract_bytes.rs
index a15431bec..c866be5e9 100644
--- a/ergotree-ir/src/mir/extract_bytes.rs
+++ b/ergotree-ir/src/mir/extract_bytes.rs
@@ -29,6 +29,9 @@ impl OneArgOp for ExtractBytes {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for ExtractBytes {
diff --git a/ergotree-ir/src/mir/extract_bytes_with_no_ref.rs b/ergotree-ir/src/mir/extract_bytes_with_no_ref.rs
index 18aa8793b..2771e12b4 100644
--- a/ergotree-ir/src/mir/extract_bytes_with_no_ref.rs
+++ b/ergotree-ir/src/mir/extract_bytes_with_no_ref.rs
@@ -29,6 +29,9 @@ impl OneArgOp for ExtractBytesWithNoRef {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for ExtractBytesWithNoRef {
diff --git a/ergotree-ir/src/mir/extract_creation_info.rs b/ergotree-ir/src/mir/extract_creation_info.rs
index 099e9eb13..eb34b74e3 100644
--- a/ergotree-ir/src/mir/extract_creation_info.rs
+++ b/ergotree-ir/src/mir/extract_creation_info.rs
@@ -31,6 +31,9 @@ impl OneArgOp for ExtractCreationInfo {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for ExtractCreationInfo {
diff --git a/ergotree-ir/src/mir/extract_id.rs b/ergotree-ir/src/mir/extract_id.rs
index 6900446dd..e33a3ce72 100644
--- a/ergotree-ir/src/mir/extract_id.rs
+++ b/ergotree-ir/src/mir/extract_id.rs
@@ -29,6 +29,9 @@ impl OneArgOp for ExtractId {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for ExtractId {
diff --git a/ergotree-ir/src/mir/extract_reg_as.rs b/ergotree-ir/src/mir/extract_reg_as.rs
index b00ad3904..a1ce698f8 100644
--- a/ergotree-ir/src/mir/extract_reg_as.rs
+++ b/ergotree-ir/src/mir/extract_reg_as.rs
@@ -6,6 +6,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 use super::expr::Expr;
@@ -76,6 +77,8 @@ impl SigmaSerializable for ExtractRegisterAs {
     }
 }
 
+impl_traversable_expr!(ExtractRegisterAs, boxed input);
+
 #[cfg(test)]
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used)]
diff --git a/ergotree-ir/src/mir/extract_script_bytes.rs b/ergotree-ir/src/mir/extract_script_bytes.rs
index 5912c2def..5f14803b6 100644
--- a/ergotree-ir/src/mir/extract_script_bytes.rs
+++ b/ergotree-ir/src/mir/extract_script_bytes.rs
@@ -29,6 +29,9 @@ impl OneArgOp for ExtractScriptBytes {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for ExtractScriptBytes {
diff --git a/ergotree-ir/src/mir/func_value.rs b/ergotree-ir/src/mir/func_value.rs
index 83ab57552..6d4fa5ca8 100644
--- a/ergotree-ir/src/mir/func_value.rs
+++ b/ergotree-ir/src/mir/func_value.rs
@@ -7,6 +7,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::sfunc::SFunc;
 use crate::types::stype::SType;
 
@@ -80,6 +81,11 @@ impl FuncValue {
         &self.body
     }
 
+    /// Function body
+    pub fn body_mut(&mut self) -> &mut Expr {
+        &mut self.body
+    }
+
     /// Type
     pub fn tpe(&self) -> SType {
         self.tpe.clone()
@@ -105,6 +111,8 @@ impl SigmaSerializable for FuncValue {
     }
 }
 
+impl_traversable_expr!(FuncValue, boxed body);
+
 #[cfg(test)]
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::panic)]
diff --git a/ergotree-ir/src/mir/get_var.rs b/ergotree-ir/src/mir/get_var.rs
index b5eb1097d..cd480b2c1 100644
--- a/ergotree-ir/src/mir/get_var.rs
+++ b/ergotree-ir/src/mir/get_var.rs
@@ -6,8 +6,11 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
+use super::expr::Expr;
+
 /// Extract value of variable from context by its ID.
 #[derive(PartialEq, Eq, Debug, Clone)]
 pub struct GetVar {
@@ -41,6 +44,8 @@ impl SigmaSerializable for GetVar {
     }
 }
 
+impl_traversable_expr!(GetVar);
+
 /// Arbitrary impl
 #[cfg(feature = "arbitrary")]
 mod arbitrary {
diff --git a/ergotree-ir/src/mir/global_vars.rs b/ergotree-ir/src/mir/global_vars.rs
index b8ca7ab4a..09165e735 100644
--- a/ergotree-ir/src/mir/global_vars.rs
+++ b/ergotree-ir/src/mir/global_vars.rs
@@ -5,8 +5,11 @@ use std::sync::Arc;
 
 use crate::has_opcode::HasOpCode;
 use crate::serialization::op_code::OpCode;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
+use super::expr::Expr;
+
 #[derive(PartialEq, Eq, Debug, Clone)]
 /// Predefined global variables
 pub enum GlobalVars {
@@ -65,6 +68,8 @@ impl Display for GlobalVars {
     }
 }
 
+impl_traversable_expr!(GlobalVars);
+
 #[cfg(test)]
 #[cfg(feature = "arbitrary")]
 mod tests {
diff --git a/ergotree-ir/src/mir/if_op.rs b/ergotree-ir/src/mir/if_op.rs
index 8c10bbf27..1298f3e30 100644
--- a/ergotree-ir/src/mir/if_op.rs
+++ b/ergotree-ir/src/mir/if_op.rs
@@ -6,6 +6,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 /// If (lazy evaluation)
@@ -49,6 +50,8 @@ impl SigmaSerializable for If {
     }
 }
 
+impl_traversable_expr!(If, boxed condition, boxed true_branch, boxed false_branch);
+
 #[cfg(feature = "arbitrary")]
 /// Arbitrary impl
 mod arbitrary {
diff --git a/ergotree-ir/src/mir/logical_not.rs b/ergotree-ir/src/mir/logical_not.rs
index 7418d8d95..cdb0cc664 100644
--- a/ergotree-ir/src/mir/logical_not.rs
+++ b/ergotree-ir/src/mir/logical_not.rs
@@ -28,6 +28,9 @@ impl OneArgOp for LogicalNot {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for LogicalNot {
diff --git a/ergotree-ir/src/mir/long_to_byte_array.rs b/ergotree-ir/src/mir/long_to_byte_array.rs
index 2c858d90c..bd01a0b4b 100644
--- a/ergotree-ir/src/mir/long_to_byte_array.rs
+++ b/ergotree-ir/src/mir/long_to_byte_array.rs
@@ -30,6 +30,9 @@ impl OneArgOp for LongToByteArray {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for LongToByteArray {
diff --git a/ergotree-ir/src/mir/method_call.rs b/ergotree-ir/src/mir/method_call.rs
index 7d644ae8f..6d6e8ccac 100644
--- a/ergotree-ir/src/mir/method_call.rs
+++ b/ergotree-ir/src/mir/method_call.rs
@@ -1,6 +1,7 @@
 use std::collections::HashMap;
 
 use crate::serialization::op_code::OpCode;
+use crate::traversable::impl_traversable_expr;
 use crate::types::smethod::SMethod;
 use crate::types::stype::SType;
 use crate::types::stype_param::STypeVar;
@@ -104,3 +105,5 @@ impl MethodCall {
 impl HasStaticOpCode for MethodCall {
     const OP_CODE: OpCode = OpCode::METHOD_CALL;
 }
+
+impl_traversable_expr!(MethodCall, boxed obj, arr args);
diff --git a/ergotree-ir/src/mir/multiply_group.rs b/ergotree-ir/src/mir/multiply_group.rs
index c37e1443c..97e4c4ec7 100644
--- a/ergotree-ir/src/mir/multiply_group.rs
+++ b/ergotree-ir/src/mir/multiply_group.rs
@@ -4,6 +4,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 use super::expr::Expr;
@@ -57,6 +58,8 @@ impl SigmaSerializable for MultiplyGroup {
     }
 }
 
+impl_traversable_expr!(MultiplyGroup, boxed left, boxed right);
+
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used)]
 mod arbitrary {
diff --git a/ergotree-ir/src/mir/negation.rs b/ergotree-ir/src/mir/negation.rs
index c64f971b1..16b3d42eb 100644
--- a/ergotree-ir/src/mir/negation.rs
+++ b/ergotree-ir/src/mir/negation.rs
@@ -28,6 +28,9 @@ impl OneArgOp for Negation {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for Negation {
diff --git a/ergotree-ir/src/mir/option_get.rs b/ergotree-ir/src/mir/option_get.rs
index 594e641ab..571c50aa2 100644
--- a/ergotree-ir/src/mir/option_get.rs
+++ b/ergotree-ir/src/mir/option_get.rs
@@ -32,6 +32,9 @@ impl OneArgOp for OptionGet {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for OptionGet {
diff --git a/ergotree-ir/src/mir/option_get_or_else.rs b/ergotree-ir/src/mir/option_get_or_else.rs
index 0be7635e1..299752f82 100644
--- a/ergotree-ir/src/mir/option_get_or_else.rs
+++ b/ergotree-ir/src/mir/option_get_or_else.rs
@@ -7,6 +7,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 use std::sync::Arc;
 
@@ -63,6 +64,8 @@ impl SigmaSerializable for OptionGetOrElse {
     }
 }
 
+impl_traversable_expr!(OptionGetOrElse, boxed input, boxed default);
+
 #[cfg(test)]
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used)]
diff --git a/ergotree-ir/src/mir/option_is_defined.rs b/ergotree-ir/src/mir/option_is_defined.rs
index 98e8df6ef..6adb2a28a 100644
--- a/ergotree-ir/src/mir/option_is_defined.rs
+++ b/ergotree-ir/src/mir/option_is_defined.rs
@@ -28,6 +28,9 @@ impl OneArgOp for OptionIsDefined {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for OptionIsDefined {
diff --git a/ergotree-ir/src/mir/or.rs b/ergotree-ir/src/mir/or.rs
index 6234b8db9..52526961e 100644
--- a/ergotree-ir/src/mir/or.rs
+++ b/ergotree-ir/src/mir/or.rs
@@ -1,4 +1,5 @@
 use super::expr::Expr;
+use super::unary_op::OneArgOp;
 use crate::has_opcode::HasStaticOpCode;
 use crate::serialization::op_code::OpCode;
 use crate::serialization::sigma_byte_reader::SigmaByteRead;
@@ -38,6 +39,16 @@ impl SigmaSerializable for Or {
     }
 }
 
+impl OneArgOp for Or {
+    fn input(&self) -> &Expr {
+        &self.input
+    }
+
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
+}
+
 #[cfg(feature = "arbitrary")]
 /// Arbitrary impl
 mod arbitrary {
diff --git a/ergotree-ir/src/mir/property_call.rs b/ergotree-ir/src/mir/property_call.rs
index 78e9ce49e..0f0f078ff 100644
--- a/ergotree-ir/src/mir/property_call.rs
+++ b/ergotree-ir/src/mir/property_call.rs
@@ -1,4 +1,5 @@
 use crate::serialization::op_code::OpCode;
+use crate::traversable::impl_traversable_expr;
 use crate::types::smethod::SMethod;
 use crate::types::stype::SType;
 
@@ -52,3 +53,5 @@ impl PropertyCall {
 impl HasStaticOpCode for PropertyCall {
     const OP_CODE: OpCode = OpCode::PROPERTY_CALL;
 }
+
+impl_traversable_expr!(PropertyCall, boxed obj);
diff --git a/ergotree-ir/src/mir/select_field.rs b/ergotree-ir/src/mir/select_field.rs
index 02f5bd306..d033b40c0 100644
--- a/ergotree-ir/src/mir/select_field.rs
+++ b/ergotree-ir/src/mir/select_field.rs
@@ -6,6 +6,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stuple::STuple;
 use crate::types::stype::SType;
 
@@ -119,6 +120,8 @@ impl SigmaSerializable for SelectField {
     }
 }
 
+impl_traversable_expr!(SelectField, boxed input);
+
 #[cfg(test)]
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used)]
diff --git a/ergotree-ir/src/mir/sigma_and.rs b/ergotree-ir/src/mir/sigma_and.rs
index 14dacc77c..6659aa762 100644
--- a/ergotree-ir/src/mir/sigma_and.rs
+++ b/ergotree-ir/src/mir/sigma_and.rs
@@ -9,6 +9,7 @@ use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
 use crate::sigma_protocol::sigma_boolean::SigmaConjectureItems;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 use super::expr::Expr;
@@ -65,6 +66,8 @@ impl SigmaSerializable for SigmaAnd {
     }
 }
 
+impl_traversable_expr!(SigmaAnd, arr items);
+
 /// Arbitrary impl
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used)]
diff --git a/ergotree-ir/src/mir/sigma_or.rs b/ergotree-ir/src/mir/sigma_or.rs
index 7fb7d8cf9..af24d4b97 100644
--- a/ergotree-ir/src/mir/sigma_or.rs
+++ b/ergotree-ir/src/mir/sigma_or.rs
@@ -9,6 +9,7 @@ use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
 use crate::sigma_protocol::sigma_boolean::SigmaConjectureItems;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 use super::expr::Expr;
@@ -65,6 +66,8 @@ impl SigmaSerializable for SigmaOr {
     }
 }
 
+impl_traversable_expr!(SigmaOr, arr items);
+
 /// Arbitrary impl
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used)]
diff --git a/ergotree-ir/src/mir/sigma_prop_bytes.rs b/ergotree-ir/src/mir/sigma_prop_bytes.rs
index f63b56ab8..9db3ae51a 100644
--- a/ergotree-ir/src/mir/sigma_prop_bytes.rs
+++ b/ergotree-ir/src/mir/sigma_prop_bytes.rs
@@ -29,6 +29,9 @@ impl OneArgOp for SigmaPropBytes {
     fn input(&self) -> &Expr {
         &self.input
     }
+    fn input_mut(&mut self) -> &mut Expr {
+        &mut self.input
+    }
 }
 
 impl OneArgOpTryBuild for SigmaPropBytes {
diff --git a/ergotree-ir/src/mir/subst_const.rs b/ergotree-ir/src/mir/subst_const.rs
index 142fc25d3..afb8a23f8 100644
--- a/ergotree-ir/src/mir/subst_const.rs
+++ b/ergotree-ir/src/mir/subst_const.rs
@@ -8,6 +8,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 #[derive(PartialEq, Eq, Debug, Clone)]
@@ -71,6 +72,8 @@ impl SigmaSerializable for SubstConstants {
     }
 }
 
+impl_traversable_expr!(SubstConstants, boxed script_bytes, boxed positions, boxed new_values);
+
 #[cfg(test)]
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::panic)]
diff --git a/ergotree-ir/src/mir/tree_lookup.rs b/ergotree-ir/src/mir/tree_lookup.rs
index 95e85eb46..918131f27 100644
--- a/ergotree-ir/src/mir/tree_lookup.rs
+++ b/ergotree-ir/src/mir/tree_lookup.rs
@@ -1,5 +1,6 @@
 //! Lookup in AVL tree
 use crate::serialization::op_code::OpCode;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 use super::expr::Expr;
@@ -58,6 +59,8 @@ impl SigmaSerializable for TreeLookup {
     }
 }
 
+impl_traversable_expr!(TreeLookup, boxed tree, boxed key, boxed proof);
+
 #[allow(clippy::unwrap_used)]
 #[cfg(feature = "arbitrary")]
 /// Arbitrary impl
diff --git a/ergotree-ir/src/mir/tuple.rs b/ergotree-ir/src/mir/tuple.rs
index 5eeb627d0..90b8cfcd1 100644
--- a/ergotree-ir/src/mir/tuple.rs
+++ b/ergotree-ir/src/mir/tuple.rs
@@ -6,6 +6,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stuple::STuple;
 use crate::types::stuple::TupleItems;
 use crate::types::stype::SType;
@@ -59,6 +60,8 @@ impl SigmaSerializable for Tuple {
     }
 }
 
+impl_traversable_expr!(Tuple, arr items);
+
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used)]
 /// Arbitrary impl
diff --git a/ergotree-ir/src/mir/unary_op.rs b/ergotree-ir/src/mir/unary_op.rs
index 6cbb6823a..11bd51e8f 100644
--- a/ergotree-ir/src/mir/unary_op.rs
+++ b/ergotree-ir/src/mir/unary_op.rs
@@ -13,6 +13,8 @@ use super::expr::InvalidArgumentError;
 pub trait OneArgOp {
     /// Input value(expr) of the IR node
     fn input(&self) -> &Expr;
+    /// Mutable reference to input value(expr) of the IR node
+    fn input_mut(&mut self) -> &mut Expr;
 }
 
 /// Constructor for unary IR nodes that check the validity of the argument
diff --git a/ergotree-ir/src/mir/upcast.rs b/ergotree-ir/src/mir/upcast.rs
index 364f143c1..79bd82bcf 100644
--- a/ergotree-ir/src/mir/upcast.rs
+++ b/ergotree-ir/src/mir/upcast.rs
@@ -8,6 +8,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 use crate::has_opcode::HasStaticOpCode;
@@ -67,6 +68,8 @@ impl SigmaSerializable for Upcast {
     }
 }
 
+impl_traversable_expr!(Upcast, boxed input);
+
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::unwrap_used)]
 /// Arbitrary impl
diff --git a/ergotree-ir/src/mir/val_def.rs b/ergotree-ir/src/mir/val_def.rs
index 5881f8e08..d241b024a 100644
--- a/ergotree-ir/src/mir/val_def.rs
+++ b/ergotree-ir/src/mir/val_def.rs
@@ -4,6 +4,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 use super::expr::Expr;
@@ -73,6 +74,8 @@ impl SigmaSerializable for ValDef {
     }
 }
 
+impl_traversable_expr!(ValDef, boxed rhs);
+
 #[cfg(test)]
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::panic)]
diff --git a/ergotree-ir/src/mir/val_use.rs b/ergotree-ir/src/mir/val_use.rs
index 1a4ae5607..684d7e03a 100644
--- a/ergotree-ir/src/mir/val_use.rs
+++ b/ergotree-ir/src/mir/val_use.rs
@@ -1,3 +1,4 @@
+use super::expr::Expr;
 use super::val_def::ValId;
 use crate::has_opcode::HasStaticOpCode;
 use crate::serialization::op_code::OpCode;
@@ -6,6 +7,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 /** Special node which represents a reference to ValDef in was introduced as result of CSE. */
@@ -38,6 +40,8 @@ impl SigmaSerializable for ValUse {
     }
 }
 
+impl_traversable_expr!(ValUse);
+
 #[cfg(test)]
 #[cfg(feature = "arbitrary")]
 #[allow(clippy::panic)]
diff --git a/ergotree-ir/src/mir/xor.rs b/ergotree-ir/src/mir/xor.rs
index 3e257256c..8258d7919 100644
--- a/ergotree-ir/src/mir/xor.rs
+++ b/ergotree-ir/src/mir/xor.rs
@@ -7,6 +7,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 use std::sync::Arc;
 
@@ -66,6 +67,8 @@ impl SigmaSerializable for Xor {
     }
 }
 
+impl_traversable_expr!(Xor, boxed left, boxed right);
+
 #[cfg(feature = "arbitrary")]
 /// Arbitrary impl
 #[allow(clippy::unwrap_used)]
diff --git a/ergotree-ir/src/mir/xor_of.rs b/ergotree-ir/src/mir/xor_of.rs
index 601437cf0..6665552e5 100644
--- a/ergotree-ir/src/mir/xor_of.rs
+++ b/ergotree-ir/src/mir/xor_of.rs
@@ -6,6 +6,7 @@ use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
+use crate::traversable::impl_traversable_expr;
 use crate::types::stype::SType;
 
 use super::expr::Expr;
@@ -41,6 +42,8 @@ impl SigmaSerializable for XorOf {
     }
 }
 
+impl_traversable_expr!(XorOf, boxed input);
+
 /// Arbitrary impl
 #[cfg(feature = "arbitrary")]
 mod arbitrary {
diff --git a/ergotree-ir/src/serialization/sigma_byte_reader.rs b/ergotree-ir/src/serialization/sigma_byte_reader.rs
index e31e96402..cfa63d03b 100644
--- a/ergotree-ir/src/serialization/sigma_byte_reader.rs
+++ b/ergotree-ir/src/serialization/sigma_byte_reader.rs
@@ -12,6 +12,7 @@ pub struct SigmaByteReader<R> {
     constant_store: ConstantStore,
     substitute_placeholders: bool,
     val_def_type_store: ValDefTypeStore,
+    was_deserialize: bool,
 }
 
 impl<R: Read> SigmaByteReader<R> {
@@ -22,6 +23,7 @@ impl<R: Read> SigmaByteReader<R> {
             constant_store,
             substitute_placeholders: false,
             val_def_type_store: ValDefTypeStore::new(),
+            was_deserialize: false,
         }
     }
 
@@ -36,6 +38,7 @@ impl<R: Read> SigmaByteReader<R> {
             constant_store,
             substitute_placeholders: true,
             val_def_type_store: ValDefTypeStore::new(),
+            was_deserialize: false,
         }
     }
 }
@@ -47,6 +50,7 @@ pub fn from_bytes<T: AsRef<[u8]>>(bytes: T) -> SigmaByteReader<Cursor<T>> {
         constant_store: ConstantStore::empty(),
         substitute_placeholders: false,
         val_def_type_store: ValDefTypeStore::new(),
+        was_deserialize: false,
     }
 }
 
@@ -63,6 +67,12 @@ pub trait SigmaByteRead: ReadSigmaVlqExt {
 
     /// ValDef types store (resolves tpe on ValUse parsing)
     fn val_def_type_store(&mut self) -> &mut ValDefTypeStore;
+
+    /// Returns if value that was deserialized has deserialize nodes, such as DeserializeContext and DeserializeRegister
+    fn was_deserialize(&self) -> bool;
+
+    /// Set that deserialization node was read
+    fn set_deserialize(&mut self, has_deserialize: bool);
 }
 
 impl<R: Read> Read for SigmaByteReader<R> {
@@ -101,4 +111,12 @@ impl<R: ReadSigmaVlqExt> SigmaByteRead for SigmaByteReader<R> {
     fn val_def_type_store(&mut self) -> &mut ValDefTypeStore {
         &mut self.val_def_type_store
     }
+
+    fn was_deserialize(&self) -> bool {
+        self.was_deserialize
+    }
+
+    fn set_deserialize(&mut self, has_deserialize: bool) {
+        self.was_deserialize = has_deserialize
+    }
 }
diff --git a/ergotree-ir/src/source_span.rs b/ergotree-ir/src/source_span.rs
index a48ae4a54..b744d8101 100644
--- a/ergotree-ir/src/source_span.rs
+++ b/ergotree-ir/src/source_span.rs
@@ -28,6 +28,7 @@ use crate::mir::select_field::SelectField;
 use crate::mir::subst_const::SubstConstants;
 use crate::mir::tree_lookup::TreeLookup;
 use crate::mir::val_def::ValDef;
+use crate::traversable::Traversable;
 
 /// Source position for the Expr
 #[derive(PartialEq, Eq, Debug, Clone, Copy)]
@@ -79,6 +80,16 @@ impl<T> Spanned<T> {
     }
 }
 
+impl<T: Traversable> Traversable for Spanned<T> {
+    type Item = T::Item;
+    fn children<'a>(&'a self) -> Box<dyn Iterator<Item = &Self::Item> + 'a> {
+        self.expr.children()
+    }
+    fn children_mut<'a>(&'a mut self) -> Box<dyn Iterator<Item = &mut T::Item> + 'a> {
+        self.expr.children_mut()
+    }
+}
+
 macro_rules! into_expr {
     ($variant: ident) => {
         impl From<$variant> for Expr {
diff --git a/ergotree-ir/src/traversable.rs b/ergotree-ir/src/traversable.rs
new file mode 100644
index 000000000..88d7006b0
--- /dev/null
+++ b/ergotree-ir/src/traversable.rs
@@ -0,0 +1,125 @@
+//! Traversable trait
+
+use crate::mir::{expr::Expr, unary_op::OneArgOp};
+
+/// Trait for types that have child nodes.
+/// In ergotree-ir this is used for traversing trees of [`Expr`] and doing rewriting operations such as replacing [ConstantPlaceholder](crate::mir::constant::ConstantPlaceholder)s with [`Constant`](crate::mir::constant::Constant)s
+pub trait Traversable {
+    /// Type that implementor has edges to. Since [Self::Item] also implements Traversable this can be used to traverse the entire tree
+    type Item: Traversable;
+    /// Return an iterator for child nodes
+    fn children<'a>(&'a self) -> Box<dyn Iterator<Item = &Self::Item> + 'a>;
+    /// Return a iterator for mutable access to all child nodes
+    fn children_mut<'a>(&'a mut self) -> Box<dyn Iterator<Item = &mut Self::Item> + 'a>;
+}
+
+impl<T: OneArgOp> Traversable for T {
+    type Item = Expr;
+
+    fn children<'a>(&'a self) -> Box<dyn Iterator<Item = &Self::Item> + 'a> {
+        Box::new(std::iter::once(self.input()))
+    }
+    fn children_mut<'a>(&'a mut self) -> Box<dyn Iterator<Item = &mut Self::Item> + 'a> {
+        Box::new(std::iter::once(self.input_mut()))
+    }
+}
+
+macro_rules! iter_from {
+    ($self:ident, opt $x:tt, $($y:tt)*) => {
+        $self.$x.as_mut().into_iter().chain(crate::traversable::iter_from!($self, $($y)*))
+    };
+    ($self:ident, arr $x:tt, $($y:tt)*) => {
+        $self.$x.iter().chain(crate::traversable::iter_from!($self, $($y)*))
+    };
+    ($self:ident, boxed $x:tt, $($y:tt)*) => {
+        std::iter::once(&*$self.$x).chain(crate::traversable::iter_from!($self, $($y)*))
+    };
+    ($self:ident, opt $x:tt) => {
+        $self.$x.as_deref().into_iter()
+    };
+    ($self:ident, arr $x:tt) => {
+        $self.$x.iter()
+    };
+    ($self:ident, boxed $x:tt) => {
+        std::iter::once(&*$self.$x)
+    };
+    ($self:ident) => {
+        std::iter::empty()
+    }
+}
+
+macro_rules! iter_from_mut {
+    ($self:ident, opt $x:tt, $($y:tt)*) => {
+        $self.$x.as_mut().into_iter().chain(crate::traversable::iter_from_mut!($self, $($y)*))
+    };
+    ($self:ident, arr $x:tt, $($y:tt)*) => {
+        $self.$x.iter_mut().chain(crate::traversable::iter_from_mut!($self, $($y)*))
+    };
+    ($self:ident, boxed $x:tt, $($y:tt)*) => {
+        std::iter::once(&mut *$self.$x).chain(crate::traversable::iter_from_mut!($self, $($y)*))
+    };
+    ($self:ident, opt $x:tt) => {
+        $self.$x.as_deref_mut().into_iter()
+    };
+    ($self:ident, arr $x:tt) => {
+        $self.$x.iter_mut()
+    };
+    ($self:ident, boxed $x:tt) => {
+        std::iter::once(&mut *$self.$x)
+    };
+    ($self:ident) => {
+        std::iter::empty()
+    }
+}
+
+// Implement Traversable<Item = Expr> for an Evaluable Node.
+macro_rules! impl_traversable_expr {
+    ($op:ident $(, $($args:tt)+ )? ) => {
+        impl crate::traversable::Traversable for $op {
+            type Item = Expr;
+            fn children(&self) -> Box<dyn Iterator<Item = &Self::Item> + '_> {
+                Box::new(crate::traversable::iter_from!(self $(, $($args)*)?))
+            }
+            fn children_mut(&mut self) -> Box<dyn Iterator<Item = &mut Self::Item> + '_> {
+                Box::new(crate::traversable::iter_from_mut!(self $(, $($args)*)?))
+            }
+        }
+    };
+}
+
+pub(crate) use impl_traversable_expr;
+pub(crate) use iter_from;
+pub(crate) use iter_from_mut;
+
+#[cfg(test)]
+mod test {
+    use crate::mir::{constant::Constant, expr::Expr};
+
+    use super::Traversable;
+
+    struct TestStruct {
+        a: Box<Expr>,
+        b: Box<Expr>,
+        c: Vec<Expr>,
+        d: Option<Box<Expr>>,
+    }
+    impl_traversable_expr!(TestStruct, boxed a, boxed b, arr c, opt d);
+    struct EmptyStruct;
+
+    impl_traversable_expr!(EmptyStruct);
+    #[test]
+    fn test_impl_traversable() {
+        let mut test_struct = TestStruct {
+            a: Box::new(Expr::from(Constant::from(1i8))),
+            b: Box::new(Expr::from(Constant::from(2i8))),
+            c: vec![Expr::from(Constant::from(3i8))],
+            d: Some(Box::new(Expr::from(Constant::from(4i8)))),
+        };
+        test_struct
+            .children_mut()
+            .zip(1..=4i8)
+            .for_each(|(c, i)| assert_eq!(&*c, &Constant::from(i).into()));
+        let mut empty = EmptyStruct;
+        assert_eq!(empty.children_mut().count(), 0);
+    }
+}


Test patch:
diff --git a/bindings/ergo-lib-wasm/tests/transaction.rs b/bindings/ergo-lib-wasm/tests/transaction.rs
index ba49cc7a3..2ec244462 100644
--- a/bindings/ergo-lib-wasm/tests/transaction.rs
+++ b/bindings/ergo-lib-wasm/tests/transaction.rs
@@ -7,6 +7,7 @@ use wasm_bindgen_test::*;
 
 wasm_bindgen_test_configure!(run_in_browser);
 
+#[allow(dead_code)]
 #[wasm_bindgen_test]
 fn test_random() {
     let sk1 = SecretKey::random_dlog();
diff --git a/ergotree-interpreter/tests/signing_spec_tests.rs b/ergotree-interpreter/tests/signing_spec_tests.rs
index 86f9af337..04b69bceb 100644
--- a/ergotree-interpreter/tests/signing_spec_tests.rs
+++ b/ergotree-interpreter/tests/signing_spec_tests.rs
@@ -1,6 +1,6 @@
-use ergotree_interpreter::eval::context::Context;
 use ergotree_interpreter::sigma_protocol::private_input::DlogProverInput;
 use ergotree_interpreter::sigma_protocol::verifier::{TestVerifier, Verifier};
+use ergotree_ir::chain::context::Context;
 use ergotree_ir::ergo_tree::ErgoTree;
 use ergotree_ir::mir::atleast::Atleast;
 use ergotree_ir::mir::constant::{Constant, Literal};