Ορισμός της ανώνυμης ψηφοφορίας

Πριν περάσουμε στις τεχνικές προδιαγραφές, αξίζει να εξηγήσουμε πώς ορίζουμε την ανώνυμη ψηφοφορία και γιατί καταλήξαμε σε αυτόν τον σχεδιασμό. Στο άρθρο ανακοίνωσης του προϊόντος παρουσιάζουμε δύο είδη ανωνυμίας: τη συσκότιση των ψηφοδελτίων (ballot obfuscation) και την ανωνυμία του ψηφοφόρου (voter anonymity).

Η συσκότιση των ψηφοδελτίων αναφέρεται στην ανωνυμία που προκύπτει από την απόκρυψη του περιεχομένου κάθε ψήφου, ενώ η ανωνυμία του ψηφοφόρου διακόπτει τον σύνδεσμο ανάμεσα σε κάθε ψηφοφόρο και την ψήφο του, χωρίς να κρύβει τις ίδιες τις ψήφους. Η δική μας υλοποίηση της ανώνυμης ψηφοφορίας βασίζεται στην ανωνυμία του ψηφοφόρου. Γιατί;

Καταρχάς, η συσκότιση των ψηφοδελτίων συνεπάγεται σημαντικούς συμβιβασμούς. Για να είναι μια ψηφοφορία επαληθεύσιμη από άκρο σε άκρο, οι ψηφοφόροι πρέπει να μπορούν να παρακολουθούν και να εξετάζουν το περιεχόμενο των ψηφοδελτίων που έχουν καταθέσει. Αν εξασφαλίσουμε την ανωνυμία μέσω της συσκότισης των ψηφοδελτίων, χάνουμε την ιδιότητα της επαληθευσιμότητας: όταν το περιεχόμενο κάθε ψήφου είναι κρυμμένο, είναι αδύνατο να επαληθεύσετε ότι η ψήφος σας καταμετρήθηκε και να ελέγξετε την ακεραιότητα της ψηφοφορίας.

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

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

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

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

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

Δέντρο Merkle του καταλόγου ψηφοφόρων

Αφετηρία του μηχανισμού καταλόγου ψηφοφόρων είναι ένα δέντρο Merkle του καταλόγου. Πρόκειται για μια δομή από κατακερματισμένα (hashed) δημόσια κλειδιά, καθένα από τα οποία αντιπροσωπεύει έναν εκλογέα με δικαίωμα ψήφου στον κατάλογο. Η χρήση δέντρου Merkle εδώ επιτρέπει ουσιαστικά σε κάθε έγκυρο ψηφοφόρο να αποδείξει ότι κατέχει ένα censusKey που ανήκει στον κατάλογο, χωρίς να γνωρίζει τα κλειδιά των υπόλοιπων ψηφοφόρων. Ο ψηφοφόρος υποβάλλει στη συνέχεια αυτή την απόδειξη ως μέρος του ψηφοδελτίου του. Στον φάκελο ψήφου (vote envelope) επισυνάπτεται επίσης ένα nullifier: ένα στοιχείο δεδομένων που παράγεται από το censusKey του χρήστη και το electionID και αντιστοιχεί μοναδικά στην ψήφο του.

Αν χρησιμοποιούνταν μόνο αυτή η απόδειξη, ο διοργανωτής μιας ψηφοφορίας θα μπορούσε να συσχετίσει κάθε φάκελο ψήφου, μέσω του nullifier του, με το censusKey ενός ψηφοφόρου, αίροντας την ανωνυμία της ψηφοφορίας. Για να το αποτρέψει αυτό, το Vocdoni χρησιμοποιεί zk-SNARKs ώστε να διασφαλίζεται η ανωνυμία της ψηφοφορίας.

zk-SNARKs για ανώνυμη ψηφοφορία¶

Το ακρωνύμιο zk-SNARK προέρχεται από το zero-knowledge Succinct Non-interactive ARgument of Knowledge (σύντομο μη διαδραστικό επιχείρημα γνώσης, μηδενικής γνώσης). Ένα zk-SNARK επιτρέπει σε έναν χρήστη να αποδείξει σε ένα τρίτο μέρος ότι κατέχει μια συγκεκριμένη πληροφορία, χωρίς να αποκαλύψει την ίδια την πληροφορία.

Στην περίπτωσή μας, τα zk-SNARKs επιτρέπουν στους ψηφοφόρους να αποδείξουν ότι ανήκουν στον κατάλογο ψηφοφόρων χωρίς να αποκαλύψουν το secretKey τους. Συγκεκριμένα, αυτό γίνεται με ένα zk-Circuit, δηλαδή ένα κύκλωμα λογισμικού σχεδιασμένο να παράγει μια απόδειξη μηδενικής γνώσης (Zero-Knowledge Proof, ZKP).

zk-Circuit¶

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

Το κύκλωμα μπορεί να χρησιμοποιηθεί για οποιαδήποτε ψηφοφορία με κατάλογο παρόμοιου μεγέθους και χρειάζεται να δημιουργηθεί μόνο μία φορά ανά μέγεθος. Πιο συγκεκριμένα, ένα κύκλωμα μπορεί να δημιουργηθεί και στη συνέχεια να επαναχρησιμοποιηθεί για οποιοδήποτε δέντρο Merkle καταλόγου με το ίδιο ύψος δέντρου. Καθώς χρησιμοποιούμε δυαδικό δέντρο, αυτό σημαίνει ότι χρειάζεται ένα κύκλωμα για κάθε τιμή n όπου το επιδιωκόμενο μέγεθος καταλόγου βρίσκεται εντός του εύρους 2^n (π.χ. 128, 256, ..., 8192, 16384 κ.ο.κ.).

Η δημιουργία του κυκλώματος βασίζεται σε μια τελετή αξιόπιστης αρχικοποίησης (trusted setup). Πρόκειται για μια διαδικασία παραγωγής των κλειδιών απόδειξης (prover) και επαλήθευσης (verifier) για το κύκλωμα και χαρακτηρίζεται «αξιόπιστη» επειδή, αν ένα μόνο μέρος έλεγχε ολόκληρη την παραγωγή αυτών των κλειδιών, θα μπορούσε να παράγει ψευδείς αποδείξεις. Γι' αυτό απαιτείται μια αποκεντρωμένη «τελετή» που διασφαλίζει την αξιοπιστία του κυκλώματος. Σε μια τέτοια τελετή, διάφορα μέρη με αντικρουόμενα συμφέροντα και σε διαφορετικές τοποθεσίες εκτελούν το καθένα από ένα βήμα της παραγωγής κλειδιών. Αρκεί έστω και ένα από αυτά τα μέρη να διατηρήσει την ακεραιότητά του για να είναι αδύνατη η παραγωγή ψευδούς απόδειξης.

Η απόδειξη franchise proof παράγεται με την εκτέλεση του κυκλώματος zk-SNARK.

• Ιδιωτικές είσοδοι: index, secretKey, census Merkle-proof
• Δημόσιες είσοδοι: census Merkle-root, nullifier, election ID, vote
• Έξοδος: franchise proof

Ορισμός της ανώνυμης ψηφοφορίας

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

Η συσκότιση των ψηφοδελτίων αναφέρεται στην ανωνυμία που προκύπτει από την απόκρυψη του περιεχομένου κάθε ψήφου, ενώ η ανωνυμία του ψηφοφόρου διακόπτει τον σύνδεσμο ανάμεσα σε κάθε ψηφοφόρο και την ψήφο του, χωρίς να κρύβει τις ίδιες τις ψήφους. Η δική μας υλοποίηση της ανώνυμης ψηφοφορίας βασίζεται στην ανωνυμία του ψηφοφόρου. Γιατί;

Καταρχάς, η συσκότιση των ψηφοδελτίων συνεπάγεται σημαντικούς συμβιβασμούς. Για να είναι μια ψηφοφορία επαληθεύσιμη από άκρο σε άκρο, οι ψηφοφόροι πρέπει να μπορούν να παρακολουθούν και να εξετάζουν το περιεχόμενο των ψηφοδελτίων που έχουν καταθέσει. Αν εξασφαλίσουμε την ανωνυμία μέσω της συσκότισης των ψηφοδελτίων, χάνουμε την ιδιότητα της επαληθευσιμότητας: όταν το περιεχόμενο κάθε ψήφου είναι κρυμμένο, είναι αδύνατο να επαληθεύσετε ότι η ψήφος σας καταμετρήθηκε και να ελέγξετε την ακεραιότητα της ψηφοφορίας.

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

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

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

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

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

Δέντρο Merkle του καταλόγου ψηφοφόρων

Αφετηρία του μηχανισμού καταλόγου ψηφοφόρων είναι ένα δέντρο Merkle του καταλόγου. Πρόκειται για μια δομή από κατακερματισμένα (hashed) δημόσια κλειδιά, καθένα από τα οποία αντιπροσωπεύει έναν εκλογέα με δικαίωμα ψήφου στον κατάλογο. Η χρήση δέντρου Merkle εδώ επιτρέπει ουσιαστικά σε κάθε έγκυρο ψηφοφόρο να αποδείξει ότι κατέχει ένα censusKey που ανήκει στον κατάλογο, χωρίς να γνωρίζει τα κλειδιά των υπόλοιπων ψηφοφόρων. Ο ψηφοφόρος υποβάλλει στη συνέχεια αυτή την απόδειξη ως μέρος του ψηφοδελτίου του. Στον φάκελο ψήφου (vote envelope) επισυνάπτεται επίσης ένα nullifier: ένα στοιχείο δεδομένων που παράγεται από το censusKey του χρήστη και το electionID και αντιστοιχεί μοναδικά στην ψήφο του.

Αν χρησιμοποιούνταν μόνο αυτή η απόδειξη, ο διοργανωτής μιας ψηφοφορίας θα μπορούσε να συσχετίσει κάθε φάκελο ψήφου, μέσω του nullifier του, με το censusKey ενός ψηφοφόρου, αίροντας την ανωνυμία της ψηφοφορίας. Για να το αποτρέψει αυτό, το Vocdoni χρησιμοποιεί zk-SNARKs ώστε να διασφαλίζεται η ανωνυμία της ψηφοφορίας.

zk-SNARKs για ανώνυμη ψηφοφορία¶

Το ακρωνύμιο zk-SNARK προέρχεται από το zero-knowledge Succinct Non-interactive ARgument of Knowledge (σύντομο μη διαδραστικό επιχείρημα γνώσης, μηδενικής γνώσης). Ένα zk-SNARK επιτρέπει σε έναν χρήστη να αποδείξει σε ένα τρίτο μέρος ότι κατέχει μια συγκεκριμένη πληροφορία, χωρίς να αποκαλύψει την ίδια την πληροφορία.

Στην περίπτωσή μας, τα zk-SNARKs επιτρέπουν στους ψηφοφόρους να αποδείξουν ότι ανήκουν στον κατάλογο ψηφοφόρων χωρίς να αποκαλύψουν το secretKey τους. Συγκεκριμένα, αυτό γίνεται με ένα zk-Circuit, δηλαδή ένα κύκλωμα λογισμικού σχεδιασμένο να παράγει μια απόδειξη μηδενικής γνώσης (Zero-Knowledge Proof, ZKP).

zk-Circuit¶

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

Το κύκλωμα μπορεί να χρησιμοποιηθεί για οποιαδήποτε ψηφοφορία με κατάλογο παρόμοιου μεγέθους και χρειάζεται να δημιουργηθεί μόνο μία φορά ανά μέγεθος. Πιο συγκεκριμένα, ένα κύκλωμα μπορεί να δημιουργηθεί και στη συνέχεια να επαναχρησιμοποιηθεί για οποιοδήποτε δέντρο Merkle καταλόγου με το ίδιο ύψος δέντρου. Καθώς χρησιμοποιούμε δυαδικό δέντρο, αυτό σημαίνει ότι χρειάζεται ένα κύκλωμα για κάθε τιμή n όπου το επιδιωκόμενο μέγεθος καταλόγου βρίσκεται εντός του εύρους 2^n (π.χ. 128, 256, ..., 8192, 16384 κ.ο.κ.).

Η δημιουργία του κυκλώματος βασίζεται σε μια τελετή αξιόπιστης αρχικοποίησης (trusted setup). Πρόκειται για μια διαδικασία παραγωγής των κλειδιών απόδειξης (prover) και επαλήθευσης (verifier) για το κύκλωμα και χαρακτηρίζεται «αξιόπιστη» επειδή, αν ένα μόνο μέρος έλεγχε ολόκληρη την παραγωγή αυτών των κλειδιών, θα μπορούσε να παράγει ψευδείς αποδείξεις. Γι' αυτό απαιτείται μια αποκεντρωμένη «τελετή» που διασφαλίζει την αξιοπιστία του κυκλώματος. Σε μια τέτοια τελετή, διάφορα μέρη με αντικρουόμενα συμφέροντα και σε διαφορετικές τοποθεσίες εκτελούν το καθένα από ένα βήμα της παραγωγής κλειδιών. Αρκεί έστω και ένα από αυτά τα μέρη να διατηρήσει την ακεραιότητά του για να είναι αδύνατη η παραγωγή ψευδούς απόδειξης.

Η απόδειξη franchise proof παράγεται με την εκτέλεση του κυκλώματος zk-SNARK.

• Ιδιωτικές είσοδοι: index, secretKey, census Merkle-proof
• Δημόσιες είσοδοι: census Merkle-root, nullifier, election ID, vote
• Έξοδος: franchise proof

Χωρίς να αποκαλύπτει το secretKey ή την απόδειξη Merkle του καταλόγου (Census Merkle Proof), το κύκλωμα αυτό μπορεί να αποδείξει ότι:

1. Ο ψηφοφόρος είναι ο κάτοχος του secretKey που αντιστοιχεί σε ένα συγκεκριμένο zkCensusKey.
2. Το zkCensusKey του ψηφοφόρου περιλαμβάνεται στο δέντρο Merkle του καταλόγου.
3. Το nullifier που παρέχει ο ψηφοφόρος αντιστοιχεί μοναδικά στο secretKey του και στο election ID μιας συγκεκριμένης ψηφοφορίας.

Αν και ο υπολογισμός είναι απαιτητικός σε επεξεργαστική ισχύ και μνήμη, οι ZKP μπορούν να παραχθούν από το πρόγραμμα-πελάτη του χρήστη, σε υλικό μέτριων δυνατοτήτων. Στο πρωτόκολλο Vocdoni, η απόδειξη επικυρώνεται από τους κόμβους του Vochain, τους miners και οποιοδήποτε τρίτο μέρος παρακολουθεί τη διαδικασία.

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

Δέντρα Merkle και δέντρα καταλόγου¶

Το δέντρο Merkle που χρησιμοποιείται για την κατασκευή του ανώνυμου καταλόγου πρέπει να είναι μια υλοποίηση φιλική προς τα zk-SNARKs. Καθώς χρησιμοποιούμε προς το παρόν τον μεταγλωττιστή Circom για τα κυκλώματα zk-SNARK, χρειαζόμαστε ένα δέντρο συμβατό με την υλοποίηση δέντρου Merkle της circomlib. Μια προδιαγραφή ενός τέτοιου δέντρου Merkle βρίσκεται εδώ.

Το Vochain χρησιμοποιεί το δέντρο Merkle arbo, μια υλοποίηση σε Go συμβατή με τον σχεδιασμό του Circom. Το δέντρο Merkle χρησιμοποιεί το Poseidon Hash, μια «φιλική προς SNARK» συνάρτηση hash που μπορεί αργότερα να αποδειχθεί μέσα σε κύκλωμα χωρίς να απαιτεί υπερβολικά πολλούς περιορισμούς (constraints). Το ακόλουθο διάγραμμα αποτυπώνει τη δομή δεδομένων των φύλλων του δέντρου Merkle που χρησιμοποιείται στο σχήμα της zk-census-proof.

Η τιμή index καθορίζεται από τον κατασκευαστή του δέντρου καταλόγου, ο οποίος διατηρεί μια τιμή index για κάθε δέντρο καταλόγου. Η τιμή αυτή αυξάνεται με την προσθήκη κάθε νέου φύλλου. Τα φύλλα δομούνται με αυτόν τον τρόπο για αποδοτικότερη χρήση των δέντρων Merkle: χωρούν έτσι τα κλειδιά περισσότερων χρηστών σε ένα μικρότερο δέντρο, μειώνοντας το μέγεθος του zk-Circuit. Αυτό συμβαίνει επειδή η τιμή (value) του key ενός φύλλου καθορίζει τη θέση του συγκεκριμένου φύλλου στο δέντρο.

Αν το κλειδί του φύλλου καθοριζόταν από το zkCensusKey αντί για ένα αυξανόμενο index, κάθε νέο φύλλο θα είχε σημαντική πιθανότητα σύγκρουσης πριν συμπληρωθούν όλες οι διαθέσιμες θέσεις φύλλων για δεδομένο ύψος. Τα δέντρα θα ήταν επομένως λιγότερο ισορροπημένα και θα απαιτούσαν μεγαλύτερα κυκλώματα για το ίδιο μέγεθος καταλόγου, λόγω αναποτελεσματικής χρήσης του χώρου του δέντρου. Με την προσέγγιση του αυξανόμενου index, αντίθετα, όλες οι θέσεις φύλλων μπορούν να συμπληρωθούν χωρίς ούτε μία σύγκρουση. Έτσι προκύπτουν πολύ μικρότερα κυκλώματα για τον ίδιο αριθμό χρηστών.

Δημιουργία των zk-Inputs¶

{
	"censusRoot": "51642541620950251760298704744678482162425252475654827255045491135352807540162",
	"censusSiblings": ["0","0","0","0"],
	"index": "30",
	"secretKey": "6190793965647866647574058687473278714480561351424348391693421151024369116465",
	"voteValue": ["100964581237483263846637432502620436451", "278307331411790712608582894981321409946"],
	"electionId": "10",
	"nullifier": "1938187656076799017313903315498318464349291455761501098436114043715056719301",
}

Προέλευση κάθε παραμέτρου zk-Input:

Όλες οι παράμετροι είναι string ή []string που αναπαριστούν bigInt ή []bigInt.

• censusRoot: υπολογίζεται από την αρχή καταλόγου (census authority) με βάση το δέντρο καταλόγου.
• censusSiblings: υπολογίζεται από την αρχή καταλόγου· είναι η απόδειξη Merkle
• ο χρήστης ανακτά τα siblings από το Vochain μέσω της πύλης (gateway).
• το μήκος του censusSiblings εξαρτάται από το zk-Circuit:
• Ο σχεδιασμός του δέντρου Merkle που χρησιμοποιείται στην circomlib έχει ως αποτέλεσμα να επιστρέφονται siblings διαφορετικού μήκους κατά τη δημιουργία μιας απόδειξης Merkle.
• Το βάθος του δέντρου, όπως ορίζεται από τη ρίζα προς τα φύλλα, εξαρτάται από κάθε φύλλο και τους γείτονές του.
• Περισσότερες λεπτομέρειες υπάρχουν στην προδιαγραφή του δέντρου Merkle.
• Για να εισαχθούν αυτά τα siblings στο κύκλωμα, το nLevels του κυκλώματος είναι σταθερό, οπότε το siblings.length πρέπει επίσης να είναι σταθερό.
• Το siblings.length εξαρτάται από το zk-Circuit που χρησιμοποιείται, και συγκεκριμένα από την παράμετρο nLevels του κυκλώματος
• Η λογική που πρέπει να υλοποιηθεί από την πλευρά του χρήστη βρίσκεται εδώ (go), γραμμές 67-70 και εδώ (js), γραμμή 23: while (siblings.length < this.levels) siblings.push(BigInt(0));
• index: καθορίζεται από το Vochain κατά την προσθήκη του zkCensusKey του χρήστη στο δέντρο καταλόγου
• secretKey: δημιουργείται από τον χρήστη
• voteValue: κατακερματισμένη τιμή της ψήφου του χρήστη, αποτελούμενη από δύο μεγάλους ακεραίους.
• Η ακατέργαστη ψήφος του χρήστη είναι ένας πίνακας τιμών μεταβλητού μήκους και οι τιμές του δεν χρειάζεται να ελεγχθούν στο κύκλωμα. Επιπλέον, οι τιμές μπορούν να είναι κρυπτογραφημένες.
• Καθώς οι κωδικοποιημένες τιμές ψήφου ενδέχεται να μη χωρούν σε σταθερό αριθμό εισόδων του κυκλώματος, υπολογίζουμε μια σύνοψη της ακατέργαστης ψήφου του χρήστη με μια συνάρτηση hash φιλική προς το EVM: sha256(vote_bytes). Η έξοδος του hash sha256 είναι ελαφρώς μεγαλύτερη από το πεδίο που χρησιμοποιείται στα SNARKs, οπότε χωρίζουμε την έξοδο του hash (32 bytes) σε 2 πίνακες των 16 bytes, τους ερμηνεύουμε ως ακεραίους (σε little-endian) και τους χρησιμοποιούμε ως εισόδους του κυκλώματος.
• Χρησιμοποιείται το hash sha256, ώστε, αν χρειαστεί στο μέλλον, να μπορεί να επαληθευτεί μέσα στο κύκλωμα. Η χρήση αυτή έχει δύο χαρακτηριστικά που πρέπει να έχετε υπόψη: το sha256 είναι δύο φορές ακριβότερο από το keccak256 σε όρους gas στο EVM, αλλά είναι υλοποιημένο σε circom, οπότε μπορεί να ελεγχθεί μέσα σε κύκλωμα· ο έλεγχος του sha256 μέσα σε κύκλωμα circom είναι ακριβός σε αριθμό περιορισμών (στην τρέχουσα έκδοση αυτής της προδιαγραφής, ο έλεγχος αυτός δεν γίνεται μέσα στο κύκλωμα).

h := sha256.Sum256(voteBytes) // voteBytes can be the votes array converted to bytes, or the encrypted votes
b1 := new(big.Int).SetBytes(swapEndianness(h[:16])) // swap endianness, as golang big int package works in big-endian, and we use little-endian
b2 := new(big.Int).SetBytes(swapEndianness(h[16:]))

Και η είσοδος json του voteValue για το κύκλωμα θα ήταν: "voteValue": [b1, b2]

• electionID: το αναγνωριστικό της ψηφοφορίας στην οποία συμμετέχει ο χρήστης
• nullifier: υπολογίζεται από τον χρήστη nullifier = poseidon.Hash(sk, electionID)

Ανώνυμη ψηφοφορία για DAOs

Για να απαντήσουμε στο ερώτημα «πώς μπορεί αυτή η τεχνολογία να χρησιμοποιηθεί για ψηφοφορίες DAO στο Ethereum», χρειάζεται να προσθέσουμε λίγο πλαίσιο:

• Προς το παρόν, η εσωτερική κρυπτογραφία, οι δομές δεδομένων και το δέντρο Merkle του Ethereum δεν είναι φιλικά προς τα zk-SNARKs, οπότε οι επιλογές είναι (για την ώρα) περιορισμένες.
• Το Vocdoni υποστηρίζει σήμερα ψηφοφορία με αποδείξεις αποθήκευσης Ethereum, που είναι επί του παρόντος ο πιο ασφαλής και χωρίς ανάγκη εμπιστοσύνης (trustless) τρόπος εκτέλεσης ψηφοφορίας εκτός αλυσίδας χωρίς κόστος gas (υλοποιημένος στο frontend https://voice.aragon.org)
• Αν και το Vocdoni δεν προσφέρει ακόμη πλήρη δεσμευτική εκτέλεση εκτός αλυσίδας (η ψηφοφορία εντός του Ethereum απαιτεί μια προσέγγιση optimistic), έχουμε πραγματοποιήσει δοκιμαστική υλοποίηση (proof-of-concept) σε αυτό το πεδίο και συνεχίζουμε την έρευνα για την επίτευξη πλήρων ιδιοτήτων (σύντομα έρχονται νέοι σχεδιασμοί και proof-of-concept).

Ο τρόπος με τον οποίο το Vocdoni μπορεί σήμερα να υποστηρίξει ανώνυμη ψηφοφορία σε DAOs είναι μέσω των παρακάτω βημάτων:

1. Δημιουργείται μια νέα ψηφοφορία στο blockchain του Vocdoni με censusRoot ίσο με τη ρίζα κατάστασης (state root) του Ethereum και τη διεύθυνση του έξυπνου συμβολαίου (smart contract) ERC20.
2. Οι χρήστες ανακτούν από το Web3 μια απόδειξη αποθήκευσης Ethereum που αποδεικνύει ότι κατέχουν tokens για ένα συμβόλαιο και μια ρίζα κατάστασης.
3. Οι χρήστες δημιουργούν ένα νέο προσωρινό secretKey και στέλνουν μια συναλλαγή στο blockchain του Vocdoni, αποδεικνύοντας ότι είναι εκλογείς με δικαίωμα ψήφου (μέσω της απόδειξης αποθήκευσης). Η συναλλαγή αυτή περιλαμβάνει το κατακερματισμένο secretKey, το οποίο προστίθεται σε ένα rolling Census που υπολογίζεται εσωτερικά από τη λογική του blockchain του Vocdoni. Το βήμα αυτό ονομάζεται προεγγραφή κλειδιού (key pre-register).
4. Μόλις ολοκληρωθεί η προεγγραφή, οι χρήστες μπορούν να ψηφίσουν ανώνυμα χρησιμοποιώντας το secretKey τους