STARK-Friendly Hash

Tire-Kicking Time

Ethereum Foundation Grant Progress

Last summer the Ethereum Foundation (EF) gave StarkWare a research grant to recommend a STARK-Friendly Hash (SFH) and then release efficient, production-quality software for a STARK system for the SFH (under a license approved by EF) for use by the Ethereum ecosystem of developers. The EF set a high bar for efficiency, well above what is achievable by libSTARK (and libSNARKand BulletProofs): a prover should generate STARK proofs for numerous repeated invocations of a hash function and the rate of proof creation (not to be confused with hash-rate — the rate of hashing) should be at least 100 hashes/second measured on a quad-core machine with 16GB of RAM. Additionally, the STARK proof for 100,000 hashes should be verifiable in 10ms on a single core and must be less than 200 KB large.

Standard hash functions like SHA2, SHA3 and Blake and standard symmetric ciphers like AES are the gold-standard in terms of security. However, those functions were selected to optimize a set of constraints related to hardware and electricity consumption. Implementations of ZKP systems didn’t exist back then and thus, “STARK-friendliness” was not a priority.

This must change. Blockchain scalability (and privacy) requires succinct proof systems that can prove statements about hashed (and encrypted) data. Often, the heaviest parts of proof construction are due to cryptographic primitives. For instance, this is the case with the Zcash Sapling ZK-SNARK that shields payments: most of the proving time (and complexity) comes from proving statements about invocations of Pedersen and Blake2b hash functions. (The goals set by the EF for StarkWare are ones of scalability, not privacy, but having efficiently provable hash functions is important in both cases).

Our project started with a rather simple goal: StarkWare was to collect and survey existing hash functions with well-established security parameters, and select the friendliest among them. However, we quickly realized there’s a better and more ambitious way to serve the Ethereum community, one that may benefit other projects in this space as well: soliciting new hash functions that are optimized for STARK friendliness. (While SNARK- and BulletProof-friendly hash functions are not goals of this project, some of the suggested STARK-friendly ones may be friendly to those ZKP systems as well.)

We approached two external academic teams of cryptographers and funded research by them which led to two pairs of constructions: the Vision/Rescuepair and the Starkad/Poseidon pair. These constructions come in pairs: one type works over binary fields and the other works over prime fields. At the same time, we learned of a third research work, called GMiMC, that was not solicited, nor funded, by StarkWare. Each of the three groups is based on different design principles. To these constructions one should add the oldest of the “finite-field friendly” constructions — MiMC. That’s our current shortlist of contenders for the title of the STARK-friendly Hash (SFH) function (we’re always on the lookout for new ones). We have already solicited an expert evaluation of the algebraic security of these candidates but that’s far from enough. So we are now inviting the public to kick the tires of these candidates via a public set of puzzles, rewarded by Ether and doled out by smart contracts. Details follow.

Collision challenges — Win Some Ether!

Dr. Tomer Ashur agreed to run the SFH challenge on StarkWare’s behalf. He consulted with the various teams that constructed the candidates and designed a set of puzzles, each one asking to find a collision in a version of one of the SFH candidates (a collision is a pair of distinct inputs that have the exact same hash). There are four ranges of parameters: low-security (expected to be broken with around 2⁴⁵ attempts), medium-security (breakeable in around 2⁸⁰ attempts), target-security (breakable in around 2¹²⁸ steps) and high-security (around 2²⁵⁶ steps to break).

The prize pool is over 200 ETH (>$40K a the time of writing) — that’s a large sum, but the cost of breaking the SFH once it’s deployed and massively used could be orders of magnitude larger. The first solver of each puzzle will be awarded according to the security level of the puzzle: 1, 2, 4 or 8 ETH for each puzzle solved. Our current plan is to run this challenge until the end of March 2020, but we might extend it and/or tweak some of the puzzles later on.

Remark: Other than this challenge, StarkWare is NOT giving away Ether, nor is it running an ICO. Beware of scammers!

For those puzzles that are defined over prime fields we’re deploying smart contracts on Ethereum that will automatically award the prize to the first solver. You may also send the solution directly to us off-chain, and we’ll collect the ETH prize and send it to you — but please note that we will be accepting solutions only from the date the smart contracts are live. For binary fields, off-chain is the only way to collect the prize (Ethereum’s VM does not naturally support binary field multiplication). Additional prizes may be handed out at our discretion for beautiful attacks and information on them.

Next step — The SFH selection committee

In November 2019 we shall convene a small committee of leading academic experts in the field of constructing and analyzing symmetric cryptographic primitives. This esteemed committee will spend a number of days examining all the data available by then regarding the SFH candidates — including whatever will emerge from the SFH challenge — and recommend which ones are safest to use. The report of this committee is expected to appear early in 2020.

With this recommendation in hand, StarkWare will start writing the code for the prover and verifier, and then undergo a number of code audits by external parties before delivering the code to the Ethereum Foundation that will share it with its developer community.

We are on a very tight schedule, the challenge in front of us is considerable and we appreciate what’s at stake here. We will do our best to meet the expectations of the Ethereum developer community. We ask for your help: please, kick some tires, win some Ether. Details and specs here.

Eli Ben-Sasson

StarkWare