Merkle tree

Blok obsahuje tisíce transakcí. Chceš ověřit, že ta tvoje je mezi nimi, ale nechceš stahovat celý blok. Merkle tree to umožní: k důkazu ti stačí logaritmus počtu transakcí, tedy u miliardy položek třicet hashů.

Je to jedna z nejelegantnějších struktur v informatice a napíšeš si ji za dvacet řádků.

▶ Spustitelné. Ulož jako merkle.py a pusť python3 merkle.py.

Jak to funguje

Zhashuj každou transakci. Pak hashe spáruj a zhashuj páry. A tak dál, dokud nezbyde jeden hash. Ten se jmenuje Merkle koren a je otiskem celé sady.

Kouzlo je v tom, co potřebuješ k důkazu. Chceš li ukázat, že tx3 je ve stromu, nemusíš posílat všechny transakce. Stačí hash jejího bratra a hashe bratrů po cestě nahoru. Příjemce z nich koren dopočítá sám a porovná s tím, který má z hlavičky bloku.

Celý program

"""Merkle tree: dokaž, že transakce je v bloku, aniž bys stahoval blok."""
import hashlib

def h(*x):
    return hashlib.sha256(''.join(x).encode()).hexdigest()

def koren(listy):
    """Hashuj po párech, dokud nezbyde jeden hash. Ten je 'otisk' celé sady."""
    uroven = [h(l) for l in listy]
    while len(uroven) > 1:
        if len(uroven) % 2: uroven.append(uroven[-1])        # nepárový se zdvojí
        uroven = [h(uroven[i], uroven[i + 1]) for i in range(0, len(uroven), 2)]
    return uroven[0]

def dukaz(listy, index):
    """Vrať jen ty hashe, které soused potřebuje k dopočítání korenu."""
    uroven, cesta = [h(l) for l in listy], []
    while len(uroven) > 1:
        if len(uroven) % 2: uroven.append(uroven[-1])
        soused = index ^ 1                                    # bratr v páru
        cesta.append((uroven[soused], 'vpravo' if soused > index else 'vlevo'))
        uroven = [h(uroven[i], uroven[i + 1]) for i in range(0, len(uroven), 2)]
        index //= 2
    return cesta

def over(list_, cesta, ocekavany_koren):
    aktualni = h(list_)
    for soused, strana in cesta:
        aktualni = h(aktualni, soused) if strana == 'vpravo' else h(soused, aktualni)
    return aktualni == ocekavany_koren

if __name__ == '__main__':
    txs = [f'tx{i}: Alice -> Bob, {i} coinu' for i in range(8)]
    k = koren(txs)
    print(f'8 transakcí, Merkle koren: {k[:32]}...')

    d = dukaz(txs, 3)
    print(f'\ndůkaz pro tx3 má {len(d)} hashů (log2 z 8 = 3):')
    for hh, strana in d: print(f'   {strana:7s} {hh[:24]}...')
    print(f'\nověření tx3:            {over(txs[3], d, k)}')
    print(f'ověření podvržené tx3:  {over("tx3: Alice -> Eva, 3 coinu", d, k)}')

    print('\n=== proč to má smysl: velikost důkazu roste logaritmicky ===')
    import math
    print(f"  {'transakcí':>12} | {'hashů v důkazu':>15} | {'místo místo celého bloku':>26}")
    for n in (8, 1024, 1_000_000, 1_000_000_000):
        hashu = math.ceil(math.log2(n))
        print(f'  {n:>12,} | {hashu:>15} | {hashu*32:>22,} B')
    print('\n  Miliarda transakcí a důkaz je 30 hashů, tedy pod kilobajt.')
    print('  Proto může tvůj telefon ověřit platbu bez stahování blockchainu.')

Co z toho vyšlo

8 transakcí, Merkle koren: cea56bbe017215a18585dd8d5a0d4132...

důkaz pro tx3 má 3 hashů (log2 z 8 = 3):
   vlevo   4c2d9313e38ae75d8ffe984d...
   vlevo   a1493f1aa243eac2b3113439...
   vpravo  2adf74d3aab64d4b48669db5...

ověření tx3:            True
ověření podvržené tx3:  False

A tady je ten důvod, proč to celé existuje:

     transakcí |  hashů v důkazu |   místo místo celého bloku
             8 |               3 |                     96 B
         1,024 |              10 |                    320 B
     1,000,000 |              20 |                    640 B
 1,000,000,000 |              30 |                    960 B

Miliarda transakcí a důkaz je pod kilobajt. Proto může tvůj telefon ověřit platbu, aniž by stahoval blockchain. Stáhne si jen hlavičky bloků, což je pár desítek megabajtů za celou historii, a k jednotlivým platbám si vyžádá Merkle důkaz.

Kde všude na to narazíš

Merkle tree není jen bitcoinová specialita. Je to obecný nástroj na otisk množiny dat, u které chceš dokazovat členství:

Jedna nepříjemnost, kterou má Bitcoin dodnes

V kódu je řádek, který zdvojí poslední hash, když je jich na úrovni nepárový počet:

if len(uroven) % 2: uroven.append(uroven[-1])        # nepárový se zdvojí

Takhle to dělá i Bitcoin, a je to slabina. Existují dvě různé sady transakcí, které dají stejný koren, protože zdvojení nejde od skutečné duplikace rozeznat. Říká se tomu CVE-2012-2459 a v Bitcoinu se to obchází kontrolou navíc, ne opravou struktury, protože změna by rozdělila síť.

Novější systémy proto místo zdvojení používají jiné pravidlo, například vynesení nepárového hashu o úroveň výš beze změny.

Cvičení

1. Blok má 4 096 transakcí. Kolik hashů má důkaz a kolik bajtů to je?
2. Změň v důkazu jeden hash a ověř znovu. Proč selže, i když ostatní hashe jsou správné?
3. Proč nejde místo Merkle tree použít prostě hash všech transakcí za sebou?

Shrnutí

• Merkle koren je otisk celé sady transakcí, vzniklý párovým hashováním až k jednomu hashi.
• Důkaz členství potřebuje jen hashe bratrů po cestě, tedy logaritmický počet.
• U miliardy transakcí je důkaz třicet hashů, tedy necelý kilobajt.
• Proto může lehký klient ověřovat platby bez stahování blockchainu.
• Zdvojování nepárového hashe je v Bitcoinu známá slabina, CVE-2012-2459.