Decoding zk-SNARKs

Before diving in, I want to preface by saying that I do not have a computer science background nor am I a zk-SNARKs expert. I am a business student with an interest to learn as much as I can about blockchain and the crypto space. Hope you enjoy reading.

zk-SNARKs stand for Zero-Knowledge Succinct Non-Interactive ARguments of Knowledge. They serve the purpose of authenticating the validity of a computation. When a transaction occurs, it must undergo a verification process. Servers race against each other to be the first to offer up a solution by utilizing their computational power.

Where are they used?
People are generally aware that Bitcoin is not fully anonymous, but rather pseudonymous (the identity of a person attempts to be masked by keys or addresses). Although the public key of someone’s digital wallet is not explicitly linked to a person’s identity, transactions and addresses are public and can be decoded.

This flaw would then logically be a driver to the rise in alternative privacy coins (e.g., Monero, Zcash, Dash, etc.). Each of these coins uses some type of encryption algorithm in order to conceal information when transactions are executed. For example, Monero uses the Ring Confidential Transactions (RingCT) algorithm, Dash is able to facilitate instant transactions through CoinJoin, and Zcash leverages the zero knowledge cryptography of zk-SNARKs.

Zero Knowledge Proofs
Simply stated, zero knowledge proofs are designed so that a prover is able to indirectly verify that a statement is true without having to provide any information beyond the verification of the statement. In practice, this means that a prover can prove that they have found a number that solves a cryptographic puzzle and fits the hash value without having to reveal the nonce.

So how can we describe this in layman’s terms?
Here’s an oversimplified analogy to help anchor the idea of zk-SNARKs. Think of the game Bobby’s World:

If you’ve never played Bobby’s World before, don’t worry. The game is simple. There is only one rule in the game; to win, figure out the rule.

The facilitator (or riddle giver) of the game will give examples like in the picture above (e.g., “there is a mirror, but no reflection. There is grass, but no dirt.”) To find the solution, you have to figure out the pattern (click here if you can’t figure it out). This could be synonymous with the “secret parameter” in zk-SNARKs. But since Bobby’s World is most commonly played with a group of people, you don’t want to immediately share the solution when you figure out the pattern. So you prove you know the answer by providing examples.

If you’ve played this game before, you may have encountered an instance where someone is able to provide a fitting solution, but the facilitator is not convinced that they truly know the rule (i.e., the facilitator believes that it was just sheer luck that the player gave an answer that matched the pattern). In that case, the facilitator will ask the player for another example. With more iterations, it becomes significantly less likely for the player to defraud the facilitator.

Now let’s loop back and dive deeper into the properties of zero knowledge proofs.

Source: https://blockgeeks.com/guides/what-is-zksnarks/

Here’s a breakdown of each component of the zk-SNARK acronym:

1) Succinct
Even when statements are large in size, proofs can be verified in only a few milliseconds (i.e., the length of the proof is constrained by a security parameter). The design feature of random sampling reinforces succinctness by truncating the time needed to verify a statement. This attribute also helps to solve issues with scalability.

2) Non-interactive
A “public verifier” exists so the verifier and the prover do not need to directly interact with each other. Instead, this “public verifier” can send encrypted queries to the prover and send encrypted responses back to the verifier.

3) Arguments
This refers to the computationally-sound property of zero knowledge proofs. The reason that zk-SNARKs are arguments and not proofs are because they assume that provers have limited computational power (quantum computing has the potential to disrupt this). As a result, these arguments satisfy computational soundness but not perfect soundness.

4) Knowledge
This aspect once again relies on the “soundness” property. A prover needs to actually have the answer (i.e., the hash function that points to a Merkle-tree node) in order to even generate an argument that substantiates the statement.

As you might have noticed, there are several disparities between zk-SNARK properties and the Bobby’s World analogy. For one, Bobby’s World is unrepeatable. Once you’ve played the game once, you’ve cracked the code and can no longer “play the game” in the future. Second, there’s an absence of a public verifier (the non-interactive element) in Bobby’s World. And third, there is information asymmetry. The zk-SNARK protocol works such that the verifier (or facilitator) will never know the solution him/herself. Only the prover (or player) knows the solution.

So how do crypto experts describe it?
Reading “Zk-SNARKs: Under the Hood” by Vitalik Buterin (Founder of Ethereum) is helpful to further engage your technical comprehension of zk-SNARKs. Note: his explanation works under the assumption that the reader has a basic understanding of quadratic arithmetic programs and elliptic curve pairings.

Christian Reitwießner (Creator of Ethereum’s native language Solidity) published a white paper on zk-SNARKs that is also worthwhile to read.

I was first introduced to Zero Knowledge Proofs at Scaling Bitcoin at Stanford this past year during a presentation given by Benedikt Bünz. The example used to explain the design and process of Zero Knowledge Proofs was a Sudoku game. Here’s a synthesized version of how it works:

• Briana (the verifier) asks Abhi (the prover) to answer a question to which only Abhi knows the solution.
• Abhi generates a random permutation from the solution set, but places a piece of paper over the Sudoku puzzle to ensure that he cannot modify the numbers.
• Briana then asks Abhi to see Row 8.
• Abhi then reveals to Briana Row 8.
• This process is then repeated over a thousand times (if only 1 try is used, there is >95% chance that Abhi will be able to defraud Briana).
• With each try, Abhi will need to generate a new permutation set (in formulaic terms, s= r+c*z ; r is the randomization of the permutation).
• But ultimately, even after a thousand iterations, Briana still does not know what the solution is.

I hope that this post and my simple analogy have helped to explain the basics of zk-SNARKs (the analogy may not have been an exhaustive comparison to the details behind the intricate protocol, but hopefully was helpful nonetheless in conceptualizing its purpose).

As Christian Reitwießner writes:

With zkSNARKs, it becomes possible to not only perform secret arbitrary computations that are verifiable by anyone, but also to do this efficiently.

The utility of zk-SNARKs has long been recognized by the crypto community and its implementation already exists in coins like ZCash. Looking forward, I am excited to see how, when, and where this technology will be utilized to create the biggest impact in the future.

-₿