The Magic Behind ZK-SNARKs: Part III of Our Review of Technical Approaches to Anonymity in Cryptocurrency

Leo Zhang

By Leo Zhang

Tags:

You're reading Part III, which covers zero-knowledge proofs and Zcash. Part I introduced the concept of anonymous transactions, methods to deanonymize Bitcoin transactions, and techniques to enhance Bitcoin privacy. Part II covered the CryptoNote protocol.

What is a zero-knowledge proof?

In recent years, as "the cloud" popularized, individuals and enterprises have begun to migrate large quantities of data outside their premises. This trend raises concerns about the integrity and confidentiality of computations conducted on this data (please see our related research on Decentralized Storage Networks for more information).

In the real world and in mathematics, to prove a statement is true, the Prover must present all the facts and inferences they can muster, which imply the statement is true. However, this may involve revealing a lot of information about the Prover in the process.

In the abstract, a zero-knowledge proof tries to present its proof without divulging any characteristics about the party submitting the proof. Consider the following example:

Picture31-1

X is a set of sensitive financial data, and f is a public function. Let’s say an external party wish to obtain the output Y to run analytics. The corporation must make sure X is confidential throughout the process. Meanwhile, the third party needs to make sure the integrity of the output in case Y:=f(X) is used in critical analytical decisions.

The Ali Baba Cave is a popular illustration of the proof process. Suppose Peggy needs to prove to Victor that she knows the password to a secret door without revealing the actual password. Peggy enters the cave without revealing which path (A or B) she chose. Victor shouts one of the two exits outside the cave. If Peggy shows up at the correct exit, it means there is 50 percent chance she actually knows the password. After repeating the trial numerous the probability of Peggy knows the code will converge to 100 percent.

Another example is the color-blind verifier. Suppose the Verifier is incapable of distinguishing a red ball from a green ball. The Prover needs to prove that she is not color-blind without telling the Verifier which ball is which. The proof process follows the steps below:

1.Verifier shows the two balls to Prover. The Verifier sees the two balls as identical.
2.Verifier hides the ball behind his back. He randomly decides to swich the balls or not.
3.Verifier shows the balls to Prover again. The Prover will say if the Verifier switched hands.

From the Verifier's perspective, there is 50% chance that the Prover just guessed if he switched behind his back. Repeating this process for sufficient number of times reduces the soundness error to minimum. Following this protocol the Prover can prove she can indeed distinguish red and green, and the Verifier still doesn't know which ball is which.

A slightly more complex example is Sodoku solution. The Prover needs to show she knows the solution to a Sodoku problem to a Verifier without revealing the answer. Researcher Aviv Zohar does an excellent job breaking down the process in his article The Incredible Machine.

Background of zero-knowledge proofs

The concept of zero-knowledge proof was first introduced by Goldwasser, Micali, and Rackoff in 1985. Today, zero-knowledge proofs have become a fundamental component in modern cryptography, and is widely used in many protocols.

GMR’s original paper is the first proposal to show it is possible two send zero knowledge by proving it interactively. In mathematics, a classic proof must satisfy the following conditions:

  • Verifier can compute the proof efficiently and mechanically.
  • It is impossible to prove a false theorem true.

Classic proofs are non-interactive. By introducing interactive Q&A and randomness in proofs, GMR made profound influence on computer science. Another innovation that contributed to interactive proofs is garbled circuits, first proposed by Chi-Chih Yao. In cryptography, proving a statement is really proving something over an arithmetic circuit. We have to convert the program into the arithmetic circuits. The construct of garbled circuits allows multiple parties to compute and publish the results without revealing their private inputs. Suppose two billionaires want to compare who is wealthier, but neither wishes to disclose the exact amount of assets. Using garbled circuits allows them to safely compare their net worths.

Picture32

In real world, interactive proofs are much more common. On a court the judge and defendant exchange questions and answers for multiple rounds to produce the proof if the defendant is guilty or innocent. When two spies meet for the first time, they usually have to exchange a series of secret phrases to confirm each other's identities.

At its core, the goal of zero-knowledge proof to cryptographically demonstrate a solution to a problem, without revealing the solution itself. Typically in a setting that the Prover is unbounded but the Verifier is limited in computation resources. A zero-knowledge proof must satisfy the following properties:

Completeness: if the statement is true, the honest verifier will be convinced of this fact by an honest prover.
Soundness: if the statement is false, no cheating prover can convince the honest verifier that it is true. In practice, soundness is probabilistic. Soundness error could occur with slim probability.
Statistical zero-knowledge: if the statement is true, no verifier learns anything other than the fact that the statement is true.

The introduction of the ZK-SNARK

While the concept of interactive proof is highly innovative in cryptography, often time they require a majority, or all corresponding parties to be online simultaneously, which can be difficult to organize. In addition, proofs of such complexity are usually too large to be wielded in practice.

In 2010, Jens Groth implemented the first non-interactive zero-knowledge protocol in polynomial time. This implementation was later developed into Zero-knowledge succinct non-interactive arguments of knowledge, or ZK-SNARKs, which are like engines that can quickly and efficiently verify a transaction without revealing any details. On a high level, the engine compiles the required program down into a Quadratic Arithmetic Program. If the program is computed correctly, the QAP equation holds. The Prover needs to convince Verifiers such equation holds. Two related notions are:

Proof-of-Knowledge: Interactive proofs in which the prover asserts “knowledge” of some object and not merely its existence. For instance, the solution to a sodoku problem is "knowledge". Proving that one knows the solution, is the proof-of-knowledge. Proof-of-Knowledge is the foundation for Schnorr Signature.

Non-Interactive Zero-Knowledge the proof: consists of a single message that can be verified by anyone. NIZKs only exist for all languages in NP if a trusted party is available for a one-time setup phase. We will go over the role of trusted setup later. For more rigorous definition, see Secure Sampling of Public Parameters for Succinct Zero Knowledge Proofs.

The Implementations of Zero-knowledge Proofs

Picture33

Zcash is an open-source project maintained by Zerocoin Electric Coin Company, or Zcash Company. The company is led by a group of top cryptography researchers including Eli Ben-Sasson, Matthew Green, and Eran Tromer.

How Zcash uses ZK-SNARKs

Unlike Monero, Zcash is not private by default. There are two types of addresses available for Zcash users: t-address and z-address. Value in t-addresses are transparent, just like Bitcoin transactions. On the other hand, value in z-addresses are shielded. Users have the option to choose between the transparent and shielded address. When sending and receiving Zcash using shielded addresses. The process generates a zero-knowledge proof which allows others to verify a transaction’s encrypted data without it being revealed.

Picture34

(Source: Zcash blog)

Public parameter generation ceremony

The trusted setup is a vital part of what makes the ZK-SNARKS engine work. The trusted party runs a probabilistic polynomial time generator algorithm. This (Ceremony) will generate a public parameter, or Common Reference String, that is used to create anonymous transactions and verify those proofs. As in the public-key cryptography, a pair of (private, public) is created. However, if an adversary knows the private key, he can counterfeit new tokens without anyone knowing. Users have no choice but to trust the group responsible for generating parameters to destroy the secret. That is why the ceremonies need to be extremely carefully ochestrated. In Zcash protocol, multiple trusted parties each generate a shard of the keypair, destroy their shard of private key, and combine their shards of public key to create the public parameter. The public key is essentially a sequence of group elements: (𝑔,𝑠∗𝑔,𝑠^2∗𝑔,𝑠^3∗𝑔,…,𝑠^𝑑∗𝑔). The trusted parties will generate the group elements in a way that none of them will know s. The participants will follow a protocol to exchange the product of generator g and some randomly chosen numbers. Private key s is the product of these randomly chosen numbers. (Source: ZCash Blog ) As long as one of them follows the protocol correctly, the group elements will be of the right form. If at least one participants destroy their private key shard, then the full private key will not form.

The computer generates pseudo-random numbers by taking certain physical parameters as seeds for entropy, such as CPU clock, mouse movement, or the CPU's internal temperature. If the pseudo-random number generation process is compromised intentionally or unintentionally, the private key will no longer be secure. The latest Zcash ceremony is called Power of Tau. Developers used radioactive toxic waste from the Chernobyl nuclear disaster site--specifically, a radioactive graphite moderator--as the source of the entropy for the random number generator.

Picture29

The CTO of Zcash Company destroying a computer used to generate the public parameter. (Source: IEEE)

For rigourous walk-through of the mathematics, see the From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again, in which the acronym ZK-SNARKs was first introduced. The original Zerocoin whitepaper is also very helpful to read.

Zcash in summary

A recent study based on the Zcash blockchain explorer shows that only 19.6% of transactions are actually using z-addresses. Furthermore, 98.1% of these transactions moved between t-addresses and z-addresses. The process of moving tokens between t-addresses and z-addresses makes Zcash transactions vulnerable to linkability analysis(see Part I). Network statistics shows on average only 3.5% of the coins are actually shielded, suggesting full anonymity is rarely used, and the cryptocurrency market overall is still very much in an early speculative phase. Nonetheless, ZK-SNARKs is a powerful technology, if the transaction addresses are employed with shielding feature, theoretically the transaction would be entirely anonymous, revealing nothing about senders, recipients, or transaction values.

Zcash requires a trusted set up stage that can be cumbersome. If the process is compromised, malicious actor can damage the integrity of the system without anyone knowing. Researchers are working on a protocol called ZK-STARK. By switching to much simpler cryptographic tools, ZK-STARK eliminates the need for the trusted setup. This still only exists in a theoretical framework. No sign of real implementation at the time this article is written.

SNARKs are quite efficient--for programs under certain size, the proof size is basically constant around 300 bytes. The proof size is 3(logd+logS), where d is the number of multiplication gates in circuits and S is the security parameter. Zcash is working on a new hardfork called Sapling. It is an upgrade that redesign the circuit system to enhance performance of the network. According to a Zcash scientist, the proving time will shrink from ~40 seconds to 4 seconds under Sapling; and RAM usage will decrease from >3GB to 40MB.

Comparison of Monero and ZCash

Picture40

As for different proof systems, it is pointless to compare which is absolutely "better". The consideration is always on the tradeoffs between performance, size, and security. In terms of implementation, Monero and ZCash are both excellent projects. Monero is community-driven, well-maintained, and is led by a group of very capable engineers. Zcash deploys the most ambitious zero-knowledge system ever used in production but requires the trusted setup. At this point it is preemptive and pointless to make a judgement on which will ultimately "win-out".

Ethics of Anonymous Cryptocurrency

In Part I we discussed the necessities of privacy in financial transactions. Full anonymity could also facilitate criminal activities or terrorism. What is the optimal way to preserve the security of a private system while allowing enforcement agencies to detect illegal activities? The challenge is that, technology itself is moral-agnostic. What we deem as just or corrupt is identical to machines. The nature of this inconsistency is profound and will likely never be resolved in perfect ways. Moreover, the benefits and security anonymous technology provide warrant its existence. The challenge will always be there, but it doesn't mean we should stop working on the next iteration.