Hashovací funkce

Hash je základní kámen všeho ostatního. Je to funkce, která z jakéhokoli vstupu udělá číslo pevné délky, a má dvě vlastnosti, na kterých stojí celý blockchain: stejný vstup dá vždy stejný výstup a z výstupu se nedá dopočítat vstup.

Nebudeme to brát na slovo. Za pár řádků si oba jevy změříš.

▶ Spustitelné. Ulož jako hash.py a pusť python3 hash.py. Nepotřebuješ nic nainstalovat, hashlib je součástí Pythonu. Poslední část běží pár sekund.

Celý program

"""Proč se hash nedá vzít zpátky a co je lavinový efekt. Jen hashlib."""
import hashlib, time

def h(s):
    return hashlib.sha256(s.encode()).hexdigest()

def bity(s):
    return bin(int.from_bytes(hashlib.sha256(s.encode()).digest(), 'big'))[2:].zfill(256)

print('=== 1. stejný vstup vždy stejný výstup, jiný vstup úplně jiný ===')
for s in ['ahoj', 'ahoj.', 'Ahoj']:
    print(f'  {s:8s} -> {h(s)}')

print('\n=== 2. lavinový efekt: jeden znak, polovina bitů ===')
a, b = bity('blok cislo 1'), bity('blok cislo 2')
zmeneno = sum(x != y for x, y in zip(a, b))
print(f'  "blok cislo 1" vs "blok cislo 2"')
print(f'  změněných bitů: {zmeneno} z 256 = {zmeneno / 256:.1%}')

celkem = 0
POKUSU = 2000
for i in range(POKUSU):
    x, y = bity(f'zprava {i}'), bity(f'zprava {i}X')
    celkem += sum(p != q for p, q in zip(x, y))
print(f'  průměr přes {POKUSU} párů: {celkem / POKUSU:.1f} bitů = {celkem / POKUSU / 256:.1%}')
print('  ideál je přesně 50 %, protože výstup má vypadat jako náhoda')

print('\n=== 3. jak drahé je najít vstup s daným výstupem ===')
for nul in range(1, 7):
    cil = '0' * nul
    t0, i = time.time(), 0
    while True:
        if h(f'ahoj {i}').startswith(cil): break
        i += 1
    print(f'  hash začínající {nul} nulami: {i:>9,} pokusů, {time.time()-t0:.2f} s   (ahoj {i})')

print('\n  Každá další nula je šestnáctkrát dražší. Tohle je celé proof of work.')
print(f'  Bitcoin dnes hledá hash s ~19 nulami. To je {16**13:,.0f}x víc práce než 6 nul.')

Co z toho vyšlo

=== 1. stejný vstup vždy stejný výstup, jiný vstup úplně jiný ===
  ahoj     -> 3f3b08eca62c21d76256e6e1d0b8bf99f4efbe376f64335b72f4163a8fc50dba
  ahoj.    -> d16b42563ade4f7005d06bd65e1505a2ec3353f6b24acf5285b5c378101b2587
  Ahoj     -> f23e6807b3fb0be0ea999ea8cb88a3e94dc359c84230461f9761efac57dcb081

Přidání tečky nezměnilo výstup „trochu". Změnilo ho celý. To je první vlastnost, kterou potřebujeme, a jmenuje se lavinový efekt.

Lavinový efekt, změřený

=== 2. lavinový efekt: jeden znak, polovina bitů ===
  "blok cislo 1" vs "blok cislo 2"
  změněných bitů: 117 z 256 = 45.7%
  průměr přes 2000 párů: 127.9 bitů = 50.0%

Změna jednoho znaku ve vstupu překlopí polovinu bitů ve výstupu. Ne desetinu, ne devadesát procent, přesně polovinu. A to je právě to, co chceš: kdyby jich bylo výrazně méně, dal by se z podobných výstupů odhadovat podobný vstup. Kdyby jich bylo víc, byla by ve výsledku pravidelnost, kterou by šlo využít.

Padesát procent znamená, že se výstup chová jako náhoda, a to je nejvyšší možná ambice hashovací funkce.

Všimni si rozdílu mezi jedním párem (45,7 %) a průměrem z dvou tisíc (50,0 %). Jednotlivý pokus kolísá, průměr se usadí přesně na polovině. Až budeš cokoli měřit, chtěj průměr.

Proč se hash nedá vzít zpátky

Neexistuje na to matematický trik. Jediná cesta je zkoušet vstupy, a tady je vidět, co to stojí:

=== 3. jak drahé je najít vstup s daným výstupem ===
  hash začínající 1 nulami:         0 pokusů, 0.00 s
  hash začínající 2 nulami:       244 pokusů, 0.00 s
  hash začínající 3 nulami:     4,974 pokusů, 0.00 s
  hash začínající 4 nulami:    48,788 pokusů, 0.02 s
  hash začínající 5 nulami:   221,965 pokusů, 0.10 s
  hash začínající 6 nulami: 7,642,028 pokusů, 3.47 s

Každá další nula v šestnáctkové soustavě je šestnáctkrát dražší. Očekávaný počet pokusů je 16^n, tedy 16, 256, 4 096, 65 536, 1 048 576, 16 777 216. Naměřená čísla kolem toho poskakují, protože každý řádek je jediný pokus a je to hra na náhodu, ale řádově to sedí.

A tohle je celý proof of work. Když se dozvíš, že Bitcoin „řeší složité matematické úlohy", je to zavádějící. Neřeší nic složitého. Hází kostkou tak dlouho, dokud nepadne dost nul, a jediné, co na tom je náročné, je počet hodů.

Pro představu: bitcoinová síť hledá hash s asi devatenácti nulami. To je proti našim šesti nulám zhruba 4,5 × 10¹⁵krát víc práce. Na jeden blok. Každých deset minut.

Tři vlastnosti, které od hashe chceme

Ta třetí je důvod, proč se dnes nepoužívá MD5 ani SHA-1: u obou se kolize najít podařilo, takže se s nimi dá podvádět. SHA-256 zatím drží.

Cvičení

1. Uprav program tak, aby místo nul na začátku hledal hash končící třemi nulami. Bude to snadnější, těžší, nebo stejné?
2. Kolik pokusů bys očekával u hashe s osmi nulami a jak dlouho by to na tvém počítači trvalo? Odhadni z naměřených dat, nespouštěj to.
3. Proč lavinový efekt musí být přesně 50 procent a ne třeba 90?

Shrnutí

• Hash je jednosměrná funkce s pevnou délkou výstupu, deterministická a bez zjevného vzoru.
• Lavinový efekt: změna jednoho znaku vstupu překlopí polovinu bitů výstupu. Změřeno na 50,0 %.
• Hash se nedá obrátit; jediná cesta je hádat vstupy, a cena roste exponenciálně s nároky.
• Proof of work není řešení složité úlohy. Je to hádání, dokud nepadne dost nul.
• Kolizní odolnost je důvod, proč se opustily MD5 a SHA-1.