search

Loopring / protocols

A zkRollup DEX & Payment Protocol
https://loopring.org
330 stars 122 forks source link

[Protocol3] Use more efficient hash functions #51

Closed Brechtpd closed 5 years ago

Brechtpd commented 5 years ago

Currently we use MiMC/e7r91 for our merkle trees. MiMC/e7r46, which is less secure but could be 'acceptable', reduces this by about 50%.

This would reduce the number of constraints in our circuits by about 30%-40%.

Links:

dong77 commented 5 years ago

@Brechtpd This might be a low-hanging fruit

dong77 commented 5 years ago

I asked Harry and Dmitry Khovratovich (who seems to be one of the experts of hash functions) about the security of MiMC/e7r46. About a month ago a new hash function called Poseidon was also published which Dmitry Khovratovich is the co-author of. Poseidon would use 8x fewer constraints compared to Pedersen (which has similar costs to MiMC/e7r92 which we currently use).

So it seems like Poseidon is the way forward and Matter Labs seems to think so as well it seems :), I haven't heard anything from them directly about this.

Below my question and his reply:

Hi Dmitri, In this post you’re sure that MiMC with 64 rounds is not secure for STARKs. Is that also the case for SNARKs? I’m trying to find out if we (Loopring) can use the MiMC/e7r46 for our Merkle tree instead of MiMC/e7r92.

Or do you think it’s better to just switch over to Poseidon for a (hopefully) cheaper hash function for SNARKs than MiMC/e7r92? (We would also need to be able to calculate the hash in EVM for a reasonable gas cost).

If you have any thoughts on this that would be very helpful!

Thanks, Brecht

Hi Brecht, yes it is insecure because the degree growth is insufficient to prevent attacks like Grobner basis. But also MiMC itself is not well suited for trees because if it is used in a sponge its rate is too small.

Yes I suggest Poseidon with x^3 or x^5 or 1/x depending on your curve. You can also exploit variable arity of Poseidon: with default width 6 you can get Merkle tree with arity 5, but if you want a power of 2, width 5 will be an optimal solution.

I know there is an ongoing implementation of Poseidon in Snarks by Matter Labs if it helps

dong77 commented 5 years ago

Completed in #256