Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Основная причина низкой эффективности STARKs заключается в том, что большинство чисел в реальных программах довольно малы, например, индексы в циклах for, логические значения, счетчики и т. д. Однако для обеспечения безопасности доказательств на основе дерева Меркла, при расширении данных с помощью кодирования Рида-Соломона, многие дополнительные избыточные значения занимают весь диапазон, даже если оригинальные значения сами по себе очень малы. Для решения этой проблемы снижение размера диапазона стало ключевой стратегией.
Ширина кодирования STARKs первого поколения составляет 252 бита, второго поколения – 64 бита, третьего поколения – 32 бита, но 32-битная ширина кодирования по-прежнему имеет много неиспользуемого пространства. В сравнении с этим, двоичная область позволяет выполнять операции непосредственно над битами, кодирование компактно и эффективно, без произвольных потерь пространства.