Skip to main content

tributary_framework/
block.rs

1use core::time::Duration;
2use alloc::boxed::Box;
3use std::{io, time::SystemTime};
4
5use blake2::{digest::Digest as _, Blake2b256};
6
7use crate::{
8  ReadWrite, Slash,
9  transaction::{TransactionError, Signed, TransactionKind, Transaction},
10};
11
12/// An error with regards to a block's validity.
13#[derive(Clone, Debug)]
14pub enum SyntacticError {
15  /// The block exceeded the size limit.
16  ExceededSizeLimit {
17    /// The size of the block when serialized.
18    ///
19    /// This may be `None` if this value couldn't be or wasn't calculated.
20    size: Option<usize>,
21  },
22  /// The block's header specified Merkle tree roots for distinct contents.
23  IncorrectContents,
24  /// The block's timestamp was absurd.
25  ///
26  /// This is determined with respect to the system's representation of time ([`SystemTime`]).
27  AbsurdTime,
28  /// The block's contents weren't ordered as expected.
29  ///
30  /// The presence of conflicting contents will be considered an invalid ordering.
31  IncorrectOrderOfContents,
32  /// An invalid transaction was included.
33  Transaction(TransactionError),
34}
35
36impl From<TransactionError> for SyntacticError {
37  fn from(error: TransactionError) -> SyntacticError {
38    SyntacticError::Transaction(error)
39  }
40}
41
42/// An error with regards to a block's validity once contextualized by the blockchain.
43#[derive(Clone, Debug)]
44pub enum SemanticError {
45  /// The block's time is too close to the prior block's.
46  TooSoon,
47  /// A slash had an invalid reason.
48  InvalidSlash {
49    /// The validator the slash was for.
50    validator: [u8; 32],
51  },
52  /// An included slash slashes a validator who has already been slashed.
53  SlashAlreadyIncluded {
54    /// The validator the slash was for.
55    validator: [u8; 32],
56  },
57  /// The provided transaction was distinct from the locally provided transaction.
58  DistinctProvided {
59    /// The provided transactions' scope.
60    scope: &'static str,
61    /// The hash of the provided transaction included in this block.
62    transaction_hash: [u8; 32],
63    /// The hash of the expected provided transaction.
64    expected_hash: [u8; 32],
65  },
66  /// An unsigned transaction included in this block was already included on the blockchain.
67  UnsignedAlreadyIncluded {
68    /// The hash of the unsigned transaction which was already included.
69    transaction_hash: [u8; 32],
70  },
71  /// The signer of this transaction was invalid within the blockchain's context.
72  ///
73  /// The signer either was not a validator of the Tributary _or_ was a validator who had a slash
74  /// included on-chain.
75  InvalidSigner {
76    /// The invalid signer who signed a transaction included in this block.
77    signer: [u8; 32],
78  },
79  /// There is a gap between a transaction included in this block and the last relevant transaction
80  /// included on-chain.
81  Gap {
82    /// The hash of the transaction included in this block.
83    transaction_hash: [u8; 32],
84    /// The nonce of the transaction included in this block.
85    transaction_nonce: u64,
86    /// The expected nonce for the next transaction within the same scope.
87    ///
88    /// This will be `None` on overflow.
89    expected_nonce: Option<u64>,
90  },
91}
92
93/// An error with regards to a block's validity _per the local view_.
94#[derive(Clone, Debug)]
95pub enum EphemeralError {
96  /// The block's header specified a parent which wasn't the chain tip.
97  UnexpectedParent,
98  /// This block occurs in the future.
99  Future,
100  /// The block had a provided transaction this validator has yet to provide.
101  NotLocallyProvidedTransaction {
102    /// The provided transaction's scope.
103    scope: &'static str,
104    /// The hash of the provided transaction included in this block.
105    transaction_hash: [u8; 32],
106  },
107}
108
109/// An error with a block.
110#[derive(Clone, Debug)]
111pub enum BlockError {
112  /// An error with regards to a block's validity.
113  Syntactic(SyntacticError),
114  /// An error with regards to a block's validity once contextualized by the blockchain.
115  Semantic(SemanticError),
116  /// An error with regards to a block's validity _per the local view_.
117  Ephemeral(EphemeralError),
118}
119
120impl From<SyntacticError> for BlockError {
121  fn from(error: SyntacticError) -> BlockError {
122    BlockError::Syntactic(error)
123  }
124}
125
126impl From<TransactionError> for BlockError {
127  fn from(error: TransactionError) -> BlockError {
128    BlockError::from(SyntacticError::from(error))
129  }
130}
131
132impl From<SemanticError> for BlockError {
133  fn from(error: SemanticError) -> BlockError {
134    BlockError::Semantic(error)
135  }
136}
137
138impl From<EphemeralError> for BlockError {
139  fn from(error: EphemeralError) -> BlockError {
140    BlockError::Ephemeral(error)
141  }
142}
143
144/// The header for a block.
145///
146/// This is binding to the block's ancestry and contents. It allows creating a view of every block
147/// on the blockchain, without syncing each individual block. Combined with a consensus commitment
148/// for the most recent block on the blockchain, this can certify agreement over an entire
149/// blockchain without syncing any transactions.
150///
151/// This is a fixed-size container. It is defined as the 104-byte concatenation of:
152/// - the block's parent's hash
153/// - the little-endian encoding of the eight-byte quantity of milliseconds since the epoch
154/// - the Merkle tree root for the slashes within this block
155/// - the Merkle tree root for the transactions within this block
156///
157/// Including the block's time in the header is an unfortunate byproduct of implementing a minimum
158/// spacing between blocks. Such a spacing effectively requires knowing when a block was proposed,
159/// to know when the next block should be proposed.
160///
161/// Commitments from consensus, as needed to certify agreement on this block, are intentionally
162/// left separate. Consensus commitments are not canonical and any unnecessary or redundant
163/// commitments MAY be pruned.
164/*
165  TODO: Should this include the block's _number_? Then we could distinguish between
166  `UnexpectedParent` as an ephemeral error with the local view and as a semantic error.
167*/
168/*
169  TODO: Should we define the parent hash as a Merkle tree, not a line of hashes? This would enable
170  optimizing the sync protocol by requesting different chunks from different validators. We just
171  have to deal with the complexity of so defining it. While the Serai libraries do define a
172  incremental Merkle tree, if we do not wish to directly depend on those libraries, we'd have to
173  write one when the data structure only really makes sense when backed by the underlying database.
174
175  That isn't unacceptable, it just questions the functionality vs. the complexity of the
176  Tributary Framework.
177*/
178#[derive(Clone, Copy, Debug)]
179#[cfg_attr(test, derive(PartialEq, Eq))]
180pub struct BlockHeader {
181  parent: [u8; 32],
182  time: u64,
183  slashes: [u8; 32],
184  transactions: [u8; 32],
185}
186
187impl ReadWrite for BlockHeader {
188  fn read(mut reader: impl io::Read) -> io::Result<Self> {
189    let parent = {
190      let mut parent = [0; 32];
191      reader.read_exact(&mut parent)?;
192      parent
193    };
194    let time = {
195      let mut time = [0; 8];
196      reader.read_exact(&mut time)?;
197      u64::from_le_bytes(time)
198    };
199    let slashes = {
200      let mut slashes = [0; 32];
201      reader.read_exact(&mut slashes)?;
202      slashes
203    };
204    let transactions = {
205      let mut transactions = [0; 32];
206      reader.read_exact(&mut transactions)?;
207      transactions
208    };
209    Ok(Self { parent, time, slashes, transactions })
210  }
211
212  fn write(&self, mut writer: impl io::Write) -> io::Result<()> {
213    let Self { parent, time, slashes, transactions } = self;
214    writer.write_all(parent)?;
215    writer.write_all(&time.to_le_bytes())?;
216    writer.write_all(slashes)?;
217    writer.write_all(transactions)
218  }
219}
220
221impl crate::merkle::Digestible for BlockHeader {
222  fn update(&self, digest: &mut (impl ?Sized + blake2::digest::Update)) {
223    self.write(crate::merkle::DigestWriter(digest)).expect("`DigestWriter` is infallible");
224  }
225}
226
227impl BlockHeader {
228  const SIZE: usize = 32 + 8 + 32 + 32;
229
230  /// The parent this builds upon.
231  ///
232  /// This will be the genesis if this is the first block on the blockchain.
233  pub fn parent(&self) -> [u8; 32] {
234    self.parent
235  }
236
237  /// The time embedded within this block header.
238  ///
239  /// This is represented in milliseconds since the epoch.
240  pub fn time(&self) -> u64 {
241    self.time
242  }
243
244  /// The slashes this block header commits to.
245  pub fn slashes(&self) -> [u8; 32] {
246    self.slashes
247  }
248
249  /// The transactions this block header commits to.
250  pub fn transactions(&self) -> [u8; 32] {
251    self.transactions
252  }
253
254  /// The hash for this block header.
255  ///
256  /// The hash is the BLAKE2b-256 hash (without any personalization) of the block header's
257  /// serialization.
258  pub fn hash(&self) -> [u8; 32] {
259    crate::merkle::Digestible::chain_update(self, Blake2b256::new()).finalize().into()
260  }
261}
262
263/// A block.
264///
265/// A block is defined as its header, a list of slashes, amd a list of transactions, as committed
266/// to within the block's header.
267///
268/// The slashes MUST be sorted by the slashed validator.
269///
270/// The transactions MUST be ordered as provided, unsigned, signed, with:
271/// - The provided transactions sorted by their scopes
272/// - The unsigned transactions sorted by their hashes
273/// - The signed transactions sorted by their signers, then their scopes, then their nonces
274///
275/// These strict requirements on ordering allow single-pass verification, without any dynamic
276/// allocations, that a block is free of conflicting unsigned/signed transactions (a problem which
277/// is considered an instance of an invalid ordering). It also allows checking provided
278/// transactions one scope at a time, and straight-line application of a block's signed
279/// transactions, after having prioritized the provided and unsigned transactions which imply some
280/// level of recognition within the application.
281///
282/// The Tributary DOES NOT enforce the uniqueness of signed transactions' hashes, where signed
283/// transactions' hashes MUST bind to all of their semantic contents.
284///
285/// The block's serialization prefixes the list of slashes with the two-byte little-endian encoding
286/// of its length and the list of transactions with the four-byte little-endian encoding of its
287/// length. The limit on slashes is complete as there are at most [`u16::MAX`] validators. The
288/// limit on transactions is practical and enforced as a syntactic requirement.
289#[derive(Clone, Debug)]
290pub struct Block<T: Transaction> {
291  header: BlockHeader,
292  slashes: Box<[Slash]>,
293  transactions: Box<[T]>,
294}
295
296impl<T: Transaction> ReadWrite for Block<T> {
297  /// This will read a block with no size limits applied. While this will not reserve capacity for
298  /// the _alleged_ length of lists, meaning the amount of memory consumed is proportional to the
299  /// amount of bytes read, the caller is expected to ensure they are prepared to read this block
300  /// in its entirety.
301  ///
302  /// Applications SHOULD apply their own size limit to the reader itself to prevent a potential
303  /// Denial of Service by transmitting several GB of data which, if deserialized, will then be
304  /// stored in memory.
305  fn read(mut reader: impl io::Read) -> io::Result<Self> {
306    let header = BlockHeader::read(&mut reader)?;
307
308    let slashes = (0 .. {
309      let mut slashes = [0; 2];
310      reader.read_exact(&mut slashes)?;
311      u16::from_le_bytes(slashes)
312    })
313      .map(|_| Slash::read(&mut reader))
314      .collect::<Result<Box<[_]>, _>>()?;
315
316    let transactions = (0 .. {
317      let mut transactions = [0; 4];
318      reader.read_exact(&mut transactions)?;
319      u32::from_le_bytes(transactions)
320    })
321      .map(|_| T::read(&mut reader))
322      .collect::<Result<Box<[_]>, _>>()?;
323
324    Ok(Block { header, slashes, transactions })
325  }
326
327  fn write(&self, mut writer: impl io::Write) -> io::Result<()> {
328    let Block { header, slashes, transactions } = self;
329    header.write(&mut writer)?;
330
331    writer.write_all(
332      &u16::try_from(slashes.len())
333        .map_err(|_| io::Error::other("block has more slashes than validators"))?
334        .to_le_bytes(),
335    )?;
336    for slash in slashes {
337      slash.write(&mut writer)?;
338    }
339
340    writer.write_all(
341      &u32::try_from(transactions.len())
342        .map_err(|_| io::Error::other("block has more than four billion transactions"))?
343        .to_le_bytes(),
344    )?;
345    for tx in transactions {
346      tx.write(&mut writer)?;
347    }
348
349    Ok(())
350  }
351}
352
353impl<T: Transaction> Block<T> {
354  /// The serialized length of an empty block.
355  ///
356  /// This is equal to the serialized length of a block header, followed by the lengths of the
357  /// (empty) list of slashes and the (empty) list of transactions.
358  pub(crate) const EMPTY_BLOCK_SIZE: usize = BlockHeader::SIZE + 2 + 4;
359
360  /// This block's time, represented as a `SystemTime`.
361  pub(crate) fn system_time(&self) -> Result<SystemTime, SyntacticError> {
362    let Some(time) = SystemTime::UNIX_EPOCH.checked_add(Duration::from_millis(self.time())) else {
363      // This block's time is absurd
364      Err(SyntacticError::AbsurdTime)?
365    };
366    Ok(time)
367  }
368
369  fn verify_syntax_slashes<'block>(
370    slashes: impl IntoIterator<Item = &'block Slash>,
371  ) -> Result<(), SyntacticError> {
372    slashes
373      .into_iter()
374      .is_sorted_by(|a, b| a.validator() < b.validator())
375      .ok_or(SyntacticError::IncorrectOrderOfContents)
376  }
377
378  fn verify_syntax_transactions<'block>(
379    genesis: [u8; 32],
380    transactions: impl IntoIterator<Item = &'block T>,
381  ) -> Result<(), SyntacticError>
382  where
383    T: 'block,
384  {
385    /*
386      We check the ordering by checking the following tuple is greater with each iteration of the
387      loop. This takes advantage of how `(T1, Tn, ...)` implements `PartialOrd` by comparing the
388      first element, and only on equality, comparing the next element (until the tuple is
389      exhausted).
390    */
391    #[expect(clippy::type_complexity)]
392    let mut order: (
393      u8,
394      Option<&'static [u8]>,
395      Option<[u8; 32]>,
396      Option<([u8; 32], Box<[u8]>, u64)>,
397    ) = (0, None, None, None);
398
399    for transaction in transactions {
400      let new_order = match transaction.kind() {
401        TransactionKind::Provided { scope } => (0, Some(scope.as_bytes()), None, None),
402        TransactionKind::Unsigned => (1, None, Some(transaction.hash()), None),
403        TransactionKind::Signed { scope, signed: Signed { signer, nonce, signature: _ } } => {
404          /*
405            If the last transaction was by this signer, within this scope, check this pair of
406            transactions is contiguous and there's no gap between them.
407          */
408          if let Some((prior_signer, ref prior_scope, prior_nonce)) = order.3 &&
409            (prior_signer == signer) &&
410            (prior_scope == &scope) &&
411            (prior_nonce.checked_add(1) != Some(nonce))
412          {
413            Err(SyntacticError::IncorrectOrderOfContents)?;
414          }
415
416          (2, None, None, Some((signer, scope, nonce)))
417        }
418      };
419
420      // If this is a provided transaction...
421      if order.0 == 0 {
422        // Require scopes be sequential, but allow multiple transactions within a scope
423        // (which all have the same order from a syntactic perspective)
424        if new_order < order {
425          Err(SyntacticError::IncorrectOrderOfContents)?;
426        }
427      } else if new_order <= order {
428        // If this isn't a provided transaction, require strictly increasing orders
429        Err(SyntacticError::IncorrectOrderOfContents)?;
430      }
431      order = new_order;
432
433      crate::transaction::verify_syntax(transaction, genesis)?;
434    }
435
436    Ok(())
437  }
438
439  /// Verify this block's syntax.
440  ///
441  /// This is a check which can be performed without any context or state, other than the genesis
442  /// hash, allowing it to be performed in response to network traffic _before_ acquiring any
443  /// mutexes or occupying any channels.
444  ///
445  /// This DOES verify the slashed validators are committed to within the block's header. This
446  /// DOES NOT verify the slashes themselves, which is semantic. This enables malleability in that
447  /// a malicious peer MAY substitute a valid slash reason for a validator with an invalid slash
448  /// reason for the same validator. The reason for a slash may be verified via [`Slash::verify`],
449  /// solely requiring the context which spawned the Tributary (not its current state).
450  ///
451  /// This DOES verify the transactions are committed to within the block's header. This DOES
452  /// verify the signed transaction's signatures. If the application's transaction type omits
453  /// signatures from the transaction's hash, due to them not affecting the semantic meaning of the
454  /// transaction, a malicious peer MAY substitute a signed transaction's valid signature with an
455  /// invalid signature.
456  ///
457  /// If the block is agreed upon by the validators via the consensus process, there MUST be valid
458  /// uncommitted data available _so long as the honest-majority assumption is upheld_. This means
459  /// if a block is received with invalid data _which wasn't committed to_, but the block is agreed
460  /// upon, it is the _peer_ which should be considered valid, not the block. The uncommitted data
461  /// should be retrieved from an honest peer instead.
462  ///
463  /// For blocks _without agreement under consensus_, it would not appear immediate to determine if
464  /// a block with invalid uncommitted data is due to a malicious proposer or a malicious peer.
465  /// However, if the block was received from a peer who isn't the proposer, the peer MUST be
466  /// faulty, as the peer either malleated the block to be invalid themselves _or_ chose to relay
467  /// an invalid block (assuming the gossip layer does not simply relay every message seen without
468  /// any scrutiny).
469  pub fn verify_syntax(&self, genesis: [u8; 32]) -> Result<(), SyntacticError> {
470    // This length is serialized as a `u32`, so it must be less than or equal to `u32::MAX`
471    if self.transactions.len() >
472      const {
473        #[expect(clippy::eq_op, clippy::manual_assert)]
474        if 4_294_967_295 != u32::MAX {
475          panic!("inlined `u32::MAX` constant wasn't correct");
476        }
477        4_294_967_295
478      }
479    {
480      Err(SyntacticError::ExceededSizeLimit { size: None })?;
481    }
482
483    // Check this block's encoded length is less than the block size limit
484    if let Some(block_size_limit) = T::BLOCK_SIZE_LIMIT {
485      let Ok(serialized_len) = crate::serialized_len(self) else {
486        Err(SyntacticError::ExceededSizeLimit { size: None })?
487      };
488      if serialized_len > block_size_limit {
489        Err(SyntacticError::ExceededSizeLimit { size: Some(serialized_len) })?;
490      }
491    }
492
493    if (self.header.slashes != crate::merkle::root::<Slash>(self.slashes.iter())) ||
494      (self.header.transactions != crate::merkle::root::<T>(self.transactions.iter()))
495    {
496      Err(SyntacticError::IncorrectContents)?;
497    }
498
499    // Check the block's time is representable
500    self.system_time()?;
501
502    Self::verify_syntax_slashes(&self.slashes)?;
503    Self::verify_syntax_transactions(genesis, &self.transactions)?;
504
505    Ok(())
506  }
507
508  /// Instantiate a block.
509  ///
510  /// This will check the block is syntactically valid via [`Block::verify_syntax`]. It is intended
511  /// to enable optimized peer-to-peer layers, where the application syncs block headers
512  /// independently from their contents, where fine control over each individual item is required
513  /// (e.g. if a single item was malleated and should be replaced).
514  pub fn instantiate(
515    genesis: [u8; 32],
516    parent: [u8; 32],
517    time: u64,
518    slashes: Box<[Slash]>,
519    transactions: Box<[T]>,
520  ) -> Result<Self, SyntacticError> {
521    let block = Block {
522      header: BlockHeader {
523        parent,
524        time,
525        slashes: crate::merkle::root::<Slash>(slashes.iter()),
526        transactions: crate::merkle::root::<T>(transactions.iter()),
527      },
528      slashes,
529      transactions,
530    };
531    block.verify_syntax(genesis)?;
532    Ok(block)
533  }
534
535  /// This block's parent's hash.
536  pub fn parent(&self) -> [u8; 32] {
537    self.header.parent
538  }
539
540  /// This block's time.
541  ///
542  /// See [`BlockHeader::time`] for more information.
543  pub fn time(&self) -> u64 {
544    self.header.time
545  }
546
547  /// The hash of this block.
548  ///
549  /// This is defined as the hash of its header.
550  pub fn hash(&self) -> [u8; 32] {
551    self.header.hash()
552  }
553
554  /// The slashes within this block.
555  pub fn slashes(&self) -> &[Slash] {
556    &self.slashes
557  }
558
559  /// The transactions within this block.
560  pub fn transactions(&self) -> &[T] {
561    &self.transactions
562  }
563}
564
565#[test]
566fn sizes() {
567  use crate::transaction::TestTransaction;
568
569  let header = BlockHeader {
570    parent: [0xaa; 32],
571    time: u64::MAX,
572    slashes: [0xbb; 32],
573    transactions: [0xcc; 32],
574  };
575  assert_eq!(header, BlockHeader::read(&mut header.serialize().as_slice()).unwrap());
576  assert_eq!(header.serialize().len(), BlockHeader::SIZE);
577  assert_eq!(
578    (Block::<TestTransaction> { header, slashes: Box::default(), transactions: Box::default() })
579      .serialize()
580      .len(),
581    Block::<TestTransaction>::EMPTY_BLOCK_SIZE
582  );
583}
584
585#[test]
586fn slashes() {
587  use crate::transaction::TestTransaction;
588
589  let slash = |validator: [u8; 32]| {
590    let mut slash = validator.to_vec();
591    loop {
592      if let Ok(slash) = Slash::read(&mut slash.as_slice()) {
593        return slash;
594      }
595      /*
596        Because this slash isn't verified and doesn't have to be valid, just to deserialize into a
597        valid instance of the literal data types, we just pad with non-zero bytes until it's the
598        correct length to deserialize.
599      */
600      slash.push(1);
601      assert!(slash.len() < (32 * 1_024), "32 KiB slash still couldn't be deserialized");
602    }
603  };
604
605  Block::<TestTransaction>::verify_syntax_slashes([&slash([0xaa; 32])]).expect("one slash");
606  Block::<TestTransaction>::verify_syntax_slashes([&slash([0xaa; 32]), &slash([0xbb; 32])])
607    .expect("sorted");
608  Block::<TestTransaction>::verify_syntax_slashes([&slash([0xaa; 32]), &slash([0xaa; 32])])
609    .expect_err("multiple inclusions");
610  Block::<TestTransaction>::verify_syntax_slashes([&slash([0xbb; 32]), &slash([0xaa; 32])])
611    .expect_err("not sorted");
612}
613
614#[test]
615fn transactions() {
616  use core::ops::Deref as _;
617
618  use zeroize::Zeroizing;
619  use rand::rngs::OsRng;
620
621  use ciphersuite::{
622    group::{ff::PrimeField as _, GroupEncoding as _},
623    Ciphersuite,
624  };
625  use dalek_ff_group::Ristretto;
626
627  use crate::transaction::TestTransaction;
628
629  let genesis = [0xfe; 32];
630
631  let (alice, bob) = {
632    let alice = Zeroizing::new(<Ristretto as Ciphersuite>::F::random(&mut OsRng));
633    let bob = Zeroizing::new(<Ristretto as Ciphersuite>::F::random(&mut OsRng));
634    if (<Ristretto as Ciphersuite>::generator() * alice.deref()).to_bytes() <
635      (<Ristretto as Ciphersuite>::generator() * bob.deref()).to_bytes()
636    {
637      (alice, bob)
638    } else {
639      (bob, alice)
640    }
641  };
642
643  let transaction = |(mut kind, salt)| {
644    let mut key = None;
645    let nonce = <Ristretto as Ciphersuite>::F::random(&mut OsRng);
646    if let TransactionKind::Signed { scope: _, signed: Signed { signer, nonce: _, signature } } =
647      &mut kind
648    {
649      let key_value = if *signer == [0xaa; 32] {
650        &alice
651      } else if *signer == [0xbb; 32] {
652        &bob
653      } else {
654        panic!()
655      };
656      *signer = (<Ristretto as Ciphersuite>::generator() * key_value.deref()).to_bytes();
657      key = Some(key_value);
658
659      signature[.. 32]
660        .copy_from_slice((<Ristretto as Ciphersuite>::generator() * nonce).to_bytes().as_ref());
661    }
662
663    let mut transaction = TestTransaction { valid: true, kind, salt };
664
665    if let Some(signature_challenge) = transaction.signature_challenge(genesis) {
666      let TransactionKind::Signed { scope: _, signed: Signed { signer: _, nonce: _, signature } } =
667        &mut transaction.kind
668      else {
669        panic!("signature challenge but not signed")
670      };
671      let s = nonce + (signature_challenge * key.unwrap().deref());
672      signature[32 ..].copy_from_slice(s.to_repr().as_ref());
673    }
674
675    transaction
676  };
677
678  // Provided transactions solely have to be ordered by scope
679  let provided = [
680    (TransactionKind::Provided { scope: "provided 0" }, 1),
681    (TransactionKind::Provided { scope: "provided 0" }, 0),
682    (TransactionKind::Provided { scope: "provided 1" }, 0),
683  ]
684  .into_iter()
685  .map(transaction)
686  .collect::<alloc::vec::Vec<_>>();
687
688  // Unsigned transactions are ordered by hash
689  let unsigned = {
690    let mut unsigned = [(TransactionKind::Unsigned, 0), (TransactionKind::Unsigned, 1)]
691      .into_iter()
692      .map(transaction)
693      .collect::<alloc::vec::Vec<_>>();
694    unsigned.sort_by_key(Transaction::hash);
695    unsigned
696  };
697
698  // Signed transactions are sorted by signer, then scope, then nonce
699  let signed = [
700    (TransactionKind::Signed {
701      scope: alloc::vec![1].into_boxed_slice(),
702      signed: Signed { signer: [0xaa; 32], nonce: 0, signature: [0; 64] },
703    }),
704    (TransactionKind::Signed {
705      scope: alloc::vec![1].into_boxed_slice(),
706      signed: Signed { signer: [0xaa; 32], nonce: 1, signature: [0; 64] },
707    }),
708    (TransactionKind::Signed {
709      scope: alloc::vec![1].into_boxed_slice(),
710      signed: Signed { signer: [0xaa; 32], nonce: 2, signature: [0; 64] },
711    }),
712    (TransactionKind::Signed {
713      scope: alloc::vec![2].into_boxed_slice(),
714      signed: Signed { signer: [0xaa; 32], nonce: 0, signature: [0; 64] },
715    }),
716    (TransactionKind::Signed {
717      scope: alloc::vec![3].into_boxed_slice(),
718      signed: Signed { signer: [0xaa; 32], nonce: 5, signature: [0; 64] },
719    }),
720    (TransactionKind::Signed {
721      scope: alloc::vec![0].into_boxed_slice(),
722      signed: Signed { signer: [0xbb; 32], nonce: 0, signature: [0; 64] },
723    }),
724  ]
725  .into_iter()
726  .map(|kind| transaction((kind, 0)))
727  .collect::<alloc::vec::Vec<_>>();
728
729  {
730    let transactions = provided.iter().chain(unsigned.iter()).chain(signed.iter());
731    Block::<TestTransaction>::verify_syntax_transactions(genesis, transactions).expect("sorted");
732  }
733
734  {
735    let transactions = unsigned.iter().chain(provided.iter());
736    Block::<TestTransaction>::verify_syntax_transactions(genesis, transactions)
737      .expect_err("unsigned before provided");
738  }
739
740  {
741    let transactions = signed.iter().chain(provided.iter());
742    Block::<TestTransaction>::verify_syntax_transactions(genesis, transactions)
743      .expect_err("signed before provided");
744  }
745
746  {
747    let transactions = signed.iter().chain(unsigned.iter());
748    Block::<TestTransaction>::verify_syntax_transactions(genesis, transactions)
749      .expect_err("signed before unsigned");
750  }
751
752  {
753    let transactions = provided.iter().rev();
754    Block::<TestTransaction>::verify_syntax_transactions(genesis, transactions)
755      .expect_err("provided with reversed scopes");
756  }
757
758  {
759    let transactions = unsigned.iter().rev();
760    Block::<TestTransaction>::verify_syntax_transactions(genesis, transactions)
761      .expect_err("unsigned with reversed hashes");
762  }
763
764  {
765    let transactions = unsigned.first().into_iter().chain(unsigned.iter());
766    Block::<TestTransaction>::verify_syntax_transactions(genesis, transactions)
767      .expect_err("unsigned with repeated transactions");
768  }
769
770  /*
771    Try every permutation of signed transactions, as they should only have a singular valid
772    ordering (the one they were defined in).
773
774    This generates every ordering via incrementing a
775    multi-digit value (the set of indexes, each digit one index),
776    exhausting its space of representable values. When the multi-digit value overflows, we're done.
777  */
778  {
779    fn increment(digits: &mut [usize], limit: usize) -> bool {
780      let mut carry = true;
781      for digit in digits {
782        *digit += usize::from(u8::from(carry));
783        carry = *digit == limit;
784        if carry {
785          *digit = 0;
786        }
787      }
788      !carry
789    }
790    let mut order = alloc::vec![0; signed.len()];
791    while increment(&mut order, signed.len()) {
792      if order != (0 .. signed.len()).collect::<alloc::vec::Vec<_>>() {
793        let transactions = order.iter().map(|i| &signed[*i]);
794        Block::<TestTransaction>::verify_syntax_transactions(genesis, transactions)
795          .expect_err("non-sorted signed transactions");
796      }
797    }
798  }
799
800  {
801    let transactions =
802      signed.iter().filter(|transaction| {
803        if let TransactionKind::Signed {
804          scope: _,
805          signed: Signed { signer: _, nonce, signature: _ },
806        } = transaction.kind() &&
807          (nonce == 1)
808        {
809          return false;
810        }
811        true
812      });
813    Block::<TestTransaction>::verify_syntax_transactions(genesis, transactions)
814      .expect_err("gap between nonces 0 and 2");
815  }
816
817  {
818    let transactions =
819      provided.iter().chain(unsigned.iter()).chain(signed.iter()).cloned().collect::<Box<_>>();
820    for i in 0 .. transactions.len() {
821      let mut transactions = transactions.clone();
822      transactions[i].valid = false;
823      Block::<TestTransaction>::verify_syntax_transactions(genesis, &transactions)
824        .expect_err("invalid transaction");
825    }
826  }
827
828  {
829    let transactions = signed.iter().cloned().collect::<Box<_>>();
830    for i in 0 .. transactions.len() {
831      let mut transactions = transactions.clone();
832      {
833        let TransactionKind::Signed { scope: _, signed: Signed { signer, .. } } =
834          &mut transactions[i].kind
835        else {
836          panic!("non-signed transaction in `signed`")
837        };
838        signer[0] ^= 1;
839      }
840      Block::<TestTransaction>::verify_syntax_transactions(genesis, &transactions)
841        .expect_err("malleated signer");
842    }
843  }
844
845  {
846    let transactions = signed.iter().cloned().collect::<Box<_>>();
847    for i in 0 .. transactions.len() {
848      let mut transactions = transactions.clone();
849      {
850        let TransactionKind::Signed { scope: _, signed: Signed { signature, .. } } =
851          &mut transactions[i].kind
852        else {
853          panic!("non-signed transaction in `signed`")
854        };
855        signature[0] ^= 1;
856      }
857      Block::<TestTransaction>::verify_syntax_transactions(genesis, &transactions)
858        .expect_err("malleated signature");
859    }
860  }
861}