tari_crypto/signatures/
commitment_and_public_key_signature.rs

1// Copyright 2021. The Tari Project
2// SPDX-License-Identifier: BSD-3-Clause
3
4use alloc::vec::Vec;
5use core::{
6    cmp::Ordering,
7    hash::{Hash, Hasher},
8    ops::{Add, Mul},
9};
10
11use rand_core::{CryptoRng, RngCore};
12use snafu::prelude::*;
13use tari_utilities::ByteArray;
14
15use crate::{
16    alloc::borrow::ToOwned,
17    commitment::{HomomorphicCommitment, HomomorphicCommitmentFactory},
18    keys::{PublicKey, SecretKey},
19    signatures::SchnorrSignature,
20};
21
22/// An error when creating a commitment signature
23#[derive(Clone, Debug, Snafu, PartialEq, Eq)]
24#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
25#[allow(missing_docs)]
26pub enum CommitmentAndPublicKeySignatureError {
27    #[snafu(display("An invalid challenge was provided"))]
28    InvalidChallenge,
29}
30
31/// # Commitment and public key (CAPK) signatures
32///
33/// Given a commitment `commitment = a*H + x*G` and group element `pubkey = y*G`, a CAPK signature is based on
34/// a representation proof of both openings: `(a, x)` and `y`. It additionally binds to arbitrary message data `m`
35/// via the challenge to produce a signature construction.
36///
37/// It is used in Tari protocols as part of transaction authorization.
38///
39/// The construction works as follows:
40/// - Sample scalar nonces `r_a, r_x, r_y` uniformly at random.
41/// - Compute ephemeral values `ephemeral_commitment = r_a*H + r_x*G` and `ephemeral_pubkey = r_y*G`.
42/// - Use strong Fiat-Shamir to produce a challenge `e`. If `e == 0` (this is unlikely), abort and start over.
43/// - Compute the responses `u_a = r_a + e*a` and `u_x = r_x + e*x` and `u_y = r_y + e*y`.
44///
45/// The signature is the tuple `(ephemeral_commitment, ephemeral_pubkey, u_a, u_x, u_y)`.
46///
47/// To verify:
48/// - The verifier computes the challenge `e` and rejects the signature if `e == 0` (this is unlikely).
49/// - Verification succeeds if and only if the following equations hold: `u_a*H + u*x*G == ephemeral_commitment +
50///   e*commitment` `u_y*G == ephemeral_pubkey + e*pubkey`
51///
52/// We note that it is possible to make verification slightly more efficient. To do so, the verifier selects a nonzero
53/// scalar weight `w` uniformly at random (not through Fiat-Shamir!) and accepts the signature if and only if the
54/// following equation holds:
55///     `u_a*H + (u_x + w*u_y)*G - ephemeral_commitment - w*ephemeral_pubkey - e*commitment - (w*e)*pubkey == 0`
56/// The use of efficient multiscalar multiplication algorithms may also be useful for efficiency.
57/// The use of precomputation tables for `G` and `H` may also be useful for efficiency.
58
59#[derive(Debug, Clone)]
60#[cfg_attr(feature = "borsh", derive(borsh::BorshSerialize, borsh::BorshDeserialize))]
61#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
62pub struct CommitmentAndPublicKeySignature<P, K> {
63    pub(crate) ephemeral_commitment: HomomorphicCommitment<P>,
64    pub(crate) ephemeral_pubkey: P,
65    pub(crate) u_a: K,
66    pub(crate) u_x: K,
67    pub(crate) u_y: K,
68}
69
70impl<P, K> CommitmentAndPublicKeySignature<P, K>
71where
72    P: PublicKey<K = K>,
73    K: SecretKey,
74{
75    /// Creates a new [CommitmentSignature]
76    pub fn new(ephemeral_commitment: HomomorphicCommitment<P>, ephemeral_pubkey: P, u_a: K, u_x: K, u_y: K) -> Self {
77        CommitmentAndPublicKeySignature {
78            ephemeral_commitment,
79            ephemeral_pubkey,
80            u_a,
81            u_x,
82            u_y,
83        }
84    }
85
86    /// Complete a signature using the given challenge. The challenge is provided by the caller to support the
87    /// multiparty use case. It is _very important_ that it be computed using strong Fiat-Shamir! Further, the
88    /// values `r_a, r_x, r_y` are nonces, must be sampled uniformly at random, and must never be reused.
89    #[allow(clippy::too_many_arguments)]
90    pub fn sign<C>(
91        a: &K,
92        x: &K,
93        y: &K,
94        r_a: &K,
95        r_x: &K,
96        r_y: &K,
97        challenge: &[u8],
98        factory: &C,
99    ) -> Result<Self, CommitmentAndPublicKeySignatureError>
100    where
101        K: Mul<P, Output = P>,
102        for<'a> &'a K: Add<&'a K, Output = K>,
103        for<'a> &'a K: Mul<&'a K, Output = K>,
104        C: HomomorphicCommitmentFactory<P = P>,
105    {
106        // The challenge is computed by wide reduction
107        let e = match K::from_uniform_bytes(challenge) {
108            Ok(e) => e,
109            Err(_) => return Err(CommitmentAndPublicKeySignatureError::InvalidChallenge),
110        };
111
112        // The challenge cannot be zero
113        if e == K::default() {
114            return Err(CommitmentAndPublicKeySignatureError::InvalidChallenge);
115        }
116
117        // Compute the response values
118        let ea = &e * a;
119        let ex = &e * x;
120        let ey = &e * y;
121
122        let u_a = r_a + &ea;
123        let u_x = r_x + &ex;
124        let u_y = r_y + &ey;
125
126        // Compute the initial values
127        let ephemeral_commitment = factory.commit(r_x, r_a);
128        let ephemeral_pubkey = P::from_secret_key(r_y);
129
130        Ok(Self::new(ephemeral_commitment, ephemeral_pubkey, u_a, u_x, u_y))
131    }
132
133    /// Verify a signature on a commitment and group element statement using a given challenge (as a byte array)
134    pub fn verify_challenge<'a, C, R>(
135        &self,
136        commitment: &'a HomomorphicCommitment<P>,
137        pubkey: &'a P,
138        challenge: &[u8],
139        factory: &C,
140        rng: &mut R,
141    ) -> bool
142    where
143        for<'b> &'a HomomorphicCommitment<P>: Mul<&'b K, Output = HomomorphicCommitment<P>>,
144        for<'b> &'b P: Mul<&'b K, Output = P>,
145        for<'b> &'b HomomorphicCommitment<P>: Add<&'b HomomorphicCommitment<P>, Output = HomomorphicCommitment<P>>,
146        for<'b> &'b P: Add<&'b P, Output = P>,
147        for<'b> &'b K: Mul<&'b K, Output = K>,
148        for<'b> &'b K: Add<&'b K, Output = K>,
149        C: HomomorphicCommitmentFactory<P = P>,
150        R: RngCore + CryptoRng,
151    {
152        // The challenge is computed by wide reduction
153        let e = match K::from_uniform_bytes(challenge) {
154            Ok(e) => e,
155            Err(_) => return false,
156        };
157
158        self.verify(commitment, pubkey, &e, factory, rng)
159    }
160
161    /// Verify a signature on a commitment and group element statement using a given challenge (as a scalar)
162    pub fn verify<'a, C, R>(
163        &self,
164        commitment: &'a HomomorphicCommitment<P>,
165        pubkey: &'a P,
166        challenge: &K,
167        factory: &C,
168        rng: &mut R,
169    ) -> bool
170    where
171        for<'b> &'a HomomorphicCommitment<P>: Mul<&'b K, Output = HomomorphicCommitment<P>>,
172        for<'b> &'b P: Mul<&'b K, Output = P>,
173        for<'b> &'b HomomorphicCommitment<P>: Add<&'b HomomorphicCommitment<P>, Output = HomomorphicCommitment<P>>,
174        for<'b> &'b P: Add<&'b P, Output = P>,
175        for<'b> &'b K: Mul<&'b K, Output = K>,
176        for<'b> &'b K: Add<&'b K, Output = K>,
177        C: HomomorphicCommitmentFactory<P = P>,
178        R: RngCore + CryptoRng,
179    {
180        // Reject a zero commitment and public key
181        if commitment.as_public_key() == &P::default() || pubkey == &P::default() {
182            return false;
183        }
184
185        // The challenge cannot be zero
186        if *challenge == K::default() {
187            return false;
188        }
189
190        // Use a single weighted equation for verification to avoid unnecessary group operations
191        // For now, we use naive multiscalar multiplication, but offload the commitment computation
192        // This allows for the use of precomputation within the commitment itself, which is more efficient
193        let w = K::random(rng); // must be random and not Fiat-Shamir!
194
195        // u_a*H + (u_x + w*u_y)*G == ephemeral_commitment + w*ephemeral_pubkey + e*commitment + (w*e)*pubkey
196        let verifier_lhs = factory
197            .commit(&(&self.u_x + &(&w * &self.u_y)), &self.u_a)
198            .as_public_key()
199            .to_owned();
200        let verifier_rhs_unweighted =
201            self.ephemeral_commitment.as_public_key() + (commitment * challenge).as_public_key();
202        let verifier_rhs_weighted = &self.ephemeral_pubkey * &w + pubkey * &(&w * challenge);
203
204        verifier_lhs == verifier_rhs_unweighted + verifier_rhs_weighted
205    }
206
207    /// Get the signature tuple `(ephemeral_commitment, ephemeral_pubkey, u_a, u_x, u_y)`
208    pub fn complete_signature_tuple(&self) -> (&HomomorphicCommitment<P>, &P, &K, &K, &K) {
209        (
210            &self.ephemeral_commitment,
211            &self.ephemeral_pubkey,
212            &self.u_a,
213            &self.u_x,
214            &self.u_y,
215        )
216    }
217
218    /// Get the response value `u_a`
219    pub fn u_a(&self) -> &K {
220        &self.u_a
221    }
222
223    /// Get the response value `u_x`
224    pub fn u_x(&self) -> &K {
225        &self.u_x
226    }
227
228    /// Get the response value `u_y`
229    pub fn u_y(&self) -> &K {
230        &self.u_y
231    }
232
233    /// Get the ephemeral commitment `ephemeral_commitment`
234    pub fn ephemeral_commitment(&self) -> &HomomorphicCommitment<P> {
235        &self.ephemeral_commitment
236    }
237
238    /// Get the ephemeral public key `ephemeral_pubkey`
239    pub fn ephemeral_pubkey(&self) -> &P {
240        &self.ephemeral_pubkey
241    }
242
243    /// Produce a canonical byte representation of the commitment signature
244    pub fn to_vec(&self) -> Vec<u8> {
245        let mut buf = Vec::with_capacity(2 * P::key_length() + 3 * K::key_length());
246        buf.extend_from_slice(self.ephemeral_commitment().as_bytes());
247        buf.extend_from_slice(self.ephemeral_pubkey().as_bytes());
248        buf.extend_from_slice(self.u_a().as_bytes());
249        buf.extend_from_slice(self.u_x().as_bytes());
250        buf.extend_from_slice(self.u_y().as_bytes());
251        buf
252    }
253}
254
255impl<'a, 'b, P, K> Add<&'b CommitmentAndPublicKeySignature<P, K>> for &'a CommitmentAndPublicKeySignature<P, K>
256where
257    P: PublicKey<K = K>,
258    &'a HomomorphicCommitment<P>: Add<&'b HomomorphicCommitment<P>, Output = HomomorphicCommitment<P>>,
259    &'a P: Add<&'b P, Output = P>,
260    K: SecretKey,
261    &'a K: Add<&'b K, Output = K>,
262{
263    type Output = CommitmentAndPublicKeySignature<P, K>;
264
265    fn add(self, rhs: &'b CommitmentAndPublicKeySignature<P, K>) -> CommitmentAndPublicKeySignature<P, K> {
266        let ephemeral_commitment_sum = self.ephemeral_commitment() + rhs.ephemeral_commitment();
267        let ephemeral_pubkey_sum_sum = self.ephemeral_pubkey() + rhs.ephemeral_pubkey();
268        let u_a_sum = self.u_a() + rhs.u_a();
269        let u_x_sum = self.u_x() + rhs.u_x();
270        let u_y_sum = self.u_y() + rhs.u_y();
271
272        CommitmentAndPublicKeySignature::new(
273            ephemeral_commitment_sum,
274            ephemeral_pubkey_sum_sum,
275            u_a_sum,
276            u_x_sum,
277            u_y_sum,
278        )
279    }
280}
281
282impl<'a, P, K> Add<CommitmentAndPublicKeySignature<P, K>> for &'a CommitmentAndPublicKeySignature<P, K>
283where
284    P: PublicKey<K = K>,
285    for<'b> &'a HomomorphicCommitment<P>: Add<&'b HomomorphicCommitment<P>, Output = HomomorphicCommitment<P>>,
286    for<'b> &'a P: Add<&'b P, Output = P>,
287    K: SecretKey,
288    for<'b> &'a K: Add<&'b K, Output = K>,
289{
290    type Output = CommitmentAndPublicKeySignature<P, K>;
291
292    fn add(self, rhs: CommitmentAndPublicKeySignature<P, K>) -> CommitmentAndPublicKeySignature<P, K> {
293        let ephemeral_commitment_sum = self.ephemeral_commitment() + rhs.ephemeral_commitment();
294        let ephemeral_pubkey_sum_sum = self.ephemeral_pubkey() + rhs.ephemeral_pubkey();
295        let u_a_sum = self.u_a() + rhs.u_a();
296        let u_x_sum = self.u_x() + rhs.u_x();
297        let u_y_sum = self.u_y() + rhs.u_y();
298
299        CommitmentAndPublicKeySignature::new(
300            ephemeral_commitment_sum,
301            ephemeral_pubkey_sum_sum,
302            u_a_sum,
303            u_x_sum,
304            u_y_sum,
305        )
306    }
307}
308
309impl<'a, 'b, P, K> Add<&'b SchnorrSignature<P, K>> for &'a CommitmentAndPublicKeySignature<P, K>
310where
311    P: PublicKey<K = K>,
312    &'a HomomorphicCommitment<P>: Add<&'b HomomorphicCommitment<P>, Output = HomomorphicCommitment<P>>,
313    &'a P: Add<&'b P, Output = P>,
314    K: SecretKey,
315    &'a K: Add<&'b K, Output = K>,
316{
317    type Output = CommitmentAndPublicKeySignature<P, K>;
318
319    fn add(self, rhs: &'b SchnorrSignature<P, K>) -> CommitmentAndPublicKeySignature<P, K> {
320        let ephemeral_commitment_sum = self.ephemeral_commitment().clone();
321        let ephemeral_pubkey_sum_sum = self.ephemeral_pubkey() + rhs.get_public_nonce();
322        let u_a_sum = self.u_a().clone();
323        let u_x_sum = self.u_x().clone();
324        let u_y_sum = self.u_y() + rhs.get_signature();
325
326        CommitmentAndPublicKeySignature::new(
327            ephemeral_commitment_sum,
328            ephemeral_pubkey_sum_sum,
329            u_a_sum,
330            u_x_sum,
331            u_y_sum,
332        )
333    }
334}
335
336impl<'a, P, K> Add<SchnorrSignature<P, K>> for &'a CommitmentAndPublicKeySignature<P, K>
337where
338    P: PublicKey<K = K>,
339    for<'b> &'a HomomorphicCommitment<P>: Add<&'b HomomorphicCommitment<P>, Output = HomomorphicCommitment<P>>,
340    for<'b> &'a P: Add<&'b P, Output = P>,
341    K: SecretKey,
342    for<'b> &'a K: Add<&'b K, Output = K>,
343{
344    type Output = CommitmentAndPublicKeySignature<P, K>;
345
346    fn add(self, rhs: SchnorrSignature<P, K>) -> CommitmentAndPublicKeySignature<P, K> {
347        let ephemeral_commitment_sum = self.ephemeral_commitment().clone();
348        let ephemeral_pubkey_sum_sum = self.ephemeral_pubkey() + rhs.get_public_nonce();
349        let u_a_sum = self.u_a().clone();
350        let u_x_sum = self.u_x().clone();
351        let u_y_sum = self.u_y() + rhs.get_signature();
352
353        CommitmentAndPublicKeySignature::new(
354            ephemeral_commitment_sum,
355            ephemeral_pubkey_sum_sum,
356            u_a_sum,
357            u_x_sum,
358            u_y_sum,
359        )
360    }
361}
362
363impl<P, K> Default for CommitmentAndPublicKeySignature<P, K>
364where
365    P: PublicKey<K = K>,
366    K: SecretKey,
367{
368    fn default() -> Self {
369        CommitmentAndPublicKeySignature::new(
370            HomomorphicCommitment::<P>::default(),
371            P::default(),
372            K::default(),
373            K::default(),
374            K::default(),
375        )
376    }
377}
378
379/// Provide a canonical ordering for commitment signatures. We use byte representations of all values in this order:
380/// `ephemeral_commitment, ephemeral_pubkey, u_a, u_x, u_y`
381impl<P, K> Ord for CommitmentAndPublicKeySignature<P, K>
382where
383    P: PublicKey<K = K>,
384    K: SecretKey,
385{
386    fn cmp(&self, other: &Self) -> Ordering {
387        let mut compare = self.ephemeral_commitment().cmp(other.ephemeral_commitment());
388        if compare != Ordering::Equal {
389            return compare;
390        }
391
392        compare = self.ephemeral_pubkey().cmp(other.ephemeral_pubkey());
393        if compare != Ordering::Equal {
394            return compare;
395        }
396
397        compare = self.u_a().as_bytes().cmp(other.u_a().as_bytes());
398        if compare != Ordering::Equal {
399            return compare;
400        }
401
402        compare = self.u_x().as_bytes().cmp(other.u_x().as_bytes());
403        if compare != Ordering::Equal {
404            return compare;
405        }
406
407        self.u_y().as_bytes().cmp(other.u_y().as_bytes())
408    }
409}
410
411impl<P, K> PartialOrd for CommitmentAndPublicKeySignature<P, K>
412where
413    P: PublicKey<K = K>,
414    K: SecretKey,
415{
416    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
417        Some(self.cmp(other))
418    }
419}
420
421impl<P, K> PartialEq for CommitmentAndPublicKeySignature<P, K>
422where
423    P: PublicKey<K = K>,
424    K: SecretKey,
425{
426    fn eq(&self, other: &Self) -> bool {
427        self.ephemeral_commitment().eq(other.ephemeral_commitment()) &&
428            self.ephemeral_pubkey().eq(other.ephemeral_pubkey()) &&
429            self.u_a().eq(other.u_a()) &&
430            self.u_x().eq(other.u_x()) &&
431            self.u_y().eq(other.u_y())
432    }
433}
434
435impl<P, K> Eq for CommitmentAndPublicKeySignature<P, K>
436where
437    P: PublicKey<K = K>,
438    K: SecretKey,
439{
440}
441
442impl<P, K> Hash for CommitmentAndPublicKeySignature<P, K>
443where
444    P: PublicKey<K = K>,
445    K: SecretKey,
446{
447    fn hash<H: Hasher>(&self, state: &mut H) {
448        state.write(&self.to_vec())
449    }
450}
tari_crypto/signatures/commitment_and_public_key_signature.rs

tari_crypto/signatures/
commitment_and_public_key_signature.rs
