Support Poseidon2

[redshiftzero]

There's another version of Poseidon, called Poseidon2: https://eprint.iacr.org/2023/323

Most relevant for us is section 7.3 which discusses mitigating the attacks found here where the researchers are able to skip 2 rounds of Poseidon 1. Note that the current additional security margin in Poseidon 1 (added in case new attacks are found) is 2 full rounds and 7.5% additional partial rounds.

This ticket is to evaluate whether we should migrate to Poseidon2 prior to mainnet launch, given that we do not want to change hash functions after launch.

Sub tasks:

• [x] Write up the implications of changing hash functions, along with the agility associated with each place in the protocol, e.g. changing Poseidon instantiations in the SCT is less disruptive than in the key/address derivation hierarchy (since all the addresses will change again)
• [ ] Update our Poseidon parameter generation: https://github.com/penumbra-zone/poseidon377/pull/48
• [ ] Pick a Poseidon2 Rust implementation. Option here: https://github.com/HorizenLabs/poseidon2 (Edit: and here: https://github.com/lurk-lab/neptune/blob/master/src/poseidon.rs)
• [ ] Implement Poseidon2 in R1CS.

[plaidfinch]

If we change poseidon implementations in the SCT post-mainnet, then we'll have to maintain two separate shielded pools forever, which makes me think this is not actually a place where things are particularly agile. Compared to in the key hierarchy, though, I suppose it is.

[hdevalence]

I'm not sure that's true — in a hypothetical V2 where we changed the hash function, we could recreate a new SCT with the same leaves but the new hash function, and use that instead. Clients would have to upgrade and re-sync, and the leaf commitment hashes would still be poseidon 1, but that's the less important part of the inclusion proofs.

[redshiftzero]

Here are the places we currently use Poseidon1 in the protocol categorized by how easy it is to change the hash function:

Least agility: Impacts all published addresses

We use rate-2 Poseidon1 to hash the spend authorization key $ak$ and the nullifier deriving key $nk$. The hash output in turn is used to compute the IVK, which is used to derive the transmission key $pk_d$. Since the transmission key is part of the address, changing the derivation of the IVK changes the address, which is the most disruptive change since it impacts all published addresses. It also is a circuit-breaking change since we derive the IVK in-circuit.

Low-medium agility: Circuit-breaking changes

The next category of places we use Poseidon1 are:

• Deriving nullifiers based on position, state commitment, and nullifier deriving key (rate 3 Poseidon1)
• Deriving swap and note commitments (rate 6 Poseidon1)
• Deriving asset-specific value generators (rate 1 Poseidon1)
• Hashing state commitments into the state commitment tree (SCT) - (rate 1 and 4 Poseidon1)

For the SCT, while we can transparently change the hash function used in the tree, since Merkle path verification in the circuits would also need to use the new hash, unless I'm missing something I think this is still a circuit-breaking change, as are the other uses of Poseidon1 in this category.

High agility: No major implications

The final place we're currently using Poseidon1 which we can easily change is:

• Deriving two Rseeds for the outputs of a swap (rate 1 Poseidon1)

We derive two Rseed values in SwapPlaintext::output_rseeds() which are then used to derive blinding factors for the swap output notes. While this is currently done inside the verification method of the current transparent swap claim, we can derive the blinding factors out of circuit based on each Rseed, and witness the resulting blinding factors in the circuit, which is what we do for the other circuits involving note commitments. This is the approach taken for the ZK swap claim in https://github.com/penumbra-zone/penumbra/pull/2151. It's also reasonable to in a future change just use Blake2 in SwapPlaintext::output_rseeds() instead of Poseidon1.