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