Introduce Absorb/Challenge traits

[rot256]

Currently the Sponge type looks like this:

impl<P: SWModelParameters, SC: SpongeConstants>
    FqSponge<P::BaseField, GroupAffine<P>, P::ScalarField> for DefaultFqSponge<P, SC>
where
    P::BaseField: PrimeField,
    <P::BaseField as PrimeField>::BigInt: Into<<P::ScalarField as PrimeField>::BigInt>,
{
    fn new(params: ArithmeticSpongeParams<P::BaseField>) -> DefaultFqSponge<P, SC> {
        ...
    }

    fn absorb_g(&mut self, g: &[GroupAffine<P>]) {
        ...
    }

    fn absorb_fr(&mut self, x: &[P::ScalarField]) {
        ...
    }

    fn digest(mut self) -> P::ScalarField {
        ...
    }

    fn challenge(&mut self) -> P::ScalarField {
        ...
    }

    fn challenge_fq(&mut self) -> P::BaseField {
        ...
    }
}

Meaning there is a method for every type you can absorb and every type you can squeeze. I suggest getting rid of this in favor of using two traits: one for "absorbable" objects and one for "squeezable" objects.

Concretely I suggest adding traits like these:

pub trait Challenge<F: FftField + PrimeField> {
    fn generate(sponge: &mut Sponge<F>) -> Self;
}

pub trait Absorb<F: FftField + PrimeField> {
    fn absorb(&self, sponge: &mut Sponge<F>);
}

And changing the sponge type so it looks more like this:

impl<F: FftField + PrimeField> Sponge<F> {
    pub fn new(constants: Constants<F>) -> Self {
        ...
    }

    // absorb an instance of T using the sponge
    pub fn absorb<T: Absorb<F>>(&mut self, val: &T) {
        val.absorb(cs, self);
    }
    
    // sample an instance of T using the sponge
    pub fn challenge<T: Challenge<F>>(&mut self) ->  T {
        T::generate(self);
    }
}

In addition we provide a few special implementations of Challenge<F> and Absorb<F>:

// can absorb a element from the same field
impl<F: FftField + PrimeField> Absorb<F> for F {
    fn absorb(&self, sponge: &mut Sponge<F>) {
        ...
    }
}

// can generate a variable from the same field (a digest)
impl<F: FftField + PrimeField> Challenge<F> for F {
    fn generate(sponge: &mut Sponge<F>) -> Self {
        ...
    }
}

This enables describing/deriving absorbing/squeezing of more complex types elsewhere in terms of these "base" implementation, e.g.

// can absorb a slice of absorbable elements
impl<F: FftField + PrimeField, T: Absorb<F>> Absorb<F> for [T] {
    fn absorb(&self,  sponge: &mut Sponge<F>) {
        self.iter().for_each(|c| c.absorb(sponge))
    }
}

// define a curve point type
pub struct Point<G>
where
    G: AffineCurve,
    G::BaseField: FftField + PrimeField,
{
    _ph: PhantomData<G>,
    x: G::BaseField,
    y: G::BaseField,
}

// can absorb curve points using a base field sponge
impl<G> Absorb<G::BaseField> for Point<G>
where
    G: AffineCurve,
    G::BaseField: FftField + PrimeField,
{
    fn absorb(&self, sponge: &mut Sponge<G::BaseField>) {
        sponge.absorb(&self.x);
        sponge.absorb(&self.y);
    }
}

Without changing the Sponge type/trait, this also enables implementing the traits for new types outside the module. In particular the above allows:

sponge.absorb(&points);

For a sequence of points (exactly like sponge.absorb_g currently), but also enables sponge.absorb(&field_elements) without changing the sponge type.

[mimoo]

have some start here: 4a95a2d. I'm missing some of useful implementations here that we should implement, also I chose a different name to differentiate absorption between different sponges

[mimoo]

I think what would be even more useful:

• on the prover side you can't put STUFF in a proof if you haven't absorbed it first (so absorb could return a special type that is in a proof)
• on the verifier side you can't extract what's in STUFF without absorbing it first (so absorb there could consume the special type and return the actual types we can manipulate)