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

Κατά την κατασκευή μιας νέας συναλλαγής, ένα πορτοφόλι Monero παραπέμπει σε μια προηγούμενη έξοδο που έλαβε ο χρήστης σε μια προηγούμενη συναλλαγή και τη χρησιμοποιεί ως είσοδο στη νέα συναλλαγή. Σήμερα, το πορτοφόλι αναμειγνύει αυτή την έξοδο με ένα σύνολο 10 εξόδων δόλωμα που επιλέγονται από τις συναλλαγές άλλων ατόμων από όλο το blockchain (υπογραφή δακτυλίου). Έτσι, ένας παρατηρητής δεν μπορεί να καταλάβει ποια από τις 11 συνολικά εξόδους είναι η πραγματική που δαπανά ένας χρήστης σε μια συναλλαγή, συσκοτίζοντας τη σύνδεση από τη νέα συναλλαγή του χρήστη με την προηγούμενη συναλλαγή του. Ο αλγόριθμος επιλογής δολωμάτων χειρίζεται ειδικά τη διαδικασία επιλογής για την επιλογή των δολωμάτων με τα οποία θα αναμειχθούν οι πραγματικές εκροές κατά την κατασκευή μιας συναλλαγής.

Μεταξύ των εκδόσεων Monero v0.14.1.0 και v0.17.2.2, ο βασικός κώδικας του πορτοφολιού είχε δύο σφάλματα στον αλγόριθμο επιλογής δόλωμα που επηρέαζαν την ιδιωτικότητα των χρηστών του Monero:

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

Και τα δύο έχουν επιδιορθωθεί στην έκδοση v0.17.2.3 και συνιστάται ιδιαίτερα να αναβαθμίσετε το συντομότερο δυνατό.

Οι χρήστες θα πρέπει επίσης να γνωρίζουν ότι οι επιπτώσεις του πρώτου σφάλματος δεν είναι τόσο σοβαρές όσο είχε αναφερθεί προηγουμένως. Δημοσιοποιήθηκε ευρέως ότι, ως αποτέλεσμα του πρώτου σφάλματος, ορισμένες πολύ πρόσφατα δαπανημένες εκροές που παρατηρήθηκαν στην αλυσίδα ήταν εγγυημένα αναγνωρίσιμες ως πραγματικές εκροές που δαπανήθηκαν σε μια συναλλαγή, ωστόσο, αυτό δεν ισχύει στην πραγματικότητα. Μετά τη δημοσίευση, μάθαμε ότι τουλάχιστον ένα δημοφιλές light πορτοφόλι (MyMonero) χρησιμοποιεί μια ξεχωριστή υλοποίηση του αλγορίθμου επιλογής δόλωμα που δεν είχε το σφάλμα. Ως εκ τούτου, οι χρήστες του MyMonero θα μπορούσαν εφικτά να έχουν κατασκευάσει συναλλαγές που επέλεγαν τις πρόσφατα δαπανήσιμες εκροές ως δόλωμα, πράγμα που σημαίνει ότι οι πρόσφατα δαπανήσιμες εκροές που παρατηρήθηκαν στην αλυσίδα δεν ήταν εγγυημένα αναγνωρίσιμες ως πραγματικές εκροές.

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

Τεχνικές εξηγήσεις

Εσφαλμένη εφαρμογή του αλγορίθμου (σφάλμα 1)

Ο αλγόριθμος επιλογής δολώματος έχει σχεδιαστεί για να επιλέγει εξόδους από όλο το blockchain με βάση τα παρατηρούμενα μοτίβα δαπανών, όπως συνιστάται στους Möser et al. Η ανάλυση του εγγράφου χρησιμοποιεί μοτίβα δαπανών από προηγούμενες εκδόσεις του Monero - όπου σε ορισμένες περιπτώσεις, οι πραγματικές έξοδοι που χρησιμοποιήθηκαν στις συναλλαγές μπορούσαν να εξαχθούν με βεβαιότητα - προκειμένου να καταλήξει σε μια κατανομή των μοτίβων δαπανών των χρηστών του Monero. Το έγγραφο υπογραμμίζει ότι οι χρήστες ήταν πιο πιθανό να ξοδέψουν τις εκροές που έλαβαν σχετικά γρήγορα από ό,τι ήταν να ξοδέψουν τις εκροές που κρατούσαν για μεγάλο χρονικό διάστημα. Στη συνέχεια, το έγγραφο συνιστά να λαμβάνονται υπόψη τα παρατηρούμενα μοτίβα δαπανών κατά την επιλογή εξόδων από όλο το blockchain για χρήση ως δόλωμα, αντί να εφαρμόζεται ίση πιθανότητα σε ολόκληρο το σύνολο των εξόδων από όλο το blockchain. Με αυτόν τον τρόπο, οι νεότερες εκροές θα είναι πιο πιθανό να επιλεγούν ως δόλωμα από ό,τι οι παλαιότερες εκροές, συσκοτίζοντας έτσι καλύτερα ποια εκροή είναι πραγματική στις συναλλαγές των χρηστών.

Όταν η σύσταση της δημοσίευσης εφαρμόστηκε για πρώτη φορά στο Monero v0.13.0.0, το πορτοφόλι εφάρμοσε σωστά το παρατηρούμενο μοτίβο δαπανών από την άκρη του blockchain κατά την επιλογή δολωμάτων. Ωστόσο, όταν ο αλγόριθμος αναβαθμίστηκε στην έκδοση v0.14.1.0, ο αλγόριθμος εφάρμοσε το παρατηρούμενο μοτίβο δαπανών από 10 μπλοκ πριν από την άκρη της αλυσίδας. Αυτό έγινε επειδή οι έξοδοι ηλικίας μικρότερης των 10 μπλοκ είναι κλειδωμένες και δεν μπορούν να ξοδευτούν, επομένως φαινόταν λογικό να εφαρμοστεί η κατανομή ξεκινώντας 10 μπλοκ πριν από την άκρη της αλυσίδας, ώστε να λαμβάνονται υπόψη μόνο οι έξοδοι που μπορούν να ξοδευτούν. Ωστόσο, η εφαρμογή κατέληξε να αγνοεί ορισμένες πολύ πρόσφατες δαπανήσιμες εξόδους για να ληφθούν υπόψη ως δόλωμα. Επιπλέον, ο αλγόριθμος επέλεξε οριακά λιγότερες εξόδους δόλωμα ηλικίας περίπου 10 έως 20 μπλοκ.

Αυτό το σφάλμα διορθώθηκε στο PR #7821.

Διαιρέστε με το 0 (σφάλμα 2)

Η αναβάθμιση του αλγορίθμου επιλογής δολωμάτων στην έκδοση v0.14.1.0 συνυπολόγισε τη διακύμανση του μεγέθους των μπλοκ, προκειμένου να ταιριάζει καλύτερα με τα μοτίβα δαπανών και να μειώσει τη μεροληψία προς την επιλογή εξόδων coinbase ως δολώματα. Κατά την επιλογή ενός δολώματος, ο αλγόριθμος καθορίζει πρώτα την ηλικία σε δευτερόλεπτα που θα πρέπει να είναι η έξοδος δολώματος (χρησιμοποιώντας την κατανομή των γνωστών μοτίβων δαπανών, όπως αναφέρθηκε παραπάνω). Στη συνέχεια, ο αλγόριθμος διαιρεί την αναμενόμενη ηλικία εξόδου σε δευτερόλεπτα με τον μέσο όρο των δευτερολέπτων που απέχουν μεταξύ κάθε εξόδου που παρατηρείται κατά το έτος που ακολουθεί, προκειμένου να καταλήξει στην έξοδο της αλυσίδας που θα πρέπει να χρησιμοποιηθεί ως δόλωμα. Εάν ο αριθμός των εξόδων σε ένα έτος είναι ισοδύναμος με τον αριθμό των δευτερολέπτων σε ένα έτος, τότε ο μέσος όρος των δευτερολέπτων μεταξύ κάθε εξόδου κατά τη διάρκεια του έτους είναι 1.

Ο υπολογισμός του μέσου όρου των δευτερολέπτων ανά έξοδο είχε ένα σφάλμα που έκοβε το αποτέλεσμα. Εάν ο μέσος όρος δευτερολέπτων ανά έξοδο έπεφτε κάτω από το 1, το αποτέλεσμα θα περικόπτονταν στο 0. Όταν ο αλγόριθμος διαιρεί την αναμενόμενη ηλικία εξόδου σε δευτερόλεπτα με το 0, καταλήγει να επιλέγει δόλωμα αποκλειστικά από το πιο πρόσφατο μπλοκ που μπορεί να ξοδευτεί στα περισσότερα συστήματα. Έτσι, εάν ο όγκος των εξόδων αυξανόταν σημαντικά κατά τη διάρκεια μιας συνεχούς περιόδου, έτσι ώστε τα δευτερόλεπτα που μεσολαβούν μεταξύ κάθε εξόδου κατά το έτος που ακολουθεί να πέσουν κάτω από το 1 (δηλαδή ο αριθμός των εξόδων κατά το έτος που ακολουθεί να υπερβαίνει τον αριθμό των δευτερολέπτων σε ένα έτος), τότε ο αλγόριθμος θα επέλεγε δόλωμα από το πιο πρόσφατο αναλώσιμο μπλοκ στη συντριπτική πλειονότητα των περιπτώσεων. Κατά τη στιγμή της παρούσας δημοσίευσης, ο μέσος όρος δευτερολέπτων ανά έξοδο είναι περίπου 1,7.

Αυτό το σφάλμα διαίρεσης με το 0 διορθώθηκε στο PR #7845.

Συμπέρασμα

Οι εργασίες για τη βελτίωση του αλγορίθμου επιλογής δολωμάτων συνεχίζονται. Έχει περιθώρια βελτίωσης ώστε να παρέχει ισχυρότερη προστασία στους χρήστες σε ένα ευρύτερο σύνολο περιστάσεων. Ένα κάλεσμα στα όπλα: οποιοσδήποτε με υπόβαθρο στη στατιστική και τη θεωρία πιθανοτήτων ενθαρρύνεται να συμμετάσχει στις συζητήσεις που αποσκοπούν στη βελτίωση του αλγορίθμου. Οι συζητήσεις γίνονται συχνά στα κανάλια IRC/Matrix #monero-research-lab και #monero-dev. Ενώ η καινοτόμος έρευνα για τη βελτίωση της κρυπτογραφίας του Monero συνεχίζεται παράλληλα, προκειμένου να αυξηθεί σημαντικά ο αριθμός των δολωμάτων που αναμειγνύονται με πραγματικές εξόδους σε μια συναλλαγή (δηλαδή να αυξηθεί το μέγεθος του δακτυλίου), η έρευνα για τη βελτίωση των τεχνικών στατιστικής απόκρυψης του αλγορίθμου επιλογής δολωμάτων λαμβάνει επίσης μεγαλύτερη προσοχή. Εάν αισθάνεστε ότι διαθέτετε τις απαιτούμενες δεξιότητες, να έχετε κατά νου ότι υπάρχει αυξανόμενο ενδιαφέρον από την κοινότητα του Monero να σας προσλάβει ενεργά στο έργο Monero. Αν ενδιαφέρεστε, σκεφτείτε να επικοινωνήσετε με μια ομάδα εργασίας του Monero.

Πρωτότυπο Άρθρο (Αγγλική): Post-Mortem of Decoy Selection Bugs

Συντάκτης Πρωτότυπου Άρθρου: Justin Berman (j-berman)

Ημερομηνία Συγγραφής Πρωτότυπου Άρθρου: 20 Σεπτεμβρίου 2021