Skip to main content

tributary_framework/tendermint/
signature_scheme.rs

1use core::{ops::Deref as _, convert::AsRef};
2use alloc::{boxed::Box, vec::Vec, vec};
3
4use zeroize::Zeroizing;
5use rand::rngs::OsRng;
6
7use blake2::{
8  digest::{Digest as _, CustomizedInit as _},
9  Blake2b512,
10};
11use ciphersuite::{
12  group::{ff::{PrimeField, FromUniformBytes as _}, GroupEncoding},
13  Ciphersuite,
14};
15use dalek_ff_group::Ristretto;
16use schnorr::{
17  SchnorrSignature,
18  aggregate::{SchnorrAggregator, SchnorrAggregate},
19};
20
21use borsh::{
22  io::{self, Read, Write},
23  BorshSerialize, BorshDeserialize,
24};
25use tendermint::InvalidAggregateSignature;
26
27/// The DST used for aggregating Schnorr signatures.
28const AGGREGATOR_DST: &[u8] = b"Tributary Tendermint Commit Aggregator";
29
30/// A transcript which has already been scoped to a message.
31///
32/// The `SignatureScheme` API expected by `tendermint-consensus` supports aggregation where
33/// multiple signers sign the same message and then non-interactively produce a single signature.
34/// Because the messages are the same, we first transcript the message, _then_ the signer's key and
35/// nonce. If we hashed the signer's key and nonce _first_, as traditional, we'd have to re-hash
36/// the message for each signer. This is safe, without a risk of collisions, as the length of the
37/// signer's key and nonce is constant.
38#[derive(Clone)]
39struct MessageScopedTranscript(Blake2b512);
40impl MessageScopedTranscript {
41  fn challenge(self, key: [u8; 32], nonce: &[u8]) -> <Ristretto as Ciphersuite>::F {
42    <Ristretto as Ciphersuite>::F::from_uniform_bytes(
43      &self.0.chain_update(key).chain_update(nonce).finalize().into(),
44    )
45  }
46}
47
48#[test]
49fn message_scoped_transcript() {
50  let transcript = MessageScopedTranscript(Blake2b512::new());
51
52  let rand_bytes = || {
53    use rand::RngCore as _;
54
55    let mut bytes = [0; 32];
56    rand::rngs::OsRng.fill_bytes(&mut bytes);
57    bytes
58  };
59
60  let key_a = rand_bytes();
61  let key_b = rand_bytes();
62
63  let nonce_a = rand_bytes();
64  let nonce_b = rand_bytes();
65
66  // This should be consistent if quieried multiple times, not mutated
67  assert_eq!(
68    transcript.clone().challenge(key_a, &nonce_a),
69    transcript.clone().challenge(key_a, &nonce_a)
70  );
71  // Yet either the key or the nonce being different should produce a different challenge
72  assert_ne!(
73    transcript.clone().challenge(key_a, &nonce_a),
74    transcript.clone().challenge(key_b, &nonce_a)
75  );
76  assert_ne!(
77    transcript.clone().challenge(key_a, &nonce_a),
78    transcript.clone().challenge(key_a, &nonce_b)
79  );
80  assert_ne!(
81    transcript.clone().challenge(key_a, &nonce_a),
82    transcript.clone().challenge(key_b, &nonce_b)
83  );
84}
85
86/// The signature scheme for a Tendermint process.
87///
88/// This is bound to the genesis hash of the Tributary, providing domain-separation across
89/// Tributaries.
90// TODO: We currently represent validators as `[u8; 32]`, the byte representation of their public
91// keys. Should we represent them as `u16`, as possible by also including a sorted list of
92// validators here?
93#[derive(Clone)]
94pub(crate) struct SignatureScheme {
95  genesis_scoped_transcript: Blake2b512,
96  validators: usize,
97}
98
99/// A signer for a signature scheme for a Tendermint process.
100///
101/// This is scoped to a specific signature scheme (and therefore a specific Tributary).
102#[derive(Clone)]
103pub(crate) struct Signer {
104  signature_scheme: SignatureScheme,
105  private_key: Zeroizing<<Ristretto as Ciphersuite>::F>,
106  public_key: [u8; 32],
107}
108
109impl SignatureScheme {
110  /// Instance a new signature scheme for Tendermint, scoped to a specific Tributary.
111  pub(crate) fn new(genesis: [u8; 32], validators: usize) -> Self {
112    Self {
113      // Initialize the transcripts for Tendermint with a customization of "tendermint", ensuring a
114      // separate domain then the Tributary itself will use for its transcripts.
115      genesis_scoped_transcript: Blake2b512::new_customized(b"tendermint").chain_update(genesis),
116      validators,
117    }
118  }
119
120  /// Instance a signer for this signature scheme.
121  pub(crate) fn signer(&self, private_key: Zeroizing<<Ristretto as Ciphersuite>::F>) -> Signer {
122    let public_key = (Ristretto::generator() * private_key.deref()).to_bytes();
123    Signer { signature_scheme: self.clone(), private_key, public_key }
124  }
125
126  /// Scope a transcript from this signature scheme to a specific message.
127  ///
128  /// The message-scoped transcript may then be scoped to a specific signer, nonce, to obtain the
129  /// signature's challenge.
130  fn message_scope(
131    &self,
132    message: impl IntoIterator<Item: AsRef<[u8]>>,
133  ) -> MessageScopedTranscript {
134    let mut transcript = self.genesis_scoped_transcript.clone();
135    for message_part in message {
136      transcript.update(message_part);
137    }
138    MessageScopedTranscript(transcript)
139  }
140}
141
142#[test]
143fn genesis_scoped_transcript() {
144  let rand_scheme = || {
145    use rand::RngCore as _;
146
147    let mut bytes = [0; 32];
148    rand::rngs::OsRng.fill_bytes(&mut bytes);
149    SignatureScheme::new(bytes, 1)
150  };
151
152  let scheme = rand_scheme();
153
154  // This should be binding to a genesis
155  assert_ne!(
156    scheme.genesis_scoped_transcript.clone().finalize(),
157    rand_scheme().genesis_scoped_transcript.finalize()
158  );
159
160  // This should handle messages by their concatenation
161  assert_eq!(
162    scheme.message_scope([*b"a", *b"b"]).0.finalize(),
163    scheme.message_scope([b"ab"]).0.finalize()
164  );
165  // This should be binding to the message
166  assert_ne!(scheme.message_scope([b"a"]).0.finalize(), scheme.message_scope([b"b"]).0.finalize());
167}
168
169/// The type for an aggregate signature.
170///
171/// This contains the _serialization_ of a [`schnorr::aggregate::SchnorrAggregate`]. It may or may
172/// not be valid.
173#[derive(Clone)]
174#[cfg_attr(test, derive(PartialEq, Eq, Debug))]
175pub struct AggregateSignature(Box<[u8]>);
176impl AsRef<[u8]> for AggregateSignature {
177  fn as_ref(&self) -> &[u8] {
178    self.0.as_ref()
179  }
180}
181
182impl AggregateSignature {
183  /// The amount of validators within this aggregate signature.
184  fn validators(&self) -> usize {
185    /*
186      The serialization is a list of signers, and their nonces, nonces followed by a single scalar.
187      We solely need to determine the length of the list of signers and their nonces to know how
188      many signers were included.
189
190      This can be minorly optimized as `self.0.len() / (32 + 32)`, relying on the integer division
191      to truncate the `32` bytes for the scalar. The lack of clarity that would incur isn't
192      preferable though.
193    */
194    #[expect(clippy::manual_assert)]
195    const {
196      if core::mem::size_of::<<<Ristretto as Ciphersuite>::G as GroupEncoding>::Repr>() != 32 {
197        panic!("(memory) representation of a Ristretto point's encoding wasn't 32 bytes")
198      }
199      if core::mem::size_of::<<<Ristretto as Ciphersuite>::F as PrimeField>::Repr>() != 32 {
200        panic!("(memory) representation of a Ristretto scalar's encoding wasn't 32 bytes")
201      }
202    }
203    let validators = (self.0.len() - 32) / (32 + 32);
204    debug_assert_eq!((validators * (32 + 32)) + 32, self.0.len());
205    validators
206  }
207}
208
209impl BorshSerialize for AggregateSignature {
210  fn serialize<W: Write>(&self, writer: &mut W) -> Result<(), io::Error> {
211    /*
212      We use `u16` to represent the amount of validators included due to Tendermint having the
213      following definition:
214
215      ```rs
216      trait ValidatorSet {
217        ...
218        fn total_weight(&self) -> NonZero<u16>;
219        ...
220      }
221
222      which means any legitimate aggregate signature will have at most `u16::MAX` weight and
223      therefore `u16::MAX` validators.
224    */
225    writer.write_all(
226      &u16::try_from(self.validators())
227        .map_err(|_| {
228          io::Error::other("aggregate signature has more validators than possible weight")
229        })?
230        .to_le_bytes(),
231    )?;
232    writer.write_all(&self.0)
233  }
234}
235impl BorshDeserialize for AggregateSignature {
236  fn deserialize_reader<R: Read>(reader: &mut R) -> Result<Self, io::Error> {
237    let validators = {
238      let mut bytes = [0; 2];
239      reader.read_exact(&mut bytes)?;
240      u16::from_le_bytes(bytes)
241    };
242
243    let len =
244      usize::from(validators).checked_mul(32 + 32).and_then(|len| len.checked_add(32)).ok_or_else(
245        || io::Error::other("length of aggregate signature overflowed platform's `usize`"),
246      )?;
247
248    let mut result = vec![0; len].into_boxed_slice();
249    reader.read_exact(&mut result)?;
250    Ok(Self(result))
251  }
252}
253
254impl tendermint::SignatureScheme for SignatureScheme {
255  // The byte representation of the validator's public key
256  type Validator = [u8; 32];
257  // The byte representation of a Schnorr signature
258  type Signature = [u8; 64];
259  type AggregateSignature = AggregateSignature;
260
261  fn verify(
262    &self,
263    validator: &Self::Validator,
264    message: impl IntoIterator<Item = impl AsRef<[u8]>>,
265    signature: &Self::Signature,
266  ) -> bool {
267    let challenge = self.message_scope(message).challenge(*validator, &signature[.. 32]);
268    /*
269      We are not required to confirm this 'validator' is actually a validator with weight, hence
270      why we solely decode and verify the corresponding signature.
271
272      If we do represent validators by their index, then this property would become almost inherent
273      however.
274    */
275    let Ok(validator) = Ristretto::read_G(&mut validator.as_slice()) else {
276      return false;
277    };
278    let Ok(signature) = SchnorrSignature::<Ristretto>::read(signature.as_slice()) else {
279      return false;
280    };
281    signature.verify(validator, challenge)
282  }
283
284  fn aggregate<'sig>(
285    &self,
286    message: impl IntoIterator<Item = impl AsRef<[u8]>>,
287    signatures: impl IntoIterator<Item = (&'sig Self::Validator, &'sig Self::Signature)>,
288  ) -> Self::AggregateSignature
289  where
290    Self::Validator: 'sig,
291    Self::Signature: 'sig,
292  {
293    let transcript = self.message_scope(message);
294    let signatures = signatures.into_iter();
295
296    let sorted = {
297      let mut sorted = Vec::with_capacity({
298        let (lower, _upper) = signatures.size_hint();
299        lower
300      });
301      for signature in signatures {
302        sorted.push(signature);
303      }
304      sorted.sort_by_key(|(validator, _signature)| **validator);
305      sorted
306    };
307
308    let mut result = Vec::with_capacity((sorted.len() * (32 + 32)) + 32);
309    let mut aggregator = SchnorrAggregator::<Ristretto>::new(AGGREGATOR_DST);
310    for (validator, signature) in sorted {
311      result.write_all(validator).expect("`<Vec<_> as io::Write>` is infallible");
312
313      let challenge = transcript.clone().challenge(*validator, &signature[.. 32]);
314      let signature = SchnorrSignature::<Ristretto>::read(signature.as_slice())
315        .expect("asked to aggregate an invalid signature");
316      aggregator.aggregate(challenge, signature);
317    }
318    let aggregate = aggregator.complete().expect("asked to aggregate no signatures");
319    aggregate.write(&mut result).expect("`<Vec<_> as io::Write>` is infallible");
320
321    AggregateSignature(result.into_boxed_slice())
322  }
323
324  fn verify_aggregate(
325    &self,
326    message: impl IntoIterator<Item = impl AsRef<[u8]>>,
327    aggregate_signature: &Self::AggregateSignature,
328  ) -> Result<impl IntoIterator<Item = Self::Validator>, InvalidAggregateSignature> {
329    let transcript = self.message_scope(message);
330
331    let (validators, aggregate_signature) = {
332      let validators_len = aggregate_signature.validators();
333      if validators_len > self.validators {
334        Err(InvalidAggregateSignature)?;
335      }
336      let aggregate_signature = aggregate_signature.as_ref();
337
338      let (validators, mut aggregate_signature) = aggregate_signature.split_at(validators_len * 32);
339
340      let (validators, []) = validators.as_chunks::<32>() else {
341        panic!("multiple of `32` wasn't evenly divisible into chunks of length `32`")
342      };
343      // Ensure the validators were sorted, ensuring no validators were present multiple times
344      if !validators.is_sorted_by(|a, b| a < b) {
345        Err(InvalidAggregateSignature)?;
346      }
347
348      let aggregate_signature = {
349        let Ok(aggregate_signature_value) =
350          SchnorrAggregate::<Ristretto>::read(&mut aggregate_signature, validators_len)
351        else {
352          Err(InvalidAggregateSignature)?
353        };
354        debug_assert_eq!(aggregate_signature, &[]);
355        aggregate_signature_value
356      };
357
358      (validators, aggregate_signature)
359    };
360
361    let mut challenges = vec![];
362    for (validator, nonce) in validators.iter().zip(aggregate_signature.Rs()) {
363      let challenge = transcript.clone().challenge(*validator, nonce.to_bytes().as_ref());
364      let Ok(validator) = <Ristretto as Ciphersuite>::read_G(&mut validator.as_slice()) else {
365        Err(InvalidAggregateSignature)?
366      };
367      challenges.push((validator, challenge));
368    }
369
370    if !aggregate_signature.verify(AGGREGATOR_DST, &challenges) {
371      Err(InvalidAggregateSignature)?;
372    }
373
374    Ok(validators.iter().copied())
375  }
376}
377
378impl tendermint::Signer for Signer {
379  type Validator = [u8; 32];
380  type Signature = [u8; 64];
381
382  fn validator(&self) -> Self::Validator {
383    self.public_key
384  }
385
386  type SignFuture = core::future::Ready<Self::Signature>;
387  fn sign(&self, message: impl IntoIterator<Item = impl AsRef<[u8]>>) -> Self::SignFuture {
388    let transcript = self.signature_scheme.message_scope(message);
389
390    let nonce = Zeroizing::new(<Ristretto as Ciphersuite>::F::random(&mut OsRng));
391    let challenge = transcript
392      .challenge(self.public_key, (Ristretto::generator() * nonce.deref()).to_bytes().as_ref());
393    let signature = SchnorrSignature::<Ristretto>::sign(&self.private_key, nonce, challenge);
394
395    core::future::ready(crate::fixed_write::<{ 32 + 32 }>(|writer| signature.write(writer)))
396  }
397}
398
399#[cfg(test)]
400#[tokio::test]
401async fn sign() {
402  use ::tendermint::{SignatureScheme as _, Signer as _};
403
404  let genesis = [0xfe; 32];
405  let signature_scheme = SignatureScheme::new(genesis, 4);
406  let key = Zeroizing::new(<Ristretto as Ciphersuite>::F::random(&mut OsRng));
407  let signer = signature_scheme.signer(key);
408  const MESSAGE: [&[u8]; 1] = [b"abc"];
409  const OTHER_MESSAGE: [&[u8]; 1] = [b"def"];
410  let signature = signer.sign(MESSAGE).await;
411  assert!(signature_scheme.verify(&signer.validator(), MESSAGE, &signature));
412  assert!(!signature_scheme.verify(&signer.validator(), OTHER_MESSAGE, &signature));
413}
414
415#[cfg(test)]
416#[tokio::test]
417async fn aggregate() {
418  use ::tendermint::{SignatureScheme as _, Signer as _};
419
420  let genesis = [0xfe; 32];
421  let signature_scheme = SignatureScheme::new(genesis, 4);
422
423  let alice =
424    signature_scheme.signer(Zeroizing::new(<Ristretto as Ciphersuite>::F::random(&mut OsRng)));
425  let bob =
426    signature_scheme.signer(Zeroizing::new(<Ristretto as Ciphersuite>::F::random(&mut OsRng)));
427
428  const MESSAGE: [&[u8]; 1] = [b"abc"];
429  const OTHER_MESSAGE: [&[u8]; 1] = [b"def"];
430
431  let test = async move |signature_scheme: &SignatureScheme, signers: &[&Signer]| {
432    let mut aggregate = vec![];
433    for signer in signers {
434      aggregate.push((signer.validator(), signer.sign(MESSAGE).await));
435    }
436    let aggregate = signature_scheme
437      .aggregate(MESSAGE, aggregate.iter().map(|(signer, signature)| (signer, signature)));
438
439    assert_eq!(aggregate.validators(), signers.len());
440
441    {
442      let deserialized_aggregate = {
443        let aggregate = borsh::to_vec(&aggregate).unwrap();
444        let mut aggregate = aggregate.as_slice();
445        let deserialized_aggregate =
446          AggregateSignature::deserialize_reader(&mut aggregate).unwrap();
447        assert_eq!(aggregate, []);
448        deserialized_aggregate
449      };
450      assert_eq!(aggregate, deserialized_aggregate);
451    }
452
453    let mut validators = signers.iter().copied().map(Signer::validator).collect::<Vec<_>>();
454    validators.sort_unstable();
455    assert_eq!(
456      signature_scheme
457        .verify_aggregate(MESSAGE, &aggregate)
458        .unwrap()
459        .into_iter()
460        .collect::<Vec<_>>(),
461      validators
462    );
463    assert!(signature_scheme.verify_aggregate(OTHER_MESSAGE, &aggregate).is_err());
464  };
465
466  test(&signature_scheme, &[&alice]).await;
467  test(&signature_scheme, &[&bob]).await;
468  test(&signature_scheme, &[&alice, &bob]).await;
469}