Schnorr a Taproot

ECDSA z minulé kapitoly funguje, ale je zbytečně složité. Existuje starší, jednodušší a lepší schéma, které se do Bitcoinu dostalo až v roce 2021, protože bylo do roku 2008 patentované.

Rozdíl je v jednom znaménku dělení, a plyne z něj vlastnost, kterou ECDSA nemá: podpisy se dají sčítat.

▶ Spustitelné. Ulož jako schnorr.py vedle podpisy.py z minulé kapitoly.

Porovnej ty dvě rovnice

ECDSA:    s = k⁻¹ · (z + r·d)        ← dělení, tedy nelineární
Schnorr:  s = k + e·d                ← jen sčítání a násobení

To je celý rozdíl. A protože je Schnorrova rovnice lineární, platí něco, co u ECDSA neplatí: součet dvou platných podpisů je platný podpis pro součet klíčů.

Ověření vypadá takhle:

platí, když:  s · G  ==  R + e · P

Sečti dvě takové rovnice a dostaneš zase rovnici stejného tvaru. U ECDSA se ti to rozpadne kvůli tomu k⁻¹.

Celý program

"""Schnorr podpis na secp256k1 a jeho hlavní přednost: podpisy jdou sčítat.
Vyžaduje podpisy.py z kapitoly o klíčích (křivka a násobení bodů)."""
import hashlib, secrets
from podpisy import N, G, scitani, nasobeni

def h(*kusy):
    """Hash vstupů na číslo menší než řád křivky."""
    m = hashlib.sha256(b''.join(k.to_bytes(32, 'big') for k in kusy)).digest()
    return int.from_bytes(m, 'big') % N

def klic():
    d = secrets.randbelow(N - 1) + 1
    return d, nasobeni(d, G)

# ---------- podpis ----------
def podepis(zprava_h, d, k=None):
    """s = k + e*d, kde e = hash(R, P, zpráva). Všimni si: žádné dělení."""
    k = k or secrets.randbelow(N - 1) + 1
    R = nasobeni(k, G)
    P = nasobeni(d, G)
    e = h(R[0], P[0], zprava_h)
    return R, (k + e * d) % N

def over(zprava_h, R, s, P):
    """Platí, když s*G == R + e*P. Je to LINEÁRNÍ rovnice, a v tom je celý vtip."""
    e = h(R[0], P[0], zprava_h)
    return nasobeni(s, G) == scitani(R, nasobeni(e, P))

if __name__ == '__main__':
    m = int.from_bytes(hashlib.sha256(b'Posilam 10 coinu Bobovi').digest(), 'big') % N
    d, P = klic()
    R, s = podepis(m, d)
    print('=== jeden podpis ===')
    print(f'  ověření originálu:      {over(m, R, s, P)}')
    m2 = int.from_bytes(hashlib.sha256(b'Posilam 100 coinu Bobovi').digest(), 'big') % N
    print(f'  ověření změněné zprávy: {over(m2, R, s, P)}')

    print('\n=== a teď to, co ECDSA neumí: sečti dva podpisy do jednoho ===')
    d1, P1 = klic()
    d2, P2 = klic()
    k1 = secrets.randbelow(N - 1) + 1
    k2 = secrets.randbelow(N - 1) + 1

    # spolecny nonce a spolecny verejny klic
    R_spol = scitani(nasobeni(k1, G), nasobeni(k2, G))
    P_spol = scitani(P1, P2)
    e = h(R_spol[0], P_spol[0], m)

    s1 = (k1 + e * d1) % N          # kazdy podepisuje sam za sebe
    s2 = (k2 + e * d2) % N
    s_spol = (s1 + s2) % N          # a podpisy se proste SECTOU

    print(f'  ověření součtu proti součtu klíčů: {over(m, R_spol, s_spol, P_spol)}')
    print('  V řetězci je vidět JEDEN podpis a JEDEN klíč.')
    print('  Nikdo nepozná, že podepisovali dva, ani kolik jich bylo.')
    print('\n  Tohle u ECDSA nejde, protože v něm je s = k⁻¹(z + r·d),')
    print('  tedy nelineární kvůli tomu dělení, a součet dvou podpisů nedá platný podpis.')

Výstup:

=== jeden podpis ===
  ověření originálu:      True
  ověření změněné zprávy: False

=== a teď to, co ECDSA neumí: sečti dva podpisy do jednoho ===
  ověření součtu proti součtu klíčů: True
  V řetězci je vidět JEDEN podpis a JEDEN klíč.

Proč na tom záleží v praxi

Skládání podpisů zní jako akademická drobnost. Není:

To třetí je z nich nejzajímavější. U ECDSA multisigu je v řetězu vidět „tohle jsou peníze, které chrání tři klíče ze čtyř", což je informace o tom, kdo a jak s nimi nakládá. Se Schnorrem to vypadá stejně jako běžná platba.

Taproot: dvě cesty k témuž výstupu

Na Schnorra navazuje myšlenka, která z toho udělá něco ještě užitečnějšího.

Za jedním klíčem může být schovaný celý strom podmínek. Pokud se všichni účastníci dohodnou, podepíší společně a nikdo se nikdy nedozví, že tam nějaké podmínky byly. Když se nedohodnou, odhalí se právě ta jedna větev, která se použila, a zbytek zůstane skrytý.

Odtud plyne pěkný princip: složitost platíš, jen když ji použiješ.

Poctivá poznámka k tomu skládání

Ukázka výše sčítá klíče naivně, tedy P = P1 + P2. Takhle se to v praxi dělat nesmí: existuje takzvaný útok podvrženým klíčem, kdy druhý účastník zvolí svůj klíč jako P2 = X - P1 a získá tím kontrolu nad společným klíčem sám.

Skutečné protokoly proto každý klíč před sečtením násobí koeficientem odvozeným ze všech klíčů dohromady, takže si útočník nemůže ten svůj zvolit až podle ostatních. Podstata skládání zůstává, jen se přidá jedna vrstva navíc.

Cvičení

1. Proč nejde sečíst dva ECDSA podpisy?
2. Co konkrétně na blockchainu uvidíš u Taproot výstupu, který se utratil dohodou všech?
3. Proč je útok podvrženým klíčem možný jen tehdy, když si útočník volí klíč jako poslední?

Shrnutí

• Schnorr má rovnici s = k + e·d, tedy bez dělení, a proto je lineární.
• Z linearity plyne, že se podpisy i klíče dají sčítat a v řetězu je vidět jen jeden pár.
• Multisig se tím stane levnějším a nerozeznatelným od běžné platby.
• Taproot schová strom podmínek za jeden klíč; při dohodě se nikdy neodhalí.
• Naivní sčítání klíčů je zranitelné podvrženým klíčem, skutečné protokoly přidávají koeficienty.