iden3/circomlib

PR for Merkle-friendly 32-byte Pedersen hash functions

weijiekoh opened this issue · 2 comments

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!

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...

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