Analysis of the Principles of Binius STARKs and Thoughts on Optimization
1 Introduction
One of the main reasons for the low efficiency of STARKs is that most of the values in actual programs are quite small, such as indices in for loops, boolean values, counters, etc. However, to ensure the security of proofs based on Merkle trees, when data is expanded using Reed-Solomon coding, many additional redundant values occupy the entire field, even though the original values themselves are very small. To solve this problem, reducing the size of the field has become a key strategy.
The first generation of STARKs has a coding width of 252 bits, the second generation has a coding width of 64 bits, and the third generation has a coding width of 32 bits. However, the 32-bit coding width still has a lot of wasted space. In comparison, the binary field allows for direct bit manipulation, making the encoding compact and efficient without any wasted space.