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