
 
 
 
 
 Författare : (1) Hao Chung∗, Carnegie Mellon University (haochung@andrew.cmu.edu) (2) Tim Roughgarden†, Columbia University och a16z (crypto tim.roughgarden@gmail.com); (3) Elaine Shi∗, Carnegie Mellon University (runting@cs.cmu.edu) Authors: (1) Hao Chung∗, Carnegie Mellon University (haochung@andrew.cmu.edu) (2) Tim Roughgarden†, Columbia University och a16z (crypto tim.roughgarden@gmail.com); (3) Elaine Shi∗, Carnegie Mellon University (runting@cs.cmu.edu) Tabell från vänster Abstrakt och 1. introduktion 1.1 Våra bidrag 1.2 TFM Incentive-Compatibility Begrepp: Ett Cheat Sheet 
 
 
 
 
 
 
 
 
 
 
 
 Definitions 2.1 Transaction Fee Mechanism 2.2 Incentive Compatibility Notions 
 
 Preliminary: Myerson’s Lemma 
 
 Warmup: Impossibility of UIC + MIC + Global SCP for Deterministic Mechanisms 
 
 
 Impossibility of UIC + MIC + Global SCP for Randomized Mechanisms and 5.1 Proof Roadmap 5.2 Formal Proofs 
 
 
 
 Feasibility and Impossibility of UIC + MIC + OCA-Proof 6.1 A Non-Truthful Mechanism with UIC + MIC + OCA-Proof 6.2 Impossibility of UIC + MIC + OCA-Proof for Truthful Mechanisms 
 
 
 
 How to Circumvent the Impossibilities and 7.1 Allowing the Globally Optimal Strategy to Coordinate 7.2 Allowing the Globally Optimal Strategy to Output Multiple Bids 7.3 Inclusion-Rule-Respecting and 7.4 Discussions and Open Questions Regarding the Use of Cryptography 
 
 
 
 Static Revelation Principle for Transaction Fee Mechanisms 8.1 Static Revelation Principle: Bidding Rules That Output Single Bid 8.2 Static Revelation Principle: Allowing Bidding Rules that Output Multiple Bids A. Jämförelse av Collusion-Resilience-begrepp Referenser Abstrakt Användare bjuder på en transaktionsavgiftsmekanism (TFM) för att få sina transaktioner inkluderade och bekräftade av ett blockchain-protokoll. Roughgarden (EC’21) inledde den formella behandlingen av TFMs och föreslog tre krav: användarincitamentskompatibilitet (UIC), miner incitamentskompatibilitet (MIC), och en form av kollusion-resiliency som kallas OCA-resiliency. Ethereums EIP1559-mekanism uppfyller alla tre egenskaper samtidigt när det inte finns någon tvist mellan transaktioner, men förlorar UIC-egenskapen när det finns för många berättigade transaktioner för att passa in i ett enda block. Chung och Shi (SODA’23) ansåg ett alternativt begrepp av kollusion-resilien Vårt huvudresultat är det första beviset på att, när det finns tvist mellan transaktioner, ingen (möjligen slumpmässig) TFM där användare förväntas satsa sannolikt uppfyller UIC, MIC och OCA-proofness.Detta resultat löser den viktigaste öppna frågan i Roughgarden (EC'21). 1 Introduktion Fastigheten på blockchain är knappt, och blockchain-användare bjuder på en auktion som kallas transaktionsavgiftsmekanismen (TFM) för att få sina transaktioner inkluderade och bekräftade på blockchain. Den ursprungliga Bitcoin-protokollet antog en enkel första pris auktion, där de bästa k bud vinner och de varje betalar sitt bud. Men sådana första pris auktioner är kända för att uppmuntra osanna bud. Därför en rad efterföljande verk [LSZ19, Yao, BEOS19, BCD+, Rou20, Rou21, FMPS21, CS23, SCW23, WSC24, GY23, ZCZ22, BGR23, TY23, KKLP23, XFP23, CMW23, LRMP23, Ndi23] utforskade vad som är "dröm TFM" för block Roughgarden [Rou21] var den förste att formellt definiera ovan nämnda krav för en TFM, som han hänvisade till som [1] och (myopisk) och , där OCA står för "off-chain-avtal" och hänvisar till sammanslagna strategier mellan gruvarbetaren och en uppsättning användare som tillåter off-chain-överföringar. Roughgarden [Rou21] visade också att den enkla "postade pris auktion med alla avgifter brända" mekanismen, som motsvarar beteendet hos Ethereums EIP-1559 TFM [BCD+] när det inte finns någon trängsel, tillfredsställer alla tre egenskaper. Men den publicerade pris auktionen med alla avgifter brända tillfredsställer inte alla tre egenskaper när det finns trängsel. I praktiken uppstår trängsel när det finns stora händelser som en NFT mynta eller prisfluktuationer - till exempel i Ethereum, ungefär 2,3% av block upplever trängsel Användarincitament kompatibilitet Minerala incitament kompatibilitet OCA-proofförmåga Chung och Shi [CS23] övervägde en alternativ uppfattning om collusion-resilience, kallad sidecontract-proofness. Tyvärr visade de att ingen (även randomiserad) TFM kan tillfredsställa användarincitamentskompatibilitet och sidecontract-proofness samtidigt. Eftersom sidecontract-proofness är en mer krävande egenskap än OCA-proofness, hade frågan som ställdes av Roughgarden [Rou21], om det finns en dröm TFM som uppfyller alla tre egenskaper under hans kollusion-resilience-uppfattning, varit öppen. Flera naturliga begrepp av kollusion-motståndskraft kan och har studerats i samband med TFM-design.Här klargör vi informellt de viktigaste skillnaderna mellan de begrepp som föreslagits av Roughgarden [Rou21] och Chung och Shi [CS23]. Dessa begrepp definieras formellt i definitionerna 4–6 (se avsnitt 2) och jämförs vidare via exempel i bilaga A. Two notions of miner-user collusion-resilience. Roughgarden:s tillräckliga uppfattning, hädanefter kallad OCA-proofness, hävdar att det bör finnas en "referensstrategi" för en gruvarbetare och alla användare som är garanterad att maximera deras gemensamma överskott. I denna referensstrategi förväntas gruvarbetaren följa den inkluderingsregel som avses av TFM. För användare kräver definitionen endast att användarna följer några fasta bud trategy σ (dvs. en kartläggning från en privat användarvärdering till en användarbud) som är individuellt rationell (dvs. σ(v) ≤ v för alla v ≥ 0). I synnerhet i referensstrategin förväntas användarna att budge självständigt (med en användares bud oberoende av andra användares värderingar och bud), och • OCA-proofness: Chung och Shi-konceptet [CS23], därefter kallat c-SCP (där SCP står för sidekontrakt-proofness), kräver att den ärliga strategin (dvs. att alla användare följer den ärliga budgivningsregeln och gruvarbetaren ärligt implementerar inkluderingsregeln) är den vinstmaximiserande strategin för varje koalition bestående av gruvarbetaren i det nuvarande blocket och mest c-användare. För sanna mekanismer är den ärliga budgivningsregeln den sanna, medan för icke-sanna mekanismer kan budgivningsregeln vara mer allmän (se avsnitt 2.1 för den formella definitionen). Chung och Shi-begreppet anpassar sig till standardbegrepp som används i en linje av arbete vid korsningen mellan spelteori och kryptografi [ •  -SCP: c c De två begreppen collusion-resilience tar upp olika problem. OCA-proofness fångar det intuitiva kravet att användare och gruvarbetare genom strategiska avvikelser - därför anser han c-SCP-konceptet fångar däremot den intuitiva idén att en gruv-användarkoalition bäst svarar på att agera ärligt, och att inga strategiska avvikelser kan tillåta koalitionen att För ytterligare diskussioner, se slutet av detta avsnitt och bilaga A. Discussion Kan inte stjäla från protokollet Endast den globala koalitionen stjäla från andra användare eller stjäla från protokollet 
 
 Den här artikeln finns tillgänglig på arkiv under CC BY 4.0 DEED-licens. Detta papper är Licensierad enligt CC BY 4.0 DEED. Tillgänglig i Arkiv Tillgänglig i Arkiv ∗ Stöds av NSF-priser 2212746, 2044679, 1704788, ett Packard-stipendium, en generös gåva från den avlidne Nikolai Mushegian, en gåva från Google och ett ACE-centerbidrag från Algorand Foundation. †Författarens forskning vid Columbia University stöds delvis av NSF-priserna CCF-2006737 och CNS-2212745, och forskningspriser från Briger Family Digital Finance Lab och Center for Digital Finance and Technologies. [1] User incentive compatibility (UIC) kallas vanligtvis dominant-strategi incentive compatible (DSIC) i mekanismdesignlitteraturen. [2] Från 1 januari 2024 till 5 februari 2024 har 256595 block producerats på Ethereum, och 5840 block bland dem var fulla (vilket innebär att mer än 99,9% av gasgränsen (30M) användes).

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

EScholar Technologies

EScholar

Det här ljudet är producerat på berättelsens originalspråk!

För länge; Att läsa

CTA: Download the FREE AI Productivity Shift report

Varför den perfekta Blockchain-avgiftsmekanismen kan vara omöjlig

About Author

KOMMENTARER

HÄNG TAGGAR

DENNA ARTIKEL PRESENTERAS I

Related Stories

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps