solana-ecvrf 0.0.1

extern crate std;

use crate::{Error, Proof, PublicKey, SecretKey, curve, scalar, sha512};
use curve25519_dalek::{
    Scalar,
    constants::{ED25519_BASEPOINT_COMPRESSED, EIGHT_TORSION},
    edwards::CompressedEdwardsY,
};
use std::vec::Vec;

/// `L` as bytes: `-1 mod L` is canonical and ends in 0xec, so `+1` never carries.
fn group_order() -> [u8; 32] {
    let mut l = (-Scalar::ONE).to_bytes();
    l[0] += 1;
    l
}

fn hex(s: &str) -> Vec<u8> {
    (0..s.len())
        .step_by(2)
        .map(|i| u8::from_str_radix(&s[i..i + 2], 16).unwrap())
        .collect()
}

/// RFC 9381 Appendix B.3, Examples 16–18: (SK, PK, alpha, pi, beta).
const VECTORS: [(&str, &str, &str, &str, &str); 3] = [
    (
        "9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60",
        "d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a",
        "",
        "8657106690b5526245a92b003bb079ccd1a92130477671f6fc01ad16f26f723f26f8a57ccaed74ee1b190bed1f479d9727d2d0f9b005a6e456a35d4fb0daab1268a1b0db10836d9826a528ca76567805",
        "90cf1df3b703cce59e2a35b925d411164068269d7b2d29f3301c03dd757876ff66b71dda49d2de59d03450451af026798e8f81cd2e333de5cdf4f3e140fdd8ae",
    ),
    (
        "4ccd089b28ff96da9db6c346ec114e0f5b8a319f35aba624da8cf6ed4fb8a6fb",
        "3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c",
        "72",
        "f3141cd382dc42909d19ec5110469e4feae18300e94f304590abdced48aed5933bf0864a62558b3ed7f2fea45c92a465301b3bbf5e3e54ddf2d935be3b67926da3ef39226bbc355bdc9850112c8f4b02",
        "eb4440665d3891d668e7e0fcaf587f1b4bd7fbfe99d0eb2211ccec90496310eb5e33821bc613efb94db5e5b54c70a848a0bef4553a41befc57663b56373a5031",
    ),
    (
        "c5aa8df43f9f837bedb7442f31dcb7b166d38535076f094b85ce3a2e0b4458f7",
        "fc51cd8e6218a1a38da47ed00230f0580816ed13ba3303ac5deb911548908025",
        "af82",
        "9bc0f79119cc5604bf02d23b4caede71393cedfbb191434dd016d30177ccbf8096bb474e53895c362d8628ee9f9ea3c0e52c7a5c691b6c18c9979866568add7a2d41b00b05081ed0f58ee5e31b3a970e",
        "645427e5d00c62a23fb703732fa5d892940935942101e456ecca7bb217c61c452118fec1219202a0edcf038bb6373241578be7217ba85a2687f7a0310b2df19f",
    ),
];

fn vectors() -> impl Iterator<Item = (SecretKey, PublicKey, Vec<u8>, Proof, [u8; 64])> {
    VECTORS.iter().map(|(sk, pk, alpha, pi, beta)| {
        (
            SecretKey(hex(sk).try_into().unwrap()),
            PublicKey(hex(pk).try_into().unwrap()),
            hex(alpha),
            Proof(hex(pi).try_into().unwrap()),
            hex(beta).try_into().unwrap(),
        )
    })
}

#[test]
fn rfc9381_verify() {
    for (_, pk, alpha, pi, beta) in vectors() {
        assert_eq!(pi.verify(&pk, &alpha), Ok(beta));
        assert_eq!(pi.derive_output(), Ok(beta));
    }
}

#[test]
fn rfc9381_prove() {
    for (sk, pk, alpha, pi, _) in vectors() {
        assert_eq!(sk.public_key(), pk);
        assert_eq!(sk.prove(&alpha), pi);
    }
}

#[test]
fn round_trip_random() {
    let mut seed = [7u8; 32];
    for i in 0..64u8 {
        seed = sha512::hashv(&[&seed])[..32].try_into().unwrap();
        let sk = SecretKey(seed);
        let alpha = &[i; 64][..i as usize];
        let pi = sk.prove(alpha);
        let beta = pi.verify(&sk.public_key(), alpha).unwrap();
        assert_eq!(pi.derive_output().unwrap(), beta);
        tampering_rejected(&sk.public_key(), alpha, &pi);
    }
}

fn tampering_rejected(pk: &PublicKey, alpha: &[u8], pi: &Proof) {
    for i in 0..crate::PROOF_LENGTH {
        let mut bad = *pi;
        bad.0[i] ^= 1;
        assert_eq!(bad.verify(pk, alpha), Err(Error::InvalidProof), "byte {i}");
    }
    assert_eq!(pi.verify(pk, b"x"), Err(Error::InvalidProof));
    let mut other = *pk;
    other.0[0] ^= 1;
    assert!(pi.verify(&other, alpha).is_err());
    // s >= L
    let mut bad = *pi;
    bad.0[48..].copy_from_slice(&group_order());
    assert_eq!(bad.verify(pk, alpha), Err(Error::InvalidProof));
}

#[test]
fn rfc_vector_tampering() {
    let (_, pk, alpha, pi, _) = vectors().next().unwrap();
    tampering_rejected(&pk, &alpha, &pi);
}

#[test]
fn small_order_keys_rejected() {
    for t in EIGHT_TORSION.iter() {
        let pk = PublicKey(t.compress().0);
        assert_eq!(pk.validate(), Err(Error::InvalidPublicKey));
    }
    // An encoding that is not a curve point: first y (with sign 0) dalek rejects.
    let off_curve = (2u8..)
        .find(|&y| CompressedEdwardsY([y; 32]).decompress().is_none())
        .unwrap();
    assert_eq!(
        PublicKey([off_curve; 32]).validate(),
        Err(Error::InvalidPublicKey)
    );
}

/// The lookup table covers exactly the small-order encodings: every 8-torsion
/// point (both signs, and the `y + p` non-canonical form when it fits in 255
/// bits) hits it, and every table entry that decodes is small-order.
#[test]
fn small_order_table_is_exact() {
    let p = {
        let mut p = [0xffu8; 32];
        p[0] = 0xed;
        p[31] = 0x7f;
        p
    };
    for t in EIGHT_TORSION.iter() {
        let y = t.compress().0;
        for sign in [0u8, 0x80] {
            let mut enc = y;
            enc[31] |= sign;
            assert!(curve::is_small_order(&enc));
            // y + p, if < 2^255
            let (mut carry, mut sum) = (0u16, [0u8; 32]);
            for i in 0..32 {
                let v = y[i] as u16 + p[i] as u16 + carry;
                sum[i] = v as u8;
                carry = v >> 8;
            }
            if carry == 0 && sum[31] & 0x80 == 0 {
                sum[31] |= sign;
                assert!(
                    CompressedEdwardsY(sum)
                        .decompress()
                        .unwrap()
                        .is_small_order()
                );
                assert!(curve::is_small_order(&sum));
            }
        }
    }
    for mut enc in curve::SMALL_ORDER_Y {
        for sign in [0u8, 0x80] {
            enc[31] = (enc[31] & 0x7f) | sign;
            if let Some(pt) = CompressedEdwardsY(enc).decompress() {
                assert!(pt.is_small_order());
            }
        }
    }
    assert!(!curve::is_small_order(&ED25519_BASEPOINT_COMPRESSED.0));
}

#[test]
fn constants_match_dalek() {
    assert_eq!(curve::BASEPOINT, ED25519_BASEPOINT_COMPRESSED.0);
    assert!(!scalar::is_canonical(&group_order()));
    let mut l_minus_1 = group_order();
    l_minus_1[0] -= 1;
    assert!(scalar::is_canonical(&l_minus_1));
    assert!(scalar::is_canonical(&[0; 32]));
}

#[test]
fn negate_challenge_is_negation_mod_l() {
    let mut c = [0u8; 16];
    for i in 0..256 {
        c = sha512::hashv(&[&c, &[i as u8]])[..16].try_into().unwrap();
        if i == 0 {
            c = [0; 16];
        }
        if i == 1 {
            c = [0xff; 16];
        }
        let neg = scalar::negate_challenge(&c);
        assert!(scalar::is_canonical(&neg));
        let mut wide = [0u8; 32];
        wide[..16].copy_from_slice(&c);
        assert_eq!(
            Scalar::from_bytes_mod_order(neg),
            -Scalar::from_bytes_mod_order(wide)
        );
    }
}

/// Bytes the TypeScript package must reproduce. `UPDATE_VECTORS=1 cargo test` rewrites the file.
#[test]
fn vectors_json_matches() {
    use std::fmt::Write as _;
    fn hex(bytes: &[u8]) -> std::string::String {
        bytes.iter().map(|b| std::format!("{b:02x}")).collect()
    }
    fn entry(sk: &SecretKey, alpha: &[u8]) -> std::string::String {
        let pi = sk.prove(alpha);
        let beta = pi.verify(&sk.public_key(), alpha).unwrap();
        std::format!(
            r#"    {{ "sk": "{}", "pk": "{}", "alpha": "{}", "pi": "{}", "beta": "{}" }}"#,
            hex(&sk.0),
            hex(&sk.public_key().0),
            hex(alpha),
            hex(&pi.0),
            hex(&beta)
        )
    }
    let rfc: Vec<_> = vectors()
        .map(|(sk, _, alpha, _, _)| entry(&sk, &alpha))
        .collect();
    // Seeds and inputs are derived, so the file is a pure function of the code. Lengths cover
    // an empty input, one and two SHA-512 blocks, and enough samples that some need a retry.
    let mut seed = [0x42u8; 32];
    let mut generated = Vec::new();
    for i in 0..24u32 {
        seed = sha512::hashv(&[&seed])[..32].try_into().unwrap();
        let len = [0usize, 1, 31, 32, 33, 75, 76, 100, 127, 128, 200, 300][i as usize % 12];
        let alpha: Vec<u8> = (0..len).map(|j| (j as u32 * 7 + i) as u8).collect();
        generated.push(entry(&SecretKey(seed), &alpha));
    }
    let mut json = std::string::String::new();
    writeln!(json, "{{\n  \"rfc9381\": [\n{}\n  ],", rfc.join(",\n")).unwrap();
    writeln!(
        json,
        "  \"generated\": [\n{}\n  ]\n}}",
        generated.join(",\n")
    )
    .unwrap();
    let path = std::concat!(std::env!("CARGO_MANIFEST_DIR"), "/tests/vectors.json");
    if std::env::var_os("UPDATE_VECTORS").is_some() {
        std::fs::write(path, &json).unwrap();
    }
    assert_eq!(
        std::fs::read_to_string(path).unwrap_or_default(),
        json,
        "run UPDATE_VECTORS=1 cargo test"
    );
}