Protocols for Univariate Sumcheck

Resumen Técnico: Protocolos para Sumcheck Univariable

1. El Problema

En el ámbito de las pruebas de conocimiento cero (SNARKs), los datos se codifican comúnmente como polinomios. Existen dos enfoques principales para representar estos datos:

1. Sistemas Multivariados: Utilizan la extensión multilineal de un vector de datos ($mlex$). El protocolo estándar de sumcheck (verificación de suma) para estos sistemas es eficiente para el probador (tiempo lineal), pero requiere múltiples rondas de interacción ($m$ rondas), lo que aumenta el ancho de banda y la carga del verificador.
2. Sistemas Univariados: Utilizan la extensión univariable de Lagrange sobre raíces de la unidad ($unex$). El protocolo estándar aquí (como Aurora) es de una sola ronda (muy eficiente para el verificador), pero históricamente ha carecido de una versión con tiempo de probador lineal, a menudo requiriendo tiempos cuasilineales o dependientes de adaptadores complejos.

La brecha: Existe una separación clara en el diseño criptográfico. Los sistemas univariados carecían de un protocolo de sumcheck que combinara la eficiencia del probador de los sistemas multivariados con la eficiencia del verificador de los sistemas univariados. Además, los intentos previos de adaptar técnicas multivariadas a dominios univariados (usando "adaptadores" de "mundo opuesto") a menudo introducían sobrecargas en la traducción de bases o tiempos de ejecución no óptimos.

2. Metodología y Enfoque

El autor propone tres enfoques candidatos para realizar un sumcheck univariable sobre raíces de la unidad con tiempo lineal para el probador. La metodología se basa en reducir el problema univariable a problemas multivariados o utilizar reducciones directas a protocolos existentes como Gemini (Bootle et al., Eurocrypt 2022).

Los tres enfoques principales son:

• A. Reducción de $mlex$a$unex$ (Protocolo 2):

  • Se presenta un protocolo de plegado recursivo lineal que identifica la extensión multilineal ($mlex$) con la univariable ($unex$).
  • Utiliza una descomposición de "cuadrado" y "no-cuadrado" de los polinomios sobre raíces de la unidad.
  • Permite ejecutar el protocolo estándar de sumcheck multivariable sobre oráculos univariados sin necesidad de traducción de bases costosa (a diferencia de métodos previos como los de Papini-Haböck o Ganesh et al.).

• B. Reducción Directa de Identidad de Dominio (Protocolo 3 - Corrección de DGM):

  • Analiza y corrige un protocolo propuesto previamente por Drake, Gabizon y Meckler (DGM) para la identidad de dominio.
  • Se identifica un fallo en la versión original de DGM (la ecuación de verificación no era una identidad polinomial válida debido a diferencias de grado).
  • Se propone una versión corregida que introduce polinomios auxiliares para verificar la consistencia de los coeficientes y grados, permitiendo una reducción recursiva hacia evaluaciones multilineales.

• C. Reducción Directa de Sumcheck (Protocolo 4):

  • Este es el enfoque más eficiente. En lugar de pasar por la identidad de dominio, reduce directamente la suma univariable a una evaluación multilineal.
  • Aprovecha la relación entre la evaluación de un polinomio univariable en raíces de la unidad y la evaluación de su contraparte multilineal en puntos específicos de la hipercubo booleano.
  • El protocolo es estructuralmente idéntico al sumcheck multivariable estándar pero aplicado directamente al dominio univariable, evitando intermediarios innecesarios.

Reducción de Rondas:
El artículo también explora cómo reducir el número de rondas de $m$ a $\log(m)$ o incluso $O(\sqrt{m})$. Esto se logra deteniendo el protocolo recursivo temprano (después de $k$ rondas) y utilizando un protocolo de una sola ronda (como Aurora) para el reclamo residual más pequeño. A diferencia de trabajos anteriores (como HybridPlonk), esta transformación no introduce sobrecarga adicional ni depende de dominios de interpolación no estándar.

3. Contribuciones Clave

1. Protocolo de Plegado Lineal (Protocolo 2): Un método lineal en tiempo para mapear $mlex$a$unex$, permitiendo el uso directo de sumcheck multivariable sobre datos univariados sin sobrecarga de traducción de bases.
2. Corrección y Formalización de DGM: Se demuestra que el protocolo DGM original es defectuoso y se ofrece una versión corregida (Protocolo 3) que funciona como una reducción válida a Gemini.
3. Protocolo de Sumcheck Directo (Protocolo 4): La contribución más significativa. Es la solución más simple y eficiente, que reduce el sumcheck univariable directamente a Gemini con un tiempo de probador estrictamente lineal ($O(d^2 m)$ o similar, dependiendo de los parámetros) y sin los pasos intermedios de identidad de dominio.
4. Análisis de Rondas: Se demuestra que estos protocolos admiten reducciones naturales de rondas ($\log(m)$ o $O(\sqrt{m})$) manteniendo la eficiencia lineal del probador, superando las limitaciones de enfoques híbridos anteriores.
5. Tabla Comparativa: Se proporciona una comparación exhaustiva (Tabla 2) que muestra que los nuevos protocolos superan a los enfoques estándar (como Aurora puro) en eficiencia del probador, acercándose a la eficiencia de los sistemas multivariados.

4. Resultados

• Eficiencia del Probador: Los protocolos propuestos logran tiempo de ejecución lineal para el probador, una característica que antes era exclusiva de los sistemas multivariados.
• Eficiencia del Verificador: Se mantiene la ventaja de los sistemas univariados, permitiendo configuraciones de una sola ronda o con muy pocas rondas ($\log(m)$), lo que reduce drásticamente el ancho de banda y la carga computacional del verificador.
• Comparación con Gemini: La combinación del Protocolo 4 con Gemini es más eficiente que la combinación de sumcheck multivariable estándar con adaptadores, ya que Gemini envía la mitad de oráculos que los adaptadores tradicionales.
• Corrección de Fallos: Se ha identificado y resuelto un error fundamental en la literatura reciente (protocolo DGM), proporcionando una base sólida para futuras implementaciones.

5. Significado e Impacto

Este trabajo cierra una brecha importante en la teoría de SNARKs. Demuestra que el sumcheck univariable de tiempo lineal es genéricamente alcanzable para polinomios preexistentes ($unex$).

• Unificación de Sistemas: Permite que los sistemas univariados (que son populares por su simplicidad y eficiencia de verificación) disfruten de la eficiencia del probador que antes solo tenían los sistemas multivariados.
• Optimización de SNARKs: Cualquier caso de uso actual del protocolo Aurora (o similares) puede beneficiarse de estas mejoras, obteniendo una eficiencia del probador previamente reservada para el "mundo" de los datos multivariados.
• Flexibilidad: La capacidad de ajustar el número de rondas (desde $m$ hasta $O(\sqrt{m})$) sin penalizaciones de rendimiento ofrece a los ingenieros de criptografía un nuevo grado de libertad para optimizar el equilibrio entre ancho de banda, tiempo de verificación y tiempo de prueba según sus necesidades específicas.

En resumen, el artículo proporciona las herramientas teóricas y prácticas necesarias para construir SNARKs univariados de alto rendimiento que no comprometan ni la velocidad del probador ni la eficiencia del verificador.