generic-schnorr 0.8.1

//! Schnorr signature implementation generic over the underlying group.

#![cfg_attr(not(test), no_std)]

#[cfg(feature = "verify-batch")]
extern crate alloc;

#[cfg(feature = "verify-batch")]
use alloc::vec::Vec;

use group::Group;
use group::cofactor::CofactorGroup;
use group::ff::PrimeField;
#[cfg(feature = "verify-batch")]
use group::ff::PrimeFieldBits;
use rand_core::{CryptoRng, RngCore};
#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};

/// Signature produced by [`sign`].
#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
#[allow(non_snake_case)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct Signature<Point, Scalar> {
    pub R: Point,
    pub s: Scalar,
}

impl<Point, Scalar> Signature<Point, Scalar> {
    /// Get the inner `R` and `s` parameters of the signature.
    pub const fn as_inner(&self) -> (&Point, &Scalar) {
        (&self.R, &self.s)
    }
}

/// Produce a [`Signature`] over `message`.
///
/// The group arithmetic uses `generator` to produce
/// public keys.
///
/// ## Safety
///
/// The user must not provide a random number generator
/// instance that is likely to produce nonce values that
/// have already been instantiated for previous signatures.
/// This poses the risk of exposing the underlying
/// secret key.
pub fn sign<Msg, Rng, HashToField, Point, Scalar>(
    generator: &Point,
    message: &Msg,
    secret_key: &Scalar,
    rng: Rng,
    hash_to_field: HashToField,
) -> Signature<Point, Scalar>
where
    Msg: ?Sized,
    HashToField: FnOnce(&Point, &Point, &Msg) -> Scalar,
    Rng: RngCore + CryptoRng,
    Point: CofactorGroup + Group<Scalar = Scalar>,
    Scalar: PrimeField,
{
    let nonce = Scalar::random(rng);

    #[allow(non_snake_case)]
    let R = *generator * nonce;

    let challenge = hash_to_field(
        &R,                         // commit to nonce
        &(*generator * secret_key), // commit to public key
        message,                    // commit to message
    );

    let s = (challenge * secret_key) + nonce;

    Signature { R, s }
}

/// Verify a signature.
///
/// The group arithmetic uses `generator` to produce
/// public keys.
pub fn verify<Msg, HashToField, Point, Scalar>(
    generator: &Point,
    message: &Msg,
    public_key: &Point,
    Signature { R, s }: &Signature<Point, Scalar>,
    hash_to_field: HashToField,
) -> bool
where
    Msg: ?Sized,
    HashToField: FnOnce(&Point, &Point, &Msg) -> Scalar,
    Point: CofactorGroup + Group<Scalar = Scalar>,
    Scalar: PrimeField,
{
    if public_key.is_small_order().into() || R.is_small_order().into() {
        return false;
    }

    let challenge = hash_to_field(
        R,          // commit to nonce
        public_key, // commit to public key
        message,    // commit to message
    );

    (*public_key * challenge + R - *generator * s)
        .clear_cofactor()
        .is_identity()
        .into()
}

/// Verify a bach of signatures over the same message,
/// from different signing keys.
///
/// The group arithmetic uses `generators[i]` to produce
/// public keys. Each `usize` value `i` in `auths` indexes
/// `generators[i]` (i.e. `generators[i] * sk == auths[i].1`).
///
/// Generators passed in are assumed to be trusted (not small order).
#[cfg(feature = "verify-batch")]
pub fn verify_batch<Msg, HashToField, Point, Scalar, Rng>(
    generators: &[Point],
    message: &Msg,
    auths: &[(usize, Point, Signature<Point, Scalar>)],
    mut hash_to_field: HashToField,
    rng: Rng,
) -> bool
where
    Msg: ?Sized,
    Rng: RngCore + CryptoRng,
    HashToField: FnMut(&Point, &Point, &Msg) -> Scalar,
    Point: CofactorGroup + Group<Scalar = Scalar>,
    Scalar: PrimeFieldBits,
{
    if auths.is_empty() {
        return true;
    }

    let mut s_coeffs = alloc::vec![Scalar::ZERO; generators.len()];
    let mut msm_buf = Vec::with_capacity(2 * auths.len() + generators.len());

    let z_seed = Scalar::random(rng);
    let mut z_pow = Scalar::ONE;

    for (generator_index, public_key, Signature { R, s }) in auths {
        if public_key.is_small_order().into() || R.is_small_order().into() {
            return false;
        }

        let challenge = hash_to_field(
            R,          // commit to nonce
            public_key, // commit to public key
            message,    // commit to message
        );

        let z = z_pow;
        let neg_z = -z_pow;

        z_pow *= z_seed;

        let s_coeff = z * s;
        s_coeffs[*generator_index] += s_coeff;

        let r_term = (neg_z, *R);
        let pk_term = (neg_z * challenge, *public_key);

        msm_buf.push(r_term);
        msm_buf.push(pk_term);
    }

    for (s_coeff, generator) in s_coeffs.into_iter().zip(generators) {
        let s_term = (s_coeff, *generator);
        msm_buf.push(s_term);
    }

    // verify: h * (\sum [s_acc]G - r_acc - pk_acc) == 0
    multiexp::multiexp_vartime(&msm_buf)
        .clear_cofactor()
        .is_identity()
        .into()
}

#[cfg(test)]
mod tests {
    use group::GroupEncoding;
    use group::ff::{Field, FromUniformBytes};
    use pasta_curves::pallas;
    use rand_chacha::ChaCha20Rng;
    use rand_core::SeedableRng;

    use super::*;

    #[test]
    fn test_sign_verify() {
        let mut csprng = test_csprng();

        let message = b"eat shit";
        let generator = pallas::Point::generator();
        let secret_key = pallas::Scalar::random(&mut csprng);

        let signature = sign(
            &generator,
            &message[..],
            &secret_key,
            &mut csprng,
            hash_to_field,
        );

        assert!(verify(
            &generator,
            &message[..],
            &(generator * secret_key),
            &signature,
            hash_to_field,
        ));
    }

    #[test]
    fn test_sign_verify_batch() {
        let mut csprng = test_csprng();

        let message = b"eat shit";
        let generators = [pallas::Point::random(&mut csprng); 4];

        let auths = (0..8)
            .map(|i| {
                let secret_key = pallas::Scalar::random(&mut csprng);
                let public_key = generators[i >> 1] * secret_key;

                let signature = sign(
                    &generators[i >> 1],
                    &message[..],
                    &secret_key,
                    &mut csprng,
                    hash_to_field,
                );

                (i >> 1, public_key, signature)
            })
            .collect::<Vec<_>>();

        assert!(verify_batch(
            &generators,
            &message[..],
            &auths,
            hash_to_field,
            csprng,
        ));
    }

    fn test_csprng() -> ChaCha20Rng {
        ChaCha20Rng::from_seed([0xbe; 32])
    }

    fn hash_to_field(
        nonce: &pallas::Point,
        public_key: &pallas::Point,
        message: &[u8],
    ) -> pallas::Scalar {
        let mut xof_stream = {
            let mut hasher = blake3::Hasher::new();
            hasher.update(&nonce.to_bytes());
            hasher.update(&public_key.to_bytes());
            hasher.update(message);
            hasher.finalize_xof()
        };

        let mut output = [0u8; 64];
        xof_stream.fill(&mut output);

        pallas::Scalar::from_uniform_bytes(&output)
    }
}