当前位置：文档之家 › From consensus to atomic broadcast Time-free byzantine-resistant protocols without signatur

From consensus to atomic broadcast Time-free byzantine-resistant protocols without signatur

  • 格式：pdf
  • 大小：220.75 KB
  • 文档页数：32

下载文档原格式

  / 32

合集下载

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

FromConsensustoAtomicBroadcast:Time-FreeByzantine-ResistantProtocolswithoutSignatures

MiguelCorreia,NunoFerreiraNeves,PauloVer´ıssimo

DI–FCULTR–05–14

October2005

DepartamentodeInform´aticaFaculdadedeCiˆenciasdaUniversidadedeLisboaCampoGrande,1749–016LisboaPortugal

Technicalreportsareavailableathttp://www.di.fc.ul.pt/tech-reports.ThefilesarestoredinPDF,withthereportnumberasfilename.Alternatively,reportsareavailablebypostfromtheaboveaddress.FromConsensustoAtomicBroadcast:Time-Free

Byzantine-ResistantProtocolswithoutSignatures∗

MIGUELCORREIANUNOFERREIRANEVESPAULOVER´ISSIMO

FaculdadedeCiˆenciasdaUniversidadedeLisboa,CampoGrande,1749-016Lisboa-Portugal

{mpc,nuno,pjv}@di.fc.ul.pt

Keywords:consensus,atomicbroadcast,asynchronoussystems,Byzantinefaults,intrusiontolerance,randomization

Firstpublished:June2004

Revised:October2005

Abstract

ThispaperproposesastackofthreeByzantine-resistantprotocolsaimedtobeusedinpracticaldis-tributedsystems:multi-valuedconsensus,vectorconsensusandatomicbroadcast.Theseprotocolsaredesignedassuccessivetransformationsfromonetoanother.Thefirstprotocol,multi-valuedconsensus,isimplementedontopofarandomizedbinaryconsensusandareliablebroadcastprotocol.Theprotocolsshareasetofimportantstructuralproperties.Firstly,theydonotusedigitalsignaturesconstructedwithpublic-keycryptography,awell-knownperformancebottleneckinthiskindofprotocols.Secondly,theyaretime-free,i.e.,theymakenosynchronyassumptions,sincetheseassumptionsareoftenvulnerabletosubtlebuteffectiveattacks.Thirdly,theyarecompletelydecentralized,thusavoidingthecostofdetectingcorruptleaders.Fourthly,theyhaveoptimalresilience,i.e.,theytoleratef=󰀍n−13󰀎outofatotalofnprocesses.Intermsoftimecomplexity,themulti-valuedconsensusprotocolterminatesinaconstantexpectednumberofrounds,whilethevectorconsensusandatomicbroadcastprotocolshaveO(f)complexity.Thepaperalsoprovestheequivalencebetweenmulti-valuedconsensusandatomicbroadcastintheByzantinefailuremodelwithoutsignatures.Asimilarproofisgivenfortheequivalencebetweenmulti-valuedconsensusandvectorconsensus.Thesetworesultshavetheoreticalrelevancesincetheyshowoncemorethatconsensusisafundamentalproblemindistributedsystems.∗ThisworkwaspartiallysupportedbytheEUthroughprojectCRiticalUTilityInfrastructurALResilience(CRUTIAL),andtheFCTthroughprojectPOSI/EIA/60334/2004(RITAS)andtheLarge-ScaleInformaticSystemsLaboratory(LASIGE).AversionofthispaperwasacceptedforpublicationbyOxfordUniversityPressintheComputerJournal.1Introduction

DistributedprotocolscapableoftoleratingByzantinefaultshavebeenstudiedformorethantwodecades[1,

2,3,4].Recently,interestintheseprotocolshasgainedanewmomentumunderthedesignationofintrusion

tolerance[5].Thebasicideaisthatthesecurityconceptsofattack,intrusionandvulnerabilitycanbeconsidered

asfaults,morepreciselyasarbitraryfaults,alsocalledByzantinefaults.Aconsequenceofthisassertionisthat

Byzantine-resistantprotocolscanbeimportantbuildingblocksfortheconstructionofsecuresystems.

Byzantine-resistant(orintrusion-tolerant)protocolsusuallyhavehighertimeandmessagecomplexities

thancrash-tolerantprotocolsdo.TheyarealsomoreCPU-timedemandingsincetheymustusecryptography1,

andoftenpublic-keycryptography.ThisCPU-timeissueisfrequentlydismissedsincetheprocessingpowerof

computersisconstantlyincreasing.However,newclassesofcomputingenvironmentsareappearinginwhich

resourcesarescarce,e.g.,embeddedsystems.ThisisanimportantmotivationforthedesignoflessCPU-time

consumingintrusion-tolerantprotocols.Moreover,public-keycryptographyoperationscanbeanimportant

bottleneckfortheperformanceofintrusion-tolerantsystemseveninmorepowerfulhardware.Castroand

Liskovdesignedanintrusion-tolerantNFSsystemwhichperformsonaverageonly3%slowerthanstandard

NFS,inpartduetoavoidingtheuseofsignaturesbasedonpublic-keycryptography[6].

AnargumentofthispaperisthatthedesignofefficientByzantine-resistantprotocolsiscrucialforthe

implementationofpracticalintrusion-tolerantsystems,thereforetheseprotocolshavetoavoidasmuchaspos-

sibletheuseofpublic-keycryptography.Moreover,practicalintrusion-tolerantsystemsrequireprotocolswith

othercharacteristics,likestrictasynchrony,optimalresilience,andlowtimecomplexity.Thepaperprovidesa

modularandconsistentfamilyofprotocolswiththeseproperties.

PaperResults.Thepaperpresentsastackofthreemessage-passingByzantine-resistantprotocols:multi-

valuedconsensus,vectorconsensusandatomicbroadcast(seeFigure1).Consensusisadistributedsystems

problemwithboththeoreticalandpracticalinterest.Theproblemcanbestatedthisway:howdoesasetof

distributedprocessesachieveagreementonavaluedespiteanumberofprocessfailures?Thepaperimplements

twoflavorsofconsensus:multi-valuedconsensusthatmakesagreementonvalueswithanarbitrarysize;and

vectorconsensusthatmakesagreementonavectorwiththevaluesproposedbyseveraloftheprocesses.An

atomicbroadcastprotocolisacommunicationprotocolthatdeliversthesamemessagestoallprocessesin

thesameorder.Atomicbroadcastis,forinstance,themaincomponentoffault-tolerantsystemsbasedonthe

state-machineapproach,withbothcrash[7]andByzantinefaults[8,6].Theprotocolsinthepaperdonotsolve

consensusfromscratchbutarebuiltontopofarandomizedbinaryconsensusprotocol(e.g.,[9,10])anda

1Herewearetalkingaboutpracticalsystems.Theoreticallywecanassumeprivatechannelsconnectingtheprocesses,thereforecryptographyisnotanabsoluterequirement.

2