Technische Samenvatting: De Perils van Parallelisme: Transactiekostenmechanismen onder Executie-onzekerheid

1. Probleemstelling

Moderne blockchains gaan over van seriële naar parallelle executie om doorvoersnelheidsproblemen te overwinnen die worden veroorzaakt door de executie in plaats van de consensus. Hoewel parallelle executie (gebruikt of gepland door chains zoals Sui, Solana, Monad en Ethereum) de capaciteit vergroot, introduceert het twee kritieke economische uitdagingen wanneer transacties betrokken zijn bij executie-onzekerheid (contingentie) en resource-contentie:

1. Executie-contingentie en Risicoallocatie: In expressieve smart contract-talen (Turing-volledig) hangt het resourcegebruik (geaccessteerde objecten) van een transactie vaak af van de staat van de blockchain tijdens runtime, wat voorafgaand aan de executie niet bekend kan zijn. Dit creëert een spanning tussen Gebruikersrisico (gebruikers betalen te veel voor gedeclareerde objecten die niet worden gebruikt) en Scheduler-risico (schedulers verliezen inkomsten wanneer gereserveerde capaciteit niet wordt betaald vanwege onder-executie).
2. Shill-aanvallen op Gasberekening: Bestaande Gas Computation Mechanisms (GCMs) ontworpen voor parallelle settings (bijv. Shapley-waarde of Time-Proportional Makespan) zijn kwetsbaar voor rationele manipulatie. Zowel gebruikers als schedulers kunnen "shill" (nep) transacties injecteren om de berekende gas of kosten strategisch te wijzigen. Gebruikers kunnen hun kosten verlagen door nutteloze parallelle transacties toe te voegen, terwijl schedulers de kosten kunnen opdrijven door nep-contentie toe te voegen.

Het paper betoogt dat huidige ontwerpen er niet in slagen om gelijktijdig rekening te houden met parallelisme, executie-onzekerheid en economische robuustheid, wat leidt tot inefficiënties en exploiteerbare kwetsbaarheden.

2. Methodologie en Model

De auteurs formaliseren een framework voor het analyseren van Transactiekostenmechanismen (TFMs) onder parallelle executie met onzekerheid.

• Transactiemodel: Een transactie $tx$ wordt gedefinieerd door compute units $t$, een prioriteitsfee $g$, en gedeclareerde read/write sets $(R, W)$. Cruciaal is dat de werkelijke geaccessteerde objecten ($X_R, X_W$) een deelverzameling kunnen zijn van de gedeclareerde sets, afhankelijk van het executiepad (contingentie).
• Fee-definities: Het paper maakt onderscheid tussen:
  • Attainable Fee ($f_{att}$): De fee als alle gedeclareerde objecten worden gebruikt.
  • Baseline Fee ($f_{base}$): De fee voor alleen deterministische objecten.
  • User-Ideal Fee ($f_{ui}$): De fee voor exact de objecten die daadwerkelijk worden gebruikt.
  • Actual Paid Fee ($f_{act}$): De betaalde fee.
• Risicometrieken:
  • **Gebruikersrisico ($UR$):**$f_{act} - f_{ui}$ (overbetaling).
  • **Scheduler-risico ($SR$):**$f_{att} - f_{act}$ (niet-gerealiseerde inkomsten).
• Adversarieel Model: Gebruikers en schedulers worden gemodelleerd als rationele, economisch gemotiveerde agenten die shill-transacties kunnen invoegen om hun kosten te minimaliseren of respectievelijk hun inkomsten te maximaliseren.
• Complexiteitsanalyse: Het paper maakt gebruik van complexiteitstheorie (specifiek P-compleetheid) om de moeilijkheid te analyseren van het voorspellen van objectgebruik zonder executie.

3. Belangrijkste Bijdragen en Resultaten

A. Onmogelijkheid van Gelijktijdige Risico-eliminatie

Het paper bewijst een fundamenteel onmogelijkheidsresultaat: Geen enkel mechanisme kan gelijktijdig zowel Gebruikersrisico als Scheduler-risico elimineren zonder transacties vooraf uit te voeren of terug te vallen op constante fees.

• Theorem 1: Als een scheduler beperkt wordt door een compute-limiet $G$ (kan niet meer werk verrichten dan de block toelaat), is het onmogelijk om betalingen zo in te stellen dat $UR=0$ en $SR=0$ voor alle inputs die conflicterende contingente transacties bevatten.
• Theorem 2 (P-compleetheid): Het beslissen of een specifiek object wordt gebruikt door een contingente transactie (het Object Usage Decision Problem) is P-compleet. Dit impliceert dat het verifiëren van objectgebruik sequentiële arbeid vereist die proportioneel is aan de executietijd, wat het voor een scheduler computationeel onhaalbaar maakt om het gebruik "goedkoop" te voorspellen vóór de executie.
• Trade-off: Er is een inherente lineaire trade-off. Het verminderen van gebruikersrisico (alleen rekenen voor gebruikte objecten) verhoogt het scheduler-risico (omzetverlies), en vice versa.

B. Karakterisering van Risicoverdelingsmechanismen

Gezien de onmogelijkheid karakteriseren de auteurs de ontwerpplek via drie canonieke risicoverdelingsmechanismen, geparametriseerd door $\alpha \in [0,1]$:

1. Gebruikersvriendelijk ($\alpha=0$): Gebruikers betalen alleen voor de gerealiseerde executie ($f_{act} = f_{ui}$). De scheduler draagt alle risico.
2. Scheduler-vriendelijk ($\alpha=1$): Gebruikers betalen voor alle gedeclareerde objecten ($f_{act} = f_{att}$). De gebruiker draagt alle risico.
3. Even-Steven ($\alpha=0.5$): Het risico wordt gelijk verdeeld.
   Het paper analyseert deze onder verschillende scheduler utility-modellen (Optimistic, Pessimistic, Median) om de inkomstenimplicaties in kaart te brengen.

C. Shill-aanvallen en Fee-gebaseerde Shill-proofness

Het paper identificeert dat standaard GCM-eigenschappen (zoals Set Inclusion) onvoldoende zijn om shill-aanvallen te voorkomen in de aanwezigheid van contingentie.

• Gebruikers-shill-aanvallen: Gebruikers injecteren nep-transacties om de effectieve gas/fee van hun echte transactie te verlagen.
• Scheduler-shill-aanvallen: Schedulers injecteren nep-transacties om de aan de eerlijke gebruikers in rekening gebrachte gas/fee te verhogen.
• Fee-gebaseerde Shill-proofness: De auteurs stellen nieuwe definities voor shill-proofness voor op basis van fees in plaats van alleen gas, waarbij rekening wordt gehouden met prioriteitsfees en executie-contingentie. Ze bewijzen dat voor Gebruikersvriendelijke mechanismen, shill-proofness alleen haalbaar is als de fee onafhankelijk is van de schedule (Theorem 3).

D. De Object-Weighted TFM (OW-TFM)

Om deze problemen op te lossen, stellen de auteurs de Object-Weighted Transaction Fee Mechanism (OW-TFM) voor.

• Mechanisme: Fees worden berekend op basis van de prijs van de door de transactie gedeclareerde objecten, waarbij objectprijzen worden bijgewerkt op basis van historische benutting (vergelijkbaar met EIP-1559).
• Risico-parameterisatie: Het mechanisme gebruikt een parameter $\alpha$ om te bepalen hoeveel een gebruiker betaalt voor gedeclareerde-maar-niet-gebruikte objecten ($\alpha \cdot \text{prijs}$).
• Shill-resistentie: De OW-TFM is aangetoond shill-proof onder specifieke condities. Omdat prijzen worden afgeleid van de benutting van vorige blocks, kan een shill-transactie in het huidige block de prijs van een object voor het huidige block niet verlagen (het kan alleen toekomstige prijzen verhogen).
• Condities: Lemma 4 stelt een drempelwaarde vast voor $\alpha$ die vereist is om scheduler-shill-aanvallen te voorkomen, afhankelijk van de ratio tussen prioriteits- en base-fee ($\pi_o$), prijsresponsiviteit ($\eta$) en retentieratio ($\gamma$).

4. Betekenis en Claims

Het paper claimt de rigoureuze fundamenten te bieden voor het evalueren en ontwerpen van fee-mechanismen voor parallelle blockchains. De betekenis ligt in:

1. Identificeren van Fundamentele Limieten: Het demonstreert dat de spanning tussen gebruikerseerlijkheid en scheduler-inkomsten in parallelle executie geen ontwerpfout is, maar een fundamenteel gevolg van executie-onzekerheid en computationele complexiteit.
2. Blootleggen van Kwetsbaarheden: Het onthult dat bestaande voorstellen voor parallelle gasberekening (bijv. Shapley-gebaseerde benaderingen) kwetsbaar zijn voor rationele shill-aanvallen, een dreiging die voorheen onbehandeld bleef in de literatuur.
3. Bieden van een Design Framework: Het biedt een principieel ontwerpplek (het $\alpha$-spectrum) en een concreet mechanisme (OW-TFM) waarmee systeemontwerpers expliciet een risicoallocatiestrategie kunnen kiezen terwijl ze resistent blijven tegen manipulatie.
4. Relevantie voor de Industrie: De resultaten zijn direct toepasbaar op en bekritiseren de ontwerpen van prominente parallelle chains (Sui, Monad, Solana) en de roadmap van Ethereum voor parallelle executie via access lists.

De auteurs hanteren een bescheiden toon, waarbij zij opmerken dat hun werk fundamentele beperkingen en trade-offs identificeert in plaats van één enkele "perfecte" oplossing voor te schrijven, waarbij zij erkennen dat praktische implementatie verdere overweging vereist van probabilistische executiemodellen en specifieke implementatiedetails.