ZKP can be used for much more than just privacy. ZKPs are so versatile that it may redefine how blockchains work.
There are many technical blog posts about Zero Knowledge Proofs (ZKP). I recently wrote one myself comparing the new general purpose zk-SNARKs. I noted there's a lack of non-technical posts on the use-cases of ZKP.
Part 1: Succinct blockchain, from gigabytes to kilobytes
Blockchains can be big and continuously grow in size every block. That’s by design. We have come to accept that this is the way it is. However, Coda’s recent testnet is different. First of all, Coda’s blockchain is fixed size. It doesn’t grow. Secondly, it’s only 22 kilobytes (!) in size. It would easily fit in a 1980s Commodore 64 or ZX Spectrum.
Yet Coda is as secure, or arguably even more secure than traditional blockchains. And more projects are following: Mir and Starling (I’m part of Starling) will launch similar but more versatile ‘succinct blockchains’ soon. How does it work?
Anyone who has ever spun up a blockchain node knows the pain: It takes hours or even days to sync a node. Blockchains are often so large that disk space and bandwidth requirements are beyond what most people have at home. This is leading to centralization. Even a popular blockchain like Ethereum consists of only about 10,000 nodes.
Most of which are hosted on AWS and the nodes are owned by just a handful of entities. Blockchain isn’t as decentralized as many people think.
Why does syncing a blockchain take so long? There are two reasons. The first reason is obvious: It takes a while to download hundreds of gigabytes of data or more. Secondly, the blockchain needs to be validated after its downloaded, because a malicious node could have sent you incorrect data.
To validate a blockchain, it has to be replayed from the genesis block: execute the first transaction and confirm that the calculated state is equal to the downloaded state.
Move to the next transaction until you’ve checked every transaction in the blockchain. It’s time consuming and wasteful; tens of thousands of nodes have done exactly the same computations before you.
The reason this is necessary is because in traditional computing, the only way to know if a computation has been computed correctly, is to redo the computation. That’s fine for small computations, but it’s not great for slow calculations like replaying a blockchain.
ZKP to improve efficiency and bandwidth
It turns out there is a way to cheaply validate a computed result without redoing the computing: Zero knowledge proofs (ZKP), of which zk-SNARKs are probably the best known ones.
How would it work? We’d have to rewrite the blockchain replay function as a zk-SNARK. The zk-SNARK will output two things: the original output (just like the original replay function) and a small mathematical proof that the result was calculated correctly.
The proof can be as small as 200 bytes (yes, that’s less than a kilobyte).
There is no need for all (or even multiple) computers to run the replay function. One computer can create the proof, an unlimited number of computers can validate at any time they see fit. Validation takes only a few milliseconds, no matter how long the original computation took (even hours, days, or years, it just doesn’t matter).
The proof can be distributed online, via a USB stick or even printed on a t-shirt for that matter.
If a malicious node changes a balance, the proof will not match the result and any validator will reject the state. If a malicious node changes the zk-SNARK code, the result will be rejected too. (There is a third parameter, a publicly shared string that ties the proof also to the zk-SNARK code.
If the code is changed, the proof and shared string won’t be matched and a validator will reject the result.)
We’ve eliminated the need to redo expensive computations, and there’s no need to download the blockchain anymore (as we already have the mathematical proof the blockchain exists and is valid). You only need the current state (e.g. the last block) plus a tiny proof that the current state is part of a valid blockchain and spend a few milliseconds to validate the result.
Recursive composition
It’s fast to validate a proof, but how about creating the proof? It turns out it’s not constant time, and it’s a lot less efficient in terms of computing and memory compared to traditional computing. In fact, while a zk-SNARK version of a replay function may sound good, it’s not a great solution in practice.
It will be huge in terms of memory and even slower than the original non-zk-SNARK replay function.
But there is another elegant solution. With a few tricks it turns out it’s possible to use recursive zk-SNARKs. With recursion, we don’t have to validate the blockchain from scratch, but we can build on top of the previous state.
That’s much faster. Note that recursive zk-SNARKs are less efficient than non-recursive zh-snarks, but recent zk-SNARK constructs have made huge strides.
A recursive zk-SNARK program uses the previous state, the proof belonging to the previous state and the new transactions as inputs. It validates the previous state (using the provided proof) and checks if the transactions in the new state are valid. If so, it will output the new state and a proof.
Once the new state and proof are distributed to the network, all nodes can simply discard the previous state without any negative consequences at all. New nodes only need to download the latest state and proof. This is how Coda, Mir, and Starling are able to have a tiny fixed-sized blockchain.
In our last example, only one node would create a new block and the proof. Obviously it isn’t necessarily that the same single node produces every block. For example, a node can be randomly chosen out of many nodes (with Verifiable Random Functions nodes can even randomly choose themselves without cheating). We could do even better.
We can divide the block producing logic into multiple zk-SNARKs.
The end result is block producers do not need the full blockchain, it only needs the previous state. How much smaller would such a solution be? A regular Coda node only needs 22 KB to store the proof, the current state, and the Merkle path to one balance.
With 22 KB, a node can validate the complete blockchain, query the balance, and create transactions. But to produce blocks, a node needs more: it would need the full balances Merkle tree of the previous state. The Merkle tree size is dependent on the number of wallets. If Coda would have as many wallets as Ethereum, a Coda block producer will still only need about 1 GB.
The smallest full node on Ethereum is (as of December 2019) 230 GB. A huge difference.
This way, the network has many more active nodes, increasing decentralization, and opens up many new possibilities of programs interacting with the blockchain without solutions like Infura or Metamask. And given that 99% of new users drop off before installing Metamask, that could have a huge impact.
Thanks for proofreading: Daniel Lubarov (Mir), Shane Vitarana, and Stan van de Burgt.
We’re hiring!
If you’re a Rust developer who’s interested in learning zk-SNARKs (but not necessarily have experience with zk-SNARKS): Starling Protocol is hiring. Starling is a programmable succinct layer one protocol based in Berkeley, CA. Starling Protocol is a diverse and inclusive workplace.
We encourage people of color, LGBTQ individuals, and women to apply. Email [email protected] for more information.
(Disclaimer: The author is a Founder at Starling Protocol)