Der P + Epsilon -Angriff

Besonderer Dank geht an Andrew Miller für den Angriff und Zack Hess, Vlad Zamfir und Paul Sztorc zur Diskussion und Antworten

Eine der interessanteren Überraschungen in der Kryptoökonomie in den letzten Wochen kam aus einem Angriff auf Schellingcoin Anfang dieses Monats von Andrew Miller konzipiert. Obwohl immer verstanden wurde, dass Schellingcoin und ähnliche Systeme (einschließlich der fortgeschritteneren Truthcoin Konsens), verlassen Sie sich auf eine neue und ungetestete kryptoökonomische Sicherheitsannahme – dass man sich sicher darauf verlassen kann, dass Menschen in einem gleichzeitigen Konsensspiel ehrlich wirken, nur weil sie glauben, dass alle anderen die Probleme, die bisher aufgeworfen wurden, mit relativ marginaler Probleme wie eine Angriffsleistung zu tun haben, aber die Fähigkeit eines Angreifers, ein kleines, aber zunehmendem Einfluss auf den Einfluss zu haben, den Ausfluss auf die Aufnahme des Auftriebs auf die Ausgabe von Aufträgen bei der Ausübung von Aufenthaltsdurchausfüßern, bei der Sie sich bei der Ausübung von Aufenthaltszeiten mit der Aufnahme von Anlehnung anwenden. Dieser Angriff hingegen zeigt ein viel grundlegenderes Problem.

Das Szenario wird wie folgt beschrieben. Angenommen, es gibt ein einfaches Schelling -Spiel, bei dem Benutzer darüber abstimmen, ob eine bestimmte Tatsache wahr ist (1) oder falsch (0); Sagen Sie in unserem Beispiel, dass es tatsächlich falsch ist. Jeder Benutzer kann entweder 1 oder 0 abstimmen. Wenn ein Benutzer genauso wie die Mehrheit stimmt, erhalten er eine Belohnung für p; Ansonsten erhalten sie 0. So sieht die Auszahlungsmatrix wie folgt aus:

Die Theorie ist, dass, wenn jeder erwartet, dass jeder andere wahrheitsgemäß abstimmt, ihr Anreiz auch ist, auch wahrheitsgemäß abzustimmen, um die Mehrheit einzuhalten, und das ist der Grund, warum man von anderen erwarten kann, dass sie überhaupt ehrlich stimmen. ein selbstverstärkendes Nash-Gleichgewicht.

Nun der Angriff. Angenommen, der Angreifer verpflichtet sich glaubwürdig (z. B. über einen Ethereum -Vertrag, indem er einfach den Ruf des eigenen Rufs aufnahm oder den Ruf eines vertrauenswürdigen Treuhandanbieters nutzt), um X an die Wähler auszuzahlen, die 1 nach dem Spiel gestimmt haben.

Daher ist es eine dominierende Strategie für jeden, 1 zu wählen, egal was Sie glauben, dass die Mehrheit tun wird. Unter der Annahme, dass das System nicht von Altruisten dominiert wird, wird die Mehrheit 1 wählen, und so muss der Angreifer überhaupt nichts bezahlen. Der Angriff hat es erfolgreich gelungen, den Mechanismus zu null Kosten zu übernehmen. Beachten Sie, dass sich dies von Nicholas Houys Argument darüber unterscheidet 51% Angriffe auf Null-Kosten-Angriffe auf den Einsatz (Ein Argument, das technisch erweiterbar für ASIC-basierte Arbeitsprogramme ist) hier nein nein epistemische Übernahme ist erforderlich; Auch wenn jeder in der Überzeugung, dass der Angreifer scheitern wird, tot bleibt, besteht sein Anreiz immer noch darin, den Angreifer zu stimmen, da der Angreifer das Versagensrisiko selbst einnimmt.

Erhöhung der Schemen

Es gibt einige Möglichkeiten, die man nehmen kann, um zu versuchen, den Schelling -Mechanismus zu retten. Ein Ansatz ist, dass wir anstelle von rund N des Schells -Konsens selbst die Entscheidung, wer auf der Grundlage des “Mehrheitsmehrs ist richtig” -Prinzips belohnt wird, Runde N + 1 verwenden, um festzustellen, wer während der Runde N belohnt werden soll. Das Standardgleichgewicht ist, dass nur Personen, die während der Runde n ordnungsgemäß gewählt wurden (sowohl in der tatsächlichen Tatsache und, wer in Runde N – 1), belohnt werden sollte. Theoretisch erfordert dies ein Angreifer, der einen kostenlosen Angriff ausführen möchte, um nicht nur eine Runde, sondern auch alle zukünftigen Runden zu korrumpieren, was die erforderliche Kapitaleinzahlung macht, die der Angreifer unbegrenzt machen muss.

Dieser Ansatz hat jedoch zwei Mängel. Zunächst ist der Mechanismus zerbrechlich: Wenn der Angreifer es schafft, in der fernen Zukunft einige Runde zu verderben, indem er P + ε an alle tatsächlich auszahlt, unabhängig davon, wer gewinnt, dann führt die Erwartung dieser korrupten Runde einen Anreiz, mit dem Angreifer zusammenzuarbeiten. Daher ist es teuer, eine Runde zu korrumpieren, aber es ist nicht viel teurer, Tausende von Runden zu korrumpieren.

Zweitens wegen DiskontierungDie erforderliche Kaution zur Überwindung des Programms muss nicht unendlich sein. Es muss nur sehr sehr groß sein (dh umgekehrt proportional zum vorherrschenden Zinssatz). Aber wenn wir nur das erforderliche Mindestbestechungsgeld größer wollen, dann gibt es eine viel einfachere und bessere Strategie dafür. Pioniert von Paul Storcz: verlangen die Teilnehmer, eine große Ablagerung abzulegen und einen Mechanismus aufzubauen, durch den es umso mehr Mittel auf dem Spiel steht. An der Grenze, bei der etwas mehr als 50% der Stimmen für ein Ergebnis und 50% zugunsten des anderen sind, die gesamte Kaution, die es den Minderheitenwählern genommen hat. Dies stellt sicher, dass der Angriff immer noch funktioniert, aber das Bestechungsgeld muss nun größer sein als die Kaution (ungefähr gleich der Auszahlung geteilt durch die Discount-Rate, wodurch uns das unendliche Rundspiel gleichermaßen Leistung erbringt) und nicht nur die Auszahlung für jede Runde. Um einen solchen Mechanismus zu überwinden, müsste man daher nachweisen können, dass man einen Angriff von 51% abziehen kann, und wir können uns vielleicht einfach wohl fühlen, wenn man angenommen wird, dass Angreifer dieser Größe nicht existieren.

Ein anderer Ansatz besteht darin, sich auf die Gegenkoordination zu verlassen. Im Wesentlichen koordinieren Sie irgendwie durch glaubwürdige Verpflichtungen bei der Abstimmung von A (wenn a die Wahrheit ist) mit Wahrscheinlichkeit von 0,6 und B mit Wahrscheinlichkeit 0,4, wobei die Theorie darin besteht, dass Benutzer (probabilistisch) die Belohnung des Mechanismus und einen Teil des Angreifer gleichzeitig beanspruchen. Dies scheint besonders gut in Spielen zu funktionieren, bei denen das Spiel stand, anstatt für jeden mehrheitlich konformen Wähler eine ständige Belohnung zu zahlen, so strukturiert ist, dass die individuelle Auszahlungen anpassen, um dieses Ziel zu erreichen, ist erforderlich. In solchen Situationen ist es aus Sicht der kollektiven Rationalität in der Tat der Fall, dass die Gruppe einen höchsten Gewinn erzielt, indem 49% ihrer Mitglieder stimmen, um die Belohnung des Angreifers zu beanspruchen, und 51% stimmen A ab, um sicherzustellen, dass die Belohnung des Angreifers ausgezahlt wird.

Dieser Ansatz selbst leidet jedoch unter dem Fehler, dass, wenn das Bestechungsgelder des Angreifers hoch genug ist, selbst von dort aus man defekt sein kann. Das grundlegende Problem ist, dass bei einer probabilistischen gemischten Strategie zwischen A und B für jede Rendite immer (fast) linear mit dem Wahrscheinlichkeitsparameter ändert. Wenn es für den Einzelnen sinnvoller ist, für B zu stimmen als für A, ist es auch sinnvoller, mit der Wahrscheinlichkeit von 0,51 für B zu stimmen als mit der Wahrscheinlichkeit von 0,49 für B, und die Stimmen mit Wahrscheinlichkeit 1 für B wird noch besser funktionieren.

Daher wird jeder die Strategie “49% für 1” übernehmen, indem sie einfach immer 1 für 1 stimmt, und so wird 1 gewinnen und der Angreifer hat die kostenlose Übernahme gelungen. Die Tatsache, dass solche komplizierten Programme existieren und so nahe kommen, dass “wir zu funktionieren”, deutet darauf hin, dass vielleicht in naher Zukunft ein komplexes Gegenkoordinationsschema entstehen wird, das tatsächlich funktioniert. Wir müssen jedoch auf die Eventualität vorbereitet sein, dass kein solches Schema entwickelt wird.

Weitere Folgen

Angesichts der bloßen Anzahl kryptoökonomischer Mechanismen, die Schellingcoin ermöglicht, und der Bedeutung solcher Schemata in fast allen rein “vertrauensfreien” Versuchen, jegliche Art von Verbindung zwischen der kryptografischen Welt und der realen Welt herzustellen, stellt dieser Angriff eine potenzielle schwerwiegende Bedrohung dar – obwohl wir später sehen werden, dass Schemen Schemes als Kategorie als Kategorie zutreffend zutreffen werden. Interessanter ist jedoch die viel größere Klasse von Mechanismen, die auf den ersten Blick nicht ganz wie Schellingcoin aussehen, aber tatsächlich sehr ähnliche Stärken und Schwächen haben.

Zeigen wir insbesondere auf ein sehr spezifisches Beispiel: Arbeitsweise. Der Nachweis der Arbeit ist in der Tat ein Multi-Gleichgewichtsspiel, in dem Schemen Schema sind: Wenn es zwei Gabeln gibt, A und B, dann erhalten Sie 25 BTC und wenn Sie sich auf der Gabel, die Sie verlieren, Sie nichts bekommen.

Nehmen wir nun an, ein Angreifer startet gleichzeitig einen Doppelabend-Angriff gegen viele Parteien (diese Anforderung stellt sicher, dass es keine einzige Partei mit sehr starkem Anreiz gibt, sich dem Angreifer zu widersetzen, und der Opposition wird stattdessen zu einem öffentlichen Wohl. Der Angreifer verpflichtet sich jedoch glaubwürdig, 25,01 BTC an alle auszuzahlen, die bei B abgebaut werden, wenn B endet. Daher wird die Auszahlungsmatrix:

Der Bergbau an B ist also eine dominante Strategie, unabhängig von den epistemischen Überzeugungen, und so mines auf B, und so gewinnt der Angreifer und zahlt sich überhaupt nichts aus. Beachten Sie insbesondere, dass wir im Arbeitsnachweis keine Einlagen haben, sodass das erforderliche Bestechungsvolumen nur für die Bergbaubelohnung multipliziert mit der Gabellänge und nicht der Kapitalkosten von 51% aller Bergbaugeräte ist. Aus kryptoökonomischer Sicherheitsansicht kann man in gewissem Sinne sagen, dass der Arbeitsnachweis praktisch kein kryptoökonomischer Sicherheitsrand hat (wenn Sie die Gegner des Beweises des Einsatzes satt haben, Sie darauf zu zeigen Dieser Artikel von Andrew PoelstraFühlen Sie sich frei, sie hier als Antwort zu verknüpfen). Wenn man sich mit dem wirklich unwohl fühlt schwache Subjektivität Bedingung des reinen Beweiss für den Einsatz, dann folgt, dass die richtige Lösung möglicherweise darin besteht, den Nachweis der Arbeit mit hybriden Beweis für den Einsatz zu erweitern, indem Sicherheitsvorkommen und doppelte Stimmen in den Bergbau hinzugefügt werden.

Natürlich hat in der Praxis der Arbeitsnachweis trotz dieses Fehlers überlebt, und in der Tat kann es in der Tat noch lange überleben. Es kann nur so sein, dass es einen Grad an Altruismus gibt, dass Angreifer nicht zu 100% davon überzeugt sind, dass sie erfolgreich sein werden – aber wenn wir uns auf Altruismus verlassen dürfen, funktioniert der naive Beweis für Stachel auch gut. Auch Schemenschemata arbeiten möglicherweise einfach in der Praxis, auch wenn sie theoretisch nicht perfekt klingen.

Im nächsten Teil dieses Beitrags werden das Konzept der “subjektiven” Mechanismen detaillierter diskutiert und wie sie verwendet werden können, um einige dieser Probleme theoretisch umzugehen.