StarkWare
Now that we’ve lifted the veil on Collaborative’s crypto investing efforts, we plan to start providing some commentary on our recent investments since we kicked off last year. We’ll be putting out several of these posts in the coming weeks, starting with one of our first investments, in a company called StarkWare.
We joined with Paradigm, Sequoia, Coinbase Ventures, and other investors in Israel-based StarkWare’s Series A. Co-founded by Chief Scientists Eli Ben-Sasson (Technion) and Alessandro Chiesa (UC Berkeley), CEO Uri Kolodny, and Chief Architect Michael Riabzev, StarkWare is solving the most important common problems of public blockchains today, scalability and privacy, with a full proof stack using zk-STARKs, a new form of cryptographic zero-knowledge proof that overcomes many of the barriers that have made use of this class of solutions impractical in the past.
Most public blockchains today (including Bitcoin and Ethereum) are structured as a complete, totally transparent public record of all mined transactions since the genesis block. This provides a way for any actor to verify that their coins have a valid spending history, but this also means that all transactions must be replicated on every node—making these platforms difficult to scale to high transaction throughput—and also that all transactions are not private (no, pseudonymous addresses do not provide strong privacy protection).
Generally speaking, zero-knowledge proofs provide a way of succinctly proving that a known function has been correctly applied to some input data, without revealing anything about the input(s). This has obvious applications to privacy, which we’ll touch on later, but the more interesting application for StarkWare in the near term is scalability. This property of condensing any general function call on input data into a single compact proof also makes zero-knowledge proof systems incredibly powerful tools for trustless “batching” of transactions. STARKs offer this without the drawbacks of other zero-knowledge proof systems that require trust in a 3rd-party setup that can be compromised or are prohibitively slow, or other “layer-2” solutions that require parties to be always online in order for the system to progress securely.
Earlier this week, StarkWare announced that their alpha build of StarkDEX is live on Ethereum’s Ropsten testnet. Built in collaboration with p2p exchange protocol developer 0x, StarkDEX is the first deployed implementation of their zk-STARK scalability engine, and it’s great to see the early results coming in. At maximum capacity, the system is able to batch-process over 550 exchange transactions at present, vs. Ethereum’s ~3 TPS limit, at less than 1% of the native gas cost per transaction. And they’re coming for payments next.
In addition to the significant advancements in scalability of trustless exchange, the privacy enabled by zero knowledge proof based financial systems is something we believe will come to be as important if not more so in the future. A cryptographically secured distributed ledger is a powerful and transformative tool for disintermediating trust to supplement, enhance, and replace existing financial infrastructure. However, the way in which most major blockchains to date have implemented this ledger at the base layer creates new issues of its own. It is well-established at this point that the usage of pseudonymous addresses in Bitcoin and other protocols does not achieve meaningful levels of anonymity or financial privacy, even when following recommended best practices. The lack of financial privacy is a significant pain point barring future adoption of public blockchains as foundational infrastructure by major financial institutions. There are several existing projects that have worked to build stronger privacy guarantees into public blockchain protocols, but each has its limitations.
For mainstream financial markets, scalability and privacy are not optional. Some degree of privacy for individuals and institutions is an integral part of trust in the functioning of a healthy financial system. The current-generation model of transacting using pseudonymous addresses and verification through simultaneous re-execution of transactions in the public distributed ledger will not be sufficient to address the need for scalability and privacy as more and more assets move onto cryptographically secured network protocols. We believe the technology in development at StarkWare will be fundamental to the crypto-powered financial infrastructure of the future. While this can all sound a bit crazy at times—co-founder Eli himself refers to this tangled branch on the cryptography/theoretical CS family tree as “moon math”—zk-STARKs are very real, and they are here.
We believe that 1) efficient verifiability of off-chain computation (such as in the scalable decentralized exchange and payments use cases), and 2) transparent privacy, will be essential ingredients in crypto-based financial systems in the future. The technology developed by the team at StarkWare solves for both at once. Eli, Alessandro, Uri, and Michael are a top-notch founding team of cryptographers, computer scientists, and entrepreneurs with incredibly deep experience and knowledge in the area of zero-knowledge proofs, and we couldn’t be happier to be along on this journey with them.
For more general reading on StarkWare, zk-STARKs, and zero knowledge proofs in general, see StarkWare’s website and blog. For more technical information, see the original zk-STARK paper by Eli & Michael plus colleagues at Technion and Cornell; StarkWare’s STARK math series of posts; Vitalik Buterin’s series of blog posts (part 1, part 2, part 3); and a hands-on tutorial for a basic zk protocol in Python from StarkWare engineer Shir Peled here.
P.S. For those curious to learn more about zero-knowledge: an introductory story about Ali Baba and zero-knowledge protocols (from Jean-Jacques Quisquater; images Wikimedia):
Once upon a time, Ali Baba, in a series of unfortunate encounters with some thieves, discovered a magical cave they were using for a hideout with a quick getaway. It had two winding passageways, one branching off to the left of the entrance, the other to the right, meeting opposite the entrance to close in a ring shape. At the opposite end of the ring-shaped passageway from the entrance there was a wall with a magic hidden door joining the two sides, locked with a secret password: “Open Sesame”.
Every day, a thief would steal Ali Baba’s basket in the bazaar and run away, fleeing into this cave when he gave chase. And every day, Ali Baba would run down one passageway or the other, choosing randomly as he was never sure which route the thief took. But whichever pathway he chose, day after day, he would only come to a dead end, never catching the thief. After a few weeks of this, Ali Baba realized these thieves must be extraordinarily lucky. If both they and he were choosing one side randomly, he reasoned, they’d have one-in-a-million odds of having gotten away consistently for this long. So, Ali Baba cleverly hid himself in a basket near the wall, waited for another thief to come along, and learned of the secret door and the magic words.
Now suppose we have two travelers who have come upon the cave, Peggy (the prover) and Victor (the verifier). Peggy has heard the story of Ali Baba and knows the secret password to the hidden door, and wants to convince Victor of this fact, but without revealing the password to him, since that would spoil the fun.
And so they play a game. First, Peggy uniformly at random takes one of the two paths, while Victor waits outside the entrance so he cannot see her choice. Then, he chooses a path (also uniformly at random) and, standing at the fork, shouts to Peggy which path she should exit by, and Peggy must come out at the entrance Victor names. If Peggy really does know the password to the magic gate, this will be easy for her - if she’s on the wrong side, she can simply cross through the magic gate to appear at the desired exit. If she does not know the password, on the other hand, she only has a 50% chance of being correct each time.
By extending this to multiple repetitions, Peggy’s probability of being correct every single time if she does not actually know the password diminishes rapidly - it halves with each additional repetition. So, after only ten repetitions, if Peggy is repeatedly able to appear at the desired exit, Victor can be 99.9% sure that Peggy does indeed know the secret password, despite Peggy never having revealed it to him.
This is the principle behind zero-knowledge protocols. The prover says or does something to convince a verifier, to within an astronomically small probability they could be lying, that they possess a certain piece of knowledge, or have executed a certain series of steps, without revealing the “secret sauce”. Peggy and Victor’s game is an example of an interactive protocol for this particular problem instance; STARKs (and other related types of zero-knowledge protocols) are applicable to general computation (not just opening a door), and convert a simulated history of randomized interactive games into a non-interactive proof - a single output that can be efficiently verified.