Introduce arbitrary_* `bitcoin` fuzz targets

diff --git a/.github/workflows/cron-daily-fuzz.yml b/.github/workflows/cron-daily-fuzz.yml
index 06795fa5..e71150aa 100644
--- a/.github/workflows/cron-daily-fuzz.yml
+++ b/.github/workflows/cron-daily-fuzz.yml
@@ -18,14 +18,17 @@ jobs:
         # We only get 20 jobs at a time, we probably don't want to go
         # over that limit with fuzzing because of the hour run time.
         fuzz_target: [
-          bitcoin_deserialize_address,
+          bitcoin_arbitrary_block,
+          bitcoin_arbitrary_script,
+          bitcoin_arbitrary_transaction,
           bitcoin_deserialize_block,
           bitcoin_deserialize_prefilled_transaction,
           bitcoin_deserialize_psbt,
           bitcoin_deserialize_script,
           bitcoin_deserialize_transaction,
           bitcoin_deserialize_witness,
-          bitcoin_outpoint_string,
+          bitcoin_parse_address,
+          bitcoin_parse_outpoint,
           bitcoin_script_bytes_to_asm_fmt,
           hashes_json,
           hashes_ripemd160,
diff --git a/fuzz/Cargo.toml b/fuzz/Cargo.toml
index 03569e20..a92bb7ae 100644
--- a/fuzz/Cargo.toml
+++ b/fuzz/Cargo.toml
@@ -22,8 +22,16 @@ serde_json = "1.0.68"
 unexpected_cfgs = { level = "deny", check-cfg = ['cfg(fuzzing)'] }
 
 [[bin]]
-name = "bitcoin_deserialize_address"
-path = "fuzz_targets/bitcoin/deserialize_address.rs"
+name = "bitcoin_arbitrary_block"
+path = "fuzz_targets/bitcoin/arbitrary_block.rs"
+
+[[bin]]
+name = "bitcoin_arbitrary_script"
+path = "fuzz_targets/bitcoin/arbitrary_script.rs"
+
+[[bin]]
+name = "bitcoin_arbitrary_transaction"
+path = "fuzz_targets/bitcoin/arbitrary_transaction.rs"
 
 [[bin]]
 name = "bitcoin_deserialize_block"
@@ -50,8 +58,12 @@ name = "bitcoin_deserialize_witness"
 path = "fuzz_targets/bitcoin/deserialize_witness.rs"
 
 [[bin]]
-name = "bitcoin_outpoint_string"
-path = "fuzz_targets/bitcoin/outpoint_string.rs"
+name = "bitcoin_parse_address"
+path = "fuzz_targets/bitcoin/parse_address.rs"
+
+[[bin]]
+name = "bitcoin_parse_outpoint"
+path = "fuzz_targets/bitcoin/parse_outpoint.rs"
 
 [[bin]]
 name = "bitcoin_script_bytes_to_asm_fmt"
diff --git a/fuzz/fuzz_targets/bitcoin/arbitrary_block.rs b/fuzz/fuzz_targets/bitcoin/arbitrary_block.rs
new file mode 100644
index 00000000..85dcde30
--- /dev/null
+++ b/fuzz/fuzz_targets/bitcoin/arbitrary_block.rs
@@ -0,0 +1,64 @@
+use arbitrary::{Arbitrary, Unstructured};
+use bitcoin::block::{self, Block, BlockCheckedExt as _};
+use honggfuzz::fuzz;
+use bitcoin::consensus::{deserialize, serialize};
+
+fn do_test(data: &[u8]) {
+    let mut u = Unstructured::new(data);
+    let b = Block::arbitrary(&mut u);
+
+    if let Ok(block) = b {
+        let serialized = serialize(&block);
+
+        // Manually call all compute functions with unchecked block data.
+        let (header, transactions) = block.clone().into_parts();
+        block::compute_merkle_root(&transactions);
+        block::compute_witness_commitment(&transactions, &[]); // TODO: Is empty slice ok?
+        block::compute_witness_root(&transactions);
+
+        if let Ok(block) = Block::new_checked(header, transactions) {
+            let _ = block.bip34_block_height();
+            block.block_hash();
+            block.weight();
+        }
+
+        let deserialized: Result<Block, _> = deserialize(serialized.as_slice());
+        assert!(deserialized.is_ok(), "Deserialization error: {:?}", deserialized.err().unwrap());
+        assert_eq!(deserialized.unwrap(), block);
+    }
+}
+
+fn main() {
+    loop {
+        fuzz!(|data| {
+            do_test(data);
+        });
+    }
+}
+
+#[cfg(all(test, fuzzing))]
+mod tests {
+    fn extend_vec_from_hex(hex: &str, out: &mut Vec<u8>) {
+        let mut b = 0;
+        for (idx, c) in hex.as_bytes().iter().enumerate() {
+            b <<= 4;
+            match *c {
+                b'A'..=b'F' => b |= c - b'A' + 10,
+                b'a'..=b'f' => b |= c - b'a' + 10,
+                b'0'..=b'9' => b |= c - b'0',
+                _ => panic!("Bad hex"),
+            }
+            if (idx & 1) == 1 {
+                out.push(b);
+                b = 0;
+            }
+        }
+    }
+
+    #[test]
+    fn duplicate_crash() {
+        let mut a = Vec::new();
+        extend_vec_from_hex("00", &mut a);
+        super::do_test(&a);
+    }
+}
diff --git a/fuzz/fuzz_targets/bitcoin/arbitrary_script.rs b/fuzz/fuzz_targets/bitcoin/arbitrary_script.rs
new file mode 100644
index 00000000..a2bdfcfe
--- /dev/null
+++ b/fuzz/fuzz_targets/bitcoin/arbitrary_script.rs
@@ -0,0 +1,84 @@
+use arbitrary::{Arbitrary, Unstructured};
+use honggfuzz::fuzz;
+
+use bitcoin::{Network};
+use bitcoin::address::Address;
+use bitcoin::consensus::serialize;
+use bitcoin::script::{self, ScriptBuf, ScriptExt as _, ScriptPubKeyExt as _};
+
+fn do_test(data: &[u8]) {
+    let mut u = Unstructured::new(data);
+    let s = ScriptBuf::arbitrary(&mut u);
+
+    if let Ok(script_buf) = s {
+        let serialized = serialize(&script_buf);
+        let _ : Result<Vec<script::Instruction>, script::Error> = script_buf.instructions().collect();
+
+        let _ = script_buf.to_string();
+        let _ = script_buf.count_sigops();
+        let _ = script_buf.count_sigops_legacy();
+        let _ = script_buf.minimal_non_dust();
+        let _ = script_buf.minimal_non_dust_custom(u.arbitrary().expect("valid arbitrary FeeRate"));
+
+        let mut builder = script::Builder::new();
+        for instruction in script_buf.instructions_minimal() {
+            if instruction.is_err() {
+                return;
+            }
+            match instruction.ok().unwrap() {
+                script::Instruction::Op(op) => {
+                    builder = builder.push_opcode(op);
+                }
+                script::Instruction::PushBytes(bytes) => {
+                    // While we enforce the minimality rule for minimal PUSHDATA opcodes, we don't
+                    // enforce the minimality of numbers since we don't have a script engine
+                    // to determine if the number is getting fed into a numeric opcode, which is
+                    // when the minimality of numbers is required.
+                    builder = builder.push_slice_non_minimal(bytes)
+                }
+            }
+        }
+        assert_eq!(builder.into_script(), script_buf);
+        assert_eq!(serialized, &serialize(&script_buf)[..]);
+
+        // Check if valid address and if that address roundtrips.
+        if let Ok(addr) = Address::from_script(&script_buf, Network::Bitcoin) {
+            assert_eq!(addr.script_pubkey(), script_buf);
+        }
+    }
+}
+
+fn main() {
+    loop {
+        fuzz!(|data| {
+            do_test(data);
+        });
+    }
+}
+
+#[cfg(all(test, fuzzing))]
+mod tests {
+    fn extend_vec_from_hex(hex: &str, out: &mut Vec<u8>) {
+        let mut b = 0;
+        for (idx, c) in hex.as_bytes().iter().enumerate() {
+            b <<= 4;
+            match *c {
+                b'A'..=b'F' => b |= c - b'A' + 10,
+                b'a'..=b'f' => b |= c - b'a' + 10,
+                b'0'..=b'9' => b |= c - b'0',
+                _ => panic!("Bad hex"),
+            }
+            if (idx & 1) == 1 {
+                out.push(b);
+                b = 0;
+            }
+        }
+    }
+
+    #[test]
+    fn duplicate_crash() {
+        let mut a = Vec::new();
+        extend_vec_from_hex("00", &mut a);
+        super::do_test(&a);
+    }
+}
diff --git a/fuzz/fuzz_targets/bitcoin/arbitrary_transaction.rs b/fuzz/fuzz_targets/bitcoin/arbitrary_transaction.rs
new file mode 100644
index 00000000..1024f4b9
--- /dev/null
+++ b/fuzz/fuzz_targets/bitcoin/arbitrary_transaction.rs
@@ -0,0 +1,68 @@
+use arbitrary::{Arbitrary, Unstructured};
+use honggfuzz::fuzz;
+use bitcoin::consensus::{deserialize, serialize};
+use bitcoin::Transaction;
+use bitcoin::transaction::TransactionExt as _;
+
+fn do_test(data: &[u8]) {
+    let mut u = Unstructured::new(data);
+    let t = Transaction::arbitrary(&mut u);
+
+    if let Ok(mut tx) = t {
+        let serialized = serialize(&tx);
+        let len = serialized.len();
+        let calculated_weight = tx.weight().to_wu() as usize;
+        for input in &mut tx.inputs {
+            input.witness = bitcoin::witness::Witness::default();
+        }
+        let no_witness_len = bitcoin::consensus::encode::serialize(&tx).len();
+        // For 0-input transactions, `no_witness_len` will be incorrect because
+        // we serialize as SegWit even after "stripping the witnesses". We need
+        // to drop two bytes (i.e. eight weight). Similarly, calculated_weight is
+        // incorrect and needs 2 wu removing for the marker/flag bytes.
+        if tx.inputs.is_empty() {
+            assert_eq!(no_witness_len * 3 + len - 8, calculated_weight - 2);
+        } else {
+            assert_eq!(no_witness_len * 3 + len, calculated_weight);
+        }
+
+        let deserialized: Result<Transaction, _> = deserialize(serialized.as_slice());
+        assert!(deserialized.is_ok(), "Deserialization error: {:?}", deserialized.err().unwrap());
+        assert_eq!(deserialized.unwrap(), tx);
+    }
+}
+
+fn main() {
+    loop {
+        fuzz!(|data| {
+            do_test(data);
+        });
+    }
+}
+
+#[cfg(all(test, fuzzing))]
+mod tests {
+    fn extend_vec_from_hex(hex: &str, out: &mut Vec<u8>) {
+        let mut b = 0;
+        for (idx, c) in hex.as_bytes().iter().enumerate() {
+            b <<= 4;
+            match *c {
+                b'A'..=b'F' => b |= c - b'A' + 10,
+                b'a'..=b'f' => b |= c - b'a' + 10,
+                b'0'..=b'9' => b |= c - b'0',
+                _ => panic!("Bad hex"),
+            }
+            if (idx & 1) == 1 {
+                out.push(b);
+                b = 0;
+            }
+        }
+    }
+
+    #[test]
+    fn duplicate_crash() {
+        let mut a = Vec::new();
+        extend_vec_from_hex("00", &mut a);
+        super::do_test(&a);
+    }
+}
diff --git a/fuzz/fuzz_targets/bitcoin/deserialize_block.rs b/fuzz/fuzz_targets/bitcoin/deserialize_block.rs
index 2ad53e8d..bdc0ce0f 100644
--- a/fuzz/fuzz_targets/bitcoin/deserialize_block.rs
+++ b/fuzz/fuzz_targets/bitcoin/deserialize_block.rs
@@ -1,8 +1,7 @@
-use bitcoin::block::{self, Block, BlockCheckedExt as _};
 use honggfuzz::fuzz;
 
 fn do_test(data: &[u8]) {
-    let block_result: Result<bitcoin::block::Block, _> =
+    let block_result: Result<bitcoin::Block, _> =
         bitcoin::consensus::encode::deserialize(data);
 
     match block_result {
@@ -10,18 +9,6 @@ fn do_test(data: &[u8]) {
         Ok(block) => {
             let ser = bitcoin::consensus::encode::serialize(&block);
             assert_eq!(&ser[..], data);
-
-            // Manually call all compute functions with unchecked block data.
-            let (header, transactions) = block.into_parts();
-            block::compute_merkle_root(&transactions);
-            block::compute_witness_commitment(&transactions, &[]); // TODO: Is empty slice ok?
-            block::compute_witness_root(&transactions);
-
-            if let Ok(block) = Block::new_checked(header, transactions) {
-                let _ = block.bip34_block_height();
-                block.block_hash();
-                block.weight();
-            }
         }
     }
 }
@@ -56,7 +43,7 @@ mod tests {
     #[test]
     fn duplicate_crash() {
         let mut a = Vec::new();
-        extend_vec_from_hex("00", &mut a);
+        extend_vec_from_hex("000700000001000000010000", &mut a);
         super::do_test(&a);
     }
 }
diff --git a/fuzz/fuzz_targets/bitcoin/deserialize_script.rs b/fuzz/fuzz_targets/bitcoin/deserialize_script.rs
index c3a553ea..407d03c7 100644
--- a/fuzz/fuzz_targets/bitcoin/deserialize_script.rs
+++ b/fuzz/fuzz_targets/bitcoin/deserialize_script.rs
@@ -1,56 +1,14 @@
-use bitcoin::address::Address;
-use bitcoin::consensus::encode;
-use bitcoin::script::{self, ScriptExt as _, ScriptPubKeyExt as _};
-use bitcoin::{FeeRate, Network};
-use bitcoin_fuzz::fuzz_utils::{consume_random_bytes, consume_u32};
 use honggfuzz::fuzz;
 
 fn do_test(data: &[u8]) {
-    let mut new_data = data;
-    let bytes = consume_random_bytes(&mut new_data);
-    let s: Result<script::ScriptPubKeyBuf, _> = encode::deserialize(bytes);
-    if let Ok(script) = s {
-        let _: Result<Vec<script::Instruction>, script::Error> = script.instructions().collect();
-
-        let _ = script.to_string();
-        let _ = script.count_sigops();
-        let _ = script.count_sigops_legacy();
-        let _ = script.minimal_non_dust();
-
-        let fee_rate = FeeRate::from_sat_per_kwu(consume_u32(&mut new_data));
-        let _ = script.minimal_non_dust_custom(fee_rate);
-
-        let mut b = script::Builder::new();
-        for ins in script.instructions_minimal() {
-            if ins.is_err() {
-                return;
-            }
-            match ins.ok().unwrap() {
-                script::Instruction::Op(op) => {
-                    b = b.push_opcode(op);
-                }
-                script::Instruction::PushBytes(bytes) => {
-                    // Any one-byte pushes, except -0, which can be interpreted as numbers, should be
-                    // reserialized as numbers. (For -1 through 16, this will use special ops; for
-                    // others it'll just reserialize them as pushes.)
-                    if bytes.len() == 1 && bytes[0] != 0x80 && bytes[0] != 0x00 {
-                        if let Ok(num) = bytes.read_scriptint() {
-                            b = b.push_int_unchecked(num);
-                        } else {
-                            b = b.push_slice(bytes);
-                        }
-                    } else {
-                        b = b.push_slice(bytes);
-                    }
-                }
-            }
-        }
-        assert_eq!(b.into_script(), script);
-        assert_eq!(data, &encode::serialize(&script)[..]);
-
-        // Check if valid address and if that address roundtrips.
-        if let Ok(addr) = Address::from_script(&script, Network::Bitcoin) {
-            assert_eq!(addr.script_pubkey(), script);
+    let script_result: Result<bitcoin::ScriptPubKeyBuf, _> =
+        bitcoin::consensus::encode::deserialize(data);
+
+    match script_result {
+        Err(_) => {}
+        Ok(script) => {
+            let ser = bitcoin::consensus::encode::serialize(&script);
+            assert_eq!(&ser[..], data);
         }
     }
 }
diff --git a/fuzz/fuzz_targets/bitcoin/deserialize_transaction.rs b/fuzz/fuzz_targets/bitcoin/deserialize_transaction.rs
index 606c2b20..eb765a47 100644
--- a/fuzz/fuzz_targets/bitcoin/deserialize_transaction.rs
+++ b/fuzz/fuzz_targets/bitcoin/deserialize_transaction.rs
@@ -1,29 +1,14 @@
-use bitcoin::transaction::TransactionExt as _;
 use honggfuzz::fuzz;
 
 fn do_test(data: &[u8]) {
-    let tx_result: Result<bitcoin::transaction::Transaction, _> =
+    let tx_result: Result<bitcoin::Transaction, _> =
         bitcoin::consensus::encode::deserialize(data);
+
     match tx_result {
         Err(_) => {}
-        Ok(mut tx) => {
+        Ok(tx) => {
             let ser = bitcoin::consensus::encode::serialize(&tx);
             assert_eq!(&ser[..], data);
-            let len = ser.len();
-            let calculated_weight = tx.weight().to_wu() as usize;
-            for input in &mut tx.inputs {
-                input.witness = bitcoin::witness::Witness::default();
-            }
-            let no_witness_len = bitcoin::consensus::encode::serialize(&tx).len();
-            // For 0-input transactions, `no_witness_len` will be incorrect because
-            // we serialize as SegWit even after "stripping the witnesses". We need
-            // to drop two bytes (i.e. eight weight). Similarly, calculated_weight is
-            // incorrect and needs 2 wu removing for the marker/flag bytes.
-            if tx.inputs.is_empty() {
-                assert_eq!(no_witness_len * 3 + len - 8, calculated_weight - 2);
-            } else {
-                assert_eq!(no_witness_len * 3 + len, calculated_weight);
-            }
         }
     }
 }
@@ -58,7 +43,7 @@ mod tests {
     #[test]
     fn duplicate_crash() {
         let mut a = Vec::new();
-        extend_vec_from_hex("000700000001000000010000", &mut a);
+        extend_vec_from_hex("00", &mut a);
         super::do_test(&a);
     }
 }
diff --git a/fuzz/fuzz_targets/bitcoin/deserialize_witness.rs b/fuzz/fuzz_targets/bitcoin/deserialize_witness.rs
index d4df534d..8cdee0de 100644
--- a/fuzz/fuzz_targets/bitcoin/deserialize_witness.rs
+++ b/fuzz/fuzz_targets/bitcoin/deserialize_witness.rs
@@ -1,18 +1,16 @@
-use arbitrary::{Arbitrary, Unstructured};
-use bitcoin::consensus::{deserialize, serialize};
 use bitcoin::witness::Witness;
 use honggfuzz::fuzz;
 
 fn do_test(data: &[u8]) {
-    let mut u = Unstructured::new(data);
+    let witness_result: Result<Witness, _> =
+        bitcoin::consensus::encode::deserialize(data);
 
-    let w = Witness::arbitrary(&mut u);
-    if let Ok(witness) = w {
-        let serialized = serialize(&witness);
-        let deserialized: Result<Witness, _> = deserialize(serialized.as_slice());
-
-        assert!(deserialized.is_ok());
-        assert_eq!(deserialized.unwrap(), witness);
+    match witness_result {
+        Err(_) => {}
+        Ok(witness) => {
+            let ser = bitcoin::consensus::encode::serialize(&witness);
+            assert_eq!(&ser[..], data);
+        }
     }
 }