Análisis del principio de Binius STARKs y reflexiones sobre su optimización
1 Introducción
Una de las principales razones de la baja eficiencia de STARKs es que la mayoría de los valores en los programas reales son bastante pequeños, como los índices en bucles for, valores booleanos, contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al expandir los datos utilizando codificación de Reed-Solomon, muchos valores redundantes adicionales ocuparán todo el dominio, incluso si el valor original es muy pequeño. Para resolver este problema, reducir el tamaño del dominio se ha convertido en una estrategia clave.
El ancho de banda de codificación de la primera generación de STARKs es de 252 bits, el ancho de banda de codificación de la segunda generación de STARKs es de 64 bits, y el ancho de banda de codificación de la tercera generación de STARKs es de 32 bits, pero el ancho de codificación de 32 bits todavía presenta un gran desperdicio de espacio. En comparación, el campo binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin desperdicio arbitrario de espacio.