Alexander Mozeika, Mohammad M. Jalalzai, Marcin P. Pawlowski
Blockchains facilitate decentralization, security, identity, and data management in cyber-physical systems. However, consensus protocols used in blockchains are prone to high message and computational complexity costs and are not suitable to be used in IoT. One way to reduce message complexity is to randomly assign network nodes into committees or shards. Keeping committee sizes small is then desirable in order to achieve lower message complexity, but this comes with a penalty of reduced reliability as there is a higher probability that a large number of faulty nodes will end up in a committee. In this work, we study the problem of estimating a probability of a failure in randomly sharded networks. We provide new results and improve existing bounds on the failure probability. Thus, our framework also paves the way to reduce committee sizes without reducing reliability.
We describe a plausible probabilistic model for a blockchain queueing environment in which rational, profit-maximising schedulers impose adversarial disciplines on incoming messages containing a payload that encodes a state transition in a machine. The model can be specialised to apply to chains with fixed or variable block times, traditional priority queue disciplines with `honest' schedulers, or adversarial public mempools. We find conditions under which the model behaves as a bulk-service queue with priority discipline and derive practical expressions for the relative block and message number of a transaction. We study this setup in the context of orders to a CFMM DEX where the execution price a user receives may be quite sensitive to its positioning in the chain -- in particular, to a string of transactions scheduled for prior execution which is not knowable at the time of order creation. We derive statistical models for the price impact of this order flow both in the presence and absence of MEV extraction activity.
Sebastian Müller, Isabel Amigo, Alexandre Reiffers-Masson, Santiago Ruano-Rincón
In directed acyclic graph (DAG)-based distributed ledgers, unreferenced blocks (tips) form the backlog of a distributed queueing system. Each new block creates one tip and attempts to remove up to $k$ existing tips by referencing them. With heterogeneous propagation delays, these service decisions are made from delayed local information, so nodes may disagree on the backlog and some reference attempts are wasted. We study a continuous-time Poisson model with bounded heterogeneous delays and uniform tip selection. We prove that the embedded tip-configuration chain is irreducible, aperiodic, and positive Harris recurrent, and hence admits a unique stationary regime. The observer and local tip-pool sizes have stationary exponential moments, converge to their stationary limits, and satisfy almost-sure ergodic averages. We also derive a Little-type identity relating the stationary mean observer tip count to the mean time until a typical block is first referenced. Simulations are included as qualitative illustrations of the effects of delay variability and issuance heterogeneity.
Open access
2 source records
math.PR
cs.DC
Mathematical and Theoretical Epidemiology and Ecology Models
It has been known for some time that the Nakamoto consensus as implemented in the Bitcoin protocol is not totally aligned with the individual interests of the participants. More precisely, it has been shown that block withholding mining strategies can exploit the difficulty adjustment algorithm of the protocol and obtain an unfair advantage. However, we show that a modification of the difficulty adjustment formula taking into account orphan blocks makes honest mining the only optimal strategy. Surprinsingly, this is still true when orphan blocks are rewarded with an amount smaller to the official block reward. This gives an incentive to signal orphan blocks. The results are independent of the connectivity of the attacker.
Yan-Xia Chang, Quan-Lin Li, Qing Wang, Xing-Shuo Song
In a practical Byzantine fault tolerance (PBFT) blockchain network, the voting nodes may always leave the network while some new nodes can also enter the network, thus the number of voting nodes is constantly changing. Such a new PBFT with dynamic nodes is called a dynamic PBFT. Clearly, the dynamic PBFT can more strongly support the decentralization and distributed structure of blockchain. However, analyzing dynamic PBFT blockchain systems will become more interesting and challenging. In this paper, we propose a large-scale Markov modeling technique to analyze the dynamic PBFT voting processes and its dynamic PBFT blockchain system. To this end, we set up a large-scale Markov process (and further a multi-dimensional Quasi-Birth-and-Death (QBD) process) and provide performance analysis for both the dynamic PBFT voting processes and the dynamic PBFT blockchain system. In particular, we obtain an effective computational method for the throughput of the complicated dynamic PBFT blockchain system. Finally, we use numerical examples to check the validity of our theoretical results and indicate how some key system parameters influence the performance measures of the dynamic PBFT voting processes and of the dynamic PBFT blockchain system. Therefore, by using the theory of multi-dimensional QBD processes and the RG-factorization technique, we hope that the methodology and results developed in this paper shed light on the study of dynamic PBFT blockchain systems such that a series of promising research can be developed potentially.
Xing-Shuo Song, Quan-Lin Li, Yan-Xia Chang, Chi Zhang
Note that the serial structure of blockchain has many essential pitfalls, thus a data network structure and its DAG-based blockchain are introduced to resolve the blockchain pitfalls. From such a network perspective, analysis of the DAG-based blockchain systems becomes interesting and challenging. So, the simulation models are adopted widely. In this paper, we first describe a simple Markov model for the DAG-based blockchain with IOTA Tangle by means of two layers of tips and internal tips' impatient connection behavior. Then we set up a continuous-time Markov process to analyze the DAG-based blockchain system and show that this Markov process is a level-dependent quasi-birth-and-death (QBD) process. Based on this, we prove that the QBD process must be irreducible and positive recurrent. Furthermore, once the stationary probability vector of the QBD process is given, we provide performance analysis of the DAG-based blockchain system. Next, we propose a new effective method for computing the average confirmation time of any arriving internal tip at this system by means of the first passage times and the PH distributions. Finally, we use numerical examples to check the validity of our theoretical results and indicate how some key system parameters influence the performance measures of this system. Therefore, we hope that the methodology and results developed in this paper can be applicable to deal with more general DAG-based blockchain systems such that a series of promising research can be developed potentially.
Many of the recent works on the profitability of rogue mining strategies hinge on a parameter called $γ$ that measures the proportion of the honest network attracted by the attacker to mine on top of his fork. These works, see arXiv:1808.01041 and arXiv.1805.08281, have surmised conclusions based on premises that erroneously treat $γ$ to be constant. In this paper, we treat $γ$ as a stochastic process and attempt to find its distribution through a Markov analysis. We begin by making strong assumptions on gamma's behaviour and proceed to translate them mathematically in order to apply them in a Markov setting. The aforementioned is executed in two separate occasions for two different models. Furthermore, we model the Bitcoin network and numerically derive a limiting distribution whereby the relative accuracy of our models is tested through a likelihood analysis. Finally, we conclude that even with control of 20% of the total hashrate, honest mining is the strongly dominant strategy.
The paper investigates the rich class of Generalized Tempered Stable distribution, an alternative to Normal distribution and the $α$-Stable distribution for modelling asset return and many physical and economic systems. Firstly, we explore some important properties of the Generalized Tempered Stable (GTS) distribution. The theoretical tools developed are used to perform empirical analysis. The GTS distribution is fitted using S&P 500, SPY ETF and Bitcoin BTC. The Fractional Fourier Transform (FRFT) technique evaluates the probability density function and its derivatives in the maximum likelihood procedure. Based on the results from the statistical inference and the Kolmogorov-Smirnov (K-S) goodness-of-fit, the GTS distribution fits the underlying distribution of the SPY ETF return. The right side of the Bitcoin BTC return, and the left side of the S&P 500 return underlying distributions fit the Tempered Stable distribution; while the left side of the Bitcoin BTC return and the right side of the S&P 500 return underlying distributions are modelled by the compound Poisson process
Hasan Mujtaba Buttar, Waqas Aman, Muhammad Mahboob Ur Rahman, Qammer H. Abbasi
This article considers an Internet-of-Things (IoT) blockchain wireless network consisting of a leader node and various follower nodes which together implement the reliable, replicated, redundant, and fault-tolerant (RAFT) consensus protocol to verify a blockchain transaction, as requested by a blockchain client. Furthermore, two kinds of active attacks, that is, jamming and impersonation, are considered on the IoT blockchain network due to the presence of multipleactivemalicious nodes in the close vicinity. When the IoT network is under a jamming attack, we utilize the stochastic geometry tool to derive the closed-form expressions for the coverage probabilities for both uplink (UL) and downlink (DL) IoT transmissions (which eventually translate to the blockchain transaction success rate). On the other hand, when the IoT network is under an impersonation attack, we propose a novel method that enables a receive IoT node to exploit the pathloss of a transmit IoT node as its fingerprint to implement a binary hypothesis test for transmit node identification. To this end, we also provide the closed-form expressions for the probabilities of false alarms, missed detection, and misclassification. Finally, we present detailed simulation results that indicate the following: 1) the coverage probability (and hence the blockchain transaction success rate) improves as the jammers’ locations move away from the IoT network and 2) the three error probabilities decrease (i.e., chances of corruption of the blockchain ledger data due to false data injection by malicious node decrease) as a function of the quality of the link between the transmit and receive IoT nodes.
The paper studies nonstationary high-dimensional vector autoregressions of order $k$, VAR($k$). Additional deterministic terms such as trend or seasonality are allowed. The number of time periods, $T$, and the number of coordinates, $N$, are assumed to be large and of the same order. Under this regime the first-order asymptotics of the Johansen likelihood ratio (LR), Pillai-Bartlett, and Hotelling-Lawley tests for cointegration are derived: the test statistics converge to nonrandom integrals. For more refined analysis, the paper proposes and analyzes a modification of the Johansen test. The new test for the absence of cointegration converges to the partial sum of the Airy$_1$ point process. Supporting Monte Carlo simulations indicate that the same behavior persists universally in many situations beyond those considered in our theorems. The paper presents empirical implementations of the approach for the analysis of S$\&$P$100$ stocks and of cryptocurrencies. The latter example has a strong presence of multiple cointegrating relationships, while the results for the former are consistent with the null of no cointegration.
Emerging applications of blockchains, such as grocery supply chains, require frequent updates to the data structure. This is in contrast with typical analyses of the Bitcoin blockchain, in which updates occur infrequently. With more frequent updates, the spread of blocks among participants in the blockchain protocol becomes complicated; thus, the structure of the blockchain data structure itself can differ significantly from the structure without the presence of network delays. In addition, emerging blockchain applications such as internet-of-things or supply chain warrant different architectures of the blockchain data structure, and so one needs a general understanding of how the data structure works rather than focusing on the specific architecture of Bitcoin. In this paper, we develop a new model to study the dynamics of the blockchain data structure in the presence of i.i.d.~network delays. Specifically, we consider an asymptotic design criterion called one-endedness, which should be satisfied by all blockchain architectures. We develop techniques to show that the one-endedness property holds for some of the leading blockchain architectures.
It is interesting but difficult and challenging to study Ethereum with multiple mining pools. One of the main difficulties comes from not only how to represent such a general tree with multiple block branches (or sub-chains) related to the multiple mining pools, but also how to analyze a multi-dimensional stochastic system due to the mining competition among the multiple mining pools. In this paper, we first set up a mathematical representation for the tree with multiple block branches. Then we provide a block classification of Ethereum: Regular blocks (in the main chain), orphan blocks, uncle blocks, stale blocks, and nephew blocks, and give some key ratios and probabilities of generating the different types of blocks by applying the law of large numbers. Based on this, we further discuss the growth rate of blockchain and the reward allocation among the multiple mining pools through applying the renewal reward theorem. Finally, we use some simulation experiments to verify our theoretical results, and show that the approximate computation approaches developed, such as the key ratios and probabilities, the long-term growth rate of blockchain, and the long-term reward allocation (rate) among the multiple mining pools, can have a faster convergence. Therefore, we provide a powerful tool for observing and understanding the influence of the selfish mining attacks on the performance of Ethereum with multiple mining pools. We believe that the methodology and results developed in this paper will shed light on the study of Ethereum with multiple mining pools, such that a series of promising research can be inspired potentially.
We propose and study a new class of polynomial voting rules for a general decentralized decision/consensus system, and more specifically for the proof-of-stake protocol. The main idea, inspired by the Penrose square-root law and the more recent quadratic voting rule, is to differentiate a voter’s voting power and the voter’s share (fraction of the total in the system). We show that, whereas voter shares form a martingale process that converges to a Dirichlet distribution, their voting powers follow a supermartingale process that decays to zero over time. This prevents any voter from controlling the voting process and, thus, enhances security. For both limiting results, we also provide explicit rates of convergence. When the initial total volume of votes (or stakes) is large, we show a phase transition in share stability (or the lack thereof), corresponding to the voter’s initial share relative to the total. We also study the scenario in which trading (of votes/stakes) among the voters is allowed and quantify the level of risk sensitivity (or risk aversion) in three categories, corresponding to the voter’s utility being a supermartingale, a submartingale, and a martingale. For each category, we identify the voter’s best strategy in terms of participation and trading. Funding: W. Tang gratefully acknowledges financial support through the National Science Foundation [Grants DMS-2113779 and DMS-2206038] and through a start-up grant at Columbia University. D. D. Yao’s work is part of a Columbia–City University/Hong Kong collaborative project that is supported by InnoHK Initiative, the Government of Hong Kong Special Administrative Region, and the Laboratory for AI-Powered Financial Technologies.
In this paper, we provide a novel dynamic decision method of blockchain selfish mining by applying the sensitivity-based optimization theory. Our aim is to find the optimal dynamic blockchain-pegged policy of the dishonest mining pool. To study the selfish mining attacks, two mining pools is designed by means of different competitive criterions, where the honest mining pool follows a two-block leading competitive criterion, while the dishonest mining pool follows a modification of two-block leading competitive criterion through using a blockchain-pegged policy. To find the optimal blockchain-pegged policy, we set up a policy-based continuous-time Markov process and analyze some key factors. Based on this, we discuss monotonicity and optimality of the long-run average profit with respect to the blockchain-pegged reward and prove the structure of the optimal blockchain-pegged policy. We hope the methodology and results derived in this paper can shed light on the dynamic decision research on the selfish mining attacks of blockchain selfish mining.
We consider the following network model motivated, in particular, by blockchains and peer-to-peer live streaming. Data packet flows arrive at the network nodes and need to be disseminated to all other nodes. Packets are relayed through the network via links of finite capacity. A packet leaves the network when it is disseminated to all nodes. Our focus is on two communication disciplines, which determine the order in which packets are transmitted over each link, namely {\em Random-Useful} (RU) and {\em Oldest-Useful} (OU). We show that RU has the maximum stability region in a general network. For the OU we demonstrate that, somewhat surprisingly, it does {\em not} in general have the maximum stability region. We prove that OU does achieve maximum stability in the important special case of a symmetric network, given by the full graph with equal capacities on all links and equal arrival rates at all nodes. We also give other stability results, and compare different disciplines' performances in a symmetric system via simulation. Finally, we study the cumulative delays experienced by a packet as it propagates through the symmetric system, specifically the delay asymptotic behavior as $N \to \infty$. We put forward some conjectures about this behavior, supported by heuristic arguments and simulation experiments.
Hansjörg Albrecher, Dina Finger, Pierre-Olivier Goffard
The resource-consuming mining of blocks on a blockchain equipped with a proof of work consensus protocol bears the risk of ruin, namely when the operational costs for the mining exceed the received rewards. In this paper we investigate to what extent it is of interest to join a mining pool that reduces the variance of the return of a miner for a specified cost for participation. Using methodology from ruin theory and risk sharing in insurance, we quantitatively study the effects of pooling in this context and derive several explicit formulas for quantities of interest. The results are illustrated in numerical examples for parameters of practical relevance.
Distributed Ledger Technologies provide a mechanism to achieve ordering among transactions that are scattered on multiple participants with no prerequisite trust relations. This mechanism is essentially based on the idea of new transactions referencing older ones in a chain structure. Recently, DAG-type Distributed Ledgers that are based on directed acyclic graphs (DAGs) were proposed to increase the system scalability through sacrificing the total order of transactions. In this paper, we develop a mathematical model to study the process that governs the addition of new transactions to the DAG-type Distributed Ledger. We propose a simple model for DAG-type Distributed Ledgers that are obtained from a recursive Young-age Preferential Attachment scheme, i.e. new connections are made preferably to transactions that have not been in the system for very long. We determine the asymptotic degree structure of the resulting graph and show that a forward component of linear size arises if the edge density is chosen sufficiently large in relation to the `young-age preference' that tunes how quickly old transactions become unattractive.
The practical Byzantine fault tolerant (PBFT) consensus mechanism is one of the most basic consensus algorithms (or protocols) in blockchain technologies, thus its performance evaluation is an interesting and challenging topic due to a higher complexity of its consensus work in the peer-to-peer network. This paper describes a simple stochastic performance model of the PBFT consensus mechanism, which is refined as not only a queueing system with complicated service times but also a level-independent quasi-birth-and-death (QBD) process. From the level-independent QBD process, we apply the matrix-geometric solution to obtain a necessary and sufficient condition under which the PBFT consensus system is stable, and to be able to numerically compute the stationary probability vector of the QBD process. Thus we provide four useful performance measures of the PBFT consensus mechanism, and can numerically calculate the four performance measures. Finally, we use some numerical examples to verify the validity of our theoretical results, and show how the four performance measures are influenced by some key parameters of the PBFT consensus. By means of the theory of multi-dimensional Markov processes, we are optimistic that the methodology and results given in this paper are applicable in a wide range research of PBFT consensus mechanism and even other types of consensus mechanisms.
The research designs a new integrated system for the security enhancement of a decentralized network by preventing damages from attackers, particularly for the 51 percent attack. The concept of multiple layered design based on Blockchain Governance Games frameworks could handle multiple number of networks analytically. The Multi-Layered Blockchain Governance Game is an innovative analytical model to find the best strategies for executing a safety operation to protect whole multiple layered network systems from attackers. This research fully analyzes a complex network with the compact mathematical forms and theoretically tractable results for predicting the moment of a safety operation execution are fully obtained. Additionally, simulation results are demonstrated to obtain the optimal values of configuring parameters of a blockchain-based security network. The Matlab codes for the simulations are publicly available to help those whom are constructing an enhanced decentralized security network architecture through this proposed integrated theoretical framework.
Internet of quantum blockchains (IoB) will be the future Internet. In this paper, we make two new contributions to IoB: developing a block based quantum channel networking technology to handle its security modeling in face of the quantum supremacy and establishing IoB based FinTech platform model with dynamic pricing for stable digital currency. The interaction between our new contributions is also addressed. In doing so, we establish a generalized IoB security model by quantum channel networking in terms of both time and space quantum entanglements with quantum key distribution (QKD). Our IoB can interact with general structured things (e.g., supply chain systems) having online trading and payment capability via stable digital currency and can handle vector-valued data streams requiring synchronized services. Thus, within our designed QKD, a generalized random number generator for private and public keys is proposed by a mixed zero-sum and non-zero-sum resource-competition pricing policy. The effectiveness of this policy is justified by diffusion modeling with approximation theory and numerical implementations.
This is an expanded version of the lecture given at the AMS Short Course on Mean Field Games, on January 13, 2020 in Denver CO. The assignment was to discuss applications of Mean Field Games in finance and economics. I need to admit upfront that several of the examples reviewed in this chapter were already discussed in book form. Still, they are here accompanied with discussions of, and references to, works which appeared over the last three years. Moreover, several completely new sections are added to show how recent developments in financial engineering and economics can benefit from being viewed through the lens of the Mean Field Game paradigm. The new financial engineering applications deal with bitcoin mining and the energy markets, while the new economic applications concern models offering a smooth transition between macro-economics and finance, and contract theory.
Mining blocks on a blockchain equipped with a proof of work consensus protocol is well known to be resource consuming. A miner bears the operational cost, mainly electricity consumption and IT gear, of mining and is compensated by a capital gain when a block is discovered. This paper aims at quantifying the profitability of mining when the possible event of ruin is also considered. This is done by formulating a tractable stochastic model and using tools from applied probability and analysis, including the explicit solution of a certain type of advanced functional differential equation. The expected profit at a future time point is determined for the situation when the miner follows the protocol as well as when the miner withholds blocks. The obtained explicit expressions allow us to analyze the sensitivity with respect to the different model components and to identify conditions under which selfish mining is a strategic advantage.
We study the growth of a time-ordered rooted tree by probabilistic attachment of new vertices to leaves. We construct a likelihood function of the leaves based on the connectivity of the tree. We take such connectivity to be induced by the merging of directed ordered paths from leaves to the root. Combining the likelihood with an assigned prior distribution leads to a posterior leaf distribution from which we sample attachment points for new vertices. We present computational examples of such Bayesian tree growth. Although the discussion is generic, the initial motivation for the paper is the concept of a distributed ledger, which may be regarded as a time-ordered random tree that grows by probabilistic leaf attachment.
For a mining strategy we define the notion of "profit lag" as the minimum time it takes to be profitable after that moment. We compute closed forms for the profit lag and the revenue ratio for the strategies "selfish mining" and "intermittent selfish mining". This confirms some earlier numerical simulations and clarifies misunderstandings on profitability in the literature. We also study mining pairs of PoW cryptocurrencies, often coming from a fork, with the same mining algorithm. This represents a vector of attack that can be exploited using the "alternate network mining" strategy that we define. We compute closed forms for the profit lag and the revenue ratiofor this strategy that is more profitable than selfish mining and intermittent selfish mining. It is also harder to counter since it does not rely on a flaw in the difficulty adjustment formula that is the reason for profitability of the other strategies.