Binius STARKs原理解析及其优化思考
1. 引言
STARKs效率低下的一个主要原因是实际程序中大多数数值较小,但为确保基于Merkle树证明的安全性,使用Reed-Solomon编码对数据进行扩展时,许多额外的冗余值会占据整个域。降低域的大小成为了关键策略。
第1代STARKs编码位宽为252bit,第2代为64bit,第3代为32bit,但32bit编码位宽仍存在大量浪费空间。相较而言,二进制域允许直接对位操作,编码紧凑高效无任意浪费,即第4代STARKs。
相比近几年研究的Goldilocks、BabyBear、Mersenne31等有限域,二进制域研究可追溯到上世