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

Issue:
[1000 SigmaUSD] PoPowHeader Interlink Batch Merkle Proof verification
Please be aware that most of the Scala reference implementation referenced below is still WIP in https://github.com/ergoplatform/ergo/pull/1526 with the issue [here](https://github.com/ergoplatform/ergo/issues/1384)

Add `BatchMerkleProof` type in `ergo_merkle_tree` crate and implement its validation against an expected root hash, see Scala [reference implementation](https://github.com/input-output-hk/scrypto/blob/88fc0ee4e1eecf3d63e5986487b243b3548bb707/src/main/scala/scorex/crypto/authds/merkle/BatchMerkleProof.scala#L11-L121) with tests equivalent to [tests in Scala implementation](https://github.com/input-output-hk/scrypto/blob/88fc0ee4e1eecf3d63e5986487b243b3548bb707/src/test/scala/scorex/crypto/authds/merkle/MerkleTreeSpecification.scala#L52-L89)
f
Add `interlinks_proof: BatchMerkleProof` property to `PoPowHeader` struct (implemented in https://github.com/ergoplatform/sigma-rust/issues/489). Implement binary serialization of the `BatchMerkleProof` type equivalent to the Scala [reference implementation](https://github.com/input-output-hk/scrypto/blob/88fc0ee4e1eecf3d63e5986487b243b3548bb707/src/main/scala/scorex/crypto/authds/merkle/serialization/BatchMerkleProofSerializer.scala#L10-L81) and JSON serialization equivalent to Scala [implementation](https://github.com/ergoplatform/ergo/blob/9114d7149338326e4c018aee91405c200381f6e9/src/main/scala/org/ergoplatform/modifiers/history/popow/PoPowHeader.scala#L75-L111)
Implement binary serialization tests equivalent to Scala [implementation](https://github.com/input-output-hk/scrypto/blob/88fc0ee4e1eecf3d63e5986487b243b3548bb707/src/test/scala/scorex/crypto/authds/merkle/serialization/BatchMerkleProofSerializerSpecification.scala#L12-L112) and a roundtrip test for JSON serialization/deserialization.

Add `NipopowProof::has_valid_proofs() -> bool` verification, see Scala [reference implementation](https://github.com/ergoplatform/ergo/blob/9114d7149338326e4c018aee91405c200381f6e9/src/main/scala/org/ergoplatform/modifiers/history/popow/NipopowProof.scala#L90-L96) which checks headers in prefix and suffix head to have valid interlinks proofs.
Implement tests equivalent to the ones [implemented](https://github.com/ergoplatform/ergo/blob/9114d7149338326e4c018aee91405c200381f6e9/src/test/scala/org/ergoplatform/modifiers/history/PoPowHeaderSpec.scala#L7-L22) in Scala 
The `NipopowProof` type is implemented in https://github.com/ergoplatform/sigma-rust/pull/517


Discussion / hints:
I'd like to take this one 

Fix patch:
diff --git a/bindings/ergo-lib-c-core/src/batchmerkleproof.rs b/bindings/ergo-lib-c-core/src/batchmerkleproof.rs
new file mode 100644
index 000000000..e91d343bd
--- /dev/null
+++ b/bindings/ergo-lib-c-core/src/batchmerkleproof.rs
@@ -0,0 +1,31 @@
+use crate::{
+    util::{const_ptr_as_ref, mut_ptr_as_mut},
+    Error,
+};
+
+pub struct BatchMerkleProof(pub ergo_lib::ergo_merkle_tree::BatchMerkleProof);
+
+pub type BatchMerkleProofPtr = *mut BatchMerkleProof;
+pub type ConstBatchMerkleProofPtr = *const BatchMerkleProof;
+
+pub unsafe fn batchmerkleproof_valid(
+    proof: ConstBatchMerkleProofPtr,
+    expected_root: &[u8],
+) -> Result<bool, Error> {
+    let proof = const_ptr_as_ref(proof, "proof")?;
+    Ok(proof.0.valid(expected_root))
+}
+
+pub unsafe fn batchmerkleproof_from_json(
+    json: &str,
+    proof_out: *mut BatchMerkleProofPtr,
+) -> Result<(), Error> {
+    let proof_out = mut_ptr_as_mut(proof_out, "proof_out")?;
+    *proof_out = Box::into_raw(Box::new(serde_json::from_str(json).map(BatchMerkleProof)?));
+    Ok(())
+}
+
+pub unsafe fn batchmerkleproof_to_json(proof: ConstBatchMerkleProofPtr) -> Result<String, Error> {
+    let proof = const_ptr_as_ref(proof, "proof")?;
+    serde_json::to_string(&proof.0).map_err(Error::from)
+}
diff --git a/bindings/ergo-lib-c-core/src/lib.rs b/bindings/ergo-lib-c-core/src/lib.rs
index 4398a8fb0..87d6ad7c3 100644
--- a/bindings/ergo-lib-c-core/src/lib.rs
+++ b/bindings/ergo-lib-c-core/src/lib.rs
@@ -11,6 +11,7 @@
 #![allow(clippy::missing_safety_doc)]
 
 pub mod address;
+pub mod batchmerkleproof;
 pub mod block_header;
 pub mod box_builder;
 pub mod box_selector;
diff --git a/bindings/ergo-lib-c-core/src/merkleproof.rs b/bindings/ergo-lib-c-core/src/merkleproof.rs
index aa2cfbd80..c3243b460 100644
--- a/bindings/ergo-lib-c-core/src/merkleproof.rs
+++ b/bindings/ergo-lib-c-core/src/merkleproof.rs
@@ -22,7 +22,7 @@ pub unsafe fn merkleproof_new(
     *proof_out = Box::into_raw(Box::new(MerkleProof(ergo_merkle_tree::MerkleProof::new(
         leaf_data,
         &[],
-    )?)));
+    ))));
     Ok(())
 }
 
diff --git a/bindings/ergo-lib-c-core/src/nipopow.rs b/bindings/ergo-lib-c-core/src/nipopow.rs
index ce5f00ab3..12d42cb92 100644
--- a/bindings/ergo-lib-c-core/src/nipopow.rs
+++ b/bindings/ergo-lib-c-core/src/nipopow.rs
@@ -1,6 +1,7 @@
 //! Bindings for NiPoPow
 
 use crate::{
+    batchmerkleproof::{BatchMerkleProof, BatchMerkleProofPtr},
     block_header::{BlockHeader, BlockHeaderPtr, BlockId, ConstBlockIdPtr},
     collections::{Collection, CollectionPtr},
     util::{const_ptr_as_ref, mut_ptr_as_mut},
@@ -142,3 +143,22 @@ pub unsafe fn popow_header_get_header(
     *header_out = Box::into_raw(Box::new(BlockHeader(popow_header_ptr.0.header.clone())));
     Ok(())
 }
+
+pub unsafe fn popow_header_get_interlinks_proof(
+    popow_header_ptr: ConstPoPowHeaderPtr,
+    proof_out: *mut BatchMerkleProofPtr,
+) -> Result<(), Error> {
+    let popow_header_ptr = const_ptr_as_ref(popow_header_ptr, "popow_header_ptr")?;
+    let proof_out = mut_ptr_as_mut(proof_out, "proof_out")?;
+    *proof_out = Box::into_raw(Box::new(BatchMerkleProof(
+        popow_header_ptr.0.interlinks_proof.clone(),
+    )));
+    Ok(())
+}
+
+pub unsafe fn popow_header_check_interlinks_proof(
+    popow_header_ptr: ConstPoPowHeaderPtr,
+) -> Result<bool, Error> {
+    let popow_header_ptr = const_ptr_as_ref(popow_header_ptr, "popow_header_ptr")?;
+    Ok(popow_header_ptr.0.check_interlinks_proof())
+}
diff --git a/bindings/ergo-lib-c/src/batchmerkleproof.rs b/bindings/ergo-lib-c/src/batchmerkleproof.rs
new file mode 100644
index 000000000..8b91a0143
--- /dev/null
+++ b/bindings/ergo-lib-c/src/batchmerkleproof.rs
@@ -0,0 +1,50 @@
+use crate::{delete_ptr, ErrorPtr};
+use ergo_lib_c_core::{batchmerkleproof::*, Error};
+use std::{
+    ffi::{CStr, CString},
+    os::raw::c_char,
+};
+
+#[no_mangle]
+pub unsafe extern "C" fn ergo_lib_batch_merkle_proof_valid(
+    proof: ConstBatchMerkleProofPtr,
+    root_hash: *const u8,
+    len: usize,
+) -> bool {
+    let root_hash = std::slice::from_raw_parts(root_hash, len);
+    // Unwrap should be safe to use here unless the caller passes a null ptr (undefined)
+    #[allow(clippy::unwrap_used)]
+    batchmerkleproof_valid(proof, root_hash).unwrap()
+}
+
+#[no_mangle]
+pub unsafe extern "C" fn ergo_lib_batch_merkle_proof_from_json(
+    json_str: *const c_char,
+    proof_out: *mut BatchMerkleProofPtr,
+) -> ErrorPtr {
+    let json_str = CStr::from_ptr(json_str).to_string_lossy();
+    Error::c_api_from(batchmerkleproof_from_json(&json_str, proof_out))
+}
+
+/// Serializes a BatchMerkleProof to json representation
+#[no_mangle]
+pub unsafe extern "C" fn ergo_lib_batch_merkle_proof_to_json(
+    proof: ConstBatchMerkleProofPtr,
+    json_str: *mut *const c_char,
+) -> ErrorPtr {
+    #[allow(clippy::unwrap_used)]
+    // Unwrap is safe, CString::new only errors if the argument contains a 0 byte
+    let res = match batchmerkleproof_to_json(proof) {
+        Ok(s) => {
+            *json_str = CString::new(s).unwrap().into_raw();
+            Ok(())
+        }
+        Err(err) => Err(err),
+    };
+    Error::c_api_from(res)
+}
+
+#[no_mangle]
+pub unsafe extern "C" fn ergo_lib_batch_merkle_proof_delete(ptr: BatchMerkleProofPtr) {
+    delete_ptr(ptr)
+}
diff --git a/bindings/ergo-lib-c/src/lib.rs b/bindings/ergo-lib-c/src/lib.rs
index 9b2606da3..c6c096e46 100644
--- a/bindings/ergo-lib-c/src/lib.rs
+++ b/bindings/ergo-lib-c/src/lib.rs
@@ -15,6 +15,7 @@
 #[macro_use]
 mod macros;
 mod address;
+mod batchmerkleproof;
 mod block_header;
 mod box_builder;
 mod box_selector;
@@ -44,6 +45,7 @@ mod tx_builder;
 mod wallet;
 
 pub use crate::address::*;
+pub use crate::batchmerkleproof::*;
 pub use crate::block_header::*;
 pub use crate::box_builder::*;
 pub use crate::box_selector::*;
diff --git a/bindings/ergo-lib-c/src/nipopow.rs b/bindings/ergo-lib-c/src/nipopow.rs
index 307413320..7ae073535 100644
--- a/bindings/ergo-lib-c/src/nipopow.rs
+++ b/bindings/ergo-lib-c/src/nipopow.rs
@@ -2,14 +2,16 @@
 use paste::paste;
 
 use ergo_lib_c_core::{
+    batchmerkleproof::BatchMerkleProofPtr,
     block_header::{BlockHeader, BlockHeaderPtr, ConstBlockIdPtr},
     collections::CollectionPtr,
     nipopow::{
         nipopow_proof_from_json, nipopow_proof_is_better_than, nipopow_proof_to_json,
         nipopow_verifier_best_chain, nipopow_verifier_new, nipopow_verifier_process,
-        popow_header_from_json, popow_header_get_header, popow_header_get_interlinks,
-        popow_header_to_json, ConstNipopowProofPtr, ConstNipopowVerifierPtr, ConstPoPowHeaderPtr,
-        NipopowProofPtr, NipopowVerifierPtr, PoPowHeaderPtr,
+        popow_header_check_interlinks_proof, popow_header_from_json, popow_header_get_header,
+        popow_header_get_interlinks, popow_header_get_interlinks_proof, popow_header_to_json,
+        ConstNipopowProofPtr, ConstNipopowVerifierPtr, ConstPoPowHeaderPtr, NipopowProofPtr,
+        NipopowVerifierPtr, PoPowHeaderPtr,
     },
     Error,
 };
@@ -152,6 +154,21 @@ pub unsafe extern "C" fn ergo_lib_popow_header_get_header(
 ) -> ErrorPtr {
     Error::c_api_from(popow_header_get_header(popow_header, header_out))
 }
+#[no_mangle]
+pub unsafe extern "C" fn ergo_lib_popow_header_get_interlinks_proof(
+    popow_header: ConstPoPowHeaderPtr,
+    header_out: *mut BatchMerkleProofPtr,
+) -> ErrorPtr {
+    Error::c_api_from(popow_header_get_interlinks_proof(popow_header, header_out))
+}
+
+#[no_mangle]
+pub unsafe extern "C" fn ergo_lib_popow_header_check_interlinks_proof(
+    popow_header_ptr: ConstPoPowHeaderPtr,
+) -> bool {
+    #[allow(clippy::unwrap_used)]
+    popow_header_check_interlinks_proof(popow_header_ptr).unwrap()
+}
 
 #[no_mangle]
 pub unsafe extern "C" fn ergo_lib_popow_header_delete(ptr: PoPowHeaderPtr) {
diff --git a/bindings/ergo-lib-ios/Sources/ErgoLib/BatchMerkleProof.swift b/bindings/ergo-lib-ios/Sources/ErgoLib/BatchMerkleProof.swift
new file mode 100644
index 000000000..bd323c4e8
--- /dev/null
+++ b/bindings/ergo-lib-ios/Sources/ErgoLib/BatchMerkleProof.swift
@@ -0,0 +1,25 @@
+import Foundation
+import ErgoLibC
+
+class BatchMerkleProof {
+    internal var pointer: BatchMerkleProofPtr
+    internal init(withRawPointer ptr: BatchMerkleProofPtr) {
+        self.pointer = ptr
+    }
+    init(withJson json: String) throws {
+        var ptr: BatchMerkleProofPtr?
+        let error = json.withCString { cs in
+            ergo_lib_batch_merkle_proof_from_json(cs, &ptr)
+        }
+        try checkError(error)
+        self.pointer = ptr!
+    }
+    func valid(expected_root: [UInt8]) -> Bool {
+        return ergo_lib_batch_merkle_proof_valid(self.pointer, expected_root, UInt(expected_root.count))
+    }
+
+    deinit {
+        ergo_lib_batch_merkle_proof_delete(self.pointer)
+    }
+
+}
diff --git a/bindings/ergo-lib-ios/Sources/ErgoLib/Nipopow.swift b/bindings/ergo-lib-ios/Sources/ErgoLib/Nipopow.swift
index 3c8bb9b0f..5931630c2 100644
--- a/bindings/ergo-lib-ios/Sources/ErgoLib/Nipopow.swift
+++ b/bindings/ergo-lib-ios/Sources/ErgoLib/Nipopow.swift
@@ -110,6 +110,17 @@ class PoPowHeader {
         return BlockIds(withRawPointer: ptr!)
     }
 
+    func getInterlinksProof() throws -> BatchMerkleProof {
+        var ptr: BatchMerkleProofPtr?
+        let error = ergo_lib_popow_header_get_interlinks_proof(self.pointer, &ptr)
+        try checkError(error)
+        return BatchMerkleProof(withRawPointer: ptr!)
+    }
+
+    func checkInterlinksProof() -> Bool {
+        return ergo_lib_popow_header_check_interlinks_proof(self.pointer)
+    }
+
     deinit {
         ergo_lib_popow_header_delete(self.pointer)
     }
diff --git a/bindings/ergo-lib-ios/Tests/ErgoLibTests/NipopowTests.swift b/bindings/ergo-lib-ios/Tests/ErgoLibTests/NipopowTests.swift
index 2382cd004..d32aebd71 100644
--- a/bindings/ergo-lib-ios/Tests/ErgoLibTests/NipopowTests.swift
+++ b/bindings/ergo-lib-ios/Tests/ErgoLibTests/NipopowTests.swift
@@ -8,51 +8,78 @@ final class PoPowHeaderTests: XCTestCase {
         // sample PoPowHeader generated from ergo-chain-generation testing infrastructure
         let json = """
           {
-            "header": {
-            "version": 1,
-            "id": "06fa44cc86a2cf45312fb1587f5eed0d9611a984344446e3f21c6e18422fe334",
-            "parentId": "0000000000000000000000000000000000000000000000000000000000000000",
-            "adProofsRoot": "d6379a936c8f885b347cd3d03f068b41b7d268729843530650348cf0755fea6d",
-            "stateRoot": "000000000000000000000000000000000000000000000000000000000000000000",
-            "transactionsRoot": "024562cb92738cbe9f5345b6d78b0272f4823692d2a16a11d80459c6d61f7860",
-            "timestamp": 0,
-            "nBits": 16842752,
-            "height": 1,
-            "extensionHash": "0e5751c026e543b2e8ab2eb06099daa1d1e5df47778f7787faab45cdf12fe3a8",
-            "powSolutions": {
+          "header": {
+          "version": 1,
+          "id": "fa31f25f95c6ae9752392daa38f45c59e57593a4def26427cbda25747938d0a3",
+          "parentId": "99e19212a3dd1f3951464cbeb42e6bc447b646fe20e362653009be31b8ac756d",
+          "adProofsRoot": "7bd5d1c0df436e1e175df31a0272013ca93f2305a1bddea99d6b607ecf24fcac",
+          "stateRoot": "000000000000000000000000000000000000000000000000000000000000000000",
+          "transactionsRoot": "024562cb92738cbe9f5345b6d78b0272f4823692d2a16a11d80459c6d61f7860",
+          "timestamp": 0,
+          "nBits": 16842752,
+          "height": 8,
+          "extensionHash": "696a076089090b128c4856a17e2e23ed2788d074fe09e9975e2ee799f79e9743",
+          "powSolutions": {
             "pk": "038b0f29a60fa8d7e1aeafbe512288a6c6bc696547bbf8247db23c95e83014513c",
-            "w": "02c80663dc9fcabee47c14a17c774eefda19cbcf2ea59f2dc70c2a544358ecb56b",
+            "w": "03a0f176159c0895ee4cc64149ff3fa8a0ccf8cf15b884fb0bfaabc0bae2355b10",
             "n": "8000000000000000",
-            "d": "106003266939236557704060319805453778767683550618649496709275559630020036173535"
+            "d": "21099867708510879837487107380901512552573946537697225889752133246839759121455"
             },
             "votes": "000000"
             },
-            "interlinks": []
-            }
+            "interlinks": [
+            "e57483be3653936848f646ebd44e8ea7311d3d8fbc07b4c900a1b7edcc0b9a74",
+            "b2525defb4a3ab2f0ffdad6f37ff5a9e330eae2f00ec0c19f1aef234369bd408",
+            "99e19212a3dd1f3951464cbeb42e6bc447b646fe20e362653009be31b8ac756d"
+            ],
+            "interlinks_proof": {
+            "indices": [
+                {
+                "index": 0,
+                "digest": "e489b3601239d37b066aa53b6640758c9774334dde616d43fb8288e1fdb4f083"
+                },
+                {
+                "index": 1,
+                "digest": "76387dd1010dbfc7e318fb7989fe3013099ca0ed4fc6176471815ab116e3542a"
+                },
+                {
+                "index": 2,
+                "digest": "c61ce82b2b3bfe369daaa51e5df8070364d68e0cb9a3dfa6ebf79e3bfb89d9fa"
+                }
+                ],
+                "proofs": [
+                    {
+                    "digest": "",
+                    "side": 1
+                    }
+                ]
+             }
+          }
           """;
         let header = """
           {
-            "version": 1,
-            "id": "06fa44cc86a2cf45312fb1587f5eed0d9611a984344446e3f21c6e18422fe334",
-            "parentId": "0000000000000000000000000000000000000000000000000000000000000000",
-            "adProofsRoot": "d6379a936c8f885b347cd3d03f068b41b7d268729843530650348cf0755fea6d",
-            "stateRoot": "000000000000000000000000000000000000000000000000000000000000000000",
-            "transactionsRoot": "024562cb92738cbe9f5345b6d78b0272f4823692d2a16a11d80459c6d61f7860",
-            "timestamp": 0,
-            "nBits": 16842752,
-            "height": 1,
-            "extensionHash": "0e5751c026e543b2e8ab2eb06099daa1d1e5df47778f7787faab45cdf12fe3a8",
-            "powSolutions": {
+        "version": 1,
+        "id": "fa31f25f95c6ae9752392daa38f45c59e57593a4def26427cbda25747938d0a3",
+        "parentId": "99e19212a3dd1f3951464cbeb42e6bc447b646fe20e362653009be31b8ac756d",
+        "adProofsRoot": "7bd5d1c0df436e1e175df31a0272013ca93f2305a1bddea99d6b607ecf24fcac",
+        "stateRoot": "000000000000000000000000000000000000000000000000000000000000000000",
+        "transactionsRoot": "024562cb92738cbe9f5345b6d78b0272f4823692d2a16a11d80459c6d61f7860",
+        "timestamp": 0,
+        "nBits": 16842752,
+        "height": 8,
+        "extensionHash": "696a076089090b128c4856a17e2e23ed2788d074fe09e9975e2ee799f79e9743",
+        "powSolutions": {
             "pk": "038b0f29a60fa8d7e1aeafbe512288a6c6bc696547bbf8247db23c95e83014513c",
-            "w": "02c80663dc9fcabee47c14a17c774eefda19cbcf2ea59f2dc70c2a544358ecb56b",
+            "w": "03a0f176159c0895ee4cc64149ff3fa8a0ccf8cf15b884fb0bfaabc0bae2355b10",
             "n": "8000000000000000",
-            "d": "106003266939236557704060319805453778767683550618649496709275559630020036173535"
-            },
-            "votes": "000000"
-           }
+            "d": "21099867708510879837487107380901512552573946537697225889752133246839759121455"
+        },
+        "votes": "000000"
+        }
         """
         let popow = try PoPowHeader(withJson: json)
-        XCTAssert((try popow.getInterlinks()).len() == 0)
+        XCTAssert((try popow.getInterlinks()).len() == 3)
         XCTAssert((try popow.getHeader()) == (try BlockHeader(withJson: header)))
+        XCTAssert(popow.checkInterlinksProof())
     }
 }
diff --git a/bindings/ergo-lib-wasm/src/batchmerkleproof.rs b/bindings/ergo-lib-wasm/src/batchmerkleproof.rs
new file mode 100644
index 000000000..3be08dce5
--- /dev/null
+++ b/bindings/ergo-lib-wasm/src/batchmerkleproof.rs
@@ -0,0 +1,26 @@
+//! BatchMerkleProof (compact Merkle multi-proofs)
+use ergo_lib::ergo_merkle_tree;
+use serde::{Deserialize, Serialize};
+use wasm_bindgen::prelude::*;
+
+/// BatchMerkleProof type to validate root hash for multiple nodes
+#[wasm_bindgen]
+#[derive(Serialize, Deserialize)]
+pub struct BatchMerkleProof(pub(crate) ergo_merkle_tree::BatchMerkleProof);
+
+#[wasm_bindgen]
+impl BatchMerkleProof {
+    /// Creates a new [`BatchMerkleProof`] from json representation
+    pub fn from_json(json: &JsValue) -> Result<BatchMerkleProof, String> {
+        json.into_serde().map_err(|err| err.to_string())
+    }
+    /// Converts [`BatchMerkleProof`] to json representation
+    pub fn to_json(&self) -> Result<JsValue, String> {
+        JsValue::from_serde(&self).map_err(|err| err.to_string())
+    }
+
+    /// Calculates root hash for [`BatchMerkleProof`] and compares it against expected root hash
+    pub fn valid(&self, expected_root: &[u8]) -> bool {
+        self.0.valid(expected_root)
+    }
+}
diff --git a/bindings/ergo-lib-wasm/src/lib.rs b/bindings/ergo-lib-wasm/src/lib.rs
index ab7855ace..2b590a931 100644
--- a/bindings/ergo-lib-wasm/src/lib.rs
+++ b/bindings/ergo-lib-wasm/src/lib.rs
@@ -18,6 +18,7 @@
 
 pub mod address;
 pub mod ast;
+pub mod batchmerkleproof;
 pub mod block_header;
 pub mod box_coll;
 pub mod box_selector;
diff --git a/bindings/ergo-lib-wasm/src/merkleproof.rs b/bindings/ergo-lib-wasm/src/merkleproof.rs
index 9e2fbfda1..618b9fe18 100644
--- a/bindings/ergo-lib-wasm/src/merkleproof.rs
+++ b/bindings/ergo-lib-wasm/src/merkleproof.rs
@@ -10,7 +10,7 @@ pub struct MerkleProof(ergo_merkle_tree::MerkleProof);
 
 /// A level node in a merkle proof
 #[wasm_bindgen]
-#[derive(Serialize, Deserialize, Debug, Copy, Clone)]
+#[derive(Serialize, Deserialize, Debug, Clone)]
 pub struct LevelNode(ergo_merkle_tree::LevelNode);
 
 #[wasm_bindgen]
@@ -24,15 +24,18 @@ impl LevelNode {
             side.try_into()?,
         )))
     }
-    /// Returns the associated digest (hash) with this node
+    /// Returns the associated digest (hash) with this node. Returns an empty array if there's no hash
     #[wasm_bindgen(getter)]
     pub fn digest(&self) -> Vec<u8> {
-        (&self.0 .0[0..]).to_owned()
+        match &self.0.hash {
+            Some(hash) => hash.0.to_vec(),
+            None => vec![],
+        }
     }
     /// Returns the associated side with this node (0 = Left, 1 = Right)
     #[wasm_bindgen(getter)]
     pub fn side(&self) -> u8 {
-        self.0 .1 as u8
+        self.0.side as u8
     }
 }
 
@@ -42,15 +45,13 @@ impl MerkleProof {
     /// You can verify it against a Blakeb256 root hash by using [`Self::valid()`]
     /// Add a node by using [`Self::add_node()`]
     /// Each digest on the level must be exactly 32 bytes
-    pub fn new(leaf_data: &[u8]) -> Result<MerkleProof, wasm_bindgen::JsValue> {
-        Ok(Self(
-            ergo_merkle_tree::MerkleProof::new(leaf_data, &[]).map_err(|err| err.to_string())?,
-        )) // There are issues with wasm when trying to pass an array of structs, so it's better to use add_node instead
+    pub fn new(leaf_data: &[u8]) -> MerkleProof {
+        Self(ergo_merkle_tree::MerkleProof::new(leaf_data, &[])) // There are issues with wasm when trying to pass an array of structs, so it's better to use add_node instead
     }
 
     /// Adds a new node to the MerkleProof above the current nodes
     pub fn add_node(&mut self, level: &LevelNode) {
-        self.0.add_node(level.0);
+        self.0.add_node(level.0.clone());
     }
 
     /// Validates the Merkle proof against the root hash
diff --git a/bindings/ergo-lib-wasm/src/nipopow.rs b/bindings/ergo-lib-wasm/src/nipopow.rs
index 4f0b89339..729c74cf7 100644
--- a/bindings/ergo-lib-wasm/src/nipopow.rs
+++ b/bindings/ergo-lib-wasm/src/nipopow.rs
@@ -70,6 +70,14 @@ impl PoPowHeader {
             .map(Into::into)
             .map_err(Into::into)
     }
+    /// Returns interlinks proof [`crate::batchmerkleproof::BatchMerkleProof`]
+    pub fn interlinks_proof(&self) -> crate::batchmerkleproof::BatchMerkleProof {
+        crate::batchmerkleproof::BatchMerkleProof(self.0.interlinks_proof.clone())
+    }
+    /// Validates interlinks merkle root with compact merkle multiproof. See [`PoPowHeader::interlinks_proof`] for BatchMerkleProof access
+    pub fn check_interlinks_proof(&self) -> bool {
+        self.0.check_interlinks_proof()
+    }
 
     /// Returns block height for Header
     pub fn height(&self) -> u32 {
diff --git a/ergo-chain-generation/Cargo.toml b/ergo-chain-generation/Cargo.toml
index 20435b8d1..14ab4951e 100644
--- a/ergo-chain-generation/Cargo.toml
+++ b/ergo-chain-generation/Cargo.toml
@@ -15,6 +15,8 @@ num-bigint = "0.4.0"
 rand = "0.8.4"
 sigma-test-util = { version = "^0.3.0", path = "../sigma-test-util" }
 ergo-nipopow = { version = "^0.2", path = "../ergo-nipopow" }
+ergo-merkle-tree = { version = "^0.2", path = "../ergo-merkle-tree" }
+
 
 [dev-dependencies]
 sigma-ser = { version = "^0.4", path = "../sigma-ser" }
diff --git a/ergo-chain-generation/src/chain_generation.rs b/ergo-chain-generation/src/chain_generation.rs
index 6a83759b4..235be6419 100644
--- a/ergo-chain-generation/src/chain_generation.rs
+++ b/ergo-chain-generation/src/chain_generation.rs
@@ -30,13 +30,12 @@ use ergo_lib::{
         prover::{ContextExtension, ProofBytes},
     },
 };
+use ergo_merkle_tree::{MerkleNode, MerkleTree};
+use ergo_nipopow::NipopowAlgos;
 use num_bigint::{BigInt, Sign};
 use rand::{thread_rng, Rng};
 
-use crate::{
-    default_miner_secret, pack_interlinks, unpack_interlinks, update_interlinks, ErgoFullBlock,
-    ExtensionCandidate, MerkleTreeNode,
-};
+use crate::{default_miner_secret, ErgoFullBlock, ExtensionCandidate};
 
 /// Section of a block which contains transactions.
 #[allow(dead_code)]
@@ -89,7 +88,7 @@ pub fn block_stream(start_block: Option<ErgoFullBlock>) -> impl Iterator<Item =
         next_block(
             None,
             txs.clone(),
-            ExtensionCandidate { fields: vec![] },
+            ExtensionCandidate::default(),
             block_version,
         )
     };
@@ -97,7 +96,7 @@ pub fn block_stream(start_block: Option<ErgoFullBlock>) -> impl Iterator<Item =
         next_block(
             Some(b.clone()),
             txs.clone(),
-            ExtensionCandidate { fields: vec![] },
+            ExtensionCandidate::default(),
             block_version,
         )
     })
@@ -112,15 +111,18 @@ fn next_block(
     let interlinks = prev_block
         .as_ref()
         .and_then(|b| {
-            Some(update_interlinks(
+            NipopowAlgos::update_interlinks(
                 b.header.clone(),
-                unpack_interlinks(&b.extension).ok()?,
-            ))
+                NipopowAlgos::unpack_interlinks(&b.extension).ok()?,
+            )
+            .ok()
         })
         .unwrap_or_default();
     if !interlinks.is_empty() {
         // Only non-empty for non-genesis block
-        extension.fields.extend(pack_interlinks(interlinks));
+        extension
+            .fields_mut()
+            .extend(ergo_nipopow::NipopowAlgos::pack_interlinks(interlinks));
     }
     prove_block(
         prev_block.map(|b| b.header),
@@ -160,21 +162,20 @@ fn prove_block(
         (BlockId(Digest32::zero()), 1)
     };
 
-    let extension_root = MerkleTreeNode::new(
+    let extension_root = MerkleTree::new(
         extension_candidate
-            .clone()
-            .fields
-            .into_iter()
+            .fields()
+            .iter()
             .map(|(key, value)| {
                 let mut data = vec![2_u8];
                 data.extend(key);
                 data.extend(value);
                 data
             })
-            .collect(),
+            .map(MerkleNode::from_bytes)
+            .collect::<Vec<MerkleNode>>(),
     )
-    .hash()
-    .into();
+    .root_hash_special();
 
     let dummy_autolykos_solution = AutolykosSolution {
         miner_pk: Box::new(EcPoint::default()),
@@ -330,7 +331,7 @@ fn numeric_hash(input: &[u8], valid_range: BigInt, order: BigInt) -> BigInt {
 /// Used in the miner when a BlockTransaction instance is not generated yet (because a header is not known)
 fn transactions_root(txs: &[Transaction], block_version: u8) -> Digest32 {
     if block_version == 1 {
-        let tree = MerkleTreeNode::new(
+        let tree = MerkleTree::new(
             txs.iter()
                 .map(|tx| {
                     blake2b256_hash(&tx.bytes_to_sign().unwrap())
@@ -338,11 +339,12 @@ fn transactions_root(txs: &[Transaction], block_version: u8) -> Digest32 {
                         .as_ref()
                         .to_vec()
                 })
-                .collect(),
+                .map(MerkleNode::from_bytes)
+                .collect::<Vec<MerkleNode>>(),
         );
-        tree.hash().into()
+        tree.root_hash_special()
     } else {
-        let tree = MerkleTreeNode::new(
+        let tree = MerkleTree::new(
             txs.iter()
                 .map(|tx| {
                     let mut data = blake2b256_hash(&tx.bytes_to_sign().unwrap())
@@ -364,9 +366,10 @@ fn transactions_root(txs: &[Transaction], block_version: u8) -> Digest32 {
                     data.extend(witness);
                     data
                 })
-                .collect(),
+                .map(MerkleNode::from_bytes)
+                .collect::<Vec<MerkleNode>>(),
         );
-        tree.hash().into()
+        tree.root_hash_special()
     }
 }
 
@@ -379,17 +382,12 @@ mod tests {
     fn generate_popowheader_chain(len: usize, start: Option<PoPowHeader>) -> Vec<PoPowHeader> {
         block_stream(start.map(|p| ErgoFullBlock {
             header: p.header,
-            extension: ExtensionCandidate {
-                fields: pack_interlinks(p.interlinks),
-            },
+            extension:
+                ExtensionCandidate::new(NipopowAlgos::pack_interlinks(p.interlinks)).unwrap(),
         }))
         .take(len)
-        .flat_map(|b| {
-            Some(PoPowHeader {
-                header: b.header,
-                interlinks: unpack_interlinks(&b.extension).ok()?,
-            })
-        })
+        .map(ErgoFullBlock::try_into)
+        .flat_map(Result::ok)
         .collect()
     }
 
@@ -483,6 +481,15 @@ mod tests {
         assert!(proof.is_better_than(&disconnected_proof).unwrap());
     }
 
+    #[test]
+    fn test_popow_extension_hash() {
+        let size = 10;
+        let chain = generate_popowheader_chain(size, None);
+        for block in chain {
+            assert!(block.check_interlinks_proof());
+        }
+    }
+
     #[test]
     fn test_popow_roundtrip() {
         use sigma_ser::ScorexSerializable;
diff --git a/ergo-chain-generation/src/fake_pow_scheme.rs b/ergo-chain-generation/src/fake_pow_scheme.rs
index 2a6ecd397..03beecc99 100644
--- a/ergo-chain-generation/src/fake_pow_scheme.rs
+++ b/ergo-chain-generation/src/fake_pow_scheme.rs
@@ -23,25 +23,18 @@ mod tests {
     use num_bigint::BigInt;
     use rand::{thread_rng, Rng};
 
-    use crate::{
-        default_miner_secret, pack_interlinks, unpack_interlinks, update_interlinks, ErgoFullBlock,
-        ExtensionCandidate, MerkleTreeNode,
-    };
+    use crate::{default_miner_secret, ErgoFullBlock, ExtensionCandidate};
+    use ergo_merkle_tree::{MerkleNode, MerkleTree};
 
     fn generate_popowheader_chain(len: usize, start: Option<PoPowHeader>) -> Vec<PoPowHeader> {
         block_stream(start.map(|p| ErgoFullBlock {
             header: p.header,
-            extension: ExtensionCandidate {
-                fields: pack_interlinks(p.interlinks),
-            },
+            extension:
+                ExtensionCandidate::new(NipopowAlgos::pack_interlinks(p.interlinks)).unwrap(),
         }))
         .take(len)
-        .flat_map(|b| {
-            Some(PoPowHeader {
-                header: b.header,
-                interlinks: unpack_interlinks(&b.extension).ok()?,
-            })
-        })
+        .map(ErgoFullBlock::try_into)
+        .flat_map(Result::ok)
         .collect()
     }
 
@@ -50,12 +43,12 @@ mod tests {
         let start = if start_block.is_some() {
             start_block
         } else {
-            next_block(None, ExtensionCandidate { fields: vec![] }, block_version)
+            next_block(None, ExtensionCandidate::default(), block_version)
         };
         std::iter::successors(start, move |b| {
             next_block(
                 Some(b.clone()),
-                ExtensionCandidate { fields: vec![] },
+                ExtensionCandidate::default(),
                 block_version,
             )
         })
@@ -69,15 +62,18 @@ mod tests {
         let interlinks = prev_block
             .as_ref()
             .and_then(|b| {
-                Some(update_interlinks(
+                NipopowAlgos::update_interlinks(
                     b.header.clone(),
-                    unpack_interlinks(&b.extension).ok()?,
-                ))
+                    NipopowAlgos::unpack_interlinks(&b.extension).ok()?,
+                )
+                .ok()
             })
             .unwrap_or_default();
         if !interlinks.is_empty() {
             // Only non-empty for non-genesis block
-            extension.fields.extend(pack_interlinks(interlinks));
+            extension
+                .fields_mut()
+                .extend(NipopowAlgos::pack_interlinks(interlinks));
         }
         prove_block(prev_block.map(|b| b.header), block_version, 0, extension)
     }
@@ -116,21 +112,20 @@ mod tests {
             (BlockId(Digest32::zero()), 1)
         };
 
-        let extension_root = MerkleTreeNode::new(
+        let extension_root = MerkleTree::new(
             extension_candidate
-                .clone()
-                .fields
-                .into_iter()
+                .fields()
+                .iter()
                 .map(|(key, value)| {
                     let mut data = vec![2_u8];
                     data.extend(key);
                     data.extend(value);
                     data
                 })
-                .collect(),
+                .map(MerkleNode::from_bytes)
+                .collect::<Vec<MerkleNode>>(),
         )
-        .hash()
-        .into();
+        .root_hash_special();
 
         let dummy_autolykos_solution = AutolykosSolution {
             miner_pk: Box::new(EcPoint::default()),
diff --git a/ergo-chain-generation/src/lib.rs b/ergo-chain-generation/src/lib.rs
index 921eb9723..8c7287d7f 100644
--- a/ergo-chain-generation/src/lib.rs
+++ b/ergo-chain-generation/src/lib.rs
@@ -17,18 +17,11 @@
 #![deny(clippy::unimplemented)]
 #![deny(clippy::panic)]
 
-use blake2::{
-    digest::{Update, VariableOutput},
-    VarBlake2b,
-};
+use ergo_lib::ergotree_ir::chain::header::Header;
 use ergo_lib::{
-    ergo_chain_types::Digest32,
+    ergo_chain_types::ExtensionCandidate,
     wallet::{ext_secret_key::ExtSecretKey, mnemonic::Mnemonic},
 };
-use ergo_lib::{
-    ergo_chain_types::{blake2b256_hash, BlockId},
-    ergotree_ir::chain::header::Header,
-};
 use ergo_nipopow::NipopowAlgos;
 use num_bigint::{BigInt, Sign};
 
@@ -47,119 +40,19 @@ pub struct ErgoFullBlock {
 impl std::convert::TryInto<ergo_nipopow::PoPowHeader> for ErgoFullBlock {
     type Error = &'static str;
     fn try_into(self) -> Result<ergo_nipopow::PoPowHeader, &'static str> {
-        let interlinks = unpack_interlinks(&self.extension)?;
+        let interlinks_proof = match NipopowAlgos::proof_for_interlink_vector(&self.extension) {
+            Some(proof) => proof,
+            None => return Err("Unable to generate BatchMerkleProof for interlinks"),
+        };
+        let interlinks = NipopowAlgos::unpack_interlinks(&self.extension)?;
         Ok(ergo_nipopow::PoPowHeader {
             header: self.header,
             interlinks,
+            interlinks_proof,
         })
     }
 }
 
-/// Extension section of Ergo block. Contains key-value storage.
-#[derive(Clone, Debug)]
-pub(crate) struct ExtensionCandidate {
-    /// Fields as a sequence of key -> value records. A key is 2-bytes long, value is 64 bytes max.
-    pub(crate) fields: Vec<([u8; 2], Vec<u8>)>,
-}
-
-static INTERLINK_VECTOR_PREFIX: u8 = 0x01;
-
-/// Unpacks interlinks from key-value format of block extension.
-pub(crate) fn unpack_interlinks(
-    extension: &ExtensionCandidate,
-) -> Result<Vec<BlockId>, &'static str> {
-    let mut res = vec![];
-    let entries = extension
-        .fields
-        .iter()
-        .filter(|&(key, _)| key[0] == INTERLINK_VECTOR_PREFIX);
-    for (_, bytes) in entries {
-        // Each interlink is packed as [qty | blockId], which qty is a single-byte value
-        // representing the number of duplicates of `blockId`. Every `BlockId` is 32 bytes which
-        // implies that `bytes` is 33 bytes.
-        if bytes.len() != 33 {
-            return Err("Interlinks must be 33 bytes in size");
-        }
-        let qty = bytes[0];
-        let block_id_bytes: [u8; 32] = bytes[1..].try_into().unwrap();
-        let block_id = BlockId(Digest32::from(block_id_bytes));
-        res.extend(std::iter::repeat(block_id).take(qty as usize));
-    }
-    Ok(res)
-}
-
-/// Packs interlinks into key-value format of the block extension.
-pub(crate) fn pack_interlinks(interlinks: Vec<BlockId>) -> Vec<([u8; 2], Vec<u8>)> {
-    let mut res = vec![];
-    let mut ix_distinct_block_ids = 0;
-    let mut curr_block_id_count = 1;
-    let mut curr_block_id = interlinks[0].clone();
-    for id in interlinks.into_iter().skip(1) {
-        if id == curr_block_id {
-            curr_block_id_count += 1;
-        } else {
-            let block_id_bytes: Vec<u8> = curr_block_id.clone().0.into();
-            let packed_value = std::iter::once(curr_block_id_count)
-                .chain(block_id_bytes)
-                .collect();
-            res.push((
-                [INTERLINK_VECTOR_PREFIX, ix_distinct_block_ids],
-                packed_value,
-            ));
-            curr_block_id = id;
-            curr_block_id_count = 1;
-            ix_distinct_block_ids += 1;
-        }
-    }
-    let block_id_bytes: Vec<u8> = curr_block_id.0.into();
-    let packed_value = std::iter::once(curr_block_id_count)
-        .chain(block_id_bytes)
-        .collect();
-    res.push((
-        [INTERLINK_VECTOR_PREFIX, ix_distinct_block_ids],
-        packed_value,
-    ));
-    res
-}
-
-/// Computes interlinks vector for a header next to `prevHeader`.
-pub(crate) fn update_interlinks(
-    prev_header: Header,
-    prev_interlinks: Vec<BlockId>,
-) -> Vec<BlockId> {
-    let is_genesis = prev_header.height == 1;
-    if !is_genesis {
-        // Interlinks vector cannot be empty in case of non-genesis header
-        assert!(!prev_interlinks.is_empty());
-        let genesis = prev_interlinks[0].clone();
-        let nipopow_algos = NipopowAlgos::default();
-        let prev_level = nipopow_algos.max_level_of(&prev_header).unwrap() as usize;
-        if prev_level > 0 {
-            // Adapted:
-            //   `(genesis +: tail.dropRight(prevLevel)) ++Seq.fill(prevLevel)(prevHeader.id)`
-            // from scala
-            if prev_interlinks.len() > prev_level {
-                std::iter::once(genesis)
-                    .chain(
-                        prev_interlinks[1..(prev_interlinks.len() - prev_level)]
-                            .iter()
-                            .cloned(),
-                    )
-                    .chain(std::iter::repeat(prev_header.id).take(prev_level))
-                    .collect()
-            } else {
-                std::iter::once(genesis)
-                    .chain(std::iter::repeat(prev_header.id).take(prev_level))
-                    .collect()
-            }
-        } else {
-            prev_interlinks
-        }
-    } else {
-        vec![prev_header.id]
-    }
-}
-
 /// Returns the secret key of the miner secret with its `BigInt` representation. Taken from ergo
 /// test suite.
 pub(crate) fn default_miner_secret() -> (ExtSecretKey, BigInt) {
@@ -173,222 +66,3 @@ pub(crate) fn default_miner_secret() -> (ExtSecretKey, BigInt) {
         BigInt::from_bytes_be(Sign::Plus, &bytes),
     )
 }
-
-/// This is currently use to generate the transaction root for a `Header`. Can remove this once the
-/// Merkle tree is implemented `ergo-merkle-tree` crate.
-#[derive(Clone, PartialEq, Eq, Debug)]
-pub(crate) enum MerkleTreeNode {
-    Internal {
-        left: Box<MerkleTreeNode>,
-        right: Box<MerkleTreeNode>,
-    },
-    Leaf(Vec<u8>),
-    Empty,
-    EmptyTree,
-}
-
-impl MerkleTreeNode {
-    pub(crate) fn new(leaves: Vec<Vec<u8>>) -> Self {
-        if leaves.is_empty() {
-            return MerkleTreeNode::EmptyTree;
-        }
-        let leaves: Vec<_> = leaves.into_iter().map(MerkleTreeNode::Leaf).collect();
-        let mut stack = vec![leaves];
-
-        while let Some(nodes) = stack.pop() {
-            let mut next_level = vec![];
-            for chunks in nodes.chunks(2) {
-                if chunks.len() == 2 {
-                    next_level.push(MerkleTreeNode::Internal {
-                        left: Box::new(chunks[0].clone()),
-                        right: Box::new(chunks[1].clone()),
-                    });
-                } else {
-                    next_level.push(MerkleTreeNode::Internal {
-                        left: Box::new(chunks[0].clone()),
-                        right: Box::new(MerkleTreeNode::Empty),
-                    });
-                }
-            }
-            if next_level.len() == 1 {
-                let root = next_level.pop().unwrap();
-                return root;
-            } else {
-                stack.push(next_level);
-            }
-        }
-        unreachable!()
-    }
-
-    /// Computes the hash of the merkle tree with `self` as root.
-    pub(crate) fn hash(&self) -> [u8; 32] {
-        let mut computed_children_nodes = vec![];
-        enum StackPushType {
-            /// Children of the node not yet pushed onto `stack`
-            First,
-            /// Second time on the stack
-            ChildrenAlreadyPushed,
-        }
-
-        let mut stack = vec![(self.clone(), StackPushType::First)];
-        while let Some((n, push_type)) = stack.pop() {
-            match n {
-                MerkleTreeNode::Internal {
-                    ref left,
-                    ref right,
-                } => {
-                    match push_type {
-                        StackPushType::First => {
-                            stack.push((n.clone(), StackPushType::ChildrenAlreadyPushed));
-                            stack.push((*left.clone(), StackPushType::First));
-                            stack.push((*right.clone(), StackPushType::First));
-                        }
-                        StackPushType::ChildrenAlreadyPushed => {
-                            // Note we pop off left child first
-                            let computed_left_child = computed_children_nodes.pop().unwrap();
-                            if let Some(computed_right_child) = computed_children_nodes.pop() {
-                                let concat =
-                                    concatenate_hashes(&computed_left_child, &computed_right_child);
-                                let hash = prefixed_hash(NodePrefix::Internal as u8, &concat);
-                                if stack.is_empty() {
-                                    return *hash;
-                                } else {
-                                    computed_children_nodes.push(*hash);
-                                }
-                            } else {
-                                let internal_hash =
-                                    prefixed_hash(NodePrefix::Internal as u8, &computed_left_child);
-                                if stack.is_empty() {
-                                    return *internal_hash;
-                                } else {
-                                    computed_children_nodes.push(*internal_hash);
-                                }
-                            }
-                        }
-                    }
-                }
-                MerkleTreeNode::Leaf(data) => match push_type {
-                    StackPushType::First => {
-                        let hash = prefixed_hash(NodePrefix::Leaf as u8, &data);
-                        computed_children_nodes.push(*hash);
-                    }
-                    StackPushType::ChildrenAlreadyPushed => {
-                        unreachable!()
-                    }
-                },
-                MerkleTreeNode::Empty => (),
-                MerkleTreeNode::EmptyTree => {
-                    return *blake2b256_hash(&[]).0;
-                }
-            }
-        }
-        unreachable!()
-    }
-}
-
-/// Each node in the merkle tree contains a 'prefixed' hash. This is done to give 'second preimage
-/// resistance'. More details can be found here <https://en.bitcoinwiki.org/wiki/Merkle_tree>
-enum NodePrefix {
-    /// Leaf nodes of the tree are hashed as `hash(0 ++ data)` where `++` denotes concatencation and
-    /// `data` is a byte array of the data.
-    Leaf = 0,
-    /// Internal nodes of the tree are hashed as `hash(1 ++ data_left_child ++ data_right_child)`.
-    Internal = 1,
-}
-
-// Generates a hash of data prefixed with `prefix`
-fn prefixed_hash(prefix: u8, data: &[u8]) -> Box<[u8; 32]> {
-    let mut hasher = VarBlake2b::new(32).unwrap();
-    hasher.update(&[prefix]);
-    hasher.update(data);
-    let hash = hasher.finalize_boxed();
-    hash.try_into().unwrap()
-}
-
-fn concatenate_hashes(hash_a: &[u8; 32], hash_b: &[u8; 32]) -> [u8; 64] {
-    let mut sum = [0; 64];
-    sum[0..32].clone_from_slice(hash_a);
-    sum[32..].clone_from_slice(hash_b);
-    sum
-}
-
-#[allow(clippy::unwrap_used)]
-#[cfg(test)]
-mod tests {
-    use crate::{concatenate_hashes, prefixed_hash, MerkleTreeNode, NodePrefix};
-
-    #[test]
-    fn test_single_leaf_merkle_tree() {
-        // Here the merkle tree looks as follows:
-        //      I
-        //     / \
-        //    L   E
-        // Where `I`, `L`, and `E` denote the root internal node, leaf node, and empty node,
-        // respectively.
-        let leaf_data: Vec<u8> = std::iter::repeat(0).take(32).collect();
-        let leaf_hash = prefixed_hash(NodePrefix::Leaf as u8, &leaf_data);
-        let root_hash = prefixed_hash(NodePrefix::Internal as u8, &*leaf_hash);
-
-        let merkle_root_node = MerkleTreeNode::new(vec![leaf_data]);
-
-        assert_eq!(merkle_root_node.hash(), *root_hash);
-    }
-
-    #[test]
-    fn test_2_leaf_merkle_tree() {
-        // Here the merkle tree looks as follows:
-        //      I
-        //     / \
-        //   L0   L1
-        // Where `I`, `L0`, and `1` denote the root internal node, first leaf node, and 2nd leaf node,
-        // respectively.
-        let leaf0_data: Vec<u8> = std::iter::repeat(0).take(32).collect();
-        let leaf1_data: Vec<u8> = std::iter::repeat(1).take(32).collect();
-        let leaf0_hash = prefixed_hash(NodePrefix::Leaf as u8, &leaf0_data);
-        let leaf1_hash = prefixed_hash(NodePrefix::Leaf as u8, &leaf1_data);
-        let root_hash = prefixed_hash(
-            NodePrefix::Internal as u8,
-            &concatenate_hashes(&*leaf0_hash, &*leaf1_hash),
-        );
-
-        let merkle_root_node = MerkleTreeNode::new(vec![leaf0_data, leaf1_data]);
-
-        assert_eq!(merkle_root_node.hash(), *root_hash);
-    }
-
-    #[test]
-    fn test_3_leaf_merkle_tree() {
-        // Here the merkle tree looks as follows:
-        //          I
-        //         / \
-        //        /   \
-        //       /     \
-        //      I0      I1
-        //     / \     / \
-        //   L0   L1  L2  E
-        let leaf0_data: Vec<u8> = std::iter::repeat(0).take(32).collect();
-        let leaf1_data: Vec<u8> = std::iter::repeat(1).take(32).collect();
-        let leaf2_data: Vec<u8> = std::iter::repeat(2).take(32).collect();
-        let leaf0_hash = prefixed_hash(NodePrefix::Leaf as u8, &leaf0_data);
-        let leaf1_hash = prefixed_hash(NodePrefix::Leaf as u8, &leaf1_data);
-        let leaf2_hash = prefixed_hash(NodePrefix::Leaf as u8, &leaf2_data);
-
-        // I0
-        let i0_hash = prefixed_hash(
-            NodePrefix::Internal as u8,
-            &concatenate_hashes(&*leaf0_hash, &*leaf1_hash),
-        );
-
-        // I1
-        let i1_hash = prefixed_hash(NodePrefix::Internal as u8, &*leaf2_hash);
-
-        let root_hash = prefixed_hash(
-            NodePrefix::Internal as u8,
-            &concatenate_hashes(&*i0_hash, &*i1_hash),
-        );
-
-        let merkle_root_node = MerkleTreeNode::new(vec![leaf0_data, leaf1_data, leaf2_data]);
-
-        assert_eq!(merkle_root_node.hash(), *root_hash);
-    }
-}
diff --git a/ergo-chain-types/src/digest32.rs b/ergo-chain-types/src/digest32.rs
index 6cfa1f8b5..f7f58d734 100644
--- a/ergo-chain-types/src/digest32.rs
+++ b/ergo-chain-types/src/digest32.rs
@@ -113,6 +113,14 @@ impl<const N: usize> TryFrom<Vec<u8>> for Digest<N> {
     }
 }
 
+impl<const N: usize> TryFrom<&[u8]> for Digest<N> {
+    type Error = DigestNError;
+    fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
+        let bytes: [u8; N] = value.try_into()?;
+        Ok(Digest::from(bytes))
+    }
+}
+
 impl<const N: usize> ScorexSerializable for Digest<N> {
     fn scorex_serialize<W: WriteSigmaVlqExt>(&self, w: &mut W) -> ScorexSerializeResult {
         w.write_all(self.0.as_ref())?;
diff --git a/ergo-chain-types/src/extensioncandidate.rs b/ergo-chain-types/src/extensioncandidate.rs
new file mode 100644
index 000000000..853328c74
--- /dev/null
+++ b/ergo-chain-types/src/extensioncandidate.rs
@@ -0,0 +1,24 @@
+/// Extension section of Ergo block. Contains key-value storage.
+#[derive(Clone, Debug, Default)]
+pub struct ExtensionCandidate {
+    /// Fields as a sequence of key -> value records. A key is 2-bytes long, value is 64 bytes max.
+    pub(crate) fields: Vec<([u8; 2], Vec<u8>)>,
+}
+
+impl ExtensionCandidate {
+    /// Creates a new [`ExtensionCandidate`] from fields. Fails if a field has a value > 64 bytes
+    pub fn new(fields: Vec<([u8; 2], Vec<u8>)>) -> Result<ExtensionCandidate, &'static str> {
+        match fields.iter().all(|(_, v)| v.len() <= 64) {
+            true => Ok(ExtensionCandidate { fields }),
+            false => Err("Values of fields must be less than 64 bytes in size"),
+        }
+    }
+    /// Return fields for this ExtensionCandidate
+    pub fn fields(&self) -> &[([u8; 2], Vec<u8>)] {
+        &self.fields
+    }
+    /// Returns fields for this ExtensionCandidate
+    pub fn fields_mut(&mut self) -> &mut Vec<([u8; 2], Vec<u8>)> {
+        &mut self.fields
+    }
+}
diff --git a/ergo-chain-types/src/lib.rs b/ergo-chain-types/src/lib.rs
index f6bf1af20..68db918ff 100644
--- a/ergo-chain-types/src/lib.rs
+++ b/ergo-chain-types/src/lib.rs
@@ -20,6 +20,7 @@
 mod base16_bytes;
 mod block_id;
 mod digest32;
+mod extensioncandidate;
 mod peer_addr;
 mod peer_connection_dir;
 
@@ -31,5 +32,6 @@ pub use digest32::ADDigest;
 pub use digest32::Digest;
 pub use digest32::Digest32;
 pub use digest32::DigestNError;
+pub use extensioncandidate::ExtensionCandidate;
 pub use peer_addr::PeerAddr;
 pub use peer_connection_dir::ConnectionDirection;
diff --git a/ergo-lib/Cargo.toml b/ergo-lib/Cargo.toml
index 4ad14018e..ba4479057 100644
--- a/ergo-lib/Cargo.toml
+++ b/ergo-lib/Cargo.toml
@@ -69,6 +69,7 @@ rest = ["ergo-rest"]
 wasm-bindgen-test = "0.3.10"
 ergotree-ir = { version = "^0.15.0", path = "../ergotree-ir", features = ["arbitrary"] }
 ergotree-interpreter = { version = "^0.15.0", path = "../ergotree-interpreter", features = ["arbitrary"] }
+ergo-merkle-tree = { version = "^0.2.0", path = "../ergo-merkle-tree", features = ["arbitrary"] }
 sigma-test-util = { version = "^0.3.0", path = "../sigma-test-util" }
 pretty_assertions = "0.7.2"
 bs58 = "0.4.0"
diff --git a/ergo-merkle-tree/Cargo.toml b/ergo-merkle-tree/Cargo.toml
index 902bc13e8..fffae9e43 100644
--- a/ergo-merkle-tree/Cargo.toml
+++ b/ergo-merkle-tree/Cargo.toml
@@ -14,7 +14,22 @@ serde = { version = "1.0", features = ["derive"], optional = true }
 serde_repr = { version = "0.1.7", optional = true }
 serde_json = { version = "1.0", optional = true }
 thiserror = { version = "1.0", optional = true } # currently thiserror is only needed for json conversion, so it's feature-gated behind json. This may change in the future
+itertools = "0.10.3"
+proptest-derive = {version = "0.3.0", optional = true }
+sigma-ser = { version = "0.4.0", path = "../sigma-ser" }
+ergo-chain-types = { version = "0.2.0", path = "../ergo-chain-types" }
+[dependencies.proptest]
+# wasm support, via https://altsysrq.github.io/proptest-book/proptest/wasm.html
+version = "1.0.0"
+# The default feature set includes things like process forking which are not
+# supported in Web Assembly.
+default-features = false
+# Enable using the `std` crate.
+features = ["std"]
+optional = true
+
 
 [features]
 default = ["json"]
 json = ["serde", "serde_json", "serde_repr", "base16", "thiserror"]
+arbitrary = ["proptest", "proptest-derive", "ergo-chain-types/arbitrary"]
diff --git a/ergo-merkle-tree/src/batchmerkleproof.rs b/ergo-merkle-tree/src/batchmerkleproof.rs
new file mode 100644
index 000000000..c823513b8
--- /dev/null
+++ b/ergo-merkle-tree/src/batchmerkleproof.rs
@@ -0,0 +1,219 @@
+use crate::LevelNode;
+use crate::NodeSide;
+use crate::{prefixed_hash2, INTERNAL_PREFIX};
+use ergo_chain_types::Digest32;
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+#[cfg_attr(feature = "arbitrary", derive(proptest_derive::Arbitrary))]
+pub struct BatchMerkleProofIndex {
+    pub index: usize,
+    pub hash: Digest32,
+}
+#[derive(Debug, Clone, PartialEq, Eq)]
+#[cfg_attr(feature = "json", derive(serde::Serialize, serde::Deserialize))]
+#[cfg_attr(
+    feature = "json",
+    serde(into = "crate::json::BatchMerkleProofJson"),
+    serde(try_from = "crate::json::BatchMerkleProofJson")
+)]
+#[cfg_attr(feature = "arbitrary", derive(proptest_derive::Arbitrary))]
+/// Compact Merkle multiproof. Can be created using [`crate::MerkleTree::proof_by_indices`]
+/// Implementation based on <https://deepai.org/publication/compact-merkle-multiproofs>
+pub struct BatchMerkleProof {
+    pub(crate) indices: Vec<BatchMerkleProofIndex>,
+    pub(crate) proofs: Vec<LevelNode>,
+}
+
+impl BatchMerkleProof {
+    /// Create a new BatchMerkleProof
+    pub fn new(indices: Vec<BatchMerkleProofIndex>, proofs: Vec<crate::LevelNode>) -> Self {
+        BatchMerkleProof { indices, proofs }
+    }
+
+    /// Generates root hash of proof, and compares it against expected root hash
+    pub fn valid(&self, expected_root: &[u8]) -> bool {
+        fn validate(
+            a: &[usize],
+            e: &[BatchMerkleProofIndex],
+            m: &[crate::LevelNode],
+        ) -> Option<Vec<Digest32>> {
+            // For each index in a, take the value of its immediate neighbor, and store each index with its neighbor
+            let b: Vec<(usize, usize)> = a
+                .iter()
+                .map(|i| if i % 2 == 0 { (*i, i + 1) } else { (i - 1, *i) })
+                .collect();
+
+            let mut e_new = vec![];
+            let mut m_new = m.to_owned();
+            // E must always have the same length as B
+            if e.len() != b.len() {
+                return None;
+            }
+            let mut i = 0;
+            // assign generated hashes to a new E that will be used for next iteration
+            while i < b.len() {
+                if b.len() > 1 && b.get(i) == b.get(i + 1) {
+                    // both indices needed for computing parent hash are part of e
+                    e_new.push(prefixed_hash2(
+                        INTERNAL_PREFIX,
+                        e[i].hash.as_ref(),
+                        e[i + 1].hash.as_ref(),
+                    ));
+                    i += 2;
+                } else {
+                    // Need an additional hash from m
+                    let head = if !m_new.is_empty() {
+                        m_new.remove(0)
+                    } else {
+                        return None;
+                    };
+
+                    if head.side == NodeSide::Left {
+                        e_new.push(prefixed_hash2(
+                            INTERNAL_PREFIX,
+                            head.hash.as_ref().map(|h| h.as_ref()),
+                            e[i].hash.as_ref(),
+                        ));
+                    } else {
+                        e_new.push(prefixed_hash2(
+                            INTERNAL_PREFIX,
+                            e[i].hash.as_ref(),
+                            head.hash.as_ref().map(|h| h.as_ref()),
+                        ));
+                    }
+                    i += 1;
+                }
+            }
+            let mut a_new: Vec<usize> = b.iter().map(|(_, b)| b / 2).collect(); // Generate indices for parents of current b
+            a_new.sort_unstable();
+            a_new.dedup();
+            // Repeat until root of tree is reached
+            if (!m_new.is_empty() || e_new.len() > 1) && !a_new.is_empty() {
+                let e: Vec<BatchMerkleProofIndex> = a_new
+                    .iter()
+                    .copied()
+                    .zip(e_new.into_iter())
+                    .map(|(index, hash)| BatchMerkleProofIndex { index, hash })
+                    .collect();
+                e_new = validate(&a_new, &e, &m_new)?;
+            }
+            Some(e_new)
+        }
+
+        let mut e = self.indices.to_owned();
+        e.sort_by_key(|BatchMerkleProofIndex { index, .. }| *index);
+        let a: Vec<usize> = e
+            .iter()
+            .map(|BatchMerkleProofIndex { index, .. }| *index)
+            .collect();
+        match validate(&a, &e, &self.proofs).as_deref() {
+            Some([root_hash]) => root_hash.as_ref() == expected_root,
+            _ => false,
+        }
+    }
+
+    /// Returns indices (leaf nodes) that are part of the proof
+    pub fn get_indices(&self) -> &[BatchMerkleProofIndex] {
+        &self.indices
+    }
+    /// Returns nodes included in proof to get to root node
+    pub fn get_proofs(&self) -> &[LevelNode] {
+        &self.proofs
+    }
+}
+
+use sigma_ser::ScorexSerializable;
+
+// Binary Serialization for BatchMerkleProof. Matches Scala implementation. Since the Scala implementation uses 4-byte ints for length/indices, this method will fail the proof or indexes length is > u32::MAX,
+impl ScorexSerializable for BatchMerkleProof {
+    fn scorex_serialize<W: sigma_ser::vlq_encode::WriteSigmaVlqExt>(
+        &self,
+        w: &mut W,
+    ) -> sigma_ser::ScorexSerializeResult {
+        w.put_u32_be_bytes(u32::try_from(self.indices.len())?)?; // for serialization, index length must be at most 4 bytes
+        w.put_u32_be_bytes(u32::try_from(self.proofs.len())?)?;
+
+        for BatchMerkleProofIndex { index, hash } in &self.indices {
+            w.put_u32_be_bytes(u32::try_from(*index)?)?;
+            w.write_all(hash.as_ref())?;
+        }
+
+        for proof in &self.proofs {
+            match proof.hash {
+                Some(ref hash) => w.write_all(hash.as_ref())?,
+                None => w.write_all(&[0; 32])?,
+            }
+            w.put_u8(proof.side as u8)?;
+        }
+
+        Ok(())
+    }
+
+    fn scorex_parse<R: sigma_ser::vlq_encode::ReadSigmaVlqExt>(
+        r: &mut R,
+    ) -> Result<Self, sigma_ser::ScorexParsingError> {
+        fn read_u32_be<R: sigma_ser::vlq_encode::ReadSigmaVlqExt>(
+            r: &mut R,
+        ) -> Result<u32, sigma_ser::ScorexParsingError> {
+            let mut bytes = [0u8; 4];
+            r.read_exact(&mut bytes)?;
+            Ok(u32::from_be_bytes(bytes))
+        }
+        let indices_len = read_u32_be(r)? as usize;
+        let proofs_len = read_u32_be(r)? as usize;
+        let indices = (0..indices_len)
+            .map(|_| {
+                let index = read_u32_be(r)? as usize;
+                let mut hash = Digest32::zero();
+                r.read_exact(&mut hash.0[..])?;
+                Ok(BatchMerkleProofIndex { index, hash })
+            })
+            .collect::<Result<Vec<BatchMerkleProofIndex>, sigma_ser::ScorexParsingError>>()?;
+
+        let proofs = (0..proofs_len)
+            .map(|_| {
+                let mut hash = Digest32::zero();
+                r.read_exact(&mut hash.0[..])?;
+                let empty = hash.as_ref().iter().all(|&b| b == 0);
+                let side: NodeSide = r.get_u8()?.try_into().map_err(|_| {
+                    sigma_ser::ScorexParsingError::ValueOutOfBounds(
+                        "Side can only be 0 or 1".into(),
+                    )
+                })?;
+
+                if empty {
+                    Ok(crate::LevelNode::empty_node(side))
+                } else {
+                    Ok(crate::LevelNode::new(hash, side))
+                }
+            })
+            .collect::<Result<Vec<crate::LevelNode>, sigma_ser::ScorexParsingError>>()?;
+        Ok(BatchMerkleProof::new(indices, proofs))
+    }
+}
+
+#[cfg(test)]
+#[cfg(feature = "arbitrary")]
+#[allow(clippy::unwrap_used, clippy::panic)]
+mod test {
+    use crate::batchmerkleproof::{BatchMerkleProof, BatchMerkleProofIndex};
+    use proptest::prelude::*;
+    use sigma_ser::ScorexSerializable;
+    proptest! {
+        #[test]
+        fn test_batchmerkleproof_serialization_roundtrip(proof in any::<BatchMerkleProof>().prop_filter("Indices > u32::max not allowed", |proof| proof.indices.len() < u32::MAX as usize && proof.indices.iter().all(|BatchMerkleProofIndex {index, ..}| *index < u32::MAX as usize))) {
+            let serialized_bytes = proof.scorex_serialize_bytes().unwrap();
+            assert_eq!(BatchMerkleProof::scorex_parse_bytes(&serialized_bytes).unwrap(), proof);
+            assert_eq!(serialized_bytes.len(), (8 + proof.proofs.len() * 33 + proof.indices.len() * 36));
+        }
+        #[test]
+        fn test_empty_deserialization(bytes in any::<[u8; 2]>()) {
+            assert!(BatchMerkleProof::scorex_parse_bytes(&bytes).is_err());
+        }
+        #[test]
+        fn test_invalid_deserialization(bytes in any::<[u8; 9]>()) {
+            assert!(BatchMerkleProof::scorex_parse_bytes(&bytes).is_err());
+        }
+
+    }
+}
diff --git a/ergo-merkle-tree/src/json.rs b/ergo-merkle-tree/src/json.rs
index cad6826e5..9bee6118c 100644
--- a/ergo-merkle-tree/src/json.rs
+++ b/ergo-merkle-tree/src/json.rs
@@ -1,3 +1,4 @@
+use crate::batchmerkleproof::{BatchMerkleProof, BatchMerkleProofIndex};
 use crate::{LevelNode, MerkleProof, NodeSide};
 use serde::{Deserialize, Serialize};
 use thiserror::Error;
@@ -9,17 +10,27 @@ impl std::convert::TryFrom<LevelNodeJson> for LevelNode {
     type Error = MerkleProofFromJsonError;
     fn try_from(node: LevelNodeJson) -> Result<Self, Self::Error> {
         let hash = base16::decode(&node.0)?;
-        Ok(LevelNode(
-            hash.try_into()
-                .map_err(|_| MerkleProofFromJsonError::LengthError)?,
-            node.1,
-        ))
+        Ok(LevelNode {
+            hash: match hash.len() {
+                0 => None,
+                _ => Some(
+                    hash.try_into()
+                        .map_err(|_| MerkleProofFromJsonError::LengthError)?,
+                ),
+            },
+            side: node.1,
+        })
     }
 }
 
 impl From<LevelNode> for LevelNodeJson {
     fn from(node: LevelNode) -> Self {
-        Self(base16::encode_lower(&node.0), node.1)
+        Self(
+            node.hash
+                .map(|hash| base16::encode_lower(&hash))
+                .unwrap_or_else(String::new),
+            node.side,
+        )
     }
 }
 
@@ -49,15 +60,12 @@ impl std::convert::TryFrom<crate::json::MerkleProofJson> for MerkleProof {
     type Error = MerkleProofFromJsonError;
     fn try_from(proof: crate::json::MerkleProofJson) -> Result<Self, Self::Error> {
         let leaf_data = base16::decode(&proof.leaf_data)?;
-        let leaf_data: [u8; 32] = leaf_data
-            .try_into()
-            .map_err(|_| MerkleProofFromJsonError::LengthError)?;
-        let mut levels = Vec::with_capacity(proof.levels.len());
-        for node in proof.levels {
-            let node: LevelNode = node.try_into()?;
-            levels.push(node);
-        }
-        Ok(Self { leaf_data, levels })
+        let levels: Result<Vec<LevelNode>, Self::Error> =
+            proof.levels.into_iter().map(LevelNode::try_from).collect();
+        Ok(Self {
+            leaf_data,
+            levels: levels?,
+        })
     }
 }
 #[cfg(feature = "json")]
@@ -69,3 +77,100 @@ impl From<MerkleProof> for MerkleProofJson {
         Self { leaf_data, levels }
     }
 }
+
+#[derive(Serialize, Deserialize)]
+struct IndexJson {
+    index: usize,
+    digest: String,
+}
+
+impl From<BatchMerkleProofIndex> for IndexJson {
+    fn from(index: BatchMerkleProofIndex) -> IndexJson {
+        IndexJson {
+            index: index.index,
+            digest: index.hash.into(),
+        }
+    }
+}
+
+impl TryFrom<IndexJson> for BatchMerkleProofIndex {
+    type Error = MerkleProofFromJsonError;
+    fn try_from(index: IndexJson) -> Result<BatchMerkleProofIndex, Self::Error> {
+        let digest = base16::decode(&index.digest)?
+            .try_into()
+            .map_err(|_| MerkleProofFromJsonError::LengthError)?;
+        Ok(BatchMerkleProofIndex {
+            index: index.index,
+            hash: digest,
+        })
+    }
+}
+
+/// Json Representation of a LevelNode. First field must be valid base16. Serializtion from LevelNode differs in ergo, which is why a different struct is used for BatchMerkleProof
+#[derive(Serialize, Deserialize, Clone, Debug)]
+pub struct BatchLevelNodeJson {
+    digest: String,
+    side: NodeSide,
+}
+
+impl std::convert::TryFrom<BatchLevelNodeJson> for LevelNode {
+    type Error = MerkleProofFromJsonError;
+    fn try_from(node: BatchLevelNodeJson) -> Result<Self, Self::Error> {
+        let hash = base16::decode(&node.digest)?;
+        Ok(LevelNode {
+            hash: match hash.len() {
+                0 => None,
+                _ => Some(
+                    hash.try_into()
+                        .map_err(|_| MerkleProofFromJsonError::LengthError)?,
+                ),
+            },
+            side: node.side,
+        })
+    }
+}
+
+impl From<LevelNode> for BatchLevelNodeJson {
+    fn from(node: LevelNode) -> Self {
+        Self {
+            digest: node
+                .hash
+                .map(|hash| base16::encode_lower(&hash))
+                .unwrap_or_else(String::new),
+            side: node.side,
+        }
+    }
+}
+#[derive(Serialize, Deserialize)]
+pub struct BatchMerkleProofJson {
+    indices: Vec<IndexJson>,
+    proofs: Vec<BatchLevelNodeJson>,
+}
+
+impl std::convert::TryFrom<BatchMerkleProofJson> for crate::batchmerkleproof::BatchMerkleProof {
+    type Error = MerkleProofFromJsonError;
+    fn try_from(
+        json: BatchMerkleProofJson,
+    ) -> Result<crate::batchmerkleproof::BatchMerkleProof, Self::Error> {
+        let indices: Result<Vec<BatchMerkleProofIndex>, Self::Error> =
+            json.indices.into_iter().map(IndexJson::try_into).collect();
+        let proofs: Result<Vec<LevelNode>, Self::Error> =
+            json.proofs.into_iter().map(LevelNode::try_from).collect();
+        Ok(BatchMerkleProof {
+            indices: indices?,
+            proofs: proofs?,
+        })
+    }
+}
+
+impl From<crate::batchmerkleproof::BatchMerkleProof> for BatchMerkleProofJson {
+    fn from(proof: crate::batchmerkleproof::BatchMerkleProof) -> BatchMerkleProofJson {
+        let indices = proof.indices.into_iter().map(IndexJson::from).collect();
+        let proofs = proof
+            .proofs
+            .into_iter()
+            .map(BatchLevelNodeJson::from)
+            .collect();
+        BatchMerkleProofJson { indices, proofs }
+    }
+}
diff --git a/ergo-merkle-tree/src/lib.rs b/ergo-merkle-tree/src/lib.rs
index a1df4c911..7143d86f6 100644
--- a/ergo-merkle-tree/src/lib.rs
+++ b/ergo-merkle-tree/src/lib.rs
@@ -20,6 +20,13 @@
 
 use blake2::digest::{Update, VariableOutput};
 use blake2::VarBlake2b;
+use ergo_chain_types::Digest32;
+
+// Constants for hashing
+/// Hash size for all nodes in [`crate::MerkleTree`], [`crate::MerkleProof`] and [`crate::BatchMerkleProof`]
+pub const HASH_SIZE: usize = 32;
+pub(crate) const INTERNAL_PREFIX: u8 = 1;
+pub(crate) const LEAF_PREFIX: u8 = 0;
 
 #[cfg(feature = "json")]
 pub(crate) mod json;
@@ -27,21 +34,38 @@ pub(crate) mod json;
 // Unwrap is safe here since the hash is guaranteed to be 32 bytes
 #[allow(clippy::unwrap_used)]
 // Generates a hash of data prefixed with `prefix`
-pub(crate) fn prefixed_hash(prefix: u8, data: &[u8]) -> Box<[u8; 32]> {
-    let mut hasher = VarBlake2b::new(32).unwrap();
+pub(crate) fn prefixed_hash(prefix: u8, data: &[u8]) -> Digest32 {
+    let mut hasher = VarBlake2b::new(HASH_SIZE).unwrap();
     hasher.update(&[prefix]);
     hasher.update(data);
-    let hash = hasher.finalize_boxed();
-    hash.try_into().unwrap()
+    let hash: Box<[u8; HASH_SIZE]> = hasher.finalize_boxed().try_into().unwrap();
+    Digest32::from(hash)
 }
 
-pub(crate) fn concatenate_hashes(hash_a: &[u8; 32], hash_b: &[u8; 32]) -> [u8; 64] {
-    let mut sum = [0; 64];
-    sum[0..32].clone_from_slice(hash_a);
-    sum[32..].clone_from_slice(hash_b);
-    sum
+#[allow(clippy::unwrap_used)]
+// Generates a hash of data prefixed with `prefix`, allows for an optional second hash
+pub(crate) fn prefixed_hash2<'a>(
+    prefix: u8,
+    data: impl Into<Option<&'a [u8]>>,
+    data2: impl Into<Option<&'a [u8]>>,
+) -> Digest32 {
+    let mut hasher = VarBlake2b::new(HASH_SIZE).unwrap();
+    hasher.update(&[prefix]);
+
+    if let Some(data) = data.into() {
+        hasher.update(data);
+    }
+    if let Some(data2) = data2.into() {
+        hasher.update(data2);
+    };
+    let hash: Box<[u8; HASH_SIZE]> = hasher.finalize_boxed().try_into().unwrap();
+    Digest32::from(hash)
 }
 
+mod batchmerkleproof;
 mod merkleproof;
+mod merkletree;
 
+pub use batchmerkleproof::BatchMerkleProof;
 pub use merkleproof::*;
+pub use merkletree::*;
diff --git a/ergo-merkle-tree/src/merkleproof.rs b/ergo-merkle-tree/src/merkleproof.rs
index 27d624576..91aa0c9f0 100644
--- a/ergo-merkle-tree/src/merkleproof.rs
+++ b/ergo-merkle-tree/src/merkleproof.rs
@@ -1,11 +1,14 @@
-use crate::{concatenate_hashes, prefixed_hash};
+use crate::INTERNAL_PREFIX;
+use crate::{prefixed_hash, prefixed_hash2};
+use ergo_chain_types::Digest32;
 
 /// The side the merkle node is on in the tree
 #[cfg_attr(
     feature = "json",
     derive(serde_repr::Serialize_repr, serde_repr::Deserialize_repr)
 )]
-#[derive(Copy, Clone, Debug)]
+#[cfg_attr(feature = "arbitrary", derive(proptest_derive::Arbitrary))]
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
 #[repr(u8)]
 pub enum NodeSide {
     /// Node is on the left side of the current level
@@ -33,13 +36,26 @@ impl std::convert::TryFrom<u8> for NodeSide {
     serde(into = "crate::json::LevelNodeJson"),
     serde(try_from = "crate::json::LevelNodeJson")
 )]
-#[derive(Copy, Clone, Debug)]
-pub struct LevelNode(pub [u8; 32], pub NodeSide);
+#[cfg_attr(feature = "arbitrary", derive(proptest_derive::Arbitrary))]
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct LevelNode {
+    /// Hash for LevelNode. Use [`LevelNode::empty_node`] to create a node with no hash
+    pub hash: Option<Digest32>,
+    /// Node Side in Merkle Tree
+    pub side: NodeSide,
+}
 
 impl LevelNode {
     /// Constructs a new levelnode from a 32 byte hash
-    pub fn new(hash: [u8; 32], side: NodeSide) -> Self {
-        Self(hash, side)
+    pub fn new(hash: Digest32, side: NodeSide) -> Self {
+        Self {
+            hash: Some(hash),
+            side,
+        }
+    }
+    /// Creates a new level node with no associated hash
+    pub fn empty_node(side: NodeSide) -> Self {
+        Self { hash: None, side }
     }
 }
 
@@ -52,21 +68,18 @@ impl LevelNode {
 )]
 #[derive(Clone, Debug)]
 pub struct MerkleProof {
-    pub(crate) leaf_data: [u8; 32],
+    pub(crate) leaf_data: Vec<u8>,
     pub(crate) levels: Vec<LevelNode>,
 }
 
 impl MerkleProof {
     /// Creates a new merkle proof with given leaf data and level data (bottom-upwards)
     /// You can verify it against a Blakeb256 root hash by using [`Self::valid()`]
-    pub fn new(
-        leaf_data: &[u8],
-        levels: &[LevelNode],
-    ) -> Result<Self, std::array::TryFromSliceError> {
-        Ok(MerkleProof {
-            leaf_data: leaf_data.try_into()?,
+    pub fn new(leaf_data: &[u8], levels: &[LevelNode]) -> Self {
+        MerkleProof {
+            leaf_data: leaf_data.to_owned(),
             levels: levels.to_owned(),
-        })
+        }
     }
 
     /// Validates the Merkle Proof against the expected root hash
@@ -75,13 +88,21 @@ impl MerkleProof {
         let hash = self
             .levels
             .iter()
-            .fold(leaf_hash, |prev_hash, node| match node.1 {
-                NodeSide::Left => prefixed_hash(1, &concatenate_hashes(&prev_hash, &node.0)), // Prefix hash with 1 (internal node hash)
-                NodeSide::Right => prefixed_hash(1, &concatenate_hashes(&node.0, &prev_hash)),
+            .fold(leaf_hash, |prev_hash, node| match node {
+                LevelNode {
+                    hash: Some(hash),
+                    side: NodeSide::Left,
+                } => prefixed_hash2(INTERNAL_PREFIX, prev_hash.as_ref(), hash.as_ref()), // Prefix hash with 1 (internal node hash)
+                LevelNode {
+                    hash: Some(hash),
+                    side: NodeSide::Right,
+                } => prefixed_hash2(INTERNAL_PREFIX, hash.as_ref(), prev_hash.as_ref()),
+                LevelNode { hash: None, .. } => prefixed_hash(INTERNAL_PREFIX, prev_hash.as_ref()),
             });
 
-        *hash == expected_root
+        hash.as_ref() == expected_root
     }
+    #[cfg(feature = "json")]
     /// Validates the MerkleProof against a base16 hash
     pub fn valid_base16(&self, expected_root: &str) -> Result<bool, base16::DecodeError> {
         // The rationale for adding this function is mainly to make using MerkleProof in Swift easier, without resorting to add a new dependency to base16
@@ -93,6 +114,11 @@ impl MerkleProof {
     pub fn add_node(&mut self, node: LevelNode) {
         self.levels.push(node);
     }
+
+    /// Returns Leaf Data for proof node
+    pub fn get_leaf_data(&self) -> &[u8] {
+        &self.leaf_data
+    }
 }
 
 #[cfg(test)]
@@ -102,6 +128,8 @@ mod test {
     use crate::LevelNode;
     use crate::MerkleProof;
     use crate::NodeSide;
+    use ergo_chain_types::Digest32;
+    use std::convert::TryFrom;
 
     // Ported client Merkle tree verification example from  https://github.com/ergoplatform/ergo/blob/master/src/test/scala/org/ergoplatform/examples/LiteClientExamples.scala
     #[test]
@@ -121,9 +149,11 @@ mod test {
         let tx_id = base16::decode(&tx_id).unwrap();
         let proof = MerkleProof::new(
             &tx_id,
-            &[LevelNode::new(levels[0..32].try_into().unwrap(), side)],
-        )
-        .unwrap();
+            &[LevelNode::new(
+                Digest32::try_from(&levels[0..32]).unwrap(),
+                side,
+            )],
+        );
         assert!(proof.valid(tx_root));
     }
 
@@ -144,4 +174,17 @@ mod test {
 
         assert!(proof.valid(&tx_root));
     }
+
+    // Tests block #0 on ergo mainnet, which contains only one transaction
+    #[test]
+    fn merkle_proof_genesis_block() {
+        let json = "{
+        \"leafData\" : \"4c6282be413c6e300a530618b37790be5f286ded758accc2aebd41554a1be308\",
+        \"levels\" : [[\"\", 0]]}";
+        let proof: MerkleProof = serde_json::from_str(json).unwrap();
+        let tx_root =
+            base16::decode("93fb06aa44413ff57ac878fda9377207d5db0e78833556b331b4d9727b3153ba")
+                .unwrap();
+        assert!(proof.valid(&tx_root));
+    }
 }
diff --git a/ergo-merkle-tree/src/merkletree.rs b/ergo-merkle-tree/src/merkletree.rs
new file mode 100644
index 000000000..9bec9ba5e
--- /dev/null
+++ b/ergo-merkle-tree/src/merkletree.rs
@@ -0,0 +1,386 @@
+use crate::batchmerkleproof::{BatchMerkleProof, BatchMerkleProofIndex};
+use crate::{prefixed_hash, prefixed_hash2, INTERNAL_PREFIX, LEAF_PREFIX};
+use ergo_chain_types::Digest32;
+use std::collections::{BTreeSet, HashMap};
+
+/// Node for a Merkle Tree
+#[derive(Debug, Clone, Eq, PartialEq)]
+#[cfg_attr(feature = "json", derive(serde::Serialize))]
+pub enum MerkleNode {
+    #[doc(hidden)]
+    Node { hash: Digest32 },
+    /// Leaf Node in MerkleTree. Can be created using [`Self::from_bytes`]
+    Leaf {
+        /// 32 byte Blake2b256 hash for data
+        hash: Digest32,
+        /// Leaf Data
+        data: Vec<u8>,
+    },
+    #[doc(hidden)]
+    EmptyNode,
+}
+
+impl MerkleNode {
+    /// Creates a new Leaf Node from bytes. The hash is prefixed with a leaf node prefix.
+    pub fn from_bytes<T: Into<Vec<u8>>>(bytes: T) -> Self {
+        let bytes = bytes.into();
+        let hash = prefixed_hash(LEAF_PREFIX, &bytes);
+        MerkleNode::Leaf { hash, data: bytes }
+    }
+    /// Gets hash for the node, returns None if it's an Empty Node
+    pub fn get_hash(&self) -> Option<&Digest32> {
+        match self {
+            MerkleNode::Node { hash } => Some(hash),
+            MerkleNode::Leaf { hash, .. } => Some(hash),
+            _ => None,
+        }
+    }
+    /// Gets data for the node if it's a leaf node
+    pub fn get_leaf_data(&self) -> Option<&Vec<u8>> {
+        match self {
+            MerkleNode::Leaf { data, .. } => Some(data),
+            _ => None,
+        }
+    }
+    pub(crate) fn empty() -> Self {
+        Self::EmptyNode
+    }
+}
+
+// utillity functions for indexing a binary tree
+fn get_left(node_index: usize) -> usize {
+    2 * node_index + 1
+}
+fn get_right(node_index: usize) -> usize {
+    2 * node_index + 2
+}
+
+fn get_parent(index: usize) -> Option<usize> {
+    index.checked_sub(1).map(|v| v / 2)
+}
+
+fn get_sibling(index: usize) -> Option<usize> {
+    let parent_index = get_parent(index)?;
+    if get_left(parent_index) != index {
+        Some(get_left(parent_index))
+    } else {
+        Some(get_right(parent_index))
+    }
+}
+
+// builds a new MerkleProof from tree nodes
+fn build_proof(
+    nodes: &[MerkleNode],
+    mut leaf_index: usize,
+    internal_nodes: usize,
+) -> Option<crate::MerkleProof> {
+    leaf_index += internal_nodes;
+    let mut proof_nodes: Vec<crate::LevelNode> = vec![];
+    let leaf_data = match nodes.get(leaf_index) {
+        Some(MerkleNode::Leaf { data, .. }) => data,
+        _ => return None,
+    };
+    while let Some(sibling) = get_sibling(leaf_index) {
+        let side = if sibling == leaf_index + 1 {
+            crate::NodeSide::Left // side information is encoded relative to the node we're trying to prove is in the tree. The leaf is on the left of the current node
+        } else {
+            crate::NodeSide::Right
+        };
+        match nodes[sibling].get_hash() {
+            Some(hash) => proof_nodes.push(crate::LevelNode::new(hash.clone(), side)),
+            _ => proof_nodes.push(crate::LevelNode::empty_node(side)),
+        }
+        leaf_index = get_parent(leaf_index)?;
+    }
+
+    Some(crate::MerkleProof::new(leaf_data, &proof_nodes))
+}
+
+fn build_multiproof(
+    nodes: &[MerkleNode],
+    leaf_indices: &[usize],
+    internal_nodes: usize,
+) -> Option<BatchMerkleProof> {
+    let mut multiproof: Vec<crate::LevelNode> = vec![];
+
+    let mut a: BTreeSet<usize> = leaf_indices
+        .iter()
+        .map(|idx| idx + internal_nodes)
+        .collect();
+    // while a does not contain the root index (0)
+    while !a.contains(&0) {
+        let mut b_pruned = BTreeSet::new();
+        for node in &a {
+            // for each leaf node, insert it and it's neighbor into the set. Since we're inserting into a set, we don't need any deduplication or sorting
+            b_pruned.insert(*node);
+            b_pruned.insert(get_sibling(*node)?);
+        }
+
+        let diff = &b_pruned - &a;
+        for node in diff {
+            let side = match get_sibling(node) {
+                Some(s) if s == node - 1 => crate::NodeSide::Right,
+                Some(_) => crate::NodeSide::Left,
+                None => unreachable!(),
+            };
+            let levelnode = match nodes[node].get_hash() {
+                Some(hash) => crate::LevelNode::new(hash.clone(), side),
+                None => crate::LevelNode::empty_node(side),
+            };
+            multiproof.push(levelnode);
+        }
+        a = b_pruned.into_iter().flat_map(get_parent).collect();
+    }
+
+    Some(BatchMerkleProof::new(
+        leaf_indices
+            .iter()
+            .flat_map(|idx| {
+                Some(BatchMerkleProofIndex {
+                    index: *idx,
+                    hash: nodes[idx + internal_nodes].get_hash().cloned()?,
+                })
+            })
+            .collect(),
+        multiproof,
+    ))
+}
+
+/// Merkle Tree
+#[derive(Debug)]
+#[cfg_attr(feature = "json", derive(serde::Serialize))]
+pub struct MerkleTree {
+    nodes: Vec<MerkleNode>,
+    elements_hash_index: HashMap<Digest32, usize>,
+    internal_nodes: usize,
+}
+
+impl MerkleTree {
+    /// Creates a new MerkleTree from leaf nodes
+    pub fn new(nodes: impl Into<Vec<MerkleNode>>) -> Self {
+        #[allow(clippy::unwrap_used)]
+        fn build_nodes(nodes: &mut [MerkleNode]) {
+            for pair in (1..nodes.len()).step_by(2).rev() {
+                let node = match (
+                    nodes[pair].get_hash(),
+                    nodes[get_sibling(pair).unwrap()].get_hash(), // since we pad nodes with no sibling with an empty node, get_sibling should always return Some
+                ) {
+                    (Some(left_hash), Some(right_hash)) => MerkleNode::Node {
+                        hash: prefixed_hash2(
+                            INTERNAL_PREFIX,
+                            left_hash.as_ref(),
+                            right_hash.as_ref(),
+                        ),
+                    },
+                    (Some(hash), None) => MerkleNode::Node {
+                        hash: prefixed_hash(INTERNAL_PREFIX, hash.as_ref()),
+                    },
+                    (None, None) => MerkleNode::EmptyNode,
+                    _ => unreachable!(),
+                };
+                nodes[get_parent(pair).unwrap()] = node;
+            }
+        }
+        let mut tree_nodes = nodes.into();
+        if tree_nodes.len() % 2 == 1 {
+            tree_nodes.push(MerkleNode::EmptyNode);
+        }
+        let elements_hash_index = tree_nodes
+            .iter()
+            .flat_map(MerkleNode::get_hash)
+            .enumerate()
+            .map(|(i, node)| (node.clone(), i))
+            .collect();
+        let leaf_nodes = tree_nodes.len();
+        // prepend leaf nodes with empty nodes to build the full tree
+        tree_nodes.splice(
+            0..0,
+            std::iter::repeat(MerkleNode::empty()).take(tree_nodes.len().next_power_of_two() - 1),
+        );
+        build_nodes(&mut tree_nodes);
+        let nodes_len = tree_nodes.len();
+        Self {
+            nodes: tree_nodes,
+            elements_hash_index,
+            internal_nodes: nodes_len - leaf_nodes,
+        }
+    }
+
+    /// Returns the root hash for MerkleTree. If the tree is empty, then returns [0; 32]
+    pub fn root_hash(&self) -> Digest32 {
+        self.nodes
+            .get(0)
+            .and_then(MerkleNode::get_hash)
+            .cloned()
+            .unwrap_or_else(Digest32::zero)
+    }
+    /// Returns the root hash for MerkleTree. If the tree is empty, then returns a special hash '0e5751c026e543b2e8ab2eb06099daa1d1e5df47778f7787faab45cdf12fe3a8', which is extension/transaction root hash for genesis block
+    /// See: <https://github.com/ergoplatform/ergo/issues/1077>
+    pub fn root_hash_special(&self) -> Digest32 {
+        self.nodes
+            .get(0)
+            .and_then(MerkleNode::get_hash)
+            .cloned()
+            .unwrap_or_else(
+                #[allow(clippy::unwrap_used)]
+                // unwrap is safe to use here, since digest size is always 32 bytes
+                || {
+                    use blake2::digest::{Update, VariableOutput};
+                    let mut hasher = crate::VarBlake2b::new(32).unwrap();
+                    hasher.update(&[]);
+                    let hash: Box<[u8; 32]> = hasher.finalize_boxed().try_into().unwrap();
+                    Digest32::from(hash)
+                },
+            )
+    }
+
+    /// Returns HashMap of hashes and their index in the tree
+    pub fn get_elements_hash_index(&self) -> &HashMap<Digest32, usize> {
+        &self.elements_hash_index
+    }
+
+    /// Builds a [`crate::MerkleProof`] for leaf_index. Returns None if index does not exist
+    pub fn proof_by_index(&self, leaf_index: usize) -> Option<crate::MerkleProof> {
+        build_proof(&self.nodes, leaf_index, self.internal_nodes)
+    }
+    /// Builds a [`crate::MerkleProof`] for given hash. Returns None if hash is not a leaf of tree
+    pub fn proof_by_element_hash(&self, hash: &Digest32) -> Option<crate::MerkleProof> {
+        let index = *self.elements_hash_index.get(hash)?;
+        self.proof_by_index(index)
+    }
+    /// Builds a [`crate::MerkleProof`] for element, by searching for its hash in the tree
+    pub fn proof_by_element(&self, data: &[u8]) -> Option<crate::MerkleProof> {
+        let hash = prefixed_hash(LEAF_PREFIX, data);
+        self.proof_by_element_hash(&hash)
+    }
+
+    /// Builds a [`crate::BatchMerkleProof`] for given indices
+    pub fn proof_by_indices(
+        &self,
+        leaf_indices: &[usize],
+    ) -> Option<crate::batchmerkleproof::BatchMerkleProof> {
+        let mut leaf_indices = leaf_indices.to_owned();
+        leaf_indices.sort_unstable();
+        leaf_indices.dedup();
+        // check that node index is in bounds, a leaf node, and not an empty node
+        if leaf_indices.is_empty()
+            || leaf_indices.iter().any(|i| {
+                self.nodes
+                    .get(self.internal_nodes + *i)
+                    .and_then(MerkleNode::get_leaf_data)
+                    .is_none()
+            })
+        {
+            return None;
+        }
+
+        build_multiproof(&self.nodes, &leaf_indices, self.internal_nodes)
+    }
+}
+
+#[cfg(test)]
+#[allow(clippy::unwrap_used, clippy::panic)]
+mod test {
+    use crate::{prefixed_hash, prefixed_hash2, MerkleNode, MerkleTree};
+
+    #[test]
+    fn merkle_tree_zero_elements() {
+        let tree = MerkleTree::new(&[][..]);
+        assert!(tree.root_hash().as_ref() == [0; 32]);
+    }
+    #[test]
+    fn merkle_tree_test_one_element() {
+        // Here the merkle tree looks as follows:
+        //      I
+        //     / \
+        //    L   E
+        // Where `I`, `L`, and `E` denote the root internal node, leaf node, and empty node,
+        // respectively.
+
+        let data = [1; 32];
+        let node = MerkleNode::from_bytes(data);
+        let tree = MerkleTree::new(&[node][..]);
+        assert_eq!(
+            tree.root_hash(),
+            prefixed_hash(1, prefixed_hash(0, &data).as_ref())
+        );
+    }
+    #[test]
+    fn merkle_tree_test_five_elements() {
+        let bytes = [1u8; 32];
+        let nodes = vec![MerkleNode::from_bytes(bytes); 5];
+        let tree = MerkleTree::new(&*nodes);
+        let h0x = prefixed_hash(0, &bytes);
+        let h10 = prefixed_hash2(1, h0x.as_ref(), h0x.as_ref());
+        let h11 = &h10;
+        let h12 = prefixed_hash(1, h0x.0.as_ref());
+        let h20 = prefixed_hash2(1, h10.as_ref(), h11.as_ref());
+        let h21 = prefixed_hash(1, h12.as_ref());
+        let h30 = prefixed_hash2(1, h20.as_ref(), h21.as_ref());
+        assert_eq!(tree.root_hash(), h30);
+    }
+
+    #[test]
+    fn merkle_tree_test_merkleproof() {
+        let nodes = [
+            MerkleNode::from_bytes([1; 32]),
+            MerkleNode::from_bytes([2; 32]),
+            MerkleNode::from_bytes([3; 32]),
+            MerkleNode::from_bytes([4; 32]),
+            MerkleNode::from_bytes([5; 32]),
+        ];
+        let tree = MerkleTree::new(&nodes[..]);
+        let tree_root = tree.root_hash();
+        for (i, node) in nodes.iter().enumerate() {
+            assert_eq!(
+                tree.proof_by_index(i).unwrap().get_leaf_data(),
+                node.get_leaf_data().unwrap()
+            );
+            assert!(tree.proof_by_index(i).unwrap().valid(tree_root.as_ref()));
+            assert!(tree
+                .proof_by_element(node.get_leaf_data().unwrap())
+                .unwrap()
+                .valid(tree_root.as_ref()));
+            assert!(tree
+                .proof_by_element_hash(node.get_hash().unwrap())
+                .unwrap()
+                .valid(tree_root.as_ref()));
+        }
+    }
+}
+
+#[cfg(feature = "arbitrary")]
+#[cfg(test)]
+#[allow(clippy::unwrap_used)]
+mod arbitrary {
+    use crate::{MerkleNode, MerkleTree};
+    use proptest::array::uniform32;
+    use proptest::collection::vec;
+    use proptest::prelude::*;
+    proptest! {
+        #[test]
+        fn merkle_tree_test_arbitrary_proof(data in vec(uniform32(0u8..), 0..1000)) {
+            let nodes: Vec<MerkleNode> = data.into_iter().map(MerkleNode::from_bytes).collect();
+            let tree = MerkleTree::new(&*nodes);
+            for (i, node) in nodes.iter().enumerate() {
+                assert_eq!(
+                    tree.proof_by_index(i).unwrap().get_leaf_data(),
+                    node.get_leaf_data().unwrap()
+                );
+                assert!(tree.proof_by_index(i).unwrap().valid(tree.root_hash().as_ref()));
+            }
+        }
+        #[test]
+        fn merkle_tree_test_arbitrary_batch_proof(data in vec(uniform32(0u8..), 0..1000), indices in vec(0..1000usize, 0..1000)) {
+            let valid = indices.iter().all(|i| *i < data.len()) && !indices.is_empty(); // TODO, is there any better strategy for proptest that doesn't require us to filter out invalid indices
+            let nodes: Vec<MerkleNode> = data.into_iter().map(MerkleNode::from_bytes).collect();
+            let tree = MerkleTree::new(&*nodes);
+            if valid {
+                assert!(tree.proof_by_indices(&indices).unwrap().valid(tree.root_hash().as_ref()));
+            }
+            else {
+                assert!(tree.proof_by_indices(&indices).is_none());
+            }
+        }
+    }
+}
diff --git a/ergo-nipopow/Cargo.toml b/ergo-nipopow/Cargo.toml
index 3c6e3bd30..dc1705057 100644
--- a/ergo-nipopow/Cargo.toml
+++ b/ergo-nipopow/Cargo.toml
@@ -26,6 +26,7 @@ proptest-derive = {version = "0.3.0", optional = true }
 sigma-ser = { version = "^0.4.0", path = "../sigma-ser" }
 sigma-util = { version = "^0.4.0", path = "../sigma-util" }
 ergo-chain-types = { version = "^0.2.0", path = "../ergo-chain-types" }
+ergo-merkle-tree = { version = "^0.2.0", path = "../ergo-merkle-tree" }
 serde = { version = "1.0", features = ["derive"] }
 serde_json = { version = "1.0" }
 
@@ -43,4 +44,4 @@ optional = true
 
 [features]
 default = []
-arbitrary = ["proptest", "proptest-derive", "ergo-chain-types/arbitrary"]
\ No newline at end of file
+arbitrary = ["proptest", "proptest-derive", "ergo-chain-types/arbitrary", "ergotree-ir/arbitrary"]
\ No newline at end of file
diff --git a/ergo-nipopow/src/lib.rs b/ergo-nipopow/src/lib.rs
index d09176b3c..68f7e5a62 100644
--- a/ergo-nipopow/src/lib.rs
+++ b/ergo-nipopow/src/lib.rs
@@ -23,6 +23,6 @@ mod nipopow_algos;
 mod nipopow_proof;
 mod nipopow_verifier;
 
-pub use nipopow_algos::{decode_compact_bits, NipopowAlgos};
+pub use nipopow_algos::{decode_compact_bits, NipopowAlgos, INTERLINK_VECTOR_PREFIX};
 pub use nipopow_proof::{NipopowProof, NipopowProofError, PoPowHeader};
 pub use nipopow_verifier::NipopowVerifier;
diff --git a/ergo-nipopow/src/nipopow_algos.rs b/ergo-nipopow/src/nipopow_algos.rs
index ac228ca06..7a5acda47 100644
--- a/ergo-nipopow/src/nipopow_algos.rs
+++ b/ergo-nipopow/src/nipopow_algos.rs
@@ -1,13 +1,17 @@
 use ergotree_ir::{chain::header::Header, sigma_protocol::dlog_group::order};
 use num_bigint::BigInt;
 use num_traits::ToPrimitive;
+use std::convert::TryInto;
 
 use crate::{
     autolykos_pow_scheme::{AutolykosPowScheme, AutolykosPowSchemeError},
     nipopow_proof::PoPowHeader,
     NipopowProof, NipopowProofError,
 };
+use ergo_chain_types::{BlockId, Digest32, ExtensionCandidate};
 
+/// Prefix for Block Interlinks
+pub const INTERLINK_VECTOR_PREFIX: u8 = 0x01;
 /// A set of utilities for working with NiPoPoW protocol.
 ///
 /// Based on papers:
@@ -191,6 +195,158 @@ impl NipopowAlgos {
         prefix.sort_by(|a, b| a.header.height.cmp(&b.header.height));
         NipopowProof::new(m, k, prefix, suffix_head, suffix_tail)
     }
+    /// Packs interlinks into key-value format of the block extension.
+    pub fn pack_interlinks(interlinks: Vec<BlockId>) -> Vec<([u8; 2], Vec<u8>)> {
+        let mut res = vec![];
+        let mut ix_distinct_block_ids = 0;
+        let mut curr_block_id_count = 1;
+        let mut curr_block_id = interlinks[0].clone();
+        for id in interlinks.into_iter().skip(1) {
+            if id == curr_block_id {
+                curr_block_id_count += 1;
+            } else {
+                let block_id_bytes: Vec<u8> = curr_block_id.clone().0.into();
+                let packed_value = std::iter::once(curr_block_id_count)
+                    .chain(block_id_bytes)
+                    .collect();
+                res.push((
+                    [INTERLINK_VECTOR_PREFIX, ix_distinct_block_ids],
+                    packed_value,
+                ));
+                curr_block_id = id;
+                curr_block_id_count = 1;
+                ix_distinct_block_ids += 1;
+            }
+        }
+        let block_id_bytes: Vec<u8> = curr_block_id.0.into();
+        let packed_value = std::iter::once(curr_block_id_count)
+            .chain(block_id_bytes)
+            .collect();
+        res.push((
+            [INTERLINK_VECTOR_PREFIX, ix_distinct_block_ids],
+            packed_value,
+        ));
+        res
+    }
+    /// Unpacks interlinks from key-value format of block extension.
+    pub fn unpack_interlinks(extension: &ExtensionCandidate) -> Result<Vec<BlockId>, &'static str> {
+        let mut res = vec![];
+        let entries = extension
+            .fields()
+            .iter()
+            .filter(|&(key, _)| key[0] == INTERLINK_VECTOR_PREFIX);
+        for (_, bytes) in entries {
+            // Each interlink is packed as [qty | blockId], which qty is a single-byte value
+            // representing the number of duplicates of `blockId`. Every `BlockId` is 32 bytes which
+            // implies that `bytes` is 33 bytes.
+            if bytes.len() != 33 {
+                return Err("Interlinks must be 33 bytes in size");
+            }
+            let qty = bytes[0];
+            let block_id_bytes: [u8; 32] = bytes[1..]
+                .try_into()
+                .map_err(|_| "Expected 32 byte BlockId")?;
+            let block_id = BlockId(Digest32::from(block_id_bytes));
+            res.extend(std::iter::repeat(block_id).take(qty as usize));
+        }
+        Ok(res)
+    }
+
+    /// Computes interlinks vector for a header next to `prevHeader`.
+    pub fn update_interlinks(
+        prev_header: Header,
+        prev_interlinks: Vec<BlockId>,
+    ) -> Result<Vec<BlockId>, AutolykosPowSchemeError> {
+        let is_genesis = prev_header.height == 1;
+        if !is_genesis {
+            // Interlinks vector cannot be empty in case of non-genesis header
+            assert!(!prev_interlinks.is_empty());
+            let genesis = prev_interlinks[0].clone();
+            let nipopow_algos = NipopowAlgos::default();
+            let prev_level = nipopow_algos.max_level_of(&prev_header)? as usize;
+            if prev_level > 0 {
+                // Adapted:
+                //   `(genesis +: tail.dropRight(prevLevel)) ++Seq.fill(prevLevel)(prevHeader.id)`
+                // from scala
+                if prev_interlinks.len() > prev_level {
+                    Ok(std::iter::once(genesis)
+                        .chain(
+                            prev_interlinks[1..(prev_interlinks.len() - prev_level)]
+                                .iter()
+                                .cloned(),
+                        )
+                        .chain(std::iter::repeat(prev_header.id).take(prev_level))
+                        .collect())
+                } else {
+                    Ok(std::iter::once(genesis)
+                        .chain(std::iter::repeat(prev_header.id).take(prev_level))
+                        .collect())
+                }
+            } else {
+                Ok(prev_interlinks)
+            }
+        } else {
+            Ok(vec![prev_header.id])
+        }
+    }
+    /// Returns [`ergo_merkle_tree::BatchMerkleProof`] for block interlinks
+    pub fn proof_for_interlink_vector(
+        ext: &ExtensionCandidate,
+    ) -> Option<ergo_merkle_tree::BatchMerkleProof> {
+        let interlinks: Vec<[u8; 2]> = ext
+            .fields()
+            .iter()
+            .map(|(key, _)| *key)
+            .filter(|key| key[0] == INTERLINK_VECTOR_PREFIX)
+            .collect();
+        if interlinks.is_empty() {
+            Some(ergo_merkle_tree::BatchMerkleProof::new(vec![], vec![]))
+        } else {
+            NipopowAlgos::extension_batch_proof_for(ext, &interlinks)
+        }
+    }
+    /// returns a MerkleProof for a single key element of [`ExtensionCandidate`]
+    pub fn extension_proof_for(
+        ext: &ExtensionCandidate,
+        key: [u8; 2],
+    ) -> Option<ergo_merkle_tree::MerkleProof> {
+        let tree = extension_merkletree(ext.fields());
+        let kv = ext.fields().iter().find(|(k, _)| *k == key)?;
+        tree.proof_by_element(&kv_to_leaf(kv))
+    }
+    /// Returns a [`ergo_merkle_tree::BatchMerkleProof`] (compact multi-proof) for multiple key elements of [`ExtensionCandidate`]
+    pub fn extension_batch_proof_for(
+        ext: &ExtensionCandidate,
+        keys: &[[u8; 2]],
+    ) -> Option<ergo_merkle_tree::BatchMerkleProof> {
+        let tree = extension_merkletree(ext.fields());
+        let indices: Vec<usize> = keys
+            .iter()
+            .flat_map(|k| ext.fields().iter().find(|(key, _)| key == k))
+            .map(kv_to_leaf)
+            .map(ergo_merkle_tree::MerkleNode::from_bytes)
+            .flat_map(|node| node.get_hash().cloned())
+            .flat_map(|hash| tree.get_elements_hash_index().get(&hash).copied())
+            .collect();
+        tree.proof_by_indices(&indices)
+    }
+}
+
+// converts a key value pair to an array of [key.length, key, val]
+fn kv_to_leaf(kv: &([u8; 2], Vec<u8>)) -> Vec<u8> {
+    std::iter::once(2u8)
+        .chain(kv.0.iter().copied())
+        .chain(kv.1.iter().copied())
+        .collect()
+}
+// creates a MerkleTree from a key/value pair of extension section
+fn extension_merkletree(kv: &[([u8; 2], Vec<u8>)]) -> ergo_merkle_tree::MerkleTree {
+    let leafs = kv
+        .iter()
+        .map(kv_to_leaf)
+        .map(ergo_merkle_tree::MerkleNode::from_bytes)
+        .collect::<Vec<ergo_merkle_tree::MerkleNode>>();
+    ergo_merkle_tree::MerkleTree::new(leafs)
 }
 
 /// The "compact" format is an encoding of a whole number `N` using an unsigned 32 bit number.
diff --git a/ergo-nipopow/src/nipopow_proof.rs b/ergo-nipopow/src/nipopow_proof.rs
index b0ff0c84a..f50f587a5 100644
--- a/ergo-nipopow/src/nipopow_proof.rs
+++ b/ergo-nipopow/src/nipopow_proof.rs
@@ -1,5 +1,6 @@
 use derive_more::From;
 use ergo_chain_types::BlockId;
+use ergo_merkle_tree::BatchMerkleProof;
 use ergotree_ir::chain::header::Header;
 use serde::{Deserialize, Serialize};
 use sigma_ser::{
@@ -83,7 +84,7 @@ impl NipopowProof {
     }
 
     fn is_valid(&self) -> bool {
-        self.has_valid_connections() && self.has_valid_heights()
+        self.has_valid_connections() && self.has_valid_heights() && self.has_valid_proofs()
     }
 
     /// Checks the connections of the blocks in the proof. Adjacent blocks should be linked either
@@ -117,6 +118,12 @@ impl NipopowProof {
             .zip(self.headers_chain().skip(1))
             .all(|(prev, next)| prev.height < next.height)
     }
+    /// Checks interlink proofs for each block using `PoPowHeader::check_interlinks_proof`
+    fn has_valid_proofs(&self) -> bool {
+        std::iter::once(&self.suffix_head)
+            .chain(self.prefix.iter())
+            .all(PoPowHeader::check_interlinks_proof)
+    }
 
     /// Returns an iterator representing a chain of `Headers` from `self.prefix`, to
     /// `self.suffix_head` and `self.suffix_tail`.
@@ -199,6 +206,34 @@ pub struct PoPowHeader {
     /// Interlinks are stored in reverse order: first element is always genesis header, then level
     /// of lowest target met etc
     pub interlinks: Vec<BlockId>,
+    /// BatchMerkleProof for interlinks in extension field
+    pub interlinks_proof: BatchMerkleProof,
+}
+
+impl PoPowHeader {
+    /// Validates interlinks merkle root against provided proof
+    pub fn check_interlinks_proof(&self) -> bool {
+        if self.interlinks.is_empty()
+            && self.interlinks_proof.get_indices().is_empty()
+            && self.interlinks_proof.get_proofs().is_empty()
+        {
+            true
+        } else {
+            let fields: Vec<ergo_merkle_tree::MerkleNode> =
+                NipopowAlgos::pack_interlinks(self.interlinks.clone())
+                    .into_iter()
+                    .map(|(k, v)| -> Vec<u8> {
+                        std::iter::once(2u8)
+                            .chain(k.iter().copied())
+                            .chain(v.into_iter())
+                            .collect()
+                    })
+                    .map(ergo_merkle_tree::MerkleNode::from_bytes)
+                    .collect();
+            let tree = ergo_merkle_tree::MerkleTree::new(fields);
+            self.interlinks_proof.valid(tree.root_hash().as_ref())
+        }
+    }
 }
 
 impl ScorexSerializable for PoPowHeader {
@@ -210,6 +245,9 @@ impl ScorexSerializable for PoPowHeader {
         for interlink in self.interlinks.iter() {
             w.write_all(&*interlink.0 .0)?;
         }
+        let proof_bytes = self.interlinks_proof.scorex_serialize_bytes()?;
+        w.put_u32(proof_bytes.len() as u32)?;
+        w.write_all(&proof_bytes)?;
 
         Ok(())
     }
@@ -229,9 +267,16 @@ impl ScorexSerializable for PoPowHeader {
                 Ok(BlockId(buf.into()))
             })
             .collect();
+
+        let proof_bytes = r.get_u32()? as usize;
+        let mut proof_buf = vec![0u8; proof_bytes];
+        r.read_exact(&mut proof_buf)?;
+        let interlinks_proof = BatchMerkleProof::scorex_parse_bytes(&proof_buf);
+
         Ok(Self {
             header,
             interlinks: interlinks?,
+            interlinks_proof: interlinks_proof?,
         })
     }
 }
@@ -243,6 +288,7 @@ mod arbitrary {
 
     use super::*;
     use ergo_chain_types::Digest32;
+    use ergo_chain_types::ExtensionCandidate;
     use proptest::prelude::*;
     use proptest::{arbitrary::Arbitrary, collection::vec};
 
@@ -254,7 +300,14 @@ mod arbitrary {
             (any::<Box<Header>>(), vec(any::<Digest32>(), 1..10))
                 .prop_map(|(header, digests)| PoPowHeader {
                     header: *header,
-                    interlinks: digests.into_iter().map(BlockId).collect(),
+                    interlinks: digests.iter().cloned().map(BlockId).collect(),
+                    interlinks_proof: NipopowAlgos::proof_for_interlink_vector(
+                        &ExtensionCandidate::new(NipopowAlgos::pack_interlinks(
+                            digests.into_iter().map(BlockId).collect(),
+                        ))
+                        .unwrap(),
+                    )
+                    .unwrap(),
                 })
                 .boxed()
         }
diff --git a/ergotree-interpreter/src/sigma_protocol/prover.rs b/ergotree-interpreter/src/sigma_protocol/prover.rs
index 3623a7b9e..3a1ba72dc 100644
--- a/ergotree-interpreter/src/sigma_protocol/prover.rs
+++ b/ergotree-interpreter/src/sigma_protocol/prover.rs
@@ -489,12 +489,11 @@ fn step4_real_conj(
                 })
                 .mapped(|c| c.into());
             Ok(Some(
-                uc.with_children(new_children).into()
-                // CorUnproven {
-                //     children: new_children,
-                //     ..cor.clone()
-                // }
-                // .into(),
+                uc.with_children(new_children).into(), // CorUnproven {
+                                                       //     children: new_children,
+                                                       //     ..cor.clone()
+                                                       // }
+                                                       // .into(),
             ))
         }
     }
diff --git a/sigma-ser/src/vlq_encode.rs b/sigma-ser/src/vlq_encode.rs
index 131f4cb41..a43dc6dc4 100644
--- a/sigma-ser/src/vlq_encode.rs
+++ b/sigma-ser/src/vlq_encode.rs
@@ -74,6 +74,12 @@ pub trait WriteSigmaVlqExt: io::Write {
         Self::put_u64(self, v as u64)
     }
 
+    /// Write bytes of v directly (big-endian format)
+    fn put_u32_be_bytes(&mut self, v: u32) -> io::Result<()> {
+        self.write_all(&v.to_be_bytes())?;
+        Ok(())
+    }
+
     /// Encode using ZigZag and then VLQ.
     fn put_i64(&mut self, v: i64) -> io::Result<()> {
         Self::put_u64(self, zig_zag_encode::encode_i64(v))


Test patch: