ZKP & ZK-SNARKS
Με λίγα λόγια
- zk-SNARKs = Συνοπτικά μη διαδραστικά επιχειρήματα γνώσης μηδενικής γνώσης
- Επιτρέπουν σε ένα μέρος να αποδείξει ότι γνωρίζει κάτι χωρίς να αποκαλύπτει την ίδια την πληροφορία
- Το Zcash χρησιμοποιεί zk-SNARKs για να αποδείξει ότι μια συναλλαγή είναι έγκυρη (σωστά ποσά, αδαπάνητες εισροές) χωρίς να αποκαλύπτει αποστολέα, παραλήπτη ή ποσό
- Το «Succinct» σημαίνει ότι η απόδειξη είναι μικρή και γρήγορη στην επαλήθευση, ακόμη και για σύνθετους ισχυρισμούς
- Το pool Orchard χρησιμοποιεί Halo 2, ένα σύστημα zk-SNARK με μηδενική ανάγκη για trusted setup
Τι είναι μια απόδειξη;
Οι αποδείξεις αποτελούν τη βάση όλων των μαθηματικών. Μια απόδειξη είναι ένας ισχυρισμός ή θεώρημα που προσπαθείς να αποδείξεις και μια ακολουθία παραγώγων που δηλώνουν ότι το θεώρημα έχει αποδειχθεί. Π.χ. το ότι όλες οι γωνίες ενός τριγώνου αθροίζουν 180° μπορεί να ελεγχθεί ανεξάρτητα από οποιονδήποτε (επαληθευτή).
Αποδείξεις
Αποδεικνύων ---> Διατυπώνει ισχυρισμό ---> Ο επαληθευτής επιλέγει ---> Αποδοχή/Απόρριψη
(Τόσο ο αποδεικνύων όσο και ο επαληθευτής είναι αλγόριθμοι)
Στην επιστήμη υπολογιστών, ο όρος για αποδείξεις που επαληθεύονται αποτελεσματικά είναι αποδείξεις NP. Αυτές οι σύντομες αποδείξεις μπορούν να επαληθευτούν σε πολυωνυμικό χρόνο. Η ευρύτερη ιδέα είναι: «Υπάρχει μια λύση σε ένα θεώρημα και μεταβιβάζεται στον επαληθευτή για έλεγχο».
Σε μια γλώσσα NP πρέπει να ισχύουν δύο προϋποθέσεις:
Πληρότητα: Οι αληθείς ισχυρισμοί θα γίνονται αποδεκτοί από τον επαληθευτή (επιτρέπει στους έντιμους αποδεικνύοντες να φτάσουν στην επαλήθευση)
Ορθότητα: Οι ψευδείς ισχυρισμοί δεν θα έχουν αποδείξεις (για κάθε στρατηγική εξαπάτησης του αποδεικνύοντος, δεν θα μπορεί να αποδείξει την ορθότητα ενός εσφαλμένου ισχυρισμού).
Διαδραστικές και πιθανοτικές αποδείξεις
Αλληλεπίδραση: Αντί να διαβάζει απλώς την απόδειξη, ο επαληθευτής αλληλεπιδρά με έναν αποδεικνύοντα αμφίδρομα σε αρκετούς γύρους μηνυμάτων.
Τυχαιότητα: Τα αιτήματα του επαληθευτή προς τον αποδεικνύοντα είναι τυχαιοποιημένα και ο αποδεικνύων πρέπει να μπορεί να απαντά σωστά σε καθένα από αυτά.
Χρησιμοποιώντας μαζί την αλληλεπίδραση και την τυχαιότητα, είναι δυνατό να αποδειχθεί ένας ισχυρισμός σε έναν τυφλό επαληθευτή σε πιθανοτικό πολυωνυμικό χρόνο (PPT).
Μπορούν οι διαδραστικές αποδείξεις να επαληθεύσουν αποτελεσματικά περισσότερα από τις αποδείξεις NP;
Αποδείξεις NP έναντι αποδείξεων IP:
| Δήλωση | NP | IP |
|---|
| NP | ναι | ναι |
| CO-NP | όχι | ναι |
| #P | όχι | ναι |
| PSPACE | όχι | ναι |
NP - Υπάρχει μια λύση σε μια δήλωση
CO-NP - Απόδειξη ότι δεν υπάρχουν λύσεις σε μια δήλωση
#P - Καταμέτρηση του αριθμού των λύσεων που υπάρχουν για μια δήλωση
PSPACE - Απόδειξη μιας εναλλαγής διαφορετικών δηλώσεων
Τι είναι η μηδενική γνώση;
Ό,τι μπορεί να υπολογίσει ένας επαληθευτής μετά από μια αλληλεπίδραση είναι ταυτόσημο με ό,τι θα μπορούσε να αποδείξει πριν από αυτήν. Η αλληλεπίδραση σε πολλούς γύρους μεταξύ του αποδεικνύοντος και του επαληθευτή δεν έχει αυξήσει την υπολογιστική ισχύ του επαληθευτή.
Η προσομοίωση Paradigm
Αυτό το πείραμα εμφανίζεται σε όλη την κρυπτογραφία. Παρουσιάζει μια «Πραγματική όψη» και μια «Προσομοιωμένη όψη».
Πραγματική όψη: Όλα τα πιθανά ιστορικά αλληλεπιδράσεων μεταξύ Αποδεικνύοντος και Επαληθευτή (P,V)
Προσομοιωμένη όψη: Ο επαληθευτής προσομοιώνει όλες τις πιθανές αλληλεπιδράσεις μεταξύ Αποδεικνύοντος και Επαληθευτή
Ένας διακριτής πολυωνυμικού χρόνου προσπαθεί να προσδιορίσει αν εξετάζει την πραγματική ή την προσομοιωμένη όψη και ζητά επανειλημμένα ένα δείγμα από αμφότερες.
Οι δύο όψεις λέγεται ότι είναι «υπολογιστικά μη διακρίσιμες» εάν, για όλους τους αλγορίθμους/στρατηγικές διακριτή, ακόμη και μετά τη λήψη πολυωνυμικού αριθμού δειγμάτων από την πραγματική ή την προσομοιωμένη όψη, η πιθανότητα είναι >1/2.
Επιχειρήματα γνώσης μηδενικής γνώσης
Ένα διαδραστικό πρωτόκολλο (P,V) είναι μηδενικής γνώσης εάν υπάρχει ένας προσομοιωτής (αλγόριθμος) τέτοιος ώστε, για κάθε επαληθευτή πιθανοτικού πολυωνυμικού χρόνου (όταν το θεώρημα είναι σωστό), οι κατανομές πιθανότητας που καθορίζουν την πραγματική από την προσομοιωμένη όψη είναι υπολογιστικά μη διακρίσιμες.
Τα διαδραστικά πρωτόκολλα είναι χρήσιμα όταν υπάρχει ένας μόνο επαληθευτής. Ένα παράδειγμα θα ήταν ένας φορολογικός ελεγκτής σε μια εφαρμογή μηδενικής γνώσης για «απόδειξη φόρων».
Τι είναι ένα SNARK;
Συνοπτικό μη διαδραστικό επιχείρημα γνώσης
Ευρύς ορισμός - Μια συνοπτική απόδειξη ότι μια δήλωση είναι αληθής. Η απόδειξη πρέπει να είναι σύντομη και γρήγορη στην επαλήθευση. Στα SNARKS αποστέλλεται ένα μόνο μήνυμα από τον Αποδεικνύοντα στον Επαληθευτή. Ο επαληθευτής μπορεί κατόπιν να επιλέξει να το αποδεχθεί ή να το απορρίψει.
Παράδειγμα δήλωσης: «Γνωρίζω ένα μήνυμα (m) τέτοιο ώστε SHA256(m)=0»
Σε ένα zk-SNARK η απόδειξη δεν αποκαλύπτει τίποτα για το μήνυμα (m).
Πολυώνυμα: Αθροίσματα όρων που περιέχουν μια σταθερά (όπως 1,2,3), μεταβλητές (όπως x,y,z) και εκθέτες μεταβλητών (όπως x², y³).
Παράδειγμα: «3x² + 8x + 17»
Αριθμητικό κύκλωμα: Ένα μοντέλο για τον υπολογισμό πολυωνύμων. Γενικότερα, μπορεί να οριστεί ως ένας κατευθυνόμενος άκυκλος γράφος, στον οποίο εκτελείται μια αριθμητική πράξη σε κάθε κόμβο του γράφου. Το κύκλωμα αποτελείται από πύλες πρόσθεσης, πύλες πολλαπλασιασμού και ορισμένες πύλες σταθερών. Με τον ίδιο τρόπο που τα Boolean κυκλώματα μεταφέρουν bits σε καλώδια, τα αριθμητικά κυκλώματα μεταφέρουν ακέραιους αριθμούς.
Σε αυτό το παράδειγμα, ο αποδεικνύων θέλει να πείσει τον επαληθευτή ότι γνωρίζει μια λύση για το αριθμητικό κύκλωμα.
Commitments: Για να το κάνει αυτό, ο αποδεικνύων θα τοποθετήσει όλες τις τιμές (ιδιωτικές και δημόσιες) που σχετίζονται με το κύκλωμα σε ένα commitment. Τα commitments αποκρύπτουν τις εισόδους τους χρησιμοποιώντας μια συνάρτηση της οποίας η έξοδος είναι μη αναστρέψιμη.
Το Sha256 είναι ένα παράδειγμα συνάρτησης κατακερματισμού που μπορεί να χρησιμοποιηθεί σε ένα σχήμα commitment.
Αφού ο αποδεικνύων δεσμευτεί στις τιμές, τα commitments αποστέλλονται στον επαληθευτή (με τη βεβαιότητα ότι δεν μπορεί να αποκαλύψει καμία από τις αρχικές τιμές). Ο αποδεικνύων μπορεί στη συνέχεια να δείξει στον επαληθευτή ότι γνωρίζει καθεμία από τις τιμές στους κόμβους του γράφου.
Μετασχηματισμός Fiat-Shamir
Για να γίνει το πρωτόκολλο μη διαδραστικό, ο αποδεικνύων παράγει τυχαιότητα (η οποία χρησιμοποιείται για την κρυφή πρόκληση) εκ μέρους του επαληθευτή, χρησιμοποιώντας μια κρυπτογραφική συνάρτηση κατακερματισμού. Αυτό είναι γνωστό ως τυχαίο μαντείο. Ο αποδεικνύων μπορεί στη συνέχεια να στείλει ένα μόνο μήνυμα στον επαληθευτή, ο οποίος μπορεί κατόπιν να ελέγξει ότι είναι σωστό.
Για να σχηματιστεί ένα SNARK που μπορεί να χρησιμοποιηθεί για γενικά κυκλώματα απαιτούνται δύο στοιχεία:
Λειτουργικό σχήμα commitment: Επιτρέπει σε έναν δεσμεύοντα να δεσμεύεται σε ένα πολυώνυμο με μια σύντομη συμβολοσειρά, την οποία μπορεί να χρησιμοποιήσει ένας επαληθευτής για να επιβεβαιώσει τις δηλωμένες αξιολογήσεις του δεσμευμένου πολυωνύμου.
Διαδραστικό μαντείο πολυωνύμων: Ο επαληθευτής ζητά από τον αποδεικνύοντα (αλγόριθμο) να ανοίξει όλα τα commitments σε διάφορα σημεία της επιλογής του χρησιμοποιώντας σχήμα commitment πολυωνύμων και ελέγχει ότι η ταυτότητα ισχύει μεταξύ τους.
Ρύθμιση
Οι διαδικασίες ρύθμισης βοηθούν τον επαληθευτή συνοψίζοντας ένα κύκλωμα και παράγοντας δημόσιες παραμέτρους.
Τύποι ρύθμισης προεπεξεργασίας:
Trusted Setup ανά κύκλωμα - Εκτελείται μία φορά για κάθε κύκλωμα. Είναι ειδικό για ένα κύκλωμα και η μυστική τυχαιότητα (Common Reference String) πρέπει να παραμείνει μυστική και να καταστραφεί.
Μια παραβιασμένη ρύθμιση σε αυτή τη μέθοδο σημαίνει ότι ένας ανέντιμος αποδεικνύων μπορεί να αποδείξει ψευδείς δηλώσεις.
Έμπιστο αλλά καθολικό Setup - Χρειάζεται να εκτελέσει trusted setup μόνο μία φορά και μπορεί στη συνέχεια να προεπεξεργαστεί ντετερμινιστικά πολλαπλά κυκλώματα.
Διαφανές Setup (χωρίς Trusted Setup)- Ο αλγόριθμος προεπεξεργασίας δεν χρησιμοποιεί καθόλου μυστική τυχαιότητα.
Τύποι κατασκευών αποδείξεων SNARK:
Groth16: Απαιτεί Trusted Setup, αλλά έχει πολύ σύντομες αποδείξεις που μπορούν να επαληθευτούν γρήγορα.
Sonic/Marlin/PLONK: Καθολικό έμπιστο Setup.
DARK/Halo/STARK: Χωρίς Trusted Setup, αλλά παράγουν ελαφρώς μεγαλύτερες αποδείξεις ή μπορεί να χρειάζονται περισσότερο χρόνο για να εκτελεστούν από τον αποδεικνύοντα.
Τα SNARKS είναι χρήσιμα όταν απαιτούνται πολλοί επαληθευτές, όπως σε ένα blockchain όπως το Zcash ή ένα zk-Rollup όπως το Aztec, ώστε πολλοί κόμβοι επικύρωσης να μην χρειάζεται να αλληλεπιδρούν σε αρκετούς γύρους με κάθε απόδειξη.
Πώς υλοποιούνται τα zk-SNARK στο Zcash;
Γενικά, οι αποδείξεις μηδενικής γνώσης είναι ένα εργαλείο για την επιβολή έντιμης συμπεριφοράς στα πρωτόκολλα χωρίς να αποκαλύπτεται καμία πληροφορία.
Το Zcash είναι ένα δημόσιο blockchain που διευκολύνει ιδιωτικές συναλλαγές. Τα zk-SNARK χρησιμοποιούνται για να αποδείξουν ότι μια ιδιωτική συναλλαγή είναι έγκυρη εντός των κανόνων συναίνεσης του δικτύου, χωρίς να αποκαλύπτονται άλλες λεπτομέρειες για τη συναλλαγή.
Επεξηγηματικό βίντεο - Σε αυτή τη διάλεξη, ο Ariel Gabizon περιγράφει το δέντρο Note Commitment του Zcash, την τυφλή αξιολόγηση πολυωνύμων και τις ομομορφικά κρυμμένες προκλήσεις, καθώς και τον τρόπο υλοποίησής τους στο δίκτυο.
Διάβασε το βιβλίο Halo2 για περισσότερες πληροφορίες.
Άλλες εφαρμογές μηδενικής γνώσης
Τα zk-SNARKs παρέχουν αρκετά πλεονεκτήματα σε μια ποικιλία διαφορετικών εφαρμογών. Ας δούμε μερικά παραδείγματα.
Κλιμάκωση: Αυτό επιτυγχάνεται με «Εξωτερική ανάθεση υπολογισμών». Δεν υπάρχει αυστηρή ανάγκη για μηδενική γνώση ώστε μια αλυσίδα L1 να επαληθεύσει την εργασία μιας off-chain υπηρεσίας. Οι συναλλαγές δεν είναι απαραίτητα ιδιωτικές σε ένα zk-EVM.
Το πλεονέκτημα μιας υπηρεσίας Rollup βασισμένης σε αποδείξεις (zk-Rollup) είναι η επεξεργασία μιας δέσμης εκατοντάδων/χιλιάδων συναλλαγών και η δυνατότητα του L1 να επαληθεύει μια συνοπτική απόδειξη ότι όλες οι συναλλαγές επεξεργάστηκαν σωστά, κλιμακώνοντας τη διεκπεραιωτική ικανότητα συναλλαγών του δικτύου κατά συντελεστή 100 ή 1000.
Διαλειτουργικότητα: Αυτό επιτυγχάνεται σε μια zk-γέφυρα με το «κλείδωμα» περιουσιακών στοιχείων σε μια αλυσίδα προέλευσης και την απόδειξη στην αλυσίδα προορισμού ότι τα περιουσιακά στοιχεία έχουν κλειδωθεί (απόδειξη συναίνεσης).
Συμμόρφωση: Έργα όπως το Espresso μπορούν να αποδείξουν ότι μια ιδιωτική συναλλαγή συμμορφώνεται με τους τοπικούς τραπεζικούς νόμους χωρίς να αποκαλύπτουν τις λεπτομέρειες της συναλλαγής.
Καταπολέμηση της παραπληροφόρησης: Μεταξύ αρκετών παραδειγμάτων εκτός blockchain και κρυπτονομισμάτων, είναι η χρήση δημιουργίας αποδείξεων σε εικόνες που έχουν υποβληθεί σε επεξεργασία από ειδησεογραφικά και μέσα ενημέρωσης, ώστε οι θεατές να μπορούν να επαληθεύουν ανεξάρτητα την πηγή μιας εικόνας και όλες τις λειτουργίες που εκτελέστηκαν σε αυτήν. https://medium.com/@boneh/using-zk-proofs-to-fight-disinformation-17e7d57fe52f
Περαιτέρω μάθηση:
Βιβλιογραφία μηδενικής γνώσης - a16z Crypto
zkSNARKs με τον Hanh Huynh Huu
Zcash: Halo 2 και SNARKs χωρίς Trusted Setups - Sean Bowe στο Dystopia labs
Αποδείξεις μηδενικής γνώσης με τον Avi Wigderson - Numberphile
Διαδραστικές αποδείξεις μηδενικής γνώσης - Άρθρο του Chainlink
Διάλεξη 1: Εισαγωγή και ιστορία του ZKP - zklearning.org
Απλή εξήγηση των αριθμητικών κυκλωμάτων - Medium
Η κλιμάκωση είναι βαρετή, η ιδιωτικότητα είναι νεκρή: ZK-Proofs, σε τι χρησιμεύουν;
Σχετικές σελίδες
