Bitlayer Research：Binius STARKs原理解析及其优化思考

作者: mutourend & lynndell, Bitlayer LabstUT币圈网 - 区块链数字货币实时行情平台

原文标题：《Binius STARKs Analysis and Its Optimization》tUT币圈网 - 区块链数字货币实时行情平台

原文链接：https://blog.bitlayer.org/Binius_STARKs_Analysis_and_Its_Optimization/tUT币圈网 - 区块链数字货币实时行情平台

摘要：第1,2,3代STARK证明系统位宽分别为252,64和32bit，编码效率虽有提高，但仍有浪费空间；Binius直接对位操作，编码紧凑高效，很可能是未来的第4代STARK。Binius使用基于塔式二进制域的算术化、改进版的HyperPlonk乘积与置换检查、小域多项式承诺等技术，从各个角度提升效率。在二进制域乘法、ZeroCheck、SumCheck、PCS等方面可进一步优化，以进一步提高证明速度和降低proof size。tUT币圈网 - 区块链数字货币实时行情平台

1 引言

区别于基于椭圆曲线的SNARKs，可将STARKs看成是hash-based SNARKs。当前STARKs效率低下的一个主要原因是：实际程序中的大多数数值都较小，如for循环中的索引、真假值、计数器等。然而，为了确保基于Merkle树证明的安全性，使用Reed-Solomon编码对数据进行扩展时，许多额外的冗余值会占据整个域，即使原始值本身非常小。为解决该问题，降低域的大小成为了关键策略。tUT币圈网 - 区块链数字货币实时行情平台

如表1所示，第1代STARKs编码位宽为252bit，第2代STARKs编码位宽为64bit，第3代STARKs编码位宽为32bit，但32bit编码位宽仍然存在大量的浪费空间。相较而言，二进制域允许直接对位进行操作，编码紧凑高效而无任意浪费空间，即第4代STARKs。tUT币圈网 - 区块链数字货币实时行情平台

表 1: STARKs 衍化路径