Validity Proofs vs. Fraud Proofs Strike Back

StarkWare
StarkWare
Dec 5, 2019 · 7 min read
Image for post
Image for post
Photo by Artur Tumasjan on Unsplash

Introduction

Recent months have seen considerable interest in Optimistic Rollup (OR), a Fraud-Proof (FP)-based scalability framework. We at StarkWare are implementing Validity Proofs (VP) because they are more secure than FP. This post points out a few additional benefits that VP have over OR and corrects common misconceptions about VP, and about StarkEx — StarkWare’s STARK-based VP scalability engine.

  • 1000X more capital-efficient for withdrawals
  • More scalable (on-chain)
  • At least as efficient, computationally

Security

In our previous analysis we compared VP, where state transitions occur strictly across valid states, to OR, where any state transition is allowed (hence: optimistic), and participants can submit proofs of fraud, i.e. of invalid state transitions. Ours was essentially a security analysis, and pointed to a well-defined attack on OR, an attack which results in all funds being stolen from the OR (additional possible attacks continue to be deliberated). Infrastructure solutions offered for blockchains must be resilient enough to haul the full load of the financial world, where $Ts are transacted daily. How do VP and OR measure up to this task? Since the cost of stealing funds from OR is unrelated to the bounty size, rational agents are bound to break the system once substantial value is placed on it. In contrast, VP cannot be moved to an invalid state and funds cannot be stolen, irrespective of the bounty size. For large-value financial systems, VP is sturdy, OR is likely to break.

Capital Efficiency

One painful problem with cryptocurrency liquidity is the delay associated with funds withdrawal. In OR, the standard withdrawal window is ~1 week — the expected duration for submitting fraud proofs (a security parameter). In VP the standard withdrawal window is ~10 min (and likely much less, with additional software and hardware improvements) — the duration of producing a proof attesting to the integrity of the latest computation. The standard withdrawal window for OR is therefore 1000X longer than for VP (as 1 week / 10 minutes ~ 1000). This 1000X penalty must be paid when using OR, whether that penalty is denominated in capital efficiency or in duration.

  • Shielded transactions: A Zerocash-style commitment is also non-fungible, in a way. To activate a fast withdrawal when moving a shielded token back to the main chain — where it is to remain shielded — the user would have to reveal a particular commitment to the liquidity provider.

Scalability (On-chain)

In this section, so as to compare apples to apples, we will consider only rollup systems, where by definition data is available on-chain: OR vs. STARK ZK-Rollup (StR). Any solution that stores data on-chain has the undesirable property of on-chain resource consumption growing linearly with the volume of rollup transactions. On-chain data includes some state (e.g. transaction details) and a witness (e.g. digital signatures that prove the consent of the transacting parties). The difference between OR and StR is that OR witness scales linearly with the number of transactions whereas StR replaces all those witnesses with a single proof that scales poly-logarithmically with the number of transactions. Importantly, for sufficiently large batches, StR’s on-chain data footprint is significantly smaller than OR’s..

General Computation Overhead (STARKs Get Better as They Get Older)

One comparison often made between VP and OR has to do with their computational overhead: for a given computation to be carried out off-chain, how much more work is required in each approach? We will focus on StarkWare’s STARK capabilities, as that is the VP framework we’re currently implementing.

  • For operations such as SHA-256 there is indeed considerable overhead, but we intend to replace these hash functions with STARK-friendly ones. We were funded by the Ethereum Foundation to do so, and expect the selected committee of academic cryptanalysis experts to issue its recommendation in Q1 of 2020. We expect the selected STARK-friendly hash function to be about 100X slower to prove than an efficient hash (e.g SHA-256) computation.
Image for post
Image for post

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