Μέτρηση της απόδοσης του SNARK: Frontends, backends και το μέλλον

Το SNARK (Συνοπτικά μη διαδραστικά επιχειρήματα γνώσης) είναι μια σημαντική κρυπτογραφική πρωτόγονη εφαρμογή εύρεσης για την επεκτασιμότητα της αλυσίδας μπλοκ (π.χ. συνάθροιση L2) και το απόρρητο. Τα SNARK επιτρέπουν σε κάποιον να αποδείξει σε έναν αναξιόπιστο επαληθευτή V (π.χ. το blockchain Ethereum) ότι γνωρίζουν κάποια δεδομένα (π.χ. μια παρτίδα έγκυρων συναλλαγών). Ένας αφελής τρόπος για να αποδειχθεί αυτό θα ήταν να στείλετε τα δεδομένα σε V, ο οποίος μπορεί στη συνέχεια να ελέγξει απευθείας την εγκυρότητά του. Ένα SNARK πετυχαίνει το ίδιο, αλλά με καλύτερο κόστος V. Συγκεκριμένα, μια απόδειξη SNARK θα πρέπει να είναι συντομότερη από την αφελή που περιλαμβάνει τα ίδια τα δεδομένα. (Για περισσότερες λεπτομέρειες, δείτε το προσχέδιο του σχολικού μου βιβλίου, Αποδείξεις, Επιχειρήματα και Μηδενική Γνώση. Για μια εισαγωγή στα SNARKs, δείτε το Sarah Meicklejohn's παρουσίαση στο a16z crypto Θερινή Ερευνητική Σειρά.)

Το κόστος επαλήθευσης για τα SNARK μπορεί να ποικίλλει, αλλά είναι καλά κατανοητό και συχνά αρκετά καλό. Για παράδειγμα, Πέφτω οι αποδείξεις κοστίζουν περίπου Αέριο 290,000 για επαλήθευση στο Ethereum, ενώ οι αποδείξεις του StarkWare κοστίζουν περίπου 5 εκατομμύρια αέριο. Τα SNARK είναι δυνητικά εφαρμόσιμα σε διαφορετικές ρυθμίσεις, ακόμη και εκτός των blockchains — για παράδειγμα, επιτρέποντας τη χρήση γρήγορων αλλά αναξιόπιστων διακομιστές και υλικού. 

Ωστόσο, επειδή η επαλήθευση SNARK είναι συνήθως φθηνή, οι κύριοι καθοριστικοί παράγοντες της δυνατότητας εφαρμογής είναι το κόστος του SNARK prover P. Σε αυτήν την ανάρτηση, εξηγώ πώς να υπολογίσετε αυτά τα κόστη για να καθορίσετε πότε είναι λογικό να χρησιμοποιείτε SNARK και πώς τα SNARK ενδέχεται να βελτιωθούν στο μέλλον. Αξίζει να σημειωθεί ότι πρόκειται για έναν χώρο που κινείται γρήγορα και αρκετά από τα έργα που συζητούνται σε αυτήν την ανάρτηση βελτιώνουν ενεργά την απόδοσή τους.

Αλλά πρώτα: Πώς αναπτύσσονται τα SNARK

Στην ανάπτυξη SNARK, ένας προγραμματιστής συνήθως γράφει ένα πρόγραμμα υπολογιστή ψ που παίρνει ως είσοδο τα δεδομένα w που ο πάρεργος ισχυρίζεται ότι ξέρει (w σημαίνει μάρτυρας), και το ελέγχει w είναι έγκυρο. Για παράδειγμα, σε συνάθροιση, το πρόγραμμα θα ελέγχει ότι όλες οι συναλλαγές γίνονται w είναι ψηφιακά υπογεγραμμένα, μην κάνετε τα υπόλοιπα λογαριασμού να πέφτουν κάτω από το μηδέν και ούτω καθεξής. Το πρόγραμμα ψ στη συνέχεια τροφοδοτείται μέσω α SNARK frontend που το μεταγλωττίζει σε μια μορφή που είναι πιο επιδεκτική στην εφαρμογή της τεχνολογίας SNARK. Αυτή η φιλική προς το SNARK μορφή ονομάζεται an ενδιάμεση αναπαράσταση (IR). 

Συνήθως, το IR είναι κάποιο είδος στιγμιότυπου ικανοποίησης κυκλώματος που ισοδυναμεί με ψ. Αυτό σημαίνει ότι το κύκλωμα C παίρνει ως είσοδο τα δεδομένα w, καθώς και ορισμένες επιπλέον εισόδους που συνήθως ονομάζονται "μη ντετερμινιστικές συμβουλές" και εκτελέσεις ψ on w. Οι εισροές συμβουλών χρησιμοποιούνται για να βοηθήσουν C τρέξιμο ψ, διατηρώντας C μικρό. Για παράδειγμα, κάθε φορά ψ διαιρεί δύο αριθμούς x και y, το πηλίκο q και το υπόλοιπο r μπορεί να παρέχεται ως συμβουλή σε C, να C μπορεί απλά να το ελέγξει x = qy + r. Αυτή η επιταγή είναι λιγότερο δαπανηρή από την πραγματοποίηση C εκτελέστε έναν αλγόριθμο διαίρεσης για να υπολογίσετε q και r από την αρχή.

Τέλος, εφαρμόζεται ένα SNARK για ικανοποίηση κυκλώματος C. Αυτό ονομάζεται το SNARK backend. Για μια χούφτα εξαιρετικά δομημένων προβλημάτων όπως π.χ πολλαπλασιασμός μήτρας, συνελίξεις, να πολλά προβλήματα γραφημάτων, υπάρχουν γνωστά SNARK που αποφεύγουν αυτό το παράδειγμα frontend/backend και έτσι επιτυγχάνουν έναν πολύ πιο γρήγορο prover. Αλλά η εστίαση αυτής της ανάρτησης είναι σε SNARK γενικής χρήσης.

Όπως θα δούμε, το κόστος prover του backend SNARK αυξάνεται με C'μικρό Μέγεθος. Τήρηση C Το μικρό μπορεί να είναι δύσκολο, επειδή τα κυκλώματα είναι μια εξαιρετικά περιορισμένη μορφή για την έκφραση ενός υπολογισμού. Αποτελούνται από πύλες, συνδεδεμένο από σύρματα. Κάθε πύλη g τροφοδοτείται με κάποιες τιμές και εφαρμόζει α πολύ απλή συνάρτηση σε αυτές τις τιμές. Το αποτέλεσμα στη συνέχεια τροφοδοτείται σε πύλες «κατάντη» μέσω των καλωδίων που προέρχονται από g.

Επεκτασιμότητα SNARK: Πόσος χρόνος χρειάζεται πραγματικά;

Το βασικό ερώτημα είναι, Πόσος περισσότερος χρόνος χρειάζεται το SNARK prover, σε σχέση με την απλή επανεκτέλεση ψ στα δεδομένα; Η απάντηση είναι η επιβαρύνοντας το prover του SNARK, σε σχέση με άμεσος έλεγχος μαρτύρων. Η τελευταία έκφραση αναφέρεται στο γεγονός ότι, στην αφελή απόδειξη στην οποία P αποστέλλει w προς την V, V έλεγχοι wτης εγκυρότητας με την εκτέλεση ψ σε αυτό. 

Είναι χρήσιμο να σπάσετε τα γενικά έξοδα του prover σε "επιβάρυνση frontend" και "backend overhead". Εάν αξιολογείται το κύκλωμα C πύλη-πύλη είναι F φορές πιο ακριβό από το τρέξιμο ψ, τότε λέμε ότι το frontend overhead είναι F. Εάν εφαρμόζεται το backend prover σε C is B φορές πιο ακριβό από την αξιολόγηση C gate-by-gate, τότε λέμε ότι το backend overhead είναι B. Το συνολικό κόστος του prover είναι το προϊόν, F·B. Αυτό το πολλαπλασιαστικό γενικό κόστος μπορεί να είναι σημαντικό ακόμα κι αν F και B είναι ατομικά μετριοπαθείς. 

Στην πράξη, F και B μπορεί και τα δύο να είναι περίπου 1000 ή μεγαλύτερα. Αυτό σημαίνει ότι η συνολική επιβάρυνση prover σε σχέση με τον άμεσο έλεγχο μαρτύρων μπορεί να είναι 1 εκατομμύριο έως 10 εκατομμύρια ή περισσότερο. Ένα πρόγραμμα που εκτελείται μόνο για ένα δευτερόλεπτο σε φορητό υπολογιστή μπορεί εύκολα να οδηγήσει σε έναν prover SNARK που απαιτεί δεκάδες ή εκατοντάδες ημέρες υπολογιστικού χρόνου (μονό νήμα). Ευτυχώς, αυτή η εργασία είναι τυπικά παραλληλιζόμενη σε διάφορους βαθμούς (ανάλογα με το SNARK). 

Συνοπτικά, εάν θέλετε να χρησιμοποιήσετε ένα SNARK σε μια εφαρμογή σήμερα, τότε ένα από τα τρία πράγματα πρέπει να ισχύει:

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

TΤο υπόλοιπο αυτής της ανάρτησης εξηγεί από πού προέρχονται τα γενικά έξοδα frontend και backend και πώς τα υπολογίζω για διαφορετικά SNARK. Στη συνέχεια θα στραφούμε σε προοπτικές βελτίωσης. 

Διαχωρισμός frontends και backends

Ο πλήρης διαχωρισμός των frontends από τα backends μπορεί να είναι δύσκολος επειδή διαφορετικά backend υποστηρίζουν διαφορετικά είδη κυκλωμάτων. Ως εκ τούτου, τα frontends μπορεί να διαφέρουν ανάλογα με το backend με το οποίο αναμένουν να συνδεθούν.

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

Τα περισσότερα backend υποστηρίζουν πραγματικά μια γενίκευση αριθμητικών κυκλωμάτων που συχνά ονομάζονται περιπτώσεις ικανοποίησης περιορισμού κατάταξης (R1CS). Με την αξιοσημείωτη εξαίρεση του Groth16 και των προκατόχων τους, αυτά τα SNARK μπορούν να κατασκευαστούν για να υποστηρίζουν και άλλα IR. Για παράδειγμα, το StarkWare χρησιμοποιεί κάτι που ονομάζεται Αλγεβρική Ενδιάμεση Αναπαράσταση (AIR), η οποία είναι επίσης παρόμοια με μια έννοια που ονομάζεται Αριθμητισμός PlonKish που μπορεί να υποστηριχθεί από το PlonK και άλλα backend. Η ικανότητα ορισμένων backends να υποστηρίζουν πιο γενικά IR μπορεί να μειώσει τα γενικά έξοδα των frontends που παράγουν αυτά τα IR. 

Τα backends ποικίλλουν επίσης ως προς τα πεπερασμένα πεδία που υποστηρίζουν εγγενώς. Θα το συζητήσω περαιτέρω στην επόμενη ενότητα.

Διάφορες προσεγγίσεις στα frontends

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

Μια δημοφιλής προσέγγιση frontend είναι η παραγωγή κυκλωμάτων που ουσιαστικά εκτελούν βήμα-βήμα κάποια απλή CPU, που ονομάζεται επίσης εικονική μηχανή (VM). Οι σχεδιαστές Frontend καθορίζουν ένα σύνολο «πρωτόγονων λειτουργιών» ανάλογες με τις οδηγίες συναρμολόγησης για πραγματικούς επεξεργαστές υπολογιστών. Οι προγραμματιστές που θέλουν να χρησιμοποιήσουν το frontend θα γράφουν είτε "προγράμματα ελέγχου μαρτύρων" απευθείας στη γλώσσα assembly ή σε κάποια γλώσσα υψηλότερου επιπέδου όπως η Solidity και τα προγράμματά τους θα μεταγλωττίζονται αυτόματα σε κώδικα συναρμολόγησης. 

Για παράδειγμα, του StarkWare Κάιρο είναι μια πολύ περιορισμένη γλώσσα συναρμολόγησης στην οποία οι οδηγίες συναρμολόγησης επιτρέπουν χονδρικά την πρόσθεση και τον πολλαπλασιασμό σε ένα πεπερασμένο πεδίο, την κλήση συνάρτησης και την ανάγνωση και εγγραφή σε μια αμετάβλητη (δηλαδή, εγγραφή μία φορά) μνήμη. Το Cairo VM είναι μια αρχιτεκτονική von Neumann, που σημαίνει ότι τα κυκλώματα που παράγονται από το frontend λαμβάνουν ουσιαστικά ένα πρόγραμμα του Cairo ως δημόσια είσοδο και «τρέχουν» το πρόγραμμα στον μάρτυρα. Η γλώσσα του Καΐρου είναι η Turing Complete — παρά το περιορισμένο σύνολο εντολών της, μπορεί να προσομοιώσει περισσότερες τυπικές αρχιτεκτονικές, αν και αυτό μπορεί να είναι ακριβό. Το frontend του Καΐρου ενεργοποιεί τα προγράμματα του Καΐρου T πρωτόγονες οδηγίες σε αυτό που ονομάζεται «πτυχίο-2 ΑΕΡΑ με T σειρές και περίπου 50 στήλες." Τι αυτό ακριβώς σημαίνει δεν είναι σημαντικό για αυτήν τη θέση, αλλά όσον αφορά τους provers SNARK, αυτό αντιστοιχεί σε κυκλώματα με μεταξύ 50 και 100 πύλες για κάθε μία από τις T βήματα της CPU του Καΐρου. 

RISC Μηδέν ακολουθεί παρόμοια προσέγγιση με το Κάιρο, αλλά με την εικονική μηχανή να είναι το λεγόμενο Αρχιτεκτονική RISC-V, μια αρχιτεκτονική ανοιχτού κώδικα με ένα πλούσιο οικοσύστημα λογισμικού που αυξάνεται σε δημοτικότητα. Ως ένα πολύ απλό σύνολο εντολών, ο σχεδιασμός μιας αποτελεσματικής διεπαφής SNARK που να το υποστηρίζει μπορεί να είναι σχετικά έλκιμος (τουλάχιστον σε σχέση με περίπλοκες αρχιτεκτονικές όπως x86 ή ARM). Από τον Μάιο, το RISC Zero γυρίζει προγράμματα εκτέλεσης T πρωτόγονες οδηγίες RISC-V σε AIR βαθμού 5 με 3T σειρές και 160 στήλες. Αυτό αντιστοιχεί σε κυκλώματα με τουλάχιστον 500 πύλες ανά βήμα της CPU RISC-V. Περαιτέρω βελτιώσεις αναμένονται στο εγγύς μέλλον.

Τα διάφορα έργα zkEVM (π.χ. zkSync 2.0, Scroll, zkEVM του Polygon) θεωρούν την εικονική μηχανή (duh) την εικονική μηχανή Ethereum. Η διαδικασία μετατροπής κάθε εντολής EVM σε ένα ισοδύναμο «gadget» (δηλαδή, ένα βελτιστοποιημένο κύκλωμα που υλοποιεί την εντολή) είναι ουσιαστικά περισσότερο εμπλεκόμενη από ό,τι για τις απλούστερες αρχιτεκτονικές Cairo και RISC-V. Για αυτόν και για άλλους λόγους, μερικά από τα έργα zkEVM δεν υλοποιούν απευθείας το σύνολο εντολών EVM, αλλά μεταγλωττίζουν προγράμματα Solidity υψηλού επιπέδου σε άλλες γλώσσες συναρμολόγησης πριν τα μετατρέψουν σε κυκλώματα. Τα αποτελέσματα των επιδόσεων αυτών των έργων εκκρεμούν.

Έργα «εξομοιωτή CPU», όπως το RISC-V και το Cairo παράγουν ένα ενιαίο κύκλωμα που μπορεί να χειριστεί όλα τα προγράμματα στη σχετική γλώσσα συναρμολόγησης. Οι εναλλακτικές προσεγγίσεις είναι «όπως ASIC», παράγοντας διαφορετικά κυκλώματα για διαφορετικά προγράμματα. Αυτή η προσέγγιση που μοιάζει με ASIC μπορεί να αποφέρει μικρότερα κυκλώματα για ορισμένα προγράμματα, ειδικά όταν η εντολή συναρμολόγησης που εκτελεί το πρόγραμμα σε κάθε χρονικό βήμα δεν εξαρτάται από την είσοδο του προγράμματος. Για παράδειγμα, μπορεί δυνητικά να αποφύγει εξ ολοκλήρου την επιβάρυνση του frontend για προγράμματα ευθείας γραμμής, όπως ο πολλαπλασιασμός του απλού πίνακα. Αλλά η προσέγγιση ASIC φαίνεται επίσης πολύ περιορισμένη. Από όσο ξέρω, δεν είναι γνωστό πώς να το χρησιμοποιήσετε για να υποστηρίξετε βρόχους χωρίς προκαθορισμένα όρια επανάληψης. 

Το τελευταίο συστατικό της επιβάρυνσης του frontend προέρχεται από το γεγονός ότι όλα τα SNARK χρησιμοποιούν κυκλώματα που λειτουργούν σε πεπερασμένα πεδία. Η CPU του φορητού υπολογιστή σας μπορεί να πολλαπλασιάσει ή να προσθέσει δύο ακέραιους αριθμούς με μία μόνο εντολή μηχανής. Εάν ένα frontend εξάγει ένα κύκλωμα σε ένα πεδίο αρκετά μεγάλου χαρακτηριστικού, μπορεί ουσιαστικά να προσομοιώσει αυτόν τον πολλαπλασιασμό ή την πρόσθεση μέσω της αντίστοιχης πράξης πεδίου. Ωστόσο, η υλοποίηση της λειτουργίας πεδίου σε μια πραγματική CPU απαιτεί συνήθως πολλές οδηγίες μηχανής (αν και ορισμένοι σύγχρονοι επεξεργαστές έχουν εγγενή υποστήριξη για ορισμένα πεδία). 

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

Υπάρχει μόνο ένα υλοποιημένο SNARK, Brakedown, που υποστηρίζει εγγενώς υπολογισμούς σε αυθαίρετα (αρκετά μεγάλα) πεδία. Μαζί με το απόγονοι, έχει την ταχύτερη γνωστή απόδοση επίδειξης σκυροδέματος ακόμη και σε πεδία που υποστηρίζουν άλλα SNARK, αλλά οι αποδείξεις του είναι επί του παρόντος πολύ μεγάλες για πολλές εφαρμογές blockchain. Πρόσφατη δουλειά επιδιώκει να βελτιώσει το μέγεθος της απόδειξης, αλλά το prover είναι ασυμπτωτικά πιο αργό και εκεί φαίνεται να είναι εμπόδια στην πρακτικότητα.

Ορισμένα έργα έχουν επιλέξει να εργαστούν σε πεδία με ιδιαίτερα γρήγορη αριθμητική. Για παράδειγμα, Plonky2 και άλλοι χρησιμοποιούν ένα πεδίο χαρακτηριστικού 2⁶⁴ - 2³² + 1 γιατί η αριθμητική σε αυτό το πεδίο μπορεί να εφαρμοστεί αρκετές φορές πιο γρήγορα από ό,τι σε λιγότερο δομημένα πεδία. Ωστόσο, η χρήση ενός τόσο μικρού χαρακτηριστικού μπορεί να οδηγήσει σε προκλήσεις στην αποτελεσματική αναπαράσταση της αριθμητικής ακεραίων μέσω λειτουργιών πεδίου (π.χ. πολλαπλασιάζοντας δύο ακέραιους χωρίς πρόσημο 32 bit μπορεί να αποφέρει αποτέλεσμα μεγαλύτερο από το χαρακτηριστικό πεδίου). 

 Αλλά ανεξάρτητα από το τι, για να επιτύχουν όλα τα δημοφιλή SNARK σήμερα 128 bit ασφάλειας (χωρίς σημαντική αύξηση στο κόστος επαλήθευσης), πρέπει να εργαστούν σε ένα πεδίο μεγέθους μεγαλύτερο από 2¹²⁸. Από όσο μπορώ να καταλάβω, αυτό σημαίνει ότι κάθε πράξη πεδίου θα απαιτεί τουλάχιστον περίπου δέκα πολλαπλασιασμούς μηχανής 64-bit, και πολύ περισσότερες προσθήκες και λειτουργίες bitwise. Ως εκ τούτου, θα πρέπει κανείς να συνυπολογίσει τουλάχιστον μια τάξη μεγέθους γενική επιβάρυνση λόγω της ανάγκης για κυκλώματα που λειτουργούν σε πεπερασμένα πεδία. 

Συνοψίζοντας, οι υπάρχουσες διεπαφές που χρησιμοποιούν μια αφαίρεση εικονικής μηχανής παράγουν κυκλώματα με 100x έως 1000x πύλες ανά βήμα της εικονικής μηχανής και πιθανώς περισσότερα για πιο περίπλοκες εικονικές μηχανές. Επιπλέον, η αριθμητική των πεπερασμένων πεδίων είναι τουλάχιστον 10 φορές πιο αργή από τις ανάλογες οδηγίες σε σύγχρονους επεξεργαστές (με πιθανές εξαιρέσεις εάν ο επεξεργαστής έχει ενσωματωμένη υποστήριξη για ορισμένα πεδία). Μια "προσέγγιση frontend ASIC" μπορεί να μειώσει ορισμένα από αυτά τα γενικά έξοδα, αλλά επί του παρόντος περιορίζεται στα είδη προγραμμάτων που μπορεί να υποστηρίξει.

Ποια είναι τα σημεία συμφόρησης του backend;

Τα SNARK για την ικανοποίηση κυκλωμάτων συνήθως σχεδιάζονται συνδυάζοντας ένα θεωρητικά ασφαλές πρωτόκολλο πληροφοριών που ονομάζεται "πολυωνυμική ΙΟΡ" με ένα κρυπτογραφικό πρωτόκολλο που ονομάζεται "πολυωνυμικό σύστημα δεσμεύσεων.» Στις περισσότερες περιπτώσεις, το συγκεκριμένο σημείο συμφόρησης για τον prover είναι το σχήμα πολυωνυμικής δέσμευσης. Συγκεκριμένα, αυτά τα SNARK έχουν τον prover να δεσμεύεται κρυπτογραφικά σε ένα ή περισσότερα πολυώνυμα των οποίων ο βαθμός είναι (τουλάχιστον) |C|, ο αριθμός των πυλών στο κύκλωμα C. 

Με τη σειρά του, το τσιμεντένιο σημείο συμφόρησης εντός του σχήματος πολυωνυμικής δέσμευσης θα εξαρτηθεί από το σχήμα που χρησιμοποιείται και το μέγεθος του κυκλώματος. Αλλά θα είναι πάντα μία από τις ακόλουθες τρεις λειτουργίες: υπολογισμός FFT, εκθέσεις σε μια κρυπτογραφική ομάδα ή Merkle-hashing. Το Merkle-hashing είναι συνήθως ένα σημείο συμφόρησης μόνο εάν το κύκλωμα είναι μικρό, επομένως δεν θα το συζητήσουμε περαιτέρω. 

Πολυωνυμικές δεσμεύσεις που βασίζονται σε διακριτό ημερολόγιο

Σε πολυωνυμικές δεσμεύσεις που βασίζονται στη σκληρότητα του προβλήματος διακριτού λογαρίθμου σε μια κρυπτογραφική ομάδα G (KZG, Αλεξίσφαιρες, Είδος λέμβου, να Hyrax-commit), ο prover πρέπει να υπολογίσει α Pedersen διανυσματική δέσμευση στους συντελεστές του πολυωνύμου. Αυτό περιλαμβάνει έναν πολλαπλό εκθετικό όγκο, μεγέθους ίσου με το βαθμό του πολυωνύμου. Στα SNARK, αυτός ο βαθμός είναι συνήθως το μέγεθος |C| του κυκλώματος C.

Έγινε αφελώς, μια πολλαπλή επέκταση μεγέθους |C| απαιτεί περίπου 1.5·|C|·κούτσουρο |G| ≈ 400·|C| ομαδικές επιχειρήσεις, όπου |G| δηλώνει τον αριθμό των στοιχείων της ομάδας G. Ωστόσο, υπάρχει μια προσέγγιση, που ονομάζεται αλγόριθμος Pippenger, η οποία μπορεί να το μειώσει κατά έναν παράγοντα περίπου log |C|. Για μεγάλα κυκλώματα (ας πούμε, |C| ≥ 225), αυτό το αρχείο καταγραφής |C| Ο παράγοντας μπορεί συγκεκριμένα να είναι 25 ή περισσότερο, δηλαδή, για μεγάλα κυκλώματα, αναμένουμε ότι η διανυσματική δέσμευση Pedersen μπορεί να είναι υπολογίσιμη με λίγο περισσότερο από 10·|C| ομαδικές λειτουργίες. Κάθε ομαδική λειτουργία με τη σειρά της τείνει να είναι (ως ένα πολύ τραχύ ballpark) περίπου 10 φορές πιο αργή από μια επιχείρηση πεπερασμένου πεδίου. Τα SNARK που χρησιμοποιούν αυτές τις πολυωνυμικές δεσμεύσεις είναι εξίσου ακριβά P περίπου 100·|C| επιτόπιες επιχειρήσεις. 

Δυστυχώς, τα υπάρχοντα SNARK έχουν επιπλέον γενικά έξοδα πέρα ​​από τον παραπάνω παράγοντα 100x. Για παράδειγμα:

• ΣπαρτιάτηςΟ prover, που χρησιμοποιεί την πολυωνυμική δέσμευση Hyrax, πρέπει να κάνει |C|^½ πολλές πολλαπλές εκθέσεις το καθένα μεγέθους |C|^½, αποδυναμώνοντας την επιτάχυνση από τον αλγόριθμο του Pippenger κατά έναν παράγοντα περίπου δύο. 
• In Groth16, P πρέπει να εργάζονται σε μια ομάδα φιλική προς το ζευγάρωμα, της οποίας οι λειτουργίες είναι συνήθως τουλάχιστον 2 φορές πιο αργές από τις ομάδες που δεν είναι φιλικές για σύζευξη. P πρέπει επίσης να εκτελέσει 3 πολλαπλές εκθέσεις αντί για 1. Σε συνδυασμό, αυτό έχει ως αποτέλεσμα τουλάχιστον έναν επιπλέον παράγοντα-6 επιβράδυνση σε σχέση με το 100·|C| εκτίμηση παραπάνω. 
• Είδος μεγάλου ψαριού και Πέφτω απαιτούν επίσης ζεύγη, και οι δοκιμαστές τους να δεσμευτούν σε σημαντικά περισσότερα από 3 πολυώνυμα. 
• Για κάθε SNARK που χρησιμοποιεί Αλεξίσφαιρες (π.χ, Halo2, που είναι χονδρικά PlonK αλλά με αλεξίσφαιρες και όχι πολυωνυμικές δεσμεύσεις KZG), ο prover πρέπει να υπολογίσει λογαριθμικά πολλές πολλαπλές εκθέσεις κατά τη φάση «ανοίγματος» του σχήματος δεσμεύσεων, και αυτό διαγράφει σε μεγάλο βαθμό οποιαδήποτε επιτάχυνση Pippenger. 

Συνοπτικά, τα γνωστά SNARK που χρησιμοποιούν διανυσματικές δεσμεύσεις Pedersen φαίνεται να έχουν επιβάρυνση backend τουλάχιστον 200x και έως 1000x ή περισσότερο. 

Άλλες πολυωνυμικές δεσμεύσεις

Για SNARK που χρησιμοποιούν άλλες πολυωνυμικές δεσμεύσεις (όπως ΔΩΡΕΑΝ και Ligero-commit), το σημείο συμφόρησης είναι ότι ο prover χρειάζεται να εκτελέσει μεγάλα FFT. Για παράδειγμα, στους AIR βαθμού 2 που παράγονται από το Κάιρο (με 51 στήλες και T σειρές, μία ανά βήμα της CPU του Καΐρου), ο αναπτυγμένος prover της StarkWare κάνει τουλάχιστον 2 FFT ανά στήλη, μήκους μεταξύ 16 ·T και 32 ·T. Οι σταθερές 16 και 32 εξαρτώνται από τις εσωτερικές παραμέτρους του FRI όπως ορίζονται από το StarkWare και μπορούν να μειωθούν — αλλά με κόστος αυξημένου κόστους επαλήθευσης. 

Αισιόδοξα, ένα FFT μήκους 32·T παίρνει περίπου 64·T·ημερολόγιο (32T) πολλαπλασιασμοί πεδίων. Αυτό σημαίνει ότι ακόμη και για σχετικά μικρές τιμές του T (π.χ, T ≥ 2²⁰), ο αριθμός των λειτουργιών πεδίου ανά στήλη είναι τουλάχιστον 64·25·T= 1600·T. Έτσι, τα γενικά έξοδα του backend φαίνεται να είναι τουλάχιστον χιλιάδες. Επιπλέον, είναι πιθανό τα μεγάλα FFT να περιορίζονται ακόμη περισσότερο από το εύρος ζώνης της μνήμης παρά από τις λειτουργίες πεδίου. 

Σε ορισμένα περιβάλλοντα, η επιβάρυνση του backend των SNARK που εκτελούν μεγάλα FFT μπορεί να μετριαστεί με μια τεχνική που ονομάζεται συσσώρευση απόδειξης. Για συνάθροιση, αυτό θα σήμαινε ότι P (η υπηρεσία συνάθροισης) χωρίζει μια μεγάλη παρτίδα συναλλαγών σε, ας πούμε, 10 μικρότερες παρτίδες. Για κάθε μικρή παρτίδα i, P παράγει μια απόδειξη SNARK πi της εγκυρότητας της παρτίδας. Αλλά P δεν δημοσιεύει αυτές τις αποδείξεις στο Ethereum, καθώς αυτό θα οδηγούσε σε σχεδόν 10πλάσια αύξηση του κόστους αερίου. Αντίθετα, το SNARK εφαρμόζεται ξανά, αυτή τη φορά για να παραχθεί μια απόδειξη π διαπιστώνοντας ότι P ξέρει π₁ ...,π₁₀. Δηλαδή ο μάρτυρας ότι P ισχυρίζεται ότι γνωρίζει είναι οι δέκα αποδείξεις π₁,…,π₁₀, και ο άμεσος έλεγχος μαρτύρων εφαρμόζει τη διαδικασία επαλήθευσης SNARK σε καθεμία από τις αποδείξεις. Αυτή η μοναδική απόδειξη π δημοσιεύεται στο Ethereum. 

Σε πολυωνυμικές δεσμεύσεις όπως το FRI και το Ligero-commit, υπάρχει έντονη ένταση μεταξύ P ώρα και ώρα V κόστος, με τις εσωτερικές παραμέτρους να λειτουργούν ως πόμολο που μπορεί να ανταλλάξει τη μία με την άλλη. Από π₁ ,…,π₁₀ δεν έχουν αναρτηθεί στο Ethereum, το πόμολο μπορεί να ρυθμιστεί έτσι ώστε αυτές οι αποδείξεις είναι μεγάλα και η παραγωγή τους είναι ταχύτερη. Μόνο στην τελική εφαρμογή του SNARK, να συγκεντρωθούν π₁ ,…,π₁₀ σε μια ενιαία απόδειξη π, χρειάζεται να διαμορφωθεί το σχέδιο δεσμεύσεων για να διασφαλιστεί μια μικρή απόδειξη. 

Η StarkWare σχεδιάζει να αναπτύξει συγκέντρωση αποδείξεων επίκειται. Αυτό είναι και το επίκεντρο έργων όπως π.χ Plonky2.

Ποια είναι τα άλλα σημεία συμφόρησης στην επεκτασιμότητα του SNARK;

Αυτή η ανάρτηση έχει επικεντρωθεί στο prover ώρα, αλλά άλλα κόστη prover μπορεί επίσης να είναι εμπόδια επεκτασιμότητας. Για παράδειγμα, για πολλά backend SNARK, ο prover χρειάζεται να αποθηκεύσει πολλά στοιχεία πεδίου για κάθε πύλη C, και αυτό το κόστος χώρου μπορεί να είναι τεράστιο. Για παράδειγμα, ένα πρόγραμμα ψ Η εκτέλεση σε ένα δευτερόλεπτο σε ένα φορητό υπολογιστή μπορεί να εκτελέσει ίσως ένα δισεκατομμύριο πρωτόγονες λειτουργίες σε έναν σύγχρονο επεξεργαστή. Όπως είδαμε, σε γενικές γραμμές θα έπρεπε να περιμένει κανείς C να απαιτούνται πάνω από 100 πύλες ανά τέτοια λειτουργία. Αυτό σημαίνει 100 δισεκατομμύρια πύλες, οι οποίες, ανάλογα με το SNARK, θα μπορούσαν να σημαίνουν δεκάδες ή εκατοντάδες terabyte χώρου για P. 

Ένα άλλο παράδειγμα: πολλά δημοφιλή SNARK (π.χ. Πέφτω, Είδος μεγάλου ψαριού, Groth16) απαιτούν μια περίπλοκη «τελετή αξιόπιστης εγκατάστασης» για τη δημιουργία ενός δομημένου «κλειδιού απόδειξης», που πρέπει να αποθηκευτεί από τον prover. Από όσο ξέρω, το μεγαλύτερη τέτοια τελετή δημιούργησε ένα κλειδί απόδειξης ικανό να υποστηρίζει κυκλώματα με περίπου 2²⁸≈250 εκατομμύρια πύλες. Το κλειδί απόδειξης έχει μέγεθος αρκετές δεκάδες gigabyte. 

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

Κοιτάζοντας το μέλλον: προοπτικές για πιο επεκτάσιμα SNARK

Τόσο τα γενικά έξοδα του frontend όσο και του backend μπορεί να είναι τρεις τάξεις μεγέθους ή περισσότερο. Μπορούμε να περιμένουμε ότι αυτά θα μειωθούν σημαντικά στο εγγύς μέλλον; 

Νομίζω ότι θα το κάνουμε — μέχρι ένα σημείο. Πρώτον, τα πιο γρήγορα backends σήμερα (π.χ. Σπαρτιάτης και Brakedown, και άλλα SNARK που συνδυάζουν το πρωτόκολλο αθροίσματος ελέγχου με πολυωνυμικές δεσμεύσεις) έχουν μεγάλες αποδείξεις - τυπικά τετραγωνική ρίζα στο μέγεθος του κυκλώματος - έτσι οι άνθρωποι δεν τις χρησιμοποιούν πραγματικά. Αναμένω ότι το μέγεθος απόδειξης και ο χρόνος επαλήθευσης θα μειωθούν σημαντικά στο εγγύς μέλλον μέσω της σύνθεσης ενός βάθους με SNARK με μικρή αντοχή. Παρόμοια με τη συγκέντρωση αποδείξεων, αυτό σημαίνει ότι ένας prover θα δημιουργήσει πρώτα μια απόδειξη SNARK π με το "fast-prover, large-proof" SNARK, αλλά όχι αποστολή π προς την V. Μάλλον, P θα χρησιμοποιούσε ένα SNARK με μικρή αντοχή για να παράγει μια απόδειξη π» ότι ξέρει π, και στείλτε π» προς την V. Αυτό θα μπορούσε να μειώσει μια τάξη μεγέθους από τα γενικά έξοδα υποστήριξης των SNARK που είναι δημοφιλή σήμερα. 

Δεύτερον, η επιτάχυνση υλικού μπορεί να βοηθήσει. Ένας πολύ πρόχειρος γενικός κανόνας είναι ότι οι GPU μπορούν να αγοράσουν 10x επιτάχυνση έναντι των CPU και οι ASIC 10x επιτάχυνση έναντι των GPU. Ωστόσο, έχω τρεις ανησυχίες σε αυτό το μέτωπο. Πρώτον, οι μεγάλοι FFT μπορεί να παρεμποδίζονται από το εύρος ζώνης μνήμης και όχι από λειτουργίες πεδίου, επομένως τα SNARK που εκτελούν τέτοια FFT μπορεί να δουν περιορισμένες επιταχύνσεις από εξειδικευμένο υλικό. Δεύτερον, ενώ αυτή η ανάρτηση επικεντρώθηκε στο σημείο συμφόρησης της πολυωνυμικής δέσμευσης, πολλά SNARK απαιτούν από τον prover να κάνει άλλες λειτουργίες που είναι ελαφρώς λιγότερο δαπανηρές. Έτσι, σπάζοντας το στενό σημείωμα της πολυωνυμικής δέσμευσης (π.χ. επιτάχυνση πολλαπλών εκθέσεων σε SNARK που βασίζονται σε διακριτά αρχεία καταγραφής) μπορεί να αφήσει μια νέα λειτουργία συμφόρησης που δεν είναι πολύ καλύτερη από την παλιά. (Για παράδειγμα, τα SNARK, συμπεριλαμβανομένων των Groth16, Marlin και PlonK, έχουν επίσης το prover do FFTs, εκτός από τις πολλαπλές εκθέσεις.) Τέλος, τα πεδία και οι ελλειπτικές καμπύλες που οδηγούν στα πιο αποτελεσματικά SNARK μπορεί να συνεχίσουν να εξελίσσονται για κάποιο χρονικό διάστημα και αυτό μπορεί να δημιουργήσει προκλήσεις για την επιτάχυνση prover που βασίζεται σε ASIC.

Από την πλευρά του μπροστινού τμήματος, μπορεί ολοένα και περισσότερο να βρίσκουμε ότι η προσέγγιση «εξομοιωτή CPU» έργων όπως το Cairo, το RISC Zero, τα zkEVM και άλλα στην πραγματικότητα προσαρμόζεται αρκετά καλά (από άποψη απόδοσης) με την πολυπλοκότητα των συνόλων εντολών της CPU. Πράγματι, αυτή ακριβώς είναι η ελπίδα των διαφόρων έργων zkEVM. Αυτό μπορεί να σημαίνει ότι, ενώ η επιβάρυνση του frontend παραμένει τρεις τάξεις μεγέθους ή περισσότερο, τα frontend καταφέρνουν να υποστηρίζουν VM που ταιριάζουν όλο και περισσότερο με πραγματικές αρχιτεκτονικές CPU. Μια αντισταθμιστική ανησυχία είναι ότι τα frontends μπορεί να γίνουν πολύπλοκα και δύσκολο να ελεγχθούν, καθώς πολλαπλασιάζονται τα χειροποίητα gadget που εφαρμόζουν όλο και πιο περίπλοκες οδηγίες. Οι επίσημες μέθοδοι επαλήθευσης πιθανότατα θα διαδραματίσουν σημαντικό ρόλο στην αντιμετώπιση αυτής της ανησυχίας. 

Τέλος, τουλάχιστον σε εφαρμογές blockchain, μπορεί να διαπιστώσουμε ότι τα περισσότερα έξυπνα συμβόλαια που εμφανίζονται στη φύση χρησιμοποιούν κατά κύριο λόγο απλές οδηγίες φιλικές προς το SNARK. Αυτό μπορεί να επιτρέψει στην πράξη χαμηλά γενικά έξοδα διεπαφής, διατηρώντας παράλληλα τη γενικότητα και τη βελτιωμένη εμπειρία προγραμματιστή που συνοδεύεται από την υποστήριξη γλωσσών προγραμματισμού υψηλού επιπέδου όπως η Solidity και πλούσια σύνολα οδηγιών, συμπεριλαμβανομένων εκείνων του EVM. 

***

Τζάστιν Τάλερ is Αναπληρωτής Καθηγητής στο Πανεπιστήμιο Georgetown. Πριν ενταχθεί στο Georgetown, πέρασε δύο χρόνια ως ερευνητής στο Yahoo Labs στη Νέα Υόρκη, πριν από την οποία ήταν ερευνητής στο Simons Institute for the Theory of Computing στο UC Berkeley. 

***

Ευχαριστίες: Είμαι ευγνώμων Έλενα Μπέργκερ για την πρόταση του θέματος αυτής της ανάρτησης και για να Arasu Arun, Joseph Bonneau, να Σαμ Ράγκσντεϊλ για διορατικά σχόλια. Ιδιαίτερες ευχαριστίες και στον εκδότη μου, Τιμ Σούλιβαν.

***

Οι απόψεις που εκφράζονται εδώ είναι αυτές του μεμονωμένου προσωπικού της AH Capital Management, LLC (“a16z”) που αναφέρεται και δεν είναι απόψεις της a16z ή των θυγατρικών της. Ορισμένες πληροφορίες που περιέχονται εδώ έχουν ληφθεί από τρίτες πηγές, συμπεριλαμβανομένων των εταιρειών χαρτοφυλακίου κεφαλαίων που διαχειρίζεται η a16z. Αν και λαμβάνεται από πηγές που πιστεύεται ότι είναι αξιόπιστες, το a16z δεν έχει επαληθεύσει ανεξάρτητα τέτοιες πληροφορίες και δεν κάνει δηλώσεις σχετικά με τη διαρκή ακρίβεια των πληροφοριών ή την καταλληλότητά τους για μια δεδομένη κατάσταση. Επιπλέον, αυτό το περιεχόμενο μπορεί να περιλαμβάνει διαφημίσεις τρίτων. Η a16z δεν έχει ελέγξει τέτοιες διαφημίσεις και δεν υποστηρίζει κανένα διαφημιστικό περιεχόμενο που περιέχεται σε αυτές.

Αυτό το περιεχόμενο παρέχεται μόνο για ενημερωτικούς σκοπούς και δεν θα πρέπει να βασίζεται ως νομική, επιχειρηματική, επενδυτική ή φορολογική συμβουλή. Θα πρέπει να συμβουλευτείτε τους δικούς σας συμβούλους για αυτά τα θέματα. Οι αναφορές σε οποιουσδήποτε τίτλους ή ψηφιακά περιουσιακά στοιχεία είναι μόνο για ενδεικτικούς σκοπούς και δεν αποτελούν επενδυτική σύσταση ή προσφορά για παροχή επενδυτικών συμβουλευτικών υπηρεσιών. Επιπλέον, αυτό το περιεχόμενο δεν απευθύνεται ούτε προορίζεται για χρήση από επενδυτές ή υποψήφιους επενδυτές και δεν μπορεί σε καμία περίπτωση να γίνει επίκληση του κατά τη λήψη απόφασης για επένδυση σε οποιοδήποτε αμοιβαίο κεφάλαιο που διαχειρίζεται η a16z. (Μια προσφορά για επένδυση σε ένα αμοιβαίο κεφάλαιο a16z θα γίνει μόνο από το μνημόνιο ιδιωτικής τοποθέτησης, τη συμφωνία εγγραφής και άλλη σχετική τεκμηρίωση οποιουδήποτε τέτοιου κεφαλαίου και θα πρέπει να διαβαστεί στο σύνολό τους.) Τυχόν επενδύσεις ή εταιρείες χαρτοφυλακίου που αναφέρονται, αναφέρονται ή που περιγράφονται δεν είναι αντιπροσωπευτικές όλων των επενδύσεων σε οχήματα που διαχειρίζεται η a16z και δεν μπορεί να υπάρξει διαβεβαίωση ότι οι επενδύσεις θα είναι κερδοφόρες ή ότι άλλες επενδύσεις που θα πραγματοποιηθούν στο μέλλον θα έχουν παρόμοια χαρακτηριστικά ή αποτελέσματα. Μια λίστα με επενδύσεις που πραγματοποιήθηκαν από αμοιβαία κεφάλαια που διαχειρίζεται ο Andreessen Horowitz (εξαιρουμένων των επενδύσεων για τις οποίες ο εκδότης δεν έχει παράσχει άδεια για δημοσιοποίηση της a16z καθώς και των απροειδοποίητων επενδύσεων σε δημόσια διαπραγματεύσιμα ψηφιακά περιουσιακά στοιχεία) είναι διαθέσιμη στη διεύθυνση https://a16z.com/investments /.

Τα γραφήματα και τα γραφήματα που παρέχονται εντός προορίζονται αποκλειστικά για ενημερωτικούς σκοπούς και δεν θα πρέπει να βασίζονται σε αυτά όταν λαμβάνεται οποιαδήποτε επενδυτική απόφαση. Οι προηγούμενες αποδόσεις δεν είναι ενδεικτικές των μελλοντικών αποτελεσμάτων. Το περιεχόμενο μιλά μόνο από την ημερομηνία που υποδεικνύεται. Οποιεσδήποτε προβλέψεις, εκτιμήσεις, προβλέψεις, στόχοι, προοπτικές και/ή απόψεις που εκφράζονται σε αυτό το υλικό υπόκεινται σε αλλαγές χωρίς προειδοποίηση και μπορεί να διαφέρουν ή να είναι αντίθετες με τις απόψεις που εκφράζονται από άλλους. Ανατρέξτε στη διεύθυνση https://a16z.com/disclosures για πρόσθετες σημαντικές πληροφορίες.