Το άρθρο αυτό προτείνει ένα proof-of-concept (απόδειξη εφικτότητας) που αξιοποιεί τα zk-SNARKs για να κατακτήσει το επόμενο σύνορο της διακυβέρνησης: διακυβέρνηση on-chain χωρίς κόστος gas, επαληθευμένη και δεσμευτική.

Το τεχνικό περιεχόμενο αυτής της πρότασης έχει δημοσιευτεί και στο φόρουμ Ethresear.ch εδώ για συζήτηση με την κοινότητα.

Υπόβαθρο

Ως κορυφαίο έργο ψηφιακής διακυβέρνησης, η Vocdoni επενδύει σημαντικά στην έρευνα και την καινοτομία γύρω από μοντέλα διακυβέρνησης. Έχουμε εντοπίσει διάφορες λύσεις διακυβέρνησης επιπέδου 2 (layer-2) που παρουσιάζουν δυνατότητες, αλλά αφήνουν ανοιχτά αρκετά τεχνικά ερωτήματα. Έχουμε επιτύχει διαδικασίες ψηφοφορίας χωρίς κόστος gas στο εξειδικευμένο blockchain ψηφοφορίας μας, τη Vochain, και έχουμε επίσης σχεδιάσει και υλοποιήσει μια μέθοδο χρήσης των Ethereum Storage Proofs (αποδείξεων αποθήκευσης) για τη μεταφορά καταλόγων ψηφοφόρων βασισμένων σε tokens ERC20 από το Ethereum στη Vochain. Μέχρι σήμερα, ωστόσο, η δυνατότητα μεταφοράς των αποτελεσμάτων πίσω στο Ethereum παρέμενε ανοιχτό ερευνητικό ερώτημα.

Για τον σκοπό αυτό, η Vocdoni διεξάγει πειράματα πάνω σε έναν νέο σχεδιασμό που θα επέτρεπε τα αποτελέσματα μιας διαδικασίας ψηφοφορίας off-chain (εκτός αλυσίδας) να μεταφέρονται στο Ethereum, χωρίς τη χρήση υποκειμενικών oracles ή οποιουδήποτε άλλου στοιχείου που απαιτεί εμπιστοσύνη.

Η βασική καινοτομία πίσω από μια τέτοια πρόταση είναι σαφής: κανένα σύστημα που γνωρίζουμε δεν μπορεί να οργανώσει μια διαδικασία ψηφοφορίας off-chain και να εκτελέσει ενέργειες στο Ethereum με βάση τα αποτελέσματά της χωρίς να απαιτείται εμπιστοσύνη σε τρίτους. Οι περιπτώσεις χρήσης της πρότασης περιλαμβάνουν δυνητικά όλες τις διαδικασίες διακυβέρνησης που εκτελούν δεσμευτικές ενέργειες με βάση τα αποτελέσματα, όπως (ενδεικτικά) ψηφοφορίες DAO για την κατανομή περιουσιακών στοιχείων ή για αλλαγές σε έξυπνα συμβόλαια (smart contracts). Οι διαδικασίες αυτές πρέπει σήμερα να διεξάγονται στο mainnet του Ethereum, με σημαντικές χρεώσεις gas για κάθε ψηφοφόρο. Εναλλακτικά, η ψηφοφορία θα μπορούσε να γίνεται off-chain, εμπιστευόμενη όμως ένα εξωτερικό στοιχείο για την ακριβή και έντιμη μεταφορά των αποτελεσμάτων πίσω στο Ethereum.

Η πρότασή μας θα επέτρεπε σε διαδικασίες ψηφοφορίας που διεξάγονται εξ ολοκλήρου off-chain να εκτελούν τα αποτελέσματα στο Ethereum με την ίδια ακεραιότητα με την on-chain διακυβέρνηση, σε ένα κλάσμα του κόστους.

Απαιτήσεις του proof-of-concept για το πρωτόκολλο ψηφοφορίας

Πριν σχεδιάσουμε μια τεχνική λύση, ορίσαμε τις παραμέτρους της ερευνητικής μας πρότασης:

Οι απαιτήσεις ήταν το πρωτόκολλο ψηφοφορίας να είναι:

1. Χωρίς αδειοδότηση (permissionless).
2. Ανθεκτικό στη λογοκρισία.
3. Σε θέση να δεσμεύει τα αποτελέσματα στο Ethereum.
4. Χωρίς κόστος gas για τους ψηφοφόρους.
5. Απαλλαγμένο από μεταφορά tokens μέσω γεφυρών.
6. Όσο το δυνατόν απλούστερο (χωρίς sidechain).
7. Συμβατό με ERC20 / ERC777 και NFT για την ψηφοφορία.

Ως σχεδιασμό proof-of-concept, αποδεχθήκαμε τους ακόλουθους περιορισμούς στην πρόταση:

1. Καμία ανωνυμία χρήστη: οι ψήφοι μπορούν να συνδεθούν με μια διεύθυνση Ethereum.
2. Χωρίς απουσία αποδεικτικού ψήφου (receipt-freeness): η αγορά ψήφων ενδέχεται να είναι εφικτή.
3. Δεν έχει σχεδιαστεί για εκλογές εθνικής κλίμακας: μόνο για DAO ή κατόχους ERC20 / NFT. Επομένως, πρέπει να οριστεί ένα μέγιστο μέγεθος καταλόγου ψηφοφόρων (ανάλογα με τις επιδόσεις και το κόστος).
4. Κανένα καθορισμένο μοντέλο κινήτρων για τους relayers.

Ιδανική πρόταση

Σύμφωνα με τον σχεδιασμό αυτής της πρότασης, κατά τη δημιουργία μιας νέας διαδικασίας ψηφοφορίας οι διοργανωτές υποβάλλουν μια συναλλαγή στο Ethereum, προσδιορίζοντας τη διεύθυνση συμβολαίου ενός token ERC20 που θα χρησιμοποιηθεί ως κατάλογος ψηφοφόρων. Το Storage Root Hash αυτής της διεύθυνσης, σε καθορισμένο ύψος μπλοκ, γίνεται η ρίζα του καταλόγου ψηφοφόρων για τη συγκεκριμένη διαδικασία. Οποιοσδήποτε κατέχει το συγκεκριμένο token μπορεί να αποδείξει το δικαίωμα συμμετοχής του παρέχοντας μια απόδειξη Merkle (μέσω του EIP1186) για το υπόλοιπό του στο token. Στη συνέχεια μπορεί να καταθέσει την ψήφο του στέλνοντας την απόδειξη (siblings) και μια υπογραφή σε έναν relayer rollup zk-SNARK, ο οποίος θα υπολογίσει μια απόδειξη των τελικών αποτελεσμάτων.

Ένα πιθανό πρόβλημα είναι ότι ο φορέας που υπολογίζει την απόδειξη zk-SNARK των αποτελεσμάτων (ο συντονιστής) θα μπορούσε, θεωρητικά, να λογοκρίνει το αποτέλεσμα αποφασίζοντας να αποκλείσει ψήφους. Αντιμετωπίζουμε το πρόβλημα αυτό επιτρέποντας σε οποιονδήποτε (όχι μόνο στον συντονιστή) να υποβάλλει νέες ψήφους: κάθε χρήστης μπορεί να δημιουργήσει και να υποβάλει ένα rollup που περιέχει την ψήφο του, αν διαπιστώσει ότι κάποιος συντονιστής δεν την έχει συμπεριλάβει.

Η πρότασή μας χρησιμοποιεί zk-SNARKs για τους ακόλουθους σκοπούς:

• Για την επαλήθευση ότι μια διεύθυνση δεν έχει ήδη ψηφίσει, μέσω του accumulator (συσσωρευτή) δέντρου Merkle.
• Για την επαλήθευση ότι ο χρήστης κατέχει tokens, μέσω Storage Proofs.
• Για τον υπολογισμό μερικών αποτελεσμάτων σε μια παρτίδα ψήφων.
• Για την επαλήθευση της υπογραφής της ψήφου.

Δεσμευτική εκτέλεση στο Ethereum με zkSNARKs — ιδανική πρόταση.

Στο παραπάνω σχήμα εντοπίζουμε 2 βασικά προβλήματα:

Πρόβλημα 1: η επαλήθευση των ERC20 Storage Proofs δεν είναι φιλική προς τα SNARK¶

Η επαλήθευση των ERC20 Storage Proofs μέσα σε ένα SNARK είναι εξαιρετικά πολύπλοκη. Αυτό οφείλεται εν μέρει στη χρήση ανάλυσης Recursive Length Prefix (RLP) και σε πολλαπλές επαληθεύσεις hash Keccak-256, που και οι δύο υπολογίζονται αναποτελεσματικά με τη σύγχρονη τεχνολογία rollup SNARK. Το πρόβλημα αυτό δύσκολα παρακάμπτεται, γι' αυτό προς το παρόν το λύνουμε με αισιόδοξη (optimistic) επικύρωση.

Πρόβλημα 2: η επαλήθευση υπογραφών ECDSA / Secp256k1 δεν είναι φιλική προς τα SNARK¶

Ένα υφιστάμενο κρυπτογραφικό πρότυπο που θα μπορούσαμε να χρησιμοποιήσουμε για την επαλήθευση υπογραφών χρηστών είναι το ECDSA με κλειδί BabyJubJub παραγόμενο από υπογραφή Ethereum, χρησιμοποιώντας την υπογραφή ως ακατέργαστο ιδιωτικό κλειδί, κάτι που επιτρέπει στον χρήστη να ανακτήσει τη διεύθυνσή του. Επειδή η μέθοδος αυτή βασίζεται σε υπογραφή του χρήστη, είναι ευάλωτη σε κακόβουλους παράγοντες που εξαπατούν τους χρήστες ώστε να υπογράψουν δόλιες συναλλαγές στο πορτοφόλι Web3 τους. Η ευπάθεια αυτή υπάρχει οπουδήποτε χρησιμοποιείται πορτοφόλι προγράμματος περιήγησης για την υπογραφή συναλλαγής. Μια πιθανή λύση θα ήταν η παραγωγή ιδιωτικού κλειδιού με χρήση της διεύθυνσης ιστού ως διαδρομής παραγωγής (derivation path).

Μια πρόσθετη πρόκληση είναι να αποδειχθεί ότι η διεύθυνση Ethereum κάθε κατόχου token εγκρίνει το κλειδί BabyJubJub για την ψηφοφορία στο ύψος μπλοκ της δημιουργίας μιας διαδικασίας ψηφοφορίας. Το επιτυγχάνουμε με ένα έξυπνο συμβόλαιο «singleton» που αντιστοιχίζει διευθύνσεις Ethereum σε δημόσια κλειδιά BabyJubJub, όπου ο χρήστης πρέπει να προσθέσει το κλειδί του στο έξυπνο συμβόλαιο μέσω μιας τυπικής συναλλαγής. Η αντιστοίχιση διεύθυνσης–κλειδιού μπορεί να αμφισβητηθεί μέσω μιας αισιόδοξης απόδειξης απάτης αποθήκευσης (εφόσον έχουμε ήδη ανοίξει τον δρόμο για την αισιόδοξη επικύρωση των Storage Proofs). Η λύση αυτή επιλύει επίσης το πρόβλημα της διαθεσιμότητας δεδομένων με έναν επαναχρησιμοποιήσιμο σχεδιασμό, καθώς αναμένεται ότι τα εξουσιοδοτημένα αυτά κλειδιά θα χρησιμοποιηθούν πολλές φορές σε διαφορετικές διαδικασίες ψηφοφορίας.

Συνοψίζοντας, μπορούμε να χειριστούμε τις περισσότερες επαληθεύσεις μέσα σε ένα SNARK, αλλά όχι όλες:

• Επαλήθευση ότι μια διεύθυνση δεν έχει ήδη ψηφίσει, μέσω του accumulator δέντρου Merkle → SNARK
• Επαλήθευση ότι ο χρήστης κατέχει tokens, μέσω Storage Proofs → Optimistic
• Υπολογισμός μερικών αποτελεσμάτων της ψηφοφορίας → SNARK
• Επαλήθευση της υπογραφής της ψήφου → SNARK

Πρόταση

Δεσμευτική εκτέλεση στο Ethereum με zkSNARKs — πρόταση

Χρήστης¶

• Δημιουργεί ένα κλειδί BabyJubJub, παραγόμενο από υπογραφή Ethereum, και το καταχωρίζει στο έξυπνο συμβόλαιο Voter Registry (μητρώο ψηφοφόρων).
• Ανακτά τις πληροφορίες της ψηφοφορίας και το Storage Proof του λογαριασμού του, δημιουργεί μια υπογραφή στο πακέτο ψήφου και το προωθεί σε έναν relayer ή σε ένα σύνολο relayers.

Έξυπνο συμβόλαιο ψηφοφορίας¶

• Καταχωρίζει τη διαδικασία ψηφοφορίας, συμπεριλαμβάνοντας: τη διεύθυνση του έξυπνου συμβολαίου ERC20, τον δείκτη slot της αντιστοίχισης διεύθυνσης→υπολοίπου του ERC20, το hash της ρίζας κατάστασης (state root) για το αρχικό μπλοκ της διαδικασίας ψηφοφορίας και τις παραμέτρους της διαδικασίας για τον υπολογισμό της καταμέτρησης (βλ. το Ballot Protocol της Vocdoni).
• Παρακολουθεί την καταχώριση νέων ψήφων μέσω zk-Rollup, ενός SNARK που αποδεικνύει:
• Τον υπολογισμό του αποτελέσματος.
• Ότι η υπογραφή της ψήφου έχει γίνει από κλειδί BabyJubJub.
• Διατηρεί ενημερωμένους τους accumulators της ψηφοφορίας.
• Διατηρεί ενημερωμένη τη λίστα των ψηφοφόρων.
• Επιτρέπει σε οποιονδήποτε να αμφισβητήσει την τελευταία καταχώριση ψήφων μέσω αποδείξεων απάτης (fraud proofs). Μια αμφισβήτηση πρέπει να παρέχει ένα από τα ακόλουθα:
• Ένα Storage Proof που αποδεικνύει ότι η διεύθυνση Ethereum ενός ψηφοφόρου δεν διαθέτει tokens.
• Ένα Storage Proof που αποδεικνύει ότι η διεύθυνση Ethereum ενός ψηφοφόρου δεν είναι συνδεδεμένη με κλειδί BabyJubJub.
• Μια απόδειξη ότι το κλειδί BabyJubJub έχει ψηφίσει (το κλειδί βρίσκεται στο δέντρο «έχουν ήδη ψηφίσει»).

Relayer¶

• φάση 0: Η εκλογική διαδικασία δημιουργείται στο Ethereum και επιλέγεται ένας relayer από λίστα διαθέσιμων relayers. Ο διοργανωτής της εκλογής πρέπει να καλύψει το κόστος της (το οποίο αποδίδεται ως αμοιβή στον συντονιστή). Ο διοργανωτής παρέχει τον bytecode EVM που πρέπει να εκτελεστεί μετά την εκλογή στο έξυπνο συμβόλαιο (ή στα έξυπνα συμβόλαια) του DAO, ανάλογα με τα αποτελέσματα.
• φάση 1: Ξεκινά η ψηφοφορία. Οποιοσδήποτε μπορεί να στείλει πακέτα ψήφων στον επιλεγμένο συντονιστή (μπορούν να χρησιμοποιηθούν μεταφορές HTTPs ή libp2p). Ο συντονιστής συγκεντρώνει τα επιλεγμένα αποτελέσματα σε παρτίδες (rollup), κατασκευάζει μια απόδειξη zk-SNARK, ανεβάζει την απόδειξη και τα αποτελέσματα στο Ethereum, συλλέγει τις ψήφους που κατέθεσαν οι χρήστες, τις επαληθεύει και τις μεταδίδει στους υπόλοιπους relayers.
• φάση 2: Οι συντονιστές που εντοπίζουν ψήφο που δεν έχει προστεθεί μπορούν να συγκεντρώσουν οι ίδιοι τις ψήφους τους σε rollup και να στείλουν μια απόδειξη εγκυρότητας zk-SNARK στο έξυπνο συμβόλαιο ψηφοφορίας. Επιπλέον, αν εντοπίσουν ότι μια ψήφος έχει προστεθεί εσφαλμένα, μπορούν να στείλουν απόδειξη απάτης που αποδεικνύει ότι το προηγουμένως προστεθέν αποτέλεσμα είναι άκυρο, και ο συντονιστής που το παρήγαγε θα υποστεί ποινή περικοπής (slashing).
• φάση 3: Όταν συμπληρωθεί η καταληκτική ημερομηνία της ψηφοφορίας:
• Το άθροισμα των αποτελεσμάτων που έχουν ανέβει (από τον συντονιστή και από οποιονδήποτε τρίτο) θεωρείται έγκυρο και η αμοιβή κατανέμεται μεταξύ του συντονιστή και των παραγόντων που συμπεριέλαβαν περισσότερες ψήφους (εφόσον υπάρχουν).
• Οποιοσδήποτε (συνήθως ο συντονιστής) καλεί τον bytecode EVM προς εκτέλεση, χρησιμοποιώντας τα τελικά αποτελέσματα ως είσοδο.

Το κύκλωμα και το συμβόλαιο¶

Ένα zk-SNARK θα συναθροίζει μια λίστα κατατεθειμένων ψήφων. Η απόδειξη zk-SNARK είναι έγκυρη με βάση μια δεδομένη λίστα ψήφων, μια ρίζα καταλόγου ψηφοφόρων, ένα αναγνωριστικό εκλογής (electionId) και ένα συναθροισμένο αποτέλεσμα.

Το κύκλωμα και το συμβόλαιο

ΕΙΣΟΔΟΙ zk-SNARK

• Hash των εισόδων (δημόσιο) (γίνεται για να μειωθεί το κόστος gas της επαλήθευσης του SNARK).
• ElectionId (ιδιωτικό).
• Υπολογισμός των αποτελεσμάτων ψηφοφορίας αυτής της παρτίδας (ιδιωτικό).
• Τρέχουσα ρίζα των nullifiers (ιδιωτικό).
• Ενημερωμένη ρίζα των nullifiers (ιδιωτικό).
• Αριθμός ψήφων στην παρτίδα (ιδιωτικό).
• Τιμές ψήφων και αντίστοιχες υπογραφές BabyJubJub [1..BATCHSIZE] (ιδιωτικό).

Οι είσοδοι της κλήσης της συνάρτησης του έξυπνου συμβολαίου για το ανέβασμα των αποτελεσμάτων του συντονιστή είναι:

• electionId.
• Λίστα των δημόσιων κλειδιών των ψηφοφόρων αυτής της παρτίδας.
• Ενημερωμένη ρίζα των nullifiers.
• Υπολογισμός των αποτελεσμάτων ψηφοφορίας αυτής της παρτίδας.
• Απόδειξη SNARK.

Υλοποίηση του proof of concept

Υλοποιήσαμε τα ελάχιστα βιώσιμα έξυπνα συμβόλαια και κυκλώματα για να ελέγξουμε το κόστος και τη βιωσιμότητα της λύσης εδώ. Το PoC αυτό περιλαμβάνει μόνο το μητρώο χρηστών, τη συνάθροιση ψήφων και την επαλήθευση αποδείξεων απάτης.

Οι δοκιμές μας κατέγραψαν τα ακόλουθα κόστη gas:

user key registry
  deployment           258,536
  registration         68,956

voting
  deployment           6,673,159
  new voting           25,989
  aggregate rollup     291,801
  fraud proof-1        574,574 (babyjubjub key not registered)
  fraud proof-2        908,822 (account ERC20 balance is zero)

Σε μετρήσεις για την εκτίμηση ενός εφικτού αριθμού ψήφων προς συνάθροιση, χρησιμοποιώντας έναν τυπικό διακομιστή με 32 GB RAM / 8 CPU, διαπιστώσαμε ότι είναι δυνατή η συνάθροιση έως 300 ψήφων (με accumulator δέντρου Merkle 64 επιπέδων και ~3,8 εκατ. περιορισμούς), με 450 δευτερόλεπτα για τη δημιουργία της απόδειξης και κατανάλωση 30 GB RAM. Για τις αποδείξεις χρησιμοποιήσαμε Groth16 με Circom, παραγωγή witness σε C++ και rapidSNARK.

Θετικό στοιχείο είναι ότι η απόδειξη που πρέπει να υπολογιστεί για τη δημιουργία μιας απόδειξης απάτης είναι αρκετά μικρή (50k) ώστε να μπορεί να παραχθεί σε πρόγραμμα περιήγησης. Αυτό επιτρέπει στους χρήστες να αμφισβητούν μια παρτίδα ψήφων χωρίς να χρειάζεται να κατεβάσουν εξειδικευμένο λογισμικό.

Μελλοντική έρευνα

Βασιζόμενοι σε αυτή την έρευνα, θα θέλαμε να διερευνήσουμε σε μεγαλύτερο βάθος τις ακόλουθες ιδέες:

• Επαλήθευση τυπικών υπογραφών Keccak / ECDSA / Sec256k1 μέσω SNARKs. Πιστεύουμε ότι σύντομα το PLOOKUP θα μπορεί να επαληθεύει αυτά τα σχήματα, κάτι που θα ανοίξει δύο δυνατότητες:
• Να αποδεικνύεται ότι το κλειδί BabyJubJub έχει παραχθεί από κλειδί Secp256k1 (αυτό χρειάζεται να γίνει μόνο μία φορά).
• Να επαληθεύεται η ίδια η υπογραφή της ψήφου.
• Επαλήθευση Storage Proofs μέσα σε SNARK. Θεωρούμε ότι ένα τόσο πολύπλοκο κύκλωμα θα μπορούσε να ενσωματωθεί εύκολα μέσω μιας zkVM, αν και το κόστος ενδέχεται να είναι σημαντικό. Μας ανησυχεί το ενδεχόμενο οι πελάτες (clients) του Ethereum να καταργήσουν τους κόμβους αρχείου (archive nodes) για να δώσουν προτεραιότητα σε υψηλότερα όρια gas, οπότε ένα ακόμη πεδίο έρευνας είναι η χρήση μεθόδων πέραν του EIP1186 για τα Storage Proofs.
• Για τον υπολογισμό της καταμέτρησης, ενσωμάτωση κάποιου είδους opcodes προς εκτέλεση μέσα σε zkVM, ώστε να καταστούν δυνατά γενικά προγραμματιζόμενα κυκλώματα ψηφοφορίας.
• Δημιουργία απόδειξης ψήφου στο πρόγραμμα περιήγησης, μείξη μέσω ομαδοποίησης σε παρτίδες και αναδρομική συνάθροιση των αποτελεσμάτων, κατ' αναλογία με το πρωτόκολλο zk.money. Αυτό θα ενίσχυε το απόρρητο της διαδικασίας ψηφοφορίας.
• Δυνατότητα υπολογισμού SNARKs σε επίπεδο προγράμματος περιήγησης με κατανεμημένο τρόπο, ακόμη κι αν είναι υπολογιστικά ακριβοί. Έτσι αποφεύγεται η εξάρτηση από διακομιστές υψηλής προβολής και, με έναν πλήρως P2P χαρακτήρα, όλη η ισχύς αποδίδεται στους ψηφοφόρους.
• Ενσωμάτωση απορρήτου και μείξης στο πρωτόκολλο ψηφοφορίας σε επίπεδο δικτύου.
• Εύρεση ενός μοντέλου κρυπτοοικονομικών που να είναι ορθολογικό και πλήρως διαλειτουργικό με το Ethereum 2.0.
• Δημιουργία μιας μοναδικής απόδειξης που να επαληθεύεται εύκολα. Αυτό ανοίγει τη δυνατότητα οποιοδήποτε προγραμματιζόμενο L1 και L2 (EVM ή όχι) να αντιδρά σε οποιαδήποτε αποτελέσματα ψηφοφοριών του Ethereum. Ο μακροπρόθεσμος στόχος είναι να μπορεί κανείς να ψηφίζει σε οποιαδήποτε αλυσίδα και να επαληθεύει τα αποτελέσματα σε οποιαδήποτε άλλη. Αυτό θα μπορούσε να εξελιχθεί σε ένα είδος χρυσού κανόνα για την επαλήθευση Storage Proofs μεταξύ rollups / αλυσίδων μέσω SNARKs.