Iván Párraga

🔐 ¿Qué son las pruebas de conocimiento cero (ZKP)? ¿Qué superpoderes añaden a los blockchains?

Iván Párraga -

La criptografía es una parte inherente de la tecnología blockchain. En la mayoría de cádenas se utiliza criptografía asimétrica y hashes criptográficos para los siguientes casos de uso:

  • utilización de firma digital para probar la propiedad de una cuenta (o dirección en el blockchain) y poder disponer de fondos (es decir, transferir criptoactivos a otras cuentas),
  • generación permissionless de cuentas en la cadena y,
  • amplia utilización de hashes para diferentes procesos: durante el minado, como identificadores de transacciones o bloques o como mecanismo para identificar de manera eficiente la validez de los datos.

Sin embargo han ido surgiendo nuevos requerimientos en los blockchains que han requerido la introducción de otros algoritmos criptográficos. Algunos de estas nuevas necesidades tienen que ver con la necesidad de encriptación de datos sensibles en blockchains públicos o la necesidad de realizar computación fuera de la cadena (por abaratamiento de costes, por ejemplo) sin perder la garantías que proveen los mecanismos de consenso de los blockchains.

Los protocolos de conocimiento cero son algoritmos criptográficos avanzados que vienen a solucionar parte de estos retos.

Un protocolo de conocimiento cero o prueba de conocimiento cero, y quizás más conocido por las siglas ZKP (del inglés Zero Knowledge Proof), es un método criptográfico que permite a una parte (el “probador”) probar el conocimiento sobre una cierta información a otra parte (el “verificador”) sin revelar el contenido de dicha información ni ningún dato adicional.

O dicho de otra manera, un protocolo de conocimiento cero es un método por el cual el probador puede demostrar al verificador que algo es cierto sin revelar ninguna información adicional aparte del hecho que este aserto en particular es cierto.

El verificador puede estar seguro que el probador conoce la información pero no tiene manera de, a su vez, probar ese conocimiento frente a un tercero. De esta manera el probador tiene la garantía que sólo él puede probar que posee la información y simultáneamente tiene controlado quién ha podido verificar ese conocimiento.

Tabla de contenidos

Ejemplo intuitivo

La entrada en inglés de la Wikipedia propone un ejemplo intuitivo de en qué consiste un ZKP que me parece muy adecuado.

Es una práctica común de la literatura sobre ZKP llamar al probador Peggy (con "p" de prover) y al verificador Victor (con "v" de verifier) , así que mantendré la tradición.

Así pues imaginemos a dos amigos, Peggy y Victor. Victor es daltónico y tiene dos bolas con las mismas dimensiones, peso, etcétera, que sólo se diferencian en que una es verde y la otra es roja. Para él, son dos bolas idénticas.

Peggy, que puede distinguir los colores, quiere demostrar a Victor que efectivamente las dos bolas son diferentes (y que ella puede percibirlo). Para probarle a Victor este hecho de forma irrefutable le propone el siguiente experimento:

  1. Victor coge una bola con cada mano,
  2. Victor muestra la bola de la mano derecha a Peggy que memoriza el color pero no lo comunica a Victor,
  3. Victor se lleva las dos bolas a la espalda y fuera de la vista de Peggy puede hacer una de las dos acciones siguientes:
    1. cambiar las bolas de mano o bien,
    2. no hacer nada,
  4. Victor muestra la bola en la mano derecha a Peggy,
  5. Peggy informa a Victor sobre si ha hecho el cambio de bola o no. Peggy puede saberlo sin duda porque si la bola que le muestra ahora tiene un color diferente a la mostrada anteriormente, necesariamente ha hecho el cambio; de igual manera, si tiene el mismo color es seguro que no la cambió.

Si el experimento se repite un número suficiente de veces la probabilidad que Peggy acierte por azar es muy pequeña. Pongamos que lo repetimos 20 veces, la probabilidad que Peggy acierte siempre si está haciendo una elección aleatoria, se reduce a una entre 220 (que podemos simplificar como “menos probabilidades que una una entre un millón”) y Victor se creerá con gran certeza que efectivamente las bolas son diferentes y que Peggy puede verlo.

Por otro lado, es interesante notar que lo único que ha demostrado Peggy a Victor es que sabe que efectivamente las bolas son diferentes pero no ha revelado en ningún momento el color de cada una de ellas. Es decir, no ha revelado más información que la que se probar que se tiene, que es un requerimiento estricto para las ZKPs.

Propiedades

Un protocolo de conocimiento cero que recibe como entrada un aserto (una declaración que puede ser verdadera o falsa), debe satisfacer las siguientes propiedades:

  1. Completitud (en inglés se habla de completeness). Si la entrada es válida, el protocolo siempre devuelve “cierto”. Es decir, si el aserto es verdadero, y el probador y el verificador son honestos, la prueba se puede aceptar.
  2. Robustez (en inglés soundness). Si la entrada es inválida, es teóricamente imposible manipular el protocolo para que conteste “cierto”. Por tanto un probador deshonesto (mentiroso) no puede engañar a un verificador honesto para que se crea un aserto inválido (excepto con un margen despreciable de probabilidad).
  3. Conocimiento cero (en inglés zero-knowledge). El verificador no obtiene ningún conocimiento adicional más allá que el aserto sea verdadero o falso.

Cabe notar que las pruebas de conocimiento cero no son pruebas en sentido matemático estricto ya que existe una probabilidad pequeña, el error de robustez del punto [2] (en inglés soundness error), que un probador deshonesto pueda engañar a un verificador. Dicho de otra manera, las pruebas de conocimiento cero son pruebas probabilísticas en vez de pruebas deterministas.

Tipos

Interactivos

El ejemplo intuitivo que describíamos anteriormente del amigo daltónico y las bolas de colores constituye un protocolo de conocimiento cero interactivo.

Estos protocolos se basan en el hecho que el probador debe interactuar con el verificador para demostrar que tiene el conocimiento de una información secreta. Generalmente el verificador planteará diferentes retos o preguntas al probador hasta que se quede convencido de que efectivamente el probador tiene el conocimiento secreto (en nuestro ejemplo esto se corresponde al número de veces que el verificador mezcla las bolas y las presenta al probador). El protocolo pues requiere comunicación directa entre probador y verificador con mensajes de ida y de vuelta entre ambos y un número y tipo de interacciones no previsible a priori.

Otra implicación derivada de esta interactividad es que el probador siempre convence a un verificador específico y necesita repetir el proceso cada vez que quiere probar su conocimiento ante un nuevo verificador.

No interactivos

Los algoritmos no interactivos surgen para suplir las desventajas de los interactivos. En particular, ofrecen las siguientes ventajas:

  1. No requieren comunicación interactiva entre probador y verificador lo que implica que no se requiere la presencia de ambos en el mismo momento.
  2. Se reduce la comunicación entre probador y verificador, existiendo un único mensaje (desde el probador al verificador).
  3. Una vez el probador ha computado una prueba, esta puede repartirse a cualquier verificador haciendo innecesario nuevas computaciones.

Haciendo un poco de historia, en 1986 Amos Fiat y Adi Shamir publicaron una técnica (conocida como Fiat-Shamir) que permitía convertir cualquier protocolo de conocimiento cero interactivo (que cumple alguna característica) en un protocolo no interactivo.

Algo después, en 1988 Manuel Blum, Paul Feldman y Silvio Micali propusieron el primer sistema no interactivo de conocimiento cero en el que el probador y el verificador utilizaban una clave compartida.

Los protocolos utilizados en los blockchains actuales se basan fuertemente en las ideas descritas en esta última propuesta. El algoritmo general de estos protocolos es el siguiente:

  1. El probador pasa la información confidencial a una función criptográfica que construye una prueba.
  2. El probador envía la prueba construida al verificador (esta es la única comunicación).
  3. El probador pasa la prueba a otra función criptográfica que la verifica y que devuelve cierto o falso en función si se debe aceptar o no.

Por supuesto el reto está en cómo construir las dos funciones. No quiero entrar ahora en los detalles técnicos pues se basan principios matemáticos criptográficos bastante sofisticados pero podemos hacer el acto de fe que sí funcionan y tienen las propiedades explicadas previamente (si no te lo crees, siempre puedes leer el artículo de Blum, Feldman y Micali).

Existen dos tipos principales de protocolos de conocimiento cero: los ZK-SNARKs y los ZK-STARKs.

ZK-SNARKs

ZK-SNARK es el acrónimo en inglés de, atención, lo siguiente: zero-Knowledge succint non-interactive argument of knowledge que tiene las siguientes características:

  • Conocimiento cero (zero-knowledge). Un verificador puede validar la integridad del aserto sin saber nada más sobre el mismo. El único conocimiento que el verificador tiene del aserto es si este es cierto o falso.
  • Sucinto (succint). La prueba de conocimiento cero es más pequeña que la información secreta y se puede verificar rápidamente.
  • No interactivo (non-interactive).
  • Argumento de conocimiento (argument of knowledge). Hace referencia a la información secreta que el probador conoce y que puede demostrar al verificador sin revelarla.

El probador y el verificador utilizan una clave compartida y secreta para generar y verificar las pruebas. La generación de la clave es un momento crítico del protocolo ya que si la entropía (aleatoriedad) utilizada para la generación de la clave cae en manos de un probador deshonesto, tendría mecanismos para engañar a un verificador. Dicho de otro modo pondría en entredicho la robustez (soundness) del protocolo.

ZK-STARKs

ZK-STARK es el acrónimo para zero-knowledge scalable argument of knowledge y son muy parecidos a los ZK-SNARKs excepto que son:

  • Escalables (scalable). Son mucho más rápidos que los ZK-SNARKs generando pruebas cuando el tamaño del conocimiento que no se quiere revelar es más grande. Tanto el tiempo empleado por el probador como por el verificador se incrementa ligeramente cuando el tamaño del conocimiento se incrementa mientras que en el caso de los ZK-SNARKs el tiempo utilizado es lineal al tamaño del secreto.
  • Transparentes (transparent). Utilizan fuentes de aleatoriedad públicamente verificables frente a las claves compartidas secretas utilizadas en los ZK-SNARKs.

Generalmente producen pruebas de mayor tamaño que los ZK-SNARKs y por tanto tienden a ser más costosos en recursos de almacenamiento (que en un blockchain se traduce en mayores comisiones de ejecución).

Aplicaciones

Las pruebas de conocimiento cero tienen muchas aplicaciones en diferentes campos como por ejemplo, el de la complejidad algorítmica o el de la criptografía.

Voy a centrarme exclusivamente en aplicaciones en el blockchain y que ya tienen sistemas implementados que las utilizan. Así nos quedamos en el mundo real y no en el de las ideas abstractas.

Pagos anónimos

En el mundo de los pagos tradicionales (pongamos por caso un pago con tarjeta de crédito) existen múltiples actores que pueden observar toda (o parte) de la información de cada pago: quién es el comprador, quién es el vendedor, dónde compra, cuánto le cuesta o, incluso, qué compra. Estos observadores pueden ser entidades tales como los esquemas de tarjetas, los bancos emisores y adquirientes, el gobierno, procesadores de pago, etcétera.

Si bien es cierto que debe haber mecanismos de protección de la sociedad frente al fraude, el blanqueo de capitales o la financiación del terrorismo, también debería existir el derecho del ciudadano honesto a mantener la privacidad de sus transacciones. Es un equilibrio complicado no bien resuelto aún.

En cualquier caso, la solución tecnológica para tener pagos totalmente anónimos existe y se basa en blockchains que incluyen en sus propios protocolos tecnología de pruebas de conocimiento cero. En estos blockchain ciertos atributos de las transacciones pueden hacerse invisibles a los observadores de la cadena. Estos atributos pueden incluir las direcciones del emisor y el receptor, el tipo de token, la cantidad o incluso los timestamps (el momento exacto de la ejecución de la transacción). Las pruebas de conocimiento cero permiten a los nodos del blockchain seguir operando con confianza pero sin tener acceso a estos detalles.

A diferencia de lo que se piensa, la mayor parte de los blockchains, incluyendo a Bitcoin o Ethereum, no son realmente anónimos. Todos los datos de las transacciones son visibles para cualquiera que observe los bloques de la cadena, bloques que no están encriptados. Lo único que pasa es que no hay un registro centralizado entre una dirección en el blockchain y una identidad, sin embargo, sin la capacidad de encriptar o ocultar estas direcciones, es muy fácil trazar las transacciones y acabar llegando a una identidad específica. Por ejemplo, para comprar una criptomoneda en algún momento tienes que hacer uso de algún exchange que las venda por dinero fiat y éste tiene la obligación de identificarte. En otro momento has podido compartir tu dirección en un marketplace o a un tercero para recibir un pago. La estructura del blockchain en realidad hace muy fácil hacer un seguimiento de las transacciones una vez se ha podido establecer un vínculo entre una dirección y un individuo.

Zcash y Monero son dos blockchains que nacen con el concepto de anonimidad por diseño y que ocultan la mayor parte de los atributos sus transacciones.

Otro proyecto interesante es (o fue) Tornado Cash, que trae el concepto de anonimidad a Ethereum (que recordemos tiene una arquitectura transparente). Tornado Cash es un servicio descentralizado que usa pruebas de conocimiento cero para ofuscar los detalles de las transacciones combinándolo con un algoritmo que mezcla las criptomonedas de varios usuarios. Curiosamente este protocolo fue sancionado por el Tesoro estadounidense pero al ser descentralizado es muy difícil acabar con su uso.

Computación verificable y escalado de L1’s

Uno de los problemas a los que se enfrentan los blockchains más populares (y por tanto más descentralizados y confiables) como Ethereum es al de la saturación. Es decir, a tener a muchos usuarios intentando ejecutar simultáneamente transacciones y smart contracts.

Esta saturación se traduce en dos efectos indeseados:

  1. se incrementa el tiempo de espera de ejecución de transacciones y smart contracts debido al alto uso de los recursos (nodos ejecutando el blockchain) y
  2. se incrementan las tarifas que los usuarios han de pagar a los validadores por la ejecución de sus transacciones o smart contracts debido a la alta competencia.

Una solución habitual consiste en delegar parte de la ejecución a un sistema externo al propio blockchain y después persistir los resultados de esa computación en el propio blockchain para poder beneficiarse de la seguridad que éste aporta. De esta manera se contribuye a disminuir la congestión y los tarifas a pagar en la cadena principal sin perder seguridad.

El blockchain principal suele denominarse L1 (por Level 1 en inglés) y el sistema al que se delega parte de la computación se le denomina L2 (por Level 2).

Para que el blockchain pueda estar seguro que la computación ejecutada en el sistema externo sea válida (sin errores o manipulaciones) se utilizan pruebas de conocimiento cero. En cuanto el L1 comprueba la validez de la prueba de conocimiento cero persiste el estado proporcionado por el sistema externo (L2) sin tener que ejecutar la computación por sí mismo.

Existen varios mecanismos de delegación de computación en un blokchain que usan pruebas de conocimiento cero entre los que destacan los zero-knowledge rollups (los más seguros) o los vallidiums.

L2BEAT es una web interesante que analiza el estado de la mayoría de soluciones L2 de Ethereum proporcionando métricas de ejecución en tiempo real, su estado de madurez y sus riesgos.

Protocolos de votación on-chain más seguros

Muchos protocolos blockchain (especialmente los DAOs), utilizan un utility token propio para votar sobre diferentes aspectos e implementar así la gobernanza del protocolo.

Un problema que tiene la votación en un blockchain donde toda la información es pública es que establece un entorno favorable a la compra de votos: alguien que tenga los suficientes recursos puede sobornar a un votante para que cambie el sentido de su voto.

Por el contrario si la votación no es transparente, desaparece en gran parte el incentivo para el sobornador porque no tiene manera de comprobar si el sobornado ha votado en el sentido que le ha sugerido: podría aceptar el soborno y votar cualquier cosa.

Sin embargo si hacemos que la votación con un algoritmo “ingénuo” que oculta la información, la comunidad no tiene garantías que los votos se hayan contabilizado de forma honesta.

Existen soluciones como MACI (Minimum Anti-Collusion Infrastructure) que usan protocolos de prueba cero que garantizan la contabilidad correcta sin mostrar el sentido de los votos.

Potocolos de identidad descentralizada o auto-identidad soberana

Los protocolos de identidad descentralizada también conocida como auto-identidad soberana (en inglés self-sovereign identity) permiten a los individuos gestionar su identidad digital controlando de forma autónoma qué piezas de información de su identidad desean ceder a terceros. Estos terceros pueden ser webs, servicios u otras aplicaciones gestionadas por todo tipo de instituciones estatales o privadas. La gestión de la identidad la realiza el propio individuo sin depender de una autoridad intermediaria o centralizada.

CanDID es una plataforma de identidad descentralizada que utiliza tecnología de ZKP para probar que algún predicado sobre la identidad sin revelar la información subyacente.

Por ejemplo, imaginemos que un cierto servicio en Internet sólo puede ofrecerse a usuarios adultos. En un mundo centralizado, ese servicio tendrá que solicitar al usuario una credencial, por ejemplo su carnet de identidad, verificar la edad y posiblemente almacenar el documento. Para satisfacer la obligación de ofrecer el servicio sólo a adultos, el usuario ha tenido que revelar una gran cantidad de información personal contenida en un documento oficial (¡no sólo la edad!).

En un mundo descentralizado, el servicio sólo tendría que hacer la pregunta: “¿es este usuario adulto?” y la plataforma de identidad descentralizada contestaría “sí” junto con una ZKP que garantiza la veracidad. Nótese que en este caso ni siquiera se ha revelado la edad real, sólo el hecho que el usuario es un adulto.

Desventajas

Coste del hardware

La generación de pruebas de conocimiento cero requiere cálculos muy complejos que en general se ejecutan mucho mejor sobre hardware especializado mucho más caro que las máquinas de propósito general.

Costes derivados de verificar las pruebas en el propio blockchain

La verificación de las pruebas generadas dentro de los smart contracts en el blockchain también es costoso.

Por ejemplo, en Ethereum cada operación tiene asignado un coste en una unidad que se denomina gas. Cuanto más complicada es la computación más gas requiere. El gas tiene un precio en ETH (el ether, abreviado ETH es la moneda nativa del blockchain Ethereum). Este precio puede fluctuar en función de diferentes condiciones. Para ejecutar una computación en el blockchain tienes que comprar el gas necesario o la transacción se abortará (y no se retornará nada del gas consumido).

Un zero-knowledge rollup paga aproximadamente 500.000 unidades de gas para verificar un solo ZK-SNARK (sin tener en cuenta el resto de cosas que pueda hacer el smart contract). Para poner este coste en contexto, una transacción en la que un usario envía a otro una cierta cantidad de ETH tiene un coste de 21.000 unidades de gas. Los ZK-TARKs son todavía más caros.

Asunciones de confianza

Sin entrar en mucho detalle técnico, en el momento actual los protocolos que usan ZK-SNARKs no tienen manera de demostrar a los usuarios que las partes participantes en el protocolo son honestas y deben aceptar la palabra de los desarrolladores.

Por su parte los ZK-STARKs están libres de sospechas ya que las fuentes de aleatoriedad utilizadas son públicamente visibles.

La amenaza de la computación cuántica

El algoritmo criptográfico utilizado por los ZK-SNARKs (ECDSA) es seguro por el momento pero el desarrollo de los ordenadores cuánticos podría romper su modelo de seguridad en el futuro.

Afortunadamente los ZK-STARKs se consideran inmunes a la computación cuántica porque utilizan hashes con una resistencia fuerte a colisión para la encriptación que son algoritmos más difíciles de romper usando algoritmos cuánticos.

Referencias