Introductory Guide to zk-SNARK

Security is no doubt an integral part of building a blockchain solution in the cryptocurrency community. As a platform that houses various financial assets and sensitive private information, it must be kept secure from attackers. One of the cryptographic techniques that provide this needed security to the blockchain is zk-SNARK.

Zk-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) is a verification method where a party (prover) can prove the possession of certain information to another party (verifier) with neither party interacting or revealing the said information to the other. This information can be anything that is deemed private by either of the 2 parties (e.g. a secret key).

To better understand zk-SNARK, we need to learn about  Zero-Knowledge Proof, the technique on which zk-SNARK is built**.**

What is Zero-Knowledge Proof?

Zero-Knowledge (ZK) Proof is a proof construction that allows the prover to show a verifier that a statement is true without revealing any other information besides the validity of the statement itself. Also known as Zero-Knowledge Protocol, it was first described by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in a 1985 paper titled The Knowledge Complexity of Interactive Proof Systems.

ZK Proofs are mostly applied to privacy and security systems. A common example of this is password verification. With ZK Proofs, one can prove they have the password to an account without revealing the password to the verifier.

For example, if a hacker manages to hack into the Twitter account of the US Government, there is no need to publish the password to prove that the account has been hacked. Rather, a single Tweet by the hacker via the US Government account claiming that the account has been hacked is sufficient.

In this case, everyone else besides the hacker has zero clues about the new password. A very popular example of this in cryptography is The Alibaba Cave Parable.

The Alibaba Cave

The Alibaba cave parable was originally introduced by the renowned cryptographer, Jean-Jacques Quisquater (et. all) in the paper titled "How to Explain Zero-Knowledge Protocols to Your Children". This paper introduced a noobish explanation of ZK Proofs using the Alibaba Cave.

The story introduces Alibaba, an old man who discovered the magic words thieves used to access a secret door in a cave and escape being caught. After experimenting with the words a few times, he changed it to something else only he knew of. However, rather than sharing the magic words with others, he wrote down subtle clues about them before his death.

Several centuries later, some curious researchers were able to break the clues and access the secret door in the cave. Television Networks got a wind of the event and all wanted an exclusive on the story.

Luckily for one of the big corporations, Mick Ali (perhaps a descendant of Ali Baba), one of the researchers decided to prove that he knew the magic words without revealing the secret.

An illustration of the Reporter, Mick Ali, and the Ali Baba Cave

After the TV crew had filmed a detailed tour of the cave, Mick Ali went in alone, down one of the 2 passages in the cave. The reporter then went in as far as the fork, then flipped a coin to choose between left and right.

If the coin came up heads, he would tell Mick to come out on the right and if the coin was Tails, he would tell Mick to come out on the left. The coin was Heads, so he told Mick to come out on the right and Mick did just that.

That way, Mick was able to prove that he knew the secret words to open the magic door without revealing the words. This Zero-Knowledge protocol is what zk-SNARK is built on.

Characteristics of zk-SNARK

As highlighted above, zk-SNARK stands for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge. Let us break down each of these components to further define what zk-SNARK is.

• Zero-Knowledge (ZK): This refers to the ability of one party to prove that they have access to particular secret information without revealing the said information to the verifying party.
• Succinct: As the name implies, it means that the proof is short, precise, and can be easily verified within a few milliseconds. The length of the proofs is usually very small even for very large programs.
• Non-interactive: It means that no interaction needs to occur between the prover and the verifier. The current way to do this is to create a Common Reference String (CRS) shared between the prover and verifier. This is called the public parameters of the system.

Considering the US-Government Twitter hack example mentioned earlier, the hacker does not need to interact with the US Government to prove that the account has been hacked. Making a public post is enough proof.

• Argument: This means that the arguments of knowledge (or witness) is computationally sound. It is almost impossible for the prover to cheat the system if they have no computationally sound argument to back up their claim. For example, if the so-called hacker is unable to tweet via the US-Government account, then they are just bluffing about having access to the password.
• Knowledge: Clearly, any prover who does not have any knowledge has nothing to prove. In zk-SNARK, the prover needs to have the required knowledge to be able to create a sound argument.

Applications of zk-SNARK

Although the first widespread application of zk-SNARK was in the ZCash blockchain protocol, more cryptocurrencies are now adopting this solution. In fact, ETH 2.0 is using the smart integration of zk-SNARK to create layer-2 scalability. However, we'll only be looking at 2 major applications in this article.

ZCash

Zk-SNARKs are applied to ZCash to create a shielded transaction that is easy and cheap to verify. However, a setup phase is required to generate the system parameters before zk-SNARKS can be applied.

This setup phase involves the generation of a \((privkey, pubkey)\) pair, after which the private key is destroyed as “toxic waste”. This is done to prevent counterfeiting new coins.

Let \(G\) be a Group with a hard discrete log and the prime number \(r\) be the order of \(G\),  where \(g\in G\). Also, let \(F\) be a Field of size \(r\) with \(s \in F\).

$$pubkey = (g,s\cdot g, s^{2}\cdot g,...,s^{d}g)$$

Recall that given a Polynomial \(P\) of degree \(d\) over \(F\), we can evaluate \(P(X) = a_{0}+a_{1}X_{1}+a_{2}X_{2}+...+a_{d}X_{d}\) at a point \(s \in F\) by substituting \(s\) for \(X\).

In ZCash, the sender (prover) needs to construct two \(degree-d\) polynomials \(P\) and \(Q\). Various mathematical procedures have been put in place to ensure that they can only make equal value polynomials \((P=Q)\), if the transaction is valid.

The verifier can now test if \(P\) and \(Q\) are equal at a point \(s\) not known by the sender. Following the zk-SNARK procedure, the prover will create two different polynomials as arguments to prove that they have knowledge of the transaction.

These polynomials are generated with no prior interaction with the verifier. Also, the polynomials can be easily solved in milliseconds by substituting the value of \(s\), a secret value that the prover has zero knowledge of.

Ethereum

One of the major issues faced by the Ethereum blockchain is scalability, which contributes to the ridiculous gas fees in the network. To solve this problem, Ethereum is developing various solutions for layer 2 scalabilities.

ZK-Rollups, a "zero-knowledge proof" approach is one of the options being developed for layer 2 construction to increase scalability through mass transfer processing rolled into a single transaction. By retaining zero knowledge of the data held in a transaction, the computing and storage resources for validating the block is reduced.

There are two types of users in the ZK-Rollup scheme, namely; the transactors and the relayers.

• Transactors: These people create a transfer and broadcast it to the network. The transfer data consists of an indexed "to" and "from" address, the value of the transaction, the network fee, and nonce. This data is shortened into a 3-byte version and the value is used to create either a deposit or withdrawal. This data is then stored in two Merkle Trees, where one stores the amount and the other stores the addresses.
• Relayers: The relayers collect the transfers and generate the SNARK proof, a hash that represents the change of the blockchain state. The SNARK proof compares the wallet values before the transfers to the wallet values after the transfers and reports only the changes in a verifiable hash to the mainnet.

Concluding Thoughts

There are several applications of zk-SNARKS in blockchain, especially as it moves towards mainstream adoption. However, one of the major constraints of zk-SNARK is that a common reference string needs to be created beforehand to produce zero-knowledge proofs that are non-interactive and short enough to publish to a blockchain.

This creates a major vulnerability where someone who has access to the secret randomness used to generate these parameters would be able to create false proofs that would look valid to the verifier. In the case of ZCash, this makes it possible for malicious parties to create counterfeit coins.

This loophole is what Eli-Ben Sasson, a professor at the Technion-Israel Institute of Technology intend to fill with the introduction of zk-STARKS.