Authenticated Algorithm forByzantine AgreementBy : D. Dolev and H.R. StrongPresented by : Gunjan KhannaMotivationn Presentation on Monday talked aboutByzantine agreement in distributed systemsn Byzantine agreement modeling is importantto model insider threatsn Byzantine Agreement defined can beachieved in (n-1) phases.n No. of processors required to tolerate ffailures are 3f +1Byzantine Agreement isExpensiven Order of Messages are O(nf) with nnodes and f failuresn n-1 rounds leads to a delay inagreementn Authentication does limit the totalnumber of processors to f +2n Total number of messages also dependupon the connectivity of graphSystem Modeln Byzantine behavior for failed nodes.n Interactive Consistency or Unanimityn Byzantine Agreementn (I)All correct processors agree on the samevaluen (II) If sender is correct, all processors agreeon its value.n Aim to prove the lower bound of f+1rounds for any type of messages.System Model Cnt.d.n Assume a completely connected Graphn Reliable Communication Channeln In case of an authentication algorithmn No one can forge the signaturesn Transmitter appends the signature to themessagenLynch and Fisher provided a t+1 bound onthe number of rounds but without anyauthenticated messages.Terms used in Papern Historyn N processor history is a finite sequence of nnode phases and a phase 0n A phase is a directed graph with nodescorresponding to processors and labels onedges.n Label is the information sent by the processorsprqFormal Termsn Subhistoryn History seen by a processor pn Only incoming edges presentn Agreement Algorithmn Class of Historiesn Correctness RuleByzantine Agreementn A processor is correct at phase k according tothe correctness rule it is correct at each ofthe previous phases k-1nCorrectness rule operates on the subhistory ofeach processn Byzantine Agreement can be achievedn (I) If for p and q correct processes FpH = FqH.n (II) If sender is correct and sends a value v thenfor a correct process p FpH = v .Theorem 1nByzantine agreement with authentication canbe achieved for n processors with atmost tfaults in t+1 phases, n>t+1n Proof:n Each node signs the value at phase i and sends itto only the processes who have not signed it yet.n F operates on the messages and throws all theincorrect messages.n After t phases each message has t signatures on itn Hence each correct value has been seen by all thecorrect process after t+1 phases.Theorem 2nByzantine agreement cannot be achieved in t orlower phases with t failures.n Proof:n Let’s assume that Byzantine agreement can beachieved in t or fewer phases.n Let R be the correctness rule and F be thedecision function. Together they achieve theByzantine agreement.n Critical Sequence which contains the incorrectprocesses.n Faulty Processes increase seriallyProof Cnt.dn If FpH’=FpH implies equivalent histories, H and H’n A node is hidden at phase k if there are nooutedges from it in any later phases.n Show by induction that “If a node r representinga processor at phase k of history H in C then,”n There is a history equivalent to H denoted by H’ throughphase k except for outedges of r with r correct and allother processes correctn If all other processes are correct then there exist H’ withoutedges of r replaced, r hidden and all other processesare correct.n Case 1 k=tProof Cnt.dn (a) If r is incorrect at phase k then wecorrect the outedges of r one at a time.n For each individual change there is a processorwhich sees the same history as beforen Final H’ will have r correct and all processestrivially correct.n (b) If r is a process and all other processesare correct then removing outedges of rwill preserve the equivalence relation in H.Proof Cnt.dn Assume (a) and (b) to be true for allphases after kn (i) Let r be the incorrect edge at phase k.n Correct all nodes at phase k hyp. (a)n While the incorrect outedges remainn Replace the position k+1 in C with s which is thetarget of the incorrect outedge.n Hide s at k+1n Correct all nodes hyp. (b)n The final result H’ will have r and all correctprocesses.Proof Cnt.dn (ii) All correct nodes at phase k and rbe a noden Correct nodes at phase k+1 hyp. (a)n Replace kth position with label of r.n While the outedges of r remainn Replace the position k+1 in C with s which is thetarget of the outedge e.n Hide s at k+1 hyb. (b)n remove en Correct all processes after phase k hyp. (a)n Hide r at phase k +1 . Hence the final resultwill have r hidden at phase k and all otherprocessors correct after phase k.Algorithms using Authenticationn A label is a sequence of authenticationor just a single authentication.n (Label a)pn No process can alter the authenticationnor can it pretend to have received anauthentication.n Main idea is to restrict the no. ofmessages.Theorem 3nByzantine agreement can be reached with t failureswithin t+1 rounds with O(e)=O(n2) messagesn Restrict the number of messages from each processor to 2.n Each processor orders the messages lexicographically in theorder (..(v)p1)p2…pn)n It relays the first two messages with distinct valuen Only one message is relayed if values are the samen If two messages are relayed within t+1 phases then it decides“sender fault”n If no other process imports any other value then v isextracted .Theorem 4nByzantine agreement can be reached for nprocesses using t+2 rounds and O(nt)messages when there are t failures totolerate.n Chose t+1 processes to be relay processes.n Non relay processes send messages only to therelay processesn Messages = O(nt)n Why are t+2 phases required ?Theorem 5n Assumptionsnt+1 connected graphnK-Diameter of a graph is the least upperbound of the lengths of the k disjoint pathsnIf d is the diameter of a t+1 connectedgraph then Byzantine agreement can bereached within t+d phases.n Proof : Trivially True from Theorem 1.Theorem 6nByzantine agreement can be reached int+1 phases with O(nt) messages in acomplete network.n Proofn If n<( 2t+1) then it is true from Theorem3.n Use only 2t+1 processes as activen Correctness Rule is same as Theorem 3.n (Lexicographically correct )Algorithm Cnt.dn Passive processes do not send any messagen They collect the signed messages and extractvalues with atleast t+1 distinct signatures.n If any correct active process extracts a valuethen some correct active process extracts thatvalue by phase t and then the message it willrelay will have t+1 active signatures.n It can be extended for the case with t -1phases.Contributionsn Proposes
View Full Document
Unlocking...