STARK-Friendly Hash Challenge

StarkWare Giving Away ETH! (fine print below)

The Ethereum Foundation (EF) asked StarkWare to recommend a STARK-Friendly Hash (SFH). Following that, StarkWare will release an efficient, production-quality software implementation for a STARK prover and verifier under a license approved by EF during the 3rd quarter of 2020. This software will subsequently be used by the Ethereum developers’ ecosystem (more details here).

The StarkWare hash challenge is a public competition to evaluate the security of proposed SFH candidates. The challenge is proposed at four security levels: low-security, medium-security, target-security, and high-security in multiple scenarios we are interested in.

We invite all interested parties to take part in the challenge and try to solve the puzzles provided. In return, we will be giving away ETH as a reward to the first person to solve each puzzle. Not the first to solve the puzzle? Don’t worry, there may still be prizes for you.

Details

Each of the four security levels consists of several puzzles to solve and they will be released according to the tentative timeline specified below. for each puzzle, we challenge you to find a pair of distinct values mapping to the same output (collision attack). For some of the puzzles we will encode the puzzle as a smart contract (released according to tentative timeline specified below), so you can claim your prize easily. In other cases we will ask you to send us an email with your solution.
In addition to the prizes we are offering for directly solving the puzzles, we will reward, at our discretion, any new information you will be providing us with (see “I Solved a Puzzle” section below).

Algorithms

The challenge features three families of algorithms developed by leading researchers in the field of symmetric-key cryptography:
  • HadesMiMC

    The HadesMiMC family by L. Grassi, D. Kales, D. Khovratovich, A. Roy, C. Rechberger, and M. Schofnegger (https://eprint.iacr.org/2019/458). This family includes Starkad for binary fields and Poseidon for prime fields. The distinguishing feature of this family is that in some rounds it uses a partial S-box layer and thus reduces the overall number of field operations required for computing the function.

  • MARVELlous

    The MARVELlous family by A. Aly, T. Ashur, E. Ben-Sasson, S. Dhooghe, and A. Szepieniec (https://eprint.iacr.org/2019/426). This family includes Vision for binary fields and Rescue for prime fields. The distinguishing feature of this family is that it utilises non-determinism to efficiently arithmetize operations that would be inefficient otherwise (e.g., calculating a cubic root).

  • GMiMC

    The GMiMC family by M. R. Albrecht, L. Grassi, L. Perrin, S. Ramacher, C. Rechberger, D. Rotaru, A. Roy, and M. Schofnegger (https://eprint.iacr.org/2019/397). This family includes GMiMCcrf, GMiMCerf, GMiMCNyb, and GMiMCmrf. For the purpose of this challenge we will only be considering GMiMCerf over prime fields.

All these hash functions were vetted by leading cryptanalysts and no obvious weaknesses were found in them. Now, before moving on to the next step in our plan, we want to crowdsource the cryptanalytic effort and hear what YOU can do with them.
In addition to the algorithms above, which have been deemed useful for our purposes due to their flexibility allowing for efficient evaluation, we will be offering puzzles for one additional less-flexible function: MiMCHash-2q/p by M. Albrecht, L. Grassi, C. Rechberger, A. Roy, and T. Tiessen (https://eprint.iacr.org/2016/492).

The Challenge

Each security level consists of 2—6 puzzles featuring different field sizes (n), capacity (c), rate (r), and number of field elements per state (m=c+r). In each puzzle, all candidate algorithms are compared with respect to the same parameter set. The exact parameters can be found in our reference implementation, released according to the tentative timeline specified below.

Finding a Collision

A collision over a value y with respect to a hash function H(*) is a pair of distinct values x and x’ such that H(x) = H(x’). Collisions must exist because H(*) has more inputs than outputs (this is the Pigeonhole Principle). We do not know of any specific collisions for the functions we’re considering. But maybe you can help us find them.

Algorithm

Implementaion

Common

Vision
+
Rescue

Starkad
+
Poseidon

GMiMCerf

MiMCHash

I Solved A Puzzle, Now What?

First of all – congratulations! Assuming you’re the first to it, there are two ways for you to claim your prize and everlasting glory: the simple way and the cool one. The simple way, which applies to all challenges, is to email us the colliding pair (at competition@starkware.co). Your email must include, in addition to the colliding pair, the name of the function (e.g., Starkad), the field size, and the parameters m, c, and r so we can easily identify which puzzle you solved. You should also tell us if you want us to add your name to our website and the wallet address to which we should send the ETH to.

We’ll then check it, send you the prize, and update the website with your name (that’s the everlasting glory part). The cool way, which will apply only to some of the puzzles (the ones defined over prime fields) is to feed your collision pair directly to an Ethereum smart contract and be automatically rewarded by it (more details on this to be provided once the contracts are released, see tentative timeline).
Fine print: (1) No rewards will be distributed before the smart contracts are live. (2) Rewards are guaranteed only to the very first solver of each challenge and only if the solution is submitted before the end of March 2020. (3) Even if you are not the first to solve, if you have interesting additional information to supply to the public (such as new attack vectors), please share it with us (at competition@starkware.co) and we may decide (at our discretion) to reward you.

Timeline*

15 Aug 2019

SFH challenge announced

26 Aug 2019

Reference implementations released

9 Sep 2019

Smart Contracts published

16 Sep 2019

SFH discussion at StarkWare Sessions

31 Mar 2020

SFH challenge ends (and smart contracts expire)

*tentative

Links to smart contracts and Hall of Fame of collision solvers will appear in the tables below.

Low Security

45 bit

1 Ether for each solution

Parameters Vision Rescue Starkad Poseidon GMiMCerf
n≈90, m=3, c=1, r=2
n≈90, m=11, c=1, r=10

MiMCHash
n≈90, m=2, c=1, r=1

Medium Security

80 bit

2 Ether for each solution

Parameters Vision Rescue Starkad Poseidon GMiMCerf
n≈80, m=4, c=2 r=2
n≈160, m=3, c=1, r=2
n≈160, m=11, c=1, r=10

MiMCHash
n≈160, m=2, c=1, r=1

Target Security

128 bit

4 Ether for each solution

Parameters Vision Rescue Starkad Poseidon GMiMCerf
n≈128, m=4, c=2, r=2
n≈256, m=3, c=1, r=2
n≈128, m=12, c=2, r=10
n≈64, m=12, c=4, r=8
n≈256, m=11, c=1, r=10

MiMCHash
n≈256, m=2, c=1, r=1

High Security

256 bit

8 Ether for each solution

Parameters Vision Rescue Starkad Poseidon GMiMCerf
n≈128, m=8, c=4, r=4
n≈128, m=14, c=4, r=10

Our Fields

Binary Prime
n≈64
GF(2)[x] mod x63+x+1
261 + 20·232 + 1
n≈80
GF(2)[x] mod x81+x4+1
281 + 80·264 + 1
n≈90
GF(2)[x] mod x91+x8+x5+1
291 + 5·264 + 1
n≈128
GF(2)[x] mod x127+x+1
2125 + 266·264 + 1
n≈160
GF(2)[x] mod x161+x18+1
2161 + 23·2128 + 1
n≈256
GF(2)[x] mod x255+x5+x3+x2+1
2253 + 2199 + 1

Our Fields

n≈64
Binary: GF(2)[x] mod x63+x+1

Prime: 261 + 20·232 + 1

n≈80

Binary: GF(2)[x] mod x81+x+1

Prime: 281 + 80·264 + 1

n≈90

Binary: GF(2)[x] mod x91+x8+x5+1
Prime: 291 + 5·264 + 1

n≈128

Binary: GF(2)[x] mod x127+x+1
Prime: 2125 + 266·264 + 1

n≈160

Binary: GF(2)[x] mod x161+x18+1
Prime: 2161 + 23·2128 + 1

n≈256

Binary: GF(2)[x] mod x255+x5+x3+x21
Prime: 2253 + 2199 + 1

FAQs

We will not be able to answer all emails. Certain emails will certainly not be answered (including ICO inquiries, token sales and proofs of P=NP).