Хеш-функции: свойства и применение

Зачем это нужно в блокчейне

Каждый заголовок блока Bitcoin содержит SHA-256 хеш. Майнинг — это поиск такого nonce, что хеш блока меньше заданной цели. Ethereum использует Keccak-256 для вычисления адресов из публичных ключей. Без хеш-функций не было бы ни Bitcoin, ни Ethereum, ни любого другого блокчейна.

Но что такое хеш-функция и почему она так надежна?

Интуитивное объяснение

Хеш-функция — это цифровой отпечаток пальца. Как у каждого человека уникальный отпечаток, так и у каждого набора данных — уникальный хеш.

Ключевые свойства:

• Детерминированность: один и тот же вход всегда дает один и тот же выход
• Фиксированный размер: SHA-256 всегда выдает 256 бит, независимо от размера входа
• Однонаправленность: по хешу невозможно восстановить исходные данные

Три свойства криптографических хеш-функций

Не каждая хеш-функция является криптографической. Криптографическая хеш-функция должна обладать тремя фундаментальными свойствами:

Стойкость к прообразу (Pre-image Resistance)

Имея хеш h, практически невозможно найти сообщение m такое, что H(m) = h.

Аналогия: Как пепел — видишь результат сгорания, но невозможно восстановить оригинальный документ.

В блокчейне: Это свойство делает майнинг сложным. Единственный способ найти nonce с нужным хешем — перебирать варианты.

Стойкость к второму прообразу (Second Pre-image Resistance)

Имея сообщение m1, практически невозможно найти другое сообщение m2 != m1 такое, что H(m1) = H(m2).

Аналогия: Как отпечаток пальца — найти другого человека с точно таким же отпечатком практически невозможно.

В блокчейне: Злоумышленник не может подменить транзакцию другой с тем же хешем.

Стойкость к коллизиям (Collision Resistance)

Практически невозможно найти любые два различных сообщения m1 != m2 с одинаковым хешем.

Аналогия: Парадокс дней рождения — найти любых двух людей с одинаковыми отпечатками проще, чем найти конкретную пару. Но для SHA-256 даже это требует 2^128 операций.

Лавинный эффект

Малейшее изменение входных данных приводит к кардинальному изменению хеша. Изменив один бит во входе, мы получим хеш, отличающийся примерно на 50% бит.

Попробуйте сами:

Алгоритмический уровень

Использование hashlib в Python

import hashlib

# Базовое хеширование
h = hashlib.sha256(b"Hello").hexdigest()
print(h)  # 185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969

# Лавинный эффект
h1 = hashlib.sha256(b"Hello").hexdigest()
h2 = hashlib.sha256(b"hello").hexdigest()  # 1 бит разницы во входе

# Подсчет отличающихся бит
diff_bits = bin(int(h1, 16) ^ int(h2, 16)).count('1')
print(f"Отличающихся бит: {diff_bits}/256")  # ~128 бит различий

Сравнение хеш-функций

import hashlib

message = b"Hello, blockchain!"

# SHA-256 (Bitcoin)
sha256 = hashlib.sha256(message).hexdigest()
print(f"SHA-256:   {sha256}")

# SHA-3-256 (NIST стандарт)
sha3 = hashlib.sha3_256(message).hexdigest()
print(f"SHA-3-256: {sha3}")

# BLAKE2b (Zcash, Polkadot)
blake2 = hashlib.blake2b(message, digest_size=32).hexdigest()
print(f"BLAKE2b:   {blake2}")

Математический уровень

Парадокс дней рождения

Для хеш-функции с выходом длиной n бит:

• Стойкость к прообразу: 2^n операций (для SHA-256: 2^256)
• Стойкость к коллизиям: 2^(n/2) операций (для SHA-256: 2^128)

Почему 2^(n/2)? Это парадокс дней рождения: в группе из 23 человек вероятность совпадения дней рождения у двух из них превышает 50%. Аналогично, после 2^128 хешей вероятность найти коллизию в SHA-256 становится значительной.

Формальное определение

Хеш-функция H: {0,1}* -> {0,1}^n является криптографически стойкой, если:

1. Для случайного y из {0,1}^n, нахождение x такого что H(x) = y требует O(2^n) операций
2. Для данного x1, нахождение x2 != x1 такого что H(x1) = H(x2) требует O(2^n) операций
3. Нахождение любой пары (x1, x2) с x1 != x2 и H(x1) = H(x2) требует O(2^(n/2)) операций

Применение хеш-функций

Практика

Закрепите знания в Jupyter notebook: 03-hashing.ipynb

В нем вы:

• Измерите лавинный эффект на 1000 случайных входах
• Реализуете SHA-256 с нуля на Python
• Проведете симуляцию парадокса дней рождения
• Сравните Keccak-256 и SHA-3-256

Итоги

• Хеш-функция — однонаправленное преобразование данных любого размера в фиксированный “отпечаток”
• Три ключевых свойства: стойкость к прообразу, к второму прообразу, к коллизиям
• Лавинный эффект: изменение 1 бита входа меняет ~50% бит выхода
• SHA-256 используется в Bitcoin, Keccak-256 — в Ethereum
• Парадокс дней рождения снижает стойкость к коллизиям до 2^(n/2)