Skip to main content

tributary_framework/
transaction.rs

1use core::fmt::Debug;
2use alloc::boxed::Box;
3use std::io;
4
5use blake2::{
6  digest::{CustomizedInit as _, Digest as _},
7  Blake2b256, Blake2b512,
8};
9
10use ciphersuite::Ciphersuite;
11use dalek_ff_group::Ristretto;
12use schnorr::SchnorrSignature;
13
14use crate::{ReadWrite, Digestible};
15
16/// An error from a transaction.
17#[derive(Clone, Debug)]
18pub enum TransactionError {
19  /// The transaction exceeded the size limit.
20  ExceededSizeLimit,
21  /// The transaction's signer wasn't a validator or was slashed.
22  InvalidSigner,
23  /// The transaction's signature was invalid.
24  InvalidSignature,
25  /// The transaction itself was invalid, as per [`Transaction::verify`].
26  InvalidTransaction,
27}
28
29/// The signature data for a `Signed` transaction.
30#[derive(Clone, Debug)]
31pub struct Signed {
32  /// The transaction's signer.
33  ///
34  /// This MUST be the Ristretto public key of a validator who has not been slashed.
35  pub signer: [u8; 32],
36  /// The transaction's nonce.
37  ///
38  /// This transaction WILL NOT be included until all prior nonces, within this transaction's
39  /// scope, have appeared on-chain.
40  pub nonce: u64,
41  /// The Ristretto Schnorr signature.
42  pub signature: [u8; 64],
43}
44
45impl ReadWrite for Signed {
46  fn read(mut reader: impl io::Read) -> io::Result<Self> {
47    let signer = {
48      let mut signer = [0; 32];
49      reader.read_exact(&mut signer)?;
50      signer
51    };
52
53    let nonce = {
54      let mut nonce = [0; 8];
55      reader.read_exact(&mut nonce)?;
56      u64::from_le_bytes(nonce)
57    };
58
59    let signature = {
60      let mut signature = [0; 64];
61      reader.read_exact(&mut signature)?;
62      signature
63    };
64
65    Ok(Self { signer, nonce, signature })
66  }
67
68  fn write(&self, mut writer: impl io::Write) -> io::Result<()> {
69    let Self { signer, nonce, signature } = self;
70    writer.write_all(signer)?;
71    writer.write_all(&nonce.to_le_bytes())?;
72    writer.write_all(signature)
73  }
74}
75
76impl Signed {
77  /// Read a `Signed` value _without its numeric nonce_.
78  ///
79  /// This is beneficial for contexts where the numeric nonce can be inferred from the
80  /// transaction's content, allowing optimizing the encoding and reducing malleability.
81  ///
82  /// This has an incompatible wire format with `<Signed as ReadWrite>::read` and requires `nonce`
83  /// be specified as an argument.
84  pub fn read_without_nonce(mut reader: impl io::Read, nonce: u64) -> io::Result<Self> {
85    let signer = {
86      let mut signer = [0; 32];
87      reader.read_exact(&mut signer)?;
88      signer
89    };
90
91    let signature = {
92      let mut signature = [0; 64];
93      reader.read_exact(&mut signature)?;
94      signature
95    };
96
97    Ok(Signed { signer, nonce, signature })
98  }
99
100  /// Write a `Signed` value _without its numeric nonce_.
101  ///
102  /// This function is the complement to [`Signed::read_without_nonce`].
103  ///
104  /// This has an incompatible wire format with `<Signed as ReadWrite>::write` and omits `nonce`
105  /// from the serialization.
106  pub fn write_without_nonce(&self, mut writer: impl io::Write) -> io::Result<()> {
107    let Self { signer, nonce: _, signature } = self;
108    writer.write_all(signer)?;
109    writer.write_all(signature)
110  }
111}
112
113/// The type of a transaction.
114///
115/// This defines the transaction's required semantics for inclusion.
116#[derive(Clone, Debug)]
117pub enum TransactionKind {
118  /// This transaction should be locally provided by every validator, in an exact order.
119  ///
120  /// The contained static string names a scope to use. This allows two distinct provided
121  /// transactions, without synchrony, to be ordered within distinct scopes without mandating
122  /// ordering with each other at time of provision. They will still be ordered into a single
123  /// linear view once included on the agreed-upon blockchain.
124  ///
125  /// The only malleability SHOULD be when this transaction appears on chain. The block producer
126  /// will only include provided transactions once locally provided, and validators will only vote
127  /// for blocks with provided transactions if they were as locally provided.
128  ///
129  /// If a supermajority of validators produce a commit for a block with a provided transaction
130  /// which isn't locally held, or even if it conflicts with a locally held provided transaction,
131  /// the block will still be added to the local chain. The application MUST check the on-chain
132  /// provided transactions are consistent with the local view.
133  ///
134  /// In order to ensure provided transactions aren't inadvertently provided multiple times, all
135  /// provided transactions MUST have a unique hash. This is solely enforced _by the mempool_,
136  /// where the literal blockchain solely requires a supermajority of validators agree on the
137  /// ordering within a scope. Under an honest-supermajority assumption, the lack of provided
138  /// transactions with identical hashes in local views (the mempools) will prevent such an
139  /// occurrence on-chain.
140  Provided {
141    /// The scope for this provided transaction.
142    scope: &'static str,
143  },
144
145  /// An unsigned transaction.
146  ///
147  /// This will be broadcast to other validators, who will add it to their mempool if they agree on
148  /// the transaction's validity. No requirements on its ordering (in relation to any other
149  /// transaction) are established.
150  ///
151  /// In order to ensure unsigned transactions aren't inadvertently included multiple times, all
152  /// unsigned transactions MUST have a unique hash.
153  Unsigned,
154
155  /// A signed transaction.
156  Signed {
157    /// The scope for this signed transaction.
158    ///
159    /// The nonce within the [`Signed`] data is local to this scope.
160    scope: Box<[u8]>,
161    /// The [`Signed`] data associated with this.
162    signed: Signed,
163  },
164}
165
166/// A Tributary transaction.
167///
168/// The implementation of `Digestible` MUST be binding to the entire transaction _except_ its
169/// signature (if signed).
170pub trait Transaction: Clone + ReadWrite + Digestible {
171  /// The size limit for a transaction.
172  ///
173  /// The Tributary will enforce no individual transaction exceeds this size.
174  ///
175  /// Transactions MUST be able to be included within a block's size limit.
176  ///
177  /// The default size limit is 2 MiB.
178  const SIZE_LIMIT: Option<usize> = Some(2 * 1024 * 1024);
179
180  /// The size limit for a block.
181  ///
182  /// The Tributary will enforce no individual block exceeds this size.
183  ///
184  /// This MUST be greater than the size of an empty block.
185  ///
186  /// The default size limt is 4 MiB.
187  const BLOCK_SIZE_LIMIT: Option<usize> = Some(4 * 1024 * 1024);
188
189  /// The type of transaction this is.
190  fn kind(&self) -> TransactionKind;
191
192  /// Verify this transaction's content.
193  ///
194  /// This MUST be a context-free validation over the data within this transaction alone. This
195  /// function is only required to apply application-specific verification rules, where the
196  /// Tributary will always apply its rules and any rules regarding the current context.
197  fn verify(&self) -> Result<(), TransactionError>;
198
199  /// Obtain the challenge for this transaction's signature.
200  ///
201  /// This MUST return `Some(_)`  when `TransactionKind::Signed { .. }` and `None` otherwise.
202  ///
203  /// The provided implementation uses BLAKE2b-512, with a personalization of "tributary tx sig",
204  /// for its hash function. It scopes to a specific Tributary via its genesis before digesting the
205  /// transaction and the present signature's nonce (its first `32` bytes).
206  fn signature_challenge(&self, genesis: [u8; 32]) -> Option<<Ristretto as Ciphersuite>::F> {
207    let TransactionKind::Signed { scope: _, signed: Signed { signature, .. } } = self.kind() else {
208      None?
209    };
210    Some(<Ristretto as Ciphersuite>::F::from_bytes_mod_order_wide(&{
211      let genesis_scoped = Blake2b512::new_customized(b"tributary tx sig").chain_update(genesis);
212      let tx_scoped = self.chain_update(genesis_scoped);
213      let nonce_scoped = tx_scoped.chain_update(&signature[.. 32]);
214      nonce_scoped.finalize().into()
215    }))
216  }
217
218  /// Hash this transaction.
219  ///
220  /// The provided implementation uses BLAKE2b-256, with a personalization of "tributary tx", for
221  /// its hash function. The implementation MUST be binding to the entire value's [`Digestible`]
222  /// content.
223  fn hash(&self) -> [u8; 32] {
224    self.chain_update(Blake2b256::new_customized(b"tributary tx")).finalize().into()
225  }
226}
227
228pub(crate) fn verify_syntax<T: Transaction>(
229  tx: &T,
230  genesis: [u8; 32],
231) -> Result<(), TransactionError> {
232  {
233    let transaction_size_limit_by_block_size_limit = match T::BLOCK_SIZE_LIMIT
234      .map(|block_size_limit| block_size_limit.checked_sub(crate::Block::<T>::EMPTY_BLOCK_SIZE))
235    {
236      Some(Some(transaction_size_limit_by_block_size_limit)) => {
237        Some(transaction_size_limit_by_block_size_limit)
238      }
239      // The block size limit is less than the size of an empty block, so any block (and
240      // therefore any transactions) will be syntactically invalid
241      Some(None) => Err(TransactionError::ExceededSizeLimit)?,
242      None => None,
243    };
244    let transaction_size =
245      crate::serialized_len(tx).map_err(|_| TransactionError::ExceededSizeLimit)?;
246    let exceeds_size_limit = |size_limit: Option<usize>| {
247      size_limit.is_some_and(|size_limit| transaction_size > size_limit)
248    };
249    if exceeds_size_limit(T::SIZE_LIMIT) ||
250      exceeds_size_limit(transaction_size_limit_by_block_size_limit)
251    {
252      Err(TransactionError::ExceededSizeLimit)?;
253    }
254  }
255
256  if let Some(signature_challenge) = tx.signature_challenge(genesis) {
257    let TransactionKind::Signed { scope: _, signed: Signed { signer, nonce: _, signature } } =
258      tx.kind()
259    else {
260      panic!(
261        "`Transaction::signature_challenge` returned `Some(_)` when not `TransactionKind::Signed`"
262      );
263    };
264    let signer = <Ristretto as Ciphersuite>::read_G(&mut signer.as_slice())
265      .map_err(|_| TransactionError::InvalidSigner)?;
266    let signature = SchnorrSignature::<Ristretto>::read(&mut signature.as_slice())
267      .map_err(|_| TransactionError::InvalidSignature)?;
268    // TODO: Queue this for batch verification
269    if !signature.verify(signer, signature_challenge) {
270      Err(TransactionError::InvalidSignature)?;
271    }
272  }
273
274  tx.verify()?;
275
276  Ok(())
277}
278
279#[cfg(test)]
280mod tests {
281  use super::*;
282
283  #[derive(Clone)]
284  pub(crate) struct TestTransaction {
285    pub(crate) valid: bool,
286    pub(crate) kind: TransactionKind,
287    pub(crate) salt: u8,
288  }
289
290  impl ReadWrite for TestTransaction {
291    fn read(mut reader: impl io::Read) -> io::Result<Self> {
292      let mut valid = [0xff; 1];
293      reader.read_exact(&mut valid)?;
294      let valid = valid[0] == 1;
295
296      let mut kind = [0xff];
297      reader.read_exact(&mut kind)?;
298      let kind = match kind[0] {
299        0xff => TransactionKind::Provided { scope: "provided 0" },
300        0xfe => TransactionKind::Provided { scope: "provided 1" },
301        1 => TransactionKind::Unsigned,
302        2 => TransactionKind::Signed {
303          scope: {
304            let mut scope = [0];
305            reader.read_exact(&mut scope)?;
306            let mut scope = alloc::vec![0; usize::from(scope[0])].into_boxed_slice();
307            reader.read_exact(&mut scope)?;
308            scope
309          },
310          signed: Signed::read(&mut reader)?,
311        },
312        _ => Err(io::Error::other("unrecognized transaction kind"))?,
313      };
314
315      let mut salt = [0xff];
316      reader.read_exact(&mut salt)?;
317      let salt = salt[0];
318
319      Ok(Self { valid, kind, salt })
320    }
321
322    fn write(&self, mut writer: impl io::Write) -> io::Result<()> {
323      writer.write_all(&[u8::from(self.valid)])?;
324      match &self.kind {
325        TransactionKind::Provided { scope } => {
326          writer.write_all(&[match *scope {
327            "provided 0" => 0xff,
328            "provided 1" => 0xfe,
329            _ => panic!("unexpected scope"),
330          }])?;
331        }
332        TransactionKind::Unsigned => {
333          writer.write_all(&[1])?;
334        }
335        TransactionKind::Signed { scope, signed } => {
336          writer.write_all(&[2])?;
337          writer.write_all(&[u8::try_from(scope.len()).unwrap()])?;
338          writer.write_all(scope)?;
339          signed.write(&mut writer)?;
340        }
341      }
342      writer.write_all(&[self.salt])?;
343
344      Ok(())
345    }
346  }
347
348  impl crate::merkle::Digestible for TestTransaction {
349    fn update(&self, digest: &mut (impl ?Sized + blake2::digest::Update)) {
350      let serialization = self.serialize();
351      let mut serialization = serialization.as_slice();
352      if matches!(&self.kind, TransactionKind::Signed { .. }) {
353        serialization = &serialization[.. (serialization.len() - 64)];
354      }
355      digest.update(serialization);
356    }
357  }
358
359  impl Transaction for TestTransaction {
360    fn kind(&self) -> TransactionKind {
361      self.kind.clone()
362    }
363    fn verify(&self) -> Result<(), TransactionError> {
364      self.valid.ok_or(TransactionError::InvalidTransaction)
365    }
366  }
367}
368#[cfg(test)]
369pub(crate) use tests::TestTransaction;