PR for Merkle-friendly 32-byte Pedersen hash functions

[weijiekoh]

Hi Jordi,

Would you be interested in a pull request to add new circuits and JS code for the following features?

All the code is here: https://github.com/weijiekoh/snarschain

1. PedersenHash circuit

   • 1 input signal: a 32-byte bigInt
   • 3 output signals:
     • x-output of a Pedersen circuit
     • y-output of a Pedersen circuit
     • 32-byte encoded-output of a new EncodePedersenPoint circuit

2. EncodePedersenPoint circuit

   • 2 input signals: x and y (32-byte bigInts)
   • 1 output signal: the 256 bits of x, but its most significant 8 bits are the 8 most significant bits of y.

3. JoinHashes circuit

   • 2 input signals: left and right
   • 1 input signal: the 128 LSBs of left concatenated with the 128 LSBs of right

4. PedersenHashDouble circuit

   • 2 input signals: left and right, a 32-byte bigInt each
   • 2 output signals:
     • out[2]: the x- and y-outputs of a Pedersen circuit
     • 32-byte encoded-output of a new EncodePedersenPoint circuit

These circuits achieve two goals:

1. Have an easy-to-use Pedersen hash circuit which outputs 32 bytes. Since the Pedersen hash function outputs a point on the BabyJub curve, which is symmetrical across the y-axis, the only relevant data is the x-value and the sign of the y-value. However, the babyJub.packPoint() function will cause an integer overflow within circom, so the next best option is to return 32 bytes consisting of the most significant 8 bits of y and the least significant 248 bits of x.

2. Have an easy-to-use Pedersen hash circuit which can be plugged in to a Merkle tree validator circuit. Since it needs to hash two 32-byte values, it takes 16 bytes from each input and then pipes them into the Pedersen single-input hash circuit described above.

I'm curious about what you think. If you like the idea, I'm happy to package what I've written as a PR to circomlib and submit that. I'm also keen to improve EncodePedersenPoint and JoinHashes if they are incorrect or insecure.

Thanks!

[weijiekoh]

I just discovered sha256compression.circom! I will try to use that instead of the naive concatenation method described above.

*edit: scratch that, that would defeat the purpose of getting better performance with Pedersen hashses. Back to the drawing board...

[jbaylina]

Pedersen needs to go to window3.
We are moving more to the Poseidon hash function in general.
The Compression of the point is already here: https://github.com/iden3/circomlib/blob/master/circuits/pointbits.circom