Poseidon hash support (optimized / non-optimized)

[drewstone]

[zhenfeizhang]

Some notes after the discussion with @chancharles92

• for a 3-inputs-1-output hash function, rescue is more efficient than poseidon in terms of jellyfish's #constraint
  • Poseidon-BLS12-377: 8 * (4 + 3 * 4) + 57 * (4 + 3) = 527
  • Poseidon-BLS12-381: 8 * 4 + 57 * 4 = 260
  • Rescue-BLS12-377: 12 * (2 * (4 + 3 * 4)) = 384
  • Rescue-BLS12-381: 12 * (4 + 8) = 144
• for a 16-inputs-1-output hash function, poseidon will likely be more efficient

[zhenfeizhang]

So it looks like for the use case with 16-in-1-out Poseidon it maybe interesting to do some PoC here.

Proposed roadmap to support Poseidon hash

• [ ] unify APIs for all hash functions under ark-sponge #50 (critical path)
• [ ] rename rescue as circuit-friendly-hashes which consists of
  • [ ] poseidon (maybe critical path)
  • [ ] rescue (critical path)
• [ ] poseidon parameters for
  • [ ] ed_on_bn_254::BaseField
  • [ ] ed_on_bls_12_377::BaseField (maybe critical path)
  • [ ] ed_on_bls_12_381::BaseField
  • [ ] bls12_377::BaseField
• [ ] native circuit for poseidon (maybe critical path)
  • [ ] subtasks TBD
• [ ] non-native circuit for poseidon
  • [ ] subtasks TBD

cc @chancharles92 @alxiong