Analyse des principes STARKs de Binius et réflexions sur l'optimisation
1. Introduction
Une des principales raisons de l'inefficacité des STARKs est que la plupart des valeurs dans les programmes réels sont assez 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 Reed-Solomon pour étendre les données implique que de nombreuses valeurs redondantes supplémentaires occuperont 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 de gaspillage. En comparaison, le domaine binaire permet d'opérer directement sur les bits, ce qui rend le codage compact et efficace.