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

Issue:
add ErgoTree interpreter, prover and verifier for P2PK scripts
Todo:
- [x] implement `fiat_shamir_tree_to_bytes()`;
- [x] implement `dlog_protocol::interactive_prover::second_message()`;
- [x] implement `serialize_sig()`;
- [ ] implement verifier;
- [ ] test generated proof in verifier;


Discussion / hints:

Fix patch:
diff --git a/.travis.yml b/.travis.yml
index c8f51fb65..53154a7ae 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -9,7 +9,7 @@ rust:
 
 os:
   - linux
-  - osx
+  # - osx # it hangs
   - windows
 
 env:
diff --git a/bindings/ergo-wallet-lib-wasm/src/lib.rs b/bindings/ergo-wallet-lib-wasm/src/lib.rs
index 93170b2a3..75d4c3ba8 100644
--- a/bindings/ergo-wallet-lib-wasm/src/lib.rs
+++ b/bindings/ergo-wallet-lib-wasm/src/lib.rs
@@ -74,6 +74,19 @@ impl Address {
     }
 }
 
+/// Secret key for the prover
+#[wasm_bindgen]
+#[derive(PartialEq, Debug, Clone)]
+pub struct SecretKey(ergo_wallet_lib::SecretKey);
+
+#[wasm_bindgen]
+impl SecretKey {
+    /// generate random key
+    pub fn random_dlog() -> SecretKey {
+        SecretKey(ergo_wallet_lib::SecretKey::random_dlog())
+    }
+}
+
 /// Transaction inputs, array of ErgoBoxCandidate
 #[wasm_bindgen]
 pub struct UnspentBoxes(Vec<chain::ErgoBoxCandidate>);
diff --git a/ergo-wallet-lib/src/secret_key.rs b/ergo-wallet-lib/src/secret_key.rs
index 7d9edc1e6..eae7f5672 100644
--- a/ergo-wallet-lib/src/secret_key.rs
+++ b/ergo-wallet-lib/src/secret_key.rs
@@ -1,6 +1,7 @@
 use sigma_tree::sigma_protocol::DlogProverInput;
 
 /// Types of secrets
+#[derive(PartialEq, Debug, Clone)]
 pub enum SecretKey {
     /// Secret exponent of a group element, i.e. secret w such as h = g^^w, where g is group generator, h is a public key.
     DlogSecretKey(DlogProverInput),
diff --git a/sigma-tree/Cargo.toml b/sigma-tree/Cargo.toml
index bb16cf05f..e6b56bed7 100644
--- a/sigma-tree/Cargo.toml
+++ b/sigma-tree/Cargo.toml
@@ -11,14 +11,15 @@ crate-type = ["cdylib", "rlib"]
 sigma-ser = { path = "../sigma-ser" }
 indexmap = "1.3.2"
 base16 = "0.2.1"
-k256 = "0.3.0"
+k256 = {version = "0.4.2", features = ["rand", "zeroize"]}
 blake2 = "0.9"
-elliptic-curve = {version = "0.4.0", features = ["getrandom"]}
+elliptic-curve = {version = "0.5.0", features = ["rand", "zeroize"]}
 serde = { version = "1.0", features = ["derive"], optional = true }
 serde_json = "1.0"
 thiserror = "1"
 bs58 = "0.3.1"
 num-bigint = "0.3.0"
+rand = "0.7"
 
 [features]
 default = []
diff --git a/sigma-tree/src/ast/constant.rs b/sigma-tree/src/ast/constant.rs
index e3cf6b9df..662629b0a 100644
--- a/sigma-tree/src/ast/constant.rs
+++ b/sigma-tree/src/ast/constant.rs
@@ -2,7 +2,7 @@ use crate::chain::{Base16DecodedBytes, Base16EncodedBytes};
 use crate::{
     chain::ErgoBox,
     serialization::{op_code::OpCode, SerializationError, SigmaSerializable},
-    sigma_protocol::{dlog_group::EcPoint, SigmaProp},
+    sigma_protocol::{dlog_group::EcPoint, sigma_boolean::SigmaProp},
     types::{LiftIntoSType, SType},
 };
 #[cfg(feature = "with-serde")]
@@ -195,9 +195,9 @@ impl Into<Constant> for i64 {
     }
 }
 
-impl Into<ConstantVal> for SigmaProp {
-    fn into(self) -> ConstantVal {
-        ConstantVal::SigmaProp(Box::new(self))
+impl<T: Into<SigmaProp>> From<T> for ConstantVal {
+    fn from(t: T) -> Self {
+        ConstantVal::SigmaProp(Box::new(t.into()))
     }
 }
 
diff --git a/sigma-tree/src/big_integer.rs b/sigma-tree/src/big_integer.rs
index d520b1187..b7c5feed0 100644
--- a/sigma-tree/src/big_integer.rs
+++ b/sigma-tree/src/big_integer.rs
@@ -1,8 +1,8 @@
-use k256::arithmetic::Scalar;
+// use k256::Scalar;
 use num_bigint::BigInt;
 // use std::convert::TryFrom;
 
-#[derive(Debug, PartialEq)]
+#[derive(Debug, PartialEq, Eq, Clone)]
 pub struct BigInteger(BigInt);
 
 impl From<BigInt> for BigInteger {
@@ -10,37 +10,3 @@ impl From<BigInt> for BigInteger {
         BigInteger(b)
     }
 }
-
-impl From<Scalar> for BigInteger {
-    fn from(s: Scalar) -> Self {
-        let bytes = s.to_bytes();
-        BigInt::from_signed_bytes_be(&bytes[..]).into()
-    }
-}
-
-// impl TryFrom<BigInteger> for Scalar {
-//     type Error;
-//     fn try_from(value: BigInteger) -> Result<Self, Self::Error> {
-//         todo!()
-//     }
-// }
-//
-
-#[cfg(test)]
-mod tests {
-    use super::*;
-    use crate::sigma_protocol::dlog_group;
-    use std::convert::TryInto;
-
-    #[test]
-    fn scalar_conversion_roundtrip() {
-        let s = dlog_group::random_scalar_in_group_range();
-        let b: BigInteger = s.into();
-        let bytes = b.0.to_signed_bytes_be();
-        let s2 =
-            Scalar::from_bytes(bytes.as_slice().try_into().expect("expected 32 bytes")).unwrap();
-        // TODO: failed on CI with non-32 bytes length
-        let b2: BigInteger = s2.into();
-        assert_eq!(b, b2);
-    }
-}
diff --git a/sigma-tree/src/chain/address.rs b/sigma-tree/src/chain/address.rs
index 35434b652..082708760 100644
--- a/sigma-tree/src/chain/address.rs
+++ b/sigma-tree/src/chain/address.rs
@@ -3,7 +3,8 @@ use crate::{
     ast::Expr,
     serialization::{SerializationError, SigmaSerializable},
     sigma_protocol::{
-        dlog_group::EcPoint, ProveDlog, SigmaBoolean, SigmaProofOfKnowledgeTree, SigmaProp,
+        dlog_group::EcPoint,
+        sigma_boolean::{ProveDlog, SigmaBoolean, SigmaProofOfKnowledgeTree, SigmaProp},
     },
     ErgoTree,
 };
diff --git a/sigma-tree/src/chain/digest32.rs b/sigma-tree/src/chain/digest32.rs
index 87a836048..820fd0773 100644
--- a/sigma-tree/src/chain/digest32.rs
+++ b/sigma-tree/src/chain/digest32.rs
@@ -83,7 +83,7 @@ impl SigmaSerializable for Digest32 {
     }
 }
 
-/// Invalie byte array size
+/// Invalid byte array size
 #[derive(Error, Debug)]
 #[error("Invalid byte array size ({0})")]
 pub struct Digest32Error(std::array::TryFromSliceError);
diff --git a/sigma-tree/src/chain/transaction.rs b/sigma-tree/src/chain/transaction.rs
index 7e13e228f..0d277f209 100644
--- a/sigma-tree/src/chain/transaction.rs
+++ b/sigma-tree/src/chain/transaction.rs
@@ -132,6 +132,11 @@ impl Transaction {
         };
         tx_to_sign.sigma_serialise_bytes()
     }
+
+    /// Get transaction id
+    pub fn id(&self) -> TxId {
+        self.tx_id.clone()
+    }
 }
 
 impl SigmaSerializable for Transaction {
diff --git a/sigma-tree/src/ergo_tree.rs b/sigma-tree/src/ergo_tree.rs
index 7cd7edb29..dad2da084 100644
--- a/sigma-tree/src/ergo_tree.rs
+++ b/sigma-tree/src/ergo_tree.rs
@@ -117,7 +117,8 @@ impl ErgoTree {
         let cursor = Cursor::new(&mut data[..]);
         let pr = PeekableReader::new(cursor);
         let constants = cs.get_all();
-        let mut sr = SigmaByteReader::new(pr, cs);
+        let new_cs = ConstantStore::new(constants.clone());
+        let mut sr = SigmaByteReader::new(pr, new_cs);
         let parsed_expr = Expr::sigma_parse(&mut sr).unwrap();
         ErgoTree {
             header: ErgoTreeHeader(ErgoTreeHeader::CONSTANT_SEGREGATION_FLAG),
@@ -251,7 +252,7 @@ impl SigmaSerializable for ErgoTree {
 mod tests {
     use super::*;
     use crate::serialization::sigma_serialize_roundtrip;
-    use crate::{ast::ConstantVal, chain, sigma_protocol::SigmaProp, types::SType};
+    use crate::{ast::ConstantVal, chain, sigma_protocol::sigma_boolean::SigmaProp, types::SType};
     use proptest::prelude::*;
 
     impl Arbitrary for ErgoTree {
diff --git a/sigma-tree/src/eval.rs b/sigma-tree/src/eval.rs
index c65da4782..2f2323edc 100644
--- a/sigma-tree/src/eval.rs
+++ b/sigma-tree/src/eval.rs
@@ -1,6 +1,6 @@
 use crate::{
     ast::{ops::BinOp, ops::NumOp, Constant, ConstantVal, Expr},
-    sigma_protocol::SigmaBoolean,
+    sigma_protocol::sigma_boolean::SigmaBoolean,
     types::SType,
 };
 
diff --git a/sigma-tree/src/eval/value.rs b/sigma-tree/src/eval/value.rs
index 57b759252..f43372804 100644
--- a/sigma-tree/src/eval/value.rs
+++ b/sigma-tree/src/eval/value.rs
@@ -1,4 +1,4 @@
-use crate::{chain::ErgoBox, sigma_protocol::SigmaBoolean};
+use crate::{chain::ErgoBox, sigma_protocol::sigma_boolean::SigmaBoolean};
 use std::ops::Add;
 
 #[allow(dead_code)]
diff --git a/sigma-tree/src/lib.rs b/sigma-tree/src/lib.rs
index 9181a3312..083b52e9e 100644
--- a/sigma-tree/src/lib.rs
+++ b/sigma-tree/src/lib.rs
@@ -12,15 +12,16 @@
 // Clippy exclusions
 #![allow(clippy::unit_arg)]
 
-pub mod ast;
 mod big_integer;
 mod constants;
 mod ergo_tree;
 mod eval;
-mod serialization;
+pub mod serialization;
 mod types;
 
+pub mod ast;
 pub mod chain;
 pub mod sigma_protocol;
 
 pub use ergo_tree::*;
+// pub use serialization::serializable::*;
diff --git a/sigma-tree/src/serialization.rs b/sigma-tree/src/serialization.rs
index aa8c42920..0e40a9264 100644
--- a/sigma-tree/src/serialization.rs
+++ b/sigma-tree/src/serialization.rs
@@ -5,12 +5,12 @@ mod constant_placeholder;
 mod data;
 mod expr;
 mod fold;
-mod serializable;
 mod sigmaboolean;
 
 pub mod constant_store;
 pub mod ergo_box;
 pub mod op_code;
+pub mod serializable;
 pub mod sigma_byte_reader;
 pub mod sigma_byte_writer;
 pub mod types;
diff --git a/sigma-tree/src/serialization/constant_store.rs b/sigma-tree/src/serialization/constant_store.rs
index 6441f97fa..d549972f1 100644
--- a/sigma-tree/src/serialization/constant_store.rs
+++ b/sigma-tree/src/serialization/constant_store.rs
@@ -8,18 +8,22 @@ pub struct ConstantStore {
 }
 
 impl ConstantStore {
+    /// Make an empty(no constants) store
     pub fn empty() -> Self {
         ConstantStore { constants: vec![] }
     }
 
+    /// Make a store with constants provided
     pub fn new(constants: Vec<Constant>) -> Self {
         ConstantStore { constants }
     }
 
+    /// Get a constant by it's index in serialized constants list (stored in ConstantPlaceholder)
     pub fn get(&self, index: u32) -> Option<&Constant> {
         self.constants.get(index as usize)
     }
 
+    /// Save a Constant and get ConstantPlaceholder(with stored index) back
     pub fn put(&mut self, c: Constant) -> ConstantPlaceholder {
         self.constants.push(c.clone());
         assert!(self.constants.len() <= u32::MAX as usize);
@@ -29,6 +33,7 @@ impl ConstantStore {
         }
     }
 
+    /// Get all stored constants (order preserved)
     pub fn get_all(&self) -> Vec<Constant> {
         self.constants.clone()
     }
diff --git a/sigma-tree/src/serialization/data.rs b/sigma-tree/src/serialization/data.rs
index 50539860a..2951df7bb 100644
--- a/sigma-tree/src/serialization/data.rs
+++ b/sigma-tree/src/serialization/data.rs
@@ -9,7 +9,7 @@ use crate::{
     types::SType,
     types::SType::*,
 };
-use sigma_protocol::{dlog_group::EcPoint, SigmaBoolean, SigmaProp};
+use sigma_protocol::{dlog_group::EcPoint, sigma_boolean::SigmaBoolean, sigma_boolean::SigmaProp};
 
 use super::sigma_byte_writer::SigmaByteWrite;
 use std::io;
diff --git a/sigma-tree/src/serialization/ergo_box.rs b/sigma-tree/src/serialization/ergo_box.rs
index 58411e10a..f5cadbb60 100644
--- a/sigma-tree/src/serialization/ergo_box.rs
+++ b/sigma-tree/src/serialization/ergo_box.rs
@@ -1,3 +1,4 @@
+//! ErgoBox and ErgoBoxCandidate serialization
 use crate::serialization::{
     sigma_byte_reader::SigmaByteRead, SerializationError, SigmaSerializable,
 };
diff --git a/sigma-tree/src/serialization/op_code.rs b/sigma-tree/src/serialization/op_code.rs
index 12c2a4004..bdd20040a 100644
--- a/sigma-tree/src/serialization/op_code.rs
+++ b/sigma-tree/src/serialization/op_code.rs
@@ -1,3 +1,5 @@
+#![allow(missing_docs)]
+
 use crate::serialization::{
     sigma_byte_reader::SigmaByteRead, SerializationError, SigmaSerializable,
 };
diff --git a/sigma-tree/src/serialization/serializable.rs b/sigma-tree/src/serialization/serializable.rs
index 3c224c671..1b662e482 100644
--- a/sigma-tree/src/serialization/serializable.rs
+++ b/sigma-tree/src/serialization/serializable.rs
@@ -1,3 +1,4 @@
+//! Serialization of Ergo types
 use super::{
     constant_store::ConstantStore,
     sigma_byte_reader::{SigmaByteRead, SigmaByteReader},
diff --git a/sigma-tree/src/serialization/sigma_byte_reader.rs b/sigma-tree/src/serialization/sigma_byte_reader.rs
index fd784a669..747404321 100644
--- a/sigma-tree/src/serialization/sigma_byte_reader.rs
+++ b/sigma-tree/src/serialization/sigma_byte_reader.rs
@@ -1,7 +1,9 @@
+//! Sigma byte stream writer
 use super::constant_store::ConstantStore;
 use sigma_ser::{peekable_reader::Peekable, vlq_encode::ReadSigmaVlqExt};
 use std::io::Read;
 
+/// Implementation of SigmaByteRead
 pub struct SigmaByteReader<R> {
     inner: R,
     constant_store: ConstantStore,
@@ -18,6 +20,8 @@ impl<R: Peekable> SigmaByteReader<R> {
         }
     }
 
+    /// Make a new reader with underlying PeekableReader and constant_store to resolve constant
+    /// placeholders
     pub fn new_with_substitute_placeholders(
         pr: R,
         constant_store: ConstantStore,
@@ -30,9 +34,12 @@ impl<R: Peekable> SigmaByteReader<R> {
     }
 }
 
+/// Sigma byte reader trait with a constant store to resolve segregated constants
 pub trait SigmaByteRead: ReadSigmaVlqExt {
+    /// Constant store with constants to resolve constant placeholder types
     fn constant_store(&mut self) -> &mut ConstantStore;
 
+    /// Option to substitute ConstantPlaceholder with Constant from the store
     fn substitute_placeholders(&self) -> bool;
 }
 
diff --git a/sigma-tree/src/serialization/sigma_byte_writer.rs b/sigma-tree/src/serialization/sigma_byte_writer.rs
index 0c54bb4dc..6237bb1bd 100644
--- a/sigma-tree/src/serialization/sigma_byte_writer.rs
+++ b/sigma-tree/src/serialization/sigma_byte_writer.rs
@@ -1,13 +1,16 @@
+//! Sigma byte stream writer
 use super::constant_store::ConstantStore;
 use sigma_ser::vlq_encode::WriteSigmaVlqExt;
 use std::io::Write;
 
+/// Implementation for SigmaByteWrite
 pub struct SigmaByteWriter<'a, W> {
     inner: &'a mut W,
     constant_store: Option<&'a mut ConstantStore>,
 }
 
 impl<'a, W: Write> SigmaByteWriter<'a, W> {
+    /// Make a new writer with underlying Write and optional constant store
     pub fn new(
         w: &'a mut W,
         constant_store: Option<&'a mut ConstantStore>,
@@ -19,7 +22,9 @@ impl<'a, W: Write> SigmaByteWriter<'a, W> {
     }
 }
 
+/// Sigma byte writer trait with a store for constant segregation
 pub trait SigmaByteWrite: WriteSigmaVlqExt {
+    /// Constant store (if any) attached to the writer to collect segregated constants
     fn constant_store(&mut self) -> Option<&mut ConstantStore>;
 }
 
diff --git a/sigma-tree/src/serialization/sigmaboolean.rs b/sigma-tree/src/serialization/sigmaboolean.rs
index e89507f25..16574f89b 100644
--- a/sigma-tree/src/serialization/sigmaboolean.rs
+++ b/sigma-tree/src/serialization/sigmaboolean.rs
@@ -3,7 +3,8 @@ use crate::serialization::{
     sigma_byte_reader::SigmaByteRead, SerializationError, SigmaSerializable,
 };
 use crate::sigma_protocol::{
-    dlog_group::EcPoint, ProveDlog, SigmaBoolean, SigmaProofOfKnowledgeTree,
+    dlog_group::EcPoint,
+    sigma_boolean::{ProveDlog, SigmaBoolean, SigmaProofOfKnowledgeTree},
 };
 
 use std::io;
diff --git a/sigma-tree/src/serialization/types.rs b/sigma-tree/src/serialization/types.rs
index a3c658d4e..423f39040 100644
--- a/sigma-tree/src/serialization/types.rs
+++ b/sigma-tree/src/serialization/types.rs
@@ -1,3 +1,5 @@
+#![allow(missing_docs)]
+
 use super::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::{
     sigma_byte_reader::SigmaByteRead, SerializationError, SigmaSerializable,
diff --git a/sigma-tree/src/sigma_protocol.rs b/sigma-tree/src/sigma_protocol.rs
index c68d7ce04..65d1624e1 100644
--- a/sigma-tree/src/sigma_protocol.rs
+++ b/sigma-tree/src/sigma_protocol.rs
@@ -1,126 +1,52 @@
 //! Sigma protocols
 
-#![allow(dead_code)]
-#![allow(unused_variables)]
-#![allow(missing_docs)]
+mod challenge;
+mod private_input;
+
+pub use challenge::*;
+pub use private_input::*;
 
 pub mod dlog_group;
 pub mod dlog_protocol;
+pub mod fiat_shamir;
 pub mod prover;
+pub mod sig_serializer;
+pub mod sigma_boolean;
+pub mod unchecked_tree;
+pub mod unproven_tree;
 pub mod verifier;
 
-use k256::arithmetic::Scalar;
+use k256::Scalar;
 
-use crate::{big_integer::BigInteger, serialization::op_code::OpCode};
-use blake2::digest::{Update, VariableOutput};
-use blake2::VarBlake2b;
-use dlog_group::EcPoint;
-use dlog_protocol::{FirstDlogProverMessage, SecondDlogProverMessage};
+use dlog_protocol::FirstDlogProverMessage;
+use sigma_boolean::{ProveDlog, SigmaBoolean, SigmaProofOfKnowledgeTree};
 use std::convert::TryInto;
+use unchecked_tree::{UncheckedSigmaTree, UncheckedTree};
+use unproven_tree::{UnprovenLeaf, UnprovenSchnorr, UnprovenTree};
 
-/// Secret key of discrete logarithm signature protocol
-pub struct DlogProverInput {
-    /// secret key value
-    pub w: Scalar,
-}
-
-impl DlogProverInput {
-    /// generates random secret in the range [0, n), where n is DLog group order.
-    pub fn random() -> DlogProverInput {
-        DlogProverInput {
-            w: dlog_group::random_scalar_in_group_range(),
-        }
-    }
-
-    /// public key of discrete logarithm signature protocol
-    fn public_image(&self) -> ProveDlog {
-        // test it, see https://github.com/ergoplatform/sigma-rust/issues/38
-        let g = dlog_group::generator();
-        ProveDlog::new(dlog_group::exponentiate(&g, &self.w))
-    }
-}
-
-/// Private inputs (secrets)
-pub enum PrivateInput {
-    DlogProverInput(DlogProverInput),
-    DiffieHellmanTupleProverInput,
-}
-
-/// Construct a new SigmaBoolean value representing public key of discrete logarithm signature protocol.
-#[derive(PartialEq, Eq, Debug, Clone)]
-pub struct ProveDlog {
-    /// public key
-    pub h: Box<EcPoint>,
-}
-
-impl ProveDlog {
-    /// create new public key
-    pub fn new(ecpoint: EcPoint) -> ProveDlog {
-        ProveDlog {
-            h: Box::new(ecpoint),
-        }
-    }
-}
-
-/// Construct a new SigmaProp value representing public key of Diffie Hellman signature protocol.
-/// Common input: (g,h,u,v)
-#[derive(PartialEq, Eq, Debug, Clone)]
-pub struct ProveDHTuple {
-    gv: Box<EcPoint>,
-    hv: Box<EcPoint>,
-    uv: Box<EcPoint>,
-    vv: Box<EcPoint>,
-}
-
-/// Sigma proposition
-#[derive(PartialEq, Eq, Debug, Clone)]
-pub enum SigmaProofOfKnowledgeTree {
-    /// public key of Diffie Hellman signature protocol
-    ProveDHTuple(ProveDHTuple),
-    /// public key of discrete logarithm signature protocol
-    ProveDlog(ProveDlog),
+/** The message sent by a prover to its associated verifier as part of a sigma protocol interaction. */
+pub trait ProverMessage {
+    /// serialized message
+    fn bytes(&self) -> Vec<u8>;
 }
 
-/// Algebraic data type of sigma proposition expressions
-/// Values of this type are used as values of SigmaProp type
-#[derive(PartialEq, Eq, Debug, Clone)]
-pub enum SigmaBoolean {
-    /// Represents boolean values (true/false)
-    TrivialProp(bool),
-    /// Sigma proposition
-    ProofOfKnowledge(SigmaProofOfKnowledgeTree),
-    /// AND conjunction for sigma propositions
-    CAND(Vec<SigmaBoolean>),
+/** First message from the prover (message `a` of `SigmaProtocol`)*/
+pub enum FirstProverMessage {
+    /// Discrete log
+    FirstDlogProverMessage(FirstDlogProverMessage),
+    /// DH tupl
+    FirstDHTProverMessage,
 }
 
-impl SigmaBoolean {
-    /// get OpCode for serialization
-    pub fn op_code(&self) -> OpCode {
+impl ProverMessage for FirstProverMessage {
+    fn bytes(&self) -> Vec<u8> {
         match self {
-            SigmaBoolean::ProofOfKnowledge(SigmaProofOfKnowledgeTree::ProveDlog(_)) => {
-                OpCode::PROVE_DLOG
-            }
-            _ => todo!(),
+            FirstProverMessage::FirstDlogProverMessage(fdpm) => fdpm.bytes(),
+            FirstProverMessage::FirstDHTProverMessage => todo!(),
         }
     }
 }
 
-/// Proposition which can be proven and verified by sigma protocol.
-#[derive(PartialEq, Eq, Debug, Clone)]
-pub struct SigmaProp(SigmaBoolean);
-
-impl SigmaProp {
-    /// create new sigma propostion from [`SigmaBoolean`] value
-    pub fn new(sbool: SigmaBoolean) -> Self {
-        SigmaProp { 0: sbool }
-    }
-
-    /// get [`SigmaBoolean`] value
-    pub fn value(&self) -> &SigmaBoolean {
-        &self.0
-    }
-}
-
 /// Proof tree
 pub enum ProofTree {
     /// Unchecked tree
@@ -130,161 +56,75 @@ pub enum ProofTree {
 }
 
 impl ProofTree {
+    /// Create a new proof tree with a new challenge
     pub fn with_challenge(&self, challenge: Challenge) -> ProofTree {
-        todo!()
-    }
-}
-
-/// Unproven tree
-pub enum UnprovenTree {
-    UnprovenSchnorr(UnprovenSchnorr),
-}
-
-impl UnprovenTree {
-    pub fn real(&self) -> bool {
         match self {
-            UnprovenTree::UnprovenSchnorr(us) => !us.simulated,
+            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(),
+                    ),
+                },
+            },
         }
     }
 }
 
-pub struct UnprovenSchnorr {
-    proposition: ProveDlog,
-    commitment_opt: Option<FirstDlogProverMessage>,
-    randomness_opt: Option<BigInteger>,
-    challenge_opt: Option<Challenge>,
-    simulated: bool,
-}
-
-#[derive(PartialEq, Eq, Debug, Clone)]
-pub struct Challenge(FiatShamirHash);
-
-/// Unchecked sigma tree
-pub enum UncheckedSigmaTree {
-    UncheckedLeaf(UncheckedLeaf),
-}
-
-pub enum UncheckedLeaf {
-    UncheckedSchnorr(UncheckedSchnorr),
-}
-
-impl UncheckedLeaf {
-    pub fn proposition(&self) -> SigmaBoolean {
-        match self {
-            UncheckedLeaf::UncheckedSchnorr(us) => SigmaBoolean::ProofOfKnowledge(
-                SigmaProofOfKnowledgeTree::ProveDlog(us.proposition.clone()),
-            ),
-        }
+impl<T: Into<UncheckedTree>> From<T> for ProofTree {
+    fn from(t: T) -> Self {
+        ProofTree::UncheckedTree(t.into())
     }
 }
 
-pub struct UncheckedSchnorr {
-    proposition: ProveDlog,
-    commitment_opt: Option<FirstDlogProverMessage>,
-    challenge: Challenge,
-    second_message: SecondDlogProverMessage,
-}
+/// Proof tree leaf
+pub trait ProofTreeLeaf {
+    /// Get proposition
+    fn proposition(&self) -> SigmaBoolean;
 
-impl UncheckedSigmaTree {
-    // pub fn challenge(&self) -> Challenge {
-    //     match self {
-    //         UncheckedSigmaTree::UncheckedLeaf(UncheckedLeaf::UncheckedSchnorr(us)) => us.challenge,
-    //     }
-    // }
+    /// Get commitment
+    fn commitment_opt(&self) -> Option<FirstProverMessage>;
 }
 
-/// Unchecked tree
-pub enum UncheckedTree {
-    /// No proof needed
-    NoProof,
-    /// Unchecked sigma tree
-    UncheckedSigmaTree(UncheckedSigmaTree),
-}
+/** Size of the binary representation of any group element (2 ^ groupSizeBits == <number of elements in a group>) */
+pub 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;
+
+/// Byte array of Group size (32 bytes)
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct GroupSizedBytes(pub Box<[u8; GROUP_SIZE]>);
 
-fn serialize_sig(tree: UncheckedTree) -> Vec<u8> {
-    match tree {
-        UncheckedTree::NoProof => vec![],
-        UncheckedTree::UncheckedSigmaTree(_) => todo!(),
+impl From<GroupSizedBytes> for Scalar {
+    fn from(b: GroupSizedBytes) -> Self {
+        let sl: &[u8] = b.0.as_ref();
+        Scalar::from_bytes_reduced(sl.try_into().expect(""))
     }
 }
 
-///  Prover Step 7: Convert the tree to a string s for input to the Fiat-Shamir hash function.
-///  The conversion should be such that the tree can be unambiguously parsed and restored given the string.
-///  For each non-leaf node, the string should contain its type (OR or AND).
-///  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.
-fn fiat_shamir_tree_to_bytes(tree: &ProofTree) -> Vec<u8> {
-    // let propTree = ErgoTree.withSegregation(SigmaPropConstant(l.proposition))
-    // val propBytes = DefaultSerializer.serializeErgoTree(propTree)
-    // val commitmentBytes = l.commitmentOpt.get.bytes
-    // leafPrefix +:
-    //   ((Shorts.toByteArray(propBytes.length.toShort) ++ propBytes) ++
-    //     (Shorts.toByteArray(commitmentBytes.length.toShort) ++ commitmentBytes))
-    todo!()
+impl From<&[u8; GROUP_SIZE]> for GroupSizedBytes {
+    fn from(b: &[u8; GROUP_SIZE]) -> Self {
+        GroupSizedBytes(Box::new(*b))
+    }
 }
 
-/** Size of the binary representation of any group element (2 ^ groupSizeBits == <number of elements in a group>) */
-pub 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;
 /** A size of challenge in Sigma protocols, in bits.
  * If this anything but 192, threshold won't work, because we have polynomials over GF(2^192) and no others.
- * So DO NOT change the value without implementing polynomials over GF(2^soundnessBits) first
- * and changing code that calls on GF2_192 and GF2_192_Poly classes!!!
  * We get the challenge by reducing hash function output to proper value.
  */
 pub const SOUNDNESS_BITS: usize = 192;
+/// A size of challenge in Sigma protocols, in bytes
 pub const SOUNDNESS_BYTES: usize = SOUNDNESS_BITS / 8;
 
-#[derive(PartialEq, Eq, Debug, Clone)]
-pub struct FiatShamirHash(pub Box<[u8; SOUNDNESS_BYTES]>);
-
-pub fn fiat_shamir_hash_fn(input: &[u8]) -> FiatShamirHash {
-    // unwrap is safe 24 bytes is a valid hash size (<= 512 && 24 % 8 == 0)
-    let mut hasher = VarBlake2b::new(SOUNDNESS_BYTES).unwrap();
-    hasher.update(input);
-    let hash = hasher.finalize_boxed();
-    // unwrap is safe due to hash size is expected to be 24
-    FiatShamirHash(hash.try_into().unwrap())
-}
-
 #[cfg(test)]
 mod tests {
     use super::*;
-    use proptest::prelude::*;
-
-    impl Arbitrary for ProveDlog {
-        type Parameters = ();
-        type Strategy = BoxedStrategy<Self>;
-
-        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
-            (any::<EcPoint>()).prop_map(ProveDlog::new).boxed()
-        }
-    }
-
-    impl Arbitrary for SigmaBoolean {
-        type Parameters = ();
-        type Strategy = BoxedStrategy<Self>;
-
-        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
-            (any::<ProveDlog>())
-                .prop_map(|p| {
-                    SigmaBoolean::ProofOfKnowledge(SigmaProofOfKnowledgeTree::ProveDlog(p))
-                })
-                .boxed()
-        }
-    }
-
-    impl Arbitrary for SigmaProp {
-        type Parameters = ();
-        type Strategy = BoxedStrategy<Self>;
-
-        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
-            (any::<SigmaBoolean>()).prop_map(SigmaProp).boxed()
-        }
-    }
 
+    #[allow(clippy::assertions_on_constants)]
     #[test]
     fn ensure_soundness_bits() {
         // see SOUNDNESS_BITS doc comment
@@ -293,9 +133,4 @@ mod tests {
         assert!(SOUNDNESS_BYTES * 8 <= 512);
         assert!(SOUNDNESS_BYTES % 8 == 0);
     }
-
-    // #[test]
-    // fn fiat_shamir_tree_to_bytes_smoke_test() {
-    //     let tree = ProofTree
-    // }
 }
diff --git a/sigma-tree/src/sigma_protocol/challenge.rs b/sigma-tree/src/sigma_protocol/challenge.rs
new file mode 100644
index 000000000..71b4d6a79
--- /dev/null
+++ b/sigma-tree/src/sigma_protocol/challenge.rs
@@ -0,0 +1,33 @@
+use super::{fiat_shamir::FiatShamirHash, SOUNDNESS_BYTES};
+use k256::Scalar;
+#[cfg(test)]
+use proptest_derive::Arbitrary;
+use std::convert::TryInto;
+
+/// Challenge in Sigma protocol
+#[cfg_attr(test, derive(Arbitrary))]
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct Challenge(FiatShamirHash);
+
+impl Into<Scalar> for Challenge {
+    fn into(self) -> Scalar {
+        let v: [u8; SOUNDNESS_BYTES] = self.0.into();
+        // prepend zeroes to 32 bytes (big-endian)
+        let mut prefix = vec![0u8; 8];
+        prefix.append(&mut v.to_vec());
+        Scalar::from_bytes_reduced(prefix.as_slice().try_into().expect("32 bytes"))
+    }
+}
+
+impl Into<Vec<u8>> for Challenge {
+    fn into(self) -> Vec<u8> {
+        let arr: [u8; SOUNDNESS_BYTES] = self.0.into();
+        arr.to_vec()
+    }
+}
+
+impl From<FiatShamirHash> for Challenge {
+    fn from(fsh: FiatShamirHash) -> Self {
+        Challenge(fsh)
+    }
+}
diff --git a/sigma-tree/src/sigma_protocol/dlog_group.rs b/sigma-tree/src/sigma_protocol/dlog_group.rs
index aecf85e4c..cf78b0740 100644
--- a/sigma-tree/src/sigma_protocol/dlog_group.rs
+++ b/sigma-tree/src/sigma_protocol/dlog_group.rs
@@ -19,37 +19,63 @@ use super::DlogProverInput;
 use crate::serialization::{
     sigma_byte_reader::SigmaByteRead, SerializationError, SigmaSerializable,
 };
-use k256::arithmetic::{ProjectivePoint, Scalar};
-use k256::{arithmetic::AffinePoint, PublicKey};
-use num_bigint::{BigInt, Sign};
+use k256::{AffinePoint, ProjectivePoint, PublicKey, Scalar};
 use sigma_ser::vlq_encode;
 
-use std::{convert::TryInto, io};
+use elliptic_curve::weierstrass::public_key::FromPublicKey;
+use std::{
+    io,
+    ops::{Add, Mul, Neg},
+};
 
+/// Elliptic curve point
 #[derive(PartialEq, Debug, Clone)]
 pub struct EcPoint(ProjectivePoint);
 
 impl EcPoint {
+    /// Number of bytes to represent any group element as byte array
     pub const GROUP_SIZE: usize = 33;
 }
 
 impl Eq for EcPoint {}
 
+impl Mul<&EcPoint> for EcPoint {
+    type Output = EcPoint;
+
+    fn mul(self, other: &EcPoint) -> EcPoint {
+        EcPoint(ProjectivePoint::add(self.0, &other.0))
+    }
+}
+
+impl Neg for EcPoint {
+    type Output = EcPoint;
+
+    fn neg(self) -> EcPoint {
+        EcPoint(ProjectivePoint::neg(self.0))
+    }
+}
+
 /// The generator g of the group is an element of the group such that, when written multiplicatively, every element
 /// of the group is a power of g.
 pub fn generator() -> EcPoint {
     EcPoint(ProjectivePoint::generator())
 }
 
-/// the identity(infinity) element of this Dlog group
+/// The identity(infinity) element
 pub const fn identity() -> EcPoint {
     EcPoint(ProjectivePoint::identity())
 }
 
+/// Check if point is identity(infinity) element
 pub fn is_identity(ge: &EcPoint) -> bool {
     *ge == identity()
 }
 
+/// Calculates the inverse of the given group element
+pub fn inverse(ec: &EcPoint) -> EcPoint {
+    -ec.clone()
+}
+
 /// Raises the base GroupElement to the exponent. The result is another GroupElement.
 pub fn exponentiate(base: &EcPoint, exponent: &Scalar) -> EcPoint {
     if !is_identity(base) {
@@ -67,38 +93,20 @@ pub fn exponentiate(base: &EcPoint, exponent: &Scalar) -> EcPoint {
 /// Creates a random member of this Dlog group
 pub fn random_element() -> EcPoint {
     let sk = DlogProverInput::random();
-    let bytes = sk.w.to_bytes();
-    let bi = BigInt::from_bytes_be(Sign::Plus, &bytes[..]);
-
     exponentiate(&generator(), &sk.w)
 }
 
 /// Creates a random scalar, a big-endian integer in the range [0, n), where n is group order
 pub fn random_scalar_in_group_range() -> Scalar {
-    loop {
-        // Generate a new secret key using the operating system's
-        // cryptographically secure random number generator
-        let sk = k256::SecretKey::generate();
-        let bytes: [u8; 32] = sk
-            .secret_scalar()
-            .as_ref()
-            .as_slice()
-            .try_into()
-            .expect("expected 32 bytes");
-        // Returns None if the byte array does not contain
-        // a big-endian integer in the range [0, n), where n is group order.
-        let maybe_scalar = Scalar::from_bytes(bytes);
-        if bool::from(maybe_scalar.is_some()) {
-            break maybe_scalar.unwrap();
-        }
-    }
+    use rand::rngs::OsRng;
+    Scalar::generate_vartime(&mut OsRng)
 }
 
 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 = caff.unwrap().to_compressed_pubkey();
+            let pubkey = PublicKey::Compressed(caff.unwrap().into());
             w.write_all(pubkey.as_bytes())?;
         } else {
             // infinity point
@@ -115,7 +123,7 @@ impl SigmaSerializable for EcPoint {
             let pubkey = PublicKey::from_bytes(&buf[..]).ok_or_else(|| {
                 SerializationError::Misc("failed to parse PK from bytes".to_string())
             })?;
-            let cp = AffinePoint::from_pubkey(&pubkey);
+            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(),
diff --git a/sigma-tree/src/sigma_protocol/dlog_protocol.rs b/sigma-tree/src/sigma_protocol/dlog_protocol.rs
index 8e5d9608f..f8fe538b4 100644
--- a/sigma-tree/src/sigma_protocol/dlog_protocol.rs
+++ b/sigma-tree/src/sigma_protocol/dlog_protocol.rs
@@ -1,35 +1,118 @@
-use super::dlog_group::EcPoint;
-use crate::big_integer::BigInteger;
+//! Discrete logarithm signature protocol
 
-pub struct FirstDlogProverMessage(EcPoint);
-pub struct SecondDlogProverMessage(BigInteger);
+use super::{dlog_group::EcPoint, FirstProverMessage, ProverMessage};
+use crate::serialization::SigmaSerializable;
+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);
+
+impl From<EcPoint> for FirstDlogProverMessage {
+    fn from(ecp: EcPoint) -> Self {
+        FirstDlogProverMessage(ecp)
+    }
+}
+
+impl ProverMessage for FirstDlogProverMessage {
+    fn bytes(&self) -> Vec<u8> {
+        self.0.sigma_serialise_bytes()
+    }
+}
+
+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 {
+    /// message `z`
+    pub z: Scalar,
+}
+
+impl From<Scalar> for SecondDlogProverMessage {
+    fn from(z: Scalar) -> Self {
+        SecondDlogProverMessage { z }
+    }
+}
+
+/// Interactive prover
 pub mod interactive_prover {
     use super::{FirstDlogProverMessage, SecondDlogProverMessage};
-    use crate::{
-        big_integer::BigInteger,
-        sigma_protocol::{dlog_group, Challenge, DlogProverInput, ProveDlog},
-    };
+    use crate::sigma_protocol::{dlog_group, Challenge, DlogProverInput, ProveDlog};
+    use dlog_group::EcPoint;
+    use k256::Scalar;
 
+    /// TBD
     pub fn simulate(
-        public_input: &ProveDlog,
-        challenge: &Challenge,
+        _public_input: &ProveDlog,
+        _challenge: &Challenge,
     ) -> (FirstDlogProverMessage, SecondDlogProverMessage) {
         todo!()
     }
 
-    pub fn first_message(proposition: &ProveDlog) -> (BigInteger, FirstDlogProverMessage) {
-        let scalar = dlog_group::random_scalar_in_group_range();
+    /// Create first message from the prover and a randomness
+    pub 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, &scalar);
-        (scalar.into(), FirstDlogProverMessage(a))
+        let a = dlog_group::exponentiate(&g, &r);
+        (r, FirstDlogProverMessage(a))
     }
 
+    /// Create second message from the prover
     pub fn second_message(
         private_input: &DlogProverInput,
-        rnd: BigInteger,
+        rnd: Scalar,
         challenge: &Challenge,
     ) -> SecondDlogProverMessage {
-        todo!()
+        let e: Scalar = challenge.clone().into();
+        // modulo multiplication, no need to explicit mod op
+        let ew = e.mul(&private_input.w);
+        // modulo addition, no need to explicit mod op
+        let z = rnd.add(&ew);
+        z.into()
+    }
+
+    /**
+     * The function computes initial prover's commitment to randomness
+     * ("a" message of the sigma-protocol) based on the verifier's challenge ("e")
+     * and prover's response ("z")
+     *
+     * g^z = a*h^e => a = g^z/h^e
+     */
+    pub fn compute_commitment(
+        proposition: &ProveDlog,
+        challenge: &Challenge,
+        second_message: &SecondDlogProverMessage,
+    ) -> EcPoint {
+        let g = dlog_group::generator();
+        let h = *proposition.h.clone();
+        let e: Scalar = challenge.clone().into();
+        let g_z = dlog_group::exponentiate(&g, &second_message.z);
+        let h_e = dlog_group::exponentiate(&h, &e);
+        g_z * &dlog_group::inverse(&h_e)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::super::*;
+    use super::*;
+    use crate::sigma_protocol::DlogProverInput;
+    use proptest::prelude::*;
+
+    proptest! {
+
+        #[test]
+        fn test_compute_commitment(secret in any::<DlogProverInput>(), challenge in any::<Challenge>()) {
+            let pk = secret.public_image();
+            let (r, commitment) = interactive_prover::first_message();
+            let second_message = interactive_prover::second_message(&secret, r, &challenge);
+            let a = interactive_prover::compute_commitment(&pk, &challenge, &second_message);
+            prop_assert_eq!(a, commitment.0);
+        }
     }
 }
diff --git a/sigma-tree/src/sigma_protocol/fiat_shamir.rs b/sigma-tree/src/sigma_protocol/fiat_shamir.rs
new file mode 100644
index 000000000..008f586d2
--- /dev/null
+++ b/sigma-tree/src/sigma_protocol/fiat_shamir.rs
@@ -0,0 +1,97 @@
+//! Fiat-Shamir transformation
+
+use super::{
+    sigma_boolean::SigmaProp,
+    unchecked_tree::{UncheckedSigmaTree, UncheckedTree},
+    unproven_tree::UnprovenTree,
+    ProofTree, ProofTreeLeaf, ProverMessage, GROUP_SIZE, SOUNDNESS_BYTES,
+};
+use crate::{ast::Expr, serialization::SigmaSerializable, ErgoTree};
+use blake2::digest::{Update, VariableOutput};
+use blake2::VarBlake2b;
+use std::{
+    convert::{TryFrom, TryInto},
+    rc::Rc,
+};
+use thiserror::Error;
+
+#[cfg(test)]
+use proptest_derive::Arbitrary;
+
+/// Hash type for Fiat-Shamir hash function (24-bytes)
+#[cfg_attr(test, derive(Arbitrary))]
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct FiatShamirHash(pub Box<[u8; SOUNDNESS_BYTES]>);
+
+/// 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)
+    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
+    FiatShamirHash(taken.into_boxed_slice().try_into().unwrap())
+}
+
+impl Into<[u8; SOUNDNESS_BYTES]> for FiatShamirHash {
+    fn into(self) -> [u8; SOUNDNESS_BYTES] {
+        *self.0
+    }
+}
+
+impl TryFrom<&[u8]> for FiatShamirHash {
+    type Error = FiatShamirHashError;
+    fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
+        let arr: [u8; SOUNDNESS_BYTES] = value.try_into()?;
+        Ok(FiatShamirHash(Box::new(arr)))
+    }
+}
+
+/// Invalid byte array size
+#[derive(Error, Debug)]
+#[error("Invalid byte array size ({0})")]
+pub struct FiatShamirHashError(std::array::TryFromSliceError);
+
+impl From<std::array::TryFromSliceError> for FiatShamirHashError {
+    fn from(err: std::array::TryFromSliceError) -> Self {
+        FiatShamirHashError(err)
+    }
+}
+
+///  Prover Step 7: Convert the tree to a string s for input to the Fiat-Shamir hash function.
+///  The conversion should be such that the tree can be unambiguously parsed and restored given the string.
+///  For each non-leaf node, the string should contain its type (OR or AND).
+///  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;
+
+    let leaf: &dyn ProofTreeLeaf = match tree {
+        ProofTree::UncheckedTree(UncheckedTree::UncheckedSigmaTree(
+            UncheckedSigmaTree::UncheckedLeaf(ul),
+        )) => ul,
+        ProofTree::UnprovenTree(UnprovenTree::UnprovenLeaf(ul)) => ul,
+        _ => todo!(),
+    };
+
+    let prop_tree = ErgoTree::with_segregation(Rc::new(Expr::Const(
+        SigmaProp::new(leaf.proposition()).into(),
+    )));
+    let mut prop_bytes = prop_tree.sigma_serialise_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
+}
diff --git a/sigma-tree/src/sigma_protocol/private_input.rs b/sigma-tree/src/sigma_protocol/private_input.rs
new file mode 100644
index 000000000..c300fb85c
--- /dev/null
+++ b/sigma-tree/src/sigma_protocol/private_input.rs
@@ -0,0 +1,47 @@
+use super::{dlog_group, ProveDlog};
+use k256::Scalar;
+
+/// Secret key of discrete logarithm signature protocol
+#[derive(PartialEq, Debug, Clone)]
+pub struct DlogProverInput {
+    /// secret key value
+    pub w: Scalar,
+}
+
+impl DlogProverInput {
+    /// generates random secret in the range [0, n), where n is DLog group order.
+    pub fn random() -> DlogProverInput {
+        DlogProverInput {
+            w: dlog_group::random_scalar_in_group_range(),
+        }
+    }
+
+    /// public key of discrete logarithm signature protocol
+    pub fn public_image(&self) -> ProveDlog {
+        // test it, see https://github.com/ergoplatform/sigma-rust/issues/38
+        let g = dlog_group::generator();
+        ProveDlog::new(dlog_group::exponentiate(&g, &self.w))
+    }
+}
+
+/// Private inputs (secrets)
+pub enum PrivateInput {
+    /// Discrete logarithm prover input
+    DlogProverInput(DlogProverInput),
+    /// DH tuple prover input
+    DiffieHellmanTupleProverInput,
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use proptest::prelude::*;
+
+    impl Arbitrary for DlogProverInput {
+        type Parameters = ();
+        type Strategy = BoxedStrategy<Self>;
+        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
+            prop_oneof![Just(DlogProverInput::random()),].boxed()
+        }
+    }
+}
diff --git a/sigma-tree/src/sigma_protocol/prover.rs b/sigma-tree/src/sigma_protocol/prover.rs
index 861c4ef6f..945abd0ff 100644
--- a/sigma-tree/src/sigma_protocol/prover.rs
+++ b/sigma-tree/src/sigma_protocol/prover.rs
@@ -1,13 +1,12 @@
 //! Interpreter with enhanced functionality to prove statements.
 
-#![allow(dead_code)]
-#![allow(unused_variables)]
-#![allow(missing_docs)]
-
 use super::{
-    dlog_protocol, fiat_shamir_hash_fn, fiat_shamir_tree_to_bytes, serialize_sig, Challenge,
-    PrivateInput, ProofTree, SigmaBoolean, SigmaProofOfKnowledgeTree, UncheckedLeaf,
-    UncheckedSchnorr, UncheckedSigmaTree, UncheckedTree, UnprovenSchnorr, UnprovenTree,
+    dlog_protocol,
+    fiat_shamir::{fiat_shamir_hash_fn, fiat_shamir_tree_to_bytes},
+    sig_serializer::serialize_sig,
+    unchecked_tree::UncheckedSchnorr,
+    Challenge, PrivateInput, ProofTree, SigmaBoolean, SigmaProofOfKnowledgeTree,
+    UncheckedSigmaTree, UncheckedTree, UnprovenLeaf, UnprovenSchnorr, UnprovenTree,
 };
 use crate::{
     chain::{ContextExtension, ProverResult},
@@ -15,25 +14,22 @@ use crate::{
     ErgoTree, ErgoTreeParsingError,
 };
 
-pub struct TestProver {
-    pub secrets: Vec<PrivateInput>,
-}
-
-impl Evaluator for TestProver {}
-impl Prover for TestProver {
-    fn secrets(&self) -> &[PrivateInput] {
-        self.secrets.as_ref()
-    }
-}
-
+/// Prover errors
 #[derive(PartialEq, Eq, Debug, Clone)]
 pub enum ProverError {
+    /// Failed to parse ErgoTree
     ErgoTreeError(ErgoTreeParsingError),
+    /// Failed to evaluate ErgoTree
     EvalError(EvalError),
+    /// Script reduced to false
     ReducedToFalse,
+    /// Failed on step2(prover does not have enough witnesses to perform the proof)
     TreeRootIsNotReal,
+    /// Simulated leaf does not have challenge
     SimulatedLeafWithoutChallenge,
+    /// Lacking challenge on step 9 for "real" unproven tree
     RealUnprovenTreeWithoutChallenge,
+    /// Cannot find a secret for "real" unproven leaf
     SecretNotFound,
 }
 
@@ -43,9 +39,18 @@ impl From<ErgoTreeParsingError> for ProverError {
     }
 }
 
+/// Prover
 pub trait Prover: Evaluator {
+    /// Secrets of the prover
     fn secrets(&self) -> &[PrivateInput];
 
+    /**
+     * The comments in this section are taken from the algorithm for the
+     * Sigma-protocol prover as described in the ErgoScript white-paper
+     * https://ergoplatform.org/docs/ErgoScript.pdf , Appendix A
+     *
+     * Generate proofs for the given message for ErgoTree reduced to Sigma boolean expression
+     */
     fn prove(
         &self,
         tree: &ErgoTree,
@@ -60,7 +65,7 @@ pub trait Prover: Evaluator {
                 SigmaBoolean::TrivialProp(true) => Ok(UncheckedTree::NoProof),
                 SigmaBoolean::TrivialProp(false) => Err(ProverError::ReducedToFalse),
                 sb => {
-                    let tree = self.convert_to_unproven(sb);
+                    let tree = convert_to_unproven(sb);
                     let unchecked_tree = self.prove_to_unchecked(tree, message)?;
                     Ok(UncheckedTree::UncheckedSigmaTree(unchecked_tree))
                 }
@@ -71,25 +76,6 @@ pub trait Prover: Evaluator {
         })
     }
 
-    fn convert_to_unproven(&self, sigma_tree: SigmaBoolean) -> UnprovenTree {
-        match sigma_tree {
-            SigmaBoolean::TrivialProp(_) => todo!(), // TODO: why it's even here
-            SigmaBoolean::ProofOfKnowledge(pok) => match pok {
-                SigmaProofOfKnowledgeTree::ProveDHTuple(_) => todo!(),
-                SigmaProofOfKnowledgeTree::ProveDlog(prove_dlog) => {
-                    UnprovenTree::UnprovenSchnorr(UnprovenSchnorr {
-                        proposition: prove_dlog,
-                        commitment_opt: None,
-                        randomness_opt: None,
-                        challenge_opt: None,
-                        simulated: false,
-                    })
-                }
-            },
-            SigmaBoolean::CAND(_) => todo!(),
-        }
-    }
-
     /// 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)
@@ -103,7 +89,7 @@ pub trait Prover: Evaluator {
 
         // 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.real() {
+        if !step1.is_real() {
             return Err(ProverError::TreeRootIsNotReal);
         }
 
@@ -120,13 +106,14 @@ pub trait Prover: Evaluator {
         // 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 mut s = fiat_shamir_tree_to_bytes(&step6);
+        let var_name = fiat_shamir_tree_to_bytes(&step6);
+        let mut s = var_name;
 
         // 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 = fiat_shamir_hash_fn(s.as_slice());
-        let step8 = step6.with_challenge(Challenge(root_challenge));
+        let root_challenge: Challenge = fiat_shamir_hash_fn(s.as_slice()).into();
+        let step8 = step6.with_challenge(root_challenge);
 
         // Prover Step 9: complete the proof by computing challenges at real nodes and additionally responses at real leaves
         let step9 = self.proving(step8)?;
@@ -147,15 +134,16 @@ pub trait Prover: Evaluator {
     */
     fn mark_real(&self, unproven_tree: UnprovenTree) -> UnprovenTree {
         match unproven_tree {
-            UnprovenTree::UnprovenSchnorr(us) => {
+            UnprovenTree::UnprovenLeaf(UnprovenLeaf::UnprovenSchnorr(us)) => {
                 let secret_known = self.secrets().iter().any(|s| match s {
                     PrivateInput::DlogProverInput(dl) => dl.public_image() == us.proposition,
                     _ => false,
                 });
-                UnprovenTree::UnprovenSchnorr(UnprovenSchnorr {
+                UnprovenSchnorr {
                     simulated: !secret_known,
                     ..us
-                })
+                }
+                .into()
             }
         }
     }
@@ -165,7 +153,7 @@ pub trait Prover: Evaluator {
      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 {
+    fn polish_simulated(&self, _unproven_tree: UnprovenTree) -> UnprovenTree {
         todo!()
     }
 
@@ -178,7 +166,7 @@ pub trait Prover: Evaluator {
     */
     fn simulate_and_commit(&self, tree: UnprovenTree) -> Result<ProofTree, ProverError> {
         match tree {
-            UnprovenTree::UnprovenSchnorr(us) => {
+            UnprovenTree::UnprovenLeaf(UnprovenLeaf::UnprovenSchnorr(us)) => {
                 if us.simulated {
                     // Step 5 (simulated leaf -- complete the simulation)
                     if let Some(challenge) = us.challenge_opt {
@@ -186,30 +174,29 @@ pub trait Prover: Evaluator {
                             &us.proposition,
                             &challenge,
                         );
-                        Ok(ProofTree::UncheckedTree(UncheckedTree::UncheckedSigmaTree(
-                            UncheckedSigmaTree::UncheckedLeaf(UncheckedLeaf::UncheckedSchnorr(
-                                UncheckedSchnorr {
-                                    proposition: us.proposition,
-                                    commitment_opt: Some(fm),
-                                    challenge,
-                                    second_message: sm,
-                                },
-                            )),
-                        )))
+                        Ok(ProofTree::UncheckedTree(
+                            UncheckedSchnorr {
+                                proposition: us.proposition,
+                                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(&us.proposition);
-                    Ok(ProofTree::UnprovenTree(UnprovenTree::UnprovenSchnorr(
+                    let (r, commitment) = dlog_protocol::interactive_prover::first_message();
+                    Ok(ProofTree::UnprovenTree(
                         UnprovenSchnorr {
                             commitment_opt: Some(commitment),
                             randomness_opt: Some(r),
                             ..us
-                        },
-                    )))
+                        }
+                        .into(),
+                    ))
                 }
             }
         }
@@ -226,7 +213,9 @@ pub trait Prover: Evaluator {
         match tree {
             ProofTree::UncheckedTree(_) => Ok(tree),
             ProofTree::UnprovenTree(unproven_tree) => match unproven_tree {
-                UnprovenTree::UnprovenSchnorr(us) if unproven_tree.real() => {
+                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()
@@ -242,16 +231,13 @@ pub trait Prover: Evaluator {
                                 us.randomness_opt.unwrap(),
                                 &challenge,
                             );
-                            Ok(ProofTree::UncheckedTree(UncheckedTree::UncheckedSigmaTree(
-                                UncheckedSigmaTree::UncheckedLeaf(UncheckedLeaf::UncheckedSchnorr(
-                                    UncheckedSchnorr {
-                                        proposition: us.proposition,
-                                        commitment_opt: None,
-                                        challenge,
-                                        second_message: z,
-                                    },
-                                )),
-                            )))
+                            Ok(UncheckedSchnorr {
+                                proposition: us.proposition,
+                                commitment_opt: None,
+                                challenge,
+                                second_message: z,
+                            }
+                            .into())
                         } else {
                             Err(ProverError::SecretNotFound)
                         }
@@ -265,61 +251,91 @@ pub trait Prover: Evaluator {
     }
 }
 
-// #[cfg(test)]
-// mod tests {
-//     use super::*;
-//     use crate::{
-//         ast::{Constant, ConstantVal, Expr},
-//         sigma_protocol::{DlogProverInput, SigmaProp},
-//         types::SType,
-//     };
-//     use std::rc::Rc;
+fn convert_to_unproven(sigma_tree: SigmaBoolean) -> UnprovenTree {
+    match sigma_tree {
+        // TODO: why it's even here? Make another SigmaBoolean without trivial props?
+        SigmaBoolean::TrivialProp(_) => todo!(),
+        SigmaBoolean::ProofOfKnowledge(pok) => match pok {
+            SigmaProofOfKnowledgeTree::ProveDHTuple(_) => todo!(),
+            SigmaProofOfKnowledgeTree::ProveDlog(prove_dlog) => UnprovenSchnorr {
+                proposition: prove_dlog,
+                commitment_opt: None,
+                randomness_opt: None,
+                challenge_opt: None,
+                simulated: false,
+            }
+            .into(),
+        },
+        SigmaBoolean::CAND(_) => todo!(),
+    }
+}
 
-//     #[test]
-//     fn test_prove_true_prop() {
-//         let bool_true_tree = ErgoTree::from(Rc::new(Expr::Const(Constant {
-//             tpe: SType::SBoolean,
-//             v: ConstantVal::Boolean(true),
-//         })));
-//         let message = vec![0u8; 100];
+/// Test prover implementation
+pub struct TestProver {
+    /// secrets to be used in proofs generation
+    pub secrets: Vec<PrivateInput>,
+}
 
-//         let prover = TestProver { secrets: vec![] };
-//         let res = prover.prove(&bool_true_tree, &Env::empty(), message.as_slice());
-//         assert!(res.is_ok());
-//         assert!(res.unwrap().proof.is_empty());
-//     }
+impl Evaluator for TestProver {}
+impl Prover for TestProver {
+    fn secrets(&self) -> &[PrivateInput] {
+        self.secrets.as_ref()
+    }
+}
 
-//     #[test]
-//     fn test_prove_false_prop() {
-//         let bool_false_tree = ErgoTree::from(Rc::new(Expr::Const(Constant {
-//             tpe: SType::SBoolean,
-//             v: ConstantVal::Boolean(false),
-//         })));
-//         let message = vec![0u8; 100];
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::{
+        ast::{Constant, ConstantVal, Expr},
+        sigma_protocol::DlogProverInput,
+        types::SType,
+    };
+    use std::rc::Rc;
 
-//         let prover = TestProver { secrets: vec![] };
-//         let res = prover.prove(&bool_false_tree, &Env::empty(), message.as_slice());
-//         assert!(res.is_err());
-//         assert_eq!(res.err().unwrap(), ProverError::ReducedToFalse);
-//     }
+    #[test]
+    fn test_prove_true_prop() {
+        let bool_true_tree = ErgoTree::from(Rc::new(Expr::Const(Constant {
+            tpe: SType::SBoolean,
+            v: ConstantVal::Boolean(true),
+        })));
+        let message = vec![0u8; 100];
 
-//     #[test]
-//     fn test_prove_pk_prop() {
-//         let secret = DlogProverInput::random();
-//         let pk = secret.public_image();
-//         let tree = ErgoTree::from(Rc::new(Expr::Const(Constant {
-//             tpe: SType::SSigmaProp,
-//             v: ConstantVal::SigmaProp(Box::new(SigmaProp(SigmaBoolean::ProofOfKnowledge(
-//                 SigmaProofOfKnowledgeTree::ProveDlog(pk),
-//             )))),
-//         })));
-//         let message = vec![0u8; 100];
+        let prover = TestProver { secrets: vec![] };
+        let res = prover.prove(&bool_true_tree, &Env::empty(), message.as_slice());
+        assert!(res.is_ok());
+        assert!(res.unwrap().proof.is_empty());
+    }
 
-//         let prover = TestProver {
-//             secrets: vec![PrivateInput::DlogProverInput(secret)],
-//         };
-//         let res = prover.prove(&tree, &Env::empty(), message.as_slice());
-//         // assert!(res.is_ok());
-//         assert!(!res.unwrap().proof.is_empty());
-//     }
-// }
+    #[test]
+    fn test_prove_false_prop() {
+        let bool_false_tree = ErgoTree::from(Rc::new(Expr::Const(Constant {
+            tpe: SType::SBoolean,
+            v: ConstantVal::Boolean(false),
+        })));
+        let message = vec![0u8; 100];
+
+        let prover = TestProver { secrets: vec![] };
+        let res = prover.prove(&bool_false_tree, &Env::empty(), message.as_slice());
+        assert!(res.is_err());
+        assert_eq!(res.err().unwrap(), ProverError::ReducedToFalse);
+    }
+
+    #[test]
+    fn test_prove_pk_prop() {
+        let secret = DlogProverInput::random();
+        let pk = secret.public_image();
+        let tree = ErgoTree::from(Rc::new(Expr::Const(Constant {
+            tpe: SType::SSigmaProp,
+            v: pk.into(),
+        })));
+        let message = vec![0u8; 100];
+
+        let prover = TestProver {
+            secrets: vec![PrivateInput::DlogProverInput(secret)],
+        };
+        let res = prover.prove(&tree, &Env::empty(), message.as_slice());
+        assert!(res.is_ok());
+        assert!(!res.unwrap().proof.is_empty());
+    }
+}
diff --git a/sigma-tree/src/sigma_protocol/sig_serializer.rs b/sigma-tree/src/sigma_protocol/sig_serializer.rs
new file mode 100644
index 000000000..7af544313
--- /dev/null
+++ b/sigma-tree/src/sigma_protocol/sig_serializer.rs
@@ -0,0 +1,75 @@
+//! Serialization of proof tree signatures
+
+use super::{
+    fiat_shamir::FiatShamirHash,
+    unchecked_tree::{UncheckedLeaf, UncheckedSchnorr},
+    Challenge, GroupSizedBytes, SigmaBoolean, SigmaProofOfKnowledgeTree, UncheckedSigmaTree,
+    UncheckedTree,
+};
+use k256::Scalar;
+use std::convert::{TryFrom, TryInto};
+
+/// Serialize proof tree signatures
+pub fn serialize_sig(tree: UncheckedTree) -> Vec<u8> {
+    match tree {
+        UncheckedTree::NoProof => vec![],
+        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());
+            res
+        }
+        _ => 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_bytes: Vec<u8>,
+) -> Result<UncheckedTree, SigParsingError> {
+    if proof_bytes.is_empty() {
+        Err(SigParsingError::InvalidProofSize)
+    } else {
+        // 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));
+                Ok(UncheckedSchnorr {
+                    proposition: dl,
+                    commitment_opt: None,
+                    challenge,
+                    second_message: z.into(),
+                }
+                .into())
+            }
+            _ => todo!(),
+        }
+    }
+}
+
+/// Errors when parsing proof tree signatures
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub enum SigParsingError {
+    /// Invalid proof size (expected 32 bytes)
+    InvalidProofSize,
+}
diff --git a/sigma-tree/src/sigma_protocol/sigma_boolean.rs b/sigma-tree/src/sigma_protocol/sigma_boolean.rs
new file mode 100644
index 000000000..2d834a78d
--- /dev/null
+++ b/sigma-tree/src/sigma_protocol/sigma_boolean.rs
@@ -0,0 +1,149 @@
+//! Sigma boolean types
+
+use super::dlog_group::EcPoint;
+use crate::serialization::op_code::OpCode;
+use std::convert::TryInto;
+
+/// Construct a new SigmaBoolean value representing public key of discrete logarithm signature protocol.
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct ProveDlog {
+    /// public key
+    pub h: Box<EcPoint>,
+}
+
+impl ProveDlog {
+    /// create new public key
+    pub fn new(ecpoint: EcPoint) -> ProveDlog {
+        ProveDlog {
+            h: Box::new(ecpoint),
+        }
+    }
+}
+
+impl From<ProveDlog> for SigmaProofOfKnowledgeTree {
+    fn from(pd: ProveDlog) -> Self {
+        SigmaProofOfKnowledgeTree::ProveDlog(pd)
+    }
+}
+
+/// Construct a new SigmaProp value representing public key of Diffie Hellman signature protocol.
+/// Common input: (g,h,u,v)
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct ProveDHTuple {
+    gv: Box<EcPoint>,
+    hv: Box<EcPoint>,
+    uv: Box<EcPoint>,
+    vv: Box<EcPoint>,
+}
+
+/// Sigma proposition
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub enum SigmaProofOfKnowledgeTree {
+    /// public key of Diffie Hellman signature protocol
+    ProveDHTuple(ProveDHTuple),
+    /// public key of discrete logarithm signature protocol
+    ProveDlog(ProveDlog),
+}
+
+/// Algebraic data type of sigma proposition expressions
+/// Values of this type are used as values of SigmaProp type
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub enum SigmaBoolean {
+    /// Represents boolean values (true/false)
+    TrivialProp(bool),
+    /// Sigma proposition
+    ProofOfKnowledge(SigmaProofOfKnowledgeTree),
+    /// AND conjunction for sigma propositions
+    CAND(Vec<SigmaBoolean>),
+}
+
+impl SigmaBoolean {
+    /// get OpCode for serialization
+    pub fn op_code(&self) -> OpCode {
+        match self {
+            SigmaBoolean::ProofOfKnowledge(SigmaProofOfKnowledgeTree::ProveDlog(_)) => {
+                OpCode::PROVE_DLOG
+            }
+            _ => todo!(),
+        }
+    }
+}
+
+impl<T: Into<SigmaProofOfKnowledgeTree>> From<T> for SigmaBoolean {
+    fn from(t: T) -> Self {
+        SigmaBoolean::ProofOfKnowledge(t.into())
+    }
+}
+
+/// Failed to extract specified underlying type from SigmaBoolean
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct ConversionError;
+
+impl TryInto<ProveDlog> for SigmaBoolean {
+    type Error = ConversionError;
+    fn try_into(self) -> Result<ProveDlog, Self::Error> {
+        match self {
+            SigmaBoolean::ProofOfKnowledge(SigmaProofOfKnowledgeTree::ProveDlog(pd)) => Ok(pd),
+            _ => Err(ConversionError),
+        }
+    }
+}
+
+/// Proposition which can be proven and verified by sigma protocol.
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct SigmaProp(SigmaBoolean);
+
+impl SigmaProp {
+    /// create new sigma propostion from [`SigmaBoolean`] value
+    pub fn new(sbool: SigmaBoolean) -> Self {
+        SigmaProp { 0: sbool }
+    }
+
+    /// get [`SigmaBoolean`] value
+    pub fn value(&self) -> &SigmaBoolean {
+        &self.0
+    }
+}
+
+impl<T: Into<SigmaBoolean>> From<T> for SigmaProp {
+    fn from(t: T) -> Self {
+        SigmaProp(t.into())
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use proptest::prelude::*;
+
+    impl Arbitrary for ProveDlog {
+        type Parameters = ();
+        type Strategy = BoxedStrategy<Self>;
+
+        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
+            (any::<EcPoint>()).prop_map(ProveDlog::new).boxed()
+        }
+    }
+
+    impl Arbitrary for SigmaBoolean {
+        type Parameters = ();
+        type Strategy = BoxedStrategy<Self>;
+
+        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
+            (any::<ProveDlog>())
+                .prop_map(|p| {
+                    SigmaBoolean::ProofOfKnowledge(SigmaProofOfKnowledgeTree::ProveDlog(p))
+                })
+                .boxed()
+        }
+    }
+
+    impl Arbitrary for SigmaProp {
+        type Parameters = ();
+        type Strategy = BoxedStrategy<Self>;
+
+        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
+            (any::<SigmaBoolean>()).prop_map(SigmaProp::new).boxed()
+        }
+    }
+}
diff --git a/sigma-tree/src/sigma_protocol/unchecked_tree.rs b/sigma-tree/src/sigma_protocol/unchecked_tree.rs
new file mode 100644
index 000000000..55ba05854
--- /dev/null
+++ b/sigma-tree/src/sigma_protocol/unchecked_tree.rs
@@ -0,0 +1,92 @@
+//! Unchecked proof tree types
+
+use super::{
+    dlog_protocol::{FirstDlogProverMessage, SecondDlogProverMessage},
+    sigma_boolean::{ProveDlog, SigmaBoolean, SigmaProofOfKnowledgeTree},
+    Challenge, FirstProverMessage, ProofTree, ProofTreeLeaf,
+};
+
+/// Unchecked tree
+#[derive(PartialEq, Debug, Clone)]
+pub enum UncheckedTree {
+    /// No proof needed
+    NoProof,
+    /// Unchecked sigma tree
+    UncheckedSigmaTree(UncheckedSigmaTree),
+}
+
+/// Unchecked sigma tree
+#[derive(PartialEq, Debug, Clone)]
+pub enum UncheckedSigmaTree {
+    /// Unchecked leaf
+    UncheckedLeaf(UncheckedLeaf),
+    /// Unchecked conjecture (OR, AND, ...)
+    UncheckedConjecture,
+}
+
+impl UncheckedSigmaTree {
+    /// Get challenge
+    pub fn challenge(&self) -> Challenge {
+        match self {
+            UncheckedSigmaTree::UncheckedLeaf(UncheckedLeaf::UncheckedSchnorr(us)) => {
+                us.challenge.clone()
+            }
+            UncheckedSigmaTree::UncheckedConjecture => todo!(),
+        }
+    }
+}
+
+impl<T: Into<UncheckedLeaf>> From<T> for UncheckedSigmaTree {
+    fn from(t: T) -> Self {
+        UncheckedSigmaTree::UncheckedLeaf(t.into())
+    }
+}
+
+impl From<UncheckedSigmaTree> for ProofTree {
+    fn from(ust: UncheckedSigmaTree) -> Self {
+        ProofTree::UncheckedTree(UncheckedTree::UncheckedSigmaTree(ust))
+    }
+}
+
+/// Unchecked leaf
+#[derive(PartialEq, Debug, Clone)]
+pub enum UncheckedLeaf {
+    /// Unchecked Schnorr
+    UncheckedSchnorr(UncheckedSchnorr),
+}
+
+impl ProofTreeLeaf for UncheckedLeaf {
+    fn proposition(&self) -> SigmaBoolean {
+        match self {
+            UncheckedLeaf::UncheckedSchnorr(us) => SigmaBoolean::ProofOfKnowledge(
+                SigmaProofOfKnowledgeTree::ProveDlog(us.proposition.clone()),
+            ),
+        }
+    }
+    fn commitment_opt(&self) -> Option<FirstProverMessage> {
+        match self {
+            UncheckedLeaf::UncheckedSchnorr(us) => us.commitment_opt.clone().map(Into::into),
+        }
+    }
+}
+
+impl From<UncheckedSchnorr> for UncheckedLeaf {
+    fn from(us: UncheckedSchnorr) -> Self {
+        UncheckedLeaf::UncheckedSchnorr(us)
+    }
+}
+
+#[allow(missing_docs)]
+#[derive(PartialEq, Debug, Clone)]
+pub struct UncheckedSchnorr {
+    pub proposition: ProveDlog,
+    pub commitment_opt: Option<FirstDlogProverMessage>,
+    pub challenge: Challenge,
+    pub second_message: SecondDlogProverMessage,
+}
+
+impl From<UncheckedSchnorr> for UncheckedTree {
+    fn from(us: UncheckedSchnorr) -> Self {
+        UncheckedTree::UncheckedSigmaTree(us.into())
+    }
+}
diff --git a/sigma-tree/src/sigma_protocol/unproven_tree.rs b/sigma-tree/src/sigma_protocol/unproven_tree.rs
new file mode 100644
index 000000000..5ce932ab9
--- /dev/null
+++ b/sigma-tree/src/sigma_protocol/unproven_tree.rs
@@ -0,0 +1,69 @@
+//! Unproven tree types
+
+use super::{
+    dlog_protocol::FirstDlogProverMessage,
+    sigma_boolean::{ProveDlog, SigmaBoolean, SigmaProofOfKnowledgeTree},
+    Challenge, FirstProverMessage, ProofTreeLeaf,
+};
+use k256::Scalar;
+
+/// Unproven trees
+pub enum UnprovenTree {
+    /// Unproven leaf
+    UnprovenLeaf(UnprovenLeaf),
+    // UnprovenConjecture,
+}
+
+impl UnprovenTree {
+    /// Is real or simulated
+    pub fn is_real(&self) -> bool {
+        match self {
+            UnprovenTree::UnprovenLeaf(UnprovenLeaf::UnprovenSchnorr(us)) => !us.simulated,
+            // UnprovenTree::UnprovenConjecture => todo!(),
+        }
+    }
+}
+
+impl<T: Into<UnprovenLeaf>> From<T> for UnprovenTree {
+    fn from(t: T) -> Self {
+        UnprovenTree::UnprovenLeaf(t.into())
+    }
+}
+
+/// Unproven leaf types
+pub enum UnprovenLeaf {
+    /// Unproven Schnorr
+    UnprovenSchnorr(UnprovenSchnorr),
+}
+
+impl ProofTreeLeaf for UnprovenLeaf {
+    fn proposition(&self) -> SigmaBoolean {
+        match self {
+            UnprovenLeaf::UnprovenSchnorr(us) => SigmaBoolean::ProofOfKnowledge(
+                SigmaProofOfKnowledgeTree::ProveDlog(us.proposition.clone()),
+            ),
+        }
+    }
+
+    fn commitment_opt(&self) -> Option<FirstProverMessage> {
+        match self {
+            UnprovenLeaf::UnprovenSchnorr(us) => us.commitment_opt.clone().map(Into::into),
+        }
+    }
+}
+
+impl From<UnprovenSchnorr> for UnprovenLeaf {
+    fn from(us: UnprovenSchnorr) -> Self {
+        UnprovenLeaf::UnprovenSchnorr(us)
+    }
+}
+
+#[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,
+}
diff --git a/sigma-tree/src/sigma_protocol/verifier.rs b/sigma-tree/src/sigma_protocol/verifier.rs
index 1dae282d9..1fefa8af5 100644
--- a/sigma-tree/src/sigma_protocol/verifier.rs
+++ b/sigma-tree/src/sigma_protocol/verifier.rs
@@ -1,17 +1,24 @@
 //! Verifier
 
-#![allow(dead_code)]
-#![allow(unused_variables)]
-#![allow(missing_docs)]
-
-use super::SigmaBoolean;
+use super::{
+    dlog_protocol,
+    fiat_shamir::{fiat_shamir_hash_fn, fiat_shamir_tree_to_bytes},
+    sig_serializer::parse_sig_compute_challenges,
+    unchecked_tree::{UncheckedLeaf, UncheckedSchnorr},
+    SigmaBoolean, UncheckedSigmaTree, UncheckedTree,
+};
 use crate::{
     eval::{Env, EvalError, Evaluator},
     ErgoTree, ErgoTreeParsingError,
 };
+use dlog_protocol::FirstDlogProverMessage;
 
+/// Errors on proof verification
+#[derive(PartialEq, Eq, Debug, Clone)]
 pub enum VerifierError {
+    /// Failed to parse ErgoTree from bytes
     ErgoTreeError(ErgoTreeParsingError),
+    /// Failed to evaluate ErgoTree
     EvalError(EvalError),
 }
 
@@ -27,14 +34,22 @@ impl From<EvalError> for VerifierError {
     }
 }
 
+/// Result of Box.ergoTree verification procedure (see `verify` method).
 pub struct VerificationResult {
-    result: bool,
-    cost: u64,
+    /// result of SigmaProp condition verification via sigma protocol
+    pub result: bool,
+    /// estimated cost of contract execution
+    pub cost: u64,
 }
 
+/// Verifier for the proofs generater by [`Prover`]
 pub trait Verifier: Evaluator {
+    /// Executes the script in a given context.
+    /// Step 1: Deserialize context variables
+    /// Step 2: Evaluate expression and produce SigmaProp value, which is zero-knowledge statement (see also `SigmaBoolean`).
+    /// Step 3: Verify that the proof is presented to satisfy SigmaProp conditions.
     fn verify(
-        &mut self,
+        &self,
         tree: &ErgoTree,
         env: &Env,
         proof: &[u8],
@@ -44,7 +59,25 @@ pub trait Verifier: Evaluator {
         let cprop = self.reduce_to_crypto(expr.as_ref(), env)?.sigma_prop;
         let res: bool = match cprop {
             SigmaBoolean::TrivialProp(b) => b,
-            sb => todo!(),
+            sb => {
+                // Perform Verifier Steps 1-3
+                match parse_sig_compute_challenges(sb, proof.to_vec()) {
+                    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()
+                    }
+                    Ok(_) => todo!(),
+                }
+            }
         };
         Ok(VerificationResult {
             result: res,
@@ -52,3 +85,168 @@ 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.
+ */
+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
+            }
+            .into()
+        }
+        UncheckedSigmaTree::UncheckedConjecture => todo!(),
+    }
+}
+
+/// Test Verifier implementation
+pub struct TestVerifier;
+
+impl Evaluator for TestVerifier {}
+impl Verifier for TestVerifier {}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::{
+        ast::{Constant, Expr},
+        sigma_protocol::{
+            prover::{Prover, TestProver},
+            DlogProverInput, PrivateInput,
+        },
+        types::SType,
+    };
+    use proptest::prelude::*;
+    use std::rc::Rc;
+
+    proptest! {
+        #[test]
+        fn test_prover_verifier_p2pk(secret in any::<DlogProverInput>(), message in any::<Vec<u8>>()) {
+            prop_assume!(!message.is_empty());
+            let pk = secret.public_image();
+            let tree = ErgoTree::from(Rc::new(Expr::Const(Constant {
+                tpe: SType::SSigmaProp,
+                v: pk.into(),
+            })));
+
+            let prover = TestProver {
+                secrets: vec![PrivateInput::DlogProverInput(secret)],
+            };
+            let res = prover.prove(&tree, &Env::empty(), message.as_slice());
+            let proof = res.unwrap().proof;
+
+            let verifier = TestVerifier;
+            let ver_res = verifier.verify(&tree, &Env::empty(), proof.as_slice(), message.as_slice());
+            prop_assert_eq!(ver_res.unwrap().result, true);
+        }
+    }
+
+    #[test]
+    #[cfg(feature = "with-serde")]
+    fn test_proof_from_mainnet() {
+        use crate::chain::{AddressEncoder, Base16DecodedBytes, NetworkPrefix, Transaction};
+        use std::convert::TryFrom;
+        let tx_json = r#"
+         {
+      "id": "0e6acf3f18b95bdc5bb1b060baa1eafe53bd89fb08b0e86d6cc00fbdd9e43189",
+      "inputs": [
+        {
+          "boxId": "f353ae1b2027e40ea318e7a2673ea4bbaa281b7acee518a0994c5cbdefb05f55",
+          "spendingProof": {
+            "proofBytes":[],
+            "extension": {"values": {}}
+          }
+        },
+        {
+          "boxId": "56111b039b86f71004b768d2e8b4579f1d79e28e7a617fd5add57a5239498c26",
+          "spendingProof": {
+            "proofBytes":[],
+            "extension": {"values": {}}
+          }
+        }
+      ],
+      "dataInputs": [
+        {
+          "boxId": "e26d41ed030a30cd563681e72f0b9c07825ac983f8c253a87a43c1da21958ece"
+        }
+      ],
+      "outputs": [
+        {
+          "boxId": "55be517150fcb7f0f1661ad3ab30f1ac62084b83ad6aa772579bc06cbb52832e",
+          "value": 1000000,
+          "ergoTree": "100604000400050004000e20b662db51cf2dc39f110a021c2a31c74f0a1a18ffffbf73e8a051a7b8c0f09ebc0e2079974b2314c531e62776e6bc4babff35b37b178cebf0976fc0f416ff34ddbc4fd803d601b2a5730000d602e4c6a70407d603b2db6501fe730100ea02d1ededededed93e4c672010407720293e4c67201050ec5720391e4c672010605730293c27201c2a793db63087201db6308a7ed938cb2db6308720373030001730493cbc272037305cd7202",
+          "assets": [
+            {
+              "tokenId": "12caaacb51c89646fac9a3786eb98d0113bd57d68223ccc11754a4f67281daed",
+              "amount": 1
+            }
+          ],
+          "creationHeight": 299218,
+          "additionalRegisters": {
+            "R4": "070327e65711a59378c59359c3e1d0f7abe906479eccb76094e50fe79d743ccc15e6",
+            "R5": "0e20e26d41ed030a30cd563681e72f0b9c07825ac983f8c253a87a43c1da21958ece",
+            "R6": "05feaff5de0f"
+          },
+          "transactionId": "0e6acf3f18b95bdc5bb1b060baa1eafe53bd89fb08b0e86d6cc00fbdd9e43189",
+          "index": 0
+        },
+        {
+          "boxId": "fa4a484c855d32a60987a4ddcf1c506aa6bab1c4cb0293c2d5ff35fcd11f2c7b",
+          "value": 1000000,
+          "ergoTree": "1005040004000e36100204a00b08cd0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ea02d192a39a8cc7a701730073011001020402d19683030193a38cc7b2a57300000193c2b2a57301007473027303830108cdeeac93b1a57304",
+          "assets": [],
+          "creationHeight": 299218,
+          "additionalRegisters": {},
+          "transactionId": "0e6acf3f18b95bdc5bb1b060baa1eafe53bd89fb08b0e86d6cc00fbdd9e43189",
+          "index": 1
+        },
+        {
+          "boxId": "3dee27d0dfb193fd6a263cf2b5b58cab99cb640d1443cd1ce63d909ad3a54197",
+          "value": 44516500000,
+          "ergoTree": "0008cd0327e65711a59378c59359c3e1d0f7abe906479eccb76094e50fe79d743ccc15e6",
+          "assets": [],
+          "creationHeight": 299218,
+          "additionalRegisters": {},
+          "transactionId": "0e6acf3f18b95bdc5bb1b060baa1eafe53bd89fb08b0e86d6cc00fbdd9e43189",
+          "index": 2
+        }
+      ],
+      "size": 673
+    }
+        "#;
+
+        let encoder = AddressEncoder::new(NetworkPrefix::Mainnet);
+        let decoded_addr = encoder
+            .parse_address_from_str("9gmNsqrqdSppLUBqg2UzREmmivgqh1r3jmNcLAc53hk3YCvAGWE")
+            .unwrap();
+
+        let ergo_tree = decoded_addr.script().unwrap();
+
+        let spending_proof_input1 = Base16DecodedBytes::try_from("6542a8b8914b103dcbc36d77da3bd58e42ca35755a5190b507764b0bae330b924ce86acfa1b5f9bfc8216c3c4628738e8274d902bea06b48".to_string()).unwrap();
+        let tx: Transaction = serde_json::from_str(tx_json).unwrap();
+        let tx_id_str: String = tx.id().into();
+        assert_eq!(
+            "0e6acf3f18b95bdc5bb1b060baa1eafe53bd89fb08b0e86d6cc00fbdd9e43189",
+            tx_id_str
+        );
+        let message = tx.bytes_to_sign();
+        let verifier = TestVerifier;
+        let ver_res = verifier.verify(
+            &ergo_tree,
+            &Env::empty(),
+            spending_proof_input1.0.as_slice(),
+            message.as_slice(),
+        );
+        assert_eq!(ver_res.unwrap().result, true);
+    }
+}


Test patch:
diff --git a/bindings/ergo-wallet-lib-wasm/tests/transaction.rs b/bindings/ergo-wallet-lib-wasm/tests/transaction.rs
index 4b00e1765..3c343e78a 100644
--- a/bindings/ergo-wallet-lib-wasm/tests/transaction.rs
+++ b/bindings/ergo-wallet-lib-wasm/tests/transaction.rs
@@ -35,3 +35,10 @@ fn test_signed_p2pk_transaction() {
     );
     assert!(res.is_err());
 }
+
+#[wasm_bindgen_test]
+fn test_random() {
+    let sk1 = SecretKey::random_dlog();
+    let sk2 = SecretKey::random_dlog();
+    assert_ne!(sk1, sk2);
+}