HashToPoint & FalconDecompressor (Falcon‑512)

Этот репозиторий содержит два смарт‑контракта(реализованы в рамках Летней школы по криптографии 2025) для поддержки верификации постквантовых подписей Falcon‑512 в сети Ethereum:

1. HashToPoint.sol – реализация функции формирования «точки решётки» из сообщения (Hash‑to‑Point) с фиксацией солей и оптимизированным вызовом keccak256.
2. FalconDecompressor.sol – реализация функции декомпрессии (Decompress), восстанавливающей коэффициенты полинома из сжатого битового представления.

---

🔍 Назначение

Контракты предназначены для использования в механизме абстракции аккаунта (Account Abstraction, ERC‑4337) при верификации постквантовых подписей Falcon‑512 на Ethereum. Они позволяют:

• Преобразовать произвольное сообщение в набор полиномиальных коэффициентов по модулю q.
• Восстановить оригинальные коэффициенты подписи из компактного представления.

---

📦 Реализованные функции

HashToPoint.sol

• hash_to_point(uint256 q, uint256 n, string message) external view returns (uint256[] memory)
  Формирует массив из n чисел по модулю q из хеша сообщения.
• shake(string message) private view returns (bytes memory)
  Псевдо‑реализация SHAKE256 через 64 итерации keccak256(salt[i] || message) с фиксированными солью SALTS[i].

Эффективность

• Вариант оптимизирован: расход газа ≈ 750 000 вместо ≈ 5 000 000 у оригинала zkNOX.

FalconDecompressor.sol

• decompress(bytes calldata data, uint256 n) external payable returns (int256[] memory)
  Декодирует битовую строку data длиной ≥ 9·n бит, восстанавливая массив из n целых коэффициентов:
  1. Чтение бита знака;
  2. Чтение 7 младших бит абсолютного значения;
  3. Подсчёт количества старших нулевых бит (k) до первого единичного;
  4. Восстановление val = abs7 + (k << 7), с учётом знака.
  5. Проверка, что все оставшиеся биты нулевые.

Эффективность

• Средний расход газа на выполнение функции≈ 4 000 000.

---

⚙️ Оптимизация и сравнение

Функция	Вариант	Расход газа
Hash-to-point	Оптимизация	~750 000
Decompress	Наша версия	~4 000 000

---

🚀 Установка и использование

git clone git@github.com:kb-nik/hash-to-point-falcon512.git
cd hash-to-point-falcon512