monero_clsag/
multisig.rs

1use core::ops::Deref as _;
2use std_shims::{
3  sync::{Arc, Mutex},
4  io::{self, Read, Write},
5  collections::HashMap,
6};
7
8use rand_core::{RngCore, CryptoRng, SeedableRng as _};
9use rand_chacha::ChaCha20Rng;
10
11use subtle::{ConstantTimeEq as _, ConditionallySelectable as _};
12use zeroize::{Zeroize, ZeroizeOnDrop, Zeroizing};
13
14use curve25519_dalek::{scalar::Scalar, edwards::EdwardsPoint};
15
16use group::{ff::PrimeField as _, Group as _, GroupEncoding as _};
17
18use transcript::{Transcript, RecommendedTranscript};
19use dalek_ff_group as dfg;
20use frost::{
21  curve::Ed25519,
22  Participant, FrostError, ThresholdKeys, ThresholdView,
23  algorithm::{WriteAddendum, Algorithm},
24};
25
26use monero_ed25519::{Point, CompressedPoint};
27
28use crate::{MAX_RING_SIZE, ClsagContext, Clsag};
29
30impl ClsagContext {
31  fn transcript<T: Transcript>(&self, transcript: &mut T) {
32    // Doesn't domain separate as this is considered part of the larger CLSAG proof
33
34    // Ring index
35    transcript.append_message(b"signer_index", [self.decoys.signer_index()]);
36
37    // Ring
38    for (i, pair) in self.decoys.ring().iter().enumerate() {
39      // Doesn't include global output indexes as CLSAG doesn't care/won't be affected by it
40      // They're just a unreliable reference to this data which will be included in the message
41      // if somehow relevant
42      transcript.append_message(b"member", [u8::try_from(i).expect("ring size exceeded 255")]);
43      // This also transcripts the key image generator since it's derived from this key
44      transcript.append_message(b"key", pair[0].compress().to_bytes());
45      transcript.append_message(b"commitment", pair[1].compress().to_bytes());
46    }
47
48    // Doesn't include the commitment's parts as the above ring + index includes the commitment
49    // The only potential malleability would be if the G/H relationship is known, breaking the
50    // discrete log problem, which breaks everything already
51  }
52}
53
54/// A channel to send the mask to use for the pseudo-out (rerandomized commitment) with.
55///
56/// A mask must be sent along this channel before any preprocess addendums are handled.
57pub struct ClsagMultisigMaskSender {
58  buf: Arc<Mutex<Option<Scalar>>>,
59}
60struct ClsagMultisigMaskReceiver {
61  buf: Arc<Mutex<Option<Scalar>>>,
62}
63impl ClsagMultisigMaskSender {
64  fn new() -> (ClsagMultisigMaskSender, ClsagMultisigMaskReceiver) {
65    let buf = Arc::new(Mutex::new(None));
66    (ClsagMultisigMaskSender { buf: buf.clone() }, ClsagMultisigMaskReceiver { buf })
67  }
68
69  /// Send a mask to a CLSAG multisig instance.
70  pub fn send(self, mask: Scalar) {
71    // There is no risk this was prior set as this consumes `self`, which does not implement
72    // `Clone`
73    *self.buf.lock() = Some(mask);
74  }
75}
76impl ClsagMultisigMaskReceiver {
77  fn recv(self) -> Option<Scalar> {
78    let mut lock = self.buf.lock();
79    // This is safe as this method may only be called once
80    let res = lock.take();
81    (*lock).zeroize();
82    res
83  }
84}
85impl Drop for ClsagMultisigMaskReceiver {
86  fn drop(&mut self) {
87    (*self.buf.lock()).zeroize();
88  }
89}
90impl ZeroizeOnDrop for ClsagMultisigMaskReceiver {}
91
92/// Addendum produced during the signing process.
93#[derive(Clone, PartialEq, Eq, Zeroize, Debug)]
94pub struct ClsagAddendum {
95  key_image_share: dfg::EdwardsPoint,
96}
97
98impl ClsagAddendum {
99  /// The key image share within this addendum.
100  pub fn key_image_share(&self) -> dfg::EdwardsPoint {
101    self.key_image_share
102  }
103}
104
105impl WriteAddendum for ClsagAddendum {
106  fn write<W: Write>(&self, writer: &mut W) -> io::Result<()> {
107    writer.write_all(&self.key_image_share.compress().to_bytes())
108  }
109}
110
111#[derive(Clone, PartialEq, Eq, Zeroize)]
112struct Interim {
113  p: Scalar,
114  c: Scalar,
115
116  clsag: Clsag,
117  pseudo_out: EdwardsPoint,
118}
119
120/// FROST-inspired algorithm for producing a CLSAG signature.
121///
122/// Before this has its `process_addendum` called, a mask must be set. Before this has its
123/// `sign_share` called, all addendums (a non-zero amount) must be processed with
124/// `process_addendum`. Before `verify`, `verify_share` are called, `sign_share` must be called.
125/// Violation of this timeline is fundamentally incorrect and may cause panics.
126///
127/// The message signed is expected to be a 32-byte value. Per Monero, it's the keccak256 hash of
128/// the transaction data which is signed. This will panic if the message is not a 32-byte value.
129#[derive(Zeroize, ZeroizeOnDrop)]
130pub struct ClsagMultisig {
131  transcript: RecommendedTranscript,
132
133  key_image_generator: EdwardsPoint,
134  /*
135    This is fine to skip, even if not preferable. These are sent over the wire during signing and
136    accordingly reasonably public. Anyone who observes them could reconstruct the key image and see
137    the set who signed, but that's it.
138  */
139  #[zeroize(skip)]
140  key_image_shares: HashMap<[u8; 32], dfg::EdwardsPoint>,
141  image: dfg::EdwardsPoint,
142
143  context: ClsagContext,
144
145  // `ClsagMultisigMaskReceiver` implements `Zeroize` within its `Drop` implementation
146  #[zeroize(skip)]
147  mask_recv: Option<ClsagMultisigMaskReceiver>,
148  mask: Option<Scalar>,
149
150  msg_hash: Option<[u8; 32]>,
151  interim: Option<Interim>,
152}
153
154impl ClsagMultisig {
155  /// Construct a new instance of multisignature CLSAG signing.
156  pub fn new(
157    transcript: RecommendedTranscript,
158    context: ClsagContext,
159  ) -> (ClsagMultisig, ClsagMultisigMaskSender) {
160    let (mask_send, mask_recv) = ClsagMultisigMaskSender::new();
161    (
162      ClsagMultisig {
163        transcript,
164
165        key_image_generator: Point::biased_hash(
166          context.decoys.signer_ring_members()[0].compress().to_bytes(),
167        )
168        .into(),
169        key_image_shares: HashMap::new(),
170        image: dfg::EdwardsPoint::identity(),
171
172        context,
173
174        mask_recv: Some(mask_recv),
175        mask: None,
176
177        msg_hash: None,
178        interim: None,
179      },
180      mask_send,
181    )
182  }
183
184  /// The key image generator used by the signer.
185  pub fn key_image_generator(&self) -> EdwardsPoint {
186    self.key_image_generator
187  }
188}
189
190impl Algorithm<Ed25519> for ClsagMultisig {
191  type Transcript = RecommendedTranscript;
192  type Addendum = ClsagAddendum;
193  // We output the CLSAG and the key image, which requires an interactive protocol to obtain
194  type Signature = (Clsag, EdwardsPoint);
195
196  // We need the nonce represented against both G and the key image generator
197  fn nonces(&self) -> Vec<Vec<dfg::EdwardsPoint>> {
198    vec![vec![dfg::EdwardsPoint::generator(), dfg::EdwardsPoint(self.key_image_generator)]]
199  }
200
201  // We also publish our share of the key image
202  fn preprocess_addendum<R: RngCore + CryptoRng>(
203    &mut self,
204    _rng: &mut R,
205    keys: &ThresholdKeys<Ed25519>,
206  ) -> ClsagAddendum {
207    ClsagAddendum {
208      key_image_share: dfg::EdwardsPoint(self.key_image_generator) *
209        keys.original_secret_share().deref(),
210    }
211  }
212
213  fn read_addendum<R: Read>(&self, reader: &mut R) -> io::Result<ClsagAddendum> {
214    let mut bytes = [0; 32];
215    reader.read_exact(&mut bytes)?;
216    // dfg ensures the point is torsion free
217    let xH = Option::<dfg::EdwardsPoint>::from(dfg::EdwardsPoint::from_bytes(&bytes))
218      .ok_or_else(|| io::Error::other("invalid key image"))?;
219    // Ensure this is a canonical point
220    if xH.to_bytes() != bytes {
221      Err(io::Error::other("non-canonical key image"))?;
222    }
223
224    Ok(ClsagAddendum { key_image_share: xH })
225  }
226
227  fn process_addendum(
228    &mut self,
229    view: &ThresholdView<Ed25519>,
230    l: Participant,
231    addendum: ClsagAddendum,
232  ) -> Result<(), FrostError> {
233    if bool::from(!view.group_key().0.ct_eq(&self.context.decoys.signer_ring_members()[0].into())) {
234      Err(FrostError::InternalError("CLSAG is being signed with a distinct key than intended"))?;
235    }
236
237    let mut offset = Scalar::ZERO;
238    if let Some(mask_recv) = self.mask_recv.take() {
239      self.transcript.domain_separate(b"CLSAG");
240      // Transcript the ring
241      self.context.transcript(&mut self.transcript);
242      // Fetch the mask from the Mutex
243      // We set it to a variable to ensure our view of it is consistent
244      // It was this or a mpsc channel... std doesn't have oneshot :/
245      let mask = mask_recv
246        .recv()
247        .ok_or(FrostError::InternalError("CLSAG mask was not provided before process_addendum"))?;
248      self.mask = Some(mask);
249      // Transcript the mask
250      self.transcript.append_message(b"mask", mask.to_bytes());
251
252      // Set the offset applied to the first participant
253      offset = view.offset();
254    }
255
256    // Transcript this participant's contribution
257    self.transcript.append_message(b"participant", l.to_bytes());
258    self
259      .transcript
260      .append_message(b"key_image_share", addendum.key_image_share.compress().to_bytes());
261
262    // Accumulate the interpolated share
263    let interpolated_key_image_share = ((addendum.key_image_share *
264      view
265        .interpolation_factor(l)
266        .ok_or(FrostError::InternalError("processing addendum for non-participant"))?) *
267      view.scalar()) +
268      dfg::EdwardsPoint(self.key_image_generator * offset);
269    self.image += interpolated_key_image_share;
270
271    self
272      .key_image_shares
273      .insert(view.verification_share(l).to_bytes(), interpolated_key_image_share);
274
275    Ok(())
276  }
277
278  fn transcript(&mut self) -> &mut Self::Transcript {
279    &mut self.transcript
280  }
281
282  fn sign_share(
283    &mut self,
284    view: &ThresholdView<Ed25519>,
285    nonce_sums: &[Vec<dfg::EdwardsPoint>],
286    nonces: Vec<Zeroizing<dfg::Scalar>>,
287    msg_hash: &[u8],
288  ) -> dfg::Scalar {
289    // Use the transcript to get a seeded random number generator
290    //
291    // The transcript contains private data, preventing passive adversaries from recreating this
292    // process even if they have access to the commitments/key image share broadcast so far
293    //
294    // Specifically, the transcript contains the signer's index within the ring, along with the
295    // opening of the commitment being re-randomized (and what it's re-randomized to)
296    let mut rng = ChaCha20Rng::from_seed(self.transcript.rng_seed(b"decoy_responses"));
297
298    let msg_hash = msg_hash.try_into().expect("CLSAG message hash should be 32-bytes");
299    self.msg_hash = Some(msg_hash);
300
301    let sign_core = Clsag::sign_core(
302      &mut rng,
303      &self.image,
304      &self.context,
305      self.mask.expect("mask wasn't set within process_addendum"),
306      &msg_hash,
307      nonce_sums[0][0].0,
308      nonce_sums[0][1].0,
309    );
310    self.interim = Some(Interim {
311      p: sign_core.key_challenge,
312      c: sign_core.challenged_mask,
313      clsag: sign_core.incomplete_clsag,
314      pseudo_out: sign_core.pseudo_out,
315    });
316
317    // r - p x, where p is the challenge for the keys
318    *nonces[0] - sign_core.key_challenge * view.secret_share().deref()
319  }
320
321  fn verify(
322    &self,
323    _: dfg::EdwardsPoint,
324    _: &[Vec<dfg::EdwardsPoint>],
325    sum: dfg::Scalar,
326  ) -> Option<Self::Signature> {
327    let interim = self.interim.as_ref().expect("verify called before sign_share");
328    let mut clsag = interim.clsag.clone();
329    {
330      // We produced shares as `r - p x`, yet the signature is actually `r - p x - c x`
331      // Substract `c x` (saved as `c`) now
332      let signer_s = monero_ed25519::Scalar::from(sum - interim.c);
333      for s_index in 0 ..= MAX_RING_SIZE {
334        if usize::from(s_index) == clsag.s.len() {
335          break;
336        }
337        let signer_index = s_index.ct_eq(&self.context.decoys.signer_index());
338        clsag.s[usize::from(s_index)].conditional_assign(&signer_s, signer_index);
339      }
340    }
341    if clsag
342      .verify(
343        self
344          .context
345          .decoys
346          .ring()
347          .iter()
348          .map(|m| [m[0].compress(), m[1].compress()])
349          .collect::<Vec<_>>(),
350        &CompressedPoint::from(self.image.0.compress().to_bytes()),
351        &CompressedPoint::from(interim.pseudo_out.compress().to_bytes()),
352        self.msg_hash.as_ref().expect("verify called before sign_share"),
353      )
354      .is_ok()
355    {
356      return Some((clsag, interim.pseudo_out));
357    }
358    None
359  }
360
361  fn verify_share(
362    &self,
363    verification_share: dfg::EdwardsPoint,
364    nonces: &[Vec<dfg::EdwardsPoint>],
365    share: dfg::Scalar,
366  ) -> Result<Vec<(dfg::Scalar, dfg::EdwardsPoint)>, ()> {
367    let interim = self.interim.as_ref().expect("verify_share called before sign_share");
368
369    // For a share `r - p x`, the following two equalities should hold:
370    // - `(r - p x)G == R.0 - pV`, where `V = xG`
371    // - `(r - p x)H == R.1 - pK`, where `K = xH` (the key image share)
372    //
373    // This is effectively a discrete log equality proof for:
374    // V, K over G, H
375    // with nonces
376    // R.0, R.1
377    // and solution
378    // s
379    //
380    // Which is a batch-verifiable rewrite of the traditional CP93 proof
381    // (and also writable as Generalized Schnorr Protocol)
382    //
383    // That means that given a proper challenge, this alone can be certainly argued to prove the
384    // key image share is well-formed and the provided signature so proves for that.
385
386    // This is a bit funky as it doesn't prove the nonces are well-formed however. They're part of
387    // the prover data/transcript for a CP93/GSP proof, not part of the statement. This practically
388    // is fine, for a variety of reasons (given a consistent `x`, a consistent `r` can be
389    // extracted, and the nonces as used in CLSAG are also part of its prover data/transcript).
390
391    let key_image_share = self.key_image_shares[&verification_share.to_bytes()];
392
393    // Hash every variable relevant here, using the hash output as the random weight
394    let mut weight_transcript =
395      RecommendedTranscript::new(b"monero-oxide v0.1 ClsagMultisig::verify_share");
396    weight_transcript.append_message(b"G", dfg::EdwardsPoint::generator().to_bytes());
397    weight_transcript.append_message(b"H", self.key_image_generator.to_bytes());
398    weight_transcript.append_message(b"xG", verification_share.to_bytes());
399    weight_transcript.append_message(b"xH", key_image_share.to_bytes());
400    weight_transcript.append_message(b"rG", nonces[0][0].to_bytes());
401    weight_transcript.append_message(b"rH", nonces[0][1].to_bytes());
402    weight_transcript.append_message(b"c", interim.p.to_repr());
403    weight_transcript.append_message(b"s", share.to_repr());
404    let weight = weight_transcript.challenge(b"weight");
405    let weight = Scalar::from_bytes_mod_order_wide(&weight.into());
406
407    let part_one = vec![
408      (share, dfg::EdwardsPoint::generator()),
409      // -(R.0 - pV) == -R.0 + pV
410      (-dfg::Scalar::ONE, nonces[0][0]),
411      (interim.p, verification_share),
412    ];
413
414    let mut part_two = vec![
415      (weight * share, dfg::EdwardsPoint(self.key_image_generator)),
416      // -(R.1 - pK) == -R.1 + pK
417      (-weight, nonces[0][1]),
418      (weight * interim.p, key_image_share),
419    ];
420
421    let mut all = part_one;
422    all.append(&mut part_two);
423    Ok(all)
424  }
425}
monero_clsag/multisig.rs

monero_clsag/
multisig.rs
