Byzantine Fault Tolerance.pptx

ByzantineFaultToleranceEleanorBirrellNovember23,2010xySIG(x,i)SIG(y,i)SIG(x,i)SKAAuthenticatedMessagesDigitalSignaturesPublic-KeyInefficientMessageAuthenticationCodes(MAC)Secret-Key3ordersofmagnitudefasterVERSKAM,MSKAMSKA,PKAb{yes,no}SIGRSA(M,SKA)=f(M)SKAmodnSIGSIGSHA(M,SKA)=SHA(SKA||SHA(SKA||f(M)))AuthenticatorsMACscannotbeauthenticatedbyathirdpartySolution:createvectorofMACs(calledauthenticator)withonecodeforeachnodeVerificationO(1)butgenerationO(n)SKAVERSKAM,MSKAMSKA,b{yes,no}SIGAUTH(M,SKA1,…,SKAn) =(SIGSHA(M,SKA1),…,SIGSHA(M,SKAn))SIGByzantineFaultTolerance(Results)(m=traitors,n=total)SynchronousSemi-SyncAsynchronousOralMessages:NegativePositiveAuthenticated:NegativePositiveByzantineFaultTolerance(Results)(m=traitors,n=total)SynchronousSemi-SyncAsynchronousOralMessages:Negativen≤3m[LSP80]m≥1[FLP82]Positiven≥3m+1[LSP80]Authenticated:Negativem≥1[FLP82]Positiven≥1[LSP80]n≥3m+1[CL99]ByzantineFaultTolerance(Results)(m=traitors,n=total)SynchronousSemi-SyncAsynchronousOralMessages:Negativen≤3m[LSP80]m≥1[FLP82]Positiven≥3m+1[LSP80]Authenticated:Negativem≥1[FLP82]Positiven≥1[LSP80]n≥3m+1[CL99]???,,(1982)LeslieLamportPhDBrandeis1972(Math)SRI,paq,MSRClocks,Paxos,LaTexRobertShostakPhDHarvard1974SRI,Ansa(Paradox),Portera,VoceraMarshallPeaseSRIInternationalARByzantineGeneralsProblemModel: v(i){Attack,Retreat}Goals:AgreeonplanAgreeongoodplanInteractiveconsistencyconditions(ICCs): Commandinggeneralisends vj(i):,(i)sholdforalliSimplerModel:. v(i){Attack,Retreat}Goals:Agreeoni’sopinionAgreeonrightopinion