Byzantine Generals in the Permissionless Setting
The challenges and solutions faced by Byzantine generals in the permissionless setting, including concepts like Byzantine Broadcast, decentralized protocols, and defense against mobile adversaries. Delve into the theorems and definitions that shape this fascinating field of study.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Byzantine Generals in the Permissionless Setting Andrew Lewis-Pye and Tim Roughgarden Presentation by Joseph Oglio
Background FLP 1 faulty process CAP partitions, consistency, availability DS f + 1 rounds needed for consensus Asynchronous vs. Synchrony vs. Partial-synchrony Authenticated vs. Unauthenticated Resource pool q PoW, PoS, may be limited (sized vs unsized)
The Framework Permitter Oracle decides if message or messages may be broadcast Possible infinite number of processes May receive finite number of messages and send a finite number of messages An external clock and timeslots At most once message delivery
Theorem 3.1. Consider the synchronous setting and suppose q < 1. There exists a (deterministic) PoS protocol solving Byzantine Broadcast for a q- bounded adversary Essentially some set of fixed nodes hold all the stake and make all the decisions (may choose to change who holds the stake)
Definition 3.2. The conditions for a permissionless protocol to be weakly decentralized depend on the setting: In the untimed setting, we require that if non-faulty p receives (m, m ) at t and broadcasts the set of messages m (at t), then m m In the timed setting, we require that if non-faulty p broadcasts m at timeslot t, then t = tm, i.e., m is broadcast at t which is its timestamp Essentially when resources shift so does the power to influence the algorithm meaning byzantine nodes can shuffle around their power
Question 1 Is there some sense in which Definition 3.2 is equivalent to the requirement of being able to defend against certain types of mobile adversary?
Theorem 3.3 Consider the synchronous setting and suppose q (0, 1]. There is no deterministic and weakly decentralized permissionless protocol that solves BB for a q-bounded adversary Centralized solution : One might have a fixed circle of participants carry out each round of BB (involving interactions over multiple timeslots according to a permissioned protocol), only allowing in new participants after the completion of each such round
Question 2 For which q [0, 1) do there exist weakly decentralized protocols giving a probabilistic solution to BB for a q-bounded adversary in the authenticated and synchronous setting? PoW and PoS go 0-1/2 can you do better?
Theorem 3.4 [PS17] Consider the synchronous and unauthenticated setting (with the framework described in Section 2, whereby processors broadcast, rather than communicate by private channels). If q (0, 1], then there is no permissioned protocol giving a probabilistic solution to BB for a q-bounded adversary.
Theorem 3.5 Consider the synchronous and unauthenticated setting. If q 1/2 , then there is no permissionless protocol giving a probabilistic solution to BB for a q-bounded adversary
Theorem 4.1 There is no permissionless protocol giving a probabilistic solution to BB in the unsized setting with partially synchronous communication.
Question 3. What are the results for the timed/untimed, sized/unsized, single/multi-permitter settings other than those used to model PoW and PoS protocols? What happens, for example, when communication is partially synchronous and we consider a variant of PoW protocols for which the total resource balance (see Section 2.3) is determined?
Question 4 What happens in the setting of partially synchronous processors, and to what extent can the techniques of [DLS88] be used to solve this question? How does this depend on whether we are working in the timed/untimed and sized/unsized settings?
Question 5. What happens in the context of a mobile adversary, and how does this depend on whether we are working in the single-permitter or multi-permitter settings? Is this a significant advantage of PoW protocols?
Question 6 How best to modify the framework, so as to model limited bandwidth (and protocols such as those for implementing sharding)?
Question 7 What changes in the context of late joining? In what ways is this different from the partially synchronous setting, and how does this relate to Question 6? How does all of this depend on other aspects of the setting?
Question 8 How should incentives be incorporated into the framework? Does it make sense to do this outside the context of defining state machine replication protocols for running currencies?
