Hashing trait

[iquerejeta]

With the progress of the Poseidon implementation #104 , it would be nice to begin a discussion on how we could implement the hash trait(s). Hopefully, this will also steer the discussion towards the gadgets design. I will eventually draft a PR.

My idea is to break the hashing family functionality into different traits:

• CollisionResistantHashing
• PseudoRandomFunction
• PreImageResistantHashing (and 2nd-pre image)

This would allow us to use hash functions which might only require collision resistance (certain use cases of merkle trees), cryptographically safe hash functions (collision + preimage + 2nd preimage resistance), or pseudo random functionality.

Was discussing with @CPerezz that it might make sense to also separate prime field hash functions and those that operate over binary fields. I agree with that, and in what concerns the prime field hash functions I would also make explicit trait distinctions for the capacity of the functions, as these might require different parametrisation. So rather than going with this type of trait definition (with hash and hash_two part of the same trait), I would rather follow this style (making an explicit distinction).

Any thoughts and comments welcome 👍

[markulf]

Your preferred style might seem more verbose as the traits are otherwise quite similar, but these seem to be different use-cases and it might make sense to treat them seperately.

Two observations, the arkworks trait, i.e. the second design, seems to hide the composer: &mut StandardComposer<F, P> but requires repeated input of parameters, which are taken from self in the first design.

In general I like the generic nature of arkworks and unless it comes at huge costs, either in performance or complicated code, it might be good to stay close to their design. This is likely a much wider discussion than this issue.

A side note, in fact this is the trait for the gadget, while what you pointed to might just be for native hash functions.

[iquerejeta]

Thanks for the comments. You are right, I missed the correct link. Edited with the one of the gadget now 👍

Regarding the composer, my first thought would be that the hash gadgets take a mutable reference to the standard composer. But I guess this question depends on how we decide to design gadgets in general, and not only hashing.

Regarding the different traits to be similar, yes. I'm not completely convinced of that design choice, but I do feel that having that level of granularity does make sense in some contexts.

[stechu]

Does PseudoRandomFunction imply CollisionResistantHashing?

[bhgomes]

I recommend the following pattern for hash functions which know their arity at compile-time: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=cc008c861ad5c5455d1ca26622284a4b

For denoting the security level, like collision resistance, PRF, preimage resistance etc, I recommend something like the CryptoRng trait which is just marker which is implemented whenever a random number generator is known to be cryptographically secure. This way, you separate the security guarantees from the usage API.

[iquerejeta]

Does PseudoRandomFunction imply CollisionResistantHashing?

Actually, it would be better to use RandomOracle instead of PseudoRandomFunction, as that might cause confusion given that the definition of a pseudo random function is slightly different to that of a hash function. At least, what I was thinking initially was to mark hash functions as random if they could be modelled as a Random Oracle. And yes, Random Oracle does imply CollisionResistant and PreImageResistant.

For denoting the security level, like collision resistance, PRF, preimage resistance etc, I recommend something like the CryptoRng trait which is just marker

Yes! I was thinking of doing something like that. So basically have some hashing trait, that defines whatever interface we want for hash functions, and then simply have markers for the other properties.