Hashcash -A Denial of Service Counter-Measure

1 Hashcash - A Denial mechanismtothrottlesystematicabuseofun-m eteredinternetresourcessuchasemail,andan onymousremailersinMay1997. Five yearson,thispapercapturesinoneplacetheva riousapplications,improvementssuggesteda ndrelatedsubsequentpublications, anddescribesinitialexperience tokenwhichcanbeusedasa proof-of-work. Interactive andnon-interactive variantsofcost-functionscanbeconstructed whichcanbeusedinsituationswheretheserver canissuea challenge(connectionorientedinteractive protocol),andwhereit cannot(wherethecommunicationis store and forward,orpacket oriented) : Hashcash , cost-functions1 IntroductionHashcash[1] wasoriginallyproposedasa mechanismtothrottlesystematicabuseofun-m eteredinternetresourcessuchasemail,andan onymousremailersinMay1997.

2 Five yearson,thispapercapturesinoneplacetheva riousapplications,improvementssuggesteda ndrelatedsubsequentpublications,anddescr ibes initialexperiencefromex-periments tokenwhichcanbeusedasa andnon-interactive variantsofcost-functionscanbeconstructed whichcanbeusedinsituationswheretheserver canissuea challenge (connectionoriented interactive protocol),andwhereit cannot(where thecommunicationis store and forward, orpacket oriented) [1] theauthorwasnotawareofthepriorworkbyDwor kandNaorin[2] whoproposeda CPUpricing functionfortheapplicationofcombatting forcost-functionshave beenfurtherdiscussedbyJuelsandBrainardin [3].

3 JakobssonandJuelsproposea dualpurposefortheworkspentina cost-function:toinadditionperformanother wiseusefulcomputationin[4].2 Cost-FunctionsAcost-functionshouldbeeffi cientlyverifiable,butparameterisablyexpe nsive usethefollowingnotationtodefinea ofcost-functionsweuseclienttorefertotheu serwhomustcomputeatoken(denoted ) usingacost-functionMINT()whichis usedtocreatetokenstoparticipateina protocolwithaserver. We (), andonlyproceedwiththeprotocolif ofwork thattheuserwillhave , theserverissuesa challenge totheclient theserverusestheCHAL functiontocompute thechallenge.

4 (Thechallengefunction is alsoparameterisedbytheworkfactor.)1 CHAL serverchallenge function MINT minttokenbasedonchallenge VALUE tokenevaluationfunctionWithnon-interacti vecost-functionstheclientchosesit s ownchallenge orrandomstartvalueintheMINT()func-tion,a ndthereis noCHAL()function. MINT minttoken VALUE tokenevaluationfunctionClearlyanon-inter activecost-functioncanbeusedinaninteract ive setting,whereas theconverseis ,ProbabilisticCost Apubliclyauditablecost-functioncanbeeffi cientlyverifiedbyany thirdpartywithoutaccesstoany trapdoororsecretinformation.

5 (Whenwesaypubliclyauditablewemeanimplici tlythatthecost-functionisefficientlypubl iclyauditablecomparedtothecostofmintingt hetoken,ratherthanauditableintheweakerse nsethattheauditorcouldrepeat theworkdonebytheclient.) Afixedcostcost-functiontakesa fixedcosttokenis a deterministicalgorithm. Aprobabilisticcostcost-functionis onewherethecostto theclientofmintinga tokenhasa predictableexpectedtime,but a randomactualtimeastheclientcanmosteffici entlycomputethecost-functionbystartingat a aretwo typesofprobabilisticcostboundedprobabili sticcostandunboundedprobabilisticcost.

6 Anunboundedprobabilisticcostcost-functio n,canintheorytake forevertocompute,though theproba-blityoftakingsignificantlylonge rthanexpecteddecreasesrapidlytowardszero . (Anexamplewouldbethecost-functionofbeing requiredtothrowa headwitha faircoin;intheorytheusercouldbeunluckyan dendupthrowingmany tails,butinpracticetheprobabilityofnotth rowinga headfor throwstendstowards rapidlyas "!# %$& (' .) Withaboundedprobabilisticcostcost-functi onthereisa limittohowunlucky theclientcanbeinit ssearchforthesolution;forexamplewherethe clientis expectedtosearchsomekey spacefora knownsolution;thesizeofthekey spaceimposesanupperbound thatthechallengercancheaplycreatetokens ofarbitrary a conflictofinterests,forexample inwebhitmetering, wheretheservermayhave aninteresttoinflatethenumberofhitsonit s pagewhereit is beingpaidperhitbyanadvertiser.)

7 Atrapdoor-freecost-functionis onewheretheserverhasnoadvantage trapdoor-freecost-functionis theHashcash[1] s client-puzzlecost-functionis areinaddition notpubliclyauditable,though thisis duetoa storageoptimiza-tionandnotinherent a non-interactive, publiclyauditable, : considerbitstring '*) + -,/.10, wedefine2 354tomeans thebitat offseti, where2 3$is theleft-most bit,and2 376896is -3 4;:<:<:=meansthebit-wisesubstringbetweenandincludingbits>and?,2 -345:<:<:='2 -34A@ BCB BD@2 -3=. So '2 -3$:<:< definea binaryinfixcomparisonoperatorEFHGJI'LKwh ereb is thelengthofthecommon left-substring 'PORQ2M3$TS'2Q3$MEFHGNI'KQU4CV$:<:<:K2M3 4'2Q3 4 Hashcashis computedrelative toa Service -name , topreventtokensmintedforoneserverbeingus edonanother(servers onlyaccepttokens mintedusingtheirownservice-name).

8 Theservice-namecanbeany bit-stringwhichuniquelyidentifiestheserv ice(eg. hostname,emailaddress,etc).Thehashcashfu nction is definedas(notethisis animprovedsimplifedvariantsinceinitialpu blicationseenoteinsection5: WWWWWWW WWWWWWW PUBLIC:hashfunctionXP Y withoutput size bits MINT Z findM []\) + -,/.^0stX_ @M EFHGNI'_` return M VALUE X_ @M aEFHGNI'_b returncThehashcashcost-functionis basedonfindingpartialhashcollisionsonthe all0 bits -bitstring . astheclientcansafelychoosehisownrandomch allenge, , becauseanyonecanefficientlyverifyany publishedtokens.

9 (InpracticedMdshouldbechosentobelarge enough tomake theprobabilitythatclientsreusea previouslyusedstartvaluenegligible;dMd', %e/fbitsshouldbeenoughevenfora busyserver.)Theserverneedstokeepa doublespendingdatabaseofspenttokens, preventthedatabasegrowing indefinitely, theservicestringcaninclude thetimeat whichit have period shouldbechosentotake accountofclockinaccuracy, computationtime, counter-measureagainstemailspam,andagain stsystematicabuseofanonymous is necessarytousenon-interactivecost-functi onsforthesescenarios asthereis nochannelfortheservertosenda challenge over.

10 Howeveroneadvantageofinteractivecost-fun ctionsisthatit ,if thereis a costassociatedwithsendingeachemailthisma ybesufficienttolimitthescaleofemailabuse perpetratedbyspammers;howeverfora pure DoS-motivatedattackadeterminedadversary mayspenda yearpre-computing tokens toallbevalidonthesameday, wouldbepossibletoreduce thescopeforsuchpre-computationattacksbyu singa slowlychangingbeacon(unpredictablebroadc astauthenticatedvalue changingovertime) included inthestartstring,limitingpre-computation attackstobeingconductedwithinthetimeperi od betweenbeacon HashcashWiththeinteractive formofhashcash,foruseininteractive settingssuchasTCP, TLS,SSH,IPSEC etcconnectionestablishmenta challenge is chosenbytheserver.