solana-ecvrf 0.0.1

//! ECVRF-EDWARDS25519-SHA512-TAI ([RFC 9381]) verification for Solana programs.
//!
//! A VRF proof is a signature whose output is also a pseudorandom 64-byte value
//! that is unique per (key, input): the prover cannot grind for a favourable
//! output, which is what makes it usable as on-chain randomness.
//!
//! On `target_os = "solana"` every primitive is a syscall: `sol_curve_*` for
//! the group arithmetic and `sol_sha512` (SIMD-0512) for hashing. Nothing
//! cryptographic runs in software.
//!
//! [RFC 9381]: https://www.rfc-editor.org/rfc/rfc9381
#![no_std]

mod curve;
mod scalar;
mod sha512;
#[cfg(target_os = "solana")]
mod syscalls;

#[cfg(all(any(feature = "prove", test), not(target_os = "solana")))]
mod prove;
#[cfg(all(any(feature = "prove", test), not(target_os = "solana")))]
pub use prove::SecretKey;

#[cfg(test)]
mod tests;

/// `suite_string` for ECVRF-EDWARDS25519-SHA512-TAI, RFC 9381 §5.5.
pub const SUITE: u8 = 0x03;
pub const PUBLIC_KEY_LENGTH: usize = 32;
/// `ptLen + cLen + qLen = 32 + 16 + 32`.
pub const PROOF_LENGTH: usize = 80;
pub const OUTPUT_LENGTH: usize = 64;

/// VRF hash output `beta_string`.
pub type Output = [u8; OUTPUT_LENGTH];

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Error {
    /// Not a point on edwards25519, or a point of order 1, 2, 4 or 8.
    InvalidPublicKey,
    /// Gamma is not on the curve, `s >= L`, or the challenge does not verify.
    InvalidProof,
}

/// An Ed25519 public key `Y = x·B`, compressed per RFC 8032 §5.1.2. The same
/// bytes as the Solana address of the proving keypair.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct PublicKey(pub [u8; PUBLIC_KEY_LENGTH]);

/// `pi_string = Gamma || c || s`.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Proof(pub [u8; PROOF_LENGTH]);

impl PublicKey {
    /// RFC 9381 §5.3 steps 1–3 with `validate_key = TRUE`: on the curve and
    /// not small-order, so the output is unique even for an adversarial key.
    /// One `validate_point` syscall (159 CU) plus a seven-entry table lookup.
    /// `verify` already covers this; use it when registering keys up front.
    #[inline]
    pub fn validate(&self) -> Result<(), Error> {
        if curve::validate(&self.0) && !curve::is_small_order(&self.0) {
            Ok(())
        } else {
            Err(Error::InvalidPublicKey)
        }
    }
}

impl Proof {
    #[inline(always)]
    fn gamma(&self) -> &[u8; 32] {
        self.0[..32].try_into().unwrap()
    }

    #[inline(always)]
    fn c(&self) -> &[u8; 16] {
        self.0[32..48].try_into().unwrap()
    }

    #[inline(always)]
    fn s(&self) -> &[u8; 32] {
        self.0[48..].try_into().unwrap()
    }

    /// RFC 9381 §5.3, `ECVRF_verify` with `validate_key = TRUE`. Returns
    /// `beta_string` on success.
    ///
    /// Syscall budget: 2 two-term multiscalar multiplications
    /// (`U = s·B - c·Y`, `V = s·H - c·Gamma`), 6 additions (`8·H'`, `8·Gamma`),
    /// plus one validation per try-and-increment attempt. `Y` and `Gamma` are
    /// not validated separately: the multiscalar multiplications decompress
    /// them and fail on a bad encoding, so an explicit check would only add a
    /// syscall each. The small-order check on `Y` is a table lookup.
    #[inline]
    pub fn verify(&self, public_key: &PublicKey, alpha: &[u8]) -> Result<Output, Error> {
        let y = &public_key.0;
        let gamma = self.gamma();
        let c = self.c();
        let s = self.s();

        if curve::is_small_order(y) {
            return Err(Error::InvalidPublicKey);
        }
        // §5.4.4 decode_proof: s canonical here; "Gamma on the curve" is
        // decided by the `V` multiscalar multiplication below.
        if !scalar::is_canonical(s) {
            return Err(Error::InvalidProof);
        }

        let h = encode_to_curve(y, alpha).ok_or(Error::InvalidProof)?;

        let neg_c = scalar::negate_challenge(c);
        // `s`, `-c` and `B` are known good, so only `Y` can make this fail.
        let u = curve::double_scalar_mul(s, &curve::BASEPOINT, &neg_c, y)
            .ok_or(Error::InvalidPublicKey)?;
        // `H` was just computed, so only `Gamma` can make this fail.
        let v = curve::double_scalar_mul(s, &h, &neg_c, gamma).ok_or(Error::InvalidProof)?;

        if challenge(y, &h, gamma, &u, &v) != *c {
            return Err(Error::InvalidProof);
        }
        self.derive_output()
    }

    #[inline]
    fn derive_output(&self) -> Result<Output, Error> {
        let gamma8 = curve::mul_by_cofactor(self.gamma()).ok_or(Error::InvalidProof)?;
        Ok(sha512::hashv(&[&[SUITE, 0x03], &gamma8, &[0x00]]))
    }
}

/// RFC 9381 §5.4.1.1, try-and-increment with `encode_to_curve_salt = Y`.
/// Returns `H = 8·H'` for the first `ctr` whose hash decodes to a point of
/// order greater than 8. Expected two attempts; `None` has probability 2^-256.
/// Validating before doubling is deliberate: a failed doubling costs 473 CU
/// against 159 for a failed validation.
#[inline]
pub(crate) fn encode_to_curve(y: &[u8; 32], alpha: &[u8]) -> Option<curve::Point> {
    for ctr in 0..=u8::MAX {
        let hash = sha512::hashv(&[&[SUITE, 0x01], y, alpha, &[ctr, 0x00]]);
        let candidate: &[u8; 32] = hash[..32].try_into().unwrap();
        if curve::validate(candidate) && !curve::is_small_order(candidate) {
            return curve::mul_by_cofactor(candidate);
        }
    }
    None
}

/// RFC 9381 §5.4.3: first 16 bytes of `SHA-512(suite || 0x02 || Y || H || Gamma || U || V || 0x00)`.
#[inline]
pub(crate) fn challenge(
    y: &[u8; 32],
    h: &[u8; 32],
    gamma: &[u8; 32],
    u: &[u8; 32],
    v: &[u8; 32],
) -> [u8; 16] {
    let hash = sha512::hashv(&[&[SUITE, 0x02], y, h, gamma, u, v, &[0x00]]);
    hash[..16].try_into().unwrap()
}