Skip to content
This repository has been archived by the owner on Feb 15, 2023. It is now read-only.

Design sponge API #1

Closed
Pratyush opened this issue Sep 25, 2020 · 8 comments
Closed

Design sponge API #1

Pratyush opened this issue Sep 25, 2020 · 8 comments

Comments

@Pratyush
Copy link
Member

Pratyush commented Sep 25, 2020

Design issue for a sponge trait that should be used across all projects that rely on the FS transform.

Tentative API:

pub enum ChallengeSize {
    /// Sample challenges from the entire field.
    Full,
    /// Sample challenges from a subset of the field of size 2^num_bits.
    Truncated { num_bits: usize },
}
pub trait FiatShamirSponge<F: Field> {
    fn absorb(&mut self, input: impl Absorbable<F, S>);
    fn squeeze(&mut self) -> F {
        self.squeeze_with_size(ChallengeSize::Full)
    }
    fn squeeze_with_size(&mut self, size: ChallengeSize) -> F;
}

pub trait Absorbable<F: Field, S: FiatShamirSponge<F>> {
	fn absorb_with_sponge(&self, sponge: &mut S);
}

Things to note:

  • Input is generic. This allows us to easily represent both byte-based and field-based sponges (eg: Blake2s and Poseidon)
  • The output is not generic, which means that this API is unsuitable for things like hashing to the curve. (The latter is useful in discrete-log protocols). Is this something we want to support (i.e. a sponge with generic output type?)

Is the foregoing API sufficient for usecases like Fractal? I think it suffices for the Marlin compiler, and for poly-commit and accumulation-scheme challenge generation.

Prior work:

@Will-Lin4
Copy link
Collaborator

Will-Lin4 commented Sep 25, 2020

My main concern over having a generic input type is that it may make the trait itself unusable in a general setting. I am not fully familiar with Rust semantics, so correct me if I'm wrong:

Generic input types (as is in the current design) would restrict the trait itself from being used in a general setting. ie. The user would not be able to take as argument a generic FiatShamirSponge type and properly use the trait because they would need to know what input type to use. So, they would need to have a specific implementation in mind to use the trait.

One possible middle ground is to introduce two new traits that only take in byte-based and field-based inputs respectively.

@Pratyush
Copy link
Member Author

The latter should not be an issue, as long you bound whatever you feed into the sponge with a T: Into<S::Input>, where S: FiatShamirSponge<F>

(we might need to have a different trait than Into, though)

@Will-Lin4
Copy link
Collaborator

Will-Lin4 commented Sep 25, 2020

The latter should not be an issue, as long you bound whatever you feed into the sponge with a T: Into<S::Input>, where S: FiatShamirSponge<F>

(we might need to have a different trait than Into, though)

I suppose this works in the case where random oracle inputs can be generically passed around. If users have non-generic inputs instead, would the trait still be restricted in general use cases?

@Pratyush
Copy link
Member Author

Yeah, you can still do, for example, u8: Into<S::Input>. But the API is kinda clunky, because relying on the conversion Into<S::Input> is unclean; different conversion use cases might have different requirements. (eg: converting to bytes for serialization is different from converting to bytes for absorbing into a sponge)

Maybe a better API would be to instead have something like:

pub trait FiatShamirSponge<F: Field> {
    fn absorb(&mut self, input: impl Absorbable<F, S>);
    fn squeeze(&mut self) -> F {
        self.squeeze_with_size(ChallengeSize::Full)
    }
    fn squeeze_with_size(&mut self, size: ChallengeSize) -> F;
}

pub trait Absorbable<F: Field, S: FiatShamirSponge<F>> {
	fn absorb_with_sponge(&self, sponge: &mut S);
}

@weikengchen
Copy link
Member

We have a slightly specialized interface for nonnative and native. This one is specialized in that it supports a nonnative field.
https://github.com/alexchmit/perfect-constraints/blob/52fc8b1358c4e302eb908c026abc593a99ad4362/ark-marlin/marlin/src/fiat_shamir/mod.rs#L46

/// the trait for Fiat-Shamir RNG
pub trait FiatShamirRng<F: PrimeField, CF: PrimeField>: RngCore {
    /// initialize the RNG
    fn new() -> Self;

    /// take in field elements
    fn absorb_nonnative_field_elements(&mut self, elems: &[F]);
    /// take in field elements
    fn absorb_native_field_elements<T: ToConstraintField<CF>>(&mut self, elems: &[T]);
    /// take in bytes
    fn absorb_bytes(&mut self, elems: &[u8]);

    /// take out field elements
    fn squeeze_nonnative_field_elements(&mut self, num: usize) -> Vec<F>;
    /// take in field elements
    fn squeeze_native_field_elements(&mut self, num: usize) -> Vec<CF>;
    /// take out field elements of 128 bits
    fn squeeze_128_bits_nonnative_field_elements(&mut self, num: usize) -> Vec<F>;
}

There are two things specialized in this design:

  • An interface to squeeze nonnative field elements. This interface could be more powerful once our NonNativeFieldVar does not need to specify NonNativeFieldParams.
  • An interface to squeeze nonnative field elements of 128-bit only (for challenges).

@Pratyush
Copy link
Member Author

One thing that we need to do is sample elements from outside given subgroups; is there an easy way to do that in this API?

Or do we just assume the probability of that is negligible?

@weikengchen
Copy link
Member

Ah, yes. In our implementation, squeeze_nonnative_field_elements would not be random in the field F. In fact, it is in a smaller range ~|F|/2.

It would still have randomness sufficient for some applications, but its distribution is uneven in the whole field. (We dropped the highest bit.)

@Pratyush
Copy link
Member Author

Initial implementation is done in #2 , so closing this .

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants