Lernen Sie die technischen Spezifikationen der anonymen Stimmabgabe bei Vocdoni kennen und erfahren Sie, wie wir zu diesem Design gekommen sind.
Ferran
· 14 Min. Lesezeit
Bevor wir in die technischen Details eintauchen, lohnt sich ein Blick darauf, wie wir anonyme Stimmabgabe definieren und warum wir zu diesem Design gekommen sind. Im Artikel zur Produktankündigung stellen wir zwei Arten von Anonymität vor: die Verschleierung der Stimmzettel (ballot obfuscation) und die Wähler-Anonymität (voter anonymity).
Bei der Verschleierung der Stimmzettel entsteht Anonymität dadurch, dass der Inhalt jeder einzelnen Stimme verborgen bleibt. Die Wähler-Anonymität kappt dagegen die Verbindung zwischen Wähler und Stimme, ohne die Stimmen selbst zu verbergen. Unsere Implementierung der anonymen Stimmabgabe setzt auf Wähler-Anonymität. Warum?
Erstens bringt die Verschleierung der Stimmzettel erhebliche Kompromisse mit sich. Damit ein Abstimmungsprozess Ende-zu-Ende-verifizierbar ist, müssen Wähler den Inhalt ihrer abgegebenen Stimmzettel nachverfolgen und prüfen können. Sichern wir die Anonymität über die Verschleierung der Stimmzettel, verlieren wir die Verifizierbarkeit: Ist der Inhalt jeder Stimme verborgen, lässt sich weder verifizieren, dass Ihre Stimme gezählt wurde, noch die Integrität der Abstimmung auditieren.
Ein weiterer Nachteil der Stimmzettel-Verschleierung ist, dass sie sich in einem digitalen Abstimmungssystem nur schwer umsetzen lässt. Eine Technik dafür ist die homomorphe Verschlüsselung, die vorgeschlagen wurde, um klassische Wahlsysteme kryptografisch zu anonymisieren. Homomorphe Verschlüsselung erlaubt Berechnungen auf verschlüsselten Werten: Die Stimmen lassen sich auszählen, ohne den Inhalt eines einzigen Stimmzettels einzusehen. In der Theorie solide, bringt homomorphe Verschlüsselung jedoch viele Nachteile mit sich, die sie als Rückgrat einer Abstimmungstechnologie weniger attraktiv machen.
Am gravierendsten: Diese Methode erlaubt nur einfache Berechnungen auf den verschlüsselten Stimmzetteln, was Verfahren wie quadratisches oder präferenzielles Abstimmen schwieriger umsetzbar macht. Außerdem garantiert homomorphe Verschlüsselung zwar die Berechnung der Ergebnisse, nicht aber die Ende-zu-Ende-Verifikation des einzelnen Stimmzettels. Das Verfahren liefert keinen kryptografischen Beweis dafür, dass der Stimmzettel eines Wählers im Ergebnis enthalten und korrekt repräsentiert ist. Wir schätzen zudem, dass die Validierung des homomorphen Beweises eines Abstimmungsprozesses erhebliche Rechenressourcen beanspruchen würde, und der Aufwand wächst mit der Größe des Prozesses. Das könnte die Vorteile eines universell verifizierbaren Systems zunichtemachen, weil die Verifikation nur auf leistungsstarken, teuren Maschinen und über einen unverhältnismäßig langen Zeitraum möglich wäre.
Die Wähler-Anonymität hat gegenüber der homomorphen Verschlüsselung mehrere Vorteile. Erstens ist ein deutlich höheres Maß an Ende-zu-Ende-Verifizierbarkeit möglich. Die Verbindung zwischen Wähler und Stimmzettel muss zwar für dritte Beobachter undurchsichtig bleiben, die Wähler selbst können ihren Stimmzettel aber weiterhin identifizieren. Weil die Stimmzettel sichtbar sind, kann jeder Nutzer seine Stimme von der Abgabe bis zur Aufnahme in die Ergebnisse nachverfolgen. Darüber hinaus können Dritte erkennen, dass jeder Stimmzettel zu einem gültigen Wähler gehört und dass sein Inhalt korrekt gezählt wurde.
Die Wähler-Anonymität ermöglicht zudem in der Regel deutlich recheneffizientere Designs. Systeme mit Wähler-Anonymität verschleiern den Stimmzettel-Beweis jedes Wählers genau einmal, statt bei jeder neu abgegebenen Stimme die gesamte Ergebnismenge neu zu verarbeiten. Es ist kein aufwendiger Rechenschritt nötig, um Ergebnisse breit verfügbar zu machen. Wahlergebnisse können sogar während eines laufenden Abstimmungsprozesses veröffentlicht werden, ohne die Anonymität zu gefährden (sofern Timing-Korrelationsangriffe abgewehrt sind).
Deshalb haben wir uns entschieden, die Wähler-Anonymität direkt in unseren Zensus-Beweis-Mechanismus einzubauen.
Ausgangspunkt des Zensus-Mechanismus ist ein Zensus-Merkle-Baum. Das ist eine Struktur aus gehashten öffentlichen Schlüsseln, von denen jeder einen stimmberechtigten Wähler im Zensus repräsentiert. Der Merkle-Baum erlaubt es jedem gültigen Wähler zu beweisen, dass er einen censusKey besitzt, der zum Zensus gehört, ohne die Schlüssel anderer Wähler zu kennen. Diesen Beweis reicht der Wähler als Teil seines Stimmzettels ein. An diesen Stimmumschlag (vote envelope) ist außerdem ein nullifier angehängt: ein Datenwert, der aus dem censusKey des Nutzers und der electionID abgeleitet wird und eindeutig dessen Stimme entspricht.
Mit diesem Beweis allein könnte der Organisator eines Prozesses jeden Stimmumschlag über dessen nullifier mit dem censusKey eines Wählers korrelieren und die Abstimmung so de-anonymisieren. Um das zu verhindern, setzt Vocdoni zk-SNARKs ein und stellt damit die Anonymität der Stimmabgabe sicher.
zk-SNARK steht für zero-knowledge Succinct Non-interactive ARgument of Knowledge. Ein zk-SNARK erlaubt es einem Nutzer, gegenüber einem Dritten zu beweisen, dass er eine bestimmte Information besitzt, ohne die Information selbst offenzulegen.
In unserem Fall können Wähler mit zk-SNARKs beweisen, dass sie zum Zensus gehören, ohne ihren secretKey preiszugeben. Konkret geschieht das mit einem zk-Circuit, einem Software-Schaltkreis, der einen Zero-Knowledge-Beweis (ZKP) erzeugt.
Wir haben einen Circuit entworfen, mit dem Nutzer einen ZKP ihrer Zensus-Mitgliedschaft erzeugen können, ohne ihren secretKey offenzulegen. Der Circuit erhält private und öffentliche Eingaben; Daten, die die Identität des Wählers verraten könnten, bleiben privat. Die öffentlichen Eingaben werden im Stimmumschlag mitgeschickt, damit Validatoren sie gegen den Beweis prüfen und sicherstellen können, dass der Nutzer nicht zweimal abgestimmt hat.
Der Circuit lässt sich für jeden Prozess mit einem Zensus ähnlicher Größe verwenden und muss nur einmal pro Größe erzeugt werden. Genauer: Ein Circuit kann einmal erzeugt und dann für jeden Zensus-Merkle-Baum mit derselben Baumhöhe wiederverwendet werden. Da wir einen Binärbaum verwenden, wird ein Circuit für jeden Wert n benötigt, bei dem die angestrebte Zensusgröße im Bereich von 2^n liegt (z. B. 128, 256, ..., 8192, 16384 usw.).
Die Circuit-Erzeugung stützt sich auf eine Trusted-Setup-Zeremonie. Dabei werden die Prover- und Verifier-Schlüssel für den Circuit erzeugt. „Trusted“ heißt das Verfahren, weil eine Partei, die die gesamte Erzeugung dieser Schlüssel kontrolliert, falsche Beweise erzeugen könnte. Deshalb braucht es eine dezentrale „Zeremonie“, um die Zuverlässigkeit des Circuits sicherzustellen. Bei einer solchen Zeremonie führen mehrere Parteien mit gegensätzlichen Interessen und an unterschiedlichen Orten jeweils einen Schritt der Schlüsselerzeugung aus. Bleibt auch nur eine dieser Parteien integer, ist es unmöglich, einen falschen Beweis zu erzeugen.
Der franchise proof wird durch Ausführen des zk-SNARK-Circuits erzeugt.
index, secretKey, census Merkle-proofcensus Merkle-root, nullifier, election ID, votefranchise proof
Bevor wir in die technischen Details eintauchen, lohnt sich ein Blick darauf, wie wir anonyme Stimmabgabe definieren und warum wir zu diesem Design gekommen sind. Im Artikel zur Produktankündigung stellen wir zwei Arten von Anonymität vor: die Verschleierung der Stimmzettel (ballot obfuscation) und die Wähler-Anonymität (voter anonymity).
Bei der Verschleierung der Stimmzettel entsteht Anonymität dadurch, dass der Inhalt jeder einzelnen Stimme verborgen bleibt. Die Wähler-Anonymität kappt dagegen die Verbindung zwischen Wähler und Stimme, ohne die Stimmen selbst zu verbergen. Unsere Implementierung der anonymen Stimmabgabe setzt auf Wähler-Anonymität. Warum?
Erstens bringt die Verschleierung der Stimmzettel erhebliche Kompromisse mit sich. Damit ein Abstimmungsprozess Ende-zu-Ende-verifizierbar ist, müssen Wähler den Inhalt ihrer abgegebenen Stimmzettel nachverfolgen und prüfen können. Sichern wir die Anonymität über die Verschleierung der Stimmzettel, verlieren wir die Verifizierbarkeit: Ist der Inhalt jeder Stimme verborgen, lässt sich weder verifizieren, dass Ihre Stimme gezählt wurde, noch die Integrität der Abstimmung auditieren.
Ein weiterer Nachteil der Stimmzettel-Verschleierung ist, dass sie sich in einem digitalen Abstimmungssystem nur schwer umsetzen lässt. Eine Technik dafür ist die homomorphe Verschlüsselung, die vorgeschlagen wurde, um klassische Wahlsysteme kryptografisch zu anonymisieren. Homomorphe Verschlüsselung erlaubt Berechnungen auf verschlüsselten Werten: Die Stimmen lassen sich auszählen, ohne den Inhalt eines einzigen Stimmzettels einzusehen. In der Theorie solide, bringt homomorphe Verschlüsselung jedoch viele Nachteile mit sich, die sie als Rückgrat einer Abstimmungstechnologie weniger attraktiv machen.
Am gravierendsten: Diese Methode erlaubt nur einfache Berechnungen auf den verschlüsselten Stimmzetteln, was Verfahren wie quadratisches oder präferenzielles Abstimmen schwieriger umsetzbar macht. Außerdem garantiert homomorphe Verschlüsselung zwar die Berechnung der Ergebnisse, nicht aber die Ende-zu-Ende-Verifikation des einzelnen Stimmzettels. Das Verfahren liefert keinen kryptografischen Beweis dafür, dass der Stimmzettel eines Wählers im Ergebnis enthalten und korrekt repräsentiert ist. Wir schätzen zudem, dass die Validierung des homomorphen Beweises eines Abstimmungsprozesses erhebliche Rechenressourcen beanspruchen würde, und der Aufwand wächst mit der Größe des Prozesses. Das könnte die Vorteile eines universell verifizierbaren Systems zunichtemachen, weil die Verifikation nur auf leistungsstarken, teuren Maschinen und über einen unverhältnismäßig langen Zeitraum möglich wäre.
Die Wähler-Anonymität hat gegenüber der homomorphen Verschlüsselung mehrere Vorteile. Erstens ist ein deutlich höheres Maß an Ende-zu-Ende-Verifizierbarkeit möglich. Die Verbindung zwischen Wähler und Stimmzettel muss zwar für dritte Beobachter undurchsichtig bleiben, die Wähler selbst können ihren Stimmzettel aber weiterhin identifizieren. Weil die Stimmzettel sichtbar sind, kann jeder Nutzer seine Stimme von der Abgabe bis zur Aufnahme in die Ergebnisse nachverfolgen. Darüber hinaus können Dritte erkennen, dass jeder Stimmzettel zu einem gültigen Wähler gehört und dass sein Inhalt korrekt gezählt wurde.
Die Wähler-Anonymität ermöglicht zudem in der Regel deutlich recheneffizientere Designs. Systeme mit Wähler-Anonymität verschleiern den Stimmzettel-Beweis jedes Wählers genau einmal, statt bei jeder neu abgegebenen Stimme die gesamte Ergebnismenge neu zu verarbeiten. Es ist kein aufwendiger Rechenschritt nötig, um Ergebnisse breit verfügbar zu machen. Wahlergebnisse können sogar während eines laufenden Abstimmungsprozesses veröffentlicht werden, ohne die Anonymität zu gefährden (sofern Timing-Korrelationsangriffe abgewehrt sind).
Deshalb haben wir uns entschieden, die Wähler-Anonymität direkt in unseren Zensus-Beweis-Mechanismus einzubauen.
Ausgangspunkt des Zensus-Mechanismus ist ein Zensus-Merkle-Baum. Das ist eine Struktur aus gehashten öffentlichen Schlüsseln, von denen jeder einen stimmberechtigten Wähler im Zensus repräsentiert. Der Merkle-Baum erlaubt es jedem gültigen Wähler zu beweisen, dass er einen censusKey besitzt, der zum Zensus gehört, ohne die Schlüssel anderer Wähler zu kennen. Diesen Beweis reicht der Wähler als Teil seines Stimmzettels ein. An diesen Stimmumschlag (vote envelope) ist außerdem ein nullifier angehängt: ein Datenwert, der aus dem censusKey des Nutzers und der electionID abgeleitet wird und eindeutig dessen Stimme entspricht.
Mit diesem Beweis allein könnte der Organisator eines Prozesses jeden Stimmumschlag über dessen nullifier mit dem censusKey eines Wählers korrelieren und die Abstimmung so de-anonymisieren. Um das zu verhindern, setzt Vocdoni zk-SNARKs ein und stellt damit die Anonymität der Stimmabgabe sicher.
zk-SNARK steht für zero-knowledge Succinct Non-interactive ARgument of Knowledge. Ein zk-SNARK erlaubt es einem Nutzer, gegenüber einem Dritten zu beweisen, dass er eine bestimmte Information besitzt, ohne die Information selbst offenzulegen.
In unserem Fall können Wähler mit zk-SNARKs beweisen, dass sie zum Zensus gehören, ohne ihren secretKey preiszugeben. Konkret geschieht das mit einem zk-Circuit, einem Software-Schaltkreis, der einen Zero-Knowledge-Beweis (ZKP) erzeugt.
Wir haben einen Circuit entworfen, mit dem Nutzer einen ZKP ihrer Zensus-Mitgliedschaft erzeugen können, ohne ihren secretKey offenzulegen. Der Circuit erhält private und öffentliche Eingaben; Daten, die die Identität des Wählers verraten könnten, bleiben privat. Die öffentlichen Eingaben werden im Stimmumschlag mitgeschickt, damit Validatoren sie gegen den Beweis prüfen und sicherstellen können, dass der Nutzer nicht zweimal abgestimmt hat.
Der Circuit lässt sich für jeden Prozess mit einem Zensus ähnlicher Größe verwenden und muss nur einmal pro Größe erzeugt werden. Genauer: Ein Circuit kann einmal erzeugt und dann für jeden Zensus-Merkle-Baum mit derselben Baumhöhe wiederverwendet werden. Da wir einen Binärbaum verwenden, wird ein Circuit für jeden Wert n benötigt, bei dem die angestrebte Zensusgröße im Bereich von 2^n liegt (z. B. 128, 256, ..., 8192, 16384 usw.).
Die Circuit-Erzeugung stützt sich auf eine Trusted-Setup-Zeremonie. Dabei werden die Prover- und Verifier-Schlüssel für den Circuit erzeugt. „Trusted“ heißt das Verfahren, weil eine Partei, die die gesamte Erzeugung dieser Schlüssel kontrolliert, falsche Beweise erzeugen könnte. Deshalb braucht es eine dezentrale „Zeremonie“, um die Zuverlässigkeit des Circuits sicherzustellen. Bei einer solchen Zeremonie führen mehrere Parteien mit gegensätzlichen Interessen und an unterschiedlichen Orten jeweils einen Schritt der Schlüsselerzeugung aus. Bleibt auch nur eine dieser Parteien integer, ist es unmöglich, einen falschen Beweis zu erzeugen.
Der franchise proof wird durch Ausführen des zk-SNARK-Circuits erzeugt.
index, secretKey, census Merkle-proofcensus Merkle-root, nullifier, election ID, votefranchise proof
Ohne den secretKey oder den Zensus-Merkle-Beweis offenzulegen, kann dieser Circuit nachweisen:
secretKey, der zu einem bestimmten zkCensusKey gehört.zkCensusKey des Wählers ist im Zensus-Merkle-Baum enthalten.nullifier entspricht eindeutig seinem secretKey und der election ID eines bestimmten Abstimmungsprozesses.Obwohl die Berechnung CPU- und speicherintensiv ist, lassen sich ZKPs im Client des Nutzers auf bescheidener Hardware erzeugen. Im Vocdoni-Protokoll wird der Beweis von den Vochain-Knoten, den Minern und jedem Dritten validiert, der den Prozess beobachtet.
Der Circuit ist auf seine Mindestanforderungen reduziert und optimiert, damit er auf jeder Art von Client-Hardware zugänglich bleibt. Aus diesem Grund verwenden wir keine Signaturprüfung, sondern einen Ansatz mit secretKey.
Der Merkle-Baum, aus dem der anonyme Zensus aufgebaut wird, muss eine zk-SNARK-freundliche Implementierung sein. Da wir derzeit den Circom-Compiler für die zk-SNARK-Circuits verwenden, brauchen wir einen Baum, der mit der Merkle-Baum-Implementierung von circomlib kompatibel ist. Eine Spezifikation eines solchen Merkle-Baums finden Sie hier.
Vochain verwendet den arbo-Merkle-Baum, eine Go-Implementierung, die mit dem Circom-Design kompatibel ist. Der Merkle-Baum nutzt den Poseidon-Hash, eine „SNARK-freundliche“ Hash-Funktion, die sich später innerhalb eines Circuits beweisen lässt, ohne zu viele Constraints zu erfordern. Das folgende Diagramm zeigt die Datenstruktur der Blätter des Merkle-Baums, der im Schema des zk-census-proof verwendet wird.
Den index-Wert legt der Ersteller des Zensus-Baums fest, der für jeden Zensus-Baum einen eigenen index-Wert führt. Dieser Wert wird mit jedem neuen Blatt hochgezählt. Die Blätter sind so strukturiert, um die Merkle-Bäume effizienter zu nutzen: Es passen mehr Nutzerschlüssel in einen kleineren Baum, was die Größe des zk-Circuits reduziert. Der Grund: Der Wert (value) des Schlüssels (key) eines Blattes bestimmt dessen Position im Baum.
Würde der Schlüssel eines Blattes durch den zkCensusKey statt durch einen inkrementellen index bestimmt, hätte jedes neue Blatt eine erhebliche Kollisionswahrscheinlichkeit, bevor alle verfügbaren Blattplätze einer gegebenen Höhe gefüllt sind. Die Bäume wären dadurch weniger ausgeglichen und würden wegen der ineffizienten Nutzung des Baumraums größere Circuits für dieselbe Zensusgröße erfordern. Mit dem inkrementellen Index lassen sich dagegen alle Blattplätze ohne eine einzige Kollision füllen. Das ergibt deutlich kleinere Circuits für dieselbe Nutzerzahl.
{
"censusRoot": "51642541620950251760298704744678482162425252475654827255045491135352807540162",
"censusSiblings": ["0","0","0","0"],
"index": "30",
"secretKey": "6190793965647866647574058687473278714480561351424348391693421151024369116465",
"voteValue": ["100964581237483263846637432502620436451", "278307331411790712608582894981321409946"],
"electionId": "10",
"nullifier": "1938187656076799017313903315498318464349291455761501098436114043715056719301",
}
Herkunft der einzelnen zk-Input-Parameter:
Alle Parameter sind string oder []string und repräsentieren bigInt bzw. []bigInt.
censusRoot: wird von der Zensus-Autorität aus dem Zensus-Baum berechnet.censusSiblings: wird von der Zensus-Autorität berechnet; das ist der Merkle-Beweis.censusSiblings hängt vom zk-Circuit ab:nLevels des Circuits fest vorgegeben; daher muss auch siblings.length fest sein.siblings.length hängt vom verwendeten zk-Circuit ab, konkret vom Parameter nLevels des Circuits.while (siblings.length < this.levels) siblings.push(BigInt(0));index: wird von der Vochain festgelegt, wenn der zkCensusKey des Nutzers in den Zensus-Baum aufgenommen wird.secretKey: wird vom Nutzer erzeugt.voteValue: gehashter Wert der Nutzerstimme, bestehend aus zwei großen Ganzzahlen.sha256(vote_bytes). Die Ausgabe des sha256-Hashes ist etwas größer als das in SNARKs verwendete Feld; deshalb teilen wir die Hash-Ausgabe (32 Bytes) in zwei 16-Byte-Arrays, interpretieren sie als Ganzzahlen (Little-Endian) und verwenden sie als Circuit-Eingaben.sha256-Hash, weil er sich bei Bedarf künftig innerhalb des Circuits verifizieren lässt. Dabei sind zwei Eigenschaften zu beachten: sha256 ist in der EVM in Bezug auf Gas doppelt so teuer wie keccak256, ist aber in Circom implementiert und kann daher innerhalb eines Circuits geprüft werden; die Prüfung von sha256 in einem Circom-Circuit ist allerdings teuer, gemessen an der Zahl der Constraints (in der aktuellen Version dieser Spezifikation wird das nicht im Circuit geprüft).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:]))
Die JSON-Eingabe des voteValue für den Circuit wäre dann: "voteValue": [b1, b2]
electionID: die ID der Wahl oder Abstimmung, an der der Nutzer teilnimmt.nullifier: wird vom Nutzer berechnet: nullifier = poseidon.Hash(sk, electionID)Um die Frage zu beantworten, wie sich diese Technologie für DAO-Abstimmungen auf Ethereum nutzen lässt, braucht es etwas Kontext:
So kann Vocdoni derzeit anonyme Abstimmungen in DAOs unterstützen:
secretKey und senden eine Transaktion an die Vocdoni-Blockchain, mit der sie (über den Storage Proof) nachweisen, dass sie stimmberechtigt sind. Diese Transaktion enthält den gehashten secretKey, der einem rolling Census hinzugefügt wird, den die Logik der Vocdoni-Blockchain intern berechnet. Dieser Schritt heißt Key-Pre-Register.secretKey anonym abstimmen.
Vocdoni hat ein neues DKG-Protokoll entwickelt, das per Design nicht-interaktiv ist, im Betrieb asynchron arbeitet und auf kryptografischen Standardprimitiven aufbaut.
Jordi Pinyana
6 Min. Lesezeit
In den vergangenen Jahren liefen Abstimmungen bei Vocdoni auf Vochain, unserer eigens für Abstimmungen entwickelten L1-Blockchain. Wie jede Blockchain gab sie uns etwas Mächtiges:…
Pau Escrich
4 Min. Lesezeit
Wir haben erfolgreich eine Pre-Seed-Runde über 1 Million US-Dollar von Angel-Investoren abgeschlossen, um DAVINCI zu entwickeln. DAVINCI überwindet die Grenzen bestehender Abstimmungssysteme und bietet eine zensurresistente, gasfreie, bestechungssichere, skalierbare und anonyme Lösung für digitale Governance.
Pau Escrich
5 Min. Lesezeit