An introduction to zk-SNARKs

Photo by Daniel Lorentzen

In this article, we will build our intuition about zk-SNARKs, a special type of cryptographic proof used to demonstrate the validity of a computation without disclosing information about that computation. This article is intended as an explainer of the foundations of zk-SNARKs for anyone who is interested, regardless of their technical background. While the topic of zk-SNARKs is complicated, we will build a fundamental intuition about how they work, then discuss the technical details of a zk-SNARK protocol.

This article is intended for people trying to wrap their heads around the cryptography and mathematics that underlie zk-SNARKs. There are great resources for building basic intuition about zk-SNARK technology¹. There are also many technical (and more succinct) descriptions of the specifics of a zk-SNARK protocol², including rigorous proofs of their security properties. Some of these resources are included in the references. There are also existing implementations worth checking out³ ⁴. In this article, we will walk through the major components of the protocol in a way that is (hopefully) accessible to people with a basic understanding of mathematics and computation.

  1. What’s a zk-SNARK?

What on earth is a zk-SNARK? zk-SNARK is an acronym describing the characteristics of a specific type of Zero Knowledge proof.

  • zk: “Zero Knowledge”
  • S: “Succinct”
  • N: “Non-interactive”
  • ARK: “ARgument of Knowledge”

“Zero Knowledge” simply means that we would like to prove something about a computation without revealing any other information about it. These proofs let you do things that seem magical, like prove that one number is greater than another, without revealing the number itself. In the real world, it should be impossible to have a secret and share it too.

“Succinct” means that it is easy for someone (a verifier) to check the results of a proof. This increases the computation for a prover (the party creating the proof), but greatly increases the utility of a zk-SNARK. Once they are created, they can easily be verified by an interested party.

“Non-interactive” means that we do not have to go back and forth to prove something. Zero Knowledge proofs are in the business of proving something with high confidence. In other words, there should be a very low (negligible) probability that the prover is lying. One way to achieve this would be to repeatedly ask the prover to do computations and check each result until we are convinced (with high probability) that the prover is being honest. Although there are some applications of interactive Zero Knowledge proofs, they do not scale well, and are not suitable for applications where a variety of verifiers need to use a proof. Being non-interactive, a zk-SNARK is better suited to many applications because a proof only has to be computed once.

“Argument of Knowledge” means, simply, that we demonstrate knowledge of something. Following the above example, we could demonstrate knowledge that an age is greater than some number, without revealing the age itself.

Two final attributes (not included in the acronym) are obvious but worth mentioning. “Completeness” means that when a zk-SNARK is used to produce a valid proof, it must be accepted by an honest verifier. “Soundness” refers to the computational soundness of the protocol. In other words, for a zk-SNARK to be worth anything, it must not be possible to provide false proofs to a verifier. In practice, a zk-SNARK must reduce the probability that a prover is able to compute a false proof to such a small number that we no longer worry about this possibility.

Note: We will refer to the “prover” and the “verifier.” The “prover” would like to demonstrate (prove) the result of some computation, and the verifier is checking their results.

2. What’s a zk-SNARK good for?

zk-SNARKS are a (relatively) new technology that has developed out of decades of research in mathematics, security, and cryptography. Today, zk-SNARKs are finding key applications in blockchains, as well as other privacy-focused domains. zk-SNARKs are especially valuable for increasing privacy and improving scalability in a blockchain while maintaining its core security properties.

To improve privacy in a blockchain, zk-SNARKS are used to record proofs of some information, rather than the information itself. Note that a blockchain is, at its core, an immutable (unchangeable) ledger. For a basic blockchain (like Bitcoin), this is a record of the transfer of finite value between parties. In this blockchain, a transfer of 1 unit of value between Person 1 and Person 2 would be recorded openly and would be visible to anyone. Using a zk-SNARK, we can obscure all 3 pieces of information and record proofs (of a value and two identities) in the blockchain, obscuring the value being transferred and the identities of the transferring parties. Z-cash, which relies on zk-SNARKs, is the largest implementation of this type of privacy-preserving blockchain¹.

For scalability (increasing the number of transactions that a blockchain can process), zk-SNARKs can be used to bundle transactions together and record a single proof for all of the transactions, rather than recording individual transactions on the blockchain itself. Because many transactions are grouped together, it is much less expensive to record transactions on the blockchain. We won’t go into too much detail here, but you can find great information about ZK-Rollups⁵.

zk-SNARKS are useful outside of blockchains, too. Imagine an identity system where you can prove that you should be granted access to a website (or anything else) without actually sharing any personally identifiable information. The same privacy-preserving property would apply to a system for payments or travel cards which could demonstrate sufficient access to funds without disclosing a personal identifier, or the total value of those funds.

3. How do zk-SNARKs work?

We have described the basics of zk-SNARKs and mentioned some of their applications. Now, we will introduce the technical details of a zk-SNARK protocol and give an outline of the clever mathematical foundations that make zk-SNARKs work.

How do zk-SNARKs work? The short answer is, it’s complicated! They are an incredible combination of mathematics and cryptography that let us do things that seem like they should be impossible. Although complicated, zk-SNARKs should be accessible to people with some fundamental understanding of mathematics and computation. I have found the in depth explanation by Maksym Petkus to be particularly helpful².

A note: the field of Non-Interactive Zero-Knowledge proofs is developing quickly! The same goes for their applications. While we expect that protocols will change and continue to improve, this article should (hopefully) provide a useful exploration of the basics of Zero-Knowledge proofs and the fundamentals of a zk-SNARK protocol.

4. What’s “under the hood?”

zk-SNARKs are a fascinating combination of mathematics and cryptography and a significant amount of research is required to fully understand how they work. Nonetheless, we can get an intuition about the most important parts of a zk-SNARK protocol by understanding the fundamental building blocks:

(1) Polynomial Functions

(2) Homomorphic Encryption

(3) Modular Arithmetic

(4) Cryptographic Pairings

Combining these mathematical techniques in the correct series of steps, we can create Zero-Knowledge proofs of computation that are efficient to verify.

(1) The mathematical foundation of zk-SNARKs are polynomial functions. We need to transform a general computation into a provable “argument of knowledge.” For a zk-SNARK, an argument of knowledge can be proved by demonstrating knowledge of a certain polynomial function to a verifier. Using the valuable fact that any (finite) computer program can be represented in terms of polynomial functions, we can transform a series of computations into a general purpose argument that we are able to prove.

To create a sound protocol which guarantees a negligible probability that the prover will be able to compute a falsified proof, zk-SNARKS employ a collection of clever tricks that remove the need for the prover and verifier to trust each other. By constructing a system which enforces honesty between the prover and the verifier, each party only needs to trust the protocol, not any other party.

zk-SNARKS rely on the selection of a random secret that is used by a prover to demonstrate knowledge of a polynomial function when the prover generates a proof. For a zk-SNARK protocol, it is important that a prover is not able to know the random value they are performing calculations with, something called “obscure evaluation”. How do we hide a random value from a prover? (2) Using “Homomorphic Encryption,” a special type of encryption that allows math (but only certain operations) to be performed on encrypted values. By encrypting random secrets a prover is not able to know what value they are using, but they can still perform calculations with it, hence the evaluation is “obscure” to the prover.

A zk-SNARK must also enforce limitations on the computations performed by the prover, like ensuring that the prover uses a polynomial of the same degree as the verifier. (3) A prover must evaluate their polynomial twice, using a special “shifted” value (computed with modular arithmetic) to prove that they are using the correct degree polynomial(s).

A final step in creating a zk-SNARK is to generate secrets in a way that allows them to be shared between verifiers. Why? Because this makes the proof “non-interactive.” Once a proof has been computed, it will be possible for multiple verifiers to check that it is a valid proof, relying on shared random values. Therefore, once a proof has been computed, verifiers will not require anything else from the prover. To share these secrets, we must encrypt them, but in a different way than we did above with “Homomorphic Encryption.” This is because Homomorphic Encryption does not allow us to do certain operations that are required for the verifier’s checks.

(4) We use “Cryptographic Pairings” to generate encrypted values that can be multiplied. Using cryptographic pairings, we are able to compute random, shared values, encrypt them, and destroy the original values. These encrypted secrets will permit verification by multiple verifiers, meaning that any proof computed by a prover is now non-interactive.

That is a lot! And a rather cursory description. The zk-SNARK protocol employs an impressive variety of cryptographic and mathematical innovations to prove general arguments of knowledge, producing a protocol which satisfies all the required attributes of the zk-SNARK protocol; easy to verify, non-interactive proofs which do not disclose information to verifiers.

Note: A single party computing shared parameters introduces risk into the protocol. How can we guarantee that this party has thrown away the original values? Knowing these values would compromise the security of the system because they could be shared with a dishonest prover. To reduce the risk of a single party retaining the original values (which are encrypted and shared with all verifiers), we can generate these values with the input of multiple parties, thereby reducing trust in a single party that is responsible for defining shared parameters.

5. Conclusion

We have covered the fundamental mathematical operations used in a zk-SNARK protocol and have discussed some of the applications of this technology. The reader may notice an absence of math in this explanation of zk-SNARKS! While the math that supports the construction of a zk-SNARK protocol is complex, it is also fascinating, and well worth digging into. Hopefully we have provided some intuition about the fundamentals of zk-SNARKs and encouraged you to read further about their applications, and the underlying mathematics that make them possible.

Sources

¹ Z-cash zk-SNARK explainer: https://z.cash/technology/zksnarks/

² A comprehensive description of zk-SNARKs: https://arxiv.org/pdf/1906.07221.pdf

³ A c++ implementation of zk-SNARKS: https://github.com/scipr-lab/libsnark

⁴ An implementation of zk-SNARKS for ethereum: https://github.com/Zokrates/ZoKrates

⁵ A description of ZK-Rollups: https://docs.ethhub.io/ethereum-roadmap/layer-2-scaling/zk-rollups/