solana_ecvrf/
lib.rs

1//! ECVRF-EDWARDS25519-SHA512-TAI ([RFC 9381]) verification for Solana programs.
2//!
3//! A VRF proof is a signature whose output is also a pseudorandom 64-byte value
4//! that is unique per (key, input): the prover cannot grind for a favourable
5//! output, which is what makes it usable as on-chain randomness.
6//!
7//! On `target_os = "solana"` every primitive is a syscall: `sol_curve_*` for
8//! the group arithmetic and `sol_sha512` (SIMD-0512) for hashing. Nothing
9//! cryptographic runs in software.
10//!
11//! [RFC 9381]: https://www.rfc-editor.org/rfc/rfc9381
12#![no_std]
13
14mod curve;
15mod scalar;
16mod sha512;
17#[cfg(target_os = "solana")]
18mod syscalls;
19
20#[cfg(all(any(feature = "prove", test), not(target_os = "solana")))]
21mod prove;
22#[cfg(all(any(feature = "prove", test), not(target_os = "solana")))]
23pub use prove::SecretKey;
24
25#[cfg(test)]
26mod tests;
27
28/// `suite_string` for ECVRF-EDWARDS25519-SHA512-TAI, RFC 9381 §5.5.
29pub const SUITE: u8 = 0x03;
30pub const PUBLIC_KEY_LENGTH: usize = 32;
31/// `ptLen + cLen + qLen = 32 + 16 + 32`.
32pub const PROOF_LENGTH: usize = 80;
33pub const OUTPUT_LENGTH: usize = 64;
34
35/// VRF hash output `beta_string`.
36pub type Output = [u8; OUTPUT_LENGTH];
37
38#[derive(Clone, Copy, Debug, PartialEq, Eq)]
39pub enum Error {
40    /// Not a point on edwards25519, or a point of order 1, 2, 4 or 8.
41    InvalidPublicKey,
42    /// Gamma is not on the curve, `s >= L`, or the challenge does not verify.
43    InvalidProof,
44}
45
46/// An Ed25519 public key `Y = x·B`, compressed per RFC 8032 §5.1.2. The same
47/// bytes as the Solana address of the proving keypair.
48#[derive(Clone, Copy, Debug, PartialEq, Eq)]
49pub struct PublicKey(pub [u8; PUBLIC_KEY_LENGTH]);
50
51/// `pi_string = Gamma || c || s`.
52#[derive(Clone, Copy, Debug, PartialEq, Eq)]
53pub struct Proof(pub [u8; PROOF_LENGTH]);
54
55impl PublicKey {
56    /// RFC 9381 §5.3 steps 1–3 with `validate_key = TRUE`: on the curve and
57    /// not small-order, so the output is unique even for an adversarial key.
58    /// One `validate_point` syscall (159 CU) plus a seven-entry table lookup.
59    /// `verify` already covers this; use it when registering keys up front.
60    #[inline]
61    pub fn validate(&self) -> Result<(), Error> {
62        if curve::validate(&self.0) && !curve::is_small_order(&self.0) {
63            Ok(())
64        } else {
65            Err(Error::InvalidPublicKey)
66        }
67    }
68}
69
70impl Proof {
71    #[inline(always)]
72    fn gamma(&self) -> &[u8; 32] {
73        self.0[..32].try_into().unwrap()
74    }
75
76    #[inline(always)]
77    fn c(&self) -> &[u8; 16] {
78        self.0[32..48].try_into().unwrap()
79    }
80
81    #[inline(always)]
82    fn s(&self) -> &[u8; 32] {
83        self.0[48..].try_into().unwrap()
84    }
85
86    /// RFC 9381 §5.3, `ECVRF_verify` with `validate_key = TRUE`. Returns
87    /// `beta_string` on success.
88    ///
89    /// Syscall budget: 2 two-term multiscalar multiplications
90    /// (`U = s·B - c·Y`, `V = s·H - c·Gamma`), 6 additions (`8·H'`, `8·Gamma`),
91    /// plus one validation per try-and-increment attempt. `Y` and `Gamma` are
92    /// not validated separately: the multiscalar multiplications decompress
93    /// them and fail on a bad encoding, so an explicit check would only add a
94    /// syscall each. The small-order check on `Y` is a table lookup.
95    #[inline]
96    pub fn verify(&self, public_key: &PublicKey, alpha: &[u8]) -> Result<Output, Error> {
97        let y = &public_key.0;
98        let gamma = self.gamma();
99        let c = self.c();
100        let s = self.s();
101
102        if curve::is_small_order(y) {
103            return Err(Error::InvalidPublicKey);
104        }
105        // §5.4.4 decode_proof: s canonical here; "Gamma on the curve" is
106        // decided by the `V` multiscalar multiplication below.
107        if !scalar::is_canonical(s) {
108            return Err(Error::InvalidProof);
109        }
110
111        let h = encode_to_curve(y, alpha).ok_or(Error::InvalidProof)?;
112
113        let neg_c = scalar::negate_challenge(c);
114        // `s`, `-c` and `B` are known good, so only `Y` can make this fail.
115        let u = curve::double_scalar_mul(s, &curve::BASEPOINT, &neg_c, y)
116            .ok_or(Error::InvalidPublicKey)?;
117        // `H` was just computed, so only `Gamma` can make this fail.
118        let v = curve::double_scalar_mul(s, &h, &neg_c, gamma).ok_or(Error::InvalidProof)?;
119
120        if challenge(y, &h, gamma, &u, &v) != *c {
121            return Err(Error::InvalidProof);
122        }
123        self.derive_output()
124    }
125
126    #[inline]
127    fn derive_output(&self) -> Result<Output, Error> {
128        let gamma8 = curve::mul_by_cofactor(self.gamma()).ok_or(Error::InvalidProof)?;
129        Ok(sha512::hashv(&[&[SUITE, 0x03], &gamma8, &[0x00]]))
130    }
131}
132
133/// RFC 9381 §5.4.1.1, try-and-increment with `encode_to_curve_salt = Y`.
134/// Returns `H = 8·H'` for the first `ctr` whose hash decodes to a point of
135/// order greater than 8. Expected two attempts; `None` has probability 2^-256.
136/// Validating before doubling is deliberate: a failed doubling costs 473 CU
137/// against 159 for a failed validation.
138#[inline]
139pub(crate) fn encode_to_curve(y: &[u8; 32], alpha: &[u8]) -> Option<curve::Point> {
140    for ctr in 0..=u8::MAX {
141        let hash = sha512::hashv(&[&[SUITE, 0x01], y, alpha, &[ctr, 0x00]]);
142        let candidate: &[u8; 32] = hash[..32].try_into().unwrap();
143        if curve::validate(candidate) && !curve::is_small_order(candidate) {
144            return curve::mul_by_cofactor(candidate);
145        }
146    }
147    None
148}
149
150/// RFC 9381 §5.4.3: first 16 bytes of `SHA-512(suite || 0x02 || Y || H || Gamma || U || V || 0x00)`.
151#[inline]
152pub(crate) fn challenge(
153    y: &[u8; 32],
154    h: &[u8; 32],
155    gamma: &[u8; 32],
156    u: &[u8; 32],
157    v: &[u8; 32],
158) -> [u8; 16] {
159    let hash = sha512::hashv(&[&[SUITE, 0x02], y, h, gamma, u, v, &[0x00]]);
160    hash[..16].try_into().unwrap()
161}
solana_ecvrf/lib.rs

solana_ecvrf/
lib.rs
