Ten post został po raz pierwszy opublikowany na Medium. Programmable Zero Knowledge Proofs Using zk-SNARKs: Part 1 | by sCrypt | Jul, 2022 | Medium
Udowodnij znajomość klucza prywatnego bez podpisów
Teoretycznie dowód z wiedzą zerową (ZKP) można skonstruować dla dowolnego problemu matematycznego¹, nie ujawniając tego rozwiązania. W praktyce opracowanie ZKP dla problemu często wymaga wynalezienia zupełnie nowego algorytmu kryptograficznego. Nie ma standardowego przepisu i wymaga rozległej i dogłębnej znajomości kryptografii. Na przykład łamigłówka ZK obejmuje protokoły ∑ i dowód deklaracji klucza ZK, zobowiązania Pedersena i heurystykę Fiata-Shamira.
zk-SNARKs standaryzują generację ZKP dla dowolnych problemów. Wystarczy wyrazić oryginalny problem, aby udowodnić go w formacie ZK, takim jak Circom w języku domenowym (DSL) lub Zokrates. Cała reszta jest obsługiwana przez ogólny framework zk-SNARK, ukrywający wszystkie zawiłości podstawowej kryptografii.
Przed zk-SNARKs, konstruowanie ZKP dla nowego problemu jest podobne do budowania nowego ASIC za każdym razem, gdy trzeba opracować nową aplikację ZKP. zk-SNARKs umożliwiają zbudowanie nowego ZKP poprzez proste zaprogramowanie ogólnego przeznaczenia „CPU ZK”. Pierwsza wymaga bycia kryptografem, a druga tylko programistą, co znacznie obniża barierę wejścia ZKP.
Aby zademonstrować siłę tej zmiany paradygmatu, używamy jej do skonstruowania najpopularniejszego ZKP: znajomości klucza prywatnego dla danego klucza publicznego, czyli logarytmu dyskretnego.
ZKP Wiedzy o Kluczu Prywatnym
Aby przenieść bitcoiny zablokowane na klucz/adres publiczny, właściciel musi wykazać, że zna odpowiedni klucz prywatny. Ale nie może tego po prostu ujawnić, w przeciwnym razie można ukraść bitcoiny. Odbywa się to za pomocą podpisu cyfrowego, formy ZKP². Pokazujemy alternatywny sposób osiągnięcia tego samego za pomocą zk-SNARK.
W Bitcoin klucz publiczny Q to po prostu klucz prywatny d mnożący generator G.
Poniższy kod Circom implementuje mnożenie skalarne na krzywej eliptycznej Bitcoina secp256k1. Możemy go łatwo użyć, aby udowodnić, że Q jest kluczem publicznym d:
Ustaw skalar wejściowy w wierszu 3 na d: zauważ, że jest prywatny i dlatego pozostaje poufny
Ustaw punkt wejściowy w linii 4 na G
Ustaw wyjście w linii 6 na Q.
Używamy standardowego algorytmu „podwój i dodaj”, aby ułatwić ekspozycję. Bardziej wydajny algorytm można znaleźć tutaj. Główna pętla występuje od linii 33 do linii 65. Używamy Secp256k1AddUnequal w linii 42 do dodawania punktów i Secp256k1Double w linii 43 do podwajania punktów. W każdej iteracji podwajamy się w wierszach 355–358. Dodajemy również, czy bieżący bit jest ustawiony.
Gdy już mamy kod Circom, możemy użyć naszej ogólnej biblioteki zk-SNARK, aby udowodnić znajomość klucza prywatnego, zachowując go w tajemnicy. Wykazaliśmy się wiedzą bez podpisu cyfrowego!
Czekaj na więcej przykładów ZKP wykorzystujących programowalność zk-SNARKs.
Podziękowanie
Ten artykuł jest inspirowany tym znakomitym zapisem.
UWAGI:
[1] W rzeczywistości ZKP można skonstruować dla dowolnego problemu NP.
[2] Używamy tu luźno ZK.
Autor : BitUp
Źródło : Programmable Zero Knowledge Proofs Using zk-SNARKs: Part 1 | by sCrypt | Jul, 2022 | Medium
