Fields are Groups

[mmaker]

A lot of cryptographic schemes (some IBEs, ABEs, hash proof systems,  and sumcheck arguments [BCS]) use the abstraction of "modules". Arkworks currently has a nice abstraction, Group, that essentially implements the operations that we would expect from a module: this is already satisfied in pairing-friendly curves by G1, G2, and PairingOutput.

It'd be really nice if also field implemented this abstraction, so to make possible the realizations of such schemes without having wrappers around the structures. To avoid confusion and lock-out of features of the multiplicative group, perhaps consider renaming Group into AdditiveGroup?. Here's a possible sketch of the steps to achieve this:

• state clearly in the documentation that Groups are additive
• make all Field a Group: this can be first perhaps done in ark-ec with a blanket implementation, to avoid moving code around (hoping this does not break anything)
• move the Group definition into ark-ff for the small operations, and re-assing group-specific methods
• rename Group into AdditiveGroup?

[Pratyush]

We can move Group to ark-ff without breaking changes, as long as we publicly re-export it from ark-ec anyway. I suggest that we go all the way and just directly make an ark-group crate that is imported by both ark-ff and ark-ec.

[mmaker]

@Pratyush @mmagician what do you think of the above?

1. I created AdditiveGroup in ark_ff which encapsulates all group operations.
2. Made Field: AdditiveGroup
3. Renamed ark_ec::Group into ark_ec::PrimeGroup
4. Made PrimeGroup: AdditiveGroup

One example where this is useful is this generic sumcheck argument; https://github.com/arkworks-rs/gemini/blob/main/src/herring/
That can avoid all this useless code: https://github.com/arkworks-rs/gemini/blob/main/src/herring/module.rs

[mmagician]

I'll look at the actual code later, the idea seems reasonable though 👍🏼

[Pratyush]

What's the difference between PrimeGroup and AdditiveGroup?

EDIT: That is, do we ever instantiate AdditiveGroups that are not of prime order?

[mmaker]

Hey, thanks for taking a look! Yes, all field extensions are not of prime order, so making them PrimeGroup wouldn't be possible. The main difference between AdditiveGroup and PrimeGroup is that ScalarField: Field in the former and ScalarField: PrimeField in the latter. Plus, there's all these methods dealing with bit- and byte-representation that are not really fit for non-cyclic groups of composite order

[mmaker]

removed some code not useful at this stage (implementation of PrimeGroup for PrimeField)

[Pratyush]

That's a good point, makes sense. In that case it might make sense to remove ScalarField from AdditiveGroup, as we might have groups with composite order that is not a prime-power. For example, elliptic curve groups.

[mmaker]

mmh ScalarField is needed for any abstract operation you do on them, and we do not have the notion of a Ring.. should I call it FieldModule, VectorSpace or something else?
Plus, all constructions that i know of need a field structure, like sumcheck arguments, hash proof systems, or ABE.

[Pratyush]

Why do you need a scalar field for operations? Group operations only require Add, Sub, Neg, Zero, One, etc, no?

Do sumcheck arguments require composite-order groups?

[mmaker]

yes we need scalar field operations -- and sumcheck arguments require modules (over rings, not necessarily over fields). See e.g. def. 4.1.

[mmaker]

bump! @Pratyush @mmagician

[Pratyush]

Hm my main worry is just that we don't have a way to define a Scalar*Field* for composite order groups. We would need to introduce a Ring abstraction (which I am fine with). However that would make the scope of this PR larger (which I am also fine with)