w3f-bls 0.3.2

//! # Aggregate BLS signature library with extensive tuning options.
//!
//! In short, anyone using BLS signatures should normally choose both
//! an orientation as well as some aggregation and batching strategies
//! These two decissions impact performance dramaticaly, but making
//! the optimal choises requires some attentiom.  This crate employs
//! convenient abstraction boundaries between curver arithmatic,
//! verifier routines, and aggregated and/or batched BLS signatures.
//!
//! ### Pairings
//!
//! If we have two elliptic curve with a pairing `e`, then
//! a BLS signature `sigma = s*H(msg)` by a public key `S = s g1`
//! can be verified with the one equation `e(g1,sigma) = e(S,H(msg))`.
//! These simple BLS signatures are very slow to verify however
//! because the pairing map `e` is far slower than many cryptographic
//! primitives.
//!
//! Our pairing `e` maps from a small curve over `F(q)` and a larger
//! curve over `F(q^2)` into some multipliccative group if a field,
//! normally over `F(q^12)`.  In principle, this map `e` into `F(q^12)`
//! makes pairing based cryptography like BLS less secure than
//! other elliptic curve based cryptography, which further slows down
//! BLS signatures by requiring larger `q`.
//!
//! ### Arithmatic
//!
//! An almost universally applicable otimization is to seperate the
//! "Miller loop" that computes in `F(q)` and `F(q^2)` from the slow
//! final exponentiation that happens in `F(q^12)`.  So our actual
//! verification equation more resembles `e(-g1,sigma) e(S,H(msg)) = 1`.
//!
//! As one curve is smaller and hence faster, the user should choose
//! which orientation of curves they prefer, meaning to which curve
//! they hash, and which curves hold the signatues and public keys.
//! In other words, your desired aggregation techniques and usage
//! characteristics should determine if youp refer the verification
//! equation `e(g1,sigma) = e(S,H(msg))` or the fliped form
//! `e(sigma,g2) = e(H(msg),S)`.  See `UsualBLS` and `TinyBLS`.
//!
//! ### Aggregation
//!
//! We consder BLS signatures interesting because they support
//! dramatic optimizations when handling multiple signatures together.
//! In fact, BLS signatures support aggregation by a third party
//! that makes signatures smaller, not merely batch verification.  
//! All this stems from the bilinearity of `e`, meaning we reduce
//! the number of pairings, or size of the miller loop, by appling
//! rules like `e(x,z)e(y,z) = e(x+y,z)`, `e(x,y)e(x,z) = e(x,y+z)`,
//! etc.
//!
//! In essence, our aggregation tricks fall into two categories,
//! linear aggregation, in which only addition is used, and
//! delinearized optimiztions, in which we multiply curve points
//! by values unforseeable to the signers.
//! In general, linear techniques provide much better performance,
//! but require stronger invariants be maintained by the caller,
//! like messages being distinct, or limited signer sets with
//! proofs-of-possession.  Also, the delinearized techniques remain
//! secure without tricky assumptions, but require more computation.
//!
//! ### Verification
//!
//! We can often further reduce the pairings required in the
//! verification equation, beyond the naieve information tracked
//! by the aggregated signature itself.  Aggregated signature must
//! state all the individual messages and/or public keys, but
//! verifiers may collapse anything permitted.
//! We thus encounter aggregation-like decissions that impact
//! verifier performance.
//!
//! We therefore provide an abstract interface that permits
//! doing further aggregation and/or passing any aggregate signature
//! to any verification routine.
//!
//! As a rule, we also attempt to batch normalize different arithmatic
//! outputs, but concievably small signer set sizes might make this
//! a pessimization.
//!
//!
//!

// To run benchmarks (nightly only):
// 1. Uncomment `#![feature(test)]` below
// 2. Uncomment `pub mod bench;` in src/experimental/mod.rs as test module
// 3. Run `cargo +nightly test --features experimental -- --bench`
//#![feature(test)]

#![cfg_attr(not(feature = "std"), no_std)]
#[cfg_attr(feature = "std", doc = include_str!("../README.md"))]
#[cfg(doctest)]
pub struct ReadmeDoctests;

extern crate ark_serialize;
extern crate ark_serialize_derive;

extern crate ark_ec;
extern crate ark_ff;
extern crate digest;
extern crate rand;
extern crate rand_chacha;
extern crate rand_core;
extern crate sha3;

extern crate alloc;

/// Emit `Clone`, `Copy`, `PartialEq`, and `Eq` for a tuple wrapper over an
/// `E: EngineBLS` parameter. Needed because Rust's built-in `#[derive]`
/// synthesises `where` clauses (e.g. `E: Clone`) that do not hold for the
/// engine type itself, so the derived impls fail to compile. This helper
/// hand-writes the impls with the correct `E: EngineBLS` bound. Internal
/// to the crate.
#[macro_export]
#[doc(hidden)]
macro_rules! derive_with_bound {
    ($wrapper:tt) => {
        impl<E: EngineBLS> Clone for $wrapper<E> {
            fn clone(&self) -> Self {
                $wrapper(self.0)
            }
        }
        impl<E: EngineBLS> Copy for $wrapper<E> {}

        impl<E: EngineBLS> PartialEq<Self> for $wrapper<E> {
            fn eq(&self, other: &Self) -> bool {
                self.0.eq(&other.0)
            }
        }

        impl<E: EngineBLS> Eq for $wrapper<E> {}
    };
}

use ark_ff::Zero;
use core::borrow::Borrow;
use digest::DynDigest;

pub mod chaum_pedersen_signature;
pub mod double_nugget;
pub mod double_nugget_precomp;
pub mod dual_scalar_mul;
pub mod engine;
pub mod nugget;
pub mod nugget_pop;
pub mod serialize;
pub mod single;
pub mod verifiers;

pub mod pop_aggregator;

#[cfg(feature = "experimental")]
pub mod experimental;

pub use engine::*;

pub use double_nugget::{
    DoubleNuggetBLS, DoubleNuggetSignature, DoubleSignedMessage, NuggetDoublePublicKey,
};
pub use double_nugget_precomp::{
    DoubleNuggetBLSPrecomp, DoubleSignedMessagePrecomp, NuggetDoublePublicKeyPrecomp,
};
pub use dual_scalar_mul::EngineBLSGLV;
pub use nugget::{
    NuggetBLS, NuggetPublicKey, NuggetSignature, PublicKeyInSignatureGroup, PublicKeyInSisterGroup,
};
pub use nugget_pop::{NuggetBLSPoP, NuggetBLSnCPPoP};
pub use serialize::SerializableToBytes;
pub use single::{Keypair, KeypairVT, PublicKey, SecretKey, SecretKeyVT, Signature, SignedMessage};

use alloc::vec::Vec;

/// Public key types usable in the [`Signed`] trait.
///
/// Standard BLS uses [`PublicKey<E>`] which carries only the key in the
/// public-key group.  Nugget-style schemes use [`NuggetDoublePublicKey<E>`]
/// (or similar) which carries keys in **both** curve groups and thus
/// supports auxiliary-key verification.
pub trait GeneralizedBLSPublicKey<E: EngineBLS> {
    /// The public key in the public-key group.
    fn public_key(&self) -> PublicKey<E>;

    /// The auxiliary public key in the signature group.
    /// Returns zero by default (no auxiliary key).
    fn public_key_in_signature_group(&self) -> nugget::PublicKeyInSignatureGroup<E> {
        nugget::PublicKeyInSignatureGroup(E::SignatureGroup::zero())
    }
}

impl<E: EngineBLS> GeneralizedBLSPublicKey<E> for PublicKey<E> {
    fn public_key(&self) -> PublicKey<E> {
        *self
    }
}

impl<E: EngineBLS> GeneralizedBLSPublicKey<E>
    for (PublicKey<E>, nugget::PublicKeyInSignatureGroup<E>)
{
    fn public_key(&self) -> PublicKey<E> {
        self.0
    }
    fn public_key_in_signature_group(&self) -> nugget::PublicKeyInSignatureGroup<E> {
        self.1
    }
}

impl<'a, E: EngineBLS, T: GeneralizedBLSPublicKey<E>> GeneralizedBLSPublicKey<E> for &'a T {
    fn public_key(&self) -> PublicKey<E> {
        (*self).public_key()
    }
    fn public_key_in_signature_group(&self) -> nugget::PublicKeyInSignatureGroup<E> {
        (*self).public_key_in_signature_group()
    }
}

/// Internal message hash size.
///
/// We choose 256 bits here so that birthday bound attacks cannot
/// find messages with the same hash.
const MESSAGE_SIZE: usize = 32;

/// Ciphersuite standards from BLS signature draft IETF proposal
const PROOF_OF_POSSESSION_ID: &'static [u8] = b"BLS_POP_";
const NORMAL_MESSAGE_SIGNATURE_ID: &'static [u8] = b"BLS_SIG_";

const NORMAL_MESSAGE_SIGNATURE_ASSUMING_POP: &'static [u8] = b"POP_";
const NORMAL_MESSAGE_SIGNATURE_BASIC: &'static [u8] = b"NUL_";
const POP_MESSAGE: &'static [u8] = b"POP_";

type MessageDigest = [u8; MESSAGE_SIZE];
/// Internal message hash type.  Short for frequent rehashing
/// by `HashMap`, etc.
#[derive(Debug, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct Message(pub MessageDigest, pub alloc::vec::Vec<u8>, MessageType);

#[derive(Debug, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
enum MessageType {
    ProofOfPossession,
    NormalAssumingPoP,
    NormalBasic,
}

impl Message {
    pub fn new(context: &[u8], message: &[u8]) -> Message {
        let msg_hash = Self::compute_internal_hash(context, message);
        Message(
            msg_hash,
            [context, message].concat(),
            MessageType::NormalBasic,
        )
    }

    pub fn new_assuming_pop(context: &[u8], message: &[u8]) -> Message {
        let msg_hash = Self::compute_internal_hash(context, message);
        Message(
            msg_hash,
            [context, message].concat(),
            MessageType::NormalAssumingPoP,
        )
    }

    pub fn new_pop_message(context: &[u8], message: &[u8]) -> Message {
        let msg_hash = Self::compute_internal_hash(context, message);
        Message(
            msg_hash,
            [context, message].concat(),
            MessageType::ProofOfPossession,
        )
    }

    fn compute_internal_hash(context: &[u8], message: &[u8]) -> [u8; MESSAGE_SIZE] {
        use sha3::{
            Shake128,
            digest::{ExtendableOutput, Update, XofReader},
        };
        let mut h = Shake128::default();
        h.update(context);
        let l = message.len() as u64;
        h.update(&l.to_le_bytes());
        h.update(message);

        let mut msg_hash = [0u8; MESSAGE_SIZE];
        h.finalize_xof().read(&mut msg_hash[..]);

        msg_hash
    }

    /// generate ciphersuite string added to the context according to
    /// BLS Signature draft proposal to IETF
    fn cipher_suite<E: EngineBLS>(&self) -> Vec<u8> {
        let id = match self.2 {
            MessageType::ProofOfPossession => PROOF_OF_POSSESSION_ID,
            MessageType::NormalAssumingPoP => NORMAL_MESSAGE_SIGNATURE_ID,
            MessageType::NormalBasic => NORMAL_MESSAGE_SIGNATURE_ID,
        };

        let h2c_suite_id = [
            E::CURVE_NAME,
            E::SIG_GROUP_NAME,
            E::CIPHER_SUIT_DOMAIN_SEPARATION,
        ]
        .concat();

        let sc_tag = match self.2 {
            MessageType::ProofOfPossession => POP_MESSAGE,
            MessageType::NormalAssumingPoP => NORMAL_MESSAGE_SIGNATURE_ASSUMING_POP,
            MessageType::NormalBasic => NORMAL_MESSAGE_SIGNATURE_BASIC,
        };

        [id, &h2c_suite_id[..], sc_tag].concat()
    }

    pub fn hash_to_signature_curve<E: EngineBLS>(&self) -> E::SignatureGroup {
        E::hash_to_signature_curve(&[&self.cipher_suite::<E>()[..], &self.1[..]].concat()[..])
    }
}

/// Representation of an aggregated BLS signature.
///
/// We implement this trait only for borrows of appropriate structs
/// because otherwise we'd need extensive lifetime plumbing here,
/// due to the absence of assocaited type constructers (ATCs).
/// We shall make `messages_and_publickeys` take `&sefl` and
/// remove these limitations in the future once ATCs stabalize,
/// thus removing `PKG`.  See [Rust RFC 1598](https://github.com/rust-lang/rfcs/blob/master/text/1598-generic_associated_types.md)
pub trait Signed: Sized {
    type E: EngineBLS;

    /// Return the aggregated signature
    fn signature(&self) -> Signature<Self::E>;

    type M: Borrow<Message>;
    type PKG: GeneralizedBLSPublicKey<Self::E>;

    /// Returns an iterator over messages and public key reference for
    /// pairings, often only partially aggregated.
    fn messages_and_publickeys(
        self,
    ) -> impl Iterator<Item = (Self::M, Self::PKG)> + ExactSizeIterator;

    /// Appropriate BLS signature verification for the `Self` type.
    ///
    /// We use `verify_simple` as a default implementation because
    /// it supports unstable `self.messages_and_publickeys()` securely
    /// by calling it only once, and does not expect pulic key points
    /// to be normalized, but this should usually be replaced by more
    /// optimized variants.
    fn verify(self) -> bool {
        verifiers::verify_simple(self)
    }
}

pub trait ProofOfPossession<E, H, PV>
where
    E: EngineBLS,
    H: DynDigest + Default + Clone,
{
    fn verify(&self, public_key_of_prover: &PV) -> bool;
}

/// ProofOfPossion trait which should be implemented by secret
pub trait ProofOfPossessionGenerator<
    E: EngineBLS,
    H: DynDigest + Default + Clone,
    PV,
    P: ProofOfPossession<E, H, PV>,
>
{
    /// The proof of possession generator is supposed to
    /// to produce a schnorr signature or a bls signature using
    /// the secret key which it claims to possess. This proves that
    /// that the secret key is known.
    fn generate_pok(&mut self) -> P;
}