Хеш-функции: фундамент блокчейна

Цели урока

• Понимать принцип работы SHA-256 и её применение в блокчейне
• Объяснять collision resistance и почему коллизии SHA-256 практически не находятся
• Различать хеширование и шифрование как два разных инструмента
• Понимать эффект лавины и его роль в Proof of Work

SHA-256 - 32 байта выхода. Bitcoin: 1 хеш вычисляется за ~20 мкс. Весь мир делает 600 экзахешей/с в поисках одного блока. Каждую секунду. Это больше, чем все компьютеры 2000 года вместе. За этой мощью - одна математическая функция.

• **Bitcoin mining** - 600 экзахешей SHA-256 каждую секунду ищут nonce для одного блока каждые ~10 минут
• **Git** - каждый коммит идентифицируется хешем SHA-1 (переходят на SHA-256). `git log` показывает эти хеши
• **HTTPS** - Certificate Transparency logs: хеши всех TLS-сертификатов публично верифицируются через Merkle trees
• **Цифровые подписи** - ECDSA и Ed25519 подписывают хеш сообщения, а не само сообщение: сначала SHA-256, потом подпись
• **Проверка целостности** - файлы Linux ISO поставляются с SHA-256 checksums: изменение одного байта даёт полностью другой хеш
• **Пароли** - sites хранят Argon2id(password), не пароль. SHA-256 для паролей небезопасен из-за GPU-скорости: 10^10 хешей/с

Ralph Merkle, NSA и история SHA

1979 год. Ralph Merkle публикует конструкцию Merkle-Damgard - основу большинства хеш-функций, включая SHA-256. Параллельно описывает Merkle trees - структуры, которые 30 лет спустя станут фундаментом Bitcoin. 1993 год: NSA разрабатывает SHA-0, публикует через NIST. Уязвимость найдена быстро. 1995 - SHA-1. 2001 - SHA-2 (включая SHA-256). 2012 - открытый конкурс NIST, победитель Keccak, стандарт SHA-3. 2017 - Google SHAttered: первая коллизия SHA-1 за 6500 лет CPU-времени и 110 лет GPU-времени, стоимость ~110 000 долларов. Bitcoin полагается на SHA-256 - если бы SHA-256 сломали, под угрозой оказались бы 1.5 триллиона долларов рынка криптовалют.

Предварительные знания

• Что такое блокчейн

SHA-256: цифровой отпечаток

SHA-256 - 32 байта выхода. Bitcoin: один хеш вычисляется за ~20 мкс. Весь мир делает 600 экзахешей/с в поисках одного блока. Каждую секунду. Это больше, чем все компьютеры 2000 года вместе взятые. **Хеш-функция** превращает данные **любого размера** в строку **фиксированной длины**. Слово «hello» или полный текст «Войны и мира» - на выходе всегда **64 шестнадцатеричных символа** (256 бит).

**Почему 256 бит?** $2^{256}$ возможных хешей. Это $\approx 10^{77}$ - превышает оценочное количество атомов в наблюдаемой Вселенной ($\approx 10^{80}$). Случайное совпадение двух хешей - практически нулевая вероятность.

SHA-256 используется повсеместно: **Bitcoin** вычисляет хеш каждого блока (дважды - SHA-256d), **Git** идентифицирует коммиты (сейчас переходит на SHA-256 с SHA-1), **HTTPS** проверяет целостность сертификатов. Одна функция - три разных системы, один математический фундамент.

Устойчивость к коллизиям

**Коллизия** - два разных входа с одинаковым хешем. Математически коллизии неизбежны (бесконечное множество входов, конечное множество хешей - принцип Дирихле). Но хорошая хеш-функция делает их **практически невозможными** для нахождения. **Collision resistance** означает: нельзя за разумное время найти m1 != m2 такие, что H(m1) = H(m2).

**Не все хеш-функции безопасны:** - **MD5** - сломана в 2004, коллизии за секунды на обычном CPU - **SHA-1** - Google SHAttered 2017: первая коллизия, 6500 лет CPU + 110 лет GPU, стоимость ~110 000 долларов - **SHA-256** - не сломана на сегодняшний день - **SHA-3 (Keccak)** - победитель конкурса NIST 2012, резервный стандарт

Зачем коллизионная стойкость в блокчейне? Злоумышленник мог бы создать вредоносную транзакцию с тем же хешем, что у легитимной. Замена была бы незаметна - верификация прошла бы успешно. Collision resistance закрывает этот вектор атаки.

Необратимость (Preimage Resistance)

**Preimage resistance** - зная хеш h, невозможно найти m такое, что H(m) = h. **Хеш-функция - односторонняя улица**: вычислить хеш данных - мгновенно. Восстановить данные по хешу - вычислительно невозможно. Количество операций: $2^{256}$ для SHA-256. Даже все компьютеры мира за все время существования Вселенной не успеют.

Перебор работает для коротких паролей. «password123» - в радужных таблицах. Именно поэтому хранение паролей требует не просто SHA-256, а **bcrypt / Argon2** - функций, спроектированных медленными намеренно. SHA-256 вычисляется за 20 мкс, bcrypt - за 100 мс. Разрыв в 5000 раз делает GPU-атаку нецелесообразной.

**Хранение паролей - правильно и неправильно:** Неправильно: хранить SHA-256(password) Почему: GPU вычисляет 10^10 SHA-256/с. Перебор 8-символьного пароля - минуты. Правильно: хранить bcrypt(password, cost=12) или Argon2id(password) Почему: bcrypt намеренно медленный - 100 мс/хеш. Перебор 8-символьного пароля - годы.

Эффект лавины

**Эффект лавины** - изменение одного бита входа **полностью меняет** выходной хеш. Хеши «hello» и «hellp» выглядят абсолютно несвязанными. Нет никакой корреляции - нет способа «приближаться» к нужному хешу постепенно.

Одна изменённая буква - ~50% бит выхода изменились. Это не случайность - это криптографическое требование. Идеальная хеш-функция: каждый бит выхода зависит от каждого бита входа. SHA-256 близка к этому идеалу.

**Критерий идеальной хеш-функции:** при изменении 1 бита входа каждый бит выхода меняется с вероятностью 50%. Это называется строгим лавинным критерием (Strict Avalanche Criterion, SAC). SHA-256 удовлетворяет SAC статистически.

Ключевые идеи

• **SHA-256** - любой вход -> 256 бит (64 hex-символа). 600 экзахешей/с в Bitcoin mining. Ralph Merkle 1979 + NSA 1993 = фундамент всего блокчейна
• **Collision resistance** - найти два входа с одинаковым хешем: 2^128 операций, 10^13 лет. Google SHAttered сломал SHA-1 за 110 000 долларов, SHA-256 - не сломан
• **Preimage resistance** - по хешу невозможно восстановить данные. Для паролей нужен bcrypt/Argon2id, не SHA-256 напрямую: GPU делает 10^10 SHA-256/с
• **Эффект лавины** - 1 изменённый бит входа меняет ~50% выхода. Без эффекта лавины Proof of Work потерял бы смысл: майнеры могли бы 'приближаться' к нужному хешу
• **Хеширование != шифрование:** мясорубка vs замок с ключом. В блокчейне оба используются с разными целями

Связанные темы

Хеш-функции - фундамент множества технологий в блокчейне и за его пределами:

• Merkle Trees — Используют хеши для построения дерева проверки транзакций - следующий урок
• Proof of Work — Майнеры ищут nonce, чтобы хеш блока начинался с N нулей - применение эффекта лавины
• Цифровые подписи — ECDSA: хеш сообщения подписывается приватным ключом

Вопросы для размышления

• Если SHA-256 когда-нибудь будет взломана, что произойдёт с Bitcoin? Какие части системы пострадают первыми?
• Почему для хранения паролей одного SHA-256 недостаточно (подсказка: rainbow tables и скорость GPU)?
• Квантовые компьютеры угрожают SHA-256? Алгоритм Гровера сокращает эффективную безопасность вдвое - с 256 бит до 128. Достаточно ли 128 бит?

Связанные уроки

• bc-03-merkle — Merkle trees строятся поверх хеш-функций - следующий урок
• bc-14-pow — Proof of Work - поиск nonce через миллиарды вызовов SHA-256
• bc-06-digital-signatures — Цифровые подписи: хеш сообщения подписывается приватным ключом
• crypto-19-hash-functions — Глубокий анализ конструкций хеш-функций в криптографии
• crypto-22-password-hashing — bcrypt/Argon2 - хеширование паролей с защитой от GPU-атак
• alg-25-rabin-karp — Rolling hash в алгоритмах строк - та же идея детерминированного отпечатка
• crypto-20-sha-family