Transparent setup of Poseidon in Rust compile-time

[weikengchen]

From an interface perspective, we want to use Poseidon as a drop-in replacement for Pedersen and SHA-256. However, this would be slightly complicated because searching for Poseidon's parameters requires some care.

• \alpha must be coprime with p-1.
• Nums of full/partial rounds are related to p, sponge rate, and the desired level of security.
• MDS matrix must go through a few steps: a random generation + three security checks + retry if not passed.
• Round constants should be randomly chosen.

Or, in short, the parameters are application-dependent (sponge rate) and field-dependent (\alpha, p, MDS, constants).

Also, different choices of \alpha could end up with very different performances. As Fractal shows, choosing a larger \alpha could significantly reduce the number of rounds.

Though it is possible to leave all the jobs to the developers, it is not ideal since the developers would need to supply parameters for each field that the application may use. It is also possible that the developers did not generate secure parameters.

---

One possibility:

• Developers only need to specify the field and sponge rate, which is the application-dependent part.
• The program runs a search function, which starts with a deterministically generated seed (e.g., SHA256 of the string "Deterministic generation of sponge parameters [sponge rate] [field prime]" as the seed). This search function would need to find the most efficient & still secure parameters.

More specifically,

• It needs to try different valid \alpha and compute the nums of full/partial rounds. Then, it needs to compute their cost and find the most efficient one.
• It needs to generate the MDS matrix using a PRNG with the seed, go through the security checks, and retry if it did not pass.
• Round constants are also generated using the PRNG.

idea? thoughts?

cc'ed: @ValarDragon

[weikengchen]

Linking the Poseidon's official implementation of the parameter calculation (https://extgit.iaik.tugraz.at/krypto/hadeshash/-/blob/master/code/calc_round_numbers.py) and MDS matrix generation (https://extgit.iaik.tugraz.at/krypto/hadeshash/-/blob/master/code/generate_parameters_grain.sage).

[burdges]

You've presumably seen https://github.com/filecoin-project/neptune by now.

There surely exist tools for serializing rust types into rust code. If such a tool replaces Cow::Owned(Box<[T]>) with Cow::Borrowed(&'static [T]) then one could avoid initialization code and provide no_std support relatively painlessly.

pub struct PoseidonParameters<F: PrimeField> {
    /// number of rounds in a full-round operation
    pub full_rounds: u32,
    /// number of rounds in a partial-round operation
    pub partial_rounds: u32,
    /// Exponent used in S-boxes
    pub alpha: u64,
    /// Additive Round keys. These are added before each MDS matrix application to make it an affine shift.
    /// They are indexed by ark[round_num][state_element_index]
    pub ark: Cow<'static,[Cow<'static,[F]>]>,
    /// Maximally Distance Separating Matrix.
    pub mds: Cow<'static,[Cow<'static,[F]>]>,
}

In theory, an automatic search might benefit from some unsafe memoization code, similar to memoize but with 'static type parameters to provide roughly

pub fn initalize_poseidon<F: PrimeField>(...) -> &'static PoseidonParameters<F> { .. }

Yet, almost everyone would serialize their parameters into rust code though. Also, folks who want caching maybe want more control themselves, so one reasonable compromise foregoes memoization and goes:

#[derive(Clone)]
pub struct PoseidonSponge<
    F: PrimeField, 
    P: Clone+Deref<Target=PoseidonParameters<F>> = Cow<'static,PoseidonParameters<F>>
> {
    params: P,
    ...
}

[weikengchen]

Thanks for the input.

The slight complexity sort of suggests that possibly the best way is to help developers generate parameters for their specific needs?

I am thinking about a sage python script that can run on the sage cloud, and it would print out Rust code of the parameters that one can copy and paste.

[burdges]

Is there ever a need to generate parameters dynamically in Rust code? If so, then someone could translate the sage script of course, and then Cow tricks help. I suppose benchmarks and tests provide some case for dynamic parameter generation, although maybe not a strong one.

I think tabels come up relatively often when doing computational mathematics, not just cryptography. I opened https://users.rust-lang.org/t/ron-are-there-crates-to-serialize-rust-types-as-correctly-formated-rust-code/55451 out of curiosity, although a serde issue might be more helpful. Let's see what exists. :)

[burdges]

There is an uneval crate that produces Rust code using serde.

It'll work on code using Vec<..> I think, but then requires lazy_static or similar. It'd requires post processing for the Cow trick because serde strips all Deref types like Cow. Example: https://github.com/burdges/uneval/blob/cow/examples/cow_test.rs

Afaik, there are no serde dependencies in arkworks anyways, adding serde sound really heavy. An approach might be some new RustConst formatter trait, similar to Debug and Display but meh..

[burdges]

I believe the constuneval crate should make convenient for developers to generate bespoke parameters which can either be used directly or serialized Rust code they can include!.

[weikengchen]

@burdges given the complexity of the matrix generation, we might consider two stages: (1) stage 1: push a few parameters for commonly used curves (2) stage 2: identify a way to generate them automatically

I think I would start with the first---so that we have Poseidon to use.

[ValarDragon]

Sorry, somehow didn't see this issue until just now. Will reply some more later, quick replies to things I saw in the last few comments:

Re the sage script, we do have a sage script that outputs rust parameter code with the original implementation of Poseidon. Probably has to be updated for the refactors that have occurred since I first wrote it for the fractal constraints.

There could be a reason to generate parameters dynamically, if you want the permutation to depend on some runtime data. But I think at that point, its probably better for efficiency reasons to separate out the implementations. (So that most applications get the MDS table / ARK's hardcoded)

[hdevalence]

I'm late chiming in here, but another option could, potentially, be to have a build dependency that implements parameter selection in Rust. This avoids the portability / reproducibility issues with Sage, at the cost of possibly having to implement extra math functionality. But at least the authors' round selection script doesn't need Sage.