Xэш-функция Tip5 на C++

О проекте

В рамках данного проекта была выполнена реализациz криптографической хеш-функции Tip5 на C++ на основе существующей реализации на Rust. Главная цель — эквивалентность алгоритма, при сохранении высокой производительности и удобстве интеграции в проекты на C++.

Tip5 — это специализированная криптографическая хеш-функция, разработанная для эффективного использования внутри STARK-доказательств, а особенно при их рекурсивной проверке. Ключевой задачей при проектировании Tip5 было обеспечить «арифметизацию» всех операций так, чтобы они сводились к низкостепенным многочленам над конечным полем, тем самым минимизировав стоимость их проверки в протоколе STARK. В алгоритме использется поле по модулю 2⁶⁴ – 2³² + 1 с быстрыми операциями умножения и редукции и возможностью эффективно строить FFT-преобразования.

Архитектура Tip5 опирается на стратегию SHARK: чередование нелинейного «S-блока» и изотонической («линейной») смеси («ARK»). В качестве S-блока используется функция отображение x ↦ x⁵, что сохраняет степень многочленов при арифметизации невысокой. Линейный шаг реализован через умножение на заранее заданную невырожденную матрицу, обеспечивающую достаточную диффузию. Для ускорения валидации внутри STARK добавлены lookup-таблицы, позволяющие проверять значение степенного отображения и умножения по готовым префиксным таблицам вместо непосредственного построения высокостепенных полиномов.

Для хеширования длинных сообщений Tip5 использует конструкцию «губка»: порция данных («rate») обрабатывается блоками по несколько полейных элементов, а оставшаяся часть («capacity») гарантирует безопасность в режиме Merkle-деревьев и протокола Фиата–Шамира. Благодаря небольшой числу раундов (например, порядка 8–12 для рекомендуемых параметров) и низкой арифметической сложности Tip5 демонстрирует высокую пропускную способность на CPU, сопоставимую с популярными хеш-функциями, при этом оставаясь полностью верифицируемым в рамках STARK-доказательств.

В практических сценариях Tip5 применяется для построения Merkle-деревьев транзакций или состояний, а также в самом цикле рекурсивной проверки STARK, где хеш промежуточных доказательств должен быть вычислен и проверен внутри следующего доказательства. Это позволяет создавать иерархические или цепочные доказательства с практически линейным ростом затрат на верификацию, сохраняя при этом прозрачность и надежность.

Технологии

Теоретическая основа