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

Issue:
[400 SigmaUSD] `AvlTree.insert` operation
Create `AvlTreeData` struct and use in `Value::AvlTree(AvlTreeData)` and in `Literal::AvlTree(AvlTreeData)` and implement serialization (`SigmaSerializable` trait).
Scala reference implementation - https://github.com/ScorexFoundation/sigmastate-interpreter/blob/c863a9b1a82589e47b15f76f3affdb30a475e740/sigmastate/src/main/scala/sigmastate/AvlTreeData.scala#L42-L101

Create `savltree` modules for AvlTree methods definitions and evaluation similar to the existing `sbox` modules.
Add `AvlTree.insert` method in `savltree` module.
Scala reference implementation - https://github.com/ScorexFoundation/sigmastate-interpreter/blob/c863a9b1a82589e47b15f76f3affdb30a475e740/sigmastate/src/main/scala/sigmastate/types.scala#L2232-L2281

Use [`BatchAvlVerifier`](https://github.com/knizhnik/scorex_crypto_avltree/blob/36a0b47742d9d8f749ce95d2a794be88a03d13ec/src/batch_avl_verifier.rs#L8-L33) from https://crates.io/crates/scorex_crypto_avltree crate.

Use the existing `ADDigest` type for tree digest.


Discussion / hints:
Starting on this issue.

Fix patch:
diff --git a/bindings/ergo-lib-wasm/Cargo.toml b/bindings/ergo-lib-wasm/Cargo.toml
index a7e90770d..c15726d94 100644
--- a/bindings/ergo-lib-wasm/Cargo.toml
+++ b/bindings/ergo-lib-wasm/Cargo.toml
@@ -21,7 +21,7 @@ serde_json = "1.0"
 js-sys = "0.3"
 
 # used in elliptic-curve(in ergo-lib), compiled here with WASM support
-getrandom = {version = "0.1", features = ["wasm-bindgen"]}
+getrandom = {version = "0.2.3", features = ["js"]}
 # The `console_error_panic_hook` crate provides better debugging of panics by
 # logging them with `console.error`. This is great for development, but requires
 # all the `std::fmt` and `std::panicking` infrastructure, so isn't great for
diff --git a/ergo-lib/Cargo.toml b/ergo-lib/Cargo.toml
index 56345f7bd..ce643ea1f 100644
--- a/ergo-lib/Cargo.toml
+++ b/ergo-lib/Cargo.toml
@@ -36,7 +36,7 @@ compiler = ["ergoscript-compiler"]
 [dev-dependencies]
 wasm-bindgen-test = "0.3.10"
 proptest-derive = "0.3.0"
-rand = "0.7.3"
+rand = "0.8.4"
 ergotree-ir = { version = "^0.13.0", path = "../ergotree-ir", features = ["arbitrary"] }
 ergotree-interpreter = { version = "^0.13.0", path = "../ergotree-interpreter", features = ["arbitrary"] }
 sigma-test-util = { version = "0.2.0", path = "../sigma-test-util" }
diff --git a/ergotree-interpreter/Cargo.toml b/ergotree-interpreter/Cargo.toml
index a687575c7..934c16978 100644
--- a/ergotree-interpreter/Cargo.toml
+++ b/ergotree-interpreter/Cargo.toml
@@ -17,10 +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.7.2", features = ["zeroize", "arithmetic", "ecdsa"] }
-elliptic-curve = {version = "0.9.6", features = [ "zeroize"]}
+k256 = { version = "0.9.6", features = ["zeroize", "arithmetic", "ecdsa"] }
+elliptic-curve = {version = "0.10.6", features = [ "zeroize", "ff"]}
 blake2 = "0.9"
-rand = "0.7"
+rand = "0.8.4"
 lazy_static = "1.4"
 thiserror = "1"
 derive_more = "0.99"
@@ -28,7 +28,9 @@ num-traits = "0.2.14"
 proptest = {version = "1.0.0", optional = true }
 proptest-derive = {version = "0.3.0", optional = true }
 base16 = "0.2.1"
+bytes = "1.1"
 num-bigint = "0.4.0"
+scorex_crypto_avltree = "0.1.0"
 
 [features]
 default = []
diff --git a/ergotree-interpreter/src/eval.rs b/ergotree-interpreter/src/eval.rs
index 1c085a3f7..68bed426a 100644
--- a/ergotree-interpreter/src/eval.rs
+++ b/ergotree-interpreter/src/eval.rs
@@ -74,6 +74,7 @@ pub(crate) mod option_get_or_else;
 pub(crate) mod option_is_defined;
 pub(crate) mod or;
 pub(crate) mod property_call;
+pub(crate) mod savltree;
 pub(crate) mod sbox;
 pub(crate) mod scoll;
 pub(crate) mod scontext;
@@ -93,6 +94,9 @@ pub(crate) mod xor_of;
 /// Interpreter errors
 #[derive(Error, PartialEq, Eq, Debug, Clone)]
 pub enum EvalError {
+    /// AVL tree errors
+    #[error("AvlTree: {0}")]
+    AvlTree(String),
     /// Only boolean or SigmaBoolean is a valid result expr type
     #[error("Only boolean or SigmaBoolean is a valid result expr type")]
     InvalidResultType,
@@ -197,6 +201,15 @@ type EvalFn = fn(env: &Env, ctx: &mut EvalContext, Value, Vec<Value>) -> Result<
 fn smethod_eval_fn(method: &SMethod) -> Result<EvalFn, EvalError> {
     use ergotree_ir::types::*;
     Ok(match method.obj_type.type_code() {
+        savltree::TYPE_CODE => match method.method_id() {
+            savltree::INSERT_METHOD_ID => self::savltree::INSERT_EVAL_FN,
+            method_id => {
+                return Err(EvalError::NotFound(format!(
+                    "Eval fn: unknown method id in SAvlTree: {:?}",
+                    method_id
+                )))
+            }
+        },
         scontext::TYPE_CODE => match method.method_id() {
             scontext::DATA_INPUTS_PROPERTY_METHOD_ID => self::scontext::DATA_INPUTS_EVAL_FN,
             scontext::SELF_BOX_INDEX_PROPERTY_METHOD_ID => self::scontext::SELF_BOX_INDEX_EVAL_FN,
diff --git a/ergotree-interpreter/src/eval/savltree.rs b/ergotree-interpreter/src/eval/savltree.rs
new file mode 100644
index 000000000..7a3185e6f
--- /dev/null
+++ b/ergotree-interpreter/src/eval/savltree.rs
@@ -0,0 +1,199 @@
+use bytes::Bytes;
+use ergotree_ir::mir::avl_tree_data::ADDigest;
+use ergotree_ir::mir::avl_tree_data::AvlTreeData;
+use ergotree_ir::mir::constant::TryExtractInto;
+use ergotree_ir::mir::value::Value;
+use ergotree_ir::serialization::SigmaSerializable;
+use scorex_crypto_avltree::authenticated_tree_ops::AuthenticatedTreeOps;
+use scorex_crypto_avltree::batch_avl_verifier::BatchAVLVerifier;
+use scorex_crypto_avltree::batch_node::AVLTree;
+use scorex_crypto_avltree::batch_node::Node;
+use scorex_crypto_avltree::batch_node::NodeHeader;
+use scorex_crypto_avltree::operation::KeyValue;
+use scorex_crypto_avltree::operation::Operation;
+
+use super::EvalError;
+use super::EvalFn;
+
+pub(crate) static INSERT_EVAL_FN: EvalFn =
+    |_env, _ctx, obj, args| {
+        let mut avl_tree_data = obj.try_extract_into::<AvlTreeData>()?;
+
+        if !avl_tree_data.tree_flags.insert_allowed() {
+            return Err(EvalError::AvlTree("Insertions not allowed".into()));
+        }
+
+        let entries = {
+            let v = args.get(0).cloned().ok_or_else(|| {
+                EvalError::AvlTree("eval is missing first arg (entries)".to_string())
+            })?;
+            v.try_extract_into::<Vec<(Vec<u8>, Vec<u8>)>>()?
+        };
+
+        let proof = {
+            let v = args.get(1).cloned().ok_or_else(|| {
+                EvalError::AvlTree("eval is missing second arg (proof)".to_string())
+            })?;
+            Bytes::from(v.try_extract_into::<Vec<u8>>()?)
+        };
+
+        let starting_digest = Bytes::from(avl_tree_data.digest.0.to_vec());
+        let mut bv = BatchAVLVerifier::new(
+            &starting_digest,
+            &proof,
+            AVLTree::new(
+                |digest| Node::LabelOnly(NodeHeader::new(Some(*digest), None)),
+                avl_tree_data.key_length as usize,
+                avl_tree_data
+                    .value_length_opt
+                    .as_ref()
+                    .map(|v| **v as usize),
+            ),
+            None,
+            None,
+        )
+        .map_err(map_eval_err)?;
+        for (key, value) in entries {
+            if bv
+                .perform_one_operation(&Operation::Insert(KeyValue {
+                    key: key.into(),
+                    value: value.into(),
+                }))
+                .is_err()
+            {
+                return Err(EvalError::AvlTree(format!(
+                    "Incorrect insert for {:?}",
+                    avl_tree_data
+                )));
+            }
+        }
+        if let Some(new_digest) = bv.digest() {
+            let digest = ADDigest::sigma_parse_bytes(&new_digest)?;
+            avl_tree_data.digest = digest;
+            Ok(Value::Opt(Box::new(Some(Value::AvlTree(
+                avl_tree_data.into(),
+            )))))
+        } else {
+            Err(EvalError::AvlTree("Cannot update digest".into()))
+        }
+    };
+
+fn map_eval_err<T: std::fmt::Debug>(e: T) -> EvalError {
+    EvalError::AvlTree(format!("{:?}", e))
+}
+
+#[allow(clippy::unwrap_used)]
+#[cfg(test)]
+#[cfg(feature = "arbitrary")]
+mod tests {
+    use std::convert::TryFrom;
+
+    use ergotree_ir::{
+        mir::{
+            avl_tree_data::{AvlTreeData, AvlTreeFlags},
+            constant::{Constant, Literal},
+            expr::Expr,
+            method_call::MethodCall,
+            value::CollKind,
+        },
+        types::{savltree, stuple::STuple, stype::SType},
+    };
+    use scorex_crypto_avltree::batch_avl_prover::BatchAVLProver;
+
+    use crate::eval::tests::eval_out_wo_ctx;
+
+    use super::*;
+    #[test]
+    fn eval_avl_tree() {
+        // This example taken from `scorex_crypto_avltree` README
+        let mut prover = BatchAVLProver::new(
+            AVLTree::new(
+                |digest| Node::LabelOnly(NodeHeader::new(Some(*digest), None)),
+                1,
+                None,
+            ),
+            true,
+        );
+        let initial_digest =
+            ADDigest::sigma_parse_bytes(&prover.digest().unwrap().into_iter().collect::<Vec<_>>())
+                .unwrap();
+        let key1 = Bytes::from(vec![1u8]);
+        let key2 = Bytes::from(vec![2u8; 1]);
+        let key3 = Bytes::from(vec![3u8; 1]);
+        let op1 = Operation::Insert(KeyValue {
+            key: key1,
+            value: Bytes::from(10u64.to_be_bytes().to_vec()),
+        });
+        let op2 = Operation::Insert(KeyValue {
+            key: key2,
+            value: Bytes::from(20u64.to_be_bytes().to_vec()),
+        });
+        let op3 = Operation::Insert(KeyValue {
+            key: key3,
+            value: Bytes::from(30u64.to_be_bytes().to_vec()),
+        });
+        prover.perform_one_operation(&op1).unwrap();
+        prover.perform_one_operation(&op2).unwrap();
+        prover.perform_one_operation(&op3).unwrap();
+        let final_digest =
+            ADDigest::sigma_parse_bytes(&prover.digest().unwrap().into_iter().collect::<Vec<_>>())
+                .unwrap();
+        let proof: Constant = prover
+            .generate_proof()
+            .into_iter()
+            .collect::<Vec<_>>()
+            .into();
+
+        let tree_flags = AvlTreeFlags::new(true, false, false);
+        let obj = Expr::Const(
+            AvlTreeData {
+                digest: initial_digest,
+                tree_flags,
+                key_length: 1,
+                value_length_opt: None,
+            }
+            .into(),
+        );
+        let pair1 = Literal::Tup(mk_pair(1u8, 10u64).into());
+        let pair2 = Literal::Tup(mk_pair(2u8, 20u64).into());
+        let pair3 = Literal::Tup(mk_pair(3u8, 30u64).into());
+        let entries = Constant {
+            tpe: SType::SColl(Box::new(SType::STuple(STuple::pair(
+                SType::SColl(Box::new(SType::SByte)),
+                SType::SColl(Box::new(SType::SByte)),
+            )))),
+            v: Literal::Coll(CollKind::WrappedColl {
+                items: vec![pair1, pair2, pair3],
+                elem_tpe: SType::STuple(STuple::pair(
+                    SType::SColl(Box::new(SType::SByte)),
+                    SType::SColl(Box::new(SType::SByte)),
+                )),
+            }),
+        };
+        let expr: Expr = MethodCall::new(
+            obj,
+            savltree::INSERT_METHOD.clone(),
+            vec![entries.into(), proof.into()],
+        )
+        .unwrap()
+        .into();
+
+        let res = eval_out_wo_ctx::<Value>(&expr);
+        if let Value::Opt(opt) = res {
+            if let Some(Value::AvlTree(avl)) = *opt {
+                assert_eq!(avl.digest, final_digest);
+            } else {
+                unreachable!();
+            }
+        } else {
+            unreachable!();
+        }
+    }
+
+    fn mk_pair(x: u8, y: u64) -> [Literal; 2] {
+        [
+            Literal::try_from(vec![x]).unwrap(),
+            Literal::try_from(y.to_be_bytes().to_vec()).unwrap(),
+        ]
+    }
+}
diff --git a/ergotree-interpreter/src/sigma_protocol/private_input.rs b/ergotree-interpreter/src/sigma_protocol/private_input.rs
index b99d156b6..8df62987b 100644
--- a/ergotree-interpreter/src/sigma_protocol/private_input.rs
+++ b/ergotree-interpreter/src/sigma_protocol/private_input.rs
@@ -5,8 +5,8 @@ use ergotree_ir::sigma_protocol::dlog_group;
 use ergotree_ir::sigma_protocol::sigma_boolean::ProveDhTuple;
 use ergotree_ir::sigma_protocol::sigma_boolean::ProveDlog;
 
+use elliptic_curve::group::ff::PrimeField;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaBoolean;
-use k256::elliptic_curve::ff::PrimeField;
 use k256::Scalar;
 
 extern crate derive_more;
diff --git a/ergotree-ir/Cargo.toml b/ergotree-ir/Cargo.toml
index 94124c301..f665753e7 100644
--- a/ergotree-ir/Cargo.toml
+++ b/ergotree-ir/Cargo.toml
@@ -16,10 +16,10 @@ 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.7.2", features = ["zeroize", "arithmetic", "ecdsa"] }
-elliptic-curve = {version = "0.9.12", features = ["zeroize"]}
+k256 = { version = "0.9.6", features = ["zeroize", "arithmetic", "ecdsa"] }
+elliptic-curve = {version = "0.10.6", features = ["zeroize", "ff"]}
 thiserror = "1"
-rand = "0.7"
+rand = "0.8.4"
 lazy_static = "1.4"
 derive_more = "0.99"
 impl-trait-for-tuples = "0.2.0"
diff --git a/ergotree-ir/src/mir.rs b/ergotree-ir/src/mir.rs
index 3eaaffb88..f5c3794a6 100644
--- a/ergotree-ir/src/mir.rs
+++ b/ergotree-ir/src/mir.rs
@@ -3,6 +3,8 @@
 pub mod and;
 pub mod apply;
 pub mod atleast;
+/// Avl tree data
+pub mod avl_tree_data;
 pub mod bin_op;
 /// Bit inversion operation on numeric type.
 pub mod bit_inversion;
diff --git a/ergotree-ir/src/mir/avl_tree_data.rs b/ergotree-ir/src/mir/avl_tree_data.rs
new file mode 100644
index 000000000..275290902
--- /dev/null
+++ b/ergotree-ir/src/mir/avl_tree_data.rs
@@ -0,0 +1,190 @@
+use crate::serialization::{
+    sigma_byte_reader::SigmaByteRead, sigma_byte_writer::SigmaByteWrite, SigmaParsingError,
+    SigmaSerializable, SigmaSerializeResult,
+};
+
+#[derive(PartialEq, Eq, Debug, Clone)]
+/// AVL tree flags
+pub struct AvlTreeFlags(u8);
+
+impl AvlTreeFlags {
+    /// Create tree-flags
+    pub fn new(insert_allowed: bool, update_allowed: bool, remove_allowed: bool) -> Self {
+        let read_only = 0;
+        let i = if insert_allowed {
+            read_only | 0x01
+        } else {
+            read_only
+        };
+        let u = if update_allowed { i | 0x02 } else { i };
+        AvlTreeFlags(if remove_allowed { u | 0x04 } else { u })
+    }
+
+    /// Parse tree-flags from byte
+    fn parse(serialized_flags: u8) -> Self {
+        let insert_allowed = serialized_flags & 0x01 != 0;
+        let update_allowed = serialized_flags & 0x02 != 0;
+        let remove_allowed = serialized_flags & 0x04 != 0;
+        Self::new(insert_allowed, update_allowed, remove_allowed)
+    }
+
+    /// Returns true if inserting is allowed
+    pub fn insert_allowed(&self) -> bool {
+        self.0 & 0x01 != 0
+    }
+
+    /// Returns true if updating is allowed
+    pub fn update_allowed(&self) -> bool {
+        self.0 & 0x02 != 0
+    }
+
+    /// Returns true if removal is allowed
+    pub fn remove_allowed(&self) -> bool {
+        self.0 & 0x04 != 0
+    }
+}
+
+/// Type of data which efficiently authenticates potentially huge dataset having key-value
+/// dictionary interface. Only root hash of dynamic AVL+ tree, tree height, key length, optional
+/// value length, and access flags are stored in an instance of the datatype.
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct AvlTreeData {
+    /// Authenticated tree digest: root hash along with tree height
+    pub digest: ADDigest,
+    /// Allowed modifications
+    pub tree_flags: AvlTreeFlags,
+    /// All the elements under the tree have the same length
+    pub key_length: u32,
+    /// If non-empty, all the values under the tree are of the same length
+    pub value_length_opt: Option<Box<u32>>,
+}
+
+impl SigmaSerializable for AvlTreeData {
+    fn sigma_serialize<W: SigmaByteWrite>(&self, w: &mut W) -> SigmaSerializeResult {
+        self.digest.sigma_serialize(w)?;
+        w.put_u8(self.tree_flags.0)?;
+        w.put_u32(self.key_length)?;
+        self.value_length_opt.sigma_serialize(w)?;
+        Ok(())
+    }
+    fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SigmaParsingError> {
+        let digest = ADDigest::sigma_parse(r)?;
+        let tree_flags = AvlTreeFlags::parse(r.get_u8()?);
+        let key_length = r.get_u32()?;
+        let value_length_opt = <Option<Box<u32>> as SigmaSerializable>::sigma_parse(r)?;
+        Ok(AvlTreeData {
+            digest,
+            tree_flags,
+            key_length,
+            value_length_opt,
+        })
+    }
+}
+
+// The following types were copied from `ergo-lib::chain::digest32` as a workaround until some
+// types are reorganized in the future.
+
+/// Digest
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct Digest<const N: usize>(pub Box<[u8; N]>);
+
+/// 32 byte array used as ID of some value: block, transaction, etc.
+/// Usually this is as blake2b hash of serialized form
+pub type Digest32 = Digest<32>;
+
+/// AVL tree digest: root hash along with tree height (33 bytes)
+pub type ADDigest = Digest<33>;
+
+impl<const N: usize> Digest<N> {
+    /// Digest size 32 bytes
+    pub const SIZE: usize = N;
+}
+
+impl<const N: usize> SigmaSerializable for Digest<N> {
+    fn sigma_serialize<W: SigmaByteWrite>(&self, w: &mut W) -> SigmaSerializeResult {
+        w.write_all(self.0.as_ref())?;
+        Ok(())
+    }
+    fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SigmaParsingError> {
+        let mut bytes = [0; N];
+        r.read_exact(&mut bytes)?;
+        Ok(Self(bytes.into()))
+    }
+}
+
+#[cfg(feature = "arbitrary")]
+#[allow(clippy::unwrap_used)]
+mod arbitrary {
+
+    use super::*;
+    use proptest::{collection::vec, prelude::*};
+    use std::convert::TryInto;
+
+    type OptBox = Option<Box<u32>>;
+    impl Arbitrary for AvlTreeData {
+        type Strategy = BoxedStrategy<Self>;
+        type Parameters = ();
+
+        fn arbitrary_with(_: Self::Parameters) -> Self::Strategy {
+            (
+                any::<ADDigest>(),
+                any::<bool>(),
+                any::<bool>(),
+                any::<bool>(),
+                any::<u32>(),
+                any::<OptBox>(),
+            )
+                .prop_map(
+                    |(
+                        digest,
+                        insert_allowed,
+                        update_allowed,
+                        remove_allowed,
+                        key_length,
+                        value_length_opt,
+                    )| AvlTreeData {
+                        digest,
+                        tree_flags: AvlTreeFlags::new(
+                            insert_allowed,
+                            update_allowed,
+                            remove_allowed,
+                        ),
+                        key_length,
+                        value_length_opt,
+                    },
+                )
+                .boxed()
+        }
+    }
+
+    impl<const N: usize> Arbitrary for Digest<N> {
+        type Parameters = ();
+        type Strategy = BoxedStrategy<Self>;
+
+        fn arbitrary_with(_: Self::Parameters) -> Self::Strategy {
+            vec(any::<u8>(), Self::SIZE)
+                .prop_map(|v| Digest(Box::new(v.try_into().unwrap())))
+                .boxed()
+        }
+    }
+}
+
+#[cfg(test)]
+#[allow(clippy::unwrap_used)]
+#[allow(clippy::panic)]
+mod tests {
+    use super::*;
+    use crate::mir::expr::Expr;
+    use crate::serialization::sigma_serialize_roundtrip;
+    use proptest::prelude::*;
+
+    proptest! {
+
+        #[test]
+        fn ser_roundtrip(v in any::<AvlTreeData>()) {
+            let expr = Expr::Const(v.into());
+            prop_assert_eq![sigma_serialize_roundtrip(&expr), expr];
+        }
+
+    }
+}
diff --git a/ergotree-ir/src/mir/constant.rs b/ergotree-ir/src/mir/constant.rs
index 4e1d4bd9d..0e4dc4193 100644
--- a/ergotree-ir/src/mir/constant.rs
+++ b/ergotree-ir/src/mir/constant.rs
@@ -19,6 +19,7 @@ mod constant_placeholder;
 
 pub use constant_placeholder::*;
 
+use super::avl_tree_data::AvlTreeData;
 use super::value::NativeColl;
 use super::value::StoreWrapped;
 use super::value::Value;
@@ -55,6 +56,8 @@ pub enum Literal {
     GroupElement(Box<EcPoint>),
     /// Ergo box ID
     CBox(IrBoxId),
+    /// AVL tree
+    AvlTree(Box<AvlTreeData>),
     /// Collection
     Coll(CollKind<Literal>),
     /// Option type
@@ -209,7 +212,7 @@ impl TryFrom<Value> for Constant {
                     Err("Can't convert Value:Tup element".into())
                 }
             }
-            Value::AvlTree => Err("Cannot convert Value::AvlTree into Constant".into()),
+            Value::AvlTree(a) => Ok(Constant::from(*a)),
             Value::Context => Err("Cannot convert Value::Context into Constant".into()),
             Value::Global => Err("Cannot convert Value::Global into Constant".into()),
             Value::Lambda(_) => Err("Cannot convert Value::Lambda(_) into Constant".into()),
@@ -359,6 +362,15 @@ impl From<BigInt256> for Constant {
     }
 }
 
+impl From<AvlTreeData> for Constant {
+    fn from(a: AvlTreeData) -> Self {
+        Constant {
+            tpe: SType::SAvlTree,
+            v: Literal::AvlTree(Box::new(a)),
+        }
+    }
+}
+
 #[allow(clippy::unwrap_used)]
 #[allow(clippy::from_over_into)]
 #[impl_for_tuples(2, 4)]
@@ -557,6 +569,19 @@ impl TryExtractFrom<Literal> for BigInt256 {
     }
 }
 
+impl TryExtractFrom<Literal> for AvlTreeData {
+    fn try_extract_from(v: Literal) -> Result<Self, TryExtractFromError> {
+        match v {
+            Literal::AvlTree(a) => Ok(*a),
+            _ => Err(TryExtractFromError(format!(
+                "expected {:?}, found {:?}",
+                std::any::type_name::<Self>(),
+                v
+            ))),
+        }
+    }
+}
+
 impl<T: TryExtractFrom<Literal>> TryExtractFrom<Literal> for Option<T> {
     fn try_extract_from(v: Literal) -> Result<Self, TryExtractFromError> {
         match v {
diff --git a/ergotree-ir/src/mir/value.rs b/ergotree-ir/src/mir/value.rs
index 209f1e884..26e873e95 100644
--- a/ergotree-ir/src/mir/value.rs
+++ b/ergotree-ir/src/mir/value.rs
@@ -13,6 +13,7 @@ use crate::types::stype::LiftIntoSType;
 use crate::types::stype::SType;
 use crate::util::AsVecI8;
 
+use super::avl_tree_data::AvlTreeData;
 use super::constant::Literal;
 use super::constant::TryExtractFrom;
 use super::constant::TryExtractFromError;
@@ -150,7 +151,7 @@ pub enum Value {
     /// Box
     CBox(IrBoxId),
     /// AVL tree
-    AvlTree,
+    AvlTree(Box<AvlTreeData>),
     /// Collection of values of the same type
     Coll(CollKind<Value>),
     /// Tuple (arbitrary type values)
@@ -224,6 +225,7 @@ impl From<Literal> for Value {
                 };
                 Value::Coll(converted_coll)
             }
+            Literal::AvlTree(a) => Value::AvlTree(a),
             Literal::Opt(lit) => Value::Opt(Box::new(lit.into_iter().next().map(Value::from))),
             Literal::Tup(t) => Value::Tup(t.mapped(Value::from)),
         }
@@ -420,6 +422,19 @@ impl TryExtractFrom<Value> for BigInt256 {
     }
 }
 
+impl TryExtractFrom<Value> for AvlTreeData {
+    fn try_extract_from(v: Value) -> Result<Self, TryExtractFromError> {
+        match v {
+            Value::AvlTree(a) => Ok(*a),
+            _ => Err(TryExtractFromError(format!(
+                "expected {:?}, found {:?}",
+                std::any::type_name::<Self>(),
+                v
+            ))),
+        }
+    }
+}
+
 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()
diff --git a/ergotree-ir/src/serialization/data.rs b/ergotree-ir/src/serialization/data.rs
index f8a151585..b50ec339a 100644
--- a/ergotree-ir/src/serialization/data.rs
+++ b/ergotree-ir/src/serialization/data.rs
@@ -1,3 +1,4 @@
+use crate::mir::avl_tree_data::AvlTreeData;
 use crate::mir::constant::Literal;
 use crate::mir::constant::TryExtractFromError;
 use crate::mir::constant::TryExtractInto;
@@ -38,6 +39,7 @@ impl DataSerializer {
             Literal::GroupElement(ecp) => ecp.sigma_serialize(w)?,
             Literal::SigmaProp(s) => s.value().sigma_serialize(w)?,
             Literal::CBox(_) => return Err(SigmaSerializationError::NotImplementedYet("Box")),
+            Literal::AvlTree(a) => a.sigma_serialize(w)?,
             Literal::Coll(ct) => match ct {
                 CollKind::NativeColl(NativeColl::CollByte(b)) => {
                     w.put_usize_as_u16_unwrapped(b.len())?;
@@ -148,11 +150,7 @@ impl DataSerializer {
                     "SBox data".to_string(),
                 ))
             }
-            SAvlTree => {
-                return Err(SigmaParsingError::NotImplementedYet(
-                    "SAvlTree data".to_string(),
-                ))
-            }
+            SAvlTree => Literal::AvlTree(Box::new(AvlTreeData::sigma_parse(r)?)),
             STypeVar(_) => return Err(SigmaParsingError::NotSupported("TypeVar data")),
             SAny => return Err(SigmaParsingError::NotSupported("SAny data")),
             SOption(_) => return Err(SigmaParsingError::NotSupported("SOption data")),
diff --git a/ergotree-ir/src/serialization/serializable.rs b/ergotree-ir/src/serialization/serializable.rs
index a0c28df72..c3a2b7a63 100644
--- a/ergotree-ir/src/serialization/serializable.rs
+++ b/ergotree-ir/src/serialization/serializable.rs
@@ -177,6 +177,18 @@ impl<T: SigmaSerializable, const L: usize, const U: usize> SigmaSerializable
     }
 }
 
+/// Corresponds to `VLQ(UInt)` format from `ErgoTree` spec.
+impl SigmaSerializable for u32 {
+    fn sigma_serialize<W: SigmaByteWrite>(&self, w: &mut W) -> SigmaSerializeResult {
+        w.put_u32(*self)?;
+        Ok(())
+    }
+    fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SigmaParsingError> {
+        let v = r.get_u32()?;
+        Ok(v)
+    }
+}
+
 impl<T: SigmaSerializable> SigmaSerializable for Option<Box<T>> {
     fn sigma_serialize<W: SigmaByteWrite>(&self, w: &mut W) -> SigmaSerializeResult {
         match self {
diff --git a/ergotree-ir/src/sigma_protocol/dlog_group.rs b/ergotree-ir/src/sigma_protocol/dlog_group.rs
index ea91c673e..5f5c97d79 100644
--- a/ergotree-ir/src/sigma_protocol/dlog_group.rs
+++ b/ergotree-ir/src/sigma_protocol/dlog_group.rs
@@ -21,7 +21,7 @@ use crate::serialization::SigmaSerializeResult;
 use crate::serialization::{
     sigma_byte_reader::SigmaByteRead, SigmaParsingError, SigmaSerializable,
 };
-use k256::elliptic_curve::ff::PrimeField;
+use elliptic_curve::group::{ff::PrimeField, prime::PrimeCurveAffine};
 use k256::elliptic_curve::sec1::ToEncodedPoint;
 use k256::{ProjectivePoint, PublicKey, Scalar};
 use num_bigint::BigUint;
diff --git a/ergotree-ir/src/types.rs b/ergotree-ir/src/types.rs
index 83b04d4ff..004195c04 100644
--- a/ergotree-ir/src/types.rs
+++ b/ergotree-ir/src/types.rs
@@ -2,6 +2,8 @@
 
 pub mod stype;
 
+/// AVL tree methods
+pub mod savltree;
 /// Box object type companion
 pub mod sbox;
 /// Collection object type companion
diff --git a/ergotree-ir/src/types/savltree.rs b/ergotree-ir/src/types/savltree.rs
new file mode 100644
index 000000000..54f64cccb
--- /dev/null
+++ b/ergotree-ir/src/types/savltree.rs
@@ -0,0 +1,53 @@
+use crate::serialization::types::TypeCode;
+
+use super::sfunc::SFunc;
+use super::smethod::MethodId;
+use super::smethod::SMethod;
+use super::smethod::SMethodDesc;
+use super::stuple::STuple;
+use super::stype::SType;
+use super::stype_companion::STypeCompanion;
+use lazy_static::lazy_static;
+
+/// SAvlTree type code
+pub const TYPE_CODE: TypeCode = TypeCode::SAVL_TREE;
+/// SAvlTree type name
+pub static TYPE_NAME: &str = "AvlTree";
+/// AvlTree.insert property
+pub const INSERT_METHOD_ID: MethodId = MethodId(12);
+
+lazy_static! {
+    /// AvlTree method descriptors
+    pub(crate) static ref METHOD_DESC: Vec<&'static SMethodDesc> =
+        vec![
+            &INSERT_METHOD_DESC,
+        ]
+    ;
+}
+
+lazy_static! {
+    static ref INSERT_METHOD_DESC: SMethodDesc = SMethodDesc {
+        method_id: INSERT_METHOD_ID,
+        name: "insert",
+        tpe: SFunc {
+            t_dom: vec![ SType::SAvlTree,
+                         SType::SColl(
+                           Box::new(
+                               SType::STuple(
+                                   STuple::pair(
+                                       SType::SColl(Box::new(SType::SByte)),
+                                       SType::SColl(Box::new(SType::SByte))
+                                   )
+                               )
+                           )
+                         ),
+                         SType::SColl(Box::new(SType::SByte)),
+                       ],
+            t_range: SType::SOption(Box::new(SType::SAvlTree)).into(),
+            tpe_params: vec![],
+        },
+    };
+    /// AvlTree.insert
+    pub static ref INSERT_METHOD: SMethod =
+        SMethod::new(STypeCompanion::AvlTree, INSERT_METHOD_DESC.clone(),);
+}
diff --git a/ergotree-ir/src/types/stype_companion.rs b/ergotree-ir/src/types/stype_companion.rs
index bedecb3ac..f07411b0a 100644
--- a/ergotree-ir/src/types/stype_companion.rs
+++ b/ergotree-ir/src/types/stype_companion.rs
@@ -4,6 +4,7 @@ use std::fmt::Debug;
 use crate::serialization::types::TypeCode;
 use crate::serialization::SigmaParsingError;
 
+use super::savltree;
 use super::sbox;
 use super::scoll;
 use super::scontext;
@@ -37,6 +38,8 @@ pub enum STypeCompanion {
     PreHeader,
     /// Option
     Option,
+    /// AVL tree
+    AvlTree,
 }
 
 impl STypeCompanion {
@@ -50,6 +53,7 @@ impl STypeCompanion {
             STypeCompanion::Header => &*sheader::METHOD_DESC,
             STypeCompanion::PreHeader => &*spreheader::METHOD_DESC,
             STypeCompanion::Option => &*soption::METHOD_DESC,
+            STypeCompanion::AvlTree => &*savltree::METHOD_DESC,
         }
     }
 
@@ -80,6 +84,7 @@ impl STypeCompanion {
             STypeCompanion::Header => sheader::TYPE_CODE,
             STypeCompanion::PreHeader => spreheader::TYPE_CODE,
             STypeCompanion::Option => soption::TYPE_CODE,
+            STypeCompanion::AvlTree => savltree::TYPE_CODE,
         }
     }
 
@@ -94,6 +99,7 @@ impl STypeCompanion {
             STypeCompanion::Header => sheader::TYPE_NAME,
             STypeCompanion::PreHeader => spreheader::TYPE_NAME,
             STypeCompanion::Option => soption::TYPE_NAME,
+            STypeCompanion::AvlTree => savltree::TYPE_NAME,
         }
     }
 }
diff --git a/sigma-ser/Cargo.toml b/sigma-ser/Cargo.toml
index 97c9cfe80..85c5f2c6d 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.20.2"
+bitvec = "0.22.3"
 
 # The `console_error_panic_hook` crate provides better debugging of panics by
 # logging them with `console.error`. This is great for development, but requires


Test patch: