Feature Request: Implementation of Poseidon2 Hash Function

[lurk-lab]

Feature Request: Implementation of Poseidon2 Hash Function

[huitseeker]

See also this circom PR (unreviewed): iden3/circomlib#98

[porcuquine]

Agreed. Here are a few not-entirely-cooked thoughts about how that might best be integrated. Some of this is more about the overall 'container' than a Poseidon 2 implementation per se:

• Implement such that it's easy to use with SAFE and swap the permutation. In other words, if someone knows they want to use Poseidon 2 in the future and wants to start writing code for that world now — they can do so using SAFE and later swap out the underlying implementation with minimal effort. (Nova is an example of a consumer already using SAFE for its random oracle).
• Add a merkle-hashing wrapper with similar API (at least in spirit) to existing 'merkle DST' implementations where a simple N-ary hash function is what the application wants (as, for example Filecoin and Lurk) do.
• Deprecate the old domain-separation tag facility. It's complicated and derives from suggestions made in the first version of the Poseidon paper. Ensuring the various modes are implemented correctly (where still stubs), then ensuring there are no inconsistencies, etc. represents a large implementation and maintenance burden.

Some of the above is not strictly required for Poseidon 2 — but I'm noting it here because it's part of a logical path forward for neptune generally, and is part of what we should consider when deciding how to integrate it.

---

A separate question is how much of the GPU support for batched hashing (on top of which tree-building is constructed) we would extend to Poseidon 2. The Neptune tree-building is no longer the most optimized (relative to approaches that keep intermediate values on the GPU). Nevertheless, the simple batched hashing is certainly useful when compared to CPU — when parallel hashing is needed.

[huitseeker]

I think we can split the issue in several steps, in that order:

• out-of-circuit implementation of Poseidon2 with minimal¹ divergence from the existing Poseidon (which helps review & incidentally, witness-gen),
• in-circuit implementation of Poseidon2 with minimal divergence from the existing Poseidon,
• SAFE API implementation that can dispatch to Poseidon / Poseidon2,
• GPU acceleration
• Merkle-hashing wrapper that can dispatch to Poseidon / Poseidon2,

I think the topics of DST deprecation, while valuable, is an orthogonal problem that deserves its own orthogonal issue.

Footnotes

1. "Minimal" here means the first priority is correctness, the second is performance, and the third is code reuse / sharing. ↩

[porcuquine]

That all makes sense to me.