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#[derive(Clone, Debug)]
14pub enum SyntacticError {
15 ExceededSizeLimit {
17 size: Option<usize>,
21 },
22 IncorrectContents,
24 AbsurdTime,
28 IncorrectOrderOfContents,
32 Transaction(TransactionError),
34}
35
36impl From<TransactionError> for SyntacticError {
37 fn from(error: TransactionError) -> SyntacticError {
38 SyntacticError::Transaction(error)
39 }
40}
41
42#[derive(Clone, Debug)]
44pub enum SemanticError {
45 TooSoon,
47 InvalidSlash {
49 validator: [u8; 32],
51 },
52 SlashAlreadyIncluded {
54 validator: [u8; 32],
56 },
57 DistinctProvided {
59 scope: &'static str,
61 transaction_hash: [u8; 32],
63 expected_hash: [u8; 32],
65 },
66 UnsignedAlreadyIncluded {
68 transaction_hash: [u8; 32],
70 },
71 InvalidSigner {
76 signer: [u8; 32],
78 },
79 Gap {
82 transaction_hash: [u8; 32],
84 transaction_nonce: u64,
86 expected_nonce: Option<u64>,
90 },
91}
92
93#[derive(Clone, Debug)]
95pub enum EphemeralError {
96 UnexpectedParent,
98 Future,
100 NotLocallyProvidedTransaction {
102 scope: &'static str,
104 transaction_hash: [u8; 32],
106 },
107}
108
109#[derive(Clone, Debug)]
111pub enum BlockError {
112 Syntactic(SyntacticError),
114 Semantic(SemanticError),
116 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#[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 pub fn parent(&self) -> [u8; 32] {
234 self.parent
235 }
236
237 pub fn time(&self) -> u64 {
241 self.time
242 }
243
244 pub fn slashes(&self) -> [u8; 32] {
246 self.slashes
247 }
248
249 pub fn transactions(&self) -> [u8; 32] {
251 self.transactions
252 }
253
254 pub fn hash(&self) -> [u8; 32] {
259 crate::merkle::Digestible::chain_update(self, Blake2b256::new()).finalize().into()
260 }
261}
262
263#[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 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 pub(crate) const EMPTY_BLOCK_SIZE: usize = BlockHeader::SIZE + 2 + 4;
359
360 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 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 #[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 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 order.0 == 0 {
422 if new_order < order {
425 Err(SyntacticError::IncorrectOrderOfContents)?;
426 }
427 } else if new_order <= order {
428 Err(SyntacticError::IncorrectOrderOfContents)?;
430 }
431 order = new_order;
432
433 crate::transaction::verify_syntax(transaction, genesis)?;
434 }
435
436 Ok(())
437 }
438
439 pub fn verify_syntax(&self, genesis: [u8; 32]) -> Result<(), SyntacticError> {
470 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 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 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 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 pub fn parent(&self) -> [u8; 32] {
537 self.header.parent
538 }
539
540 pub fn time(&self) -> u64 {
544 self.header.time
545 }
546
547 pub fn hash(&self) -> [u8; 32] {
551 self.header.hash()
552 }
553
554 pub fn slashes(&self) -> &[Slash] {
556 &self.slashes
557 }
558
559 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 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 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 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 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 {
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}