zk-SNARK stands for Zero-Knowledge Succinct Non-interactive ARgument of Knowledge.

An argument or proof (they are not the same, but we can ignore their differences in this post) is a protocol where two parties, the prover, and the verifier, interact, and the former tries to convince the latter of some statement.

For instance, our mobile phone asks a powerful server to perform some expensive computation that it cannot compute itself; the server sends back the result, along with a proof that the output is indeed the result of the required computation. Namely, the server wants to convince our phone that the result is correct. An argument of knowledge goes a bit further. The probador aims to convince the verifier that it knows something.

Let's say we have paid some money to this server (server A) to compute something for us, and we want to make sure that it did not ask some other server to perform this calculation (in that case, we would prefer to interact with the second server and get a better price). In this case, we can ask server A for a proof of knowledge of all the intermediate steps that made it arrive at the solution. Of course, we are not going to check them all! I mean, we have a phone and probably can’t even try. But we want to make sure server A knows them. Then, we need an argument of knowledge.

Now, why succinct? Well, this is an easy one. We want to check with a phone some computation that the very powerful server A has performed. This checking must be cheaper to run than the computation itself. Not only cheaper but, let's say, way cheaper. Because otherwise, why pay for something we can calculate ourselves with just a bit of effort? What is more, the proof has to be small, otherwise it could be the case that our phone cannot even receive it. Also, we want to reduce the interaction between the prover and the verifier as much as possible. Why? Because having to send information back and forward would imply that both devices need to be in constant communication, so neither of them can be turned off or even offline. The ideal amount of interaction is then no interaction. The verifier makes a request, which in general is public and then does not imply communication, the prover runs its calculations and sends the result plus the proof. The verifier checks it on its own and we are done. That is where the non-interactive part comes from.

To explain zero-knowledge we will migrate examples and talk about the very exciting field of cryptocurrencies. This time we are user A and want to transfer some of our crypto coins to user B. As you may, or may not, know, this transaction has to be published in the corresponding blockchain, which is public and accessible to all. Also, there is no central authority that maintains it, but only miners that are somewhat aleatory selected to create blocks that include transactions. You can think of it as a public book that everyone can read, where everyone can publish but the pages (and everything written on them) are added by users (the miners) that pass some selection process (and receive very nice rewards). So, users send their transactions to the miners, the miners add them to their pages and then try to add these pages to the book. Once the page containing our transaction is in the book (actually, it has been in the book for some time), the transaction is considered done.

How can we pay? To transfer to user B we need to prove something like "I am a user A, owner of account A and want to transfer X crypto coins to user B". Noisy, right? Cryptocurrencies are meant to be as private as possible and then we would like the blockchain (which is public and available to everyone) to contain only something like "I am a user that holds some account that has enough money to send to another user what I want to send, and I do so". Way better, right? That is what zero-knowledge is for: the verifier only learns what it must learn, so we can prove the first statement but we do not leak more than what the second statement says.

Proving ownership of an account can be done by proving knowledge of the password (or secret key) that corresponds to such an account. This is something very similar to what we do with ATMs, but in this case, as we are doing everything in the Blockchain and cannot hide with our bodies and hands what is published there, we better just publish a zero-knowledge argument of knowledge.

Who are the verifiers in this setting? Anyone could be, but in particular, the miners always verify a transaction before publishing it. Now, miners own very powerful machines so, what is succinctness for? Well, the fact is that publishing in a Blockchain has its cost, and also miners have to verify thousands of transactions, so we want to keep it short and fast for them.

Succinctness or zero-knowledge are not exclusive properties to zk-SNARKs but, as you can imagine from the description, both find very nice applications in real world. Importantly, there are different trade-offs we can chose in terms of efficiency, security, communication costs for proof systems and, even though zk-SNARKs sound ideal as described in this post, they are designed to maximize efficiency and pay costs in other aspects, as security.

If you want to know more about this, stay tuned for future posts!