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

Issue:
[1500 SigmaUSD] NiPoPoW proof verification
Required for SPV workflow step 1.1 defined in https://github.com/ergoplatform/sigma-rust/issues/495

See [KMZ17](https://fc20.ifca.ai/preproceedings/74.pdf) for reference.

Implement `NipopowProof` in ergo-nipopow crate equivalent of the reference Scala implementation - https://github.com/ergoplatform/ergo/blob/c320810c498bca25a44197840c7c5a86440c5906/src/main/scala/org/ergoplatform/modifiers/history/popow/NipopowProof.scala#L9-L157 including binary and JSON serialization and everything in the call hierarchy starting from `NipopowProof.isBetterThan` and all the way down including `NipopowAlgos.bestArg` and `AutolykosPowScheme.powHit`.

Implement `NipopowVerifier` equivalent of the reference Scala implementation - https://github.com/ergoplatform/ergo/blob/c320810c498bca25a44197840c7c5a86440c5906/src/main/scala/org/ergoplatform/local/NipopowVerifier.scala#L8-L27

**EDIT**: Both `NipopowProof` and `NipopowVerifier` (with `process` and `best_proof`) should be exposed in Wasm/iOS API.


Discussion / hints:
Going to tackle this one.
I've yet to put through a draft PR, but I've finished studying the KMZ17 paper and I'm going down this rabbit hole with how Ergo and Bitcoin encode the difficulty targets.
No worries! Take your time! I appreciate you're taking a thorough approach.
Hey! I'm sorry, I totally forgot that it should be exposed in Wasm/iOS. I've added an EDIT in the description. 
Sure, no problem!

Fix patch:
diff --git a/Cargo.toml b/Cargo.toml
index 4e3ac453c..fbe3df08c 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -8,6 +8,7 @@ members = [
     "ergotree-interpreter",
     "ergo-lib",
     "ergo-p2p",
+    "ergo-chain-generation",
     "ergo-chain-types",
     "ergo-nipopow",
     "ergo-merkle-tree",
diff --git a/bindings/ergo-lib-c-core/src/block_header.rs b/bindings/ergo-lib-c-core/src/block_header.rs
index e5163f645..004c16e20 100644
--- a/bindings/ergo-lib-c-core/src/block_header.rs
+++ b/bindings/ergo-lib-c-core/src/block_header.rs
@@ -1,6 +1,9 @@
 //! Block header
 
-use crate::{error::*, util::mut_ptr_as_mut};
+use crate::{
+    error::*,
+    util::{const_ptr_as_ref, mut_ptr_as_mut},
+};
 use ergo_lib::ergotree_ir::chain::header::Header;
 
 /// Block header
@@ -19,3 +22,20 @@ pub unsafe fn block_header_from_json(
     *block_header_out = Box::into_raw(Box::new(header));
     Ok(())
 }
+
+/// Get `BlockHeader`s id
+pub unsafe fn block_header_id(
+    block_header_ptr: ConstBlockHeaderPtr,
+    block_id_out: *mut BlockIdPtr,
+) -> Result<(), Error> {
+    let block_header = const_ptr_as_ref(block_header_ptr, "block_header_ptr")?;
+    let block_id_out = mut_ptr_as_mut(block_id_out, "block_id_out")?;
+    *block_id_out = Box::into_raw(Box::new(BlockId(block_header.0.id.clone())));
+    Ok(())
+}
+
+/// Block id
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct BlockId(pub(crate) ergo_lib::ergotree_ir::chain::block_id::BlockId);
+pub type BlockIdPtr = *mut BlockId;
+pub type ConstBlockIdPtr = *const BlockId;
diff --git a/bindings/ergo-lib-c-core/src/error_conversion.rs b/bindings/ergo-lib-c-core/src/error_conversion.rs
index 83bc1b1bd..78de1ad6e 100644
--- a/bindings/ergo-lib-c-core/src/error_conversion.rs
+++ b/bindings/ergo-lib-c-core/src/error_conversion.rs
@@ -6,6 +6,7 @@ use std::num::ParseIntError;
 use base16::DecodeError;
 use bounded_vec::BoundedVecOutOfBounds;
 use ergo_lib::chain::transaction::TransactionError;
+use ergo_lib::ergo_nipopow::NipopowProofError;
 use ergo_lib::ergoscript_compiler::compiler::CompileError;
 use ergo_lib::ergotree_ir::chain::address::AddressEncoderError;
 use ergo_lib::ergotree_ir::chain::address::AddressError;
@@ -70,3 +71,4 @@ convert_error_via_debug!(ParseIntError);
 convert_error_via_debug!(ChildIndexError);
 convert_error_via_debug!(BoundedVecOutOfBounds);
 convert_error_via_debug!(TransactionError);
+convert_error_via_debug!(NipopowProofError);
diff --git a/bindings/ergo-lib-c-core/src/lib.rs b/bindings/ergo-lib-c-core/src/lib.rs
index e0a1e06a8..a1474be66 100644
--- a/bindings/ergo-lib-c-core/src/lib.rs
+++ b/bindings/ergo-lib-c-core/src/lib.rs
@@ -28,6 +28,7 @@ pub mod header;
 pub mod input;
 mod json;
 pub mod merkleproof;
+pub mod nipopow;
 pub mod reduced;
 pub mod secret_key;
 pub mod token;
diff --git a/bindings/ergo-lib-c-core/src/nipopow.rs b/bindings/ergo-lib-c-core/src/nipopow.rs
new file mode 100644
index 000000000..6eadc5397
--- /dev/null
+++ b/bindings/ergo-lib-c-core/src/nipopow.rs
@@ -0,0 +1,95 @@
+//! Bindings for NiPoPow
+
+use crate::{
+    block_header::{BlockHeader, ConstBlockIdPtr},
+    collections::{Collection, CollectionPtr},
+    util::{const_ptr_as_ref, mut_ptr_as_mut},
+    Error,
+};
+
+/// A structure representing NiPoPow proof.
+#[derive(Debug)]
+pub struct NipopowProof(ergo_lib::ergo_nipopow::NipopowProof);
+pub type NipopowProofPtr = *mut NipopowProof;
+pub type ConstNipopowProofPtr = *const NipopowProof;
+
+/// Implementation of the ≥ algorithm from [`KMZ17`], see Algorithm 4
+///
+/// [`KMZ17`]: https://fc20.ifca.ai/preproceedings/74.pdf
+pub unsafe fn nipopow_proof_is_better_than(
+    nipopow_proof_ptr: ConstNipopowProofPtr,
+    other_nipopow_proof_ptr: ConstNipopowProofPtr,
+) -> Result<bool, Error> {
+    let self_proof = const_ptr_as_ref(nipopow_proof_ptr, "nipopow_proof_ptr")?;
+    let other_proof = const_ptr_as_ref(other_nipopow_proof_ptr, "other_nipopow_proof_ptr")?;
+    Ok(self_proof.0.is_better_than(&other_proof.0)?)
+}
+
+/// Parse from JSON.
+pub unsafe fn nipopow_proof_from_json(
+    json: &str,
+    nipopow_proof_out: *mut NipopowProofPtr,
+) -> Result<(), Error> {
+    let nipopow_proof_out = mut_ptr_as_mut(nipopow_proof_out, "nipopow_proof_out")?;
+    let proof = serde_json::from_str(json).map(NipopowProof)?;
+    *nipopow_proof_out = Box::into_raw(Box::new(proof));
+    Ok(())
+}
+
+/// JSON representation as text
+pub unsafe fn nipopow_proof_to_json(
+    nipopow_proof_ptr: ConstNipopowProofPtr,
+) -> Result<String, Error> {
+    let proof = const_ptr_as_ref(nipopow_proof_ptr, "nipopow_proof_ptr")?;
+    let s = serde_json::to_string(&proof.0)?;
+    Ok(s)
+}
+
+/// A verifier for PoPoW proofs. During its lifetime, it processes many proofs with the aim of
+/// deducing at any given point what is the best (sub)chain rooted at the specified genesis.
+#[derive(Debug)]
+pub struct NipopowVerifier(ergo_lib::ergo_nipopow::NipopowVerifier);
+pub type NipopowVerifierPtr = *mut NipopowVerifier;
+pub type ConstNipopowVerifierPtr = *const NipopowVerifier;
+
+/// Create new instance
+pub unsafe fn nipopow_verifier_new(
+    genesis_block_id_ptr: ConstBlockIdPtr,
+    nipopow_verifier_out: *mut NipopowVerifierPtr,
+) -> Result<(), Error> {
+    let genesis_block_id = const_ptr_as_ref(genesis_block_id_ptr, "genesis_block_id_ptr")?;
+    let nipopow_verifier_out = mut_ptr_as_mut(nipopow_verifier_out, "nipopow_verifier_out")?;
+    *nipopow_verifier_out = Box::into_raw(Box::new(NipopowVerifier(
+        ergo_lib::ergo_nipopow::NipopowVerifier::new(genesis_block_id.0.clone()),
+    )));
+    Ok(())
+}
+
+/// Returns chain of `BlockHeader`s from the best proof.
+pub unsafe fn nipopow_verifier_best_chain(
+    nipopow_verifier_ptr: ConstNipopowVerifierPtr,
+    best_chain_out: *mut CollectionPtr<BlockHeader>,
+) -> Result<(), Error> {
+    let verifier = const_ptr_as_ref(nipopow_verifier_ptr, "nipopow_verifier_ptr")?;
+    let best_chain_out = mut_ptr_as_mut(best_chain_out, "best_chain_out")?;
+    *best_chain_out = Box::into_raw(Box::new(Collection(
+        verifier
+            .0
+            .best_chain()
+            .into_iter()
+            .map(BlockHeader)
+            .collect(),
+    )));
+    Ok(())
+}
+
+/// Process given proof
+pub unsafe fn nipopow_verifier_process(
+    nipopow_verifier_ptr: NipopowVerifierPtr,
+    nipopow_proof_ptr: ConstNipopowProofPtr,
+) -> Result<(), Error> {
+    let verifier = mut_ptr_as_mut(nipopow_verifier_ptr, "nipopow_verifier_ptr")?;
+    let new_proof = const_ptr_as_ref(nipopow_proof_ptr, "nipopow_proof_ptr")?;
+    verifier.0.process(new_proof.0.clone())?;
+    Ok(())
+}
diff --git a/bindings/ergo-lib-c/src/block_header.rs b/bindings/ergo-lib-c/src/block_header.rs
index c3000bcd1..2ca36fe1f 100644
--- a/bindings/ergo-lib-c/src/block_header.rs
+++ b/bindings/ergo-lib-c/src/block_header.rs
@@ -2,7 +2,10 @@
 use paste::paste;
 
 use ergo_lib_c_core::{
-    block_header::{block_header_from_json, BlockHeader, BlockHeaderPtr, ConstBlockHeaderPtr},
+    block_header::{
+        block_header_from_json, block_header_id, BlockHeader, BlockHeaderPtr, BlockIdPtr,
+        ConstBlockHeaderPtr,
+    },
     Error,
 };
 use std::{ffi::CStr, os::raw::c_char};
@@ -20,11 +23,27 @@ pub unsafe extern "C" fn ergo_lib_block_header_from_json(
     Error::c_api_from(res)
 }
 
+/// Get `BlockHeader`s id
+#[no_mangle]
+pub unsafe extern "C" fn ergo_lib_block_header_id(
+    block_header_ptr: ConstBlockHeaderPtr,
+    block_id_out: *mut BlockIdPtr,
+) {
+    #[allow(clippy::unwrap_used)]
+    block_header_id(block_header_ptr, block_id_out).unwrap();
+}
+
 /// Delete `BlockHeader`
 #[no_mangle]
 pub unsafe extern "C" fn ergo_lib_block_header_delete(ptr: BlockHeaderPtr) {
     delete_ptr(ptr)
 }
 
+/// Delete `BlockId`
+#[no_mangle]
+pub unsafe extern "C" fn ergo_lib_block_id_delete(ptr: BlockIdPtr) {
+    delete_ptr(ptr)
+}
+
 make_collection!(BlockHeaders, BlockHeader);
 make_ffi_eq!(BlockHeader);
diff --git a/bindings/ergo-lib-c/src/lib.rs b/bindings/ergo-lib-c/src/lib.rs
index 7e69d840c..f3c650c96 100644
--- a/bindings/ergo-lib-c/src/lib.rs
+++ b/bindings/ergo-lib-c/src/lib.rs
@@ -30,6 +30,8 @@ mod ext_secret_key;
 mod header;
 mod input;
 mod merkleproof;
+mod nipopow;
+
 mod reduced;
 mod secret_key;
 mod token;
@@ -51,6 +53,7 @@ pub use crate::ergo_tree::*;
 pub use crate::header::*;
 pub use crate::input::*;
 pub use crate::merkleproof::*;
+pub use crate::nipopow::*;
 pub use crate::reduced::*;
 pub use crate::secret_key::*;
 pub use crate::token::*;
@@ -100,6 +103,14 @@ pub struct ReturnNum<T: IntegerType> {
     error: ErrorPtr,
 }
 
+/// Convenience type to allow us to pass Rust bools (with possible error) through FFI to the C side.
+#[repr(C)]
+pub struct ReturnBool {
+    /// Returned value. Note that it's only valid if the error field is null!
+    value: bool,
+    error: ErrorPtr,
+}
+
 /// Convenience type to allow us to pass Rust `Option<_>` types through FFI to C side.
 #[repr(C)]
 pub struct ReturnOption {
diff --git a/bindings/ergo-lib-c/src/nipopow.rs b/bindings/ergo-lib-c/src/nipopow.rs
new file mode 100644
index 000000000..e263d4fe7
--- /dev/null
+++ b/bindings/ergo-lib-c/src/nipopow.rs
@@ -0,0 +1,108 @@
+//! Bindings for NiPoPow
+
+use ergo_lib_c_core::{
+    block_header::{BlockHeader, 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,
+        ConstNipopowProofPtr, ConstNipopowVerifierPtr, NipopowProofPtr, NipopowVerifierPtr,
+    },
+    Error,
+};
+use std::{
+    ffi::{CStr, CString},
+    os::raw::c_char,
+};
+
+use crate::{delete_ptr, ErrorPtr, ReturnBool};
+
+/// Implementation of the ≥ algorithm from [`KMZ17`], see Algorithm 4
+///
+/// [`KMZ17`]: https://fc20.ifca.ai/preproceedings/74.pdf
+#[no_mangle]
+pub unsafe extern "C" fn ergo_lib_nipopow_proof_is_better_than(
+    nipopow_proof_ptr: ConstNipopowProofPtr,
+    other_nipopow_proof_ptr: ConstNipopowProofPtr,
+) -> ReturnBool {
+    match nipopow_proof_is_better_than(nipopow_proof_ptr, other_nipopow_proof_ptr) {
+        Ok(value) => ReturnBool {
+            value,
+            error: std::ptr::null_mut(),
+        },
+        Err(e) => ReturnBool {
+            value: false, // Just a dummy value
+            error: Error::c_api_from(Err(e)),
+        },
+    }
+}
+
+/// Parse from JSON.
+#[no_mangle]
+pub unsafe extern "C" fn ergo_lib_nipopow_proof_from_json(
+    json_str: *const c_char,
+    nipopow_proof_out: *mut NipopowProofPtr,
+) -> ErrorPtr {
+    let json = CStr::from_ptr(json_str).to_string_lossy();
+    let res = nipopow_proof_from_json(&json, nipopow_proof_out);
+    Error::c_api_from(res)
+}
+
+/// JSON representation as text
+#[no_mangle]
+pub unsafe extern "C" fn ergo_lib_nipopow_proof_to_json(
+    nipopow_proof_ptr: ConstNipopowProofPtr,
+    _json_str: *mut *const c_char,
+) -> ErrorPtr {
+    #[allow(clippy::unwrap_used)]
+    let res = match nipopow_proof_to_json(nipopow_proof_ptr) {
+        Ok(s) => {
+            *_json_str = CString::new(s).unwrap().into_raw();
+            Ok(())
+        }
+        Err(e) => Err(e),
+    };
+    Error::c_api_from(res)
+}
+
+/// Delete `NipopowProof`
+#[no_mangle]
+pub unsafe extern "C" fn ergo_lib_nipopow_proof_delete(ptr: NipopowProofPtr) {
+    delete_ptr(ptr)
+}
+
+/// Create new `NipopowVerifier` instance
+#[no_mangle]
+pub unsafe extern "C" fn ergo_lib_nipopow_verifier_new(
+    genesis_block_id_ptr: ConstBlockIdPtr,
+    nipopow_verifier_out: *mut NipopowVerifierPtr,
+) {
+    #[allow(clippy::unwrap_used)]
+    nipopow_verifier_new(genesis_block_id_ptr, nipopow_verifier_out).unwrap();
+}
+
+/// Returns chain of `BlockHeader`s from the best proof.
+#[no_mangle]
+pub unsafe extern "C" fn ergo_lib_nipopow_verifier_best_chain(
+    nipopow_verifier_ptr: ConstNipopowVerifierPtr,
+    best_chain_out: *mut CollectionPtr<BlockHeader>,
+) {
+    #[allow(clippy::unwrap_used)]
+    nipopow_verifier_best_chain(nipopow_verifier_ptr, best_chain_out).unwrap();
+}
+
+/// Process given proof
+#[no_mangle]
+pub unsafe extern "C" fn ergo_lib_nipopow_verifier_process(
+    nipopow_verifier_ptr: NipopowVerifierPtr,
+    nipopow_proof_ptr: ConstNipopowProofPtr,
+) -> ErrorPtr {
+    let res = nipopow_verifier_process(nipopow_verifier_ptr, nipopow_proof_ptr);
+    Error::c_api_from(res)
+}
+
+/// Delete `NipopowVerifier`
+#[no_mangle]
+pub unsafe extern "C" fn ergo_lib_nipopow_verifier_delete(ptr: NipopowVerifierPtr) {
+    delete_ptr(ptr)
+}
diff --git a/bindings/ergo-lib-ios/Sources/ErgoLib/BlockHeader.swift b/bindings/ergo-lib-ios/Sources/ErgoLib/BlockHeader.swift
index 195444609..215549da7 100644
--- a/bindings/ergo-lib-ios/Sources/ErgoLib/BlockHeader.swift
+++ b/bindings/ergo-lib-ios/Sources/ErgoLib/BlockHeader.swift
@@ -21,11 +21,33 @@ class BlockHeader {
         self.pointer = ptr
     }
     
+    /// Get Block id
+    func getBlockId() -> BlockId {
+        var ptr: BlockIdPtr?
+        ergo_lib_block_header_id(self.pointer, &ptr)
+        return BlockId(withRawPointer: ptr!)
+    }
+    
     deinit {
         ergo_lib_block_header_delete(self.pointer)
     }
 }
 
+/// Represents the id of a ``BlockHeader``
+class BlockId {
+    internal var pointer: BlockIdPtr
+    
+    /// Takes ownership of an existing ``BlockIdPtr``. Note: we must ensure that no other instance
+    /// of ``BlockId`` can hold this pointer.
+    internal init(withRawPointer ptr: BlockIdPtr) {
+        self.pointer = ptr
+    }
+    
+    deinit {
+        ergo_lib_block_id_delete(self.pointer)
+    }
+}
+
 extension BlockHeader: Equatable {
     static func ==(lhs: BlockHeader, rhs: BlockHeader) -> Bool {
         ergo_lib_block_header_eq(lhs.pointer, rhs.pointer)
@@ -40,6 +62,7 @@ class BlockHeaders {
     init() {
         self.pointer = BlockHeaders.initRawPtrEmpty()
     }
+    
     /// Parse ``BlockHeader`` array from JSON (Node API)
     init(fromJSON: Any) throws {
         let json = JSON(fromJSON)
@@ -60,6 +83,12 @@ class BlockHeaders {
         }
     }
     
+    /// Takes ownership of an existing ``BlockHeadersPtr``. Note: we must ensure that no other instance
+    /// of ``BlockHeaders`` can hold this pointer.
+    internal init(withRawPointer ptr: BlockHeadersPtr) {
+        self.pointer = ptr
+    }
+    
     /// Use the C-API to create an empty collection and return the raw pointer that points to this
     /// collection.
     private static func initRawPtrEmpty() -> BlockHeaderPtr {
diff --git a/bindings/ergo-lib-ios/Sources/ErgoLib/Nipopow.swift b/bindings/ergo-lib-ios/Sources/ErgoLib/Nipopow.swift
new file mode 100644
index 000000000..da4d608fb
--- /dev/null
+++ b/bindings/ergo-lib-ios/Sources/ErgoLib/Nipopow.swift
@@ -0,0 +1,73 @@
+
+import Foundation
+import ErgoLibC
+
+/// NiPoPow proof
+class NipopowProof {
+    internal var pointer: NipopowProofPtr
+    
+    /// Parse ``NipopowProof`` from JSON
+    init(withJson json: String) throws {
+        var ptr: NipopowProofPtr?
+        let error = json.withCString { cs in
+            ergo_lib_nipopow_proof_from_json(cs, &ptr)
+        }
+        try checkError(error)
+        self.pointer = ptr!
+    }
+    
+    /// Implementation of the ≥ algorithm from [`KMZ17`], see Algorithm 4
+    ///
+    /// [`KMZ17`]: https://fc20.ifca.ai/preproceedings/74.pdf
+    func isBetterThan(otherProof: NipopowProof) throws -> Bool {
+        let res = ergo_lib_nipopow_proof_is_better_than(self.pointer, otherProof.pointer)
+        try checkError(res.error)
+        return res.value
+    }
+    
+    /// JSON representation as text
+    func toJSON() throws -> JSON? {
+        var cStr: UnsafePointer<CChar>?
+        let error = ergo_lib_nipopow_proof_to_json(self.pointer, &cStr)
+        try checkError(error)
+        let str = String(cString: cStr!)
+        ergo_lib_delete_string(UnsafeMutablePointer(mutating: cStr))
+        return try str.data(using: .utf8, allowLossyConversion: false).map {
+            try JSON(data: $0)
+        }
+    }
+    
+    deinit {
+        ergo_lib_nipopow_proof_delete(self.pointer)
+    }
+}
+
+/// A verifier for PoPoW proofs. During its lifetime, it processes many proofs with the aim of
+/// deducing at any given point what is the best (sub)chain rooted at the specified genesis.
+class NipopowVerifier {
+    internal var pointer: NipopowVerifierPtr
+    
+    /// Create new instance
+    init(withGenesisBlockId genesisBlockId: BlockId) {
+        var ptr: NipopowProofPtr?
+        ergo_lib_nipopow_verifier_new(genesisBlockId.pointer, &ptr)
+        self.pointer = ptr!
+    }
+    
+    /// Returns chain of `BlockHeader`s from the best proof.
+    func bestChain() -> BlockHeaders {
+        var ptr: BlockHeadersPtr?
+        ergo_lib_nipopow_verifier_best_chain(self.pointer, &ptr)
+        return BlockHeaders(withRawPointer: ptr!)
+    }
+    
+    /// Process given proof
+    func process(newProof: NipopowProof) throws {
+        let error = ergo_lib_nipopow_verifier_process(self.pointer, newProof.pointer)
+        try checkError(error)
+    }
+    
+    deinit {
+        ergo_lib_nipopow_verifier_delete(self.pointer)
+    }
+}
diff --git a/bindings/ergo-lib-wasm/src/block_header.rs b/bindings/ergo-lib-wasm/src/block_header.rs
index 433d20919..581f015f5 100644
--- a/bindings/ergo-lib-wasm/src/block_header.rs
+++ b/bindings/ergo-lib-wasm/src/block_header.rs
@@ -21,8 +21,18 @@ impl BlockHeader {
     pub fn from_json(json: &str) -> Result<BlockHeader, JsValue> {
         serde_json::from_str(json).map(Self).map_err(to_js)
     }
+
+    /// Get Header's id
+    pub fn id(&self) -> BlockId {
+        self.0.id.clone().into()
+    }
 }
 
+/// Block id
+#[wasm_bindgen]
+#[derive(PartialEq, Eq, Debug, Clone, From, Into)]
+pub struct BlockId(pub(crate) ergo_lib::ergotree_ir::chain::block_id::BlockId);
+
 /// Collection of BlockHeaders
 #[wasm_bindgen]
 #[derive(PartialEq, Eq, Debug, Clone)]
diff --git a/bindings/ergo-lib-wasm/src/error_conversion.rs b/bindings/ergo-lib-wasm/src/error_conversion.rs
index 6c3c40d83..795c5c5ee 100644
--- a/bindings/ergo-lib-wasm/src/error_conversion.rs
+++ b/bindings/ergo-lib-wasm/src/error_conversion.rs
@@ -5,6 +5,7 @@ use std::num::ParseIntError;
 
 use base16::DecodeError;
 use bounded_vec::BoundedVecOutOfBounds;
+use ergo_lib::ergo_nipopow::NipopowProofError;
 use ergo_lib::ergotree_ir::chain::address::AddressEncoderError;
 use ergo_lib::ergotree_ir::chain::address::AddressError;
 use ergo_lib::ergotree_ir::chain::digest32::Digest32Error;
@@ -83,3 +84,4 @@ from_error_to_wrap_via_debug!(BoundedVecOutOfBounds);
 from_error_to_wrap_via_debug!(ExtSecretKeyError);
 from_error_to_wrap_via_debug!(DerivationPathError);
 from_error_to_wrap_via_debug!(ExtPubKeyError);
+from_error_to_wrap_via_debug!(NipopowProofError);
diff --git a/bindings/ergo-lib-wasm/src/lib.rs b/bindings/ergo-lib-wasm/src/lib.rs
index c1c55eba1..209177e89 100644
--- a/bindings/ergo-lib-wasm/src/lib.rs
+++ b/bindings/ergo-lib-wasm/src/lib.rs
@@ -29,6 +29,8 @@ pub mod ergo_tree;
 pub mod header;
 pub mod input;
 pub mod merkleproof;
+pub mod nipopow;
+
 pub mod prover_result;
 pub mod secret_key;
 pub mod token;
diff --git a/bindings/ergo-lib-wasm/src/nipopow.rs b/bindings/ergo-lib-wasm/src/nipopow.rs
new file mode 100644
index 000000000..ed4753eb8
--- /dev/null
+++ b/bindings/ergo-lib-wasm/src/nipopow.rs
@@ -0,0 +1,55 @@
+//! Bindings for NiPoPow
+
+use super::block_header::BlockId;
+use derive_more::{From, Into};
+use wasm_bindgen::prelude::*;
+
+use crate::{block_header::BlockHeader, error_conversion::to_js};
+
+/// A structure representing NiPoPow proof.
+#[wasm_bindgen]
+#[derive(Debug, From, Into)]
+pub struct NipopowProof(ergo_lib::ergo_nipopow::NipopowProof);
+
+impl NipopowProof {
+    /// Implementation of the ≥ algorithm from [`KMZ17`], see Algorithm 4
+    ///
+    /// [`KMZ17`]: https://fc20.ifca.ai/preproceedings/74.pdf
+    pub fn is_better_than(&self, that: &NipopowProof) -> Result<bool, JsValue> {
+        self.0.is_better_than(&that.0).map_err(to_js)
+    }
+
+    /// JSON representation as text
+    pub fn to_json(&self) -> Result<String, JsValue> {
+        serde_json::to_string_pretty(&self.0).map_err(to_js)
+    }
+
+    /// Parse from JSON
+    /// supports Ergo Node/Explorer API and box values and token amount encoded as strings
+    pub fn from_json(json: &str) -> Result<Self, JsValue> {
+        serde_json::from_str(json).map(Self).map_err(to_js)
+    }
+}
+
+/// A verifier for PoPoW proofs. During its lifetime, it processes many proofs with the aim of
+/// deducing at any given point what is the best (sub)chain rooted at the specified genesis.
+#[wasm_bindgen]
+#[derive(Debug, From, Into)]
+pub struct NipopowVerifier(ergo_lib::ergo_nipopow::NipopowVerifier);
+
+impl NipopowVerifier {
+    /// Create new instance
+    pub fn new(genesis_block_id: BlockId) -> Self {
+        ergo_lib::ergo_nipopow::NipopowVerifier::new(genesis_block_id.0).into()
+    }
+
+    /// Returns chain of `BlockHeader`s from the best proof.
+    pub fn best_chain(&self) -> Vec<BlockHeader> {
+        self.0.best_chain().into_iter().map(|h| h.into()).collect()
+    }
+
+    /// Process given proof
+    pub fn process(&mut self, new_proof: NipopowProof) -> Result<(), JsValue> {
+        self.0.process(new_proof.0).map_err(to_js)
+    }
+}
diff --git a/ergo-chain-generation/Cargo.toml b/ergo-chain-generation/Cargo.toml
new file mode 100644
index 000000000..e12c21be9
--- /dev/null
+++ b/ergo-chain-generation/Cargo.toml
@@ -0,0 +1,17 @@
+[package]
+name = "ergo-chain-generation"
+version = "0.14.0"
+license = "CC0-1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+base16 = "0.2.1"
+blake2 = "0.9"
+byteorder = "1"
+ergo-lib = {version = "^0.14.0", path = "../ergo-lib"}
+num-bigint = "0.4.0"
+rand = "0.8.4"
+sigma-test-util = { version = "^0.3.0", path = "../sigma-test-util" }
+ergo-nipopow = { version = "^0.1", path = "../ergo-nipopow" }
diff --git a/ergo-chain-generation/src/chain_generation.rs b/ergo-chain-generation/src/chain_generation.rs
new file mode 100644
index 000000000..eca66b0a6
--- /dev/null
+++ b/ergo-chain-generation/src/chain_generation.rs
@@ -0,0 +1,473 @@
+//! Chain generation with Autolykos v1 and v2 proof of work. To make things tests tractable the
+//! difficulty is set to 1.
+
+use std::convert::TryFrom;
+
+use ergo_lib::ergotree_interpreter::sigma_protocol::{
+    private_input::DlogProverInput,
+    prover::{ContextExtension, ProofBytes},
+};
+use ergo_lib::ergotree_ir::{
+    chain::{
+        digest32::{blake2b256_hash, ADDigest, Digest32},
+        ergo_box::{box_value::BoxValue, BoxId},
+        header::{AutolykosSolution, Header},
+        votes::Votes,
+    },
+    ergo_tree::ErgoTree,
+    serialization::{sigma_byte_writer::SigmaByteWriter, SigmaSerializable},
+    sigma_protocol::dlog_group::{order, EcPoint},
+};
+use ergo_lib::{
+    chain::{
+        ergo_box::box_builder::ErgoBoxCandidateBuilder,
+        transaction::{prover_result::ProverResult, Input, Transaction, TxIoVec},
+    },
+    ergotree_ir::chain::block_id::BlockId,
+};
+use num_bigint::{BigInt, Sign};
+use rand::{thread_rng, Rng};
+
+use crate::{
+    default_miner_secret, pack_interlinks, unpack_interlinks, update_interlinks, ErgoFullBlock,
+    ExtensionCandidate, MerkleTreeNode,
+};
+
+/// Section of a block which contains transactions.
+#[allow(dead_code)]
+struct BlockTransactions {
+    /// Identifier of a header of a corresponding block
+    header_id: BlockId,
+    /// Protocol version for the block
+    block_version: u8,
+    /// Transactions of the block
+    txs: Vec<Transaction>,
+}
+
+/// Returns an iterator to generate an arbitrary number of simulated Ergo blocks
+pub fn block_stream(start_block: Option<ErgoFullBlock>) -> impl Iterator<Item = ErgoFullBlock> {
+    let spending_proof = ProverResult {
+        proof: ProofBytes::try_from(String::from("7c")).unwrap(),
+        extension: ContextExtension::empty(),
+    };
+    let inputs = vec![Input {
+        box_id: BoxId::zero(),
+        spending_proof,
+    }];
+
+    // Corresponds to `BoxUtils.minimalErgoAmountSimulated` call in `ChainGenerator.scala` in `ergo`.
+    let output_candidates = {
+        // Taken from `dex_t2tpool_parse` unit test in `ergotree-ir`.
+        let base16_str = "19a3030f0400040204020404040404060406058080a0f6f4acdbe01b058080a0f6f4acdbe01b050004d00f0400040005000500d81ad601b2a5730000d602e4c6a70405d603db63087201d604db6308a7d605b27203730100d606b27204730200d607b27203730300d608b27204730400d609b27203730500d60ab27204730600d60b9973078c720602d60c999973088c720502720bd60d8c720802d60e998c720702720dd60f91720e7309d6108c720a02d6117e721006d6127e720e06d613998c7209027210d6147e720d06d615730ad6167e721306d6177e720c06d6187e720b06d6199c72127218d61a9c72167218d1edededededed93c27201c2a793e4c672010405720292c17201c1a793b27203730b00b27204730c00938c7205018c720601ed938c7207018c720801938c7209018c720a019593720c730d95720f929c9c721172127e7202069c7ef07213069a9c72147e7215067e9c720e720206929c9c721472167e7202069c7ef0720e069a9c72117e7215067e9c721372020695ed720f917213730e907217a19d721972149d721a7211ed9272199c7217721492721a9c72177211";
+
+        let tree_bytes = base16::decode(base16_str.as_bytes()).unwrap();
+        let ergo_tree = ErgoTree::sigma_parse_bytes(&tree_bytes).unwrap();
+
+        let value = BoxValue::try_from(i64::MAX).unwrap();
+        let creation_height = i32::MAX as u32;
+        let box_candidate = ErgoBoxCandidateBuilder::new(value, ergo_tree, creation_height)
+            .build()
+            .unwrap();
+        vec![box_candidate]
+    };
+
+    let txs = vec![Transaction::new(
+        TxIoVec::from_vec(inputs).unwrap(),
+        None,
+        TxIoVec::from_vec(output_candidates).unwrap(),
+    )
+    .unwrap()];
+    let block_version = 1;
+    let start = if start_block.is_some() {
+        start_block
+    } else {
+        next_block(
+            None,
+            txs.clone(),
+            ExtensionCandidate { fields: vec![] },
+            block_version,
+        )
+    };
+    std::iter::successors(start, move |b| {
+        next_block(
+            Some(b.clone()),
+            txs.clone(),
+            ExtensionCandidate { fields: vec![] },
+            block_version,
+        )
+    })
+}
+
+fn next_block(
+    prev_block: Option<ErgoFullBlock>,
+    txs: Vec<Transaction>,
+    mut extension: ExtensionCandidate,
+    block_version: u8,
+) -> Option<ErgoFullBlock> {
+    let interlinks = prev_block
+        .as_ref()
+        .map(|b| update_interlinks(b.header.clone(), unpack_interlinks(&b.extension)))
+        .unwrap_or_default();
+    if !interlinks.is_empty() {
+        // Only non-empty for non-genesis block
+        extension.fields.extend(pack_interlinks(interlinks));
+    }
+    prove_block(
+        prev_block.map(|b| b.header),
+        block_version,
+        txs,
+        0,
+        extension,
+    )
+}
+
+fn prove_block(
+    parent_header: Option<Header>,
+    version: u8,
+    transactions: Vec<Transaction>,
+    timestamp: u64,
+    extension_candidate: ExtensionCandidate,
+) -> Option<ErgoFullBlock> {
+    // Corresponds to initial difficulty of 1, in line with the ergo test suite.
+    let n_bits = 16842752_u64;
+    let state_root = ADDigest::zero();
+    let votes = Votes([0, 0, 0]);
+
+    // Ergo test suite uses randomly generated value for ad_proofs_root.
+    let mut rng = thread_rng();
+    let how_many: usize = rng.gen_range(0..5000);
+    let mut ad_proofs_bytes: Vec<u8> = std::iter::repeat(0_u8).take(how_many).collect();
+    for x in &mut ad_proofs_bytes {
+        *x = rng.gen();
+    }
+    let ad_proofs_root = blake2b256_hash(&ad_proofs_bytes);
+    let transaction_root = transactions_root(&transactions, version);
+
+    // Now prove
+    let (parent_id, height) = if let Some(parent_header) = parent_header {
+        (parent_header.id.clone(), parent_header.height + 1)
+    } else {
+        (BlockId(Digest32::zero()), 1)
+    };
+
+    let extension_root = MerkleTreeNode::new(
+        extension_candidate
+            .clone()
+            .fields
+            .into_iter()
+            .map(|(key, value)| {
+                let mut data = vec![2_u8];
+                data.extend(key);
+                data.extend(value);
+                data
+            })
+            .collect(),
+    )
+    .hash()
+    .into();
+
+    let dummy_autolykos_solution = AutolykosSolution {
+        miner_pk: Box::new(EcPoint::default()),
+        pow_onetime_pk: None,
+        nonce: vec![],
+        pow_distance: Some(BigInt::from(0_u8)),
+    };
+
+    let mut header = Header {
+        version,
+        id: BlockId(Digest32::zero()),
+        parent_id,
+        ad_proofs_root,
+        state_root,
+        transaction_root,
+        timestamp,
+        n_bits,
+        height,
+        extension_root,
+        autolykos_solution: dummy_autolykos_solution,
+        votes,
+    };
+    let msg = blake2b256_hash(&header.serialize_without_pow().unwrap())
+        .0
+        .to_vec();
+    // Order of the secp256k1 elliptic curve
+    let order = order();
+    let target_b = order.clone() / ergo_nipopow::decode_compact_bits(header.n_bits);
+
+    let x = DlogProverInput::random();
+    let x_bigint = BigInt::from_bytes_be(Sign::Plus, &x.to_bytes());
+
+    use byteorder::{BigEndian, WriteBytesExt};
+    let mut height_bytes = Vec::with_capacity(4);
+    #[allow(clippy::unwrap_used)]
+    height_bytes.write_u32::<BigEndian>(header.height).unwrap();
+    let popow_algos = ergo_nipopow::NipopowAlgos::default();
+    let big_n = popow_algos.pow_scheme.calc_big_n(version, height);
+
+    // Check nonces
+    let min_nonce = i64::MIN;
+    let max_nonce = i64::MAX;
+
+    let (sk, sk_bigint) = default_miner_secret();
+    let p1 = sk.public_image_bytes().unwrap();
+    let p2 = x.public_image().h.sigma_serialize_bytes().unwrap();
+    for i in min_nonce..max_nonce {
+        let nonce = {
+            let mut bytes = vec![];
+            bytes.write_i64::<BigEndian>(i).unwrap();
+            bytes
+        };
+        let seed_hash = if version == 1 {
+            let mut seed = msg.clone();
+            seed.extend(&nonce);
+            *blake2b256_hash(&seed).0
+        } else {
+            *popow_algos
+                .pow_scheme
+                .calc_seed_v2(big_n, &msg, &nonce, &height_bytes)
+                .unwrap()
+        };
+
+        let sum = popow_algos
+            .pow_scheme
+            .gen_indexes(&seed_hash, big_n)
+            .into_iter()
+            .map(|ix| {
+                let mut index_bytes = vec![];
+                index_bytes.write_u32::<BigEndian>(ix).unwrap();
+                generate_element(version, &msg, &p1, &p2, &index_bytes, &height_bytes)
+            })
+            .fold(BigInt::from(0_u8), |acc, e| acc + e);
+        let d = if version == 1 {
+            (x_bigint.clone() * sum - sk_bigint.clone()).modpow(&BigInt::from(1_u8), &order.clone())
+        } else {
+            BigInt::from_bytes_be(Sign::Plus, &*blake2b256_hash(&sum.to_signed_bytes_be()).0)
+        };
+
+        if d <= target_b {
+            let autolykos_solution = AutolykosSolution {
+                miner_pk: sk.public_key().unwrap().public_key.into(),
+                pow_onetime_pk: Some(x.public_image().h),
+                nonce,
+                pow_distance: Some(d),
+            };
+            // Compute header ID
+            let mut id_bytes = header.serialize_without_pow().unwrap();
+            let mut data = Vec::new();
+            let mut w = SigmaByteWriter::new(&mut data, None);
+            autolykos_solution.serialize_bytes(version, &mut w).unwrap();
+            id_bytes.extend(data);
+            let id = BlockId(blake2b256_hash(&id_bytes));
+            header.id = id;
+            header.autolykos_solution = autolykos_solution;
+            break;
+        }
+    }
+
+    Some(ErgoFullBlock {
+        header,
+        extension: extension_candidate,
+    })
+}
+
+/// Generate element of Autolykos equation.
+fn generate_element(
+    version: u8,
+    msg: &[u8],
+    pk: &[u8],
+    w: &[u8],
+    index_bytes: &[u8],
+    height_bytes: &[u8],
+) -> BigInt {
+    let popow_algos = ergo_nipopow::NipopowAlgos::default();
+    if version == 1 {
+        // Autolykos v. 1: H(j|M|pk|m|w) (line 5 from the Algo 2 of the spec)
+        let mut concat = vec![];
+        concat.extend(index_bytes);
+        concat.extend(popow_algos.pow_scheme.calc_big_m());
+        concat.extend(pk);
+        concat.extend(msg);
+        concat.extend(w);
+        let valid_range = (BigInt::from(2_u8).pow(256) / order()) * order();
+        numeric_hash(&concat, valid_range, order())
+    } else {
+        // Autolykos v. 2: H(j|h|M) (line 5 from the Algo 2 of the spec)
+        let mut concat = vec![];
+        concat.extend(index_bytes);
+        concat.extend(height_bytes);
+        concat.extend(popow_algos.pow_scheme.calc_big_m());
+        BigInt::from_bytes_be(Sign::Plus, &blake2b256_hash(&concat).0[1..])
+    }
+}
+
+/// One way cryptographic hash function that produces numbers in [0,q) range.
+/// It calculates Blake2b256 hash of a provided input and checks whether the result is
+/// in range from 0 to a maximum number divisible by q without remainder.
+/// If yes, it returns the result mod q, otherwise make one more iteration using hash as an input.
+/// This is done to ensure uniform distribution of the resulting numbers.
+fn numeric_hash(input: &[u8], valid_range: BigInt, order: BigInt) -> BigInt {
+    let mut hashed: Vec<u8> = blake2b256_hash(input).into();
+    loop {
+        let bi = BigInt::from_bytes_be(Sign::Plus, &hashed);
+        if bi < valid_range {
+            break bi.modpow(&BigInt::from(1_u8), &order);
+        } else {
+            hashed = blake2b256_hash(&hashed).into();
+        }
+    }
+}
+
+/// 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(
+            txs.iter()
+                .map(|tx| {
+                    blake2b256_hash(&tx.bytes_to_sign().unwrap())
+                        .0
+                        .as_ref()
+                        .to_vec()
+                })
+                .collect(),
+        );
+        tree.hash().into()
+    } else {
+        let tree = MerkleTreeNode::new(
+            txs.iter()
+                .map(|tx| {
+                    let mut data = blake2b256_hash(&tx.bytes_to_sign().unwrap())
+                        .0
+                        .as_ref()
+                        .to_vec();
+                    //  Id of transaction "witness" (taken from Bitcoin jargon, means commitment to
+                    //  signatures of a transaction).  Id is 248-bit long, to distinguish
+                    //  transaction ids from witness ids in Merkle tree of transactions, where both
+                    //  kinds of ids are written into leafs of the tree.
+                    let witness: Vec<u8> = tx
+                        .inputs
+                        .iter()
+                        .flat_map(|input| {
+                            let i: Vec<u8> = input.spending_proof.proof.clone().into();
+                            i
+                        })
+                        .collect();
+                    data.extend(witness);
+                    data
+                })
+                .collect(),
+        );
+        tree.hash().into()
+    }
+}
+
+#[allow(clippy::unwrap_used)]
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use ergo_nipopow::{NipopowAlgos, NipopowProof, PoPowHeader};
+
+    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),
+            },
+        }))
+        .take(len)
+        .map(|b| PoPowHeader {
+            header: b.header,
+            interlinks: unpack_interlinks(&b.extension),
+        })
+        .collect()
+    }
+
+    #[test]
+    fn test_nipopow_lowest_common_ancestor_diverging_autolykos_v1() {
+        let popow_algos = NipopowAlgos::default();
+        for size in [10, 100, 200] {
+            let stream = block_stream(None);
+            let chain_0: Vec<_> = stream.take(size).collect();
+            let branch_point = chain_0[size / 2].clone();
+            let mut chain_1 = chain_0[..(size / 2)].to_vec();
+            chain_1.extend(block_stream(Some(branch_point.clone())).take(size / 2));
+            let chain_0_headers: Vec<_> = chain_0.iter().map(|b| &b.header).collect();
+            let chain_1_headers: Vec<_> = chain_1.iter().map(|b| &b.header).collect();
+            assert_eq!(
+                popow_algos.lowest_common_ancestor(&chain_0_headers, &chain_1_headers),
+                Some(branch_point.header.clone())
+            );
+        }
+    }
+
+    #[test]
+    fn test_nipopow_best_arg_always_greater_for_better_proofs_autolykos_v1() {
+        let m = 30;
+        let k = 30;
+        let popow_algos = NipopowAlgos::default();
+
+        let chain_0 = generate_popowheader_chain(100, None);
+        let proof_0 = popow_algos.prove(&chain_0, k, m).unwrap();
+        let chain_1 = chain_0[0..70].to_vec();
+        let proof_1 = popow_algos.prove(&chain_1, k, m).unwrap();
+
+        assert!(proof_0.has_valid_connections());
+        assert!(proof_1.has_valid_connections());
+        assert!(proof_0.prefix.len() > proof_1.prefix.len());
+
+        let chain_0_headers: Vec<_> = chain_0.iter().map(|p| &p.header).collect();
+        let chain_1_headers: Vec<_> = chain_1.iter().map(|p| &p.header).collect();
+
+        assert!(
+            popow_algos.best_arg(&chain_0_headers, m).unwrap()
+                > popow_algos.best_arg(&chain_1_headers, m).unwrap()
+        );
+    }
+
+    #[test]
+    fn test_nipopow_is_better_than_marginally_longer_chain_better_autolykos_v1() {
+        let m = 30;
+        let k = 30;
+        let popow_algos = NipopowAlgos::default();
+
+        let short_chain = generate_popowheader_chain(1000, None);
+        let branch_point = short_chain[short_chain.len() - 1].clone();
+        let mut long_chain = short_chain.clone();
+        long_chain.extend(std::iter::once(
+            generate_popowheader_chain(2, Some(branch_point))[1].clone(),
+        ));
+        let short_proof = popow_algos.prove(&short_chain, k, m).unwrap();
+        let long_proof = popow_algos.prove(&long_chain, k, m).unwrap();
+        assert!(!short_proof.is_better_than(&long_proof).unwrap());
+    }
+
+    #[test]
+    fn test_nipopow_is_better_than_disconnected_chain_should_not_win_autolykos_v1() {
+        let m = 50;
+        let k = 1;
+        let size = 100;
+        let popow_algos = NipopowAlgos::default();
+
+        let longer_chain = generate_popowheader_chain(size * 2, None);
+        let longer_proof = popow_algos.prove(&longer_chain, k, m).unwrap();
+
+        let chain = longer_chain[0..size].to_vec();
+        let proof = popow_algos.prove(&chain, k, m).unwrap();
+
+        let disconnected_proof_prefix: Vec<_> = proof
+            .prefix
+            .clone()
+            .into_iter()
+            .take(proof.prefix.len() / 2)
+            .chain(longer_proof.prefix)
+            .collect();
+        let disconnected_proof = NipopowProof {
+            popow_algos,
+            m,
+            k,
+            prefix: disconnected_proof_prefix,
+            suffix_head: proof.suffix_head.clone(),
+            suffix_tail: proof.suffix_tail.clone(),
+        };
+        assert!(proof.is_better_than(&disconnected_proof).unwrap());
+    }
+}
diff --git a/ergo-chain-generation/src/fake_pow_scheme.rs b/ergo-chain-generation/src/fake_pow_scheme.rs
new file mode 100644
index 000000000..9c5140a8a
--- /dev/null
+++ b/ergo-chain-generation/src/fake_pow_scheme.rs
@@ -0,0 +1,362 @@
+//! Fake pow scheme from `ergo` node tests. This method generates blocks according to Autolykos v1
+//! and the 'd' parameter is generated deterministically such that the level of the block is
+//! **always** positive.
+//!
+//! Tests are all adapted from <https://github.com/ergoplatform/ergo/blob/master/src/test/scala/org/ergoplatform/modifiers/history/PoPowAlgosSpec.scala>
+
+#[allow(clippy::unwrap_used)]
+#[cfg(test)]
+mod tests {
+    use ergo_nipopow::{NipopowAlgos, NipopowProof};
+
+    use ergo_lib::ergotree_interpreter::sigma_protocol::private_input::DlogProverInput;
+    use ergo_lib::ergotree_ir::{
+        chain::{
+            block_id::BlockId,
+            digest32::{blake2b256_hash, ADDigest, Digest32},
+            header::{AutolykosSolution, Header},
+            votes::Votes,
+        },
+        serialization::sigma_byte_writer::SigmaByteWriter,
+        sigma_protocol::dlog_group::{order, EcPoint},
+    };
+    use ergo_nipopow::PoPowHeader;
+    use num_bigint::BigInt;
+    use rand::{thread_rng, Rng};
+
+    use crate::{
+        default_miner_secret, pack_interlinks, unpack_interlinks, update_interlinks, ErgoFullBlock,
+        ExtensionCandidate, MerkleTreeNode,
+    };
+
+    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),
+            },
+        }))
+        .take(len)
+        .map(|b| PoPowHeader {
+            header: b.header,
+            interlinks: unpack_interlinks(&b.extension),
+        })
+        .collect()
+    }
+
+    fn block_stream(start_block: Option<ErgoFullBlock>) -> impl Iterator<Item = ErgoFullBlock> {
+        let block_version = 1;
+        let start = if start_block.is_some() {
+            start_block
+        } else {
+            next_block(None, ExtensionCandidate { fields: vec![] }, block_version)
+        };
+        std::iter::successors(start, move |b| {
+            next_block(
+                Some(b.clone()),
+                ExtensionCandidate { fields: vec![] },
+                block_version,
+            )
+        })
+    }
+
+    fn next_block(
+        prev_block: Option<ErgoFullBlock>,
+        mut extension: ExtensionCandidate,
+        block_version: u8,
+    ) -> Option<ErgoFullBlock> {
+        let interlinks = prev_block
+            .as_ref()
+            .map(|b| update_interlinks(b.header.clone(), unpack_interlinks(&b.extension)))
+            .unwrap_or_default();
+        if !interlinks.is_empty() {
+            // Only non-empty for non-genesis block
+            extension.fields.extend(pack_interlinks(interlinks));
+        }
+        prove_block(prev_block.map(|b| b.header), block_version, 0, extension)
+    }
+
+    fn prove_block(
+        parent_header: Option<Header>,
+        version: u8,
+        timestamp: u64,
+        extension_candidate: ExtensionCandidate,
+    ) -> Option<ErgoFullBlock> {
+        // Corresponds to initial difficulty of 1, in line with the ergo test suite.
+        let n_bits = 16842752_u64;
+        let state_root = ADDigest::zero();
+        let votes = Votes([0, 0, 0]);
+
+        // Ergo test suite uses randomly generated value for ad_proofs_root.
+        let mut rng = thread_rng();
+        let how_many: usize = rng.gen_range(0..5000);
+        let mut ad_proofs_bytes: Vec<u8> = std::iter::repeat(0_u8).take(how_many).collect();
+        for x in &mut ad_proofs_bytes {
+            *x = rng.gen();
+        }
+        let ad_proofs_root = blake2b256_hash(&ad_proofs_bytes);
+
+        // Use dummy transaction root.
+        let transaction_root = [
+            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+            0, 0, 0,
+        ]
+        .into();
+
+        // Now prove
+        let (parent_id, height) = if let Some(parent_header) = parent_header {
+            (parent_header.id.clone(), parent_header.height + 1)
+        } else {
+            (BlockId(Digest32::zero()), 1)
+        };
+
+        let extension_root = MerkleTreeNode::new(
+            extension_candidate
+                .clone()
+                .fields
+                .into_iter()
+                .map(|(key, value)| {
+                    let mut data = vec![2_u8];
+                    data.extend(key);
+                    data.extend(value);
+                    data
+                })
+                .collect(),
+        )
+        .hash()
+        .into();
+
+        let dummy_autolykos_solution = AutolykosSolution {
+            miner_pk: Box::new(EcPoint::default()),
+            pow_onetime_pk: None,
+            nonce: vec![],
+            pow_distance: Some(BigInt::from(0_u8)),
+        };
+
+        let mut header = Header {
+            version,
+            id: BlockId(Digest32::zero()),
+            parent_id,
+            ad_proofs_root,
+            state_root,
+            transaction_root,
+            timestamp,
+            n_bits,
+            height,
+            extension_root,
+            autolykos_solution: dummy_autolykos_solution,
+            votes,
+        };
+
+        let x = DlogProverInput::random();
+
+        let (sk, _) = default_miner_secret();
+        let nonce: Vec<u8> = std::iter::repeat(0_u8).take(8).collect();
+        let d = order() / (height + 1);
+        let autolykos_solution = AutolykosSolution {
+            miner_pk: sk.public_key().unwrap().public_key.into(),
+            pow_onetime_pk: Some(x.public_image().h),
+            nonce,
+            pow_distance: Some(d),
+        };
+
+        // Compute header ID
+        let mut id_bytes = header.serialize_without_pow().unwrap();
+        let mut data = Vec::new();
+        let mut w = SigmaByteWriter::new(&mut data, None);
+        autolykos_solution.serialize_bytes(version, &mut w).unwrap();
+        id_bytes.extend(data);
+        let id = BlockId(blake2b256_hash(&id_bytes));
+        header.id = id;
+        header.autolykos_solution = autolykos_solution;
+
+        Some(ErgoFullBlock {
+            header,
+            extension: extension_candidate,
+        })
+    }
+    #[test]
+    fn test_nipopow_level_0_valid() {
+        let popow_algos = NipopowAlgos::default();
+        for b in block_stream(None).take(10) {
+            assert!(popow_algos.max_level_of(&b.header).unwrap() >= 0);
+        }
+    }
+
+    #[test]
+    fn test_nipopow_lowest_common_ancestor_diverging() {
+        let popow_algos = NipopowAlgos::default();
+        for size in [10, 100, 200] {
+            let stream = block_stream(None);
+            let chain_0: Vec<_> = stream.take(size).collect();
+            let branch_point = chain_0[size / 2].clone();
+            let mut chain_1 = chain_0[..(size / 2)].to_vec();
+            chain_1.extend(block_stream(Some(branch_point.clone())).take(size / 2));
+            let chain_0_headers: Vec<_> = chain_0.iter().map(|b| &b.header).collect();
+            let chain_1_headers: Vec<_> = chain_1.iter().map(|b| &b.header).collect();
+            assert_eq!(
+                popow_algos.lowest_common_ancestor(&chain_0_headers, &chain_1_headers),
+                Some(branch_point.header.clone())
+            );
+        }
+    }
+
+    #[test]
+    fn test_nipopow_best_arg_always_equal_for_equal_proofs() {
+        let m = 30;
+        let k = 30;
+        let popow_algos = NipopowAlgos::default();
+
+        let chain_0 = generate_popowheader_chain(100, None);
+        let proof_0 = popow_algos.prove(&chain_0, k, m).unwrap();
+        let chain_1 = generate_popowheader_chain(100, None);
+        let proof_1 = popow_algos.prove(&chain_1, k, m).unwrap();
+
+        assert!(proof_0.has_valid_connections());
+        assert!(proof_1.has_valid_connections());
+        assert_eq!(proof_0.prefix.len(), proof_1.prefix.len());
+
+        let chain_0_headers: Vec<_> = chain_0.iter().map(|p| &p.header).collect();
+        let chain_1_headers: Vec<_> = chain_1.iter().map(|p| &p.header).collect();
+
+        assert_eq!(
+            popow_algos.best_arg(&chain_0_headers, m).unwrap(),
+            popow_algos.best_arg(&chain_1_headers, m).unwrap()
+        );
+    }
+
+    #[test]
+    fn test_nipopow_best_arg_always_greater_for_better_proofs() {
+        let m = 30;
+        let k = 30;
+        let popow_algos = NipopowAlgos::default();
+
+        let chain_0 = generate_popowheader_chain(100, None);
+        let proof_0 = popow_algos.prove(&chain_0, k, m).unwrap();
+        let chain_1 = generate_popowheader_chain(70, None);
+        let proof_1 = popow_algos.prove(&chain_1, k, m).unwrap();
+
+        assert!(proof_0.has_valid_connections());
+        assert!(proof_1.has_valid_connections());
+        assert!(proof_0.prefix.len() > proof_1.prefix.len());
+
+        let chain_0_headers: Vec<_> = chain_0.iter().map(|p| &p.header).collect();
+        let chain_1_headers: Vec<_> = chain_1.iter().map(|p| &p.header).collect();
+
+        assert!(
+            popow_algos.best_arg(&chain_0_headers, m).unwrap()
+                > popow_algos.best_arg(&chain_1_headers, m).unwrap()
+        );
+    }
+
+    #[test]
+    fn test_nipopow_is_better_than_marginally_longer_chain_better() {
+        let m = 30;
+        let k = 30;
+        let popow_algos = NipopowAlgos::default();
+
+        let short_chain = generate_popowheader_chain(1000, None);
+        let branch_point = short_chain[short_chain.len() - 1].clone();
+        let mut long_chain = short_chain.clone();
+        long_chain.extend(std::iter::once(
+            generate_popowheader_chain(2, Some(branch_point))[1].clone(),
+        ));
+        let short_proof = popow_algos.prove(&short_chain, k, m).unwrap();
+        let long_proof = popow_algos.prove(&long_chain, k, m).unwrap();
+        assert!(!short_proof.is_better_than(&long_proof).unwrap());
+    }
+
+    #[test]
+    fn test_nipopow_is_better_than_disconnected_chain_should_not_win() {
+        let m = 50;
+        let k = 1;
+        let size = 100;
+        let popow_algos = NipopowAlgos::default();
+        let chain = generate_popowheader_chain(size, None);
+        let proof = popow_algos.prove(&chain, k, m).unwrap();
+
+        let longer_chain = generate_popowheader_chain(size * 2, None);
+        let longer_proof = popow_algos.prove(&longer_chain, k, m).unwrap();
+
+        let disconnected_proof_prefix: Vec<_> = proof
+            .prefix
+            .clone()
+            .into_iter()
+            .take(proof.prefix.len() / 2)
+            .chain(longer_proof.prefix)
+            .collect();
+        let disconnected_proof = NipopowProof {
+            popow_algos,
+            m,
+            k,
+            prefix: disconnected_proof_prefix,
+            suffix_head: proof.suffix_head.clone(),
+            suffix_tail: proof.suffix_tail.clone(),
+        };
+        assert!(proof.is_better_than(&disconnected_proof).unwrap());
+    }
+
+    #[test]
+    fn test_nipopow_has_valid_connections_ensure_connected_prefix_chain() {
+        let m = 5;
+        let k = 5;
+        for size in [100, 200] {
+            let popow_algos = NipopowAlgos::default();
+            let chain = generate_popowheader_chain(size, None);
+            let proof = popow_algos.prove(&chain, k, m).unwrap();
+            let random_block = generate_popowheader_chain(1, None);
+            let mut disconnected_proof_prefix = proof.prefix.clone();
+            disconnected_proof_prefix[proof.prefix.len() / 2] = random_block[0].clone();
+            let disconnected_proof = NipopowProof {
+                popow_algos,
+                m,
+                k,
+                prefix: disconnected_proof_prefix,
+                suffix_head: proof.suffix_head.clone(),
+                suffix_tail: proof.suffix_tail.clone(),
+            };
+            assert!(proof.has_valid_connections());
+            assert!(!disconnected_proof.has_valid_connections());
+        }
+    }
+
+    #[test]
+    fn test_nipopow_has_valid_connections_ensure_connected_suffix_chain() {
+        let m = 5;
+        let k = 5;
+        for size in [100, 200] {
+            let popow_algos = NipopowAlgos::default();
+            let chain = generate_popowheader_chain(size, None);
+            let proof = popow_algos.prove(&chain, k, m).unwrap();
+            let random_block = generate_popowheader_chain(1, None);
+            let mut disconnected_proof_suffix_tail = proof.suffix_tail.clone();
+            disconnected_proof_suffix_tail[proof.suffix_tail.len() / 2] =
+                random_block[0].header.clone();
+            let disconnected_proof = NipopowProof {
+                popow_algos,
+                m,
+                k,
+                prefix: proof.prefix.clone(),
+                suffix_head: proof.suffix_head.clone(),
+                suffix_tail: disconnected_proof_suffix_tail,
+            };
+            assert!(proof.has_valid_connections());
+            assert!(!disconnected_proof.has_valid_connections());
+        }
+    }
+
+    #[test]
+    fn test_nipopow_has_valid_connections_ensure_prefix_last_and_suffix_head_linked() {
+        let prefix = generate_popowheader_chain(1, None);
+        let suffix = generate_popowheader_chain(1, None);
+        let proof = NipopowProof {
+            popow_algos: NipopowAlgos::default(),
+            m: 0,
+            k: 0,
+            prefix,
+            suffix_head: suffix[0].clone(),
+            suffix_tail: vec![suffix[0].header.clone()],
+        };
+        assert!(!proof.has_valid_connections());
+    }
+}
diff --git a/ergo-chain-generation/src/lib.rs b/ergo-chain-generation/src/lib.rs
new file mode 100644
index 000000000..172a99344
--- /dev/null
+++ b/ergo-chain-generation/src/lib.rs
@@ -0,0 +1,377 @@
+//! Generate Ergo blockchains for simulation and testing
+
+// Coding conventions
+#![forbid(unsafe_code)]
+#![deny(non_upper_case_globals)]
+#![deny(non_camel_case_types)]
+#![deny(non_snake_case)]
+#![deny(unused_mut)]
+#![deny(dead_code)]
+#![deny(unused_imports)]
+#![deny(missing_docs)]
+#![deny(rustdoc::broken_intra_doc_links)]
+#![deny(clippy::wildcard_enum_match_arm)]
+//#![deny(clippy::unwrap_used)]
+#![deny(clippy::expect_used)]
+#![deny(clippy::todo)]
+#![deny(clippy::unimplemented)]
+#![deny(clippy::panic)]
+
+use blake2::{
+    digest::{Update, VariableOutput},
+    VarBlake2b,
+};
+use ergo_lib::ergotree_ir::chain::{
+    block_id::BlockId,
+    digest32::{blake2b256_hash, Digest32},
+    header::Header,
+};
+use ergo_lib::wallet::{ext_secret_key::ExtSecretKey, mnemonic::Mnemonic};
+use ergo_nipopow::NipopowAlgos;
+use num_bigint::{BigInt, Sign};
+
+pub mod chain_generation;
+mod fake_pow_scheme;
+
+/// Ergo block
+#[derive(Clone, Debug)]
+pub struct ErgoFullBlock {
+    pub(crate) header: Header,
+    //block_transactions: BlockTransactions,
+    pub(crate) extension: ExtensionCandidate,
+    //ad_proofs: ProofBytes,
+}
+
+/// 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) -> Vec<BlockId> {
+    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.
+        assert_eq!(bytes.len(), 33);
+        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));
+    }
+    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) {
+    let test_mnemonic =
+        "ozone drill grab fiber curtain grace pudding thank cruise elder eight picnic";
+    let seed = Mnemonic::to_seed(test_mnemonic, "");
+    let default_root_secret = ExtSecretKey::derive_master(seed).unwrap();
+    let bytes = default_root_secret.secret_key_bytes();
+    (
+        default_root_secret,
+        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-lib/Cargo.toml b/ergo-lib/Cargo.toml
index 181683f11..66f952518 100644
--- a/ergo-lib/Cargo.toml
+++ b/ergo-lib/Cargo.toml
@@ -19,6 +19,7 @@ sigma-ser = { version = "^0.3.0", path = "../sigma-ser" }
 sigma-util = { version = "^0.3.0", path = "../sigma-util" }
 ergotree-ir = { version = "^0.14.0", path = "../ergotree-ir", features = ["json"] }
 ergotree-interpreter = { version = "^0.14.0", path = "../ergotree-interpreter" }
+ergo-nipopow = { version = "^0.1", path = "../ergo-nipopow" }
 ergoscript-compiler = { version = "^0.10.0", path = "../ergoscript-compiler" , optional = true}
 ergo-merkle-tree = { version = "0.1.0", path = "../ergo-merkle-tree" }
 indexmap = "1.3.2"
@@ -67,3 +68,4 @@ ergotree-interpreter = { version = "^0.14.0", path = "../ergotree-interpreter",
 sigma-test-util = { version = "^0.3.0", path = "../sigma-test-util" }
 pretty_assertions = "0.7.2"
 bs58 = "0.4.0"
+byteorder = "1"
diff --git a/ergo-lib/src/lib.rs b/ergo-lib/src/lib.rs
index dae532f8a..9a9c595a5 100644
--- a/ergo-lib/src/lib.rs
+++ b/ergo-lib/src/lib.rs
@@ -25,6 +25,7 @@ mod utils;
 pub mod wallet;
 
 pub extern crate ergo_merkle_tree;
+pub extern crate ergo_nipopow;
 /// Re-exported types from dependencies
 #[cfg(feature = "compiler")]
 pub extern crate ergoscript_compiler;
diff --git a/ergo-nipopow/Cargo.toml b/ergo-nipopow/Cargo.toml
index fe8900d74..d11f8c97d 100644
--- a/ergo-nipopow/Cargo.toml
+++ b/ergo-nipopow/Cargo.toml
@@ -14,7 +14,17 @@ exclude = [
 crate-type = ["cdylib", "rlib"]
 
 [dependencies]
+base16 = "0.2.1"
+bounded-integer = { version = "^0.5", features = ["types"] }
+byteorder = "1"
 thiserror = "1"
 derive_more = "0.99"
+ergotree-ir = { version = "^0.14.0", path = "../ergotree-ir", features = ["json"] }
+num-bigint = "0.4.0"
+num-traits = "0.2.14"
+sigma-ser = { version = "^0.3.0", path = "../sigma-ser" }
+sigma-util = { version = "^0.3.0", path = "../sigma-util" }
+serde = { version = "1.0", features = ["derive"] }
+serde_json = { version = "1.0" }
 
 [dev-dependencies]
diff --git a/ergo-nipopow/src/autolykos_pow_scheme.rs b/ergo-nipopow/src/autolykos_pow_scheme.rs
new file mode 100644
index 000000000..61116c573
--- /dev/null
+++ b/ergo-nipopow/src/autolykos_pow_scheme.rs
@@ -0,0 +1,332 @@
+use bounded_integer::{BoundedI32, BoundedU64};
+use derive_more::From;
+use ergotree_ir::chain::header::Header;
+use num_bigint::{BigInt, Sign};
+use sigma_ser::ScorexSerializationError;
+use sigma_util::hash::blake2b256_hash;
+
+/// Autolykos PoW puzzle scheme implementation.
+///
+/// See for reference implmentation - <https://github.com/ergoplatform/ergo/blob/f7b91c0be00531c6d042c10a8855149ca6924373/src/main/scala/org/ergoplatform/mining/AutolykosPowScheme.scala>
+///
+/// Based on k-sum problem, so general idea is to find k numbers in a table of size N, such that
+/// sum of numbers (or a hash of the sum) is less than target value.
+///
+/// See <https://docs.ergoplatform.com/ErgoPow.pdf> for details
+///
+/// CPU Mining process is implemented in inefficient way and should not be used in real environment.
+///
+/// See <https://github.com/ergoplatform/ergo/papers/yellow/pow/ErgoPow.tex> for full description
+#[derive(Debug, Clone)]
+pub struct AutolykosPowScheme {
+    /// Represents the number of elements in one solution. **Important assumption**: `k <= 32`.
+    k: BoundedU64<1, 32>,
+    /// Let `N` denote the initial table size. Then `n` is the value satisfying `N = 2 ^ n`.
+    /// **Important assumption**: `n < 31`.
+    n: BoundedI32<1, 30>,
+}
+
+impl AutolykosPowScheme {
+    /// Get hit for Autolykos header (to test it then against PoW target)
+    pub fn pow_hit(&self, header: &Header) -> Result<BigInt, AutolykosPowSchemeError> {
+        if header.version == 1 {
+            header
+                .autolykos_solution
+                .pow_distance
+                .as_ref()
+                .cloned()
+                .ok_or(AutolykosPowSchemeError::MissingPowDistanceParameter)
+        } else {
+            use byteorder::{BigEndian, WriteBytesExt};
+            // hit for version 2
+            let msg = blake2b256_hash(&header.serialize_without_pow()?).to_vec();
+            let nonce = header.autolykos_solution.nonce.clone();
+            let mut height_bytes = Vec::with_capacity(4);
+            #[allow(clippy::unwrap_used)]
+            height_bytes.write_u32::<BigEndian>(header.height).unwrap();
+
+            let mut concat = msg.clone();
+            concat.extend(&nonce);
+
+            // `N` from autolykos paper
+            let big_n = self.calc_big_n(header.version, header.height);
+            let seed_hash = self.calc_seed_v2(big_n, &msg, &nonce, &height_bytes)?;
+            let indexes = self.gen_indexes(&seed_hash, big_n);
+
+            let f2 = indexes.into_iter().fold(BigInt::from(0u32), |acc, idx| {
+                // This is specific to autolykos v2.
+                let mut concat = vec![];
+                #[allow(clippy::unwrap_used)]
+                concat.write_u32::<BigEndian>(idx).unwrap();
+                concat.extend(&height_bytes);
+                concat.extend(&self.calc_big_m());
+                acc + BigInt::from_bytes_be(Sign::Plus, &blake2b256_hash(&concat)[1..])
+            });
+
+            // sum as byte array is always about 32 bytes
+            #[allow(clippy::unwrap_used)]
+            let array = as_unsigned_byte_array(32, f2).unwrap();
+            Ok(BigInt::from_bytes_be(Sign::Plus, &*blake2b256_hash(&array)))
+        }
+    }
+
+    /// Constant data to be added to hash function to increase its calculation time
+    pub fn calc_big_m(&self) -> Vec<u8> {
+        use byteorder::{BigEndian, WriteBytesExt};
+        (0u64..1024)
+            .flat_map(|x| {
+                let mut bytes = Vec::with_capacity(8);
+                #[allow(clippy::unwrap_used)]
+                bytes.write_u64::<BigEndian>(x).unwrap();
+                bytes
+            })
+            .collect()
+    }
+
+    /// Computes `J` (denoted by `seed` in Ergo implementation) line 4, algorithm 1 of Autolykos v2
+    /// in ErgoPow paper.
+    pub fn calc_seed_v2(
+        &self,
+        big_n: usize,
+        msg: &[u8],
+        nonce: &[u8],
+        header_height_bytes: &[u8],
+    ) -> Result<Box<[u8; 32]>, AutolykosPowSchemeError> {
+        let mut concat: Vec<u8> = vec![];
+        concat.extend(msg);
+        concat.extend(nonce);
+
+        let pre_i8 = BigInt::from_bytes_be(Sign::Plus, &(blake2b256_hash(&concat)[(32 - 8)..]));
+
+        // Note that `N` parameter has an upper bound of 2,147,387,550 which can fit in a `i32` (4
+        // bytes), so the truncation for `i` below is safe.
+        let i =
+            as_unsigned_byte_array(4, pre_i8.modpow(&BigInt::from(1u32), &BigInt::from(big_n)))?;
+
+        let big_m = self.calc_big_m();
+
+        concat = i;
+        concat.extend(header_height_bytes);
+        concat.extend(&big_m);
+        let f = blake2b256_hash(&concat);
+
+        concat = f[1..].to_vec();
+        concat.extend(msg);
+        concat.extend(nonce);
+        Ok(blake2b256_hash(&concat))
+    }
+
+    /// Returns a list of size `k` with numbers in [0,`N`)
+    pub fn gen_indexes(&self, seed_hash: &[u8; 32], big_n: usize) -> Vec<u32> {
+        let mut res = vec![];
+        let mut extended_hash: Vec<u8> = seed_hash.to_vec();
+        extended_hash.extend(&seed_hash[..3]);
+        for i in 0..self.k.get() {
+            let i = i as usize;
+            res.push(
+                BigInt::from_bytes_be(Sign::Plus, &extended_hash[i..(i + 4)])
+                    .modpow(&BigInt::from(1u32), &BigInt::from(big_n))
+                    .to_u32_digits()
+                    .1[0],
+            );
+        }
+        res
+    }
+
+    /// Calculates table size (N value) for a given height (moment of time)
+    pub fn calc_big_n(&self, header_version: u8, header_height: u32) -> usize {
+        // Number of elements in a table to find k-sum problem solution on top of
+        let n_base = 2i32.pow(self.n.get() as u32) as usize;
+        if header_version == 1 {
+            n_base
+        } else {
+            // On this height, the table (`N` value) will stop to grow
+            let n_increasement_height_max = 4198400;
+            let height = usize::min(n_increasement_height_max, header_height as usize);
+
+            // Initial height since which table (`N` value) starting to increase by 5% per `IncreasePeriodForN` blocks
+            let increase_start = 600 * 1024;
+            if height < increase_start {
+                n_base
+            } else {
+                // Table size (`N`) increased every 50 * 1024 blocks
+                let increase_period_for_big_n = 50 * 1024;
+                let iters_number = (height - increase_start) / increase_period_for_big_n + 1;
+                (1..=iters_number).fold(n_base, |acc, _| acc / 100 * 105)
+            }
+        }
+    }
+}
+
+impl Default for AutolykosPowScheme {
+    fn default() -> Self {
+        // The following paramter values are mandated by Ergo-node Autolykos implementation.
+        #[allow(clippy::unwrap_used)]
+        AutolykosPowScheme {
+            k: BoundedU64::new(32).unwrap(),
+            n: BoundedI32::new(26).unwrap(),
+        }
+    }
+}
+
+/// Port of BouncyCastle's BigIntegers::asUnsignedByteArray method.
+fn as_unsigned_byte_array(
+    length: usize,
+    big_int: BigInt,
+) -> Result<Vec<u8>, AutolykosPowSchemeError> {
+    let bytes = big_int.to_signed_bytes_be();
+    if bytes.len() == length {
+        return Ok(bytes);
+    }
+
+    let start = if bytes[0] == 0 { 1 } else { 0 };
+    let count = bytes.len() - start;
+    if count > length {
+        return Err(AutolykosPowSchemeError::BigIntToFixedByteArrayError);
+    }
+    let mut res: Vec<_> = std::iter::repeat(0).take(length).collect();
+    res[(length - count)..].copy_from_slice(&bytes[start..]);
+    Ok(res)
+}
+
+#[derive(PartialEq, Debug, Clone, From)]
+pub enum AutolykosPowSchemeError {
+    /// Scorex-serialization error
+    ScorexSerializationError(ScorexSerializationError),
+    /// Error occurring when trying to convert a `BigInt` into a fixed-length byte-array.
+    BigIntToFixedByteArrayError,
+    /// Occurs when `Header.version == 1` and the `pow_distance` parameter is None.
+    MissingPowDistanceParameter,
+}
+
+/// The following tests are taken from <https://github.com/ergoplatform/ergo/blob/f7b91c0be00531c6d042c10a8855149ca6924373/src/test/scala/org/ergoplatform/mining/AutolykosPowSchemeSpec.scala#L43-L130>
+#[allow(clippy::unwrap_used)]
+#[cfg(test)]
+mod tests {
+    use ergotree_ir::{serialization::SigmaSerializable, sigma_protocol::dlog_group::order};
+
+    use crate::nipopow_algos::decode_compact_bits;
+
+    use super::*;
+
+    #[test]
+    fn test_calc_big_n() {
+        let pow = AutolykosPowScheme::default();
+        let n_base = 2i32.pow(pow.n.get() as u32) as usize;
+
+        // autolykos v1
+        assert_eq!(pow.calc_big_n(1, 700000), n_base);
+        assert_eq!(pow.calc_big_n(1, 100000), n_base);
+        assert_eq!(pow.calc_big_n(1, 70000000), n_base);
+
+        // autolykos v2
+        assert_eq!(pow.calc_big_n(2, 500000), n_base);
+        assert_eq!(pow.calc_big_n(2, 600000), n_base);
+        assert_eq!(pow.calc_big_n(2, 600 * 1024), 70464240);
+        assert_eq!(pow.calc_big_n(2, 650 * 1024), 73987410);
+        assert_eq!(pow.calc_big_n(2, 700000), 73987410);
+        assert_eq!(pow.calc_big_n(2, 788400), 81571035); // 3 years
+        assert_eq!(pow.calc_big_n(2, 1051200), 104107290); // 4 years
+        assert_eq!(pow.calc_big_n(2, 4198400), 2143944600); // max height
+        assert_eq!(pow.calc_big_n(2, 41984000), 2143944600);
+    }
+
+    #[test]
+    fn test_first_increase_in_big_n() {
+        // Test vectors for first increase in N value (height 614,400)
+        let json = r#"
+          {
+            "extensionId" : "00cce45975d87414e8bdd8146bc88815be59cd9fe37a125b5021101e05675a18",
+            "difficulty" : "16384",
+            "votes" : "000000",
+            "timestamp" : 4928911477310178288,
+            "size" : 223,
+            "stateRoot" : "5c8c00b8403d3701557181c8df800001b6d5009e2201c6ff807d71808c00019780",
+            "height" : 614400,
+            "nBits" : 37748736,
+            "version" : 2,
+            "id" : "5603a937ec1988220fc44fb5022fb82d5565b961f005ebb55d85bd5a9e6f801f",
+            "adProofsRoot" : "5d3f80dcff7f5e7f59007294c180808d0158d1ff6ba10000f901c7f0ef87dcff",
+            "transactionsRoot" : "f17fffacb6ff7f7f1180d2ff7f1e24ffffe1ff937f807f0797b9ff6ebdae007e",
+            "extensionHash" : "1480887f80007f4b01cf7f013ff1ffff564a0000b9a54f00770e807f41ff88c0",
+            "powSolutions" : {
+              "pk" : "03bedaee069ff4829500b3c07c4d5fe6b3ea3d3bf76c5c28c1d4dcdb1bed0ade0c",
+              "n" : "0000000000003105"
+             },
+            "adProofsId" : "dec129290a763f4de41f04e87e2b661dd59758af6bdd00dd51f5d97c3a8cb9b5",
+            "transactionsId" : "eba1dd82cf51147232e09c1f72b37c554c30f63274d5093bff36849a83472a42",
+            "parentId" : "ac2101807f0000ca01ff0119db227f202201007f62000177a080005d440896d0"
+          } 
+          "#;
+
+        let header: Header = serde_json::from_str(json).unwrap();
+        assert_eq!(header.height, 614400);
+
+        let msg = base16::encode_lower(&*blake2b256_hash(&header.serialize_without_pow().unwrap()));
+        assert_eq!(
+            msg,
+            "548c3e602a8f36f8f2738f5f643b02425038044d98543a51cabaa9785e7e864f"
+        );
+
+        let pow = AutolykosPowScheme::default();
+        assert_eq!(pow.calc_big_n(header.version, header.height), 70464240);
+
+        // Vector obtained from a miner dev
+        let hit = pow.pow_hit(&header).unwrap();
+        assert_eq!(
+            hit,
+            BigInt::from_signed_bytes_be(
+                &base16::decode("0002fcb113fe65e5754959872dfdbffea0489bf830beb4961ddc0e9e66a1412a")
+                    .unwrap()
+            )
+        );
+
+        // Check decoded header.nBits
+        let decoded = decode_compact_bits(header.n_bits);
+
+        // Target `b` from encoded difficulty `nBits`
+        let target_b = order() / decoded;
+        assert_eq!(
+            target_b,
+            BigInt::parse_bytes(
+                b"7067388259113537318333190002971674063283542741642755394446115914399301849",
+                10
+            )
+            .unwrap()
+        );
+
+        assert_eq!(
+            base16::encode_lower(
+                &header
+                    .autolykos_solution
+                    .miner_pk
+                    .sigma_serialize_bytes()
+                    .unwrap()
+            ),
+            "03bedaee069ff4829500b3c07c4d5fe6b3ea3d3bf76c5c28c1d4dcdb1bed0ade0c"
+        );
+
+        assert_eq!(
+            base16::encode_lower(&header.autolykos_solution.nonce),
+            "0000000000003105"
+        );
+
+        // Check that header is valid
+        assert!(hit < target_b);
+    }
+
+    #[test]
+    fn test_invalid_header() {
+        let json = "{\"extensionId\":\"277907e4e5e42f27e928e6101cc4fec173bee5d7728794b73d7448c339c380e5\",\"difficulty\":\"1325481984\",\"votes\":\"000000\",\"timestamp\":1611225263165,\"size\":219,\"stateRoot\":\"c0d0b5eafd07b22487dac66628669c42a242b90bef3e1fcdc76d83140d58b6bc0e\",\"height\":2870,\"nBits\":72286528,\"version\":2,\"id\":\"5b0ce6711de6b926f60b67040cc4512804517785df375d063f1bf1d75588af3a\",\"adProofsRoot\":\"49453875a43035c7640dee2f905efe06128b00d41acd2c8df13691576d4fd85c\",\"transactionsRoot\":\"770cbb6e18673ed025d386487f15d3252115d9a6f6c9b947cf3d04731dd6ab75\",\"extensionHash\":\"9bc7d54583c5d44bb62a7be0473cd78d601822a626afc13b636f2cbff0d87faf\",\"powSolutions\":{\"pk\":\"0288114b0586efea9f86e4587f2071bc1c85fb77e15eba96b2769733e0daf57903\",\"w\":\"0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798\",\"n\":\"000100000580a91b\",\"d\":0},\"adProofsId\":\"4fc36d59bf26a672e01fbfde1445bd66f50e0f540f24102e1e27d0be1a99dfbf\",\"transactionsId\":\"d196ef8a7ef582ab1fdab4ef807715183705301c6ae2ff0dcbe8f1d577ba081f\",\"parentId\":\"ab19e6c7a4062979dddb534df83f236d1b949c7cef18bcf434a67e87c593eef9\"}";
+        let header: Header = serde_json::from_str(json).unwrap();
+        let pow = AutolykosPowScheme::default();
+        // Check decoded header.nBits
+        let decoded = decode_compact_bits(header.n_bits);
+
+        // Target `b` from encoded difficulty `nBits`
+        let target_b = order() / decoded;
+        let hit = pow.pow_hit(&header).unwrap();
+
+        assert!(hit >= target_b);
+    }
+}
diff --git a/ergo-nipopow/src/lib.rs b/ergo-nipopow/src/lib.rs
index bf1446657..74eba0d43 100644
--- a/ergo-nipopow/src/lib.rs
+++ b/ergo-nipopow/src/lib.rs
@@ -1,5 +1,5 @@
 //! Ergo NiPoPoW implementation
-//! See FC 20 (published) version https://fc20.ifca.ai/preproceedings/74.pdf
+//! See FC 20 (published) version <https://fc20.ifca.ai/preproceedings/74.pdf>
 
 // Coding conventions
 #![forbid(unsafe_code)]
@@ -17,3 +17,11 @@
 #![deny(clippy::todo)]
 #![deny(clippy::unimplemented)]
 #![deny(clippy::panic)]
+mod autolykos_pow_scheme;
+mod nipopow_algos;
+mod nipopow_proof;
+mod nipopow_verifier;
+
+pub use nipopow_algos::{decode_compact_bits, NipopowAlgos};
+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
new file mode 100644
index 000000000..522337742
--- /dev/null
+++ b/ergo-nipopow/src/nipopow_algos.rs
@@ -0,0 +1,303 @@
+use ergotree_ir::{chain::header::Header, sigma_protocol::dlog_group::order};
+use num_bigint::BigInt;
+use num_traits::ToPrimitive;
+
+use crate::{
+    autolykos_pow_scheme::{AutolykosPowScheme, AutolykosPowSchemeError},
+    nipopow_proof::PoPowHeader,
+    NipopowProof, NipopowProofError,
+};
+
+/// A set of utilities for working with NiPoPoW protocol.
+///
+/// Based on papers:
+///
+/// [`KMZ17`]: https://fc20.ifca.ai/preproceedings/74.pdf
+///
+/// [`KLS16`]: http://fc16.ifca.ai/bitcoin/papers/KLS16.pdf
+///
+/// Please note that for KMZ17 we're using the version published @ Financial Cryptography 2020,
+/// which is different from previously published versions on IACR eprint.
+#[derive(Default, Debug, Clone)]
+pub struct NipopowAlgos {
+    /// The proof-of-work scheme
+    pub pow_scheme: AutolykosPowScheme,
+}
+
+impl NipopowAlgos {
+    /// Computes best score of a given chain.
+    /// The score value depends on number of µ-superblocks in the given chain.
+    ///
+    /// see [`KMZ17`], Algorithm 4
+    ///
+    /// [`KMZ17`]:
+    /// "To find the best argument of a proof π given b, best-arg_m collects all the μ
+    /// indices which point to superblock levels that contain valid arguments after block b.
+    /// Argument validity requires that there are at least m μ-superblocks following block b,
+    /// which is captured by the comparison|π↑μ{b:}|≥m. 0 is always considered a valid level,
+    /// regardless of how many blocks are present there. These level indices are collected into set M.
+    /// For each of these levels, the score of their respective argument is evaluated by weighting the
+    /// number of blocks by the level as 2μ|π↑μ{b:}|. The highest possible score across all levels is returned."
+    ///
+    /// function best-arg_m(π, b)
+    /// M←{μ:|π↑μ{b:}|≥m}∪{0}
+    /// return max_{μ∈M} {2μ·|π↑μ{b:}|}
+    /// end function
+    ///
+    /// [`KMZ17`]: https://fc20.ifca.ai/preproceedings/74.pdf
+    pub fn best_arg(&self, chain: &[&Header], m: u32) -> Result<usize, AutolykosPowSchemeError> {
+        // Little helper struct for loop below
+        struct Acc {
+            level: u32,
+            acc: Vec<(u32, usize)>,
+        }
+        let mut res = Acc {
+            level: 1,
+            acc: vec![(0, chain.len())],
+        };
+        let acc = loop {
+            let mut args = vec![];
+            for h in chain {
+                if (self.max_level_of(h)? as u32) >= res.level {
+                    args.push(h);
+                }
+            }
+            if args.len() >= (m as usize) {
+                res.acc.insert(0, (res.level, args.len()));
+                res = Acc {
+                    level: res.level + 1,
+                    acc: res.acc,
+                };
+            } else {
+                break res.acc;
+            }
+        };
+        #[allow(clippy::unwrap_used)]
+        Ok(acc
+            .into_iter()
+            .map(|(level, size)| {
+                // 2^µ * |C↑µ|
+                2usize.pow(level) * size
+            })
+            .max()
+            .unwrap())
+    }
+
+    /// Computes max level (μ) of the given header, such that μ = log(T) − log(id(B))
+    pub fn max_level_of(&self, header: &Header) -> Result<i32, AutolykosPowSchemeError> {
+        let genesis_header = header.height == 1;
+        if !genesis_header {
+            // Order of the secp256k1 elliptic curve
+            let order = order();
+            #[allow(clippy::unwrap_used)]
+            let required_target = (order / decode_compact_bits(header.n_bits))
+                .to_f64()
+                .unwrap();
+            #[allow(clippy::unwrap_used)]
+            let real_target = self.pow_scheme.pow_hit(header)?.to_f64().unwrap();
+            let level = required_target.log2() - real_target.log2();
+            Ok(level as i32)
+        } else {
+            Ok(i32::MAX)
+        }
+    }
+
+    /// Finds the last common header (branching point) between `left_chain` and `right_chain`.
+    pub fn lowest_common_ancestor(
+        &self,
+        left_chain: &[&Header],
+        right_chain: &[&Header],
+    ) -> Option<Header> {
+        if let Some(head_left) = left_chain.first() {
+            if let Some(head_right) = right_chain.first() {
+                if *head_left != *head_right {
+                    return None;
+                }
+            }
+        }
+        let mut common = vec![];
+        let mut right_ix_start = 0;
+        for left_header in left_chain {
+            let start_ix = right_ix_start;
+            for (i, right_header) in right_chain.iter().enumerate().skip(start_ix) {
+                if **left_header == **right_header {
+                    right_ix_start = i + 1;
+                    common.push(*left_header);
+                }
+            }
+        }
+        common.last().cloned().cloned()
+    }
+
+    /// Computes NiPoPow proof for the given `chain` according to given `params`.
+    pub fn prove(
+        &self,
+        chain: &[PoPowHeader],
+        k: u32,
+        m: u32,
+    ) -> Result<NipopowProof, NipopowProofError> {
+        if k == 0 {
+            return Err(NipopowProofError::ZeroKParameter);
+        }
+        if chain.len() < ((k + m) as usize) {
+            return Err(NipopowProofError::ChainTooShort);
+        }
+        if chain[0].header.height != 1 {
+            return Err(NipopowProofError::NonAnchoredChain);
+        }
+
+        let suffix = chain[(chain.len() - (k as usize))..].to_vec();
+        let suffix_head = suffix[0].clone();
+        let suffix_tail: Vec<Header> = suffix[1..].iter().map(|p| p.header.clone()).collect();
+        #[allow(clippy::unwrap_used)]
+        let max_level: i32 = if chain.len() > (k as usize) {
+            (chain[..(chain.len() - (k as usize))]
+                .last()
+                .unwrap()
+                .interlinks
+                .len()
+                - 1) as i32
+        } else {
+            return Err(NipopowProofError::ChainTooShort);
+        };
+
+        // Here is non-recursive implementation of the scala `provePrefix` function
+        let mut prefix = vec![];
+        let mut stack = vec![(chain[0].clone(), max_level)];
+        while let Some((anchoring_point, level)) = stack.pop() {
+            if level >= 0 {
+                // C[:−k]{B:}↑µ
+                let mut sub_chain = vec![];
+
+                for p in &chain[..(chain.len() - (k as usize))] {
+                    let max_level = self.max_level_of(&p.header)?;
+                    if max_level >= level && p.header.height >= anchoring_point.header.height {
+                        sub_chain.push(p.clone());
+                    }
+                }
+
+                if (m as usize) < sub_chain.len() {
+                    stack.push((sub_chain[sub_chain.len() - (m as usize)].clone(), level - 1));
+                } else {
+                    stack.push((anchoring_point, level - 1));
+                }
+                for pph in sub_chain {
+                    if !prefix.contains(&pph) {
+                        prefix.push(pph);
+                    }
+                }
+            }
+        }
+        prefix.sort_by(|a, b| a.header.height.cmp(&b.header.height));
+        NipopowProof::new(m, k, prefix, suffix_head, suffix_tail)
+    }
+}
+
+/// The "compact" format is an encoding of a whole number `N` using an unsigned 32 bit number.
+/// This number encodes a base-256 scientific notation representation of `N` (similar to a floating
+/// point format):
+///  - The most significant 8 bits represent the number of bytes necessary to represent `N` in
+///    two's-complement form; denote it by `exponent`.
+///  - The lower 23 bits are the mantissa(significand).
+///  - Bit number 24 (0x800000) represents the sign of N.
+///
+/// There are 2 cases to consider:
+///  - If `exponent >= 3` then `N` is represented by
+///      `(-1^sign) * mantissa * 256^(exponent-3)`
+///    E.g. suppose the compact form is given in hex-format by `0x04123456`. Mantissa is `0x123456`
+///    and `exponent == 4`. So `N == 0x123456 * 265^1`. Now note that we need exactly 4 bytes to
+///    represent `N`; 3 bytes for the mantissa and 1 byte for the rest. In base-256:
+///      `N == B(0x12)B(0x34)B(0x56)0`
+///    where `B(y)` denotes the base-256 representation of a hex-number `y` (note how each base-256
+///    digit is represented by a single-byte).
+///  - If `exponent < 3` then `N` is represented by the `exponent`-most-significant-bytes of the
+///    mantissa. E.g. suppose the compact form is given in hex-format by `0x01003456`. Noting that
+///    each hex-digit is represented by 4-bits, our `exponent == 0x01` which is `1` base-10.  The
+///    mantissa is represented by `0x003456` and it's most signficant byte is `0x00`. Therefore
+///    `N == 0`.
+///
+/// Satoshi's original implementation used BN_bn2mpi() and BN_mpi2bn(). MPI uses the most
+/// significant bit of the first byte as sign. Thus 0x1234560000 is compact 0x05123456 and
+/// 0xc0de000000 is compact 0x0600c0de. Compact 0x05c0de00 would be -0x40de000000.
+///
+/// Bitcoin only uses this "compact" format for encoding difficulty targets, which are unsigned
+/// 256bit quantities.  Thus, all the complexities of the sign bit and using base 256 are probably
+/// an implementation accident.
+pub fn decode_compact_bits(n_bits: u64) -> BigInt {
+    let compact = n_bits as i64;
+    let size = ((compact >> 24) as i32) & 0xFF;
+    if size == 0 {
+        return BigInt::from(0);
+    }
+    let mut buf: Vec<i8> = std::iter::repeat(0).take(size as usize).collect();
+    if size >= 1 {
+        // Store the first byte of the mantissa
+        buf[0] = (((compact >> 16) as i32) & 0xFF) as i8;
+    }
+    if size >= 2 {
+        buf[1] = (((compact >> 8) as i32) & 0xFF) as i8;
+    }
+    if size >= 3 {
+        buf[2] = ((compact as i32) & 0xFF) as i8;
+    }
+
+    let is_negative = (buf[0] as i32) & 0x80 == 0x80;
+    if is_negative {
+        buf[0] &= 0x7f;
+        let buf: Vec<_> = buf.into_iter().map(|x| x as u8).collect();
+        -BigInt::from_signed_bytes_be(&buf)
+    } else {
+        let buf: Vec<_> = buf.into_iter().map(|x| x as u8).collect();
+        BigInt::from_signed_bytes_be(&buf)
+    }
+}
+
+#[allow(clippy::unwrap_used)]
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use num_bigint::ToBigInt;
+
+    #[test]
+    fn test_decode_n_bits() {
+        // Following example taken from https://btcinformation.org/en/developer-reference#target-nbits
+        let n_bits = 0x181bc330;
+        assert_eq!(
+            decode_compact_bits(n_bits),
+            BigInt::parse_bytes(b"1bc330000000000000000000000000000000000000000000", 16).unwrap()
+        );
+
+        let n_bits = 0x01003456;
+        assert_eq!(
+            decode_compact_bits(n_bits),
+            ToBigInt::to_bigint(&0x00).unwrap()
+        );
+
+        let n_bits = 0x01123456;
+        assert_eq!(
+            decode_compact_bits(n_bits),
+            ToBigInt::to_bigint(&0x12).unwrap()
+        );
+
+        let n_bits = 0x04923456;
+        assert_eq!(
+            decode_compact_bits(n_bits),
+            ToBigInt::to_bigint(&-0x12345600).unwrap()
+        );
+
+        let n_bits = 0x04123456;
+        assert_eq!(
+            decode_compact_bits(n_bits),
+            ToBigInt::to_bigint(&0x12345600).unwrap()
+        );
+
+        let n_bits = 0x05123456;
+        assert_eq!(
+            decode_compact_bits(n_bits),
+            ToBigInt::to_bigint(&0x1234560000i64).unwrap()
+        );
+
+        let n_bits = 16842752;
+        assert_eq!(decode_compact_bits(n_bits), BigInt::from(1_u8));
+    }
+}
diff --git a/ergo-nipopow/src/nipopow_proof.rs b/ergo-nipopow/src/nipopow_proof.rs
new file mode 100644
index 000000000..917b633e4
--- /dev/null
+++ b/ergo-nipopow/src/nipopow_proof.rs
@@ -0,0 +1,215 @@
+use derive_more::From;
+use ergotree_ir::chain::{block_id::BlockId, header::Header};
+use serde::{Deserialize, Serialize};
+use sigma_ser::{
+    vlq_encode::{ReadSigmaVlqExt, WriteSigmaVlqExt},
+    ScorexParsingError, ScorexSerializable, ScorexSerializeResult,
+};
+
+use crate::{
+    autolykos_pow_scheme::{self},
+    nipopow_algos::NipopowAlgos,
+};
+
+#[derive(Serialize, Deserialize, Debug, Clone)]
+/// A structure representing NiPoPow proof as a persistent modifier.
+pub struct NipopowProof {
+    /// Algos
+    #[serde(skip_serializing, skip_deserializing)]
+    pub popow_algos: NipopowAlgos,
+    /// Security parameter (min μ-level superchain length)
+    #[serde(rename = "m")]
+    pub m: u32,
+    /// Security parameter (min suffix length, >= 1)
+    #[serde(rename = "k")]
+    pub k: u32,
+    /// Proof prefix headers
+    #[serde(rename = "prefix")]
+    pub prefix: Vec<PoPowHeader>,
+    /// First header of the suffix
+    #[serde(rename = "suffixHead")]
+    pub suffix_head: PoPowHeader,
+    /// Tail of the proof suffix headers
+    #[serde(rename = "suffixTail")]
+    pub suffix_tail: Vec<Header>,
+}
+
+impl NipopowProof {
+    /// Create new proof instance
+    pub fn new(
+        m: u32,
+        k: u32,
+        prefix: Vec<PoPowHeader>,
+        suffix_head: PoPowHeader,
+        suffix_tail: Vec<Header>,
+    ) -> Result<NipopowProof, NipopowProofError> {
+        if k >= 1 {
+            Ok(NipopowProof {
+                popow_algos: NipopowAlgos::default(),
+                m,
+                k,
+                prefix,
+                suffix_head,
+                suffix_tail,
+            })
+        } else {
+            Err(NipopowProofError::ZeroKParameter)
+        }
+    }
+
+    /// Implementation of the ≥ algorithm from [`KMZ17`], see Algorithm 4
+    ///
+    /// [`KMZ17`]: https://fc20.ifca.ai/preproceedings/74.pdf
+    pub fn is_better_than(&self, that: &NipopowProof) -> Result<bool, NipopowProofError> {
+        if self.is_valid() && that.is_valid() {
+            if let Some(lca) = self.popow_algos.lowest_common_ancestor(
+                &self.headers_chain().collect::<Vec<_>>(),
+                &that.headers_chain().collect::<Vec<_>>(),
+            ) {
+                let self_headers = self
+                    .headers_chain()
+                    .filter(|h| h.height > lca.height)
+                    .collect::<Vec<_>>();
+                let that_headers = that
+                    .headers_chain()
+                    .filter(|h| h.height > lca.height)
+                    .collect::<Vec<_>>();
+                Ok(self.popow_algos.best_arg(&self_headers, self.m)?
+                    > self.popow_algos.best_arg(&that_headers, self.m)?)
+            } else {
+                Ok(false)
+            }
+        } else {
+            Ok(self.is_valid())
+        }
+    }
+
+    fn is_valid(&self) -> bool {
+        self.has_valid_connections() && self.has_valid_heights()
+    }
+
+    /// Checks the connections of the blocks in the proof. Adjacent blocks should be linked either
+    /// via interlink or parent block id. Returns true if all adjacent blocks are correctly
+    /// connected.
+    pub fn has_valid_connections(&self) -> bool {
+        self.prefix
+            .iter()
+            .zip(
+                self.prefix
+                    .iter()
+                    .skip(1)
+                    .chain(std::iter::once(&self.suffix_head)),
+            )
+            .all(|(prev, next)| {
+                // Note that blocks with level 0 do not appear at all within interlinks, which is
+                // why we need to check the parent block id as well.
+                next.interlinks.contains(&prev.header.id) || next.header.parent_id == prev.header.id
+            })
+            && std::iter::once(&self.suffix_head.header)
+                .chain(self.suffix_tail.iter())
+                .zip(self.suffix_tail.iter())
+                .all(|(prev, next)| next.parent_id == prev.id)
+    }
+
+    /// Checks if the heights of the header-chain provided are consistent, meaning that for any two
+    /// blocks b1 and b2, if b1 precedes b2 then b1's height should be smaller. Return true if the
+    /// heights of the header-chain are consistent
+    fn has_valid_heights(&self) -> bool {
+        self.headers_chain()
+            .zip(self.headers_chain().skip(1))
+            .all(|(prev, next)| prev.height < next.height)
+    }
+
+    /// Returns an iterator representing a chain of `Headers` from `self.prefix`, to
+    /// `self.suffix_head` and `self.suffix_tail`.
+    pub(crate) fn headers_chain(&self) -> impl Iterator<Item = &Header> {
+        self.prefix
+            .iter()
+            .map(|p| &p.header)
+            .chain(std::iter::once(&self.suffix_head.header).chain(self.suffix_tail.iter()))
+    }
+}
+
+impl ScorexSerializable for NipopowProof {
+    fn scorex_serialize<W: WriteSigmaVlqExt>(&self, w: &mut W) -> ScorexSerializeResult {
+        w.put_u32(self.m)?;
+        w.put_u32(self.k)?;
+        w.put_u32(self.prefix.len() as u32)?;
+        for p in &self.prefix {
+            let prefix_num_bytes = p.scorex_serialize_bytes()?.len();
+            w.put_u32(prefix_num_bytes as u32)?;
+            p.scorex_serialize(w)?;
+        }
+        let suffix_head_num_bytes = self.suffix_head.scorex_serialize_bytes()?.len();
+        w.put_u32(suffix_head_num_bytes as u32)?;
+        self.suffix_head.scorex_serialize(w)?;
+        w.put_u32(self.suffix_tail.len() as u32)?;
+        for h in &self.suffix_tail {
+            let header_num_bytes = h.scorex_serialize_bytes()?.len();
+            w.put_u32(header_num_bytes as u32)?;
+            h.scorex_serialize(w)?;
+        }
+        Ok(())
+    }
+
+    fn scorex_parse<R: ReadSigmaVlqExt>(r: &mut R) -> Result<Self, ScorexParsingError> {
+        let m = r.get_u32()?;
+        let k = r.get_u32()?;
+        let num_prefixes = r.get_u32()? as usize;
+        let mut prefix = Vec::with_capacity(num_prefixes);
+        for _ in 0..num_prefixes {
+            let _size = r.get_u32()?;
+            prefix.push(PoPowHeader::scorex_parse(r)?);
+        }
+        let _suffix_head_size = r.get_u32()?;
+        let suffix_head = PoPowHeader::scorex_parse(r)?;
+        let num_suffix_tail = r.get_u32()? as usize;
+        let mut suffix_tail = Vec::with_capacity(num_suffix_tail);
+        for _ in 0..num_suffix_tail {
+            let _size = r.get_u32();
+            suffix_tail.push(Header::scorex_parse(r)?);
+        }
+        Ok(NipopowProof {
+            popow_algos: NipopowAlgos::default(),
+            m,
+            k,
+            prefix,
+            suffix_head,
+            suffix_tail,
+        })
+    }
+}
+
+/// `NipopowProof` errors
+#[derive(PartialEq, Debug, Clone, From)]
+pub enum NipopowProofError {
+    /// Errors from `AutolykosPowScheme`
+    AutolykosPowSchemeError(autolykos_pow_scheme::AutolykosPowSchemeError),
+    /// `k` parameter == 0. Must be >= 1.
+    ZeroKParameter,
+    /// Can not prove non-anchored (first block is non-Genesis) chain
+    NonAnchoredChain,
+    /// Chain must be of length `>= k + m`
+    ChainTooShort,
+}
+
+#[derive(Serialize, Deserialize, Debug, Clone, PartialEq, Eq)]
+/// Stub type until issue #489 is closed.
+pub struct PoPowHeader {
+    /// The block header
+    pub header: Header,
+    /// Interlinks are stored in reverse order: first element is always genesis header, then level
+    /// of lowest target met etc
+    pub interlinks: Vec<BlockId>,
+}
+
+#[allow(clippy::todo)]
+impl ScorexSerializable for PoPowHeader {
+    fn scorex_serialize<W: WriteSigmaVlqExt>(&self, _w: &mut W) -> ScorexSerializeResult {
+        todo!()
+    }
+
+    fn scorex_parse<R: ReadSigmaVlqExt>(_r: &mut R) -> Result<Self, ScorexParsingError> {
+        todo!()
+    }
+}
diff --git a/ergo-nipopow/src/nipopow_verifier.rs b/ergo-nipopow/src/nipopow_verifier.rs
new file mode 100644
index 000000000..581728972
--- /dev/null
+++ b/ergo-nipopow/src/nipopow_verifier.rs
@@ -0,0 +1,44 @@
+use ergotree_ir::chain::{block_id::BlockId, header::Header};
+
+use crate::nipopow_proof::{NipopowProof, NipopowProofError};
+
+/// A verifier for PoPoW proofs. During its lifetime, it processes many proofs with the aim of
+/// deducing at any given point what is the best (sub)chain rooted at the specified genesis.
+#[derive(Debug)]
+pub struct NipopowVerifier {
+    best_proof: Option<NipopowProof>,
+    /// `BlockId` of the genesis block.
+    genesis_block_id: BlockId,
+}
+
+impl NipopowVerifier {
+    /// Create new instance
+    pub fn new(genesis_block_id: BlockId) -> Self {
+        NipopowVerifier {
+            best_proof: None,
+            genesis_block_id,
+        }
+    }
+
+    /// Returns chain of `Header`s from the best proof.
+    pub fn best_chain(&self) -> Vec<Header> {
+        self.best_proof
+            .as_ref()
+            .map_or_else(Vec::new, |p| p.headers_chain().cloned().collect())
+    }
+
+    /// Process given proof
+    pub fn process(&mut self, new_proof: NipopowProof) -> Result<(), NipopowProofError> {
+        let h = new_proof.headers_chain().next();
+        if let Some(h) = h {
+            if h.id == self.genesis_block_id {
+                if let Some(p) = &self.best_proof {
+                    if new_proof.is_better_than(p)? {
+                        self.best_proof = Some(new_proof);
+                    }
+                }
+            }
+        }
+        Ok(())
+    }
+}
diff --git a/ergotree-interpreter/src/eval/sheader.rs b/ergotree-interpreter/src/eval/sheader.rs
index 126d19edc..206ef488f 100644
--- a/ergotree-interpreter/src/eval/sheader.rs
+++ b/ergotree-interpreter/src/eval/sheader.rs
@@ -2,7 +2,10 @@
 
 use std::convert::TryInto;
 
-use ergotree_ir::{bigint256::BigInt256, chain::header::Header, mir::constant::TryExtractInto};
+use ergotree_ir::{
+    bigint256::BigInt256, chain::header::Header, mir::constant::TryExtractInto,
+    sigma_protocol::dlog_group::EcPoint,
+};
 
 use super::{EvalError, EvalFn};
 
@@ -58,22 +61,31 @@ pub(crate) static HEIGHT_EVAL_FN: EvalFn = |_env, _ctx, obj, _args| {
 
 pub(crate) static MINER_PK_EVAL_FN: EvalFn = |_env, _ctx, obj, _args| {
     let header = obj.try_extract_into::<Header>()?;
-    Ok(header.miner_pk.into())
+    Ok(header.autolykos_solution.miner_pk.into())
 };
 
 pub(crate) static POW_ONETIME_PK_EVAL_FN: EvalFn = |_env, _ctx, obj, _args| {
     let header = obj.try_extract_into::<Header>()?;
-    Ok(header.pow_onetime_pk.into())
+    Ok(header
+        .autolykos_solution
+        .pow_onetime_pk
+        .unwrap_or_else(|| Box::new(EcPoint::default()))
+        .into())
 };
 
 pub(crate) static POW_NONCE_EVAL_FN: EvalFn = |_env, _ctx, obj, _args| {
     let header = obj.try_extract_into::<Header>()?;
-    Ok(header.nonce.into())
+    Ok(header.autolykos_solution.nonce.into())
 };
 
 pub(crate) static POW_DISTANCE_EVAL_FN: EvalFn = |_env, _ctx, obj, _args| {
     let header = obj.try_extract_into::<Header>()?;
-    let pow_distance: BigInt256 = header.pow_distance.try_into().map_err(EvalError::Misc)?;
+    let pow_distance: BigInt256 = header
+        .autolykos_solution
+        .pow_distance
+        .unwrap_or_default()
+        .try_into()
+        .map_err(EvalError::Misc)?;
     Ok(pow_distance.into())
 };
 
@@ -84,7 +96,7 @@ pub(crate) static VOTES_EVAL_FN: EvalFn = |_env, _ctx, obj, _args| {
 
 #[cfg(test)]
 #[cfg(feature = "arbitrary")]
-#[allow(clippy::expect_used, clippy::panic)]
+#[allow(clippy::expect_used, clippy::panic, clippy::unwrap_used)]
 mod tests {
     use std::convert::{TryFrom, TryInto};
     use std::rc::Rc;
@@ -270,7 +282,15 @@ mod tests {
         let expected = ctx
             .headers
             .get(HEADER_INDEX)
-            .map(|h| [h.miner_pk.clone(), h.pow_onetime_pk.clone()])
+            .map(|h| {
+                [
+                    h.autolykos_solution.miner_pk.clone(),
+                    h.autolykos_solution
+                        .pow_onetime_pk
+                        .clone()
+                        .unwrap_or_else(|| Box::new(EcPoint::default())),
+                ]
+            })
             .expect("internal error: empty headers array");
         let actual = eval_header_pks(ctx);
         assert_eq!(expected, actual);
@@ -280,7 +300,11 @@ mod tests {
     fn test_eval_pow_distance() {
         let expr = create_get_header_property_expr(sheader::POW_DISTANCE_PROPERTY.clone());
         let ctx = Rc::new(force_any_val::<Context>());
-        let expected = ctx.headers[HEADER_INDEX].pow_distance.clone();
+        let expected = ctx.headers[HEADER_INDEX]
+            .autolykos_solution
+            .pow_distance
+            .clone()
+            .unwrap_or_default();
         let actual = {
             let bi = eval_out::<BigInt256>(&expr, ctx);
             bi.into()
@@ -292,7 +316,7 @@ mod tests {
     fn test_eval_pow_nonce() {
         let expr = create_get_header_property_expr(sheader::POW_NONCE_PROPERTY.clone());
         let ctx = Rc::new(force_any_val::<Context>());
-        let expected = ctx.headers[HEADER_INDEX].nonce.clone();
+        let expected = ctx.headers[HEADER_INDEX].autolykos_solution.nonce.clone();
         let actual = eval_out::<Vec<i8>>(&expr, ctx).as_vec_u8();
         assert_eq!(expected, actual);
     }
diff --git a/ergotree-ir/Cargo.toml b/ergotree-ir/Cargo.toml
index 205c7fe44..68b2884df 100644
--- a/ergotree-ir/Cargo.toml
+++ b/ergotree-ir/Cargo.toml
@@ -27,6 +27,7 @@ impl-trait-for-tuples = "0.2.0"
 proptest-derive = {version = "0.3.0", optional = true }
 bs58 = "0.4.0"
 base16 = "0.2.1"
+byteorder = "1"
 num-bigint = "0.4.0"
 #bounded-vec = { git = "https://github.com/ergoplatform/bounded-vec", rev="f684d78" }
 bounded-vec = { version = "^0.5.0", features=["serde"] }
@@ -38,7 +39,7 @@ strum = "0.21"
 strum_macros = "0.21"
 indexmap = "1.3.2"
 serde = { version = "1.0", features = ["derive"], optional = true }
-serde_json = { version = "1.0", optional = true }
+serde_json = { version = "1.0", features = ["arbitrary_precision"], optional = true }
 
 [dependencies.proptest]
 # wasm support, via https://altsysrq.github.io/proptest-book/proptest/wasm.html
diff --git a/ergotree-ir/src/chain/digest32.rs b/ergotree-ir/src/chain/digest32.rs
index 5d52554cb..b6c3014c2 100644
--- a/ergotree-ir/src/chain/digest32.rs
+++ b/ergotree-ir/src/chain/digest32.rs
@@ -6,6 +6,11 @@ use crate::serialization::SigmaParsingError;
 use crate::serialization::SigmaSerializable;
 use crate::serialization::SigmaSerializeResult;
 use crate::util::AsVecI8;
+use sigma_ser::vlq_encode::ReadSigmaVlqExt;
+use sigma_ser::vlq_encode::WriteSigmaVlqExt;
+use sigma_ser::ScorexParsingError;
+use sigma_ser::ScorexSerializable;
+use sigma_ser::ScorexSerializeResult;
 use std::convert::TryFrom;
 use std::convert::TryInto;
 use std::fmt::Formatter;
@@ -112,6 +117,18 @@ impl<const N: usize> SigmaSerializable for Digest<N> {
     }
 }
 
+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())?;
+        Ok(())
+    }
+    fn scorex_parse<R: ReadSigmaVlqExt>(r: &mut R) -> Result<Self, ScorexParsingError> {
+        let mut bytes = [0; N];
+        r.read_exact(&mut bytes)?;
+        Ok(Self(bytes.into()))
+    }
+}
+
 impl AsRef<[u8]> for Digest32 {
     fn as_ref(&self) -> &[u8] {
         &self.0[..]
diff --git a/ergotree-ir/src/chain/ergo_box/box_value.rs b/ergotree-ir/src/chain/ergo_box/box_value.rs
index c175b8e28..edd4af2f8 100644
--- a/ergotree-ir/src/chain/ergo_box/box_value.rs
+++ b/ergotree-ir/src/chain/ergo_box/box_value.rs
@@ -17,16 +17,15 @@ use thiserror::Error;
 pub struct BoxValue(pub(crate) u64);
 
 #[cfg(feature = "json")]
-#[serde_with::serde_as]
 #[derive(
     serde::Serialize, serde::Deserialize, PartialEq, Eq, Hash, Debug, Clone, Copy, FromStr,
 )]
+#[serde(
+    try_from = "crate::chain::json::box_value::BoxValueJson",
+    into = "crate::chain::json::box_value::BoxValueJson"
+)]
 /// Box value in nanoERGs with bound checks
-pub struct BoxValue(
-    // Tries to decode as u64 first, then fallback to string. Encodes as u64 always
-    // see details - https://docs.rs/serde_with/1.9.4/serde_with/struct.PickFirst.html
-    #[serde_as(as = "serde_with::PickFirst<(_, serde_with::DisplayFromStr)>")] pub(crate) u64,
-);
+pub struct BoxValue(pub(crate) u64);
 
 impl BoxValue {
     /// Minimal box value per byte of the serialized box that was set on on launch
diff --git a/ergotree-ir/src/chain/header.rs b/ergotree-ir/src/chain/header.rs
index 8e1f703a3..3693df930 100644
--- a/ergotree-ir/src/chain/header.rs
+++ b/ergotree-ir/src/chain/header.rs
@@ -1,10 +1,17 @@
 //! Block header
+use std::io::Write;
+
 use num_bigint::BigInt;
+use sigma_ser::vlq_encode::{ReadSigmaVlqExt, WriteSigmaVlqExt};
+use sigma_ser::{
+    ScorexParsingError, ScorexSerializable, ScorexSerializationError, ScorexSerializeResult,
+};
 
-use crate::sigma_protocol::dlog_group;
+use crate::serialization::sigma_byte_writer::SigmaByteWriter;
+use crate::sigma_protocol::dlog_group::{self, EcPoint};
 
 use super::block_id::BlockId;
-use super::digest32::{ADDigest, Digest32};
+use super::digest32::{blake2b256_hash, ADDigest, Digest32};
 use super::preheader::PreHeader;
 use super::votes::Votes;
 
@@ -42,23 +49,228 @@ pub struct Header {
     /// Root hash of extension section
     #[cfg_attr(feature = "json", serde(rename = "extensionHash"))]
     pub extension_root: Digest32,
+    /// Solution for an Autolykos PoW puzzle
+    #[cfg_attr(feature = "json", serde(rename = "powSolutions"))]
+    pub autolykos_solution: AutolykosSolution,
+    /// Miner votes for changing system parameters.
+    /// 3 bytes in accordance to Scala implementation, but will use `Vec` until further improvements
+    #[cfg_attr(feature = "json", serde(rename = "votes"))]
+    pub votes: Votes,
+}
+
+impl Header {
+    /// Used in nipowpow
+    pub fn serialize_without_pow(&self) -> Result<Vec<u8>, ScorexSerializationError> {
+        use byteorder::{BigEndian, WriteBytesExt};
+        let mut data = Vec::new();
+        let mut w = SigmaByteWriter::new(&mut data, None);
+        w.put_u8(self.version)?;
+        self.parent_id.0.scorex_serialize(&mut w)?;
+        self.ad_proofs_root.scorex_serialize(&mut w)?;
+        self.transaction_root.scorex_serialize(&mut w)?;
+        self.state_root.scorex_serialize(&mut w)?;
+        w.put_u64(self.timestamp)?;
+        self.extension_root.scorex_serialize(&mut w)?;
+
+        // n_bits needs to be serialized in big-endian format. Note that it actually fits in a
+        // `u32`.
+        let mut n_bits_writer = vec![];
+        #[allow(clippy::unwrap_used)]
+        n_bits_writer
+            .write_u32::<BigEndian>(self.n_bits as u32)
+            .unwrap();
+        w.write_all(&n_bits_writer)?;
+
+        w.put_u32(self.height)?;
+        w.write_all(&self.votes.0)?;
+
+        // For block version >= 2, this new byte encodes length of possible new fields.
+        // Set to 0 for now, so no new fields.
+        if self.version > 1 {
+            w.put_i8(0)?;
+        }
+        Ok(data)
+    }
+}
+
+impl ScorexSerializable for Header {
+    fn scorex_serialize<W: WriteSigmaVlqExt>(&self, w: &mut W) -> ScorexSerializeResult {
+        let bytes = self.serialize_without_pow()?;
+        w.write_all(&bytes)?;
+
+        // Serialize `AutolykosSolution`
+        self.autolykos_solution.serialize_bytes(self.version, w)?;
+        Ok(())
+    }
+
+    fn scorex_parse<R: ReadSigmaVlqExt>(r: &mut R) -> Result<Self, ScorexParsingError> {
+        let version = r.get_u8()?;
+        let parent_id = BlockId(Digest32::scorex_parse(r)?);
+        let ad_proofs_root = Digest32::scorex_parse(r)?;
+        let transaction_root = Digest32::scorex_parse(r)?;
+        let state_root = ADDigest::scorex_parse(r)?;
+        let timestamp = r.get_u64()?;
+        let extension_root = Digest32::scorex_parse(r)?;
+        let mut n_bits_buf = [0u8, 0, 0, 0];
+        r.read_exact(&mut n_bits_buf)?;
+        let n_bits = {
+            use byteorder::{BigEndian, ReadBytesExt};
+            let mut reader = std::io::Cursor::new(n_bits_buf);
+            #[allow(clippy::unwrap_used)]
+            {
+                reader.read_u32::<BigEndian>().unwrap() as u64
+            }
+        };
+        let height = r.get_u32()?;
+        let mut votes_bytes = [0u8, 0, 0];
+        r.read_exact(&mut votes_bytes)?;
+        let votes = Votes(votes_bytes);
+
+        // For block version >= 2, a new byte encodes length of possible new fields.  If this byte >
+        // 0, we read new fields but do nothing, as semantics of the fields is not known.
+        if version > 1 {
+            let new_field_size = r.get_u8()?;
+            if new_field_size > 0 {
+                let mut field_bytes: Vec<u8> =
+                    std::iter::repeat(0).take(new_field_size as usize).collect();
+                r.read_exact(&mut field_bytes)?;
+            }
+        }
+
+        // Parse `AutolykosSolution`
+        let autolykos_solution = if version == 1 {
+            let miner_pk = EcPoint::scorex_parse(r)?.into();
+            let pow_onetime_pk = Some(EcPoint::scorex_parse(r)?.into());
+            let mut nonce: Vec<u8> = std::iter::repeat(0).take(8).collect();
+            r.read_exact(&mut nonce)?;
+            let d_bytes_len = r.get_u8()?;
+            let mut d_bytes: Vec<u8> = std::iter::repeat(0).take(d_bytes_len as usize).collect();
+            r.read_exact(&mut d_bytes)?;
+            let pow_distance = Some(BigInt::from_signed_bytes_be(&d_bytes));
+            AutolykosSolution {
+                miner_pk,
+                pow_onetime_pk,
+                nonce,
+                pow_distance,
+            }
+        } else {
+            // autolykos v2
+            let pow_onetime_pk = None;
+            let pow_distance = None;
+            let miner_pk = EcPoint::scorex_parse(r)?.into();
+            let mut nonce: Vec<u8> = std::iter::repeat(0).take(8).collect();
+            r.read_exact(&mut nonce)?;
+            AutolykosSolution {
+                miner_pk,
+                pow_onetime_pk,
+                nonce,
+                pow_distance,
+            }
+        };
+
+        // The `Header.id` field isn't serialized/deserialized but rather computed as a hash of
+        // every other field in `Header`. First we initialize header with dummy id field then
+        // compute the hash.
+        let mut header = Header {
+            version,
+            id: BlockId(Digest32::zero()),
+            parent_id,
+            ad_proofs_root,
+            state_root,
+            transaction_root,
+            timestamp,
+            n_bits,
+            height,
+            extension_root,
+            autolykos_solution: autolykos_solution.clone(),
+            votes,
+        };
+
+        let mut id_bytes = header.serialize_without_pow()?;
+        let mut data = Vec::new();
+        let mut w = SigmaByteWriter::new(&mut data, None);
+        autolykos_solution.serialize_bytes(version, &mut w)?;
+        id_bytes.extend(data);
+        let id = BlockId(blake2b256_hash(&id_bytes));
+        header.id = id;
+        Ok(header)
+    }
+}
+
+/// Solution for an Autolykos PoW puzzle. In Autolykos v.1 all the four fields are used, in
+/// Autolykos v.2 only `miner_pk` and `nonce` fields are used.
+#[cfg_attr(feature = "json", derive(serde::Serialize, serde::Deserialize))]
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct AutolykosSolution {
     /// Public key of miner. Part of Autolykos solution.
-    #[cfg_attr(feature = "json", serde(skip_serializing, skip_deserializing))]
+    #[cfg_attr(feature = "json", serde(rename = "pk"))]
     pub miner_pk: Box<dlog_group::EcPoint>,
     /// One-time public key. Prevents revealing of miners secret.
-    #[cfg_attr(feature = "json", serde(skip_serializing, skip_deserializing))]
-    pub pow_onetime_pk: Box<dlog_group::EcPoint>,
+    #[cfg_attr(feature = "json", serde(default, rename = "w"))]
+    pub pow_onetime_pk: Option<Box<dlog_group::EcPoint>>,
     /// nonce
-    #[cfg_attr(feature = "json", serde(skip_serializing, skip_deserializing))]
+    #[cfg_attr(
+        feature = "json",
+        serde(
+            rename = "n",
+            serialize_with = "crate::chain::json::autolykos_solution::as_base16_string",
+            deserialize_with = "crate::chain::json::autolykos_solution::from_base16_string"
+        )
+    )]
     pub nonce: Vec<u8>,
     /// Distance between pseudo-random number, corresponding to nonce `nonce` and a secret,
-    /// corresponding to `miner_pk`. The lower `pow_distance` is, the harder it was to find this solution.
-    #[cfg_attr(feature = "json", serde(skip_serializing, skip_deserializing))]
-    pub pow_distance: BigInt,
-    /// Miner votes for changing system parameters.
-    /// 3 bytes in accordance to Scala implementation, but will use `Vec` until further improvements
-    #[cfg_attr(feature = "json", serde(rename = "votes"))]
-    pub votes: Votes,
+    /// corresponding to `miner_pk`. The lower `pow_distance` is, the harder it was to find this
+    /// solution.
+    ///
+    /// Note: we serialize/deserialize through custom functions since `BigInt`s serde implementation
+    /// encodes the sign and absolute-value of the value separately, which is incompatible with the
+    /// JSON representation used by Ergo. ASSUMPTION: we assume that `pow_distance` encoded as a
+    /// `u64`.
+    #[cfg_attr(
+        feature = "json",
+        serde(
+            default,
+            rename = "d",
+            serialize_with = "crate::chain::json::autolykos_solution::bigint_as_str",
+            deserialize_with = "crate::chain::json::autolykos_solution::bigint_from_serde_json_number"
+        )
+    )]
+    pub pow_distance: Option<BigInt>,
+}
+
+impl AutolykosSolution {
+    /// Serialize instance
+    pub fn serialize_bytes<W: WriteSigmaVlqExt>(
+        &self,
+        version: u8,
+        w: &mut W,
+    ) -> Result<(), ScorexSerializationError> {
+        if version == 1 {
+            self.miner_pk.scorex_serialize(w)?;
+            self.pow_onetime_pk
+                .as_ref()
+                .ok_or(ScorexSerializationError::Misc(
+                    "pow_onetime_pk must == Some(_) for autolykos v1",
+                ))?
+                .scorex_serialize(w)?;
+            w.write_all(&self.nonce)?;
+
+            let d_bytes = self
+                .pow_distance
+                .as_ref()
+                .ok_or(ScorexSerializationError::Misc(
+                    "pow_distance must be == Some(_) for autolykos v1",
+                ))?
+                .to_signed_bytes_be();
+            w.put_u8(d_bytes.len() as u8)?;
+            w.write_all(&d_bytes)?;
+        } else {
+            // Autolykos v2
+            self.miner_pk.scorex_serialize(w)?;
+            w.write_all(&self.nonce)?;
+        }
+        Ok(())
+    }
 }
 
 impl From<Header> for PreHeader {
@@ -69,23 +281,26 @@ impl From<Header> for PreHeader {
             timestamp: bh.timestamp,
             n_bits: bh.n_bits,
             height: bh.height,
-            miner_pk: bh.miner_pk,
+            miner_pk: bh.autolykos_solution.miner_pk,
             votes: bh.votes,
         }
     }
 }
 
 #[cfg(feature = "arbitrary")]
+#[allow(clippy::unwrap_used)]
 mod arbitrary {
+
     use num_bigint::BigInt;
     use proptest::array::{uniform3, uniform32};
     use proptest::prelude::*;
 
-    use crate::chain::digest32::ADDigest;
-    use crate::chain::digest32::Digest;
+    use crate::chain::digest32::{blake2b256_hash, ADDigest};
+    use crate::chain::digest32::{Digest, Digest32};
+    use crate::serialization::sigma_byte_writer::SigmaByteWriter;
     use crate::sigma_protocol::dlog_group::EcPoint;
 
-    use super::{BlockId, Header, Votes};
+    use super::{AutolykosSolution, BlockId, Header, Votes};
 
     impl Arbitrary for Header {
         type Parameters = ();
@@ -95,18 +310,16 @@ mod arbitrary {
                 uniform32(1u8..),
                 uniform32(1u8..),
                 uniform32(1u8..),
-                uniform32(1u8..),
                 // Timestamps between 2000-2050
                 946_674_000_000..2_500_400_300_000u64,
-                any::<u64>(),
+                any::<u32>(), // Note: n_bits must fit in u32
                 0..1_000_000u32,
-                any::<Box<EcPoint>>(),
-                any::<Box<EcPoint>>(),
+                prop::sample::select(vec![1_u8, 2]),
+                any::<Box<AutolykosSolution>>(),
                 uniform3(1u8..),
             )
                 .prop_map(
                     |(
-                        id,
                         parent_id,
                         ad_proofs_root,
                         transaction_root,
@@ -114,33 +327,50 @@ mod arbitrary {
                         timestamp,
                         n_bits,
                         height,
-                        miner_pk,
-                        pow_onetime_pk,
+                        version,
+                        autolykos_solution,
                         votes,
                     )| {
-                        let id = BlockId(Digest(id.into()));
                         let parent_id = BlockId(Digest(parent_id.into()));
                         let ad_proofs_root = Digest(ad_proofs_root.into());
                         let transaction_root = Digest(transaction_root.into());
                         let extension_root = Digest(extension_root.into());
                         let votes = Votes(votes);
-                        Self {
-                            version: 1,
-                            id,
+
+                        // The `Header.id` field isn't serialized/deserialized but rather computed
+                        // as a hash of every other field in `Header`. First we initialize header
+                        // with dummy id field then compute the hash.
+                        let mut header = Self {
+                            version,
+                            id: BlockId(Digest32::zero()),
                             parent_id,
                             ad_proofs_root,
                             state_root: ADDigest::zero(),
                             transaction_root,
                             timestamp,
-                            n_bits,
+                            n_bits: n_bits as u64,
                             height,
                             extension_root,
-                            miner_pk,
-                            pow_onetime_pk,
-                            nonce: Vec::new(),
-                            pow_distance: BigInt::default(),
+                            autolykos_solution: *autolykos_solution.clone(),
                             votes,
+                        };
+                        let mut id_bytes = header.serialize_without_pow().unwrap();
+                        let mut data = Vec::new();
+                        let mut w = SigmaByteWriter::new(&mut data, None);
+                        autolykos_solution.serialize_bytes(version, &mut w).unwrap();
+                        id_bytes.extend(data);
+                        let id = BlockId(blake2b256_hash(&id_bytes));
+                        header.id = id;
+
+                        // Manually set the following parameters to `None` for autolykos v2. This is
+                        // allowable since serialization/deserialization of the `Header` ignores
+                        // these fields for version > 1.
+                        if header.version > 1 {
+                            header.autolykos_solution.pow_onetime_pk = None;
+                            header.autolykos_solution.pow_distance = None;
                         }
+
+                        header
                     },
                 )
                 .boxed()
@@ -148,12 +378,51 @@ mod arbitrary {
 
         type Strategy = BoxedStrategy<Header>;
     }
+
+    impl Arbitrary for AutolykosSolution {
+        type Parameters = ();
+        type Strategy = BoxedStrategy<AutolykosSolution>;
+
+        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
+            (
+                any::<Box<EcPoint>>(),
+                prop::collection::vec(0_u8.., 8),
+                any::<Box<EcPoint>>(),
+                any::<u64>(),
+            )
+                .prop_map(
+                    |(miner_pk, nonce, pow_onetime_pk, pow_distance)| AutolykosSolution {
+                        miner_pk,
+                        nonce,
+                        pow_onetime_pk: Some(pow_onetime_pk),
+                        pow_distance: Some(BigInt::from(pow_distance)),
+                    },
+                )
+                .boxed()
+        }
+    }
 }
 
-#[allow(clippy::unwrap_used)]
+#[allow(clippy::unwrap_used, clippy::panic)]
 #[cfg(test)]
+#[cfg(feature = "arbitrary")]
 mod tests {
+    use std::str::FromStr;
+
+    use num_bigint::BigInt;
+
     use crate::chain::header::Header;
+    use proptest::prelude::*;
+    use sigma_ser::scorex_serialize_roundtrip;
+
+    proptest! {
+        #![proptest_config(ProptestConfig::with_cases(64))]
+
+        #[test]
+        fn ser_roundtrip(v in any::<Header>()) {
+            assert_eq![scorex_serialize_roundtrip(&v), v]
+        }
+    }
 
     #[test]
     fn parse_block_header() {
@@ -175,7 +444,7 @@ mod tests {
               "pk": "02b3a06d6eaa8671431ba1db4dd427a77f75a5c2acbd71bfb725d38adc2b55f669",
               "w": "0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798",
               "n": "5939ecfee6b0d7f4",
-              "d": 0
+              "d": "1234000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
             },
             "adProofsId": "86eaa41f328bee598e33e52c9e515952ad3b7874102f762847f17318a776a7ae",
             "transactionsId": "ac80245714f25aa2fafe5494ad02a26d46e7955b8f5709f3659f1b9440797b3e",
@@ -183,6 +452,13 @@ mod tests {
         }"#;
         let header: Header = serde_json::from_str(json).unwrap();
         assert_eq!(header.height, 471746);
+        assert_eq!(
+            header.autolykos_solution.pow_distance,
+            Some(BigInt::from_str(
+                "1234000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
+            )
+            .unwrap())
+        );
     }
 
     #[test]
@@ -206,7 +482,7 @@ mod tests {
               "pk": "02b3a06d6eaa8671431ba1db4dd427a77f75a5c2acbd71bfb725d38adc2b55f669",
               "w": "0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798",
               "n": "5939ecfee6b0d7f4",
-              "d": 0
+              "d": 1234000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
             },
             "adProofsId": "86eaa41f328bee598e33e52c9e515952ad3b7874102f762847f17318a776a7ae",
             "transactionsId": "ac80245714f25aa2fafe5494ad02a26d46e7955b8f5709f3659f1b9440797b3e",
@@ -214,5 +490,12 @@ mod tests {
         }"#;
         let header: Header = serde_json::from_str(json).unwrap();
         assert_eq!(header.height, 471746);
+        assert_eq!(
+            header.autolykos_solution.pow_distance,
+            Some(BigInt::from_str(
+                "1234000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
+            )
+            .unwrap())
+        );
     }
 }
diff --git a/ergotree-ir/src/chain/json.rs b/ergotree-ir/src/chain/json.rs
index 723f3d479..2f17a99dc 100644
--- a/ergotree-ir/src/chain/json.rs
+++ b/ergotree-ir/src/chain/json.rs
@@ -2,8 +2,12 @@
 
 use serde::Serializer;
 
+pub(crate) mod autolykos_solution;
+pub(crate) mod box_value;
 pub(crate) mod ergo_box;
 pub mod ergo_tree;
+pub(crate) mod token;
+pub(crate) mod votes;
 
 /// Serialize bytes ([u8]) as base16 encoded string
 pub fn serialize_bytes<S, T>(bytes: T, serializer: S) -> Result<S::Ok, S::Error>
diff --git a/ergotree-ir/src/chain/json/autolykos_solution.rs b/ergotree-ir/src/chain/json/autolykos_solution.rs
new file mode 100644
index 000000000..c5bb2d208
--- /dev/null
+++ b/ergotree-ir/src/chain/json/autolykos_solution.rs
@@ -0,0 +1,66 @@
+//! Code to implement `AutolykosSolution` JSON encoding
+
+use std::str::FromStr;
+
+use num_bigint::BigInt;
+use serde::{Deserialize, Deserializer};
+
+pub(crate) fn as_base16_string<S>(value: &[u8], serializer: S) -> Result<S::Ok, S::Error>
+where
+    S: serde::Serializer,
+{
+    serializer.serialize_str(&base16::encode_lower(value))
+}
+
+pub(crate) fn from_base16_string<'de, D>(deserializer: D) -> Result<Vec<u8>, D::Error>
+where
+    D: Deserializer<'de>,
+{
+    use serde::de::Error;
+    String::deserialize(deserializer)
+        .and_then(|string| base16::decode(&string).map_err(|err| Error::custom(err.to_string())))
+}
+
+/// Serialize `BigInt` as a string
+pub(crate) fn bigint_as_str<S>(value: &Option<BigInt>, serializer: S) -> Result<S::Ok, S::Error>
+where
+    S: serde::Serializer,
+{
+    if let Some(value) = value {
+        serializer.serialize_str(&value.to_string())
+    } else {
+        serializer.serialize_unit()
+    }
+}
+
+/// Deserialize a `BigInt` instance from either a String or from a `serde_json::Number` value.  We
+/// need to do this because the JSON specification allows for arbitrarily-large numbers, a feature
+/// that Autolykos makes use of to encode the PoW-distance (d) parameter. Note that we also need to
+/// use `serde_json` with the `arbitrary_precision` feature for this to work.
+pub(crate) fn bigint_from_serde_json_number<'de, D>(
+    deserializer: D,
+) -> Result<Option<BigInt>, D::Error>
+where
+    D: Deserializer<'de>,
+{
+    use serde::de::Error;
+
+    match DeserializeBigIntFrom::deserialize(deserializer) {
+        Ok(s) => match s {
+            DeserializeBigIntFrom::String(s) => BigInt::from_str(&s)
+                .map(Some)
+                .map_err(|e| Error::custom(e.to_string())),
+            DeserializeBigIntFrom::SerdeJsonNumber(n) => BigInt::from_str(&n.to_string())
+                .map(Some)
+                .map_err(|e| Error::custom(e.to_string())),
+        },
+        Err(e) => Err(Error::custom(e.to_string())),
+    }
+}
+
+#[derive(Deserialize)]
+#[serde(untagged)]
+enum DeserializeBigIntFrom {
+    String(String),
+    SerdeJsonNumber(serde_json::Number),
+}
diff --git a/ergotree-ir/src/chain/json/box_value.rs b/ergotree-ir/src/chain/json/box_value.rs
new file mode 100644
index 000000000..cc9dfd566
--- /dev/null
+++ b/ergotree-ir/src/chain/json/box_value.rs
@@ -0,0 +1,40 @@
+//! Code to implement `BoxValue` JSON encoding
+
+use std::convert::TryFrom;
+
+use crate::chain::ergo_box::box_value::BoxValue;
+
+/// Helper struct to serialize/deserialize `BoxValue`.
+///
+/// We use `serde_json::Number` below due to a known `serde_json` bug described here:
+/// <https://github.com/serde-rs/json/issues/740>. Basically we can't deserialise any integer types
+/// directly within untagged enums when the `arbitrary_precision` feature is used. The workaround is
+/// to deserialize as `serde_json::Number` first, then manually convert the type.
+///
+/// Tries to decode as `BigInt` first, then fallback to string. Encodes as `BigInt` always.
+/// see details - https://docs.rs/serde_with/1.9.4/serde_with/struct.PickFirst.html
+#[cfg(feature = "json")]
+#[serde_with::serde_as]
+#[derive(serde::Serialize, serde::Deserialize)]
+pub(crate) struct BoxValueJson(
+    #[serde_as(as = "serde_with::PickFirst<(_, serde_with::DisplayFromStr)>")]
+    pub(crate)  serde_json::Number,
+);
+
+impl TryFrom<BoxValueJson> for BoxValue {
+    type Error = String;
+
+    fn try_from(value: BoxValueJson) -> Result<Self, Self::Error> {
+        if let Some(n) = value.0.as_u64() {
+            Ok(BoxValue(n))
+        } else {
+            Err(String::from("can't convert `BoxValueJson` into `BoxValue`"))
+        }
+    }
+}
+
+impl From<BoxValue> for BoxValueJson {
+    fn from(value: BoxValue) -> Self {
+        BoxValueJson(serde_json::Number::from(value.0))
+    }
+}
diff --git a/ergotree-ir/src/chain/json/token.rs b/ergotree-ir/src/chain/json/token.rs
new file mode 100644
index 000000000..43652123b
--- /dev/null
+++ b/ergotree-ir/src/chain/json/token.rs
@@ -0,0 +1,41 @@
+//! Code to implement `TokenAmount` JSON encoding
+
+use std::convert::TryFrom;
+
+use crate::chain::token::TokenAmount;
+
+/// Helper struct to serialize/deserialize `TokenAmount`.
+///
+/// We use `serde_json::Number` below due to a known `serde_json` bug described here:
+/// <https://github.com/serde-rs/json/issues/740>. Basically we can't deserialise any integer types
+/// directly within untagged enums when the `arbitrary_precision` feature is used. The workaround is
+/// to deserialize as `serde_json::Number` first, then manually convert the type.
+///
+/// Tries to decode as `BigInt` first, then fallback to string. Encodes as `BigInt` always.
+/// see details - https://docs.rs/serde_with/1.9.4/serde_with/struct.PickFirst.html
+#[cfg(feature = "json")]
+#[serde_with::serde_as]
+#[derive(serde::Serialize, serde::Deserialize)]
+pub(crate) struct TokenAmountJson(
+    #[serde_as(as = "serde_with::PickFirst<(_, serde_with::DisplayFromStr)>")] serde_json::Number,
+);
+
+impl TryFrom<TokenAmountJson> for TokenAmount {
+    type Error = String;
+
+    fn try_from(value: TokenAmountJson) -> Result<Self, Self::Error> {
+        if let Some(n) = value.0.as_u64() {
+            Ok(TokenAmount(n))
+        } else {
+            Err(String::from(
+                "can't convert `TokenAmountJson` into `TokenAmount`",
+            ))
+        }
+    }
+}
+
+impl From<TokenAmount> for TokenAmountJson {
+    fn from(value: TokenAmount) -> Self {
+        TokenAmountJson(serde_json::Number::from(value.0))
+    }
+}
diff --git a/ergotree-ir/src/chain/json/votes.rs b/ergotree-ir/src/chain/json/votes.rs
new file mode 100644
index 000000000..b0cc90208
--- /dev/null
+++ b/ergotree-ir/src/chain/json/votes.rs
@@ -0,0 +1,48 @@
+//! Code to implement `Votes` JSON encoding
+
+use std::convert::{TryFrom, TryInto};
+
+use crate::chain::{
+    base16_bytes::Base16DecodedBytes,
+    votes::{Votes, VotesError},
+};
+
+#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
+#[serde(untagged)]
+pub(crate) enum VotesEncodingVariants {
+    AsStr(Base16DecodedBytes),
+    /// We need `serde_json::Number` here due to a known `serde_json` bug described here:
+    /// <https://github.com/serde-rs/json/issues/740>. Basically we can't deserialise any integer
+    /// types directly within untagged enums when the `arbitrary_precision` feature is used. The
+    /// workaround is to deserialize as `serde_json::Number` first, then manually convert the type.
+    AsByteArray(Vec<serde_json::Number>), // explorer v1
+}
+
+impl TryFrom<VotesEncodingVariants> for Votes {
+    type Error = VotesError;
+
+    fn try_from(value: VotesEncodingVariants) -> Result<Self, Self::Error> {
+        match value {
+            VotesEncodingVariants::AsStr(bytes) => bytes.try_into(),
+            VotesEncodingVariants::AsByteArray(bytes) => bytes.try_into(),
+        }
+    }
+}
+
+impl TryFrom<Vec<serde_json::Number>> for Votes {
+    type Error = VotesError;
+
+    fn try_from(bytes: Vec<serde_json::Number>) -> Result<Self, Self::Error> {
+        let bytes_u8: Vec<u8> = bytes
+            .into_iter()
+            .map(|n| {
+                #[allow(clippy::unwrap_used)]
+                {
+                    n.as_u64().unwrap() as u8
+                }
+            })
+            .collect();
+        let arr: [u8; 3] = bytes_u8.as_slice().try_into()?;
+        Ok(Self(arr))
+    }
+}
diff --git a/ergotree-ir/src/chain/token.rs b/ergotree-ir/src/chain/token.rs
index d558e0648..f7a44acc6 100644
--- a/ergotree-ir/src/chain/token.rs
+++ b/ergotree-ir/src/chain/token.rs
@@ -69,15 +69,14 @@ pub struct TokenAmount(u64);
 
 /// Token amount with bound checks
 #[cfg(feature = "json")]
-#[serde_with::serde_as]
 #[derive(
     serde::Serialize, serde::Deserialize, PartialEq, Eq, Hash, Debug, Clone, Copy, PartialOrd, Ord,
 )]
-pub struct TokenAmount(
-    // Tries to decode as u64 first, then fallback to string. Encodes as u64 always
-    // see details - https://docs.rs/serde_with/1.9.4/serde_with/struct.PickFirst.html
-    #[serde_as(as = "serde_with::PickFirst<(_, serde_with::DisplayFromStr)>")] u64,
-);
+#[serde(
+    try_from = "crate::chain::json::token::TokenAmountJson",
+    into = "crate::chain::json::token::TokenAmountJson"
+)]
+pub struct TokenAmount(pub(crate) u64);
 
 impl TokenAmount {
     /// minimal allowed value
diff --git a/ergotree-ir/src/chain/votes.rs b/ergotree-ir/src/chain/votes.rs
index ccb7bb3a5..62c310f18 100644
--- a/ergotree-ir/src/chain/votes.rs
+++ b/ergotree-ir/src/chain/votes.rs
@@ -11,30 +11,13 @@ use super::base16_bytes::Base16EncodedBytes;
 #[derive(PartialEq, Eq, Debug, Clone)]
 #[cfg_attr(
     feature = "json",
-    serde(into = "Base16EncodedBytes", try_from = "VotesEncodingVariants")
+    serde(
+        into = "Base16EncodedBytes",
+        try_from = "crate::chain::json::votes::VotesEncodingVariants"
+    )
 )]
 pub struct Votes(pub [u8; 3]);
 
-#[cfg_attr(feature = "json", derive(serde::Serialize, serde::Deserialize))]
-#[derive(Debug, Clone)]
-#[cfg_attr(feature = "json", serde(untagged))]
-#[allow(dead_code)]
-enum VotesEncodingVariants {
-    AsStr(Base16DecodedBytes),
-    AsByteArray(Vec<u8>), // explorer v1
-}
-
-impl TryFrom<VotesEncodingVariants> for Votes {
-    type Error = VotesError;
-
-    fn try_from(value: VotesEncodingVariants) -> Result<Self, Self::Error> {
-        match value {
-            VotesEncodingVariants::AsStr(bytes) => bytes.try_into(),
-            VotesEncodingVariants::AsByteArray(bytes) => bytes.try_into(),
-        }
-    }
-}
-
 impl From<Votes> for Vec<u8> {
     fn from(v: Votes) -> Self {
         v.0.to_vec()
diff --git a/ergotree-ir/src/serialization/serializable.rs b/ergotree-ir/src/serialization/serializable.rs
index 8dfe99a53..8e71cc452 100644
--- a/ergotree-ir/src/serialization/serializable.rs
+++ b/ergotree-ir/src/serialization/serializable.rs
@@ -12,7 +12,7 @@ use crate::types::smethod::MethodId;
 use bounded_vec::BoundedVec;
 use bounded_vec::BoundedVecOutOfBounds;
 use io::Cursor;
-use sigma_ser::vlq_encode;
+use sigma_ser::{vlq_encode, ScorexParsingError, ScorexSerializationError};
 use std::convert::TryInto;
 use std::io;
 use thiserror::Error;
@@ -32,6 +32,9 @@ pub enum SigmaSerializationError {
     /// Serialization not supported
     #[error("serialization not supported: {0}")]
     NotSupported(&'static str),
+    /// Scorex serialization error
+    #[error("Scorex serialization error: {0}")]
+    ScorexSerializationError(#[from] ScorexSerializationError),
 }
 
 impl From<io::Error> for SigmaSerializationError {
@@ -97,6 +100,9 @@ pub enum SigmaParsingError {
     /// Invalid item quantity for BoundedVec
     #[error("Invalid item quantity for BoundedVec: {0}")]
     BoundedVecOutOfBounds(#[from] BoundedVecOutOfBounds),
+    /// Scorex parsing error
+    #[error("Scorex parsing error: {0}")]
+    ScorexParsingError(#[from] ScorexParsingError),
 }
 
 impl From<io::Error> for SigmaParsingError {
diff --git a/ergotree-ir/src/sigma_protocol/dlog_group.rs b/ergotree-ir/src/sigma_protocol/dlog_group.rs
index 8f268911d..bac035168 100644
--- a/ergotree-ir/src/sigma_protocol/dlog_group.rs
+++ b/ergotree-ir/src/sigma_protocol/dlog_group.rs
@@ -26,15 +26,22 @@ use elliptic_curve::group::prime::PrimeCurveAffine;
 use elliptic_curve::rand_core::RngCore;
 use k256::elliptic_curve::sec1::ToEncodedPoint;
 use k256::{ProjectivePoint, PublicKey, Scalar};
-use num_bigint::BigUint;
 use num_bigint::Sign;
 use num_bigint::ToBigUint;
+use num_bigint::{BigInt, BigUint};
 use num_traits::ToPrimitive;
+use sigma_ser::vlq_encode::{ReadSigmaVlqExt, WriteSigmaVlqExt};
+use sigma_ser::{ScorexParsingError, ScorexSerializable, ScorexSerializeResult};
 use std::convert::TryFrom;
 use std::ops::{Add, Mul, Neg};
 
 /// Elliptic curve point
 #[derive(PartialEq, Clone, Default)]
+#[cfg_attr(
+    feature = "json",
+    derive(serde::Serialize, serde::Deserialize),
+    serde(into = "String", try_from = "String")
+)]
 pub struct EcPoint(ProjectivePoint);
 
 #[allow(clippy::unwrap_used)]
@@ -60,6 +67,24 @@ impl EcPoint {
     }
 }
 
+impl TryFrom<String> for EcPoint {
+    type Error = String;
+    fn try_from(value: String) -> Result<Self, Self::Error> {
+        EcPoint::from_base16_str(value)
+            .ok_or_else(|| String::from("Ecpoint: error parsing from base16-encoded string"))
+    }
+}
+
+impl From<EcPoint> for String {
+    fn from(value: EcPoint) -> String {
+        #[allow(clippy::unwrap_used)]
+        {
+            let bytes = value.sigma_serialize_bytes().unwrap();
+            String::from_utf8(bytes).unwrap()
+        }
+    }
+}
+
 impl Eq for EcPoint {}
 
 impl Mul<&EcPoint> for EcPoint {
@@ -164,6 +189,18 @@ pub fn bigint256_to_scalar(bi: BigInt256) -> Option<Scalar> {
 
 impl SigmaSerializable for EcPoint {
     fn sigma_serialize<W: SigmaByteWrite>(&self, w: &mut W) -> SigmaSerializeResult {
+        let _ = self.scorex_serialize(w)?;
+        Ok(())
+    }
+
+    fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SigmaParsingError> {
+        let e = Self::scorex_parse(r)?;
+        Ok(e)
+    }
+}
+
+impl ScorexSerializable for EcPoint {
+    fn scorex_serialize<W: WriteSigmaVlqExt>(&self, w: &mut W) -> ScorexSerializeResult {
         let caff = self.0.to_affine();
         if caff.is_identity().into() {
             // infinity point
@@ -175,12 +212,12 @@ impl SigmaSerializable for EcPoint {
         Ok(())
     }
 
-    fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SigmaParsingError> {
+    fn scorex_parse<R: ReadSigmaVlqExt>(r: &mut R) -> Result<Self, ScorexParsingError> {
         let mut buf = [0; EcPoint::GROUP_SIZE];
         r.read_exact(&mut buf[..])?;
         if buf[0] != 0 {
             let pubkey = PublicKey::from_sec1_bytes(&buf[..]).map_err(|e| {
-                SigmaParsingError::Misc(format!("failed to parse PK from bytes: {:?}", e))
+                ScorexParsingError::Misc(format!("failed to parse PK from bytes: {:?}", e))
             })?;
             Ok(EcPoint(pubkey.to_projective()))
         } else {
@@ -190,6 +227,16 @@ impl SigmaSerializable for EcPoint {
     }
 }
 
+/// Order of the secp256k1 elliptic curve
+pub fn order() -> BigInt {
+    #[allow(clippy::unwrap_used)]
+    BigInt::parse_bytes(
+        b"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141",
+        16,
+    )
+    .unwrap()
+}
+
 /// Arbitrary impl for EcPoint
 #[cfg(feature = "arbitrary")]
 mod arbitrary {
diff --git a/sigma-ser/src/scorex_serialize.rs b/sigma-ser/src/scorex_serialize.rs
index 167a2b8a9..3058a701b 100644
--- a/sigma-ser/src/scorex_serialize.rs
+++ b/sigma-ser/src/scorex_serialize.rs
@@ -21,6 +21,9 @@ pub enum ScorexSerializationError {
     /// Integer type conversion failed
     #[error("Bounds check error: {0}")]
     TryFrom(#[from] std::num::TryFromIntError),
+    /// Misc error
+    #[error("error: {0}")]
+    Misc(&'static str),
 }
 
 impl From<io::Error> for ScorexSerializationError {


Test patch: