Důkazy s nulovou znalostí

Dá se dokázat, že něco víš, aniž bys prozradil co? Zní to jako protimluv a je to nejdůležitější kryptografický nápad posledních dvaceti let. Stojí na něm dnešní škálování, soukromí i identita.

A dá se to ukázat na dvaceti řádcích s křivkou, kterou už znáš.

▶ Spustitelné. Ulož jako zk.py vedle podpisy.py.

Co to má umět

Důkaz s nulovou znalostí musí splňovat tři věci naráz:

Ta třetí je ta zvláštní. Jak dokážeš, že se někdo něco nedozvěděl?

Celý důkaz

"""Skutečný důkaz s nulovou znalostí, na dvacet řádků.
Dokážu ti, že znám privátní klíč, aniž bych ti o něm cokoli řekl."""
import secrets, hashlib
from podpisy import N, G, scitani, nasobeni

def dukaz(d):
    """Dokazovatel: znám d takové, že P = d*G. Neprozradím d."""
    k = secrets.randbelow(N - 1) + 1
    R = nasobeni(k, G)                       # 1. závazek: pošlu R, k si nechám
    return k, R

def vyzva():
    return secrets.randbelow(N - 1) + 1      # 2. ověřovatel hodí náhodnou výzvu

def odpoved(k, e, d):
    return (k + e * d) % N                   # 3. odpověď, ze které d nejde vytáhnout

def over(P, R, e, s):
    return nasobeni(s, G) == scitani(R, nasobeni(e, P))

if __name__ == '__main__':
    d = secrets.randbelow(N - 1) + 1         # tajemství
    P = nasobeni(d, G)                       # veřejné

    print('=== poctivý dokazovatel ===')
    k, R = dukaz(d)
    e = vyzva()
    s = odpoved(k, e, d)
    print(f'  ověřeno: {over(P, R, e, s)}')
    print(f'  ověřovatel viděl R, e, s. Tajemství d nikdy neopustilo dokazovatele.')

    print('\n=== podvodník, který d nezná ===')
    k2, R2 = dukaz(secrets.randbelow(N - 1) + 1)   # hádá
    e2 = vyzva()
    s2 = odpoved(k2, e2, secrets.randbelow(N - 1) + 1)
    print(f'  ověřeno: {over(P, R2, e2, s2)}   <- neprojde')

    print('\n=== proč to NIC neprozradí: podvodník to umí předstírat,')
    print('    pokud zná výzvu předem ===')
    e3 = vyzva()                              # podvodník výzvu zná dopředu
    s3 = secrets.randbelow(N - 1) + 1         # zvolí odpověď náhodně
    # a dopocita R tak, aby rovnice vysla: R = s*G - e*P
    minus_e_P = nasobeni(N - e3 % N, P)
    R3 = scitani(nasobeni(s3, G), minus_e_P)
    print(f'  ověřeno: {over(P, R3, e3, s3)}   <- projde, a přitom d nezná!')
    print('\n  Tím je dokázáno, že trojice (R, e, s) neobsahuje o d žádnou informaci:')
    print('  jde vyrobit i bez něj. Bezpečnost stojí čistě na tom, že poctivý')
    print('  dokazovatel se zaváže k R DŘÍV, než uslyší výzvu.')

    print('\n=== a proč to nejde podvést doopravdy ===')
    print('  Kdyby podvodník uměl odpovědět na DVĚ různé výzvy se stejným R,')
    print('  vypadlo by z toho d: ze s1 = k + e1*d a s2 = k + e2*d plyne')
    print('  d = (s1 - s2) / (e1 - e2). Umět odpovědět vždy tedy znamená d znát.')

Jak to funguje: závaž se, dostaň výzvu, odpověz

Pořadí je celé kouzlo. Dokazovatel se musí zavázat k R dřív, než uslyší výzvu. Kdyby výzvu znal předem, dokázal by odpověď zfalšovat.

Důkaz nulové znalosti je ten třetí blok výstupu

=== proč to NIC neprozradí: podvodník to umí předstírat,
    pokud zná výzvu předem ===
  ověřeno: True   <- projde, a přitom d nezná!

Tohle je nejchytřejší část a stojí za to ji pochopit. Ukázali jsme, že celý zápis komunikace se dá vyrobit bez znalosti tajemství, pokud si člověk zvolí pořadí jinak.

Z toho plyne, že v tom zápisu žádná informace o tajemství není. Kdyby tam byla, nešlo by ho vyrobit bez ní. Tomuhle argumentu se říká simulátor a je to standardní způsob, jak se nulová znalost dokazuje.

A proč to zároveň nejde podvést

Kdyby podvodník uměl odpovědět na DVĚ různé výzvy se stejným R,
vypadlo by z toho d: ze s1 = k + e1*d a s2 = k + e2*d plyne
d = (s1 - s2) / (e1 - e2).

Tomu se říká extraktor: kdo umí odpovědět vždycky, ten tajemství zná, protože by se z něj dalo vytáhnout. Dohromady se simulátorem je to celý bezpečnostní argument.

Mimochodem, všimni si té rovnice. Je to přesně ten samý výpočet, kterým se v kapitole o klíčích prozradí klíč při opakovaném použití nonce. Stejná matematika, jednou jako útok, podruhé jako důkaz bezpečnosti.

Od tohohle k tomu, o čem se dnes mluví

Náš důkaz dokazuje jedno konkrétní tvrzení: „znám diskrétní logaritmus". Moderní systémy umí totéž pro libovolný výpočet: „znám vstupy, pro které tenhle program vydá tenhle výsledek". Tomu se říká SNARK nebo STARK podle konstrukce.

Zásadní je jedna vlastnost:

Ta asymetrie mění, co jde postavit:

Škálování. Zk-rollup provede tisíce transakcí mimo hlavní řetěz a přiloží jeden důkaz, že je provedl správně. Hlavní řetěz nemusí ty transakce vidět, stačí ověřit důkaz. Proto zk-rollupy nepotřebují čekací lhůtu, o které mluví kapitola o škálování: u nich se správnost ověří matematicky, ne tím, že se čeká, jestli někdo podvod ohlásí.

Soukromí. Dá se dokázat „tahle platba je platná, součty sedí a nikde nevznikly peníze z ničeho", aniž by se odhalilo kdo, komu a kolik.

Identita. Dá se dokázat „je mi přes osmnáct" bez ukázání data narození, nebo „jsem v seznamu oprávněných" bez prozrazení které položky.

Co to není

Aby to nevypadalo jako zázrak, tři poctivé výhrady:

• Není to zadarmo. Výroba důkazu je řádově dražší než výpočet samotný.
• Nedůvěřuješ nikomu, ale věříš matematice a implementaci. Chyba v obvodu nebo v knihovně je stejně fatální jako chyba v kontraktu, a je hůř vidět.
• Některé konstrukce potřebují důvěryhodné nastavení. Při jejich vzniku se generují parametry a kdo by si nechal pomocná data, uměl by vyrábět falešné důkazy. Řeší se to ceremoniemi s mnoha účastníky, kde stačí, aby byl jeden poctivý, ale je to předpoklad navíc.

Cvičení

1. Proč se musí dokazovatel zavázat k R dřív, než uslyší výzvu?
2. Co by se stalo, kdyby dokazovatel použil stejné R pro dvě různé výzvy?
3. Proč zk-rollup nepotřebuje čekací lhůtu, kterou má rollup s důkazem podvodu?

Shrnutí

• Důkaz s nulovou znalostí splňuje úplnost, správnost a to, že ověřovatel se nedozví nic navíc.
• Schéma je závazek, výzva, odpověď, a záleží na pořadí.
• Nulová znalost se dokazuje simulátorem: zápis jde vyrobit i bez tajemství, tedy nic neobsahuje.
• Správnost se dokazuje extraktorem: kdo umí odpovědět vždy, ten tajemství zná.
• Moderní SNARK a STARK to umí pro libovolný výpočet a ověření je levné bez ohledu na složitost.
• Odtud plynou zk-rollupy bez čekací lhůty, soukromé platby i dokazování vlastností bez údajů.