Хеш-функция Tip5 на C++

Open Source project

Реализация хеш-функции Tip5 на C++

Tip5 hash implementation in C++

Tip5 hash implementation in C++ GitHub repository

Реализация хеш-функция Tip5 на C++
Реализция хеш-функции Tip5 на C++

О проекте

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

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

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

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

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

Технологии

  • Язык программирования: C++17
  • Система сборки: CMake
  • Фреймворк тестирования: Google Test
  • CI : GitHub Actions
  • Целевые платформы: GNU Linux, macOS, Windows

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

  • Alan Szepieniec, Alexander Lemmens, Jan Ferdinand Sauer, Bobbin Threadbare, Al-Kindi (2023). The Tip5 Hash Function for Recursive STARKs — Cryptology ePrint Archive, Paper 2023/107.
    https://eprint.iacr.org/2023/107

Хотите портировать, оптимизировать или исправить сложный алгоритм?

Объясню возможности и ограничения, реализую современный CI/CD-пайплайн, организую разработку