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

Issue:
Sigma protocol implementation for And, Or



Discussion / hints:

Fix patch:
diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml
index aad0c4049..c80609799 100644
--- a/.github/workflows/ci.yml
+++ b/.github/workflows/ci.yml
@@ -93,7 +93,7 @@ jobs:
         if: matrix.os == 'ubuntu-latest'
         uses: actions-rs/tarpaulin@master
         with:
-          args: '--timeout=360 -v --out Lcov --exclude-files bindings/*'
+          args: '--avoid-cfg-tarpaulin --timeout=360 -v --out Lcov --exclude-files bindings/*'
       # - name: Upload coverage report to Codecov
       #   if: matrix.os == 'ubuntu-latest'
       #   uses: codecov/codecov-action@v1
diff --git a/ergo-lib/CHANGELOG.md b/ergo-lib/CHANGELOG.md
index 55f901e42..486cfedb3 100644
--- a/ergo-lib/CHANGELOG.md
+++ b/ergo-lib/CHANGELOG.md
@@ -6,6 +6,10 @@ and this project adheres to [Semantic Versioning](http://semver.org/).
 
 <!-- next-header -->
 ## [Unreleased] - ReleaseDate
+
+### Added 
+- AND, OR conjecture support in sigma protocol [#226](https://github.com/ergoplatform/sigma-rust/pull/226);
+
 ## [0.13.1] - 2021-05-28
 
 ### Fixed 
diff --git a/ergo-lib/src/wallet/signing.rs b/ergo-lib/src/wallet/signing.rs
index 56ce949c0..b9a5f5906 100644
--- a/ergo-lib/src/wallet/signing.rs
+++ b/ergo-lib/src/wallet/signing.rs
@@ -1,5 +1,6 @@
 //! Transaction signing
 
+use ergotree_interpreter::sigma_protocol::prover::hint::HintsBag;
 use std::collections::HashMap;
 use std::rc::Rc;
 
@@ -151,6 +152,7 @@ pub fn sign_transaction(
                     &Env::empty(),
                     ctx,
                     message_to_sign.as_slice(),
+                    &HintsBag::empty(),
                 )
                 .map(|proof| {
                     let input = Input::new(input.box_id.clone(), proof.into());
@@ -208,7 +210,7 @@ mod tests {
                 &b.ergo_tree,
                 &Env::empty(),
                 Rc::new(force_any_val::<Context>()),
-                &input.spending_proof.proof,
+                input.spending_proof.proof.clone(),
                 &message,
             )?;
             Ok(res.result && acc)
@@ -346,7 +348,7 @@ mod tests {
             &ergo_tree,
             &Env::empty(),
             Rc::new(force_any_val::<Context>()),
-            &tx.inputs.get(1).unwrap().spending_proof.proof,
+            tx.inputs.get(1).unwrap().spending_proof.proof.clone(),
             message.as_slice(),
         );
         assert_eq!(ver_res.unwrap().result, true);
diff --git a/ergoscript-compiler/src/hir/rewrite.rs b/ergoscript-compiler/src/hir/rewrite.rs
index f1a38fd9c..3d1b4d5dc 100644
--- a/ergoscript-compiler/src/hir/rewrite.rs
+++ b/ergoscript-compiler/src/hir/rewrite.rs
@@ -22,7 +22,7 @@ pub fn rewrite<E, F: Fn(&Expr) -> Result<Option<Expr>, E>>(e: Expr, f: F) -> Res
                 ..e
             },
         },
-        ExprKind::Ident(_) => f(&e)?.unwrap_or(e),
+        ExprKind::Ident(_) => f(&e)?.unwrap_or(e), // TODO: duplicate call to f?
         ExprKind::GlobalVars(_) => f(&e)?.unwrap_or(e),
         ExprKind::Literal(_) => f(&e)?.unwrap_or(e),
     })
diff --git a/ergotree-interpreter/Cargo.toml b/ergotree-interpreter/Cargo.toml
index 306029ceb..69b270d9b 100644
--- a/ergotree-interpreter/Cargo.toml
+++ b/ergotree-interpreter/Cargo.toml
@@ -17,9 +17,10 @@ crate-type = ["cdylib", "rlib"]
 sigma-util = { version = "^0.2.0", path = "../sigma-util" }
 ergotree-ir = { version = "^0.13.0", path = "../ergotree-ir" }
 indexmap = "1.3.2"
-k256 = { version = "0.4.2", features = ["rand", "zeroize"] }
+k256 = { version = "0.7.2", features = ["zeroize", "arithmetic", "ecdsa"] }
+elliptic-curve = {version = "0.9.6", features = [ "zeroize"]}
 blake2 = "0.9"
-elliptic-curve = {version = "0.5.0", features = ["rand", "zeroize"]}
+rand = "0.7"
 lazy_static = "1.4"
 thiserror = "1"
 derive_more = "0.99"
diff --git a/ergotree-interpreter/src/eval.rs b/ergotree-interpreter/src/eval.rs
index d98b90231..459647c41 100644
--- a/ergotree-interpreter/src/eval.rs
+++ b/ergotree-interpreter/src/eval.rs
@@ -66,6 +66,8 @@ pub(crate) mod sbox;
 pub(crate) mod scoll;
 pub(crate) mod scontext;
 pub(crate) mod select_field;
+pub(crate) mod sigma_and;
+pub(crate) mod sigma_or;
 pub(crate) mod sigma_prop_bytes;
 pub(crate) mod tuple;
 pub(crate) mod upcast;
diff --git a/ergotree-interpreter/src/eval/expr.rs b/ergotree-interpreter/src/eval/expr.rs
index c9e2a6505..7603c85c3 100644
--- a/ergotree-interpreter/src/eval/expr.rs
+++ b/ergotree-interpreter/src/eval/expr.rs
@@ -57,8 +57,8 @@ impl Evaluable for Expr {
             Expr::ForAll(op) => op.eval(env, ctx),
             Expr::Tuple(op) => op.eval(env, ctx),
             Expr::DecodePoint(op) => op.eval(env, ctx),
-            Expr::SigmaAnd(_) => todo!(),
-            Expr::SigmaOr(_) => todo!(),
+            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::GetVar(op) => op.eval(env, ctx),
diff --git a/ergotree-interpreter/src/eval/sigma_and.rs b/ergotree-interpreter/src/eval/sigma_and.rs
new file mode 100644
index 000000000..e918c3028
--- /dev/null
+++ b/ergotree-interpreter/src/eval/sigma_and.rs
@@ -0,0 +1,61 @@
+use ergotree_ir::mir::constant::TryExtractInto;
+use ergotree_ir::mir::sigma_and::SigmaAnd;
+use ergotree_ir::mir::value::Value;
+use ergotree_ir::sigma_protocol::sigma_boolean::cand::Cand;
+use ergotree_ir::sigma_protocol::sigma_boolean::SigmaProp;
+
+use crate::eval::env::Env;
+use crate::eval::EvalContext;
+use crate::eval::EvalError;
+use crate::eval::Evaluable;
+
+impl Evaluable for SigmaAnd {
+    fn eval(&self, env: &Env, ctx: &mut EvalContext) -> Result<Value, EvalError> {
+        let items_v_res: Result<Vec<Value>, EvalError> =
+            self.items.iter().map(|arg| arg.eval(env, ctx)).collect();
+        let items_sigmabool = items_v_res?
+            .try_extract_into::<Vec<SigmaProp>>()?
+            .into_iter()
+            .map(|sp| sp.into())
+            .collect();
+        Ok(Value::SigmaProp(Box::new(SigmaProp::new(
+            Cand::normalized(items_sigmabool),
+        ))))
+    }
+}
+
+#[allow(clippy::unwrap_used)]
+#[cfg(test)]
+mod tests {
+    use ergotree_ir::sigma_protocol::sigma_boolean::SigmaBoolean;
+    use ergotree_ir::sigma_protocol::sigma_boolean::SigmaConjecture;
+    use std::rc::Rc;
+
+    use crate::eval::context::Context;
+    use crate::eval::tests::eval_out;
+
+    use super::*;
+
+    use ergotree_ir::mir::expr::Expr;
+    use proptest::collection;
+    use proptest::prelude::*;
+    use sigma_test_util::force_any_val;
+
+    proptest! {
+
+        #![proptest_config(ProptestConfig::with_cases(8))]
+
+        #[test]
+        fn eval(sigmaprops in collection::vec(any::<SigmaProp>(), 2..10)) {
+            let items = sigmaprops.clone().into_iter().map(|sp| Expr::Const(sp.into())).collect();
+            let expr: Expr = SigmaAnd::new(items).unwrap().into();
+            let ctx = Rc::new(force_any_val::<Context>());
+            let res = eval_out::<SigmaProp>(&expr, ctx);
+            let expected_sb: Vec<SigmaBoolean> = sigmaprops.into_iter().map(|sp| sp.into()).collect();
+            prop_assert!(matches!(res.clone().into(), SigmaBoolean::SigmaConjecture(SigmaConjecture::Cand(_))));
+            if let SigmaBoolean::SigmaConjecture(SigmaConjecture::Cand(Cand {items: actual_sb})) = res.into() {
+                prop_assert_eq!(actual_sb, expected_sb);
+            }
+        }
+    }
+}
diff --git a/ergotree-interpreter/src/eval/sigma_or.rs b/ergotree-interpreter/src/eval/sigma_or.rs
new file mode 100644
index 000000000..dfc62c34d
--- /dev/null
+++ b/ergotree-interpreter/src/eval/sigma_or.rs
@@ -0,0 +1,61 @@
+use ergotree_ir::mir::constant::TryExtractInto;
+use ergotree_ir::mir::sigma_or::SigmaOr;
+use ergotree_ir::mir::value::Value;
+use ergotree_ir::sigma_protocol::sigma_boolean::cor::Cor;
+use ergotree_ir::sigma_protocol::sigma_boolean::SigmaProp;
+
+use crate::eval::env::Env;
+use crate::eval::EvalContext;
+use crate::eval::EvalError;
+use crate::eval::Evaluable;
+
+impl Evaluable for SigmaOr {
+    fn eval(&self, env: &Env, ctx: &mut EvalContext) -> Result<Value, EvalError> {
+        let items_v_res: Result<Vec<Value>, EvalError> =
+            self.items.iter().map(|arg| arg.eval(env, ctx)).collect();
+        let items_sigmabool = items_v_res?
+            .try_extract_into::<Vec<SigmaProp>>()?
+            .into_iter()
+            .map(|sp| sp.into())
+            .collect();
+        Ok(Value::SigmaProp(Box::new(SigmaProp::new(Cor::normalized(
+            items_sigmabool,
+        )))))
+    }
+}
+
+#[allow(clippy::unwrap_used)]
+#[cfg(test)]
+mod tests {
+    use ergotree_ir::sigma_protocol::sigma_boolean::SigmaBoolean;
+    use ergotree_ir::sigma_protocol::sigma_boolean::SigmaConjecture;
+    use std::rc::Rc;
+
+    use crate::eval::context::Context;
+    use crate::eval::tests::eval_out;
+
+    use super::*;
+
+    use ergotree_ir::mir::expr::Expr;
+    use proptest::collection;
+    use proptest::prelude::*;
+    use sigma_test_util::force_any_val;
+
+    proptest! {
+
+        #![proptest_config(ProptestConfig::with_cases(8))]
+
+        #[test]
+        fn eval(sigmaprops in collection::vec(any::<SigmaProp>(), 2..10)) {
+            let items = sigmaprops.clone().into_iter().map(|sp| Expr::Const(sp.into())).collect();
+            let expr: Expr = SigmaOr::new(items).unwrap().into();
+            let ctx = Rc::new(force_any_val::<Context>());
+            let res = eval_out::<SigmaProp>(&expr, ctx);
+            let expected_sb: Vec<SigmaBoolean> = sigmaprops.into_iter().map(|sp| sp.into()).collect();
+            prop_assert!(matches!(res.clone().into(), SigmaBoolean::SigmaConjecture(SigmaConjecture::Cor(_))));
+            if let SigmaBoolean::SigmaConjecture(SigmaConjecture::Cor(Cor {items: actual_sb})) = res.into() {
+                prop_assert_eq!(actual_sb, expected_sb);
+            }
+        }
+    }
+}
diff --git a/ergotree-interpreter/src/sigma_protocol.rs b/ergotree-interpreter/src/sigma_protocol.rs
index 961a48ae7..98079e4ad 100644
--- a/ergotree-interpreter/src/sigma_protocol.rs
+++ b/ergotree-interpreter/src/sigma_protocol.rs
@@ -1,12 +1,16 @@
 //! Sigma protocols
 
+#![deny(clippy::unwrap_used)]
+
 pub mod private_input;
 pub mod prover;
 pub mod verifier;
 
 mod challenge;
+mod crypto_utils;
 mod dlog_protocol;
 mod fiat_shamir;
+mod proof_tree;
 mod sig_serializer;
 mod unchecked_tree;
 mod unproven_tree;
@@ -17,17 +21,22 @@ use k256::Scalar;
 use dlog_protocol::FirstDlogProverMessage;
 use std::convert::TryInto;
 use unchecked_tree::{UncheckedSigmaTree, UncheckedTree};
-use unproven_tree::{UnprovenLeaf, UnprovenSchnorr, UnprovenTree};
+use unproven_tree::{UnprovenLeaf, UnprovenSchnorr};
 
 use self::challenge::Challenge;
+use self::unchecked_tree::UncheckedSchnorr;
+
+use derive_more::From;
+use derive_more::TryInto;
 
 /** The message sent by a prover to its associated verifier as part of a sigma protocol interaction. */
-pub trait ProverMessage {
+pub(crate) trait ProverMessage {
     /// serialized message
     fn bytes(&self) -> Vec<u8>;
 }
 
 /** First message from the prover (message `a` of `SigmaProtocol`)*/
+#[derive(PartialEq, Debug, Clone, From, TryInto)]
 pub enum FirstProverMessage {
     /// Discrete log
     FirstDlogProverMessage(FirstDlogProverMessage),
@@ -44,57 +53,14 @@ impl ProverMessage for FirstProverMessage {
     }
 }
 
-/// Proof tree
-pub enum ProofTree {
-    /// Unchecked tree
-    UncheckedTree(UncheckedTree),
-    /// Unproven tree
-    UnprovenTree(UnprovenTree),
-}
-
-impl ProofTree {
-    /// Create a new proof tree with a new challenge
-    pub fn with_challenge(&self, challenge: Challenge) -> ProofTree {
-        match self {
-            ProofTree::UncheckedTree(_) => todo!(),
-            ProofTree::UnprovenTree(ut) => match ut {
-                UnprovenTree::UnprovenLeaf(ul) => match ul {
-                    UnprovenLeaf::UnprovenSchnorr(us) => ProofTree::UnprovenTree(
-                        UnprovenSchnorr {
-                            challenge_opt: Some(challenge),
-                            ..us.clone()
-                        }
-                        .into(),
-                    ),
-                },
-            },
-        }
-    }
-}
-
-impl<T: Into<UncheckedTree>> From<T> for ProofTree {
-    fn from(t: T) -> Self {
-        ProofTree::UncheckedTree(t.into())
-    }
-}
-
-/// Proof tree leaf
-pub trait ProofTreeLeaf {
-    /// Get proposition
-    fn proposition(&self) -> SigmaBoolean;
-
-    /// Get commitment
-    fn commitment_opt(&self) -> Option<FirstProverMessage>;
-}
-
 /** Size of the binary representation of any group element (2 ^ groupSizeBits == <number of elements in a group>) */
-pub const GROUP_SIZE_BITS: usize = 256;
+pub(crate) const GROUP_SIZE_BITS: usize = 256;
 /** Number of bytes to represent any group element as byte array */
-pub const GROUP_SIZE: usize = GROUP_SIZE_BITS / 8;
+pub(crate) const GROUP_SIZE: usize = GROUP_SIZE_BITS / 8;
 
 /// Byte array of Group size (32 bytes)
 #[derive(PartialEq, Eq, Debug, Clone)]
-pub struct GroupSizedBytes(pub Box<[u8; GROUP_SIZE]>);
+pub(crate) struct GroupSizedBytes(pub(crate) Box<[u8; GROUP_SIZE]>);
 
 impl From<GroupSizedBytes> for Scalar {
     fn from(b: GroupSizedBytes) -> Self {
diff --git a/ergotree-interpreter/src/sigma_protocol/challenge.rs b/ergotree-interpreter/src/sigma_protocol/challenge.rs
index f7344d05d..1d036bf30 100644
--- a/ergotree-interpreter/src/sigma_protocol/challenge.rs
+++ b/ergotree-interpreter/src/sigma_protocol/challenge.rs
@@ -1,7 +1,12 @@
 use super::{fiat_shamir::FiatShamirHash, SOUNDNESS_BYTES};
+use ergotree_ir::serialization::sigma_byte_reader::SigmaByteRead;
+use ergotree_ir::serialization::sigma_byte_writer::SigmaByteWrite;
+use ergotree_ir::serialization::SerializationError;
+use ergotree_ir::serialization::SigmaSerializable;
 use k256::Scalar;
 #[cfg(feature = "arbitrary")]
 use proptest_derive::Arbitrary;
+use std::convert::TryFrom;
 use std::convert::TryInto;
 
 /// Challenge in Sigma protocol
@@ -19,6 +24,24 @@ impl From<Challenge> for Scalar {
     }
 }
 
+impl Challenge {
+    pub fn secure_random() -> Self {
+        Self(FiatShamirHash::secure_random())
+    }
+
+    pub fn xor(self, other: Challenge) -> Self {
+        let this: [u8; SOUNDNESS_BYTES] = self.0.into();
+        let that: [u8; SOUNDNESS_BYTES] = other.0.into();
+        let res: Vec<u8> = this
+            .iter()
+            .zip(that.iter())
+            .map(|(&x1, &x2)| x1 ^ x2)
+            .collect();
+        #[allow(clippy::unwrap_used)] // since the size is unchanged
+        FiatShamirHash::try_from(res.as_slice()).unwrap().into()
+    }
+}
+
 impl From<Challenge> for Vec<u8> {
     fn from(v: Challenge) -> Self {
         let arr: [u8; SOUNDNESS_BYTES] = v.0.into();
@@ -31,3 +54,15 @@ impl From<FiatShamirHash> for Challenge {
         Challenge(fsh)
     }
 }
+
+impl SigmaSerializable for Challenge {
+    fn sigma_serialize<W: SigmaByteWrite>(&self, w: &mut W) -> Result<(), std::io::Error> {
+        w.write_all(self.0 .0.as_ref())
+    }
+
+    fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SerializationError> {
+        let mut chal_bytes: [u8; super::SOUNDNESS_BYTES] = [0; super::SOUNDNESS_BYTES];
+        r.read_exact(&mut chal_bytes)?;
+        Ok(Challenge::from(FiatShamirHash(Box::new(chal_bytes))))
+    }
+}
diff --git a/ergotree-interpreter/src/sigma_protocol/crypto_utils.rs b/ergotree-interpreter/src/sigma_protocol/crypto_utils.rs
new file mode 100644
index 000000000..f2c6e7e34
--- /dev/null
+++ b/ergotree-interpreter/src/sigma_protocol/crypto_utils.rs
@@ -0,0 +1,8 @@
+/// Generate cryptographically secure random bytes
+pub fn secure_random_bytes(how_many: usize) -> Vec<u8> {
+    use rand::rngs::OsRng;
+    use rand::RngCore;
+    let mut bytes: Vec<u8> = vec![0; how_many];
+    OsRng.fill_bytes(&mut bytes);
+    bytes
+}
diff --git a/ergotree-interpreter/src/sigma_protocol/dlog_protocol.rs b/ergotree-interpreter/src/sigma_protocol/dlog_protocol.rs
index 89bd997dc..bdefc7266 100644
--- a/ergotree-interpreter/src/sigma_protocol/dlog_protocol.rs
+++ b/ergotree-interpreter/src/sigma_protocol/dlog_protocol.rs
@@ -1,13 +1,13 @@
 //! Discrete logarithm signature protocol
 
-use super::{FirstProverMessage, ProverMessage};
+use super::ProverMessage;
 use ergotree_ir::serialization::SigmaSerializable;
 use ergotree_ir::sigma_protocol::dlog_group::EcPoint;
 use k256::Scalar;
 
 /// First message from the prover (message `a` of `SigmaProtocol`) for discrete logarithm case
 #[derive(PartialEq, Eq, Debug, Clone)]
-pub struct FirstDlogProverMessage(pub EcPoint);
+pub struct FirstDlogProverMessage(pub(crate) EcPoint);
 
 impl From<EcPoint> for FirstDlogProverMessage {
     fn from(ecp: EcPoint) -> Self {
@@ -21,12 +21,6 @@ impl ProverMessage for FirstDlogProverMessage {
     }
 }
 
-impl From<FirstDlogProverMessage> for FirstProverMessage {
-    fn from(v: FirstDlogProverMessage) -> Self {
-        FirstProverMessage::FirstDlogProverMessage(v)
-    }
-}
-
 /// Second message from the prover (message `z` of `SigmaProtocol`) for discrete logarithm case
 #[derive(PartialEq, Debug, Clone)]
 pub struct SecondDlogProverMessage {
@@ -41,7 +35,9 @@ impl From<Scalar> for SecondDlogProverMessage {
 }
 
 /// Interactive prover
-pub mod interactive_prover {
+pub(crate) mod interactive_prover {
+    use std::ops::Mul;
+
     use super::{FirstDlogProverMessage, SecondDlogProverMessage};
     use crate::sigma_protocol::{private_input::DlogProverInput, Challenge};
     use ergotree_ir::sigma_protocol::dlog_group;
@@ -49,16 +45,24 @@ pub mod interactive_prover {
     use ergotree_ir::sigma_protocol::sigma_boolean::ProveDlog;
     use k256::Scalar;
 
-    /// TBD
-    pub fn simulate(
-        _public_input: &ProveDlog,
-        _challenge: &Challenge,
+    pub(crate) fn simulate(
+        public_input: &ProveDlog,
+        challenge: &Challenge,
     ) -> (FirstDlogProverMessage, SecondDlogProverMessage) {
-        todo!()
+        //SAMPLE a random z <- Zq
+        let z = dlog_group::random_scalar_in_group_range();
+
+        //COMPUTE a = g^z*h^(-e)  (where -e here means -e mod q)
+        let e: Scalar = challenge.clone().into();
+        let minus_e = e.negate();
+        let h_to_e = dlog_group::exponentiate(&public_input.h, &minus_e);
+        let g_to_z = dlog_group::exponentiate(&dlog_group::generator(), &z);
+        let a = g_to_z * &h_to_e;
+        (FirstDlogProverMessage(a), SecondDlogProverMessage { z })
     }
 
     /// Create first message from the prover and a randomness
-    pub fn first_message() -> (Scalar, FirstDlogProverMessage) {
+    pub(crate) fn first_message() -> (Scalar, FirstDlogProverMessage) {
         let r = dlog_group::random_scalar_in_group_range();
         let g = dlog_group::generator();
         let a = dlog_group::exponentiate(&g, &r);
@@ -66,7 +70,7 @@ pub mod interactive_prover {
     }
 
     /// Create second message from the prover
-    pub fn second_message(
+    pub(crate) fn second_message(
         private_input: &DlogProverInput,
         rnd: Scalar,
         challenge: &Challenge,
@@ -86,7 +90,7 @@ pub mod interactive_prover {
      *
      * g^z = a*h^e => a = g^z/h^e
      */
-    pub fn compute_commitment(
+    pub(crate) fn compute_commitment(
         proposition: &ProveDlog,
         challenge: &Challenge,
         second_message: &SecondDlogProverMessage,
diff --git a/ergotree-interpreter/src/sigma_protocol/fiat_shamir.rs b/ergotree-interpreter/src/sigma_protocol/fiat_shamir.rs
index 7b874d02d..15dc8e96b 100644
--- a/ergotree-interpreter/src/sigma_protocol/fiat_shamir.rs
+++ b/ergotree-interpreter/src/sigma_protocol/fiat_shamir.rs
@@ -1,14 +1,14 @@
 //! Fiat-Shamir transformation
 
-use super::{
-    unchecked_tree::{UncheckedSigmaTree, UncheckedTree},
-    unproven_tree::UnprovenTree,
-    ProofTree, ProofTreeLeaf, ProverMessage, GROUP_SIZE, SOUNDNESS_BYTES,
-};
+use super::crypto_utils::secure_random_bytes;
+use super::proof_tree::ProofTreeKind;
+use crate::sigma_protocol::ProverMessage;
 use blake2::digest::{Update, VariableOutput};
 use blake2::VarBlake2b;
 use ergotree_ir::ergo_tree::ErgoTree;
 use ergotree_ir::mir::expr::Expr;
+use ergotree_ir::serialization::sigma_byte_writer::SigmaByteWrite;
+use ergotree_ir::serialization::sigma_byte_writer::SigmaByteWriter;
 use ergotree_ir::serialization::SigmaSerializable;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaProp;
 use std::convert::{TryFrom, TryInto};
@@ -17,19 +17,35 @@ use thiserror::Error;
 #[cfg(feature = "arbitrary")]
 use proptest_derive::Arbitrary;
 
+use super::proof_tree::ProofTree;
+use super::GROUP_SIZE;
+use super::SOUNDNESS_BYTES;
+
 /// Hash type for Fiat-Shamir hash function (24-bytes)
 #[cfg_attr(feature = "arbitrary", derive(Arbitrary))]
 #[derive(PartialEq, Eq, Debug, Clone)]
 pub struct FiatShamirHash(pub Box<[u8; SOUNDNESS_BYTES]>);
 
+impl FiatShamirHash {
+    pub fn secure_random() -> Self {
+        #[allow(clippy::unwrap_used)] // since we set the correct size
+        secure_random_bytes(SOUNDNESS_BYTES)
+            .as_slice()
+            .try_into()
+            .unwrap()
+    }
+}
+
 /// Fiat-Shamir hash function
 pub fn fiat_shamir_hash_fn(input: &[u8]) -> FiatShamirHash {
     // unwrap is safe, since 32 bytes is a valid hash size (<= 512 && 24 % 8 == 0)
+    #[allow(clippy::unwrap_used)]
     let mut hasher = VarBlake2b::new(GROUP_SIZE).unwrap();
     hasher.update(input);
     let hash = hasher.finalize_boxed();
     let taken: Vec<u8> = hash.to_vec().into_iter().take(SOUNDNESS_BYTES).collect();
     // unwrap is safe due to hash size is expected to be SOUNDNESS_BYTES
+    #[allow(clippy::unwrap_used)]
     FiatShamirHash(taken.into_boxed_slice().try_into().unwrap())
 }
 
@@ -64,32 +80,56 @@ impl From<std::array::TryFromSliceError> for FiatShamirHashError {
 ///  For each leaf node, the string should contain the Sigma-protocol statement being proven and the commitment.
 ///  The string should not contain information on whether a node is marked "real" or "simulated",
 ///  and should not contain challenges, responses, or the real/simulated flag for any node.
-pub fn fiat_shamir_tree_to_bytes(tree: &ProofTree) -> Vec<u8> {
-    const LEAF_PREFIX: u8 = 1;
+pub(crate) fn fiat_shamir_tree_to_bytes(
+    tree: &ProofTree,
+) -> Result<Vec<u8>, FiatShamirTreeSerializationError> {
+    let mut data = Vec::new();
+    let mut w = SigmaByteWriter::new(&mut data, None);
+    fiat_shamir_write_bytes(tree, &mut w)?;
+    Ok(data)
+}
 
-    let leaf: &dyn ProofTreeLeaf = match tree {
-        ProofTree::UncheckedTree(UncheckedTree::UncheckedSigmaTree(
-            UncheckedSigmaTree::UncheckedLeaf(ul),
-        )) => ul,
-        ProofTree::UnprovenTree(UnprovenTree::UnprovenLeaf(ul)) => ul,
-        _ => todo!(),
-    };
+#[derive(Error, PartialEq, Eq, Debug, Clone)]
+#[error("FiatShamirTreeSerializationError: {0}")]
+pub struct FiatShamirTreeSerializationError(String);
+
+impl From<std::io::Error> for FiatShamirTreeSerializationError {
+    fn from(error: std::io::Error) -> Self {
+        FiatShamirTreeSerializationError(error.to_string())
+    }
+}
+
+fn fiat_shamir_write_bytes<W: SigmaByteWrite>(
+    tree: &ProofTree,
+    w: &mut W,
+) -> Result<(), FiatShamirTreeSerializationError> {
+    const INTERNAL_NODE_PREFIX: u8 = 0;
+    const LEAF_PREFIX: u8 = 1;
 
-    let prop_tree =
-        ErgoTree::with_segregation(&Expr::Const(SigmaProp::new(leaf.proposition()).into()));
-    let mut prop_bytes = prop_tree.sigma_serialize_bytes();
-    // TODO: is unwrap safe here? Create new type with non-optional commitment? Decide when other scenarios
-    // are implemented (leafs and trees)
-    let mut commitment_bytes = leaf.commitment_opt().unwrap().bytes();
-    let mut res = vec![LEAF_PREFIX];
-    res.append((prop_bytes.len() as u16).to_be_bytes().to_vec().as_mut());
-    res.append(prop_bytes.as_mut());
-    res.append(
-        (commitment_bytes.len() as u16)
-            .to_be_bytes()
-            .to_vec()
-            .as_mut(),
-    );
-    res.append(commitment_bytes.as_mut());
-    res
+    Ok(match tree.as_tree_kind() {
+        ProofTreeKind::Leaf(leaf) => {
+            let prop_tree =
+                ErgoTree::with_segregation(&Expr::Const(SigmaProp::new(leaf.proposition()).into()));
+            let prop_bytes = prop_tree.sigma_serialize_bytes();
+            let commitment_bytes = leaf
+                .commitment_opt()
+                .ok_or_else(|| {
+                    FiatShamirTreeSerializationError(format!("empty commitment in {:?}", leaf))
+                })?
+                .bytes();
+            w.put_u8(LEAF_PREFIX)?;
+            w.put_i16_be_bytes(prop_bytes.len() as i16)?;
+            w.write_all(prop_bytes.as_ref())?;
+            w.put_i16_be_bytes(commitment_bytes.len() as i16)?;
+            w.write_all(commitment_bytes.as_slice())?
+        }
+        ProofTreeKind::Conjecture(c) => {
+            w.put_u8(INTERNAL_NODE_PREFIX)?;
+            w.put_u8(c.conjecture_type() as u8)?;
+            w.put_i16_be_bytes(c.children().len() as i16)?;
+            for child in c.children() {
+                fiat_shamir_write_bytes(&child, w)?;
+            }
+        }
+    })
 }
diff --git a/ergotree-interpreter/src/sigma_protocol/private_input.rs b/ergotree-interpreter/src/sigma_protocol/private_input.rs
index a99539f07..ce2fbafa9 100644
--- a/ergotree-interpreter/src/sigma_protocol/private_input.rs
+++ b/ergotree-interpreter/src/sigma_protocol/private_input.rs
@@ -1,10 +1,15 @@
 //! Private input types for the prover's secrets
-use elliptic_curve::FromBytes;
+use std::convert::TryInto;
+
 use ergotree_ir::sigma_protocol::dlog_group;
 use ergotree_ir::sigma_protocol::sigma_boolean::ProveDlog;
+
+use k256::elliptic_curve::ff::PrimeField;
 use k256::Scalar;
 
-use crate::util::IntoOption;
+extern crate derive_more;
+use derive_more::From;
+use num_bigint::BigUint;
 
 /// Secret key of discrete logarithm signature protocol
 #[derive(PartialEq, Debug, Clone)]
@@ -25,12 +30,31 @@ impl DlogProverInput {
     }
 
     /// Attempts to parse the given byte array as an SEC-1-encoded scalar(secret key).
-    /// Returns None if the byte array does not contain a big-endian integer in the range
-    /// [0, modulus).
+    /// Returns None if the byte array does not contain a big-endian integer in the range [0, modulus).
     pub fn from_bytes(bytes: &[u8; DlogProverInput::SIZE_BYTES]) -> Option<DlogProverInput> {
-        Scalar::from_bytes(bytes.into())
-            .into_option()
-            .map(DlogProverInput::from)
+        Scalar::from_repr(bytes.clone().into()).map(DlogProverInput::from)
+    }
+
+    /// Attempts to parse the given Base16-encoded byte array as an SEC-1-encoded scalar(secret key).
+    /// Returns None if the byte array does not contain a big-endian integer in the range [0, modulus).
+    pub fn from_base16_str(str: String) -> Option<DlogProverInput> {
+        base16::decode(&str)
+            .ok()
+            .map(|bytes| bytes.as_slice().try_into().ok().map(Self::from_bytes))
+            .flatten()
+            .flatten()
+    }
+
+    /// Attempts to create DlogProverInput from BigUint
+    /// Returns None if not in the range [0, modulus).
+    pub fn from_biguint(b: BigUint) -> Option<DlogProverInput> {
+        let bytes = b.to_bytes_be();
+        bytes
+            .as_slice()
+            .try_into()
+            .ok()
+            .map(Self::from_bytes)
+            .flatten()
     }
 
     /// byte representation of the underlying scalar
@@ -53,6 +77,7 @@ impl From<Scalar> for DlogProverInput {
 }
 
 /// Private inputs (secrets)
+#[derive(PartialEq, Debug, Clone, From)]
 pub enum PrivateInput {
     /// Discrete logarithm prover input
     DlogProverInput(DlogProverInput),
diff --git a/ergotree-interpreter/src/sigma_protocol/proof_tree.rs b/ergotree-interpreter/src/sigma_protocol/proof_tree.rs
new file mode 100644
index 000000000..c9871c5ae
--- /dev/null
+++ b/ergotree-interpreter/src/sigma_protocol/proof_tree.rs
@@ -0,0 +1,240 @@
+extern crate derive_more;
+
+use std::fmt::Debug;
+
+use derive_more::From;
+use derive_more::TryInto;
+use ergotree_ir::sigma_protocol::sigma_boolean::SigmaBoolean;
+
+use crate::sigma_protocol::unproven_tree::CandUnproven;
+use crate::sigma_protocol::unproven_tree::UnprovenConjecture;
+use crate::sigma_protocol::UncheckedSchnorr;
+use crate::sigma_protocol::UnprovenSchnorr;
+
+use super::challenge::Challenge;
+use super::prover::ProverError;
+use super::unchecked_tree::UncheckedConjecture;
+use super::unchecked_tree::UncheckedSigmaTree;
+use super::unchecked_tree::UncheckedTree;
+use super::unproven_tree::CorUnproven;
+use super::unproven_tree::NodePosition;
+use super::unproven_tree::UnprovenLeaf;
+use super::unproven_tree::UnprovenTree;
+use super::FirstProverMessage;
+
+/// Proof tree
+#[derive(PartialEq, Debug, Clone, From, TryInto)]
+pub(crate) enum ProofTree {
+    /// Unchecked tree
+    UncheckedTree(UncheckedTree),
+    /// Unproven tree
+    UnprovenTree(UnprovenTree),
+}
+
+impl ProofTree {
+    /// Create a new proof tree with a new challenge
+    pub(crate) fn with_challenge(&self, challenge: Challenge) -> ProofTree {
+        match self {
+            ProofTree::UncheckedTree(_) => todo!(),
+            ProofTree::UnprovenTree(ut) => ut.clone().with_challenge(challenge).into(),
+        }
+    }
+
+    pub(crate) fn with_position(&self, updated: NodePosition) -> Self {
+        match self {
+            ProofTree::UncheckedTree(_) => todo!(),
+            ProofTree::UnprovenTree(ut) => ut.clone().with_position(updated).into(),
+        }
+    }
+
+    pub(crate) fn as_tree_kind(&self) -> ProofTreeKind {
+        match self {
+            ProofTree::UncheckedTree(unch) => unch.as_tree_kind(),
+            ProofTree::UnprovenTree(unp) => unp.as_tree_kind(),
+        }
+    }
+
+    #[allow(dead_code)]
+    pub(crate) fn position(&self) -> &NodePosition {
+        match self {
+            ProofTree::UncheckedTree(_) => todo!(),
+            ProofTree::UnprovenTree(unp) => unp.position(),
+        }
+    }
+
+    pub(crate) fn challenge(&self) -> Option<Challenge> {
+        match self {
+            ProofTree::UncheckedTree(unch) => unch.challenge(),
+            ProofTree::UnprovenTree(unp) => unp.challenge(),
+        }
+    }
+}
+
+impl From<UncheckedSchnorr> for ProofTree {
+    fn from(v: UncheckedSchnorr) -> Self {
+        UncheckedTree::UncheckedSigmaTree(v.into()).into()
+    }
+}
+
+impl From<UnprovenSchnorr> for ProofTree {
+    fn from(v: UnprovenSchnorr) -> Self {
+        UnprovenTree::UnprovenLeaf(v.into()).into()
+    }
+}
+
+impl From<CandUnproven> for ProofTree {
+    fn from(v: CandUnproven) -> Self {
+        UnprovenTree::UnprovenConjecture(v.into()).into()
+    }
+}
+
+impl From<CorUnproven> for ProofTree {
+    fn from(v: CorUnproven) -> Self {
+        UnprovenTree::UnprovenConjecture(v.into()).into()
+    }
+}
+
+impl From<UnprovenConjecture> for ProofTree {
+    fn from(v: UnprovenConjecture) -> Self {
+        UnprovenTree::UnprovenConjecture(v).into()
+    }
+}
+
+impl From<UnprovenLeaf> for ProofTree {
+    fn from(v: UnprovenLeaf) -> Self {
+        UnprovenTree::UnprovenLeaf(v).into()
+    }
+}
+
+impl From<UncheckedSigmaTree> for ProofTree {
+    fn from(ust: UncheckedSigmaTree) -> Self {
+        ProofTree::UncheckedTree(UncheckedTree::UncheckedSigmaTree(ust))
+    }
+}
+
+impl From<UncheckedConjecture> for ProofTree {
+    fn from(v: UncheckedConjecture) -> Self {
+        UncheckedTree::UncheckedSigmaTree(v.into()).into()
+    }
+}
+
+/// Proof tree leaf
+pub(crate) trait ProofTreeLeaf: Debug {
+    /// Get proposition
+    fn proposition(&self) -> SigmaBoolean;
+
+    /// Get commitment
+    fn commitment_opt(&self) -> Option<FirstProverMessage>;
+}
+
+pub(crate) enum ConjectureType {
+    And = 0,
+    Or = 1,
+    // Threshold = 2,
+}
+
+pub(crate) trait ProofTreeConjecture {
+    fn conjecture_type(&self) -> ConjectureType;
+    fn children(&self) -> Vec<ProofTree>;
+}
+
+pub(crate) enum ProofTreeKind<'a> {
+    Leaf(&'a dyn ProofTreeLeaf),
+    Conjecture(&'a dyn ProofTreeConjecture),
+}
+
+/// Traverses the tree in the top-down manner, calling `f` for every node/leaf and setting
+/// it's returned value (if `Some`) as new node/leaf or do nothing if it's returned `None`
+pub(crate) fn rewrite<F>(tree: ProofTree, f: &F) -> Result<ProofTree, ProverError>
+where
+    F: Fn(&ProofTree) -> Result<Option<ProofTree>, ProverError>,
+{
+    let cast_to_ust = |children: Vec<ProofTree>| {
+        children
+            .into_iter()
+            .map(|c| {
+                if let ProofTree::UncheckedTree(UncheckedTree::UncheckedSigmaTree(ust)) = c {
+                    Ok(ust)
+                } else {
+                    Err(ProverError::Unexpected(format!(
+                        "rewrite: expected UncheckedSigmaTree got: {:?}",
+                        c
+                    )))
+                }
+            })
+            .collect::<Result<Vec<UncheckedSigmaTree>, _>>()
+    };
+
+    let rewritten_tree = f(&tree)?.unwrap_or(tree);
+    Ok(match &rewritten_tree {
+        ProofTree::UnprovenTree(unp_tree) => match unp_tree {
+            UnprovenTree::UnprovenLeaf(_) => rewritten_tree,
+            UnprovenTree::UnprovenConjecture(conj) => match conj {
+                UnprovenConjecture::CandUnproven(cand) => UnprovenTree::UnprovenConjecture(
+                    UnprovenConjecture::CandUnproven(CandUnproven {
+                        children: cand
+                            .children
+                            .clone()
+                            .into_iter()
+                            .map(|c| rewrite(c, f))
+                            .collect::<Result<Vec<ProofTree>, _>>()?,
+                        ..cand.clone()
+                    }),
+                )
+                .into(),
+                UnprovenConjecture::CorUnproven(cor) => {
+                    UnprovenTree::UnprovenConjecture(UnprovenConjecture::CorUnproven(CorUnproven {
+                        children: cor
+                            .children
+                            .clone()
+                            .into_iter()
+                            .map(|c| rewrite(c, f))
+                            .collect::<Result<Vec<ProofTree>, _>>()?,
+                        ..cor.clone()
+                    }))
+                    .into()
+                }
+            },
+        },
+        ProofTree::UncheckedTree(unch_tree) => match unch_tree {
+            UncheckedTree::NoProof => rewritten_tree,
+            UncheckedTree::UncheckedSigmaTree(ust) => match ust {
+                UncheckedSigmaTree::UncheckedLeaf(_) => rewritten_tree,
+                UncheckedSigmaTree::UncheckedConjecture(conj) => match conj {
+                    UncheckedConjecture::CandUnchecked {
+                        challenge,
+                        children,
+                    } => {
+                        let rewritten_children = children
+                            .clone()
+                            .into_iter()
+                            .map(|c| rewrite(c.into(), f))
+                            .collect::<Result<Vec<ProofTree>, _>>()?;
+                        let casted_children = cast_to_ust(rewritten_children)?;
+                        UncheckedConjecture::CandUnchecked {
+                            children: casted_children,
+                            challenge: challenge.clone(),
+                        }
+                        .into()
+                    }
+                    UncheckedConjecture::CorUnchecked {
+                        challenge,
+                        children,
+                    } => {
+                        let rewritten_children = children
+                            .clone()
+                            .into_iter()
+                            .map(|c| rewrite(c.into(), f))
+                            .collect::<Result<Vec<ProofTree>, _>>()?;
+                        let casted_children = cast_to_ust(rewritten_children)?;
+                        UncheckedConjecture::CorUnchecked {
+                            children: casted_children,
+                            challenge: challenge.clone(),
+                        }
+                        .into()
+                    }
+                },
+            },
+        },
+    })
+}
diff --git a/ergotree-interpreter/src/sigma_protocol/prover.rs b/ergotree-interpreter/src/sigma_protocol/prover.rs
index 564345023..23acc1148 100644
--- a/ergotree-interpreter/src/sigma_protocol/prover.rs
+++ b/ergotree-interpreter/src/sigma_protocol/prover.rs
@@ -3,30 +3,53 @@
 mod context_extension;
 mod prover_result;
 
+pub mod hint;
+
+use crate::sigma_protocol::fiat_shamir::fiat_shamir_hash_fn;
+use crate::sigma_protocol::fiat_shamir::fiat_shamir_tree_to_bytes;
+use crate::sigma_protocol::proof_tree::ProofTree;
+use crate::sigma_protocol::unchecked_tree::UncheckedLeaf;
+use crate::sigma_protocol::unproven_tree::CandUnproven;
+use crate::sigma_protocol::unproven_tree::CorUnproven;
+use crate::sigma_protocol::unproven_tree::NodePosition;
+use crate::sigma_protocol::Challenge;
+use crate::sigma_protocol::UncheckedSigmaTree;
+use crate::sigma_protocol::UnprovenLeaf;
+use ergotree_ir::sigma_protocol::sigma_boolean::SigmaBoolean;
+use std::convert::TryInto;
 use std::rc::Rc;
 
 pub use context_extension::*;
 use ergotree_ir::ergo_tree::ErgoTree;
 use ergotree_ir::ergo_tree::ErgoTreeParsingError;
+use ergotree_ir::sigma_protocol::sigma_boolean::SigmaConjecture;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaProofOfKnowledgeTree;
 pub use prover_result::*;
 
-use super::{
-    dlog_protocol,
-    fiat_shamir::{fiat_shamir_hash_fn, fiat_shamir_tree_to_bytes},
-    private_input::PrivateInput,
-    sig_serializer::serialize_sig,
-    unchecked_tree::UncheckedSchnorr,
-    Challenge, ProofTree, SigmaBoolean, UncheckedSigmaTree, UncheckedTree, UnprovenLeaf,
-    UnprovenSchnorr, UnprovenTree,
-};
+use self::hint::HintsBag;
+
+use super::dlog_protocol;
+use super::fiat_shamir::FiatShamirTreeSerializationError;
+use super::private_input::PrivateInput;
+use super::proof_tree;
+use super::proof_tree::ProofTreeLeaf;
+use super::sig_serializer::serialize_sig;
+use super::unchecked_tree::UncheckedConjecture;
+use super::unchecked_tree::UncheckedSchnorr;
+use super::unchecked_tree::UncheckedTree;
+use super::unproven_tree::UnprovenConjecture;
+use super::unproven_tree::UnprovenSchnorr;
+use super::unproven_tree::UnprovenTree;
+
 use crate::eval::context::Context;
 use crate::eval::env::Env;
 use crate::eval::{EvalError, Evaluator};
+
+use derive_more::From;
 use thiserror::Error;
 
 /// Prover errors
-#[derive(Error, PartialEq, Eq, Debug, Clone)]
+#[derive(Error, PartialEq, Eq, Debug, Clone, From)]
 pub enum ProverError {
     /// Failed to parse ErgoTree
     #[error("Ergo tree error: {0}")]
@@ -49,12 +72,12 @@ pub enum ProverError {
     /// Cannot find a secret for "real" unproven leaf
     #[error("Cannot find a secret for \"real\" unproven leaf")]
     SecretNotFound,
-}
-
-impl From<ErgoTreeParsingError> for ProverError {
-    fn from(err: ErgoTreeParsingError) -> Self {
-        ProverError::ErgoTreeError(err)
-    }
+    /// Unexpected value encountered
+    #[error("Unexpected: {0}")]
+    Unexpected(String),
+    /// Error while tree serialization for Fiat-Shamir hash
+    #[error("Fiat-Shamir tree serialization error: {0}")]
+    FiatShamirTreeSerializationError(FiatShamirTreeSerializationError),
 }
 
 /// Prover
@@ -75,6 +98,7 @@ pub trait Prover: Evaluator {
         env: &Env,
         ctx: Rc<Context>,
         message: &[u8],
+        hints_bag: &HintsBag,
     ) -> Result<ProverResult, ProverError> {
         let expr = tree.proposition()?;
         let proof = self
@@ -85,7 +109,7 @@ pub trait Prover: Evaluator {
                 SigmaBoolean::TrivialProp(false) => Err(ProverError::ReducedToFalse),
                 sb => {
                     let tree = convert_to_unproven(sb);
-                    let unchecked_tree = self.prove_to_unchecked(tree, message)?;
+                    let unchecked_tree = prove_to_unchecked(self, tree, message, hints_bag)?;
                     Ok(UncheckedTree::UncheckedSigmaTree(unchecked_tree))
                 }
             });
@@ -94,186 +118,586 @@ pub trait Prover: Evaluator {
             extension: ContextExtension::empty(),
         })
     }
+}
 
-    /// The comments in this section are taken from the algorithm for the
-    /// Sigma-protocol prover as described in the white paper
-    /// https://ergoplatform.org/docs/ErgoScript.pdf (Appendix A)
-    fn prove_to_unchecked(
-        &self,
-        unproven_tree: UnprovenTree,
-        message: &[u8],
-    ) -> Result<UncheckedSigmaTree, ProverError> {
-        // Prover Step 1: Mark as real everything the prover can prove
-        let step1 = self.mark_real(unproven_tree);
-
-        // Prover Step 2: If the root of the tree is marked "simulated" then the prover does not have enough witnesses
-        // to perform the proof. Abort.
-        if !step1.is_real() {
-            return Err(ProverError::TreeRootIsNotReal);
-        }
+/// The comments in this section are taken from the algorithm for the
+/// Sigma-protocol prover as described in the white paper
+/// https://ergoplatform.org/docs/ErgoScript.pdf (Appendix A)
+// if we are concerned about timing attacks against the prover, we should make sure that this code
+//  takes the same amount of time regardless of which nodes are real and which nodes are simulated
+//  In particular, we should avoid the use of exists and forall, because they short-circuit the evaluation
+//  once the right value is (or is not) found. We should also make all loops look similar, the same
+//  amount of copying is done regardless of what's real or simulated,
+//  real vs. simulated computations take the same time, etc.
+fn prove_to_unchecked<P: Prover + ?Sized>(
+    prover: &P,
+    unproven_tree: UnprovenTree,
+    message: &[u8],
+    hints_bag: &HintsBag,
+) -> Result<UncheckedSigmaTree, ProverError> {
+    // Prover Step 1: Mark as real everything the prover can prove
+    let step1 = mark_real(prover, unproven_tree, hints_bag)?;
+    dbg!(&step1);
 
-        // Prover Step 3: Change some "real" nodes to "simulated" to make sure each node
-        // has the right number of simulated children.
+    // Prover Step 2: If the root of the tree is marked "simulated" then the prover does not have enough witnesses
+    // to perform the proof. Abort.
+    if !step1.is_real() {
+        return Err(ProverError::TreeRootIsNotReal);
+    }
 
-        // skipped, since it leaves UnprovenSchnorr untouched
-        // let step3 = self.polish_simulated(step1);
+    // Prover Step 3: Change some "real" nodes to "simulated" to make sure each node
+    // has the right number of simulated children.
 
-        // Prover Steps 4, 5, and 6 together: find challenges for simulated nodes; simulate simulated leaves;
-        // compute commitments for real leaves
-        let step6 = self.simulate_and_commit(step1)?;
+    let step3 = polish_simulated(prover, step1)?;
+    dbg!(&step3);
 
-        // Prover Steps 7: convert the relevant information in the tree (namely, tree structure, node types,
-        // the statements being proven and commitments at the leaves)
-        // to a string
-        let var_name = fiat_shamir_tree_to_bytes(&step6);
-        let mut s = var_name;
+    // Prover Steps 4, 5, and 6 together: find challenges for simulated nodes; simulate simulated leaves;
+    // compute commitments for real leaves
+    let step6 = simulate_and_commit(step3, hints_bag)?;
+    dbg!(&step6);
 
-        // Prover Step 8: compute the challenge for the root of the tree as the Fiat-Shamir hash of s
-        // and the message being signed.
-        s.append(&mut message.to_vec());
-        let root_challenge: Challenge = fiat_shamir_hash_fn(s.as_slice()).into();
-        let step8 = step6.with_challenge(root_challenge);
+    // Prover Steps 7: convert the relevant information in the tree (namely, tree structure, node types,
+    // the statements being proven and commitments at the leaves)
+    // to a string
+    let var_name = fiat_shamir_tree_to_bytes(&step6.clone().into())?;
+    let mut s = var_name;
 
-        // Prover Step 9: complete the proof by computing challenges at real nodes and additionally responses at real leaves
-        let step9 = self.proving(step8)?;
+    // Prover Step 8: compute the challenge for the root of the tree as the Fiat-Shamir hash of s
+    // and the message being signed.
+    s.append(&mut message.to_vec());
+    let root_challenge: Challenge = fiat_shamir_hash_fn(s.as_slice()).into();
+    let step8 = step6.with_challenge(root_challenge);
+    dbg!(&step8);
 
-        // Prover Step 10: output the right information into the proof
-        match step9 {
-            ProofTree::UncheckedTree(UncheckedTree::UncheckedSigmaTree(tree)) => Ok(tree),
-            _ => todo!(),
-        }
+    // Prover Step 9: complete the proof by computing challenges at real nodes and additionally responses at real leaves
+    let step9 = proving(prover, step8.into(), hints_bag)?;
+    dbg!(&step9);
+    // Prover Step 10: output the right information into the proof
+    convert_to_unchecked(step9)
+}
+
+/**
+ Prover Step 1: This step will mark as "real" every node for which the prover can produce a real proof.
+ This step may mark as "real" more nodes than necessary if the prover has more than the minimal
+ necessary number of witnesses (for example, more than one child of an OR).
+ This will be corrected in the next step.
+ In a bottom-up traversal of the tree, do the following for each node:
+*/
+fn mark_real<P: Prover + ?Sized>(
+    prover: &P,
+    unproven_tree: UnprovenTree,
+    hints_bag: &HintsBag,
+) -> Result<UnprovenTree, ProverError> {
+    proof_tree::rewrite(unproven_tree.into(), &|tree| {
+        Ok(match tree {
+            ProofTree::UnprovenTree(unp) => match unp {
+                UnprovenTree::UnprovenLeaf(unp_leaf) => match unp_leaf {
+                    UnprovenLeaf::UnprovenSchnorr(us) => {
+                        // If the node is a leaf, mark it "real'' if either the witness for it is
+                        // available or a hint shows the secret is known to an external participant in multi-signing;
+                        // else mark it "simulated"
+                        let secret_known =
+                            hints_bag.real_images().contains(&unp_leaf.proposition())
+                                || prover.secrets().iter().any(|s| match s {
+                                    PrivateInput::DlogProverInput(dl) => {
+                                        dl.public_image() == us.proposition
+                                    }
+                                    _ => false,
+                                });
+                        Some(
+                            UnprovenSchnorr {
+                                simulated: !secret_known,
+                                ..us.clone()
+                            }
+                            .into(),
+                        )
+                    }
+                },
+                UnprovenTree::UnprovenConjecture(unp_conj) => match unp_conj {
+                    UnprovenConjecture::CandUnproven(cand) => {
+                        // If the node is AND, mark it "real" if all of its children are marked real; else mark it "simulated"
+                        let simulated = cast_to_unp(cand.children.clone())?
+                            .into_iter()
+                            .any(|c| c.simulated());
+                        Some(
+                            CandUnproven {
+                                simulated,
+                                ..cand.clone()
+                            }
+                            .into(),
+                        )
+                    }
+                    UnprovenConjecture::CorUnproven(cor) => {
+                        // If the node is OR, mark it "real" if at least one child is marked real; else mark it "simulated"
+                        let simulated = cast_to_unp(cor.children.clone())?
+                            .into_iter()
+                            .all(|c| c.simulated());
+                        Some(
+                            CorUnproven {
+                                simulated,
+                                ..cor.clone()
+                            }
+                            .into(),
+                        )
+                    }
+                },
+            },
+            ProofTree::UncheckedTree(_) => None,
+        })
+    })?
+    .try_into()
+    .map_err(|e: &str| ProverError::Unexpected(e.to_string()))
+}
+
+/// Set positions for children of a unproven inner node (conjecture, so AND/OR/THRESHOLD)
+fn set_positions(uc: UnprovenConjecture) -> UnprovenConjecture {
+    let upd_children: Vec<ProofTree> = uc
+        .children()
+        .into_iter()
+        .enumerate()
+        .map(|(idx, utree)| utree.with_position(uc.position().child(idx)))
+        .collect();
+    match uc {
+        UnprovenConjecture::CandUnproven(cand) => cand.with_children(upd_children).into(),
+        UnprovenConjecture::CorUnproven(cor) => cor.with_children(upd_children).into(),
     }
+}
 
-    /**
-     Prover Step 1: This step will mark as "real" every node for which the prover can produce a real proof.
-     This step may mark as "real" more nodes than necessary if the prover has more than the minimal
-     necessary number of witnesses (for example, more than one child of an OR).
-     This will be corrected in the next step.
-     In a bottom-up traversal of the tree, do the following for each node:
-    */
-    fn mark_real(&self, unproven_tree: UnprovenTree) -> UnprovenTree {
-        match unproven_tree {
-            UnprovenTree::UnprovenLeaf(UnprovenLeaf::UnprovenSchnorr(us)) => {
-                let secret_known = self.secrets().iter().any(|s| match s {
-                    PrivateInput::DlogProverInput(dl) => dl.public_image() == us.proposition,
-                    _ => false,
-                });
-                UnprovenSchnorr {
-                    simulated: !secret_known,
-                    ..us
-                }
-                .into()
+/// If the node is OR marked "real",  mark all but one of its children "simulated"
+/// (the node is guaranteed by step 1 to have at least one "real" child).
+/// Which particular child is left "real" is not important for security;
+/// the choice can be guided by efficiency or convenience considerations.
+fn make_cor_children_simulated(cor: CorUnproven) -> Result<CorUnproven, ProverError> {
+    let casted_children = cast_to_unp(cor.children)?;
+    let first_real_child = casted_children
+        .iter()
+        .find(|it| it.is_real())
+        .ok_or_else(|| {
+            ProverError::Unexpected(format!(
+                "make_cor_children_simulated: no real child is found amoung: {:?}",
+                casted_children
+            ))
+        })?;
+    let children = casted_children
+        .clone()
+        .into_iter()
+        .map(|c| {
+            if &c == first_real_child || c.simulated() {
+                c
+            } else {
+                c.with_simulated(true)
             }
-        }
-    }
+        })
+        .map(|c| c.into())
+        .collect();
+    Ok(CorUnproven { children, ..cor })
+}
 
-    /**
-     Prover Step 3: This step will change some "real" nodes to "simulated" to make sure each node has
-     the right number of simulated children.
-     In a top-down traversal of the tree, do the following for each node:
-    */
-    fn polish_simulated(&self, _unproven_tree: UnprovenTree) -> UnprovenTree {
-        todo!()
-    }
+fn cast_to_unp(children: Vec<ProofTree>) -> Result<Vec<UnprovenTree>, ProverError> {
+    children
+        .into_iter()
+        .map(|c| {
+            if let ProofTree::UnprovenTree(ut) = c {
+                Ok(ut)
+            } else {
+                Err(ProverError::Unexpected(format!(
+                    "make_cor_children_simulated: expected UnprovenTree got: {:?}",
+                    c
+                )))
+            }
+        })
+        .collect()
+}
 
-    /**
-     Prover Step 4: In a top-down traversal of the tree, compute the challenges e for simulated children of every node
-     Prover Step 5: For every leaf marked "simulated", use the simulator of the Sigma-protocol for that leaf
-     to compute the commitment $a$ and the response z, given the challenge e that is already stored in the leaf.
-     Prover Step 6: For every leaf marked "real", use the first prover step of the Sigma-protocol for that leaf to
-     compute the commitment a.
-    */
-    fn simulate_and_commit(&self, tree: UnprovenTree) -> Result<ProofTree, ProverError> {
-        match tree {
-            UnprovenTree::UnprovenLeaf(UnprovenLeaf::UnprovenSchnorr(us)) => {
-                if us.simulated {
-                    // Step 5 (simulated leaf -- complete the simulation)
-                    if let Some(challenge) = us.challenge_opt {
-                        let (fm, sm) = dlog_protocol::interactive_prover::simulate(
-                            &us.proposition,
-                            &challenge,
-                        );
-                        Ok(ProofTree::UncheckedTree(
-                            UncheckedSchnorr {
-                                proposition: us.proposition,
-                                commitment_opt: Some(fm),
-                                challenge,
-                                second_message: sm,
-                            }
-                            .into(),
-                        ))
+/// Prover Step 3: This step will change some "real" nodes to "simulated" to make sure each node has
+/// the right number of simulated children.
+/// In a top-down traversal of the tree, do the following for each node:
+fn polish_simulated<P: Prover + ?Sized>(
+    _prover: &P,
+    unproven_tree: UnprovenTree,
+) -> Result<UnprovenTree, ProverError> {
+    proof_tree::rewrite(unproven_tree.into(), &|tree| match tree {
+        ProofTree::UnprovenTree(ut) => match ut {
+            UnprovenTree::UnprovenLeaf(_) => Ok(None),
+            UnprovenTree::UnprovenConjecture(conj) => match conj {
+                UnprovenConjecture::CandUnproven(cand) => {
+                    // If the node is marked "simulated", mark all of its children "simulated"
+                    let a: CandUnproven = if cand.simulated {
+                        cand.clone().with_children(
+                            cast_to_unp(cand.children.clone())?
+                                .into_iter()
+                                .map(|c| c.with_simulated(true).into())
+                                .collect(),
+                        )
+                    } else {
+                        cand.clone()
+                    };
+                    Ok(Some(set_positions(a.into()).into()))
+                }
+                UnprovenConjecture::CorUnproven(cor) => {
+                    // If the node is marked "simulated", mark all of its children "simulated"
+                    let o: CorUnproven = if cor.simulated {
+                        CorUnproven {
+                            children: cast_to_unp(cor.children.clone())?
+                                .into_iter()
+                                .map(|c| c.with_simulated(true).into())
+                                .collect::<Vec<ProofTree>>(),
+                            ..cor.clone()
+                        }
                     } else {
-                        Err(ProverError::SimulatedLeafWithoutChallenge)
+                        // If the node is OR marked "real",  mark all but one of its children "simulated"
+                        make_cor_children_simulated(cor.clone())?
+                    };
+                    Ok(Some(set_positions(o.into()).into()))
+                }
+            },
+        },
+        ProofTree::UncheckedTree(_) => Ok(None),
+    })?
+    .try_into()
+    .map_err(|e: &str| ProverError::Unexpected(e.to_string()))
+}
+
+/**
+ Prover Step 4: In a top-down traversal of the tree, compute the challenges e for simulated children of every node
+ Prover Step 5: For every leaf marked "simulated", use the simulator of the Sigma-protocol for that leaf
+ to compute the commitment $a$ and the response z, given the challenge e that is already stored in the leaf.
+ Prover Step 6: For every leaf marked "real", use the first prover step of the Sigma-protocol for that leaf to
+ compute the commitment a.
+*/
+fn simulate_and_commit(
+    unproven_tree: UnprovenTree,
+    hints_bag: &HintsBag,
+) -> Result<UnprovenTree, ProverError> {
+    proof_tree::rewrite(unproven_tree.into(), &|tree| {
+        match tree {
+            // Step 4 part 1: If the node is marked "real", then each of its simulated children gets a fresh uniformly
+            // random challenge in {0,1}^t.
+
+            // A real AND node has no simulated children
+            ProofTree::UnprovenTree(UnprovenTree::UnprovenConjecture(
+                UnprovenConjecture::CandUnproven(cand),
+            )) if cand.is_real() => Ok(None),
+
+            //real OR
+            ProofTree::UnprovenTree(UnprovenTree::UnprovenConjecture(
+                UnprovenConjecture::CorUnproven(cor),
+            )) if cor.is_real() => {
+                let new_children = cast_to_unp(cor.children.clone())?
+                    .into_iter()
+                    .map(|c| {
+                        if c.is_real() {
+                            c
+                        } else {
+                            // take challenge from previously done proof stored in the hints bag,
+                            // or generate random challenge for simulated child
+                            let new_challenge: Challenge = hints_bag
+                                .proofs()
+                                .into_iter()
+                                .find(|p| p.position() == c.position())
+                                .map(|p| p.challenge().clone())
+                                .unwrap_or_else(Challenge::secure_random);
+                            c.with_challenge(new_challenge)
+                        }
+                    })
+                    .map(|c| c.into())
+                    .collect();
+                Ok(Some(
+                    CorUnproven {
+                        children: new_children,
+                        ..cor.clone()
                     }
+                    .into(),
+                ))
+            }
+
+            // Step 4 part 2: If the node is marked "simulated", let e_0 be the challenge computed for it.
+            // All of its children are simulated, and thus we compute challenges for all
+            // of them, as follows:
+            ProofTree::UnprovenTree(UnprovenTree::UnprovenConjecture(
+                UnprovenConjecture::CandUnproven(cand),
+            )) => {
+                // If the node is AND, then all of its children get e_0 as the challenge
+                if let Some(challenge) = cand.challenge_opt.clone() {
+                    let new_children = cand
+                        .children
+                        .clone()
+                        .into_iter()
+                        .map(|it| it.with_challenge(challenge.clone()))
+                        .collect();
+                    Ok(Some(
+                        CandUnproven {
+                            children: new_children,
+                            ..cand.clone()
+                        }
+                        .into(),
+                    ))
                 } else {
-                    // Step 6 (real leaf -- compute the commitment a)
-                    let (r, commitment) = dlog_protocol::interactive_prover::first_message();
-                    Ok(ProofTree::UnprovenTree(
-                        UnprovenSchnorr {
-                            commitment_opt: Some(commitment),
-                            randomness_opt: Some(r),
-                            ..us
+                    Err(ProverError::Unexpected(
+                        "simulate_and_commit: missing CandUnproven(simulated).challenge"
+                            .to_string(),
+                    ))
+                }
+            }
+
+            ProofTree::UnprovenTree(UnprovenTree::UnprovenConjecture(
+                UnprovenConjecture::CorUnproven(cor),
+            )) => {
+                // If the node is OR, then each of its children except one gets a fresh uniformly random
+                // challenge in {0,1}^t. The remaining child gets a challenge computed as an XOR of the challenges of all
+                // the other children and e_0.
+                if let Some(challenge) = cor.challenge_opt.clone() {
+                    let unproven_children = cast_to_unp(cor.children.clone())?;
+                    let mut tail: Vec<UnprovenTree> = unproven_children
+                        .clone()
+                        .into_iter()
+                        .skip(1)
+                        .map(|it| it.with_challenge(Challenge::secure_random()))
+                        .collect();
+                    let mut xored_challenge = challenge;
+                    for it in &tail {
+                        xored_challenge = xored_challenge.xor(it.challenge().ok_or_else(|| {
+                            ProverError::Unexpected(format!("no challenge in {:?}", it))
+                        })?);
+                    }
+                    let head = if let Some(first) = unproven_children.first() {
+                        first.clone().with_challenge(xored_challenge)
+                    } else {
+                        return Err(ProverError::Unexpected(format!(
+                            "empty children in {:?}",
+                            cor
+                        )));
+                    };
+                    let mut new_children = vec![head];
+                    new_children.append(&mut tail);
+                    Ok(Some(
+                        CorUnproven {
+                            children: new_children.into_iter().map(|c| c.into()).collect(),
+                            ..cor.clone()
                         }
                         .into(),
                     ))
+                } else {
+                    Err(ProverError::Unexpected(
+                        "simulate_and_commit: missing CandUnproven(simulated).challenge"
+                            .to_string(),
+                    ))
                 }
             }
+
+            ProofTree::UnprovenTree(UnprovenTree::UnprovenLeaf(UnprovenLeaf::UnprovenSchnorr(
+                us,
+            ))) => {
+                // Steps 5 & 6: first try pulling out commitment from the hints bag. If it exists proceed with it,
+                // otherwise, compute the commitment (if the node is real) or simulate it (if the node is simulated)
+
+                // Step 6 (real leaf -- compute the commitment a or take it from the hints bag)
+                let res: ProofTree = match hints_bag
+                    .commitments()
+                    .into_iter()
+                    .find(|c| c.position() == us.position)
+                {
+                    Some(cmt_hint) => {
+                        let pt: ProofTree = UnprovenSchnorr {
+                            commitment_opt: Some(
+                                cmt_hint
+                                    .commitment()
+                                    .try_into()
+                                    .map_err(|e: &str| ProverError::Unexpected(e.to_string()))?,
+                            ),
+                            ..us.clone()
+                        }
+                        .into();
+                        pt
+                    }
+                    None => {
+                        if us.simulated {
+                            // Step 5 (simulated leaf -- complete the simulation)
+                            if let Some(challenge) = us.challenge_opt.clone() {
+                                let (fm, sm) = dlog_protocol::interactive_prover::simulate(
+                                    &us.proposition,
+                                    &challenge,
+                                );
+                                Ok(ProofTree::UncheckedTree(
+                                    UncheckedSchnorr {
+                                        proposition: us.proposition.clone(),
+                                        commitment_opt: Some(fm),
+                                        challenge,
+                                        second_message: sm,
+                                    }
+                                    .into(),
+                                ))
+                            } else {
+                                Err(ProverError::SimulatedLeafWithoutChallenge)
+                            }
+                        } else {
+                            // Step 6 (real leaf -- compute the commitment a)
+                            let (r, commitment) =
+                                dlog_protocol::interactive_prover::first_message();
+                            Ok(ProofTree::UnprovenTree(
+                                UnprovenSchnorr {
+                                    commitment_opt: Some(commitment),
+                                    randomness_opt: Some(r),
+                                    ..us.clone()
+                                }
+                                .into(),
+                            ))
+                        }?
+                    }
+                };
+                Ok(Some(res))
+            }
+            ProofTree::UncheckedTree(_) => Ok(None),
         }
-    }
+    })?
+    .try_into()
+    .map_err(|e: &str| ProverError::Unexpected(e.to_string()))
+}
 
-    /**
-     Prover Step 9: Perform a top-down traversal of only the portion of the tree marked "real" in order to compute
-     the challenge e for every node marked "real" below the root and, additionally, the response z for every leaf
-     marked "real"
-    */
-    fn proving(&self, tree: ProofTree) -> Result<ProofTree, ProverError> {
-        // If the node is a leaf marked "real", compute its response according to the second prover step
-        // of the Sigma-protocol given the commitment, challenge, and witness
-        match tree {
-            ProofTree::UncheckedTree(_) => Ok(tree),
+/**
+ Prover Step 9: Perform a top-down traversal of only the portion of the tree marked "real" in order to compute
+ the challenge e for every node marked "real" below the root and, additionally, the response z for every leaf
+ marked "real"
+*/
+fn proving<P: Prover + ?Sized>(
+    prover: &P,
+    proof_tree: ProofTree,
+    hints_bag: &HintsBag,
+) -> Result<ProofTree, ProverError> {
+    proof_tree::rewrite(proof_tree, &|tree| {
+        match &tree {
+            ProofTree::UncheckedTree(unch) => match unch {
+                UncheckedTree::NoProof => Err(ProverError::Unexpected(
+                    "Unexpected NoProof in proving()".to_string(),
+                )),
+                UncheckedTree::UncheckedSigmaTree(ust) => match ust {
+                    UncheckedSigmaTree::UncheckedLeaf(_) => Ok(None),
+                    UncheckedSigmaTree::UncheckedConjecture(_) => Err(ProverError::Unexpected(
+                        format!("proving: unexpected {:?}", tree),
+                    )),
+                },
+            },
             ProofTree::UnprovenTree(unproven_tree) => match unproven_tree {
-                UnprovenTree::UnprovenLeaf(UnprovenLeaf::UnprovenSchnorr(us))
-                    if unproven_tree.is_real() =>
-                {
-                    if let Some(challenge) = us.challenge_opt.clone() {
-                        if let Some(priv_key) = self
-                            .secrets()
-                            .iter()
-                            .flat_map(|s| match s {
-                                PrivateInput::DlogProverInput(dl) => vec![dl],
-                                _ => vec![],
-                            })
-                            .find(|prover_input| prover_input.public_image() == us.proposition)
-                        {
-                            let z = dlog_protocol::interactive_prover::second_message(
-                                &priv_key,
-                                us.randomness_opt.unwrap(),
-                                &challenge,
-                            );
-                            Ok(UncheckedSchnorr {
-                                proposition: us.proposition,
-                                commitment_opt: None,
-                                challenge,
-                                second_message: z,
+                UnprovenTree::UnprovenConjecture(conj) => match conj {
+                    UnprovenConjecture::CandUnproven(cand) => {
+                        if cand.is_real() {
+                            // If the node is AND, let each of its children have the challenge e_0
+                            if let Some(challenge) = cand.challenge_opt.clone() {
+                                let updated = cand
+                                    .clone()
+                                    .children
+                                    .into_iter()
+                                    .map(|child| child.with_challenge(challenge.clone()))
+                                    .collect();
+                                Ok(Some(cand.clone().with_children(updated).into()))
+                            } else {
+                                Err(ProverError::Unexpected(
+                                    "proving: CandUnproven.challenge_opt is empty".to_string(),
+                                ))
                             }
-                            .into())
                         } else {
-                            Err(ProverError::SecretNotFound)
+                            Ok(None)
                         }
-                    } else {
-                        Err(ProverError::RealUnprovenTreeWithoutChallenge)
                     }
+                    UnprovenConjecture::CorUnproven(cor) => {
+                        // If the node is OR, it has only one child marked "real".
+                        // Let this child have the challenge equal to the XOR of the challenges of all
+                        // the other children and e_0
+                        if cor.is_real() {
+                            if let Some(root_challenge) = &cor.challenge_opt {
+                                let challenge: Challenge = cor
+                                    .children
+                                    .clone()
+                                    .into_iter()
+                                    .flat_map(|c| c.challenge())
+                                    .fold(root_challenge.clone(), |acc, c| acc.xor(c));
+                                let children = cor
+                                    .children
+                                    .clone()
+                                    .into_iter()
+                                    .map(|c| match c {
+                                        ProofTree::UnprovenTree(ref ut) if ut.is_real() => {
+                                            c.with_challenge(challenge.clone())
+                                        }
+                                        _ => c,
+                                    })
+                                    .collect();
+                                Ok(Some(
+                                    CorUnproven {
+                                        children,
+                                        ..cor.clone()
+                                    }
+                                    .into(),
+                                ))
+                            } else {
+                                Err(ProverError::Unexpected(
+                                    "proving: CorUnproven.challenge_opt is empty".to_string(),
+                                ))
+                            }
+                        } else {
+                            Ok(None)
+                        }
+                    }
+                },
+
+                // If the node is a leaf marked "real", compute its response according to the second prover step
+                // of the Sigma-protocol given the commitment, challenge, and witness, or pull response from the hints bag
+                UnprovenTree::UnprovenLeaf(unp_leaf) if unp_leaf.is_real() => match unp_leaf {
+                    UnprovenLeaf::UnprovenSchnorr(us) => {
+                        if let Some(challenge) = us.challenge_opt.clone() {
+                            if let Some(priv_key) = prover
+                                .secrets()
+                                .iter()
+                                .flat_map(|s| match s {
+                                    PrivateInput::DlogProverInput(dl) => vec![dl],
+                                    _ => vec![],
+                                })
+                                .find(|prover_input| prover_input.public_image() == us.proposition)
+                            {
+                                let z = dlog_protocol::interactive_prover::second_message(
+                                    &priv_key,
+                                    us.randomness_opt.ok_or_else(|| {
+                                        ProverError::Unexpected(format!(
+                                            "empty randomness in {:?}",
+                                            us
+                                        ))
+                                    })?,
+                                    &challenge,
+                                );
+                                Ok(Some(
+                                    UncheckedSchnorr {
+                                        proposition: us.proposition.clone(),
+                                        commitment_opt: None,
+                                        challenge,
+                                        second_message: z,
+                                    }
+                                    .into(),
+                                ))
+                            } else {
+                                Err(ProverError::SecretNotFound)
+                            }
+                        } else {
+                            Err(ProverError::RealUnprovenTreeWithoutChallenge)
+                        }
+                    }
+                },
+                UnprovenTree::UnprovenLeaf(unp_leaf) => {
+                    // if the simulated node is proven by someone else, take it from hints bag
+                    let res: ProofTree = hints_bag
+                        .simulated_proofs()
+                        .into_iter()
+                        .find(|proof| proof.image == unp_leaf.proposition())
+                        .map(|proof| proof.unchecked_tree.into())
+                        .unwrap_or_else(|| unp_leaf.clone().into());
+                    Ok(Some(res))
                 }
-                _ => todo!(),
             },
         }
-    }
+    })
 }
 
-fn convert_to_unproven(ergo_lib: SigmaBoolean) -> UnprovenTree {
-    match ergo_lib {
-        // TODO: why it's even here? Make another SigmaBoolean without trivial props?
-        SigmaBoolean::TrivialProp(_) => todo!(),
+fn convert_to_unproven(sb: SigmaBoolean) -> UnprovenTree {
+    match sb {
         SigmaBoolean::ProofOfKnowledge(pok) => match pok {
             SigmaProofOfKnowledgeTree::ProveDhTuple(_) => todo!(),
             SigmaProofOfKnowledgeTree::ProveDlog(prove_dlog) => UnprovenSchnorr {
@@ -282,10 +706,85 @@ fn convert_to_unproven(ergo_lib: SigmaBoolean) -> UnprovenTree {
                 randomness_opt: None,
                 challenge_opt: None,
                 simulated: false,
+                position: NodePosition::crypto_tree_prefix(),
             }
             .into(),
         },
-        SigmaBoolean::Cand(_) => todo!(),
+        SigmaBoolean::SigmaConjecture(SigmaConjecture::Cand(cand)) => CandUnproven {
+            proposition: cand.clone(),
+            challenge_opt: None,
+            simulated: false,
+            children: cand
+                .items
+                .into_iter()
+                .map(|it| convert_to_unproven(it).into())
+                .collect(),
+            position: NodePosition::crypto_tree_prefix(),
+        }
+        .into(),
+        SigmaBoolean::SigmaConjecture(SigmaConjecture::Cor(cor)) => CorUnproven {
+            proposition: cor.clone(),
+            challenge_opt: None,
+            simulated: false,
+            children: cor
+                .items
+                .into_iter()
+                .map(|it| convert_to_unproven(it).into())
+                .collect(),
+            position: NodePosition::crypto_tree_prefix(),
+        }
+        .into(),
+        SigmaBoolean::TrivialProp(_) => panic!("TrivialProp is not expected here"),
+    }
+}
+
+fn convert_to_unchecked(tree: ProofTree) -> Result<UncheckedSigmaTree, ProverError> {
+    match &tree {
+        ProofTree::UncheckedTree(unch_tree) => match unch_tree {
+            UncheckedTree::NoProof => Err(ProverError::Unexpected(
+                "convert_to_unchecked: unexpected NoProof".to_string(),
+            )),
+            UncheckedTree::UncheckedSigmaTree(ust) => match ust {
+                UncheckedSigmaTree::UncheckedLeaf(ul) => match ul {
+                    UncheckedLeaf::UncheckedSchnorr(_) => Ok(ust.clone()),
+                },
+                UncheckedSigmaTree::UncheckedConjecture(_) => Err(ProverError::Unexpected(
+                    format!("convert_to_unchecked: unexpected {:?}", tree),
+                )),
+            },
+        },
+        ProofTree::UnprovenTree(unp_tree) => match unp_tree {
+            UnprovenTree::UnprovenLeaf(_) => Err(ProverError::Unexpected(format!(
+                "convert_to_unchecked: unexpected {:?}",
+                tree
+            ))),
+            UnprovenTree::UnprovenConjecture(conj) => match conj {
+                UnprovenConjecture::CandUnproven(cand) => Ok(UncheckedConjecture::CandUnchecked {
+                    challenge: cand.challenge_opt.clone().ok_or_else(|| {
+                        ProverError::Unexpected(format!("no challenge in {:?}", cand))
+                    })?,
+                    children: cand
+                        .children
+                        .clone()
+                        .into_iter()
+                        .map(convert_to_unchecked)
+                        .collect::<Result<Vec<UncheckedSigmaTree>, _>>()?,
+                }
+                .into()),
+                UnprovenConjecture::CorUnproven(cor) => Ok(UncheckedConjecture::CorUnchecked {
+                    challenge: cor.challenge_opt.clone().ok_or_else(|| {
+                        ProverError::Unexpected(format!("no challenge in {:?}", cor))
+                    })?,
+                    children: cor
+                        .children
+                        .clone()
+                        .into_iter()
+                        .map(convert_to_unchecked)
+                        .collect::<Result<Vec<UncheckedSigmaTree>, _>>()?,
+                }
+                .into()),
+            },
+        },
     }
 }
 
@@ -302,12 +801,15 @@ impl Prover for TestProver {
     }
 }
 
+#[allow(clippy::unwrap_used)]
 #[cfg(test)]
 mod tests {
     use super::*;
     use crate::sigma_protocol::private_input::DlogProverInput;
     use ergotree_ir::mir::constant::Constant;
     use ergotree_ir::mir::expr::Expr;
+    use ergotree_ir::mir::sigma_and::SigmaAnd;
+    use ergotree_ir::mir::sigma_or::SigmaOr;
     use ergotree_ir::mir::value::Value;
     use ergotree_ir::types::stype::SType;
     use sigma_test_util::force_any_val;
@@ -327,6 +829,7 @@ mod tests {
             &Env::empty(),
             Rc::new(force_any_val::<Context>()),
             message.as_slice(),
+            &HintsBag::empty(),
         );
         assert!(res.is_ok());
         assert_eq!(res.unwrap().proof, ProofBytes::Empty);
@@ -346,6 +849,7 @@ mod tests {
             &Env::empty(),
             Rc::new(force_any_val::<Context>()),
             message.as_slice(),
+            &HintsBag::empty(),
         );
         assert!(res.is_err());
         assert_eq!(res.err().unwrap(), ProverError::ReducedToFalse);
@@ -366,8 +870,123 @@ mod tests {
             &Env::empty(),
             Rc::new(force_any_val::<Context>()),
             message.as_slice(),
+            &HintsBag::empty(),
         );
         assert!(res.is_ok());
         assert_ne!(res.unwrap().proof, ProofBytes::Empty);
     }
+
+    #[test]
+    fn test_prove_pk_and_pk() {
+        let secret1 = DlogProverInput::random();
+        let secret2 = DlogProverInput::random();
+        let pk1 = secret1.public_image();
+        let pk2 = secret2.public_image();
+        let expr: Expr = SigmaAnd::new(vec![Expr::Const(pk1.into()), Expr::Const(pk2.into())])
+            .unwrap()
+            .into();
+        let tree: ErgoTree = expr.into();
+        let message = vec![0u8; 100];
+
+        let prover = TestProver {
+            secrets: vec![secret1.into(), secret2.into()],
+        };
+        let res = prover.prove(
+            &tree,
+            &Env::empty(),
+            Rc::new(force_any_val::<Context>()),
+            message.as_slice(),
+            &HintsBag::empty(),
+        );
+        assert_ne!(res.unwrap().proof, ProofBytes::Empty);
+    }
+
+    #[test]
+    fn test_prove_pk_and_or() {
+        let secret1 = DlogProverInput::random();
+        let secret2 = DlogProverInput::random();
+        let secret3 = DlogProverInput::random();
+        let pk1 = secret1.public_image();
+        let pk2 = secret2.public_image();
+        let pk3 = secret3.public_image();
+        let expr: Expr = SigmaAnd::new(vec![
+            Expr::Const(pk1.into()),
+            SigmaOr::new(vec![Expr::Const(pk2.into()), Expr::Const(pk3.into())])
+                .unwrap()
+                .into(),
+        ])
+        .unwrap()
+        .into();
+        let tree: ErgoTree = expr.into();
+        let message = vec![0u8; 100];
+
+        let prover = TestProver {
+            secrets: vec![secret1.into(), secret2.into()],
+        };
+        let res = prover.prove(
+            &tree,
+            &Env::empty(),
+            Rc::new(force_any_val::<Context>()),
+            message.as_slice(),
+            &HintsBag::empty(),
+        );
+        assert_ne!(res.unwrap().proof, ProofBytes::Empty);
+    }
+
+    #[test]
+    fn test_prove_pk_or_pk() {
+        let secret1 = DlogProverInput::random();
+        let secret2 = DlogProverInput::random();
+        let pk1 = secret1.public_image();
+        let pk2 = secret2.public_image();
+        let expr: Expr = SigmaOr::new(vec![Expr::Const(pk1.into()), Expr::Const(pk2.into())])
+            .unwrap()
+            .into();
+        let tree: ErgoTree = expr.into();
+        let message = vec![0u8; 100];
+
+        let prover = TestProver {
+            secrets: vec![secret1.into(), secret2.into()],
+        };
+        let res = prover.prove(
+            &tree,
+            &Env::empty(),
+            Rc::new(force_any_val::<Context>()),
+            message.as_slice(),
+            &HintsBag::empty(),
+        );
+        assert_ne!(res.unwrap().proof, ProofBytes::Empty);
+    }
+
+    #[test]
+    fn test_prove_pk_or_and() {
+        let secret1 = DlogProverInput::random();
+        let secret2 = DlogProverInput::random();
+        let secret3 = DlogProverInput::random();
+        let pk1 = secret1.public_image();
+        let pk2 = secret2.public_image();
+        let pk3 = secret3.public_image();
+        let expr: Expr = SigmaOr::new(vec![
+            Expr::Const(pk1.into()),
+            SigmaAnd::new(vec![Expr::Const(pk2.into()), Expr::Const(pk3.into())])
+                .unwrap()
+                .into(),
+        ])
+        .unwrap()
+        .into();
+        let tree: ErgoTree = expr.into();
+        let message = vec![0u8; 100];
+
+        let prover = TestProver {
+            secrets: vec![secret2.into(), secret3.into()],
+        };
+        let res = prover.prove(
+            &tree,
+            &Env::empty(),
+            Rc::new(force_any_val::<Context>()),
+            message.as_slice(),
+            &HintsBag::empty(),
+        );
+        assert_ne!(res.unwrap().proof, ProofBytes::Empty);
+    }
 }
diff --git a/ergotree-interpreter/src/sigma_protocol/prover/hint.rs b/ergotree-interpreter/src/sigma_protocol/prover/hint.rs
new file mode 100644
index 000000000..cf1767e12
--- /dev/null
+++ b/ergotree-interpreter/src/sigma_protocol/prover/hint.rs
@@ -0,0 +1,226 @@
+//! Hints for a prover which helps the prover to prove a statement.
+
+use ergotree_ir::sigma_protocol::sigma_boolean::SigmaBoolean;
+use num_bigint::BigInt;
+
+use crate::sigma_protocol::challenge::Challenge;
+use crate::sigma_protocol::unchecked_tree::UncheckedTree;
+use crate::sigma_protocol::unproven_tree::NodePosition;
+use crate::sigma_protocol::FirstProverMessage;
+
+/// A hint for a prover which helps the prover to prove a statement. For example, if the statement is "pk1 && pk2",
+/// and the prover knows only a secret for the public key pk1, the prover fails on proving without a hint. But if the
+/// prover knows that pk2 is known to another party, the prover may prove the statement (with an empty proof for "pk2").
+#[derive(PartialEq, Debug, Clone)]
+pub enum Hint {
+    /// A hint which is indicating that a secret associated with its public image "image" is already proven.
+    SecretProven(SecretProven),
+    /// A family of hints which are about a correspondence between a public image of a secret image and prover's commitment
+    /// to randomness ("a" in a sigma protocol).
+    CommitmentHint(CommitmentHint),
+}
+
+/// A hint which contains a proof-of-knowledge for a secret associated with its public image "image",
+/// with also the mark that the proof is real.
+#[derive(PartialEq, Debug, Clone)]
+pub struct RealSecretProof {
+    /// Public image of a secret which is proven
+    pub image: SigmaBoolean,
+    /// Challenge used for a proof
+    pub challenge: Challenge,
+    /// Proof in a tree form
+    pub unchecked_tree: UncheckedTree,
+    /// A hint is related to a subtree (or a leaf) of a tree. This field encodes a position in the tree.
+    pub position: NodePosition,
+}
+
+/// A hint which contains a proof-of-knowledge for a secret associated with its public image "image",
+/// with also the mark that the proof is real.
+#[derive(PartialEq, Debug, Clone)]
+pub struct SimulatedSecretProof {
+    /// Public image of a secret which is proven
+    pub image: SigmaBoolean,
+    /// Challenge used for a proof
+    pub challenge: Challenge,
+    /// Proof in a tree form
+    pub unchecked_tree: UncheckedTree,
+    /// A hint is related to a subtree (or a leaf) of a tree. This field encodes a position in the tree.
+    pub position: NodePosition,
+}
+
+/// A hint which is indicating that a secret associated with its public image "image" is already proven.
+#[derive(PartialEq, Debug, Clone)]
+pub enum SecretProven {
+    /// A hint which contains a proof-of-knowledge for a secret associated with its public image "image",
+    /// with also the mark that the proof is real.
+    RealSecretProof(RealSecretProof),
+    /// A hint which contains a proof-of-knowledge for a secret associated with its public image "image",
+    /// with also the mark that the proof is real.
+    SimulatedSecretProof(SimulatedSecretProof),
+}
+
+impl SecretProven {
+    /// A hint is related to a subtree (or a leaf) of a tree. This field encodes a position in the tree.
+    pub fn position(&self) -> &NodePosition {
+        todo!()
+    }
+
+    /// Challenge used for a proof
+    pub fn challenge(&self) -> &Challenge {
+        todo!()
+    }
+}
+
+/// A hint which contains a commitment to randomness associated with a public image of a secret.
+#[derive(PartialEq, Debug, Clone)]
+pub struct RealCommitment {
+    ///  image of a secret
+    pub image: SigmaBoolean,
+    /// commitment to randomness used while proving knowledge of the secret
+    pub commitment: FirstProverMessage,
+    /// A hint is related to a subtree (or a leaf) of a tree. This field encodes a position in the tree.
+    pub position: NodePosition,
+}
+
+/// A family of hints which are about a correspondence between a public image of a secret image and prover's commitment
+/// to randomness ("a" in a sigma protocol).
+#[derive(PartialEq, Debug, Clone)]
+pub enum CommitmentHint {
+    /// * A hint which a commitment to randomness associated with a public image of a secret, as well as randomness itself.
+    ///  * Please note that this randomness should be kept in secret by the prover.
+    ///  *
+    OwnCommitment {
+        ///  image of a secret
+        image: SigmaBoolean,
+        /// randomness
+        secret_randomness: BigInt,
+        /// commitment to randomness used while proving knowledge of the secret
+        commitment: FirstProverMessage,
+        /// A hint is related to a subtree (or a leaf) of a tree. This field encodes a position in the tree.
+        position: NodePosition,
+    },
+    /// A hint which contains a commitment to randomness associated with a public image of a secret.
+    RealCommitment(RealCommitment),
+    ///A hint which contains a commitment to randomness associated with a public image of a secret.
+    SimulatedCommitment {
+        /// image of a secret
+        image: SigmaBoolean,
+        /// commitment to randomness used while proving knowledge of the secret
+        commitment: FirstProverMessage,
+        /// A hint is related to a subtree (or a leaf) of a tree. This field encodes a position in the tree.
+        position: NodePosition,
+    },
+}
+
+impl CommitmentHint {
+    /// A hint is related to a subtree (or a leaf) of a tree. Returns position in the tree.
+    pub fn position(&self) -> NodePosition {
+        todo!()
+    }
+
+    /// commitment to randomness used while proving knowledge of the secret
+    pub fn commitment(&self) -> FirstProverMessage {
+        todo!()
+    }
+}
+
+/// Collection of hints to be used by a prover
+pub struct HintsBag {
+    /// Hints stored in a bag
+    hints: Vec<Hint>,
+}
+
+impl HintsBag {
+    /// Bag without hints
+    pub fn empty() -> Self {
+        HintsBag { hints: vec![] }
+    }
+
+    /// Commitments from all CommitmentHints in the bag
+    pub fn commitments(&self) -> Vec<CommitmentHint> {
+        self.hints
+            .clone()
+            .into_iter()
+            .filter_map(|hint| {
+                if let Hint::CommitmentHint(v) = hint {
+                    Some(v)
+                } else {
+                    None
+                }
+            })
+            .collect()
+    }
+
+    /// RealSecretProof hints only
+    pub fn real_proofs(&self) -> Vec<RealSecretProof> {
+        self.hints
+            .clone()
+            .into_iter()
+            .filter_map(|hint| {
+                if let Hint::SecretProven(SecretProven::RealSecretProof(v)) = hint {
+                    Some(v)
+                } else {
+                    None
+                }
+            })
+            .collect()
+    }
+
+    /// RealCommitment hints only
+    pub fn real_commitments(&self) -> Vec<RealCommitment> {
+        self.hints
+            .clone()
+            .into_iter()
+            .filter_map(|hint| {
+                if let Hint::CommitmentHint(CommitmentHint::RealCommitment(v)) = hint {
+                    Some(v)
+                } else {
+                    None
+                }
+            })
+            .collect()
+    }
+
+    /// Images of real secrets + real commitments in the bag
+    pub fn real_images(&self) -> Vec<SigmaBoolean> {
+        let mut from_proofs: Vec<SigmaBoolean> =
+            self.real_proofs().iter().map(|p| p.image.clone()).collect();
+        let mut from_comms: Vec<SigmaBoolean> = self
+            .real_commitments()
+            .iter()
+            .map(|c| c.image.clone())
+            .collect();
+        from_proofs.append(&mut from_comms);
+        from_proofs
+    }
+
+    /// SimulatedSecretProof proofs only
+    pub fn simulated_proofs(&self) -> Vec<SimulatedSecretProof> {
+        self.hints
+            .clone()
+            .into_iter()
+            .filter_map(|hint| {
+                if let Hint::SecretProven(SecretProven::SimulatedSecretProof(v)) = hint {
+                    Some(v)
+                } else {
+                    None
+                }
+            })
+            .collect()
+    }
+
+    /// All proofs from SecretProven variants
+    pub fn proofs(&self) -> Vec<SecretProven> {
+        self.hints
+            .clone()
+            .into_iter()
+            .filter_map(|hint| {
+                if let Hint::SecretProven(sp) = hint {
+                    Some(sp)
+                } else {
+                    None
+                }
+            })
+            .collect()
+    }
+}
diff --git a/ergotree-interpreter/src/sigma_protocol/sig_serializer.rs b/ergotree-interpreter/src/sigma_protocol/sig_serializer.rs
index a0dee2e75..ec3db1aad 100644
--- a/ergotree-interpreter/src/sigma_protocol/sig_serializer.rs
+++ b/ergotree-interpreter/src/sigma_protocol/sig_serializer.rs
@@ -1,77 +1,208 @@
 //! Serialization of proof tree signatures
 
 use super::prover::ProofBytes;
-use super::{
-    fiat_shamir::FiatShamirHash,
-    unchecked_tree::{UncheckedLeaf, UncheckedSchnorr},
-    Challenge, GroupSizedBytes, SigmaBoolean, UncheckedSigmaTree, UncheckedTree,
-};
+use super::unchecked_tree::UncheckedConjecture;
+use super::unchecked_tree::UncheckedLeaf;
+use super::unchecked_tree::UncheckedSigmaTree;
+use super::unchecked_tree::UncheckedTree;
+use crate::sigma_protocol::Challenge;
+use crate::sigma_protocol::GroupSizedBytes;
+use crate::sigma_protocol::UncheckedSchnorr;
 
+use ergotree_ir::serialization::sigma_byte_reader;
+use ergotree_ir::serialization::sigma_byte_reader::SigmaByteRead;
+use ergotree_ir::serialization::sigma_byte_writer::SigmaByteWrite;
+use ergotree_ir::serialization::sigma_byte_writer::SigmaByteWriter;
+use ergotree_ir::serialization::SerializationError;
+use ergotree_ir::serialization::SigmaSerializable;
+use ergotree_ir::sigma_protocol::sigma_boolean::SigmaBoolean;
+use ergotree_ir::sigma_protocol::sigma_boolean::SigmaConjecture;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaProofOfKnowledgeTree;
+
+use derive_more::From;
 use k256::Scalar;
-use std::convert::{TryFrom, TryInto};
+use thiserror::Error;
 
-/// Serialize proof tree signatures
-pub fn serialize_sig(tree: UncheckedTree) -> ProofBytes {
+/// Recursively traverses the given node and serializes challenges and prover messages to the given writer.
+/// Note, sigma propositions and commitments are not serialized.
+/// Returns the proof bytes containing all the serialized challenges and prover messages (aka `z` values)
+pub(crate) fn serialize_sig(tree: UncheckedTree) -> ProofBytes {
     match tree {
         UncheckedTree::NoProof => ProofBytes::Empty,
-        UncheckedTree::UncheckedSigmaTree(UncheckedSigmaTree::UncheckedLeaf(
-            UncheckedLeaf::UncheckedSchnorr(us),
-        )) => {
-            let mut res: Vec<u8> = Vec::with_capacity(64);
-            res.append(&mut us.challenge.into());
-            let mut sm_bytes = us.second_message.z.to_bytes();
-            res.append(&mut sm_bytes.as_mut_slice().to_vec());
-            ProofBytes::Some(res)
+        UncheckedTree::UncheckedSigmaTree(ust) => {
+            let mut data = Vec::new();
+            let mut w = SigmaByteWriter::new(&mut data, None);
+            sig_write_bytes(&ust, &mut w, true)
+                // since serialization may fail only for underlying IO errors it's ok to force unwrap
+                .expect("serialization failed");
+            ProofBytes::Some(data)
         }
-        _ => todo!(),
     }
 }
 
-/**
- * Verifier Step 2: In a top-down traversal of the tree, obtain the challenges for the children of every
- * non-leaf node by reading them from the proof or computing them.
- * Verifier Step 3: For every leaf node, read the response z provided in the proof.
- */
-pub fn parse_sig_compute_challenges(
-    exp: SigmaBoolean,
-    proof: &ProofBytes,
+/// Recursively traverses the given node and serializes challenges and prover messages to the given writer.
+/// Note, sigma propositions and commitments are not serialized.
+/// Returns the proof bytes containing all the serialized challenges and prover messages (aka `z` values)
+fn sig_write_bytes<W: SigmaByteWrite>(
+    node: &UncheckedSigmaTree,
+    w: &mut W,
+    write_challenges: bool,
+) -> Result<(), std::io::Error> {
+    if write_challenges {
+        node.challenge().sigma_serialize(w)?;
+    }
+    match node {
+        UncheckedSigmaTree::UncheckedLeaf(leaf) => match leaf {
+            UncheckedLeaf::UncheckedSchnorr(us) => {
+                let mut sm_bytes = us.second_message.z.to_bytes();
+                w.write_all(sm_bytes.as_mut_slice())
+            }
+        },
+        UncheckedSigmaTree::UncheckedConjecture(conj) => match conj {
+            UncheckedConjecture::CandUnchecked {
+                challenge: _,
+                children,
+            } => {
+                // don't write children's challenges -- they are equal to the challenge of this node
+                for child in children {
+                    sig_write_bytes(child, w, false)?;
+                }
+                Ok(())
+            }
+            UncheckedConjecture::CorUnchecked {
+                challenge: _,
+                children,
+            } => {
+                // don't write last child's challenge -- it's computed by the verifier via XOR
+                if let Some((last, elements)) = children.split_last() {
+                    for child in elements {
+                        sig_write_bytes(child, w, true)?;
+                    }
+                    sig_write_bytes(last, w, false)?;
+                }
+                Ok(())
+            }
+        },
+    }
+}
+
+/// Verifier Step 2: In a top-down traversal of the tree, obtain the challenges for the children of every
+/// non-leaf node by reading them from the proof or computing them.
+/// Verifier Step 3: For every leaf node, read the response z provided in the proof.
+/// * `exp` - sigma proposition which defines the structure of bytes from the reader
+/// * `proof` - proof to extract challenges from
+pub(crate) fn parse_sig_compute_challenges(
+    exp: &SigmaBoolean,
+    proof: ProofBytes,
 ) -> Result<UncheckedTree, SigParsingError> {
-    if let ProofBytes::Some(proof_bytes) = proof {
-        // Verifier Step 2: Let e_0 be the challenge in the node here (e_0 is called "challenge" in the code)
-        let chal_len = super::SOUNDNESS_BYTES;
-        let challenge = if let Some(bytes) = proof_bytes.get(..chal_len) {
-            // safe since it should only be of the required size
-            Challenge::from(FiatShamirHash::try_from(bytes).unwrap())
-        } else {
-            return Err(SigParsingError::InvalidProofSize);
-        };
-        match exp {
-            SigmaBoolean::ProofOfKnowledge(SigmaProofOfKnowledgeTree::ProveDlog(dl)) => {
-                let scalar_bytes: &[u8; super::GROUP_SIZE] =
-                    match proof_bytes.get(chal_len..chal_len + super::GROUP_SIZE) {
-                        Some(v) => v.try_into().unwrap(), // safe, since it should only be of this size
-                        None => return Err(SigParsingError::InvalidProofSize),
-                    };
-                let z = Scalar::from(GroupSizedBytes::from(scalar_bytes));
+    match proof {
+        ProofBytes::Empty => Ok(UncheckedTree::NoProof),
+        ProofBytes::Some(mut proof_bytes) => {
+            let mut r = sigma_byte_reader::from_bytes(proof_bytes.as_mut_slice());
+            parse_sig_compute_challnges_reader(exp, &mut r, None).map(|tree| tree.into())
+        }
+    }
+}
+
+/// Verifier Step 2: In a top-down traversal of the tree, obtain the challenges for the children of every
+/// non-leaf node by reading them from the proof or computing them.
+/// Verifier Step 3: For every leaf node, read the response z provided in the proof.
+/// * `exp` - sigma proposition which defines the structure of bytes from the reader
+fn parse_sig_compute_challnges_reader<R: SigmaByteRead>(
+    exp: &SigmaBoolean,
+    r: &mut R,
+    challenge_opt: Option<Challenge>,
+) -> Result<UncheckedSigmaTree, SigParsingError> {
+    // Verifier Step 2: Let e_0 be the challenge in the node here (e_0 is called "challenge" in the code)
+    let challenge = if let Some(c) = challenge_opt {
+        c
+    } else {
+        Challenge::sigma_parse(r)?
+    };
+
+    match exp {
+        SigmaBoolean::TrivialProp(_) => {
+            panic!("TrivialProp should be handled before this call")
+        }
+        SigmaBoolean::ProofOfKnowledge(tree) => match tree {
+            SigmaProofOfKnowledgeTree::ProveDlog(dl) => {
+                // Verifier Step 3: For every leaf node, read the response z provided in the proof.
+                let mut scalar_bytes: [u8; super::GROUP_SIZE] = [0; super::GROUP_SIZE];
+                r.read_exact(&mut scalar_bytes)?;
+                let z = Scalar::from(GroupSizedBytes(scalar_bytes.into()));
                 Ok(UncheckedSchnorr {
-                    proposition: dl,
+                    proposition: dl.clone(),
                     commitment_opt: None,
                     challenge,
                     second_message: z.into(),
                 }
                 .into())
             }
-            _ => todo!(),
-        }
-    } else {
-        Err(SigParsingError::InvalidProofSize)
+            SigmaProofOfKnowledgeTree::ProveDhTuple(_) => todo!("DHT is not yet supported"),
+        },
+        SigmaBoolean::SigmaConjecture(conj) => match conj {
+            SigmaConjecture::Cand(cand) => {
+                // Verifier Step 2: If the node is AND, then all of its children get e_0 as
+                // the challenge
+                let mut children: Vec<UncheckedSigmaTree> = Vec::new();
+                for it in cand.items.clone() {
+                    children.push(parse_sig_compute_challnges_reader(
+                        &it,
+                        r,
+                        Some(challenge.clone()),
+                    )?);
+                }
+                Ok(UncheckedConjecture::CandUnchecked {
+                    challenge,
+                    children,
+                }
+                .into())
+            }
+            SigmaConjecture::Cor(cor) => {
+                // Verifier Step 2: If the node is OR, then each of its children except rightmost
+                // one gets the challenge given in the proof for that node.
+                // The rightmost child gets a challenge computed as an XOR of the challenges of all the other children and e_0.
+
+                // Read all the children but the last and compute the XOR of all the challenges including e_0
+                let mut children: Vec<UncheckedSigmaTree> = Vec::new();
+
+                if let Some((last, rest)) = cor.items.split_last() {
+                    for it in rest {
+                        children.push(parse_sig_compute_challnges_reader(&it, r, None)?);
+                    }
+                    let xored_challenge = children
+                        .clone()
+                        .into_iter()
+                        .map(|c| c.challenge())
+                        .fold(challenge.clone(), |acc, c| acc.xor(c));
+                    let last_child =
+                        parse_sig_compute_challnges_reader(last, r, Some(xored_challenge))?;
+                    children.push(last_child);
+                }
+
+                Ok(UncheckedConjecture::CorUnchecked {
+                    challenge,
+                    children,
+                }
+                .into())
+            }
+        },
     }
 }
 
 /// Errors when parsing proof tree signatures
-#[derive(PartialEq, Eq, Debug, Clone)]
+#[derive(Error, PartialEq, Eq, Debug, Clone, From)]
 pub enum SigParsingError {
-    /// Invalid proof size (expected 32 bytes)
-    InvalidProofSize,
+    /// IO error
+    #[error("IO error: {0}")]
+    IoError(String),
+    /// Serialization error
+    #[error("Serialization error: {0}")]
+    SerializationError(SerializationError),
+}
+
+impl From<std::io::Error> for SigParsingError {
+    fn from(e: std::io::Error) -> Self {
+        SigParsingError::IoError(e.to_string())
+    }
 }
diff --git a/ergotree-interpreter/src/sigma_protocol/unchecked_tree.rs b/ergotree-interpreter/src/sigma_protocol/unchecked_tree.rs
index 14990c35e..aa73a2ed4 100644
--- a/ergotree-interpreter/src/sigma_protocol/unchecked_tree.rs
+++ b/ergotree-interpreter/src/sigma_protocol/unchecked_tree.rs
@@ -4,13 +4,20 @@ use ergotree_ir::sigma_protocol::sigma_boolean::ProveDlog;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaBoolean;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaProofOfKnowledgeTree;
 
+use super::proof_tree::ConjectureType;
+use super::proof_tree::ProofTree;
+use super::proof_tree::ProofTreeConjecture;
+use super::proof_tree::ProofTreeKind;
+use super::proof_tree::ProofTreeLeaf;
 use super::{
     dlog_protocol::{FirstDlogProverMessage, SecondDlogProverMessage},
-    Challenge, FirstProverMessage, ProofTree, ProofTreeLeaf,
+    Challenge, FirstProverMessage,
 };
 
+use derive_more::From;
+
 /// Unchecked tree
-#[derive(PartialEq, Debug, Clone)]
+#[derive(PartialEq, Debug, Clone, From)]
 pub enum UncheckedTree {
     /// No proof needed
     NoProof,
@@ -18,36 +25,53 @@ pub enum UncheckedTree {
     UncheckedSigmaTree(UncheckedSigmaTree),
 }
 
+impl UncheckedTree {
+    pub(crate) fn as_tree_kind(&self) -> ProofTreeKind {
+        match self {
+            UncheckedTree::NoProof => panic!("NoProof has not ProofTreeKind representation"),
+            UncheckedTree::UncheckedSigmaTree(ust) => ust.as_tree_kind(),
+        }
+    }
+
+    pub(crate) fn challenge(&self) -> Option<Challenge> {
+        match self {
+            UncheckedTree::NoProof => None,
+            UncheckedTree::UncheckedSigmaTree(ust) => Some(ust.challenge()),
+        }
+    }
+}
+
 /// Unchecked sigma tree
-#[derive(PartialEq, Debug, Clone)]
+#[derive(PartialEq, Debug, Clone, From)]
 pub enum UncheckedSigmaTree {
     /// Unchecked leaf
     UncheckedLeaf(UncheckedLeaf),
     /// Unchecked conjecture (OR, AND, ...)
-    UncheckedConjecture,
+    UncheckedConjecture(UncheckedConjecture),
 }
 
 impl UncheckedSigmaTree {
     /// Get challenge
-    pub fn challenge(&self) -> Challenge {
+    pub(crate) fn challenge(&self) -> Challenge {
         match self {
             UncheckedSigmaTree::UncheckedLeaf(UncheckedLeaf::UncheckedSchnorr(us)) => {
                 us.challenge.clone()
             }
-            UncheckedSigmaTree::UncheckedConjecture => todo!(),
+            UncheckedSigmaTree::UncheckedConjecture(uc) => uc.challenge(),
         }
     }
-}
 
-impl<T: Into<UncheckedLeaf>> From<T> for UncheckedSigmaTree {
-    fn from(t: T) -> Self {
-        UncheckedSigmaTree::UncheckedLeaf(t.into())
+    pub(crate) fn as_tree_kind(&self) -> ProofTreeKind {
+        match self {
+            UncheckedSigmaTree::UncheckedLeaf(ul) => ProofTreeKind::Leaf(ul),
+            UncheckedSigmaTree::UncheckedConjecture(uc) => ProofTreeKind::Conjecture(uc),
+        }
     }
 }
 
-impl From<UncheckedSigmaTree> for ProofTree {
-    fn from(ust: UncheckedSigmaTree) -> Self {
-        ProofTree::UncheckedTree(UncheckedTree::UncheckedSigmaTree(ust))
+impl From<UncheckedSchnorr> for UncheckedSigmaTree {
+    fn from(v: UncheckedSchnorr) -> Self {
+        UncheckedSigmaTree::UncheckedLeaf(v.into())
     }
 }
 
@@ -79,7 +103,6 @@ impl From<UncheckedSchnorr> for UncheckedLeaf {
     }
 }
 
-#[allow(missing_docs)]
 #[derive(PartialEq, Debug, Clone)]
 pub struct UncheckedSchnorr {
     pub proposition: ProveDlog,
@@ -93,3 +116,90 @@ impl From<UncheckedSchnorr> for UncheckedTree {
         UncheckedTree::UncheckedSigmaTree(us.into())
     }
 }
+
+#[derive(PartialEq, Debug, Clone)]
+pub enum UncheckedConjecture {
+    CandUnchecked {
+        challenge: Challenge,
+        children: Vec<UncheckedSigmaTree>,
+    },
+    CorUnchecked {
+        challenge: Challenge,
+        children: Vec<UncheckedSigmaTree>,
+    },
+}
+
+impl UncheckedConjecture {
+    pub fn with_children(self, new_children: Vec<UncheckedSigmaTree>) -> Self {
+        match self {
+            UncheckedConjecture::CandUnchecked {
+                challenge,
+                children: _,
+            } => UncheckedConjecture::CandUnchecked {
+                challenge,
+                children: new_children,
+            },
+            UncheckedConjecture::CorUnchecked {
+                challenge,
+                children: _,
+            } => UncheckedConjecture::CorUnchecked {
+                challenge,
+                children: new_children,
+            },
+        }
+    }
+
+    pub fn children_ust(&self) -> &[UncheckedSigmaTree] {
+        match self {
+            UncheckedConjecture::CandUnchecked {
+                challenge: _,
+                children,
+            } => children,
+            UncheckedConjecture::CorUnchecked {
+                challenge: _,
+                children,
+            } => children,
+        }
+    }
+
+    pub fn challenge(&self) -> Challenge {
+        match self {
+            UncheckedConjecture::CandUnchecked {
+                challenge,
+                children: _,
+            } => challenge.clone(),
+            UncheckedConjecture::CorUnchecked {
+                challenge,
+                children: _,
+            } => challenge.clone(),
+        }
+    }
+}
+
+impl ProofTreeConjecture for UncheckedConjecture {
+    fn conjecture_type(&self) -> ConjectureType {
+        match self {
+            UncheckedConjecture::CandUnchecked { .. } => ConjectureType::And,
+            UncheckedConjecture::CorUnchecked { .. } => ConjectureType::Or,
+        }
+    }
+
+    fn children(&self) -> Vec<ProofTree> {
+        match self {
+            UncheckedConjecture::CandUnchecked {
+                challenge: _,
+                children,
+            } => children
+                .iter()
+                .map(|ust| ust.clone().into())
+                .collect::<Vec<ProofTree>>(),
+            UncheckedConjecture::CorUnchecked {
+                challenge: _,
+                children,
+            } => children
+                .iter()
+                .map(|ust| ust.clone().into())
+                .collect::<Vec<ProofTree>>(),
+        }
+    }
+}
diff --git a/ergotree-interpreter/src/sigma_protocol/unproven_tree.rs b/ergotree-interpreter/src/sigma_protocol/unproven_tree.rs
index 5cdd52550..10bebdbd7 100644
--- a/ergotree-interpreter/src/sigma_protocol/unproven_tree.rs
+++ b/ergotree-interpreter/src/sigma_protocol/unproven_tree.rs
@@ -1,40 +1,150 @@
 //! Unproven tree types
 
-use super::{dlog_protocol::FirstDlogProverMessage, Challenge, FirstProverMessage, ProofTreeLeaf};
+use super::proof_tree::ConjectureType;
+use super::proof_tree::ProofTree;
+use super::proof_tree::ProofTreeConjecture;
+use super::proof_tree::ProofTreeKind;
+use super::{dlog_protocol::FirstDlogProverMessage, Challenge, FirstProverMessage};
+use crate::sigma_protocol::proof_tree::ProofTreeLeaf;
+use ergotree_ir::sigma_protocol::sigma_boolean::cand::Cand;
+use ergotree_ir::sigma_protocol::sigma_boolean::cor::Cor;
 use ergotree_ir::sigma_protocol::sigma_boolean::ProveDlog;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaBoolean;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaProofOfKnowledgeTree;
 use k256::Scalar;
 
+extern crate derive_more;
+use derive_more::From;
+
 /// Unproven trees
-pub enum UnprovenTree {
-    /// Unproven leaf
+#[derive(PartialEq, Debug, Clone, From)]
+pub(crate) enum UnprovenTree {
     UnprovenLeaf(UnprovenLeaf),
-    // UnprovenConjecture,
+    UnprovenConjecture(UnprovenConjecture),
 }
 
 impl UnprovenTree {
     /// Is real or simulated
-    pub fn is_real(&self) -> bool {
+    pub(crate) fn is_real(&self) -> bool {
+        !self.simulated()
+    }
+
+    pub(crate) fn simulated(&self) -> bool {
+        match self {
+            UnprovenTree::UnprovenLeaf(UnprovenLeaf::UnprovenSchnorr(us)) => us.simulated,
+            UnprovenTree::UnprovenConjecture(uc) => match uc {
+                UnprovenConjecture::CandUnproven(cand) => cand.simulated,
+                UnprovenConjecture::CorUnproven(cor) => cor.simulated,
+            },
+        }
+    }
+
+    pub(crate) fn with_position(self, updated: NodePosition) -> Self {
+        match self {
+            UnprovenTree::UnprovenLeaf(ul) => ul.with_position(updated).into(),
+            UnprovenTree::UnprovenConjecture(uc) => uc.with_position(updated).into(),
+        }
+    }
+
+    pub(crate) fn with_challenge(self, challenge: Challenge) -> Self {
+        match self {
+            UnprovenTree::UnprovenLeaf(ul) => ul.with_challenge(challenge).into(),
+            UnprovenTree::UnprovenConjecture(uc) => uc.with_challenge(challenge).into(),
+        }
+    }
+
+    pub(crate) fn with_simulated(self, simulated: bool) -> Self {
+        match self {
+            UnprovenTree::UnprovenLeaf(ul) => ul.with_simulated(simulated).into(),
+            UnprovenTree::UnprovenConjecture(uc) => uc.with_simulated(simulated).into(),
+        }
+    }
+
+    pub(crate) fn as_tree_kind(&self) -> ProofTreeKind {
+        match self {
+            UnprovenTree::UnprovenLeaf(ul) => ProofTreeKind::Leaf(ul),
+            UnprovenTree::UnprovenConjecture(uc) => ProofTreeKind::Conjecture(uc),
+        }
+    }
+
+    pub(crate) fn challenge(&self) -> Option<Challenge> {
+        match self {
+            UnprovenTree::UnprovenLeaf(ul) => ul.challenge(),
+            UnprovenTree::UnprovenConjecture(uc) => uc.challenge(),
+        }
+    }
+
+    pub(crate) fn position(&self) -> &NodePosition {
         match self {
-            UnprovenTree::UnprovenLeaf(UnprovenLeaf::UnprovenSchnorr(us)) => !us.simulated,
-            // UnprovenTree::UnprovenConjecture => todo!(),
+            UnprovenTree::UnprovenLeaf(ul) => ul.position(),
+            UnprovenTree::UnprovenConjecture(uc) => uc.position(),
         }
     }
 }
 
-impl<T: Into<UnprovenLeaf>> From<T> for UnprovenTree {
-    fn from(t: T) -> Self {
-        UnprovenTree::UnprovenLeaf(t.into())
+impl From<UnprovenSchnorr> for UnprovenTree {
+    fn from(v: UnprovenSchnorr) -> Self {
+        UnprovenTree::UnprovenLeaf(v.into())
+    }
+}
+
+impl From<CandUnproven> for UnprovenTree {
+    fn from(v: CandUnproven) -> Self {
+        UnprovenTree::UnprovenConjecture(v.into())
+    }
+}
+
+impl From<CorUnproven> for UnprovenTree {
+    fn from(v: CorUnproven) -> Self {
+        UnprovenTree::UnprovenConjecture(v.into())
     }
 }
 
 /// Unproven leaf types
-pub enum UnprovenLeaf {
+#[derive(PartialEq, Debug, Clone, From)]
+pub(crate) enum UnprovenLeaf {
     /// Unproven Schnorr
     UnprovenSchnorr(UnprovenSchnorr),
 }
 
+impl UnprovenLeaf {
+    fn with_position(self, updated: NodePosition) -> Self {
+        match self {
+            UnprovenLeaf::UnprovenSchnorr(us) => us.with_position(updated).into(),
+        }
+    }
+
+    fn with_challenge(self, challenge: Challenge) -> Self {
+        match self {
+            UnprovenLeaf::UnprovenSchnorr(us) => us.with_challenge(challenge).into(),
+        }
+    }
+
+    fn with_simulated(self, simulated: bool) -> Self {
+        match self {
+            UnprovenLeaf::UnprovenSchnorr(us) => us.with_simulated(simulated).into(),
+        }
+    }
+
+    pub(crate) fn is_real(&self) -> bool {
+        match self {
+            UnprovenLeaf::UnprovenSchnorr(us) => us.is_real(),
+        }
+    }
+
+    pub(crate) fn challenge(&self) -> Option<Challenge> {
+        match self {
+            UnprovenLeaf::UnprovenSchnorr(us) => us.challenge_opt.clone(),
+        }
+    }
+
+    pub(crate) fn position(&self) -> &NodePosition {
+        match self {
+            UnprovenLeaf::UnprovenSchnorr(us) => &us.position,
+        }
+    }
+}
+
 impl ProofTreeLeaf for UnprovenLeaf {
     fn proposition(&self) -> SigmaBoolean {
         match self {
@@ -51,18 +161,214 @@ impl ProofTreeLeaf for UnprovenLeaf {
     }
 }
 
-impl From<UnprovenSchnorr> for UnprovenLeaf {
-    fn from(us: UnprovenSchnorr) -> Self {
-        UnprovenLeaf::UnprovenSchnorr(us)
+#[derive(PartialEq, Debug, Clone, From)]
+pub(crate) enum UnprovenConjecture {
+    CandUnproven(CandUnproven),
+    CorUnproven(CorUnproven),
+}
+
+impl UnprovenConjecture {
+    pub(crate) fn children(&self) -> Vec<ProofTree> {
+        match self {
+            UnprovenConjecture::CandUnproven(cand) => cand.children.clone(),
+            UnprovenConjecture::CorUnproven(cor) => cor.children.clone(),
+        }
+    }
+
+    pub(crate) fn position(&self) -> &NodePosition {
+        match self {
+            UnprovenConjecture::CandUnproven(cand) => &cand.position,
+            UnprovenConjecture::CorUnproven(cor) => &cor.position,
+        }
+    }
+
+    fn challenge(&self) -> Option<Challenge> {
+        match self {
+            UnprovenConjecture::CandUnproven(cand) => cand.challenge_opt.clone(),
+            UnprovenConjecture::CorUnproven(cor) => cor.challenge_opt.clone(),
+        }
+    }
+
+    fn with_position(self, updated: NodePosition) -> Self {
+        match self {
+            UnprovenConjecture::CandUnproven(cand) => cand.with_position(updated).into(),
+            UnprovenConjecture::CorUnproven(cor) => cor.with_position(updated).into(),
+        }
+    }
+
+    fn with_challenge(self, challenge: Challenge) -> Self {
+        match self {
+            UnprovenConjecture::CandUnproven(cand) => cand.with_challenge(challenge).into(),
+            UnprovenConjecture::CorUnproven(cor) => cor.with_challenge(challenge).into(),
+        }
+    }
+
+    fn with_simulated(self, simulated: bool) -> Self {
+        match self {
+            UnprovenConjecture::CandUnproven(cand) => cand.with_simulated(simulated).into(),
+            UnprovenConjecture::CorUnproven(cor) => cor.with_simulated(simulated).into(),
+        }
+    }
+}
+
+impl ProofTreeConjecture for UnprovenConjecture {
+    fn conjecture_type(&self) -> ConjectureType {
+        match self {
+            UnprovenConjecture::CandUnproven(_) => ConjectureType::And,
+            UnprovenConjecture::CorUnproven(_) => ConjectureType::Or,
+        }
+    }
+
+    fn children(&self) -> Vec<ProofTree> {
+        match self {
+            UnprovenConjecture::CandUnproven(cand) => cand.children.clone(),
+            UnprovenConjecture::CorUnproven(cor) => cor.children.clone(),
+        }
+    }
+}
+
+#[derive(PartialEq, Debug, Clone)]
+pub(crate) struct UnprovenSchnorr {
+    pub(crate) proposition: ProveDlog,
+    pub(crate) commitment_opt: Option<FirstDlogProverMessage>,
+    pub(crate) randomness_opt: Option<Scalar>,
+    pub(crate) challenge_opt: Option<Challenge>,
+    pub(crate) simulated: bool,
+    pub(crate) position: NodePosition,
+}
+
+impl UnprovenSchnorr {
+    fn with_position(self, updated: NodePosition) -> Self {
+        UnprovenSchnorr {
+            position: updated,
+            ..self
+        }
+    }
+
+    fn with_challenge(self, challenge: Challenge) -> Self {
+        UnprovenSchnorr {
+            challenge_opt: Some(challenge),
+            ..self
+        }
+    }
+
+    fn with_simulated(self, simulated: bool) -> Self {
+        UnprovenSchnorr { simulated, ..self }
+    }
+
+    pub(crate) fn is_real(&self) -> bool {
+        !self.simulated
+    }
+}
+
+/// Data type which encodes position of a node in a tree.
+///
+/// Position is encoded like following (the example provided is for CTHRESHOLD(2, Seq(pk1, pk2, pk3 && pk4)) :
+///
+/// r#"
+///            0
+///          / | \
+///         /  |  \
+///       0-0 0-1 0-2
+///               /|
+///              / |
+///             /  |
+///            /   |
+///          0-2-0 0-2-1
+/// "#;
+///
+/// So a hint associated with pk1 has a position "0-0", pk4 - "0-2-1" .
+///
+/// Please note that "0" prefix is for a crypto tree. There are several kinds of trees during evaluation.
+/// Initial mixed tree (ergoTree) would have another prefix.
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct NodePosition {
+    /// positions from root (inclusive) in top-down order
+    positions: Vec<usize>,
+}
+
+impl NodePosition {
+    pub fn crypto_tree_prefix() -> Self {
+        NodePosition { positions: vec![0] }
+    }
+
+    pub fn child(&self, child_idx: usize) -> NodePosition {
+        let mut positions = self.positions.clone();
+        positions.push(child_idx);
+        NodePosition { positions }
     }
 }
 
-#[allow(missing_docs)]
 #[derive(PartialEq, Debug, Clone)]
-pub struct UnprovenSchnorr {
-    pub proposition: ProveDlog,
-    pub commitment_opt: Option<FirstDlogProverMessage>,
-    pub randomness_opt: Option<Scalar>,
-    pub challenge_opt: Option<Challenge>,
-    pub simulated: bool,
+pub(crate) struct CandUnproven {
+    pub(crate) proposition: Cand,
+    pub(crate) challenge_opt: Option<Challenge>,
+    pub(crate) simulated: bool,
+    pub(crate) children: Vec<ProofTree>,
+    pub(crate) position: NodePosition,
+}
+
+impl CandUnproven {
+    pub(crate) fn is_real(&self) -> bool {
+        !self.simulated
+    }
+
+    fn with_position(self, updated: NodePosition) -> Self {
+        CandUnproven {
+            position: updated,
+            ..self
+        }
+    }
+
+    fn with_challenge(self, challenge: Challenge) -> Self {
+        CandUnproven {
+            challenge_opt: Some(challenge),
+            ..self
+        }
+    }
+
+    fn with_simulated(self, simulated: bool) -> Self {
+        Self { simulated, ..self }
+    }
+
+    pub(crate) fn with_children(self, children: Vec<ProofTree>) -> Self {
+        CandUnproven { children, ..self }
+    }
+}
+
+#[derive(PartialEq, Debug, Clone)]
+pub(crate) struct CorUnproven {
+    pub(crate) proposition: Cor,
+    pub(crate) challenge_opt: Option<Challenge>,
+    pub(crate) simulated: bool,
+    pub(crate) children: Vec<ProofTree>,
+    pub(crate) position: NodePosition,
+}
+
+impl CorUnproven {
+    pub(crate) fn is_real(&self) -> bool {
+        !self.simulated
+    }
+
+    fn with_position(self, updated: NodePosition) -> Self {
+        Self {
+            position: updated,
+            ..self
+        }
+    }
+
+    fn with_challenge(self, challenge: Challenge) -> Self {
+        Self {
+            challenge_opt: Some(challenge),
+            ..self
+        }
+    }
+
+    fn with_simulated(self, simulated: bool) -> Self {
+        Self { simulated, ..self }
+    }
+
+    pub(crate) fn with_children(self, children: Vec<ProofTree>) -> Self {
+        Self { children, ..self }
+    }
 }
diff --git a/ergotree-interpreter/src/sigma_protocol/verifier.rs b/ergotree-interpreter/src/sigma_protocol/verifier.rs
index feeab11d3..38f1e54ca 100644
--- a/ergotree-interpreter/src/sigma_protocol/verifier.rs
+++ b/ergotree-interpreter/src/sigma_protocol/verifier.rs
@@ -2,7 +2,9 @@
 
 use std::rc::Rc;
 
+use super::fiat_shamir::FiatShamirTreeSerializationError;
 use super::prover::ProofBytes;
+use super::sig_serializer::SigParsingError;
 use super::{
     dlog_protocol,
     fiat_shamir::{fiat_shamir_hash_fn, fiat_shamir_tree_to_bytes},
@@ -17,25 +19,27 @@ use dlog_protocol::FirstDlogProverMessage;
 use ergotree_ir::ergo_tree::ErgoTree;
 use ergotree_ir::ergo_tree::ErgoTreeParsingError;
 
+use derive_more::From;
+use thiserror::Error;
+
 /// Errors on proof verification
-#[derive(PartialEq, Eq, Debug, Clone)]
+#[derive(Error, PartialEq, Eq, Debug, Clone, From)]
 pub enum VerifierError {
     /// Failed to parse ErgoTree from bytes
+    #[error("ErgoTreeError: {0}")]
     ErgoTreeError(ErgoTreeParsingError),
     /// Failed to evaluate ErgoTree
+    #[error("EvalError: {0}")]
     EvalError(EvalError),
-}
-
-impl From<ErgoTreeParsingError> for VerifierError {
-    fn from(err: ErgoTreeParsingError) -> Self {
-        VerifierError::ErgoTreeError(err)
-    }
-}
-
-impl From<EvalError> for VerifierError {
-    fn from(err: EvalError) -> Self {
-        VerifierError::EvalError(err)
-    }
+    /// Signature parsing error
+    #[error("SigParsingError: {0}")]
+    SigParsingError(SigParsingError),
+    /// Unexpected value encountered
+    #[error("Unexpected: {0}")]
+    Unexpected(String),
+    /// Error while tree serialization for Fiat-Shamir hash
+    #[error("Fiat-Shamir tree serialization error: {0}")]
+    FiatShamirTreeSerializationError(FiatShamirTreeSerializationError),
 }
 
 /// Result of Box.ergoTree verification procedure (see `verify` method).
@@ -57,7 +61,7 @@ pub trait Verifier: Evaluator {
         tree: &ErgoTree,
         env: &Env,
         ctx: Rc<Context>,
-        proof: &ProofBytes,
+        proof: ProofBytes,
         message: &[u8],
     ) -> Result<VerificationResult, VerifierError> {
         let expr = tree.proposition()?;
@@ -66,21 +70,12 @@ pub trait Verifier: Evaluator {
             SigmaBoolean::TrivialProp(b) => b,
             sb => {
                 // Perform Verifier Steps 1-3
-                match parse_sig_compute_challenges(sb, proof) {
-                    Err(_) => false,
-                    Ok(UncheckedTree::UncheckedSigmaTree(sp)) => {
-                        // Perform Verifier Step 4
-                        let new_root = compute_commitments(sp);
-                        // Verifier Steps 5-6: Convert the tree to a string `s` for input to the Fiat-Shamir hash function,
-                        // using the same conversion as the prover in 7
-                        // Accept the proof if the challenge at the root of the tree is equal to the Fiat-Shamir hash of `s`
-                        // (and, if applicable,  the associated data). Reject otherwise.
-                        let mut s = fiat_shamir_tree_to_bytes(&new_root.clone().into());
-                        s.append(&mut message.to_vec());
-                        let expected_challenge = fiat_shamir_hash_fn(s.as_slice());
-                        new_root.challenge() == expected_challenge.into()
+                match parse_sig_compute_challenges(&sb, proof)? {
+                    UncheckedTree::UncheckedSigmaTree(sp) => {
+                        // Perform Verifier Steps 4-6
+                        check_commitments(sp, message)?
                     }
-                    Ok(_) => todo!(),
+                    UncheckedTree::NoProof => false,
                 }
             }
         };
@@ -91,26 +86,48 @@ pub trait Verifier: Evaluator {
     }
 }
 
-/**
- * Verifier Step 4: For every leaf node, compute the commitment a from the challenge e and response $z$,
- * per the verifier algorithm of the leaf's Sigma-protocol.
- * If the verifier algorithm of the Sigma-protocol for any of the leaves rejects, then reject the entire proof.
- */
+/// Perform Verifier Steps 4-6
+fn check_commitments(sp: UncheckedSigmaTree, message: &[u8]) -> Result<bool, VerifierError> {
+    // Perform Verifier Step 4
+    let new_root = compute_commitments(sp);
+    let mut s = fiat_shamir_tree_to_bytes(&new_root.clone().into())?;
+    s.append(&mut message.to_vec());
+    // Verifier Steps 5-6: Convert the tree to a string `s` for input to the Fiat-Shamir hash function,
+    // using the same conversion as the prover in 7
+    // Accept the proof if the challenge at the root of the tree is equal to the Fiat-Shamir hash of `s`
+    // (and, if applicable,  the associated data). Reject otherwise.
+    let expected_challenge = fiat_shamir_hash_fn(s.as_slice());
+    Ok(new_root.challenge() == expected_challenge.into())
+}
+
+/// Verifier Step 4: For every leaf node, compute the commitment a from the challenge e and response $z$,
+/// per the verifier algorithm of the leaf's Sigma-protocol.
+/// If the verifier algorithm of the Sigma-protocol for any of the leaves rejects, then reject the entire proof.
 fn compute_commitments(sp: UncheckedSigmaTree) -> UncheckedSigmaTree {
     match sp {
-        UncheckedSigmaTree::UncheckedLeaf(UncheckedLeaf::UncheckedSchnorr(sn)) => {
-            let a = dlog_protocol::interactive_prover::compute_commitment(
-                &sn.proposition,
-                &sn.challenge,
-                &sn.second_message,
-            );
-            UncheckedSchnorr {
-                commitment_opt: Some(FirstDlogProverMessage(a)),
-                ..sn
+        UncheckedSigmaTree::UncheckedLeaf(leaf) => match leaf {
+            UncheckedLeaf::UncheckedSchnorr(sn) => {
+                let a = dlog_protocol::interactive_prover::compute_commitment(
+                    &sn.proposition,
+                    &sn.challenge,
+                    &sn.second_message,
+                );
+                UncheckedSchnorr {
+                    commitment_opt: Some(FirstDlogProverMessage(a)),
+                    ..sn
+                }
+                .into()
             }
-            .into()
-        }
-        UncheckedSigmaTree::UncheckedConjecture => todo!(),
+        },
+        UncheckedSigmaTree::UncheckedConjecture(conj) => conj
+            .clone()
+            .with_children(
+                conj.children_ust()
+                    .iter()
+                    .map(|c| compute_commitments(c.clone()))
+                    .collect(),
+            )
+            .into(),
     }
 }
 
@@ -120,38 +137,513 @@ pub struct TestVerifier;
 impl Evaluator for TestVerifier {}
 impl Verifier for TestVerifier {}
 
+#[allow(clippy::unwrap_used)]
 #[cfg(test)]
 #[cfg(feature = "arbitrary")]
 mod tests {
     use super::*;
+    use crate::sigma_protocol::prover::hint::HintsBag;
     use crate::sigma_protocol::{
         private_input::{DlogProverInput, PrivateInput},
         prover::{Prover, TestProver},
     };
     use ergotree_ir::mir::expr::Expr;
+    use ergotree_ir::mir::sigma_and::SigmaAnd;
+    use ergotree_ir::mir::sigma_or::SigmaOr;
+    use ergotree_ir::serialization::SigmaSerializable;
+    use num_bigint::BigUint;
+    use proptest::collection::vec;
     use proptest::prelude::*;
     use sigma_test_util::force_any_val;
     use std::rc::Rc;
 
+    fn proof_append_byte(proof: &ProofBytes) -> ProofBytes {
+        match proof {
+            ProofBytes::Empty => panic!(),
+            ProofBytes::Some(bytes) => {
+                let mut new_bytes = bytes.clone();
+                new_bytes.push(1u8);
+                ProofBytes::Some(new_bytes)
+            }
+        }
+    }
+
     proptest! {
 
-        #![proptest_config(ProptestConfig::with_cases(16))]
+        #![proptest_config(ProptestConfig::with_cases(4))]
 
         #[test]
-        fn test_prover_verifier_p2pk(secret in any::<DlogProverInput>(), message in any::<Vec<u8>>()) {
-            prop_assume!(!message.is_empty());
+        fn test_prover_verifier_p2pk(secret in any::<DlogProverInput>(), message in vec(any::<u8>(), 100..200)) {
             let pk = secret.public_image();
             let tree = ErgoTree::from(Expr::Const(pk.into()));
 
             let prover = TestProver {
                 secrets: vec![PrivateInput::DlogProverInput(secret)],
             };
-            let res = prover.prove(&tree, &Env::empty(), Rc::new(force_any_val::<Context>()), message.as_slice());
+            let res = prover.prove(&tree,
+                &Env::empty(),
+                Rc::new(force_any_val::<Context>()),
+                message.as_slice(),
+                &HintsBag::empty());
             let proof = res.unwrap().proof;
+            let verifier = TestVerifier;
+            prop_assert_eq!(verifier.verify(&tree,
+                                            &Env::empty(),
+                                            Rc::new(force_any_val::<Context>()),
+                                            proof.clone(),
+                                            message.as_slice())
+                            .unwrap().result,
+                            true);
 
+            // possible to append bytes
+            prop_assert_eq!(verifier.verify(&tree,
+                                            &Env::empty(),
+                                            Rc::new(force_any_val::<Context>()),
+                                            proof_append_byte(&proof),
+                                            message.as_slice())
+                            .unwrap().result,
+                            true);
+
+            // wrong message
+            prop_assert_eq!(verifier.verify(&tree,
+                                            &Env::empty(),
+                                            Rc::new(force_any_val::<Context>()),
+                                            proof,
+                                            vec![1u8; 100].as_slice())
+                            .unwrap().result,
+                            false);
+        }
+
+        #[test]
+        fn test_prover_verifier_conj_and(secret1 in any::<DlogProverInput>(),
+                                         secret2 in any::<DlogProverInput>(),
+                                         message in vec(any::<u8>(), 100..200)) {
+            let pk1 = secret1.public_image();
+            let pk2 = secret2.public_image();
+            let expr: Expr = SigmaAnd::new(vec![Expr::Const(pk1.into()), Expr::Const(pk2.into())])
+                .unwrap()
+                .into();
+            let tree = ErgoTree::from(expr);
+            let prover = TestProver {
+                secrets: vec![PrivateInput::DlogProverInput(secret1), PrivateInput::DlogProverInput(secret2)],
+            };
+            let res = prover.prove(&tree,
+                &Env::empty(),
+                Rc::new(force_any_val::<Context>()),
+                message.as_slice(),
+                &HintsBag::empty());
+            let proof = res.unwrap().proof;
             let verifier = TestVerifier;
-            let ver_res = verifier.verify(&tree, &Env::empty(), Rc::new(force_any_val::<Context>()),  &proof, message.as_slice());
+            let ver_res = verifier.verify(&tree,
+                                          &Env::empty(),
+                                          Rc::new(force_any_val::<Context>()),
+                                          proof,
+                                          message.as_slice());
             prop_assert_eq!(ver_res.unwrap().result, true);
         }
+
+        #[test]
+        fn test_prover_verifier_conj_and_and(secret1 in any::<DlogProverInput>(),
+                                             secret2 in any::<DlogProverInput>(),
+                                             secret3 in any::<DlogProverInput>(),
+                                             message in vec(any::<u8>(), 100..200)) {
+            let pk1 = secret1.public_image();
+            let pk2 = secret2.public_image();
+            let pk3 = secret3.public_image();
+            let expr: Expr = SigmaAnd::new(vec![
+                Expr::Const(pk1.into()),
+                SigmaAnd::new(vec![Expr::Const(pk2.into()), Expr::Const(pk3.into())])
+                    .unwrap()
+                    .into(),
+            ]).unwrap().into();
+            let tree = ErgoTree::from(expr);
+            let prover = TestProver {
+                secrets: vec![PrivateInput::DlogProverInput(secret1),
+                    PrivateInput::DlogProverInput(secret2),
+                    PrivateInput::DlogProverInput(secret3)
+                ],
+            };
+            let res = prover.prove(&tree,
+                &Env::empty(),
+                Rc::new(force_any_val::<Context>()),
+                message.as_slice(),
+                &HintsBag::empty());
+            let proof = res.unwrap().proof;
+            let verifier = TestVerifier;
+            let ver_res = verifier.verify(&tree,
+                                          &Env::empty(),
+                                          Rc::new(force_any_val::<Context>()),
+                                          proof,
+                                          message.as_slice());
+            prop_assert_eq!(ver_res.unwrap().result, true);
+        }
+
+        #[test]
+        fn test_prover_verifier_conj_or(secret1 in any::<DlogProverInput>(),
+                                         secret2 in any::<DlogProverInput>(),
+                                         message in vec(any::<u8>(), 100..200)) {
+            let pk1 = secret1.public_image();
+            let pk2 = secret2.public_image();
+            let expr: Expr = SigmaOr::new(vec![Expr::Const(pk1.into()), Expr::Const(pk2.into())])
+                .unwrap()
+                .into();
+            let tree = ErgoTree::from(expr);
+            let secrets = vec![PrivateInput::DlogProverInput(secret1), PrivateInput::DlogProverInput(secret2)];
+            // any secret (out of 2) known to prover should be enough
+            for secret in secrets {
+                let prover = TestProver {
+                    secrets: vec![secret.clone()],
+                };
+                let res = prover.prove(&tree,
+                    &Env::empty(),
+                    Rc::new(force_any_val::<Context>()),
+                    message.as_slice(),
+                    &HintsBag::empty());
+                let proof = res.unwrap().proof;
+                let verifier = TestVerifier;
+                let ver_res = verifier.verify(&tree,
+                                              &Env::empty(),
+                                              Rc::new(force_any_val::<Context>()),
+                                              proof,
+                                              message.as_slice());
+                prop_assert_eq!(ver_res.unwrap().result, true, "verify failed on secret: {:?}", &secret);
+            }
+        }
+
+        #[test]
+        fn test_prover_verifier_conj_or_or(secret1 in any::<DlogProverInput>(),
+                                             secret2 in any::<DlogProverInput>(),
+                                             secret3 in any::<DlogProverInput>(),
+                                             message in vec(any::<u8>(), 100..200)) {
+            let pk1 = secret1.public_image();
+            let pk2 = secret2.public_image();
+            let pk3 = secret3.public_image();
+            let expr: Expr = SigmaOr::new(vec![
+                Expr::Const(pk1.into()),
+                SigmaOr::new(vec![Expr::Const(pk2.into()), Expr::Const(pk3.into())])
+                    .unwrap()
+                    .into(),
+            ]).unwrap().into();
+            let tree = ErgoTree::from(expr);
+            let secrets = vec![
+                PrivateInput::DlogProverInput(secret1),
+                PrivateInput::DlogProverInput(secret2),
+                PrivateInput::DlogProverInput(secret3)
+            ];
+            // any secret (out of 3) known to prover should be enough
+            for secret in secrets {
+                let prover = TestProver {
+                    secrets: vec![secret.clone()],
+                };
+                let res = prover.prove(&tree,
+                    &Env::empty(),
+                    Rc::new(force_any_val::<Context>()),
+                    message.as_slice(),
+                    &HintsBag::empty());
+                let proof = res.unwrap().proof;
+                let verifier = TestVerifier;
+                let ver_res = verifier.verify(&tree,
+                                              &Env::empty(),
+                                              Rc::new(force_any_val::<Context>()),
+                                              proof,
+                                              message.as_slice());
+                prop_assert_eq!(ver_res.unwrap().result, true, "verify failed on secret: {:?}", &secret);
+            }
+        }
+    }
+
+    #[test]
+    fn sig_test_vector_provedlog() {
+        // test vector data from
+        // https://github.com/ScorexFoundation/sigmastate-interpreter/blob/6c51c13f7a494a191a7ea5645e56b04fb46a418d/sigmastate/src/test/scala/sigmastate/crypto/SigningSpecification.scala#L14-L30
+        let msg =
+            base16::decode(b"1dc01772ee0171f5f614c673e3c7fa1107a8cf727bdf5a6dadb379e93c0d1d00")
+                .unwrap();
+        let sk = DlogProverInput::from_biguint(
+            BigUint::parse_bytes(
+                b"109749205800194830127901595352600384558037183218698112947062497909408298157746",
+                10,
+            )
+            .unwrap(),
+        )
+        .unwrap();
+        let signature = base16::decode(b"bcb866ba434d5c77869ddcbc3f09ddd62dd2d2539bf99076674d1ae0c32338ea95581fdc18a3b66789904938ac641eba1a66d234070207a2").unwrap();
+
+        // check expected public key
+        assert_eq!(
+            base16::encode_lower(&sk.public_image().sigma_serialize_bytes()),
+            "03cb0d49e4eae7e57059a3da8ac52626d26fc11330af8fb093fa597d8b93deb7b1"
+        );
+
+        let expr: Expr = sk.public_image().into();
+        let verifier = TestVerifier;
+        let ver_res = verifier.verify(
+            &expr.into(),
+            &Env::empty(),
+            Rc::new(force_any_val::<Context>()),
+            signature.into(),
+            msg.as_slice(),
+        );
+        assert_eq!(ver_res.unwrap().result, true);
+    }
+
+    #[test]
+    fn sig_test_vector_conj_and() {
+        // corresponding sigmastate test
+        // in SigningSpecification.property("AND signature test vector")
+        let msg =
+            base16::decode(b"1dc01772ee0171f5f614c673e3c7fa1107a8cf727bdf5a6dadb379e93c0d1d00")
+                .unwrap();
+        let sk1 = DlogProverInput::from_biguint(
+            BigUint::parse_bytes(
+                b"109749205800194830127901595352600384558037183218698112947062497909408298157746",
+                10,
+            )
+            .unwrap(),
+        )
+        .unwrap();
+        let sk2 = DlogProverInput::from_biguint(
+            BigUint::parse_bytes(
+                b"50415569076448343263191022044468203756975150511337537963383000142821297891310",
+                10,
+            )
+            .unwrap(),
+        )
+        .unwrap();
+
+        let signature = base16::decode(b"9b2ebb226be42df67817e9c56541de061997c3ea84e7e72dbb69edb7318d7bb525f9c16ccb1adc0ede4700a046d0a4ab1e239245460c1ba45e5637f7a2d4cc4cc460e5895125be73a2ca16091db2dcf51d3028043c2b9340").unwrap();
+
+        let expr: Expr = SigmaAnd::new(vec![
+            Expr::Const(sk1.public_image().into()),
+            Expr::Const(sk2.public_image().into()),
+        ])
+        .unwrap()
+        .into();
+        let tree: ErgoTree = expr.into();
+
+        // let prover = TestProver {
+        //     secrets: vec![sk1.into(), sk2.into()],
+        // };
+        // let res = prover.prove(
+        //     &tree,
+        //     &Env::empty(),
+        //     Rc::new(force_any_val::<Context>()),
+        //     msg.as_slice(),
+        //     &HintsBag::empty(),
+        // );
+        // let proof: Vec<u8> = res.unwrap().proof.into();
+        // dbg!(base16::encode_lower(&proof));
+
+        let verifier = TestVerifier;
+        let ver_res = verifier.verify(
+            &tree,
+            &Env::empty(),
+            Rc::new(force_any_val::<Context>()),
+            signature.into(),
+            msg.as_slice(),
+        );
+        assert_eq!(ver_res.unwrap().result, true);
+    }
+
+    #[test]
+    fn sig_test_vector_conj_or() {
+        // corresponding sigmastate test
+        // in SigningSpecification.property("OR signature test vector")
+        let msg =
+            base16::decode(b"1dc01772ee0171f5f614c673e3c7fa1107a8cf727bdf5a6dadb379e93c0d1d00")
+                .unwrap();
+        let sk1 = DlogProverInput::from_biguint(
+            BigUint::parse_bytes(
+                b"109749205800194830127901595352600384558037183218698112947062497909408298157746",
+                10,
+            )
+            .unwrap(),
+        )
+        .unwrap();
+        let sk2 = DlogProverInput::from_biguint(
+            BigUint::parse_bytes(
+                b"50415569076448343263191022044468203756975150511337537963383000142821297891310",
+                10,
+            )
+            .unwrap(),
+        )
+        .unwrap();
+
+        let signature = base16::decode(b"ec94d2d5ef0e1e638237f53fd883c339f9771941f70020742a7dc85130aaee535c61321aa1e1367befb500256567b3e6f9c7a3720baa75ba6056305d7595748a93f23f9fc0eb9c1aaabc24acc4197030834d76d3c95ede60c5b59b4b306cd787d010e8217f34677d046646778877c669").unwrap();
+
+        let expr: Expr = SigmaOr::new(vec![
+            Expr::Const(sk1.public_image().into()),
+            Expr::Const(sk2.public_image().into()),
+        ])
+        .unwrap()
+        .into();
+        let tree: ErgoTree = expr.into();
+
+        // let prover = TestProver {
+        //     secrets: vec![sk1.into()],
+        // };
+        // let res = prover.prove(
+        //     &tree,
+        //     &Env::empty(),
+        //     Rc::new(force_any_val::<Context>()),
+        //     msg.as_slice(),
+        //     &HintsBag::empty(),
+        // );
+        // let proof: Vec<u8> = res.unwrap().proof.into();
+        // dbg!(base16::encode_lower(&proof));
+
+        let verifier = TestVerifier;
+        let ver_res = verifier.verify(
+            &tree,
+            &Env::empty(),
+            Rc::new(force_any_val::<Context>()),
+            signature.into(),
+            msg.as_slice(),
+        );
+        assert_eq!(ver_res.unwrap().result, true);
+    }
+
+    #[test]
+    fn sig_test_vector_conj_and_or() {
+        // corresponding sigmastate test
+        // in SigningSpecification.property("AND with OR signature test vector")
+        let msg =
+            base16::decode(b"1dc01772ee0171f5f614c673e3c7fa1107a8cf727bdf5a6dadb379e93c0d1d00")
+                .unwrap();
+        let sk1 = DlogProverInput::from_biguint(
+            BigUint::parse_bytes(
+                b"109749205800194830127901595352600384558037183218698112947062497909408298157746",
+                10,
+            )
+            .unwrap(),
+        )
+        .unwrap();
+        let sk2 = DlogProverInput::from_biguint(
+            BigUint::parse_bytes(
+                b"50415569076448343263191022044468203756975150511337537963383000142821297891310",
+                10,
+            )
+            .unwrap(),
+        )
+        .unwrap();
+
+        let sk3 = DlogProverInput::from_biguint(
+            BigUint::parse_bytes(
+                b"34648336872573478681093104997365775365807654884817677358848426648354905397359",
+                10,
+            )
+            .unwrap(),
+        )
+        .unwrap();
+
+        let signature = base16::decode(b"397e005d85c161990d0e44853fbf14951ff76e393fe1939bb48f68e852cd5af028f6c7eaaed587f6d5435891a564d8f9a77288773ce5b526a670ab0278aa4278891db53a9842df6fba69f95f6d55cfe77dd7b4bdccc1a3378ac4524b51598cb813258f64c94e98c3ef891a6eb8cbfd2e527a9038ca50b5bb50058de55a859a169628e6ae5ba4cb0332c694e450782d6f").unwrap();
+
+        let expr: Expr = SigmaAnd::new(vec![
+            Expr::Const(sk1.public_image().into()),
+            SigmaOr::new(vec![
+                Expr::Const(sk2.public_image().into()),
+                Expr::Const(sk3.public_image().into()),
+            ])
+            .unwrap()
+            .into(),
+        ])
+        .unwrap()
+        .into();
+        let tree: ErgoTree = expr.into();
+
+        // let prover = TestProver {
+        //     secrets: vec![sk1.into(), sk2.into()],
+        // };
+        // let res = prover.prove(
+        //     &tree,
+        //     &Env::empty(),
+        //     Rc::new(force_any_val::<Context>()),
+        //     msg.as_slice(),
+        //     &HintsBag::empty(),
+        // );
+        // let proof: Vec<u8> = res.unwrap().proof.into();
+        // dbg!(base16::encode_lower(&proof));
+
+        let verifier = TestVerifier;
+        let ver_res = verifier.verify(
+            &tree,
+            &Env::empty(),
+            Rc::new(force_any_val::<Context>()),
+            signature.into(),
+            msg.as_slice(),
+        );
+        assert_eq!(ver_res.unwrap().result, true);
+    }
+
+    #[test]
+    fn sig_test_vector_conj_or_and() {
+        // corresponding sigmastate test
+        // in SigningSpecification.property("OR with AND signature test vector")
+        let msg =
+            base16::decode(b"1dc01772ee0171f5f614c673e3c7fa1107a8cf727bdf5a6dadb379e93c0d1d00")
+                .unwrap();
+        let sk1 = DlogProverInput::from_biguint(
+            BigUint::parse_bytes(
+                b"109749205800194830127901595352600384558037183218698112947062497909408298157746",
+                10,
+            )
+            .unwrap(),
+        )
+        .unwrap();
+        let sk2 = DlogProverInput::from_biguint(
+            BigUint::parse_bytes(
+                b"50415569076448343263191022044468203756975150511337537963383000142821297891310",
+                10,
+            )
+            .unwrap(),
+        )
+        .unwrap();
+
+        let sk3 = DlogProverInput::from_biguint(
+            BigUint::parse_bytes(
+                b"34648336872573478681093104997365775365807654884817677358848426648354905397359",
+                10,
+            )
+            .unwrap(),
+        )
+        .unwrap();
+
+        let signature = base16::decode(b"a58b251be319a9656c21876b1136a59f42b18835dec6076c92f7a925ba28d2030218c177ab07563003eff5250cfafeb631ef610f4d710ab8e821bf632203adf23f4376580eaa17ddb36c0138f73a88551f45d92cde2b66dfbb5906c02e4d48106ff08be4a2fc29ec242f495468692f9ddeeb029dc5d8f38e2649cf09c44b67cbcfb3de4202026fb84d23ce2b4ff0f69b").unwrap();
+
+        let expr: Expr = SigmaOr::new(vec![
+            Expr::Const(sk1.public_image().into()),
+            SigmaAnd::new(vec![
+                Expr::Const(sk2.public_image().into()),
+                Expr::Const(sk3.public_image().into()),
+            ])
+            .unwrap()
+            .into(),
+        ])
+        .unwrap()
+        .into();
+        let tree: ErgoTree = expr.into();
+
+        // let prover = TestProver {
+        //     secrets: vec![sk1.into(), sk2.into()],
+        // };
+        // let res = prover.prove(
+        //     &tree,
+        //     &Env::empty(),
+        //     Rc::new(force_any_val::<Context>()),
+        //     msg.as_slice(),
+        //     &HintsBag::empty(),
+        // );
+        // let proof: Vec<u8> = res.unwrap().proof.into();
+        // dbg!(base16::encode_lower(&proof));
+
+        let verifier = TestVerifier;
+        let ver_res = verifier.verify(
+            &tree,
+            &Env::empty(),
+            Rc::new(force_any_val::<Context>()),
+            signature.into(),
+            msg.as_slice(),
+        );
+        assert_eq!(ver_res.unwrap().result, true);
     }
 }
diff --git a/ergotree-ir/Cargo.toml b/ergotree-ir/Cargo.toml
index 14fdbeb8b..1e03df34b 100644
--- a/ergotree-ir/Cargo.toml
+++ b/ergotree-ir/Cargo.toml
@@ -16,8 +16,8 @@ crate-type = ["cdylib", "rlib"]
 [dependencies]
 sigma-ser = { version = "^0.2.0", path = "../sigma-ser" }
 sigma-util = { version = "^0.2.0", path = "../sigma-util" }
-k256 = { version = "0.4.2", features = ["rand", "zeroize"] }
-elliptic-curve = {version = "0.5.0", features = ["rand", "zeroize"]}
+k256 = { version = "0.7.2", features = ["zeroize", "arithmetic", "ecdsa"] }
+elliptic-curve = {version = "0.9.12", features = ["zeroize"]}
 thiserror = "1"
 rand = "0.7"
 lazy_static = "1.4"
diff --git a/ergotree-ir/README.md b/ergotree-ir/README.md
index 4fbf9caf3..9593ade25 100644
--- a/ergotree-ir/README.md
+++ b/ergotree-ir/README.md
@@ -61,8 +61,8 @@ Descriptions for the operations can be found in [ErgoTree Specification](https:/
 - executeFromVar
 - executeFromSelfReg
 - getVar
-- allZK
-- anyZK
+- :heavy_check_mark: allZK
+- :heavy_check_mark: anyZK
 - :heavy_check_mark: decodePoint
 - xorOf
 
diff --git a/ergotree-ir/src/mir/bin_op.rs b/ergotree-ir/src/mir/bin_op.rs
index b03b6cd8a..828ad8f03 100644
--- a/ergotree-ir/src/mir/bin_op.rs
+++ b/ergotree-ir/src/mir/bin_op.rs
@@ -223,7 +223,7 @@ mod tests {
     // Test that binop with boolean literals serialized correctly
     #[test]
     fn regression_249() {
-        let e = Expr::sigma_parse_bytes(&vec![0xed, 0x85, 0x03]);
+        let e = Expr::sigma_parse_bytes(&[0xed, 0x85, 0x03]);
         assert_eq!(
             e,
             Ok(Expr::BinOp(BinOp {
diff --git a/ergotree-ir/src/mir/sigma_and.rs b/ergotree-ir/src/mir/sigma_and.rs
index 89db0b0ee..b463644f7 100644
--- a/ergotree-ir/src/mir/sigma_and.rs
+++ b/ergotree-ir/src/mir/sigma_and.rs
@@ -8,6 +8,7 @@ use crate::serialization::SigmaSerializable;
 use crate::types::stype::SType;
 
 use super::expr::Expr;
+use super::expr::InvalidArgumentError;
 use crate::has_opcode::HasStaticOpCode;
 
 /// AND conjunction for sigma propositions
@@ -18,6 +19,26 @@ pub struct SigmaAnd {
 }
 
 impl SigmaAnd {
+    /// Create new object, returns an error if any of the requirements failed
+    pub fn new(items: Vec<Expr>) -> Result<Self, InvalidArgumentError> {
+        let item_types: Vec<SType> = items
+            .clone()
+            .into_iter()
+            .map(|it| it.post_eval_tpe())
+            .collect();
+        if item_types
+            .iter()
+            .all(|tpe| matches!(tpe, SType::SSigmaProp))
+        {
+            Ok(Self { items })
+        } else {
+            Err(InvalidArgumentError(format!(
+                "Sigma conjecture: expected all items be of type SSigmaProp, got {:?},\n items: {:?}",
+                item_types, items
+            )))
+        }
+    }
+
     /// Type
     pub fn tpe(&self) -> SType {
         SType::SSigmaProp
@@ -34,9 +55,7 @@ impl SigmaSerializable for SigmaAnd {
     }
 
     fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SerializationError> {
-        Ok(Self {
-            items: Vec::<Expr>::sigma_parse(r)?,
-        })
+        Ok(Self::new(Vec::<Expr>::sigma_parse(r)?)?)
     }
 }
 
@@ -53,7 +72,7 @@ mod arbitrary {
         type Parameters = ();
 
         fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
-            vec(any_with::<Constant>(SType::SSigmaProp.into()), 2..5)
+            vec(any_with::<Constant>(SType::SSigmaProp.into()), 0..5)
                 .prop_map(|constants| Self {
                     items: constants.into_iter().map(|c| c.into()).collect(),
                 })
diff --git a/ergotree-ir/src/mir/sigma_or.rs b/ergotree-ir/src/mir/sigma_or.rs
index 1a4e56d72..22cb572df 100644
--- a/ergotree-ir/src/mir/sigma_or.rs
+++ b/ergotree-ir/src/mir/sigma_or.rs
@@ -8,6 +8,7 @@ use crate::serialization::SigmaSerializable;
 use crate::types::stype::SType;
 
 use super::expr::Expr;
+use super::expr::InvalidArgumentError;
 use crate::has_opcode::HasStaticOpCode;
 
 /// OR conjunction for sigma propositions
@@ -18,6 +19,26 @@ pub struct SigmaOr {
 }
 
 impl SigmaOr {
+    /// Create new object, returns an error if any of the requirements failed
+    pub fn new(items: Vec<Expr>) -> Result<Self, InvalidArgumentError> {
+        let item_types: Vec<SType> = items
+            .clone()
+            .into_iter()
+            .map(|it| it.post_eval_tpe())
+            .collect();
+        if item_types
+            .iter()
+            .all(|tpe| matches!(tpe, SType::SSigmaProp))
+        {
+            Ok(Self { items })
+        } else {
+            Err(InvalidArgumentError(format!(
+                "Sigma conjecture: expected all items be of type SSigmaProp, got {:?},\n items: {:?}",
+                item_types, items
+            )))
+        }
+    }
+
     /// Type
     pub fn tpe(&self) -> SType {
         SType::SSigmaProp
@@ -34,9 +55,7 @@ impl SigmaSerializable for SigmaOr {
     }
 
     fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SerializationError> {
-        Ok(Self {
-            items: Vec::<Expr>::sigma_parse(r)?,
-        })
+        Ok(Self::new(Vec::<Expr>::sigma_parse(r)?)?)
     }
 }
 
diff --git a/ergotree-ir/src/mir/value.rs b/ergotree-ir/src/mir/value.rs
index 434bc7685..94406b258 100644
--- a/ergotree-ir/src/mir/value.rs
+++ b/ergotree-ir/src/mir/value.rs
@@ -388,6 +388,12 @@ impl TryExtractFrom<Value> for BigInt {
     }
 }
 
+impl<T: TryExtractFrom<Value> + StoreWrapped> TryExtractFrom<Vec<Value>> for Vec<T> {
+    fn try_extract_from(v: Vec<Value>) -> Result<Self, TryExtractFromError> {
+        v.into_iter().map(|it| it.try_extract_into::<T>()).collect()
+    }
+}
+
 impl TryFrom<Value> for ProveDlog {
     type Error = TryExtractFromError;
     fn try_from(cv: Value) -> Result<Self, Self::Error> {
diff --git a/ergotree-ir/src/serialization/sigma_byte_reader.rs b/ergotree-ir/src/serialization/sigma_byte_reader.rs
index c1c4a939c..c491b0c93 100644
--- a/ergotree-ir/src/serialization/sigma_byte_reader.rs
+++ b/ergotree-ir/src/serialization/sigma_byte_reader.rs
@@ -1,7 +1,9 @@
 //! Sigma byte stream writer
 use super::constant_store::ConstantStore;
 use super::val_def_type_store::ValDefTypeStore;
+use sigma_ser::peekable_reader::PeekableReader;
 use sigma_ser::{peekable_reader::Peekable, vlq_encode::ReadSigmaVlqExt};
+use std::io::Cursor;
 use std::io::Read;
 
 /// Implementation of SigmaByteRead
@@ -38,6 +40,16 @@ impl<R: Peekable> SigmaByteReader<R> {
     }
 }
 
+/// Create SigmaByteReader from a byte array (with empty constant store)
+pub fn from_bytes<T: AsRef<[u8]>>(bytes: T) -> SigmaByteReader<PeekableReader<Cursor<T>>> {
+    SigmaByteReader {
+        inner: PeekableReader::new(Cursor::new(bytes)),
+        constant_store: ConstantStore::empty(),
+        substitute_placeholders: false,
+        val_def_type_store: ValDefTypeStore::new(),
+    }
+}
+
 /// Sigma byte reader trait with a constant store to resolve segregated constants
 pub trait SigmaByteRead: ReadSigmaVlqExt + Peekable {
     /// Constant store with constants to resolve constant placeholder types
diff --git a/ergotree-ir/src/serialization/sigmaboolean.rs b/ergotree-ir/src/serialization/sigmaboolean.rs
index 673cd904f..d68d5723f 100644
--- a/ergotree-ir/src/serialization/sigmaboolean.rs
+++ b/ergotree-ir/src/serialization/sigmaboolean.rs
@@ -18,7 +18,7 @@ impl SigmaSerializable for SigmaBoolean {
                 SigmaProofOfKnowledgeTree::ProveDhTuple { .. } => todo!(),
                 SigmaProofOfKnowledgeTree::ProveDlog(v) => v.sigma_serialize(w),
             },
-            SigmaBoolean::Cand(_) => todo!(),
+            SigmaBoolean::SigmaConjecture(_) => todo!(),
             SigmaBoolean::TrivialProp(_) => Ok(()), // besides opCode no additional bytes
         }
     }
diff --git a/ergotree-ir/src/sigma_protocol.rs b/ergotree-ir/src/sigma_protocol.rs
index 813199f7e..8811e0075 100644
--- a/ergotree-ir/src/sigma_protocol.rs
+++ b/ergotree-ir/src/sigma_protocol.rs
@@ -1,4 +1,6 @@
 //! Data types used in Sigma protocol
 
+#![deny(clippy::unwrap_used)]
+
 pub mod dlog_group;
 pub mod sigma_boolean;
diff --git a/ergotree-ir/src/sigma_protocol/dlog_group.rs b/ergotree-ir/src/sigma_protocol/dlog_group.rs
index b7404ffa2..e67753e74 100644
--- a/ergotree-ir/src/sigma_protocol/dlog_group.rs
+++ b/ergotree-ir/src/sigma_protocol/dlog_group.rs
@@ -18,10 +18,10 @@
 use crate::serialization::{
     sigma_byte_reader::SigmaByteRead, SerializationError, SigmaSerializable,
 };
-use k256::{AffinePoint, ProjectivePoint, PublicKey, Scalar};
+use k256::elliptic_curve::sec1::ToEncodedPoint;
+use k256::{ProjectivePoint, PublicKey, Scalar};
 use sigma_ser::vlq_encode;
 
-use elliptic_curve::weierstrass::public_key::FromPublicKey;
 use std::{
     io,
     ops::{Add, Mul, Neg},
@@ -34,6 +34,14 @@ pub struct EcPoint(ProjectivePoint);
 impl EcPoint {
     /// Number of bytes to represent any group element as byte array
     pub const GROUP_SIZE: usize = 33;
+
+    /// Attempts to parse from Base16-encoded string
+    pub fn from_base16_str(str: String) -> Option<Self> {
+        base16::decode(&str)
+            .ok()
+            .map(|bytes| Self::sigma_parse_bytes(&bytes).ok())
+            .flatten()
+    }
 }
 
 impl Eq for EcPoint {}
@@ -100,13 +108,12 @@ pub fn random_scalar_in_group_range() -> Scalar {
 impl SigmaSerializable for EcPoint {
     fn sigma_serialize<W: vlq_encode::WriteSigmaVlqExt>(&self, w: &mut W) -> Result<(), io::Error> {
         let caff = self.0.to_affine();
-        if bool::from(caff.is_some()) {
-            let pubkey = PublicKey::Compressed(caff.unwrap().into());
-            w.write_all(pubkey.as_bytes())?;
-        } else {
+        if caff.is_identity().into() {
             // infinity point
             let zeroes = [0u8; EcPoint::GROUP_SIZE];
             w.write_all(&zeroes)?;
+        } else {
+            w.write_all(caff.to_encoded_point(true).as_bytes())?;
         }
         Ok(())
     }
@@ -115,17 +122,10 @@ impl SigmaSerializable for EcPoint {
         let mut buf = [0; EcPoint::GROUP_SIZE];
         r.read_exact(&mut buf[..])?;
         if buf[0] != 0 {
-            let pubkey = PublicKey::from_bytes(&buf[..]).ok_or_else(|| {
-                SerializationError::Misc("failed to parse PK from bytes".to_string())
+            let pubkey = PublicKey::from_sec1_bytes(&buf[..]).map_err(|e| {
+                SerializationError::Misc(format!("failed to parse PK from bytes: {:?}", e))
             })?;
-            let cp = AffinePoint::from_public_key(&pubkey);
-            if bool::from(cp.is_none()) {
-                Err(SerializationError::Misc(
-                    "failed to get affine point from PK".to_string(),
-                ))
-            } else {
-                Ok(EcPoint(ProjectivePoint::from(cp.unwrap())))
-            }
+            Ok(EcPoint(pubkey.to_projective()))
         } else {
             // infinity point
             Ok(EcPoint(ProjectivePoint::identity()))
@@ -156,6 +156,7 @@ mod arbitrary {
 #[cfg(test)]
 mod tests {
     use super::*;
+    use crate::mir::expr::Expr;
     use crate::serialization::sigma_serialize_roundtrip;
     use proptest::prelude::*;
 
@@ -163,7 +164,8 @@ mod tests {
 
         #[test]
         fn ser_roundtrip(v in any::<EcPoint>()) {
-            prop_assert_eq![sigma_serialize_roundtrip(&v), v];
+            let e: Expr = v.into();
+            prop_assert_eq![sigma_serialize_roundtrip(&e), e];
         }
     }
 }
diff --git a/ergotree-ir/src/sigma_protocol/sigma_boolean.rs b/ergotree-ir/src/sigma_protocol/sigma_boolean.rs
index ae4f8b342..4714064c9 100644
--- a/ergotree-ir/src/sigma_protocol/sigma_boolean.rs
+++ b/ergotree-ir/src/sigma_protocol/sigma_boolean.rs
@@ -1,5 +1,8 @@
 //! Sigma boolean types
 
+use self::cand::Cand;
+use self::cor::Cor;
+
 use super::dlog_group::EcPoint;
 use crate::ergo_tree::ErgoTree;
 use crate::has_opcode::HasOpCode;
@@ -14,6 +17,9 @@ use derive_more::From;
 use derive_more::Into;
 use derive_more::TryInto;
 
+pub mod cand;
+pub mod cor;
+
 /// Construct a new SigmaBoolean value representing public key of discrete logarithm signature protocol.
 #[derive(PartialEq, Eq, Debug, Clone)]
 pub struct ProveDlog {
@@ -59,6 +65,15 @@ pub enum SigmaProofOfKnowledgeTree {
     ProveDlog(ProveDlog),
 }
 
+/// Conjunctions for sigma propositions
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub enum SigmaConjecture {
+    /// AND
+    Cand(Cand),
+    /// OR
+    Cor(Cor),
+}
+
 /// Algebraic data type of sigma proposition expressions
 /// Values of this type are used as values of SigmaProp type
 #[derive(PartialEq, Eq, Debug, Clone, From, TryInto)]
@@ -67,8 +82,8 @@ pub enum SigmaBoolean {
     TrivialProp(bool),
     /// Sigma proposition
     ProofOfKnowledge(SigmaProofOfKnowledgeTree),
-    /// AND conjunction for sigma propositions
-    Cand(Vec<SigmaBoolean>),
+    /// Conjunctions for sigma propositions
+    SigmaConjecture(SigmaConjecture),
 }
 
 impl HasOpCode for SigmaBoolean {
@@ -97,6 +112,12 @@ impl TryInto<ProveDlog> for SigmaBoolean {
     }
 }
 
+impl From<ProveDlog> for SigmaBoolean {
+    fn from(v: ProveDlog) -> Self {
+        SigmaBoolean::ProofOfKnowledge(SigmaProofOfKnowledgeTree::ProveDlog(v))
+    }
+}
+
 /// Proposition which can be proven and verified by sigma protocol.
 #[derive(PartialEq, Eq, Debug, Clone, From, Into)]
 pub struct SigmaProp(SigmaBoolean);
diff --git a/ergotree-ir/src/sigma_protocol/sigma_boolean/cand.rs b/ergotree-ir/src/sigma_protocol/sigma_boolean/cand.rs
new file mode 100644
index 000000000..ff93275ab
--- /dev/null
+++ b/ergotree-ir/src/sigma_protocol/sigma_boolean/cand.rs
@@ -0,0 +1,90 @@
+//! AND conjunction for sigma proposition
+use super::SigmaBoolean;
+use crate::sigma_protocol::sigma_boolean::SigmaConjecture;
+
+/// AND conjunction for sigma proposition
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct Cand {
+    /// Items of the conjunctions
+    pub items: Vec<SigmaBoolean>,
+}
+
+impl Cand {
+    /// Connects the given sigma propositions into CAND proposition performing
+    /// partial evaluation when some of them are trivial propositioins.
+    pub fn normalized(items: Vec<SigmaBoolean>) -> SigmaBoolean {
+        assert!(!items.is_empty());
+        let mut res = Vec::new();
+        for it in items {
+            match it {
+                SigmaBoolean::TrivialProp(false) => return it,
+                SigmaBoolean::TrivialProp(true) => (),
+                _ => res.push(it),
+            }
+        }
+        if res.is_empty() {
+            true.into()
+        } else if res.len() == 1 {
+            #[allow(clippy::unwrap_used)]
+            res.first().unwrap().clone()
+        } else {
+            SigmaBoolean::SigmaConjecture(SigmaConjecture::Cand(Cand { items: res }))
+        }
+    }
+}
+
+#[allow(clippy::unwrap_used)]
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::sigma_protocol::sigma_boolean::ProveDlog;
+    use sigma_test_util::force_any_val;
+    use std::convert::TryInto;
+
+    #[test]
+    fn trivial_true() {
+        let cand = Cand::normalized(vec![true.into()]);
+        assert!(matches!(cand, SigmaBoolean::TrivialProp(true)));
+    }
+
+    #[test]
+    fn trivial_false() {
+        let cand = Cand::normalized(vec![false.into()]);
+        assert!(matches!(cand, SigmaBoolean::TrivialProp(false)));
+    }
+
+    #[test]
+    fn pk() {
+        let pk = force_any_val::<ProveDlog>();
+        let cand = Cand::normalized(vec![pk.clone().into()]);
+        let res: ProveDlog = cand.try_into().unwrap();
+        assert_eq!(res, pk);
+    }
+
+    #[test]
+    fn pk_triv_true() {
+        let pk = force_any_val::<ProveDlog>();
+        let cand = Cand::normalized(vec![pk.clone().into(), true.into()]);
+        let res: ProveDlog = cand.try_into().unwrap();
+        assert_eq!(res, pk);
+    }
+
+    #[test]
+    fn pk_triv_false() {
+        let pk = force_any_val::<ProveDlog>();
+        let cand = Cand::normalized(vec![pk.into(), false.into()]);
+        assert!(matches!(cand, SigmaBoolean::TrivialProp(false)));
+    }
+
+    #[test]
+    fn pk_pk() {
+        let pk1 = force_any_val::<ProveDlog>();
+        let pk2 = force_any_val::<ProveDlog>();
+        let pks = vec![pk1.into(), pk2.into()];
+        let cand = Cand::normalized(pks.clone());
+        assert!(matches!(
+            cand,
+            SigmaBoolean::SigmaConjecture(SigmaConjecture::Cand(Cand {items})) if items == pks
+        ));
+    }
+}
diff --git a/ergotree-ir/src/sigma_protocol/sigma_boolean/cor.rs b/ergotree-ir/src/sigma_protocol/sigma_boolean/cor.rs
new file mode 100644
index 000000000..5206b8187
--- /dev/null
+++ b/ergotree-ir/src/sigma_protocol/sigma_boolean/cor.rs
@@ -0,0 +1,90 @@
+//! OR conjunction for sigma proposition
+use super::SigmaBoolean;
+use crate::sigma_protocol::sigma_boolean::SigmaConjecture;
+
+/// OR conjunction for sigma proposition
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct Cor {
+    /// Items of the conjunctions
+    pub items: Vec<SigmaBoolean>,
+}
+
+impl Cor {
+    /// Connects the given sigma propositions into COR proposition performing
+    /// partial evaluation when some of them are trivial propositioins.
+    pub fn normalized(items: Vec<SigmaBoolean>) -> SigmaBoolean {
+        assert!(!items.is_empty());
+        let mut res = Vec::new();
+        for it in items {
+            match it {
+                SigmaBoolean::TrivialProp(true) => return it,
+                SigmaBoolean::TrivialProp(false) => (),
+                _ => res.push(it),
+            }
+        }
+        if res.is_empty() {
+            false.into()
+        } else if res.len() == 1 {
+            #[allow(clippy::unwrap_used)]
+            res.first().unwrap().clone()
+        } else {
+            SigmaBoolean::SigmaConjecture(SigmaConjecture::Cor(Cor { items: res }))
+        }
+    }
+}
+
+#[allow(clippy::unwrap_used)]
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::sigma_protocol::sigma_boolean::ProveDlog;
+    use sigma_test_util::force_any_val;
+    use std::convert::TryInto;
+
+    #[test]
+    fn trivial_true() {
+        let cor = Cor::normalized(vec![true.into()]);
+        assert!(matches!(cor, SigmaBoolean::TrivialProp(true)));
+    }
+
+    #[test]
+    fn trivial_false() {
+        let cor = Cor::normalized(vec![false.into()]);
+        assert!(matches!(cor, SigmaBoolean::TrivialProp(false)));
+    }
+
+    #[test]
+    fn pk() {
+        let pk = force_any_val::<ProveDlog>();
+        let cor = Cor::normalized(vec![pk.clone().into()]);
+        let res: ProveDlog = cor.try_into().unwrap();
+        assert_eq!(res, pk);
+    }
+
+    #[test]
+    fn pk_triv_true() {
+        let pk = force_any_val::<ProveDlog>();
+        let cor = Cor::normalized(vec![pk.into(), true.into()]);
+        assert!(matches!(cor, SigmaBoolean::TrivialProp(true)));
+    }
+
+    #[test]
+    fn pk_triv_false() {
+        let pk = force_any_val::<ProveDlog>();
+        let cor = Cor::normalized(vec![pk.clone().into(), false.into()]);
+        let res: ProveDlog = cor.try_into().unwrap();
+        assert_eq!(res, pk);
+    }
+
+    #[test]
+    fn pk_pk() {
+        let pk1 = force_any_val::<ProveDlog>();
+        let pk2 = force_any_val::<ProveDlog>();
+        let pks = vec![pk1.into(), pk2.into()];
+        let cor = Cor::normalized(pks.clone());
+        assert!(matches!(
+            cor,
+            SigmaBoolean::SigmaConjecture(SigmaConjecture::Cor(Cor {items})) if items == pks
+        ));
+    }
+}
diff --git a/sigma-ser/Cargo.toml b/sigma-ser/Cargo.toml
index c4cdfd76e..5ffdd0f5c 100644
--- a/sigma-ser/Cargo.toml
+++ b/sigma-ser/Cargo.toml
@@ -16,7 +16,7 @@ crate-type = ["cdylib", "rlib"]
 [dependencies]
 # wasm-bindgen = "0.2"
 thiserror = "1"
-bitvec = "0.22.3"
+bitvec = "0.20.2"
 
 # The `console_error_panic_hook` crate provides better debugging of panics by
 # logging them with `console.error`. This is great for development, but requires
diff --git a/sigma-ser/src/vlq_encode.rs b/sigma-ser/src/vlq_encode.rs
index bd6467f52..93fb2d053 100644
--- a/sigma-ser/src/vlq_encode.rs
+++ b/sigma-ser/src/vlq_encode.rs
@@ -110,6 +110,11 @@ pub trait WriteSigmaVlqExt: io::Write {
         }
         Ok(())
     }
+
+    /// Put the two bytes of the big-endian representation of the i16 value into the writer.
+    fn put_i16_be_bytes(&mut self, v: i16) -> io::Result<()> {
+        self.write_all(v.to_be_bytes().as_ref())
+    }
 }
 
 /// Mark all types implementing `Write` as implementing the extension.
@@ -187,10 +192,7 @@ pub trait ReadSigmaVlqExt: io::Read {
         let mut buf = vec![0u8; byte_num];
         self.read_exact(&mut buf)?;
         // May fail if number of bits in buf is larger that maximum value of usize
-        let mut bits = match BitVec::<Lsb0, u8>::from_slice(&buf) {
-            Ok(v) => v,
-            Err(_) => return Err(VlqEncodingError::VlqDecodingFailed),
-        };
+        let mut bits = BitVec::<Lsb0, u8>::from_vec(buf);
         bits.truncate(size);
         Ok(bits.iter().map(|x| *x).collect::<Vec<bool>>())
     }


Test patch: