05 - Zero-Knowledge Proofs

Zero-Knowledge Proofs

In our section on scalability later in the course, we will discuss Zero-Knowledge Proof rollups, but we won’t go into detail about what ZKPs are. In this section, we’ll discuss the basics of ZKPs and compare two common implementations of ZKPs you’ll see in blockchain.

Zero-Knowledge Proofs have been researched since the 1980s—the initial researchers of ZKPs received the Turing Award, the highest award in computer science, for their work. Their development stems from the field of computational complexity and, while most of the work of ZKPs is very technical, we’ll try to provide a broad overview.

The goal of zero-knowledge proofs (ZKPs) is for a verifier to be able to convince themselves that a prover possesses knowledge of a secret parameter, called a witness, satisfying some relation, without revealing the witness to the verifier or anyone else. Zero-knowledge proofs are currently being researched as solutions to two main issues in public blockchains:

  1. Privacy: All essential information within a blockchain network must be public. ZKPs allow users to verify / prove certain elements of information (such as the answer to a crossword puzzle) while not revealing the information itself (to not give the answer to someone else). Certain tools, such as AZTEC, promise to use ZKPs to provide channels which shield the entire nature of certain transactions from the public blockchain while still using the public blockchain’s security promises.
  2. Scalability: As blockchain networks grow, the amount of data they require to be maintained grows as well. ZKPs compress large amounts of data into compact, verifiable proofs, a characteristic scalability researchers hope to use to dramatically reduce the data required to maintain security on a public blockchain.From ZCash:“Succinct” zero-knowledge proofs (SNARKs, STARKs) can be verified within a few milliseconds, with a proof length of only a few hundred bytes even for statements about programs that are very large.

A common way Zero-Knowledge Proofs are used in blockchain is as follows. A Verifier will take the piece of data to be verified and put it through a private process (ZK-SNARK or STARK, for example) which produces a program called a Proof Circuit. This Proof Circuit can then be posted openly (such as in a Smart Contract) as it reveals no meaningful information about the nature of the data it represents. A Prover can then use the Proof Circuit to irrefutably prove they know the piece of data by publicly “solving” the Proof Circuit, a process that also reveals nothing about the nature of the data.

The Ethereum Foundation described the impact of this privacy would have on a blockchain:

Imagine, for example, an election or auction conducted on the blockchain via a smart contract such that the results can be verified by any observer of the blockchain, but the individual votes or bids are not revealed. Another possible scenario may involve selective disclosure where users would have the ability to prove they are in a certain city without disclosing their exact location. (source)

ZKPs in Action

zk-SNARKs

Succinct Non-Interactive ARgument of Knowledge, or SNARKs, were first widely implemented on a blockchain by ZCash, a fork of Bitcoin. Ethereum introduced SNARK capacity with the Byzantium fork by including precompiled contracts that allowed efficient SNARK verification on-chain. SNARKs are being discussed in terms of privacy (as in ZCash) and scalability (as in SNARK roll-ups)

Pros:

  • Small, constant proof size
  • Constant-time verification costs (source)

Cons:

zk-STARKs

Scalable and Transparent ARgument of Knowledge, or STARKs, share a similar fundamental ideas with SNARKs but differ in execution. Their development and advocacy is done chiefly by STARKware, a private company led by Eli Ben Sasson, with assistance from the Ethereum Foundation.

Pros:

  • No trusted setup required
  • Faster proving time relative to SNARKs (source)

Cons:

  • STARKs have a larger proof size than SNARKs
  • As of June 2019, STARKs still in development

ZKP Tutorials

More Resources