search

iden3 / circomlib

Library of basic circuits for circom
601 stars 209 forks source link

PR for Merkle-friendly 32-byte Pedersen hash functions #2

Open weijiekoh opened 5 years ago

weijiekoh commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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