Κατακερματισμός και commitments: Ο μαγικός σφραγισμένος φάκελος

Πρωτότυπη έρευνα από Annkkitaaa

Πώς να κλειδώσεις ένα μυστικό δημόσια και να μην μπορείς ποτέ να πεις ψέματα γι’ αυτό

Σειρά: Zcash από τις πρώτες αρχές . Άρθρο 3 . Κατακερματισμός και commitments Κοινό: νέοι χρήστες. Βασιζόμαστε στο Άρθρο 1 (πεπερασμένα πεδία) και στο Άρθρο 2 (ελλειπτικές καμπύλες), αλλά η διαίσθηση στέκεται και από μόνη της. Τι θα αποκομίσεις: μια σαφή κατανόηση των συναρτήσεων κατακερματισμού, του τι πραγματικά σημαίνουν τα «απόκρυψη» και «δέσμευση», και του τρόπου με τον οποίο το Zcash δημιουργεί τα commitments των note που θεμελιώνουν κάθε ιδιωτική πληρωμή.

Στο Άρθρο 0 περιγράψαμε έναν «μαγικό σφραγισμένο φάκελο»: κάτι που μπορείς να καρφιτσώσεις σε έναν δημόσιο πίνακα και που αποδεικνύει ότι υπάρχει ένας φάκελος ενώ κρύβει το περιεχόμενό του, και που δεν μπορείς ποτέ να αντικαταστήσεις αργότερα. Υποσχεθήκαμε να εξηγήσουμε πώς είναι δυνατό κάτι τέτοιο. Αυτό είναι το σχετικό άρθρο. Χρειαζόμαστε δύο συστατικά: συναρτήσεις κατακερματισμού και commitments.

1. Γιατί να σε ενδιαφέρει;

Φαντάσου ότι προβλέπεις το αποτέλεσμα μιας εκλογής και θέλεις να αποδείξεις, εκ των υστέρων, ότι το είχες προβλέψει εκ των προτέρων. Δεν μπορείς απλώς να ανακοινώσεις την πρόβλεψή σου (επηρεάζει τους ανθρώπους ή προκαλεί κατηγορίες ότι την άλλαξες). Και δεν μπορείς να την κρατήσεις εντελώς μυστική (τότε δεν μπορείς να αποδείξεις τίποτα αργότερα).

Αυτό που θέλεις είναι ένας τρόπος να κλειδώσεις τώρα μια τιμή, δημόσια, έτσι ώστε:

• κανείς να μην μπορεί να καταλάβει τι κλείδωσες (παραμένει μυστικό προς το παρόν), και
• αργότερα, όταν το αποκαλύψεις, να μην μπορείς να πεις ψέματα για το τι ήταν.

Αυτό το εργαλείο «κλείδωσε τώρα, αποκάλυψε αργότερα, χωρίς ψέματα» ονομάζεται commitment, και βρίσκεται παντού στο Zcash. Η αξία και ο ιδιοκτήτης ενός note κλειδώνονται σε ένα commitment τη στιγμή που δημιουργείται το note. Για να δημιουργήσουμε commitments, χρειαζόμαστε πρώτα το βασικό εργαλείο τους: τη συνάρτηση κατακερματισμού.

2. Η διαίσθηση: Ένα αποτύπωμα για δεδομένα

Μια συνάρτηση κατακερματισμού δέχεται οποιαδήποτε δεδομένα, από ένα μόνο γράμμα έως μια ολόκληρη βιβλιοθήκη, και τα συμπιέζει σε μια σύντομη συμβολοσειρά σταθερού μεγέθους που ονομάζεται digest ή hash. Σκέψου το ως ένα αποτύπωμα για δεδομένα.

Ένα καλό κρυπτογραφικό αποτύπωμα έχει τέσσερις ιδιότητες. Κράτησέ τες ως διαισθήσεις, όχι ως εξισώσεις:

Και μία ακόμη συμπεριφορά που κάνει τα αποτυπώματα να μοιάζουν σχεδόν μαγικά:

Το φαινόμενο χιονοστιβάδας (επαληθευμένο)

Άλλαξε την είσοδο κατά το ελάχιστο και το αποτύπωμα αλλάζει εντελώς, χωρίς καμία ομοιότητα με το παλιό. Εδώ είναι δύο πραγματικά αποτυπώματα SHA-256 από μηνύματα που διαφέρουν κατά έναν μόνο χαρακτήρα:

H("Pay Bob 5 ZEC") = 6e2dc1a954c70cc865f18ea8cb70b7b56eeaf6ca42b380824a55d65dc342f34b
H("Pay Bob 6 ZEC") = 76abc346d8d3053f76a9ae18b617af71f02729a73ec6a51732d2d94934e4217f

Από τα 64 δεκαεξαδικά ψηφία, τα 59 είναι διαφορετικά. Ένας χαρακτήρας στην είσοδο, ένα εντελώς άσχετο αποτύπωμα στην έξοδο. Γι’ αυτό δεν μπορείς να μετακινήσεις σταδιακά μια είσοδο προς ένα αποτύπωμα-στόχο: δεν υπάρχει κανένα σήμα «πιο ζεστό / πιο κρύο» για να ακολουθήσεις.

3. Από το αποτύπωμα στο commitment

Εδώ είναι μια δελεαστική αλλά ελαττωματική ιδέα: για να δεσμευτείς σε μια μυστική τιμή v, απλώς δημοσίευσε το αποτύπωμά της H(v).

Αυτό σε δεσμεύει καλά (δεν μπορείς αργότερα να ισχυριστείς διαφορετικό v, επειδή αυτό θα απαιτούσε σύγκρουση). Όμως αποτυγχάνει να κρύψει. Αν το σύνολο των πιθανών τιμών είναι μικρό, ένας επιτιθέμενος απλώς υπολογίζει το αποτύπωμα κάθε υποψηφίου και συγκρίνει. Δεσμεύεσαι στο «ναι» ή στο «όχι»; Υπολογίζει hash και για τα δύο και μαθαίνει αμέσως ποιο διάλεξες. Ο ντετερμινισμός, φίλος μας πριν από λίγο, τώρα διαρρέει το μυστικό.

Η λύση είναι μία λέξη: τυχαιότητα.

Ένα commitment είναι το αποτύπωμα της τιμής σου αναμεμειγμένο με έναν νέο τυχαίο αριθμό: commitment = H(v, r) όπου το r είναι μια μυστική τυχαία τιμή «τυφλώματος».

Τώρα το ίδιο v δημιουργεί ένα commitment με διαφορετική όψη κάθε φορά, επειδή το r είναι διαφορετικό. Οι δύο ιδιότητες που θέλαμε τελικά ισχύουν και οι δύο:

Για να ανοίξεις (αποκαλύψεις) το commitment αργότερα, δημοσιεύεις τα v και r· οποιοσδήποτε επανυπολογίζει το H(v, r) και ελέγχει ότι ταιριάζει. Έχεις δεσμευτεί. Αυτός είναι ο μαγικός σφραγισμένος φάκελος από το Άρθρο 0, υλοποιημένος.

Δύο συμπεράσματα να θυμάσαι για πάντα: η δέσμευση προέρχεται από την ανθεκτικότητα του hash στις συγκρούσεις· η απόκρυψη προέρχεται από τον τυχαίο παράγοντα τυφλώματος r.

4. Δύο τρόποι να δημιουργήσεις τον φάκελο

Υπάρχουν δύο συνηθισμένες συνταγές, και το Zcash χρησιμοποιεί και τις δύο.

Η τελευταία γραμμή είναι ο λόγος που τα commitments Pedersen έχουν τόσο μεγάλη σημασία στο Zcash. Επειδή το commit(v_1) + commit(v_2) είναι ένα έγκυρο commit(v_1 + v_2), το πρωτόκολλο μπορεί αργότερα να αποδείξει ότι τα χρήματα που εισέρχονται ισούνται με τα χρήματα που εξέρχονται προσθέτοντας commitments μεταξύ τους, χωρίς να αποκαλύπτει ούτε ένα ποσό. Αποθηκεύουμε αυτό το γεγονός για το Άρθρο 6.

5. Μια λεπτομέρεια που διαμορφώνει ολόκληρο το Zcash: Κατακερματισμός φιλικός προς ZK

Ακολουθεί μια διαπίστωση που χάνουν οι περισσότερες εισαγωγές, και είναι ακριβώς το σημείο «τα μαθηματικά συναντούν τη μηχανική» που αξίζει να τονιστεί.

Το SHA-256 είναι ένα εξαιρετικό αποτύπωμα για την καθημερινή πληροφορική. Όμως το Zcash δεν απλώς υπολογίζει hashes· πρέπει να αποδείξει, μέσα σε μια απόδειξη μηδενικής γνώσης, ότι ένα hash υπολογίστηκε σωστά (το Άρθρο 5 εξηγεί το γιατί). Και εδώ είναι η παγίδα: μια απόδειξη μηδενικής γνώσης λειτουργεί στη γλώσσα της αριθμητικής πεπερασμένων πεδίων (Άρθρο 1), ενώ το SHA-256 βασίζεται σε πράξεις χειρισμού bit (μετατοπίσεις, AND, XOR). Η έκφραση όλων αυτών των πράξεων bit σε αριθμητική πεδίων είναι εξαιρετικά δαπανηρή, κάνοντας τις αποδείξεις τεράστιες και αργές.

Έτσι οι κρυπτογράφοι του Zcash σχεδίασαν συναρτήσεις κατακερματισμού των οποίων τα εσωτερικά είναι ήδη αριθμητική πεδίων, καθιστώντας τες οικονομικές στην απόδειξη:

Αυτή η μοναδική τεχνική πίεση, «πρέπει να είναι οικονομικό να αποδειχθεί», είναι ο λόγος που το Zcash εφηύρε και υιοθέτησε ειδικές συναρτήσεις κατακερματισμού αντί να χρησιμοποιεί SHA-256 παντού.

6. Πού βρίσκεται αυτό στο Zcash

Το Zcash έχει χρησιμοποιήσει διαφορετικά hashes στα σχέδιά του, καθένα επιλεγμένο για τη συγκεκριμένη εργασία:

Τα ονόματα που πρέπει να αναγνωρίζεις είναι τα Pedersen και Sinsemilla (hashes τύπου commitment που δημιουργούνται από σημεία καμπύλης, άρα κληρονομούν την υπερδύναμη «προστίθενται» και αποδεικνύονται οικονομικά) και το Poseidon (ένα hash αριθμητικής πεδίων, κατασκευασμένο ειδικά για κυκλώματα μηδενικής γνώσης). Όταν το Άρθρο 0 είπε ότι το περιεχόμενο ενός note σφραγίζεται σε ένα commitment, αυτός είναι ο μηχανισμός που κάνει τη σφράγιση.

Άρα ο ανοιχτός βρόχος από το Άρθρο 0, «πώς μπορεί ένας σφραγισμένος φάκελος να κρύβει το περιεχόμενό του και παρ’ όλα αυτά να είναι αδύνατο να πλαστογραφηθεί;», τώρα κλείνει: απόκρυψη από έναν τυχαίο παράγοντα τυφλώματος, δέσμευση από ανθεκτικότητα σε συγκρούσεις ή από την παγίδα της καμπύλης.

7. Μια ειλικρινής διευκρίνιση

Απλοποιήσαμε για να παραμείνουν τα πράγματα σαφή. Τα πραγματικά σχήματα commitments καθορίζουν ακριβώς τον τρόπο κωδικοποίησης των v και r και τους generators που χρησιμοποιούνται· η «απόκρυψη» και η «δέσμευση» έχουν η καθεμία παραλλαγές (τέλεια έναντι υπολογιστικής) με ακριβείς ορισμούς ασφάλειας· και δεν δείξαμε τα εσωτερικά των Pedersen, Sinsemilla ή Poseidon. Τίποτα από αυτά δεν αλλάζει τη διαίσθηση: ένα commitment είναι ένα αποτύπωμα συν τυχαιότητα που κρύβει τώρα και δεσμεύει για πάντα. Οι λεπτομέρειες επιστρέφουν, επισημασμένες, όταν τις χρειάζεται το άρθρο για το πρωτόκολλο.

8. Σύνοψη

• Μια συνάρτηση κατακερματισμού είναι ένα αποτύπωμα για δεδομένα: ντετερμινιστική, γρήγορη προς τα εμπρός, μονόδρομη, ανθεκτική σε συγκρούσεις, με φαινόμενο χιονοστιβάδας (ένα bit στην είσοδο, ένα εντελώς διαφορετικό αποτύπωμα στην έξοδο).
• Ένα commitment σού επιτρέπει να κλειδώσεις μια τιμή δημόσια τώρα και να την αποκαλύψεις αργότερα χωρίς να μπορείς να πεις ψέματα.
• Η δημοσίευση ενός απλού αποτυπώματος H(v) δεσμεύει, αλλά δεν κρύβει. Η προσθήκη ενός τυχαίου παράγοντα τυφλώματος, H(v, r), το διορθώνει: απόκρυψη από το r, δέσμευση από ανθεκτικότητα σε συγκρούσεις.
• Το Zcash χρησιμοποιεί τόσο commitments βασισμένα σε hash όσο και Pedersen· τα commitments Pedersen επιπλέον προστίθενται, κάτι που το Άρθρο 6 θα αξιοποιήσει για να αποδείξει ιδιωτικά την ισορροπία αξίας.
• Επειδή τα hashes πρέπει να αποδεικνύονται μέσα σε αποδείξεις μηδενικής γνώσης, το Zcash χρησιμοποιεί hashes φιλικά προς ZK που βασίζονται σε αριθμητική πεδίων (Pedersen, Sinsemilla, Poseidon) αντί για SHA-256 παντού.

Γλωσσάρι

Συχνές ερωτήσεις

Γιατί να μην κρυπτογραφήσεις απλώς την τιμή αντί να δεσμευτείς σε αυτήν; Η κρυπτογράφηση αφορά τη μυστικότητα που μπορείς αργότερα να αποκρυπτογραφήσεις. Ένα commitment αφορά τη δέσμευση: την εγγύηση ότι δεν μπορείς να αλλάξεις την απάντησή σου αργότερα. Διαφορετικές εργασίες.

Αν τα commitments κρύβουν την τιμή, πώς ελέγχει κάποιος τους κανόνες; Αυτός είναι ο ρόλος των αποδείξεων μηδενικής γνώσης (Άρθρο 5): αποδεικνύουν ότι η κρυφή τιμή υπακούει στους κανόνες χωρίς να την αποκαλύπτουν.

Έχει παραβιαστεί το SHA-256, αφού το Zcash το αποφεύγει σε ορισμένα σημεία; Όχι. Το SHA-256 είναι αξιόπιστο και το Zcash εξακολουθεί να το χρησιμοποιεί. Απλώς είναι δαπανηρό να αποδειχθεί μέσα σε ένα κύκλωμα, γι’ αυτό υπάρχουν hashes φιλικά προς ZK για αυτή τη συγκεκριμένη εργασία.

Από πού προέρχεται το τυχαίο r και ποιος το διατηρεί; Παράγεται εκ νέου όταν δημιουργείται το note και είναι γνωστό στον ιδιοκτήτη του note. Είναι μέρος αυτού που κάνει κάθε note μοναδικό και ιδιωτικό.

Δοκίμασε τη διαίσθησή σου

Δεσμεύεσαι στην εκλογική πρόβλεψή σου ως H(v, r) και τη δημοσιεύεις. Ένας φίλος επιμένει ότι πρέπει να δημοσιεύσεις μόνο το H(v) για να παραμείνει απλούστερο. Σε μία πρόταση, γιατί είναι κακή ιδέα αν υπάρχουν μόνο δύο πιθανά αποτελέσματα; (Απάντηση παρακάτω.)

Τι ακολουθεί

Άρθρο 4 . Δέντρα Merkle: τώρα έχουμε εκατομμύρια commitments να συσσωρεύονται. Το Άρθρο 4 δείχνει πώς το Zcash τα οργανώνει σε ένα μόνο δέντρο, του οποίου το μικρό αποτύπωμα ρίζας αντιπροσωπεύει ολόκληρο το ιστορικό, και πώς μπορείς να αποδείξεις ότι το note σου βρίσκεται σε αυτό το δέντρο χωρίς να αποκαλύψεις ποιο είναι. Αυτή είναι η πραγματική μορφή του «δημόσιου πίνακα» του Άρθρου 0.

Μέρος της σειράς Zcash από τις πρώτες αρχές για το ZecHub. Άδεια CC BY-SA 4.0.