An impossibility theorem on truth-telling in fully decentralised systems

BISWorkingPapers No1117 Animpossibilitytheoremontruth-tellinginfullydecentralizedsystems byRodneyGarrattandCyrilMonnet MonetaryandEconomicDepartment August2023 JELclassification:C72,D72,D86,O33. Keywords:decentralizedsystems,smartcontracts,truth-telling,oracleproblem. BISWorkingPapersarewrittenbymembersoftheMonetaryandEconomicDepartmentoftheBankforInternationalSettlements,andfromtimetotimebyothereconomists,andarepublishedbytheBank.Thepapersareonsubjectsoftopicalinterestandaretechnicalincharacter.TheviewsexpressedinthemarethoseoftheirauthorsandnotnecessarilytheviewsoftheBIS. ThispublicationisavailableontheBISwebsite(www.bis.org). ©BankforInternationalSettlements2023.Allrightsreserved.Briefexcerptsmaybereproducedortranslatedprovidedthesourceisstated. ISSN1020-0959(print) ISSN1682-7678(online) AnImpossibilityTheoremonTruth-TellinginFullyDecentralizedSystems∗ RodneyGarratt†CyrilMonnet‡August2023 Abstract Weshowthattruthfulreportingabouttherealizationofapubliclyob-servedeventcannotbeimplementedasauniqueequilibriuminacompletelydecentralizedenvironment.Ourworkprovidesatheoreticalunderpinningoftheneedfororaclesandtherelated“oracleproblem.” Keywords:decentralizedsystems,smartcontracts,truth-telling,oracleproblem JELClassificationNumbers:C72,D72,D86,O33 Thetruth?What’sthat?Don’tyouknowthatthedayhascomewhenthetruthiswhatwecaretomakeit? –IainCrichtonSmith,ConsidertheLilies ∗TheviewsexpressedarethoseoftheauthorsanddonotnecessarilyreflectthoseoftheBIS.WearegratefultoBrunoBiais,GabrieleCamera,JonathanChiu,JohannesHoerner,ThorKoeppl,Jean-CharlesRochet,HyunSongShin,JensWitkowskiandconferenceandseminarparticipantsatthe2022TheoryandExperimentsinMonetaryEconomicsconferenceatGeorgeMasonUni-versity,Tokenomics2022,the2023ASSAWinterMeetings,theFrankfurtSchoolofFinanceandManagement,theUniversityofBonn,andtheToulouseSchoolofEconomicsforhelpfulcomments. †BankforInternationalSettlements.Email:rodney.garratt@bis.org. ‡UniversityofBernandStudyCenterGerzensee.Email:cyril.monnet@unibe.ch 1Introduction Smartcontractsareself-executingprogrammablecontractsbetweentwoormoreparties.Smartcontractsdonotrequireavettingauthoritybecausetheirlegitimacyreliesondecentralizedledgertechnologies.Howevertheimplementationofmanypotentiallyusefulsmartcontractapplicationsdependsuponverifyingthatsomereal-worldeventhastakenplace(thinkinsurancecontracts).Thisisaproblem.Giventheirfullydecentralizednature,howdoesasmartcontractselectwhatthetruestateoftheworldis?Moregenerally,howdofullydecentralizedsystemsfunctionwhentheiroperationdependsontheexistenceofasingle,mutuallyaccepted,recordofthetruth,butthereisnosingleauthoritythatcanprovidethisrecord? Thispaperconsidersasituationwheremultipleindividualsseektoenterintoagreementsbasedontheoutcomeofareal-worldevent,butthereisnotrustedparty(i.e.,contractiblesource)thatcanbeusedtodeterminepayoffs.Inthiscase,payoffsmustbebasedonsomeformofcollectiveagreementonthetruestateoftheworld.Byappealingtothreebasicproperties,anonymity,neutrality,andmonotonicity,wecanrestrictattentiontomajorityvoting.Inthisenvironment,agentsreportthetruththatismostbeneficialforthem.Incentivestorewardconsensusdonotnecessarilymakethingsbetter.Rather,theyleadtoasituationthatisakintoabeautycontesta`laKeynes(1936),inwhichagentsreportwhattheythinkthemajorityofotheragentswillreport.Withorwithoutreportingincentives,thereportofthetruestatethatresultsfrommajorityvotingdoesnotdependuponthetruestate. Ourmainanalysisfocusesonsimultaneousvoting.However,wealsobrieflyexplorethepossibilityofsequentialplay,byallowingindividualstovoteinarandomorderandallowingeachindividualtoseethepreviousvotes.Inathree-agentmodelwithsequentialvotingindividualsunanimouslyagreeonwhatthestateoftheworldis,butthismaynotbethetruestate.Theresultsuggeststhatsequentialvotingisnotasolutiontothetruth-tellingproblem. Ourgeneralresult,whichappliestosimultaneousvotinggames,isthattheonlywaythatindividualsarewillingtovoteaccordingtothetruestateisiftheyarecom-pletelyindifferentastowhatthetruestateshouldbe.Thatis,theirpayoffscannotdependontheiractionsortheirindividualreports.Thisgeneralresultsuggeststhatabsentadditionalmotivation(e.g.,deontologicalpreferencestowardtruth-telling,seeBergstrometal.(2019))thatlinksindividualpayoffstothetruth,thereisnowaytoimplementcontractsthatpayoutbasedonanobservedstatewithoutatrustedsource. Ouranalysishasaspectsincommonwithpeerpredictiongames(PPG);see,forexampleGaoetal.(2016)andKongandSchoenbeck(2019)andthereferences therein.Inthesesettings,thereistypicallyoneobjectthathasanunknowncharac-teristicandseveralagentscanexertefforttoobtainasignalaboutthischaracteristic.Thesesignalscanbecorrelated(i.e,comefromthesamedistribution),butthereistypicallynoknown“groundtruth.”Theliteraturestudiespeerpredictionmecha-nismsthatareusedtomakesureagentsexerteffortandthattheycommunicatetheirsignalstruthfully. AnaspectthatmakesbothourgameandPPGsimilaristhatinbothcasesagentshavetosendsignalsaboutwhattheyobserve.Alsoneitherthepeerpredictionmechanismnorourscanrelyonthegroundtruth(evenifitexists)tod