Vitalik Buterin μέσω του Ιστολόγιο Vitalik Buterin
Αυτός είναι ένας καθρέφτης της ανάρτησης στο https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
Αυτό είναι το τρίτο μέρος μιας σειράς άρθρων που εξηγούν πώς λειτουργεί η τεχνολογία πίσω από τα zk-SNARKs. τα προηγούμενα άρθρα για τετραγωνικά αριθμητικά προγράμματα και ζεύγη ελλειπτικών καμπυλών απαιτείται ανάγνωση και αυτό το άρθρο θα προϋποθέτει τη γνώση και των δύο εννοιών. Υποτίθεται επίσης βασική γνώση του τι είναι και τι κάνουν τα zk-SNARK. Δείτε επίσης Το άρθρο του Christian Reitwiessner εδώ για μια άλλη τεχνική εισαγωγή.
Στα προηγούμενα άρθρα, παρουσιάσαμε το πρόγραμμα τετραγωνικής αριθμητικής, έναν τρόπο αναπαράστασης οποιουδήποτε υπολογιστικού προβλήματος με πολυωνυμική εξίσωση που είναι πολύ πιο επιδεκτική σε διάφορες μορφές μαθηματικών τεχνασμάτων. Παρουσιάσαμε επίσης ζεύγη ελλειπτικών καμπυλών, που επιτρέπουν μια πολύ περιορισμένη μορφή μονόδρομης ομομορφικής κρυπτογράφησης που σας επιτρέπει να κάνετε έλεγχο ισότητας. Τώρα, θα ξεκινήσουμε από εκεί που σταματήσαμε και θα χρησιμοποιήσουμε ζεύγη ελλειπτικών καμπυλών, μαζί με μερικά άλλα μαθηματικά κόλπα, προκειμένου να επιτρέψουμε σε έναν δοκιμαστή να αποδείξει ότι γνωρίζει μια λύση για ένα συγκεκριμένο QAP χωρίς να αποκαλύψει τίποτα άλλο για το πραγματική λύση.
Αυτό το άρθρο θα επικεντρωθεί στο Πρωτόκολλο Πινόκιο από τους Parno, Gentry, Howell και Raykova από το 2013 (που συχνά ονομάζεται PGHR13). υπάρχουν μερικές παραλλαγές στον βασικό μηχανισμό, επομένως ένα σχήμα zk-SNARK που εφαρμόζεται στην πράξη μπορεί να λειτουργεί ελαφρώς διαφορετικά, αλλά οι βασικές αρχές θα παραμείνουν γενικά οι ίδιες.
Για να ξεκινήσουμε, ας πάμε στη βασική κρυπτογραφική υπόθεση που βασίζεται στην ασφάλεια του μηχανισμού που πρόκειται να χρησιμοποιήσουμε: *γνώση εκθέτη* υπόθεση.
Βασικά, εάν λάβετε ένα ζεύγος σημείων � και �, όπου �⋅�=�, και λάβετε έναν πόντο �, τότε δεν είναι δυνατό να καταλήξετε στο �⋅� εκτός εάν το � «προέρχεται» από το � με κάποιο τρόπο που ξέρεις. Αυτό μπορεί να φαίνεται διαισθητικά προφανές, αλλά αυτή η υπόθεση στην πραγματικότητα δεν μπορεί να προέλθει από οποιαδήποτε άλλη υπόθεση (π.χ. διακριτή σκληρότητα καταγραφής) που συνήθως χρησιμοποιούμε όταν αποδεικνύουμε την ασφάλεια των πρωτοκόλλων που βασίζονται σε ελλειπτικές καμπύλες, και έτσι τα zk-SNARK βασίζονται στην πραγματικότητα σε ένα κάπως πιο τρανταχτό θεμέλιο από την κρυπτογραφία ελλειπτικής καμπύλης γενικότερα — αν και εξακολουθεί να είναι αρκετά στιβαρό ώστε οι περισσότεροι κρυπτογράφοι να είναι εντάξει με αυτό.
Τώρα, ας δούμε πώς μπορεί να χρησιμοποιηθεί. Υποθέτουμε ότι ένα ζευγάρι σημείων (�,�) πέφτει από τον ουρανό, όπου �⋅�=�, αλλά κανείς δεν ξέρει ποια είναι η τιμή του �. Τώρα, ας υποθέσουμε ότι βρίσκω ένα ζευγάρι σημείων (�,�) όπου �⋅�=�. Στη συνέχεια, η υπόθεση KoE υπονοεί ότι ο μόνος τρόπος που θα μπορούσα να είχα κάνει αυτό το ζευγάρι πόντων ήταν παίρνοντας � και � και πολλαπλασιάζοντας και τα δύο με κάποιο παράγοντα r που προσωπικά γνωρίζω. Σημειώστε επίσης ότι χάρη στη μαγεία των ζευγών ελλειπτικών καμπυλών, ελέγχοντας ότι �=�⋅� στην πραγματικότητα δεν απαιτεί γνώση � – Αντίθετα, μπορείτε απλώς να ελέγξετε εάν �(�,�)=�(�,�).
Ας κάνουμε κάτι πιο ενδιαφέρον. Ας υποθέσουμε ότι έχουμε δέκα ζεύγη πόντων που πέφτουν από τον ουρανό: (�1,�1),(�2,�2)…(�10,�10). Σε όλες τις περιπτώσεις, ��⋅�=��. Ας υποθέσουμε ότι στη συνέχεια σας παρέχω ένα ζεύγος σημείων (�,�) όπου �⋅�=�. Τι ξέρεις τώρα; Γνωρίζετε ότι το � είναι κάποιος γραμμικός συνδυασμός �1⋅�1+�2⋅�2+…+�10⋅�10, όπου γνωρίζω τους συντελεστές �1,��2...�10. Δηλαδή, ο μόνος τρόπος για να φτάσετε σε ένα τέτοιο ζεύγος σημείων (�,�) είναι να πάρετε μερικά πολλαπλάσια των �1,�2...�10 και να τα προσθέσετε μαζί και να κάνετε τον ίδιο υπολογισμό με �1,�2… �10.
Λάβετε υπόψη ότι, δεδομένου οποιουδήποτε συγκεκριμένου συνόλου �1...�10 σημείων για τα οποία μπορεί να θέλετε να ελέγξετε γραμμικούς συνδυασμούς, δεν μπορείτε πραγματικά να δημιουργήσετε τα συνοδευτικά �1…�10 σημεία χωρίς να γνωρίζετε τι είναι και εάν γνωρίζετε τι � είναι τότε μπορείτε να δημιουργήσετε ένα ζεύγος (�,�) όπου �⋅�=� για ό,τι θέλετε, χωρίς να μπείτε στον κόπο να δημιουργήσετε έναν γραμμικό συνδυασμό. Ως εκ τούτου, για να λειτουργήσει αυτό, είναι απολύτως επιτακτικό όποιος δημιουργεί αυτά τα σημεία να είναι αξιόπιστος και να διαγράφει πραγματικά � μόλις δημιούργησε τα δέκα σημεία. Από εδώ προέρχεται η έννοια της «έμπιστης εγκατάστασης»..
Θυμηθείτε ότι η λύση σε ένα QAP είναι ένα σύνολο πολυωνύμων (�,�,�) τέτοια ώστε �(�)⋅�(�)−��(�)=�(�)⋅�(�), όπου:
- Το � είναι ένας γραμμικός συνδυασμός ενός συνόλου πολυωνύμων {�1…��}
- Το � είναι ο γραμμικός συνδυασμός του {�1…��} με τους ίδιους συντελεστές
- Το � είναι ένας γραμμικός συνδυασμός του {�1…��} με τους ίδιους συντελεστές
Τα σύνολα {�1…��},{�1…��} και {�1…��} και το πολυώνυμο � αποτελούν μέρος της δήλωσης προβλήματος.
Ωστόσο, στις περισσότερες περιπτώσεις του πραγματικού κόσμου, τα �,� και � είναι εξαιρετικά μεγάλα. για κάτι με πολλές χιλιάδες πύλες κυκλώματος όπως μια συνάρτηση κατακερματισμού, τα πολυώνυμα (και οι παράγοντες για τους γραμμικούς συνδυασμούς) μπορεί να έχουν πολλές χιλιάδες όρους. Ως εκ τούτου, αντί να έχουμε τον prover να παρέχει απευθείας τους γραμμικούς συνδυασμούς, θα χρησιμοποιήσουμε το τέχνασμα που εισαγάγαμε παραπάνω για να αποδείξουμε τον prover ότι παρέχει κάτι που είναι γραμμικός συνδυασμός, αλλά χωρίς να αποκαλύπτει τίποτα άλλο.
Ίσως έχετε παρατηρήσει ότι το παραπάνω κόλπο λειτουργεί σε ελλειπτικά σημεία καμπύλης, όχι σε πολυώνυμα. Ως εκ τούτου, αυτό που συμβαίνει στην πραγματικότητα είναι ότι προσθέτουμε τις ακόλουθες τιμές στην αξιόπιστη εγκατάσταση:
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
Μπορείτε να σκεφτείτε το t ως ένα «μυστικό σημείο» στο οποίο αξιολογείται το πολυώνυμο. � είναι μια "γεννήτρια" (κάποιο τυχαίο ελλειπτικό σημείο καμπύλης που καθορίζεται ως μέρος του πρωτοκόλλου) και �,��,�� και � είναι «τοξικά απόβλητα», αριθμοί που πρέπει οπωσδήποτε να διαγραφούν με κάθε κόστος, διαφορετικά όποιος τα έχει θα μπορεί να κάνει πλαστές αποδείξεις. Τώρα, αν κάποιος σας δώσει ένα ζευγάρι πόντους �, � έτσι ώστε �⋅��=� (υπενθύμιση: δεν χρειάζεται �� να το ελέγξουμε, καθώς μπορούμε να κάνουμε έναν έλεγχο ζεύξης), τότε ξέρετε ότι αυτό που που σας δίνουμε είναι ένας γραμμικός συνδυασμός �� πολυωνύμων που αξιολογούνται σε �.
Ως εκ τούτου, μέχρι στιγμής ο prover πρέπει να δώσει:
- ��=�⋅�(�),���=�⋅�(�)⋅��
- ��=�⋅�(�),���=�⋅�(�)⋅��
- ��=�⋅�(�),���=�⋅�(�)⋅��
Σημειώστε ότι ο prover στην πραγματικότητα δεν χρειάζεται να γνωρίζει (και δεν πρέπει να γνωρίζει!) �,��,�� ή �� για να υπολογίσει αυτές τις τιμές. Αντίθετα, ο prover θα πρέπει να μπορεί να υπολογίσει αυτές τις τιμές μόνο από τα σημεία που προσθέτουμε στην αξιόπιστη εγκατάσταση.
Το επόμενο βήμα είναι να βεβαιωθείτε ότι και οι τρεις γραμμικοί συνδυασμοί έχουν τους ίδιους συντελεστές. Αυτό μπορούμε να το κάνουμε προσθέτοντας ένα άλλο σύνολο τιμών στην αξιόπιστη ρύθμιση: �⋅(��(�)+��(�)+��(�))⋅�, όπου το � είναι ένας άλλος αριθμός που θα πρέπει να θεωρείται "τοξικός waste» και απορρίπτεται αμέσως μόλις ολοκληρωθεί η αξιόπιστη εγκατάσταση. Στη συνέχεια, μπορούμε να ζητήσουμε από τον prover να δημιουργήσει έναν γραμμικό συνδυασμό με αυτές τις τιμές με τους ίδιους συντελεστές και να χρησιμοποιήσει το ίδιο τέχνασμα σύζευξης όπως παραπάνω για να επαληθεύσει ότι αυτή η τιμή ταιριάζει με το παρεχόμενο �+�+�.
Τέλος, πρέπει να αποδείξουμε ότι �⋅�−�=�⋅�. Αυτό το κάνουμε για άλλη μια φορά με έλεγχο σύζευξης:
�(��,��)/�(���,�)?=�(�ℎ,�⋅�(�))
Όπου �ℎ=�⋅�(�). Εάν η σύνδεση μεταξύ αυτής της εξίσωσης και του �⋅�−�=�⋅� δεν έχει νόημα για εσάς, επιστρέψτε και διαβάστε το άρθρο για τα ζευγάρια.
Είδαμε παραπάνω πώς να μετατρέψουμε τα �,� και � σε ελλειπτικά σημεία καμπύλης. Το � είναι απλώς η γεννήτρια (δηλαδή το σημείο της ελλειπτικής καμπύλης ισοδύναμο του αριθμού ένα). Μπορούμε να προσθέσουμε �⋅�(�) στην αξιόπιστη ρύθμιση. � είναι πιο δύσκολο. Το � είναι απλώς ένα πολυώνυμο και προβλέπουμε πολύ λίγο εκ των προτέρων σχετικά με το ποιοι θα είναι οι συντελεστές του για κάθε μεμονωμένη λύση QAP. Ως εκ τούτου, πρέπει να προσθέσουμε ακόμη περισσότερα δεδομένα στην αξιόπιστη εγκατάσταση. συγκεκριμένα η σειρά:
�,�⋅�,�⋅�2,�⋅�3,�⋅�4….
Στην αξιόπιστη εγκατάσταση του Zcash, η ακολουθία εδώ φτάνει περίπου τα 2 εκατομμύρια. Αυτές είναι πόσες δυνάμεις του � χρειάζεστε για να βεβαιωθείτε ότι θα μπορείτε πάντα να υπολογίζετε το �(�), τουλάχιστον για τη συγκεκριμένη περίπτωση QAP που τους ενδιαφέρει. Και με αυτό, ο prover μπορεί να παρέχει όλες τις πληροφορίες στον επαληθευτή για να κάνει τον τελικό έλεγχο.
Υπάρχει μια ακόμη λεπτομέρεια που πρέπει να συζητήσουμε. Τις περισσότερες φορές δεν θέλουμε απλώς να αποδείξουμε αφηρημένα ότι κάποια λύση υπάρχει για κάποιο συγκεκριμένο πρόβλημα. μάλλον, θέλουμε να αποδείξουμε είτε την ορθότητα κάποιας συγκεκριμένης λύσης (π.χ. αποδεικνύοντας ότι αν πάρετε τη λέξη "αγελάδα" και το SHA3 την κατακερματίσετε ένα εκατομμύριο φορές, το τελικό αποτέλεσμα ξεκινά με 0x73064fe5), είτε ότι υπάρχει λύση εάν περιορίσετε κάποιες από τις παραμέτρους. Για παράδειγμα, σε μια παρουσία κρυπτονομίσματος όπου τα ποσά των συναλλαγών και τα υπόλοιπα των λογαριασμών είναι κρυπτογραφημένα, θέλετε να αποδείξετε ότι γνωρίζετε κάποιο κλειδί αποκρυπτογράφησης k έτσι ώστε:
decrypt(old_balance, k) >= decrypt(tx_value, k)
decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
Το κρυπτογραφημένο old_balance
, tx_value
και new_balance
θα πρέπει να προσδιορίζονται δημόσια, καθώς αυτές είναι οι συγκεκριμένες τιμές που προσπαθούμε να επαληθεύσουμε τη συγκεκριμένη στιγμή. μόνο το κλειδί αποκρυπτογράφησης πρέπει να είναι κρυφό. Απαιτούνται ορισμένες μικρές τροποποιήσεις στο πρωτόκολλο για τη δημιουργία ενός "προσαρμοσμένου κλειδιού επαλήθευσης" που αντιστοιχεί σε κάποιο συγκεκριμένο περιορισμό στις εισόδους.
Τώρα, ας κάνουμε ένα βήμα πίσω. Πρώτα απ 'όλα, εδώ είναι ο αλγόριθμος επαλήθευσης στο σύνολό του, ευγενική προσφορά του Ben Sasson, Tromer, Virza και Chiesa:
Η πρώτη γραμμή ασχολείται με την παραμετροποίηση. ουσιαστικά, μπορείτε να σκεφτείτε τη λειτουργία του ως τη δημιουργία ενός "προσαρμοσμένου κλειδιού επαλήθευσης" για τη συγκεκριμένη περίπτωση του προβλήματος όπου προσδιορίζονται ορισμένα από τα επιχειρήματα. Η δεύτερη γραμμή είναι ο έλεγχος γραμμικού συνδυασμού για �,� και �; η τρίτη γραμμή είναι ο έλεγχος ότι οι γραμμικοί συνδυασμοί έχουν τους ίδιους συντελεστές και η τέταρτη γραμμή είναι ο έλεγχος προϊόντος �⋅�−�=�⋅�.
Συνολικά, η διαδικασία επαλήθευσης είναι μερικοί πολλαπλασιασμοί ελλειπτικών καμπυλών (ένας για κάθε μεταβλητή «δημόσιας» εισόδου) και πέντε έλεγχοι σύζευξης, ένας από τους οποίους περιλαμβάνει έναν επιπλέον πολλαπλασιασμό ζεύξης. Η απόδειξη περιέχει οκτώ ελλειπτικά σημεία καμπύλης: ένα ζευγάρι σημείων το καθένα για �(�),�(�) και �(�), ένα σημείο �� για �⋅(�(�)+�(�)+�(� )), και ένα σημείο �ℎ για �(�). Επτά από αυτά τα σημεία βρίσκονται στην καμπύλη �� (32 byte το καθένα, καθώς μπορείτε να συμπιέσετε τη συντεταγμένη � σε ένα μόνο bit) και στην υλοποίηση Zcash ένα σημείο (��) βρίσκεται στη συνεστραμμένη καμπύλη στο ��2 (64 bytes), οπότε το συνολικό μέγεθος της απόδειξης είναι ~288 byte.
Τα δύο πιο δύσκολα υπολογιστικά μέρη της δημιουργίας μιας απόδειξης είναι:
- Διαίρεση (�⋅�−�)/� για να ληφθεί � (αλγόριθμοι που βασίζονται στο Γρήγορος μετασχηματισμός Fourier μπορεί να το κάνει σε υποτετραγωνικό χρόνο, αλλά εξακολουθεί να είναι αρκετά υπολογιστικά εντατικό)
- Κάνοντας τους πολλαπλασιασμούς και τις προσθέσεις της ελλειπτικής καμπύλης για τη δημιουργία των τιμών �(�),�(�),�(�) και �(�) και τα αντίστοιχα ζεύγη τους
Ο βασικός λόγος για τον οποίο η δημιουργία μιας απόδειξης είναι τόσο δύσκολη είναι το γεγονός ότι αυτό που ήταν μια ενιαία δυαδική λογική πύλη στον αρχικό υπολογισμό μετατρέπεται σε μια πράξη που πρέπει να υποβληθεί σε κρυπτογραφική επεξεργασία μέσω πράξεων ελλειπτικής καμπύλης, εάν κάνουμε μια απόδειξη μηδενικής γνώσης από αυτήν . Αυτό το γεγονός, μαζί με την υπεργραμμικότητα των γρήγορων μετασχηματισμών Fourier, σημαίνει ότι η δημιουργία απόδειξης διαρκεί ~20–40 δευτερόλεπτα για μια συναλλαγή Zcash.
Μια άλλη πολύ σημαντική ερώτηση είναι: μπορούμε να προσπαθήσουμε να κάνουμε την αξιόπιστη ρύθμιση λίγο… λιγότερο απαιτητική; Δυστυχώς δεν μπορούμε να το κάνουμε εντελώς άπιστο. η ίδια η υπόθεση KoE αποκλείει τη δημιουργία ανεξάρτητων ζευγών (��,���⋅�) χωρίς να γνωρίζουμε τι είναι. Ωστόσο, μπορούμε να αυξήσουμε σημαντικά την ασφάλεια χρησιμοποιώντας τον πολυμερή υπολογισμό �-of-� - δηλαδή, δημιουργώντας την αξιόπιστη ρύθμιση μεταξύ � μερών με τέτοιο τρόπο ώστε εφόσον τουλάχιστον ένας από τους συμμετέχοντες διέγραψε τα τοξικά του απόβλητα, τότε είστε εντάξει .
Για να πάρετε μια ιδέα για το πώς θα το κάνατε αυτό, ακολουθεί ένας απλός αλγόριθμος για τη λήψη ενός υπάρχοντος σετ (�,�⋅�,��⋅�2,�⋅�3…) και "προσθήκη" του δικού σας μυστικού έτσι ώστε να χρειάζεστε τόσο το μυστικό σας όσο και το προηγούμενο μυστικό (ή το προηγούμενο σύνολο μυστικών) για να εξαπατήσετε.
Το σύνολο εξόδου είναι απλά:
�,(�⋅�)⋅�,(�⋅�2)⋅�2,(�⋅�3)⋅�3…
Λάβετε υπόψη ότι μπορείτε να δημιουργήσετε αυτό το σετ γνωρίζοντας μόνο το αρχικό σετ και τα s, και το νέο σετ λειτουργεί με τον ίδιο τρόπο όπως το παλιό σετ, με τη διαφορά ότι τώρα χρησιμοποιείτε το �⋅� ως "τοξικό απόβλητο" αντί του �. Εφόσον εσείς και το άτομο (ή τα άτομα) που δημιούργησαν το προηγούμενο σετ δεν αποτυγχάνετε να διαγράψετε τα τοξικά σας απόβλητα και αργότερα να συνεννοηθείτε, το σετ είναι "ασφαλές".
Αυτό για την πλήρη αξιόπιστη εγκατάσταση είναι αρκετά πιο δύσκολο, καθώς εμπλέκονται πολλές τιμές και ο αλγόριθμος πρέπει να γίνει μεταξύ των μερών σε αρκετούς γύρους. Είναι ένας τομέας ενεργούς έρευνας για να δούμε αν ο αλγόριθμος υπολογισμού πολλαπλών μερών μπορεί να απλοποιηθεί περαιτέρω και να απαιτήσει λιγότερους γύρους ή να γίνει πιο παραλληλός, καθώς όσο περισσότερα μπορείτε να το κάνετε τόσο περισσότερα μέρη καθίσταται εφικτό να συμπεριλάβετε στη διαδικασία αξιόπιστης ρύθμισης . Είναι λογικό να δούμε γιατί μια αξιόπιστη ρύθμιση μεταξύ έξι συμμετεχόντων που όλοι γνωρίζουν και συνεργάζονται μεταξύ τους μπορεί να κάνει μερικούς ανθρώπους να νιώθουν άβολα, αλλά μια αξιόπιστη ρύθμιση με χιλιάδες συμμετέχοντες θα ήταν σχεδόν αδιάκριτη από την έλλειψη εμπιστοσύνης – και αν είστε πραγματικά παρανοϊκοί , μπορείτε να μπείτε και να συμμετάσχετε στη διαδικασία ρύθμισης μόνοι σας και να είστε βέβαιοι ότι διαγράψατε προσωπικά την αξία σας.
Ένας άλλος τομέας ενεργούς έρευνας είναι η χρήση άλλων προσεγγίσεων που δεν χρησιμοποιούν ζεύγη και το ίδιο αξιόπιστο πρότυπο εγκατάστασης για την επίτευξη του ίδιου στόχου. βλέπω Η πρόσφατη παρουσίαση του Eli ben Sasson για μία εναλλακτική (αν και προειδοποιήστε, είναι τουλάχιστον τόσο περίπλοκο μαθηματικά όσο είναι τα SNARK!)
Ιδιαίτερες ευχαριστίες στον Ariel Gabizon και τον Christian Reitwiessner για την κριτική.
- SEO Powered Content & PR Distribution. Ενισχύστε σήμερα.
- PlatoData.Network Vertical Generative Ai. Ενδυναμώστε τον εαυτό σας. Πρόσβαση εδώ.
- PlatoAiStream. Web3 Intelligence. Ενισχύθηκε η γνώση. Πρόσβαση εδώ.
- PlatoESG. Ανθρακας, Cleantech, Ενέργεια, Περιβάλλον, Ηλιακός, Διαχείριση των αποβλήτων. Πρόσβαση εδώ.
- PlatoHealth. Ευφυΐα βιοτεχνολογίας και κλινικών δοκιμών. Πρόσβαση εδώ.
- BlockOffsets. Εκσυγχρονισμός της περιβαλλοντικής αντιστάθμισης ιδιοκτησίας. Πρόσβαση εδώ.
- πηγή: Νοημοσύνη δεδομένων Πλάτωνα.