1区块链长延时协议技术研究AnalysisoftheBlockchainProtocolwithLongDelays Nakamoto’sblockchainBitcoinDecentralizedpaymentsystemLedgermaintainedbythepublicinadecentralizedmannerAttractivepropertiesDecentralization,Pseudonymity,Robustness…BlockchainChain-structuredledgermaintainedbyalltheparticipants(miners) Nakamoto’sblockchainBlockchainBasicsecurityrequirementAlltheminersmaintainthesamerecordAchieveconsensusinthepermissionlesssettingB1 B2 B3B1 B2 B3B1 B’2 B’3permissionlessanyonecanjoin(orleave)theprotocolexecution Nakamoto’sblockchainProofofwork(PoW)Solvea“cryptographicpuzzle”BitcoinBackboneProtocol[GKL15]blockchainC=(!",!$,…,!&)block !(=(ℎ(,$,-(,.(,ℎ()ℎ(=/(ℎ(,$||-(|.(,s.t.ℎ(<DH(h|- ? <6h0m1r1Block1h1m2r2Block2 Nakamoto’sblockchainProofofwork(PoW)Integrity:MoredifficultfortheadversarytomodifythechainSynchronism:helpthedistributedminerstosynchronizeSlowdownthegenerationofblocksLongestchainruleH(h|" ? <% Nakamoto’sblockchainCommonprefix Chaingrowth ChainqualitySecurityGaray,KiayiasandLeonardos[GKL15]providearigorousanalysisofblockchainprotocolSynchronousmodelPass,Seemanandshelat[PSS17]analyzethesecurityinanasynchronousnetworkwitha-prioriboundeddelayAsynchronousmodelWhyconsiderthedelay? Blockchainprotocolwithdelays7BitcoinP2PnetworkDelaysareinevitableNewblockThepropagationdelayinthenetworkistheprimarycauseforblockchainforks[DW13]DeckerandWattenhoferInformationpropagationinthebitcoinnetwork(2013) BlockchainprotocolwithdelaysResults[PSS17],0/1Chaingrowth:(,-.)/,where2≈*+Consistency:4withprobability1−*789(4)Chainquality:1−(1+;)<=(,0/1)/Limitation:!≪#(%/'()Theproofholdsforarelativelysmalldelayonly*:thenumberofminers+:theprobabilitythataminersucceedsinminingablockataround!silence !silenceuniquesuccessConvergenceopportunity8Intherealworld, longdelays,say∆≥1/np,couldbecausedeasily!“bad”asynchronousnetworks,equipmentfailure,…maliciousattackseclipseattacks[HKZG15],whichallowanadversarytocontrol32IPaddressestomonopolizeallconnectionstoandfromatargetbitcoinnodewith85%probabilityEclipseattacks[HKZG15]9 Blockchainprotocolwithdelays.IstheblockchainprotocolbasedonPOWstillsecureintheasynchronousnetwork,wherelongdelay,sayΔ≥1/np,isallowed? OurcontributionFocusontheeffectoflongdelay,especiallyΔ≥1/npProvethatthecommonprefixproperty,thechaingrowthpropertyandchainqualitycanstillholdinourmodelwhenconsideringlongdelayRefinethedefinitionsforsecuritySimplifiedproofmethodforPOWbasedblockchain OurblockchainmodelTheadversaryADeliverallmessagessentbyminersDelaythetargetchainswithprobabilityαWithinΔroundsDonothaveanyhashpowerAdversaryNewblockNewblockdelayedα1nextroundwithinΔround1-α012 OurblockchainmodelModificationtoblockchainprotocolConsecutiveblockscannotbeminedbythesameminer(notthesameminingpool)asinglemineranindependentcommunicationnodeofthenetworkhasaunitcomputationalpowerInpracticeitisunlikelythataminercanminetwoconsecutiveblockslargenumberofminersnsmalldifficultyparameterp OurblockchainmodelHonestminerssettingTheadversarydoesnotcorruptanyminers(Nohashpower)OurmodelcapturesaclassofpracticalattacksintherealworldMoredifficulttocontrolasizablefractionofhashingpowerMucheasiertodisruptcommunicationsamongminersPresentaconcreteattackinwhichanadversarywithoutanyhashpowermaythreatenthecommonprefixpropertyTooweak? SecurityrequirementsChainGrowthPreviouswork:theminimumlengthincreaseofallhonestminers’chainsOurwork:thelengthincreaseofthemajorityofhonestminers’chainsmajority!∈($,1]%Excludethe“bad”honestminorityChaingrowthin[PSS17]isaspecialcaseofourswhenλ=1duringTrounds 3 3 31 3 SecurityrequirementsCommonPrefixPreviouswork:Allthehonestminershavethesamehistory(prefix)Ourwork:ThemajorityofthehonestminershavethesamehistoryAllowsomeminers’chainstobeinconsistentwiththemainchain%majority!∈($,1]B1 B2 B3B1 B2 B3B4 B5 B6B4 B5 B6) StateoftheMainChainTreeMCtocapturetheevolutionofthemainchainsInspiredbyFtreemodel[PSS17],recordallthebranches(orforks)TreeMCinourmodelOnlystorethecurrentstateofthemainchainsDelayedchainsarenotrecordedinTreeMCBasicoperations:AddBlock,DeleteBlock!"!#(#)!#(&)&!(#)!#(')&!(&)&!(')&!(()# "# #) =(!,!#,!#)#&)&=(!",!&,!&)#&)'=(!",!',!')#&)(=(!",!',!() DifferencebetweenTreeMCandtheminers’viewEachminerhastheirownview ofthemainchain,whichmaybedifferentwithTreeMCIntermsof chaingrowthand commonprefix,thedifferenceisnegligibleReducedtothesecurityofTreeMCSimpleproofforTreeMCUsefulpropertiesonthedepthofTreeMC Securityproof ChainGrowthMainideaofproof Securityproof CommonPrefixMainideaofproofTheeventconvergeOnlyoneminersucceedsinminingatroundr∗.C∗isdelayablewhilethereisnonewblockminedinfollowingΔroundsORThechainC∗isundelayablePr $%&'()*( >1−./(1+2Δ)ForTreeMCwithcommonprefixofdepthd-T1− ./1+2Δ5 LongDelayAttackonCommonPrefixConcreteattackonthecommonprefixofTreeMCwhenΔandαare“too”largerelativetoafixedTGoalofattack:increasethelengthofthetwobranchesbyT LongDelayAttackonCommonPrefixWithinappropriateparameters,adversarieswithoutanyhashpowercanthreatenthecommon prefixpropertyForα=0.8andT=6,thesuccessprobabilityincreasesasΔgetslarger.thesuccessprobabilitygrowsmuchfasterwhenΔ>60(10min).WhenΔ>120(20min),thesuccessprobabilitycanreachabout1%.Corruptedminersetting? CorruptedminersettingTheadversarycancorruptsomeminersandhavecertainfractionofthetotalcomputationalpowerCommonprefixChaingrowthChainquality SecurityproofincorruptedminerssettingChaingrowthCommonprefixChainqualityConsecutiveblockscannotbeminedbythesameminer SecurityproofincorruptedminerssettingMainideaprovethattherateofminingbycorruptedminersisslowerthantherateofconvergewithoverwhelmingprobability Publications PuwenWei,QuanYuanandYuliangZheng.Securityoftheblockchainagainstlongdelayattack.In:AdvancesinCryptology–ASIACRYPT2018.QuanYuan,PuwenWei,KetingJiaandHaiyangXue.Analysisoftheblockchainprotocolagainststaticadversarialminerscorruptedbylongdelayattackers.In:SCIENCECHINAInformationSciences,2019(accepted)Thanks!谢谢聆听