monero_clsag/
multisig.rs

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

monero_clsag/
multisig.rs
