Edmund/continue poseidon

[edmundnoble]

This PR supersedes #1274.

Remaining work: check test vectors, check gas. Edit: both done.

The performance improvements in this PR go from this:

defaultMain [bench "poseidon" $ whnf poseidon [1,2,3,4,5,6,7,8]]
benchmarking poseidon
time                 1.696 ms   (1.686 ms .. 1.710 ms)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 1.704 ms   (1.695 ms .. 1.722 ms)
std dev              41.47 μs   (25.65 μs .. 74.70 μs)
variance introduced by outliers: 13% (moderately inflated)

to this:

defaultMain [bench "poseidon" $ whnf poseidon [1,2,3,4,5,6,7,8]]
benchmarking poseidon
time                 1.222 ms   (1.215 ms .. 1.230 ms)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 1.222 ms   (1.212 ms .. 1.244 ms)
std dev              49.37 μs   (21.97 μs .. 99.33 μs)

and from this:

defaultMain [bench "poseidon" $ whnf poseidon [1,2]]
benchmarking poseidon
time                 182.7 μs   (182.1 μs .. 183.3 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 182.0 μs   (181.2 μs .. 182.7 μs)
std dev              2.628 μs   (2.202 μs .. 3.368 μs)

to this:

defaultMain [bench "poseidon" $ whnf poseidon [1,2]]
benchmarking poseidon
time                 159.5 μs   (155.2 μs .. 164.8 μs)
                     0.996 R²   (0.993 R² .. 0.999 R²)
mean                 155.5 μs   (153.7 μs .. 157.8 μs)
std dev              6.763 μs   (5.227 μs .. 10.27 μs)
variance introduced by outliers: 43% (moderately inflated)

PR checklist:

• [ ] Test coverage for the proposed changes
• [ ] PR description contains example output from repl interaction or a snippet from unit test output
• [ ] Documentation has been updated if new natives or FV properties have been added. To generate new documentation, issue cabal run tests. If they pass locally, docs are generated.
• [ ] Any changes that could be relevant to users have been recorded in the changelog
• [ ] In case of changes to the Pact trace output (pact -t), make sure pact-lsp is in sync.

Additionally, please justify why you should or should not do the following:

• [ ] Confirm replay/back compat
• [ ] Benchmark regressions
• [ ] (For Kadena engineers) Run integration-tests against a Chainweb built with this version of Pact

[edmundnoble]

Gas graph: The actual inputs don't affect the time taken to compute the hash from what I can tell, only the number of them, so that's the X axis. The Y axis is micros * 2.5, i.e. gas as a unit of time.

[edmundnoble]

Here's where exactly the constants came from: https://github.com/iden3/circomlibjs/blob/main/src/poseidon_constants.js. I've patched the PR to use the exact same constants (in hex, just like they do it) so it's easier to compare. I have verified by hand that the output for these test vectors matches the output from https://github.com/iden3/circomlibjs/blob/main/src/poseidon_reference.js.