logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro