Протоколы ZK используют специальные хеш-функции, которые алгебраически просты. Но если наша система доказательств поддерживала бы таблицы поиска, могли бы мы сделать лучше? Представляем Polocolo: новую хеш-функцию, дружелюбную к ZK, для PlonKup, соавтором которой является криптограф Zellic @baaaaaarkingdog.

В ZK-дружественных хеш-функциях функции алгебраически просты для повышения эффективности. Поэтому атака на ZK-дружественную хеш-функцию сосредоточена на проблеме ограниченного ввода и ограниченного вывода (CICO), так как решение системы уравнений обычно является наиболее эффективной атакой на ZK-дружественные хеш-функции. Хотя разработчики тщательно выбирают свои структуры и параметры с учетом этих векторов атак, атаки на ZK-дружественные хеш-функции все еще являются распространенной практикой.

Если система ZK-доказательств допускает только операции сложения и умножения, операции, которые нельзя представить алгебраически, просто требуют большого количества ограничений. Но если система ZK-доказательств поддерживает операции поиска, необходимое количество вентилей резко сокращается. Таким образом, основное преимущество использования вентилей поиска в ZK-дружественных хеш-функциях заключается в том, что они не выражаются простым алгебраическим способом, что может обеспечить устойчивость к алгебраическим атакам.

Усиленный бетон — это первая хеш-функция, основанная на поиске, совместимая с ZK, которая состоит из слоев Кирпичей, Бетона и Арматуры (именно здесь используются таблицы поиска). Однако ключевым недостатком является высокая стоимость оценки слоя Арматуры в ZK-окружении. Из 15 слоев в Усиленном бетоне только один является слоем Арматуры. Желательно и естественно итеративно обрабатывать простой слой в нескольких раундах, так как снижение стоимости слоя Арматуры и его итерация в нескольких раундах могут повысить безопасность и позволить найти компромисс между эффективностью и безопасностью. Это мотивирует дизайн Polocolo.

Чтобы решить проблему высокой стоимости в слое Bars, был предложен альтернативный подход, названный методом остатка от степени. Polocolo — это хеш-функция, основанная на поиске, совместимая с ZK, с другой концепцией дизайна. Название Polocolo происходит от остатка от степени для более дешевого поиска в таблице.

Метод остатка по степени эффективно применяет таблицы поиска к элементам Fp для большого простого числа: p(≈2^256). S-бокс, построенный с использованием метода остатка по степени, имеет высокую степень, которая требует всего 14 ворот PLONK, что значительно меньше, чем 94 ворот, необходимых для функции Bar из Reinforced Concrete. Используя этот S-бокс, мы предлагаем Polocolo, новую хеш-функцию, основанную на таблицах поиска и дружелюбную к ZK.

Polocolo был разработан криптографом Zellic @baaaaaarkingdog, членом KAIST CryptLab, вместе с другими исследователями из той же лаборатории. В Части 2 мы представим подробные спецификации и криптоанализ Polocolo, а также сравнение производительности с другими хэш-функциями, совместимыми с ZK.