Why Starkware matters: Zero Knowledge Proofs and the Search for Scale and Privacy in a Blockchain World

Cryptocurrency reminds me a great deal of what the Internet felt like back in 1992. At that time, my friends and I would dial into Compuserve and chat with one another in a MUD that another friend had written. There was a relatively limited audience that was online at the time since Netscape would not release its first browser for another two years. Similarly, while the core technology behind crypto continues to be fascinating, for the reach of applications built on blockchain to be utilized by the masses, we must build additional robust infrastructure and applications. This fascination with the foundational elements of what we see being built in cryptocurrency and blockchain is the reason I chose to make the largest investment Floodgate had done to date in the crypto space into Starkware in the first quarter of this year.

Blockchains reinvent trust

Blockchain solves one of the internet’s most exciting and high leverage problems: how do you make trust more easily accessible or potentially irrelevant? It’s a problem that has shown up again and again in a world where we transact increasingly with people and institutions we have never seen or met — how do you establish trust? Early e-commerce sites needed to convince users to trust them with their payment information. Platforms like eBay built reputation systems that gave people the confidence to buy from other users. Moreover, today, companies like Lyft use ratings, driver verification and other methods to ensure that their riders and drivers have a positive experience. However, in each case, we built trust in others by placing our faith in eBay or Lyft or Paypal or some other institution.

Trust, in other words, is mediated by a third party and is built on reputation and a history of mutual experience. Trusted intermediaries like this can reduce risk and friction by supplying a platform for transactions, but they also increase transaction costs. Through the use of a publicly distributed ledger, blockchain provides a mechanism to democratize the notion of trust by replacing the fuzzy notion of reputation with the more concrete verifiability of information. It democratizes trust.

But blockchain has limitations today

In the process of democratizing trust through blockchain, two critical problems have emerged: privacy and scalability.

Verifiability has enabled us to democratize trust, but we have lost true privacy. While blockchain is pseudonymous, it is not anonymous. It is akin to having a pseudonym under which users make transactions. If the alias is revealed for any reason, all of the transactions under that pseudonym are revealed.
Today, web trackers and cookies send information about purchases and browsing behavior to third parties that can be used to know more about the users behind transactions done on commerce sites using cryptocurrency, namely Bitcoin. In one recent paper, Steven Goldfeder, Harry Kalodner , Dillon Reisman, Arvind Narayanan show how this information can be used to de-anonymize users of cryptocurrency. Given the information available about the time of purchase and purchase amount as well as the other parties with which transactions are happening, revealing one user may result in other users also being unintentionally exposed. This lack of security concerning the anonymity of transactions is problematic for individuals, but for enterprises, this can be a real show stopper — especially for publicly traded companies where current information on sales or cost basis is proprietary and can create volatility in stock prices.

The second reasonably well-understood problem is concerning the scalability of blockchain. Blockchain has inherent limits based on block creation time and block size. For bitcoin, the capacity for transactions is roughly seven transactions per second while robust payment networks like Visa process thousands of transactions per second. Aside from Ripple which can handle 1500 transactions per second, most cryptocurrencies today are managing tens of transactions per second. Clearly, for enterprise level applications, these currencies need to find ways in which they can scale universally.

Enter Starkware and Zero Knowledge Proofs

Starkware was founded by an all-star team consisting of Uri Kolodny, Eli Ben-Sasson, Alessandro Chiesa and Michael Riabzev. The core technical team are some of the early academics that pioneered SNARKs, a type of zero-knowledge proof that powers Zcash, a privacy coin. They are a powerhouse with stars from Technion and Berkeley. Starkware is creating the software implementations for STARKs (zero knowledge scalable, transparent arguments of knowledge) which produces a proof that a complex computation was done correctly. A notable characteristic of this proof is that it can be verified in a fraction of the time that it takes to run the actual computation. It is also possible to create a recursive STARK which then bundles the proofs and establishes a meta-proof for that bundle creating further computational efficiencies.

Zero-knowledge proofs themselves are quite elegant in concept so let’s take a moment to dive deeper into what they are.

Heroine of Cryptography and Zero Knowledge Proofs

When the history of cryptocurrency is written someday, alongside the contribution of the mysterious figure Satoshi Nakamoto or the charismatic co-founder of Ethereum, Vitalik Buterin, or others, I hope that we will also focus on the often overlooked stories surrounding computational theory that has formed the underpinning of modern cryptography and thus, cryptocurrency. One heroine in that storyline will be Shafi Goldwasser. Goldwasser is the 2012 Turing Award winner (the Nobel Prize of computing), and she is a world leader in the theory of computation as a co-inventor of probabilistic encryption and zero-knowledge proofs.

Zero-knowledge proofs are one of the most powerful tools created in the field of cryptography. Zero Knowledge Proofs were created within the area of computational complexity theory and interactive proofs. Researchers were looking at the problem in which provers (someone trying to show the truth of a particular mathematical computation) and verifiers (someone who is to be convinced that a mathematical computation is correct) interact and what types of protocols could be both complete and sound. Most of the research was focused on a malicious prover trying to trick an honest verifier into verifying a false statement. Goldwasser along with her two colleagues Silvio Micali and Charles Rackoff posed an unusual question: what happens if we don’t trust the verifier and thus want to limit the information we reveal to the verifier. In other words, how much data needs to be disclosed to the verifier if the only output we seek is a verification that the computation is true or false. It turns out that proof of knowledge does not require the revelation of that knowledge.

While the mathematics is quite complicated, there are visual ways in which the concept can be explained. One of my favorites is called the Ali Baba Cave. In this example, we establish proof of knowledge of a secret password for a door inside a circular cave without divulging the password. Suppose there is a cave that looks as follows:

There is the mouth of the cave (point A) and an entry path into the cave that then splits in two at point B. Path 1 and Path 2 wrap around and meet at a secret door that can only be opened by a password. Now suppose that Peggy (the prover) knows the password to the secret door and needs to establish this with Victor (the verifier). The following process would show to Victor with high probability that Peggy knows the password:

1. Victor waits at point A as Peggy goes into the cave.
2. Peggy takes either Path 1 or 2 without Victor seeing which path she took
3. Victor moves to point B and shouts to Peggy on which way she should return (Path 1 or 2) and observes on which path Peggy returns

If Peggy knows the password to the secret door, this should not be a problem as she can open the door if necessary to return on the correct path. If Peggy does not know the password to the secret door, she would have to return on the same path she took and inevitably, she would return on the wrong path roughly 50% of the time. In other words, the probability that she could anticipate Victor’s path requests correctly multiple times becomes smaller and smaller with each request. This protocol illustrates the following:

1. Interactive: The proof is established through activity between Peggy and Victor
2. Zero Knowledge: Victor cannot learn the secret password following this protocol
3. Complete: If Peggy knows the secret password, she will be able to complete the proof
4. Sound: If Peggy does not know the secret password, it is highly unlikely that she will be able to pass multiple rounds
5. Repudiatable: The protocol manages to keep hidden from everyone except Victor whether Peggy knows the password. In this case, an observer might believe that Victor and Peggy had colluded and agreed upon the asks he would make so that she appears to know the password which ultimately means proving her knowledge to Victor doesn’t mean revealing her knowledge to anyone else.
6. Non-transferable: Victor cannot copy the proof without knowledge of the secret password

Zero-knowledge proofs prove that, probabilistically, it is highly likely that a particular computation (e.g., a transaction occurred) is indeed valid.
This is important for blockchain technology because now it enables us to keep the nature of the transaction private because we can verify that the transaction occurred using zero-knowledge proofs. Because verification of the proofs is comparatively computationally light, it becomes possible to scale the blockchain in a way that was not possible as we recursively stack these proofs.

The elegance of this solution, as well as the team behind Starkware, made me a believer earlier in 2018. As we near the ten-year mark of bitcoin’s launch, the potential for blockchain and the core concepts it supports has momentum, especially with talented developers that I haven’t seen in some time. Many of these applications would benefit from a fully public blockchain but require privacy at the transaction level and greater scalability whether they are in finance, healthcare or other applications. The time is right for a company that can solve this set of problems. That’s why I’m so excited about the work Starkware is doing to bring zero-knowledge verification to the blockchain. As an investor and an academic, there’s nothing that brings me greater joy than watching research leave the lab and make an impact on the world, and I’m thrilled to join the Starkware team on this journey.