MiMC/e7r46

[Brechtpd]

Hi Harry,

In this post you say that it may be acceptable to reduce the number of rounds for MiMC from 91 to 46. Do you still think that's the case (when used as the hash function for Merkle trees)? Or is this still uncertain?

Any advice greatly appreciated. :)

[HarryR]

Hi,

I am still uncertain about this, because I'm unsure of the details of how to attribute some kind of 'security level' to the number of rounds - aside from what is mentioned in the paper - where, when the degree of the polynomial exceeds the range of the field we are no-longer able to interpolate it at any cost rather than just 'at cost'.

I guess the problem depends on 'what is the real-world cost of interpolating a 2^n polynomial, where n is either >= log2(p) (as in, you cannot interpolate it) or n ~= log2(p)/2' where the cost is reduced. This problem hinges upon two arguments:

1) There is something more efficient than Lagrange interpolation 2) The real-world cost of Lagrange interpolation, even where n ~= log2(p)/2, is greater than any benefit you could gain from exploiting such a system.

I am on unsteady hypothetical ground here, I don't know... if you reduce the number of rounds to 46 instead of 91... what is the security?

shrug if you could help out, or provide insightful references, I would really appreciate it...

[Brechtpd]

I'm afraid I can't provide any help on this. But I asked Dmitry Khovratovich and he told met that

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.

We'll be looking into using Poseidon.

Thanks for the help!

[HarryR]

Just to follow-up:

Ethsnarks is using MiMC with a one-way compression construct called Miyaguchi-Preneel, rather than in the sponge construct, this requires a little under 800 constraints (with 91 rounds) for every pair of field elements, it is also collision resistant so it can be used to construct Merkle trees, and as the hash function for Schnorr signature verification.

Do you have a link to pseudocode for Poseidon? From the whitepaper I can't see enough to be able to implement it.

[Brechtpd]

Hi Harry,

Thanks for the extra info about MiMC. This is way above my head but it seems like it works differently than Dmitry expected. Still, the number of constraints with Poseidon is potentially even lower than MiMC with fewer rounds so we'll still explore that option.

I actually found out yesterday that circomlib has an implementation but I haven't looked at it yet. Matter Labs is also working on an implementation I've heard (Alex also mentioned it in their talk yesterday at Scaling Ethereum).

Some extra info from Dmitry:

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.

[Brechtpd]

Unrelated, but we're looking for people to audit our ZK rollup based Loopring protocol v3 ~3 months from now. If I'm not mistaken you work for ZK Labs who do auditing, and it seems like you would be the ideal candidate to do so. If you/ZK Labs have the time and are interested please let me know. :)

[HarryR]

I'm not affiliated with ZK Labs any more, nor have I been for a while, if anybody tells you otherwise please get in touch with me directly.

I don't do audits. However I could spend some time with you trying to identify risks, helping figure out the unknowns, and just providing a critical eye.

[Brechtpd]

Oh I see, I only saw that you were listed under team on the frontpage, but that seems to be outdated then.

But yes, that would be great! Can you send some details on how that would work for you to Brecht@loopring.org and Daniel@loopring.org? Thanks!