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!
zk-SNARK son las siglas en inglés de Zero-Knowledge Succinct Non-interactive ARgument of Knowledge, que sería algo así como Argumentos de Conocimiento, No interactivos, Succintos y con conocimiento Nulo. Muy confuso, ¿no? Vamos poco a poco.
Un argumento, o una prueba, (en realidad no son lo mismo pero por hoy podemos asumir que si) es un protocolo donde dos partes, un probador y un verificador interactuan, y en el cuál el primero intenta convencer al segundo de alguna sentencia. Por ejemplo,
Nuestro celular le pide a un servidor grande que haga un cálculo muy costoso que no puede realizar él mismo. El servidor responde con el resultado y una prueba de que este ha sido computado correctamente (esta sería la sentencia a probar).
Es decir, el servidor quiere convencer a nuestro celular de que el resultado es el correcto.
Un argumento de conocimiento va un poco más lejos. El probador quiere convencer al verificador de que sabe algo
Digamos que hemos pagado al servidor (servidor A) para hacer un cálculo y nos queremos asegurar no sólo de que el cálculo es correcto si no también de que el servidor A lo ha hecho él mismo y no ha pedido ayuda a otro servidor (en ese caso, preferiríamos hablar con el segundo servidor y conseguir un mejor precio).
Para evitar esa situación, podemos pedir al servidor A que nos provea con una prueba de conocimiento de todos los pasos intermedios que hizo para llegar a la solución.
Naturalmente, no vamos a chequear uno por uno cada uno de estos pasos, pues sólo contamos con un teléfono móbil y lo más probable es que no podamos siquiera intentarlo.
Pero nos queremos asegurar que servidor A conoce esos pasos, por lo tanto, necesitamos una prueba de conocimiento de ellos.
Ahora, ¿Sucinto? Sucinto significa "que está expresado de manera breve, concisa y precisa".
Es decir, que tiene que ser corto, eficiente. ¿Por qué? Bueno, eso es fácil: queremos chequear con un teléfono móbil un cálculo que ha realizado servidor A, el cuál posee un poder computacional mucho mayor.
Este paso de verificación tiene que ser más rápido de correr que el cálculo en sí. De hecho, no basta con más rápido, si no que debe ser muchísimo más rápido.
Si no es así, ¿Por qué pagaríamos por algo que podemos calcular por nuestros medios? Y además la prueba en sí debe ser chica, de otra manera nuesto dispositivo no podrá ni recibirla.
Por otro lado, nos gustaría reducir la interacción entre el probador y el verificador lo máximo posible.
¿Por qué? Porque tener que enviar mensajes de un lado al otro implica que los dos dispositivos, celular y servidor, tienen que estar en constante comunicación, por lo que ninguno se puede apagar o siquiera desconectar.
La cantidad ideal de interacción es lo que llamamos no interacción: el verificador pide un cálculo, paso que en general no se realiza ya que la sentencia a probar es pública, el probador lleva a cabo el cálculo y envía el resultado + la prueba.
Finalmente, el verificador chequea el resultado y la prueba para sí mismo y fin. De aquí viene lo no interactivo del argumento.
Para explicar el conocimiento nulo vamos a cambiar el ejemplo y hablar un poquito de las tan famosas criptomonedas.
Imaginemos que somos la (el) usuaria(o) A y queremos transferir algunas de nuestras criptomonedas al usuario B. Como sabŕan, o quizás no, estas transacciones se publican en el blockchian correspondiente a nuestra criptomoneda, que es público y accesible para todo el mundo.
Además, no hay una autoridad central que mantenga este blockchain, si no que es mantenido por las(os) mineras)os), usuari@s elegidos casi aleatoriamente para crear bloques que incluyan las transacciones.
Podemos por ejemplo, pensar el blockchain como un libro público, que todas las personas pueden leer y en el cuál todas las personas pueden publicar. Sin embargo, lo que querramos publicar debe ser incluído en páginas que son agregadas al libro por las(os) mineras)os), que pasan cierto proceso de selección y reciben recompensas por cada página que agregan.
Recapitulando, yo usuaria(o) envío mi transacción a las(os) mineras)os), éstos las agregan a una página y luego intentan incluir esa página en el libro.
Una vez que la página que contiene nuestra transacción es publicada (en realidad, una vez que ha permanecido en el libro por cierto tiempo) la transacción se considera realizada.
¿Cómo pagamos? Para transferir al usuario B necesitamos probar algo así como "Yo soy la (el) usuaria(o) A, dueña(o) de la cuenta A y quiero transferirle X criptomonedas al usuario B".
¿Raro, no? Las criptomonedas se construyen para ser tan privadas como sea posible, y por lo tanto nos gustaría publicar en el blockchain (que, recordemos, es público y está disponible para cualquier persona) algo como "Yo soy usuaria(o) dueña(o) de una cuenta, en la cual hay suficiente dinero para enviarle a B lo que quiero enviarle, y le envío".
Mejor, ¿No?.
Esa es exactamente la tarea del conocimiento nulo: el verificador solo puede saber lo estrictamente necesario, es decir, podemos probar algo como la primera sentencia, pero sin filtrar más información que la contenida en la segunda.
Probar, por ejemplo, posesión de una cuenta puede hacerse probando conocimiento de la contraseña (o de la clave secreta) que corresponde a dicha cuenta.
Esto es básicamente lo que hacemos cuando usamos cajeros automáticos, solo que en este caso como no podemos cubrir con nuestros cuerpos o manos lo que publicamos en el blockchain, lo que hacemos es publicar, en lugar de nuestra contraseña, una prueba de conocimiento con conocimiento nulo, valga la redundancia.
¿Quiénes verifican en este caso? Bueno, en principio cualquier persona que lo desee pero, en particular, las(os) mineras)os) deben verificar todas las transacciones antes de publicarlas.
Ahora, las(os) mineras)os) poseen máquinas con mucho poder computacional, ¿para qué mantener las pruebas sucintas? El caso es que publicar en el blockchain tiene un costo y además, las(os) mineras)os) deben verificar miles de transacciones, por lo que queremos mantenerlas pequeñas y rápidas de verificar.
Un detalle importante es que tanto el ser sucintos como el conocimiento nulo no son propiedades exclusivas de los zk-SNARKs, si no que como podrán imaginarse, ambas propiedades son altamente requeridas en distintos protocolos. Más aún, hay muchos protocolos que nos ofrecen distintos niveles de eficiencia, seguridad y comunicación pero ninguno, ni los zk-SNARKs, están siquiera cerca de ser ideales en todos los aspectos. Éstos últimos están diseñados para maximizar la eficiencia, pero a costa de otros aspectos, como la seguridad.
Si te interesa saber más de este tema, háznoslo saber y mantente atento(a) a próximas publicaciones!