Zrozumieć dowody z wiedzą zerową

Dowody z wiedzą zerową (ang. Zero-Knowledge Proofs, ZKP) są fascynującą technologią kryptograficzną, ponieważ umożliwiają jednej stronie udowodnienie drugiej stronie, że zna pewną informację, nie ujawniając tej informacji.

Najbardziej popularnym zastosowaniem ZKP jest powiązanie ich z technologią blockchain w kryptowalutach. Przykładowo, w kryptowalutach takich jak Zcash wykorzystuje się ZKP, a dokładniej protokół zk-SNARK, do zapewnienia anonimowości transakcji. Użytkownicy mogą udowodnić, że posiadają środki i mogą dokonać transakcji, nie ujawniając kwoty ani tożsamości. Zastosowania ZKP nie ograniczają się jednak do kryptowalut. Technologia ta jest szeroko badana w kontekście skalowalności blockchainów, tj., aby oszczędzić zasoby, transakcje są przeprowadzane poza głównym łańcuchem, a dopiero ich zbiorcze podsumowanie jest zapisywane na głównym łańcuchu wraz z dowodem ZKP, że te transakcje są poprawne. Coraz popularniejsze staje się również wykorzystanie ZKP w innych dziedzinach wymagających ochrony prywatności, np. w przypadku uwierzytelnienia urządzeń IoT (Internet of Things), gdzie dowody te zapewniają bezpieczną wymianę informacji między urządzeniami bez konieczności ujawniania wrażliwych danych.  Przykładowo w rozwiązaniach dla inteligentnego domu urządzenia mogą udowodnić, że należą do sieci, aby uzyskać dostęp do jej zasobów. Badania nad wdrożeniem ZKP w IoT to jak na razie głównie prototypy akademickie, ale z roku na rok liczba prac w tym obszarze rośnie. Ciekawe podsumowanie najnowszych rozwiązań uwierzytelniania opartego na ZKP w IoT opisali (Chen i inni 2023).

Dowody z wiedzą zerową zostały pierwszy raz opisane w 1985 r. (Micali, Rackoff i Goldwasser 1985).  Micali, Rackoff i Goldwasser pokazali, że możliwe jest w sposób interaktywny udowodnić, że pewna liczba nie jest resztą kwadratową modulo m, bez ujawniania żadnych dodatkowych informacji. Rozstrzygnięcie, czy dana liczba całkowita a jest resztą kwadratową czy nieresztą kwadratową modulo liczba naturalna m jest trudnym problemem obliczeniowym, gdy rozkład na czynniki pierwsze liczby m nie jest znany. Jeśli liczba a nie jest resztą kwadratową modulo m, oznacza to, że nie istnieje liczba całkowita x, dla której x² = a(mod m).

Dowód z wiedzą zerową dla pewnego stwierdzenia musi spełniać następujące właściwości:

• Kompletność (ang. completeness) – jeśli stwierdzenie jest prawdziwe, to weryfikujący postępujący zgodnie z protokołem zostanie przekonany o prawdziwości tego stwierdzenia.
• Rzetelność (ang. soundness) – jeśli stwierdzenie jest fałszywe, to prawdopodobieństwo, że weryfikujący da się oszukać jest znikome.
• Wiedza zerowa (ang. zero-knowledge) – w procesie przeprowadzenia dowodu nie zostanie ujawnione nic, poza tym, że to stwierdzenie jest prawdziwe.

Pierwsze dowody z wiedzą zerową miały charakter interaktywny. Aby lepiej zrozumieć ich ideę oraz związane z nimi wyzwania, warto przytoczyć przykład eksperymentu, w którym Peggy chce udowodnić Victorowi – osobie nierozróżniającej kolorów – że posiada dwie różne kulki: jedną czerwoną, drugą zieloną. Wybór imion nie jest przypadkowy. Peggy pełni rolę dowodzącego (prover), a Victor jest weryfikatorem (verifier). Kulki, poza kolorem, są identyczne pod każdym innym względem. Victor początkowo zakłada, że nie różnią się one od siebie. Celem eksperymentu jest przekonanie go, że kulki rzeczywiście są różne, przy jednoczesnym zachowaniu w tajemnicy informacji o tym, która jest czerwona, a która zielona. W tym celu przeprowadzana jest następująca procedura: Peggy przekazuje kulki Victorowi, który chowa je za plecami, a następnie losowo wybiera jedną z nich i pokazuje ją Peggy, pytając, czy dokonał zmiany w stosunku do poprzedniego wyboru. Victor może za plecami przełożyć kulki z ręki do ręki bez wiedzy Peggy. Ponieważ Peggy potrafi rozróżniać kolory, zawsze udziela poprawnej odpowiedzi. Aby Victor zyskał pewność, że kulki rzeczywiście są różne, eksperyment powtarza się wielokrotnie. Jeśli procedura zostanie przeprowadzona tylko raz, istnieje 50% szans, że Peggy przypadkowo udzieli poprawnej odpowiedzi. Jednak wraz ze wzrostem liczby rund prawdopodobieństwo, że jej odpowiedzi są jedynie wynikiem zgadywania, drastycznie maleje. Po n rundach wynosi ono 1/2ⁿ​, co oznacza, że już po kilkunastu powtórzeniach Victor może być pewien, że kulki nie są identyczne.
Klasyczne dowody z wiedzą zerową wymagały wielu rund interakcji pomiędzy dowodzącym, a weryfikującym. Już w latach osiemdziesiątych wykazano, że „wyzwanie” generowane przez weryfikatora można zastąpić pseudolosowym ciągiem dostępnym zarówno dla weryfikującego, jak i dowodzącego, przekształcając tym samym dowód w formę nieinteraktywną. W tym celu często stosuje się transformację Fiata-Shamira, która wykorzystuje funkcję haszującą do deterministycznego generowania „wyzwania”. W systemach masowych, takich jak blockchain, lub w zastosowaniach obejmujących wielu weryfikujących, konieczność ciągłej interakcji staje się nieefektywna i trudna do zrealizowania. Z tego względu współczesny rozwój koncentruje się głównie na technologiach nieinteraktywnych dowodów z wiedzą zerową (NIZKP). W tego rodzaju podejściu dowód jest generowany jednokrotnie przez dowodzącego i może być weryfikowany przez dowolną liczbę weryfikujących, bez potrzeby dodatkowej wymiany komunikatów. To rozwiązanie znacząco zwiększa efektywność i skalowalność w nowoczesnych systemach rozproszonych. Najbardziej popularne protokoły NIZKP do zk-SNARK, zk-STARK i Bulletproofs.

Protokół zk-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) można w jednym zdaniu opisać jako zwięzły (ang. succint) NIZKP. Oznacza to, że dowód ma bardzo mały rozmiar. Dzięki temu może być łatwo przesyłany i weryfikowany, co jest kluczowe w zastosowaniach takich jak blockchain. Jednak w przypadku klasycznego zk-SNARK przed przeprowadzeniem dowodu niezbędne jest wygenerowanie kluczy przez zaufaną trzecią stronę.  Klucze te są wykorzystywane zarówno do tworzenia, jak i weryfikacji dowodów, co rodzi pewien problem – potrzebę zaufania do procesu konfiguracji, a to natomiast wpływa na transparentność systemu. Idea zk-SNARK była rozwijana już wcześniej, ale zyskała dużą popularność dopiero po jej wdrożeniu w celu ochrony prywatności transakcji w kryptowalucie Zcash. Projekt Zcash został zaproponowany w 2014 roku w pracy (Ben-Sasson, Chiesa i inni 2014), a oficjalnie wprowadzony na rynek w 2016 roku.

Protokół Bulletproof został zaprezentowany w roku 2017 r. przez grupę naukowców z uniwersytetu Stanford w pracy (Bünz i inni 2017).  Umożliwia on efektywne dowodzenie, że dana liczba mieści się w określonym zakresie, bez ujawniania jej wartości. Protokoły Bulletproofs nie wymagają wcześniejszej generacji parametrów przez zaufaną trzecią stronę (ang. trusted setup). Dla przeprowadzenia dowodu dla dużego zbioru danych rozmiar dowodu jest mały. Rozmiar dowodu zwiększa się w sposób logarytmiczny w stosunku do rozmiaru danych, dla których przeprowadza się dowód. Dzięki temu protokoły Bulletproof są skalowalne. Znalazły zastosowanie np. w kryptowalucie Monero. Obecnie Bulletproofs opierają się na zobowiązaniach Pedersena, których bezpieczeństwo wynika z trudności problemu logarytmu dyskretnego. W związku z tym, w swojej obecnej formie, nie są one postkwantowo bezpieczne.

Protokół zk-STARK (Zero-Knowledge Scalable Transparent Argument of Knowledge) został opisany w pracy (Ben-Sasson, Bentov i inni 2018). Jego charakterystycznymi cechami jest to, że generowane dowody są jednocześnie transparentne, jak i mają świetną skalowalność. Dzięki temu bardzo dobrze nadają się do weryfikacja obliczeń na ogromnych zbiorach danych. Główne kryptograficzne prymitywy wykorzystywane w zk-STARK to:

• protokół FRI (Fast Reed-Solomon Interactive Oracle Proof), stosowany do obliczania wartości wielomianu i interpolacji, umożliwiający generowanie zwięzłych dowodów poprawności obliczeń na dużych zbiorach danych, zapewniając transparentność i skalowalność;
• zobowiązania wielomianowe, które są kryptograficznymi mechanizmami umożliwiającymi zobowiązanie się do wielomianu bez ujawniania jego współczynników, zapewniając integralność obliczeń oraz efektywną weryfikację dowodów;
• testowanie niskiego stopnia, stosowane w zk-STARK do weryfikacji, czy wielomian ma odpowiednio niski stopień, co gwarantuje, że poprawnie reprezentuje dowodzone obliczenia.

Praktycznym wdrożeniem zk-STARK jest jego wykorzystanie w StarkNet. StarkNet to zdecentralizowana warstwa 2 (L2) dla Ethereum, która wykorzystuje zk-STARK do skalowania sieci. Dzięki temu możliwe jest masowe przetwarzanie transakcji off-chain oraz ich późniejsza weryfikacja na Ethereum przy użyciu zk-STARK. Transakcja off-chain to transakcja, która odbywa się poza głównym blockchainem, co pozwala na szybsze i tańsze przetwarzanie operacji. Dopiero zbiorczy wynik wielu takich transakcji jest zapisywany na Ethereum, co znacząco redukuje koszty gasu, czyli opłaty za wykonanie transakcji, która zależy od skomplikowania operacji i zatłoczenia sieci. To zwiększa skalowalność sieci.

Najważniejsze różnice między Bulletproof, zk-SNARK i zk-STARK pokazano w Tabela 1.

Akceleracja obliczeń

ZKP wymagają intensywnych obliczeń, zwłaszcza podczas generowania dowodu. Akceleracja obliczeń jest kluczowa, aby przyspieszyć procesy, zmniejszyć koszty oraz umożliwić ich implementację w systemach o ograniczonych zasobach. Dzięki temu ZKP mogą znaleźć zastosowanie w wielu obszarach, w których obecne ograniczenia sprzętowe uniemożliwiają ich efektywne wykorzystanie. Akceleracje realizuje się m.in. z wykorzystaniem GPU, układów FPGA i układów ASIC. Wiele operacji wykonywanych jest na krzywych eliptycznych. Jednym z najbardziej obciążających obliczeniowo problemów w kryptografii krzywych eliptycznych jest MSM (Multi-Scalar Multiplication). Operacja ta polega na mnożeniu wielu punktów na krzywej eliptycznej przez różne skalary, a następnie sumowaniu ich wyników. Problem sprowadza się do wyznaczenia punktu R:

R = a₁P₁ + a₂P₂ + … + a_nP_n, gdzie a_i to skalary (liczby całkowite), P_i to punkty na krzywej eliptycznej, a R jest punktem, który jest wynikiem operacji MSM.

MSM jest bardzo kosztowne obliczeniowo, ponieważ każda operacja mnożenia punktów na krzywej eliptycznej wymaga wielu modularnych operacji i inwersji. W zk-SNARK obliczenia są wykonywane na setkach tysięcy punktów, co sprawia, że MSM stanowi wąskie gardło wydajności całego procesu.

NTT (Number Theoretic Transform) jest przekształceniem wykorzystywanym do zredukowania złożoności obliczeniowej mnożenia wielomianów z 0(n²) do 0(n log n). NTT pozwala na przekształcenie wielomianu do innej reprezentacji, w której mnożenie jest znacznie bardziej efektywne. Następnie odwrotne przekształcenie, czyli iNTT (inverse NTT), umożliwia powrót do klasycznej reprezentacji współczynnikowej. Chociaż zastosowanie przekształceń znacząco przyspiesza obliczenia, same operacje NTT i iNTT również muszą być odpowiednio zoptymalizowane, aby zapewnić satysfakcjonującą wydajność.

Kierunki rozwoju

Wraz z rozwojem technologii kwantowych, coraz większe znaczenie zyskuje zagadnienie kryptografii postkwantowej, czyli algorytmów odpornych na ataki z użyciem komputerów kwantowych. W tym kontekście pojawia się również potrzeba opracowania dowodów z wiedzą zerową odpornych na ataki z wykorzystaniem komputera kwantowego. Komputery kwantowe mogą z łatwością rozwiązywać pewne problemy, które obecnie uznaje się za trudne obliczeniowo, np. faktoryzacja iloczynu dużych liczb pierwszych czy problem logarytmu dyskretnego. Bezpieczeństwo wielu algorytmów ZKP opiera się na problemie logarytmu dyskretnego, np. zk-SNARK, Bulletproofs. Algorytm Shora potrafi efektywnie rozwiązywać takie problemy. zk-STARK został opracowany tak, aby był postkwantowo bezpieczny. Nie opiera się problemach łamanych przez algorytm Shora i algorytm Grovera. Bezpieczeństwo zk-STARK opiera się na funkcjach haszujących. Obecnie trwają również badania nad nowymi postkwantowymi protokołami ZKP wykorzystującymi:

• kraty (lattice-based ZKP) – oparte na problemach kratowych (Gao i inni 2021)
• schematy kodowe (code-based) – bazujące na problemach z teorii kodów korekcyjnych, np. (Ouyang, Tang i Xu 2024)
• ZKP oparte na funkcjach haszujacych – odporne na komputery kwantowe dzięki odporności funkcji skrótu na ataki algorytmem Grovera, np. Orion ZKP (Xie, Zhang i Song 2022)

Innym kierunkiem rozwoju jest szukanie nowych konstrukcji ZKP, aby ułatwić akcelerację obliczeń. Nową konstrukcją jest Binius, czyli SNARK zoptymalizowany pod implementacje sprzętowe. Wykorzystuje on arytmetykę w ciałach binarnych, dzięki czemu przeprowadzenie operacji arytmetycznych w sprzęcie jest efektywne. Rozszerzenie ciała binarnego jest przeprowadzane przez konstrukcję wież ciał binarnych (ang. tower construction). Konstrukcja została opublikowana w 2023 roku w pracy (Diamond i Posen 2023). Implementacje są efektywne, ponieważ konstrukcja rozszerzonych ciał binarnych umożliwia działanie na bitach, które są podstawową jednostką informacji. Działania w binarnych ciałach rozszerzonych pozwalają na efektywną implementacje w układach cyfrowych, w przeciwieństwie do arytmetyki w ciałach skończonych nad liczbami pierwszymi, których rząd często ma długość 256 bitów. Dzięki użyciu małych ciał, system Binius osiąga nawet 50-krotnie lepszą efektywność niż porównywalne rozwiązania (np. plonky2) przy operacjach na 1-bitowych elementach, a możliwe są dalsze optymalizacje. Inną zaletą jest zgodność ze standardowymi funkcjami skrótu. SNARK-i tego typu sprawnie obsługują operacje bitowe (XOR, przesunięcia), co umożliwia efektywne wykorzystanie popularnych funkcji haszujących, np. SHA-256, Keccak-256 czy Grøstl.

Podsumowanie

ZKP to przełomowa technologia kryptograficzna, która coraz mocniej zaznacza swoją obecność w nowoczesnych systemach cyfrowych. Umożliwia ona weryfikację informacji bez konieczności jej ujawniania, co ma ogromne znaczenie dla prywatności, bezpieczeństwa i wydajności systemów informatycznych.

Zastosowania ZKP są już szeroko rozwijane – od prywatnych transakcji w kryptowalutach, aż po bezpieczną komunikację w systemach IoT. Ewolucja od interaktywnych dowodów do form nieinteraktywnych znacząco zwiększyła ich użyteczność i efektywność w środowiskach masowych, takich jak sieci zdecentralizowane.

Największym wyzwaniem wciąż pozostaje złożoność obliczeniowa generowania dowodów, co jednak jest aktywnie adresowane przez rozwój akceleracji sprzętowej i nowych konstrukcji (np. Binius). Wobec nadchodzącej ery komputerów kwantowych, kluczowy staje się rozwój postkwantowych wariantów ZKP.

ZKP mają potencjał, by stać się fundamentem nowoczesnej infrastruktury cyfrowej, zapewniając jednocześnie bezpieczeństwo, prywatność i skalowalność – czyli cechy kluczowe dla zaufanych systemów przyszłości.

Bibliografia

1. A. Micali, C. Rackoff i S. Goldwasser. 1985. „The knowledge complexity of interactive proof systems.” Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing. New York: Association for Computing Machinery. 291-304.
2. Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille i Greg Maxwell. 2017. „Bulletproofs: Short Proofs for Confidential Transactions and More.” Cryptology {ePrint} Archive (2017/1066).
3. Benjamin E. Diamond i Jim Posen. 2023. „Succinct Arguments over Towers of Binary Fields.” Cryptology {ePrint} Archive, Paper 2023/1784.
4. Bjorn Oude Roelink, Mohammed El-Hajj i Dipti Sarmah. 2024. „Systematic review: Comparing zk-SNARK, zk-STARK, and bulletproof protocols for privacy-preserving authentication.” SECURITY AND PRIVACY.
5. Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer i Madars Virza. 2014. „Zerocash: Decentralized Anonymous Payments from Bitcoin.” Cryptology {ePrint} Archive, (Paper 2014/349).
6. Eli Ben-Sasson, Iddo Bentov, Yinon Horesh i Michael Riabzev. 2018. „Scalable, transparent, and post-quantum secure computational integrity.” Cryptology {ePrint} Archive Paper 2018/046.
7. Jean-Jacques Quisquater, Myriam Quisquater, Muriel Quisquater, Michaël Quisquater, Louis C. Guillou, Marie Annick Guillou, Gaïd Guillou i inni. 1989. „How to Explain Zero-Knowledge Protocols to Your Children.” W Advances in Cryptology – CRYPTO ’89, 9th Annual International Cryptology Conference, 628-631. Santa Barbara,California, USA: Springer.
8. Shang Gao, Tianyu Zheng, Yu GUO, Zhe Peng i Bin Xiao. 2021. „Lattice-based Zero-knowledge Proofs for Blockchain Confidential Transactions.” Cryptology {ePrint} Archive, Paper 2021/1674.
9. T. Xie, Y. Zhang i D. Song. 2022. „Orion: Zero Knowledge Proof with Linear Prover Time.” Advances in Cryptology – CRYPTO 2022. Cham: Springer. 299-328.
10. Ying Ouyang, Deng Tang i Yanhong Xu. 2024. „Code-Based Zero-Knowledge from {VOLE}-in-the-Head and Their Applications: Simpler, Faster, and Smaller.” Cryptology {ePrint} Archive, Paper 2024/1414.
11. Z. Chen, Y. Jiang, Z. Song i L.Chen. 2023. „A Survey on Zero-Knowledge Authentication for Internet of Things.” Electronics.

Źródło: Wojsko Polskie

Przeczytaj też: