Análisis del principio de Binius STARKs y reflexiones sobre la optimización
1. Introducción
Una de las principales razones de la baja eficiencia de los STARKs es que la mayoría de los valores numéricos en los programas reales son bastante pequeños, como los índices en un bucle for, los valores booleanos, los contadores, etc. Sin embargo, para garantizar la seguridad de las pruebas basadas en árboles de Merkle, al usar la codificación de Reed-Solomon para expandir los datos, muchos valores redundantes adicionales ocuparán todo el campo, incluso si el valor original en sí es muy pequeño. Para resolver este problema, reducir el tamaño del campo 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 todavía presenta un gran desperdicio de espacio. En comparación, el campo binario permite operar directamente sobre los bits, codificando de manera compacta y eficiente.