Technische Zusammenfassung: Adversarial Procurement in Blockchains

Problemstellung

Die Arbeit behandelt die Herausforderung des adversarial procurement (feindseligen Beschaffens) in Blockchain-Protokollen, speziell im Kontext aufkommender Designs, die die rechnerische Asymmetrie zwischen der Ausführung und der Verifizierung von Aufgaben nutzen (z. B. Zero-Knowledge-Beweise oder SNARKs). In diesen Systemen muss ein Protokoll teure rechnerische Aufgaben (wie das Erstellen eines Gültigkeitsbeweises für einen Block) an eine Menge von $n$ pseudonymen, nicht vertrauenswürdigen Beweiser auslagern.

Das Kernproblem besteht darin, einen Mechanismus zu entwerfen, der:

1. Mindestens einen Beweiser incentiviert, die Aufgabe auszuführen (Sicherstellung von Liveness).
2. Den wirtschaftlichen Verlust im Worst-Case-Szenario minimiert, in dem bis zu $n-h$ Beweiser adversarial (byzantinisch) sind und vom Protokoll abweichen können, um einen Liveness-Fehler zu verursachen (kein Beweis geliefert) oder eine Überzahlung herbeizuführen.
3. Ohne Vertrauen operiert, da Beweiser keinen Ruf haben und sich nicht glaubwürdig zu zukünftigen Handlungen verpflichten können.

Die Autoren modellieren dies als ein Mechanismus-Design-Problem, bei dem der Protokoll-Designer die Summe der geleisteten Zahlungen und die Strafe $C$, die fällig wird, wenn kein Beweis geliefert wird, minimieren möchte, unter der Annahme, dass ein Angreifer eine Teilmenge der Beweiser kontrolliert und handelt, um den Verlust des Protokolls zu maximieren.

Methodik

Die Autoren formalisieren das Problem unter Verwendung eines spieltheoretischen Rahmens:

• Aufbau: Es gibt $n$ Beweiser, von denen $h$ ehrlich sind. Die Kosten für die Generierung eines Beweises werden auf 1 normiert. Wenn kein Beweis produziert wird, erleidet das Protokoll eine Liveness-Strafe $C$.
• Angreifermodell: Der Angreifer kann bis zu $a = n-h$ Beweiser korrumpieren. Der Angreifer beobachtet den Mechanismus und wählt das Worst-Case-Verhalten (entweder Verweigerung der Beweislieferung, um die Strafe $C$ auszulösen, oder Lieferung von Beweisen, um Zahlungen zu manipulieren).
• Ziel: Minimierung des Worst-Case-Verlusts $\ell(p, s)$, definiert als die erwarteten Gesamtkosten (Zahlungen + Strafe) unter der Worst-Case-Angreiferstrategie, unter der Nebenbedingung, dass der Mechanismus anreizkompatibel ist (ehrliche Beweiser maximieren ihren Nutzen durch Befolgung des Protokolls).

Um das Problem handhabbar zu machen, leiten die Autoren Folgendes ab:

1. Eine untere Schranke $g(s)$ für den optimalen Protokollverlust, parametrisiert durch den Strategie-Vektor $s$ (die Wahrscheinlichkeit, mit der jeder Beweiser einen Beweis liefert). Diese Schranke geht von einem „geschwächten" Angreifer aus, der zwischen zwei extremen Strategien wählt: vollständig ehrliches Handeln oder vollständige Verweigerung der Lieferung.
2. Eine Analyse der Minimierer dieser unteren Schranke, die sie entweder als Designated Uniform Committee Equilibria (ein deterministischer Anführer + ein Komitee von Randomisierern) oder als Symmetric Committee Equilibria (ein Komitee von Randomisierern ohne designierten Anführer) charakterisiert.
3. Eine Untersuchung der Umsetzbarkeit: Feststellung, ob eine Zahlungsregel existiert, die diese Gleichgewichte induziert und gleichzeitig die Kosten der unteren Schranke erreicht.
4. Eine Erweiterung der Analyse um negative Zahlungen (Slashing/Staking), bei denen Beweiser Sicherheiten hinterlegen, die verwirkt werden können, wenn das Protokoll einen Angriff erkennt.

Wichtige Beiträge und Ergebnisse

1. Charakterisierung optimaler Gleichgewichte

Die Arbeit beweist, dass die Minimierer der unteren Schranke $g(s)$ ausschließlich von zwei Typen sind:

• Designierte Gleichgewichte: Ein Beweiser ist dafür designiert, mit Wahrscheinlichkeit 1 zu liefern, während ein Komitee der Größe $k$ mit Wahrscheinlichkeit $s \in (0, 1)$ liefert.
• Symmetrische Gleichgewichte: Ein Komitee der Größe $k$ liefert mit Wahrscheinlichkeit $s$, und kein einzelner Beweiser ist designiert.

2. Approximationsgarantien

• Additive 1-Approximation: Die Autoren beweisen, dass für jede Zahlungsregel und jedes Gleichgewicht ein designiertes Gleichgewicht existiert, dessen Verlust höchstens 1 Einheit (die Kosten eines einzelnen Beweises) über dem optimalen Verlust liegt (Satz 3.1).
• Umsetzbarkeit: Alle designierten Gleichgewichte sind mit einer einfachen Zahlungsregel umsetzbar (Lemma 3.4). Im Gegensatz dazu sind symmetrische Gleichgewichte nur unter spezifischen Bedingungen umsetzbar (z. B. wenn $C$ im Verhältnis zu $n$ und $h$ hinreichend groß ist) und erfordern oft komplexe Zahlungsstrukturen oder negative Zahlungen, um machbar zu sein.

3. Asymptotische Skalierung

• Logarithmische Skalierung: Der Worst-Case-Verlust des optimalen designierten Gleichgewichts skaliert als $O(\frac{\log C}{\tau})$, wobei $\tau = h/n$ der Anteil der ehrlichen Beweiser ist. Dies zeigt, dass selbst bei einem festen Anteil an Angreifern die Protokollkosten nur logarithmisch mit der Schwere der Liveness-Strafe wachsen.
• Auswirkung von Staking: Die Einführung eines gesamten Einsatzes $B$ (Sicherheiten) verbessert die Skalierung erheblich. Wenn $B$ proportional zu $C$ ist, skaliert der Verlust als $O(1/\tau)$ und wird effektiv konstant relativ zu $C$.

4. Übergangsdynamiken

Die Arbeit analysiert den Übergang zwischen designierter und symmetrischer Optimalität als Funktion von $C$ (Strafgröße) und $\tau$ (Ehrlichkeitsanteil).

• Für kleine $C$ oder hohe $\tau$ ist der designierte Mechanismus optimal.
• Für sehr große $C$ wird der symmetrische Mechanismus in der Analyse der unteren Schranke optimal.
• Aufgrund von Umsetzbarkeitsbeschränkungen bleibt der designierte Mechanismus jedoch oft die praktische Wahl, selbst in Regimen, in denen die symmetrische untere Schranke niedriger ist, da die symmetrische Lösung negative Zahlungen erfordern kann, die unpraktikabel oder komplex zu implementieren sind.

Bedeutung und praktische Empfehlungen

Die Arbeit argumentiert, dass die theoretischen Ergebnisse handlungsleitende Hinweise für Designer von Blockchain-Protokollen bieten, insbesondere für zk-EVM (Zero-Knowledge Ethereum Virtual Machine) und andere Märkte für verifizierbare Auslagerung.

• Empfehlung: Die Autoren empfehlen dringend die Annahme des optimalen designierten Uniform Committee Equilibrium. Dieses Design designiert einen einzelnen „Anführer" (oder primären Arbeiter), der den Beweis deterministisch produziert, unterstützt von einem Komitee von „Backups", die Beweise mit einer berechneten Wahrscheinlichkeit $s$ produzieren.
• Begründung:
  1. Einfachheit: Die Zahlungsregel ist intuitiv und ähnelt bestehenden Konsensmechanismen (z. B. anführerbasierte Konsensbildung mit attestierenden Komitees).
  2. Nahezu-Optimalität: Der Verlust liegt höchstens um die Kosten eines Beweises über dem theoretischen Optimum, was angesichts aktueller Beweis-Kosten (oft Bruchteile eines Dollars) vernachlässigbar ist.
  3. Robustheit: Er behandelt Worst-Case-adversariales Verhalten effektiv und skaliert logarithmisch mit der Strafe $C$.
  4. Machbarkeit: Im Gegensatz zu symmetrischen Mechanismen, die für Optimalität komplexe lotterieartige Zahlungen oder negative Zahlungen (Slashing) erfordern können, sind designierte Mechanismen immer mit positiven Zahlungen umsetzbar.

Die Arbeit schließt, dass symmetrische Mechanismen zwar theoretisch interessant und in spezifischen asymptotischen Regimen optimal sind, der designierte Mechanismus jedoch die beste Balance aus theoretischer Optimalität, Umsetzbarkeit und Vertrautheit für die Blockchain-Community bietet. Die Autoren stellen fest, dass ihr Modell allgemein auf jedes erlaubnisfreie Delegationsproblem anwendbar ist, das Liveness-Fehler beinhaltet, einschließlich verifizierbarer KI-Inferenz und TEE-basierter Berechnungen.