Rechercher

ZK-Snarks: A Small Proof with a Big Potential


If you've done your own research on blockchain and cryptocurrencie, you have most likely come across the terms Zero-Knowledge, Zk-Snark, Starks, and other cryptographic proof instruments and wondered what was behind it all. So today let's talk about it shall we ?

 

The idea of creating a decentralized currency, which appears to be a simple and understandable concept on the surface, quickly becomes a headache when it comes to implementation. People do not trust one another, they are not synchronized, they take too long to agree, and so on.... The concept of proofs emerges quite naturally in this context in order to allow people to agree on aspects of network execution. And this where Zero-Knowledge Proofs and Zk-Snarks come into play.


Let us begin by revisiting the concept of Zero-Knowledge Proof. The idea here is to demonstrate to someone that you know a piece of information without revealing it; everyone can devise his or her own method to accomplish this, and it is not limited to the cryptographic domain. Consider your friend Jean, who is colorblind; red and blue represent the same gray to him. To demonstrate that there is a distinction between the two, you give him two balls, one red and one blue, and instruct him to place them behind his back and then decide whether he wants to switch them or keep them as they are. By the time he reveals them, you'll be able to tell if the balls have changed hands, and John will be convinced that you can tell the difference. But, in order to be completely convinced, John decides to repeat the process a dozen times before accepting the test's validity. This is known as interactive proof, and it involves the two parties exchanging information back and forth for a number of rounds.


An interactive proof is incompatible with a monetary system that strives to be as efficient as possible. The goal is then to create a non-interactive proof, which is where we introduce the Succinct Non-interactive Argument of Knowledge, abbreviated as Snarks, with the succinctness implying that the proof is instantaneous to verify. We apply the principle of Zero-Knowledge and get a ZK-Snark as a result.


A Snark is a proof of correct computation, which means it will demonstrate that a program was correctly executed. To accomplish this, a program, such as one that returns the average of two numbers, must be converted into a more mathematical form defined as "provable," where we have the mathematical tools to construct a proof, a process that alternates between different techniques. For example, we can convert our program into a polynomial, and the evaluation of this polynomial will be correct only if the program execution was correct. Instead of rerunning the program, the verifier will only need to evaluate the polynomial to determine whether or not the program was correctly executed.


Snarks have numerous applications. Naturally, early implementations concentrated on privacy-related applications. Zcash is the most prominent example of a crypto-currency which creates proof that a sender in a transaction has the funds and private key associated with the account they claim to have, allowing them to avoid disclosing the information.

However, Snarks are also being used to scale existing Layer 1 systems such as Ethereum, where Snarks should be used in their implementation of ZK-Rollups as a short proof proving the validity of a large set of transactions at once. They can also reduce system storage requirements by demonstrating the correct state transition from the genesis to the last block, eliminating the need to check the entire blockchain when becoming a network node.


Before finishing this presentation, it is necessary to mention the disadvantages of Snarks, because they are not used in all contexts for a reason. Converting a program into its mathematical "provable" form is very computationally expensive, a simple function to verify the preimage of a hash has a setup time of around 20sec and requires 350mb of memory. So it is important to weigh the pros and cons before incorporating them into a crypto protocol