Τα Merkle Trees είναι ένα θεμελιώδες συστατικό των blockchain που υποστηρίζουν τη λειτουργικότητά τους. Επιτρέπουν την αποτελεσματική και ασφαλή επαλήθευση μεγάλων δομών δεδομένων και, στην περίπτωση των blockchains, δυνητικά απεριόριστων συνόλων δεδομένων.
Η εφαρμογή των δέντρων Merkle σε blockchains έχει πολλαπλά αποτελέσματα. Τους επιτρέπει να κλιμακώνονται ενώ παρέχει επίσης την αρχιτεκτονική που βασίζεται σε κατακερματισμό για να διατηρούν την ακεραιότητα των δεδομένων και έναν ασήμαντο τρόπο επαλήθευσης της ακεραιότητας των δεδομένων.
Οι κρυπτογραφικές συναρτήσεις κατακερματισμού είναι η υποκείμενη τεχνολογία που επιτρέπει στα δέντρα Merkle να λειτουργούν, επομένως πρώτα, είναι σημαντικό να κατανοήσουμε ποιες είναι οι κρυπτογραφικές συναρτήσεις κατακερματισμού.
Γρήγορη ετυμηγορία: Τα δέντρα Merkle είναι δομές δεδομένων που αποτελούνται από κρυπτογραφικούς κατακερματισμούς που επιτρέπουν αποτελεσματική επαλήθευση ακεραιότητας και χαρτογράφηση μεγάλων συνόλων δεδομένων, καθιστώντας τα αναπόσπαστο στοιχείο συστημάτων όπως οι αλυσίδες μπλοκ και ο έλεγχος κατανεμημένων εκδόσεων.
Γρήγορα γεγονότα
| Βασικά σημεία | Περιγραφή |
|---|---|
| Κρυπτογραφικές συναρτήσεις κατακερματισμού | Συναρτήσεις κατακερματισμού που λαμβάνουν μια είσοδο οποιουδήποτε μεγέθους και εξάγουν μια τιμή κατακερματισμού σταθερού μήκους. Χρησιμοποιείται σε δέντρα Merkle. |
| δομή δέντρου merkle | Δομή δεδομένων δέντρου όπου κάθε κόμβος χωρίς φύλλα είναι ένας κατακερματισμός των θυγατρικών κόμβων του. Επιτρέπει την αποτελεσματική χαρτογράφηση και επαλήθευση μεγάλων συνόλων δεδομένων. |
| Κατακερματισμός ρίζας | Κατακερματισμός στην κορυφή του δέντρου Merkle που αντιπροσωπεύει τον κατακερματισμό ολόκληρου του δέντρου. Λειτουργεί ως δακτυλικό αποτύπωμα για το πλήρες σύνολο δεδομένων. |
| Merkle αποδείξεις | Επιτρέψτε την επαλήθευση της ακεραιότητας των δεδομένων και της θέσης στο δέντρο χωρίς να χρειάζεται το πλήρες σύνολο δεδομένων, μόνο κατακερματισμός ρίζας. |
| Εφαρμογή στο Bitcoin | Τα δέντρα Merkle αποθηκεύουν συναλλαγές σε μπλοκ. Ο κατακερματισμός ρίζας που είναι αποθηκευμένος στην κεφαλίδα μπλοκ επιτρέπει στους κόμβους SPV να επαληθεύουν τις συναλλαγές. |
| Άλλες υλοποιήσεις blockchain | Χρησιμοποιείται σε πολλά blockchain όπως το Ethereum που χρησιμοποιεί πιο πολύπλοκα Merkle Patricia Trees. |
| Κατανεμημένα συστήματα | Επιτρέψτε σε συστήματα ελέγχου έκδοσης όπως το Git και το IPFS να επαληθεύουν εύκολα τα δεδομένα που μοιράζονται μεταξύ ομοτίμων. |
Συναρτήσεις κρυπτογραφικού κατακερματισμού
Με απλά λόγια, συνάρτηση κατακερματισμού είναι οποιαδήποτε συνάρτηση που χρησιμοποιείται για την αντιστοίχιση δεδομένων αυθαίρετου μεγέθους (εισόδου) σε έξοδο σταθερού μεγέθους. Ένας αλγόριθμος κατακερματισμού εφαρμόζεται στην είσοδο δεδομένων και η προκύπτουσα έξοδος σταθερού μήκους αναφέρεται ως κατακερματισμός.
Πολλοί αλγόριθμοι κατακερματισμού είναι ευρέως διαθέσιμοι στο κοινό και μπορούν να επιλεγούν με βάση τις ανάγκες σας.
Ο κατακερματισμός που προκύπτει από την αυθαίρετη είσοδο δεν είναι μόνο σταθερός σε μήκος, είναι επίσης εντελώς μοναδικός για την είσοδο και η ίδια η συνάρτηση είναι ντετερμινιστική. Δηλαδή, όσες φορές κι αν εκτελείτε τη συνάρτηση στην ίδια είσοδο, η έξοδος θα είναι πάντα η ίδια.
Για παράδειγμα, εάν έχετε τα ακόλουθα σύνολα δεδομένων παρακάτω ως είσοδο, οι προκύπτουσες έξοδοι είναι μοναδικές για κάθε είσοδο. Παρατηρήστε πώς στο δεύτερο και τρίτο παράδειγμα, παρόλο που η διαφορά των εισόδων είναι μόνο μία λέξη, οι προκύπτουσες έξοδοι είναι τελείως διαφορετικές.
Αυτό είναι πολύ σημαντικό καθώς επιτρέπει την «δακτυλική λήψη» δεδομένων.
Μια κρυπτογραφική συνάρτηση κατακερματισμού, εικόνα από τη Wikipedia
Δεδομένου ότι το μήκος εξόδου (άθροισμα κατακερματισμού στο παράδειγμα) είναι πάντα το ίδιο με αυτό που καθορίζεται από τον αλγόριθμο κατακερματισμού που χρησιμοποιείται, τεράστιες ποσότητες δεδομένων μπορούν να εντοπιστούν αποκλειστικά μέσω του κατακερματισμού που προκύπτει.
Με συστήματα που περιέχουν τεράστιες ποσότητες δεδομένων, τα οφέλη από τη δυνατότητα αποθήκευσης και αναγνώρισης δεδομένων με έξοδο σταθερού μήκους μπορούν να δημιουργήσουν τεράστια εξοικονόμηση αποθήκευσης και να συμβάλουν στην αύξηση της αποδοτικότητας.
Εντός των blockchain, χρησιμοποιούνται αλγόριθμοι κατακερματισμού για τον προσδιορισμό της κατάστασης του blockchain.
Οι αλυσίδες μπλοκ είναι συνδεδεμένες λίστες που περιέχουν δεδομένα και έναν δείκτη κατακερματισμού που δείχνει στο προηγούμενο μπλοκ, δημιουργώντας μια αλυσίδα από συνδεδεμένα μπλοκ, εξ ου και το όνομα "blockchain".
Κάθε μπλοκ συνδέεται μεταξύ τους μέσω ενός δείκτη κατακερματισμού, ο οποίος είναι ο κατακερματισμός των δεδομένων μέσα στο προηγούμενο μπλοκ μαζί με τη διεύθυνση του προηγούμενου μπλοκ. Συνδέοντας μπλοκ δεδομένων σε αυτή τη μορφή, κάθε κατακερματισμός που προκύπτει από το προηγούμενο μπλοκ αντιπροσωπεύει ολόκληρη την κατάσταση της αλυσίδας μπλοκ, αφού όλα τα κατακερματισμένα δεδομένα των προηγούμενων μπλοκ κατακερματίζονται σε ένα κατακερματισμό.
Αυτό αντιπροσωπεύεται (στην περίπτωση του αλγόριθμου SHA-256) από μια έξοδο (hash) όπως αυτή:
b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7
Το παραπάνω hash είναι το δακτυλικό αποτύπωμα ολόκληρης της κατάστασης του blockchain πριν από αυτό. Η κατάσταση της αλυσίδας μπλοκ πριν από το νέο μπλοκ (ως κατακερματισμένα δεδομένα) είναι η είσοδος και ο κατακερματισμός που προκύπτει είναι η έξοδος.
Παρόλο που είναι δυνατή η χρήση κρυπτογραφικών κατακερματισμών χωρίς δέντρα Merkle, είναι εξαιρετικά αναποτελεσματικό και μη επεκτάσιμο. Η χρήση κατακερματισμών για την αποθήκευση δεδομένων σε ένα μπλοκ σε μορφή σειράς είναι χρονοβόρα και δυσκίνητη.
Όπως θα δείτε, τα δέντρα Merkle επιτρέπουν την ασήμαντη ανάλυση της ακεραιότητας των δεδομένων καθώς και την αντιστοίχιση αυτών των δεδομένων σε ολόκληρο το δέντρο χρησιμοποιώντας αποδείξεις Merkle.
Merkle Trees και Merkle Proofs
Πήρε το όνομά του από τον Ralph Merkle, ο οποίος κατοχύρωσε την ιδέα το 1979, τα δέντρα Merkle είναι βασικά δέντρα δομών δεδομένων όπου κάθε κόμβος χωρίς φύλλα είναι ένας κατακερματισμός των αντίστοιχων θυγατρικών κόμβων του.
Οι κόμβοι φύλλων είναι η χαμηλότερη βαθμίδα κόμβων στο δέντρο. Στην αρχή, μπορεί να ακούγεται δύσκολο να γίνει κατανοητό, αλλά αν κοιτάξετε την εικόνα που χρησιμοποιείται συνήθως παρακάτω, θα γίνει πολύ πιο κατανοητό.
Ένα παράδειγμα δυαδικού δέντρου κατακερματισμού, Εικόνα από τη Wikipedia
Είναι σημαντικό, παρατηρήστε πώς οι μη-φύλλοι κόμβοι ή «κλαδιά» (που αντιπροσωπεύονται από Hash 0-0 και Hash 0-1) στην αριστερή πλευρά, είναι κατακερματισμοί των αντίστοιχων παιδιών τους L1 και L2. Επιπλέον, παρατηρήστε πώς ο κατακερματισμός διακλάδωσης 0 είναι ο κατακερματισμός των συνδεόμενων παιδιών του, διακλαδίζει τον κατακερματισμό 0-0 και τον κατακερματισμό 0-1.
Το παραπάνω παράδειγμα είναι η πιο κοινή και απλή μορφή ενός δέντρου Merkle που είναι γνωστό ως Binary Merkle Tree. Όπως μπορείτε να δείτε, υπάρχει ένα top hash που είναι ο κατακερματισμός ολόκληρου του δέντρου, γνωστός ως hash ρίζας. Ουσιαστικά, τα δέντρα Merkle είναι μια δομή δεδομένων που μπορεί να λάβει «n» αριθμό κατακερματισμών και να τον αναπαραστήσει με έναν μόνο κατακερματισμό.
Η δομή του δέντρου επιτρέπει την αποτελεσματική αντιστοίχιση αυθαίρετα μεγάλων ποσοτήτων δεδομένων και επιτρέπει τον εύκολο εντοπισμό του πού συμβαίνουν αλλαγές σε αυτά τα δεδομένα. Αυτή η ιδέα επιτρέπει τις αποδείξεις Merkle, με τις οποίες κάποιος μπορεί να επαληθεύσει ότι ο κατακερματισμός των δεδομένων είναι συνεπής μέχρι το δέντρο και στη σωστή θέση χωρίς να χρειάζεται να κοιτάξει πραγματικά ολόκληρο το σύνολο των κατακερματισμών.
Αντίθετα, μπορούν να επαληθεύσουν ότι ένα κομμάτι δεδομένων είναι συνεπές με τον κατακερματισμό ρίζας ελέγχοντας μόνο ένα μικρό υποσύνολο των κατακερματισμών και όχι ολόκληρο το σύνολο δεδομένων.
Εφόσον ο κατακερματισμός ρίζας είναι δημόσια γνωστός και αξιόπιστος, είναι δυνατό για οποιονδήποτε θέλει να πραγματοποιήσει αναζήτηση κλειδιού-τιμής σε μια βάση δεδομένων να χρησιμοποιήσει μια απόδειξη Merkle για να επαληθεύσει τη θέση και την ακεραιότητα ενός τμήματος δεδομένων σε μια βάση δεδομένων που έχει μια συγκεκριμένη ρίζα.
Όταν ο κατακερματισμός ρίζας είναι διαθέσιμος, το δέντρο κατακερματισμού μπορεί να ληφθεί από οποιαδήποτε μη αξιόπιστη πηγή και ένας κλάδος του δέντρου μπορεί να ληφθεί κάθε φορά με άμεση επαλήθευση της ακεραιότητας των δεδομένων, ακόμα κι αν ολόκληρο το δέντρο δεν είναι ακόμη διαθέσιμο.
Ένα από τα πιο σημαντικά οφέλη της δομής δέντρου Merkle είναι η δυνατότητα ελέγχου ταυτότητας αυθαίρετα μεγάλων συνόλων δεδομένων μέσω ενός παρόμοιου μηχανισμού κατακερματισμού που χρησιμοποιείται για την επαλήθευση πολύ μικρότερων ποσοτήτων δεδομένων.
Το δέντρο είναι πλεονεκτικό για τη διανομή μεγάλων συνόλων δεδομένων σε διαχειρίσιμα μικρότερα μέρη όπου το εμπόδιο για την επαλήθευση της ακεραιότητας μειώνεται σημαντικά παρά το συνολικό μεγαλύτερο μέγεθος δεδομένων.
Το root hash μπορεί να χρησιμοποιηθεί ως δακτυλικό αποτύπωμα για ένα ολόκληρο σύνολο δεδομένων, συμπεριλαμβανομένης μιας ολόκληρης βάσης δεδομένων ή αντιπροσωπεύοντας ολόκληρη την κατάσταση μιας αλυσίδας μπλοκ. Στις επόμενες ενότητες, θα συζητήσουμε πώς το Bitcoin και άλλα συστήματα εφαρμόζουν τα δέντρα Merkle.
Merkle Trees σε Bitcoin
Η κρυπτογραφική συνάρτηση κατακερματισμού που χρησιμοποιείται από το Bitcoin είναι ο αλγόριθμος SHA-256. Αυτό σημαίνει "Ασφαλής αλγόριθμος κατακερματισμού", του οποίου η έξοδος είναι σταθερό μήκος 256 bit. Η βασική λειτουργία των δέντρων Merkle στο Bitcoin είναι η αποθήκευση και τελικά το κλάδεμα συναλλαγών σε κάθε μπλοκ.
Όπως αναφέρθηκε προηγουμένως, τα μπλοκ σε μια αλυσίδα μπλοκ συνδέονται μέσω κατακερματισμών του προηγούμενου μπλοκ. Στο Bitcoin, κάθε μπλοκ περιέχει όλες τις συναλλαγές εντός αυτού του μπλοκ καθώς και την κεφαλίδα του μπλοκ που αποτελείται από:
- Αποκλεισμός αριθμού έκδοσης
- Προηγούμενος κατακερματισμός αποκλεισμού
- Timestamp
- Στόχος Δυσκολίας Εξόρυξης
- Nonce
- Merkle Root Hash
Η παρακάτω εικόνα είναι από τη λευκή βίβλο του Bitcoin και δείχνει πώς το δέντρο Merkle ταιριάζει σε κάθε μπλοκ.
Οι συναλλαγές περιλαμβάνονται σε μπλοκ από τους εξορύκτες και κατακερματίζονται ως μέρος ενός δέντρου Merkle, οδηγώντας στη ρίζα Merkle που αποθηκεύεται στην κεφαλίδα μπλοκ. Αυτός ο σχεδιασμός έχει μια σειρά από ξεχωριστά πλεονεκτήματα.
Πιο συγκεκριμένα, όπως περιγράφεται στη λευκή βίβλο, αυτό επιτρέπει την ύπαρξη κόμβων Επαλήθευσης Απλής Πληρωμής (SPV), γνωστών επίσης ως «ελαφροί πελάτες». Αυτοί οι κόμβοι δεν χρειάζεται να κατεβάσουν ολόκληρη την αλυσίδα μπλοκ Bitcoin, μόνο τις κεφαλίδες μπλοκ της μεγαλύτερης αλυσίδας.
Οι κόμβοι SPV μπορούν να το επιτύχουν αυτό ρωτώντας τους ομοτίμους κόμβους τους μέχρι να πειστούν ότι οι αποθηκευμένες κεφαλίδες μπλοκ στις οποίες λειτουργούν αποτελούν μέρος της μεγαλύτερης αλυσίδας. Ένας κόμβος SPV μπορεί στη συνέχεια να προσδιορίσει την κατάσταση μιας συναλλαγής χρησιμοποιώντας την απόδειξη Merkle για να αντιστοιχίσει τη συναλλαγή σε ένα συγκεκριμένο δέντρο Merkle με τον κατακερματισμό ρίζας του αντίστοιχου δέντρου Merkle σε μια κεφαλίδα μπλοκ που είναι μέρος της μεγαλύτερης αλυσίδας.
Επιπλέον, η εφαρμογή των δέντρων Merkle από το Bitcoin επιτρέπει το κλάδεμα του blockchain προκειμένου να εξοικονομηθεί χώρος. Αυτό είναι αποτέλεσμα της αποθήκευσης μόνο του κατακερματισμού ρίζας στην κεφαλίδα του μπλοκ, επομένως, τα παλιά μπλοκ μπορούν να κλαδευτούν αφαιρώντας τα περιττά κλαδιά του δέντρου Merkle διατηρώντας μόνο αυτά που χρειάζονται για την απόδειξη Merkle.
Εφαρμογή Merkle Trees σε άλλα Blockchains και συστήματα
Αν και το Bitcoin ήταν το πρώτο blockchain που εφάρμοσε τα Merkle trees, πολλά άλλα blockchain εφαρμόζουν παρόμοιες δομές Merkle δέντρων ή ακόμα πιο περίπλοκες εκδόσεις.
Επιπλέον, η εφαρμογή Merkle tree δεν περιορίζεται μόνο σε blockchains και εφαρμόζεται σε μια ποικιλία άλλων συστημάτων.
Το Ethereum, που είναι το άλλο πιο αναγνωρίσιμο κρυπτονόμισμα, είναι επίσης ένα εξαιρετικό παράδειγμα μιας διαφορετικής υλοποίησης δέντρου Merkle. Επειδή το Ethereum είναι ολοκληρωμένο ως πλατφόρμα για τη δημιουργία πολύ πιο περίπλοκων εφαρμογών, χρησιμοποιεί μια πιο σύνθετη έκδοση του δέντρου Merkle που ονομάζεται Merkle Patricia Tree και είναι στην πραγματικότητα 3 ξεχωριστά δέντρα Merkle που χρησιμοποιούνται για τρία είδη αντικειμένων. Μπορείτε να μάθετε περισσότερα για αυτά τα δέντρα εδώ.
Τέλος, τα δέντρα Merkle είναι σημαντικό συστατικό των κατανεμημένων συστημάτων ελέγχου εκδόσεων όπως το Git και το IPFS. Η ικανότητά τους να διασφαλίζουν και να επαληθεύουν εύκολα την ακεραιότητα των δεδομένων που μοιράζονται μεταξύ υπολογιστών σε μορφή P2P τα καθιστά ανεκτίμητα για αυτά τα συστήματα.
Συμπέρασμα
Τα δέντρα Merkle αποτελούν αναπόσπαστο στοιχείο των blockchain και τους επιτρέπουν αποτελεσματικά να λειτουργούν με αποδεδειγμένη αμετάβλητη και ακεραιότητα συναλλαγών.
Η κατανόηση του ρόλου που διαδραματίζουν στα κατανεμημένα δίκτυα και η υποκείμενη τεχνολογία κρυπτογραφικών συναρτήσεων κατακερματισμού είναι ζωτικής σημασίας για την κατανόηση των βασικών εννοιών στα κρυπτονομίσματα καθώς συνεχίζουν να εξελίσσονται σε μεγαλύτερα και πιο σύνθετα συστήματα.
Πηγή: https://blockonomi.com/merkle-tree/