Prepare Zexe for recursion

[weikengchen]

Updated. This is a bundle of changes to prepare Zexe for recursion. This PR consists of several independent changes:

1. Add the CycleEngine, which some of us may have heard of. This is to represent a cycle of pairing-friendly curves.

/// A cycle of pairing-friendly elliptic curves.
pub trait CycleEngine:
    Sized
    + 'static
    + Copy
    + Debug
    + Sync
    + Send
where
    <Self::E2 as PairingEngine>::G1Projective: MulAssign<<Self::E1 as PairingEngine>::Fq>,
    <Self::E2 as PairingEngine>::G2Projective: MulAssign<<Self::E1 as PairingEngine>::Fq>,
{
    type E1: PairingEngine;
    type E2: PairingEngine<
        Fr = <Self::E1 as PairingEngine>::Fq,
        Fq = <Self::E1 as PairingEngine>::Fr,
    >;
}

2. Add a prepared verifier inNIZKVerifierGadget and implement it for Groth16 and GM17.

3. Add a new trait ToConstraintFieldGadget and implement it for a number of group and field types.

   pub trait ToConstraintFieldGadget<ConstraintF: PrimeField> {
   fn to_field_gadgets<CS: ConstraintSystem<ConstraintF>>(
       &self,
       cs: CS,
   ) -> Result<Vec<FpGadget<ConstraintF>>, SynthesisError>;
   }

[weikengchen]

The test has passed. Please leave comments.

[Pratyush]

Could you explain why the change to PrimeField is necessary? Couldn't you just bound it downstream by ConstraintF: PrimeField?

Either way, how difficult do you think would it be to split that into a separate PR so that it's easier to see the main logic changes in this PR? If it's too difficult then it's fine to leave it in here

Finally, I'm not entirely convinced by the need for a separate PreparedVerifierGadget; is it not possible to simply add a new function to the existing VerifierGadget? I feel like some logic could be unified that way (because the first thing that VerifierGadget does is call vk.prepare())

[weikengchen]

Very good questions.

---

For the first one, I remember I encountered an issue when the constraint field might not be PrimeField but I forgot. I will try to recollect the information. If it is not needed (i.e., can be avoided by other ways), I will avoid such massive changes.

But anyway, I will separate those changes from this commit, thereby simplifying the matter.

---

For the second one, I can merge it into VerifierGadget.

[weikengchen]

The changes have been made. I updated the PR text above.

[weikengchen]

Just woke up. Will apply the changes soon.

[weikengchen]

Suggestions applied. CI passed.

A new implementation of ToConstraintField for Boolean is made, which gets rid of the one constraint (from conditional_select). https://github.com/scipr-lab/zexe/pull/241/files#diff-fd3cb57c15b5fca1c3c09d44fcbf134dR856

[weikengchen]

I have the feeling that prepared group elements are not going to be used unless when they are hardcoded? (i.e., alloc_constant)

[weikengchen]

repost in case of missing:

I have the feeling that allocating prepared group elements would only be used when they are hardcoded? (i.e., alloc_constant)

[weikengchen]

Since alloc is untrusted, alloc_input for prepared arguments is unnecessarily costly.

[weikengchen]

Thanks for the commit!

[Pratyush]

You could have a commitment to the prepared gadgets (if you have a very efficient hash function)

Either way, I've moved it into todo-s for the time being.

By they way, I've followed your suggestion in the refactor to make AllocGadget have a "main" method which takes in a enum parameter

enum AllocType {
    Const,
    Witness,
    Input,
}

This should make the duplication disappear in the refactor.

[weikengchen]

Great!