论文标题
关于区块链设计的渐近标准：异步组成模型
On an Asymptotic Criterion for Blockchain Design: The Asynchronous Composition Model
论文作者
论文摘要
受区块链的启发，我们引入了一个动态生长的有向无环图（DAG）的动态增长模型，称为异步组成模型，但遵守I.I.D.随机延迟$（ξ_t）$具有有限的均值。根据构造功能$ f $，将时间$ t $的新顶点$ t $连接到从图$ g _ {（t-ξ_t）_+} $中选择的顶点，并通过与图形$ g_ {t-1} $结合来更新图形。此过程对应于在区块链中添加新区块，由于网络通信而出现延迟。感兴趣的主要问题是图表序列的异步极限的末端结构，随着时间的增加到无穷大。 我们考虑了以下感兴趣的构造功能，a）中瘤构造$ f _ {\ mathrm {nak}} $，其中从根部最远的顶点中均匀地选择了一个顶点，从而导致一棵树，b）构建功能的混合物$（f_k）总共选择了少于$ k $），而无需更换。分析背后的主要思想是将时间延迟过程从DAG过程中解开，并在时间延迟过程中构建适当的再生结构，从而引起了马尔可夫行为，以实现DAG过程的功能。我们确定$ f_ \ mathrm {nak}的异步极限，（f_k）_ {k \ ge 2} $，任何非平凡的混合物$ f $都是单端的，而$ f_1 $的异步极限几乎是无限的，几乎是无限的。我们还研究了$ f_ \ mathrm {nak} $的图序列最长路径的基本增长特性。此外，我们证明了选择$ f_1 $的（时间和样本依赖性）概率的相变，使异步极限具有一个或无限的多端。最后，我们证明构建$ f_ \ infty $是$（f_k）_k $的适当限制。
Inspired by blockchains, we introduce a dynamically growing model of rooted Directed Acyclic Graphs (DAGs) referred to as the asynchronous composition model, subject to i.i.d. random delays $(ξ_t)$ with finite mean. The new vertex at time $t$ is connected to vertices chosen from the graph $G_{(t-ξ_t)_+}$ according to a construction function $f$ and the graph is updated by taking union with the graph $G_{t-1}$. This process corresponds to adding new blocks in a blockchain, where the delays arise due to network communication. The main question of interest is the end structure of the asynchronous limit of the graph sequence as time increases to infinity. We consider the following construction functions of interest, a) Nakamoto construction $f_{\mathrm{Nak}}$, in which a vertex is uniformly selected from those furthest from the root, resulting in a tree, and b) mixture of construction functions $(f_k)_{1\le k\le \infty}$, where in $f_k$ a random set of $k$ leaves (all if there are less than $k$ in total) is chosen without replacement. The main idea behind the analysis is decoupling the time-delay process from the DAG process and constructing an appropriate regenerative structure in the time-delay process giving rise to Markovian behavior for a functional of the DAG process. We establish that the asynchronous limits for $f_\mathrm{Nak}, (f_k)_{k \ge 2}$, and any non-trivial mixture $f$ are one-ended, while the asynchronous limit for $f_1$ has infinitely many ends, almost surely. We also study fundamental growth properties of the longest path for the sequence of graphs for $f_\mathrm{Nak}$. In addition, we prove a phase transition on the (time and sample-path dependent) probability of choosing $f_1$ such that the asynchronous limit either has one or infinitely many ends. Finally, we show that the construction $f_\infty$ is an appropriate limit of the $(f_k)_k$.
