Technische Samenvatting: Adversariale Aanschaf in Blockchains

Probleemstelling

Het artikel behandelt de uitdaging van adversariale aanschaf in blockchainprotocollen, specifiek in de context van opkomende ontwerpen die gebruikmaken van de computationele asymmetrie tussen het uitvoeren en verifiëren van taken (bijvoorbeeld Zero-Knowledge-bewijzen, of SNARKs). In deze systemen moet een protocol dure computationele taken (zoals het genereren van een geldigheidsbewijs voor een blok) uitbesteden aan een set van $n$ pseudonieme, niet-vertrouwde bewijzers.

Het kernprobleem is het ontwerpen van een mechanisme dat:

1. Prikkels creëert zodat ten minste één bewijzer de taak uitvoert (zorgen voor levendigheid).
2. Economisch verlies minimaliseert in het worst-case scenario waarin maximaal $n-h$ bewijzers adversariaal (Byzantijns) zijn en kunnen afwijken van het protocol om een levendigheidsfout te veroorzaken (geen bewijs afgeleverd) of een overbetaling te induceren.
3. Zonder vertrouwen opereert, aangezien bewijzers geen reputatie hebben en niet geloofwaardig kunnen toezeggen tot toekomstige acties.

De auteurs modelleren dit als een mechanismeontwerpprobleem waarbij de protocolontwerper streeft naar het minimaliseren van de som van de betaalde bedragen en de boete $C$ die wordt opgelegd als er geen bewijs wordt afgeleverd, ervan uitgaande dat een adversary een subset van bewijzers controleert en handelt om het verlies van het protocol te maximaliseren.

Methodologie

De auteurs formaliseren het probleem met behulp van een speltheoretisch raamwerk:

• Opzet: Er zijn $n$ bewijzers, waarvan $h$ eerlijk zijn. De kosten van het genereren van een bewijs zijn genormaliseerd tot 1. Als er geen bewijs wordt geproduceerd, loopt het protocol een levendigheidboete $C$ op.
• Adversary-model: De adversary kan maximaal $a = n-h$ bewijzers corrumperen. De adversary observeert het mechanisme en kiest het worst-case gedrag (hetzij weigeren bewijzen af te leveren om de boete $C$ te activeren, hetzij bewijzen afleveren om betalingen te manipuleren).
• Doel: Minimaliseer het worst-case verlies $\ell(p, s)$, gedefinieerd als de verwachte totale kosten (betalingen + boete) onder de worst-case adversariële strategie, onderworpen aan de beperking dat het mechanisme prikkelcompatibel is (eerlijke bewijzers maximaliseren hun nut door het protocol te volgen).

Om het probleem hanteerbaar te maken, doen de auteurs het volgende:

1. Ze leiden een ondergrensfunctie $g(s)$ af voor het optimale protocolverlies, geparametriseerd door de strategievector $s$ (de waarschijnlijkheid dat elke bewijzer een bewijs aflevert). Deze ondergrens gaat uit van een "verzwakte" adversary die kiest tussen twee extreme strategieën: volledig eerlijk handelen of volledig weigeren af te leveren.
2. Ze analyseren de minimalizers van deze ondergrens, en karakteriseren deze als Aangewezen Uniform Comité-evenwichten (één deterministische leider + een comité van randomizers) of Symmetrische Comité-evenwichten (een comité van randomizers zonder aangewezen leider).
3. Ze onderzoeken implementeerbaarheid: het bepalen of er een betalingsregel bestaat die deze evenwichten induceert terwijl de ondergrenskosten worden bereikt.
4. Ze breiden de analyse uit om negatieve betalingen (slashing/staking) op te nemen, waarbij bewijzers onderpand plaatsen dat kan worden verbeurd verklaard als het protocol een aanval detecteert.

Belangrijkste Bijdragen en Resultaten

1. Karakterisering van Optimale Evenwichten

Het artikel bewijst dat de minimalizers van de ondergrens $g(s)$ uitsluitend van twee types zijn:

• Aangewezen Evenwichten: Één bewijzer is aangewezen om met waarschijnlijkheid 1 af te leveren, terwijl een comité van grootte $k$ aflevert met waarschijnlijkheid $s \in (0, 1)$.
• Symmetrische Evenwichten: Een comité van grootte $k$ levert af met waarschijnlijkheid $s$, en er is geen enkele bewijzer aangewezen.

2. Benaderingsgaranties

• Additieve 1-benadering: De auteurs bewijzen dat voor elke betalingsregel en elk evenwicht er een aangewezen evenwicht bestaat waarvan het verlies maximaal 1 eenheid (de kosten van één bewijs) hoger is dan het optimale verlies (Stelling 3.1).
• Implementeerbaarheid: Alle aangewezen evenwichten zijn implementeerbaar met een eenvoudige betalingsregel (Lemma 3.4). Daarentegen zijn symmetrische evenwichten alleen implementeerbaar onder specifieke voorwaarden (bijvoorbeeld wanneer $C$ voldoende groot is ten opzichte van $n$ en $h$), en vereisen ze vaak complexe betalingsstructuren of negatieve betalingen om haalbaar te zijn.

3. Asymptotische Schaling

• Logaritmische Schaling: Het worst-case verlies van het optimale aangewezen evenwicht schaalt als $O(\frac{\log C}{\tau})$, waarbij $\tau = h/n$ het aandeel eerlijke bewijzers is. Dit geeft aan dat zelfs met een vast aandeel adversaries, de protocolkosten slechts logaritmisch groeien met de ernst van de levendigheidboete.
• Invloed van Staking: Het introduceren van een totale stake $B$ (onderpand) verbetert de schaling aanzienlijk. Als $B$ evenredig is met $C$, schaalt het verlies als $O(1/\tau)$, wat effectief constant wordt ten opzichte van $C$.

4. Transitiedynamiek

Het artikel analyseert de overgang tussen aangewezen en symmetrische optimaliteit als functie van $C$ (boetegrootte) en $\tau$ (eerlijkheidsfractie).

• Voor kleine $C$ of hoge $\tau$ is het aangewezen mechanisme optimaal.
• Voor zeer grote $C$ wordt het symmetrische mechanisme optimaal in de ondergrensanalyse.
• Echter, vanwege implementeerbaarheidsbeperkingen, blijft het aangewezen mechanisme vaak de praktische keuze, zelfs in regimes waar de symmetrische ondergrens lager is, omdat de symmetrische oplossing negatieve betalingen kan vereisen die onhaalbaar of complex te implementeren zijn.

Betekenis en Praktische Aanbevelingen

Het artikel betoogt dat de theoretische resultaten bruikbare richtlijnen bieden voor blockchainprotocolontwerpers, met name voor zk-EVM (Zero-Knowledge Ethereum Virtual Machine) en andere markten voor verifieerbare uitbesteding.

• Aanbeveling: De auteurs raden ten sterkste aan het optimale aangewezen uniforme comité-evenwicht te adopteren. Dit ontwerp wijst één "leider" (of primaire werknemer) aan om het bewijs deterministisch te produceren, ondersteund door een comité van "back-ups" dat bewijzen produceert met een berekende waarschijnlijkheid $s$.
• Onderbouwing:
  1. Eenvoud: De betalingsregel is intuïtief en lijkt op bestaande consensusmechanismen (bijvoorbeeld leidersgebaseerde consensus met attestatiecomités).
  2. Bijna-Optimaliteit: Het verlies ligt maximaal één bewijskosten verwijderd van het theoretische optimum, wat verwaarloosbaar is gezien de huidige bewijskosten (vaak fracties van een dollar).
  3. Robuustheid: Het behandelt het worst-case adversariële gedrag effectief, met een logaritmische schaling ten opzichte van de boete $C$.
  4. Haalbaarheid: In tegenstelling tot symmetrische mechanismen, die complexe loterij-stijl betalingen of negatieve betalingen (slashing) kunnen vereisen om optimaal te zijn, zijn aangewezen mechanismen altijd implementeerbaar met positieve betalingen.

Het artikel concludeert dat hoewel symmetrische mechanismen theoretisch interessant zijn en optimaal in specifieke asymptotische regimes, het aangewezen mechanisme de beste balans biedt tussen theoretische optimaliteit, implementeerbaarheid en bekendheid bij de blockchaingemeenschap. De auteurs merken op dat hun model breed van toepassing is op elk toestemmingsvrij delegatieprobleem dat levendigheidsfouten omvat, waaronder verifieerbare AI-inferentie en TEE-gebaseerde berekeningen.