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

Issue:
Implement EQ
Test it with values of types like `Coll[(Coll[(Option[Coll[(Int, Option[BigInt]]], AvlTree)], Coll[Byte])]`


Discussion / hints:

Fix patch:
diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml
index d4977da8d..b98fb2602 100644
--- a/.github/workflows/ci.yml
+++ b/.github/workflows/ci.yml
@@ -69,6 +69,8 @@ jobs:
 
     steps:
       - uses: actions/checkout@v2
+        with:
+          fetch-depth: 0
       - uses: actions-rs/toolchain@v1
         with:
           toolchain: stable
@@ -92,12 +94,17 @@ jobs:
         uses: actions-rs/tarpaulin@master
         with:
           args: '-v --out Lcov --exclude-files bindings/*'
-      - name: Push code coverage results to coveralls.io
+      - name: Upload coverage report to Codecov
         if: matrix.os == 'ubuntu-latest' && github.event_name == 'pull_request'
-        uses: coverallsapp/github-action@master
+        uses: codecov/codecov-action@v1
         with:
-          github-token: ${{ secrets.GITHUB_TOKEN }}
-          path-to-lcov: ./lcov.info
+          fail_ci_if_error: true
+      # - name: Push code coverage results to coveralls.io
+      #   if: matrix.os == 'ubuntu-latest' && github.event_name == 'pull_request'
+      #   uses: coverallsapp/github-action@master
+      #   with:
+      #     github-token: ${{ secrets.GITHUB_TOKEN }}
+      #     path-to-lcov: ./lcov.info
         
   doc-links:
     name: Intra-documentation links
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
index 9076cc87c..26701feb4 100644
--- a/CONTRIBUTING.md
+++ b/CONTRIBUTING.md
@@ -19,7 +19,7 @@ When we're ready to release, a project owner should do the following:
 - `cargo release minor --dry-run --no-dev-version -vv` if you intend to bump a minor version or change `minor` to
   `major` to bump a major version, `patch` to bump a patch/hotfix version (add
   `--exclude sigma-ser` if you want to skip `sigma-ser` release);
-- check the output and run it without `--dry-run` to actually execute it;
+- check the output and run it without `--dry-run` to actually execute it(make sure that you have api token from `crates.io`, otherwise run `cargo login` first);
 - Build and publish npm package (`cd bindings/ergo-lib-wasm && npm run publish-nodejs && npm run publish-browser`);
 - Merge release branch into develop
 - Merge release branch into master
diff --git a/README.md b/README.md
index 0573a864d..30d8ae908 100644
--- a/README.md
+++ b/README.md
@@ -1,4 +1,4 @@
-[![Coverage Status](https://coveralls.io/repos/github/ergoplatform/sigma-rust/badge.svg)](https://coveralls.io/github/ergoplatform/sigma-rust)
+[![codecov](https://codecov.io/gh/ergoplatform/sigma-rust/branch/develop/graph/badge.svg?token=W1ITCGM9ZP)](https://codecov.io/gh/ergoplatform/sigma-rust)
 
 Rust implementation of [ErgoScript](https://github.com/ScorexFoundation/sigmastate-interpreter) cryptocurrency scripting language. 
 
diff --git a/ergo-lib/CHANGELOG.md b/ergo-lib/CHANGELOG.md
index fb319bd9a..59f381656 100644
--- a/ergo-lib/CHANGELOG.md
+++ b/ergo-lib/CHANGELOG.md
@@ -6,6 +6,11 @@ and this project adheres to [Semantic Versioning](http://semver.org/).
 
 <!-- next-header -->
 ## [Unreleased] - ReleaseDate
+
+### Added 
+- `SType::STuple()` and `Value::Tup()` types to store tuples. Implemented serialization, conversion between Rust types and `Constant`(`Value`, `SType`) [#166](https://github.com/ergoplatform/sigma-rust/pull/166);
+- `EQ(==)`, `NEQ(!=)` implementation [#166](https://github.com/ergoplatform/sigma-rust/pull/166);
+
 ## [0.4.2] - 2020-12-21
 
 ### Added 
diff --git a/ergo-lib/Cargo.toml b/ergo-lib/Cargo.toml
index 9da08012a..b3cf04d9a 100644
--- a/ergo-lib/Cargo.toml
+++ b/ergo-lib/Cargo.toml
@@ -28,6 +28,7 @@ num-bigint = "0.3.0"
 rand = "0.7"
 lazy_static = "1.4"
 derive_more = "0.99"
+impl-trait-for-tuples = "0.2.0"
 
 [features]
 default = ["json"]
diff --git a/ergo-lib/README.md b/ergo-lib/README.md
index ff45bf3bb..c7405e507 100644
--- a/ergo-lib/README.md
+++ b/ergo-lib/README.md
@@ -13,6 +13,8 @@
 ## Interpreter (what's implemented):
 - global vars (`INPUTS`, `OUTPUTS`, `SELF`, `HEIGHT`);
 - `Context` properties (`dataInputs`);
+- Value types with serialization for most of them(types and values);
+- `EQ`(`==`), `NEQ`(`!=`);
 
 ## Usage 
 ## Crate features
diff --git a/ergo-lib/src/ast.rs b/ergo-lib/src/ast.rs
index 6551458ca..8950d3aff 100644
--- a/ergo-lib/src/ast.rs
+++ b/ergo-lib/src/ast.rs
@@ -1,11 +1,11 @@
 //! AST for ErgoTree
 
+pub(crate) mod bin_op;
 pub(crate) mod coll_fold;
 pub(crate) mod expr;
 pub(crate) mod extract_reg_as;
 pub(crate) mod global_vars;
 pub(crate) mod method_call;
-pub(crate) mod ops;
 pub(crate) mod option_get;
 pub(crate) mod predef_func;
 pub(crate) mod property_call;
diff --git a/ergo-lib/src/ast/bin_op.rs b/ergo-lib/src/ast/bin_op.rs
new file mode 100644
index 000000000..5bd30228d
--- /dev/null
+++ b/ergo-lib/src/ast/bin_op.rs
@@ -0,0 +1,184 @@
+//! Operators in ErgoTree
+
+use eval::costs::Costs;
+
+use crate::eval;
+use crate::eval::Env;
+use crate::eval::EvalContext;
+use crate::eval::EvalError;
+use crate::eval::Evaluable;
+use crate::serialization::op_code::OpCode;
+
+use super::expr::Expr;
+use super::value::Value;
+
+extern crate derive_more;
+use derive_more::From;
+
+#[derive(PartialEq, Eq, Debug, Clone, Copy)]
+/// Operations for numerical types
+pub enum NumOp {
+    /// Addition
+    Add,
+}
+
+impl From<NumOp> for OpCode {
+    fn from(_: NumOp) -> Self {
+        todo!()
+    }
+}
+
+#[derive(PartialEq, Eq, Debug, Clone, Copy)]
+pub enum LogicOp {
+    Eq,
+    NEq,
+    GE,
+    GT,
+    LE,
+    LT,
+}
+
+impl From<LogicOp> for OpCode {
+    fn from(op: LogicOp) -> Self {
+        match op {
+            LogicOp::Eq => OpCode::EQ,
+            LogicOp::NEq => OpCode::NEQ,
+            _ => todo!(),
+        }
+    }
+}
+
+#[derive(PartialEq, Eq, Debug, Clone, Copy, From)]
+/// Binary operations
+pub enum BinOpKind {
+    /// Binary operations for numerical types
+    Num(NumOp),
+    Logic(LogicOp),
+}
+
+impl From<BinOpKind> for OpCode {
+    fn from(op: BinOpKind) -> Self {
+        match op {
+            BinOpKind::Num(o) => o.into(),
+            BinOpKind::Logic(o) => o.into(),
+        }
+    }
+}
+
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct BinOp {
+    pub kind: BinOpKind,
+    pub left: Expr,
+    pub right: Expr,
+}
+
+impl BinOp {
+    pub fn op_code(&self) -> OpCode {
+        self.kind.into()
+    }
+}
+
+impl Evaluable for BinOp {
+    fn eval(&self, env: &Env, ctx: &mut EvalContext) -> Result<Value, EvalError> {
+        let lv = self.left.eval(env, ctx)?;
+        let rv = self.right.eval(env, ctx)?;
+        ctx.cost_accum.add(Costs::DEFAULT.eq_const_size)?;
+        match self.kind {
+            BinOpKind::Num(_) => todo!(),
+            BinOpKind::Logic(op) => match op {
+                LogicOp::Eq => Ok(Value::Boolean(lv == rv)),
+                LogicOp::NEq => Ok(Value::Boolean(lv != rv)),
+                _ => todo!(),
+            },
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use std::rc::Rc;
+
+    use crate::ast::constant::Constant;
+    use crate::eval::context::Context;
+    use crate::eval::tests::eval_out;
+    use crate::test_util::force_any_val;
+
+    use super::*;
+
+    fn check_eq_neq(left: Constant, right: Constant) -> bool {
+        let eq_op: Expr = Box::new(BinOp {
+            kind: BinOpKind::Logic(LogicOp::Eq),
+            left: Box::new(left.clone()).into(),
+            right: Box::new(right.clone()).into(),
+        })
+        .into();
+        let ctx = Rc::new(force_any_val::<Context>());
+        let neq_op: Expr = Box::new(BinOp {
+            kind: BinOpKind::Logic(LogicOp::NEq),
+            left: Box::new(left).into(),
+            right: Box::new(right).into(),
+        })
+        .into();
+        let ctx1 = Rc::new(force_any_val::<Context>());
+        eval_out::<bool>(&eq_op, ctx) && !eval_out::<bool>(&neq_op, ctx1)
+    }
+
+    #[test]
+    fn num_eq() {
+        assert!(check_eq_neq(1i64.into(), 1i64.into()));
+    }
+
+    #[test]
+    fn num_neq() {
+        assert!(!check_eq_neq(2i64.into(), 1i64.into()));
+    }
+
+    #[test]
+    fn option_eq() {
+        assert!(check_eq_neq(Some(1i64).into(), Some(1i64).into()));
+        let none: Option<i64> = None;
+        assert!(check_eq_neq(none.into(), none.into()));
+        // Option<Vec<i8>>
+        assert!(check_eq_neq(
+            Some(vec![1i8, 2i8]).into(),
+            Some(vec![1i8, 2i8]).into()
+        ));
+        // Vec<Option<i64>>
+        assert!(check_eq_neq(
+            vec![Some(1i64), Some(1i64)].into(),
+            vec![Some(1i64), Some(1i64)].into()
+        ));
+    }
+
+    #[test]
+    fn option_neq() {
+        assert!(!check_eq_neq(Some(2i64).into(), Some(1i64).into()));
+        let none: Option<i64> = None;
+        assert!(!check_eq_neq(none.into(), Some(1i64).into()));
+        // Option<Vec<i8>>
+        assert!(!check_eq_neq(
+            Some(vec![1i8, 2i8]).into(),
+            Some(vec![2i8, 2i8]).into()
+        ));
+        // Vec<Option<i64>>
+        assert!(!check_eq_neq(
+            vec![Some(1i64), Some(1i64)].into(),
+            vec![Some(2i64), Some(1i64)].into()
+        ));
+    }
+
+    #[test]
+    fn tuple_eq() {
+        assert!(check_eq_neq((1i64, true).into(), (1i64, true).into()));
+    }
+
+    use proptest::prelude::*;
+
+    proptest! {
+
+        #[test]
+        fn test_eq(v in any::<Constant>()) {
+            prop_assert![check_eq_neq(v.clone(), v)];
+        }
+    }
+}
diff --git a/ergo-lib/src/ast/constant.rs b/ergo-lib/src/ast/constant.rs
index d7c644737..4aaec5b45 100644
--- a/ergo-lib/src/ast/constant.rs
+++ b/ergo-lib/src/ast/constant.rs
@@ -9,9 +9,11 @@ use crate::{
     serialization::{SerializationError, SigmaSerializable},
     sigma_protocol::{dlog_group::EcPoint, sigma_boolean::SigmaProp},
 };
+use impl_trait_for_tuples::impl_for_tuples;
 #[cfg(feature = "json")]
 use serde::{Deserialize, Serialize};
 use std::convert::TryFrom;
+use std::convert::TryInto;
 
 mod constant_placeholder;
 
@@ -152,7 +154,7 @@ impl From<Vec<i8>> for Constant {
     fn from(v: Vec<i8>) -> Constant {
         Constant {
             tpe: SType::SColl(Box::new(SType::SByte)),
-            v: Value::Coll(Box::new(Coll::Primitive(CollPrim::CollByte(v)))),
+            v: v.into(),
         }
     }
 }
@@ -166,6 +168,28 @@ impl<T: LiftIntoSType + StoredNonPrimitive + Into<Value>> From<Vec<T>> for Const
     }
 }
 
+impl<T: LiftIntoSType + Into<Value>> From<Option<T>> for Constant {
+    fn from(opt: Option<T>) -> Self {
+        Constant {
+            tpe: SType::SOption(Box::new(T::stype())),
+            v: opt.into(),
+        }
+    }
+}
+
+#[impl_for_tuples(2, 4)]
+impl Into<Constant> for Tuple {
+    fn into(self) -> Constant {
+        let constants: Vec<Constant> = [for_tuples!(  #( Tuple.into() ),* )].to_vec();
+        let (types, values): (Vec<SType>, Vec<Value>) =
+            constants.into_iter().map(|c| (c.tpe, c.v)).unzip();
+        Constant {
+            tpe: SType::STuple(types.try_into().unwrap()),
+            v: Value::Tup(values.try_into().unwrap()),
+        }
+    }
+}
+
 /// Extract value wrapped in a type
 pub trait TryExtractInto<F> {
     /// Extract value of the given type from any type (e.g. ['Constant'], [`super::value::Value`])
@@ -196,99 +220,206 @@ impl<T: TryExtractFrom<Value>> TryExtractFrom<Constant> for T {
     }
 }
 
-impl TryExtractFrom<Constant> for Vec<i8> {
-    fn try_extract_from(c: Constant) -> Result<Self, TryExtractFromError> {
-        match c.v {
-            Value::Coll(v) => match *v {
-                Coll::Primitive(CollPrim::CollByte(bs)) => Ok(bs),
-                _ => Err(TryExtractFromError(format!(
-                    "expected {:?}, found {:?}",
-                    std::any::type_name::<Self>(),
-                    v
-                ))),
-            },
-            _ => Err(TryExtractFromError(format!(
-                "expected {:?}, found {:?}",
-                std::any::type_name::<Self>(),
-                c.v
-            ))),
-        }
-    }
-}
-
-impl TryExtractFrom<Constant> for Vec<u8> {
-    fn try_extract_from(cv: Constant) -> Result<Self, TryExtractFromError> {
-        use crate::util::FromVecI8;
-        Vec::<i8>::try_extract_from(cv).map(Vec::<u8>::from_vec_i8)
-    }
-}
-
 #[cfg(test)]
 mod tests {
+    use core::fmt;
+
+    use crate::types::stype::TupleItems;
+
     use super::*;
     use proptest::collection::vec;
     use proptest::prelude::*;
 
+    fn primitive_type_value() -> BoxedStrategy<Constant> {
+        prop_oneof![
+            any::<bool>().prop_map_into(),
+            any::<i8>().prop_map_into(),
+            any::<i16>().prop_map_into(),
+            any::<i32>().prop_map_into(),
+            any::<i64>().prop_map_into(),
+            any::<EcPoint>().prop_map_into(),
+            any::<SigmaProp>().prop_map_into(),
+            vec(any::<i8>(), 0..100).prop_map_into(),
+            vec(any::<i64>(), 0..100).prop_map_into(),
+        ]
+        .boxed()
+    }
+
+    fn coll_from_constant(c: Constant, length: usize) -> Constant {
+        Constant {
+            tpe: SType::SColl(Box::new(c.tpe.clone())),
+            v: Value::Coll(Box::new(if c.tpe == SType::SByte {
+                let mut values: Vec<i8> = Vec::with_capacity(length);
+                let byte: i8 = c.v.try_extract_into().unwrap();
+                for _ in 0..length {
+                    values.push(byte);
+                }
+                Coll::Primitive(CollPrim::CollByte(values))
+            } else {
+                let mut values: Vec<Value> = Vec::with_capacity(length);
+                for _ in 0..length {
+                    values.push(c.v.clone());
+                }
+                Coll::NonPrimitive {
+                    elem_tpe: c.tpe,
+                    v: values,
+                }
+            })),
+        }
+    }
+
     impl Arbitrary for Constant {
         type Parameters = ();
         type Strategy = BoxedStrategy<Self>;
 
         fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
-            prop_oneof![
-                any::<bool>().prop_map_into(),
-                any::<i8>().prop_map_into(),
-                any::<i16>().prop_map_into(),
-                any::<i32>().prop_map_into(),
-                any::<i64>().prop_map_into(),
-                any::<EcPoint>().prop_map_into(),
-                any::<SigmaProp>().prop_map_into(),
-                (vec(any::<i8>(), 0..100)).prop_map_into(),
-                (vec(any::<i16>(), 0..100)).prop_map_into(),
-                (vec(any::<i32>(), 0..100)).prop_map_into(),
-                (vec(any::<i64>(), 0..100)).prop_map_into(),
-            ]
+            prop_oneof![primitive_type_value().prop_recursive(4, 64, 15, |elem| {
+                prop_oneof![
+                    // Coll[_]
+                    elem.clone().prop_map(|c| coll_from_constant(c, 0)),
+                    elem.clone().prop_map(|c| coll_from_constant(c, 1)),
+                    elem.clone().prop_map(|c| coll_from_constant(c, 2)),
+                    elem.clone().prop_map(|c| coll_from_constant(c, 10)),
+                    // no Option[_] since it cannot be serialized (for now)
+                    // // Some(v)
+                    // elem.clone().prop_map(|c| Constant {
+                    //     tpe: SType::SOption(Box::new(c.tpe)),
+                    //     v: Value::Opt(Box::new(Some(c.v)))
+                    // }),
+                    // // None
+                    // elem.prop_map(|c| Constant {
+                    //     tpe: SType::SOption(Box::new(c.tpe)),
+                    //     v: Value::Opt(Box::new(None))
+                    // })
+
+                    // Tuple
+                    vec(elem, 2..=4).prop_map(|constants| Constant {
+                        tpe: SType::STuple(
+                            TupleItems::try_from(
+                                constants
+                                    .clone()
+                                    .into_iter()
+                                    .map(|c| c.tpe)
+                                    .collect::<Vec<SType>>()
+                            )
+                            .unwrap()
+                        ),
+                        v: Value::Tup(
+                            constants
+                                .into_iter()
+                                .map(|c| c.v)
+                                .collect::<Vec<Value>>()
+                                .try_into()
+                                .unwrap()
+                        )
+                    }),
+                ]
+            })]
             .boxed()
         }
     }
 
+    fn test_constant_roundtrip<T>(v: T)
+    where
+        T: TryExtractInto<T> + TryExtractFrom<Value> + Into<Constant> + fmt::Debug + Eq + Clone,
+    {
+        let constant: Constant = v.clone().into();
+        let v_extracted: T = constant.try_extract_into::<T>().unwrap();
+        assert_eq!(v, v_extracted);
+    }
+
     proptest! {
 
         #[test]
-        fn test_try_extract_from(c in any::<Constant>()) {
-            // let c = force_any_val::<Constant>();
-            match c.clone().tpe {
-                SType::SBoolean => {
-                    let _ = bool::try_extract_from(c).unwrap();
-                }
-                SType::SByte => {
-                    let _ = i8::try_extract_from(c).unwrap();
-                }
-                SType::SShort => {
-                    let _ = i16::try_extract_from(c).unwrap();
-                }
-                SType::SInt => {
-                    let _ = i32::try_extract_from(c).unwrap();
-                }
-                SType::SLong => {
-                    let _ = i64::try_extract_from(c).unwrap();
-                }
-                SType::SGroupElement => {
-                    let _ = EcPoint::try_extract_from(c).unwrap();
-                }
-                SType::SSigmaProp => {
-                    let _ = SigmaProp::try_extract_from(c).unwrap();
-                }
-                SType::SColl(elem_type) => {
-                    match *elem_type {
-                        SType::SByte => { let _ = Vec::<i8>::try_extract_from(c).unwrap(); }
-                        SType::SShort => { let _ = Vec::<i16>::try_extract_from(c).unwrap(); }
-                        SType::SInt => { let _ = Vec::<i32>::try_extract_from(c).unwrap(); }
-                        SType::SLong => { let _ = Vec::<i64>::try_extract_from(c).unwrap(); }
-                        _ => todo!()
-                    }
-                }
-                _ => todo!(),
-            };
+        fn bool_roundtrip(v in any::<bool>()) {
+            test_constant_roundtrip(v);
         }
+
+        #[test]
+        fn i8_roundtrip(v in any::<i8>()) {
+            test_constant_roundtrip(v);
+        }
+
+        #[test]
+        fn i16_roundtrip(v in any::<i16>()) {
+            test_constant_roundtrip(v);
+        }
+
+        #[test]
+        fn i32_roundtrip(v in any::<i32>()) {
+            test_constant_roundtrip(v);
+        }
+
+        #[test]
+        fn i64_roundtrip(v in any::<i64>()) {
+            test_constant_roundtrip(v);
+        }
+
+        #[test]
+        fn group_element_roundtrip(v in any::<EcPoint>()) {
+            test_constant_roundtrip(v);
+        }
+
+        #[test]
+        fn sigma_prop_roundtrip(v in any::<SigmaProp>()) {
+            test_constant_roundtrip(v);
+        }
+
+        #[test]
+        fn vec_i8_roundtrip(v in any::<Vec<i8>>()) {
+            test_constant_roundtrip(v);
+        }
+
+        #[test]
+        fn vec_u8_roundtrip(v in any::<Vec<u8>>()) {
+            test_constant_roundtrip(v);
+        }
+
+        #[test]
+        fn vec_i16_roundtrip(v in any::<Vec<i16>>()) {
+            test_constant_roundtrip(v);
+        }
+
+        #[test]
+        fn vec_i32_roundtrip(v in any::<Vec<i32>>()) {
+            test_constant_roundtrip(v);
+        }
+
+        #[test]
+        fn vec_i64_roundtrip(v in any::<Vec<i64>>()) {
+            test_constant_roundtrip(v);
+        }
+
+        #[test]
+        fn vec_sigmaprop_roundtrip(v in any::<Vec<SigmaProp>>()) {
+            test_constant_roundtrip(v);
+        }
+
+        #[test]
+        fn option_primitive_type_roundtrip(v in any::<Option<i64>>()) {
+            test_constant_roundtrip(v);
+        }
+
+        #[test]
+        fn option_nested_vector_type_roundtrip(v in any::<Option<Vec<(i64, bool)>>>()) {
+            test_constant_roundtrip(v);
+        }
+
+        #[test]
+        fn option_nested_tuple_type_roundtrip(v in any::<Option<(i64, bool)>>()) {
+            test_constant_roundtrip(v);
+        }
+
+
+        #[test]
+        fn tuple_primitive_types_roundtrip(v in any::<(i64, bool)>()) {
+            test_constant_roundtrip(v);
+        }
+
+        #[test]
+        fn tuple_nested_types_roundtrip(v in any::<(Option<i64>, Vec<SigmaProp>)>()) {
+            test_constant_roundtrip(v);
+        }
+
     }
 }
diff --git a/ergo-lib/src/ast/expr.rs b/ergo-lib/src/ast/expr.rs
index f2e9338a5..91f72c399 100644
--- a/ergo-lib/src/ast/expr.rs
+++ b/ergo-lib/src/ast/expr.rs
@@ -3,13 +3,13 @@ use core::fmt;
 use crate::serialization::op_code::OpCode;
 use crate::types::stype::SType;
 
+use super::bin_op::BinOp;
 use super::coll_fold::Fold;
 use super::constant::Constant;
 use super::constant::ConstantPlaceholder;
 use super::extract_reg_as::ExtractRegisterAs;
 use super::global_vars::GlobalVars;
 use super::method_call::MethodCall;
-use super::ops;
 use super::option_get::OptionGet;
 use super::predef_func::PredefFunc;
 use super::property_call::PropertyCall;
@@ -37,7 +37,7 @@ pub enum Expr {
     /// Property call
     ProperyCall(Box<PropertyCall>),
     /// Binary operation
-    BinOp(ops::BinOp, Box<Expr>, Box<Expr>),
+    BinOp(Box<BinOp>),
     /// Option get method
     OptionGet(Box<OptionGet>),
     /// Extract register's value (box.RX properties)
@@ -56,6 +56,7 @@ impl Expr {
             Expr::Context => OpCode::CONTEXT,
             Expr::OptionGet(v) => v.op_code(),
             Expr::ExtractRegisterAs(v) => v.op_code(),
+            Expr::BinOp(op) => op.op_code(),
             _ => todo!("{0:?}", self),
         }
     }
diff --git a/ergo-lib/src/ast/ops.rs b/ergo-lib/src/ast/ops.rs
deleted file mode 100644
index 5a5ae237a..000000000
--- a/ergo-lib/src/ast/ops.rs
+++ /dev/null
@@ -1,14 +0,0 @@
-//! Operators in ErgoTree
-#[derive(PartialEq, Eq, Debug, Clone)]
-/// Operations for numerical types
-pub enum NumOp {
-    /// Addition
-    Add,
-}
-
-#[derive(PartialEq, Eq, Debug, Clone)]
-/// Binary operations
-pub enum BinOp {
-    /// Binary operations for numerical types
-    Num(NumOp),
-}
diff --git a/ergo-lib/src/ast/value.rs b/ergo-lib/src/ast/value.rs
index 8c8fa95aa..deb419e7e 100644
--- a/ergo-lib/src/ast/value.rs
+++ b/ergo-lib/src/ast/value.rs
@@ -1,8 +1,11 @@
 //! Ergo data type
 
 use std::convert::TryFrom;
+use std::convert::TryInto;
 use std::rc::Rc;
 
+use impl_trait_for_tuples::impl_for_tuples;
+
 use crate::chain::ergo_box::ErgoBox;
 use crate::eval::context::Context;
 use crate::sigma_protocol::dlog_group::EcPoint;
@@ -12,6 +15,7 @@ use crate::sigma_protocol::sigma_boolean::SigmaProofOfKnowledgeTree;
 use crate::sigma_protocol::sigma_boolean::SigmaProp;
 use crate::types::stype::LiftIntoSType;
 use crate::types::stype::SType;
+use crate::types::stype::TupleItems;
 
 use super::constant::TryExtractFrom;
 use super::constant::TryExtractFromError;
@@ -82,7 +86,7 @@ pub enum Value {
     /// Collection of values of the same type
     Coll(Box<Coll>),
     /// Tuple (arbitrary type values)
-    Tup(Vec<Value>),
+    Tup(TupleItems<Value>),
     /// Transaction(and blockchain) context info
     Context(Rc<Context>),
     /// Optional value
@@ -144,6 +148,18 @@ impl From<ErgoBox> for Value {
     }
 }
 
+impl From<Vec<i8>> for Value {
+    fn from(v: Vec<i8>) -> Self {
+        Value::Coll(Box::new(Coll::Primitive(CollPrim::CollByte(v))))
+    }
+}
+
+impl<T: Into<Value>> From<Option<T>> for Value {
+    fn from(opt: Option<T>) -> Self {
+        Value::Opt(Box::new(opt.map(|v| v.into())))
+    }
+}
+
 /// Marker trait to select types for which CollElems::NonPrimitive is used to store elements as Vec<ConstantVal>
 pub trait StoredNonPrimitive {}
 
@@ -152,16 +168,30 @@ impl StoredNonPrimitive for i16 {}
 impl StoredNonPrimitive for i32 {}
 impl StoredNonPrimitive for i64 {}
 impl StoredNonPrimitive for ErgoBox {}
+impl StoredNonPrimitive for EcPoint {}
+impl StoredNonPrimitive for SigmaProp {}
+impl<T: StoredNonPrimitive> StoredNonPrimitive for Option<T> {}
 
-impl<T: LiftIntoSType + StoredNonPrimitive + Into<Value>> Into<Value> for Vec<T> {
-    fn into(self) -> Value {
+#[impl_for_tuples(2, 4)]
+impl StoredNonPrimitive for Tuple {}
+
+impl<T: LiftIntoSType + StoredNonPrimitive + Into<Value>> From<Vec<T>> for Value {
+    fn from(v: Vec<T>) -> Self {
         Value::Coll(Box::new(Coll::NonPrimitive {
             elem_tpe: T::stype(),
-            v: self.into_iter().map(|i| i.into()).collect(),
+            v: v.into_iter().map(|i| i.into()).collect(),
         }))
     }
 }
 
+#[impl_for_tuples(2, 4)]
+impl Into<Value> for Tuple {
+    fn into(self) -> Value {
+        let v: Vec<Value> = [for_tuples!(  #( Tuple.into() ),* )].to_vec();
+        Value::Tup(v.try_into().unwrap())
+    }
+}
+
 impl TryExtractFrom<Value> for bool {
     fn try_extract_from(cv: Value) -> Result<bool, TryExtractFromError> {
         match cv {
@@ -268,6 +298,33 @@ impl<T: TryExtractFrom<Value> + StoredNonPrimitive> TryExtractFrom<Value> for Ve
     }
 }
 
+impl TryExtractFrom<Value> for Vec<i8> {
+    fn try_extract_from(v: Value) -> Result<Self, TryExtractFromError> {
+        match v {
+            Value::Coll(v) => match *v {
+                Coll::Primitive(CollPrim::CollByte(bs)) => Ok(bs),
+                _ => Err(TryExtractFromError(format!(
+                    "expected {:?}, found {:?}",
+                    std::any::type_name::<Self>(),
+                    v
+                ))),
+            },
+            _ => Err(TryExtractFromError(format!(
+                "expected {:?}, found {:?}",
+                std::any::type_name::<Self>(),
+                v
+            ))),
+        }
+    }
+}
+
+impl TryExtractFrom<Value> for Vec<u8> {
+    fn try_extract_from(v: Value) -> Result<Self, TryExtractFromError> {
+        use crate::util::FromVecI8;
+        Vec::<i8>::try_extract_from(v).map(Vec::<u8>::from_vec_i8)
+    }
+}
+
 impl TryFrom<Value> for ProveDlog {
     type Error = TryExtractFromError;
     fn try_from(cv: Value) -> Result<Self, Self::Error> {
@@ -300,3 +357,38 @@ impl TryExtractFrom<Value> for Rc<Context> {
         }
     }
 }
+
+impl<T: TryExtractFrom<Value>> TryExtractFrom<Value> for Option<T> {
+    fn try_extract_from(v: Value) -> Result<Self, TryExtractFromError> {
+        match v {
+            Value::Opt(opt) => opt.map(T::try_extract_from).transpose(),
+            _ => Err(TryExtractFromError(format!(
+                "expected Context, found {:?}",
+                v
+            ))),
+        }
+    }
+}
+
+#[impl_for_tuples(2, 4)]
+impl TryExtractFrom<Value> for Tuple {
+    fn try_extract_from(v: Value) -> Result<Self, TryExtractFromError> {
+        match v {
+            Value::Tup(items) => {
+                let mut iter = items.iter();
+                Ok(for_tuples!( ( #(
+                                Tuple::try_extract_from(
+                                    iter
+                                        .next()
+                                        .cloned()
+                                        .ok_or_else(|| TryExtractFromError("not enough items in STuple".to_string()))?
+                                )?
+                                ),* ) ))
+            }
+            _ => Err(TryExtractFromError(format!(
+                "expected Context, found {:?}",
+                v
+            ))),
+        }
+    }
+}
diff --git a/ergo-lib/src/ergo_tree.rs b/ergo-lib/src/ergo_tree.rs
index 7686bfe6f..8d93984a4 100644
--- a/ergo-lib/src/ergo_tree.rs
+++ b/ergo-lib/src/ergo_tree.rs
@@ -337,6 +337,7 @@ mod tests {
         assert!(ErgoTree::sigma_parse_bytes(vec![
             ErgoTreeHeader::CONSTANT_SEGREGATION_FLAG,
             1,
+            0,
             99,
             99
         ])
diff --git a/ergo-lib/src/eval.rs b/ergo-lib/src/eval.rs
index 73c45d029..36e5e7720 100644
--- a/ergo-lib/src/eval.rs
+++ b/ergo-lib/src/eval.rs
@@ -13,10 +13,9 @@ use thiserror::Error;
 use self::context::Context;
 use self::cost_accum::CostError;
 
-mod costs;
-
 pub(crate) mod context;
 pub(crate) mod cost_accum;
+pub(crate) mod costs;
 pub(crate) mod expr;
 pub(crate) mod global_vars;
 pub(crate) mod method_call;
@@ -92,8 +91,8 @@ pub trait Evaluator {
 }
 
 pub struct EvalContext {
-    ctx: Rc<Context>,
-    cost_accum: CostAccumulator,
+    pub ctx: Rc<Context>,
+    pub cost_accum: CostAccumulator,
 }
 
 impl EvalContext {
@@ -109,37 +108,6 @@ pub trait Evaluable {
     fn eval(&self, env: &Env, ctx: &mut EvalContext) -> Result<Value, EvalError>;
 }
 
-// #[allow(unconditional_recursion)]
-// fn eval(
-//     expr: &Expr,
-//     env: &Env,
-//     ca: &mut CostAccumulator,
-//     ctx: &Context,
-// ) -> Result<Value, EvalError> {
-//     match expr {
-//         Expr::Const(c) => Ok(c.v.clone()),
-//         Expr::Coll { .. } => todo!(),
-//         Expr::Tup { .. } => todo!(),
-//         Expr::PredefFunc(_) => todo!(),
-//         Expr::CollM(_) => todo!(),
-//         Expr::BoxM(_) => todo!(),
-//         Expr::GlobalVars(v) => v.eval(env, ca, ctx),
-//         Expr::MethodCall(v) => v.eval(env, ca, ctx),
-//         Expr::BinOp(_bin_op, l, r) => {
-//             let _v_l = eval(l, env, ca, ctx)?;
-//             let _v_r = eval(r, env, ca, ctx)?;
-//             ca.add_cost_of(expr);
-//             todo!()
-//             // Ok(match bin_op {
-//             //     BinOp::Num(op) => match op {
-//             //         NumOp::Add => v_l + v_r,
-//             //     },
-//             // })
-//         }
-//         _ => Err(EvalError::UnexpectedExpr),
-//     }
-// }
-
 #[cfg(test)]
 pub mod tests {
 
diff --git a/ergo-lib/src/eval/costs.rs b/ergo-lib/src/eval/costs.rs
index d019394e6..1d330ec57 100644
--- a/ergo-lib/src/eval/costs.rs
+++ b/ergo-lib/src/eval/costs.rs
@@ -6,13 +6,15 @@ use derive_more::{From, Into};
 #[derive(PartialEq, Eq, Debug, Clone, From, Into)]
 pub struct Cost(u32);
 
-pub struct Costs {}
-
-impl Costs {
-    pub const DEFAULT: Costs = Costs {};
+pub struct Costs {
+    pub eq_const_size: Cost,
 }
 
 impl Costs {
+    pub const DEFAULT: Costs = Costs {
+        eq_const_size: Cost(1),
+    };
+
     pub fn cost_of(&self, _: &Expr) -> Cost {
         Cost(1)
     }
diff --git a/ergo-lib/src/eval/expr.rs b/ergo-lib/src/eval/expr.rs
index 25c273aab..55da93452 100644
--- a/ergo-lib/src/eval/expr.rs
+++ b/ergo-lib/src/eval/expr.rs
@@ -7,29 +7,19 @@ use super::EvalError;
 use super::Evaluable;
 
 impl Evaluable for Expr {
-    fn eval(&self, env: &Env, ectx: &mut EvalContext) -> Result<Value, EvalError> {
-        ectx.cost_accum.add_cost_of(self)?;
+    fn eval(&self, env: &Env, ctx: &mut EvalContext) -> Result<Value, EvalError> {
+        ctx.cost_accum.add_cost_of(self)?;
         match self {
             Expr::Const(c) => Ok(c.v.clone()),
             Expr::PredefFunc(_) => todo!(),
             Expr::Fold(_) => todo!(),
-            Expr::ExtractRegisterAs(v) => v.eval(env, ectx),
-            Expr::GlobalVars(v) => v.eval(env, ectx),
-            Expr::MethodCall(v) => v.eval(env, ectx),
-            Expr::ProperyCall(v) => v.eval(env, ectx),
-            Expr::BinOp(_bin_op, _l, _r) => {
-                todo!()
-                // let _v_l = eval(l, env, ca, ctx)?;
-                // let _v_r = eval(r, env, ca, ctx)?;
-                // ca.add_cost_of(expr);
-                // Ok(match bin_op {
-                //     BinOp::Num(op) => match op {
-                //         NumOp::Add => v_l + v_r,
-                //     },
-                // })
-            }
-            Expr::Context => Ok(Value::Context(ectx.ctx.clone())),
-            Expr::OptionGet(v) => v.eval(env, ectx),
+            Expr::ExtractRegisterAs(op) => op.eval(env, ctx),
+            Expr::GlobalVars(op) => op.eval(env, ctx),
+            Expr::MethodCall(op) => op.eval(env, ctx),
+            Expr::ProperyCall(op) => op.eval(env, ctx),
+            Expr::BinOp(op) => op.eval(env, ctx),
+            Expr::Context => Ok(Value::Context(ctx.ctx.clone())),
+            Expr::OptionGet(v) => v.eval(env, ctx),
             _ => Err(EvalError::UnexpectedExpr(format!(
                 "Don't know how to eval Expr: {}",
                 self
diff --git a/ergo-lib/src/serialization.rs b/ergo-lib/src/serialization.rs
index 1223015ad..23a2b9c2d 100644
--- a/ergo-lib/src/serialization.rs
+++ b/ergo-lib/src/serialization.rs
@@ -1,5 +1,6 @@
 //! Serializers
 
+mod bin_op;
 mod constant;
 mod constant_placeholder;
 mod data;
diff --git a/ergo-lib/src/serialization/bin_op.rs b/ergo-lib/src/serialization/bin_op.rs
new file mode 100644
index 000000000..d91dcbd18
--- /dev/null
+++ b/ergo-lib/src/serialization/bin_op.rs
@@ -0,0 +1,61 @@
+use std::io::Error;
+
+use crate::ast::bin_op::BinOp;
+use crate::ast::bin_op::BinOpKind;
+use crate::ast::expr::Expr;
+
+use super::sigma_byte_reader::SigmaByteRead;
+use super::sigma_byte_writer::SigmaByteWrite;
+use super::SerializationError;
+use super::SigmaSerializable;
+
+pub fn bin_op_sigma_serialize<W: SigmaByteWrite>(bin_op: &BinOp, w: &mut W) -> Result<(), Error> {
+    bin_op.left.sigma_serialize(w)?;
+    bin_op.right.sigma_serialize(w)?;
+    Ok(())
+}
+
+pub fn bin_op_sigma_parse<R: SigmaByteRead>(
+    op_kind: BinOpKind,
+    r: &mut R,
+) -> Result<Expr, SerializationError> {
+    let left = Expr::sigma_parse(r)?;
+    let right = Expr::sigma_parse(r)?;
+    Ok(Box::new(BinOp {
+        kind: op_kind,
+        left,
+        right,
+    })
+    .into())
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::ast::bin_op::LogicOp;
+    use crate::serialization::sigma_serialize_roundtrip;
+    use crate::test_util::force_any_val;
+
+    fn test_ser_roundtrip(kind: BinOpKind, left: Expr, right: Expr) {
+        let eq_op: Expr = Box::new(BinOp { kind, left, right }).into();
+        assert_eq![sigma_serialize_roundtrip(&eq_op), eq_op];
+    }
+
+    #[test]
+    fn ser_roundtrip_eq() {
+        test_ser_roundtrip(
+            LogicOp::Eq.into(),
+            force_any_val::<Expr>(),
+            force_any_val::<Expr>(),
+        )
+    }
+
+    #[test]
+    fn ser_roundtrip_neq() {
+        test_ser_roundtrip(
+            LogicOp::NEq.into(),
+            force_any_val::<Expr>(),
+            force_any_val::<Expr>(),
+        )
+    }
+}
diff --git a/ergo-lib/src/serialization/data.rs b/ergo-lib/src/serialization/data.rs
index 948320b15..d1b46a99a 100644
--- a/ergo-lib/src/serialization/data.rs
+++ b/ergo-lib/src/serialization/data.rs
@@ -11,6 +11,7 @@ use crate::types::stype::SType;
 use crate::util::AsVecU8;
 
 use super::sigma_byte_writer::SigmaByteWrite;
+use std::convert::TryInto;
 use std::io;
 
 pub struct DataSerializer {}
@@ -23,13 +24,11 @@ impl DataSerializer {
             Value::Byte(v) => w.put_i8(*v),
             Value::Short(v) => w.put_i16(*v),
             Value::Int(v) => w.put_i32(*v),
-            // Value::TInt(v) => w.put_i32(v.raw),
             Value::Long(v) => w.put_i64(*v),
             Value::BigInt => todo!(),
             Value::GroupElement(ecp) => ecp.sigma_serialize(w),
             Value::SigmaProp(s) => s.value().sigma_serialize(w),
             Value::CBox(_) => todo!(),
-            // Value::TBox(_) => todo!(),
             Value::AvlTree => todo!(),
             Value::Coll(ct) => match &**ct {
                 Coll::Primitive(CollPrim::CollByte(b)) => {
@@ -42,8 +41,10 @@ impl DataSerializer {
                         .try_for_each(|e| DataSerializer::sigma_serialize(e, w))
                 }
             },
-            Value::Tup(_) => todo!(),
-            Value::Opt(_) => todo!(), // unsupported, see https://github.com/ScorexFoundation/sigmastate-interpreter/issues/659
+            Value::Tup(items) => items
+                .iter()
+                .try_for_each(|i| DataSerializer::sigma_serialize(i, w)),
+            Value::Opt(_) => panic!(), // unsupported, see https://github.com/ScorexFoundation/sigmastate-interpreter/issues/659
             Value::Context(_) => todo!(), // TODO: throw error? it should not be here
         }
     }
@@ -81,12 +82,15 @@ impl DataSerializer {
                     v: elems,
                 }))
             }
-            STup(types) => {
+            STuple(types) => {
                 let mut items = Vec::new();
                 types.iter().try_for_each(|tpe| {
                     DataSerializer::sigma_parse(tpe, r).map(|v| items.push(v))
                 })?;
-                Value::Tup(items)
+                // we get the tuple item value for each tuple item type,
+                // since items types quantity has checked bounds, we can be sure that items count
+                // is correct
+                Value::Tup(items.try_into().unwrap())
             }
 
             c => {
diff --git a/ergo-lib/src/serialization/expr.rs b/ergo-lib/src/serialization/expr.rs
index 1de5a1b14..83675b9c2 100644
--- a/ergo-lib/src/serialization/expr.rs
+++ b/ergo-lib/src/serialization/expr.rs
@@ -1,4 +1,7 @@
+use super::bin_op::bin_op_sigma_parse;
+use super::bin_op::bin_op_sigma_serialize;
 use super::{op_code::OpCode, sigma_byte_writer::SigmaByteWrite};
+use crate::ast::bin_op::LogicOp;
 use crate::ast::coll_fold::Fold;
 use crate::ast::constant::Constant;
 use crate::ast::constant::ConstantPlaceholder;
@@ -37,6 +40,7 @@ impl SigmaSerializable for Expr {
                     Expr::Context => Ok(()),
                     Expr::OptionGet(v) => v.sigma_serialize(w),
                     Expr::ExtractRegisterAs(v) => v.sigma_serialize(w),
+                    Expr::BinOp(op) => bin_op_sigma_serialize(op, w),
                     _ => panic!(format!("don't know how to serialize {:?}", expr)),
                 }
             }
@@ -83,6 +87,8 @@ impl SigmaSerializable for Expr {
                 OpCode::EXTRACT_REGISTER_AS => {
                     Ok(Box::new(ExtractRegisterAs::sigma_parse(r)?).into())
                 }
+                OpCode::EQ => Ok(bin_op_sigma_parse(LogicOp::Eq.into(), r)?),
+                OpCode::NEQ => Ok(bin_op_sigma_parse(LogicOp::NEq.into(), r)?),
                 o => Err(SerializationError::NotImplementedOpCode(o.value())),
             }
         }
diff --git a/ergo-lib/src/serialization/op_code.rs b/ergo-lib/src/serialization/op_code.rs
index b51da013f..b374e0a90 100644
--- a/ergo-lib/src/serialization/op_code.rs
+++ b/ergo-lib/src/serialization/op_code.rs
@@ -20,6 +20,9 @@ impl OpCode {
 
     pub const CONSTANT_PLACEHOLDER: OpCode = Self::new_op_code(3);
 
+    pub const EQ: OpCode = Self::new_op_code(35);
+    pub const NEQ: OpCode = Self::new_op_code(36);
+
     /// Environment (context methods)
     pub const HEIGHT: OpCode = Self::new_op_code(51);
     pub const INPUTS: OpCode = Self::new_op_code(52);
diff --git a/ergo-lib/src/serialization/serializable.rs b/ergo-lib/src/serialization/serializable.rs
index 0b83893a5..0b83bcdb8 100644
--- a/ergo-lib/src/serialization/serializable.rs
+++ b/ergo-lib/src/serialization/serializable.rs
@@ -12,9 +12,9 @@ use thiserror::Error;
 /// Ways serialization might fail
 #[derive(Error, Eq, PartialEq, Debug, Clone)]
 pub enum SerializationError {
-    /// Failed to parse op
-    #[error("op parsing error")]
-    InvalidOpCode,
+    /// Invalid op code
+    #[error("invalid op code: {0}")]
+    InvalidOpCode(u8),
     /// Lacking support for the op
     #[error("not implemented op error")]
     NotImplementedOpCode(u8),
@@ -39,6 +39,9 @@ pub enum SerializationError {
     /// Value out of bounds
     #[error("Value out of bounds: {0}")]
     ValueOutOfBounds(String),
+    /// Tuple items out of bounds
+    #[error("Tuple items out of bounds: {0}")]
+    TupleItemsOutOfBounds(usize),
 }
 
 impl From<vlq_encode::VlqEncodingError> for SerializationError {
diff --git a/ergo-lib/src/serialization/types.rs b/ergo-lib/src/serialization/types.rs
index ba8d9ff07..05191c691 100644
--- a/ergo-lib/src/serialization/types.rs
+++ b/ergo-lib/src/serialization/types.rs
@@ -6,6 +6,7 @@ use crate::serialization::{
 };
 use crate::types::stype::SType;
 use sigma_ser::vlq_encode;
+use std::convert::TryInto;
 use std::{io, ops::Add};
 use vlq_encode::WriteSigmaVlqExt;
 
@@ -28,17 +29,40 @@ impl TypeCode {
     pub const SBIGINT: TypeCode = Self::new(6);
     pub const SGROUP_ELEMENT: TypeCode = Self::new(7);
     pub const SSIGMAPROP: TypeCode = Self::new(8);
+
     pub const SANY: TypeCode = Self::new(97);
 
-    pub const COLLECTION_TYPE_CONSTR_ID: u8 = 1;
-    pub const COLLECTION_TYPE_CODE: TypeCode =
-        Self::new((TypeCode::MAX_PRIM_TYPECODE + 1) * TypeCode::COLLECTION_TYPE_CONSTR_ID);
+    const COLLECTION_CONSTR_ID: u8 = 1;
+    pub const COLLECTION: TypeCode =
+        Self::new((TypeCode::MAX_PRIM_TYPECODE + 1) * TypeCode::COLLECTION_CONSTR_ID);
+    const NESTED_COLLECTION_CONSTS_ID: u8 = 2;
+    pub const NESTED_COLLECTION: TypeCode =
+        Self::new((TypeCode::MAX_PRIM_TYPECODE + 1) * TypeCode::NESTED_COLLECTION_CONSTS_ID);
+
+    const TUPLE_PAIR1_CONSTR_ID: u8 = 5;
+    pub const TUPLE_PAIR1: TypeCode =
+        Self::new((TypeCode::MAX_PRIM_TYPECODE + 1) * TypeCode::TUPLE_PAIR1_CONSTR_ID);
+
+    const TUPLE_PAIR2_CONSTR_ID: u8 = 6;
+    pub const TUPLE_PAIR2: TypeCode =
+        Self::new((TypeCode::MAX_PRIM_TYPECODE + 1) * TypeCode::TUPLE_PAIR2_CONSTR_ID);
+
+    pub const TUPLE_TRIPLE: TypeCode = Self::TUPLE_PAIR2;
 
-    pub const OPTION_TYPE_CONSTR_ID: u8 = 3;
-    pub const OPTION_COLLECTION_TYPE_CONSTR_ID: u8 = 4;
-    pub const OPTION_TYPE_CODE: TypeCode =
-        Self::new((TypeCode::MAX_PRIM_TYPECODE + 1) * TypeCode::OPTION_TYPE_CONSTR_ID);
-    pub const OPTION_COLLECTION_TYPE_CODE: TypeCode =
+    const TUPLE_PAIR_SYMMETRIC_TYPE_CONSTR_ID: u8 = 7;
+    pub const TUPLE_PAIR_SYMMETRIC: TypeCode = Self::new(
+        (TypeCode::MAX_PRIM_TYPECODE + 1) * TypeCode::TUPLE_PAIR_SYMMETRIC_TYPE_CONSTR_ID,
+    );
+
+    pub const TUPLE_QUADRUPLE: TypeCode = Self::TUPLE_PAIR_SYMMETRIC;
+
+    pub const TUPLE: TypeCode = Self::new((TypeCode::MAX_PRIM_TYPECODE + 1) * 8);
+
+    const OPTION_CONSTR_ID: u8 = 3;
+    const OPTION_COLLECTION_TYPE_CONSTR_ID: u8 = 4;
+    pub const OPTION: TypeCode =
+        Self::new((TypeCode::MAX_PRIM_TYPECODE + 1) * TypeCode::OPTION_CONSTR_ID);
+    pub const OPTION_COLLECTION: TypeCode =
         Self::new((TypeCode::MAX_PRIM_TYPECODE + 1) * TypeCode::OPTION_COLLECTION_TYPE_CONSTR_ID);
 
     const fn new(c: u8) -> TypeCode {
@@ -81,7 +105,7 @@ fn get_embeddable_type(code: u8) -> Result<SType, SerializationError> {
         TypeCode::SBIGINT => Ok(SType::SBigInt),
         TypeCode::SGROUP_ELEMENT => Ok(SType::SGroupElement),
         TypeCode::SSIGMAPROP => Ok(SType::SSigmaProp),
-        _ => Err(SerializationError::InvalidOpCode),
+        _ => Err(SerializationError::InvalidOpCode(code)),
     }
 }
 
@@ -128,25 +152,76 @@ impl SigmaSerializable for SType {
             SType::SBox => todo!(),
             SType::SAvlTree => todo!(),
             SType::SOption(elem_type) if is_stype_embeddable(elem_type) => {
-                let code = TypeCode::OPTION_TYPE_CODE + elem_type.type_code();
+                let code = TypeCode::OPTION + elem_type.type_code();
                 code.sigma_serialize(w)
             }
             SType::SOption(elem_type) => match &**elem_type {
                 SType::SColl(elem_type) if is_stype_embeddable(elem_type.as_ref()) => {
-                    let code = TypeCode::OPTION_COLLECTION_TYPE_CODE + elem_type.type_code();
+                    let code = TypeCode::OPTION_COLLECTION + elem_type.type_code();
                     code.sigma_serialize(w)
                 }
                 _ => {
-                    TypeCode::OPTION_TYPE_CODE.sigma_serialize(w)?;
+                    TypeCode::OPTION.sigma_serialize(w)?;
                     elem_type.sigma_serialize(w)
                 }
             },
             SType::SColl(elem_type) if is_stype_embeddable(elem_type) => {
-                let code = TypeCode::COLLECTION_TYPE_CODE + elem_type.type_code();
+                let code = TypeCode::COLLECTION + elem_type.type_code();
                 code.sigma_serialize(w)
             }
-            SType::SColl(_) => todo!(),
-            SType::STup(_) => todo!(),
+            SType::SColl(elem_type) => match &**elem_type {
+                SType::SColl(inner_elem_type) if is_stype_embeddable(inner_elem_type.as_ref()) => {
+                    let code = TypeCode::NESTED_COLLECTION + inner_elem_type.type_code();
+                    code.sigma_serialize(w)
+                }
+                _ => {
+                    TypeCode::COLLECTION.sigma_serialize(w)?;
+                    elem_type.sigma_serialize(w)
+                }
+            },
+            SType::STuple(items) => match items.clone().as_slice() {
+                [t1, t2] => match (t1, t2) {
+                    (p, _) if is_stype_embeddable(p) => {
+                        if p == t2 {
+                            // Symmetric pair of primitive types (`(Int, Int)`, `(Byte,Byte)`, etc.)
+                            let code = TypeCode::TUPLE_PAIR_SYMMETRIC + p.type_code();
+                            code.sigma_serialize(w)
+                        } else {
+                            // Pair of types where first is primitive (`(_, Int)`)
+                            let code = TypeCode::TUPLE_PAIR1 + p.type_code();
+                            code.sigma_serialize(w)?;
+                            t2.sigma_serialize(w)
+                        }
+                    }
+                    (_, p) if is_stype_embeddable(p) => {
+                        // Pair of types where second is primitive (`(Int, _)`)
+                        let code = TypeCode::TUPLE_PAIR2 + p.type_code();
+                        code.sigma_serialize(w)?;
+                        t1.sigma_serialize(w)
+                    }
+                    (_, _) => {
+                        // Pair of non-primitive types (`((Int, Byte), (Boolean,Box))`, etc.)
+                        TypeCode::TUPLE_PAIR1.sigma_serialize(w)?;
+                        t1.sigma_serialize(w)?;
+                        t2.sigma_serialize(w)
+                    }
+                },
+                _ => match items.len() {
+                    3 => {
+                        TypeCode::TUPLE_TRIPLE.sigma_serialize(w)?;
+                        items.iter().try_for_each(|i| i.sigma_serialize(w))
+                    }
+                    4 => {
+                        TypeCode::TUPLE_QUADRUPLE.sigma_serialize(w)?;
+                        items.iter().try_for_each(|i| i.sigma_serialize(w))
+                    }
+                    _ => {
+                        TypeCode::TUPLE.sigma_serialize(w)?;
+                        w.put_u8(items.len() as u8)?;
+                        items.iter().try_for_each(|i| i.sigma_serialize(w))
+                    }
+                },
+            },
             SType::SFunc(_) => todo!(),
             SType::SContext(_) => todo!(),
             SType::STypeVar(_) => todo!(),
@@ -155,37 +230,110 @@ impl SigmaSerializable for SType {
 
     fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SerializationError> {
         // for reference see http://github.com/ScorexFoundation/sigmastate-interpreter/blob/25251c1313b0131835f92099f02cef8a5d932b5e/sigmastate/src/main/scala/sigmastate/serialization/TypeSerializer.scala#L118-L118
-        let type_code = TypeCode::sigma_parse(r)?;
-        let constr_id = type_code.value() / TypeCode::PRIM_RANGE;
-        let prim_id = type_code.value() % TypeCode::PRIM_RANGE;
-        let tpe = match constr_id {
-            // primitive
-            0 => get_embeddable_type(type_code.value())?,
-            // Coll[_]
-            1 => {
-                let t_elem = get_embeddable_type(prim_id)?;
-                SType::SColl(Box::new(t_elem))
-            }
-            // Option[_]
-            3 => {
-                let t_elem = get_embeddable_type(prim_id)?;
-                SType::SOption(Box::new(t_elem))
-            }
-            // Option[Coll[_]]
-            4 => {
-                let t_elem = get_embeddable_type(prim_id)?;
-                SType::SOption(SType::SColl(t_elem.into()).into())
+        let c = TypeCode::sigma_parse(r)?;
+
+        let tpe = if c.value() < TypeCode::TUPLE.value() {
+            let constr_id = c.value() / TypeCode::PRIM_RANGE;
+            let prim_id = c.value() % TypeCode::PRIM_RANGE;
+            match constr_id {
+                // primitive
+                0 => get_embeddable_type(c.value())?,
+                // Coll[_]
+                1 => {
+                    let t_elem = get_arg_type(r, prim_id)?;
+                    SType::SColl(Box::new(t_elem))
+                }
+                // Coll[Coll[_]]
+                2 => {
+                    let t_elem = get_arg_type(r, prim_id)?;
+                    SType::SColl(Box::new(SType::SColl(Box::new(t_elem))))
+                }
+                // Option[_]
+                3 => {
+                    let t_elem = get_arg_type(r, prim_id)?;
+                    SType::SOption(Box::new(t_elem))
+                }
+                // Option[Coll[_]]
+                4 => {
+                    let t_elem = get_arg_type(r, prim_id)?;
+                    SType::SOption(SType::SColl(t_elem.into()).into())
+                }
+                TypeCode::TUPLE_PAIR1_CONSTR_ID => {
+                    // (_, t2)
+                    let (t1, t2) = if prim_id == 0 {
+                        // Pair of non-primitive types (`((Int, Byte), (Boolean,Box))`, etc.)
+                        (Self::sigma_parse(r)?, Self::sigma_parse(r)?)
+                    } else {
+                        // Pair of types where first is primitive (`(_, Int)`)
+                        (get_embeddable_type(prim_id)?, Self::sigma_parse(r)?)
+                    };
+                    SType::STuple(vec![t1, t2].try_into().unwrap())
+                }
+                TypeCode::TUPLE_PAIR2_CONSTR_ID => {
+                    // (t1, _)
+                    if prim_id == 0 {
+                        // Triple of types
+                        let t1 = Self::sigma_parse(r)?;
+                        let t2 = Self::sigma_parse(r)?;
+                        let t3 = Self::sigma_parse(r)?;
+                        SType::STuple(vec![t1, t2, t3].try_into().unwrap())
+                    } else {
+                        // Pair of types where second is primitive (`(Int, _)`)
+                        let t2 = get_embeddable_type(prim_id)?;
+                        let t1 = Self::sigma_parse(r)?;
+                        SType::STuple(vec![t1, t2].try_into().unwrap())
+                    }
+                }
+                TypeCode::TUPLE_PAIR_SYMMETRIC_TYPE_CONSTR_ID => {
+                    // (_, _)
+                    if prim_id == 0 {
+                        // Quadriple of types
+                        let t1 = Self::sigma_parse(r)?;
+                        let t2 = Self::sigma_parse(r)?;
+                        let t3 = Self::sigma_parse(r)?;
+                        let t4 = Self::sigma_parse(r)?;
+                        SType::STuple(vec![t1, t2, t3, t4].try_into().unwrap())
+                    } else {
+                        // Symmetric pair of primitive types (`(Int, Int)`, `(Byte,Byte)`, etc.)
+                        let t = get_embeddable_type(prim_id)?;
+                        SType::STuple(vec![t.clone(), t].try_into().unwrap())
+                    }
+                }
+                _ => {
+                    return Err(SerializationError::NotImplementedYet(
+                        "parsing type is not yet implemented".to_string(),
+                    ))
+                }
             }
-            _ => {
-                return Err(SerializationError::NotImplementedYet(
-                    "parsing type is not yet implemented".to_string(),
-                ))
+        } else {
+            match c {
+                TypeCode::TUPLE => {
+                    let len = r.get_u8()?;
+                    let mut items = Vec::with_capacity(len as usize);
+                    for _ in 0..len {
+                        items.push(SType::sigma_parse(r)?);
+                    }
+                    SType::STuple(
+                        items
+                            .try_into()
+                            .map_err(|_| SerializationError::TupleItemsOutOfBounds(len as usize))?,
+                    )
+                }
+                _ => todo!(),
             }
         };
         Ok(tpe)
     }
 }
 
+fn get_arg_type<R: SigmaByteRead>(r: &mut R, prim_id: u8) -> Result<SType, SerializationError> {
+    if prim_id == 0 {
+        SType::sigma_parse(r)
+    } else {
+        get_embeddable_type(prim_id)
+    }
+}
+
 #[cfg(test)]
 mod tests {
     use super::*;
@@ -196,6 +344,7 @@ mod tests {
 
         #[test]
         fn ser_roundtrip(v in any::<SType>()) {
+            dbg!(v.clone());
             prop_assert_eq![sigma_serialize_roundtrip(&v), v];
         }
     }
diff --git a/ergo-lib/src/types/stype.rs b/ergo-lib/src/types/stype.rs
index eb761daff..6732a863a 100644
--- a/ergo-lib/src/types/stype.rs
+++ b/ergo-lib/src/types/stype.rs
@@ -1,5 +1,11 @@
 //! SType hierarchy
 
+use std::convert::TryFrom;
+use std::convert::TryInto;
+use std::slice::Iter;
+
+use impl_trait_for_tuples::impl_for_tuples;
+
 use crate::chain::ergo_box::ErgoBox;
 use crate::serialization::types::TypeCode;
 use crate::sigma_protocol::dlog_group::EcPoint;
@@ -45,7 +51,7 @@ pub enum SType {
     /// Collection of elements of the same type
     SColl(Box<SType>),
     /// Tuple (elements can have different types)
-    STup(Vec<SType>),
+    STuple(TupleItems<SType>),
     /// Function (signature)
     SFunc(Box<SFunc>),
     /// Context object ("CONTEXT" in ErgoScript)
@@ -67,9 +73,9 @@ impl SType {
             SType::SSigmaProp => TypeCode::SSIGMAPROP,
             SType::SBox => todo!(),
             SType::SAvlTree => todo!(),
-            SType::SOption(_) => todo!(),
-            SType::SColl(_) => todo!(),
-            SType::STup(_) => todo!(),
+            SType::SOption(_) => TypeCode::OPTION,
+            SType::SColl(_) => TypeCode::COLLECTION,
+            SType::STuple(_) => TypeCode::TUPLE,
             SType::SFunc(_) => todo!(),
             SType::SContext(_) => todo!(),
             SType::STypeVar(_) => todo!(),
@@ -80,10 +86,47 @@ impl SType {
     pub fn type_companion(&self) -> Option<Box<STypeCompanion>> {
         todo!()
     }
+}
 
-    /// Create new SColl with the given element type
-    pub fn new_scoll(elem_type: SType) -> SType {
-        SType::SColl(Box::new(elem_type))
+/// Tuple items with bounds check (2..=255)
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct TupleItems<T>(Vec<T>);
+
+#[allow(clippy::len_without_is_empty)]
+impl<T> TupleItems<T> {
+    // pub fn into_vec(self) -> Vec<T> {
+    //     self.0
+    // }
+
+    /// Get the length (quantity)
+    pub fn len(&self) -> usize {
+        self.0.len()
+    }
+
+    /// Get an iterator
+    pub fn iter(&self) -> Iter<T> {
+        self.0.iter()
+    }
+
+    /// Get a slice
+    pub fn as_slice(&self) -> &[T] {
+        self.0.as_slice()
+    }
+}
+
+/// Out of bounds items quantity error
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct STupleItemsOutOfBoundsError();
+
+impl<T> TryFrom<Vec<T>> for TupleItems<T> {
+    type Error = STupleItemsOutOfBoundsError;
+
+    fn try_from(items: Vec<T>) -> Result<Self, Self::Error> {
+        if items.len() >= 2 && items.len() <= 255 {
+            Ok(TupleItems(items))
+        } else {
+            Err(STupleItemsOutOfBoundsError())
+        }
     }
 }
 
@@ -165,6 +208,20 @@ impl LiftIntoSType for EcPoint {
     }
 }
 
+impl<T: LiftIntoSType> LiftIntoSType for Option<T> {
+    fn stype() -> SType {
+        SType::SOption(Box::new(T::stype()))
+    }
+}
+
+#[impl_for_tuples(2, 4)]
+impl LiftIntoSType for Tuple {
+    fn stype() -> SType {
+        let v: Vec<SType> = [for_tuples!(  #( Tuple::stype() ),* )].to_vec();
+        SType::STuple(v.try_into().unwrap())
+    }
+}
+
 #[cfg(test)]
 mod tests {
     use super::*;
@@ -189,11 +246,21 @@ mod tests {
         type Strategy = BoxedStrategy<Self>;
 
         fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
-            prop_oneof![
-                primitive_type(),
-                primitive_type().prop_map(SType::new_scoll),
-            ]
-            .boxed()
+            primitive_type()
+                .prop_recursive(
+                    4,  // no more than this branches deep
+                    64, // total elements target
+                    16, // each collection max size
+                    |elem| {
+                        prop_oneof![
+                            prop::collection::vec(elem.clone(), 2..=4)
+                                .prop_map(|elems| SType::STuple(elems.try_into().unwrap())),
+                            elem.clone().prop_map(|tpe| SType::SColl(Box::new(tpe))),
+                            elem.prop_map(|tpe| SType::SOption(Box::new(tpe))),
+                        ]
+                    },
+                )
+                .boxed()
         }
     }
 }


Test patch: