Eurocrypt es una de las tres conferencias principales organizadas por la Asociación Internacional de Investigación Criptológica (IACR), la conferencia académica más famosa en criptografía. La Conferencia Internacional Anual sobre Teoría y Aplicaciones de Técnicas Criptográficas se celebra cada primavera en Europa. Esta serie de conferencias se celebró por primera vez en 1982 y Eurocrypt 2020 es la 39ª Conferencia Internacional sobre Teoría y Aplicación de la Criptografía, que se realizó como una conferencia virtual por primera vez.
Uno de los predecesores obvios e inmediatos de este trabajo es el documento titulado “Técnicas de procesamiento por lotes para acumuladores con aplicaciones a PIO y cadenas de bloques sin estado”, de Dan Boneh, Benedikt Bünz y Ben Fisch. En este artículo, los autores desarrollan herramientas basadas en grupos de orden desconocido para generar esquemas criptográficos como acumuladores y compromisos de vectores. Alan Szepieniec había estudiado estas herramientas y en un esfuerzo de investigación inicialmente no relacionado estaba buscando formas de mejorar el sistema de prueba STARK confiando en herramientas criptográficas más potentes que simples hashes.
En un evento poco después de Eurocrypt 2019, Alan se acercó a Benedikt con una pregunta sobre la aplicación de herramientas para grupos de orden desconocido a sistemas de prueba similares a STARK. La primera versión del protocolo principal se remonta a un correo electrónico de seguimiento escrito poco después de esa conversación. Un par de semanas después, Ben se unió al equipo, el protocolo principal se había convertido en algo casi irreconocible desde su primera versión, y el objetivo apropiado del proyecto había sido recalibrado no solo para producir una nueva herramienta en la caja de herramientas SNARK, ni para producir un nuevo SNARK transparente independiente, pero para reevaluar todo el campo de SNARK a la luz de los compiladores DARK que pueden hacerlos transparentes.
Los sistemas de prueba no interactivos producen una serie de datos criptográficos que dan fe de la ejecución honesta de un cálculo, llamada prueba. El probador, la parte que ejecuta el cálculo y genera la prueba, está sujeto a restricciones de recursos alternativas del verificador, la parte que verifica la corrección de la prueba. La naturaleza de esta disparidad de recursos da lugar a muchas preguntas de interés teórico y práctico. Sin embargo, en el contexto de la criptografía, generalmente nos centramos en dos tipos de disparidades de recursos. Primero, cuando al probador se le permite mucho más tiempo que al verificador, este último se caracteriza como sucinto y el sistema de prueba en su conjunto como un argumento sucinto de conocimiento no interactivo sucinto (SNARK). En segundo lugar, cuando el probador tiene acceso a información secreta y el verificador no lo está, se dice que el sistema de prueba proporciona conocimiento cero (ZK).
Los sistemas SNARK y a prueba de conocimiento cero (así como los zk-SNARK, que cuentan con lo mejor de ambos mundos) tienen aplicaciones inmediatas en blockchains porque sus propiedades, concisión y conocimiento cero logrados se traducen en escalabilidad y privacidad. En lugar de procesar una gran cantidad de bloques, un nodo sucinto puede verificar que la salida reclamada de este procesamiento sea realmente válida, con mucho menos trabajo; o en lugar de verificar un montón de firmas, un nodo sucinto puede verificar una pequeña prueba que atestigua la validez de todas las firmas de una sola vez. Del mismo modo, en lugar de exponer información confidencial crucial para modificar o actuar en un contrato inteligente, el propietario simplemente puede proporcionar la actualización necesaria junto con un zk-SNARK que permite al resto de la red verificar la corrección de la actualización.
Hasta ahora, solo había dos bases criptográficas para generar SNARK. El primer método, que tiene su origen en el teorema original de PCP, es a través de los árboles Merkle de las palabras de código Reed-Solomon y se representa mejor en el sistema de prueba STARK. Si bien las pruebas resultantes se verifican rápidamente, tienen un tamaño de más de cientos de kilobytes. El segundo método es a través de curvas elípticas equipadas con mapas bilineales criptográficos, también conocidos como emparejamientos. Si bien el tamaño de prueba aquí es pequeño, cientos de bytes, el inconveniente es que este tamaño solo se puede lograr a expensas de un procedimiento de configuración confiable.
Construimos un nuevo esquema de compromiso polinómico para polinomios univariados y multivariados sobre campos finitos, con pruebas de evaluación de tamaño logarítmico y tiempo de verificación, medidos en el número de coeficientes del polinomio. La técnica subyacente es un argumento de conocimiento diofantino (OSCURO), que aprovecha representaciones enteras de polinomios y grupos de orden desconocido. La seguridad se muestra desde el fuerte RSA y los supuestos de raíz adaptativa. Además, el esquema no requiere una configuración confiable si se instancia con grupos de clase. Aplicamos este nuevo compilador criptográfico a una clase restringida de PIO lineales algebraicos, que llamamos PIO polinomiales, para obtener argumentos de conocimiento interactivos de monedas públicas doblemente eficientes para cualquier relación NP con comunicación sucinta. Con el preprocesamiento lineal, el trabajo del verificador en línea es logarítmico en la complejidad del circuito de la relación.
Hay muchos ejemplos existentes de PIO polinomiales (PIOP) que se remontan al primer PCP (BFLS, STOC’91). Presentamos una compilación genérica de cualquier PIOP utilizando nuestro esquema de compromiso polinómico DARK. En particular, compilar el PIOP de PLONK (GWC, ePrint'19), una mejora en Sonic (MBKM, CCS'19), produce un argumento interactivo de monedas públicas con preprocesamiento cuasi-lineal, tiempo de prueba cuasi-lineal (en línea), comunicación logarítmica y tiempo de verificación logarítmica (en línea) en el tamaño del circuito. La aplicación de Fiat-Shamir da como resultado un SNARK, que llamamos Supersonic.
Supersonic también es concretamente eficiente con pruebas de 10 KB y menos de 100 ms de tiempo de verificación para circuitos con 1 millón de puertas (estimado para seguridad de 120 bits). Lo más importante, este SNARK es transparente: no requiere una configuración confiable. Obtenemos zk-SNARK aplicando una variante oculta de nuestro esquema de compromiso polinómico con evaluaciones de conocimiento cero. Supersonic es el primer sistema zk-SNARK completo que tiene tanto un tiempo de prueba práctico como un tamaño de prueba y tiempo de verificación asintóticamente （estrictamente） logarítmico.