1/// This file implements the EdDSA verification in-circuit.
 2use ark_crypto_primitives::sponge::{
 3    constraints::CryptographicSpongeVar,
 4    poseidon::{constraints::PoseidonSpongeVar, PoseidonConfig},
 5};
 6use ark_ec::CurveGroup;
 7use ark_ff::Field;
 8use ark_r1cs_std::{
 9    boolean::Boolean, fields::fp::FpVar, fields::nonnative::NonNativeFieldVar, groups::CurveVar,
10    ToBitsGadget, ToConstraintFieldGadget,
11};
12use ark_relations::r1cs::ConstraintSystemRef;
13
14/// CF stands for ConstraintField
15pub type CF<C> = <<C as CurveGroup>::BaseField as Field>::BasePrimeField;
16
17/// gadget to compute the EdDSA verification in-circuit
18pub fn verify<C, GC>(
19    cs: ConstraintSystemRef<CF<C>>,
20    poseidon_config: PoseidonConfig<CF<C>>,
21    pk: GC,
22    sig: (GC, NonNativeFieldVar<C::ScalarField, CF<C>>),
23    msg: FpVar<CF<C>>,
24) -> ark_relations::r1cs::Result<Boolean<CF<C>>>
25where
26    C: CurveGroup,
27    GC: CurveVar<C, CF<C>> + ToConstraintFieldGadget<CF<C>>,
28{
29    let (r, s): (GC, NonNativeFieldVar<C::ScalarField, CF<C>>) = sig;
30
31    let r_xy = r.to_constraint_field()?;
32    let pk_xy = pk.to_constraint_field()?;
33
34    let mut poseidon = PoseidonSpongeVar::new(cs.clone(), &poseidon_config);
35    poseidon.absorb(&r_xy)?;
36    poseidon.absorb(&pk_xy)?;
37    poseidon.absorb(&msg)?;
38    let k = poseidon.squeeze_field_elements(1)?;
39    let k = k
40        .first()
41        .ok_or(ark_relations::r1cs::SynthesisError::Unsatisfiable)?;
42
43    let kx_b = pk.scalar_mul_le(k.to_bits_le()?.iter())?;
44
45    let g = GC::new_constant(cs.clone(), C::generator())?;
46    let s_b = g.scalar_mul_le(s.to_bits_le()?.iter())?;
47    let r_rec: GC = s_b - kx_b;
48    Ok(r_rec.is_eq(&r)?)
49}
50
51#[cfg(test)]
52mod tests {
53    use ark_ff::PrimeField;
54    use ark_r1cs_std::{alloc::AllocVar, eq::EqGadget, fields::nonnative::NonNativeFieldVar};
55    use ark_relations::r1cs::ConstraintSystem;
56    use rand_core::OsRng;
57
58    use super::*;
59    use crate::ed_on_bn254_twist::{
60        constraints::EdwardsVar as GVar, BaseField as Fq, EdwardsConfig, EdwardsProjective as G,
61        ScalarField as Fr,
62    };
63    use crate::{poseidon_config, SigningKey};
64
65    #[test]
66    fn gadget_verify() {
67        let poseidon_config = poseidon_config::<Fq>(4, 8, 60);
68        let sk = SigningKey::<EdwardsConfig>::generate::<blake2::Blake2b512>(&mut OsRng).unwrap();
69        let msg_raw = b"xxx yyy <<< zzz >>> bunny";
70        let msg = Fq::from_le_bytes_mod_order(msg_raw);
71        let sig = sk
72            .sign::<blake2::Blake2b512>(&poseidon_config, &msg)
73            .unwrap();
74        let pk = sk.public_key();
75        pk.verify(&poseidon_config, &msg, &sig).unwrap();
76
77        let cs = ConstraintSystem::<Fq>::new_ref();
78        let pk_var: GVar = GVar::new_witness(cs.clone(), || Ok(*pk.as_ref())).unwrap();
79        let r_var: GVar = GVar::new_witness(cs.clone(), || Ok(*sig.r())).unwrap();
80        let s_var = NonNativeFieldVar::<Fr, Fq>::new_witness(cs.clone(), || Ok(sig.s())).unwrap();
81        let msg_var = FpVar::<Fq>::new_witness(cs.clone(), || Ok(msg)).unwrap();
82
83        let res = verify::<G, GVar>(cs.clone(), poseidon_config, pk_var, (r_var, s_var), msg_var)
84            .unwrap();
85        res.enforce_equal(&Boolean::<Fq>::TRUE).unwrap();
86
87        dbg!(cs.num_constraints());
88        assert!(cs.is_satisfied().unwrap());
89    }
90}