Secrets and how to prove them: A magician’s guide to zero-knowledge proofs
Any sufficiently advanced technology is indistinguishable from magic (or so science fiction writer Arthur C. Clarke famously said). One such area of science-fiction-like progress is that of zero-knowledge proofs (or ZKPs), a cryptographic tool that addresses two critical challenges in web3: scalability and privacy. In particular, ZKPs could be the key to unlocking lower transaction fees, designing new privacy-preserving applications, and, as a result, welcome the next billion crypto users. Even beyond crypto, ZKPs may one day help transmit sensitive data securely, combat illicit finance, or fight disinformation.
But what are ZKPs? There are many clever explanations out there for engineers, researchers, and the crypto community, but they aren’t always intended for audiences with less experience in crypto or computer science. Even with the wealth of analogies available – from Waldo to Ali Baba’s Cave – it’s not easy to find an accurate, easy-to-grasp explanation of ZKPs that fully captures their superpowers.
So in this post, I combine my background in both crypto and magic to explore a new analogy: Think of ZKPs like a great magic trick. Check out the demo below, and read on for an overview of the defining properties (scalability and privacy) of ZKPs – and how all of this plays out using magic.
But first, some context: What are zero-knowledge proofs?
I’ll start by sharing a high-level definition of a ZKP (specifically one called a zk-SNARK), and its various properties before mapping those properties to the analogy of magic.
Expanding on a16z crypto research partner Justin Thaler’s definition of a SNARK: “A zk-SNARK lets someone (called a prover) prove to an untrusting party (called a verifier) that they know some data, without revealing anything about the data itself.” Or, alternatively, as the MIT AIP ZK Course phrases it, “Zero-Knowledge protocols allow me to prove to you that I know a fact without telling you the fact.”
This is exciting in the context of public blockchains because ZKPs can, at the same time, protect private information while allowing anyone to verify (without a doubt) that the information is true. zk-SNARKs are also succinct and work-saving: “Succinctness” means the size of the proof is smaller than the data you are proving you know. And “work-saving” means it is faster for the verifier to verify a proof than to analyze the original data itself (on Ethereum, this means smart contracts process less data so gas costs are lower for users). Layer 2 blockchains can leverage the succinctness and work-saving property of zk-SNARKs to allow decentralized applications to process more data, with lower costs.
In summary, zk-SNARKs have two main properties:
- privacy: Nothing about the data (or fact or “knowledge”) you are proving is revealed to the Verifier.
- succinct and work-saving: It is more efficient to verify the proof than to directly check the original data itself.
Even this high-level description sounds a little like a riddle: How can someone prove they know something without sharing their knowledge of it?
Let’s walk through this definition again… but this time, using some magic.
Magic tricks as zero knowledge proofs
To put it simply, magic tricks are zero-knowledge proofs. In a magic trick, a magician claims to know a secret that allows them to perform the illusion. But they don’t want to reveal this secret to their spectators – that would ruin the trick.
Extending this to ZKPs: Think of a magician as the “prover” and their audience as the “verifier.” A successful performance of a magic trick (hopefully followed by gasps of disbelief and wild applause) is analogous to a “valid” proof: The trick worked, so the magician must know the secret to performing it. Of course, if the illusion does not work, the proof is “invalid”: The audience is disappointed and the magician might not actually know the secret method.
So magic tricks demonstrate one property of a ZKP: privacy. But what about the properties of succinctness and work-saving? Let’s go back to the analogy…
A spectator could skip the show entirely and just ask the magician to share the secret method behind a trick. But magic secrets can be complex and elaborate. Even just explaining a trick’s method, with all its subtleties and nuances, can take a long time to grasp let alone understand. And sometimes, when asked to reveal their secrets, magicians might purposefully reveal a “false” solution to their spectators to lead them down the wrong path. Without mastering the trick on their own, spectators can’t be unequivocally sure that the secret method really works – and mastery could take days, months, or years.
So, just as directly checking the secret method for correctness is actually time and work-intensive – even if the magician were willing to reveal the secret to the spectator – so is the case for ZKPs. It’s much faster for the spectator to verify that the secret method works by simply enjoying the performance.
Unshuffling
As a quick example, in the video above I claim to know a secret method that allows me to instantly “unshuffle” a deck of cards. I want to prove to you that I have this ability without revealing how it works. The action of displaying an organized deck of cards at the trick’s conclusion is a valid proof that I must know a secret method to “unshuffle” cards. Also, you can instantly verify my claim when I show the organized deck, much faster than learning the trick yourself.
***
I hope this analogy has helped demystify zero-knowledge proofs. And that magic tricks and magicians hiding secrets can serve as a helpful mental model for understanding key properties of ZKPs, even for those who aren’t cryptography researchers or engineers.
Again: magic tricks are actually zero-knowledge proofs. And zero-knowledge proofs are indistinguishable from magic.
If you have more ideas for simply explaining zero knowledge or any other complex concepts in computer science, cryptography, or web3 more broadly (especially using a deck of cards) please share them with me on Twitter @blauyourmind or Farcaster @michaelblau!
Special thanks to Stephanie Zinn, Justin Thaler, Joe Bonneau, Tim Roughgarden, Guy Wuollet, Sam Ragsdale, Max Lukianchikov, Ali Yahya, Carra Wu, Jay Drain; Erin Brethauer, Tim Hussin, and Sonal Chokshi.
***
The views expressed here are those of the individual AH Capital Management, L.L.C. (“a16z”) personnel quoted and are not the views of a16z or its affiliates. Certain information contained in here has been obtained from third-party sources, including from portfolio companies of funds managed by a16z. While taken from sources believed to be reliable, a16z has not independently verified such information and makes no representations about the current or enduring accuracy of the information or its appropriateness for a given situation. In addition, this content may include third-party advertisements; a16z has not reviewed such advertisements and does not endorse any advertising content contained therein.
This content is provided for informational purposes only, and should not be relied upon as legal, business, investment, or tax advice. You should consult your own advisers as to those matters. References to any securities or digital assets are for illustrative purposes only, and do not constitute an investment recommendation or offer to provide investment advisory services. Furthermore, this content is not directed at nor intended for use by any investors or prospective investors, and may not under any circumstances be relied upon when making a decision to invest in any fund managed by a16z. (An offering to invest in an a16z fund will be made only by the private placement memorandum, subscription agreement, and other relevant documentation of any such fund and should be read in their entirety.) Any investments or portfolio companies mentioned, referred to, or described are not representative of all investments in vehicles managed by a16z, and there can be no assurance that the investments will be profitable or that other investments made in the future will have similar characteristics or results. A list of investments made by funds managed by Andreessen Horowitz (excluding investments for which the issuer has not provided permission for a16z to disclose publicly as well as unannounced investments in publicly traded digital assets) is available at https://a16z.com/investments/.
Charts and graphs provided within are for informational purposes solely and should not be relied upon when making any investment decision. Past performance is not indicative of future results. The content speaks only as of the date indicated. Any projections, estimates, forecasts, targets, prospects, and/or opinions expressed in these materials are subject to change without notice and may differ or be contrary to opinions expressed by others. Please see https://a16z.com/disclosures for additional important information.