How Zero Knowledge Proofs Are Changing Blockchain (in non-technical terms)

Ronald Mannak
Dec 24, 2019 · 6 min read
Image for post
Image for post

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. ZKP can be used for much more than just privacy. ZKPs are so versatily that it may redefine how blockchains work.

Part 1: Succinct blockchain, from gigabytes to kilobytes

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

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

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 zk-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 proof reading: Daniel Lubarov (Mir), Shane Vitarana, Stan van de Burgt, Taariq Lewis, and Dmitriy Berenzon.

We’re hiring!

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

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