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