monero_clsag/
multisig.rs

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

monero_clsag/
multisig.rs
