Cicada verfügt über neuartige Datenschutzeigenschaften, minimiert Vertrauensannahmen und ist effizient genug, um im Ethereum-Mainnet verwendet zu werden.
**Geschrieben von:**Michael Zhu
Zusammengestellt von: Lynn, MarsBit
Alle sinnvoll funktionierenden Abstimmungssysteme basieren auf Integrität und Transparenz. Auf den ersten Blick macht dies die Blockchain zu einer idealen Plattform, auf der diese Systeme aufbauen können – tatsächlich haben viele dezentrale Organisationen erlaubnislose Abstimmungen als Mittel zum Ausdruck kollektiver Absichten angenommen, wobei sie oft über enorme Reichtümer verfügen oder wichtige Protokollparameter optimieren. Aber On-Chain-Voting hat auch Nachteile. Der Datenschutz ist noch unerforscht und unentwickelt, was für Web3-Abstimmungssysteme nicht gut ist – in den meisten derzeit verwendeten On-Chain-Abstimmungsprotokollen sind Stimmzettel und Abstimmungsergebnisse vollständig öffentlich. Ohne Privatsphäre können Abstimmungsergebnisse leicht manipuliert und die Anreize für Wähler falsch ausgerichtet werden, was möglicherweise zu undemokratischen Ergebnissen führt.
Aus diesem Grund veröffentlichen wir Cicada: eine neue Open-Source-Solidity-Bibliothek, die Timelock-Rätsel und wissensfreie Beweise nutzt, um private Abstimmungen in der Kette zu ermöglichen. Im Vergleich zu bestehenden Systemen verfügt Cicada über neuartige Datenschutzeigenschaften, minimiert Vertrauensannahmen und ist effizient genug, um im Ethereum-Mainnet eingesetzt zu werden.
In diesem Beitrag untersuchen wir den Stand des Wahlschutzes und geben eine allgemeine Beschreibung der Funktionsweise von Cicada (formelle Beweise folgen in Kürze). Wir empfehlen Entwicklern auch, sich das GitHub-Repository anzusehen – Cicada kann auf viele Arten optimiert und erweitert werden, um verschiedene Abstimmungsschemata und -funktionen zu unterstützen, und wir hoffen, mit der Community zusammenzuarbeiten, um diese Möglichkeiten zu erkunden.
Kurzübersicht über private Umfragen
In jedem Abstimmungssystem (on-chain oder anderweitig) müssen viele verschiedene Datenschutzebenen berücksichtigt werden. Die Offenlegung einzelner Stimmzettel, laufender Auszählungen und Wähleridentitäten wirken sich alle auf unterschiedliche Weise auf die Wählermotivation aus. Welche Datenschutzeigenschaften notwendig sind, hängt vom Kontext der Abstimmung ab. Einige davon tauchen häufig in der Kryptographie- und Sozialwissenschaftsliteratur auf:
- Stimmzettel-Datenschutz: Geheime Stimmzettel, auch als „australische Stimmzettel“ bekannt, wurden für reale Wahlsysteme entwickelt, um individuelle Wählerpräferenzen zu wahren und Bestechung und Nötigung einzudämmen (in der Kette gesetzt, erfordern wir möglicherweise eine stärkere Eigenschaft als Stimmzettel). Privatsphäre – siehe „Quittungslosigkeit“ weiter unten). Die Privatsphäre bei Abstimmungen kann auch die Tendenz zur sozialen Erwünschtheit abmildern – jemand hat weniger Druck, aufgrund dessen, was andere über seine Entscheidungen denken, abzustimmen.
- Vertraulichkeit laufender Auszählungen: Viele Abstimmungssysteme verbergen laufende Auszählungen oder wie viele Stimmen für jede Option bereits abgegeben wurden, während die Wähler noch abstimmen, um die Wahlbeteiligung und die Wähleranreize nicht zu beeinträchtigen. Wir haben dies in der realen Welt gesehen; zum Beispiel tendieren US-Senatoren, die später abstimmen, eher dazu, sich ihrer Partei anzuschließen, als Senatoren, die früher abstimmen. Und in der Kette: Bei der tokengewichteten Abstimmung können Wale ihre Gegner in einem falschen Sicherheitsgefühl wiegen, indem sie sie an der Spitze halten (einige sind möglicherweise zu faul zum Wählen, weil sie davon ausgehen, dass sie trotzdem gewinnen) und dann ihre eigene Stimme abgeben in letzter Minute Kommen Sie und entscheiden Sie über das Ergebnis.
- Anonymität der Wähler: In vielen realen Wahlsystemen ist Ihre Stimme nicht öffentlich, aber die Tatsache, dass Sie abgestimmt haben, ist oft öffentlich. Dies ist wichtig, um Wählerbetrug vorzubeugen, denn durch die Veröffentlichung von Wählerunterlagen können Menschen überprüfen, ob andere in ihrem Namen gewählt haben. On-Chain können wir jedoch Wählerbetrug verhindern und gleichzeitig die Anonymität mithilfe kryptografischer Primitive wahren. Mit Semaphore können Sie beispielsweise ohne Wissen nachweisen, dass Sie ein gültiger Wähler sind, der noch nicht gewählt hat.
- Keine Empfangsfähigkeit: Einzelne Wähler legen eine „Quittung“ ihres Stimmzettels vor, um zu beweisen, wie sie gegenüber Dritten gestimmt haben, was andernfalls zu einem Ticketverkauf führen könnte. Eine eng verwandte, aber stärkere Eigenschaft ist die Zwangresistenz, die jemanden daran hindert, Wähler zu einer bestimmten Wahl zu zwingen. Besonders attraktiv sind diese Immobilien in einem dezentralen Umfeld, in dem Stimmrechte durch Smart-Contract-Märkte liquidiert werden können. Leider sind sie auch schwer zu implementieren – Juels et al. weisen darauf hin, dass dies in einer erlaubnisfreien Umgebung ohne vertrauenswürdige Hardware unmöglich ist.
Cicada konzentriert sich auf den Datenschutz bei der Stimmauszählung während des Fluges, kann aber (wie wir später besprechen) mit Zero-Knowledge-Gruppenzugehörigkeitsnachweisen kombiniert werden, um die Anonymität der Wähler und den Datenschutz bei der Abstimmung zu gewährleisten.
Wir stellen vor: Cicada: Datenschutz bei der Stimmenzählung vor dem Problem der homomorphen Zeitsperre
Um die Privatsphäre der laufenden Stimmenauszählung zu gewährleisten, nutzt Cicada kryptografische Grundelemente, die (unserem Wissen) noch nie zuvor in der Kette verwendet wurden.
Erstens ist das Zeitschloss-Rätsel (Rivest, Shamir, Wagner, 1996) ein verschlüsseltes Rätsel, das ein Geheimnis verbirgt, das erst nach Ablauf einer vorgegebenen Zeitspanne gelüftet werden kann – genauer gesagt, das Rätsel kann wiederholt werden, indem man einige nicht parallele Berechnungen zum Entschlüsseln. Zeitgesperrte Rätsel sind im Zusammenhang mit Abstimmungen nützlich, um Privatsphäre bei der Durchführung von Statistiken zu gewährleisten: Benutzer können ihre Stimmen als zeitgesperrte Rätsel abgeben, sodass sie während des Abstimmungsprozesses geheim bleiben, aber nach der Abstimmung preisgegeben werden können. Im Gegensatz zu den meisten anderen privaten Abstimmungsstrukturen ermöglicht dies den Betrieb der statistischen Privatsphäre, ohne auf statistische Agenturen (z. B. Wahlhelfer, die Papier- oder digitale Stimmzettel zählen), Schwellenwertverschlüsselung (mehrere vertrauenswürdige Parteien müssen zusammenarbeiten, um eine Nachricht zu entschlüsseln) oder andere vertrauenswürdige Parteien angewiesen zu sein: Jeder kann ein Zeitschloss-Rätsel lösen, um sicherzustellen, dass das Ergebnis nach der Abstimmung bekannt gegeben wird.
Zweitens hat ein isomorphes Zeitschloss-Puzzle (Malavolta Thyagarajan, 2019) die zusätzliche Eigenschaft, dass einige Berechnungen zu verschlüsselten Werten mit Kenntnis des geheimen Schlüssels, Entschlüsselung des Puzzles oder Verwendung einer Hintertür möglich sind. Insbesondere ein linear homomorphes Timelock-Puzzle ermöglicht es uns, Puzzles miteinander zu kombinieren, um ein neues Puzzle zu erstellen, das die Summe der geheimen Werte des ursprünglichen Puzzles enthält.
Wie die Autoren des Papiers betonen, sind linear homomorphe Zeitschloss-Rätsel ein besonders gut geeignetes Grundelement für private Abstimmungen: Stimmen können als Rätsel kodiert und homomorph kombiniert werden, um ein kodiertes Endergebnis zu erhalten. Das bedeutet, dass nur eine Berechnung erforderlich ist, um das Endergebnis zu ermitteln, und nicht für jede Abstimmung ein eigenes Rätsel gelöst werden muss.
Eine neue Struktur: Effizienz und Kompromisse
Damit ein Abstimmungsschema in der Kette praktikabel ist, müssen mehrere Aspekte berücksichtigt werden. Erstens könnte ein Angreifer versuchen, Stimmen zu manipulieren, indem er einen falsch codierten Stimmzettel abgibt. Beispielsweise möchten wir möglicherweise, dass das Zeitsperrrätsel für jeden Stimmzettel als boolescher Wert codiert wird: „1“ für den Vorschlag, über den abgestimmt wird, und „0“ für „Nein“. Ein leidenschaftlicher Befürworter eines Vorschlags könnte versuchen, etwa „100“ zu kodieren, um sein effektives Stimmrecht zu erhöhen.
Wir können diesen Angriff verhindern, indem wir den Wähler zusammen mit der Stimmabgabe selbst einen wissensfreien Beweis für die Gültigkeit der Stimmabgabe vorlegen lassen. Allerdings sind wissensfreie Beweise rechenintensiv – um die Kosten der Wählerbeteiligung so gering wie möglich zu halten, sollten Beweise (1) auf der Clientseite effizient berechenbar und (2) in der Kette effizient überprüfbar sein.
Um die Beweise so effizient wie möglich zu gestalten, verwenden wir ein benutzerdefiniertes Sigma-Protokoll – wissensfreie Beweise, die für bestimmte algebraische Beziehungen entwickelt wurden, anstelle eines allgemeinen Beweissystems. Dadurch ist die Prüfzeit extrem schnell: Die Erstellung eines Stimmzettelgültigkeitsnachweises in Python dauert auf einem handelsüblichen Laptop 14 ms.
Obwohl der Validator für das Sigma-Protokoll konzeptionell einfach ist, erfordert er eine ziemlich große Anzahl modularer Potenzierungen. Das lineare homomorphe Schema von Malavolta und Thyagarajan verwendet die Paillier-Verschlüsselung, sodass diese Potenzierungen für einige RSA-Modulo N Modulo N^2 durchführen. Bei angemessenen N-Größen ist die Potenzierung in den meisten EVM-Ketten sehr teuer (Millionen Gas). Um die Kosten zu senken, verwendet Cicada Exponential ElGamal – Exponential ElGamal bietet weiterhin additive Homomorphismen, arbeitet aber mit kleineren Modulen (N statt N^2).
Ein Nachteil der Verwendung von ElGamal besteht darin, dass der letzte Schritt der Entschlüsselung der Zählung das Bruteforce des diskreten Protokolls erfordert (beachten Sie, dass dies außerhalb der Kette erfolgt und in der Kette effektiv überprüft wird). Daher funktioniert es nur, wenn die erwartete endgültige Stimmenzahl relativ gering ist (z. B. weniger als 2^32 oder etwa 4,3 Millionen Stimmen). Im ursprünglichen Paillier-basierten Schema können Zählungen unabhängig von ihrer Größe effizient entschlüsselt werden.
Auch die Wahl des RSA-Moduls N erfordert Kompromisse. Unsere Implementierung verwendet einen 1024-Bit-Modul für die Gaseffizienz. Dies liegt zwar deutlich über dem größten jemals öffentlich faktorisierten RSA-Modul (829 Bit), liegt jedoch unter der allgemein empfohlenen Größe von 2048 Bit für RSA-Verschlüsselung oder -Signierung. Unser Antrag erfordert jedoch keine langfristige Sicherheit: Sobald die Wahl vorbei ist, besteht kein Risiko, wenn N in Zukunft in Betracht gezogen wird. Es ist sinnvoll, einen relativ kleinen Modul zu verwenden, vorausgesetzt, dass Auszählungen und Stimmen nach Ablauf der Zeitsperre veröffentlicht werden. (Dies kann auch in Zukunft problemlos aktualisiert werden, wenn der Zerlegungsalgorithmus verbessert wird.)
Anonymität und Wahlberechtigung
Wie oben erwähnt, bietet Cicada Privatsphäre bei der Zählung von Runs – eine zeitlich begrenzte Puzzle-Eigenschaft, die die Stimmenauszählung während der Abstimmung geheim hält. Allerdings ist jeder einzelne Stimmzettel auch ein Zeitschloss-Puzzle, verschlüsselt unter denselben öffentlichen Parametern. Dies bedeutet, dass genau wie die Zählung entschlüsselt werden kann (durch Durchführung der erforderlichen Berechnungen), auch jede Stimme entschlüsselt werden kann. Mit anderen Worten: Cicada garantiert die Privatsphäre der Stimmzettel nur während der Abstimmung – wenn neugierige Beobachter den Stimmzettel eines bestimmten Wählers entschlüsseln möchten, können sie dies tun. Das Entschlüsseln eines einzelnen Stimmzettels ist genauso teuer wie das Entschlüsseln der endgültigen Auszählung. Daher ist es naiverweise O(n) Arbeit, einen Stimmzettel mit n Wählern vollständig zu entschlüsseln. Aber alle diese Stimmen können parallel entschlüsselt werden (vorausgesetzt, es gibt genügend Maschinen), was genauso viel Zeit in Anspruch nimmt wie die Entschlüsselung der endgültigen Zählung.
Für einige Stimmen ist dies möglicherweise nicht wünschenswert. Auch wenn wir damit zufrieden sind, vorübergehend den Datenschutz bei der Stimmauszählung zu gewährleisten, möchten wir möglicherweise, dass der Datenschutz bei Abstimmungen auf unbestimmte Zeit gewährleistet bleibt. Um dies zu erreichen, können wir Cicada mit einem anonymen Wählerberechtigungsprotokoll kombinieren, das mit einem wissensfreien Nachweis der Gruppenmitgliedschaft instanziiert wird. Selbst wenn der Stimmzettel freigegeben wird, zeigt sich auf diese Weise lediglich, dass jemand auf diese Weise abgestimmt hat – und das wissen wir bereits aus der Auszählung.
In unserem Repository enthalten wir einen Beispielvertrag, der Semaphore zur Anonymisierung von Wählern verwendet. Beachten Sie jedoch, dass der Cicada-Vertrag selbst keine Annahmen darüber macht, wie die Wahlberechtigung bestimmt oder durchgesetzt wird. Insbesondere können Sie Semaphore beispielsweise durch Semacaulk oder ZK Proof of State ersetzen (wie hier und hier vorgeschlagen).
Statistische Behörde
Eine unserer ersten Prioritäten bei der Entwicklung von Cicada bestand darin, die Notwendigkeit einer statistischen Agentur zu vermeiden: Viele private Abstimmungsstrukturen erfordern eine halb vertrauenswürdige statistische Agentur (oder ein delegiertes Komitee, das über sichere Mehrparteienberechnungen koordiniert wird), um Stimmen zu empfangen und zu aggregieren. Im Blockchain-Kontext bedeutet dies, dass diese Systeme nicht allein durch intelligente Verträge ausgeführt werden können, sondern ein gewisses Maß an menschlichem Eingreifen und Vertrauen erfordern.
In den meisten Strukturen wird den Auszählungsbehörden nicht auf ihre Integrität vertraut (sie können die Stimmenauszählung nicht manipulieren), wohl aber auf ihre Lebensfähigkeit – wenn sie offline sind, können sie das Endergebnis nicht berechnen, was die Abstimmung auf unbestimmte Zeit verzögert. In einigen Strukturen wird ihnen auch die Wahrung der Privatsphäre anvertraut – das heißt, sie wissen, wie jeder Einzelne abstimmt, von ihnen wird jedoch erwartet, dass sie die Abstimmungsergebnisse veröffentlichen, ohne diese Informationen preiszugeben.
Während statistische Autoritäten in vielen realen Szenarien eine vernünftige (und notwendige) Annahme darstellen, sind sie in einer Blockchain-Umgebung, in der unser Ziel darin besteht, das Vertrauen zu minimieren und Zensurresistenz sicherzustellen, nicht ideal.
Cicada erforscht eine von vielen Richtungen im Bereich der Privatsphäre bei Abstimmungen in der Kette und ergänzt einen Großteil der von anderen Gruppen durchgeführten Forschung. Wie oben erwähnt, ist Cicada eng mit anonymen Gruppenmitgliedschaftstechnologien wie Semaphoren, ZK-Proof-of-Storage und Rate-Limit-Invalidierern verbunden. Cicada kann auch den vom Nouns Vortex-Team vorgeschlagenen Optimistic Proof Checker integrieren, um die Gasbelastung der Wähler zu reduzieren.
Es besteht auch die Möglichkeit, Cicada so anzupassen, dass es verschiedene Abstimmungsschemata unterstützt (z. B. tokengewichtete Abstimmung, quadratische Abstimmung) – komplexere Schemata sind möglicherweise zu rechenintensiv für das Ethereum-Mainnet, können aber auf L2 praktisch sein. In diesem Sinne freuen wir uns über Ihre Beiträge, Empfehlungen und Vorschläge, wo Sie Cicada als nächstes hinbringen können.
*Danksagungen: Cicada wurde gemeinsam mit Joseph Bonneau entwickelt. Vielen Dank an Andrew Hall für Hintergrundinformationen zum historischen Hintergrund der Privatsphäre bei Abstimmungen. Vielen Dank auch an Robert Hackett für sein Feedback zu diesem Artikel. Besonderer Dank geht an Stephanie Zinn für die Bearbeitung. *
