1use crate::{Parameters, PublicKey, Signature};
  2
  3use ark_ec::ProjectiveCurve;
  4use ark_ed_on_bn254::{constraints::EdwardsVar, EdwardsParameters, FqParameters};
  5use ark_ff::{fields::Fp256, to_bytes, PrimeField};
  6use ark_r1cs_std::{
  7    alloc::{AllocVar, AllocationMode},
  8    bits::uint8::UInt8,
  9    boolean::Boolean,
 10    eq::EqGadget,
 11    fields::fp::FpVar,
 12    groups::GroupOpsBounds,
 13    prelude::CurveVar,
 14    ToBitsGadget,
 15};
 16use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystemRef, Namespace, SynthesisError};
 17use ark_std::ops::Mul;
 18
 19use core::{borrow::Borrow, marker::PhantomData};
 20use derivative::Derivative;
 21
 22// hash
 23use arkworks_native_gadgets::poseidon as poseidon_native;
 24// use arkworks_r1cs_gadgets::poseidon;
 25use arkworks_r1cs_gadgets::poseidon::{FieldHasherGadget, PoseidonGadget};
 26
 27use crate::ConstraintF;
 28
 29#[derive(Derivative)]
 30#[derivative(
 31    Debug(bound = "C: ProjectiveCurve, GC: CurveVar<C, ConstraintF<C>>"),
 32    Clone(bound = "C: ProjectiveCurve, GC: CurveVar<C, ConstraintF<C>>")
 33)]
 34pub struct PublicKeyVar<C: ProjectiveCurve, GC: CurveVar<C, ConstraintF<C>>>
 35where
 36    for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
 37{
 38    pub_key: GC,
 39    #[doc(hidden)]
 40    _group: PhantomData<*const C>,
 41}
 42
 43impl<C, GC> AllocVar<PublicKey<C>, ConstraintF<C>> for PublicKeyVar<C, GC>
 44where
 45    C: ProjectiveCurve,
 46    GC: CurveVar<C, ConstraintF<C>>,
 47    for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
 48{
 49    fn new_variable<T: Borrow<PublicKey<C>>>(
 50        cs: impl Into<Namespace<ConstraintF<C>>>,
 51        f: impl FnOnce() -> Result<T, SynthesisError>,
 52        mode: AllocationMode,
 53    ) -> Result<Self, SynthesisError> {
 54        let pub_key = GC::new_variable(cs, f, mode)?;
 55        Ok(Self {
 56            pub_key,
 57            _group: PhantomData,
 58        })
 59    }
 60}
 61
 62#[derive(Derivative)]
 63#[derivative(
 64    Debug(bound = "C: ProjectiveCurve, GC: CurveVar<C, ConstraintF<C>>"),
 65    Clone(bound = "C: ProjectiveCurve, GC: CurveVar<C, ConstraintF<C>>")
 66)]
 67pub struct SignatureVar<C: ProjectiveCurve, GC: CurveVar<C, ConstraintF<C>>>
 68where
 69    for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
 70{
 71    s: Vec<UInt8<ConstraintF<C>>>,
 72    r: GC,
 73    _curve: PhantomData<C>,
 74}
 75
 76impl<C, GC> AllocVar<Signature<C>, ConstraintF<C>> for SignatureVar<C, GC>
 77where
 78    C: ProjectiveCurve,
 79    GC: CurveVar<C, ConstraintF<C>>,
 80    for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
 81{
 82    fn new_variable<T: Borrow<Signature<C>>>(
 83        cs: impl Into<Namespace<ConstraintF<C>>>,
 84        f: impl FnOnce() -> Result<T, SynthesisError>,
 85        mode: AllocationMode,
 86    ) -> Result<Self, SynthesisError> {
 87        f().and_then(|val| {
 88            let cs = cs.into();
 89            // let s = val.borrow().s;
 90            let mut s = Vec::<UInt8<ConstraintF<C>>>::new();
 91            let s_bytes = to_bytes![val.borrow().s].unwrap();
 92            #[allow(clippy::needless_range_loop)]
 93            for i in 0..s_bytes.len() {
 94                s.push(UInt8::<ConstraintF<C>>::new_variable(
 95                    cs.clone(),
 96                    || Ok(s_bytes[i]),
 97                    mode,
 98                )?);
 99            }
100
101            let r = GC::new_variable(cs, || Ok(val.borrow().r), mode)?;
102
103            Ok(Self {
104                s,
105                r,
106                _curve: PhantomData,
107            })
108        })
109    }
110}
111
112#[derive(Clone)]
113pub struct ParametersVar<C: ProjectiveCurve, GC: CurveVar<C, ConstraintF<C>>>
114where
115    for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
116{
117    generator: GC,
118    _curve: PhantomData<C>,
119}
120
121impl<C, GC> AllocVar<Parameters<C>, ConstraintF<C>> for ParametersVar<C, GC>
122where
123    C: ProjectiveCurve,
124    GC: CurveVar<C, ConstraintF<C>>,
125    for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
126{
127    fn new_variable<T: Borrow<Parameters<C>>>(
128        cs: impl Into<Namespace<ConstraintF<C>>>,
129        f: impl FnOnce() -> Result<T, SynthesisError>,
130        mode: AllocationMode,
131    ) -> Result<Self, SynthesisError> {
132        f().and_then(|val| {
133            let cs = cs.into();
134            let generator = GC::new_variable(cs, || Ok(val.borrow().generator), mode)?;
135            Ok(Self {
136                generator,
137                _curve: PhantomData,
138            })
139        })
140    }
141}
142
143pub struct BlindSigVerifyGadget<C: ProjectiveCurve, GC: CurveVar<C, ConstraintF<C>>>
144where
145    for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
146{
147    _params: Parameters<C>, // TODO review if needed, maybe delete
148    _gc: PhantomData<GC>,
149}
150
151impl<C: ProjectiveCurve, GC: CurveVar<C, ConstraintF<C>>> BlindSigVerifyGadget<C, GC>
152where
153    C: ProjectiveCurve,
154    GC: CurveVar<C, ConstraintF<C>>,
155    for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
156    ark_r1cs_std::groups::curves::twisted_edwards::AffineVar<
157        EdwardsParameters,
158        FpVar<Fp256<FqParameters>>,
159    >: From<GC>,
160    <C as ProjectiveCurve>::BaseField: PrimeField,
161    FpVar<<C as ProjectiveCurve>::BaseField>: Mul<FpVar<Fp256<FqParameters>>>,
162    FpVar<<C as ProjectiveCurve>::BaseField>: From<FpVar<Fp256<FqParameters>>>,
163{
164    fn verify(
165        parameters: &ParametersVar<C, GC>,
166        poseidon_hash: &PoseidonGadget<ConstraintF<C>>,
167        m: FpVar<ConstraintF<C>>,
168        s: &SignatureVar<C, GC>,
169        q: &PublicKeyVar<C, GC>,
170    ) -> Result<Boolean<ConstraintF<C>>, SynthesisError> {
171        let sG = parameters
172            .generator
173            .scalar_mul_le(s.s.to_bits_le()?.iter())?;
174
175        // Note: in a circuit that aggregates multiple verifications, the hashing step could be
176        // done outside the signature verification, once for all 1 votes and once for all 0 votes,
177        // saving lots of constraints
178        let hm = poseidon_hash.hash(&[m])?;
179        let r = EdwardsVar::from(s.r.clone()); // WIP
180        let rx_fpvar: FpVar<ConstraintF<C>> = r.x.into();
181
182        // G * s == R + Q * (R.x * H(m))
183        let Q_rx_hm_0 = q.pub_key.scalar_mul_le(rx_fpvar.to_bits_le()?.iter())?;
184        let Q_rx_hm = Q_rx_hm_0.scalar_mul_le(hm.to_bits_le()?.iter())?;
185        let RHS = s.r.clone() + Q_rx_hm;
186
187        sG.is_eq(&RHS)
188    }
189}
190
191pub struct BlindSigBatchVerifyGadget<
192    C: ProjectiveCurve,
193    GC: CurveVar<C, ConstraintF<C>>,
194    const NUM_SIGS: usize,
195> where
196    for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
197{
198    _params: Parameters<C>, // TODO review if needed, maybe delete
199    _gc: PhantomData<GC>,
200}
201
202impl<C: ProjectiveCurve, GC: CurveVar<C, ConstraintF<C>>, const NUM_SIGS: usize>
203    BlindSigBatchVerifyGadget<C, GC, NUM_SIGS>
204where
205    C: ProjectiveCurve,
206    GC: CurveVar<C, ConstraintF<C>>,
207    for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
208    ark_r1cs_std::groups::curves::twisted_edwards::AffineVar<
209        EdwardsParameters,
210        FpVar<Fp256<FqParameters>>,
211    >: From<GC>,
212    <C as ProjectiveCurve>::BaseField: PrimeField,
213    FpVar<<C as ProjectiveCurve>::BaseField>: Mul<FpVar<Fp256<FqParameters>>>,
214    FpVar<<C as ProjectiveCurve>::BaseField>: From<FpVar<Fp256<FqParameters>>>,
215{
216    fn batch_verify(
217        parameters: &ParametersVar<C, GC>,
218        poseidon_hash: &PoseidonGadget<ConstraintF<C>>,
219        m: FpVar<ConstraintF<C>>,
220        sigs: &[SignatureVar<C, GC>],
221        q: &PublicKeyVar<C, GC>,
222    ) -> Result<Boolean<ConstraintF<C>>, SynthesisError> {
223        // Note: in a circuit that aggregates multiple verifications, the hashing step could be
224        // done outside the signature verification, once for all 1 votes and once for all 0 votes,
225        // saving lots of constraints
226        let hm = poseidon_hash.hash(&[m])?;
227
228        #[allow(clippy::needless_range_loop)]
229        for i in 0..NUM_SIGS {
230            let sG = parameters
231                .generator
232                .scalar_mul_le(sigs[i].s.to_bits_le()?.iter())?;
233
234            let r = EdwardsVar::from(sigs[i].r.clone()); // WIP
235            let rx_fpvar: FpVar<ConstraintF<C>> = r.x.into();
236
237            // G * s == R + Q * (R.x * H(m))
238            let Q_rx_hm_0 = q.pub_key.scalar_mul_le(rx_fpvar.to_bits_le()?.iter())?;
239            let Q_rx_hm = Q_rx_hm_0.scalar_mul_le(hm.to_bits_le()?.iter())?;
240            let RHS = sigs[i].r.clone() + Q_rx_hm;
241            sG.enforce_equal(&RHS)?;
242        }
243        Ok(Boolean::TRUE)
244    }
245}
246
247// example of circuit using BlindSigVerifyGadget to verify a single blind signature
248#[derive(Clone)]
249pub struct BlindSigVerifyCircuit<C: ProjectiveCurve, GC: CurveVar<C, ConstraintF<C>>>
250where
251    <C as ProjectiveCurve>::BaseField: PrimeField,
252{
253    _group: PhantomData<*const GC>,
254    pub params: Parameters<C>,
255    pub poseidon_hash_native: poseidon_native::Poseidon<ConstraintF<C>>,
256    pub signature: Option<Signature<C>>,
257    pub pub_key: Option<PublicKey<C>>,
258    pub message: Option<ConstraintF<C>>,
259}
260
261impl<C: ProjectiveCurve, GC: CurveVar<C, ConstraintF<C>>> ConstraintSynthesizer<ConstraintF<C>>
262    for BlindSigVerifyCircuit<C, GC>
263where
264    C: ProjectiveCurve,
265    GC: CurveVar<C, ConstraintF<C>>,
266    for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
267    ark_r1cs_std::groups::curves::twisted_edwards::AffineVar<
268        EdwardsParameters,
269        FpVar<Fp256<FqParameters>>,
270    >: From<GC>,
271    <C as ProjectiveCurve>::BaseField: PrimeField,
272    FpVar<<C as ProjectiveCurve>::BaseField>: Mul<FpVar<Fp256<FqParameters>>>,
273    FpVar<<C as ProjectiveCurve>::BaseField>: From<FpVar<Fp256<FqParameters>>>,
274{
275    #[tracing::instrument(target = "r1cs", skip(self, cs))]
276    fn generate_constraints(
277        self,
278        cs: ConstraintSystemRef<ConstraintF<C>>,
279    ) -> Result<(), SynthesisError> {
280        let parameters =
281            ParametersVar::new_constant(ark_relations::ns!(cs, "parameters"), &self.params)?;
282
283        let pub_key =
284            PublicKeyVar::<C, GC>::new_input(ark_relations::ns!(cs, "public key"), || {
285                self.pub_key.ok_or(SynthesisError::AssignmentMissing)
286            })?;
287        let m = FpVar::<ConstraintF<C>>::new_input(ark_relations::ns!(cs, "message"), || {
288            self.message.ok_or(SynthesisError::AssignmentMissing)
289        })?;
290        let signature =
291            SignatureVar::<C, GC>::new_witness(ark_relations::ns!(cs, "signature"), || {
292                self.signature.ok_or(SynthesisError::AssignmentMissing)
293            })?;
294        #[allow(clippy::redundant_clone)]
295        let poseidon_hash = PoseidonGadget::<ConstraintF<C>>::from_native(
296            &mut cs.clone(),
297            self.poseidon_hash_native,
298        )
299        .unwrap();
300
301        let v = BlindSigVerifyGadget::<C, GC>::verify(
302            &parameters,
303            &poseidon_hash,
304            m,
305            &signature,
306            &pub_key,
307        )?;
308        v.enforce_equal(&Boolean::TRUE)
309    }
310}
311
312// example of circuit using BlindSigVerifyGadget to verify a batch of blind signatures
313#[derive(Clone)]
314pub struct BlindSigBatchVerifyCircuit<
315    C: ProjectiveCurve,
316    GC: CurveVar<C, ConstraintF<C>>,
317    const NUM_SIGS: usize,
318> where
319    <C as ProjectiveCurve>::BaseField: PrimeField,
320{
321    _group: PhantomData<*const GC>,
322    pub params: Parameters<C>,
323    pub poseidon_hash_native: poseidon_native::Poseidon<ConstraintF<C>>,
324    pub signatures: Option<Vec<Signature<C>>>,
325    pub pub_key: Option<PublicKey<C>>,
326    pub message: Option<ConstraintF<C>>,
327}
328
329impl<C: ProjectiveCurve, GC: CurveVar<C, ConstraintF<C>>, const NUM_SIGS: usize>
330    ConstraintSynthesizer<ConstraintF<C>> for BlindSigBatchVerifyCircuit<C, GC, NUM_SIGS>
331where
332    C: ProjectiveCurve,
333    GC: CurveVar<C, ConstraintF<C>>,
334    for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
335    ark_r1cs_std::groups::curves::twisted_edwards::AffineVar<
336        EdwardsParameters,
337        FpVar<Fp256<FqParameters>>,
338    >: From<GC>,
339    <C as ProjectiveCurve>::BaseField: PrimeField,
340    FpVar<<C as ProjectiveCurve>::BaseField>: Mul<FpVar<Fp256<FqParameters>>>,
341    FpVar<<C as ProjectiveCurve>::BaseField>: From<FpVar<Fp256<FqParameters>>>,
342{
343    #[tracing::instrument(target = "r1cs", skip(self, cs))]
344    fn generate_constraints(
345        self,
346        cs: ConstraintSystemRef<ConstraintF<C>>,
347    ) -> Result<(), SynthesisError> {
348        let parameters =
349            ParametersVar::new_constant(ark_relations::ns!(cs, "parameters"), &self.params)?;
350
351        let pub_key =
352            PublicKeyVar::<C, GC>::new_input(ark_relations::ns!(cs, "public key"), || {
353                self.pub_key.ok_or(SynthesisError::AssignmentMissing)
354            })?;
355        let m = FpVar::<ConstraintF<C>>::new_input(ark_relations::ns!(cs, "message"), || {
356            self.message.ok_or(SynthesisError::AssignmentMissing)
357        })?;
358
359        let mut signatures: Vec<SignatureVar<C, GC>> = Vec::new();
360        for i in 0..NUM_SIGS {
361            let signature = self.signatures.as_ref().and_then(|s| s.get(i));
362
363            let signature =
364                SignatureVar::<C, GC>::new_witness(ark_relations::ns!(cs, "signature"), || {
365                    signature.ok_or(SynthesisError::AssignmentMissing)
366                })?;
367            signatures.push(signature);
368        }
369
370        #[allow(clippy::redundant_clone)]
371        let poseidon_hash = PoseidonGadget::<ConstraintF<C>>::from_native(
372            &mut cs.clone(),
373            self.poseidon_hash_native,
374        )
375        .unwrap();
376
377        let v = BlindSigBatchVerifyGadget::<C, GC, NUM_SIGS>::batch_verify(
378            &parameters,
379            &poseidon_hash,
380            m,
381            &signatures,
382            &pub_key,
383        )?;
384        v.enforce_equal(&Boolean::TRUE)
385    }
386}
387
388#[cfg(test)]
389mod test {
390    use super::*;
391    use crate::{poseidon_setup_params, BlindSigScheme};
392    use ark_ed_on_bn254::constraints::EdwardsVar as BabyJubJubVar;
393    use ark_ed_on_bn254::EdwardsProjective as BabyJubJub;
394
395    use arkworks_native_gadgets::poseidon;
396    use arkworks_utils::Curve;
397
398    use ark_relations::r1cs::ConstraintSystem;
399
400    type Fq = <BabyJubJub as ProjectiveCurve>::BaseField;
401    // type Fr = <BabyJubJub as ProjectiveCurve>::ScalarField;
402    type S = BlindSigScheme<BabyJubJub>;
403
404    fn generate_single_sig_native_data(
405        poseidon_hash: &poseidon::Poseidon<Fq>,
406    ) -> (
407        Parameters<BabyJubJub>,
408        PublicKey<BabyJubJub>,
409        Fq,
410        Signature<BabyJubJub>,
411    ) {
412        let mut rng = ark_std::test_rng();
413        let params = S::setup();
414        let (pk, sk) = S::keygen(&params, &mut rng);
415        let (k, signer_r) = S::new_request_params(&params, &mut rng);
416        let m = Fq::from(1234);
417        let (m_blinded, u) = S::blind(&params, &mut rng, &poseidon_hash, m, signer_r).unwrap();
418        let s_blinded = S::blind_sign(sk, k, m_blinded);
419        let s = S::unblind(s_blinded, u);
420        let verified = S::verify(&params, &poseidon_hash, m, s.clone(), pk);
421        assert!(verified);
422        (params, pk, m, s)
423    }
424
425    fn generate_batch_sig_native_data(
426        poseidon_hash: &poseidon::Poseidon<Fq>,
427        n: usize,
428    ) -> (
429        Parameters<BabyJubJub>,
430        PublicKey<BabyJubJub>,
431        Fq,
432        Vec<Signature<BabyJubJub>>,
433    ) {
434        let mut rng = ark_std::test_rng();
435        let params = S::setup();
436        let (pk, sk) = S::keygen(&params, &mut rng);
437        let m = Fq::from(1234);
438        let mut signatures: Vec<Signature<BabyJubJub>> = Vec::new();
439        for _ in 0..n {
440            let (k, signer_r) = S::new_request_params(&params, &mut rng);
441            let (m_blinded, u) = S::blind(&params, &mut rng, &poseidon_hash, m, signer_r).unwrap();
442            let s_blinded = S::blind_sign(sk, k, m_blinded);
443            let s = S::unblind(s_blinded, u);
444            let verified = S::verify(&params, &poseidon_hash, m, s.clone(), pk);
445            assert!(verified);
446            signatures.push(s);
447        }
448        (params, pk, m, signatures)
449    }
450
451    #[test]
452    fn test_single_verify() {
453        let poseidon_params = poseidon_setup_params::<Fq>(Curve::Bn254, 5, 3);
454        let poseidon_hash = poseidon::Poseidon::new(poseidon_params);
455
456        // create signature using native-rust lib
457        let (params, pk, m, s) = generate_single_sig_native_data(&poseidon_hash);
458
459        // use the constraint system to verify the signature
460        type SG = BlindSigVerifyGadget<BabyJubJub, BabyJubJubVar>;
461        let cs = ConstraintSystem::<Fq>::new_ref();
462
463        let params_var =
464            ParametersVar::<BabyJubJub, BabyJubJubVar>::new_constant(cs.clone(), params).unwrap();
465        let signature_var =
466            SignatureVar::<BabyJubJub, BabyJubJubVar>::new_witness(cs.clone(), || Ok(&s)).unwrap();
467        let pk_var =
468            PublicKeyVar::<BabyJubJub, BabyJubJubVar>::new_witness(cs.clone(), || Ok(&pk)).unwrap();
469        let m_var = FpVar::<Fq>::new_witness(cs.clone(), || Ok(&m)).unwrap();
470        let poseidon_hash_var =
471            PoseidonGadget::<Fq>::from_native(&mut cs.clone(), poseidon_hash).unwrap();
472
473        let valid_sig = SG::verify(
474            &params_var,
475            &poseidon_hash_var,
476            m_var,
477            &signature_var,
478            &pk_var,
479        )
480        .unwrap();
481        valid_sig.enforce_equal(&Boolean::<Fq>::TRUE).unwrap();
482        assert!(cs.is_satisfied().unwrap());
483    }
484
485    #[test]
486    fn test_single_verify_constraint_system() {
487        let poseidon_params = poseidon_setup_params::<Fq>(Curve::Bn254, 5, 3);
488        let poseidon_hash = poseidon::Poseidon::new(poseidon_params);
489
490        // create signature using native-rust lib
491        let (params, pk, m, s) = generate_single_sig_native_data(&poseidon_hash);
492
493        // use the constraint system to verify the signature
494        let circuit = BlindSigVerifyCircuit::<BabyJubJub, BabyJubJubVar> {
495            params,
496            poseidon_hash_native: poseidon_hash,
497            signature: Some(s),
498            pub_key: Some(pk),
499            message: Some(m),
500            _group: PhantomData,
501        };
502        let cs = ConstraintSystem::<Fq>::new_ref();
503        circuit.generate_constraints(cs.clone()).unwrap();
504        let is_satisfied = cs.is_satisfied().unwrap();
505        assert!(is_satisfied);
506        println!("num_cnstraints={:?}", cs.num_constraints());
507    }
508
509    #[test]
510    fn test_batch_verify_constraint_system() {
511        let poseidon_params = poseidon_setup_params::<Fq>(Curve::Bn254, 5, 3);
512        let poseidon_hash = poseidon::Poseidon::new(poseidon_params);
513
514        // create signatures using native-rust lib
515        const NUM_SIGS: usize = 5;
516        let (params, pk, m, sigs) = generate_batch_sig_native_data(&poseidon_hash, NUM_SIGS);
517
518        // use the constraint system to verify the batch of signatures
519        let circuit = BlindSigBatchVerifyCircuit::<BabyJubJub, BabyJubJubVar, NUM_SIGS> {
520            params,
521            poseidon_hash_native: poseidon_hash,
522            signatures: Some(sigs),
523            pub_key: Some(pk),
524            message: Some(m),
525            _group: PhantomData,
526        };
527        let cs = ConstraintSystem::<Fq>::new_ref();
528        circuit.generate_constraints(cs.clone()).unwrap();
529        let is_satisfied = cs.is_satisfied().unwrap();
530        assert!(is_satisfied);
531        println!("num_cnstraints={:?}", cs.num_constraints());
532    }
533}