Binius STARKsの原理分析とその最適化思考
1 はじめに
STARKsの効率が低下する主な理由の一つは、実際のプログラムでのほとんどの数値が小さいことであり、例えばforループのインデックス、真偽値、カウンターなどです。しかし、Merkleツリーに基づく証明の安全性を確保するために、Reed-Solomon符号を使用してデータを拡張する際、多くの追加の冗長値が全体の領域を占めてしまい、元の値自体が非常に小さい場合でもそうなります。この問題を解決するために、領域のサイズを減らすことが重要な戦略となりました。
第1世代STARKsのエンコーディングビット幅は252ビット、第2世代STARKsのエンコーディングビット幅は64ビット、第3世代STARKsのエンコーディングビット幅は32ビットですが、32ビットのエンコーディングビット幅には依然として大量の無駄なスペースが存在します。比較すると、バイナリフィールドはビットに直接操作を行うことを許可し、エンコーディングがコンパクトで効率的であり、無駄なスペースがありません。