zebra_chain/transaction/
arbitrary.rs

1//! Arbitrary data generation for transaction proptests
2
3use std::{cmp::max, collections::HashMap, ops::Neg, sync::Arc};
4
5use chrono::{TimeZone, Utc};
6use proptest::{array, collection::vec, option, prelude::*, test_runner::TestRunner};
7use reddsa::{orchard::Binding, Signature};
8
9use crate::{
10    amount::{self, Amount, NegativeAllowed, NonNegative},
11    at_least_one,
12    block::{self, arbitrary::MAX_PARTIAL_CHAIN_BLOCKS},
13    orchard,
14    parameters::{Network, NetworkUpgrade},
15    primitives::{Bctv14Proof, Groth16Proof, Halo2Proof, ZkSnarkProof},
16    sapling::{self, AnchorVariant, PerSpendAnchor, SharedAnchor},
17    serialization::{self, ZcashDeserializeInto},
18    sprout, transparent,
19    value_balance::{ValueBalance, ValueBalanceError},
20    LedgerState,
21};
22
23use itertools::Itertools;
24
25use super::{
26    FieldNotPresent, JoinSplitData, LockTime, Memo, Transaction, UnminedTx, VerifiedUnminedTx,
27};
28
29/// The maximum number of arbitrary transactions, inputs, or outputs.
30///
31/// This size is chosen to provide interesting behaviour, but not be too large
32/// for debugging.
33pub const MAX_ARBITRARY_ITEMS: usize = 4;
34
35// TODO: if needed, fixup transaction outputs
36//       (currently 0..=9 outputs, consensus rules require 1..)
37impl Transaction {
38    /// Generate a proptest strategy for V1 Transactions
39    pub fn v1_strategy(ledger_state: LedgerState) -> BoxedStrategy<Self> {
40        (
41            transparent::Input::vec_strategy(&ledger_state, MAX_ARBITRARY_ITEMS),
42            vec(any::<transparent::Output>(), 0..MAX_ARBITRARY_ITEMS),
43            any::<LockTime>(),
44        )
45            .prop_map(|(inputs, outputs, lock_time)| Transaction::V1 {
46                inputs,
47                outputs,
48                lock_time,
49            })
50            .boxed()
51    }
52
53    /// Generate a proptest strategy for V2 Transactions
54    pub fn v2_strategy(ledger_state: LedgerState) -> BoxedStrategy<Self> {
55        (
56            transparent::Input::vec_strategy(&ledger_state, MAX_ARBITRARY_ITEMS),
57            vec(any::<transparent::Output>(), 0..MAX_ARBITRARY_ITEMS),
58            any::<LockTime>(),
59            option::of(any::<JoinSplitData<Bctv14Proof>>()),
60        )
61            .prop_map(
62                |(inputs, outputs, lock_time, joinsplit_data)| Transaction::V2 {
63                    inputs,
64                    outputs,
65                    lock_time,
66                    joinsplit_data,
67                },
68            )
69            .boxed()
70    }
71
72    /// Generate a proptest strategy for V3 Transactions
73    pub fn v3_strategy(ledger_state: LedgerState) -> BoxedStrategy<Self> {
74        (
75            transparent::Input::vec_strategy(&ledger_state, MAX_ARBITRARY_ITEMS),
76            vec(any::<transparent::Output>(), 0..MAX_ARBITRARY_ITEMS),
77            any::<LockTime>(),
78            any::<block::Height>(),
79            option::of(any::<JoinSplitData<Bctv14Proof>>()),
80        )
81            .prop_map(
82                |(inputs, outputs, lock_time, expiry_height, joinsplit_data)| Transaction::V3 {
83                    inputs,
84                    outputs,
85                    lock_time,
86                    expiry_height,
87                    joinsplit_data,
88                },
89            )
90            .boxed()
91    }
92
93    /// Generate a proptest strategy for V4 Transactions
94    pub fn v4_strategy(ledger_state: LedgerState) -> BoxedStrategy<Self> {
95        (
96            transparent::Input::vec_strategy(&ledger_state, MAX_ARBITRARY_ITEMS),
97            vec(any::<transparent::Output>(), 0..MAX_ARBITRARY_ITEMS),
98            any::<LockTime>(),
99            any::<block::Height>(),
100            option::of(any::<JoinSplitData<Groth16Proof>>()),
101            option::of(any::<sapling::ShieldedData<sapling::PerSpendAnchor>>()),
102        )
103            .prop_map(
104                move |(
105                    inputs,
106                    outputs,
107                    lock_time,
108                    expiry_height,
109                    joinsplit_data,
110                    sapling_shielded_data,
111                )| {
112                    Transaction::V4 {
113                        inputs,
114                        outputs,
115                        lock_time,
116                        expiry_height,
117                        joinsplit_data: if ledger_state.height.is_min() {
118                            // The genesis block should not contain any joinsplits.
119                            None
120                        } else {
121                            joinsplit_data
122                        },
123                        sapling_shielded_data: if ledger_state.height.is_min() {
124                            // The genesis block should not contain any shielded data.
125                            None
126                        } else {
127                            sapling_shielded_data
128                        },
129                    }
130                },
131            )
132            .boxed()
133    }
134
135    /// Generate a proptest strategy for V5 Transactions
136    pub fn v5_strategy(ledger_state: LedgerState) -> BoxedStrategy<Self> {
137        (
138            NetworkUpgrade::branch_id_strategy(),
139            any::<LockTime>(),
140            any::<block::Height>(),
141            transparent::Input::vec_strategy(&ledger_state, MAX_ARBITRARY_ITEMS),
142            vec(any::<transparent::Output>(), 0..MAX_ARBITRARY_ITEMS),
143            option::of(any::<sapling::ShieldedData<sapling::SharedAnchor>>()),
144            option::of(any::<orchard::ShieldedData>()),
145        )
146            .prop_map(
147                move |(
148                    network_upgrade,
149                    lock_time,
150                    expiry_height,
151                    inputs,
152                    outputs,
153                    sapling_shielded_data,
154                    orchard_shielded_data,
155                )| {
156                    Transaction::V5 {
157                        network_upgrade: if ledger_state.transaction_has_valid_network_upgrade() {
158                            ledger_state.network_upgrade()
159                        } else {
160                            network_upgrade
161                        },
162                        lock_time,
163                        expiry_height,
164                        inputs,
165                        outputs,
166                        sapling_shielded_data: if ledger_state.height.is_min() {
167                            // The genesis block should not contain any shielded data.
168                            None
169                        } else {
170                            sapling_shielded_data
171                        },
172                        orchard_shielded_data: if ledger_state.height.is_min() {
173                            // The genesis block should not contain any shielded data.
174                            None
175                        } else {
176                            orchard_shielded_data
177                        },
178                    }
179                },
180            )
181            .boxed()
182    }
183
184    /// Proptest Strategy for creating a Vector of transactions where the first
185    /// transaction is always the only coinbase transaction
186    pub fn vec_strategy(
187        mut ledger_state: LedgerState,
188        len: usize,
189    ) -> BoxedStrategy<Vec<Arc<Self>>> {
190        // TODO: fixup coinbase miner subsidy
191        let coinbase = Transaction::arbitrary_with(ledger_state.clone()).prop_map(Arc::new);
192        ledger_state.has_coinbase = false;
193        let remainder = vec(
194            Transaction::arbitrary_with(ledger_state).prop_map(Arc::new),
195            0..=len,
196        );
197
198        (coinbase, remainder)
199            .prop_map(|(first, mut remainder)| {
200                remainder.insert(0, first);
201                remainder
202            })
203            .boxed()
204    }
205
206    /// Apply `f` to the transparent output, `v_sprout_new`, and `v_sprout_old` values
207    /// in this transaction, regardless of version.
208    pub fn for_each_value_mut<F>(&mut self, mut f: F)
209    where
210        F: FnMut(&mut Amount<NonNegative>),
211    {
212        for output_value in self.output_values_mut() {
213            f(output_value);
214        }
215
216        for sprout_added_value in self.output_values_to_sprout_mut() {
217            f(sprout_added_value);
218        }
219        for sprout_removed_value in self.input_values_from_sprout_mut() {
220            f(sprout_removed_value);
221        }
222    }
223
224    /// Apply `f` to the sapling value balance and orchard value balance
225    /// in this transaction, regardless of version.
226    pub fn for_each_value_balance_mut<F>(&mut self, mut f: F)
227    where
228        F: FnMut(&mut Amount<NegativeAllowed>),
229    {
230        if let Some(sapling_value_balance) = self.sapling_value_balance_mut() {
231            f(sapling_value_balance);
232        }
233
234        if let Some(orchard_value_balance) = self.orchard_value_balance_mut() {
235            f(orchard_value_balance);
236        }
237    }
238
239    /// Fixup transparent values and shielded value balances,
240    /// so that transaction and chain value pools won't overflow MAX_MONEY.
241    ///
242    /// These fixes are applied to coinbase and non-coinbase transactions.
243    //
244    // TODO: do we want to allow overflow, based on an arbitrary bool?
245    pub fn fix_overflow(&mut self) {
246        fn scale_to_avoid_overflow<C: amount::Constraint>(amount: &mut Amount<C>)
247        where
248            Amount<C>: Copy,
249        {
250            const POOL_COUNT: u64 = 4;
251
252            let max_arbitrary_items: u64 = MAX_ARBITRARY_ITEMS.try_into().unwrap();
253            let max_partial_chain_blocks: u64 = MAX_PARTIAL_CHAIN_BLOCKS.try_into().unwrap();
254
255            // inputs/joinsplits/spends|outputs/actions * pools * transactions
256            let transaction_pool_scaling_divisor =
257                max_arbitrary_items * POOL_COUNT * max_arbitrary_items;
258            // inputs/joinsplits/spends|outputs/actions * transactions * blocks
259            let chain_pool_scaling_divisor =
260                max_arbitrary_items * max_arbitrary_items * max_partial_chain_blocks;
261            let scaling_divisor = max(transaction_pool_scaling_divisor, chain_pool_scaling_divisor);
262
263            *amount = (*amount / scaling_divisor).expect("divisor is not zero");
264        }
265
266        self.for_each_value_mut(scale_to_avoid_overflow);
267        self.for_each_value_balance_mut(scale_to_avoid_overflow);
268    }
269
270    /// Fixup transparent values and shielded value balances,
271    /// so that this transaction passes the "non-negative chain value pool" checks.
272    /// (These checks use the sum of unspent outputs for each transparent and shielded pool.)
273    ///
274    /// These fixes are applied to coinbase and non-coinbase transactions.
275    ///
276    /// `chain_value_pools` contains the chain value pool balances,
277    /// as of the previous transaction in this block
278    /// (or the last transaction in the previous block).
279    ///
280    /// `outputs` must contain all the [`transparent::Output`]s spent in this transaction.
281    ///
282    /// Currently, these fixes almost always leave some remaining value in each transparent
283    /// and shielded chain value pool.
284    ///
285    /// Before fixing the chain value balances, this method calls `fix_overflow`
286    /// to make sure that transaction and chain value pools don't overflow MAX_MONEY.
287    ///
288    /// After fixing the chain value balances, this method calls `fix_remaining_value`
289    /// to fix the remaining value in the transaction value pool.
290    ///
291    /// Returns the remaining transaction value, and the updated chain value balances.
292    ///
293    /// # Panics
294    ///
295    /// If any spent [`transparent::Output`] is missing from
296    /// [`transparent::OutPoint`]s.
297    //
298    // TODO: take some extra arbitrary flags, which select between zero and non-zero
299    //       remaining value in each chain value pool
300    pub fn fix_chain_value_pools(
301        &mut self,
302        chain_value_pools: ValueBalance<NonNegative>,
303        outputs: &HashMap<transparent::OutPoint, transparent::Output>,
304    ) -> Result<(Amount<NonNegative>, ValueBalance<NonNegative>), ValueBalanceError> {
305        self.fix_overflow();
306
307        // a temporary value used to check that inputs don't break the chain value balance
308        // consensus rules
309        let mut input_chain_value_pools = chain_value_pools;
310
311        for input in self.inputs() {
312            input_chain_value_pools = input_chain_value_pools
313                .add_transparent_input(input, outputs)
314                .expect("find_valid_utxo_for_spend only spends unspent transparent outputs");
315        }
316
317        // update the input chain value pools,
318        // zeroing any inputs that would exceed the input value
319
320        // TODO: consensus rule: normalise sprout JoinSplit values
321        //       so at least one of the values in each JoinSplit is zero
322        for input in self.input_values_from_sprout_mut() {
323            match input_chain_value_pools
324                .add_chain_value_pool_change(ValueBalance::from_sprout_amount(input.neg()))
325            {
326                Ok(new_chain_pools) => input_chain_value_pools = new_chain_pools,
327                // set the invalid input value to zero
328                Err(_) => *input = Amount::zero(),
329            }
330        }
331
332        // positive value balances subtract from the chain value pool
333
334        let sapling_input = self.sapling_value_balance().constrain::<NonNegative>();
335        if let Ok(sapling_input) = sapling_input {
336            match input_chain_value_pools.add_chain_value_pool_change(-sapling_input) {
337                Ok(new_chain_pools) => input_chain_value_pools = new_chain_pools,
338                Err(_) => *self.sapling_value_balance_mut().unwrap() = Amount::zero(),
339            }
340        }
341
342        let orchard_input = self.orchard_value_balance().constrain::<NonNegative>();
343        if let Ok(orchard_input) = orchard_input {
344            match input_chain_value_pools.add_chain_value_pool_change(-orchard_input) {
345                Ok(new_chain_pools) => input_chain_value_pools = new_chain_pools,
346                Err(_) => *self.orchard_value_balance_mut().unwrap() = Amount::zero(),
347            }
348        }
349
350        let remaining_transaction_value = self.fix_remaining_value(outputs)?;
351
352        // check our calculations are correct
353        let transaction_chain_value_pool_change =
354            self
355            .value_balance_from_outputs(outputs)
356            .expect("chain value pool and remaining transaction value fixes produce valid transaction value balances")
357            .neg();
358
359        let chain_value_pools = chain_value_pools
360            .add_transaction(self, outputs)
361            .unwrap_or_else(|err| {
362                panic!(
363                    "unexpected chain value pool error: {err:?}, \n\
364                     original chain value pools: {chain_value_pools:?}, \n\
365                     transaction chain value change: {transaction_chain_value_pool_change:?}, \n\
366                     input-only transaction chain value pools: {input_chain_value_pools:?}, \n\
367                     calculated remaining transaction value: {remaining_transaction_value:?}",
368                )
369            });
370
371        Ok((remaining_transaction_value, chain_value_pools))
372    }
373
374    /// Returns the total input value of this transaction's value pool.
375    ///
376    /// This is the sum of transparent inputs, sprout input values,
377    /// and if positive, the sapling and orchard value balances.
378    ///
379    /// `outputs` must contain all the [`transparent::Output`]s spent in this transaction.
380    fn input_value_pool(
381        &self,
382        outputs: &HashMap<transparent::OutPoint, transparent::Output>,
383    ) -> Result<Amount<NonNegative>, ValueBalanceError> {
384        let transparent_inputs = self
385            .inputs()
386            .iter()
387            .map(|input| input.value_from_outputs(outputs))
388            .sum::<Result<Amount<NonNegative>, amount::Error>>()
389            .map_err(ValueBalanceError::Transparent)?;
390        // TODO: fix callers which cause overflows, check for:
391        //       cached `outputs` that don't go through `fix_overflow`, and
392        //       values much larger than MAX_MONEY
393        //.expect("chain is limited to MAX_MONEY");
394
395        let sprout_inputs = self
396            .input_values_from_sprout()
397            .sum::<Result<Amount<NonNegative>, amount::Error>>()
398            .expect("chain is limited to MAX_MONEY");
399
400        // positive value balances add to the transaction value pool
401        let sapling_input = self
402            .sapling_value_balance()
403            .sapling_amount()
404            .constrain::<NonNegative>()
405            .unwrap_or_else(|_| Amount::zero());
406
407        let orchard_input = self
408            .orchard_value_balance()
409            .orchard_amount()
410            .constrain::<NonNegative>()
411            .unwrap_or_else(|_| Amount::zero());
412
413        let transaction_input_value_pool =
414            (transparent_inputs + sprout_inputs + sapling_input + orchard_input)
415                .expect("chain is limited to MAX_MONEY");
416
417        Ok(transaction_input_value_pool)
418    }
419
420    /// Fixup non-coinbase transparent values and shielded value balances,
421    /// so that this transaction passes the "non-negative remaining transaction value"
422    /// check. (This check uses the sum of inputs minus outputs.)
423    ///
424    /// Returns the remaining transaction value.
425    ///
426    /// `outputs` must contain all the [`transparent::Output`]s spent in this transaction.
427    ///
428    /// Currently, these fixes almost always leave some remaining value in the
429    /// transaction value pool.
430    ///
431    /// # Panics
432    ///
433    /// If any spent [`transparent::Output`] is missing from
434    /// [`transparent::OutPoint`]s.
435    //
436    // TODO: split this method up, after we've implemented chain value balance adjustments
437    //
438    // TODO: take an extra arbitrary bool, which selects between zero and non-zero
439    //       remaining value in the transaction value pool
440    pub fn fix_remaining_value(
441        &mut self,
442        outputs: &HashMap<transparent::OutPoint, transparent::Output>,
443    ) -> Result<Amount<NonNegative>, ValueBalanceError> {
444        if self.is_coinbase() {
445            // TODO: if needed, fixup coinbase:
446            // - miner subsidy
447            // - founders reward or funding streams (hopefully not?)
448            // - remaining transaction value
449
450            // Act as if the generated test case spends all the miner subsidy, miner fees, and
451            // founders reward / funding stream correctly.
452            return Ok(Amount::zero());
453        }
454
455        let mut remaining_input_value = self.input_value_pool(outputs)?;
456
457        // assign remaining input value to outputs,
458        // zeroing any outputs that would exceed the input value
459
460        for output_value in self.output_values_mut() {
461            if remaining_input_value >= *output_value {
462                remaining_input_value = (remaining_input_value - *output_value)
463                    .expect("input >= output so result is always non-negative");
464            } else {
465                *output_value = Amount::zero();
466            }
467        }
468
469        for output_value in self.output_values_to_sprout_mut() {
470            if remaining_input_value >= *output_value {
471                remaining_input_value = (remaining_input_value - *output_value)
472                    .expect("input >= output so result is always non-negative");
473            } else {
474                *output_value = Amount::zero();
475            }
476        }
477
478        if let Some(value_balance) = self.sapling_value_balance_mut() {
479            if let Ok(output_value) = value_balance.neg().constrain::<NonNegative>() {
480                if remaining_input_value >= output_value {
481                    remaining_input_value = (remaining_input_value - output_value)
482                        .expect("input >= output so result is always non-negative");
483                } else {
484                    *value_balance = Amount::zero();
485                }
486            }
487        }
488
489        if let Some(value_balance) = self.orchard_value_balance_mut() {
490            if let Ok(output_value) = value_balance.neg().constrain::<NonNegative>() {
491                if remaining_input_value >= output_value {
492                    remaining_input_value = (remaining_input_value - output_value)
493                        .expect("input >= output so result is always non-negative");
494                } else {
495                    *value_balance = Amount::zero();
496                }
497            }
498        }
499
500        // check our calculations are correct
501        let remaining_transaction_value = self
502            .value_balance_from_outputs(outputs)
503            .expect("chain is limited to MAX_MONEY")
504            .remaining_transaction_value()
505            .unwrap_or_else(|err| {
506                panic!(
507                    "unexpected remaining transaction value: {err:?}, \
508                     calculated remaining input value: {remaining_input_value:?}"
509                )
510            });
511        assert_eq!(
512            remaining_input_value,
513            remaining_transaction_value,
514            "fix_remaining_value and remaining_transaction_value calculated different remaining values"
515        );
516
517        Ok(remaining_transaction_value)
518    }
519}
520
521impl Arbitrary for Memo {
522    type Parameters = ();
523
524    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
525        (vec(any::<u8>(), 512))
526            .prop_map(|v| {
527                let mut bytes = [0; 512];
528                bytes.copy_from_slice(v.as_slice());
529                Memo(Box::new(bytes))
530            })
531            .boxed()
532    }
533
534    type Strategy = BoxedStrategy<Self>;
535}
536
537/// Generates arbitrary [`LockTime`]s.
538impl Arbitrary for LockTime {
539    type Parameters = ();
540
541    fn arbitrary_with(_args: ()) -> Self::Strategy {
542        prop_oneof![
543            (block::Height::MIN.0..=LockTime::MAX_HEIGHT.0)
544                .prop_map(|n| LockTime::Height(block::Height(n))),
545            (LockTime::MIN_TIMESTAMP..=LockTime::MAX_TIMESTAMP).prop_map(|n| {
546                LockTime::Time(
547                    Utc.timestamp_opt(n, 0)
548                        .single()
549                        .expect("in-range number of seconds and valid nanosecond"),
550                )
551            })
552        ]
553        .boxed()
554    }
555
556    type Strategy = BoxedStrategy<Self>;
557}
558
559impl<P: ZkSnarkProof + Arbitrary + 'static> Arbitrary for JoinSplitData<P> {
560    type Parameters = ();
561
562    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
563        (
564            any::<sprout::JoinSplit<P>>(),
565            vec(any::<sprout::JoinSplit<P>>(), 0..MAX_ARBITRARY_ITEMS),
566            array::uniform32(any::<u8>()),
567            vec(any::<u8>(), 64),
568        )
569            .prop_map(|(first, rest, pub_key_bytes, sig_bytes)| Self {
570                first,
571                rest,
572                pub_key: ed25519_zebra::VerificationKeyBytes::from(pub_key_bytes),
573                sig: ed25519_zebra::Signature::from({
574                    let mut b = [0u8; 64];
575                    b.copy_from_slice(sig_bytes.as_slice());
576                    b
577                }),
578            })
579            .boxed()
580    }
581
582    type Strategy = BoxedStrategy<Self>;
583}
584
585impl<AnchorV> Arbitrary for sapling::ShieldedData<AnchorV>
586where
587    AnchorV: AnchorVariant + Clone + std::fmt::Debug + 'static,
588    sapling::TransferData<AnchorV>: Arbitrary,
589{
590    type Parameters = ();
591
592    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
593        (
594            any::<Amount>(),
595            any::<sapling::TransferData<AnchorV>>(),
596            vec(any::<u8>(), 64),
597        )
598            .prop_map(|(value_balance, transfers, sig_bytes)| Self {
599                value_balance,
600                transfers,
601                binding_sig: redjubjub::Signature::from({
602                    let mut b = [0u8; 64];
603                    b.copy_from_slice(sig_bytes.as_slice());
604                    b
605                }),
606            })
607            .boxed()
608    }
609
610    type Strategy = BoxedStrategy<Self>;
611}
612
613impl Arbitrary for sapling::TransferData<PerSpendAnchor> {
614    type Parameters = ();
615
616    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
617        vec(any::<sapling::Output>(), 0..MAX_ARBITRARY_ITEMS)
618            .prop_flat_map(|outputs| {
619                (
620                    if outputs.is_empty() {
621                        // must have at least one spend or output
622                        vec(
623                            any::<sapling::Spend<PerSpendAnchor>>(),
624                            1..MAX_ARBITRARY_ITEMS,
625                        )
626                    } else {
627                        vec(
628                            any::<sapling::Spend<PerSpendAnchor>>(),
629                            0..MAX_ARBITRARY_ITEMS,
630                        )
631                    },
632                    Just(outputs),
633                )
634            })
635            .prop_map(|(spends, outputs)| {
636                if !spends.is_empty() {
637                    sapling::TransferData::SpendsAndMaybeOutputs {
638                        shared_anchor: FieldNotPresent,
639                        spends: spends.try_into().unwrap(),
640                        maybe_outputs: outputs,
641                    }
642                } else if !outputs.is_empty() {
643                    sapling::TransferData::JustOutputs {
644                        outputs: outputs.try_into().unwrap(),
645                    }
646                } else {
647                    unreachable!("there must be at least one generated spend or output")
648                }
649            })
650            .boxed()
651    }
652
653    type Strategy = BoxedStrategy<Self>;
654}
655
656impl Arbitrary for sapling::TransferData<SharedAnchor> {
657    type Parameters = ();
658
659    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
660        vec(any::<sapling::Output>(), 0..MAX_ARBITRARY_ITEMS)
661            .prop_flat_map(|outputs| {
662                (
663                    any::<sapling::tree::Root>(),
664                    if outputs.is_empty() {
665                        // must have at least one spend or output
666                        vec(
667                            any::<sapling::Spend<SharedAnchor>>(),
668                            1..MAX_ARBITRARY_ITEMS,
669                        )
670                    } else {
671                        vec(
672                            any::<sapling::Spend<SharedAnchor>>(),
673                            0..MAX_ARBITRARY_ITEMS,
674                        )
675                    },
676                    Just(outputs),
677                )
678            })
679            .prop_map(|(shared_anchor, spends, outputs)| {
680                if !spends.is_empty() {
681                    sapling::TransferData::SpendsAndMaybeOutputs {
682                        shared_anchor,
683                        spends: spends.try_into().unwrap(),
684                        maybe_outputs: outputs,
685                    }
686                } else if !outputs.is_empty() {
687                    sapling::TransferData::JustOutputs {
688                        outputs: outputs.try_into().unwrap(),
689                    }
690                } else {
691                    unreachable!("there must be at least one generated spend or output")
692                }
693            })
694            .boxed()
695    }
696
697    type Strategy = BoxedStrategy<Self>;
698}
699
700impl Arbitrary for orchard::ShieldedData {
701    type Parameters = ();
702
703    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
704        (
705            any::<orchard::shielded_data::Flags>(),
706            any::<Amount>(),
707            any::<orchard::tree::Root>(),
708            any::<Halo2Proof>(),
709            vec(
710                any::<orchard::shielded_data::AuthorizedAction>(),
711                1..MAX_ARBITRARY_ITEMS,
712            ),
713            any::<BindingSignature>(),
714        )
715            .prop_map(
716                |(flags, value_balance, shared_anchor, proof, actions, binding_sig)| Self {
717                    flags,
718                    value_balance,
719                    shared_anchor,
720                    proof,
721                    actions: actions
722                        .try_into()
723                        .expect("arbitrary vector size range produces at least one action"),
724                    binding_sig: binding_sig.0,
725                },
726            )
727            .boxed()
728    }
729
730    type Strategy = BoxedStrategy<Self>;
731}
732
733#[derive(Copy, Clone, Debug, Eq, PartialEq)]
734struct BindingSignature(pub(crate) Signature<Binding>);
735
736impl Arbitrary for BindingSignature {
737    type Parameters = ();
738
739    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
740        (vec(any::<u8>(), 64))
741            .prop_filter_map(
742                "zero Signature::<Binding> values are invalid",
743                |sig_bytes| {
744                    let mut b = [0u8; 64];
745                    b.copy_from_slice(sig_bytes.as_slice());
746                    if b == [0u8; 64] {
747                        return None;
748                    }
749                    Some(BindingSignature(Signature::<Binding>::from(b)))
750                },
751            )
752            .boxed()
753    }
754
755    type Strategy = BoxedStrategy<Self>;
756}
757
758impl Arbitrary for Transaction {
759    type Parameters = LedgerState;
760
761    fn arbitrary_with(ledger_state: Self::Parameters) -> Self::Strategy {
762        match ledger_state.transaction_version_override() {
763            Some(1) => return Self::v1_strategy(ledger_state),
764            Some(2) => return Self::v2_strategy(ledger_state),
765            Some(3) => return Self::v3_strategy(ledger_state),
766            Some(4) => return Self::v4_strategy(ledger_state),
767            Some(5) => return Self::v5_strategy(ledger_state),
768            Some(_) => unreachable!("invalid transaction version in override"),
769            None => {}
770        }
771
772        match ledger_state.network_upgrade() {
773            NetworkUpgrade::Genesis | NetworkUpgrade::BeforeOverwinter => {
774                Self::v1_strategy(ledger_state)
775            }
776            NetworkUpgrade::Overwinter => Self::v2_strategy(ledger_state),
777            NetworkUpgrade::Sapling => Self::v3_strategy(ledger_state),
778            NetworkUpgrade::Blossom | NetworkUpgrade::Heartwood | NetworkUpgrade::Canopy => {
779                Self::v4_strategy(ledger_state)
780            }
781            NetworkUpgrade::Nu5
782            | NetworkUpgrade::Nu6
783            | NetworkUpgrade::Nu6_1
784            | NetworkUpgrade::Nu7 => prop_oneof![
785                Self::v4_strategy(ledger_state.clone()),
786                Self::v5_strategy(ledger_state)
787            ]
788            .boxed(),
789
790            #[cfg(zcash_unstable = "zfuture")]
791            NetworkUpgrade::ZFuture => prop_oneof![
792                Self::v4_strategy(ledger_state.clone()),
793                Self::v5_strategy(ledger_state)
794            ]
795            .boxed(),
796        }
797    }
798
799    type Strategy = BoxedStrategy<Self>;
800}
801
802impl Arbitrary for UnminedTx {
803    type Parameters = ();
804
805    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
806        any::<Transaction>().prop_map_into().boxed()
807    }
808
809    type Strategy = BoxedStrategy<Self>;
810}
811
812impl Arbitrary for VerifiedUnminedTx {
813    type Parameters = ();
814
815    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
816        (
817            any::<UnminedTx>(),
818            any::<Amount<NonNegative>>(),
819            any::<u32>(),
820            any::<(u16, u16)>().prop_map(|(unpaid_actions, conventional_actions)| {
821                (
822                    unpaid_actions % conventional_actions.saturating_add(1),
823                    conventional_actions,
824                )
825            }),
826            any::<f32>(),
827            serialization::arbitrary::datetime_u32(),
828            any::<block::Height>(),
829        )
830            .prop_map(
831                |(
832                    transaction,
833                    miner_fee,
834                    sigops,
835                    (conventional_actions, mut unpaid_actions),
836                    fee_weight_ratio,
837                    time,
838                    height,
839                )| {
840                    if unpaid_actions > conventional_actions {
841                        unpaid_actions = conventional_actions;
842                    }
843
844                    let conventional_actions = conventional_actions as u32;
845                    let unpaid_actions = unpaid_actions as u32;
846
847                    Self {
848                        transaction,
849                        miner_fee,
850                        sigops,
851                        conventional_actions,
852                        unpaid_actions,
853                        fee_weight_ratio,
854                        time: Some(time),
855                        height: Some(height),
856                    }
857                },
858            )
859            .boxed()
860    }
861    type Strategy = BoxedStrategy<Self>;
862}
863
864// Utility functions
865
866/// Convert `trans` into a fake v5 transaction,
867/// converting sapling shielded data from v4 to v5 if possible.
868pub fn transaction_to_fake_v5(
869    trans: &Transaction,
870    network: &Network,
871    height: block::Height,
872) -> Transaction {
873    use Transaction::*;
874
875    let block_nu = NetworkUpgrade::current(network, height);
876
877    match trans {
878        V1 {
879            inputs,
880            outputs,
881            lock_time,
882        } => V5 {
883            network_upgrade: block_nu,
884            inputs: inputs.to_vec(),
885            outputs: outputs.to_vec(),
886            lock_time: *lock_time,
887            expiry_height: height,
888            sapling_shielded_data: None,
889            orchard_shielded_data: None,
890        },
891        V2 {
892            inputs,
893            outputs,
894            lock_time,
895            ..
896        } => V5 {
897            network_upgrade: block_nu,
898            inputs: inputs.to_vec(),
899            outputs: outputs.to_vec(),
900            lock_time: *lock_time,
901            expiry_height: height,
902            sapling_shielded_data: None,
903            orchard_shielded_data: None,
904        },
905        V3 {
906            inputs,
907            outputs,
908            lock_time,
909            ..
910        } => V5 {
911            network_upgrade: block_nu,
912            inputs: inputs.to_vec(),
913            outputs: outputs.to_vec(),
914            lock_time: *lock_time,
915            expiry_height: height,
916            sapling_shielded_data: None,
917            orchard_shielded_data: None,
918        },
919        V4 {
920            inputs,
921            outputs,
922            lock_time,
923            sapling_shielded_data,
924            ..
925        } => V5 {
926            network_upgrade: block_nu,
927            inputs: inputs.to_vec(),
928            outputs: outputs.to_vec(),
929            lock_time: *lock_time,
930            expiry_height: height,
931            sapling_shielded_data: sapling_shielded_data
932                .clone()
933                .and_then(sapling_shielded_v4_to_fake_v5),
934            orchard_shielded_data: None,
935        },
936        v5 @ V5 { .. } => v5.clone(),
937        #[cfg(feature = "tx_v6")]
938        v6 @ V6 { .. } => v6.clone(),
939    }
940}
941
942/// Convert a v4 sapling shielded data into a fake v5 sapling shielded data,
943/// if possible.
944fn sapling_shielded_v4_to_fake_v5(
945    v4_shielded: sapling::ShieldedData<PerSpendAnchor>,
946) -> Option<sapling::ShieldedData<SharedAnchor>> {
947    use sapling::ShieldedData;
948    use sapling::TransferData::*;
949
950    let unique_anchors: Vec<_> = v4_shielded
951        .spends()
952        .map(|spend| spend.per_spend_anchor)
953        .unique()
954        .collect();
955
956    let fake_spends: Vec<_> = v4_shielded
957        .spends()
958        .cloned()
959        .map(sapling_spend_v4_to_fake_v5)
960        .collect();
961
962    let transfers = match v4_shielded.transfers {
963        SpendsAndMaybeOutputs { maybe_outputs, .. } => {
964            let shared_anchor = match unique_anchors.as_slice() {
965                [unique_anchor] => *unique_anchor,
966                // Multiple different anchors, can't convert to v5
967                _ => return None,
968            };
969
970            SpendsAndMaybeOutputs {
971                shared_anchor,
972                spends: fake_spends.try_into().unwrap(),
973                maybe_outputs,
974            }
975        }
976        JustOutputs { outputs } => JustOutputs { outputs },
977    };
978
979    let fake_shielded_v5 = ShieldedData::<SharedAnchor> {
980        value_balance: v4_shielded.value_balance,
981        transfers,
982        binding_sig: v4_shielded.binding_sig,
983    };
984
985    Some(fake_shielded_v5)
986}
987
988/// Convert a v4 sapling spend into a fake v5 sapling spend.
989fn sapling_spend_v4_to_fake_v5(
990    v4_spend: sapling::Spend<PerSpendAnchor>,
991) -> sapling::Spend<SharedAnchor> {
992    use sapling::Spend;
993
994    Spend::<SharedAnchor> {
995        cv: v4_spend.cv,
996        per_spend_anchor: FieldNotPresent,
997        nullifier: v4_spend.nullifier,
998        rk: v4_spend.rk,
999        zkproof: v4_spend.zkproof,
1000        spend_auth_sig: v4_spend.spend_auth_sig,
1001    }
1002}
1003
1004/// Iterate over V4 transactions in the block test vectors for the specified `network`.
1005pub fn test_transactions(
1006    network: &Network,
1007) -> impl DoubleEndedIterator<Item = (block::Height, Arc<Transaction>)> {
1008    let blocks = network.block_iter();
1009
1010    transactions_from_blocks(blocks)
1011}
1012
1013/// Returns an iterator over V5 transactions extracted from the given blocks.
1014pub fn v5_transactions<'b>(
1015    blocks: impl DoubleEndedIterator<Item = (&'b u32, &'b &'static [u8])> + 'b,
1016) -> impl DoubleEndedIterator<Item = Transaction> + 'b {
1017    transactions_from_blocks(blocks).filter_map(|(_, tx)| match *tx {
1018        Transaction::V1 { .. }
1019        | Transaction::V2 { .. }
1020        | Transaction::V3 { .. }
1021        | Transaction::V4 { .. } => None,
1022        ref tx @ Transaction::V5 { .. } => Some(tx.clone()),
1023        #[cfg(feature = "tx_v6")]
1024        ref tx @ Transaction::V6 { .. } => Some(tx.clone()),
1025    })
1026}
1027
1028/// Generate an iterator over ([`block::Height`], [`Arc<Transaction>`]).
1029pub fn transactions_from_blocks<'a>(
1030    blocks: impl DoubleEndedIterator<Item = (&'a u32, &'a &'static [u8])> + 'a,
1031) -> impl DoubleEndedIterator<Item = (block::Height, Arc<Transaction>)> + 'a {
1032    blocks.flat_map(|(&block_height, &block_bytes)| {
1033        let block = block_bytes
1034            .zcash_deserialize_into::<block::Block>()
1035            .expect("block is structurally valid");
1036
1037        block
1038            .transactions
1039            .into_iter()
1040            .map(move |transaction| (block::Height(block_height), transaction))
1041    })
1042}
1043
1044/// Modify a V5 transaction to insert fake Orchard shielded data.
1045///
1046/// Creates a fake instance of [`orchard::ShieldedData`] with one fake action. Note that both the
1047/// action and the shielded data are invalid and shouldn't be used in tests that require them to be
1048/// valid.
1049///
1050/// A mutable reference to the inserted shielded data is returned, so that the caller can further
1051/// customize it if required.
1052///
1053/// # Panics
1054///
1055/// Panics if the transaction to be modified is not V5.
1056pub fn insert_fake_orchard_shielded_data(
1057    transaction: &mut Transaction,
1058) -> &mut orchard::ShieldedData {
1059    // Create a dummy action
1060    let mut runner = TestRunner::default();
1061    let dummy_action = orchard::Action::arbitrary()
1062        .new_tree(&mut runner)
1063        .unwrap()
1064        .current();
1065
1066    // Pair the dummy action with a fake signature
1067    let dummy_authorized_action = orchard::AuthorizedAction {
1068        action: dummy_action,
1069        spend_auth_sig: Signature::from([0u8; 64]),
1070    };
1071
1072    // Place the dummy action inside the Orchard shielded data
1073    let dummy_shielded_data = orchard::ShieldedData {
1074        flags: orchard::Flags::empty(),
1075        value_balance: Amount::try_from(0).expect("invalid transaction amount"),
1076        shared_anchor: orchard::tree::Root::default(),
1077        proof: Halo2Proof(vec![]),
1078        actions: at_least_one![dummy_authorized_action],
1079        binding_sig: Signature::from([0u8; 64]),
1080    };
1081
1082    // Replace the shielded data in the transaction
1083    match transaction {
1084        Transaction::V5 {
1085            orchard_shielded_data,
1086            ..
1087        } => {
1088            *orchard_shielded_data = Some(dummy_shielded_data);
1089
1090            orchard_shielded_data
1091                .as_mut()
1092                .expect("shielded data was just inserted")
1093        }
1094        _ => panic!("Fake V5 transaction is not V5"),
1095    }
1096}