ark-vrf 0.5.1

//! # Elliptic Curve VRF
//!
//! Implementations of Verifiable Random Function with Additional Data (VRF-AD)
//! schemes built on a transcript-based Fiat-Shamir transform with support for
//! multiple input/output pairs via delinearization.
//!
//! Built on the [Arkworks](https://github.com/arkworks-rs) framework with
//! configurable cryptographic parameters and `no_std` support.
//!
//! ## Security
//!
//! VRF input points **must** be constructed via hash-to-curve (e.g.
//! [`Input::new`]) so that nobody knows their discrete-log relation to the
//! generator `G`. If the prover knew such a relation, they could forge
//! outputs. This is critical because the delinearization merges the Schnorr
//! and VRF pairs into a single check.
//!
//! ## Schemes
//!
//! - **Tiny VRF**: Compact proof. Loosely inspired by
//!   [RFC-9381](https://datatracker.ietf.org/doc/rfc9381), adapted with a
//!   transcript-based Fiat-Shamir transform, support for additional data, and
//!   multiple I/O pairs via delinearization.
//!
//! - **Thin VRF**: Same structure as Tiny VRF but stores the nonce commitment
//!   instead of the challenge, enabling batch verification at the cost of a
//!   slightly larger proof.
//!
//! - **Pedersen VRF**: Key-hiding VRF based on the construction introduced by
//!   [BCHSV23](https://eprint.iacr.org/2023/002). Replaces the public key with a
//!   Pedersen commitment to the secret key, serving as a building block for
//!   anonymized ring signatures.
//!
//! - **Ring VRF**: Anonymized ring VRF combining Pedersen VRF with the ring proof
//!   scheme derived from [CSSV22](https://eprint.iacr.org/2022/1362). Proves that
//!   a single blinded key is a member of a committed ring without revealing which one.
//!
//! ### Specifications
//!
//! - [VRF Schemes](https://github.com/davxy/bandersnatch-vrf-spec)
//! - [Ring Proof](https://github.com/davxy/ring-proof-spec)
//!
//! ## Built-In suites
//!
//! The library conditionally includes the following pre-configured suites (see features section):
//!
//! - **Ed25519**: Supports Tiny, Thin, and Pedersen VRF.
//! - **Secp256r1**: Supports Tiny, Thin, and Pedersen VRF.
//! - **Bandersnatch** (_Edwards curve on BLS12-381_): Supports Tiny, Thin, Pedersen, and Ring VRF.
//! - **JubJub** (_Edwards curve on BLS12-381_): Supports Tiny, Thin, Pedersen, and Ring VRF.
//! - **Baby-JubJub** (_Edwards curve on BN254_): Supports Tiny, Thin, Pedersen, and Ring VRF.
//!
//! ## Usage
//!
//! ```rust,ignore
//! use ark_vrf::suites::bandersnatch::*;
//!
//! let secret = Secret::from_seed([0; 32]);
//! let public = secret.public();
//! let input = Input::new(b"example input").unwrap();
//! let output = secret.output(input);
//! let hash_bytes: [u8; 32] = output.hash();
//! ```
//!
//! ## Features
//!
//! - `default`: `std`
//! - `full`: Enables all features listed below except `secret-split`, `parallel`, `asm`, `test-vectors`.
//! - `secret-split`: Split-secret scalar multiplication. Secret scalar is split into the sum
//!   of two scalars, which randomly mutate but retain the same sum. Incurs 2x penalty in some internal
//!   sensible scalar multiplications, but provides side channel defenses.
//! - `ring`: Ring-VRF for the curves supporting it.
//! - `test-vectors`: Deterministic ring-vrf proof. Useful for reproducible test vectors generation.
//!
//! ### Curves
//!
//! - `ed25519`
//! - `jubjub`
//! - `bandersnatch`
//! - `baby-jubjub`
//! - `secp256r1`
//!
//! ### Arkworks optimizations
//!
//! - `parallel`: Parallel execution where worth using `rayon`.
//! - `asm`: Assembly implementation of some low level operations.
//!
//! ## License
//!
//! Distributed under the [MIT License](./LICENSE).

#![cfg_attr(not(feature = "std"), no_std)]
#![deny(unsafe_code)]

use ark_ec::{AffineRepr, CurveGroup};
use ark_ff::{PrimeField, Zero};
use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
use ark_std::vec::Vec;

use utils::transcript::Transcript;
use zeroize::Zeroize;

pub mod pedersen;
pub mod suites;
pub mod thin;
pub mod tiny;
pub mod utils;

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

#[cfg(test)]
mod testing;

/// Re-export stuff that may be useful downstream.
pub mod reexports {
    pub use ark_ec;
    pub use ark_ff;
    pub use ark_serialize;
    pub use ark_std;
}

/// Suite's affine curve point type.
pub type AffinePoint<S> = <S as Suite>::Affine;
/// Suite's base field type.
pub type BaseField<S> = <AffinePoint<S> as AffineRepr>::BaseField;
/// Suite's scalar field type.
pub type ScalarField<S> = <AffinePoint<S> as AffineRepr>::ScalarField;
/// Suite's curve configuration type.
pub type CurveConfig<S> = <AffinePoint<S> as AffineRepr>::Config;

/// Crate error type.
#[derive(Debug)]
pub enum Error {
    /// Proof verification failed.
    VerificationFailure,
    /// Invalid input data (e.g. point not in the prime-order subgroup,
    /// deserialization failure, ring size exceeding parameters).
    InvalidData,
}

impl From<ark_serialize::SerializationError> for Error {
    fn from(_err: ark_serialize::SerializationError) -> Self {
        Error::InvalidData
    }
}

/// Defines a cipher suite.
///
/// Configures the elliptic curve, transcript, and core operations (nonce
/// generation, challenge derivation, hash-to-curve) for a VRF-AD scheme.
/// The default implementations are inspired by RFC-9381 and RFC-8032 but
/// use a pluggable [`Transcript`]-based Fiat-Shamir transform rather than
/// the specific hash constructions prescribed by the RFC. Default methods
/// can be overridden to implement custom VRF variants.
pub trait Suite: Copy {
    /// Suite identifier.
    ///
    /// A unique byte string used for transcript domain separation and as the
    /// hash-to-curve DST prefix. The actual constructions a `SUITE_ID` stands
    /// for are defined by the suite specification (see each suite's module
    /// docs). Implementations targeting interop must use the same string.
    const SUITE_ID: &'static [u8];

    /// Curve point in affine representation.
    ///
    /// The point is guaranteed to be in the correct prime order subgroup
    /// by the `AffineRepr` bound.
    type Affine: AffineRepr;

    /// Fiat-Shamir transcript.
    ///
    /// Provides absorb/squeeze interface for challenge generation,
    /// nonce derivation, delinearization, and other hash-based operations.
    type Transcript: Transcript;

    /// Generator used through all the suite.
    ///
    /// Defaults to Arkworks provided generator.
    #[inline(always)]
    fn generator() -> AffinePoint<Self> {
        Self::Affine::generator()
    }

    /// Generate a nonce scalar from the secret key and transcript state.
    ///
    /// The transcript typically carries shared state from `vrf_transcript`,
    /// binding the nonce to the I/O pairs and additional data.
    ///
    /// Defaults to [`utils::nonce`] (deterministic, inspired by RFC-8032 section 5.1.6).
    #[inline(always)]
    fn nonce(sk: &ScalarField<Self>, transcript: Option<Self::Transcript>) -> ScalarField<Self> {
        utils::nonce::<Self>(sk, transcript)
    }

    /// Derive a challenge scalar from curve points and transcript state.
    ///
    /// Absorbs curve points into the transcript and squeezes a scalar.
    /// The transcript typically carries shared state from `vrf_transcript`.
    ///
    /// Defaults to [`utils::challenge`] (inspired by RFC-9381 section 5.4.3).
    #[inline(always)]
    fn challenge(
        pts: &[&AffinePoint<Self>],
        transcript: Option<Self::Transcript>,
    ) -> ScalarField<Self> {
        utils::challenge::<Self>(pts, transcript)
    }

    /// Hash data to a curve point.
    ///
    /// The input `data` is the raw pre-image; any salting must be applied
    /// by the caller before invoking this method.
    ///
    /// Defaults to [`utils::hash_to_curve_tai`] (try-and-increment).
    /// Override for alternative methods like [`utils::hash_to_curve_ell2_xmd`] (Elligator2).
    #[inline(always)]
    fn data_to_point(data: &[u8]) -> Option<AffinePoint<Self>> {
        utils::hash_to_curve_tai::<Self>(data)
    }

    /// Map a curve point to a hash value.
    ///
    /// Defaults to [`utils::point_to_hash`].
    #[inline(always)]
    fn point_to_hash<const N: usize>(pt: &AffinePoint<Self>) -> [u8; N] {
        utils::point_to_hash::<Self, N>(pt, false)
    }
}

/// Secret key for VRF operations.
///
/// Contains the private scalar and cached public key.
/// Implements automatic zeroization on drop.
#[derive(Debug, Clone, PartialEq)]
pub struct Secret<S: Suite> {
    /// Secret scalar.
    pub(crate) scalar: ScalarField<S>,
    /// Cached public key.
    pub(crate) public: Public<S>,
}

impl<S: Suite> Drop for Secret<S> {
    fn drop(&mut self) {
        self.scalar.zeroize()
    }
}

impl<S: Suite> CanonicalSerialize for Secret<S> {
    fn serialize_with_mode<W: ark_std::io::prelude::Write>(
        &self,
        writer: W,
        compress: ark_serialize::Compress,
    ) -> Result<(), ark_serialize::SerializationError> {
        self.scalar.serialize_with_mode(writer, compress)
    }

    fn serialized_size(&self, compress: ark_serialize::Compress) -> usize {
        self.scalar.serialized_size(compress)
    }
}

impl<S: Suite> CanonicalDeserialize for Secret<S> {
    fn deserialize_with_mode<R: ark_std::io::prelude::Read>(
        reader: R,
        compress: ark_serialize::Compress,
        validate: ark_serialize::Validate,
    ) -> Result<Self, ark_serialize::SerializationError> {
        let scalar = <ScalarField<S> as CanonicalDeserialize>::deserialize_with_mode(
            reader, compress, validate,
        )?;
        Ok(Self::from_scalar(scalar))
    }
}

impl<S: Suite> ark_serialize::Valid for Secret<S> {
    fn check(&self) -> Result<(), ark_serialize::SerializationError> {
        self.scalar.check()
    }
}

impl<S: Suite> Secret<S> {
    /// Construct a `Secret` from the given scalar.
    pub fn from_scalar(scalar: ScalarField<S>) -> Self {
        let public = Public((S::generator() * scalar).into_affine());
        Self { scalar, public }
    }

    /// Derives a `Secret` scalar deterministically from a seed.
    ///
    /// The seed is hashed using the suite's transcript, and the output is
    /// reduced modulo the curve's order to produce a valid scalar in the
    /// range `[1, n - 1]`. No clamping or multiplication by the cofactor is
    /// performed, regardless of the curve.
    ///
    /// The caller is responsible for ensuring that the resulting scalar is
    /// used safely with respect to the target curve's cofactor and subgroup
    /// properties.
    pub fn from_seed(seed: [u8; 32]) -> Self {
        let mut cnt = 0_u8;
        let sk = ScalarField::<S>::from_le_bytes_mod_order(&seed);
        let scalar = loop {
            let mut transcript = S::Transcript::new(S::SUITE_ID);
            transcript.absorb_raw(&seed);
            if cnt > 0 {
                transcript.absorb_raw(&[cnt]);
            }
            let scalar = utils::nonce::<S>(&sk, Some(transcript.clone()));
            if !scalar.is_zero() {
                break scalar;
            }
            // Reaching 256 consecutive zero scalars is unreachable under
            // standard assumptions on the transcript hash (probability
            // ≈ 2^(-65000)); hitting it implies a broken primitive.
            cnt = cnt
                .checked_add(1)
                .expect("unreachable: transcript hash produced 256 consecutive zero scalars");
        };
        Self::from_scalar(scalar)
    }

    /// Construct an ephemeral `Secret` using the provided randomness source.
    pub fn from_rand(rng: &mut impl ark_std::rand::RngCore) -> Self {
        let mut seed = [0u8; 32];
        rng.fill_bytes(&mut seed);
        Self::from_seed(seed)
    }

    /// Get the secret scalar.
    pub fn scalar(&self) -> &ScalarField<S> {
        &self.scalar
    }

    /// Get the associated public key.
    pub fn public(&self) -> Public<S> {
        self.public
    }

    /// Get the VRF output point relative to input.
    pub fn output(&self, input: Input<S>) -> Output<S> {
        Output(smul!(input.0, self.scalar).into_affine())
    }

    /// Get the VRF input-output pair relative to input.
    pub fn vrf_io(&self, input: Input<S>) -> VrfIo<S> {
        VrfIo {
            input,
            output: self.output(input),
        }
    }
}

/// Public key generic over the cipher suite.
///
/// Elliptic curve point representing the public component of a VRF key pair.
#[derive(Debug, Copy, Clone, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
pub struct Public<S: Suite>(pub AffinePoint<S>);

impl<S: Suite> Public<S> {
    /// Construct from an affine point with subgroup validation.
    ///
    /// Returns `Error::InvalidData` if the point is not in the prime-order subgroup.
    pub fn from_affine(value: AffinePoint<S>) -> Result<Self, Error> {
        ark_serialize::Valid::check(&value).map_err(|_| Error::InvalidData)?;
        Ok(Self(value))
    }

    /// Construct from an affine point without subgroup checks.
    ///
    /// The caller must ensure `value` is in the prime-order subgroup.
    pub fn from_affine_unchecked(value: AffinePoint<S>) -> Self {
        Self(value)
    }
}

/// VRF input point generic over the cipher suite.
///
/// Elliptic curve point representing the VRF input.
#[derive(Debug, Clone, Copy, PartialEq, Eq, CanonicalSerialize, CanonicalDeserialize)]
pub struct Input<S: Suite>(pub AffinePoint<S>);

impl<S: Suite> Input<S> {
    /// Construct from [`Suite::data_to_point`].
    ///
    /// Maps arbitrary data to a curve point via hash-to-curve.
    pub fn new(data: &[u8]) -> Option<Self> {
        S::data_to_point(data).map(Input)
    }
}

impl<S: Suite> Input<S> {
    /// Construct from an affine point with subgroup validation.
    ///
    /// Returns `Error::InvalidData` if the point is not in the prime-order subgroup.
    ///
    /// Note: this only validates subgroup membership, not that the point was
    /// produced by hash-to-curve. The caller is still responsible for ensuring
    /// the point is not in a known discrete-log relation with the suite
    /// generator (required for Thin-VRF soundness).
    pub fn from_affine(value: AffinePoint<S>) -> Result<Self, Error> {
        ark_serialize::Valid::check(&value).map_err(|_| Error::InvalidData)?;
        Ok(Self(value))
    }

    /// Construct from an affine point without subgroup checks.
    ///
    /// # Safety
    ///
    /// The caller must ensure that `value` is in the prime-order subgroup and
    /// was produced by a hash-to-curve procedure (or is otherwise not in a
    /// known discrete-log relation with the suite generator). The latter is
    /// required for the soundness of schemes like Thin-VRF where the input
    /// and generator are delinearized into a single check.
    pub fn from_affine_unchecked(value: AffinePoint<S>) -> Self {
        Self(value)
    }
}

/// VRF output point generic over the cipher suite.
///
/// Elliptic curve point representing the VRF output.
#[derive(Debug, Clone, Copy, PartialEq, Eq, CanonicalSerialize, CanonicalDeserialize)]
pub struct Output<S: Suite>(pub AffinePoint<S>);

impl<S: Suite> Output<S> {
    /// Construct from an affine point with subgroup validation.
    ///
    /// Returns `Error::InvalidData` if the point is not in the prime-order subgroup.
    pub fn from_affine(value: AffinePoint<S>) -> Result<Self, Error> {
        ark_serialize::Valid::check(&value).map_err(|_| Error::InvalidData)?;
        Ok(Self(value))
    }

    /// Construct from an affine point without subgroup checks.
    ///
    /// The caller must ensure `value` is in the prime-order subgroup.
    pub fn from_affine_unchecked(value: AffinePoint<S>) -> Self {
        Self(value)
    }
}

impl<S: Suite> Output<S> {
    /// Hash the output point to a deterministic byte string.
    pub fn hash<const N: usize>(&self) -> [u8; N] {
        S::point_to_hash(&self.0)
    }
}

/// VRF input-output pair.
#[derive(Debug, Clone, Copy, PartialEq, Eq, CanonicalSerialize, CanonicalDeserialize)]
pub struct VrfIo<S: Suite> {
    pub input: Input<S>,
    pub output: Output<S>,
}

impl<S: Suite> AsRef<[VrfIo<S>]> for VrfIo<S> {
    fn as_ref(&self) -> &[VrfIo<S>] {
        core::slice::from_ref(self)
    }
}

/// Type aliases for the given suite.
#[macro_export]
macro_rules! suite_types {
    ($suite:ident) => {
        #[allow(dead_code)]
        pub type Secret = $crate::Secret<$suite>;
        #[allow(dead_code)]
        pub type Public = $crate::Public<$suite>;
        #[allow(dead_code)]
        pub type Input = $crate::Input<$suite>;
        #[allow(dead_code)]
        pub type Output = $crate::Output<$suite>;
        #[allow(dead_code)]
        pub type AffinePoint = $crate::AffinePoint<$suite>;
        #[allow(dead_code)]
        pub type ScalarField = $crate::ScalarField<$suite>;
        #[allow(dead_code)]
        pub type BaseField = $crate::BaseField<$suite>;
        #[allow(dead_code)]
        pub type TinyProof = $crate::tiny::Proof<$suite>;
        #[allow(dead_code)]
        pub type PedersenProof = $crate::pedersen::Proof<$suite>;
        #[allow(dead_code)]
        pub type PedersenBatchItem = $crate::pedersen::BatchItem<$suite>;
        #[allow(dead_code)]
        pub type PedersenBatchVerifier = $crate::pedersen::BatchVerifier<$suite>;
        #[allow(dead_code)]
        pub type ThinProof = $crate::thin::Proof<$suite>;
        #[allow(dead_code)]
        pub type ThinBatchItem = $crate::thin::BatchItem<$suite>;
        #[allow(dead_code)]
        pub type ThinBatchVerifier = $crate::thin::BatchVerifier<$suite>;
        #[allow(dead_code)]
        pub type VrfIo = $crate::VrfIo<$suite>;
    };
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::tiny::{Prover, Verifier};
    use ark_ec::AffineRepr;
    use suites::testing::{Input, Secret, TestSuite};
    use testing::{TEST_SEED, random_val};

    #[test]
    fn vrf_output_check() {
        use ark_std::rand::SeedableRng;
        let mut rng = ark_std::rand::rngs::StdRng::from_seed([42; 32]);
        let secret = Secret::from_seed(TEST_SEED);
        let input = Input::from_affine_unchecked(random_val(Some(&mut rng)));
        let output = secret.output(input);

        let expected = "4af9bf572a107a8f61faa380667efe27eaf399cc8e718d57ef328924eb51d450";
        assert_eq!(expected, hex::encode(output.hash::<32>()));
    }

    #[test]
    fn prove_uniqueness_vulnerability() {
        use ark_ff::BigInteger;
        use ark_std::{One, Zero};
        use utils::common::{DomSep, ExactChain};

        type S = TestSuite;
        type Sc = ScalarField<S>;

        let secret = crate::Secret::<S>::from_seed(TEST_SEED);
        let public = secret.public();
        let input = Input::new(b"uniqueness attack").unwrap();
        let honest_output = secret.output(input);

        // 1. Find a low-order point L (order 2 for Ed25519)
        // For Ed25519, (0, -1) is order 2.
        let low_order_pt =
            AffinePoint::<S>::new_unchecked(BaseField::<S>::zero(), -BaseField::<S>::one());
        assert!(!low_order_pt.is_zero());
        // Verify it's order 2: 2 * L = O
        assert!((low_order_pt.into_group() + low_order_pt.into_group()).is_zero());

        // 2. Compute gamma' = gamma + L
        let malicious_output =
            Output::from_affine_unchecked((honest_output.0 + low_order_pt).into_affine());
        assert_ne!(honest_output, malicious_output);
        assert_ne!(honest_output.hash::<32>(), malicious_output.hash::<32>());

        // 3. Forge a proof by grinding k until c*z_1 is even (so c*z_1*L = 0)
        //
        // The verify equation for the VRF I/O part is s*I_m - c*O_m = k*I_m,
        // where O_m includes z_1*(O_honest + L). For this to hold we need
        // c*z_1*L = 0, i.e. c*z_1 must be even (since L has order 2).
        // Since c is odd (ground below) we also need z_1 to be even.
        // z_1 is the delinearization scalar determined by (pk, ios, ad), so
        // we iterate over ad values to find one where z_1 is even.
        let malicious_io = VrfIo {
            input,
            output: malicious_output,
        };
        let mal_ios = [malicious_io];

        // Search for an ad that produces an even delinearization scalar z_1.
        let mut ad_ctr = 0u32;
        let (ad, t, merged_input) = loop {
            let ad = format!("ad-{ad_ctr}");
            let schnorr = core::iter::once(VrfIo {
                input: Input(S::generator()),
                output: Output(public.0),
            });
            let chain = ExactChain::new(schnorr, mal_ios.iter().copied());
            let (t, zs) =
                utils::vrf_transcript_scalars_from_iter(DomSep::TinyVrf, chain, ad.as_bytes());
            // z_1 is the delinearization scalar for the VRF pair
            if zs[1].into_bigint().is_even() {
                // Compute merged input: I_m = z_0*G + z_1*I
                let i_m = (S::generator() * zs[0] + input.0 * zs[1]).into_affine();
                break (ad, t, i_m);
            }
            ad_ctr += 1;
            assert!(ad_ctr < 100, "Failed to find suitable ad");
        };

        // Now grind k to get an odd challenge c (so that q-c is even, i.e. (-c)*L = 0).
        let mut ctr = 0u64;
        let proof = loop {
            let mut k_seed = [0u8; 8];
            k_seed.copy_from_slice(&ctr.to_le_bytes());
            let k = Sc::from_le_bytes_mod_order(&k_seed);

            // R = k * I_m (merged input including Schnorr pair)
            let r = (merged_input * k).into_affine();

            let c = S::challenge(&[&r], Some(t.clone()));

            if !c.into_bigint().is_even() {
                let s = k + c * secret.scalar;
                break crate::tiny::Proof { c, s };
            }
            ctr += 1;
            assert!(ctr <= 1000, "Grinding failed");
        };

        // 4. Verify the malicious proof
        assert!(public.verify(malicious_io, ad.as_bytes(), &proof).is_ok());

        // 5. Verify the honest proof still works
        let honest_io = VrfIo {
            input,
            output: honest_output,
        };
        let honest_proof = secret.prove(honest_io, ad.as_bytes());
        assert!(
            public
                .verify(honest_io, ad.as_bytes(), &honest_proof)
                .is_ok()
        );

        // Two different outputs for the same input and public key.
        assert_ne!(honest_output.hash::<32>(), malicious_output.hash::<32>());
    }
}