Las Crónicas de ZK: Esquemas de Compromiso (Parte 2)

A lo largo de los dos artículos anteriores, estuve dando indicios de cómo los sistemas ZK modernos dependen de formas de, hablando en términos generales, codificar circuitos como polinomios.

Si bien todavía no tenemos el contexto completo de cómo va a funcionar esto, usar esta estrategia nos va a requerir diseñar un nuevo tipo de esquema de compromiso. Ya no vamos a comprometernos a valores individuales, sino a los polinomios en sí mismos.

Supongo que esto puede sonar raro al principio. Pero en realidad es algo que insinuamos hace mucho tiempo, cuando aprendimos sobre el protocolo de la verificación de la suma.

Hay que ejercitar un poco esos músculos de la memoria!

En aquel momento hablamos de tener acceso de oráculo para algún polinomio, pero en realidad no sabíamos cómo hacer eso.

Hoy es el momento de develar ese misterio. Y al hacerlo, tendremos todo listo en materia de preparativos, y estaremos completamente preparados para volver a estudiar nuevos protocolos.

¿Listos? ¡Vamos!

Motivación

Creo que es una buena idea empezar imaginando para qué vamos a estar utilizando todo este asunto de "comprometerse a un polinomio".

La idea principal es bastante directa, de hecho: en lugar de revisar todas las compuertas de un circuito, nos gustaría muestrear algunas restricciones al azar.

Por ejemplo, los cables que se conectan a una compuerta de multiplicación deberían seguir la relación esperada $a \cdot b = c$. O quizás, queremos requerir que algunos cables $x$, $y$, y $z$ tengan el mismo valor.

Luego queremos evaluar los polinomios de codificación en las posiciones que nos dan la información que necesitamos para verificar la restricción deseada, y después simplemente verificamos que la restricción se cumpla.

Suena fácil, ¿no?

Como ya habrán aprendido a esperar a esta altura, nunca es tan simple. El problema en este caso es que estos polinomios de codificación van a ser al menos tan grandes como los circuitos originales... ¡así que enviarle estos polinomios a un verificador no es mucho mejor que simplemente enviar compromisos de todos los cables!

Como hicimos en nuestro ejemplo de Protocolos Sigma. Recuerden, no era una estrategia muy escalable.

Para que esto funcione entonces, vamos a necesitar un acercamiento diferente. Así que acá va una idea: ¿qué tal si evitamos compartir el polinomio por completo?

Esencialmente, podríamos intentar idear una forma de que un verificador pueda solicitar evaluaciones. Esta es la configuración que originalmente llamamos acceso de oráculo de un polinomio: uno no calcula las evaluaciones por sí mismo, sino que delega la carga de trabajo a un tercero "confiable".

Confianza, sin embargo, es una palabra que debemos usar con cautela. Y en el caso de un probador que intenta convencer a un verificador, simplemente confiar en que el primero entregue evaluaciones correctas es una receta para el desastre.

¡Porque abre la posibilidad a todo tipo de trampas!

Así que en realidad, lo que buscamos es una forma de solicitar evaluaciones verificables: pido la evaluación de algún polinomio $P(X)$ en algún valor $a$, ustedes lo calculan, pero no solo responden con $P(a)$, sino también con una pequeña prueba de validez o correctitud.

Esta es la esencia de los esquemas de compromiso que vamos a estudiar hoy: esquemas de compromiso polinomiales, o PCS para abreviar (por sus siglas en inglés). Vamos a ver que la prueba de correctitud usualmente se valida contra un compromiso inicial del polinomio en cuestión - que es la razón por la cual estas técnicas se llaman esquemas de compromiso en primer lugar.

¡Genial! Eso es más o menos suficiente preámbulo para que entendamos hacia dónde va todo esto.

¡Empecemos con algo simple!

Árboles de Merkle

El primerísimo tipo de esquema de compromiso de polinomios del que vamos a hablar es uno que ya mencionamos. La estrategia es voluminosa, pero directa: ¡simplemente nos comprometemos con todos los valores funcionales posibles de una vez!

¡Así es!

Ya vimos esto en acción: todo lo que hacemos es calcular una raíz, y luego probamos inclusión mediante un camino de Merkle. ¡Más fácil, imposible!

Limitaciones

Sin embargo, cuando hablamos de esta idea por primera vez hace un par de artículos, inmediatamente detectamos un problema con el enfoque. Notamos que esta es una buena forma de comprometerse con una cantidad de valores, pero ¿cómo sabemos que estos valores realmente vienen de un polinomio?

En efecto, los árboles de Merkle son una excelente forma de comprometerse con $n$ valores arbitrarios, pero probar que son evaluaciones polinomiales requiere un poco de esfuerzo extra.

La solución viene en la forma de una técnica llamada Pruebas Interactivas de Oráculo Reed-Solomon Rápidas (o FRI, para abreviar).

Sí, el nombre suena aterrador, lo sé. Y en realidad es bastante complejo, así que vamos a dejar los detalles para más adelante, para cuando veamos un tipo de sistema de prueba llamado STARK.

Aunque no es necesario entrar en detalles, hay algo que les puedo adelantar: lo máximo que FRI puede hacer es mostrar que el polinomio comprometido tiene un grado menor que algún límite superior $d$. ¡Eso es todo lo que podemos saber!

Eso va a ser suficiente en algunos contextos, pero en la mayoría de los casos, no lo será. A menudo vamos a necesitar garantías más fuertes, lo que en nuestro caso significa obtener límites de grado exactos.

¿Por qué? Bueno, ¿recuerdan que dijimos que íbamos a codificar circuitos como polinomios? El éxito de la estrategia de codificación depende de una relación precisa entre el tamaño del circuito y el grado del polinomio.

Definitivamente es posible obtener estas garantías. Pero para eso, vamos a necesitar otra pieza más de maquinaria criptográfica.

Emparejamientos

Desde que introdujimos los grupos en nuestro conjunto de herramientas, cada construcción que produjimos ha vivido en un único grupo. Eso está perfectamente bien, porque siempre aprovechamos el problema del logaritmo discreto, así que todo está construido sobre una base de seguridad sólida.

Pero por desgracia, hay un límite a lo que se puede hacer con un solo grupo.

En particular, el esquema de compromiso que vamos a mirar más adelante está basado en algo que ya sabemos que es problemático: multiplicar exponentes. Recuerden, sumar exponentes es fácil:

$$g^a \cdot g^b = g^{a + b}$$

¿Pero multiplicarlos? No hay caso. Al menos, si solo consideramos las operaciones de grupo estándar.

Por suerte para nosotros, hay un artefacto que podemos usar para hacer justamente esto: ¡los emparejamientos! Existen exactamente por esta razón: nos permiten, en cierto sentido, multiplicar elementos de distintos grupos.

Suena como una tarea simple, pero en realidad es extremadamente complejo hacerlo bien. Las matemáticas detrás de ellos son tan elegantes como crípticas, así que no nos vamos a sumergir en los mecanismos internos que hacen posibles los emparejamientos. Solo nos importa que existen, y que algún criptógrafo confiable ha implementado una buena librería que podemos usar.

Sin embargo, si realmente, realmente quieren saber cómo funcionan los emparejamientos, no los voy a detener. Es un tema maravilloso. Pueden leer más sobre ellos acá. Aunque quizás necesiten empezar acá para comprender algunos conceptos fundamentales importantes.

Definición y Propiedades

Vayamos entonces con las definiciones. Un emparejamiento es una función o mapa que toma dos entradas provenientes de distintos grupos, y produce una salida que pertenece a otro grupo más:

$$e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_t$$

Sin embargo, no todo mapa de este tipo es un emparejamiento. Para que se considere como tal, debe satisfacer una propiedad particular, llamada bilinealidad. Usando nuestra confiable notación exponencial, esta se puede resumir como:

$$e(g^a,h^b) = e(g,h)^{ab}$$

Esencialmente, la bilinealidad nos otorga la capacidad de mover la exponenciación de un lado a otro. Y esa simple reorganización nos permite hacer algunas cosas bastante geniales.

Para que esto quede un poco más completo, también debería mencionar que necesitamos que estos mapas sean no degenerados ($e(g, h) \neq 1$ para generadores $g$ y $h$), y eficientemente computables.

En resumen, eso es lo que es un emparejamiento. De nuevo, vamos a avanzar bajo el supuesto de que podemos encontrar tales funciones.

¡Bien! ¿Pero por qué son tan especiales estos mapas?

Diffie-Hellman Decisional

Bueno, en realidad, su existencia los hace especiales por las razones equivocadas: resulta que rompen un problema que solía considerarse difícil.

En criptografía, esto generalmente no es algo bueno.

Para entender completamente el poder de los emparejamientos entonces, necesitamos hablar de ese supuesto, relacionado con el problema del logaritmo discreto que conocemos tan bien.

La configuración es así: imaginen que tenemos un grupo grande, y les doy tres elementos del grupo: $g^a$, $g^b$, y $h$. La pregunta es simple: ¿pueden determinar si $h$ es igual a $g^{ab}$?

Piénsenlo por un momento. No estamos preguntando si $h$ es igual a $g^{a + b}$, ya que eso sería trivial. No, estamos preguntando sobre el producto de $a$ y $b$. Si conocemos $a$ y $b$ de antemano, podemos hacer el cálculo, claro. Pero ir en la dirección contraria nos requeriría resolver problemas de logaritmo discreto, que como sabemos, son muy difíciles de resolver.

Esto es lo que llamamos el problema Diffie-Hellman Decisional, o DDH para abreviar. Asumir que este problema es difícil es clave para la seguridad de algunos criptosistemas populares, como el intercambio de claves Diffie-Hellman y la encriptación ElGamal.

Pero acá está la cosa: los emparejamientos rompen DDH. Hay formas de crear lo que llamamos un auto-emparejamiento, que usa entradas del mismo grupo, y simplemente verificar esto:

$$e(g^a,g^b) = e(g,g^{ab})= e(g,h)$$

Y obtener nuestra respuesta.

Entonces, si los emparejamientos rompen DDH... ¿Son peligrosos entonces peligrosos?

¡Para nada! O al menos, lo serían, si fueran fáciles de encontrar.

Además, como nota al margen: noten que aunque podamos romper el DDH, el problema del logaritmo discreto (DLP) queda intacto. Es importante entender que son problemas diferentes. ¡Y la seguridad de cualquier método depende de en qué problema difícil se apoya!

Sin una dirección clara, construir un emparejamiento es como buscar una aguja en un pajar. Por lo tanto, los protocolos que dependen de la dificultad del DDH probablemente estén bien, porque se cree que encontrar un emparejamiento que se pueda usar para romperlos es prácticamente imposible.

Por el contrario, podemos producir emparejamientos si sabemos dónde buscar. Se construyen a partir de grupos de curvas elípticas, y no cualquiera de esos tampoco: hay un subconjunto de curvas llamadas curvas amigables con emparejamientos, que tienen características muy especiales que hacen que construir emparejamientos sea una realidad. Es solo en estas situaciones que el DDH es fácil.

Y acá va una opinión polémica: ¿romper el DDH es realmente algo malo? La respuesta depende del contexto: si lo usamos para romper protocolos, bueno, sí. ¿Pero y si en cambio pudiéramos construir cosas? ¡Entonces sería una bendición en lugar de una maldición!

¡Muy bien entonces! Ya tenemos lo que necesitamos para seguir adelante. Pero antes de saltar a lo bueno, hay algo importante que necesitamos comentar.

Preprocesamiento

El éxito y la eficiencia de los esquemas de compromiso de polinomios que estamos por ver dependen fuertemente de la existencia de un paso de preprocesamiento.

Podemos dividir estos procesos de setup en dos tipos: confiables y transparentes. Ambas producen un conjunto de parámetros públicos que luego se usan para elaborar pruebas de apertura, pero la diferencia principal entre estos tipos es que las preprocesamientos confiables requieren que se genere un valor secreto durante el proceso.

Y este valor es bastante molesto. Si no se descarta o destruye después del paso de setup, las consecuencias son devastadoras: ¡cualquiera que conozca este valor puede forjar pruebas válidas para afirmaciones falsas!

Por esta razón, a este valor secreto a menudo se le llama "residuo tóxico".

Es por eso que este tipo de setups son confiables: confiamos en que quien sea que ejecute el preprocesamiento va a descartar este valor. Por el contrario, los setups transparentes no necesitan estos secretos potencialmente dañinos, así que son una especie de estándar de oro en términos de seguridad.

Sin embargo, algunos esquemas de compromiso polinpmiales igual eligen optar por setups confiables. Y la pregunta obvia es ¿por qué? ¿Por qué elegir voluntariamente una estrategia que tiene una falla tan grande?

Dos razones, en realidad.

Primero, ¡porque nada es gratis! Los setup transparentes suelen venir con un costo de rendimiento. Y en nuestra búsqueda por construir sistemas de prueba eficientes, cada pizca de sobrecarga importa.

Segundo, los setups confiables no tienen que significar confiar ciegamente en una sola parte. Es por esto que estos setups a menudo se ejecutan como ceremonias, donde muchos participantes independientes pueden contribuir pequeños pedacitos de aleatoriedad, y los parámetros finales se derivan de todas las contribuciones combinadas. Así, el residuo tóxico nunca es conocido completamente por nadie.

Eso es todo lo que necesitan saber por ahora. Y con eso resuelto, finalmente podemos enfocarnos en los esquemas de compromiso en sí.

¡Volvámonos locos entonces! ¿Qué tipo de construcciones alocadas se nos pueden ocurrir?

KZG

Resulta que los emparejamientos nos dan exactamente la funcionalidad correcta para verificar aperturas de polinomios de formas casi mágicas.

Uno de los métodos más importantes a los que dan lugar se debe a Kate, Zaverucha, y Goldberg, y de manera similar a GKR en su elección de nombre, se popularizó como el esquema de compromiso de polinomios KZG.

El proceso tiene un total de tres pasos: preprocesamiento, compromiso, y apertura. Creo que es mejor abordarlos en ese orden exacto, incluso cuando la razón por la que las cosas se hacen de cierta manera no va a ser inmediatamente obvia.

¡Confíen en el proceso!

Un Setup Confiable

Entonces primero, tenemos el paso de preprocesamiento. La salida de este paso es lo que se llama una cadena de referencia estructurada (o SRS): un conjunto de elementos de grupo de tamaño $d$. Casualmente, este número $d$ va a ser el grado máximo de los polinomios con los que podemos comprometernos usando dicho SRS.

Esta es un setup confiable universal: ejecutamos el proceso una vez, y podemos usar esto para comprometernos con cualquier polinomio de grado a lo sumo $d$. Algunos otros métodos usan setups confiables por circuito, como vamos a ver más adelante. ¡En este sentido, los setups universales son más convenientes!

Derivar el SRS es en realidad bastante simple. Primero, necesitamos un grupo $\mathbb{G}$ de orden primo $p$, y un generador $g$. Luego, necesitamos muestrear un valor aleatorio distinto de cero del campo $\mathbb{F}_p$. Si llamamos a ese valor aleatorio $\tau$, entonces el SRS consiste en las siguientes potencias de $g$:

$$(g, g^\tau, g^{{\tau}^2}, g^{{\tau}^3}, \ ... , g^{{\tau}^d})$$

Naturalmente, el residuo tóxico del que hablamos es $τ$. Vamos a ver cómo podríamos forjar una prueba falsa en un momento - pero mientras tanto, noten que no podemos recuperar $τ$ a partir del SRS, ¡porque eso nos requeriría resolver un problema de logaritmo discreto!

Una vez que tenemos nuestro SRS, comprometerse con cualquier polinomio $Q(X)$ de grado a lo sumo $d$ es muy directo, ya que solo necesitamos calcular:

$$c = g^{Q(\tau)}$$

Esperen un segundo. ¿No acabamos de decir que $\tau$ tiene que descartarse absolutamente? Entonces, ¿cómo puede alguien calcular $c$, si $\tau$ es desconocido?

En efecto, el cálculo directo no es posible. Pero hay una solución alternativa inteligente que podemos usar, y tiene que ver con la forma precisa del SRS. Todo lo que necesitamos hacer es tomar los coeficientes $q_i$ de $Q(X)$, y luego calcular este producto de acá:

$$c = \prod_{i=0}^d {(g^{{\tau}^i})}^{q_i}$$

Puede parecer aterrador, pero todo lo que estamos haciendo ahí es tomar cada uno de los valores del SRS, elevarlos a su coeficiente correspondiente (es decir, que comparten el mismo índice), y luego simplemente multiplicar todo junto. Es fácil demostrar que esto es igual a $c$:

$$\prod_{i=0}^d {(g^{{\tau}^i})}^{q_i} = \prod_{i=0}^d g^{q_i{\tau}^i} = g^{\sum_{i=0}^d q_i{\tau}^i} = g^{Q(\tau)} = c$$

Eso es bastante satisfactorio en sí mismo, ¿no? También, noten que $c$ es un elemento de $\mathbb{G}$.

¡Genial! Tenemos nuestro compromiso, que se puede compartir con un verificador. Con esto en manos, ahora si que podemos enfocarnos en la acción de verdad.

Abriendo una Evaluación

El verificador puede ahora solicitar al probador, quien calculó el compromiso, que abra el polinomio en algún valor elegido, digamos $z$. Por supuesto, el probador va a calcular $v = Q(z)$, pero enviar ese valor por si solo no es suficiente: también hay que adjuntar una prueba de validez para que el verificador la verifique.

Click to zoom

Naturalmente, necesitamos descifrar cómo construir la prueba $\pi$. Y es acá donde las cosas se ponen un poco más complicadas.

Antes incluso de llegar a usar emparejamientos, primero necesitamos construir lo que se llama un polinomio testigo. Es un pequeño truco muy elegante, y necesita de nuestra atención ya que es una pieza crucial en el éxito de KZG.

Lo que hacemos es esencialmente transformar la afirmación $v = Q(z)$ en una forma más adecuada para verificar. Para esto, definimos el polinomio $H(X)$ como:

$$H(X) = Q(X) {-} v$$

A simple vista, esto parece bastante intrascendente. Sin embargo, sabemos algo sobre este polinomio que podemos usar a nuestro favor: tiene una raíz en $X = z$.

¡Siempre y cuando el probador sea honesto y realmente se cumpla $v = Q(z)$!

Si hay algo que sabemos sobre las raíces, es que podemos reescribir el polinomio como:

$$H(X) = Q(X) {-} v = W(X)(X-z)$$

Ese $W(X)$ de ahí es el polinomio cociente de $H(X)$ y $(X {-} z)$. En otras palabras, $(X {-} z)$ divide perfectamente a $H(X)$, sin dejar resto:

$$W(X) = \frac{Q(X) {-} v}{X {-} z}$$

Y, de nuevo, esto solo es cierto en la medida en que la evaluación $v = Q(z)$ sea correcta.

¡Perfecto! No precisamos más que eso, porque la prueba $\pi$ se calcula a partir de este polinomio testigo, y es simplemente:

$$\pi = g^{W(\tau)}$$

Donde usamos el SRS para calcular esto una vez más.

Sí, sé que es un poco confuso - pero todavía no llegamos a la parte más loca. Porque ahora, el verificador tiene que verificar esa prueba usando el compromiso original $c$. Esta es la parte donde se necesitan los emparejamientos.

Vamos a necesitar un auto-emparejamiento entre los grupos $\mathbb{G}$ y $\mathbb{G}_t$, y con él, el verificador va a checkear esta igualdad de acá:

$$e(c \cdot g^{-v}, g) \overset{?}{=} e(\pi, g^{\tau} \cdot g^{-z})$$

Como dirían los españoles, ¡flipante! Sugiero tomarse un respiro para asimilar completamente esta igualdad. De hecho, los invito a intentar verificar esa expresión para comprobar su correctitud - es un ejercicio divertido para comprender cómo funciona la bilinealidad. En esencia, lo que esto está haciendo es verificar que el compromiso y la prueba son consistentes, usando esa relación del polinomio testigo y la bilinealidad para atar todo junto.

Demostrar que es vinculante (binding) es un poco más complejo, pero la idea central es que producir una prueba válida $\pi$ para un $v$ incorrecto resulta ser equivalente a resolver una variante del problema DDH que discutimos antes, ¡que resulta seguir siendo difícil incluso para grupos amigables con emparejamientos!

¡Y eso es KZG en toda su gloria!

Rompiendo el Esquema

Antes de cerrar el capítulo sobre este método, sin embargo, quiero mostrarles exactamente qué tan fácil es romperlo con el conocimiento del secreto $\tau$, para que podamos entender claramente la importancia de descartarlo.

Supongamos por un segundo que $\tau$ es conocido. El verificador pide alguna apertura $Q(z)$, y aunque la evaluación correcta es $v = Q(z)$, nos gustaría convencerlo de que el resultado es en realidad algún otro valor $y$. ¿Qué necesitamos hacer para lograr esto?

Lo que necesitamos es forjar una prueba $\pi'$ para que pase la validación. ¡Eso es todo! Así que trabajemos hacia atrás desde ahí.

La verificación que se realiza depende de la estructura esperada del polinomio testigo: es posible dividir $Q(X) {-} v$ porque sabemos que hay una raíz en $X = z$. Esto nos da un conjunto de coeficientes que podemos usar para calcular $\pi$ usando el SRS, porque esa es la única forma de obtener $\pi$ sin conocer $\tau$.

Si intentamos calcular un polinomio testigo para el valor falso $y$, nos encontraríamos con un problema, porque $y$ no es una raíz de nuestro $H(X)$ original, y por lo tanto tendríamos un resto al dividir por $(X {-} z)$. Y entonces, esta expresión de acá no sería un polinomio, sino solo una función racional:

$$W’(X) = \frac{Q(X) {-} y}{X {-} z}$$

Pero... si conocemos $\tau$, ¿entonces a quién le importa? ¡Simplemente pueden calcular $W'(\tau)$ directamente! Y la prueba falsa sería directamente:

$$\pi‘ = g^{W’(\tau)}$$

Solo que esta vez, somos capaces de calcularla sin mayores dificultades.

Eso es todo. No hace falta mucho para producir esa prueba forjada, y de ahí la necesidad de deshacerse del valor secreto. Realmente es un residuo tóxico.

¡Uf! Fue un montón, ¿no?

Podríamos analizar esto más a fondo, pero creo que con eso alcanza por ahora.

Admito que mi cerebro quedó bastante frito después de escribir esto, ¡y me imagino que ustedes probablemente están en una situación similar mientras leen!

Lo interesante de KZG es que tanto el compromiso como la prueba son un único elemento de grupo. Eso es muy liviano, e ideal para mantener económicos algunos protocolos que vienen a continuación. Es un buen argumento de venta - pero es tan bueno como nuestra capacidad de mantener oculto ese valor secreto $\tau$.

Resumen

Y con eso, ¡tenemos nuestro primer esquema de compromiso polinomial completamente funcional!

Esto significa que tenemos al menos una forma de abordar esas consultas de oráculo de las que hablamos en encuentros anteriores. Esto no solo completa nuestra descripción del protocolo de la verificación de la suma (que parece haber sido hace siglos), sino que también habilita todo un nuevo mundo de posibilidades.

Claro, KZG no es la única solución posible (ya mencionamos FRI, pero también vamos a explorar otras opciones), y la investigación sigue produciendo PCS nuevos y mejorados que pueden hacer que la computación verificable sea incluso más eficiente.

Aunque, debo decir, KZG ya es una solución muy elegante, y especialmente liviana en términos de comunicación: tanto el compromiso con el polinomio como la prueba de correctitud son un único elemento de grupo. ¡Eso va a importar mucho cuando empecemos a incorporarlo en sistemas de prueba completos!

Y crucialmente, introdujimos una pieza de matemática importante que puede ser realmente útil: ¡los emparejamientos!

Quizás el aspecto más cuestionable de KZG es su setup confiable. He sido bastante insistente al respecto, porque sabemos que existe la posibilidad de setups más seguros.

Aunque hay detalles de por medio, es una dirección que definitivamente necesitamos explorar.

Para llegar ahí, a continuación vamos a hablar de toda una familia de argumentos de conocimiento, que comprenden un conjunto importante de ideas que son absolutamente imprescindibles en nuestra búsqueda del conocimiento cero.

Así que, ¡nos vemos en el próximo artículo!