Binius STARKs 原理解析及其优化思考
1. 引言
与基于椭圆曲线的 SNARKs 不同,STARKs 可被视为基于哈希的 SNARKs。当前 STARKs 效率低下的一个主要原因是:实际程序中的大多数数值都较小,如 for 循环中的索引、布尔值、计数器等。然而,为了确保基于 Merkle 树证明的安全性,使用 Reed-Solomon 编码对数据进行扩展时,许多额外的冗余值会占据整个域,即使原始值本身非常小。为解决该问题,降低域的大小成为了关键策略。
第 1 代 STARKs 编码位宽为 252bit,第 2 代 STARKs 编码位宽为 64bit,第 3 代 STAR