practical byzantine fault tolerance - cs.berkeley.edu.ppt

Practical Byzantine Fault ToleranceMiguel Castro and Barbara LiskovMITPresented to cs294-4 by Owen CooperThe problem?Provide a reliable answer to putation even in the presence of Byzantine faults. ?A client would like to?Transmit a request?Wait for k replies?Conclude that the answer is a true answerThe works are unreliable?Can delay, reorder, drop,retransmit?Some fraction of nodes are unreliable?May behave in any way, and need not follow the protocol.?Nodes can verify the authenticity of messages Failures?The system requires 3f+1 nodes to withstand f failures?All f nodes may be faulty, and not respond?But there is no guarantee that the remaining n-f are good, and good nodes must outnumber bad nodes. ?This holds if n-2f > f or n > 3fNodes?Maintain a state ?Log?View number?state?Can perform a set of operations ?Need not be simple read/write?Must be deterministic?Well behaved nodes must:?start at the same state?Execute requests in the same order Views?Operations occur within views?For a given view, a particular node in is designated the primary node, and the others are backup nodes?Primary = v mod n?N is number of nodes?V is the view numberProtocolA three phase protocol?Pre-prepare: primary proposes an order ?Prepare: Backup copies agree on # ?Commit: agree mitAgreement?Quorum based?2f+1 nodes must have same value ?System has 3f+1 nodes?Any 2f+1 subset has >= 1 good node mon?Good nodes don’t lie?Same decision at each node w/ quorumMessages ?The following messages are used by the protocol, and are signed by the sender?Request <o,t,c> (called m)?Sent from the client to the primary?Contains: client #, timestamp, and operation?Reply <v,t,c,I,r>?Pre-prepare <v,d,n>, m?Multicast from primary to backups?Contains view #, sequence #, digest?Message may be sent separatelyMessages 2?Prepare <v,n,d,I >?Sent amongst backups ?Commit <v,n,d,I >?Replica I is prepared mit seq # n, view v?Messages are accepted in each phase ?If the current node is in view v?The sequence number,n, is