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