RFC: The SnarkyType trait and derive macros

[mimoo]

We want people to be able to create their own types on top of the main type FieldVar.

We have a trait SnarkyType for that, and we're also working on a derive macro as well (e.g. #[derive(SnarkyType)]).

Because FieldVar is generic in its field (FieldVar<F: PrimeField>), SnarkyType also has to track that field.

We could use an associated type (e.g. trait SnarkyType { type F: PrimeField; /* ... */ }) but we instead chose to add a type parameter on the trait (i.e. trait SnarkyType<F>).

Problem

This means that types implemented by people will be generic, and might not take into account edge cases depending on the field.

For example, one of the Pasta field is larger than the other one, and as such a type containing a field element from the other curve can be represented in 1 or 2 elements depending on the curve you're on.

Furthermore, the check function that constrains a snarkytype to be valid might be different depending on the field you're on.

Discussion on solutions

For the reasons stated above, we might not want to have SnarkyType be generic over a field. And so, moving the field type to an associated type could be a better design.

This solution leads to more questions though:

what about general types that don't care?. For example, the boolean type should work the same on any curve, and so it should be the same for both fields.

We might want to simply have it generic at first:

pub struct BooleanVar<F>

but have two implementations:

impl SnarkyType for BooleanVar<Fp> { type Field = Fp; /* ... */ }
impl SnarkyType for BooleanVar<Fq> { type Field = Fq; /* ... */ }

but this mean having redundant code. One solution could be to have macros to easily derive the two implementations.

what about the derive macro? What does it mean for the derive macro if we use an associated type? I think we could specialize it like this: #[derive(SnarkyType(Fp))]. And if we don't specify Fp or Fq perhaps we could derive both implementations automatically.

In general though, I would imagine that a type that needs to be different on one curve or the other would need to have its own SnarkyType implementations anyway. So I suggest that we don't expose specialization of the field in the derive macro, and just always derive the two fields implementations automatically.

what about other fields? At the moment we only support the Pasta Fp and Fq fields. But what if we wanted to support more fields down the line? The generic approach allows us not to corner ourselves into a specific field (or set of fields) which is nice...

So perhaps, the associated type is not a good solution. Rather, in the case where a type really needs a SnarkyType implementation specific to a field, we could simply implement it for that specific field (instead of a general SnarkyType implementation):

impl SnarkyType<Fp> for YourType { /* ... */ }

---

The solution is thus to keep SnarkyType generic over a field (i.e. SnarkyType<F: PrimeField>).

Note: a SnarkyCircuit already fixes and forces a user into a curve/field:

pub trait SnarkyCircuit: Sized {
    type Curve: KimchiCurve;

A useful derive macro

In general, we want two derive macro: one for types that are just dumb containers, and one for types that aren't just dumb containers.

Dumb containers

The first one just cares about creating a SnarkyType that is a tuple of all its SnarkyType fields.

For example, you can see this implementation on a tuple of two SnarkyTypes:

impl<F, T1, T2> SnarkyType<F> for (T1, T2)
where
    F: PrimeField,
    T1: SnarkyType<F>,
    T2: SnarkyType<F>,
{
    type Auxiliary = (T1::Auxiliary, T2::Auxiliary);

    type OutOfCircuit = (T1::OutOfCircuit, T2::OutOfCircuit);

    const SIZE_IN_FIELD_ELEMENTS: usize = T1::SIZE_IN_FIELD_ELEMENTS + T2::SIZE_IN_FIELD_ELEMENTS;

    fn to_cvars(&self) -> (Vec<FieldVar<F>>, Self::Auxiliary) {
        let (mut cvars1, aux1) = self.0.to_cvars();
        let (cvars2, aux2) = self.1.to_cvars();
        cvars1.extend(cvars2);
        (cvars1, (aux1, aux2))
    }
    
    // and so on...

in this case, the derive macro #[derive(SnarkyType)] can simply do the following:

• ensure that our type is generic over an F: PrimeField (because we need to reuse that F in our impl<F> SnarkyType<F>)
• add bounds on all the field types, to make sure that they implement SnarkyType as well
• generate code for an implementation of SnarkyType that follows the pattern above

Not dumb containers

The second type is usually different in two ways:

• it has a specific check function
• it has a specific auxiliary type and function
• it might have fields that are not implementing SnarkyType
• it might have an out-of-circuit type that's more than just a tuple of its field types

One way is to implement it using a derive macro that specifies the implementations, as well as specific attributes to skip some fields:

#[derive(SnarkyType))]
#[snarky(check = "my_check_impl")]
#[snarky(auxiliary_fn = "aux_fn", auxiliary_type = "MyAuxType")]
#[snarky(value = "OutOfCircuitType")]
struct MyStruct<F: PrimeField> {
    some_field: SomeSnarkyType,
    #[snarky(skip)]
    some_other_field: NotASnarkyType,
}

I don't think there's really another way to do it, as we need access to the structure in order to understand how to implement the different functions.

For handling the out-of-circuit value, we could require a trait to be implement if #[snarky(value = _)] is passed:

pub trait CircuitAndValue<F>: SnarkyType<F>
where
    F: PrimeField,
{
    fn to_value(fields: Vec<F>, aux: Self::Auxiliary) -> Self::OutOfCircuit;
    fn from_value(value: &Self::OutOfCircuit) -> (Vec<F>, Self::Auxiliary);
}

Specific fields

I think we can even go further to address the previously discussed constraint of types that only work for a specific field. For example:

#[derive(SnarkyType)]
#[snarky(field=Fp)]
struct MyStruct<Vesta> {
    // ...

Implementation

The derive macro was implemented here: https://github.com/o1-labs/proof-systems/blob/mimoo/snarky2/kimchi/snarky-deriver/src/lib.rs