2018 has become the year of privacy. In the US, Facebook CEO and Harvard dropout Mark Zuckerberg was hauled in front of Congress to give testimony on Facebook’s recent privacy crisis. In Europe, the General Data Protection Regulation (GDPR) was introduced on the 25th of May 2018, broadly redefining the individual’s right to his own data. Within hours of the new regulation coming into effect, users filed complaints regarding privacy violations against Google and Facebook.
In the world of cryptocurrencies, privacy is also becoming a dominant issue. Ethereum founder Vitalik Buterin for example, recently shifted his stance towards a “considerably more pro-privacy” position.
I made a comment buried in a reddit thread yesterday about how my views on privacy have changed over the last few years (I'm more strongly pro-privacy now), and was encouraged to signal-boost it. Here you go:https://t.co/dgy7X7YEzM pic.twitter.com/ebcqsiLz2x
— Vitalik "Not giving away ETH" Buterin (@VitalikButerin) May 27, 2018
Looking at the bigger picture, it is crucial that public figures like Vitalik put an emphasis on privacy. Ethereum, bitcoin and most other cryptocurrencies have always used transparency as a way of ensuring integrity. With users current privacy concerns in mind, a new solution needs to be found.
Most cryptocurrencies are in fact pseudonymous, meaning that members of a transaction are publicly visible in the form of their wallet addresses. Once the owner of a wallet address is known therefore, it becomes trivial to track that persons incoming and outgoing funds.
As transparency played such a significant role in the adoption stage, privacy concerns were historically put to one side as more pressing issues, such as scalability, where prioritized. In the wake of GDPR and growing privacy concerns from the general public, however this position is no longer tenable. Privacy has become one of the defining topics of 2018 and crypto needs to adapt quickly.
Luckily, zero-knowledge proofs (ZKP) are here to save the day!
What are zero knowledge proofs (ZKPs)?
In a nutshell, zero knowledge proofs allow Alice (the prover) to prove something to Bob (the verifier) without having to relay any information about the thing itself.
This can be done in one of two ways: 1) Interactively, or 2) Non-interactively.
Interactive zero knowledge proofs are a mind-bending technology first articulated in 1985 by MIT professors Shafi Goldwasser, Silvio Micali, and Charles Rackoff in their paper “The Knowledge Complexity of Interactive Proof-Systems.”
Three years after Goldwasser and co, Manuel Blum, Paul Feldman, and Silvio Micali added an important piece of research by discovering that zero knowledge proofs did not have to involve interaction, coining the term “non-interactive zero knowledge proofs”.
Regardless of which approach you take, however, all zero knowledge proofs rely on three key axioms:
-
- Completeness: If the statement is correct, an honest verifier will be convinced by an honest prover.
- Soundness: If the statement is incorrect, the prover cannot convince an honest verifier that it is true.
- Zero-knowledge: If the statement is correct, no cheating verifier learns anything other than that the statement is correct.
What are interactive zero knowledge proofs?
Now that we understand the key axioms underlying all zero knowledge proofs, let’s look at an example to illustrate their power. First, let’s assume you have a friend who is color blind. For reasons too complex to get into here, you are trying to prove to him that the two cups he is holding are identical apart from one being green, and the other being red.
In order to prove to him that they are distinguishable by color, you ask him to put the cups behind his back, holding one in each hand. Now you turn away while he chooses to either switch the cups or not.
You turn back towards your color blind friend while he brings each hand forward. You know that he switched the cups as the green cup is now in his left hand, while the red one has shifted to the right. Your friend now makes the statement: “I switched the cups behind my back.” Without having to provide any additional information therefore, you are able to verify this statement as correct.
Importantly, ZKPs are probabilistic. In the example given above, your color blind friend might say that the odds of picking the correct cup at random were 50%, attributing the validity of your statement to luck. Thus it is important for ZKPs to be repeated numerous times, until the odds diminish and the probability of continuously guessing the correct answer becomes close to zero. For this reason ZKPs require large amounts of computational power, and are therefore quite costly.
The example described above shows us that it is possible to prove something without giving any information about the thing itself in an interactive way. This is therefore called an interactive zero knowledge proof.
Zero knowledge proofs and the blockchain
Typical transactions performed on the bitcoin and ethereum blockchains can easily be de-anonymized. As more users look for the ability to perform transactions in private therefore, an increasing number of protocols have been introduced to meet that demand.
In ethereum’s case, the most significant came through the Byzantium hard fork in October 2017. Specifically, the Byzantium update included EIP196 and EIP197, which permitted zkSnarks for the first time.
What are zkSnarks?
I have good news and bad news. The good news is that the definition of zkSnarks fits into a tweet:
Generator (C circuit, λ is ☣️):
(pk, vk) = G(λ, C)
Prover (x pub inp, w sec inp):
π = P(pk, x, w)
Verifier:
V(vk, x, π) == (∃ w s.t. C(x,w))— Christian Lundkvist (@ChrisLundkvist) November 19, 2016
The bad news is that this definition is of limited value to most people (like me). Instead, let’s bring it down a notch and describe it in more digestible terms.
In brief, zkSnarks are the preferred way of implementing zero knowledge proofs on the blockchain.
As you have already guessed, “zk” stands for zero knowledge. “Snark” stands for “succinct non-interactive arguments of knowledge.” Let’s take a look at this acronym in more detail:
- Succinct: The messages are very small in size
- Non-interactive: In contrast to the cup example provided above, zkSnarks rely on no or little interaction. In order to achieve this, zkSNARKs typically require a setup phase. Once the setup is established, a single message is sent between the prover and the verifier.
- ARguments: This refers to the verifiers’ limited protection. Indeed, Provers with sufficient CPU power at their disposal can generate false proofs.
- of Knowledge: The Prover needs to know about the relevant witness in order to be able to construct a proof. This could be the address he wants to use to spend, or the path to a specific Merkle-tree node for example.
zkSnarks implementation in Zcash
Interestingly, the first cryptocurrency to use zero knowledge proofs was Zcash. Here, two different blockchain transactions are available: transparent and shielded. Transparent transactions are the publically viewable iterations you are used to seeing with most crypto transactions.
Shielded transactions on the other hand, allow members of a transaction to keep specific data private. This gives Zcash holders the opportunity to pick between both public and private transactions.
Finally, Zcash has helped to develop the first Zero Knowledge Security Layer. This fascinating new technology lets Enterprises quickly implement zkSnarks through a plug-and-play secondary layer.
Criticisms of zkSnarks
Although zkSnarks have quickly become the new standard for privacy in the blockchain space, the technology is not without flaws. These are detailed in a recently published paper by the International Association for Cryptologic Research. ZkSnarks:
- require a complex setup phase performed by a trusted party.
- rely on non-standard cryptographic assumptions.
- incur significant costs.
With these issues in mind, it’s understandable why many privacy focused cryptocurrencies like Monero have stuck to alternatives like Ring Confidential Transactions.
Interestingly, a new piece of research titled “doubly-efficient zkSNARKs without trusted setup” claims to show: “a succinct zero-knowledge argument […] with no trusted setup and low concrete cost for both the prover and the verifier, based on standard cryptographic assumptions”
If these findings are verified, it could be a momentous breakthrough for the field of cryptography.
The emergence of zkStarks
In January of 2018, an Israel-based startup called Technion published a whitepaper introducing the concept of zkStarks. According to the whitepaper, these offer a “trustless” way of providing zero knowledge proofs, meaning they do not require a setup phase.
Additionally, zkStarks may prove to be a significant step in the evolution of privacy focused blockchain solutions, because the protocol manages to compress large amounts of information into tiny proofs. This would remove problems #1 and #3 listed above, and therefore represents an important step forward.
Finally, Technion claim that zkStarks are quantum proof, meaning they cannot be broken by super fast quantum computers.
Conclusion
Zero knowledge proofs are an ingenious way of ensuring privacy on the blockchain. Zcash and Ethereum have successfully implemented protocols which use this technology and many more will follow.
Research on this topic has yielding great results, and if recent findings hold up to scrutiny, we will soon see further stages in the evolution of this technology. More specifically, either researchers will solve the three key issues surrounding zkSnarks, or it will be replaced by zkStarks.
Whichever solution ends up winning the day, 2018 will forever be the year in which crypto started crushing it on privacy.
Nice article! A small correction – The Technion is not an Israeli startup. It is the Israel Institute of Technology.