Poseidon circuit

[sinui0]

Regarding our recent discussion to produce SNARK-friendly hashes of the query and response data using 2PC, we'll need to produce the boolean circuits for Poseidon.

[themighty1]

Just to recap. We have a garbling scheme BMR16 already implemented in Rust here https://github.com/GaloisInc/swanky/tree/master/fancy-garbling
This scheme's has very attractive properties in terms of bandwidth cost:

• free addition
• free multiplication by a constant
• constant cost of exponentiation by a public exponent regardless of the size of the exponent.

We are looking for a snark-friendly hash which fits all those criteria.
It seems by looking at the source code of https://github.com/iden3/go-iden3-crypto/blob/master/poseidon/poseidon.go that Poseidon is a perfect fit because
it does not multiply two variables but only multiplies by a constant.

[themighty1]

in the BMR16 paper Figure 3 (p.16) shows that for 64-bit numbers exponentiation-by-constant gate costs 365*16=~5KB.

Usually in zksnarks we deal with 256-bit numbers, so we can extrapolate that it will cost ~30KB to exponentiate a 256-bit number.

Edit: Poseidon hashes 16 field elements (of 31 bytes each), not 16 bytes. Fixed numbers accordingly.

It takes 204 exponentiations to hash 16*31=496 bytes of data with vanilla Poseidon. That's gonna cost us (204 * 30) / 496 * 16 = ~200KB of bandwidth per 16 bytes of plaintext. Not ideal but a starting reference point.

[themighty1]

Oh, just realized that have some kind of "golden poseidon". It operates on 64-bit fields (i guess that's the new field from plonky2).
It does 118 exponentiations to process 8 Field elements, so it will cost us (356 * 16 * 118) / (8 * 8) * 16 =~168KB per 16 bytes of plaintext.

[sinui0]

Closing this issue as we determined that Poseidon can't viably be computed with a boolean circuit, and the BMR16 scheme does not support constant cost exponentiation by a prime.

We're instead pursuing another technique to generate Poseidon commitments using a combination of garbled circuits and SNARK