primitives: Implement decoders

diff --git a/Cargo-minimal.lock b/Cargo-minimal.lock
index 750738c6..a75d1055 100644
--- a/Cargo-minimal.lock
+++ b/Cargo-minimal.lock
@@ -134,6 +134,7 @@ dependencies = [
  "bitcoin_hashes 0.16.0",
  "consensus-encoding",
  "hex-conservative 0.3.0",
+ "hex_lit",
  "serde",
  "serde_json",
 ]
diff --git a/Cargo-recent.lock b/Cargo-recent.lock
index 42f41654..72965f60 100644
--- a/Cargo-recent.lock
+++ b/Cargo-recent.lock
@@ -133,6 +133,7 @@ dependencies = [
  "bitcoin_hashes 0.16.0",
  "consensus-encoding",
  "hex-conservative 0.3.0",
+ "hex_lit",
  "serde",
  "serde_json",
 ]
diff --git a/primitives/Cargo.toml b/primitives/Cargo.toml
index 4d831b4c..c4d28dab 100644
--- a/primitives/Cargo.toml
+++ b/primitives/Cargo.toml
@@ -36,6 +36,7 @@ serde = { version = "1.0.195", default-features = false, features = ["derive", "
 [dev-dependencies]
 serde_json = "1.0.68"
 bincode = "1.3.1"
+hex_lit = "0.1.1"
 
 [package.metadata.docs.rs]
 all-features = true
diff --git a/primitives/src/block.rs b/primitives/src/block.rs
index ab87c613..7f28ade9 100644
--- a/primitives/src/block.rs
+++ b/primitives/src/block.rs
@@ -7,20 +7,28 @@
 //! module describes structures and functions needed to describe
 //! these blocks and the blockchain.
 
+use core::convert::Infallible;
 use core::fmt;
 #[cfg(feature = "alloc")]
 use core::marker::PhantomData;
 
 #[cfg(feature = "arbitrary")]
 use arbitrary::{Arbitrary, Unstructured};
-use encoding::{CompactSizeEncoder, Encodable, Encoder2, SliceEncoder};
+use encoding::Encodable;
+#[cfg(feature = "alloc")]
+use encoding::{CompactSizeEncoder, Decodable, Decoder, Decoder6, Encoder2, SliceEncoder};
 use hashes::{sha256d, HashEngine as _};
+use internals::write_err;
 
+#[cfg(feature = "alloc")]
+use crate::pow::{CompactTargetDecoder, CompactTargetDecoderError};
 #[cfg(feature = "alloc")]
 use crate::prelude::Vec;
+#[cfg(feature = "alloc")]
+use crate::transaction::{TxMerkleNodeDecoder, TxMerkleNodeDecoderError};
 use crate::{BlockTime, CompactTarget, TxMerkleNode};
 #[cfg(feature = "alloc")]
-use crate::{Transaction, WitnessMerkleNode};
+use crate::{BlockTimeDecoder, BlockTimeDecoderError, Transaction, WitnessMerkleNode};
 
 #[rustfmt::skip]                // Keep public re-exports separate.
 #[doc(inline)]
@@ -30,7 +38,9 @@ pub use units::block::{BlockHeight, BlockHeightInterval, BlockMtp, BlockMtpInter
 pub use units::block::TooBigForRelativeHeightError;
 
 #[doc(inline)]
-pub use crate::hash_types::{BlockHash, BlockHashEncoder, WitnessCommitment};
+pub use crate::hash_types::{
+    BlockHash, BlockHashDecoder, BlockHashDecoderError, BlockHashEncoder, WitnessCommitment,
+};
 
 /// Marker for whether or not a block has been validated.
 ///
@@ -295,6 +305,139 @@ impl Encodable for Header {
     }
 }
 
+/// The decoder for the [`Header`] type.
+#[cfg(feature = "alloc")]
+pub struct HeaderDecoder(
+    Decoder6<
+        VersionDecoder,
+        BlockHashDecoder,
+        TxMerkleNodeDecoder,
+        BlockTimeDecoder,
+        CompactTargetDecoder,
+        encoding::ArrayDecoder<4>, // Nonce
+        HeaderDecoderError,
+    >,
+);
+
+#[cfg(feature = "alloc")]
+impl Decoder for HeaderDecoder {
+    type Output = Header;
+    type Error = HeaderDecoderError;
+
+    #[inline]
+    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<bool, Self::Error> {
+        self.0.push_bytes(bytes)
+    }
+
+    #[inline]
+    fn end(self) -> Result<Self::Output, Self::Error> {
+        let (version, prev_blockhash, merkle_root, time, bits, nonce) = self.0.end()?;
+        let nonce = u32::from_le_bytes(nonce);
+        Ok(Header { version, prev_blockhash, merkle_root, time, bits, nonce })
+    }
+
+    #[inline]
+    fn read_limit(&self) -> usize { self.0.read_limit() }
+}
+
+#[cfg(feature = "alloc")]
+impl Decodable for Header {
+    type Decoder = HeaderDecoder;
+    fn decoder() -> Self::Decoder {
+        HeaderDecoder(Decoder6::new(
+            VersionDecoder::new(),
+            BlockHashDecoder::new(),
+            TxMerkleNodeDecoder::new(),
+            BlockTimeDecoder::new(),
+            CompactTargetDecoder::new(),
+            encoding::ArrayDecoder::new(),
+        ))
+    }
+}
+
+/// An error consensus decoding a `Header`.
+#[cfg(feature = "alloc")]
+#[derive(Debug, Clone, PartialEq, Eq)]
+#[non_exhaustive]
+pub enum HeaderDecoderError {
+    /// Error while decoding the `version`.
+    Version(VersionDecoderError),
+    /// Error while decoding the `prev_blockhash`.
+    PrevBlockhash(BlockHashDecoderError),
+    /// Error while decoding the `merkle_root`.
+    MerkleRoot(TxMerkleNodeDecoderError),
+    /// Error while decoding the `time`.
+    Time(BlockTimeDecoderError),
+    /// Error while decoding the `bits`.
+    Bits(CompactTargetDecoderError),
+    /// Error while decoding the `nonce`.
+    Nonce(encoding::UnexpectedEofError),
+}
+
+#[cfg(feature = "alloc")]
+impl From<Infallible> for HeaderDecoderError {
+    fn from(never: Infallible) -> Self { match never {} }
+}
+
+#[cfg(feature = "alloc")]
+impl From<VersionDecoderError> for HeaderDecoderError {
+    fn from(e: VersionDecoderError) -> Self { Self::Version(e) }
+}
+
+#[cfg(feature = "alloc")]
+impl From<BlockHashDecoderError> for HeaderDecoderError {
+    fn from(e: BlockHashDecoderError) -> Self { Self::PrevBlockhash(e) }
+}
+
+#[cfg(feature = "alloc")]
+impl From<TxMerkleNodeDecoderError> for HeaderDecoderError {
+    fn from(e: TxMerkleNodeDecoderError) -> Self { Self::MerkleRoot(e) }
+}
+
+#[cfg(feature = "alloc")]
+impl From<BlockTimeDecoderError> for HeaderDecoderError {
+    fn from(e: BlockTimeDecoderError) -> Self { Self::Time(e) }
+}
+
+#[cfg(feature = "alloc")]
+impl From<CompactTargetDecoderError> for HeaderDecoderError {
+    fn from(e: CompactTargetDecoderError) -> Self { Self::Bits(e) }
+}
+
+#[cfg(feature = "alloc")]
+impl From<encoding::UnexpectedEofError> for HeaderDecoderError {
+    fn from(e: encoding::UnexpectedEofError) -> Self { Self::Nonce(e) }
+}
+
+#[cfg(feature = "alloc")]
+impl fmt::Display for HeaderDecoderError {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        match *self {
+            Self::Version(ref e) => write_err!(f, "header decoder error"; e),
+            Self::PrevBlockhash(ref e) => write_err!(f, "header decoder error"; e),
+            Self::MerkleRoot(ref e) => write_err!(f, "header decoder error"; e),
+            Self::Time(ref e) => write_err!(f, "header decoder error"; e),
+            Self::Bits(ref e) => write_err!(f, "header decoder error"; e),
+            Self::Nonce(ref e) => write_err!(f, "header decoder error"; e),
+        }
+    }
+}
+
+#[cfg(feature = "std")]
+#[cfg(feature = "alloc")]
+impl std::error::Error for HeaderDecoderError {
+    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
+        match *self {
+            Self::Version(ref e) => Some(e),
+            Self::PrevBlockhash(ref e) => Some(e),
+            Self::MerkleRoot(ref e) => Some(e),
+            Self::Time(ref e) => Some(e),
+            Self::Bits(ref e) => Some(e),
+            Self::Nonce(ref e) => Some(e),
+        }
+    }
+}
+
 impl From<Header> for BlockHash {
     #[inline]
     fn from(header: Header) -> BlockHash { header.block_hash() }
@@ -391,6 +534,65 @@ impl Encodable for Version {
     }
 }
 
+/// The decoder for the [`Version`] type.
+pub struct VersionDecoder(encoding::ArrayDecoder<4>);
+
+impl VersionDecoder {
+    /// Constructs a new [`Version`] decoder.
+    pub fn new() -> Self { Self(encoding::ArrayDecoder::new()) }
+}
+
+impl Default for VersionDecoder {
+    fn default() -> Self { Self::new() }
+}
+
+impl encoding::Decoder for VersionDecoder {
+    type Output = Version;
+    type Error = VersionDecoderError;
+
+    #[inline]
+    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<bool, Self::Error> {
+        Ok(self.0.push_bytes(bytes)?)
+    }
+
+    #[inline]
+    fn end(self) -> Result<Self::Output, Self::Error> {
+        let n = i32::from_le_bytes(self.0.end()?);
+        Ok(Version::from_consensus(n))
+    }
+
+    #[inline]
+    fn read_limit(&self) -> usize { self.0.read_limit() }
+}
+
+impl encoding::Decodable for Version {
+    type Decoder = VersionDecoder;
+    fn decoder() -> Self::Decoder { VersionDecoder(encoding::ArrayDecoder::<4>::new()) }
+}
+
+/// An error consensus decoding an `Version`.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct VersionDecoderError(encoding::UnexpectedEofError);
+
+impl From<Infallible> for VersionDecoderError {
+    fn from(never: Infallible) -> Self { match never {} }
+}
+
+impl From<encoding::UnexpectedEofError> for VersionDecoderError {
+    fn from(e: encoding::UnexpectedEofError) -> Self { Self(e) }
+}
+
+impl fmt::Display for VersionDecoderError {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write_err!(f, "version decoder error"; self.0)
+    }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for VersionDecoderError {
+    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> { Some(&self.0) }
+}
+
 #[cfg(feature = "arbitrary")]
 #[cfg(feature = "alloc")]
 impl<'a> Arbitrary<'a> for Block {
diff --git a/primitives/src/hash_types/block_hash.rs b/primitives/src/hash_types/block_hash.rs
index b1d2d139..438b7b5a 100644
--- a/primitives/src/hash_types/block_hash.rs
+++ b/primitives/src/hash_types/block_hash.rs
@@ -2,7 +2,7 @@
 
 //! The `BlockHash` type.
 
-#[cfg(not(feature = "hex"))]
+use core::convert::Infallible;
 use core::fmt;
 #[cfg(feature = "hex")]
 use core::str;
@@ -13,6 +13,7 @@ use encoding::Encodable;
 use hashes::sha256d;
 #[cfg(feature = "hex")]
 use hex::FromHex as _;
+use internals::write_err;
 
 /// A bitcoin block hash.
 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
@@ -41,3 +42,62 @@ impl Encodable for BlockHash {
         BlockHashEncoder(encoding::ArrayEncoder::without_length_prefix(self.to_byte_array()))
     }
 }
+
+/// The decoder for the [`BlockHash`] type.
+pub struct BlockHashDecoder(encoding::ArrayDecoder<32>);
+
+impl BlockHashDecoder {
+    /// Constructs a new [`BlockHash`] decoder.
+    pub fn new() -> Self { Self(encoding::ArrayDecoder::new()) }
+}
+
+impl Default for BlockHashDecoder {
+    fn default() -> Self { Self::new() }
+}
+
+impl encoding::Decoder for BlockHashDecoder {
+    type Output = BlockHash;
+    type Error = BlockHashDecoderError;
+
+    #[inline]
+    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<bool, Self::Error> {
+        Ok(self.0.push_bytes(bytes)?)
+    }
+
+    #[inline]
+    fn end(self) -> Result<Self::Output, Self::Error> {
+        let a = self.0.end()?;
+        Ok(BlockHash::from_byte_array(a))
+    }
+
+    #[inline]
+    fn read_limit(&self) -> usize { self.0.read_limit() }
+}
+
+impl encoding::Decodable for BlockHash {
+    type Decoder = BlockHashDecoder;
+    fn decoder() -> Self::Decoder { BlockHashDecoder(encoding::ArrayDecoder::<32>::new()) }
+}
+
+/// An error consensus decoding an `BlockHash`.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct BlockHashDecoderError(encoding::UnexpectedEofError);
+
+impl From<Infallible> for BlockHashDecoderError {
+    fn from(never: Infallible) -> Self { match never {} }
+}
+
+impl From<encoding::UnexpectedEofError> for BlockHashDecoderError {
+    fn from(e: encoding::UnexpectedEofError) -> Self { Self(e) }
+}
+
+impl fmt::Display for BlockHashDecoderError {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write_err!(f, "sequence decoder error"; self.0)
+    }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for BlockHashDecoderError {
+    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> { Some(&self.0) }
+}
diff --git a/primitives/src/hash_types/mod.rs b/primitives/src/hash_types/mod.rs
index e50bddad..5bb54e15 100644
--- a/primitives/src/hash_types/mod.rs
+++ b/primitives/src/hash_types/mod.rs
@@ -19,10 +19,10 @@ mod wtxid;
 #[rustfmt::skip]                // Keep public re-exports separate.
 #[doc(inline)]
 pub use self::{
-    block_hash::{BlockHash, BlockHashEncoder},
+    block_hash::{BlockHash, BlockHashDecoder, BlockHashDecoderError, BlockHashEncoder},
     ntxid::Ntxid,
-    transaction_merkle_node::{TxMerkleNode, TxMerkleNodeEncoder},
-    txid::Txid,
+    transaction_merkle_node::{TxMerkleNode, TxMerkleNodeEncoder, TxMerkleNodeDecoder, TxMerkleNodeDecoderError},
+    txid::{Txid},
     wtxid::Wtxid,
     witness_commitment::WitnessCommitment,
     witness_merkle_node::WitnessMerkleNode,
diff --git a/primitives/src/hash_types/transaction_merkle_node.rs b/primitives/src/hash_types/transaction_merkle_node.rs
index 91d89ea0..685fdca8 100644
--- a/primitives/src/hash_types/transaction_merkle_node.rs
+++ b/primitives/src/hash_types/transaction_merkle_node.rs
@@ -2,7 +2,7 @@
 
 //! The `TxMerkleNode` type.
 
-#[cfg(not(feature = "hex"))]
+use core::convert::Infallible;
 use core::fmt;
 #[cfg(feature = "hex")]
 use core::str;
@@ -12,6 +12,7 @@ use arbitrary::{Arbitrary, Unstructured};
 use hashes::sha256d;
 #[cfg(feature = "hex")]
 use hex::FromHex as _;
+use internals::write_err;
 
 /// A hash of the Merkle tree branch or root for transactions.
 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
@@ -35,3 +36,62 @@ impl encoding::Encodable for TxMerkleNode {
         TxMerkleNodeEncoder(encoding::ArrayEncoder::without_length_prefix(self.to_byte_array()))
     }
 }
+
+/// The decoder for the [`TxMerkleNode`] type.
+pub struct TxMerkleNodeDecoder(encoding::ArrayDecoder<32>);
+
+impl TxMerkleNodeDecoder {
+    /// Constructs a new [`TxMerkleNode`] decoder.
+    pub fn new() -> Self { Self(encoding::ArrayDecoder::new()) }
+}
+
+impl Default for TxMerkleNodeDecoder {
+    fn default() -> Self { Self::new() }
+}
+
+impl encoding::Decoder for TxMerkleNodeDecoder {
+    type Output = TxMerkleNode;
+    type Error = TxMerkleNodeDecoderError;
+
+    #[inline]
+    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<bool, Self::Error> {
+        Ok(self.0.push_bytes(bytes)?)
+    }
+
+    #[inline]
+    fn end(self) -> Result<Self::Output, Self::Error> {
+        let a = self.0.end()?;
+        Ok(TxMerkleNode::from_byte_array(a))
+    }
+
+    #[inline]
+    fn read_limit(&self) -> usize { self.0.read_limit() }
+}
+
+impl encoding::Decodable for TxMerkleNode {
+    type Decoder = TxMerkleNodeDecoder;
+    fn decoder() -> Self::Decoder { TxMerkleNodeDecoder(encoding::ArrayDecoder::<32>::new()) }
+}
+
+/// An error consensus decoding an `TxMerkleNode`.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct TxMerkleNodeDecoderError(encoding::UnexpectedEofError);
+
+impl From<Infallible> for TxMerkleNodeDecoderError {
+    fn from(never: Infallible) -> Self { match never {} }
+}
+
+impl From<encoding::UnexpectedEofError> for TxMerkleNodeDecoderError {
+    fn from(e: encoding::UnexpectedEofError) -> Self { Self(e) }
+}
+
+impl fmt::Display for TxMerkleNodeDecoderError {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write_err!(f, "sequence decoder error"; self.0)
+    }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for TxMerkleNodeDecoderError {
+    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> { Some(&self.0) }
+}
diff --git a/primitives/src/lib.rs b/primitives/src/lib.rs
index 1d488901..589b3d39 100644
--- a/primitives/src/lib.rs
+++ b/primitives/src/lib.rs
@@ -62,7 +62,7 @@ pub use units::{
     parse_int,
     result::{self, NumOpResult},
     sequence::{self, Sequence},
-    time::{self, BlockTime},
+    time::{self, BlockTime, BlockTimeDecoder, BlockTimeDecoderError},
     weight::{self, Weight},
 };
 
diff --git a/primitives/src/pow.rs b/primitives/src/pow.rs
index f21f9f97..63aec1b5 100644
--- a/primitives/src/pow.rs
+++ b/primitives/src/pow.rs
@@ -2,8 +2,11 @@
 
 //! Proof-of-work related integer types.
 
+use core::convert::Infallible;
 use core::fmt;
 
+use internals::write_err;
+
 /// Encoding of 256-bit target as 32-bit float.
 ///
 /// This is used to encode a target into the block header. Satoshi made this part of consensus code
@@ -62,6 +65,65 @@ impl encoding::Encodable for CompactTarget {
     }
 }
 
+/// The decoder for the [`CompactTarget`] type.
+pub struct CompactTargetDecoder(encoding::ArrayDecoder<4>);
+
+impl CompactTargetDecoder {
+    /// Constructs a new [`CompactTarget`] decoder.
+    pub fn new() -> Self { Self(encoding::ArrayDecoder::new()) }
+}
+
+impl Default for CompactTargetDecoder {
+    fn default() -> Self { Self::new() }
+}
+
+impl encoding::Decoder for CompactTargetDecoder {
+    type Output = CompactTarget;
+    type Error = CompactTargetDecoderError;
+
+    #[inline]
+    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<bool, Self::Error> {
+        Ok(self.0.push_bytes(bytes)?)
+    }
+
+    #[inline]
+    fn end(self) -> Result<Self::Output, Self::Error> {
+        let n = u32::from_le_bytes(self.0.end()?);
+        Ok(CompactTarget::from_consensus(n))
+    }
+
+    #[inline]
+    fn read_limit(&self) -> usize { self.0.read_limit() }
+}
+
+impl encoding::Decodable for CompactTarget {
+    type Decoder = CompactTargetDecoder;
+    fn decoder() -> Self::Decoder { CompactTargetDecoder(encoding::ArrayDecoder::<4>::new()) }
+}
+
+/// An error consensus decoding an `CompactTarget`.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct CompactTargetDecoderError(encoding::UnexpectedEofError);
+
+impl From<Infallible> for CompactTargetDecoderError {
+    fn from(never: Infallible) -> Self { match never {} }
+}
+
+impl From<encoding::UnexpectedEofError> for CompactTargetDecoderError {
+    fn from(e: encoding::UnexpectedEofError) -> Self { Self(e) }
+}
+
+impl fmt::Display for CompactTargetDecoderError {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write_err!(f, "sequence decoder error"; self.0)
+    }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for CompactTargetDecoderError {
+    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> { Some(&self.0) }
+}
+
 #[cfg(test)]
 mod tests {
     #[cfg(feature = "alloc")]
diff --git a/primitives/src/script/borrowed.rs b/primitives/src/script/borrowed.rs
index 31c962ea..940db85f 100644
--- a/primitives/src/script/borrowed.rs
+++ b/primitives/src/script/borrowed.rs
@@ -165,12 +165,10 @@ impl<T> Encodable for Script<T> {
         Self: 'a;
 
     fn encoder(&self) -> Self::Encoder<'_> {
-        ScriptEncoder(
-            Encoder2::new(
-                CompactSizeEncoder::new(self.as_bytes().len()),
-                BytesEncoder::without_length_prefix(self.as_bytes())
-            )
-        )
+        ScriptEncoder(Encoder2::new(
+            CompactSizeEncoder::new(self.as_bytes().len()),
+            BytesEncoder::without_length_prefix(self.as_bytes()),
+        ))
     }
 }
 
diff --git a/primitives/src/script/mod.rs b/primitives/src/script/mod.rs
index 824b5444..c81d4beb 100644
--- a/primitives/src/script/mod.rs
+++ b/primitives/src/script/mod.rs
@@ -24,7 +24,7 @@ use crate::prelude::{Borrow, BorrowMut, Box, Cow, ToOwned, Vec};
 #[doc(inline)]
 pub use self::{
     borrowed::{Script, ScriptEncoder},
-    owned::ScriptBuf,
+    owned::{ScriptBuf, ScriptBufDecoder, ScriptBufDecoderError},
     tag::{Tag, RedeemScriptTag, ScriptPubKeyTag, ScriptSigTag, TapScriptTag, WitnessScriptTag},
 };
 #[doc(inline)]
@@ -47,9 +47,15 @@ pub type ScriptSig = Script<ScriptSigTag>;
 /// A `scriptPubKey` (locking script).
 pub type ScriptPubKeyBuf = ScriptBuf<ScriptPubKeyTag>;
 
+/// A `scriptPubKey` decoder.
+pub type ScriptPubKeyBufDecoder = ScriptBufDecoder<ScriptPubKeyTag>;
+
 /// A script signature (scriptSig).
 pub type ScriptSigBuf = ScriptBuf<ScriptSigTag>;
 
+/// A `scriptSig` decoder.
+pub type ScriptSigBufDecoder = ScriptBufDecoder<ScriptSigTag>;
+
 /// A Segwit v1 Taproot script.
 pub type TapScriptBuf = ScriptBuf<TapScriptTag>;
 
diff --git a/primitives/src/script/owned.rs b/primitives/src/script/owned.rs
index fcb1d67a..eef5a5aa 100644
--- a/primitives/src/script/owned.rs
+++ b/primitives/src/script/owned.rs
@@ -1,10 +1,14 @@
 // SPDX-License-Identifier: CC0-1.0
 
+use core::convert::Infallible;
+use core::fmt;
 use core::marker::PhantomData;
 use core::ops::{Deref, DerefMut};
 
 #[cfg(feature = "arbitrary")]
 use arbitrary::{Arbitrary, Unstructured};
+use encoding::{ByteVecDecoder, ByteVecDecoderError, Decodable, Decoder};
+use internals::write_err;
 
 use super::Script;
 use crate::prelude::{Box, Vec};
@@ -146,6 +150,60 @@ impl<T> DerefMut for ScriptBuf<T> {
     fn deref_mut(&mut self) -> &mut Self::Target { self.as_mut_script() }
 }
 
+/// The decoder for the [`ScriptBuf`] type.
+pub struct ScriptBufDecoder<T>(ByteVecDecoder, PhantomData<T>);
+
+impl<T> ScriptBufDecoder<T> {
+    /// Constructs a new [`ScriptBuf`] decoder.
+    pub fn new() -> Self { Self(ByteVecDecoder::new(), PhantomData) }
+}
+
+impl<T> Default for ScriptBufDecoder<T> {
+    fn default() -> Self { Self::new() }
+}
+
+impl<T> Decoder for ScriptBufDecoder<T> {
+    type Output = ScriptBuf<T>;
+    type Error = ScriptBufDecoderError;
+
+    #[inline]
+    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<bool, Self::Error> {
+        Ok(self.0.push_bytes(bytes)?)
+    }
+
+    #[inline]
+    fn end(self) -> Result<Self::Output, Self::Error> { Ok(ScriptBuf::from_bytes(self.0.end()?)) }
+
+    #[inline]
+    fn read_limit(&self) -> usize { self.0.read_limit() }
+}
+
+impl<T> Decodable for ScriptBuf<T> {
+    type Decoder = ScriptBufDecoder<T>;
+    fn decoder() -> Self::Decoder { ScriptBufDecoder(ByteVecDecoder::new(), PhantomData) }
+}
+
+/// An error consensus decoding a `ScriptBuf<T>`.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct ScriptBufDecoderError(ByteVecDecoderError);
+
+impl From<Infallible> for ScriptBufDecoderError {
+    fn from(never: Infallible) -> Self { match never {} }
+}
+
+impl From<ByteVecDecoderError> for ScriptBufDecoderError {
+    fn from(e: ByteVecDecoderError) -> Self { Self(e) }
+}
+
+impl fmt::Display for ScriptBufDecoderError {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write_err!(f, "decoder error"; self.0) }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for ScriptBufDecoderError {
+    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> { Some(&self.0) }
+}
+
 #[cfg(feature = "arbitrary")]
 impl<'a, T> Arbitrary<'a> for ScriptBuf<T> {
     #[inline]
@@ -163,6 +221,8 @@ mod tests {
     #[cfg(feature = "alloc")]
     use alloc::vec;
 
+    use super::*;
+
     #[test]
     fn script_buf_from_bytes() {
         let bytes = vec![1, 2, 3];
@@ -222,4 +282,31 @@ mod tests {
         script.reserve_exact(10);
         assert!(script.capacity() >= 10);
     }
+
+    #[test]
+    fn script_consensus_decode_empty() {
+        let bytes = vec![0_u8];
+        let mut push = bytes.as_slice();
+        let mut decoder = ScriptBuf::decoder();
+        decoder.push_bytes(&mut push).unwrap();
+
+        let got = decoder.end().unwrap();
+        let want = ScriptBuf::new();
+
+        assert_eq!(got, want);
+    }
+
+    #[test]
+    fn script_consensus_decode_empty_with_more_data() {
+        // An empty script sig with a bunch of unrelated data at the end.
+        let bytes = vec![0x00_u8, 0xff, 0xff, 0xff, 0xff];
+        let mut push = bytes.as_slice();
+        let mut decoder = ScriptBuf::decoder();
+        decoder.push_bytes(&mut push).unwrap();
+
+        let got = decoder.end().unwrap();
+        let want = ScriptBuf::new();
+
+        assert_eq!(got, want);
+    }
 }
diff --git a/primitives/src/transaction.rs b/primitives/src/transaction.rs
index b3a049fb..89df54aa 100644
--- a/primitives/src/transaction.rs
+++ b/primitives/src/transaction.rs
@@ -10,23 +10,23 @@
 //!
 //! This module provides the structures and functions needed to support transactions.
 
-#[cfg(feature = "alloc")]
-use core::cmp;
-#[cfg(feature = "alloc")]
-#[cfg(feature = "hex")]
 use core::convert::Infallible;
 use core::fmt;
+#[cfg(feature = "alloc")]
+use core::{cmp, mem};
 
 #[cfg(feature = "arbitrary")]
 use arbitrary::{Arbitrary, Unstructured};
-use encoding::{ArrayEncoder, BytesEncoder, Encodable, Encoder2};
+use encoding::{ArrayEncoder, BytesEncoder, Encodable, Encoder2, UnexpectedEofError};
 #[cfg(feature = "alloc")]
-use encoding::{CompactSizeEncoder, Encoder, Encoder3, Encoder6, SliceEncoder};
+use encoding::{
+    CompactSizeEncoder, Decodable, Decoder, Decoder2, Decoder3, Encoder, Encoder3, Encoder6,
+    SliceEncoder, VecDecoder, VecDecoderError,
+};
 #[cfg(feature = "alloc")]
 use hashes::sha256d;
 #[cfg(feature = "alloc")]
 use internals::compact_size;
-#[cfg(feature = "hex")]
 use internals::write_err;
 #[cfg(feature = "serde")]
 use serde::{de, Deserialize, Deserializer, Serialize, Serializer};
@@ -34,23 +34,25 @@ use serde::{de, Deserialize, Deserializer, Serialize, Serializer};
 use units::parse_int;
 
 #[cfg(feature = "alloc")]
-use crate::amount::AmountEncoder;
+use crate::amount::{AmountDecoder, AmountDecoderError, AmountEncoder};
 #[cfg(feature = "alloc")]
-use crate::locktime::absolute::LockTimeEncoder;
+use crate::locktime::absolute::{LockTimeDecoder, LockTimeDecoderError, LockTimeEncoder};
 #[cfg(feature = "alloc")]
 use crate::prelude::Vec;
 #[cfg(feature = "alloc")]
-use crate::script::ScriptEncoder;
+use crate::script::{
+    ScriptBufDecoderError, ScriptEncoder, ScriptPubKeyBufDecoder, ScriptSigBufDecoder,
+};
 #[cfg(feature = "alloc")]
-use crate::sequence::SequenceEncoder;
+use crate::sequence::{SequenceDecoder, SequenceDecoderError, SequenceEncoder};
 #[cfg(feature = "alloc")]
-use crate::witness::WitnessEncoder;
+use crate::witness::{WitnessDecoder, WitnessDecoderError, WitnessEncoder};
 #[cfg(feature = "alloc")]
 use crate::{absolute, Amount, ScriptPubKeyBuf, ScriptSigBuf, Sequence, Weight, Witness};
 
 #[rustfmt::skip]            // Keep public re-exports separate.
 #[doc(inline)]
-pub use crate::hash_types::{Ntxid, Txid, Wtxid};
+pub use crate::hash_types::{Ntxid, Txid, Wtxid, BlockHashDecoder, BlockHashDecoderError, TxMerkleNodeDecoder, TxMerkleNodeDecoderError};
 
 /// Bitcoin transaction.
 ///
@@ -355,6 +357,388 @@ impl Encodable for Transaction {
     }
 }
 
+/// The decoder for the [`Transaction`] type.
+#[cfg(feature = "alloc")]
+pub struct TransactionDecoder {
+    state: TransactionDecoderState,
+}
+
+#[cfg(feature = "alloc")]
+impl TransactionDecoder {
+    /// Constructs a new [`TransactionDecoder`].
+    pub fn new() -> Self { Self { state: TransactionDecoderState::Version(VersionDecoder::new()) } }
+}
+
+#[cfg(feature = "alloc")]
+impl Default for TransactionDecoder {
+    fn default() -> Self { Self::new() }
+}
+
+#[cfg(feature = "alloc")]
+impl TransactionDecoderState {
+    #[track_caller]
+    fn version_transition(&mut self) -> VersionDecoder {
+        match mem::replace(self, TransactionDecoderState::Transitioning) {
+            TransactionDecoderState::Version(decoder) => decoder,
+            _ => panic!("transition called on invalid state"),
+        }
+    }
+
+    #[track_caller]
+    fn inputs_transition(&mut self) -> VecDecoder<TxIn> {
+        match mem::replace(self, TransactionDecoderState::Transitioning) {
+            TransactionDecoderState::Inputs(_, _, decoder) => decoder,
+            _ => panic!("transition called on invalid state"),
+        }
+    }
+
+    #[track_caller]
+    fn outputs_transition(&mut self) -> (Vec<TxIn>, VecDecoder<TxOut>) {
+        match mem::replace(self, TransactionDecoderState::Transitioning) {
+            TransactionDecoderState::Outputs(_, inputs, _, decoder) => (inputs, decoder),
+            _ => panic!("transition called on invalid state"),
+        }
+    }
+
+    #[track_caller]
+    fn witness_transition(&mut self) -> (Vec<TxIn>, Vec<TxOut>, WitnessDecoder) {
+        match mem::replace(self, TransactionDecoderState::Transitioning) {
+            TransactionDecoderState::Witnesses(_, inputs, outputs, _, decoder) =>
+                (inputs, outputs, decoder),
+            _ => panic!("transition called on invalid state"),
+        }
+    }
+
+    #[track_caller]
+    fn lock_time_transition(&mut self) -> (Vec<TxIn>, Vec<TxOut>, LockTimeDecoder) {
+        match mem::replace(self, TransactionDecoderState::Transitioning) {
+            TransactionDecoderState::LockTime(_, inputs, outputs, decoder) =>
+                (inputs, outputs, decoder),
+            _ => panic!("transition called on invalid state"),
+        }
+    }
+}
+
+#[cfg(feature = "alloc")]
+#[allow(clippy::too_many_lines)] // TODO: Can we clean this up?
+impl Decoder for TransactionDecoder {
+    type Output = Transaction;
+    type Error = TransactionDecoderError;
+
+    #[inline]
+    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<bool, Self::Error> {
+        use {
+            TransactionDecoderError as E, TransactionDecoderErrorInner as Inner,
+            TransactionDecoderState as State,
+        };
+
+        loop {
+            match &mut self.state {
+                State::Version(decoder) => {
+                    if decoder.push_bytes(bytes)? {
+                        // Still more bytes required.
+                        return Ok(true);
+                    }
+                    let decoder = self.state.version_transition();
+                    let version = decoder.end()?;
+                    self.state = State::Inputs(version, Attempt::First, VecDecoder::<TxIn>::new());
+                }
+                State::Inputs(version, attempt, decoder) => {
+                    if decoder.push_bytes(bytes)? {
+                        return Ok(true);
+                    }
+                    // Copy the state because we need mutable access to self to transition.
+                    let version = *version;
+                    let attempt = *attempt;
+
+                    let decoder = self.state.inputs_transition();
+                    let inputs = decoder.end()?;
+
+                    if Attempt::First == attempt {
+                        if inputs.is_empty() {
+                            self.state = State::SegwitFlag(version);
+                        } else {
+                            self.state = State::Outputs(
+                                version,
+                                inputs,
+                                IsSegwit::No,
+                                VecDecoder::<TxOut>::new(),
+                            );
+                        }
+                    } else {
+                        self.state = State::Outputs(
+                            version,
+                            inputs,
+                            IsSegwit::Yes,
+                            VecDecoder::<TxOut>::new(),
+                        );
+                    }
+                }
+                State::SegwitFlag(version) => {
+                    if bytes.is_empty() {
+                        return Ok(true);
+                    }
+                    let version = *version;
+
+                    let segwit_flag = bytes[0];
+                    *bytes = &bytes[1..];
+
+                    if segwit_flag != 1 {
+                        return Err(E(Inner::UnsupportedSegwitFlag(segwit_flag)));
+                    }
+                    self.state = State::Inputs(version, Attempt::Second, VecDecoder::<TxIn>::new());
+                }
+                State::Outputs(version, _, is_segwit, decoder) => {
+                    if decoder.push_bytes(bytes)? {
+                        return Ok(true);
+                    }
+                    // These types are Copy, so we can deref them but does not work for vectors.
+                    let version = *version;
+                    let is_segwit = *is_segwit;
+
+                    // We get the inputs vector here instead of in the pattern match because I
+                    // couldn't find another way to get it out of behind the mutable reference.
+                    let (inputs, decoder) = self.state.outputs_transition();
+                    let outputs = decoder.end()?;
+                    if is_segwit == IsSegwit::Yes {
+                        self.state = State::Witnesses(
+                            version,
+                            inputs,
+                            outputs,
+                            Iteration(0),
+                            WitnessDecoder::new(),
+                        );
+                    } else {
+                        self.state =
+                            State::LockTime(version, inputs, outputs, LockTimeDecoder::new());
+                    }
+                }
+                State::Witnesses(version, _, _, iteration, decoder) => {
+                    if decoder.push_bytes(bytes)? {
+                        return Ok(true);
+                    }
+                    let version = *version;
+                    let iteration = iteration.0;
+
+                    let (mut inputs, outputs, decoder) = self.state.witness_transition();
+                    inputs[iteration].witness = decoder.end()?;
+                    if iteration < inputs.len() - 1 {
+                        self.state = State::Witnesses(
+                            version,
+                            inputs,
+                            outputs,
+                            Iteration(iteration + 1),
+                            WitnessDecoder::new(),
+                        );
+                    } else {
+                        if !inputs.is_empty() && inputs.iter().all(|input| input.witness.is_empty())
+                        {
+                            return Err(E(Inner::NoWitnesses));
+                        }
+                        self.state =
+                            State::LockTime(version, inputs, outputs, LockTimeDecoder::new());
+                    }
+                }
+                State::LockTime(version, _, _, decoder) => {
+                    if decoder.push_bytes(bytes)? {
+                        return Ok(true);
+                    }
+                    let version = *version;
+
+                    let (inputs, outputs, decoder) = self.state.lock_time_transition();
+                    let lock_time = decoder.end()?;
+                    self.state = State::Done(Transaction { version, lock_time, inputs, outputs });
+                    return Ok(false);
+                }
+                State::Done(..) => return Ok(false),
+                State::Transitioning => {
+                    panic!("use of decoder in transitioning state");
+                }
+            }
+        }
+    }
+
+    #[inline]
+    fn end(self) -> Result<Self::Output, Self::Error> {
+        use TransactionDecoderState as State;
+
+        match self.state {
+            State::Version(_) => panic!("tried to end decoder in state: Version"),
+            State::Inputs(..) => panic!("tried to end decoder in state: Inputs"),
+            State::SegwitFlag(..) => panic!("tried to end decoder in state: SegwitFlag"),
+            State::Outputs(..) => panic!("tried to end decoder in state: Outputs"),
+            State::Witnesses(..) => panic!("tried to end decoder in state: Witnesses"),
+            State::LockTime(..) => panic!("tried to end decoder in state: LockTime"),
+            State::Done(tx) => Ok(tx),
+            State::Transitioning => {
+                panic!("use of decoder in transitioning state");
+            }
+        }
+    }
+
+    #[inline]
+    fn read_limit(&self) -> usize {
+        use TransactionDecoderState as State;
+
+        match &self.state {
+            State::Version(decoder) => decoder.read_limit(),
+            State::Inputs(_, _, decoder) => decoder.read_limit(),
+            State::SegwitFlag(_) => 1,
+            State::Outputs(_, _, _, decoder) => decoder.read_limit(),
+            State::Witnesses(_, _, _, _, decoder) => decoder.read_limit(),
+            State::LockTime(_, _, _, decoder) => decoder.read_limit(),
+            State::Done(_) => 0,
+            State::Transitioning => panic!("use of decoder in transitioning state"),
+        }
+    }
+}
+
+#[cfg(feature = "alloc")]
+impl Decodable for Transaction {
+    type Decoder = TransactionDecoder;
+    fn decoder() -> Self::Decoder { TransactionDecoder::new() }
+}
+
+/// The state of the transiting decoder.
+#[cfg(feature = "alloc")]
+enum TransactionDecoderState {
+    /// Decoding the transaction version.
+    Version(VersionDecoder),
+    /// Decoding the transaction inputs.
+    Inputs(Version, Attempt, VecDecoder<TxIn>),
+    /// Decoding the segwit flag.
+    SegwitFlag(Version),
+    /// Decoding the transaction outputs.
+    Outputs(Version, Vec<TxIn>, IsSegwit, VecDecoder<TxOut>),
+    /// Decoding the segwit transaction witnesses.
+    Witnesses(Version, Vec<TxIn>, Vec<TxOut>, Iteration, WitnessDecoder),
+    /// Decoding the transaction lock time.
+    LockTime(Version, Vec<TxIn>, Vec<TxOut>, LockTimeDecoder),
+    /// Done decoding the [`Transaction`].
+    Done(Transaction),
+    /// Temporary state during transitions, should never be observed.
+    Transitioning,
+}
+
+/// Boolean used to track number of times we have attempted to decode the inputs vector.
+#[cfg(feature = "alloc")]
+#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+enum Attempt {
+    /// First time reading inputs.
+    First,
+    /// Second time reading inputs.
+    Second,
+}
+
+/// Boolean used to track whether or not this transaction uses segwit encoding.
+#[cfg(feature = "alloc")]
+#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+enum IsSegwit {
+    /// Yes so uses segwit encoding.
+    Yes,
+    /// No segwit flag, marker, or witnesses.
+    No,
+}
+
+/// How many times we have state transitioned to encoding a witness (zero-based).
+#[cfg(feature = "alloc")]
+#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+struct Iteration(usize);
+
+/// An error consensus decoding a `Transaction`.
+#[cfg(feature = "alloc")]
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct TransactionDecoderError(TransactionDecoderErrorInner);
+
+#[cfg(feature = "alloc")]
+#[derive(Debug, Clone, PartialEq, Eq)]
+enum TransactionDecoderErrorInner {
+    /// Error while decoding the `version`.
+    Version(VersionDecoderError),
+    /// We only support segwit flag value 0x01.
+    UnsupportedSegwitFlag(u8),
+    /// Error while decoding the `inputs`.
+    Inputs(VecDecoderError<TxInDecoderError>),
+    /// Error while decoding the `outputs`.
+    Outputs(VecDecoderError<TxOutDecoderError>),
+    /// Error while decoding one of the witnesses.
+    Witness(WitnessDecoderError),
+    /// Non-empty Segwit transaction with no witnesses.
+    NoWitnesses,
+    /// Error while decoding the `lock_time`.
+    LockTime(LockTimeDecoderError),
+}
+
+#[cfg(feature = "alloc")]
+impl From<Infallible> for TransactionDecoderError {
+    fn from(never: Infallible) -> Self { match never {} }
+}
+
+#[cfg(feature = "alloc")]
+impl From<VersionDecoderError> for TransactionDecoderError {
+    fn from(e: VersionDecoderError) -> Self { Self(TransactionDecoderErrorInner::Version(e)) }
+}
+
+#[cfg(feature = "alloc")]
+impl From<VecDecoderError<TxInDecoderError>> for TransactionDecoderError {
+    fn from(e: VecDecoderError<TxInDecoderError>) -> Self {
+        Self(TransactionDecoderErrorInner::Inputs(e))
+    }
+}
+
+#[cfg(feature = "alloc")]
+impl From<VecDecoderError<TxOutDecoderError>> for TransactionDecoderError {
+    fn from(e: VecDecoderError<TxOutDecoderError>) -> Self {
+        Self(TransactionDecoderErrorInner::Outputs(e))
+    }
+}
+
+#[cfg(feature = "alloc")]
+impl From<WitnessDecoderError> for TransactionDecoderError {
+    fn from(e: WitnessDecoderError) -> Self { Self(TransactionDecoderErrorInner::Witness(e)) }
+}
+
+#[cfg(feature = "alloc")]
+impl From<LockTimeDecoderError> for TransactionDecoderError {
+    fn from(e: LockTimeDecoderError) -> Self { Self(TransactionDecoderErrorInner::LockTime(e)) }
+}
+
+#[cfg(feature = "alloc")]
+impl fmt::Display for TransactionDecoderError {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        use TransactionDecoderErrorInner as E;
+
+        match self.0 {
+            E::Version(ref e) => write_err!(f, "transaction decoder error"; e),
+            E::UnsupportedSegwitFlag(v) =>
+                write!(f, "we only support segwit flag value 0x01: {}", v),
+            E::Inputs(ref e) => write_err!(f, "transaction decoder error"; e),
+            E::Outputs(ref e) => write_err!(f, "transaction decoder error"; e),
+            E::Witness(ref e) => write_err!(f, "transaction decoder error"; e),
+            E::NoWitnesses => write!(f, "non-empty Segwit transaction with no witnesses"),
+            E::LockTime(ref e) => write_err!(f, "transaction decoder error"; e),
+        }
+    }
+}
+
+#[cfg(feature = "std")]
+#[cfg(feature = "alloc")]
+impl std::error::Error for TransactionDecoderError {
+    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
+        use TransactionDecoderErrorInner as E;
+
+        match self.0 {
+            E::Version(ref e) => Some(e),
+            E::UnsupportedSegwitFlag(_) => None,
+            E::Inputs(ref e) => Some(e),
+            E::Outputs(ref e) => Some(e),
+            E::Witness(ref e) => Some(e),
+            E::NoWitnesses => None,
+            E::LockTime(ref e) => Some(e),
+        }
+    }
+}
+
 /// Bitcoin transaction input.
 ///
 /// It contains the location of the previous transaction's output,
@@ -474,6 +858,107 @@ impl Encoder for WitnessesEncoder<'_> {
     }
 }
 
+/// The decoder for the [`TxIn`] type.
+#[cfg(feature = "alloc")]
+pub struct TxInDecoder(
+    Decoder3<OutPointDecoder, ScriptSigBufDecoder, SequenceDecoder, TxInDecoderError>,
+);
+
+#[cfg(feature = "alloc")]
+impl Decoder for TxInDecoder {
+    type Output = TxIn;
+    type Error = TxInDecoderError;
+
+    #[inline]
+    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<bool, Self::Error> {
+        self.0.push_bytes(bytes)
+    }
+
+    #[inline]
+    fn end(self) -> Result<Self::Output, Self::Error> {
+        let (previous_output, script_sig, sequence) = self.0.end()?;
+        Ok(TxIn { previous_output, script_sig, sequence, witness: Witness::default() })
+    }
+
+    #[inline]
+    fn read_limit(&self) -> usize { self.0.read_limit() }
+}
+
+#[cfg(feature = "alloc")]
+impl Decodable for TxIn {
+    type Decoder = TxInDecoder;
+    fn decoder() -> Self::Decoder {
+        TxInDecoder(Decoder3::new(
+            OutPointDecoder::new(),
+            ScriptSigBufDecoder::new(),
+            SequenceDecoder::new(),
+        ))
+    }
+}
+
+/// An error consensus decoding a `TxIn`.
+#[cfg(feature = "alloc")]
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct TxInDecoderError(TxInDecoderErrorInner);
+
+#[cfg(feature = "alloc")]
+#[derive(Debug, Clone, PartialEq, Eq)]
+enum TxInDecoderErrorInner {
+    /// Error while decoding the `previous_output`.
+    PreviousOutput(OutPointDecoderError),
+    /// Error while decoding the `script_sig`.
+    ScriptSig(ScriptBufDecoderError),
+    /// Error while decoding the `sequence`.
+    Sequence(SequenceDecoderError),
+}
+
+#[cfg(feature = "alloc")]
+impl From<Infallible> for TxInDecoderError {
+    fn from(never: Infallible) -> Self { match never {} }
+}
+
+#[cfg(feature = "alloc")]
+impl From<OutPointDecoderError> for TxInDecoderError {
+    fn from(e: OutPointDecoderError) -> Self { Self(TxInDecoderErrorInner::PreviousOutput(e)) }
+}
+
+#[cfg(feature = "alloc")]
+impl From<ScriptBufDecoderError> for TxInDecoderError {
+    fn from(e: ScriptBufDecoderError) -> Self { Self(TxInDecoderErrorInner::ScriptSig(e)) }
+}
+
+#[cfg(feature = "alloc")]
+impl From<SequenceDecoderError> for TxInDecoderError {
+    fn from(e: SequenceDecoderError) -> Self { Self(TxInDecoderErrorInner::Sequence(e)) }
+}
+
+#[cfg(feature = "alloc")]
+impl fmt::Display for TxInDecoderError {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        use TxInDecoderErrorInner as E;
+
+        match self.0 {
+            E::PreviousOutput(ref e) => write_err!(f, "txin decoder error"; e),
+            E::ScriptSig(ref e) => write_err!(f, "txin decoder error"; e),
+            E::Sequence(ref e) => write_err!(f, "txin decoder error"; e),
+        }
+    }
+}
+
+#[cfg(feature = "alloc")]
+#[cfg(feature = "std")]
+impl std::error::Error for TxInDecoderError {
+    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
+        use TxInDecoderErrorInner as E;
+
+        match self.0 {
+            E::PreviousOutput(ref e) => Some(e),
+            E::ScriptSig(ref e) => Some(e),
+            E::Sequence(ref e) => Some(e),
+        }
+    }
+}
+
 /// Bitcoin transaction output.
 ///
 /// Defines new coins to be created as a result of the transaction,
@@ -512,6 +997,92 @@ impl Encodable for TxOut {
     }
 }
 
+/// The decoder for the [`TxOut`] type.
+#[cfg(feature = "alloc")]
+pub struct TxOutDecoder(Decoder2<AmountDecoder, ScriptPubKeyBufDecoder, TxOutDecoderError>);
+
+#[cfg(feature = "alloc")]
+impl Decoder for TxOutDecoder {
+    type Output = TxOut;
+    type Error = TxOutDecoderError;
+
+    #[inline]
+    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<bool, Self::Error> {
+        Ok(self.0.push_bytes(bytes)?)
+    }
+
+    #[inline]
+    fn end(self) -> Result<Self::Output, Self::Error> {
+        let (amount, script_pubkey) = self.0.end()?;
+        Ok(TxOut { amount, script_pubkey })
+    }
+
+    #[inline]
+    fn read_limit(&self) -> usize { self.0.read_limit() }
+}
+
+#[cfg(feature = "alloc")]
+impl Decodable for TxOut {
+    type Decoder = TxOutDecoder;
+    fn decoder() -> Self::Decoder {
+        TxOutDecoder(Decoder2::new(AmountDecoder::new(), ScriptPubKeyBufDecoder::new()))
+    }
+}
+
+/// An error consensus decoding a `TxOut`.
+#[cfg(feature = "alloc")]
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct TxOutDecoderError(TxOutDecoderErrorInner);
+
+/// An error consensus decoding a `TxOut`.
+#[cfg(feature = "alloc")]
+#[derive(Debug, Clone, PartialEq, Eq)]
+enum TxOutDecoderErrorInner {
+    /// Error while decoding the `amount`.
+    Amount(AmountDecoderError),
+    /// Error while decoding the `script_pubkey`.
+    ScriptPubKey(ScriptBufDecoderError),
+}
+
+#[cfg(feature = "alloc")]
+impl From<Infallible> for TxOutDecoderError {
+    fn from(never: Infallible) -> Self { match never {} }
+}
+
+#[cfg(feature = "alloc")]
+impl From<AmountDecoderError> for TxOutDecoderError {
+    fn from(e: AmountDecoderError) -> Self { Self(TxOutDecoderErrorInner::Amount(e)) }
+}
+
+#[cfg(feature = "alloc")]
+impl From<ScriptBufDecoderError> for TxOutDecoderError {
+    fn from(e: ScriptBufDecoderError) -> Self { Self(TxOutDecoderErrorInner::ScriptPubKey(e)) }
+}
+
+#[cfg(feature = "alloc")]
+impl fmt::Display for TxOutDecoderError {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        use TxOutDecoderErrorInner as E;
+
+        match self.0 {
+            E::Amount(ref e) => write_err!(f, "txout decoder error"; e),
+            E::ScriptPubKey(ref e) => write_err!(f, "txout decoder error"; e),
+        }
+    }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for TxOutDecoderError {
+    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
+        use TxOutDecoderErrorInner as E;
+
+        match self.0 {
+            E::Amount(ref e) => Some(e),
+            E::ScriptPubKey(ref e) => Some(e),
+        }
+    }
+}
+
 /// A reference to a transaction output.
 ///
 /// # Bitcoin Core References
@@ -603,6 +1174,67 @@ fn parse_vout(s: &str) -> Result<u32, ParseOutPointError> {
     parse_int::int_from_str(s).map_err(ParseOutPointError::Vout)
 }
 
+/// The decoder for the [`OutPoint`] type.
+// 32 for the txid + 4 for the vout
+pub struct OutPointDecoder(encoding::ArrayDecoder<36>);
+
+impl OutPointDecoder {
+    /// Constructs a new [`OutPoint`] decoder.
+    pub fn new() -> Self { Self(encoding::ArrayDecoder::new()) }
+}
+
+impl Default for OutPointDecoder {
+    fn default() -> Self { Self::new() }
+}
+
+impl encoding::Decoder for OutPointDecoder {
+    type Output = OutPoint;
+    type Error = OutPointDecoderError;
+
+    #[inline]
+    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<bool, Self::Error> {
+        self.0.push_bytes(bytes).map_err(OutPointDecoderError)
+    }
+
+    #[inline]
+    fn end(self) -> Result<Self::Output, Self::Error> {
+        let encoded = self.0.end().map_err(OutPointDecoderError)?;
+
+        let mut txid_buf = [0_u8; 32];
+        txid_buf.copy_from_slice(&encoded[..32]);
+        let txid = Txid::from_byte_array(txid_buf);
+
+        let mut vout_buf = [0_u8; 4];
+        vout_buf.copy_from_slice(&encoded[32..]);
+        let vout = u32::from_le_bytes(vout_buf);
+
+        Ok(OutPoint { txid, vout })
+    }
+
+    #[inline]
+    fn read_limit(&self) -> usize { self.0.read_limit() }
+}
+
+impl encoding::Decodable for OutPoint {
+    type Decoder = OutPointDecoder;
+    fn decoder() -> Self::Decoder { OutPointDecoder::default() }
+}
+
+/// Error while decoding an `OutPoint`.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct OutPointDecoderError(UnexpectedEofError);
+
+impl core::fmt::Display for OutPointDecoderError {
+    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+        write_err!(f, "out point decoder error"; self.0)
+    }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for OutPointDecoderError {
+    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> { Some(&self.0) }
+}
+
 #[cfg(feature = "serde")]
 impl Serialize for OutPoint {
     fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
@@ -836,6 +1468,62 @@ impl encoding::Encodable for Version {
     }
 }
 
+/// The decoder for the [`Version`] type.
+pub struct VersionDecoder(encoding::ArrayDecoder<4>);
+
+impl VersionDecoder {
+    /// Constructs a new [`Version`] decoder.
+    pub fn new() -> Self { Self(encoding::ArrayDecoder::new()) }
+}
+
+impl Default for VersionDecoder {
+    fn default() -> Self { Self::new() }
+}
+
+impl encoding::Decoder for VersionDecoder {
+    type Output = Version;
+    type Error = VersionDecoderError;
+
+    #[inline]
+    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<bool, Self::Error> {
+        self.0.push_bytes(bytes).map_err(VersionDecoderError)
+    }
+
+    #[inline]
+    fn end(self) -> Result<Self::Output, Self::Error> {
+        let bytes = self.0.end().map_err(VersionDecoderError)?;
+        let n = u32::from_le_bytes(bytes);
+        Ok(Version::maybe_non_standard(n))
+    }
+
+    #[inline]
+    fn read_limit(&self) -> usize { self.0.read_limit() }
+}
+
+impl encoding::Decodable for Version {
+    type Decoder = VersionDecoder;
+    fn decoder() -> Self::Decoder { VersionDecoder(encoding::ArrayDecoder::<4>::new()) }
+}
+
+/// An error consensus decoding an `Version`.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct VersionDecoderError(encoding::UnexpectedEofError);
+
+impl From<Infallible> for VersionDecoderError {
+    fn from(never: Infallible) -> Self { match never {} }
+}
+
+impl fmt::Display for VersionDecoderError {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write_err!(f, "version decoder error"; self.0)
+    }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for VersionDecoderError {
+    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> { Some(&self.0) }
+}
+
 #[cfg(feature = "arbitrary")]
 #[cfg(feature = "alloc")]
 impl<'a> Arbitrary<'a> for Transaction {
@@ -894,10 +1582,13 @@ impl<'a> Arbitrary<'a> for Version {
 #[cfg(feature = "alloc")]
 #[cfg(test)]
 mod tests {
-    #[cfg(feature = "alloc")]
+    #[cfg(feature = "hex")]
+    use alloc::string::ToString;
     use alloc::{format, vec};
 
     use encoding::Encoder as _;
+    #[cfg(feature = "hex")]
+    use hex_lit::hex;
 
     use super::*;
     #[cfg(all(feature = "alloc", feature = "hex"))]
@@ -1446,4 +2137,77 @@ mod tests {
         // Exhausted
         assert_eq!(encoder.current_chunk(), None);
     }
+
+    #[test]
+    #[cfg(all(feature = "alloc", feature = "hex"))]
+    fn decode_segwit_transaction() {
+        let tx_bytes = hex!(
+            "02000000000101595895ea20179de87052b4046dfe6fd515860505d6511a9004cf12a1f93cac7c01000000\
+            00ffffffff01deb807000000000017a9140f3444e271620c736808aa7b33e370bd87cb5a078702483045022\
+            100fb60dad8df4af2841adc0346638c16d0b8035f5e3f3753b88db122e70c79f9370220756e6633b17fd271\
+            0e626347d28d60b0a2d6cbb41de51740644b9fb3ba7751040121028fa937ca8cba2197a37c007176ed89410\
+            55d3bcb8627d085e94553e62f057dcc00000000"
+        );
+        let mut decoder = Transaction::decoder();
+        let mut slice = tx_bytes.as_slice();
+        decoder.push_bytes(&mut slice).unwrap();
+        let tx = decoder.end().unwrap();
+
+        // All these tests aren't really needed because if they fail, the hash check at the end
+        // will also fail. But these will show you where the failure is so I'll leave them in.
+        assert_eq!(tx.version, Version::TWO);
+        assert_eq!(tx.inputs.len(), 1);
+        // In particular this one is easy to get backward -- in bitcoin hashes are encoded
+        // as little-endian 256-bit numbers rather than as data strings.
+        assert_eq!(
+            format!("{:x}", tx.inputs[0].previous_output.txid),
+            "7cac3cf9a112cf04901a51d605058615d56ffe6d04b45270e89d1720ea955859".to_string()
+        );
+        assert_eq!(tx.inputs[0].previous_output.vout, 1);
+        assert_eq!(tx.outputs.len(), 1);
+        assert_eq!(tx.lock_time, absolute::LockTime::ZERO);
+
+        assert_eq!(
+            format!("{:x}", tx.compute_txid()),
+            "f5864806e3565c34d1b41e716f72609d00b55ea5eac5b924c9719a842ef42206".to_string()
+        );
+        assert_eq!(
+            format!("{:x}", tx.compute_wtxid()),
+            "80b7d8a82d5d5bf92905b06f2014dd699e03837ca172e3a59d51426ebbe3e7f5".to_string()
+        );
+    }
+
+    #[test]
+    #[cfg(all(feature = "alloc", feature = "hex"))]
+    fn decode_nonsegwit_transaction() {
+        let tx_bytes = hex!("0100000001a15d57094aa7a21a28cb20b59aab8fc7d1149a3bdbcddba9c622e4f5f6a99ece010000006c493046022100f93bb0e7d8db7bd46e40132d1f8242026e045f03a0efe71bbb8e3f475e970d790221009337cd7f1f929f00cc6ff01f03729b069a7c21b59b1736ddfee5db5946c5da8c0121033b9b137ee87d5a812d6f506efdd37f0affa7ffc310711c06c7f3e097c9447c52ffffffff0100e1f505000000001976a9140389035a9225b3839e2bbf32d826a1e222031fd888ac00000000");
+
+        let mut decoder = Transaction::decoder();
+        let mut slice = tx_bytes.as_slice();
+        decoder.push_bytes(&mut slice).unwrap();
+        let tx = decoder.end().unwrap();
+
+        // All these tests aren't really needed because if they fail, the hash check at the end
+        // will also fail. But these will show you where the failure is so I'll leave them in.
+        assert_eq!(tx.version, Version::ONE);
+        assert_eq!(tx.inputs.len(), 1);
+        // In particular this one is easy to get backward -- in bitcoin hashes are encoded
+        // as little-endian 256-bit numbers rather than as data strings.
+        assert_eq!(
+            format!("{:x}", tx.inputs[0].previous_output.txid),
+            "ce9ea9f6f5e422c6a9dbcddb3b9a14d1c78fab9ab520cb281aa2a74a09575da1".to_string()
+        );
+        assert_eq!(tx.inputs[0].previous_output.vout, 1);
+        assert_eq!(tx.outputs.len(), 1);
+        assert_eq!(tx.lock_time, absolute::LockTime::ZERO);
+
+        assert_eq!(
+            format!("{:x}", tx.compute_txid()),
+            "a6eab3c14ab5272a58a5ba91505ba1a4b6d7a3a9fcbd187b6cd99a7b6d548cb7".to_string()
+        );
+        assert_eq!(
+            format!("{:x}", tx.compute_wtxid()),
+            "a6eab3c14ab5272a58a5ba91505ba1a4b6d7a3a9fcbd187b6cd99a7b6d548cb7".to_string()
+        );
+    }
 }
diff --git a/primitives/src/witness.rs b/primitives/src/witness.rs
index 00446eb2..08bfee3b 100644
--- a/primitives/src/witness.rs
+++ b/primitives/src/witness.rs
@@ -4,19 +4,27 @@
 //!
 //! This module contains the [`Witness`] struct and related methods to operate on it
 
+use core::convert::Infallible;
 use core::fmt;
 use core::ops::Index;
 
 #[cfg(feature = "arbitrary")]
 use arbitrary::{Arbitrary, Unstructured};
-use encoding::{BytesEncoder, CompactSizeEncoder, Encodable, Encoder, Encoder2};
+#[cfg(doc)]
+use encoding::Decoder4;
+use encoding::{
+    self, BytesEncoder, CompactSizeDecoder, CompactSizeDecoderError, CompactSizeEncoder, Decoder,
+    Encodable, Encoder, Encoder2, LengthPrefixExceedsMaxError,
+};
 #[cfg(feature = "hex")]
 use hex::{error::HexToBytesError, FromHex};
-use internals::compact_size;
 use internals::slice::SliceExt;
 use internals::wrap_debug::WrapDebug;
+use internals::{compact_size, write_err};
 
 use crate::prelude::{Box, Vec};
+#[cfg(doc)]
+use crate::TxIn;
 
 /// The Witness is the data used to unlock bitcoin since the [SegWit upgrade].
 ///
@@ -287,6 +295,144 @@ impl Encoder for WitnessEncoder<'_> {
     fn advance(&mut self) -> bool { self.0.advance() }
 }
 
+/// The decoder for the [`Witness`] type.
+#[cfg(feature = "alloc")]
+pub struct WitnessDecoder {
+    /// A decoder for the initial length prefix and subsequent per-element prefixes.
+    prefix_decoder: Option<CompactSizeDecoder>,
+    /// Holds the elements.
+    buffer: Vec<Vec<u8>>,
+    /// True if the initial compact size has been read.
+    initial_length_prefix_read: bool, // I.e not the one for each element.
+    /// Set after the initial length prefix is read.
+    ///
+    /// This is read as a u64, checked to be below 4,000,000 then
+    /// cast to a `usize` to make usage easier.
+    witness_elements: usize,
+    /// Index of the element we are going to decode next.
+    idx: usize,
+    /// True if the element length prefix has been read.
+    element_length_prefix_read: bool,
+    /// Bytes left to read for this element.
+    bytes_to_read: usize,
+}
+
+impl WitnessDecoder {
+    /// Constructs a new witness decoder.
+    pub fn new() -> Self {
+        Self {
+            prefix_decoder: None,
+            buffer: Vec::new(),
+            initial_length_prefix_read: false,
+            witness_elements: 0,
+            idx: 0,
+            element_length_prefix_read: false,
+            bytes_to_read: 0,
+        }
+    }
+}
+
+impl Default for WitnessDecoder {
+    fn default() -> Self { Self::new() }
+}
+
+impl Decoder for WitnessDecoder {
+    type Output = Witness;
+    type Error = WitnessDecoderError;
+
+    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<bool, Self::Error> {
+        use {WitnessDecoderError as E, WitnessDecoderErrorInner as Inner};
+
+        // First call to `push_bytes`.
+        if !self.initial_length_prefix_read {
+            let mut decoder = self.prefix_decoder.take().unwrap_or_default();
+
+            if decoder.push_bytes(bytes).map_err(|e| E(Inner::LengthPrefixDecode(e)))? {
+                self.prefix_decoder = Some(decoder);
+                return Ok(true);
+            }
+            let length = decoder.end().map_err(|e| E(Inner::LengthPrefixDecode(e)))?;
+
+            self.witness_elements = encoding::cast_to_usize_if_valid(length)
+                .map_err(|e| E(Inner::LengthPrefixInvalid(e)))?;
+            self.initial_length_prefix_read = true;
+
+            if self.witness_elements == 0 {
+                return Ok(false);
+            }
+
+            // `cast_to_usize_if_valid` asserts length < 4,000,000, so no DoS vector here.
+            self.buffer = Vec::with_capacity(self.witness_elements);
+        }
+
+        loop {
+            if bytes.is_empty() {
+                return Ok(true);
+            }
+
+            if self.element_length_prefix_read {
+                let v = self.buffer.get_mut(self.idx).expect("we created this last call");
+                let copy_len = bytes.len().min(self.bytes_to_read);
+
+                v.extend_from_slice(&bytes[..copy_len]);
+                *bytes = &bytes[copy_len..];
+                self.bytes_to_read -= copy_len;
+
+                if self.bytes_to_read == 0 {
+                    self.element_length_prefix_read = false;
+                    self.idx += 1;
+                    if self.idx == self.witness_elements {
+                        return Ok(false);
+                    }
+                }
+            } else {
+                let mut decoder = self.prefix_decoder.take().unwrap_or_default();
+
+                if decoder.push_bytes(bytes).map_err(|e| E(Inner::LengthPrefixDecode(e)))? {
+                    self.prefix_decoder = Some(decoder);
+                    return Ok(true);
+                }
+                let length = decoder.end().map_err(|e| E(Inner::LengthPrefixDecode(e)))?;
+                self.bytes_to_read = encoding::cast_to_usize_if_valid(length)
+                    .map_err(|e| E(Inner::LengthPrefixInvalid(e)))?;
+                self.element_length_prefix_read = true;
+
+                // `cast_to_usize_if_valid` asserts length < 4,000,000, so no DoS vector here.
+                let v = Vec::with_capacity(self.bytes_to_read);
+                self.buffer.push(v);
+            }
+        }
+    }
+
+    fn end(self) -> Result<Self::Output, Self::Error> {
+        use {WitnessDecoderError as E, WitnessDecoderErrorInner as Inner};
+
+        let remaining = self.witness_elements - self.idx;
+
+        if remaining == 0 {
+            Ok(Witness::from_slice(&self.buffer))
+        } else {
+            Err(E(Inner::UnexpectedEof(UnexpectedEofError { missing_elements: remaining })))
+        }
+    }
+
+    fn read_limit(&self) -> usize {
+        if !self.initial_length_prefix_read {
+            return match &self.prefix_decoder {
+                Some(compact_size_decoder) => compact_size_decoder.read_limit(),
+                None => 1,
+            };
+        }
+        // The only assumption we can make is that each witness element is at least one byte.
+        self.witness_elements.saturating_sub(self.buffer.len())
+    }
+}
+
+impl encoding::Decodable for Witness {
+    type Decoder = WitnessDecoder;
+    fn decoder() -> Self::Decoder { WitnessDecoder::default() }
+}
+
 // Note: we use `Borrow` in the following `PartialEq` impls specifically because of its additional
 // constraints on equality semantics.
 impl<T: core::borrow::Borrow<[u8]>> PartialEq<[T]> for Witness {
@@ -592,6 +738,65 @@ impl Default for Witness {
     fn default() -> Self { Self::new() }
 }
 
+/// An error when consensus decoding a [`Witness`].
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct WitnessDecoderError(WitnessDecoderErrorInner);
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+enum WitnessDecoderErrorInner {
+    /// Error decoding the vector length prefix.
+    LengthPrefixDecode(CompactSizeDecoderError),
+    /// Length prefix exceeds 4,000,000.
+    LengthPrefixInvalid(LengthPrefixExceedsMaxError),
+    /// Not enough bytes given to decoder.
+    UnexpectedEof(UnexpectedEofError),
+}
+
+impl From<Infallible> for WitnessDecoderError {
+    fn from(never: Infallible) -> Self { match never {} }
+}
+
+impl fmt::Display for WitnessDecoderError {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        use WitnessDecoderErrorInner as E;
+
+        match self.0 {
+            E::LengthPrefixDecode(ref e) => write_err!(f, "vec decoder error"; e),
+            E::LengthPrefixInvalid(ref e) => write_err!(f, "vec decoder error"; e),
+            E::UnexpectedEof(ref e) => write_err!(f, "decoder error"; e),
+        }
+    }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for WitnessDecoderError {
+    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
+        use WitnessDecoderErrorInner as E;
+
+        match self.0 {
+            E::LengthPrefixDecode(ref e) => Some(e),
+            E::LengthPrefixInvalid(ref e) => Some(e),
+            E::UnexpectedEof(ref e) => Some(e),
+        }
+    }
+}
+
+/// Not enough witness elements (bytes) given to decoder.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct UnexpectedEofError {
+    /// Number of elements missing to complete decoder.
+    missing_elements: usize,
+}
+
+impl core::fmt::Display for UnexpectedEofError {
+    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+        write!(f, "not enough witness elements for decoder, missing {}", self.missing_elements)
+    }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for UnexpectedEofError {}
+
 #[cfg(feature = "arbitrary")]
 impl<'a> Arbitrary<'a> for Witness {
     fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
@@ -988,4 +1193,67 @@ mod test {
 
         assert_eq!(&got, &want);
     }
+
+    #[cfg(feature = "alloc")]
+    fn witness_test_case() -> (Witness, Vec<u8>) {
+        let bytes1 = [1u8];
+        let bytes2 = [2u8, 3];
+        let bytes3 = [4u8, 5, 6];
+        let data = [&bytes1[..], &bytes2[..], &bytes3[..]];
+
+        let witness = Witness::from_iter(data);
+
+        #[rustfmt::skip]
+        let encoded = vec![
+            0x03_u8,
+            0x01, 0x01,
+            0x02, 0x02, 0x03,
+            0x03, 0x04, 0x05, 0x06
+        ];
+
+        (witness, encoded)
+    }
+
+    #[cfg(feature = "alloc")]
+    #[test]
+    fn decode_witness_one_single_call() {
+        let (want, encoded) = witness_test_case();
+
+        let mut slice = encoded.as_slice();
+        let mut decoder = WitnessDecoder::new();
+        decoder.push_bytes(&mut slice).unwrap();
+
+        let got = decoder.end().unwrap();
+
+        assert_eq!(got, want);
+    }
+
+    #[cfg(feature = "alloc")]
+    #[test]
+    #[allow(clippy::many_single_char_names)]
+    fn decode_witness_many_calls() {
+        let (want, encoded) = witness_test_case();
+
+        let mut decoder = WitnessDecoder::new();
+
+        let mut a = &encoded.as_slice()[0..1]; // [3]
+        let mut b = &encoded.as_slice()[1..2]; // [1]
+        let mut c = &encoded.as_slice()[2..5]; // [1, 2, 2]
+        let mut d = &encoded.as_slice()[5..6]; // [3]
+        let mut e = &encoded.as_slice()[6..7]; // [3]
+        let mut f = &encoded.as_slice()[7..9]; // [4, 5]
+        let mut g = &encoded.as_slice()[9..]; // [6]
+
+        decoder.push_bytes(&mut a).unwrap();
+        decoder.push_bytes(&mut b).unwrap();
+        decoder.push_bytes(&mut c).unwrap();
+        decoder.push_bytes(&mut d).unwrap();
+        decoder.push_bytes(&mut e).unwrap();
+        decoder.push_bytes(&mut f).unwrap();
+        decoder.push_bytes(&mut g).unwrap();
+
+        let got = decoder.end().unwrap();
+
+        assert_eq!(got, want);
+    }
 }