sequential17roco.com

MixcoinAnonymityforBitcoinwithaccountablemixes(Fullversion)JosephBonneau1,ArvindNarayanan1,AndrewMiller2,JeremyClark3,andJoshuaA.
Kroll1andEdwardW.
Felten11PrincetonUniversity2UniversityofMaryland3ConcordiaUniversityAbstract.
WeproposeMixcoin,aprotocoltofacilitateanonymouspay-mentsinBitcoinandsimilarcryptocurrencies.
Webuildontheemergentphenomenonofcurrencymixes,addinganaccountabilitymechanismtoexposetheft.
Wedemonstratethatincentivesofmixesandclientscanbealignedtoensurethatrationalmixeswillnotsteal.
OurschemeisecientandfullycompatiblewithBitcoin.
Againstapassiveattacker,ourschemeprovidesananonymitysetofallotherusersmixingcoinscontemporaneously.
Thisisaninterestingnewpropertywithnoclearanaloginbetter-studiedcommunicationmixes.
Againstactiveattackersourschemeoerssimilaranonymitytotraditionalcommunicationmixes.
1IntroductionProtectingtheprivacyofnancialtransactionshaslongbeenagoalofthecryp-tographycommunity,datingatleasttoChaum'sworkonanonymousdigitalcashusingblindsignatures[6].
Despiteinitialexcitement,anonymousdigitalpaymentshavenotseenmassadoption.
Onereasonisthattraditionalelectroniccashrequiresacentral,trustedentity,typicallycalledabank.
Bycontrast,BitcoinisarelativelyyoungdecentralizedcurrencythathasrocketedtopopularitywithamonetarybaseworthoverUS$6billioninearly2014.
Bitcoincanbethoughtofasapublic,distributedledgerthatlogsalltransactionsinordertopreventdoublespending[24].
Usingaproof-of-worksystem,theintegrityoftheledgerismaintainedaslongasamajorityofthecomputingpoweriscontributedbyhonestparticipants[18].
Bitcoindoesnotprovidetrueanonymity:transactionsinvolvepseudonymousaddresses,meaningauser'stransactionscanoftenbeeasilylinkedtogether.
Further,ifanyoneofthosetransactionsislinkedtotheuser'sidentity,allofhertransactionsmaybeexposed.
AsmallbutgrowingbodyofacademicliteraturehasfoundthatBitcoinoersonlyweakanonymityinpractice(seeSection2.
2).
Thishasledtotheriseofmixingservices(ortumblers4)whichpromisetotake4Bitcointumblersarenamedaftermachinesusedtowashphysicalcoins.
2auser'scoinsandrandomlyexchangethemforotherusers'coinstoobfuscatetheirownership,thoughthesecomewithnoprotectionfromtheftbytheservice.
TheBitcoincommunityiswellawareofthisissue,leadingtomuchinterestintheprovisionofstrongeranonymity.
WeprovidemoredetailinSection8,butexistingproposalscanbethoughtofintwomaingroups.
Firstareproposalswhichprovidestronganonymitybutrequireadvancedcryptographyandsub-stantialmodicationstoBitcoin,likeZerocoin[22],orevenacompletelynewcurrencyaswithZerocash[4].
Second,thereareproposalssuchasCoinJoin[19]orCoinSwap[20]whicharebackwards-compatiblewithBitcoinbuthavepracti-calcomplicationsandmayprovidesmalleranonymitysets.
Ourgoalistoenablestronganonymityinasimpleschemethatcanbedeployedimmediately.
Ourstrategyistobuildontheexistingphenomenonofmixes,buttoaddaninde-pendentcryptographicaccountabilitylayer.
Ourmaincontributionsinclude:Accountability.
Mixcoinmixesissuesignedwarranties(Section4)touserswhichroughlystate:"ifAlicesendsmevcoinsbytimet1,Iwillsendvcoinsbacktoherbytimet2.
"Ausercanthencondentlysendfundstothemix,knowingthatifthemixmisbehavesshecanpublishthiswarranty,damagingthemix'sreputationand(presumably)itsbusinessmodel.
Randomizedmixingfees.
Weshowhowpayingmixesfortheirservicesincen-tivizeshonestbehavior(Section6),yetxedfeesundermineanonymitywhencoinsaremixedmultipletimes.
Insteadweapplyrandomized,all-or-nothingfeesinwhichmixesretaintheentirevaluefromasmallpercentageoftransactions.
WeshowhowtogeneratetherequisiterandomnessinafairandaccountablemannerusingtheunpredictabilityoftheBitcoinblockchainitself.
Mixindistinguishability.
Althoughusersinteractwithspecicmixes,single-usemixaddressesenableasurprisingpropertythatpassiveadversariescan'tdeter-minewhichmixauserisinteractingwith.
Theanonymitysetinthiscaseisthenthesetofallusersinteractingwithanymixatthesametime.
MixnetworksforBitcoin.
Againstanactiveattackerwhocanbreakmixin-distinguishability,wedrawontheexperiencefromanonymouscommunicationnetworkstodemonstratehowchainingmultiplemixestogethercanstillprovidestronganonymity.
Thereareimportantdierencesfromcommunicationmixes,however,whichwediscussinSection7).
Ourcoreprotocolisaverygeneraldesign,allowingclientsandmixestospecifyavarietyoffreeparameters.
Weexpectthat,becauseanonymitylovescompany[12],theseparameterswillconvergetoglobalvalues(Section7.
6).
Inparticular,weexpectmixingtocompleteinafewhourswithmixingfeesoflessthan1%(Section6).
GiventhismodestoverheadandthefactthatMixcoincanbedeployedimmediatelywithnochangestoBitcoinitself,itisourhopethatallBitcoinuserswillhavetheopportunitytomixtheircoins,makingstrongnancialprivacypracticalinadecentralizeddigitalcurrency.
32BackgroundInthissectionweprovideabasicmodelofBitcoin.
WefocusonthepropertiesrequiredforMixcoin,whichcouldbeimplementedontopofanydistributedcurrencysystemsimilartoBitcoininthesebasicrespects.
Wethenmodeltoday'snascentBitcoinmixesandtheattackstheyarevulnerableto.
2.
1BitcoinBitcoincanbethoughtofasadecentralizedsystemwhichtracksamappingbetweenaddressesandmonetaryvaluedenominatedincoins.
5Anaddress,whichwedenoteκ,issimplyapublickey.
Addressesarepseudonymous:anybodycancreateanarbitrarynumberofaddressesforfreewithnoverication.
Controlofanaddress'sprivatekeyprovides"ownership"ofallcoinsmappedtothataddress.
Thesimplest6Bitcointransactionisessentiallyastatementthatanaddressκinwouldliketotransfersomevaluevtoanaddressκout,signedbyκin.
Adistributedconsensusprotocolmaintainsaglobalhistoryofalltransactionstopreventdoublespending.
Transactionsaregroupedintoblocksforeciency,whicharechainedinalinearstructurecalledtheblockchain.
Thechainrep-resents(probabilistic)consensus;atpresentmostBitcoinuserswillconsideratransactionconrmedifitappearsinablockwithatleastw=6blocksfollowingit.
Newblocksaregeneratedroughlyonceeverytenminutes.
2.
2DeanonymizationinBitcoinCreatingnewaddressesistrivial,butthisdoesnotmakeBitcoinanonymousasalltransfersareglobally(andpermanently)visibleintheblockchain.
Severalrecentpapershavestudiedwaystolinkauser'saddressestoeachotherandtoanexternalidentity[21,27,29,2].
Fourmajortechniqueshavebeenexplored.
First,inmulti-inputtransactions,sharedspendingauthorityisevidenceofjointcontrol.
Therationaleisthatdierententitiesareunlikelytobeco-spendersofthesametransaction.
Secondistheuseoftaintanalysistotrackows.
Thetaintbetweenaddressesκinandκoutisdenedasthepercentageofthebalanceofκoutthatcamefromκin.
Taintanalysiscanovercomesimplemanualobfuscationtechniques.
Moregenerally,onecananalyzeBitcoin'soveralltransactiongraph,witheachaddressasanodeandeachtransactionasaweighted,directededgebetweennodes.
Variousheuristicscanbeusedforclusteringaddressesandtrackingows,suchasdetectingthe"changeaddress"inamulti-outputtransaction(therationalebeingthatthechangeaddressisprobablycontrolledbythesameentityastheinputaddress).
Third,therearevarioussidechannelattackssuchastiming,precisevalues,and5Thisisasimplicationforconceptualclarity.
Onatechnicallevel,monetaryvalueisassignedtotransactionsandnottoaddresses.
6Bitcointransactionsmayfeaturemultipleinputsandoutputs.
Bitcoinalsofeaturesalimitedscriptinglanguageallowingmorecomplicatedtransactions.
4network-layerinformation.
Finally,anattackercanuseauxiliaryinformation(e.
g.
,informationinforumsorgleanedfrommerchants)toconnectpseudonymstoidentities.
Therstthreetechniqueshaveprovedquitepowerful.
Thefourthtechnique(useofauxiliaryinformation)isnecessarytolinkaBitcoinusertoareal-worldidentity.
However,itismoredicultforresearcherstocarryoutusingpublicinformationthanforawell-fundedadversarywhomaycompeldisclosuresfromvariousmerchantsorserviceproviders,sotheacademicliteraturehasgenerallystoppedshortofthisstep.
Nonetheless,theevidencesuggeststhattheanonymitypropertiesofBitcoincannotberelieduponinthefaceofadeterminedadversary.
2.
3CurrentBitcoinmixesTopreservetheirprivacy,someBitcoinusersexchangetheircoinsusingmixes,directlyanalogoustotheconceptincommunicationnetworks.
Inthecommonimplementationamixingaddressreceivescoinsfrommultipleclientsandfor-wardsthemrandomlytoafreshaddressforeachclient.
Severalsuchserviceshavearisen,typicallychargingcommissionsinthe1–3%rangeandrequiringmanualinteractionthroughawebsite7toarrangetransactions.
Asmall-scalestudyofthreemixingservicesfoundthatinonecase,taintanalysiswasimme-diatelysucienttolinktheinputandoutput[23].
Intheothertwocases,taintanalysisdidnotsucceedbutthetransactiongraphshowedrichstructure,leav-ingopenthequestionofmoresophisticatedlinkingattacks.
Anecdotalevidencefromuserforumsincludecomplaintsslowmixingtimesofupto48hoursandlowtransactionvolumesleadingtousersfrequentlyreceivingtheirowncoinsinreturn.
8Reportsoftheftbymixesarealsoasignicantconcern,withthepopu-larBitcoinWikiwarning:.
.
.
ifthemixingoutputfailstobedeliveredoraccesstofundsisdeniedthereisnorecourse.
Useatyourowndiscretion.
Incontrasttodedicatedmixingservices,someserviceswithahighpreexistingtrustrequirementhavedeployedimplicitmixingsuccessfully.
Forexample,theSilkRoadmarketplacemediatedandmixedalltransactionsbetweenbuyersandsellers[7],whilesome"eWallet"servicespromisethatwhenuserswithdrawfundstheywillreceiverandomcoinsfromtheprovider'sreserves.
2.
4MixnetworksforanonymouscommunicationMixnetworkswereintroducedbyChaumin1981foranonymouscommunica-tion[5].
Signicantresearchhasanalyzedtherelationshipbetweendesignparam-eters,suchasrouteselectionandushingpolicies,andtheresultinganonymity(see[26]forasurvey),muchofwhichisbroadlyapplicabletonancialmixing.
Veriablemixing,beginningwithSakoandKillian[30],aimstoprovideac-countabilitybymixesissuingaproofthattheiroutputisapermutationoftheir7SomemixingservicesareonlyaccessibleasTorhiddenservices.
8Receivingone'sowncoinsbackfromamixisnotnecessarilyavulnerability.
Thiswillhappenwithprobability1NinarandompermutationofNparticipant'scoins.
5input,particularlyimportantwhenuserscannottracetheirowninputthroughthemix.
Inreputablemixing,beginningwith[15],eachmixprovidesproofthateachoutputcorrespondstosomeinput,asopposedtothemixitselforiginatingthemessage.
Unfortunatelytheselinesofresearcharelargelyorthogonaltotheriskoftheftinanancialmix.
Incommunicationmixes,messagescanberesent,whichisnotpossibleinBitcoinastransactionsareirreversible.
3AsimplemodelofmixingWhiletherearesomedierencesinhowcurrentmixesoperate,wedescribethemodelonwhichMixcoin'sdesignrests.
WestartwithaclientAlice(A)whoownssomenumberofBitcoinsatanaddressκinwhichweassumeislinkabletoherrealworldidentity.
Alicewishestotransfersomeofherfundstoafreshaddressκoutinsuchawaythatitisdiculttolinkκouttoκin(andhenceAliceherself),inexchangeforamixingfee.
AlicewillsendsomeofhercoinstoamixM,afor-protentitywhichwillholdAlice'sfundsinescrowforanagreedtimeperiodbeforesendinganequalvaluetoκout.
Wedon'trequireMtohaveanyreal-worldreputationorassets,onlytomaintainthesamedigitalidentitylongenoughtobuildavirtualreputation.
Aliceisexposedtotwomajorthreats:TheftBecausemixesroutinelysendfundstofreshaddresseswithnotransactionhistory,itispossibleforamaliciousmixtosendAlice'sfundstoitsownsecretaddressκMinsteadofκoutasrequested.
ThoughAlicecanpubliclycomplainaboutthetheftandattempttoundermineM'sreputation,thereisnowayforobserverstodeterminewhichofAorMownsκMandthereforeAlice'sclaimcouldbelibelous.
For-protmixesmayrationallyattempttounderminetrustintheircompetitorsthroughfalseaccusationsoftheft.
Becauseallegationsoftheftcannotbeproven,itisdiculttodeterminewhichmixesarehonest.
DeanonymizationBecausethemixlearnsthatthesamepartyownsbothad-dresses(κin,κout),Alice'sanonymitydependsonthemixkeepingthispairingsecretforever.
Amixwhichismalicious,compromised,orsubpoenaedmightshareitsrecordsandundermineAlice'sanonymity.
Alternately,themixcouldsendcoinsinanon-randommannerwhichrevealstheconnectiontoobservers.
4TheMixcoinprotocolOurgoalwithMixcoinistoprovideaprotocolformixingwithaccountability.
Priortomixing,themixgivesAliceasignedwarrantywhichwillenablehertounambiguouslyproveifthemixhasmisbehaved.
Dishonestmixeswillquicklyhavetheirreputationdestroyedandlosebusiness.
Securityagainsttheftthusreducestoproperlyaligningeconomicincentivesofmixesandclients.
However,thereisnowaytoprovethatamixisnotstoringrecordssucienttodeanonymizeitsclients.
Similarlytomixnetworksforcommunication,Alice6canmitigatethisriskbyrelayingcoinsthroughaseriesofmixeswhichmustallcolludeinordertodeanonymizehernaloutputaddress.
4.
1AssumptionsWeassumetheavailabilityofmultiplemixesMi,eachrepresentedbyawarranty-signingkeyKMi.
Asfor-protenterprises,mixesaremotivatedtobuildandmaintainareputationinKMi,soitmustbeusedconsistently.
Unlikemixes,Alicedoesnotneedtomaintainanylong-termpublickeynoranypublicreputation.
Alicemustbeabletonegotiatewiththemixoverananonymousandconden-tialchannel.
InpracticethiswilllikelyberealizedbymixesrunningadedicatedTorhiddenservice,butthisisoutofscopeoftheMixcoinprotocolitself.
Ideally,thischannelwillalsobedeniableforclients,sothatthemixcannotprovethatanyclientcontacteditaboutmixingfunds.
4.
2CoreprotocolWeoutlinethecoreMixcoinprotocolinConstruction1whichmixesasingle"chunk"vofAlice'sfunds.
Foreectiveanonymity,chunksizesshouldbestan-dardized,asdiscussedinSection7.
6.
Whilethecoreprotocolcanstandonitsown,typicallyAlicewillneedtosplitherfundsintomultiplechunksandperformmultiplesequentialroundsofmixingforeach.
ThekeyaccountabilitymechanismisAlice'sreceiptofasignedwarrantypriortomixing.
InStep1Alicecontactsthemixoverananonymouschannelandproposesasetofmixingparameters:vthevalue(chunksize)tobemixedt1thedeadline9bywhichAlicemustsendfundstothemixt2thedeadlinebywhichthemixmustreturnfundstoAliceκouttheaddresswhereAlicewishestotransferherfundsρthemixingfeerateAlicewillpaynanonce,usedtodeterminepaymentofrandomizedmixingfeeswthenumberofblocksthemixrequirestoconrmAlice'spaymentIfthemixacceptstheseterms(Step2a)itgeneratesafreshescrowaddressκescandsendsbackawarrantycontainingallofAlice'sparametersplusκesc,signedusingKM.
ThemixmayalsorejectAlice'srequestforanyreason(Step2b),thoughinpracticeweexpectthatareputablemixwillabidebyapublishedpolicyforacceptableterms.
10Alicesimilarlyhasnoobligationtotransferfundsafterreceivingawarranty.
IfAlicedeclines(orforgets)todosobythedeadlinet1themixmaydeleteitsrecordsandmoveon.
IfAlicedoestransfertheagreedvaluevtoκescbythedeadlinet1(Step3),thenthemixisobligatedtotransferanequalvaluetoκoutbytimet2(unless10Aspresented,thisisanall-or-nothingnegotiationwithAliceproposingtermsandthemixeitheracceptingorrejecting.
Morecomplicatednegotiationsarepossiblebutweexpectthistobethesimplest.
7TheMixcoinprotocol1)Aanon→M:v,t1,t2,w,κout,ρ,n2a)Aanon←M:{v,t1,t2,w,κesc,κout,ρ,n}KMMacceptsterms,speciesκesc2b)Aanon←M:⊥MrejectstermsAdestroysκout3)A(bytimet1):Transfer(v,κin,κesc)Apaysontime(fromanyaddress)MabortsprotocolAdoesn'tpayX=Beacon(t1,w,n)X>ρMretainsfundsX≤ρ4a)M:(bytimet2)Transfer(v,κesc,κout)Mactshonestly4b)Notransfertoκoutbytimet2MstealsfundsA,MdestroyrecordsProtocolsuccessful5)Apublicizes:{v,t1,t2,w,κesc,κout,ρ,n}KMAdetectstheft(aftert2)Construction1:AsinglemixingroundbetweenclientAandmixM.
AownstheaddressesκinandκoutandMownsκescandκesc.
TherandomvalueXR←(0,1)iscomputedusingBeacon,apseudorandomfunctionusingtheBitcoinblockt1+wplusthenoncen,andcomparedtothefeerateρ.
Timest1andt2areblocksintheblockchain.
Curlybrackets({}K)indicateadigitalsignatureunderasigningkeyK.
8thefundsareretainedasamixingfee—seeSection4.
4).
Ifthemixdoessofaithfully(Step4a),thenbothpartiesshoulddestroytheirrecordstoensureforwardanonymityagainstfuturedatabreaches.
Ifthemixfailstotransferthevaluevtoκoutbytimet2(Step4b),11thenAlicepublishesherwarranty(Step5).
Becausethewarrantyissignedbythemix'slong-termkeyKMandallBitcointransactionsarepubliclylogged,anybodycanverifythatthemixcheated.
4.
3FreshnessofaddressesBoththemix'sescrowaddressκescandAlice'soutputaddressκoutshouldbefreshaddressescreatedspecicallyforthismixing.
Thisisrequiredbecausewar-rantiesincludeneitherκinnorκesc,sotheywillappeartobesatisedaslongasvistransferredontimetoκescandthenκoutfromanyaddress.
Thusbothpartiesshouldpickaddresseswithnootherpossiblesourceofincomesothattheotherpartymustthemselvespaytofulllthecontract.
ThishasthebenetofminimizingwhatAlicerevealsifshepublishesawarranty,asκoutisuselessifthemixingtransactionitwascreatedforendsupfailing.
4.
4MixingfeesAsimpleapproachistospecifyaxedmixingfeerateρandhavethemixreturn(1ρ)·vtoκoutinsteadofthefullv.
However,thisisproblematicforsequentialmixing,asthesmalleroutputvalue(1ρ)·vcannotbetheinputtoasubsequentroundofmixingwiththesamev.
Thiscouldbeaddressedbyusingdiminishingtransactionsizesvi=(1ρ)i·vforeachroundi,butthiswouldunderminethegoal(Section7.
6)ofindistinguishabletransfersandlimittheanonymitysetineachroundtoonlyothertransactionsatthesameroundofmixing.
Oursolutionisrandomizedmixingfees,wherebywithprobabilityρthemixretainstheentirevaluevasafee,andwithprobability(1ρ)takesnofeeatall.
Thisproducesanexpectedmixingfeerateofρandleavesκoutwitheithernothingorafullvwhichcanbedirectlyre-mixed.
Thissolutionisrelatedtotheideaofelectroniclotterytickets[28]usedinsomemicropaymentsystems.
12Themixmustuseapubliclyveriablemechanismtorandomlychoosewhichchunkstoretainasmixingfees.
Specically,themixmustgeneratea(ρ,1ρ)-randombitwhichneitherpartycanpredictbutcanbeauditedafterwardsforfairness.
Thiscanbedonewithapublicsourceofrandomnesscalledabeacon.
Thereareotheroptions,suchasacoin-tossingprotocol[25]betweenAliceandthemix,butthesewouldintroduceanextraroundofcommunication.
IfthebeaconisexternaltoBitcoin(e.
g.
,NIST'sbeacon[1]ornancialdata[8]),warrantieswouldneedtobesynchronizedtoreal-worldtimetoenable11ThereisnowayinBitcointoguaranteeatransactionwillbeincludedinanyspecicblock.
Thereforeinpracticemixeswilllikelyrequireasafetymarginofseveralblockstot2toensuretheycanincludethetransactionbeforethattime.
12Ourmotivationtouserandomizedfeesisdierentfromthecaseofmicropaymentsystems,whichdosotoavoidtransactioncostsfrommanylow-valuedpayments.
9auditing.
Alternatively,randomnesscanbeextractedfromfutureBitcoinblocks,assumingtheexactsetoffuturetransactionsincludedineachblock(aswellastherandomnonceusedtosolvetheproof-of-workpuzzle)isunknown.
13Becauseeachblockincludesthevalueofthepreviousblock,everytransactionduringaconrmationperiodofwblocksaddsrandomness.
14ThewarrantyalsoincludesanoncenspeciedbyAlicetoensurethatthemixwillcomputeanindependentvalueforalltransactionsitismanaging.
Specically,themixcomputesX=Beacon(t1,w,n)=PRNG(n||Bt1+w),whereBiistheMerklerootofblockiintheblockchainandPRNGisacryptographicpseudorandomnumbergeneratorwhichoutputsavalueuniformlydrawnfromtherange(0,1).
ThemixretainsAlice'sfundsonlyifX≤ρ.
BecausethiscomputationcanbeperformedbyanybodyifAlice'swarrantyispublished,cheatingbythemixisdetectable.
Furthermore,innormaloperationAlice'swarranty(containingn)iskeptsecretsoobserverscan'ttellwhichtransactionswereretainedbythemix.
Adrawbackofrandomizedfeesisincreasedvarianceintheeectivemixingfeerateforusersmixingasmallnumberofchunks.
Toaddressthis,vshouldbekeptaslowaspossiblesothatmostuserscanmixatleastvρcoins.
4.
5TransactionfeesInadditiontomixingfees,AlicemayhavetopaytransactionfeestoBitcoinminerstoensurehertransactionsareincludedintheblockchain.
15Fixedtrans-actionfeesposethesameproblemforanonymitythatxedmixingfeeswould,butpayingminersrandomlywouldrequirechangestoBitcoinitself.
Givenasourceofanonymouscoins,Alicecouldaddresstheproblemofde-creasingchunksizesby"toppingup"eachchunkafteritismixedusingherpoolofanonynmizedcoins.
However,itdoesn'tworkforAlicetosimplymixonechunkperfectlyandthenuseittopupmanyotherchunks,asthiswouldpubliclylinkeachofthosetoppedupchunksasbelongingtothesameparty.
ThusAlicewouldneedalargenumberofmutuallyunlinkableaddressesholdingtransaction-feesizedvaluesusefulfortoppingup.
Acquiringthesethroughmix-ingbecomesarecursiveproblemthough,astheythemselveswouldrequireanevengreaternumberofunlinkableaddressesfortheirmixing!
Instead,mixescaneectivelypaytransactionfeesboth16forthetransferfromκintoκescandfromκesctoκout.
Assumingminersrequireaminimumtransactionfeeτ(withτv),Alicecantransfervfromκinofwhichthemixwillreceivevτataddressκesc.
Themixcanthenformanoutputtransaction13Amixmightalsobeaminer,inwhichcaseitmayattempttoinuencetheblock.
However,suchanattackishighlyuneconomicalgiventhehighrewardforminingablockcomparedtomixingfees.
WeaddresstheinfeasiblitythisattackinAppendixC.
14Thoughinpracticew=6isacommonstandard,weincludewasanegotiableparameterinthewarrantytoenableexibility.
15Sometransactionsareacceptedtodaywithoutfees,thoughminersmaychangethisatanytime,whichmayoccurasthemintingratedecreases.
16Inpipelinedsequentialmixing,whichwewilldiscussinSection5,mostmixeswillneedonlypayonetransactionfee.
10withvτfromsomeκescand2τfromathirdaddressκescwhichthemixpreviouslyretainedasamixingfee,ensuringthatκoutreceivesafullvwhiletheminersstillcollectafeeofτforeachtransaction.
Ofcourse,themixingfeerateρmustbeincreasedtocoverthemix'sexpectedoutlaysontransactionfees.
Thisposesaproblemformixindistinguishability,whichwe'lldiscussfurtherinSection7.
2,asatthemixmustusethesameκesctocovertransactionfeesformultiplechunkswhichwillthenallclearlycomefromthesamemix.
ItisalsopossibleformixestocollaborateandmixtheirreservesavailablefortransactionfeesusinganothermixingtechniquesuchasCoinJoin[19],whichmaybemoresuitedformixestoexecutethanindividualusers.
5SequentialmixingGiventheaboveMixcoinprotocolforinteractingwithasinglemix,AlicewillmostlikelywanttosendherfundsthroughNindependentmixestoprotectheranonymityagainstthecompromiseofanindividualmix.
Todoso,AlicecanchooseasequenceofNmixesM1,.
.
.
MNandexecutetheMixcoinprotocolwitheachoftheminreverseorder,instructingeachmixMitoforwardherfundstotheescrowaddressκesci+1whichshepreviouslyreceivedfrommixMi+1.
AfterobtainingNsignedwarranties,17Alicethentransfersherchunktoκesc1andifanymixinthesequencefailstotransferitshecanproveitwiththeappropriatewarranty.
Onesubtletyisthateachmixcanlikelydeterminewhichnumberitisinthesequencebasedontiminginformation,asthelatermixeswillbecontactedfurtherinadvancefromwhenmixingwillactuallytakeplace.
Inpractice,Alicemostlikelywantstotransfersomevaluekvbysplittingintokseparatechunks.
ThismeansshewillneedtonegotiateatotalofkNwarrantieswithmixes.
Animportantconsiderationisthateachchunkshouldtravelthroughanindependently-chosenrandomsequenceofmixes.
Otherwise,Alice'schunkswouldbeexchangedforeachothermorefrequentlythanwouldhappenviachance,whichwouldleakinformationtoapotentialattacker.
5.
1DynamicselectionofmixingpathsUnliketraditionalmixnetworks,analternateapproachispossibleinwhichAlicedoesn'tnegotiateanend-to-endpathupfrontbutreceivesherchunksbackaftereachmixroundatfreshintermediateaddresses.
ThisapproachenablesAlicetodynamicallydeterminewhichmixestouseandhowmany,andwouldhidefromeachmixwhichorderitisinthemixingsequence.
Thedownsideofthisapproachisaddedlatency,aswellaspayingdoublethenumberoftransactionfees.
18Giventhesedrawbacks,weanticipatethatdynamicmixingisalessattractiveoption,thoughitcouldbeusedinhybridformwithAliceperformingmultiplesequentialmixestoavoidnegotiatingaverylongpathupfront.
17Unlikeintraditionalcommunicationnetworks,anonionroutingapproachdoesn'tseempossibleduetotheinteractivityrequiredinMixcoin.
18Transactionfeescanstillbepaidbymixestoavoidthechunksizevaluedeclining,butthiswillrequireanincreaseinρwhichAlicewillhavetopay.
116MixincentivesandmixingfeesEstablishingthemixingfeerateρrequiresconsideringthedualrolesofmixingfees.
First,theycancoverdirectexpensesformixessuchasBitcointransactionfeesandelectricitybills.
Secondandmostimportantly,theyprovideamechanismformixestoprotfromhonestbehavioranddisincentivizemixesfromceasingoperationsandabscondingwithusers'funds.
Becausehigherfeesmorestronglyincentivizehonesty,aninterestingpropertyarisesthatusersshouldavoidmixescharginglessthansomeminimumacceptablevalueofρ.
Inasteady-statemodel,themixhastwochoicesforanygivenblockintime:continuetooperatehonestlyuntilthenextblock,orabscondandretainalluserfundsitholdsinescrow.
TheexpectedvalueofeitherchoicescaleslinearlywithQ,theaverageamountofmoneyowinginto(andoutof)themixduringanyoneblock.
Iftistheaveragetimeperiod(inblocks)thatthemixholdsfundsduringamixinground,thentheexpectedpayoofabscondingisE[abscond]=Qt.
Theexpectedpayofromchoosingtocontinuewouldproperlybedenedrecursively,sincethemixisabletoplaythesamegameagain.
However,understeadystateconditionstheoptimaldecisionwillbethesameineveryround,soifthemixinitiallychoosestocontinueitwilldosoindenitely.
Assumingthemixisexponentiallydiscountingfutureearnings19atarater(perblock),thenetpresentvalueofindenitehonestbehaviorwithafeerateρis:E[continue]=ρQ+(1r)E[continue]=ρQ+(1r)ρQ+(1r)2ρQ+.
.
.
=ρrQIncentivizinghonestbehaviorthereforerequiresthatρr>t.
Withtheinter-pretationthatrforarationalmixisequivalenttothehighestavailablerisk-freerateofreturnavailable,thisconditionissimplythattheexpectedvalueoffeescollectedbyamixduringthetimeitholdsfundsisgreaterthantheamountthosefundswouldyieldduringthesametimeperiodifinvested.
20Thiscanbeexplainedbyconsideringthatwewantanhonestmixtocontinuallydecidedto"invest"itspotentialearningsQtfromabscondingintocontinuingtoserveasamix,earningareturnofρQduringeveryblock.
Wecanestimatethatrelativelylowmixingfeesshouldsucetoincentivizehonestbehavior.
Assumingaveryattractiverateofreturnofr≈20%annuallyisavailabletothemix,amixtimeoft≈1hourgivesalowerboundofρmin≈215.
Evenconsideringachunktakingapaththrough10consecutivemixes,thisstillleavesonlyaneectivefeerateof≈212necessarytodiscourageabsconding.
Thissuggeststhatverylowmixingfeesmaybesucienttocovertheriskoftheft.
19Theexchangerateofbitcoinsmayofcoursebedrasticallydierentinthefuture.
Weassumemixeshavenoprivateinformationaboutthefuturevalueofbitcoinsandthereforeuseitscurrentmarketpriceincalculatingthenetpresentvalue.
20Thisequivalenceignorestheeectsofcompoundinginterest,thoughrandtarebothlowenoughthat(1+r)t1+rt.
12Abscondingmightbeslightlymorefavorableinpracticeduetoseveralfactorsmissingfromasimpleanalysis,suchassuper-exponentialtimediscountingbythemix,theriskthatbusinessmaydecline,orthefactthatthemixcanchoosetoabscondduringaperiodofunusuallyhightransactionow.
Still,actualmixingfeeswillbedominatedbyoperatingcosts,suggestingthatanymixwhichhasbeenoperatingforanon-trivialperiodoftimeisturningaprotandisunlikelytoabscond.
Unfortunately,Alicecan'tknowwhatmixes'operatingcostsare,andthereforecannotverifythatarationalmixwillchoosetostayinbusinessatagiveninstant.
Nevertheless,sinceabscondingisaone-timeaction,shecangainsomeassurancefromthelongevityofthemix.
7AnonymitypropertiesGiventhelargenumberofnegotiableparametersinMixcoin,ouranonymityanalysisistheoretical.
Theactualanonymityguaranteeswilldependonhowthemixingecosystemevolves.
However,wecandescribeathreatmodel,quan-tifyanonymityunderasimpliedmodel,discussoptimalstrategiesformixesandclients,enumeratesomeattacksandhowtoavoidthem.
Wecandrawmanycon-nectionstotheextensiveliteratureonmixnetworksforcommunication,datingtotheinitialproposalofcommunicationmixes[5].
Thatsaid,nancialmixingalsodiersfromcommunicationnetworksinimportantways.
7.
1ThreatmodelMixingliteraturetypicallyanalyzestheanonymitysetofpossiblepartnersinacommunicationsnetwork.
Forunidirectionalormessage-basedsystems(asop-posedtostreams),theanonymitysetmaybeconsideredseparatelyforsendersandreceiversthoughthetwooftenhavesymmetricproperties.
WithMixcointhecommoncaseisasinglelinkableinputaddresssendingmultiplechunkstodistinctoutputaddresseswhichneverreceiveanyotherinput.
Wefocusonanattackerwhowantstogainasmuchinformationaspossibleabouttheanonymitysetofpossiblepre-mixinginputaddresseswhichmayhavebeenthesourceofthefundsheldbyanaloutputaddressκout.
BecausetheBitcoinblockchainisapermanent,publicrecordofalltrans-actions,everyattackeristriviallyaglobalpassiveadversary,acommonattackmodelstudiedforcommunicationmixes.
21Mixingliteraturealsoconsidersex-tendedattackercapabilities,suchascompromisingmixes,delayingorblockingmessages,replayingoldmessages,oroodingthenetworkwithdummymes-sages[32].
ReplayshouldbeimpossibleinMixcoinduetothedoublespendingpreventioninBitcoin.
Floodingispossibleandweshouldassumeattackershavethiscapability.
DelayingBitcointransactionsispossible,butnottrivial.
Anyminercanrefusetoincludetransactionsinblockstheymine,butthisscales21Torisnotablynotdesignedtowithstandattackbyaglobalpassiveadversary,asTorrelaysprovidenomixingoftrac[13].
13withtheproportionofminingpowertheattackercontrols,makinganeectiveattackpracticallyexpensive.
Anattackermightalsotrytooodminerswithlargervaluetransactions,butthereisnowaytodososelectivelyandthiswouldthusamounttoadenialofserviceattackonallofBitcoin.
Assuminganattackerdoesn'tcontrolasubstantialportionoftheminingpool,blockingtransactionsindenitelyshouldbeeectivelyimpossible.
7.
2Thepassiveadversary'sviewwithmixindistinguishabilityThebest-casescenarioforMixcoinisapassiveadversary.
Weassumethisadver-sarycanreliablydeterminewithhighprobabilitywhichBitcointransactionsaremixtrac,giventheirsizevandtheiruseofone-timeescrowaddresses.
How-ever,duetotheirone-timenature,thissimpleadversarymaybeunabletolinkescrowaddressestospecicmixes,anovelpropertywithnoapparentprecedentincommunicationmixeswhichwecallmixindistinguishability.
Ifthisisthecase,theadversaryislefttoobserveaseaofapparentlyiden-ticalescrowaddressesandthesystemappearstofunctionasoneuniversalmixconsistingofallparticipantsusingthechunksizev.
Thereareseveralscenariosinwhichmixindistinguishabilitymayfail(whichwewilldiscussinSection7.
3)buttheanonymityoeredisquitestronginthiscase.
PhantommixingMixindistinguishabilitybringsaboutaninterestingpossi-bility,alsowithnoprecedentincommunicationmixes.
Usersmayapparentlygainsomeanonymityby"phantommixing":sendingtheirfundsthroughescrowaddressestheycontrolthemselves.
Toapassiveobserverthisisindistinguishablefromausersendingfundsthroughagenuinethird-partymix.
Ofcourse,ifasig-nicantproportionofusersdothis,theseuserswillloseanonymityasattackerswillbeabletoinferthattheownerofachunk'snaloutputaddressisthesameastheownerofthechunk'sinputaddresswithelevatedprobability.
Thereforewedon'tconsiderthistobealikelyphenomenon.
7.
3ActiveadversariesanddistinguishablemixesThereareseveralwaysthatanactiveattackermightbeabletodistinguishwhichescrowaddressescorrespondtowhichmixandhencewhichmixesareinvolvedinachunk'smixingpath.
ObservethatwhenAlicesendsachunkfromκintoMviaκesc,theclientwhoultimatelyreceivesthischunkwilllearnthatκininteractedwithM.
Similarly,theclientwhosendsthechunktoκescwhichiseventuallysenttoκoutwillalsolearnthatAliceinteractedwithM.
Anactiveadversarycanexploitthisinaoodingattack,learninguptotwootheraddressesinteractingwiththesamemixforeachchunksentthroughthatmix.
Asecondattackvector,ifmixesareforcedpaytransactionfees,isthatwhenauser'schunkisretainedasamixingfeebymixMitmaymightbeusedbyMtopaytransactionfeesonmanyothertransactions,allofwhichcanthenbelinkedtoM.
Theeectivenessofthisattackdependsontheratiooftransaction14feesperchunkτtoaveragemixingfeesperchunkρv.
Mixeswillhavetospendaproportionτρvoftheirmixingfeerevenueontransactionfees,soifmixesallocateaconstantproportionofeachretainedchunktotransactionfeeseachretainedchunkwillpayfeeson1ρ·τρvothertransactions.
Sinceeachchunkisretainedwithprobabilityρ,theexpectednumberoftransactionsidentiablebyagiveninputtransactionisjustτρv,whichismaximizedat1ifmixingfeesareonlyhighenoughtocovertransactionfees.
ThusforeachmixingtransactionanactiveattackerperformswithM,shecanlinkupto(1ρ)·2+τρvothertransactionstoM.
Observingthemajorityoflinksthereforeappearstorequireanattackergeneratealargeportionofthemix'strac.
Finally,theattackermaybethemixthemselves,orbeablecompromisethemixorsubpoenaitsrecords,whichwouldrevealallinput/outputpairs.
WecouldattempttosupplementMixcoinbyissuingusersblindedtokenstoredeemwiththemixinexchangeforcoinsinthestyleofChaum'soriginaldigitalcashscheme[6].
However,thiswouldgreatlycomplicatedisputeresolutionastheusermustprovethattheyattemptedtoredeemtheirtokentothemixandthemixrefused.
Thiswouldrequirepublishingredemptionorderstoapublicledger,suchasBitcoinitself.
Weleavethedetailsofsuchaschemeforfuturework.
Againstsuchastrongactiveattackerwhocanlinkeveryescrowaddresstoitsoriginatingmix,thesystemappearssimilartobeatraditionalcommunicationmixnetworkwithmixesbehavingasstop-and-gomixes[17]withlimitedpoolingduetotheblocksize.
Stop-and-gomixessuerfromlowguaranteesofanonymityinperiodsoflowtrac,butimplementingotherstrategiessuchasthresholdmixesappearsverydiculttoachievewithourwarrantysystemsassignicantlymoreinformation(includingtheentiresetoftransactionssenttoamix)wouldneedtobeavailabletoenforcewarranties.
Assumingareasonablysteadyowoftrac,theanonymitysetstillsnowballsquickly.
WedemonstratethisviasimulationinAppendixD.
7.
4AnonymitysetsandmixdelayRegardlessofmixdistinguishability,thereisatrade-obetweenmixingchunkswithmanymixesforashortescrowperiodeachorfewmixeswithalongerescrowperiod.
Theescrowperiodislimitedbyt2andt1asspeciedinthewarranty,withamaximumdelayofδmax=t2t1.
Mixeswillalsorequireaminimumdelayofδmin=w(typically6blocks)toprotectagainstdoublespending.
Pickingthesmallestpossiblet2=t1+wallowsAlicetoaordmoreroundsofmixinginagiventimeperiod.
ButthisalsomeansthatAlice'sanonymitysetfortheroundconsistsonlyofotherchunksthatweremixedattimeexactlyt1.
Weassumethatindividualmixeswillonlyissuewarrantieswithaspecicδmaxasamatterofpolicy,22andwillthenuniformlyatrandomchooseade-layδ∈R[w,δmax]beforeforwardingAlice'schunk.
23Thuseachmixingstep22Allowingdierentdelaysperclientwouldopenthepossibilityoffree-ridingandmakeanonymityanalysismuchmorecomplex[14].
23Non-uniformdistributionssuchasanexponentialdistributionarepossible,buttheymakeitdiculttoprovidearmboundonthedelayasrequiredbythewarranty.
15addslg(Q(δmaxw+1))bitsofentropytoAlice'sanonymityset,atadelayofδmaxblocks.
24Inotherwords,theentropyofheranonymitysetgrowsbylg(Q(δmaxw+1))δmaxperblock.
Itturnsoutthatforw=6thisexpressionismaxi-mizedforδmax=6forQ≥128(andδmax=7for13≤Q<128)soitappearsminimaldelaysandlongermixingchainsarepreferable.
Whateverthemix'spublishedpolicyis,Alicecaneasilyverifythattheran-domdistributionofδmatchesthemix'spolicysinceweexpectthatovertimeshewillsendalargenumberofchunkstothemix.
Ifthemixcheatsandpicksde-laysthatdon'tmatchthedistributionspeciedinitspolicy,itisnotaviolationofthewarranty(aslongasthemixadherestoitsmaximumdelay).
However,individualclientscandetectthischeatingandtaketheirbusinesselsewhere.
Latency/anonymitytrade-oIfwearewillingtosacricemixindistin-guishability,mixescansignicantlydecreaselatencybyskippingthenormalconrmationdelayofw=6blocks,batchingalloftheirQpermutedchunksinagivenblockintooneatomictransactionwithQinputsandQoutputs.
Intheeventofafork,ifanyinputtransactiontothemixisremovedfromtheblockchaintheentiretransactionwillbeinvalidandcan'tbereplayed,protectingthemix.
Thusthereisatrade-obetweenanonymityandlatency,andmuchlowerlatencycanbeachievedatthecostofmixindistinguishability.
7.
5MixingmultiplechunksSofarwehaveconsideredeachchunkindividually.
However,ifAlicecombinesmanymixedchunkstomakeapayment,heranonymitysetwillbereducedtotheintersectionoftheanonymitysetsofallchunks.
Aslongasshemixedthosechunkssucientlyatthesametime,thenthosechunkswillhavethesameanonymitysets,andherpaymentisstillunlinkable.
However,ifevenoneofthechunkstravelsthroughapathconsistingentirelyofcompromisedmixes,Alice'sentirepaymentcompletelylosesanonymity.
Ifeachchunkisroutedindependently,thenwithsay25%ofmixescompromised,thereisa220chanceofroutingachunkthroughachainof10compromisedmixes,whichmaybeacceptablylow.
Howeverthisprobabilityincreasesrapidlyifagreaterfractionofmixesarecompromised.
Onewaytoavoidthiswouldbetorandomlypickasetofmixesforeachbatchoffundstomix,andtousearandompermutationofthatsetforeachchunksinthebatch.
InTor,thereisasimilarargumentforwhybuildingcircuitsimprovesanonymityasopposedtoroutingeachpacketindependently.
Theselectionofmixesforeachchunk'spathposesaninterestingchallenge.
Foranonymity,eachchunk'spathshouldbechosenindependentlyatrandomfromthesamedistribution.
Weenvisionmixreputationlists(MRLs)publishedbyneutralevaluatorswhichestimatelegitimatemixtransactionvolumeviathe24BecauseAlicemusthavealreadynegotiatedhermixingwarrantyforthenextround,eachwarrantymustbedelayedbythemaximumδmaxblocks.
16methodsoutlinedinAppendixB.
Suchlistswouldincludeasuggestedproba-bilitydistributionovermixesbasedonreputationscores,limitingexposuretounreputablemixeswithoutweighingtooheavilytowardsasmallsetofthemostreputablemixeswhichcouldcolludetobreakanonymity.
Userswillwanttosharearandompathselectionalgorithmtoavoidleakinginformation,andthereforeweexpectafewdominantMRLservicestoarise.
ItseemstemptingtosimplyusetheNmostpopularmixespermanently,sinceusingmorepopularmixesimprovestheanonymityset.
However,usingpopularmixesimprovesanonymityonlyagainstanverypowerfulactiveadversary,andpopularmixesmaybemoreattractivetargetsfortheadversarytocompromiseleadingtoagreaterprobabilityofpickingacompletelycompromisedpath.
Thisquestionalsoimpactshowmanymixesweexpecttosee.
Ifthereisastrongpreferenceforpopularmixes,thenthebarriertoentrywillbehighandtherstentrantswillcornerthemarket.
Ifnot,therewillbeadiversityofmixes.
Itisimpossibletodenitivelyanswerthisquestion,butourbestguessisthattherewillbeperhapsadozenpopularmixesfollowedbyalongtail,andclientswilluseacombinationofthetwotypesinthepathstheychoose.
7.
6ConvergenceoffreeparametersOurdesignintentionallyleavesmanyparametersfree,suchasthechunksizev,thetimedelayt2t1andthenumberofroundsN.
OurphilosophyistoavoidembeddingtheseintotheprotocolastheoptimalchoicesmaydriftovertimeasthemixingecosystemevolvesandtheunderlyingparametersofBitcoinchange.
Yetitiscriticalforanonymitythatalargenumberofuserschoosethesamevalues25toavoidsplittingtheiranonymitysetsbasedonparameterchoices.
Asacasestudy,considertheeectoftwodierentcommonvaluesofv.
Eachwillbeclearlyidentiableintheblockchainandhencetheanonymitysetforeachchunkislimitedinthebestcasetothoseuserswhomixedachunkofidenticalsizeinthesametimeperiod.
Wecouldattempttoamelioratethisslightlybyhopingthatallusersmixchunksofbothsizesregularly,butthisisquitefragile.
26Thebest-casescenarioforanonymityisifalluserschoosethesamechunksize.
Yetthereisaninherenttrade-o:settingvtoohighwillexcludeusersowninglessthanvcoins,27whiledecreasingvwillrequireproportionatelymorerunsoftheprotocolandmoretransactionsintheblockchain.
28Still,weexpectvandotherparameterstoconvergeinpracticetoacommonvalue(orasmallset)fortworeasons.
First,likewithBitcoinitselfmostclients25Notethatthemixingfeerateρisunobservableandhenceshouldhavenoimpactonanonymityandcanbechosenindependentlybydierentmixes.
26Forexample,ifchunksizesαandβarecommon,ausermixingx=k1α+k2βwillhaveheranonymitysetlimitedtootherusersmixingatleastk1chunksofsizeαandatleastk2ofsizeβ,insteadofallusersmixingatleastx.
27Additionally,withrandomizedmixingfees(seeSection4.
4)usersowningonlyasmallmultipleofvmayfaceunacceptablyhighvarianceintheirfeerate.
28TheBitcoincommunityfrownsoncreatinglargenumbersoflow-valuetransactions(referredtoasdust)becauseitplacesahighervericationburdenonminers.
17willlikelyuseoneofasmallnumberofsoftwareimplementationswhichincludereasonableparametersandapopularmixreputationlist,asdiscussedinSection7.
5Secondandmoreimportantly,allclientshaveanincentivetochoosethemostpopularparametersinanapplicationofthe"anonymitylovescompany"principle[12].
Unilateralvariationinauser'stransactionsizes,forexample,couldleakinformationwhichwouldhelpEvedeanonymizeAlice'scoins.
ThusweexpectMixcoinuserstorelativelyquicklyconvergeonaglobalsetofparameters,orpossiblyasmallnumberof"avors"ofMixcoin,tomaximizeanonymity.
Itisanopenquestionhowtheseparametersmightchangeovertime.
Forexample,asBitcoinexperiencesinationordeationtheoptimalchunksizewillchange.
Weexpectthattheecosystemwouldreactbyintroducinganewchunksize,withatransitionalperiodwheresomemixesandclientsusetheoldsizeandothersusethenewone,withthenewchunksizegraduallywinningover.
7.
7SidechannelsFinancialmixingintroducesseveralsubtlesidechannels.
29Themostobviousispaymentsizes:IfAlicereceivesaveryspecicamountofBitcoinsatherlong-termaddress,isobservedmixingthem,andadaylateranequalquantityofmixedchunksarecombinedtomakeapayment,theadversarymightplausiblyinferthatAlicemadethepayment.
30ThiscanbeaddressedifAlicemixesherincomingfundsassoonasshereceivesthemandnotimmediatelypriortomakingapayment.
Ofcourse,thisrequiresAlicetoalwayscarryabalanceofmixedfundsandneverpaythemalloutatonce.
Moresubtleissuesarisebecausemixedchunkscarryanimplicittimestampofwhentheywerelastmixed.
SupposeAliceimmediatelymixesthreelarge,equal-sizedquantitiesofincomeonthreespecicdatesandthenlatercombinesarandomsubsetofhermixedchunkstomakeapayment.
EvecantracetheoutgoingpaymenttoAliceifitcontainsamixofchunksfromthesetimesandAlicewastheonlypersonmixingateachofthem.
31TheattackmightworkevenifAlicewasn'ttheonlypersonmixing:ifAlicepicksarandomsetofhermixedchunks,thentheproportionofchunksfromeachtimeperiodintheoutgoingpaymentwillcorrespondtotheamountAlicemixedineachtimeperiod.
Thus,evenperfectmixingcanleaveAlice'stransactionslinkablewithoutfurtherobfuscation.
OnedefenseisforAlicetoonlymakepaymentsusingchunksthatweremixedcontemporaneously.
Thisworksifpaymentsaresmallenough.
Second,Alicecouldre-mixallofherchunkseverytimeshereceivesincome.
Thisdestroysthetiminginformation,butisexpensive.
Third,ifAlicehasadvancenoticebeforeneedingtomakeapayment,shecanemployinput/outputmixing.
Alicemixesherfundsassoonasshereceivesincome.
Whensheneedstomakea29Network-levelsidechannelsareoutofscope.
Asnotedearlier,weassumethatMix-coinclientsalwayscommunicateusingasecureanonymitynetworksuchasTor.
30Thisisanalogoustoapacketcountingattackincommunicationmixes.
31Thisisanalogoustoanintersectionattackinthemixingliterature.
18payment,shemixesasetof(alreadymixed)chunkstotalingtheamountsheowes.
Itintroducesadelayinpaymentequivalenttomixingtime,whichiswhyAlicemusthaveadvancenotice.
Finally,inAppendixAweintroducecontinualmixing,amorecomplexapproachwhichcanprovidestrongerguaranteesofanonymity.
8RelatedBitcoinanonymitytechnologiesSeveralacademicproposalshaveaimedtoprovidestronganonymitycrypto-graphically.
MostprominentisZerocoin[22],whichusesacryptographicaccu-mulatorwithzero-knowledgeproofsofinclusiontoimplementaglobalcurrencypoolfromwhichuserscandepositcoinsandwithdrawrandomcoinswithoutanytrustedparties.
UnfortunatelyZerocoinandrelatedproposalssuchasPinoc-chiocoin[10]requiremodicationstoBitcoinwhichappearunlikelyduetothecomputationaloverhead.
Mixcoin,bycontrast,canbedeployedimmediately.
Zerocash[4]providesevenstrongeranonymity,revealingnoinformationpub-liclywhichlinksthesourceanddestinationoftransactions.
Zerocoinfundamen-tallyrequiresstartinganewcurrencyandhenceisnotbackwards-compatiblewithBitcoinorrelatedcurrencies.
Zerocashalsorequiresatrustedsetupphase,andknowledgeoftherandomnessusedcanbeusedtoforgecoins.
32Analternatelineofresearch,mostlyarisingfromtheBitcoindevelopercom-munity,istoremovethetrustrequirementfrommixingusingmorecomplicated(butalreadysupported)Bitcointransactionscripts.
Forexample,Barberetal.
's"fairexchange"protocol[3]orMaxwell'sCoinSwap[20]allowtwopartiestoanonymouslyswapcoinswithnoriskoftheftusingamulti-stepprotocolandatleast4transactions(comparedto2inMixcoin).
BothoftheseprotocolscouldbeusedasanalternativetoMixcointofacilitatemixingwithnoriskoftheftandmixindistinguishabilityagainstapassiveattackerandouranonymityanalysiswouldstillapply,includingthelossofmixindistinguishabilityagainstaoodingattack.
Incorporatingtransactionfeesisanotheropenproblemintheseprotocolsandtheredoesn'tappeartobeasimplewaytoapplyourrandomizedapproach.
Finally,CoinJoin[19]enableskuserstoatomicallytransferfundsfromtheirkinputaddressestotheirkoutputaddressesinarandompermutation.
Sincethetransactionisatomicandrequireseveryparticipanttosign,thereisnoriskoftheft.
Thetransactionfunctionsasanimplicitmixbetweentheparticipants.
Howeverarrangingtheoutputaddressesrandomlywithoutuserslearningthecorrespondenceforotherusers'coinsintroducescomplexity.
Thiscanbesolvedcryptographically[9],butthislikelylimitsktotensofusersorless.
Alternately,atrustedfacilitatorcanbeused,inwhichcasekislimitedtoperhapshundredsofusersduetothecostofincreasinglylargetransactions.
Ineithercase,asin-gleattackercaneasilyblockthetransactionbyparticipatinginitiallytoformthetransaction,butfailingtosignthenalizedtransaction.
OverallweexpectCoinJoinmightbeusefulforsmall-scalemixingbuttheanonymityoeredmaybelowerduetothelackofmixindistinguishability.
32ThetrustedsetupmaybeobviatedusingtechniqueslikeRSA-UFOs[31].
199ConclusionDespitesignicantinterestinprovidingstronganonymityforBitcoin,thedesignofarobustprotocolwiththatcanbedeployedwithoutmodicationstoBitcoinhasremainedanopenquestion.
InthispaperweproposedMixcoin,whichwebelievemeetsthesegoals.
Ourkeyinnovationsarecryptographicaccountability,randomizedmixingfees,andanadaptationofmixnetworkstoBitcoin.
WelookforwardtoengagingwiththeacademiccommunityandtheBitcoincommunitytofurtherrenethedesignandtoprogresstowardimplementationanddeployment.
Wealsoprovideaninitialtreatmentofmixingfornancialprivacy,aresearchareawhichweexpectwillbeasdeepandchallengingasmixingforcommunica-tionprivacy.
Manybasicpropertiesofcommunicationmixes,suchastheabilitytopadorreplaymessages,don'texistinanancialsetting.
Yetinterestingnewproperties,suchasthepossibilityofindistinguishablemixes,arise.
Weexpectthatensuringnancialprivacy,regardlessoftheunderlyingmixingprotocol,willrequirecarefulconsiderationofsomeofthehigher-levelsidechannelswehaveonlybrieyexploredhere.
Acknowledgments.
Wethankouranonymousrefereesandallwhoreaddraftsandcontributedvaluablesuggestionstothiswork,especiallyAaronJohnson,IanMiers,RogerDingledine,GeorgeDanezis,PeterEckersley,PeterToddandEranTromer.
JoshuaKrollwassupportedbytheNationalScienceFoundationGraduateResearchFellowshipProgramundergrantnumberDGE-1148900.
20References1.
NISTRandomnessBeacon.
http://www.
nist.
gov/itl/csd/ct/nist_beacon.
cfm2.
Androulaki,E.
,Karame,G.
O.
,Roeschlin,M.
,Scherer,T.
,Capkun,S.
:EvaluatingUserPrivacyinBitcoin.
In:FC(2013)3.
Barber,S.
,Boyen,X.
,Shi,E.
,Uzun,E.
:BittertoBetter—HowtoMakeBitcoinaBetterCurrency.
In:FC(2013)4.
Ben-Sasson,E.
,Chiesa,A.
,Garman,C.
,Green,M.
,Miers,I.
,Tromer,E.
,Virza,M.
:Zerocash:DecentralizedanonymouspaymentsfromBitcoin.
In:SecurityandPrivacy(SP),2014IEEESymposiumon.
IEEE(2014)5.
Chaum,D.
:Untraceableelectronicmail,returnaddresses,anddigitalpseudonyms.
CommunicationsoftheACM24(2),84–90(1981)6.
Chaum,D.
:Blindsignaturesforuntraceablepayments.
In:CRYPTO(1982)7.
Christin,N.
:Travelingthesilkroad:Ameasurementanalysisofalargeanony-mousonlinemarketplace.
In:Proceedingsofthe22ndInternationalConferenceonWorldWideWeb.
pp.
213–224.
InternationalWorldWideWebConferencesSteeringCommittee(2013)8.
Clark,J.
,Hengartner,U.
:OntheUseofFinancialDataasaRandomBeacon.
UsenixEVT/WOTE(2010)9.
Coutu,O.
:DecentralizedMixersinBitcoin.
In:BitcoinConference(2013)10.
Danezis,G.
,Fournet,C.
,Kohlweiss,M.
,Parno,B.
:PinocchioCoin:BuildingZe-rocoinfromaSuccinctPairing-BasedProofSystem.
In:LanguageSupportforPrivacy-EnhancingTechnologies(PETShop)(2013)11.
Diaz,C.
,Seys,S.
,Claessens,J.
,Preneel,B.
:Towardsmeasuringanonymity.
In:PETS(2003)12.
Dingledine,R.
,Mathewson,N.
:AnonymityLovesCompany:UsabilityandtheNetworkEect.
In:WEIS(2006)13.
Dingledine,R.
,Mathewson,N.
,Syverson,P.
:Tor:Thesecond-generationonionrouter.
In:USENIXSecurity(2004)14.
Dingledine,R.
,Serjantov,A.
,Syverson,P.
:Blendingdierentlatencytracwithalpha-mixing.
In:PET.
pp.
245–257.
Springer(2006)15.
Golle,P.
:Reputablemixnetworks.
In:PETS(2004)16.
Jolly,G.
M.
:Explicitestimatesfromcapture-recapturedatawithbothdeathandimmigration-stochasticmodel.
Biometrika52(1/2),225–247(1965)17.
Kesdogan,D.
,Egner,J.
,B¨uschkes,R.
:Stop-and-go-mixesprovidingprobabilisticanonymityinanopensystem.
In:InformationHiding.
pp.
83–98.
Springer(1998)18.
Kroll,J.
A.
,Davey,I.
C.
,Felten,E.
W.
:TheEconomicsofBitcoinMining,orBitcoininthePresenceofAdversaries.
In:WEIS(Jun2013)19.
Maxwell,G.
:CoinJoin:Bitcoinprivacyfortherealworld.
https://bitcointalk.
org/index.
phptopic=321228(August2013)20.
Maxwell,G.
:CoinSwap:Transactiongraphdisjointtrustlesstrading.
CoinSwap:Transactiongraphdisjointtrustlesstrading(October2013)21.
Meiklejohn,S.
,Pomarole,M.
,Jordan,G.
,Levchenko,K.
,McCoy,D.
,Voelker,G.
M.
,Savage,S.
:Astfulofbitcoins:characterizingpaymentsamongmenwithnonames.
In:IMC(2013)22.
Miers,I.
,Garman,C.
,Green,M.
,Rubin,A.
D.
:Zerocoin:AnonymousDistributedE-CashfromBitcoin.
IEEESymposiumonSecurityandPrivacy(2013)23.
M¨oser,M.
:AnonymityofBitcoinTransactions:AnAnalysisofMixingServices.
In:ProceedingsofM¨unsterBitcoinConference(2013)24.
Nakamoto,S.
:Bitcoin:Apeer-to-peerelectioniccashsystem(2008)2125.
Naor,M.
:Bitcommitmentusingpseudo-randomness.
In:AdvancesinCryptology-ProceedingsofCRYPTO89.
pp.
128–136.
Springer(1990)26.
Raymond,J.
:Tracanalysis:protocols,attacks,designissues,andopenproblems.
In:PETS(2001)27.
Reid,F.
,Harrigan,M.
:Ananalysisofanonymityinthebitcoinsystem.
In:SecurityandPrivacyinSocialNetworks(2013)28.
Rivest,R.
:ElectronicLotteryTicketsasMicropayments.
In:FC(1997)29.
Ron,D.
,Shamir,A.
:QuantitativeAnalysisoftheFullBitcoinTransactionGraph.
FC(2012)30.
Sako,K.
,Kilian,J.
:Receipt-FreeMix-TypeVotingScheme-APracticalSolutiontotheImplementationofaVotingBooth.
In:EUROCRYPT(1995)31.
Sander,T.
:EcientAccumulatorsWithoutTrapdoor.
In:ICICS(1999)32.
Serjantov,A.
,Dingledine,R.
,Syverson,P.
:Fromatrickletoaood:Activeattacksonseveralmixtypes.
In:InformationHiding(2003)AContinualmixingAmorein-depthdefenseagainstsomeoftheside-channelattacksintroducedinSection7.
7iscontinualmixing,whichdoesnotrequireadvancenoticeofpayments.
Inadditiontoavoidingthetimingsidechannel,itactuallyincreasesAlice'sanonymityset.
ThecoreideaisthatAlicecontinuesmixinghercoinsuntilsheisreadytospendthem,butatagreatlyreducedrate(e.
g.
,oneroundpermonth).
LetAbeatimeperiodsuchthatAliceispreparedtokeephercoinsfortimeAbetweenreceivingthemandspendingthem.
Thenthecontinualmixingalgorithmforachunkcforwhichinitialmixingcompletesattimet0isasfollows:generateA,c=U[0,A]mixcattimeA,candthereafteratAintervalsmarkcasspendableaftertherstcontinualmixroundItiseasytoverifythatregardlessofthetimingsofthepaymentsreceivedbyAlice,thedistributionlastmixingtimesforeachofherspendablechunksisalwaysU[0,A].
Thisnulliesthetimingchannel,exceptforthematterofpickingA.
IfAlicemakesapaymentwitharandomsubsetofherspendablechunks,EvecaninferAwithhighaccuracy.
Pickinginvolvesatrade-o.
Fromthepointofviewofabusiness,ifistoohigh,itaddslatencytotheoperatingcycleanddecreasescashow.
Ifistoolow,itleadstoahigherdepreciationrateoflong-termassetsduetothemixingfeesincurredbycontinualmixing.
Further,clientsmustconsidereachothers'choicesinpicking,sinceanonymitylovescompanyandhighlyunusualvaluesofwillhelpEve.
Giventheseconstraints,weproposeseveralgloballyxedvaluesof:forinstance,aday,aweek,amonth,andaquarter;eachclientisfreetopickthevaluethatbestsuitstheiroperatingpatterns.
AlicecannowexpectheranonymitysettobethesetofallMixcoinclientswhohavethesamevalueof.
22Someinferenceattacksarehardtopreventwithanymixingsystem.
Forexample,ifAliceowesBobahighlyuniqueamountofmoney,andneitherAlicenorBobtransactswithanyotherusers,thisinformationissucienttolinkAlice'soutowwithBob'sinow.
Unlikelyassuchsituationsareformostusersintherealworld,theyposeaproblemforanalysisofanonymityofoursystem.
BImprovingmixtrustworthinessIfamixcheats,thecheatedclientcanensurethatthemixgetsapoorreputation.
ButhowcanamixbuildareputationfortrustworthinessEveniftherearenotheftreportsagainstit,itmightsimplybebecausethemixdoesn'thavemuchvolumeyet.
Further,totheextentthatmorepopularmixesmayoerbetteranonymity(Section7.
3),clientswouldliketoestimatemixtransactionvolumes.
Inthissectionwediscusswaystobettermeasure,aswellasprove,mixtrust-worthiness,andevenamechanismforrecourseagainstcheatingmixes.
Theseareall"out-of-band"anddonotrequiremodicationstotheMixcoinprotocol.
B.
1ExternalreputationWhilesomemixoperatorsmaychoosetobeanonymous,othersmaybecomfort-ablerevealingtheirreal-worldidentity.
Abankortrustedcommunitymembercouldleveragetheirexternalreputationtoincreasetrustintheirmixservice.
B.
2ThrottlingThrottling,orratelimitingbytheclient,letsAlicelimitherexposuretoagivenmixatanygiventime.
IfAlicewantshermaximumexposuretoMtobeE,shetransactswithMattheaveragerateofEδmaxperblock,whereδmaxisthemaximummixdelaythatshepicksforM.
IfshestopstransactingwithMassoonasshedetectsmisbehavior,thenMcanstealatmostEofhercoins.
B.
3AggregatingtheftreportsEssentialtothesuccessofMixcoinisanexternalmechanismforclientsoftwaretoreporttheftbymixes.
Thesereportswillbeaggregatedandre-distributedtoclients.
Sinceitisimpossibletofalselyallegetheft,thismechanismneednotbetrusted.
Further,thisaggregatorcouldcombinetheftreportdatawithestimatesofmixvolumestopublishmixreputationlists.
B.
4UserreportsToestimatevolume,clientuserscouldpublishthroughout-of-bandchannels,suchasforums,logscontainingaggregatestatisticsabouttheirusageofvariousmixes(e.
g.
,"Alicemixed10,000chunksthroughmixM1inAugust").
Ifthesearereputablemembersofthecommunity(forexample,withlongstandingactiveaccounts),observerscanbereasonablycondentthattheyarenotsybils.
Suchreportsprovidelowerboundsonmixvolume.
23B.
5MarkandrecaptureThemark-and-recapturemethodforestimatingwildlifepopulations(e.
g.
,[16])couldbeusedtoestimateamix'sescrowreservesandhenceitsvolume.
Themethodinvolvesengagingthemixinntransactionsoverashortperiod,andobservingwhatfractionofthesegetforwardedamongthesetofcorrespondingreturntransactions.
IfthetransactionvolumeofthemixisQ,thenatanytimetheescrowpoolcontainsQtransactions,andtheexpectednumberofcorrespond-ingreturnsisapproximatelyn/QwhennismuchsmallerthanQ.
Themixmayattempttoinatethismeasurementbysimulatingtransactionsofsybilclientsandcontributingitsownfundstotheescrowpool.
Todefeatsybildetectionbytransactingwithothermixeswouldincurfeesproportionaltotheinatedvol-ume.
Thus,toinatetheapparentvolumetotwicetheactualamount,themixwouldhavetoforegoitsentireprots.
Amorerigorousversionofthisisforareputableentity,suchasConsumerReports,toperformasurveyofpubliclyknownmixesbyperiodicallycarry-ingoutsmalltransactionsandreporttheresults.
Thesuccessofthisapproachdependsonthe(network-level)anonymityofthesurveyor'sactions.
33B.
6FidelitybondsAswediscussedinSection6,onceamixsteadystate,itisrationaltostayinbusiness.
Bootstrappingtrustisachallengefornew,unknownmixservicewithmanyparallelsinbusinessandinlife.
Infact,theearliestmodernbanksfacedtheissueofgettingclientstoentrusttheirmoney.
Howcouldclientsbesurethebankwouldn'tdisappearovernightThebankssolvedthisproblembysignalingwithhuge,expensivebuildingswithgleamingfacadesthattheywereinitforthelonghaul.
34Eortandmoneyexpendedbytheoperatorofanewmixinadvertisingtheservicecouldserveassuchacostlysignal.
ButBitcoinalsohasamechanismforexplicitsignaling:delitybonds.
Somewhatdierentfromreal-worlddelitybonds,BitcoindelitybondsareaprotocolfortheownerofaBitcoinaddresstosacricecoins,i.
e.
,makethemprovablyunspendable.
Weenvisionthatmixesmightoptionallyputupadelitybondtogaintrustinitially.
Onepossiblegame-theoreticexplanationforwhysignalingbybanksworked,andwhydelitybondsbymixesmightwork,involvesasymmetricinformation.
Let'ssayabusiness(abankormix)hasdonetheresearchandconcludedthatthemarketisripeforanewentrant.
Itthereforesetsupshopwithhonestintentions.
Butconsiderclientswhotypicallydonothaveaccesstothismarketresearchorotherreasonsforthebusiness'sbeliefinitslong-termviability.
To33Asanaside,anonymityisanissueforsurveyorganizationsinphysical-worldtrans-actionsaswell.
Consumerreportshadapolicyofpurchasingvehicleswithcashtoprotecttheiridentity,buthadtoabandonthepracticewhencardealersrealizedthattheyweretheonlyentitytopaywithcash.
34Otherexamplesofcostlyactionsundertakenforthepurposeofsignalingcommitmentareganginitiationsandengagementrings.
24suchaclient,thebusinessmayverywellhavetheintentionofneverreachingthesteadystate,butinsteadabscondingassoonasafewtentativeclientsentrustthemwithmoneymoney.
Byundertakingacostlyaction,thebusinesssignalsitsbeliefthatitcanbeviable.
Sincethesunkcostexceedswhatthebusinessmightgainbyabscondingbeforereachingthesteadystate,abusinessthatdoesnotbelieveinitsownviabilitywillnotundertakethecostlyaction.
ViaaBayesianargument,theclientcaninferthatthebusinessdoesnotintendtoabscond.
CManipulatingthebeacongeneratedbytheblockchainInSection4.
4,weassumedthatvaluesintheblockchainareunpredictableforbothAliceandthemix,andthereforecanbesafelyusedtodeterminewhichtransactionsthemixisabletoretainasafee.
Inreality,themixmightalsocontrolsignicantminingresourcesandthereforeattempttoinuencethevalueofblocksinthechaintocollectahighereectivemixingfeeratethanρ.
Thisattackfacestwomajordiculties.
First,itisverycostlytoinuenceblocks.
Becausethevalueofblockhashesistheoutputofaproof-of-workscheme,theonlyeectivemeansforinuencingtheirvalueistodiscardsomevalidblockswhichMndsinhopesofndinganalternateblockwhichincreasesthenum-berofmixingfeesMcollects.
Discardingotherwisevalidblocksmakestheat-tackveryexpensive,giventhehighvalueofminedblocks(currentlyaroundUS$20,000)andexpenseofcomputingthem.
Second,evengiventheabilitytodiscardsomeblocksinthehopeofndingablockwhichallowsMtocollectahighermixingfeethanusual,itisdiculttondablockwhichwillsignicantlyincreasethenumberofmixingfeesretained.
AssumingthemixisholdingQtransactionsandisabletochoosefromasmallnumbernofpotentialblocks,eachpotentialblockenablesthemixtoretainanindependentlyrandomsubsetoftheQtransactionswithprobabilityρeach.
ThenumberoftransactionsretainedisthereforeamultinomialdistributionwithexpectedvalueρQandvarianceQ(1ρ)ρ.
UnderreasonableassumptionsforQandρ,forexampleQ=100andρ=2%,evengenerating1000validblocks(whichwouldbeabsurdlyexpensivecomputationally)produceslessthana40%chanceofndingablockwhichevendoublesthemix'sfeerate.
DGrowthinanonymityagainstastrongattackerAsclaimedinSection7.
3,evenagainstanattackerabletoidentifywhichmixescorrespondtoescrowaddressesintheblockchaintheprobabilitydistributionovertheanonymitysetofachunkrapidlyapproachestheuniformdistributionaftermultipleroundsofmixing.
Assumethattherearemmixes,andQchunksarebeingmixedinNconcurrent,synchronousrounds.
Inotherwords,ineachround,eachchunkisassignedtoagivenmix,anditsanonymitysetforthatroundisthesetofallotherchunksassignedtothatmixinthatround.
Wecanquantifythisbymeasuringthestatisticaldistance(L1distance)fromtheuniformdistribution.
Figure1summarizestheresultsofsimulation.
25Fig.
1.
Simulation.
Statisticaldistance(L1distance)betweenPDFofachunk'sanonymitysetandtheuniformdistribution,asafunctionofthenumberofrounds.
Q=1000chunksinallexperiments.
Therstlineshowsm=100mixes,witheachmixbeingequallypopular(i.
e.
,ineachround,eachchunkisindependentlyequallylikelytobesenttoeachmix).
WeobservethatthestatisticaldistanceofthePDFfromuniformdropsexponentiallywiththenumberofrounds.
After7roundsitisunder0.
1,andafter10roundsitisabout2.
4·104.
Theotherlinesshowthesituationwhenthemixtracisskewedaccordingtoapowerlawdistribution,i.
e.
,ineachround,eachchunkisindependentlysenttomixiwithprobabilityproportionalto1i.
Herethedistributionconvergestouniformevenfaster.
Decreasingthenumberofmixeshasasimilareect.
Thesearebothillustrationsofthefactthatanonymitylovescompany.
Thedegreeofanonymity[11]convergesto1similarly.
With100mixeswithpower-lawtrac,after4roundsitexceeds0.
99andafter10roundsitisabout12·109.
Whilethisisasimpliedmodel,wecaninferalotabouttheanonymitypropertiesofMixcoin.
Qualitatively,afterafewroundsAlice'schunkisuniformlymixedwithalltheotherchunksthatarebeingmixedcontemporaneously.
Thechunk'sanonymitysetdoesnotincludechunksthatweremixedatadierenttime,forexampleamonthago.
Iftheattackerhascompromisedsomeofthemixes,aslongassomeoftheroundsofmixing(sayN)wentthroughhonestmixes,theanonymitypropertiesareidenticaltousingNroundsofmixingwithallhonestmixes.