Δέντρα Merkle: Πώς το blockchain θυμάται κάθε note

Πρωτότυπη έρευνα από Annkkitaaa

Σύνοψη εκατομμυρίων commitments σε ένα μικροσκοπικό αποτύπωμα

Σειρά: Zcash από τις πρώτες αρχές . Άρθρο 4 . Δέντρα Merkle Κοινό: νέοι χρήστες. Βασιζόμαστε στο Άρθρο 3 (hashing και commitments). Αν ξέρεις τι είναι ένα αποτύπωμα και ένα commitment, είσαι έτοιμος. Τι θα αποκομίσεις: μια διαισθητική και σωστή εικόνα των δέντρων Merkle, πώς να αποδεικνύεις συμμετοχή χωρίς να αποκαλύπτεις ποιο στοιχείο εννοείς και ακριβώς πώς αυτό γίνεται το δέντρο note commitments του Zcash.

Το Άρθρο 0 περιέγραψε έναν «δημόσιο πίνακα» που περιέχει κάθε note που έχει ποτέ δημιουργηθεί και συνεχώς μεγαλώνει. Μέχρι τώρα μπορείς να μαντέψεις τι είναι καρφιτσωμένο σε αυτόν: commitments (Άρθρο 3), οι σφραγισμένοι φάκελοι. Όμως ένας πραγματικός πίνακας θα περιείχε εκατοντάδες εκατομμύρια από αυτά. Πώς το δίκτυο τα αποθηκεύει, τα επαληθεύει και σου επιτρέπει να αποδείξεις ότι ο φάκελός σου βρίσκεται στον πίνακα χωρίς να τον υποδείξεις; Η απάντηση είναι μία από τις πιο κομψές δομές στην επιστήμη υπολογιστών: το δέντρο Merkle.

1. Γιατί πρέπει να σε ενδιαφέρει;

Δύο προβλήματα εμφανίζονται μόλις έχεις μια τεράστια δημόσια λίστα commitments.

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

Πρόβλημα δεύτερο: ιδιωτική συμμετοχή. Για να ξοδέψεις ένα note (Άρθρο 0), πρέπει να αποδείξεις ότι το commitment σου βρίσκεται πράγματι στον πίνακα. Όμως αν το υποδείξεις («είναι η καταχώριση αριθμός 4.201.337!»), μόλις έχεις αποκαλύψει την ταυτότητά σου. Πρέπει να αποδείξεις «ο φάκελός μου βρίσκεται κάπου σε αυτόν τον πίνακα» χωρίς να αποκαλύψεις ποιος είναι.

Ένα δέντρο Merkle λύνει και τα δύο ταυτόχρονα. Συμπιέζει ολόκληρη τη λίστα σε ένα μοναδικό αποτύπωμα και σου επιτρέπει να αποδείξεις συμμετοχή με μια μικροσκοπική απόδειξη που κρύβει τη θέση.

2. Η διαίσθηση: ένα τουρνουά αποτυπωμάτων

Φαντάσου ένα ταμπλό τουρνουά νοκ άουτ, αλλά αντί να προκρίνονται παίκτες, συνδυάζονται αποτυπώματα.

• Στο κάτω μέρος, κάθε στοιχείο δεδομένων αποκτά το δικό του αποτύπωμα (το hash του από το Άρθρο 3). Αυτά είναι τα φύλλα.
• Βάλ’ τα σε ζεύγη. Τα δύο αποτυπώματα κάθε ζεύγους γίνονται hash μαζί σε ένα γονικό αποτύπωμα.
• Βάλε σε ζεύγη τους γονείς, κάνε hash κάθε ζεύγος μαζί και συνέχισε έτσι.
• Συνέχισε μέχρι ένα μοναδικό αποτύπωμα να βρίσκεται στην κορυφή. Αυτός ο πρωταθλητής είναι η ρίζα Merkle.

Η σημαντικότερη ιδιότητα προκύπτει άμεσα από το φαινόμενο χιονοστιβάδας (Άρθρο 3):

Η ρίζα είναι ένα αποτύπωμα όλων όσων βρίσκονται από κάτω της. Άλλαξε οποιοδήποτε φύλλο, έστω και κατά ένα bit, και αλλάζει το αποτύπωμά του, που αλλάζει τον γονέα του, που αλλάζει εκείνον τον γονέα, μέχρι την κορυφή. Η ρίζα αλλάζει. Άρα μία μικρή τιμή ρίζας πιστοποιεί την ακεραιότητα ολόκληρης της λίστας. Αυτό λύνει το Πρόβλημα πρώτο.

3. Ένα πραγματικό δέντρο, υπολογισμένο ακριβώς

Ας δημιουργήσουμε το παραπάνω δέντρο τεσσάρων φύλλων με πραγματικά αποτυπώματα SHA-256 πάνω στα φύλλα A, B, C, D (τα digests εμφανίζονται περικομμένα για ευκολότερη ανάγνωση):

hA = 559aead08264...     hB = df7e70e50215...
hC = 6b23c0d5f35d...     hD = 3f39d5c348e5...

hAB = H(hA , hB) = 63956f0ce48e...
hCD = H(hC , hD) = 98a2fbfddbc7...

ROOT = H(hAB , hCD) = 1b3faa3fcc5e...

Όλα είναι απλώς «κάνε hash ένα πράγμα και μετά κάνε hash ζεύγη από hashes». Τίποτα πιο εξωτικό από το Άρθρο 3, απλώς οργανωμένο σε δέντρο.

4. Το έξυπνο μέρος: απόδειξη συμμετοχής χωρίς αποκάλυψη θέσης

Τώρα το Πρόβλημα δεύτερο. Ας πούμε ότι θέλεις να αποδείξεις πως το φύλλο C βρίσκεται στο δέντρο, σε κάποιον που γνωρίζει μόνο τη ρίζα. Δεν του παραδίδεις ολόκληρο το δέντρο. Του δίνεις μόνο τα αποτυπώματα που χρειάζονται για να ανέβεις από το C στη ρίζα, τα οποία ονομάζονται διαδρομή αυθεντικοποίησης (ή απόδειξη Merkle):

Για να αποδείξεις ότι το C βρίσκεται στο δέντρο, παρείχε:

• το αδελφό του hD, και
• τον θείο του hAB.

Ο επαληθευτής, γνωρίζοντας μόνο τη ρίζα, επανυπολογίζει την ανάβαση:

step 1:  H(hC , hD)        = hCD       (combine C with its sibling)
step 2:  H(hAB , hCD)      = ROOT?     (combine with the uncle)

Υπολογισμένο πραγματικά: αυτό δίνει το 1b3faa3fcc5e..., το οποίο ταιριάζει με τη ρίζα. Το φύλλο αποδεικνύεται ότι βρίσκεται στο δέντρο.

Δύο πράγματα το καθιστούν ισχυρό:

• Είναι μικροσκοπικό. Για 4 φύλλα παρείχες 2 hashes. Για ένα δέντρο με n φύλλα, παρέχεις μόνο περίπου log_2(n) hashes. Για ένα δισεκατομμύριο φύλλα, αυτό είναι περίπου 30 hashes, όχι ένα δισεκατομμύριο. Η απόδειξη σχεδόν δεν μεγαλώνει καθώς το δέντρο εκρήγνυται σε μέγεθος.
• Είναι ο σπόρος της ιδιωτικότητας. Η απόδειξη δείχνει ότι το φύλλο σου βρίσκεται κάπου στο δέντρο. Όταν ο ίδιος έλεγχος εκτελείται μέσα σε μια απόδειξη μηδενικής γνώσης (Άρθρο 5), ακόμη και η ίδια η διαδρομή κρύβεται, οπότε αποδεικνύεις «το note μου βρίσκεται στο δέντρο» χωρίς να αποκαλύπτεις ούτε το note ούτε τη θέση του. Αυτό λύνει πλήρως το Πρόβλημα δεύτερο.

5. Από ένα δέντρο Merkle στο δέντρο note commitments του Zcash

Τώρα μπορούμε να δηλώσουμε με ακρίβεια τι είναι πραγματικά ο «δημόσιος πίνακας» του Άρθρου 0:

Το δέντρο note commitments είναι ένα δέντρο Merkle του οποίου τα φύλλα είναι note commitments. Κάθε φορά που δημιουργείται ένα note οπουδήποτε στον κόσμο, το commitment του προστίθεται ως το επόμενο φύλλο και η ρίζα ενημερώνεται.

Μερικές πραγματικές λεπτομέρειες:

• Μόνο μεγαλώνει. Φύλλα προστίθενται, ποτέ δεν αφαιρούνται. Αυτό ονομάζεται αυξητικό δέντρο Merkle. (Αντιστοιχεί στο «ο πίνακας δεν αφαιρεί ποτέ τίποτα» του Άρθρου 0.)
• Η ρίζα ονομάζεται anchor. Όταν ξοδεύεις, η συναλλαγή σου αναφέρεται σε ένα πρόσφατο anchor και αποδεικνύει, με μηδενική γνώση, ότι το commitment του note σου βρίσκεται στο δέντρο με αυτή τη ρίζα.
• Σταθερό βάθος. Τα θωρακισμένα δέντρα του Zcash έχουν βάθος 32, που σημαίνει ότι μπορούν να περιέχουν έως 2^(32) (πάνω από τέσσερα δισεκατομμύρια) notes.
• Hashing φιλικό προς ZK. Το δέντρο δεν δημιουργείται με SHA-256. Το Sapling κάνει hash στο δέντρο με Pedersen hashes και το Orchard χρησιμοποιεί Sinsemilla (και τα δύο από το Άρθρο 3), ακριβώς ώστε η ανάβαση συμμετοχής να αποδεικνύεται οικονομικά μέσα σε ένα κύκλωμα.

Ένα πράγμα που το δέντρο δεν χειρίζεται: διπλές δαπάνες

Το δέντρο αποδεικνύει ότι ένα note υπάρχει. Δεν σε εμποδίζει από μόνο του να ξοδέψεις το ίδιο note δύο φορές. Αυτή η δουλειά ανήκει στο σύνολο nullifier από το Άρθρο 0: μια ξεχωριστή συλλογή από «token ακύρωσης». Όταν ξοδεύεις, δημοσιεύεις το nullifier του note και το δίκτυο απορρίπτει κάθε nullifier που έχει ξαναδεί.

Άρα οι δύο δημόσιες δομές παίζουν συμπληρωματικούς ρόλους και το να παραμένουν χωριστές είναι ακριβώς αυτό που διακόπτει τον σύνδεσμο ανάμεσα στη γέννηση και τον θάνατο ενός note:

6. Μια ειλικρινής διευκρίνιση

Απλοποιήσεις, όπως συνήθως. Τα πραγματικά αυξητικά δέντρα Merkle παρακολουθούν κόμβους «frontier», ώστε η ρίζα να μπορεί να ενημερώνεται χωρίς να ξαναδημιουργούνται όλα· το δίκτυο διατηρεί ένα παράθυρο πρόσφατων anchors, όχι μόνο το νεότερο, ώστε τα πορτοφόλια να μη χαλούν με κάθε νέο μπλοκ· και τα κενά φύλλα χρησιμοποιούν μια καθορισμένη τιμή συμπλήρωσης. Επίσης σχεδιάσαμε δυαδικά δέντρα με τακτοποιημένες δυνάμεις του δύο. Τίποτα από αυτά δεν αλλάζει τη διαίσθηση: φύλλα από commitments, που γίνονται hash ανά ζεύγη μέχρι μία ρίζα, με σύντομες αποδείξεις συμμετοχής. Η ακριβής λογιστική επιστρέφει στο άρθρο του πρωτοκόλλου.

7. Σύνοψη

• Ένα δέντρο Merkle κάνει hash δεδομένα σε φύλλα, έπειτα κάνει hash ζεύγη προς τα πάνω μέχρι να απομείνει μία ρίζα.
• Χάρη στο φαινόμενο χιονοστιβάδας, η ρίζα είναι αποτύπωμα ολόκληρης της λίστας: άλλαξε ένα φύλλο και η ρίζα αλλάζει. Μία μικρή τιμή πιστοποιεί ένα τεράστιο σύνολο δεδομένων.
• Μια απόδειξη συμμετοχής (διαδρομή αυθεντικοποίησης) είναι απλώς τα αδελφά hashes κατά την ανάβαση προς τη ρίζα, περίπου log_2(n) hashes, επομένως οι αποδείξεις παραμένουν μικροσκοπικές ακόμη και για δισεκατομμύρια φύλλα.
• Όταν εκτελείται μέσα σε μια απόδειξη μηδενικής γνώσης, αυτός ο έλεγχος συμμετοχής κρύβει ποιο φύλλο εννοείς, αποδεικνύοντας «το note μου βρίσκεται στο δέντρο» χωρίς να αποκαλύπτει το note ή τη θέση του.
• Το δέντρο note commitments του Zcash είναι ένα αυξητικό δέντρο Merkle από note commitments, βάθους 32, του οποίου η ρίζα είναι το anchor· το Sapling κάνει hash με Pedersen και το Orchard με Sinsemilla.
• Το δέντρο αποδεικνύει ύπαρξη· το ξεχωριστό σύνολο nullifier αποτρέπει διπλές δαπάνες. Η διατήρησή τους χωριστά είναι αυτό που αποσυνδέει τη γέννηση ενός note από τον θάνατό του.

Γλωσσάρι

Συχνές ερωτήσεις

Γιατί δέντρο και όχι απλώς μια μεγάλη λίστα hashes; Μια επίπεδη λίστα θα σε ανάγκαζε να αποκαλύψεις ή να επεξεργαστείς κάθε καταχώριση για να αποδείξεις συμμετοχή. Ένα δέντρο σου δίνει αποδείξεις λογαριθμικού μεγέθους και μία μοναδική ρίζα για ακεραιότητα.

Χρειάζεται ο επαληθευτής ολόκληρο το δέντρο; Όχι. Ο επαληθευτής χρειάζεται μόνο τη ρίζα μαζί με τη σύντομη διαδρομή αυθεντικοποίησής σου. Αυτό είναι όλο το νόημα.

Γιατί βάθος 32 συγκεκριμένα; Περιορίζει το δέντρο σε περίπου τέσσερα δισεκατομμύρια notes, που προσφέρει άφθονο περιθώριο, ενώ διατηρεί την απόδειξη συμμετοχής (και το κόστος της μέσα στο κύκλωμα) σε σταθερό και διαχειρίσιμο μέγεθος.

Αν η ρίζα αλλάζει με κάθε νέο note, πώς παραμένουν έγκυρες οι παλιές αποδείξεις; Το δίκτυο θυμάται ένα παράθυρο πρόσφατων ριζών (anchors), επομένως μια απόδειξη που δημιουργήθηκε απέναντι σε ένα ελαφρώς παλαιότερο anchor εξακολουθεί να επαληθεύεται. Το άρθρο του πρωτοκόλλου το κάνει ακριβές.

Δοκίμασε τη διαίσθησή σου

Στο δέντρο μας με 4 φύλλα, ας υποθέσουμε ότι ένας επιτιθέμενος αντικαθιστά κρυφά το φύλλο C με διαφορετική τιμή, αλλά αφήνει τη δημοσιευμένη ρίζα αμετάβλητη. Τι πάει στραβά γι’ αυτόν και γιατί δεν μπορεί να το διορθώσει αθόρυβα; (Απάντηση παρακάτω.)

Τι ακολουθεί

Άρθρο 5 . Αποδείξεις μηδενικής γνώσης: η κορύφωση. Τώρα έχουμε δημιουργήσει notes, commitments και το δέντρο, και συνεχίζουμε να λέμε «αποδεικνύεται με μηδενική γνώση». Το Άρθρο 5 εξηγεί επιτέλους πώς μπορείς να αποδείξεις ότι μια δήλωση είναι αληθής, ότι το note σου βρίσκεται στο δέντρο, ότι το nullifier σου είναι σωστό και ότι τα χρήματα ισοσκελίζονται, χωρίς να αποκαλύπτεις τίποτα από αυτά.

Μέρος της σειράς Zcash από τις πρώτες αρχές για το ZecHub. Με άδεια CC BY-SA 4.0.