Feature Request: Implementation of Poseidon2 Hash Function

[huitseeker]

I would like to propose the implementation of the Poseidon2 hash function in the Neptune repository. This recent advancement enhances the efficiency of the Poseidon hash function, specifically tailored for zero-knowledge applications.

Referencing the research paper and the explanatory note provided by the authors, Poseidon2 enhances performance by focusing on its linear layers and round constant addition. This new design requires only a short chain of additions for computation, significantly reducing the number of multiplications and reductions.

Specifically,

• Poseidon2 employs a fixed matrix for the external linear layers and another matrix for the internal linear layers, differing from the original Poseidon, which uses the same expensive MDS matrix in each linear layer.
• Poseidon2 directly modifies the round constant addition, eliminating the need for the efficient representation required in the original Poseidon.

Given these improvements, Poseidon2 can offer a performance boost of up to a factor of 4 compared to the original Poseidon, without any increase in the number of rounds or other disadvantages. The reference implementation provided by HorizenLabs may be useful for this implementation.

Considering the focus of the Neptune repository on the Poseidon hash function, I believe that including Poseidon2 would greatly enhance its performance and efficiency.

[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.