Skip to main content

Zero-Knowledge Proofs (ZKP)

A specific, narrower aspect of Secure Computation is Zero-Knowledge Proofs (ZKP), which focuses on proving/disproving statements (i.e., yes/no questions only). The formulation of ZKP involves two parties of interest — a prover and a verifier. The goal is to have the prover prove to the verifier some argument, without revealing any other information.

The simplest type of ZKP are proofs of knowledge. In this version, the prover must show that he possesses knowledge of some secret information, without revealing it. If the rules of the game were different and we didn’t care about revealing the secret information, then the solution would be trivial — simply show the secret to the verifier. One significant real life example where ZKP are useful is authentication. One could prove his or her identity by showing they have knowledge of some secret passphrase or a key, without actually providing that secret directly.

Zero knowledge proofs could be summarized into three properties of interest –

These properties capture well the intuition of ZKPs — proving statements without revealing any side-information is possible.

Despite popular belief, the concept of ZKPs is not new and dates back to the 80s of the previous century. ZKPs have long been associated with MPC. The reason the two are interconnected is because both deal with private computation in an environment where multiple parties exist. In fact, ZKP is an important tool in implementing MPC that is also secure against byzantine faults — a generic term for describing nodes in a network that can behave in arbitrary (including malicious) ways. In this threat model, ZKP is used internally by the nodes running the secure multi-party computation protocols, to prove to each other that they have correctly performed the computational task at hand and that they have not revealed any secret information. On the flipside, MPC itself can be used to instantiate zero-knowledge protocols.

The recent interest in ZKP stems from the introduction of zk-SNARKs (zero-knowledge Succinct Non-interactive Arguments of Knowledge). zk-SNARKs are a special form of ZKP that is also non-interactive — the prover and verifier aren’t required to be online at the same time, and succinct — the proofs are small in size, which makes verification fast. The two big shortcomings of the technology are that generating the proof is still incredibly slow (proving relatively simple statements would still take minutes) and that the cryptographic assumptions used are fairly new and not well established in academia or industry.

zk-SNARKs have found at least one interesting application of creating a truly anonymous cryptocurrency. Z.Cash is an adaptation of the Bitcoin blockchain to include zk-SNARKs built-in, with the goal of encrypting the transactional entries in the ledger, while still proving that no double-spending occurs. Z.Cash (originally known as Zerocash in academia), seems to have found an interesting use-case that is able to make good use of the practical limitations of the technology — holding succinct proofs in a permanent ledger might be worth the overhead involved with generating the proofs in the first place. Another interesting bit of information is that launching the Z.Cash blockchain involved a ceremony to generate the public parameters used throughout the system. That ceremony was an implementation of a MPC protocol, used in order to decentralize the trust across several participants and not just a single one. - Computing Over Encrypted Data - 零知识证明该怎么入门?