Análisis de los principios de Binius STARKs y reflexiones sobre su optimización
1 Introducción
A diferencia de los SNARKs basados en curvas elípticas, los STARKs pueden considerarse como SNARKs basados en hash. Una de las principales razones por las que los STARKs son ineficientes en la actualidad es que la mayoría de los valores numéricos en los programas reales son pequeños, como los índices de bucle, los valores booleanos, los contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al utilizar la codificación de Reed-Solomon para expandir los datos, muchos valores redundantes ocuparán todo el dominio, incluso si los valores originales son pequeños. Para resolver este problema, reducir el tamaño del dominio se convierte en una estrategia clave.
La primera generación de STARKs tiene un ancho de codificación de 252 bits, la segunda generación de 64 bits y la tercera generación de 32 bits, pero la codificación de 32 bits todavía tiene una gran cantidad de espacio desperdiciado. En comparación, el campo binario permite operar directamente sobre los bits, con una codificación compacta y eficiente sin desperdicio, que se puede considerar como la cuarta generación de STARK.