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    }
791
792    type Strategy = BoxedStrategy<Self>;
793}
794
795impl Arbitrary for UnminedTx {
796    type Parameters = ();
797
798    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
799        any::<Transaction>().prop_map_into().boxed()
800    }
801
802    type Strategy = BoxedStrategy<Self>;
803}
804
805impl Arbitrary for VerifiedUnminedTx {
806    type Parameters = ();
807
808    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
809        (
810            any::<UnminedTx>(),
811            any::<Amount<NonNegative>>(),
812            any::<u64>(),
813            any::<(u16, u16)>().prop_map(|(unpaid_actions, conventional_actions)| {
814                (
815                    unpaid_actions % conventional_actions.saturating_add(1),
816                    conventional_actions,
817                )
818            }),
819            any::<f32>(),
820            serialization::arbitrary::datetime_u32(),
821            any::<block::Height>(),
822        )
823            .prop_map(
824                |(
825                    transaction,
826                    miner_fee,
827                    legacy_sigop_count,
828                    (conventional_actions, mut unpaid_actions),
829                    fee_weight_ratio,
830                    time,
831                    height,
832                )| {
833                    if unpaid_actions > conventional_actions {
834                        unpaid_actions = conventional_actions;
835                    }
836
837                    let conventional_actions = conventional_actions as u32;
838                    let unpaid_actions = unpaid_actions as u32;
839
840                    Self {
841                        transaction,
842                        miner_fee,
843                        legacy_sigop_count,
844                        conventional_actions,
845                        unpaid_actions,
846                        fee_weight_ratio,
847                        time: Some(time),
848                        height: Some(height),
849                    }
850                },
851            )
852            .boxed()
853    }
854    type Strategy = BoxedStrategy<Self>;
855}
856
857// Utility functions
858
859/// Convert `trans` into a fake v5 transaction,
860/// converting sapling shielded data from v4 to v5 if possible.
861pub fn transaction_to_fake_v5(
862    trans: &Transaction,
863    network: &Network,
864    height: block::Height,
865) -> Transaction {
866    use Transaction::*;
867
868    let block_nu = NetworkUpgrade::current(network, height);
869
870    match trans {
871        V1 {
872            inputs,
873            outputs,
874            lock_time,
875        } => V5 {
876            network_upgrade: block_nu,
877            inputs: inputs.to_vec(),
878            outputs: outputs.to_vec(),
879            lock_time: *lock_time,
880            expiry_height: height,
881            sapling_shielded_data: None,
882            orchard_shielded_data: None,
883        },
884        V2 {
885            inputs,
886            outputs,
887            lock_time,
888            ..
889        } => V5 {
890            network_upgrade: block_nu,
891            inputs: inputs.to_vec(),
892            outputs: outputs.to_vec(),
893            lock_time: *lock_time,
894            expiry_height: height,
895            sapling_shielded_data: None,
896            orchard_shielded_data: None,
897        },
898        V3 {
899            inputs,
900            outputs,
901            lock_time,
902            ..
903        } => V5 {
904            network_upgrade: block_nu,
905            inputs: inputs.to_vec(),
906            outputs: outputs.to_vec(),
907            lock_time: *lock_time,
908            expiry_height: height,
909            sapling_shielded_data: None,
910            orchard_shielded_data: None,
911        },
912        V4 {
913            inputs,
914            outputs,
915            lock_time,
916            sapling_shielded_data,
917            ..
918        } => V5 {
919            network_upgrade: block_nu,
920            inputs: inputs.to_vec(),
921            outputs: outputs.to_vec(),
922            lock_time: *lock_time,
923            expiry_height: height,
924            sapling_shielded_data: sapling_shielded_data
925                .clone()
926                .and_then(sapling_shielded_v4_to_fake_v5),
927            orchard_shielded_data: None,
928        },
929        v5 @ V5 { .. } => v5.clone(),
930        #[cfg(feature = "tx_v6")]
931        v6 @ V6 { .. } => v6.clone(),
932    }
933}
934
935/// Convert a v4 sapling shielded data into a fake v5 sapling shielded data,
936/// if possible.
937fn sapling_shielded_v4_to_fake_v5(
938    v4_shielded: sapling::ShieldedData<PerSpendAnchor>,
939) -> Option<sapling::ShieldedData<SharedAnchor>> {
940    use sapling::ShieldedData;
941    use sapling::TransferData::*;
942
943    let unique_anchors: Vec<_> = v4_shielded
944        .spends()
945        .map(|spend| spend.per_spend_anchor)
946        .unique()
947        .collect();
948
949    let fake_spends: Vec<_> = v4_shielded
950        .spends()
951        .cloned()
952        .map(sapling_spend_v4_to_fake_v5)
953        .collect();
954
955    let transfers = match v4_shielded.transfers {
956        SpendsAndMaybeOutputs { maybe_outputs, .. } => {
957            let shared_anchor = match unique_anchors.as_slice() {
958                [unique_anchor] => *unique_anchor,
959                // Multiple different anchors, can't convert to v5
960                _ => return None,
961            };
962
963            SpendsAndMaybeOutputs {
964                shared_anchor,
965                spends: fake_spends.try_into().unwrap(),
966                maybe_outputs,
967            }
968        }
969        JustOutputs { outputs } => JustOutputs { outputs },
970    };
971
972    let fake_shielded_v5 = ShieldedData::<SharedAnchor> {
973        value_balance: v4_shielded.value_balance,
974        transfers,
975        binding_sig: v4_shielded.binding_sig,
976    };
977
978    Some(fake_shielded_v5)
979}
980
981/// Convert a v4 sapling spend into a fake v5 sapling spend.
982fn sapling_spend_v4_to_fake_v5(
983    v4_spend: sapling::Spend<PerSpendAnchor>,
984) -> sapling::Spend<SharedAnchor> {
985    use sapling::Spend;
986
987    Spend::<SharedAnchor> {
988        cv: v4_spend.cv,
989        per_spend_anchor: FieldNotPresent,
990        nullifier: v4_spend.nullifier,
991        rk: v4_spend.rk,
992        zkproof: v4_spend.zkproof,
993        spend_auth_sig: v4_spend.spend_auth_sig,
994    }
995}
996
997/// Iterate over V4 transactions in the block test vectors for the specified `network`.
998pub fn test_transactions(
999    network: &Network,
1000) -> impl DoubleEndedIterator<Item = (block::Height, Arc<Transaction>)> {
1001    let blocks = network.block_iter();
1002
1003    transactions_from_blocks(blocks)
1004}
1005
1006/// Returns an iterator over V5 transactions extracted from the given blocks.
1007pub fn v5_transactions<'b>(
1008    blocks: impl DoubleEndedIterator<Item = (&'b u32, &'b &'static [u8])> + 'b,
1009) -> impl DoubleEndedIterator<Item = Transaction> + 'b {
1010    transactions_from_blocks(blocks).filter_map(|(_, tx)| match *tx {
1011        Transaction::V1 { .. }
1012        | Transaction::V2 { .. }
1013        | Transaction::V3 { .. }
1014        | Transaction::V4 { .. } => None,
1015        ref tx @ Transaction::V5 { .. } => Some(tx.clone()),
1016        #[cfg(feature = "tx_v6")]
1017        ref tx @ Transaction::V6 { .. } => Some(tx.clone()),
1018    })
1019}
1020
1021/// Generate an iterator over ([`block::Height`], [`Arc<Transaction>`]).
1022pub fn transactions_from_blocks<'a>(
1023    blocks: impl DoubleEndedIterator<Item = (&'a u32, &'a &'static [u8])> + 'a,
1024) -> impl DoubleEndedIterator<Item = (block::Height, Arc<Transaction>)> + 'a {
1025    blocks.flat_map(|(&block_height, &block_bytes)| {
1026        let block = block_bytes
1027            .zcash_deserialize_into::<block::Block>()
1028            .expect("block is structurally valid");
1029
1030        block
1031            .transactions
1032            .into_iter()
1033            .map(move |transaction| (block::Height(block_height), transaction))
1034    })
1035}
1036
1037/// Modify a V5 transaction to insert fake Orchard shielded data.
1038///
1039/// Creates a fake instance of [`orchard::ShieldedData`] with one fake action. Note that both the
1040/// action and the shielded data are invalid and shouldn't be used in tests that require them to be
1041/// valid.
1042///
1043/// A mutable reference to the inserted shielded data is returned, so that the caller can further
1044/// customize it if required.
1045///
1046/// # Panics
1047///
1048/// Panics if the transaction to be modified is not V5.
1049pub fn insert_fake_orchard_shielded_data(
1050    transaction: &mut Transaction,
1051) -> &mut orchard::ShieldedData {
1052    // Create a dummy action
1053    let mut runner = TestRunner::default();
1054    let dummy_action = orchard::Action::arbitrary()
1055        .new_tree(&mut runner)
1056        .unwrap()
1057        .current();
1058
1059    // Pair the dummy action with a fake signature
1060    let dummy_authorized_action = orchard::AuthorizedAction {
1061        action: dummy_action,
1062        spend_auth_sig: Signature::from([0u8; 64]),
1063    };
1064
1065    // Place the dummy action inside the Orchard shielded data
1066    let dummy_shielded_data = orchard::ShieldedData {
1067        flags: orchard::Flags::empty(),
1068        value_balance: Amount::try_from(0).expect("invalid transaction amount"),
1069        shared_anchor: orchard::tree::Root::default(),
1070        proof: Halo2Proof(vec![]),
1071        actions: at_least_one![dummy_authorized_action],
1072        binding_sig: Signature::from([0u8; 64]),
1073    };
1074
1075    // Replace the shielded data in the transaction
1076    match transaction {
1077        Transaction::V5 {
1078            orchard_shielded_data,
1079            ..
1080        } => {
1081            *orchard_shielded_data = Some(dummy_shielded_data);
1082
1083            orchard_shielded_data
1084                .as_mut()
1085                .expect("shielded data was just inserted")
1086        }
1087        _ => panic!("Fake V5 transaction is not V5"),
1088    }
1089}