Γεια σου Χαμπρ!
Σε αυτό το άρθρο θα μιλήσω για τη δημιουργία ψευδοτυχαίων αριθμών από συμμετέχοντες που δεν εμπιστεύονται ο ένας τον άλλον. Όπως θα δούμε παρακάτω, η υλοποίηση μιας «σχεδόν» καλής γεννήτριας είναι αρκετά απλή, αλλά μια πολύ καλή είναι δύσκολη.
Γιατί θα ήταν απαραίτητο να δημιουργηθούν τυχαίοι αριθμοί μεταξύ των συμμετεχόντων που δεν εμπιστεύονται ο ένας τον άλλον; Ένας τομέας εφαρμογής είναι οι αποκεντρωμένες εφαρμογές. Για παράδειγμα, μια εφαρμογή που δέχεται ένα στοίχημα από έναν συμμετέχοντα και είτε διπλασιάζει το ποσό με πιθανότητα 49% είτε αφαιρεί με πιθανότητα 51% θα λειτουργήσει μόνο εάν μπορεί να λάβει αμερόληπτα έναν τυχαίο αριθμό. Εάν ένας εισβολέας μπορεί να επηρεάσει το αποτέλεσμα της δημιουργίας τυχαίων αριθμών και ακόμη και να αυξήσει ελαφρώς τις πιθανότητες να λάβει μια πληρωμή στην εφαρμογή, θα την καταστρέψει εύκολα.
Όταν σχεδιάζουμε ένα πρωτόκολλο δημιουργίας κατανεμημένων τυχαίων αριθμών, θέλουμε να έχει τρεις ιδιότητες:
-
Πρέπει να είναι αμερόληπτος. Με άλλα λόγια, κανένας συμμετέχων δεν πρέπει με κανέναν τρόπο να επηρεάσει το αποτέλεσμα της γεννήτριας τυχαίων αριθμών.
-
Πρέπει να είναι απρόβλεπτος. Με άλλα λόγια, κανένας συμμετέχων δεν θα πρέπει να μπορεί να προβλέψει ποιος αριθμός θα δημιουργηθεί (ή να συμπεράνει κάποια από τις ιδιότητές του) πριν δημιουργηθεί.
-
Το πρωτόκολλο πρέπει να είναι βιώσιμο, δηλαδή να είναι ανθεκτικό στο γεγονός ότι ένα ορισμένο ποσοστό συμμετεχόντων αποσυνδέεται από το δίκτυο ή προσπαθεί σκόπιμα να διακόψει το πρωτόκολλο.
Σε αυτό το άρθρο θα εξετάσουμε δύο προσεγγίσεις: RANDAO + VDF και την προσέγγιση κωδικών διαγραφής. Στο επόμενο μέρος, θα εξετάσουμε λεπτομερώς την προσέγγιση με βάση τις υπογραφές κατωφλίου.
Αλλά πρώτα, ας δούμε έναν απλό και κοινώς χρησιμοποιούμενο αλγόριθμο που είναι βιώσιμος, απρόβλεπτος, αλλά προκατειλημμένος.
ΡΑΝΤΑΟ
Το RANDAO είναι μια πολύ απλή και επομένως αρκετά διαδεδομένη προσέγγιση για τη δημιουργία τυχαίας. Όλοι οι συμμετέχοντες στο δίκτυο επιλέγουν πρώτα τοπικά έναν ψευδοτυχαίο αριθμό και μετά κάθε συμμετέχων στέλνει έναν κατακερματισμό του επιλεγμένου αριθμού. Στη συνέχεια, οι συμμετέχοντες με τη σειρά αποκαλύπτουν τους αριθμούς που έχουν επιλέξει και εκτελούν μια λειτουργία XOR στους αριθμούς που αποκαλύπτονται και το αποτέλεσμα αυτής της λειτουργίας γίνεται το αποτέλεσμα του πρωτοκόλλου.
Το βήμα της δημοσίευσης των κατακερματισμών πριν από την αποκάλυψη των αριθμών είναι απαραίτητο, ώστε ο εισβολέας να μην μπορεί να επιλέξει τον αριθμό του αφού δει τους αριθμούς των άλλων συμμετεχόντων. Αυτό θα του επέτρεπε να προσδιορίζει σχεδόν μόνος του την έξοδο της γεννήτριας τυχαίων αριθμών.
Κατά τη διάρκεια του πρωτοκόλλου, οι συμμετέχοντες πρέπει να καταλήξουν σε μια κοινή απόφαση (τη λεγόμενη συναίνεση) δύο φορές: πότε να αρχίσουν να αποκαλύπτουν τους επιλεγμένους αριθμούς και επομένως να σταματήσουν να δέχονται κατακερματισμούς και πότε να σταματήσουν να αποδέχονται τους επιλεγμένους αριθμούς και να υπολογίζουν το τυχαίο που προκύπτει αριθμός. Η λήψη τέτοιων αποφάσεων μεταξύ συμμετεχόντων που δεν εμπιστεύονται ο ένας τον άλλον δεν είναι εύκολη υπόθεση από μόνη της και θα επανέλθουμε σε αυτό σε μελλοντικά άρθρα· σε αυτό το άρθρο θα υποθέσουμε ότι ένας τέτοιος αλγόριθμος συναίνεσης είναι διαθέσιμος σε εμάς.
Ποιες από τις ιδιότητες που περιγράψαμε παραπάνω έχει το RANDAO; Είναι απρόβλεπτο, έχει την ίδια ζωτικότητα με το υποκείμενο πρωτόκολλο συναίνεσης, αλλά είναι προκατειλημμένο. Συγκεκριμένα, ένας εισβολέας μπορεί να παρατηρήσει το δίκτυο και αφού οι άλλοι συμμετέχοντες αποκαλύψουν τους αριθμούς τους, μπορεί να υπολογίσει το XOR τους και να αποφασίσει αν θα αποκαλύψει ή όχι τον αριθμό του για να επηρεάσει το αποτέλεσμα. Αν και αυτό εμποδίζει τον εισβολέα να προσδιορίσει μόνος του την έξοδο της γεννήτριας τυχαίων αριθμών, εξακολουθεί να του δίνει 1 bit επιρροής. Και αν οι εισβολείς ελέγχουν αρκετούς συμμετέχοντες, τότε ο αριθμός των bit που ελέγχουν θα είναι ίσος με τον αριθμό των συμμετεχόντων υπό τον έλεγχό τους.
Η επιρροή των επιτιθέμενων μπορεί να μειωθεί σημαντικά απαιτώντας από τους συμμετέχοντες να αποκαλύψουν τους αριθμούς με τη σειρά. Τότε ο εισβολέας θα μπορεί να επηρεάσει το αποτέλεσμα μόνο αν ανοίξει τελευταίος. Ενώ η επιρροή είναι σημαντικά μικρότερη, ο αλγόριθμος εξακολουθεί να είναι προκατειλημμένος.
RANDAO+VDF
Ένας τρόπος για να κάνετε το RANDAO αμερόληπτο είναι ο εξής: αφού αποκαλυφθούν όλοι οι αριθμοί και υπολογιστεί το XOR, το αποτέλεσμά του τροφοδοτείται στην είσοδο μιας συνάρτησης, η οποία χρειάζεται πολύ χρόνο για να υπολογιστεί, αλλά σας επιτρέπει να ελέγξετε την ορθότητα των υπολογισμός πολύ γρήγορα.
(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро
Αυτή η λειτουργία ονομάζεται επαληθεύσιμη συνάρτηση καθυστέρησης ή VDF. Εάν ο υπολογισμός του τελικού αποτελέσματος διαρκεί περισσότερο από το στάδιο αποκάλυψης αριθμού, τότε ο επιτιθέμενος δεν θα μπορεί να προβλέψει το αποτέλεσμα της εμφάνισης ή της απόκρυψης του αριθμού του και επομένως θα χάσει την ευκαιρία να επηρεάσει το αποτέλεσμα.
Η ανάπτυξη καλών VDF είναι εξαιρετικά δύσκολη. Πρόσφατα υπήρξαν αρκετές ανακαλύψεις, π.χ.
Η μεγαλύτερη πρόκληση αυτής της προσέγγισης είναι η ρύθμιση του VDF έτσι ώστε ακόμη και ένας συμμετέχων με πολύ ακριβό εξειδικευμένο υλικό να μην μπορεί να υπολογίσει το VDF πριν από το τέλος της φάσης ανακάλυψης. Στην ιδανική περίπτωση, ο αλγόριθμος θα πρέπει να έχει ακόμη και ένα σημαντικό περιθώριο ασφαλείας, ας πούμε 10x. Το παρακάτω σχήμα δείχνει μια επίθεση από έναν ηθοποιό που έχει ένα εξειδικευμένο ASIC που του επιτρέπει να εκτελέσει ένα VDF πιο γρήγορα από τον χρόνο που έχει διατεθεί για να αποκαλύψει την επιβεβαίωση RANDAO. Ένας τέτοιος συμμετέχων μπορεί ακόμα να υπολογίσει το τελικό αποτέλεσμα χρησιμοποιώντας ή όχι χρησιμοποιώντας τον αριθμό του και, στη συνέχεια, με βάση τον υπολογισμό, να επιλέξει αν θα το εμφανίσει ή όχι.
Για την οικογένεια VDF που αναφέρθηκε παραπάνω, η απόδοση ενός αποκλειστικού ASIC μπορεί να είναι 100+ φορές υψηλότερη από το συμβατικό υλικό. Έτσι, εάν η φάση ανάπτυξης διαρκεί 10 δευτερόλεπτα, τότε το VDF που υπολογίζεται σε ένα τέτοιο ASIC πρέπει να πάρει περισσότερα από 100 δευτερόλεπτα για να έχει 10x περιθώριο ασφαλείας και, επομένως, το ίδιο VDF που υπολογίζεται σε υλικό εμπορευμάτων πρέπει να διαρκεί 100 x 100 δευτερόλεπτα = ~ 3 ώρες.
Το Ίδρυμα Ethereum σχεδιάζει να λύσει αυτό το πρόβλημα δημιουργώντας τα δικά του διαθέσιμα στο κοινό, δωρεάν ASIC. Μόλις συμβεί αυτό, όλα τα άλλα πρωτόκολλα μπορούν επίσης να επωφεληθούν από αυτήν την τεχνολογία, αλλά μέχρι τότε η προσέγγιση RANDAO+VDF δεν θα είναι τόσο βιώσιμη για πρωτόκολλα που δεν μπορούν να επενδύσουν στην ανάπτυξη των δικών τους ASIC.
Έχουν συγκεντρωθεί πολλά άρθρα, βίντεο και άλλες πληροφορίες σχετικά με το VDF
Χρησιμοποιούμε κωδικούς διαγραφής
Σε αυτή την ενότητα, θα εξετάσουμε ένα πρωτόκολλο δημιουργίας τυχαίων αριθμών που χρησιμοποιεί
Η κύρια ιδέα του πρωτοκόλλου είναι η εξής. Για απλότητα, ας υποθέσουμε ότι υπάρχουν ακριβώς 100 συμμετέχοντες. Ας υποθέσουμε επίσης ότι όλοι οι συμμετέχοντες τοπικά έχουν κάποιο ιδιωτικό κλειδί και τα δημόσια κλειδιά όλων των συμμετεχόντων είναι γνωστά σε όλους τους συμμετέχοντες:
-
Κάθε συμμετέχων τοπικά έρχεται με μια μεγάλη συμβολοσειρά, τη χωρίζει σε 67 μέρη, δημιουργεί κωδικούς διαγραφής για να αποκτήσει 100 κοινές χρήσεις, έτσι ώστε οποιαδήποτε 67 να είναι αρκετά για να ανακτήσει τη συμβολοσειρά, εκχωρεί καθένα από τα 100 κοινά στοιχεία σε έναν από τους συμμετέχοντες και τους κρυπτογραφεί με δημόσιο κλειδί του ίδιου συμμετέχοντα. Όλες οι κωδικοποιημένες μετοχές δημοσιεύονται στη συνέχεια.
-
Οι συμμετέχοντες χρησιμοποιούν κάποιο είδος συναίνεσης για να καταλήξουν σε συμφωνία για κωδικοποιημένα σύνολα από συγκεκριμένους 67 συμμετέχοντες.
-
Μόλις επιτευχθεί συναίνεση, κάθε συμμετέχων παίρνει τα κωδικοποιημένα μερίδια σε καθένα από τα 67 σύνολα κρυπτογραφημένα με το δημόσιο κλειδί του, αποκρυπτογραφεί όλα αυτά τα κοινά στοιχεία και δημοσιεύει όλα αυτά τα αποκρυπτογραφημένα κοινόχρηστα.
-
Μόλις 67 συμμετέχοντες ολοκληρώσουν το βήμα (3), όλα τα συμφωνημένα σύνολα μπορούν να αποκωδικοποιηθούν πλήρως και να ανακατασκευαστούν λόγω των ιδιοτήτων των κωδικών διαγραφής και ο τελικός αριθμός μπορεί να ληφθεί ως XOR των αρχικών σειρών με τις οποίες ξεκίνησαν οι συμμετέχοντες στο (1) .
Αυτό το πρωτόκολλο μπορεί να αποδειχθεί αμερόληπτο και απρόβλεπτο. Ο προκύπτων τυχαίος αριθμός καθορίζεται μετά την επίτευξη συναίνεσης, αλλά δεν είναι γνωστός σε κανέναν έως ότου ⅔ από τους συμμετέχοντες αποκωδικοποιήσουν τα μέρη που είναι κρυπτογραφημένα με το δημόσιο κλειδί τους. Έτσι, ο τυχαίος αριθμός προσδιορίζεται πριν δημοσιευτούν επαρκείς πληροφορίες για την ανακατασκευή του.
Τι συμβαίνει εάν στο βήμα (1) ένας από τους συμμετέχοντες έστειλε κωδικοποιημένα κοινόχρηστα στοιχεία στους άλλους συμμετέχοντες που δεν είναι ο σωστός κωδικός διαγραφής για κάποια συμβολοσειρά; Χωρίς πρόσθετες αλλαγές, διαφορετικοί συμμετέχοντες είτε δεν θα μπορούν να ανακτήσουν καθόλου τη συμβολοσειρά είτε θα ανακτήσουν διαφορετικές συμβολοσειρές, κάτι που θα έχει ως αποτέλεσμα διαφορετικοί συμμετέχοντες να λαμβάνουν διαφορετικό τυχαίο αριθμό. Για να το αποτρέψετε αυτό, μπορείτε να κάνετε τα εξής: κάθε συμμετέχων, εκτός από τα κωδικοποιημένα μερίδια, υπολογίζει επίσης
Όταν στο βήμα (4) ο συμμετέχων αποκρυπτογραφήσει 67 beats για μια συγκεκριμένη χορδή και προσπαθήσει να ανακατασκευάσει την αρχική συμβολοσειρά από αυτά, είναι δυνατή μία από τις επιλογές:
-
Η συμβολοσειρά αποκαθίσταται και εάν στη συνέχεια κωδικοποιηθεί ξανά με διαγραφή και υπολογιστεί το δέντρο Merkle για τα τοπικά υπολογισμένα μερίδια, η ρίζα συμπίπτει με εκείνη για την οποία επιτεύχθηκε συναίνεση.
-
Η σειρά αποκαθίσταται, αλλά η τοπικά υπολογισμένη ρίζα δεν ταιριάζει με εκείνη στην οποία επιτεύχθηκε συναίνεση.
-
Η σειρά δεν αποκαθίσταται.
Είναι εύκολο να δείξουμε ότι εάν η επιλογή (1) συνέβη για τουλάχιστον έναν συμμετέχοντα παραπάνω, τότε η επιλογή (1) συνέβη για όλους τους συμμετέχοντες και αντίστροφα, εάν η επιλογή (2) ή (3) συνέβη για τουλάχιστον έναν συμμετέχοντα, τότε για όλους τους συμμετέχοντες θα συμβεί η επιλογή (2) ή (3). Έτσι, για κάθε σειρά του σετ, είτε όλοι οι συμμετέχοντες θα την ανακτήσουν με επιτυχία είτε όλοι οι συμμετέχοντες θα αποτύχουν να την ανακτήσουν. Ο προκύπτων τυχαίος αριθμός είναι τότε ένα XOR μόνο των σειρών που μπόρεσαν να ανακτήσουν οι συμμετέχοντες.
Υπογραφές κατωφλίου
Μια άλλη προσέγγιση για την τυχαιότητα είναι η χρήση αυτών που ονομάζονται υπογραφές κατωφλίου BLS. Μια γεννήτρια τυχαίων αριθμών που βασίζεται σε υπογραφές κατωφλίου έχει ακριβώς τις ίδιες εγγυήσεις με τον αλγόριθμο που βασίζεται σε κώδικα διαγραφής που περιγράφεται παραπάνω, αλλά έχει σημαντικά χαμηλότερο ασυμπτωτικό αριθμό μηνυμάτων που αποστέλλονται μέσω του δικτύου για κάθε παραγόμενο αριθμό.
Οι υπογραφές BLS είναι ένα σχέδιο που επιτρέπει σε πολλούς συμμετέχοντες να δημιουργήσουν μια κοινή υπογραφή για ένα μήνυμα. Αυτές οι υπογραφές χρησιμοποιούνται συχνά για εξοικονόμηση χώρου και εύρους ζώνης, χωρίς να απαιτείται η αποστολή πολλαπλών υπογραφών.
Μια κοινή εφαρμογή για υπογραφές BLS σε πρωτόκολλα blockchain, εκτός από τη δημιουργία τυχαίων αριθμών, είναι η υπογραφή μπλοκ σε πρωτόκολλα BFT. Ας υποθέσουμε ότι 100 συμμετέχοντες δημιουργούν μπλοκ και ένα μπλοκ θεωρείται οριστικό εάν το υπογράψουν 67 από αυτούς. Μπορούν όλοι να υποβάλουν τα μέρη της υπογραφής BLS και να χρησιμοποιήσουν κάποιο αλγόριθμο συναίνεσης για να συμφωνήσουν σε 67 από αυτά και στη συνέχεια να τα συγχωνεύσουν σε μία υπογραφή BLS. Οποιαδήποτε 67 (ή περισσότερα) μέρη μπορούν να χρησιμοποιηθούν για τη δημιουργία της τελικής υπογραφής, η οποία θα εξαρτηθεί από το ποιες υπογραφές συνδυάστηκαν και επομένως μπορεί να διαφέρουν, αν και διαφορετικές επιλογές από τους 67 συμμετέχοντες θα δημιουργήσουν διαφορετική υπογραφή, οποιαδήποτε τέτοια υπογραφή θα είναι έγκυρη υπογραφή για το μπλοκ. Οι υπόλοιποι συμμετέχοντες χρειάζεται μόνο να λάβουν και να επαληθεύσουν μόνο μία υπογραφή ανά μπλοκ, αντί για 67, μέσω του δικτύου, γεγονός που μειώνει σημαντικά το φορτίο στο δίκτυο.
Αποδεικνύεται ότι εάν τα ιδιωτικά κλειδιά που χρησιμοποιούν οι συμμετέχοντες δημιουργούνται με συγκεκριμένο τρόπο, τότε ανεξάρτητα από το ποιες 67 υπογραφές (ή περισσότερες, αλλά όχι λιγότερες) συγκεντρωθούν, η υπογραφή που προκύπτει θα είναι η ίδια. Αυτό μπορεί να χρησιμοποιηθεί ως πηγή τυχαίας: οι συμμετέχοντες συμφωνούν πρώτα σε κάποιο μήνυμα που θα υπογράψουν (αυτό θα μπορούσε να είναι η έξοδος του RANDAO ή απλώς ο κατακερματισμός του τελευταίου μπλοκ, δεν έχει σημασία αρκεί να αλλάζει κάθε φορά και είναι συνεπής) και δημιουργήστε μια υπογραφή BLS για αυτό. Το αποτέλεσμα της παραγωγής θα είναι απρόβλεπτο έως ότου 67 συμμετέχοντες δώσουν τα μέρη τους και μετά από αυτό το αποτέλεσμα είναι ήδη προκαθορισμένο και δεν μπορεί να εξαρτάται από τις ενέργειες κανενός συμμετέχοντα.
Αυτή η προσέγγιση για την τυχαιότητα είναι βιώσιμη εφόσον τουλάχιστον ⅔ από τους συμμετέχοντες στο διαδίκτυο ακολουθούν και οι δύο το πρωτόκολλο και είναι αμερόληπτη και απρόβλεπτη εφόσον τουλάχιστον το ⅓ από τους συμμετέχοντες ακολουθούν το πρωτόκολλο. Είναι σημαντικό να σημειωθεί ότι ένας εισβολέας που ελέγχει περισσότερους από ⅓ αλλά λιγότερους από ⅔ των συμμετεχόντων μπορεί να σταματήσει το πρωτόκολλο, αλλά δεν μπορεί να προβλέψει ή να επηρεάσει την έξοδο του.
Οι ίδιες οι υπογραφές κατωφλίου είναι ένα πολύ ενδιαφέρον θέμα. Στο δεύτερο μέρος του άρθρου, θα αναλύσουμε λεπτομερώς πώς λειτουργούν και πώς ακριβώς είναι απαραίτητο να δημιουργηθούν κλειδιά συμμετεχόντων, ώστε οι υπογραφές κατωφλίου να μπορούν να χρησιμοποιηθούν ως γεννήτρια τυχαίων αριθμών.
Εν κατακλείδι
Αυτό το άρθρο είναι το πρώτο από μια σειρά άρθρων τεχνικού ιστολογίου
Ο κωδικός πρωτοκόλλου είναι ανοιχτός, η εφαρμογή μας είναι γραμμένη σε Rust, μπορεί να βρεθεί
Μπορείτε να δείτε πώς είναι η ανάπτυξη για το NEAR και να πειραματιστείτε στο διαδικτυακό IDE
Μπορείτε να παρακολουθήσετε όλες τις ειδήσεις στα ρωσικά στο
Τα λέμε σύντομα!
Πηγή: www.habr.com