Το πρωτόκολλο συναίνεσης Stellar περιγράφηκε για πρώτη φορά στο David Mazier το 2015. Πρόκειται για ένα «ομοσπονδιακό βυζαντινό σύστημα συμφωνίας» που επιτρέπει σε αποκεντρωμένα υπολογιστικά δίκτυα χωρίς ηγέτες να επιτύχουν αποτελεσματικά συναίνεση για μια απόφαση. Το δίκτυο πληρωμών Stellar χρησιμοποιεί το Stellar Consensus Protocol (SCP) για να διατηρεί ένα συνεπές ιστορικό συναλλαγών που είναι ορατό σε όλους τους συμμετέχοντες.
Τα πρωτόκολλα συναίνεσης θεωρούνται δυσνόητα. Το SCP είναι απλούστερο από τα περισσότερα από αυτά, αλλά εξακολουθεί να μοιράζεται αυτή τη φήμη - εν μέρει λόγω της εσφαλμένης ιδέας ότι η "ομοσπονδιακή ψηφοφορία", η οποία είναι το θέμα του πρώτου μισού του επιστημονικού άρθρου, είναι η SCP. Αλλά αυτό δεν είναι αλήθεια! Αυτό είναι απλώς ένα σημαντικό δομικό στοιχείο που χρησιμοποιεί το δεύτερο μισό του άρθρου για να δημιουργήσει πραγματικός Πρωτόκολλο αστρικής συναίνεσης.
Σε αυτό το άρθρο θα εξηγήσουμε εν συντομία τι είναι «σύστημα συμφωνιών», τι μπορεί να το κάνει «βυζαντινό» και γιατί το βυζαντινό σύστημα «ομοσπονδιακό». Στη συνέχεια θα εξηγήσουμε τη διαδικασία ομοσπονδιακής ψηφοφορίας που περιγράφεται στο άρθρο SCP και, τέλος, θα εξηγήσουμε το ίδιο το πρωτόκολλο SCP.
Συστήματα συμφωνίας
Ένα σύστημα συμφωνιών επιτρέπει σε μια ομάδα συμμετεχόντων να καταλήξουν σε συναίνεση για ένα θέμα, όπως το τι να παραγγείλει για μεσημεριανό γεύμα.
Στην Interstellar, έχουμε εφαρμόσει το δικό μας σύστημα συμφωνιών φαγητού: παραγγέλνουμε αυτό που λέει ο διευθυντής εργασιών μας, John. Αυτό είναι ένα απλό και αποτελεσματικό σύστημα συμφωνίας. Όλοι εμπιστευόμαστε τον Γιάννη και πιστεύουμε ότι θα βρίσκει κάτι ενδιαφέρον και θρεπτικό κάθε μέρα.
Τι γίνεται όμως αν ο Γιάννης κάνει κατάχρηση της εμπιστοσύνης μας; Μπορεί να αποφασίσει μόνος του ότι πρέπει να γίνουμε όλοι vegans. Σε μια ή δύο εβδομάδες, μάλλον θα τον ανατρέψουμε και θα παραδώσουμε την εξουσία στην Ελίζαμπεθ. Αλλά ξαφνικά λατρεύει τα αβοκάντο με γαύρο και πιστεύει ότι όλοι έτσι πρέπει να είναι. Η εξουσία διαφθείρει. Επομένως, είναι καλύτερα να βρείτε κάποια πιο δημοκρατική μέθοδο: κάποιο τρόπο για να βεβαιωθείτε ότι λαμβάνονται υπόψη διαφορετικές προτιμήσεις, διασφαλίζοντας ταυτόχρονα ένα έγκαιρο και ξεκάθαρο αποτέλεσμα, ώστε να μην παραγγείλει κανείς μεσημεριανό γεύμα ή πέντε άτομα να κάνουν διαφορετικές παραγγελίες ή τη συζήτηση σέρνεται μέχρι το βράδυ.
Φαίνεται ότι η λύση είναι απλή: κάντε ψηφοφορία! Αλλά αυτή είναι μια παραπλανητική εντύπωση. Ποιος θα συγκεντρώσει τα ψηφοδέλτια και θα αναφέρει τα αποτελέσματα; Και γιατί να πιστεύουν οι άλλοι αυτά που λέει; Ίσως μπορούμε αρχικά ψηφίζουμε έναν ηγέτη στον οποίο εμπιστευόμαστε ότι θα ηγηθεί της ψηφοφορίας - αλλά που θα την οδηγήσει πρώτα με ψηφοφορία; Τι γίνεται αν δεν μπορούμε να συμφωνήσουμε για έναν ηγέτη; Ή τι γίνεται αν καταλήξουμε σε συμφωνία, αλλά αυτός ο αρχηγός κολλήσει σε μια συνάντηση ή πάει σε αναρρωτική άδεια;
Παρόμοια προβλήματα παρουσιάζονται σε κατανεμημένα δίκτυα υπολογιστών. Όλοι οι συμμετέχοντες ή οι κόμβοι πρέπει να συμφωνήσουν σε κάποια απόφαση, όπως ποιος είναι η σειρά να ενημερώσει ένα κοινόχρηστο αρχείο ή να αφαιρέσει μια εργασία από την ουρά επεξεργασίας. Σε ένα δίκτυο κρυπτονομισμάτων, οι κόμβοι πρέπει επανειλημμένα να επιλέξουν πώς θα μοιάζει η πλήρης ιστορία από πολλές πιθανές εκδόσεις, οι οποίες μερικές φορές συγκρούονται. Αυτή η συμφωνία δικτύου παρέχει διαβεβαίωση στον παραλήπτη ότι το κέρμα είναι (α) έγκυρο (όχι πλαστό) και (β) δεν έχει δαπανηθεί ακόμη αλλού. Αυτό εξασφαλίζει επίσης ότι θα μπορεί να ξοδέψει τα νομίσματα στο μέλλον επειδή ο νέος παραλήπτης θα έχει τις ίδιες εγγυήσεις για τους ίδιους λόγους.
Οποιοδήποτε σύστημα συναίνεσης σε ένα κατανεμημένο υπολογιστικό δίκτυο πρέπει να είναι ανεκτικό σε σφάλματα: πρέπει να παράγει σταθερά αποτελέσματα παρά τα σφάλματα όπως αργές συνδέσεις, κόμβοι που δεν ανταποκρίνονται και εσφαλμένη σειρά μηνυμάτων. βυζαντινός Το σύστημα συμφωνίας είναι επιπρόσθετα ανθεκτικό σε «βυζαντινά» λάθη: κόμβοι που δίνουν ψευδείς πληροφορίες, είτε λόγω σφάλματος είτε σε μια σκόπιμη προσπάθεια να υπονομεύσουν το σύστημα ή να αποκτήσουν κάποιο πλεονέκτημα. Η «βυζαντινή» ανοχή σφαλμάτων - η ικανότητα να εμπιστεύεται κανείς μια ομαδική απόφαση ακόμα και όταν ορισμένα μέλη της ομάδας μπορεί να λένε ψέματα ή να μην ακολουθούν με άλλο τρόπο τους κανόνες λήψης αποφάσεων - ονομάζεται που προσπάθησε να συντονίσει την επίθεση. στον Άντονι Στίβενς.
Σκεφτείτε την ιδιοκτήτρια κρυπτονομισμάτων Alice, η οποία πρέπει να επιλέξει ανάμεσα στην αγορά νόστιμου παγωτού από τον Bob και στην εξόφληση του χρέους της Carol. Ίσως η Αλίκη θέλει να πληρώσει και τους δύο ταυτόχρονα ξοδεύοντας δόλια το ίδιο νόμισμα. Για να το κάνει αυτό, πρέπει να πείσει τον υπολογιστή του Μπομπ ότι το νόμισμα δεν πληρώθηκε ποτέ στην Κάρολ και να πείσει τον υπολογιστή της Κάρολ ότι το νόμισμα δεν πληρώθηκε ποτέ στον Μπομπ. Το βυζαντινό σύστημα συμφωνιών το καθιστά αυτό ουσιαστικά αδύνατο, χρησιμοποιώντας μια μορφή πλειοψηφικού κανόνα που ονομάζεται απαρτία. Ένας κόμβος σε ένα τέτοιο δίκτυο αρνείται να μετακινηθεί σε μια συγκεκριμένη έκδοση της ιστορίας μέχρι να δει ότι ένας επαρκής αριθμός ομότιμων - μια απαρτία - συμφωνεί σε μια τέτοια μετάβαση. Μόλις συμβεί αυτό, θα σχηματίσουν ένα μπλοκ ψηφοφορίας αρκετά μεγάλο ώστε να αναγκάσει τους υπόλοιπους κόμβους του δικτύου να συμφωνήσουν με την απόφασή τους. Η Αλίκη μπορεί να αναγκάσει ορισμένους κόμβους να πουν ψέματα για λογαριασμό της, αλλά αν το δίκτυο είναι αρκετά μεγάλο, η προσπάθειά της θα κατακλυστεί από τις ψήφους τίμιων κόμβων.
Πόσοι κόμβοι απαιτούνται για την απαρτία; Τουλάχιστον, πλειοψηφία, ή μάλλον ειδική πλειοψηφία για την καταπολέμηση των λαθών και της απάτης. Αλλά για να μετρήσετε την πλειοψηφία, πρέπει να γνωρίζετε τον συνολικό αριθμό των συμμετεχόντων. Στο γραφείο Interstellar ή στις περιφερειακές εκλογές, αυτοί οι αριθμοί είναι εύκολο να βρεθούν. Αλλά αν η ομάδα σας είναι ένα χαλαρά καθορισμένο δίκτυο στο οποίο οι κόμβοι μπορούν να εισέλθουν και να φύγουν κατά βούληση χωρίς έγκριση από το κέντρο, τότε χρειάζεστε ομοσπονδιακός ένα σύστημα βυζαντινών συμφωνιών ικανό να προσδιορίζει απαρτίες όχι από μια προκαθορισμένη λίστα κόμβων, αλλά δυναμικά, από ένα διαρκώς μεταβαλλόμενο και αναπόφευκτα ελλιπές στιγμιότυπο κόμβων σε μια δεδομένη χρονική στιγμή.
Μπορεί να φαίνεται αδύνατο να δημιουργηθεί απαρτία από την προοπτική ενός μεμονωμένου κόμβου σε ένα τεράστιο δίκτυο, αλλά είναι δυνατό. Μια τέτοια απαρτία μπορεί ακόμη και να εγγυηθεί τα αποτελέσματα της αποκεντρωμένης ψηφοφορίας. Η λευκή βίβλος SCP δείχνει πώς να το κάνετε αυτό χρησιμοποιώντας μια διαδικασία που ονομάζεται με ομοσπονδιακή ψηφοφορία.
Για ανυπόμονα
Το υπόλοιπο άρθρο περιγράφει την ομοσπονδιακή ψηφοφορία και το πρωτόκολλο συναίνεσης Stellar με περισσότερες λεπτομέρειες. Εάν δεν σας ενδιαφέρουν οι λεπτομέρειες, ακολουθεί μια γενική επισκόπηση της διαδικασίας.
- Οι κόμβοι διεξάγουν γύρους ομοσπονδιακής ψηφοφορίας για τους "υποψηφίους". Ο ομοσπονδιακός γύρος ψηφοφορίας σημαίνει:
- Ο κόμβος ψηφίζει για κάποια δήλωση, για παράδειγμα, "Προτείνω την τιμή του V".
- Ο κόμβος ακούει τις φωνές των συνομηλίκων μέχρι να βρει έναν που μπορεί να "λάβει".
- Ο κόμβος αναζητά "απαρτία" για αυτόν τον ισχυρισμό. Η απαρτία «επιβεβαιώνει» τον υποψήφιο.
- Μόλις ένας κόμβος μπορεί να επιβεβαιώσει έναν ή περισσότερους υποψηφίους, επιχειρεί να «προετοιμάσει» το «ψηφοδέλτιο» μέσα από αρκετούς γύρους ομοσπονδιακής ψηφοφορίας.
- Μόλις ένας κόμβος είναι σε θέση να επαληθεύσει ότι το ψηφοδέλτιο είναι έτοιμο, επιχειρεί να το δεσμεύσει μέσω ακόμη περισσότερων γύρους ομοσπονδιακής ψηφοφορίας.
- Μόλις ένας κόμβος μπορεί να επιβεβαιώσει μια δέσμευση ενός ψηφοδελτίου, μπορεί να "εξωτερικεύσει" την αξία αυτού του ψηφοδελτίου χρησιμοποιώντας το ως συναινετικό αποτέλεσμα.
Αυτά τα βήματα περιλαμβάνουν πολλαπλούς γύρους ομοσπονδιακής ψηφοφορίας, οι οποίοι αποτελούν συλλογικά έναν γύρο SCP. Ας ρίξουμε μια πιο προσεκτική ματιά στο τι συμβαίνει σε κάθε βήμα.
Ομοσπονδιακή ψηφοφορία
Η ομοσπονδιακή ψηφοφορία είναι μια διαδικασία για τον καθορισμό του εάν το δίκτυο μπορεί να συμφωνήσει σε μια πρόταση. Στον γύρο ψηφοφορίας, κάθε κόμβος πρέπει να επιλέξει μία από τις δυνητικά πολλές πιθανές τιμές. Δεν μπορεί να το κάνει αυτό αν δεν είναι βέβαιο ότι άλλοι κόμβοι στο δίκτυο δεν θα επιλέξουν διαφορετικό αποτέλεσμα. Για να βεβαιωθείτε για αυτό, οι κόμβοι ανταλλάσσουν ένα μπαράζ μηνυμάτων πέρα δώθε έτσι ώστε όλοι επιβεβαίωσεΌτι απαρτία κόμβους αποδέχεται ίδιο απόφαση. Το υπόλοιπο αυτής της ενότητας εξηγεί τους όρους αυτής της πρότασης και πώς λαμβάνει χώρα ολόκληρη η διαδικασία.
Απαρτίες και φέτες απαρτίας
Ας ξεκινήσουμε ορίζοντας απαρτία. Όπως συζητήσαμε παραπάνω, σε ένα αποκεντρωμένο δίκτυο με δυναμική ιδιότητα μέλους, είναι αδύνατο να γνωρίζουμε εκ των προτέρων τον αριθμό των κόμβων και επομένως πόσοι χρειάζονται για την πλειοψηφία. Η ομοσπονδιακή ψηφοφορία λύνει αυτό το πρόβλημα εισάγοντας μια νέα ιδέα περικοπή απαρτίας (τεμάχιο απαρτίας): Ένα μικρό σύνολο ομότιμων που εμπιστεύεται ένας κόμβος για την επικοινωνία πληροφοριών κατάστασης ψηφοφορίας στο υπόλοιπο δίκτυο. Κάθε κόμβος ορίζει το δικό του τμήμα απαρτίας (της οποίας γίνεται de facto μέλος).
Ο σχηματισμός απαρτίας ξεκινά με μια περικοπή απαρτίας. Για κάθε κόμβο, προστίθενται οι κομμένοι κόμβοι του. Στη συνέχεια προστίθενται οι όροι φέτας αυτούς τους κόμβους και ούτω καθεξής. Καθώς συνεχίζετε, υπάρχουν όλο και περισσότεροι κόμβοι που δεν μπορείτε να προσθέσετε επειδή περιλαμβάνονται ήδη στο slice. Όταν δεν υπάρχουν άλλοι νέοι κόμβοι για προσθήκη, η διαδικασία σταματά: έχουμε σχηματίσει απαρτία με «μεταβατικό κλείσιμο» του τμήματος απαρτίας του αρχικού κόμβου.
Για να βρείτε απαρτία από έναν δεδομένο κόμβο...
... προσθέστε μέλη της φέτας του...
...μετά προσθέτουμε μέλη φέτας αυτών των κόμβων.
Συνεχίζουμε μέχρι να μην μείνουν κόμβοι για προσθήκη.
Δεν έχουν απομείνει κόμβοι για προσθήκη. Αυτό είναι απαρτία.
Στην πραγματικότητα, κάθε κόμβος μπορεί να εμφανιστεί σε περισσότερες από μία φέτες. Για να σχηματίσετε απαρτία, επιλέξτε μόνο ένα από τα τμήματα και προσθέστε μέλη. στη συνέχεια επιλέξτε οποιαδήποτε φέτα για κάθε ένα από τα μέλη και προσθέστε μέλη το κόψτε και ούτω καθεξής. Αυτό σημαίνει ότι κάθε κόμβος είναι μέλος πολλών πιθανών απαρτιών.
Επιλέξτε μόνο ένα τμήμα απαρτίας σε κάθε βήμα.
Μία πιθανή απαρτία. Ή εναλλακτική...
...επιλέξτε άλλες φέτες...
…(όταν είναι δυνατόν)…
... δημιουργεί άλλη απαρτία.
Πώς γνωρίζει ένας κόμβος σε ποιες φέτες βρίσκονται άλλοι κόμβοι; Με τον ίδιο τρόπο όπως και άλλες πληροφορίες για άλλους κόμβους: από τις μεταδόσεις που εκπέμπει κάθε κόμβος στο δίκτυο όταν αλλάζει η κατάσταση ψήφου του. Κάθε εκπομπή περιλαμβάνει πληροφορίες σχετικά με τα τμήματα του κόμβου αποστολής. Η λευκή βίβλος SCP δεν καθορίζει μηχανισμό επικοινωνίας. Οι εφαρμογές συνήθως χρησιμοποιούνται για εγγυημένη μετάδοση μηνυμάτων σε όλο το δίκτυο.
Υπενθυμίζουμε ότι στο μη ομοσπονδιακό βυζαντινό σύστημα συμφωνιών, ως απαρτία ορίζεται η πλειοψηφία όλων των κόμβων. Το σύστημα των βυζαντινών συμφωνιών σχεδιάζεται από τη σκοπιά του ερωτήματος: πόσους ανέντιμους κόμβους μπορεί να ανεχθεί το σύστημα; Σε ένα σύστημα Ν κόμβων που έχουν σχεδιαστεί για να επιβιώνουν από αποτυχίες, ένας κόμβος θα πρέπει να είναι σε θέση να κάνει πρόοδο λαμβάνοντας ανατροφοδότηση από N−f ομοτίμους, καθώς ο f από αυτούς μπορεί να είναι εκτός λειτουργίας. Αλλά έχοντας λάβει μια απάντηση από N−f peers, μπορούμε να υποθέσουμε ότι όλοι οι f peers (από τους οποίους ο κόμβος δεν έλαβε απάντηση) είναι πραγματικά ειλικρινείς. Έτσι, f από τους ομότιμους N−f (από τους οποίους ελήφθη η απάντηση) είναι κακόβουλοι. Για να καταλήξουν οι κόμβοι στην ίδια συναίνεση, η πλειοψηφία των υπολοίπων κόμβων πρέπει να είναι ειλικρινής, δηλαδή, χρειαζόμαστε το N−f να είναι μεγαλύτερο από 2f ή N > 3f. Έτσι, συνήθως ένα σύστημα που έχει σχεδιαστεί για να επιβιώνει από αποτυχίες f θα έχει συνολικά N=3f+1 κόμβους και μέγεθος απαρτίας 2f+1. Μόλις μια πρόταση περάσει το όριο απαρτίας, το υπόλοιπο δίκτυο είναι πεπεισμένο ότι τυχόν ανταγωνιστικές προτάσεις θα αποτύχουν. Έτσι το δίκτυο συγκλίνει στο αποτέλεσμα.
Όμως σε ένα ομοσπονδιακό βυζαντινό σύστημα συμφωνιών, όχι μόνο δεν μπορεί να υπάρξει πλειοψηφία (γιατί κανείς δεν γνωρίζει το συνολικό μέγεθος του δικτύου), αλλά η έννοια της πλειοψηφίας είναι εντελώς άχρηστη! Εάν η ιδιότητα μέλους στο σύστημα είναι ανοιχτή, τότε κάποιος μπορεί να κερδίσει την πλειοψηφία απλώς εκτελώντας μια λεγόμενη επίθεση Sybil: συνδέοντας επανειλημμένα στο δίκτυο σε πολλούς κόμβους. Γιατί λοιπόν μπορεί να ονομαστεί μεταβατικό κλείσιμο φέτας απαρτία, και πώς είναι σε θέση να καταστείλει τις ανταγωνιστικές προτάσεις;
Τεχνικά, σε καμία περίπτωση! Φανταστείτε ένα δίκτυο έξι κόμβων, όπου δύο τρίδυμα είναι απομονωμένα μεταξύ τους σε απαρτίες. Η πρώτη υποομάδα μπορεί να πάρει μια απόφαση που η δεύτερη δεν θα ακούσει ποτέ και το αντίστροφο. Δεν υπάρχει τρόπος για αυτό το δίκτυο να καταλήξει σε συναίνεση (εκτός από τυχαία).
Επομένως, το SCP απαιτεί ότι για την ομοσπονδιακή ψηφοφορία (και για να ισχύουν τα σημαντικά θεωρήματα της εργασίας), το δίκτυο πρέπει να έχει μια ιδιότητα που ονομάζεται διασταύρωση απαρτιών. Σε ένα δίκτυο με αυτήν την ιδιότητα, τυχόν δύο απαρτίες που μπορούν να δημιουργηθούν πάντα επικαλύπτονται σε τουλάχιστον έναν κόμβο. Για τον προσδιορισμό του κυρίαρχου συναισθήματος του δικτύου, αυτό είναι τόσο καλό όσο και η πλειοψηφία. Διαισθητικά, αυτό σημαίνει ότι εάν οποιαδήποτε απαρτία συμφωνεί με τη δήλωση X, καμία άλλη απαρτία δεν μπορεί ποτέ να συμφωνήσει με οτιδήποτε άλλο, επειδή θα περιλαμβάνει απαραίτητα κάποιον κόμβο από την πρώτη απαρτία που έχει ήδη ψηφίσει για το X.
Εάν υπάρχει διασταύρωση απαρτιών στο δίκτυο...
...τότε δύο απαρτίες μπορείτε να δημιουργήσετε...
...πάντα θα τέμνονται.
(Φυσικά, οι επικαλυπτόμενοι κόμβοι μπορεί να αποδειχθούν βυζαντινοί ή κακοί. Σε αυτήν την περίπτωση, η τομή απαρτίας δεν βοηθά καθόλου το δίκτυο να συμφωνήσει. Για το λόγο αυτό, πολλά από τα αποτελέσματα στη λευκή βίβλο SCP βασίζονται σε ρητές παραδοχές, όπως αυτό που απομένει στη διέλευση απαρτίας δικτύου ακόμα και μετά την αφαίρεση κακών κόμβων. Για απλότητα, ας αφήσουμε αυτές τις υποθέσεις σιωπηρή στο υπόλοιπο άρθρο).
Μπορεί να φαίνεται παράλογο να περιμένουμε ότι μια αξιόπιστη διέλευση απαρτίας είναι δυνατή σε ένα δίκτυο ανεξάρτητων κόμβων. Υπάρχουν όμως δύο λόγοι που συμβαίνει αυτό.
Ο πρώτος λόγος είναι η ύπαρξη του ίδιου του Διαδικτύου. Το Διαδίκτυο είναι ένα τέλειο παράδειγμα ενός δικτύου ανεξάρτητων κόμβων με τεμνόμενες απαρτίες. Οι περισσότεροι κόμβοι στο Διαδίκτυο συνδέονται μόνο με μερικούς άλλους τοπικούς κόμβους, αλλά αυτά τα μικρά σύνολα επικαλύπτονται αρκετά ώστε να είναι δυνατή η πρόσβαση σε κάθε κόμβο από κάθε άλλο κόμβο κατά μήκος κάποιας διαδρομής.
Ο δεύτερος λόγος είναι συγκεκριμένος για το δίκτυο πληρωμών Stellar (η πιο κοινή χρήση του SCP). Κάθε στοιχείο στο δίκτυο Stellar έχει έναν εκδότη και οι οδηγίες της Stellar απαιτούν από κάθε εκδότη να ορίσει έναν ή περισσότερους κόμβους στο δίκτυο για την επεξεργασία αιτημάτων εξαργύρωσης. Είναι προς το συμφέρον σας να συμπεριλάβετε άμεσα ή έμμεσα αυτούς τους κόμβους σε τμήματα απαρτίας για κάθε στοιχείο που σας ενδιαφέρει. Στη συνέχεια, τα απαρτία για όλους τους κόμβους που ενδιαφέρονται για ένα δεδομένο στοιχείο θα επικαλύπτονται τουλάχιστον σε αυτούς τους κόμβους εξαργύρωσης. Οι κόμβοι που ενδιαφέρονται για πολλαπλά περιουσιακά στοιχεία θα περιλαμβάνουν όλους τους κόμβους εξαγοράς των αντίστοιχων εκδοτών στα τμήματα απαρτίας τους και θα επιδιώξουν να συγκεντρώσουν όλα τα περιουσιακά στοιχεία μαζί. Επιπλέον, τυχόν στοιχεία που δεν συνδέονται με αυτόν τον τρόπο με άλλα στο δίκτυο και δεν πρέπει να συνδεθεί - έχει σχεδιαστεί έτσι ώστε να μην υπάρχει επικάλυψη απαρτίας για αυτό το δίκτυο (για παράδειγμα, τράπεζες από τη ζώνη του δολαρίου μερικές φορές θέλουν να συναλλάσσονται με τράπεζες από τη ζώνη του ευρώ και τράπεζες από τη ζώνη του πέσο, επομένως βρίσκονται στο ίδιο δίκτυο, αλλά καμία από αυτούς νοιάζονται για το χωριστό δίκτυο παιδιών που πουλάνε κάρτες του μπέιζμπολ).
Φυσικά, ожидание δεν υπάρχει απαρτία εγγύηση. Άλλα βυζαντινά συστήματα συμφωνιών οφείλουν μεγάλο μέρος της πολυπλοκότητάς τους στην εξασφάλιση απαρτιών. Μια σημαντική καινοτομία του SCP είναι ότι αφαιρεί την ευθύνη για τη δημιουργία απαρτιών από τον ίδιο τον αλγόριθμο συναίνεσης και τον φέρνει στο επίπεδο εφαρμογής. Έτσι, παρόλο που η ομοσπονδιακή ψηφοφορία είναι αρκετά γενική για να ψηφίσει για οποιοδήποτε θέμα, η αξιοπιστία της εξαρτάται ουσιαστικά από την ευρύτερη έννοια αυτών των σημασιών. Ορισμένες υποθετικές χρήσεις μπορεί να μην είναι τόσο ευνοϊκές για τη δημιουργία καλά συνδεδεμένων δικτύων όσο άλλες.
Ψηφοφορία, αποδοχή και επιβεβαίωση
Σε έναν ομοσπονδιακό γύρο ψηφοφορίας, ένας κόμβος ξεκινά προαιρετικά να ψηφίζει για κάποια τιμή V. Αυτό σημαίνει τη μετάδοση ενός μηνύματος στο δίκτυο: "Είμαι ο κόμβος N, οι φέτες απαρτίας μου είναι Q και ψηφίζω για το V." Όταν ένας κόμβος ψηφίζει με αυτόν τον τρόπο, υπόσχεται ότι δεν έχει καταψηφίσει ποτέ το V και δεν θα το κάνει ποτέ.
Στις εκπομπές peer-to-peer, κάθε κόμβος βλέπει πώς ψηφίζουν οι άλλοι. Μόλις ένας κόμβος συλλέξει αρκετά από αυτά τα μηνύματα, μπορεί να παρακολουθήσει τμήματα απαρτίας και να προσπαθήσει να βρει απαρτίες. Αν δει απαρτία ομοτίμων που ψηφίζουν επίσης V, μπορεί να προχωρήσει σε υιοθεσία V και μετάδοση αυτού του νέου μηνύματος στο δίκτυο: «Είμαι ο κόμβος N, τα τμήματα απαρτίας μου είναι Q και αποδέχομαι το V». Η αποδοχή παρέχει ισχυρότερη εγγύηση από την απλή ψηφοφορία. Όταν ένας κόμβος ψηφίζει για V, δεν μπορεί ποτέ να ψηφίσει άλλες επιλογές. Αλλά εάν ένας κόμβος δέχεται το V, κανένας κόμβος στο Δίκτυο δεν θα δεχτεί ποτέ την άλλη επιλογή (το θεώρημα 8 στη λευκή βίβλο SCP το αποδεικνύει αυτό).
Φυσικά, υπάρχει μεγάλη πιθανότητα να μην υπάρξει αμέσως απαρτία κόμβων που συμφωνούν με το V. Άλλοι κόμβοι μπορεί να ψηφίσουν άλλες τιμές. Αλλά υπάρχει ένας άλλος τρόπος για να περάσει ένας κόμβος από την απλή ψηφοφορία στην αποδοχή. Το N μπορεί να δεχτεί μια διαφορετική τιμή για το W, ακόμα κι αν δεν το ψήφισε, ακόμα κι αν δεν βλέπει απαρτία για αυτό. Για να αποφασίσετε να αλλάξετε την ψήφο σας, απλώς δείτε σετ μπλοκαρίσματος κόμβοι που έχουν αποδεχτεί W. Ένα σύνολο αποκλεισμού είναι ένας κόμβος από κάθε ένα από τα τμήματα απαρτίας N. Όπως υποδηλώνει το όνομα, μπορεί ΟΙΚΟΔΟΜΙΚΟ ΤΕΤΡΑΓΩΝΟ οποιοδήποτε άλλο νόημα. Εάν όλοι οι κόμβοι σε ένα τέτοιο σύνολο δέχονται το W, τότε (από το Θεώρημα 8) δεν θα είναι ποτέ δυνατό να σχηματιστεί απαρτία που να παίρνει διαφορετική τιμή, και επομένως είναι επίσης ασφαλές για το Ν να δεχτεί το W.
Κόμβος Ν με τρεις φέτες απαρτίας.
Το BDF είναι ένα σύνολο αποκλεισμού για το N: περιλαμβάνει έναν κόμβο από κάθε ένα από τα τμήματα του N.
Το BE είναι επίσης ένα σύνολο αποκλεισμού για το N επειδή το E εμφανίζεται σε δύο φέτες του N.
Αλλά το σύνολο αποκλεισμού δεν είναι απαρτία. Θα ήταν πολύ εύκολο να εξαπατήσετε τον κόμβο N ώστε να αποδεχτεί την επιθυμητή τιμή εάν αρκούσε να χακάρετε μόνο έναν κόμβο σε κάθε ένα από τα κομμάτια του N. Επομένως, η αποδοχή της τιμής δεν είναι το τέλος της ψηφοφορίας. Αντίθετα, το N πρέπει να επιβεβαιώσει την τιμή, δηλαδή να δει μια απαρτία κόμβων που την αποδέχονται. Εάν φτάσει τόσο μακριά, τότε, όπως αποδεικνύει η λευκή βίβλος SCP (στο Θεώρημα 11), και το υπόλοιπο δίκτυο θα επιβεβαιώσει τελικά την ίδια τιμή, οπότε το N θα τερματίσει την ομοσπονδιακή ψήφο με μια συγκεκριμένη τιμή ως αποτέλεσμα.
Ομοσπονδιακή ψηφοφορία.
Η διαδικασία ψηφοφορίας, αποδοχής και επιβεβαίωσης συνιστά έναν πλήρη γύρο ομοσπονδιακής ψηφοφορίας. Το πρωτόκολλο συναίνεσης Stellar συνδυάζει πολλούς από αυτούς τους γύρους για να δημιουργήσει ένα πλήρες σύστημα συναίνεσης.
Stellar Consensus Protocol
Οι δύο πιο σημαντικές ιδιότητες ενός συστήματος συναίνεσης είναι − ασφάλεια и επιβίωση. Ένας αλγόριθμος συναίνεσης είναι "ασφαλής" εάν δεν μπορεί ποτέ να δώσει διαφορετικά αποτελέσματα σε διαφορετικούς συμμετέχοντες (το αντίγραφο της ιστορίας του Μπομπ δεν θα έρχεται ποτέ σε αντίθεση με την Κάρολ). "Βιωσιμότητα" σημαίνει ότι ο αλγόριθμος θα παράγει πάντα ένα αποτέλεσμα, δηλαδή δεν θα κολλάει.
Περιγράφεται η ομοσπονδιακή διαδικασία ψηφοφορίας αβλαβής με την έννοια ότι εάν ένας κόμβος επιβεβαιώσει την τιμή του V, κανένας άλλος κόμβος δεν θα επιβεβαιώσει την άλλη τιμή. Αλλά «δεν θα επιβεβαιώσει άλλη έννοια» δεν σημαίνει ότι θα επιβεβαιώσει απαραίτητα κάτι. Οι συμμετέχοντες μπορούν να ψηφίσουν σε τόσες πολλές διαφορετικές τιμές που τίποτα δεν θα φτάσει το όριο αποδοχής. Αυτό σημαίνει ότι στην ομοσπονδιακή ψηφοφορία δεν υπάρχει επιβίωση.
Το πρωτόκολλο συναίνεσης Stellar χρησιμοποιεί ομοσπονδιακή ψηφοφορία με τρόπο που διασφαλίζει τόσο την ασφάλεια όσο και τη δυνατότητα επιβίωσης. (Οι εγγυήσεις ασφάλειας και επιβίωσης του SCP έχουν ένα θεωρητικό όριο. Ο σχεδιασμός επιλέγει μια πολύ ισχυρή εγγύηση ασφάλειας, θυσιάζοντας έναν μικρό μετριασμό επιβίωσης, αλλά εάν δοθεί αρκετός χρόνος, είναι πολύ πιθανό να επιτευχθεί συναίνεση.) Με λίγα λόγια, η ιδέα είναι να έχουμε πολλαπλές ομοσπονδιακές ψήφους σε πολλαπλές τιμές έως ότου μία από αυτές να περάσει από όλες τις φάσεις ψηφοφορίας SCP που περιγράφονται παρακάτω.
Οι τιμές στις οποίες το SCP επιδιώκει συναίνεση θα μπορούσαν να είναι το ιστορικό συναλλαγών ή μια παραγγελία μεσημεριανού γεύματος ή κάτι άλλο, αλλά είναι σημαντικό να σημειωθεί ότι αυτές δεν είναι οι τιμές που γίνονται αποδεκτές ή επιβεβαιωμένες. Αντίθετα, η ομοσπονδιακή ψηφοφορία γίνεται σύμφωνα με δηλώσεις σχετικά με αυτές τις αξίες.
Οι πρώτοι γύροι της ομοσπονδιακής ψηφοφορίας πραγματοποιούνται στις στάδιο υποψηφιοτήτων (φάση υποψηφιότητας), σε ένα σύνολο δηλώσεων όπως "I nominate V", ίσως για πολλές διαφορετικές τιμές του V. Ο σκοπός της υποψηφιότητας είναι να βρείτε μία ή περισσότερες δηλώσεις που περνούν από αποδοχή και επιβεβαίωση.
Μετά την εύρεση επαληθεύσιμων υποψηφίων, το SCP περνά στη φάση της ψηφοφορίας, όπου ο στόχος είναι να βρεθεί ένα συγκεκριμένο δελτίο (δηλαδή δοχείο για την προτεινόμενη τιμή) και απαρτία που μπορεί να δηλώσει διαπράττω για αυτό (δεσμεύομαι). Εάν μια απαρτία δεσμεύσει ένα ψηφοδέλτιο, η αξία του γίνεται αποδεκτή ως συναίνεση. Αλλά για να μπορέσει ένας κόμβος να ψηφίσει σε μια δέσμευση ψηφοδελτίου, πρέπει πρώτα να επιβεβαιώσει ακύρωση όλα τα ψηφοδέλτια με μικρότερη αντίτιμο. Αυτά τα βήματα - ακύρωση ψηφοδελτίων για να βρεθεί ένα που μπορεί να δεσμευτεί - περιλαμβάνουν πολλούς γύρους ομοσπονδιακής ψηφοφορίας για πολλαπλές αξιώσεις ψηφοδελτίων.
Οι ακόλουθες ενότητες περιγράφουν την υποψηφιότητα και την ψηφοφορία με περισσότερες λεπτομέρειες.
Υποψηφιότητα
Στην αρχή της φάσης υποψηφιότητας, κάθε κόμβος μπορεί να επιλέξει αυθόρμητα μια τιμή για το V και να ψηφίσει υπέρ της δήλωσης "I nominate V". Ο στόχος σε αυτό το στάδιο είναι να επιβεβαιωθεί ο διορισμός κάποιας αξίας μέσω μιας ομοσπονδιακής ψηφοφορίας.
Ίσως αρκετοί κόμβοι ψηφίζουν αρκετά διαφορετικές προτάσεις που καμία υποψηφιότητα δεν μπορεί να φτάσει το όριο αποδοχής. Επομένως, εκτός από τη μετάδοση των δικών τους ψήφων υποψηφιοτήτων, οι κόμβοι «αντανακλούν» τις υποψηφιότητες των ομοτίμων τους. Ηχώ σημαίνει ότι εάν ένας κόμβος ψηφίσει για την υποψηφιότητα V, αλλά δει ένα μήνυμα από έναν γείτονα που ψηφίζει για την υποψηφιότητα W, θα ψηφίσει τώρα τόσο για το V όσο και για το W. (Δεν επαναλαμβάνονται όλες οι ψήφοι ομοτίμων κατά την υποψηφιότητα, επειδή αυτό μπορεί να οδηγήσει σε έκρηξη διαφορετικοί υποψήφιοι. Το SCP περιλαμβάνει έναν μηχανισμό για τη ρύθμιση αυτών των ψήφων. Εν ολίγοις, υπάρχει μια φόρμουλα για τον καθορισμό της "προτεραιότητας" ενός ομότιμου από την άποψη ενός κόμβου και αντικατοπτρίζονται μόνο οι ψήφοι των κόμβων υψηλής προτεραιότητας. Όσο μεγαλύτερη είναι η υποψηφιότητα τόσο χαμηλότερο είναι το όριο, οπότε ο κόμβος επεκτείνει το σύνολο ομότιμων των οποίων οι ψήφοι θα αντικατοπτρίζει. Ο τύπος προτεραιότητας περιλαμβάνει τον αριθμό θέσης ως μία από τις εισόδους του, επομένως ένας ομότιμος υψηλής προτεραιότητας για μία θέση μπορεί να είναι ομότιμος χαμηλής προτεραιότητας για άλλο, και το αντίστροφο).
Εννοιολογικά, η υποψηφιότητα είναι παράλληλη, τόσο η V όσο και η W είναι ξεχωριστές ομοσπονδιακές ψήφοι, καθεμία ξεχωριστά ικανή να επιτύχει αποδοχή ή επιβεβαίωση. Στην πράξη, τα μηνύματα πρωτοκόλλου SCP συσκευάζουν αυτές τις μεμονωμένες ψήφους μαζί.
Αν και η ψηφοφορία για την υποψηφιότητα του V είναι μια υπόσχεση ότι δεν θα καταψηφιστεί ποτέ η υποψηφιότητα του V, είναι στο επίπεδο εφαρμογής - σε αυτήν την περίπτωση SCP - που καθορίζεται τι σημαίνει "κατά". Το SCP δεν βλέπει μια δήλωση που να έρχεται σε αντίθεση με την ψηφοφορία "I nominating X", δηλαδή δεν υπάρχει μήνυμα "Im ενάντια στο nominating X", επομένως ο κόμβος μπορεί να ψηφίσει για να ορίσει οποιεσδήποτε τιμές. Πολλές από αυτές τις υποψηφιότητες δεν θα πάνε πουθενά, αλλά τελικά ο κόμβος θα μπορεί να αποδεχτεί ή να επιβεβαιώσει μία ή περισσότερες τιμές. Μόλις επιβεβαιωθεί ένας υποψήφιος, γίνεται υποψήφιος.
Υποψηφιότητα SCP με χρήση ομοσπονδιακής ψηφοφορίας. Μπορεί να υπάρχουν πολλές τιμές «Β» που προβάλλονται από τους ομοτίμους και «αντανακλώνται» από τον κόμβο.
Οι υποψηφιότητες ενδέχεται να οδηγήσουν σε πολλαπλούς επιβεβαιωμένους υποψηφίους. Επομένως, το SCP απαιτεί από το επίπεδο εφαρμογής να παρέχει κάποια μέθοδο συνδυασμού των υποψηφίων σε ένα σύνθετος (σύνθετος). Η μέθοδος σύνδεσης μπορεί να είναι οτιδήποτε. Το κύριο πράγμα είναι ότι εάν αυτή η μέθοδος είναι ντετερμινιστική, τότε κάθε κόμβος θα συνδυάζει τους ίδιους υποψηφίους. Σε ένα σύστημα μεσημεριανής ψηφοφορίας, η «ενοποίηση» μπορεί απλώς να σημαίνει την απόρριψη ενός από τους δύο υποψηφίους. (Αλλά με ντετερμινιστικό τρόπο: κάθε κόμβος πρέπει να επιλέξει την ίδια τιμή για επαναφορά. Για παράδειγμα, η προηγούμενη επιλογή με αλφαβητική σειρά). Στο δίκτυο πληρωμών Stellar, όπου ψηφίζεται το ιστορικό συναλλαγών, η συγχώνευση δύο προτεινόμενων υποψηφίων περιλαμβάνει τη συγχώνευση των συναλλαγών που περιέχουν και της τελευταίας από τις δύο χρονικές σημάνσεις τους.
Η λευκή βίβλος SCP αποδεικνύει (Θεώρημα 12) ότι στο τέλος της φάσης επέκτασης, το δίκτυο συγκλίνει τελικά σε ένα μόνο σύνθετο. Αλλά υπάρχει ένα πρόβλημα: η ομοσπονδιακή ψηφοφορία είναι ένα ασύγχρονο πρωτόκολλο (όπως το SCP). Με άλλα λόγια, οι κόμβοι δεν συντονίζονται από το χρόνο, αλλά μόνο από τα μηνύματα που στέλνουν. Από την άποψη του κόμβου, δεν είναι σαφές πότε τελείωσε φάση επέκτασης. Και παρόλο που όλοι οι κόμβοι θα φτάσουν τελικά στο ίδιο σύνθετο, μπορεί να ακολουθήσουν διαφορετικές διαδρομές στην πορεία, δημιουργώντας διαφορετικούς σύνθετους υποψηφίους στην πορεία και δεν μπορούν ποτέ να πουν ποιος είναι ο τελικός.
Αλλά είναι φυσιολογικό. Η υποψηφιότητα είναι απλώς προετοιμασία. Το κύριο πράγμα είναι να περιοριστεί ο αριθμός των υποψηφίων για να επιτευχθεί συναίνεση, η οποία προκύπτει στη διαδικασία ψηφοφορία (ψηφοφορία).
Τρέξιμο
Το Bulletin είναι ζευγάρι , όπου ο μετρητής είναι ένας ακέραιος αριθμός που ξεκινά από το 1 και η τιμή είναι υποψήφιος από το στάδιο υποψηφιότητας. Αυτό μπορεί να είναι ο υποψήφιος ενός κόμβου ή ο υποψήφιος ενός γειτονικού κόμβου που γίνεται αποδεκτός από αυτόν τον κόμβο. Σε γενικές γραμμές, μια ψηφοφορία περιλαμβάνει επανειλημμένες προσπάθειες για να εξαναγκάσει το δίκτυο να επιτύχει συναίνεση για κάποιον υποψήφιο σε κάποιο ψηφοδέλτιο κρατώντας δυνητικά πολλές ομοσπονδιακές ψηφοφορίες στις δηλώσεις ψηφοδελτίων. Οι μετρητές στα ψηφοδέλτια παρακολουθούν τις προσπάθειες που έγιναν και τα ψηφοδέλτια με υψηλότερα ψηφοδέλτια υπερισχύουν έναντι των ψηφοδελτίων με μικρότερη καταμέτρηση. Αν το ενημερωτικό δελτίο κολλάει, ξεκινά μια νέα ψηφοφορία, τώρα στο ψηφοδέλτιο .
Είναι σημαντικό να γίνει διάκριση τιμές (για παράδειγμα, ποια πρέπει να είναι η παραγγελία του μεσημεριανού γεύματος: πίτσα ή σαλάτες), ενημερωτικά δελτία (ζεύγος αντιτιμητικής) και δηλώσεις σχετικά με τα ψηφοδέλτια. Ο γύρος SCP περιλαμβάνει αρκετούς γύρους ομοσπονδιακής ψηφοφορίας, ιδίως για τις ακόλουθες δηλώσεις:
- «Είμαι έτοιμος να δεσμεύσω το ψηφοδέλτιο Β» και
- «Ανακοινώνω τη δέσμευση του ψηφοδελτίου Β»
Από την οπτική γωνία ενός δεδομένου κόμβου, η συναίνεση επιτυγχάνεται όταν βρίσκει ένα ψηφοδέλτιο Β για το οποίο μπορεί να επιβεβαιώσει (δηλαδή να βρει απαρτία αποδοχής) τη δήλωση "Δεσμεύω το ψηφοδέλτιο Β". Από αυτό το σημείο και μετά, είναι ασφαλές να ενεργήσετε με βάση την τιμή που καθορίζεται στο B - για παράδειγμα, κάνοντας αυτήν την παραγγελία για μεσημεριανό γεύμα. Ονομάζεται εξωτερίκευση νοήματα. Μόλις επιβεβαιωθεί η αποδοχή του ψηφοδελτίου, ένας κόμβος μπορεί να είναι σίγουρος ότι οποιοσδήποτε άλλος κόμβος έχει εξωτερικεύσει την ίδια τιμή ή θα το κάνει στο μέλλον.
Αν και πολλές ομοσπονδιακές ψηφοφορίες διενεργούνται εννοιολογικά για αξιώσεις για πολλά διαφορετικά ψηφοδέλτια, δεν ανταλλάσσουν τόσα πολλά μηνύματα επειδή κάθε μήνυμα περιλαμβάνει έναν αριθμό ψηφοδελτίων. Ένα μήνυμα προωθεί έτσι την κατάσταση πολλών ομοσπονδιακών ψήφων ταυτόχρονα, για παράδειγμα: «Δέχομαι τη δέσμευση ψηφοδελτίων που κυμαίνονται από πριν "
Τι σημαίνουν οι όροι «προετοιμασμένος» και «δέσμευση»;
Ένας κόμβος ψηφίζει για τη δέσμευση ενός ψηφοδελτίου όταν είναι βέβαιος ότι άλλοι κόμβοι δεν θα δεσμεύσουν ψηφοδέλτια με διαφορετικές τιμές. Πειστικός αυτός είναι ο σκοπός της προετοιμασίας της αίτησης. Μια ψηφοφορία που λέει "Είμαι έτοιμος να δεσμεύσω το ψηφοδέλτιο Β" είναι μια υπόσχεση να μην δεσμεύσω ποτέ ένα ψηφοδέλτιο μικρότερο από το Β, δηλαδή με μικρότερο αριθμό (το SCP απαιτεί οι τιμές στα ψηφοδέλτια να είναι σε μια συγκεκριμένη σειρά. Έτσι, ενημερωτικό δελτίο πιο λιγο , εάν N1
Γιατί το «Είμαι έτοιμος να δεσμεύσω το ψηφοδέλτιο Β» σημαίνει «Υπόσχομαι να μην δεσμεύσω ποτέ ψηφοδέλτια μικρότερα από το Β»; Επειδή το SCP ορίζει το abort ως το αντίθετο του commit. Η ψηφοφορία για την προετοιμασία ενός ψηφοδελτίου περιλαμβάνει επίσης ψηφοφορία για τον αποκλεισμό ορισμένων άλλων ψηφοδελτίων και, όπως συζητήσαμε νωρίτερα, η ψηφοφορία για ένα πράγμα είναι μια υπόσχεση να μην καταψηφιστεί ποτέ.
Πριν από τη μετάδοση μιας δέσμευσης, ένας κόμβος πρέπει πρώτα να βρει ένα δελτίο που μπορεί να επιβεβαιώσει ως προετοιμασμένο. Με άλλα λόγια, εκτελεί μια ομοσπονδιακή ψηφοφορία στο θέμα «Είμαι έτοιμος να δεσμεύσω το ψηφοδέλτιο Β», πιθανώς σε πολλά διαφορετικά ψηφοδέλτια, μέχρι να βρει ένα που δέχεται απαρτία.
Από πού προέρχονται τα ψηφοδέλτια για την προετοιμασία της ψηφοφορίας; Πρώτον, ο κόμβος εκπέμπει προετοιμασίες για να ψηφίσει το <1,C>, όπου το C είναι ο σύνθετος υποψήφιος που παράγεται στο στάδιο της υποψηφιότητας. Ωστόσο, ακόμη και μετά την έναρξη των προετοιμασιών για την ψηφοφορία, οι υποψηφιότητες ενδέχεται να οδηγήσουν σε πρόσθετους υποψηφίους που εμφανίζονται ως νέα ψηφοδέλτια. Εν τω μεταξύ, οι ομότιμοι μπορούν να έχουν διαφορετικούς υποψηφίους και μπορούν να σχηματίσουν ένα σύνολο αποκλεισμού που αποδέχεται το "Είμαι έτοιμος να δεσμεύσω το ψηφοδέλτιο Β2", το οποίο θα πείσει τον κόμβο να το αποδεχθεί επίσης. Τέλος, υπάρχει ένας μηχανισμός χρονικού ορίου που δημιουργεί νέους γύρους ομοσπονδιακής ψηφοφορίας για νέα ψηφοδέλτια με υψηλότερη καταμέτρηση εάν τα τρέχοντα ψηφοδέλτια έχουν κολλήσει.
Μόλις ο κόμβος βρει ένα ψηφοδέλτιο Β το οποίο μπορεί να επιβεβαιώσει ως προετοιμασμένο, εκπέμπει ένα νέο μήνυμα «Διαθέστε το ψηφοδέλτιο Β». Αυτή η ψηφοφορία λέει στους συνομηλίκους ότι ο κόμβος δεν θα εγκαταλείψει ποτέ το Β. Στην πραγματικότητα, εάν το Β είναι ψηφοδέλτιο , στη συνέχεια «Δέσμευση ψηφοδελτίου " σημαίνει την ανεπιφύλακτη συγκατάθεση για ψήφο για την ετοιμότητα κάθε ψηφοδελτίου από σε <∞, s>. Αυτή η πρόσθετη τιμή βοηθά άλλους ομότιμους να καλύψουν τη διαφορά του ομότιμου δέσμευσης εάν βρίσκονται ακόμα σε προηγούμενα στάδια του πρωτοκόλλου.
Σε αυτό το στάδιο, αξίζει να τονίσουμε για άλλη μια φορά ότι πρόκειται για ασύγχρονα πρωτόκολλα. Ακριβώς επειδή ένας κόμβος στέλνει θετικές ψήφους για μια δέσμευση δεν σημαίνει ότι κάνουν και οι όμοιοί του. Μερικοί από αυτούς μπορεί να εξακολουθούν να ψηφίζουν δηλώσεις στο πλαίσιο της προετοιμασίας για ψηφοφορία, άλλοι μπορεί να έχουν ήδη εξωτερικεύσει το νόημα. Το SCP εξηγεί πώς ένας κόμβος πρέπει να επεξεργάζεται κάθε τύπο ομότιμου μηνύματος ανεξάρτητα από τη φάση του.
Εάν εμφανίζεται το μήνυμα «Έχω ανακοινώσει μια δέσμευση » δεν μπορεί να ληφθεί ή να επιβεβαιωθεί, δηλαδή η πιθανότητα αποδοχής ή επιβεβαίωσης του μηνύματος ή - ή, σε κάθε περίπτωση, οποιοδήποτε ψηφοδέλτιο με την τιμή C, και όχι οποιοδήποτε άλλο, αφού ο κόμβος έχει ήδη υποσχεθεί ότι δεν θα ακυρώσει ποτέ . Μέχρι τη στιγμή που ένας κόμβος εκπέμπει ψήφους υπέρ μιας δέσμευσης, θα είναι C ή τίποτα, ανάλογα με το πόσο μακριά φτάνει η συναίνεση. Ωστόσο, αυτό δεν είναι ακόμα αρκετό για τον κόμβο να εξωτερικεύσει τον C. Ορισμένοι βυζαντινοί όμοιοι (οι οποίοι αποτελούν λιγότερο από απαρτία, με βάση τις υποθέσεις ασφαλείας μας) μπορεί να ψεύδονται στον κόμβο. Η αποδοχή και στη συνέχεια η επιβεβαίωση κάποιου ψηφοδελτίου (ή μιας σειράς ψηφοδελτίων) είναι αυτό που δίνει στον κόμβο τη σιγουριά να εξωτερικεύσει τελικά το C.
Ψηφοφορία SCP μέσω ομοσπονδιακής ψηφοφορίας. Δεν εμφανίζεται: Ο χρονοδιακόπτης μπορεί να σβήσει ανά πάσα στιγμή, αυξάνοντας την καταμέτρηση στο ψηφοδέλτιο (και πιθανώς δημιουργώντας ένα νέο σύνθετο από πρόσθετους υποψηφίους).
Και είναι όλο! Μόλις το δίκτυο καταλήξει σε συναίνεση, είναι έτοιμο να το κάνει ξανά και ξανά. Στο δίκτυο πληρωμών Stellar, αυτό συμβαίνει περίπου μία φορά κάθε 5 δευτερόλεπτα: ένα κατόρθωμα που απαιτεί τόσο την ασφάλεια όσο και τη δυνατότητα επιβίωσης που εγγυάται το SCP.
Το SCP μπορεί να το επιτύχει αυτό βασιζόμενος σε πολλαπλούς γύρους ομοσπονδιακής ψηφοφορίας. Η ομοσπονδιακή ψηφοφορία καθίσταται δυνατή από την έννοια των τμημάτων απαρτίας: σύνολα ομότιμων που κάθε κόμβος έχει αποφασίσει να εμπιστευτεί ως μέρος της (υποκειμενικής) απαρτίας του. Αυτή η διαμόρφωση σημαίνει ότι η συναίνεση μπορεί να επιτευχθεί ακόμη και σε ένα δίκτυο με ανοιχτά μέλη και βυζαντινές απάτες.
Περαιτέρω ανάγνωση
- Μπορείτε να βρείτε την αρχική λευκή βίβλο SCP Και σχέδιο προδιαγραφών για την εφαρμογή του.
- Ο αρχικός συγγραφέας του πρωτοκόλλου SCP, David Mazier, το εξηγεί με απλοποιημένο (αλλά και πάλι τεχνικό) τρόπο. .
- Ίσως εκπλαγείτε που δεν βρήκατε τους όρους «εξόρυξη» ή «απόδειξη εργασίας» σε αυτό το άρθρο. Το SCP δεν χρησιμοποιεί αυτές τις μεθόδους, αλλά ορισμένοι άλλοι αλγόριθμοι συναίνεσης κάνουν. Ο Ζέιν Γουίδερσπουν έγραψε προσβάσιμος .
- ένα απλό δίκτυο που επιτυγχάνει συναίνεση σε έναν πλήρη γύρο SCP.
- Για αναγνώστες που ενδιαφέρονται για υλοποιήσεις SCP: βλ , που χρησιμοποιείται από το δίκτυο πληρωμών Stellar ή , το οποίο έγραψα για καλύτερη κατανόηση του SCP.
Πηγή: www.habr.com