STARK-Friendly Hash

Tire-Kicking Time

StarkWare
StarkWare
Aug 15, 2019 · 5 min read

Ethereum Foundation Grant Progress

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!

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

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

StarkWare

Developing the Full Proof Stack for STARK

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store