Permissionless Consensus Tutorial (7 of 13) скачать в хорошем качестве

Permissionless Consensus Tutorial (7 of 13)

Speaker: Andrew Lewis-Pye (London School of Economics) Coauthor: Tim Roughgarden (Columbia University) Accompanying paper: https://arxiv.org/pdf/2304.14701 Accompanying tweetstorm: https://x.com/Tim_Roughgarden/status/... Abstract: Blockchain protocols such as Bitcoin and Ethereum operate in the “permissionless” setting (as opposed to the “permissioned” setting, as classically studied in distributed computing). The shift from the permissioned to the permissionless setting entails three distinct challenges: The unknown players challenge. The set of distinct entities that might run the protocol is unknown at the time of protocol deployment and is of unknown size. The player inactivity challenge. Such entities can start or stop running the protocol at any time. The sybil challenge. Each such entity can operate the protocol using an unknown and unbounded set of identifiers (a.k.a. “sybils”). These three challenges are logically independent, and every subset of them leads to a distinct and well-defined setting that has its own set of possibility and impossibility results. In this tutorial, we’ll describe a cohesive approach to modeling the three challenges outlined above. In addition to being of theoretical interest, our framework naturally allows one to make formal statements about modern blockchain protocols (e.g., articulating the goals of the Ethereum protocol, rigorously assessing the extent to which the protocol achieves those goals, and investigating whether there could be protocols that “better” achieve them while operating under the same set of constraints). A key aspect of our approach is to establish a "degree of permissonlessness" hierarchy that parameterizes what a protocol may assume about the activity of honest players (in the tradition of the standard parameterizations of fault severity and network reliability). This hierarchy is defined by four settings: the fully permissionless, dynamically available, quasi-permissioness, and permissioned settings. We then focus on possibility and impossibility results separating the various levels of this hierarchy. As an example, we will describe the “Dynamic Availability Dilemma”: an SMR protocol operating in the dynamically available setting cannot satisfy asynchronous safety, and cannot satisfy either accountability or optimistic responsiveness, while protocols operating in the quasi-permissionless setting can (simultaneously) satisfy all three of the latter properties.