Loading...
Σειρά: Zcash από πρώτες αρχές . Άρθρο 5 . Αποδείξεις μηδενικής γνώσης Κοινό: νέοι χρήστες. Βασιζόμαστε σε κάθε προηγούμενο άρθρο (πεπερασμένα πεδία, καμπύλες, commitments, δέντρα Merkle), αλλά επαναφέρουμε κάθε ιδέα όταν τη χρειαζόμαστε. Με τι θα φύγεις: μια διαισθητική, σωστή κατανόηση του τι είναι μια απόδειξη μηδενικής γνώσης, των τριών εγγυήσεων που παρέχει, του πώς αποδεικνύονται αυθαίρετες δηλώσεις και του τι τροφοδοτεί το Zcash του Sapling και το Orchard.
Αυτό είναι το άρθρο προς το οποίο ανέβαινε ολόκληρη η σειρά. Από το Άρθρο 0 και μετά λέγαμε συνεχώς ότι μια πληρωμή επικυρώνεται «πίσω από μια κουρτίνα», αποδεικνύεται σωστή ενώ δεν αποκαλύπτει τίποτα. Μια απόδειξη μηδενικής γνώσης είναι αυτή η κουρτίνα. Είναι το κομμάτι που τελικά λύνει το παράδοξο με το οποίο ξεκινήσαμε: πώς μπορεί το κοινό να επαληθεύσει μια συναλλαγή που δεν επιτρέπεται να δει;
Θυμήσου την αντίφαση στην καρδιά του Zcash:
Αυτά μοιάζουν αμοιβαία αποκλειόμενα. Η επαλήθευση φαίνεται να απαιτεί να κοιτάς. Η ιδιωτικότητα απαγορεύει να κοιτάς. Αν δεν μπορείς να τα συμφιλιώσεις, δεν μπορείς να έχεις ιδιωτικό χρήμα που να εμπιστεύεται ο καθένας.
Μια απόδειξη μηδενικής γνώσης (ZKP) είναι η συμφιλίωση. Επιτρέπει σε έναν αποδεικνύοντα να πείσει έναν επαληθευτή ότι μια δήλωση είναι αληθής χωρίς να αποκαλύπτει τίποτα πέρα από το γεγονός ότι είναι αληθής. Κανένα ποσό. Καμία ταυτότητα. Κανένα note. Μόνο: «όλα εδώ υπακούουν στους κανόνες.» Ας χτίσουμε τη διαίσθηση πριν από κάθε μηχανισμό.
Απόδειξε ότι γνωρίζεις έναν κωδικό χωρίς να τον πεις. Ένας ιστότοπος θα μπορούσε να επαληθεύσει ότι γνωρίζεις τον κωδικό σου παρακολουθώντας σε να ξεκλειδώνεις κάτι που ξεκλειδώνει μόνο ο κωδικός, χωρίς να βλέπει ποτέ τον ίδιο τον κωδικό. Αποδεικνύεις γνώση χωρίς αποκάλυψη.
Ο φίλος με αχρωματοψία και οι δύο μπάλες. Κρατάς μια κόκκινη και μια πράσινη μπάλα που μοιάζουν ίδιες στον φίλο σου με αχρωματοψία. Θέλεις να τον πείσεις ότι έχουν διαφορετικά χρώματα χωρίς να του πεις ποια είναι ποια. Κρύβει και τις δύο πίσω από την πλάτη του, προαιρετικά τις ανταλλάσσει, και σου δείχνει μία. Λες αν τις αντάλλαξε. Αν οι μπάλες όντως διαφέρουν, έχεις πάντα δίκιο. Αν ήταν ίδιες, θα μάντευες, σωστά μόνο τις μισές φορές. Μετά από 20 γύρους, το αδιάκοπο σερί σου τον πείθει ότι διαφέρουν, όμως δεν μαθαίνει ποτέ ποια μπάλα είναι κόκκινη. Πείθεται για ένα γεγονός χωρίς να μαθαίνει τίποτα άλλο. Αυτή είναι η μηδενική γνώση σε μικρογραφία.
Η σπηλιά. Μια σπηλιά σε σχήμα δαχτυλιδιού έχει στο βάθος μια μαγική πόρτα που ανοίγει μόνο με μια μυστική λέξη. Ισχυρίζεσαι ότι γνωρίζεις τη λέξη. Για να το αποδείξεις χωρίς να την αποκαλύψεις: ένας επαληθευτής περιμένει έξω ενώ μπαίνεις και επιλέγεις τυχαία το αριστερό ή το δεξί πέρασμα. Έπειτα ο επαληθευτής φωνάζει από ποια πλευρά θέλει να βγεις. Αν γνωρίζεις πραγματικά τη λέξη, μπορείς πάντα να συμμορφωθείς (μπορείς να ανοίξεις την πόρτα για να αλλάξεις πλευρά αν χρειάζεται). Αν μπλοφάρεις, μπορείς να βγεις από τη σωστή πλευρά μόνο από τύχη, με πιθανότητα 50/50 σε κάθε γύρο. Επανάλαβέ το 20 φορές και οι πιθανότητες ενός μπλοφαδόρου να επιβιώσει είναι λιγότερες από μία στο εκατομμύριο.
Αυτή η ιστορία της σπηλιάς δείχνει διακριτικά τις τρεις εγγυήσεις που πρέπει να παρέχει κάθε απόδειξη μηδενικής γνώσης.
| Εγγύηση | Στην ιστορία της σπηλιάς | Στο Zcash |
|---|---|---|
| Πληρότητα | Αν γνωρίζεις τη λέξη, βγαίνεις πάντα από τη σωστή πλευρά | Μια έγκυρη συναλλαγή παράγει πάντα μια αποδεκτή απόδειξη |
| Ακεραιότητα | Ένας μπλοφαδόρος συλλαμβάνεται με συντριπτική πιθανότητα | Μια δόλια συναλλαγή (πλαστό χρήμα, διπλή δαπάνη) δεν μπορεί να παράγει μια αποδεκτή απόδειξη |
| Μηδενική γνώση | Ο επαληθευτής δεν ακούει ποτέ τη μυστική λέξη | Το δίκτυο δεν μαθαίνει ποτέ ποσά, διευθύνσεις ή ποιο note είναι αυτό |
Αν αποτύχει οποιαδήποτε από αυτές, το σύστημα καταρρέει: χωρίς πληρότητα απορρίπτονται οι ειλικρινείς χρήστες· χωρίς ακεραιότητα οι πλαστογράφοι τυπώνουν χρήμα· χωρίς μηδενική γνώση η ιδιωτικότητα εξατμίζεται.
Η σπηλιά αποδεικνύει ένα χαριτωμένο γεγονός. Το Zcash χρειάζεται να αποδείξει μια σύνθετη δήλωση: «Γνωρίζω ένα αδιάθετο note στο δέντρο, είμαι εξουσιοδοτημένος να το δαπανήσω, το nullifier του υπολογίζεται σωστά και οι εισροές μου ισούνται με τις εκροές μου.» Πώς φτάνουμε από μπάλες και σπηλιές σε αυτό;
Η γέφυρα είναι μια ιδέα που συνδέει ολόκληρη αυτή τη σειρά:
Κάθε δήλωση που μπορείς να ελέγξεις με έναν υπολογισμό μπορεί να ξαναγραφτεί ως ένα αριθμητικό κύκλωμα: ένα δίκτυο προσθέσεων και πολλαπλασιασμών πάνω σε ένα πεπερασμένο πεδίο (Άρθρο 1).
Σκέψου το κύκλωμα ως μια λίστα αριθμητικών περιορισμών που όλοι ικανοποιούνται μόνο αν η δήλωση είναι αληθής. Οι ιδιωτικές είσοδοι που κάνουν τα πάντα να επαληθεύονται, το note σου, το κλειδί σου, η διαδρομή Merkle, ονομάζονται μάρτυρας.
Γι’ αυτό αφιερώσαμε το Άρθρο 1 στα πεπερασμένα πεδία και το Άρθρο 3 στα hashes φιλικά προς ZK: το κύκλωμα μιλά την αριθμητική των πεδίων, επομένως κάθε λειτουργία μέσα στη δήλωση (συμπεριλαμβανομένου του hashing και της ανάβασης Merkle του Άρθρου 4) πρέπει να εκφράζεται με αυτόν τον τρόπο. Όσο φθηνότερο είναι να εκφραστεί κάθε λειτουργία, τόσο μικρότερη και ταχύτερη είναι η απόδειξη.
Η σπηλιά χρειαζόταν πολλούς γύρους αλληλεπίδρασης. Αυτό είναι ανέφικτο για ένα blockchain, όπου μια απόδειξη πρέπει να δημοσιεύεται μία φορά και να ελέγχεται από όλους, για πάντα. Δύο αναβαθμίσεις το διορθώνουν.
Μη διαδραστικό (η ιδέα Fiat-Shamir). Αντί για έναν ζωντανό επαληθευτή που φωνάζει τυχαίες προκλήσεις, ο αποδεικνύων παράγει ο ίδιος τις «τυχαίες προκλήσεις» κάνοντας hashing της δικής του μέχρι-τότε απόδειξης. Επειδή ένα καλό hash είναι απρόβλεπτο (Άρθρο 3), ο αποδεικνύων δεν μπορεί να κατασκευάσει τις προκλήσεις προς όφελός του. Η πολυλογάδικη συνομιλία συμπυκνώνεται σε μια ενιαία αυτοτελή απόδειξη που μπορεί να ελέγξει οποιοσδήποτε αργότερα, χωρίς αλληλεπίδραση.
Συνοπτικό. Τα καλύτερα συστήματα κάνουν την απόδειξη μικροσκοπική και γρήγορη στην επαλήθευση, ανεξάρτητα από το πόσο μεγάλη είναι η δήλωση. Αυτό είναι το πραγματικά εκπληκτικό μέρος.
Μια απόδειξη Groth16 (το σύστημα που χρησιμοποιεί το Sapling) είναι περίπου 192 bytes και επαληθεύεται σε χιλιοστά του δευτερολέπτου, είτε η δήλωση που αποδεικνύει είναι μικρή είτε τεράστια. Μερικές εκατοντάδες bytes μπορούν να πιστοποιήσουν έναν υπολογισμό που περιλαμβάνει πολλές χιλιάδες περιορισμούς.
Συνδύασέ τα και παίρνεις το ακρωνύμιο που θα βλέπεις παντού:
zk-SNARK = zero-knowledge Succinct Non-interactive ARgument of Knowledge. Μηδενική γνώση (δεν αποκαλύπτει τίποτα), συνοπτικό (μικροσκοπικό και γρήγορο), μη διαδραστικό (μία φορά), επιχείρημα γνώσης (ο αποδεικνύων πραγματικά γνωρίζει έναν έγκυρο μάρτυρα).
Δεν υπάρχει δωρεάν γεύμα. Πολλά SNARKs χρειάζονται ένα εφάπαξ setup που παράγει δημόσιες παραμέτρους για το κύκλωμα. Το setup παράγει ως παραπροϊόν μυστική τυχαιότητα, και αυτό το μυστικό πρέπει να καταστραφεί. Αν το κρατούσε κάποιος, θα μπορούσε να πλαστογραφήσει αποδείξεις, δηλαδή να πλαστογραφήσει χρήμα (αν και, κρίσιμα, πάλι δεν θα μπορούσε να παραβιάσει την ιδιωτικότητα).
Αυτό το εναπομείναν μυστικό αποκαλείται τοξικά απόβλητα. Για να το απορρίψει με ασφάλεια, το Zcash πραγματοποίησε περίπλοκες τελετές πολλών μερών, στις οποίες πολλοί ανεξάρτητοι συμμετέχοντες συνέβαλαν τυχαιότητα· εφόσον έστω ένας κατέστρεψε ειλικρινά το κομμάτι του, τα τοξικά απόβλητα δεν μπορούν να ανακτηθούν.
Νεότερα συστήματα καταργούν αυτή την απαίτηση εντελώς, γεγονός που είναι ένας από τους σημαντικότερους λόγους για τους οποίους το Zcash εξέλιξε το σύστημα αποδείξεών του με την πάροδο του χρόνου.
| Σχεδιασμός | Σύστημα αποδείξεων | Trusted setup; | Βασίζεται σε |
|---|---|---|---|
| Sprout (πρώιμο) | πρώιμο zk-SNARK | Ναι | αρχική τελετή |
| Sapling | Groth16 | Ναι (η τελετή πολλών μερών «Powers of Tau» + Sapling) | BLS12-381 (Άρθρο 2) |
| Orchard (τρέχον) | Halo 2 | Χωρίς trusted setup | Pallas / Vesta (Άρθρο 2) |
Η πορεία από το Sprout στο Sapling και στο Orchard είναι σε μεγάλο βαθμό μια ιστορία αποδείξεων που γίνονται μικρότερες, ταχύτερες και απαλλάσσονται από το trusted setup. Το Halo 2, που χρησιμοποιείται από το Orchard, δεν χρειάζεται καμία τελετή και είναι σχεδιασμένο να υποστηρίζει αναδρομή (αποδείξεις που επαληθεύουν άλλες αποδείξεις), γι’ αυτό το Orchard χρησιμοποιεί τον κύκλο καμπυλών Pallas/Vesta του Άρθρου 2: κάθε καμπύλη είναι ρυθμισμένη να επαληθεύει αποδείξεις γραμμένες πάνω στην άλλη.
Αυτό κλείνει τον μεγαλύτερο κύκλο από το Άρθρο 0. Η μαγεία «πίσω από την κουρτίνα» είναι ένα zk-SNARK: αποδεικνύει ότι η συναλλαγή σου ικανοποιεί ένα αριθμητικό κύκλωμα που κωδικοποιεί όλους τους κανόνες, χωρίς να αποκαλύπτει τίποτα πέρα από το μοναδικό bit «έγκυρη».
Οι αποδείξεις μηδενικής γνώσης είναι ένα βαθύ πεδίο και μείναμε σκόπιμα στο επίπεδο της διαίσθησης. Δεν ορίσαμε τα ακριβή πιθανοτικά όρια στην ακεραιότητα, την ακριβή μορφή ενός αριθμητικού κυκλώματος (R1CS, PLONKish και ούτω καθεξής), το πώς πολυώνυμα και commitments μετατρέπουν ένα κύκλωμα σε σύντομη απόδειξη ή τα πραγματικά εσωτερικά στοιχεία των Groth16 και Halo 2. Η σπηλιά είναι μια διαδραστική απόδειξη· τα συστήματα παραγωγής είναι μη διαδραστικά και πολύ πιο περίπλοκα. Τίποτα από αυτά δεν αλλάζει τον πυρήνα: αποδεικνύεις ότι ένα κύκλωμα ικανοποιείται από έναν μυστικό μάρτυρα, πλήρως, με ακεραιότητα και χωρίς να αποκαλύπτεις τίποτα. Ο μηχανισμός αποτελεί ολόκληρη σειρά από μόνος του.
| Όρος | Σημασία σε απλά ελληνικά |
|---|---|
| Zero-knowledge proof | Πείσε κάποιον ότι μια δήλωση είναι αληθής χωρίς να αποκαλύψεις τίποτα άλλο |
| Prover / Verifier | Αυτός που δημιουργεί την απόδειξη / αυτός που την ελέγχει |
| Completeness | Οι αληθείς δηλώσεις γίνονται πάντα αποδεκτές (από έναν ειλικρινή αποδεικνύοντα) |
| Soundness | Οι ψευδείς δηλώσεις απορρίπτονται (οι απατεώνες δεν μπορούν να κερδίσουν παρά μόνο από τύχη) |
| Witness | Οι μυστικές είσοδοι που κάνουν τη δήλωση αληθή |
| Arithmetic circuit | Μια δήλωση ξαναγραμμένη ως προσθέσεις και πολλαπλασιασμοί πάνω σε ένα πεπερασμένο πεδίο |
| Non-interactive (Fiat-Shamir) | Μια εφάπαξ απόδειξη που δεν χρειάζεται ζωντανή αλληλεπίδραση |
| Succinct | Η απόδειξη είναι μικροσκοπική και γρήγορη στην επαλήθευση ανεξάρτητα από το μέγεθος της δήλωσης |
| zk-SNARK | Συνοπτικό μη διαδραστικό επιχείρημα γνώσης μηδενικής γνώσης |
Αν η απόδειξη δεν αποκαλύπτει τίποτα, πώς σημαίνει κάτι ο έλεγχός της; Επειδή τα μαθηματικά είναι διαρρυθμισμένα έτσι ώστε μόνο ένας πραγματικός, έγκυρος μάρτυρας να μπορεί να παράγει μια απόδειξη που περνάει. Η επιτυχής επαλήθευση είναι από μόνη της το στοιχείο, χωρίς να απαιτείται αποκάλυψη.
Θα μπορούσε κάποιος να πλαστογραφήσει μια απόδειξη; Η ακεραιότητα το καθιστά ανέφικτο. Η μία εξαίρεση είναι ένα SNARK του οποίου διατηρήθηκαν τα τοξικά απόβλητα του trusted setup· γι’ αυτό ακριβώς έχουν σημασία οι τελετές για την καταστροφή τους.
Ένα παραβιασμένο trusted setup διαρρέει τα ιδιωτικά δεδομένα μου; Όχι. Θα επέτρεπε σε έναν επιτιθέμενο να πλαστογραφήσει νέο χρήμα, αλλά δεν αποκαλύπτει ποσά, διευθύνσεις ή notes. Η ιδιωτικότητα και η ακεραιότητα είναι ξεχωριστές εγγυήσεις.
Γιατί το Zcash άλλαξε συστήματα αποδείξεων με την πάροδο του χρόνου; Για να αποκτήσει μικρότερες, ταχύτερες αποδείξεις και, με το Halo 2, να εξαλείψει εντελώς το trusted setup και να επιτρέψει την αναδρομή.
Στη σπηλιά, γιατί είναι απαραίτητο ο επαληθευτής να επιλέγει την πλευρά εξόδου αφού ο αποδεικνύων έχει ήδη μπει, αντί να την ανακοινώνει εκ των προτέρων; (Απάντηση παρακάτω.)
Αν ο επαληθευτής ανακοίνωνε πρώτα την πλευρά, ένας μπλοφαδόρος που δεν γνωρίζει τη λέξη θα μπορούσε απλώς να περπατήσει από την αρχή προς εκείνη την πλευρά και να βγει χαλαρά, χωρίς να χρειαστεί ποτέ την πόρτα. Η επιλογή αφού ο αποδεικνύων δεσμευτεί σε ένα πέρασμα αναγκάζει έναν μπλοφαδόρο να βασιστεί στην τύχη (50/50 ανά γύρο), κάτι που κάνει τους επαναλαμβανόμενους γύρους πειστικούς. Αυτή η διάταξη «δεσμεύσου πρώτα, έπειτα δέξου την πρόκληση» είναι ακριβώς αυτό που διατηρεί το Fiat-Shamir, παράγοντας την πρόκληση από ένα hash της ήδη δεσμευμένης απόδειξης του αποδεικνύοντα.
Άρθρο 6 . Το θωρακισμένο πρωτόκολλο, από άκρη σε άκρη: το φινάλε. Παίρνουμε κάθε κομμάτι, notes, commitments, το δέντρο commitment note, nullifiers, ισορροπία αξίας και την απόδειξη μηδενικής γνώσης, και συναρμολογούμε μια πλήρη θωρακισμένη συναλλαγή Zcash, κλείνοντας κάθε κύκλο που άνοιξε στο Άρθρο 0.
Μέρος της σειράς Zcash από πρώτες αρχές για ZecHub. Με άδεια CC BY-SA 4.0.
| Trusted setup / toxic waste |
| Εφάπαξ δημιουργία παραμέτρων της οποίας το εναπομείναν μυστικό πρέπει να καταστραφεί |