penumbra-zone / poseidon377

An instantiation of the Poseidon hash for use with decaf377
https://protocol.penumbra.zone/main/crypto/poseidon.html
Other
28 stars 10 forks source link

r1cs: `PoseidonSpongeVar` permutation #30

Closed redshiftzero closed 1 year ago

redshiftzero commented 1 year ago

Followup from #29: We are using PoseidonSpongeVar from ark-sponge for in-circuit hashing (ref https://github.com/penumbra-zone/penumbra/issues/714).

~However, the implementation of the permutation via PoseidonSpongeVar::permute does not use the optimizations we added support for in our parameter generation code in #17 and in our poseidon-permutation crate in #20. For some concrete numbers, we saw a ~1.9x reduction in the number of multiplications for our 4:1 hash (see PR text #21 for where this number comes from)~.

Edit: These optimizations only work out of circuit, as (ref section 6.2.1 in the paper), the R1CS cost does not change due to the (constant multiplication) linear layers.

redshiftzero commented 1 year ago

To prioritize the above here are the circuit costs of various gadgets as of commit 0db4a2be63ff444aa5e481cf82e6eb22e6653500 (in penumbra):

The numbers below include the constraint cost of witnessing the required instance variables:

redshiftzero commented 1 year ago

This is no longer planned for implementation due to #40

redshiftzero commented 1 year ago

Reopening as #40 was backburnered