ZK Story time: Co jsem slyšel od Shafiho Goldwassera, spoluvynálezce ZK (a držitele Turingovy ceny). Nezačalo to jako "důkazy". Článek ZK byl 4-5krát odmítnut na recenzovaných konferencích. Matematici silně protestovali proti tomu, aby se tyto věci nazývaly "důkazy". Podrobnosti: Nesnažila se definovat nový model důkazů. Není zač. Ona a její spoluautoři chtěli vyřešit problém hraní pokeru pomocí telefonu. (Stalo se to tolika z nás) V té době už bylo známo, jak "zamíchat" balíček karet mezi dvěma lidmi, kteří si telefonují (bez předpokladů důvěry a bez důvěryhodné třetí strany). Problém byl v tom, že dva hráči bez předpokladů důvěry museli dodržovat *pravidla* hry, aniž by byly odhaleny informace. To je to, co si dala za cíl vyřešit. A skončili s protokolem, aby si oba hráči navzájem "dokázali", že si další náhodnou kartu vytáhli správně. Neuvědomili si okamžitě, že je to forma důkazu. To jim navrhl Michael Sipser, když mu to popisovali. Ale je to velmi podivný pojem "důkaz". Musí se spoléhat na náhodnost. Má malou pravděpodobnost chyby. Pokud jste někdy viděli "řádný" matematický důkaz (řekněme pro nekonečno prvočísel), pak se přirozeně vzbouříte proti takovému chaotickému a k chybám náchylnému druhu "důkazu". Což je důvod, proč po velmi dlouhou dobu, když Shafi a Silvio a mnozí další představili světu tyto magické ZK důkazy, lidé proti tomu bojovali. Je to slavná tradice v teoretické informatice, kterou sdílíte se svými kolegy poté, co byla vaše úžasná přihláška na konference STOC nebo FOCS (S-tier) znovu odmítnuta. Řeknete "věděli jste, že článek ZK byl 5krát odmítnut a 2 ze spoluautorů nakonec získali Turingovu cenu?" Skončím tím, že článek STARK byl zamítnut 4krát, FRI byl odmítnut dvakrát. Jen říkám ;-)