Czas na historię ZK: Co usłyszałem od Shafi Goldwasser, współwynalazczyni ZK (i laureatki nagrody Turinga). Nie zaczęło się od "dowodów". Artykuł o ZK został odrzucony 4-5 razy przez konferencje recenzowane. Matematycy stanowczo sprzeciwiali się nazywaniu tych rzeczy "dowodami". Szczegóły: Nie próbowała zdefiniować nowego modelu dla dowodów. Wcale nie. Ona i jej współautorzy chcieli rozwiązać problem grania w pokera przez telefon. (Przydarzyło się to wielu z nas) Do tego czasu już wiedziano, jak *tasować* talię kart między dwiema osobami rozmawiającymi przez telefon (bez założeń dotyczących zaufania i bez zaufanej trzeciej strony). Problem polegał na tym, że dwaj gracze bez założeń dotyczących zaufania muszą przestrzegać *zasad* gry, bez ujawniania informacji. To było to, co postanowiła rozwiązać. I skończyli z protokołem, w którym dwaj gracze "udowadniają" sobie nawzajem, że poprawnie wylosowali następną losową kartę. Nie zdali sobie od razu sprawy, że to forma dowodu. Zasugerował im to Michael Sipser, gdy im to opisali. Ale to bardzo dziwna koncepcja "dowodu". Musi opierać się na losowości. Ma małe prawdopodobieństwo błędu. Jeśli kiedykolwiek widziałeś "właściwy" dowód matematyczny (powiedzmy, dla nieskończoności liczb pierwszych), to naturalnie będziesz się buntować przeciwko tak chaotycznemu i podatnemu na błędy rodzajowi "dowodu". Dlatego przez bardzo długi czas, gdy Shafi, Silvio i wielu innych przedstawiali te magiczne dowody ZK światu, ludzie się temu sprzeciwiali. To znany kawałek wiedzy w teorii informatyki, który dzielisz z rówieśnikami po tym, jak twoje niesamowite zgłoszenie na STOC lub FOCS (konferencje S-tier) zostało ponownie odrzucone. Powiesz: "czy wiesz, że artykuł o ZK został odrzucony 5 razy, a 2 z współautorów zdobyli nagrodę Turinga?" Zakończę mówiąc, że artykuł o STARK został odrzucony 4 razy, a FRI dwa razy. Tylko mówię ;-)