Permissionless Consensus in the Resource Model
Permissionless Consensus in the Resource Model
复制标题
资源模型中的无许可共识
DOI：
10.1007/978-3-031-18283-9_29
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Ben Terner
中科院分区：
文献类型：
--
作者：
Ben Terner
.中本聪的比特币协议激发了人们对分布式计算的无许可制度的兴趣，在这种制度中，参与者可以随意加入和离开互联网规模的协议执行，而不需要向任何权威机构注册。无许可机制对共识协议中使用的经典技术提出了挑战，在共识协议中，参与者试图就其输入的函数达成一致。至关重要的是，经典的共识技术要求诚实的参与者保持在线和活跃，并知道参与者数量的上限。比特币通过要求工作量证明来解决这个问题，以便在协议中发送消息，其他受比特币启发的作品已经开发了X证明变体来弥补工作量证明的缺点。我们提出了一个称为资源的X证明的抽象，其灵感来自于实践中使用了多少变体。然后，我们表明，只要有一些额外的假设，资源是足够的，以实现共识的许可制度。特别是，通过对资源的适当假设，不需要知道网络延迟的界限，参与者不需要时钟，并且参与者可以任意加入和离开执行。核心思想是将焦点从执行中诚实方的比例转移到诚实方发送的消息的比例。我们正式模型的共识协议的许可制度，并展示了如何参数化的许可执行只使用诚实的参与者获得的资源的长期比例和上限的资源进入系统的速率，相对于最大的网络延迟（不需要知道网络延迟）。沿着这条路，我们提供了一个区块链的广义定义，我们称之为图共识。我们提出了一个协议，在不允许的制度，实现图的共识，即使当资源进入系统以高速率，但所需的诚实的多数增加的速度。我们展示了如何稍微修改协议以实现一位共识。最后，我们证明了对于每个输出大多数诚实顶点的图共识协议，存在一个1位共识协议。
. Nakamoto’s Bitcoin protocol inspired interest in the permissionless regime of distributed computing, in which participants may join and leave an internet-scale protocol execution at will, without needing to register with any authority. The permissionless regime poses challenges to the classical techniques used for consensus protocols, in which participants attempt to agree on a function of their inputs. Crucially, classical consensus techniques require honest participants to remain online and active, and to know an upperbound on the number of participants. Bitcoin addresses this issue by requiring Proof of Work in order to send a message in protocol, and other Bitcoin-inspired works have developed Proof of X variants to remediate the shortcomings of Proof of Work. We propose an abstraction for Proof of X called resources , inspired by how many variants are used in practice. We then show that given few additional assumptions, resources are sufficient to achieve consensus in the permissionless regime. In particular, with appropriate assumptions about resources, it is not necessary to know a bound on the network delay, participants do not need clocks, and participants can join and leave the execution arbitrarily. The core idea is to shift focus from the proportion of honest parties in an execution to the proportion of messages sent by honest parties. We formally model consensus protocols in the permissionless regime, and show how to parameterize a permissionless execution using only the long-term proportion of resources acquired by honest participants and an upperbound on the rate at which resources enter the system, relative to the maximum network delay (without needing to know the network delay). Along the way, we provide a generalized definition of blockchains which we call graph consensus. We present a protocol in the permissionless regime that achieves graph consensus, even when resources enter the system at high rates, but the required honest majority increases with the rate. We show how the protocol can be modified slightly to achieve one-bit consensus. Finally, we show that for every graph consensus protocol that outputs a majority of honest vertices there exists a one-bit consensus protocol.