Analyse des principes des STARKs de Binius et réflexion sur leur optimisation
1 Introduction
Une des principales raisons de l'inefficacité des STARKs est que la plupart des valeurs numériques dans les programmes réels sont relativement petites, comme les index dans les boucles for, les valeurs booléennes, les compteurs, etc. Cependant, pour garantir la sécurité des preuves basées sur les arbres de Merkle, l'utilisation du codage de Reed-Solomon pour étendre les données entraîne de nombreuses valeurs redondantes supplémentaires qui occupent tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, la réduction de la taille du domaine est devenue une stratégie clé.
Comme indiqué dans le tableau 1, la largeur de codage des STARKs de première génération est de 252 bits, celle des STARKs de deuxième génération est de 64 bits, et celle des STARKs de troisième génération est de 32 bits, mais la largeur de codage de 32 bits présente encore un grand espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, rendant le codage compact et efficace.