Communication Complexity in Byzantine Agreement Research
The presentation discusses communication complexity in Byzantine Agreement, emphasizing a lower bound of (f/2) when After the Fact removal is considered. It explores two major contributions - the communication lower bound in randomized protocols and near-optimal subquadratic Byzantine Agreement. The concept of After the Fact removal is explained, along with scenarios involving adversaries corrupting nodes. The research disallows After the Fact removal and relies on cryptographic and setup assumptions, incorporating verifiable randomness and a memory-eraser model. The algorithm basics involve random leader selection, node voting, and memory-eraser model to prevent adversary advantage.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Authors: Ittai Abraham T-H. Hubert Chan Danny Dolev Kartik Nayak Rafael Pass, Ling Ren, and Elaine Shi Presenter: Kendric Hood Communication Complexity of Byzantine Agreement, Revisited
Two Major Contributions 1. There is a communication lower bound of (f2) when After the Fact removal is present (in randomized protocals) 2. Near-Optimal subquadratic Byzantine Agreement
After the fact removal After the fact removal is when an honest Node A sends a messages in round R Then in R+1 A is corrupted, and can remove it s message from round R and even replace it with a different message.
There is a communication lower bound of (f2) This works in a Byzantine Broadcast setting One Node (the sender) Receives a bit [1,0] and then must propagate this bit to all other nodes in the network. All honest nodes should output the same bit
There is a communication lower bound of (f2) cont. Suppose there are two adversaries A1and A2.A1 corrupts a set V of Nodes such that V = F/2. These Nodes preform honestly except They ignore the first f/2 messages they receive 1. They will never send a messages to another Node in V 2. All other Nodes are honest and in set U including the sender
Adversaries A2 If (f/2)2 messages are sent to V then at lest one node (P) in V must have gotten f/2 messages. A2 simply corrupts these nodes (for a total of F Byzantine nodes) and prevents them from sending to P. Now assume all of the above but the input bit is 0 and if an honest node does not receive any input it will output 1, thus all nodes expect P will output 0 and P will output 1
Near-Optimal subquadratic Byzantine Agreement The Authors disallow after the fact removal and rely on cryptographic and setup assumptions The authors also use verifiable randomness and a memory- eraser model.
Basics of the algorithm A node is selected at random to be the leader (via mining to propose) Then log(k) (where k is a security parameter) nodes are selected to vote on the purposed value. With memory-eraser model disallowing after the fact removal Randomness An adversary gains no advantage in corrupting a node that has already voted and can not predict which nodes will vote for the next purposed value. Thus they are reduced to guessing.
