Feature request: poseidon 2 implementation

[mrain]

For VID

References

• Poseidon2 paper
• plonky3 reference implementation
• zkhash rust implementation that we might directly use or modify on top.

[alxiong]

Existing work

After reading through both plonky3 and zkhash's implementations, here is a summary:

• zkhash is written by the author of P2 paper, using arkworks backend, can be directly used by us, (except we need to extend a few trait impl for them, e.g. HasherDigest since we can't directly impl Digest for them)
• plonky3 uses their only FieldAlgebra internally defined
• zkhash's impl is still academic code, less actively maintained, code structure is okay but not great, many prunable logic (as I assume they modify on top of their existing poseidon impl, there are some legacy baggage)
• plonky3's impl is clean, modular, and performant.
  • one questionable design decision that I hesitate to follow is turning all poseidon related param as generic parameter struct Poseidon2<F, ExternalPerm, InternalPerm, const WIDTH: usize, const D: u64> whereas zkhash's only generic over the field choice and accept the parameters at construction time. adding so many generics and then bunch of trait bounds to restrict their relationship bloated the code and affect readability.

Actions:

1. minimally wrapping zkhash to make Poseidon2 MT available in jellyfish first

• a non-trivial adaption: zkhash uses stateful self, but our api (and plonky3's) are purely functional

2. I will implement our own, following more closely with plonky3's structure, inside jellyfish, then drop-in replace zkhash

The OOP to functional conversion requires as troublesome as a rewrite. I'll simply reimplement. We can't directly use zkhash unfortunately

Auxiliary

• We should use nimue's Sponge which is friendly to field-oriented sponge, than ark-sponge's trait. The problem of adopting the byte-oriented sponge is emblematic here (those unimplemented) in our own code.

[alxiong]

Once #708 is merged, we have some follow-up (in descending priority)

• Change jf_merkle_tree's import from path = "../poseidon2" to a tag after we add a tag to a commit on main
• Add a CRHF for poseidon2
• Implement Sponge (from nimue crate) on Poseidon2
• Implement circuit for P2