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 pequeños, como los índices en los bucles for, valores booleanos, contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al extender los datos utilizando codificación de Reed-Solomon, muchos valores redundantes adicionales ocupan todo el dominio, incluso si el valor original en sí es muy pequeño. Para resolver este problema, reducir el tamaño del dominio se ha convertido en una estrategia clave.
Como se muestra en la Tabla 1, el ancho de codificación de la primera generación de STARKs es de 252 bits, el ancho de codificación de la segunda generación de STARKs es de 64 bits, y el ancho de codificación de la tercera generación de STARKs es de 32 bits, pero el ancho de codificación de 32 bits aún presenta un gran espacio desperdiciado. En comparación, el campo binario permite operar directamente sobre los bits, codificando de manera compacta y eficiente.