Ελλειπτικές καμπύλες: Εκεί όπου γεννιούνται τα κλειδιά και τα commitments του Zcash

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

Ένας μονόδρομος χτισμένος από σημεία σε μια καμπύλη

Σειρά: Zcash από τις πρώτες αρχές . Άρθρο 2 . Ελλειπτικές καμπύλες Κοινό: Νέοι χρήστες. Υποθέτουμε μόνο το Άρθρο 1 (πεπερασμένα πεδία): αριθμητική που επαναλαμβάνεται modulo ενός πρώτου αριθμού. Δεν χρειάζεται κανένα άλλο υπόβαθρο. Τι θα αποκομίσεις: Μια διαισθητική και σωστή εικόνα των ελλειπτικών καμπυλών, της «κρυφής πόρτας» που τις κάνει χρήσιμες, και ακριβώς πώς το Zcash τις μετατρέπει σε κλειδιά και commitments.

Το Άρθρο 1 μάς έδωσε ένα τέλειο πεδίο για αριθμητική: το πεπερασμένο πεδίο. Όμως ένα πεδίο από μόνο του είναι απλώς αριθμοί. Για να δημιουργήσει κλειδιά και τους «σφραγισμένους φακέλους» από το Άρθρο 0, το Zcash χρειάζεται ένα αντικείμενο με ένα ειδικό, μονοκατευθυντικό είδος δυσκολίας: εύκολο να υπολογιστεί προς τα εμπρός, πρακτικά αδύνατο να αντιστραφεί. Αυτό το αντικείμενο είναι μια ελλειπτική καμπύλη. Αυτό το άρθρο τη χτίζει από την αρχή, με τη διαίσθηση πριν από την άλγεβρα.

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

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

Να γιατί. Το μυστικό κλειδί σου είναι ένας αριθμός που κρατάς κρυφό. Το δημόσιο κλειδί σου (και η διεύθυνσή σου) παράγεται από αυτό και εμφανίζεται στον κόσμο. Ολόκληρη η ασφάλεια του συστήματος βασίζεται σε ένα γεγονός: δεδομένου του δημόσιου κλειδιού, κανείς δεν μπορεί να εργαστεί προς τα πίσω για να βρει το μυστικό κλειδί σου. Αν μπορούσε, θα μπορούσε να ξοδέψει τα χρήματά σου.

Άρα χρειαζόμαστε μια μαθηματική πράξη όπου:

• Η μετάβαση προς τα εμπρός (μυστικό -> δημόσιο) είναι γρήγορη και εύκολη, αλλά
• Η μετάβαση προς τα πίσω (δημόσιο -> μυστικό) είναι τόσο δύσκολη ώστε όλοι οι υπολογιστές στη Γη, εργαζόμενοι για τη διάρκεια ζωής του σύμπαντος, δεν θα την ολοκλήρωναν.

Ο απλός πολλαπλασιασμός σε πεπερασμένο πεδίο δεν αρκεί· η διαίρεση τον αναιρεί αμέσως (αυτός ήταν ολόκληρος ο σκοπός του Άρθρου 1). Χρειαζόμαστε κάτι χωρίς εύκολο κουμπί «αναίρεσης». Οι ελλειπτικές καμπύλες παρέχουν ακριβώς αυτό και, ως επιπλέον πλεονέκτημα, τα σημεία τους συνδυάζονται με τρόπο ιδανικό για την κατασκευή commitments. Ας δούμε πώς.

2. Η διαίσθηση: μια καμπύλη της οποίας τα σημεία μπορείς να «προσθέσεις»

Ξέχασε την κρυπτογραφία για μια στιγμή. Μια ελλειπτική καμπύλη είναι απλώς το σύνολο των σημείων (x, y) που ικανοποιούν μια εξίσωση της μορφής:

y^2 = x^3 + ax + b

Πάνω στους συνηθισμένους αριθμούς μοιάζει με μια ομαλή, κυματιστή καμπύλη, συχνά με έναν στρογγυλεμένο βρόχο και δύο ουρές:

Το πραγματικά εκπληκτικό μέρος: μπορείς να «προσθέσεις» δύο σημεία σε αυτή την καμπύλη ώστε να πάρεις ένα τρίτο σημείο στην ίδια καμπύλη. Δεν πρόκειται για συνηθισμένη πρόσθεση συντεταγμένων. Είναι ένας γεωμετρικός κανόνας και είναι ευκολότερο να τον δεις παρά να τον περιγράψεις.

Ο κανόνας της χορδής (πρόσθεση δύο διαφορετικών σημείων)

Για να προσθέσεις P + Q:

1. Σχεδίασε μια ευθεία γραμμή που περνά από τα P και Q.
2. Αυτή η γραμμή τέμνει την καμπύλη σε ακριβώς ένα ακόμη σημείο. Ονόμασέ το R*.
3. Ανάκλασε το R* ως προς τον οριζόντιο άξονα. Αυτή η ανάκλαση είναι η απάντηση, το P + Q.

Ο κανόνας της εφαπτομένης (πρόσθεση ενός σημείου με τον εαυτό του)

Για να υπολογίσεις το P + P (γράφεται 2P), δεν υπάρχει δεύτερο σημείο από το οποίο να περάσεις μια γραμμή, οπότε χρησιμοποιείς αντί γι’ αυτό την εφαπτομένη γραμμή στο P και έπειτα ακολουθείς την ίδια διαδικασία «τρίτη τομή, κατόπιν ανάκλαση».

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

Το σημείο στο άπειρο (το μηδέν της καμπύλης)

Κάθε αριθμητικό σύστημα χρειάζεται ένα 0, το στοιχείο που δεν αλλάζει τίποτα όταν το προσθέτεις. Σε μια ελλειπτική καμπύλη, αυτόν τον ρόλο παίζει ένα ειδικό πρόσθετο σημείο που ονομάζεται σημείο στο άπειρο, γραμμένο ως O. Μπορείς να το φανταστείς ως «απείρως ψηλά», το μέρος όπου συναντιούνται οι κατακόρυφες γραμμές. Η πρόσθεση του O σε οποιοδήποτε σημείο το αφήνει αμετάβλητο, ακριβώς όπως η πρόσθεση του 0.

3. Από τις εικόνες σε ένα πεπερασμένο πεδίο

Η ομαλή καμπύλη παραπάνω είναι η διαίσθηση. Όμως το Zcash δεν χρησιμοποιεί πραγματικούς αριθμούς (στρογγυλοποιούνται και αποκαλύπτουν μέγεθος, όπως είδαμε στο Άρθρο 1). Χρησιμοποιεί μια ελλειπτική καμπύλη πάνω σε ένα πεπερασμένο πεδίο: την ίδια εξίσωση y^2 = x^3 + ax + b, αλλά με όλη την αριθμητική να εκτελείται modulo ενός πρώτου αριθμού.

Όταν το κάνεις αυτό, η όμορφη καμπύλη διαλύεται σε μια διασπορά ασύνδετων κουκκίδων, μία κουκκίδα για κάθε ζεύγος (x, y) που ικανοποιεί την εξίσωση modulo p. Παύει να μοιάζει με καμπύλη. Όμως εδώ βρίσκεται το κρίσιμο σημείο:

Η άλγεβρα του κανόνα χορδής-και-εφαπτομένης εξακολουθεί να λειτουργεί τέλεια. Οι ίδιοι τύποι που έβρισκαν το P + Q γεωμετρικά, τώρα το υπολογίζουν με αριθμητική πεπερασμένου πεδίου. Οι κουκκίδες εξακολουθούν να σχηματίζουν μια ομάδα, με το ίδιο 0 (το σημείο στο άπειρο).

Ας το κάνουμε πραγματικό με ένα μικροσκοπικό, πλήρως επαληθευμένο παράδειγμα.

Μια πλήρης καμπύλη, υπολογισμένη ακριβώς

Πάρε το y^2 = x^3 + 2x + 2 πάνω στο πεπερασμένο πεδίο F_17. Ο υπολογισμός κάθε έγκυρου σημείου δίνει ακριβώς 18 σημεία, συν το σημείο στο άπειρο = 19 συνολικά. Μερικά από αυτά:

(0,6) (0,11) (3,1) (3,16) (5,1) (5,16) (6,3) (6,14) (7,6) (7,11) ...

Τώρα επίλεξε το σημείο G = (5, 1) και συνέχισε να το προσθέτεις στον εαυτό του. Δες τι συμβαίνει (κάθε γραμμή παρακάτω υπολογίστηκε, δεν εικάστηκε):

Δύο πράγματα που πρέπει να προσέξεις:

• Επισκέπτεται και τα 18 πεπερασμένα σημεία και έπειτα καταλήγει στο O στο βήμα 19, και μετά θα επαναλαμβανόταν για πάντα. Το αρχικό σημείο G «παράγει» ολόκληρη την ομάδα, γι’ αυτό το αποκαλούμε γεννήτορα.
• Είναι μια επαληθευμένη ομάδα: για παράδειγμα 1G + 2G = (5,1) + (6,3) = (10,6), το οποίο είναι ακριβώς 3G. Η πρόσθεση είναι εσωτερικά συνεπής, όπως ακριβώς απαιτεί μια ομάδα.

4. Η κρυφή πόρτα: βαθμωτός πολλαπλασιασμός

Αυτός ο πίνακας του 1G, 2G, 3G, ... είναι η καρδιά των πάντων. Η επανειλημμένη πρόσθεση ενός σημείου στον εαυτό του ονομάζεται βαθμωτός πολλαπλασιασμός: το σημείο kG σημαίνει «το G προστιθέμενο στον εαυτό του k φορές».

Τώρα η μαγεία. Εξέτασε τις δύο κατευθύνσεις:

Αυτή η ασυμμετρία είναι ο μονόδρομος που χρειαζόμασταν στην Ενότητα 1. Το πρόβλημα προς τα πίσω («ποιο k παρήγαγε αυτό το σημείο;») ονομάζεται πρόβλημα διακριτού λογαρίθμου ελλειπτικής καμπύλης (ECDLP) και, στις καμπύλες που χρησιμοποιεί το Zcash, καμία γνωστή μέθοδος δεν το λύνει πριν από τον θερμικό θάνατο του σύμπαντος.

Στη δική μας καμπύλη-παιχνίδι F_17 θα μπορούσες απλώς να διαβάσεις το k από τον πίνακα, επειδή έχει μόλις 19 σημεία. Οι πραγματικές καμπύλες έχουν περίπου 2^(255) σημεία. Ο πίνακας θα είχε περισσότερες γραμμές από τα άτομα στο σύμπαν, επομένως το «να το διαβάσεις από τον πίνακα» δεν είναι επιλογή. Το μικρό μέγεθος είναι αυτό που κάνει την καμπύλη-παιχνίδι διδακτική και επίσης ο λόγος που δεν είναι ασφαλής.

5. Πώς γεννιούνται τα κλειδιά (η ανταμοιβή)

Τώρα έχουμε όσα χρειάζονται για να εξηγήσουμε ένα πραγματικό κρυπτογραφικό κλειδί, και είναι εκπληκτικά απλό:

Επίλεξε έναν μυστικό αριθμό k. Δημοσίευσε το σημείο kG. Αυτό ήταν όλο. Το k είναι το ιδιωτικό κλειδί σου. Το kG είναι το δημόσιο κλειδί σου. Ο μονόδρομος (ECDLP) εγγυάται ότι κανείς δεν μπορεί να αντιστρέψει το kG για να βρει το k.

Αυτή η μοναδική ιδέα, ένα δημόσιο κλειδί είναι ένας μυστικός βαθμωτός αριθμός επί έναν σταθερό γεννήτορα, είναι ο σπόρος των spending keys, των viewing keys και των διευθύνσεων του Zcash. Το πλήρες δέντρο κλειδιών προσθέτει περισσότερη δομή από πάνω, όμως κάθε κλάδος αναπτύσσεται από αυτή τη ρίζα.

Επιπλέον: γιατί τα σημεία καμπύλης δημιουργούν τέλεια commitments

Θυμήσου τον «σφραγισμένο φάκελο» (commitment) από το Άρθρο 0, που έπρεπε να κρύβει το περιεχόμενό του αλλά να είναι αδύνατο να πλαστογραφηθεί. Οι ελλειπτικές καμπύλες μάς προσφέρουν έναν καθαρό τρόπο να τον δημιουργήσουμε. Πάρε δύο σταθερά, δημόσια σημεία γεννήτορες G και H, μια μυστική τιμή v και έναν τυχαίο αριθμό απόκρυψης r, και σχημάτισε:

Commitment  =  v.G  +  r.H

Αυτό είναι ένα Pedersen commitment και έχει και τις δύο ιδιότητες που θέλαμε:

• Απόκρυψη: Το τυχαίο r διασκορπίζει το αποτέλεσμα σε ολόκληρη την καμπύλη, επομένως το σημείο δεν αποκαλύπτει τίποτα για το v.
• Δεσμευτικότητα: Το ECDLP καθιστά ανέφικτο να βρεις ένα διαφορετικό (v, r) που δίνει το ίδιο σημείο, επομένως δεν μπορείς να αλλάξεις γνώμη για όσα έχεις δεσμεύσει.

Μια επιπλέον ιδιότητα αποδεικνύεται ανεκτίμητη αργότερα: αυτά τα commitments αθροίζονται. Το commitment για το v_1 συν το commitment για το v_2 είναι ένα έγκυρο commitment για το v_1 + v_2. Αυτή η «ομομορφική» συμπεριφορά είναι ο τρόπος με τον οποίο το Zcash θα αποδείξει αργότερα ότι τα χρήματα που εισέρχονται σε μια συναλλαγή ισούνται με τα χρήματα που εξέρχονται, χωρίς να αποκαλύπτει κανένα ποσό. Θα αξιοποιήσουμε αυτό το πλεονέκτημα περίπου στο Άρθρο 6.

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

Τα ίχνη είναι συγκεκριμένα και επαληθεύσιμα.

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

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

Μερικές απλοποιήσεις διατήρησαν το κείμενο ευανάγνωστο. Χρησιμοποιήσαμε τη μορφή σύντομης Weierstrass (y^2 = x^3 + ax + b)· οι καμπύλες του Zcash συχνά γράφονται σε άλλες ισοδύναμες μορφές (η Jubjub είναι μια καμπύλη twisted Edwards) που επιλέγονται για αποδοτικότητα και ασφάλεια, αλλά η ιδέα της ομάδας είναι πανομοιότυπη. Δεν ορίσαμε τους ακριβείς τύπους πρόσθεσης σημείων (είναι η αλγεβρική εκδοχή του «τρίτη τομή, κατόπιν ανάκλαση») και αφήσαμε στην άκρη λεπτομέρειες όπως η τάξη της καμπύλης, οι cofactors και τα «pairings», που γίνονται σημαντικά στα άρθρα για τα συστήματα αποδείξεων. Τίποτα από αυτά δεν αλλάζει τη διαίσθηση· την οξύνει.

8. Σύνοψη

• Ένα σύστημα ιδιωτικότητας χρειάζεται έναν μονόδρομο: εύκολο προς τα εμπρός, ανέφικτο προς τα πίσω. Οι ελλειπτικές καμπύλες προσφέρουν έναν τέτοιο.
• Μια ελλειπτική καμπύλη είναι το σύνολο σημείων που ικανοποιούν το y^2 = x^3 + ax + b και τα σημεία της μπορούν να προστεθούν μέσω του γεωμετρικού κανόνα χορδής-και-εφαπτομένης, με ένα ειδικό σημείο στο άπειρο να ενεργεί ως μηδέν.
• Πάνω σε ένα πεπερασμένο πεδίο, η καμπύλη γίνεται διασπορά κουκκίδων, αλλά η ίδια πρόσθεση εξακολουθεί να λειτουργεί και τα σημεία σχηματίζουν μια ομάδα. (Επαληθευμένο παράδειγμα: το y^2 = x^3 + 2x + 2 πάνω στο F_17 έχει 19 σημεία και το G = (5,1) τα παράγει όλα.)
• Ο βαθμωτός πολλαπλασιασμός kG είναι εύκολο να υπολογιστεί αλλά ανέφικτο να αντιστραφεί: το ECDLP. Αυτή είναι η κρυφή πόρτα.
• Κλειδιά: Ιδιωτικό κλειδί k, δημόσιο κλειδί kG. Commitments: Η μορφή Pedersen v.G + r.H, η οποία κρύβει, δεσμεύει και βολικά αθροίζεται.
• Στο Zcash, το Sapling χρησιμοποιεί BLS12-381 + Jubjub και το Orchard χρησιμοποιεί τις καμπύλες Pallas/Vesta (Pasta)· κάθε κλειδί και commitment βρίσκεται πάνω σε αυτές.

Γλωσσάρι

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

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

Έχει αποδειχθεί ότι το ECDLP είναι δύσκολο; Δεν έχει αποδειχθεί αδύνατο, αλλά δεκαετίες έντονης προσπάθειας δεν έχουν βρει καμία αποδοτική επίθεση σε καμπύλες που έχουν επιλεγεί σωστά. Η ασφάλεια βασίζεται σε αυτή την καλά δοκιμασμένη υπόθεση.

Θα μπορούσε ένας κβαντικός υπολογιστής να το παραβιάσει; Ένας αρκετά μεγάλος κβαντικός υπολογιστής θα μπορούσε να παραβιάσει το ECDLP. Αυτό είναι μια γνωστή μακροπρόθεσμη ανησυχία σε ολόκληρο τον κλάδο και ένας ενεργός τομέας έρευνας· οι σημερινές καμπύλες παραμένουν ασφαλείς απέναντι στους κλασικούς υπολογιστές.

Γιατί το Zcash χρησιμοποιεί περισσότερες από μία καμπύλες; Διαφορετικές εργασίες. Μία καμπύλη υποστηρίζει το σύστημα αποδείξεων μηδενικής γνώσης· μια άλλη (ενσωματωμένη στο πεδίο της πρώτης) καθιστά αποδοτικές τις πράξεις κλειδιών και commitments μέσα στην απόδειξη. Τα επόμενα άρθρα εξηγούν γιατί αυτή η σύζευξη έχει σημασία.

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

Χρησιμοποιώντας τον επαληθευμένο πίνακα στην Ενότητα 3, ποιο είναι το 9G + 10G στην καμπύλη-παιχνίδι μας; Και τι σου λέει η απάντηση για το G; (Απάντηση παρακάτω.)

Τι ακολουθεί

Άρθρο 3 . Hashing και commitments: Θα ανοίξουμε σωστά τον «μαγικό σφραγισμένο φάκελο». Τώρα έχεις δει έναν τρόπο δημιουργίας ενός commitment από σημεία καμπύλης· στη συνέχεια εξετάζουμε τι πραγματικά σημαίνουν η απόκρυψη και η δεσμευτικότητα, γνωρίζουμε τις συναρτήσεις hash και συνδέουμε και τα δύο με τα note commitments που θεμελιώνουν κάθε πληρωμή του Zcash.

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