Los protocolos interactivos holográficos de oráculo polinómico de tiempo lineal con verificación de tiempo logarítmico para sistemas de restricciones de rango-1 del protocolo de búsqueda
Autores: Zhang, Shuangjun
Idioma: Inglés
Editor: MDPI
Año: 2025
Acceso abierto
Artículo científico
2025
Los protocolos interactivos holográficos de oráculo polinómico de tiempo lineal con verificación de tiempo logarítmico para sistemas de restricciones de rango-1 del protocolo de búsqueda
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Polinomio
Iop holográfico
Snark
R1cs
Protocolo de sumcheck
Orion
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 20
Citaciones: Sin citaciones
Los SNARKs modernos se construyen utilizando Pruebas de Oráculo Interactivas polinómicas (IOPs) y compromisos polinómicos. En este trabajo, presentamos un novedoso IOP holográfico polinómico para el lenguaje completo Rank-1 Constraint System (R1CS), donde holográfico IOP significa que el sistema de prueba admite preprocesamiento. Nuestra construcción logra una demostración de tiempo lineal, verificación de tiempo logarítmico y complejidad de consulta constante. Para una instancia R1CS con tamaño (n) sobre un campo finito suficientemente grande, el tiempo del probador es (n), el tiempo del verificador es (log n), y la complejidad de consulta es (1). Al combinar nuestro IOP holográfico polinómico con el reciente esquema de compromiso polinómico Orion, obtenemos un SNARK transparente para R1CS con un rendimiento notable: el tiempo del probador es (n), el tiempo del verificador es (log n), y el tamaño de la prueba es (log n). La técnica principal en nuestra construcción es el protocolo clásico SumCheck, que nos permite verificar eficientemente si un polinomio n-variado suma a un valor específico en un dominio dado, como {0, 1}. Además, mostramos cómo lograr la holografía a partir del protocolo de búsqueda, lo que nos permite verificar eficientemente que todos los elementos en un vector estén contenidos en otro vector. Introducimos un nuevo IOP polinómico para la relación de búsqueda con un probador de tiempo lineal.
Descripción
Los SNARKs modernos se construyen utilizando Pruebas de Oráculo Interactivas polinómicas (IOPs) y compromisos polinómicos. En este trabajo, presentamos un novedoso IOP holográfico polinómico para el lenguaje completo Rank-1 Constraint System (R1CS), donde holográfico IOP significa que el sistema de prueba admite preprocesamiento. Nuestra construcción logra una demostración de tiempo lineal, verificación de tiempo logarítmico y complejidad de consulta constante. Para una instancia R1CS con tamaño (n) sobre un campo finito suficientemente grande, el tiempo del probador es (n), el tiempo del verificador es (log n), y la complejidad de consulta es (1). Al combinar nuestro IOP holográfico polinómico con el reciente esquema de compromiso polinómico Orion, obtenemos un SNARK transparente para R1CS con un rendimiento notable: el tiempo del probador es (n), el tiempo del verificador es (log n), y el tamaño de la prueba es (log n). La técnica principal en nuestra construcción es el protocolo clásico SumCheck, que nos permite verificar eficientemente si un polinomio n-variado suma a un valor específico en un dominio dado, como {0, 1}. Además, mostramos cómo lograr la holografía a partir del protocolo de búsqueda, lo que nos permite verificar eficientemente que todos los elementos en un vector estén contenidos en otro vector. Introducimos un nuevo IOP polinómico para la relación de búsqueda con un probador de tiempo lineal.