Είναι δυνατόν να δημιουργήσουμε τυχαίους αριθμούς εάν δεν εμπιστευόμαστε ο ένας τον άλλον; Μέρος 2ο

Γεια σου Χαμπρ!

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

Σε αυτό το μέρος του άρθρου, θα ρίξουμε μια πιο προσεκτική ματιά σε μια άλλη προσέγγιση που χρησιμοποιεί υπογραφές κατωφλίου.

Λίγη κρυπτογραφία

Για να κατανοήσετε πώς λειτουργούν οι υπογραφές κατωφλίου, πρέπει να κατανοήσετε μια μικρή βασική κρυπτογραφία. Θα χρησιμοποιήσουμε δύο έννοιες: βαθμωτές ή απλά αριθμούς, τις οποίες θα υποδηλώσουμε με πεζά γράμματα (x, y) και σημεία στην ελλειπτική καμπύλη, τα οποία θα συμβολίσουμε με κεφαλαία γράμματα.

Για να κατανοήσετε τα βασικά των υπογραφών κατωφλίου, δεν χρειάζεται να κατανοήσετε πώς λειτουργούν οι ελλειπτικές καμπύλες, εκτός από μερικά βασικά πράγματα:

1. Τα σημεία σε μια ελλειπτική καμπύλη μπορούν να προστεθούν και να πολλαπλασιαστούν με ένα βαθμωτό (θα υποδηλώσουμε τον πολλαπλασιασμό με ένα βαθμωτό ως xG, αν και η σημειογραφία Gx χρησιμοποιείται επίσης συχνά στη βιβλιογραφία). Το αποτέλεσμα της πρόσθεσης και του πολλαπλασιασμού με ένα βαθμωτό είναι ένα σημείο σε μια ελλειπτική καμπύλη.

2. Γνωρίζοντας μόνο την ουσία G και το προϊόν του με βαθμωτό xG δεν μπορεί να υπολογιστεί x.

Θα χρησιμοποιήσουμε επίσης την έννοια του πολυωνύμου p(x) βαθμό k-1. Συγκεκριμένα, θα χρησιμοποιήσουμε την ακόλουθη ιδιότητα των πολυωνύμων: αν γνωρίζουμε την τιμή p(x) για κάθε k διαφορετικός x (και δεν έχουμε περισσότερες πληροφορίες p(x)), μπορούμε να υπολογίσουμε p(x) για οποιονδήποτε άλλον x.

Είναι ενδιαφέρον ότι για οποιοδήποτε πολυώνυμο p(x) και κάποιο σημείο στην καμπύλη Gγνωρίζοντας το νόημα p(x)G για κάθε k διαφορετικές έννοιες x, μπορούμε επίσης να υπολογίσουμε p(x)G για κάθε x.

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

Γεννήτρια τυχαίων αριθμών στις υπογραφές κατωφλίου

Ας πούμε ότι n Οι συμμετέχοντες θέλουν να δημιουργήσουν έναν τυχαίο αριθμό και θέλουμε να συμμετάσχει οποιοσδήποτε k υπήρχαν αρκετά από αυτά για να δημιουργήσουν έναν αριθμό, αλλά έτσι ώστε οι επιτιθέμενοι που ελέγχουν k-1 ή λιγότεροι συμμετέχοντες δεν μπορούσαν να προβλέψουν ή να επηρεάσουν τον αριθμό που δημιουργήθηκε.

Ας υποθέσουμε ότι υπάρχει ένα τέτοιο πολυώνυμο p(x) βαθμό k-1 τι γνωρίζει ο πρώτος συμμετέχων p (1), ο δεύτερος ξέρει p(2), και ούτω καθεξής (n-ο ξέρει p(n)). Υποθέτουμε επίσης ότι για κάποιο προκαθορισμένο σημείο G όλοι γνωρίζουν p(x)G για όλες τις αξίες x. θα καλέσουμε πι) "ιδιωτικό στοιχείο" iο συμμετέχων (γιατί μόνο iο ος συμμετέχων τη γνωρίζει), και Χοίρος «δημόσιο στοιχείο» i-ος συμμετέχων (γιατί όλοι οι συμμετέχοντες τη γνωρίζουν). Όπως θυμάστε, γνώση Χοίρος δεν αρκεί για την αποκατάσταση πι).

Δημιουργώντας ένα τέτοιο πολυώνυμο έτσι ώστε μόνο i-Ο τρίτος συμμετέχων και κανείς άλλος δεν γνώριζε το ιδιωτικό του στοιχείο - αυτό είναι το πιο περίπλοκο και ενδιαφέρον μέρος του πρωτοκόλλου και θα το αναλύσουμε παρακάτω. Προς το παρόν, ας υποθέσουμε ότι έχουμε ένα τέτοιο πολυώνυμο και όλοι οι συμμετέχοντες γνωρίζουν τα ιδιωτικά στοιχεία τους.

Πώς μπορούμε να χρησιμοποιήσουμε ένα τέτοιο πολυώνυμο για να δημιουργήσουμε έναν τυχαίο αριθμό; Αρχικά, χρειαζόμαστε κάποια συμβολοσειρά που δεν έχει χρησιμοποιηθεί προηγουμένως ως είσοδος στη γεννήτρια. Στην περίπτωση blockchain, ο κατακερματισμός του τελευταίου μπλοκ h είναι καλός υποψήφιος για μια τέτοια γραμμή. Αφήστε τους συμμετέχοντες να θέλουν να δημιουργήσουν έναν τυχαίο αριθμό χρησιμοποιώντας h σαν σπόρος. Οι συμμετέχοντες μετατρέπονται πρώτοι h σε ένα σημείο της καμπύλης χρησιμοποιώντας οποιαδήποτε προκαθορισμένη συνάρτηση:

H = scalarToPoint(h)

Στη συνέχεια, κάθε συμμετέχων i υπολογίζει και δημοσιεύει Γεια = p(i)H, τι μπορούν να κάνουν γιατί ξέρουν p(i) και H. Αποκάλυψη HΔεν επιτρέπω σε άλλους συμμετέχοντες να επαναφέρουν το ιδιωτικό στοιχείο iο συμμετέχων, και επομένως ένα σύνολο ιδιωτικών στοιχείων μπορεί να χρησιμοποιηθεί από μπλοκ σε μπλοκ. Έτσι, ο ακριβός αλγόριθμος παραγωγής πολυωνύμων που περιγράφεται παρακάτω χρειάζεται να εκτελεστεί μόνο μία φορά.

Όταν k οι συμμετέχοντες υποβλήθηκαν σε αυτοψία Γεια = p(i)H, ο καθένας μπορεί να υπολογίσει Hx = p(x)H για όλα x χάρη στην ιδιότητα των πολυωνύμων που συζητήσαμε στην τελευταία ενότητα. Αυτή τη στιγμή όλοι οι συμμετέχοντες υπολογίζουν H0 = p(0)H, και αυτός είναι ο τυχαίος αριθμός που προκύπτει. Σημειώστε ότι κανείς δεν γνωρίζει p(0), και επομένως ο μόνος τρόπος υπολογισμού p(0)H - αυτό είναι παρεμβολή p(x)H, που είναι δυνατό μόνο όταν k αξίες p(i)H γνωστός. Ανοίγοντας οποιαδήποτε μικρότερη ποσότητα p(i)H δεν παρέχει καμία πληροφορία για ρ(0)Η.

Η παραπάνω γεννήτρια έχει όλες τις ιδιότητες που θέλουμε: μόνο οι εισβολείς ελέγχουν k-1 συμμετέχοντες ή λιγότεροι δεν έχουν πληροφορίες ή επιρροή στο συμπέρασμα, ενώ κανένας k Οι συμμετέχοντες μπορούν να υπολογίσουν τον αριθμό που προκύπτει και οποιοδήποτε υποσύνολο του k Οι συμμετέχοντες θα καταλήγουν πάντα στο ίδιο αποτέλεσμα για τον ίδιο σπόρο.

Υπάρχει ένα πρόβλημα που αποφύγαμε προσεκτικά παραπάνω. Για να λειτουργήσει η παρεμβολή, είναι σημαντικό η τιμή Hi που δημοσιεύτηκε από κάθε συμμετέχοντα i ήταν πραγματικά το ίδιο p(i)H. Αφού κανείς εκτός i-ο συμμετέχων δεν γνωρίζει πι), κανένας εκτός i-Ο συμμετέχων δεν μπορεί να το επαληθεύσει Hi πραγματικά υπολογίζεται σωστά και χωρίς κρυπτογραφική απόδειξη ορθότητας Hεγώ ένας εισβολέας μπορεί να δημοσιεύσει οποιαδήποτε τιμή ως Γεια σας, και επηρεάζουν αυθαίρετα την έξοδο της γεννήτριας τυχαίων αριθμών:

Διαφορετικές τιμές του H_1 που αποστέλλονται από τον πρώτο συμμετέχοντα οδηγούν σε διαφορετικά προκύπτοντα H_0

Υπάρχουν τουλάχιστον δύο τρόποι για να αποδειχθεί η ορθότητα Hi, θα τα εξετάσουμε αφού αναλύσουμε τη δημιουργία του πολυωνύμου.

Πολυωνυμική γενιά

Στην τελευταία ενότητα υποθέσαμε ότι έχουμε ένα τέτοιο πολυώνυμο p(x) βαθμό k-1 ότι ο συμμετέχων i ξέρει πι), και κανείς άλλος δεν έχει πληροφορίες σχετικά με αυτήν την τιμή. Στην επόμενη ενότητα θα το χρειαστούμε επίσης για κάποιο προκαθορισμένο σημείο G όλοι ήξεραν p(x)G για όλα x.

Σε αυτή την ενότητα θα υποθέσουμε ότι κάθε συμμετέχων τοπικά έχει κάποιο ιδιωτικό κλειδί xi, έτσι ώστε όλοι να γνωρίζουν το αντίστοιχο δημόσιο κλειδί Xi.

Ένα πιθανό πρωτόκολλο δημιουργίας πολυωνύμων είναι το εξής:

1. Κάθε συμμετέχων i δημιουργεί τοπικά ένα αυθαίρετο πολυώνυμο pi(x) βαθμός k-1. Στη συνέχεια στέλνουν κάθε συμμετέχοντα j αξία pi(j), κρυπτογραφημένο με δημόσιο κλειδί Xj. Έτσι μόνο i-th и j-th ο συμμετέχων γνωρίζει pi(j). Συμμέτοχος i ανακοινώνει επίσης δημόσια pi(j)G για όλα j από 1 να k περιεκτικός.

2. Όλοι οι συμμετέχοντες χρησιμοποιούν κάποια συναίνεση για να επιλέξουν k συμμετέχοντες των οποίων τα πολυώνυμα θα χρησιμοποιηθούν. Δεδομένου ότι ορισμένοι συμμετέχοντες ενδέχεται να είναι εκτός σύνδεσης, δεν μπορούμε να περιμένουμε έως ότου όλοι n οι συμμετέχοντες θα δημοσιεύσουν πολυώνυμα. Το αποτέλεσμα αυτού του βήματος είναι ένα σύνολο Z που αποτελείται από τουλάχιστον k πολυώνυμα που δημιουργήθηκαν στο βήμα (1).

3. Οι συμμετέχοντες φροντίζουν για τις αξίες που γνωρίζουν pi(ι) αντιστοιχεί σε δημοσίως ανακοινωθεί pi(j)G. Μετά από αυτό το βήμα Z μόνο πολυώνυμα για τα οποία μεταδίδεται ιδιωτικά pi(ι) αντιστοιχεί σε δημοσίως ανακοινωθεί pi(j)G.

4. Κάθε συμμετέχων j υπολογίζει το ιδιωτικό του στοιχείο p(j) ως άθροισμα pi(ι) για όλους i в Z. Κάθε συμμετέχων υπολογίζει επίσης όλες τις τιμές p(x)G ως άθροισμα pi(x)G για όλα τα i в Z.

Σημειώστε ότι p(x) - είναι πραγματικά ένα πολυώνυμο k-1, γιατί είναι το άθροισμα του ατόμου pi(x), καθένα από τα οποία είναι ένα πολυώνυμο βαθμού k-1. Στη συνέχεια, σημειώστε ότι ενώ κάθε συμμετέχων j ξέρει p(j), δεν έχουν πληροφορίες για p(x) για x ≠ j. Πράγματι, για να υπολογίσουν αυτή την τιμή, πρέπει να γνωρίζουν τα πάντα αρτοφόριο), και εφόσον ο συμμετέχων j δεν γνωρίζει τουλάχιστον ένα από τα επιλεγμένα πολυώνυμα, δεν έχει επαρκείς πληροφορίες για p(x).

Αυτή είναι η όλη διαδικασία δημιουργίας πολυωνύμων που χρειαζόταν στην τελευταία ενότητα. Τα βήματα 1, 2 και 4 παραπάνω έχουν μια αρκετά προφανή εφαρμογή. Αλλά το βήμα 3 δεν είναι τόσο ασήμαντο.

Συγκεκριμένα, πρέπει να είμαστε σε θέση να αποδείξουμε ότι είναι κρυπτογραφημένο pi(ι) αντιστοιχούν πραγματικά στα δημοσιευμένα pi(j)G. Αν δεν μπορούμε να το αποδείξουμε, ο επιθετικός i μπορεί να στείλει σκουπίδια pi(ι) στον συμμετέχοντα j, και συμμετέχων j δεν θα μπορέσει να πάρει την πραγματική αξία pi(j), και δεν θα μπορεί να υπολογίσει το ιδιωτικό του στοιχείο.

Υπάρχει ένα κρυπτογραφικό πρωτόκολλο που σας επιτρέπει να δημιουργήσετε ένα πρόσθετο μήνυμα απόδειξηi(j), έτσι ώστε οποιοσδήποτε συμμετέχων, να έχει κάποια αξία e, καθώς proofi(j) и pi(j)G, μπορεί να το επαληθεύσει τοπικά e - είναι αλήθεια pi(j), κρυπτογραφημένο με το κλειδί του συμμετέχοντα j. Δυστυχώς, το μέγεθος τέτοιων στοιχείων είναι απίστευτα μεγάλο και δεδομένου ότι είναι απαραίτητο να δημοσιευθούν O(nk) Τέτοια στοιχεία δεν μπορούν να χρησιμοποιηθούν για το σκοπό αυτό.

Αντί να το αποδείξει pi(j) αντιστοιχεί pi(j)G μπορούμε να διαθέσουμε ένα πολύ μεγάλο χρονικό διάστημα στο πρωτόκολλο δημιουργίας πολυωνύμων, κατά το οποίο όλοι οι συμμετέχοντες ελέγχουν τα ληφθέντα κρυπτογραφημένα pi(j), και αν το αποκρυπτογραφημένο μήνυμα δεν αντιστοιχεί στο κοινό pi(j)G, δημοσιεύουν μια κρυπτογραφική απόδειξη ότι το κρυπτογραφημένο μήνυμα που έλαβαν είναι εσφαλμένο. Αποδείξτε ότι το μήνυμα όχι αντιστοιχεί Χοίρος) πολύ πιο εύκολο από το να αποδείξεις ότι ταιριάζει. Θα πρέπει να σημειωθεί ότι αυτό απαιτεί από κάθε συμμετέχοντα να εμφανίζεται στο διαδίκτυο τουλάχιστον μία φορά κατά τη διάρκεια του χρόνου που έχει δοθεί για τη δημιουργία τέτοιων αποδεικτικών στοιχείων και βασίζεται στην υπόθεση ότι εάν δημοσιεύσει μια τέτοια απόδειξη, θα φτάσει σε όλους τους άλλους συμμετέχοντες στον ίδιο χρόνο.

Εάν ένας συμμετέχων δεν εμφανίστηκε στο διαδίκτυο κατά τη διάρκεια αυτής της χρονικής περιόδου και είχε τουλάχιστον ένα λανθασμένο στοιχείο, τότε ο συγκεκριμένος συμμετέχων δεν θα μπορεί να συμμετάσχει σε περαιτέρω δημιουργία αριθμών. Το πρωτόκολλο, ωστόσο, θα εξακολουθεί να λειτουργεί εάν υπάρχει τουλάχιστον k συμμετέχοντες που είτε μόλις έλαβαν τα σωστά εξαρτήματα είτε κατάφεραν να αφήσουν αποδείξεις ανακρίβειας εντός του καθορισμένου χρόνου.

Αποδείξεις ορθότητας H_i

Το τελευταίο μέρος που μένει να συζητηθεί είναι πώς θα αποδειχθεί η ορθότητα των δημοσιευμένων Hεγώ, δηλαδή αυτό Γεια = p(i)H, χωρίς άνοιγμα πι).

Ας θυμηθούμε ότι οι αξίες H, G, p(i)G κοινό και γνωστό σε όλους. Λήψη λειτουργίας πι) γνωρίζων Χοίρος и G που ονομάζεται διακριτός λογάριθμος, ή dlog, και θέλουμε να αποδείξουμε ότι:

dlog(p(i)G, G) = dlog(Hi, H)

χωρίς αποκάλυψη πι). Κατασκευές για τέτοιες αποδείξεις υπάρχουν, για παράδειγμα Πρωτόκολλο Schnorr.

Με αυτό το σχέδιο, κάθε συμμετέχων, μαζί με Hi αποστέλλει απόδειξη ορθότητας σύμφωνα με το σχέδιο.

Μόλις δημιουργηθεί ένας τυχαίος αριθμός, συχνά χρειάζεται να χρησιμοποιηθεί από άλλους συμμετέχοντες εκτός από αυτούς που τον δημιούργησαν. Αυτοί οι συμμετέχοντες, μαζί με τον αριθμό, πρέπει να στείλουν όλους Hi και σχετικά αποδεικτικά στοιχεία.

Ένας περίεργος αναγνώστης μπορεί να ρωτήσει: αφού ο τελικός τυχαίος αριθμός είναι H0, και p(0)G - Αυτή είναι δημόσια πληροφόρηση, γιατί χρειαζόμαστε αποδείξεις για κάθε άτομο Hγιατί να μην στείλω απόδειξη

dlog(p(0)G, G) = dlog(H0, H)

Το πρόβλημα είναι ότι μια τέτοια απόδειξη δεν μπορεί να δημιουργηθεί χρησιμοποιώντας το Πρωτόκολλο Schnorr επειδή κανείς δεν γνωρίζει την τιμή p (0), απαραίτητο για τη δημιουργία της απόδειξης, και επιπλέον, ολόκληρη η γεννήτρια τυχαίων αριθμών βασίζεται στο γεγονός ότι κανείς δεν γνωρίζει αυτήν την τιμή. Επομένως είναι απαραίτητο να υπάρχουν όλες οι αξίες Hi και τα ατομικά τους στοιχεία για την απόδειξη της ορθότητας H0.

Ωστόσο, εάν υπήρχε κάποια πράξη σε σημεία σε ελλειπτικές καμπύλες που είναι σημασιολογικά παρόμοια με τον πολλαπλασιασμό, η απόδειξη της ορθότητας H0 θα ήταν ασήμαντο, απλά θα το φροντίζαμε

H0 × G = p(0)G × H

Εάν η επιλεγμένη καμπύλη υποστηρίζει ζεύγη ελλειπτικών καμπυλών, αυτή η απόδειξη λειτουργεί. Σε αυτήν την περίπτωση HΤο 0 δεν είναι μόνο η έξοδος μιας γεννήτριας τυχαίων αριθμών, η οποία μπορεί να επαληθευτεί από οποιονδήποτε συμμετέχοντα που γνωρίζει G,H и ρ(0)G. HΤο 0 είναι επίσης μια υπογραφή στο μήνυμα που χρησιμοποιήθηκε ως σπόρος, επιβεβαιώνοντας αυτό k и n οι συμμετέχοντες υπέγραψαν αυτό το μήνυμα. Έτσι, εάν σπόρος - είναι ο κατακερματισμός του μπλοκ στο πρωτόκολλο blockchain, λοιπόν H0 είναι ταυτόχρονα μια πολλαπλή υπογραφή σε ένα μπλοκ και ένας πολύ καλός τυχαίος αριθμός.

Εν κατακλείδι

Αυτό το άρθρο είναι μέρος μιας σειράς τεχνικών ιστολογίων NEAR. Το NEAR είναι ένα πρωτόκολλο και πλατφόρμα blockchain για την ανάπτυξη αποκεντρωμένων εφαρμογών με έμφαση στην ευκολία ανάπτυξης και ευκολίας χρήσης για τους τελικούς χρήστες.

Ο κωδικός πρωτοκόλλου είναι ανοιχτός, η εφαρμογή μας είναι γραμμένη σε Rust, μπορεί να βρεθεί εδώ.

Μπορείτε να δείτε πώς είναι η ανάπτυξη για το NEAR και να πειραματιστείτε στο διαδικτυακό IDE εδώ.

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

Τα λέμε σύντομα!

Πηγή: www.habr.com