Blockchain Papers

Jona Stinner, Marcel Tyrell

No abstract is available for this record.

Stefano Bistarelli, Rocco De Nicola, Letterio Galletta, Cosimo Laneve · 6 authors

Abstract We analyze the protocol of the bitcoin blockchain by using the PRISM probabilistic model checker. In particular, we (i) extend PRISM with the ledger data type , (ii) model the behavior of the key participants in the protocol—the miners —and (iii) describe the whole protocol as a parallel composition of processes. The probabilistic analysis of the model highlights how forks happen and how they depend on specific parameters of the protocol, such as the difficulty of the cryptopuzzle and the network communication delays. Our results confirm that considering transactions in blocks at depth larger than 5 as confirmed is reasonable because the majority of miners have consistent blockchains up‐to that depth with probability of almost 1. We also study the behavior of networks with churn miners, which may leave the network and rejoin afterwards, and with different topologies.

Befekadu G. Gebraselase, Bjarne E. Helvik, Yuming Jiang

Blockchain is a technology that provides a distributed ledger that stores previous records while maintaining consistency and security. Bitcoin is the first and largest decentralized electronic cryptographic system that uses blockchain technology. It faces a challenge in making all the nodes synchronize and have the same overall view with the cost of scalability and performance. In addition, with miners' financial interest playing a significant role in choosing transactions from the backlog, small fee or small fee per byte value transactions will exhibit more delays. To study the issues related to the system's performance, we developed an $M(t)/M^N/1$ model. The backlog's arrival follows an inhomogeneous Poison process to the system that has infinite buffer capacity, and the service time is distributed exponentially, which removes $N$ transactions at time. Besides validating the model with measurement data, we have used the model to study the reward distribution when miners take transaction selection strategies like fee per byte, fee-based, and FIFO. The analysis shows that smaller fee transactions exhibit higher waiting times, even with increasing the block size. Moreover, the miner transaction selection strategy impacts the final gain.

Xu Wang, Wei Ni, Xuan F. Zha, Guangsheng Yu · 7 authors

As distributed ledgers, blockchains run consensus protocols which trade capacity for consistency, especially in non-ideal networks with incomplete connectivity and erroneous links. Existing studies on the tradeoff between capacity and consistency are only qualitative or rely on specific assumptions. This paper presents discrete-time Markov chain models to quantify the capacity of Proof-of-Work based public blockchains in non-ideal networks. The comprehensive model is collapsed to be ergodic under the eventual consistency of blockchains, achieving tractability and efficient evaluations of blockchain capacity. A closed-form expression for the capacity is derived in the case of two miners. Another important aspect is that we extend the ergodic model to analyze the capacity under strong consistency, evaluating the robustness of blockchains against double-spending attacks. Validated by simulations, the proposed models are accurate and reveal the effect of link quality and the distribution of mining rates on blockchain capacity and the ratio of stale blocks.

Authors unavailable

This work proposes Practical Byzantine Fault Tolerance (PBFT) ordering service needed for block formation in permissioned blockchain environments. Contrary to current PBFT implementations that only provide a single point of entry to the ordering service, we allow each ordering node to act as an entry point that proposes and conducts the consensus process of including new record in the distributed ledger. To ensure atomicity of record insertion in distributed ledger, we have developed a bandwidth reservation protocol that uses a modification of CSMA/CA protocol to regulate access to the broadcast medium formed by the P2P network of TCP connections between orderers. We have modeled record insertion service time in a cluster where ordering nodes have random position within Cartesian coordinate system. We have also modeled total request access time to the ledger which includes waiting time in the ordered's queue and record insertion time. These models are used to evaluate system performance under variable request rate ordering service, variable number of nodes and variable physical cluster dimensions. We also address cluster interconnections which can increase coverage and capacity of PBFT system.

Long Shi, Taotao Wang, Jun Li, Shengli Zhang · 5 authors

As the underlying consensus protocol of Bitcoin and Ethereum blockchains, Proof-of-Work (PoW) features a cryptographic mathematical puzzle whose solution is easy to verify but extremely hard to solve. Under PoW, miners maintain the security of blockchain by devoting computing powers to solve the puzzle; the miner who has solved the puzzle successfully generates a block, along with a reward (e.g., a set of cryptocurrency). The average waiting time to generate a block is inversely proportional to the computing power of the miner. To reduce the average block generation time, a group of individual miners can form a centralized mining pool to aggregate their computing power to solve the puzzle together and share the reward contained in the block. However, if the aggregated computing power of the pool forms a substantial portion of the total computing power in the network, the pooled mining undermines the core spirit of blockchain, i.e., the decentralization, and harms its security. To discourage the pooled mining, we develop a new consensus protocol called Proof-of-Age (PoA) that builds upon the native PoW protocol. The core idea of PoA lies in using Age-of-Work (AoW) to measure the effective mining periods that the miners have devoted to maintaining the security of blockchain. Unlike in the native PoW protocol, in our PoA protocol, miners benefit from its effective mining periods even if they have not successfully mined a block. We first employ a continuous time Markov chain (CTMC) to model the block generation process of the PoA based blockchain. Based on this CTMC model, we then analyze the block generation rates of the mining pool and solo miners respectively. Our analytical results verify that under PoA, the block generation rates of miners in the mining pool are reduced compared to that of solo miners, thereby disincentivizing the pooled mining. Finally, we simulate the mining process in the PoA blockchain to demonstrate the consistency of the analytical results.

Daniel M. Kane, Andreas Fackler, Adam Gągol, Damian Straszak

There has been recently a lot of progress in designing efficient partially synchronous BFT consensus protocols that are meant to serve as core consensus engines for Proof of Stake blockchain systems. While the state-of-the-art solutions attain virtually optimal performance under this theoretical model, there is still room for improvement, as several practical aspects of such systems are not captured by this model. Most notably, during regular execution, due to financial incentives in such systems, one expects an overwhelming fraction of nodes to honestly follow the protocol rules and only few of them to be faulty, most likely due to temporary network issues. Intuitively, the fact that almost all nodes behave honestly should result in stronger confidence in blocks finalized in such periods, however it is not the case under the classical model, where finality is binary. We propose Highway, a new consensus protocol that is safe and live in the classical partially synchronous BFT model, while at the same time offering practical improvements over existing solutions. Specifically, block finality in Highway is not binary but is expressed by fraction of nodes that would need to break the protocol rules in order for a block to be reverted. During periods of honest participation finality of blocks might reach well beyond 1/3 (as what would be the maximum for classical protocols), up to even 1 (complete certainty). Having finality defined this way, Highway offers flexibility with respect to the configuration of security thresholds among nodes running the protocol, allowing nodes with lower thresholds to reach finality faster than the ones requiring higher levels of confidence.

Roberta Pellegrino, Nicola Costantino, Danilo Tauro

The purpose of this paper is to study how advanced information about customer needs obtained through an Advance Purchase Discount (APD) contract can be exploited to coordinate the capital flow and enhance the efficiency of a two-stage supply chain (SC) under decentralized control in cases of stochastic customer demand. We developed an APD model in the form of an option contract, where the model and evaluation include the flexibility for the upstream firm to decide whether to provide a discount for an advance purchase at its own discretion. Applying the model to a Fortune 100 company, a leader in the Fast Mover Consumer Goods (FMCG) industry, showed that under certain conditions, and with suitably chosen contract parameters, management of decentralized control via APD contracts can lead to system-wide efficiency, and the individual decision makers pursue their own best interests, ensuring a win-win condition.

Hansjörg Albrecher, Pierre-Olivier Goffard

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.

Michael Neuder, Daniel J. Moroz, Rithvik Rao, David C. Parkes

Blockchains are intended to be immutable, so an attacker who is able to delete transactions through a chain reorganization (a malicious reorg) can perform a profitable double-spend attack. We study the rate at which an attacker can execute reorgs in the Tezos Proof-of-Stake protocol. As an example, an attacker with 40% of the staking power is able to execute a 20-block malicious reorg at an average rate of once per day, and the attack probability increases super-linearly as the staking power grows beyond 40%. Moreover, an attacker of the Tezos protocol knows in advance when an attack opportunity will arise, and can use this knowledge to arrange transactions to double-spend. We show that in particular cases, the Tezos protocol can be adjusted to protect against deep reorgs. For instance, we demonstrate protocol parameters that reduce the rate of length-20 reorg opportunities for a 40% attacker by two orders of magnitude. We also observe a trade-off between optimizing for robustness to deep reorgs (costly deviations that may be net profitable because they enable double-spends) and robustness to selfish mining (mining deviations that result in typically short reorgs that are profitable even without double-spends). That is, the parameters that optimally protect against one make the other attack easy. Finally, we develop a method that monitors the Tezos blockchain health with respect to malicious reorgs using only publicly available information.

Nohpill Park, Abhilash Kancharla, Hye-Young Kim

This paper proposes a real-time chain and a novel embedded Markovian queueing model with variable bulk arrival (VBA) and variable bulk service (VBS) in order to establish and assure a theoretical foundation to design a blockchain-based real-time system with particular interest in Ethereum. Based on the proposed model, various performances are simulated in a numerical manner in order to validate the efficacy of the model by checking good agreements with the results against intuitive and typical expectations as a baseline. A demo of the proposed real-time chain is developed in this work by modifying the open source of Ethereum Geth 1.9.11. The work in this paper will provide both a theoretical foundation to design and optimize the performances of the proposed real-time chain, and ultimately address and resolve the performance bottleneck due to the conventional block-synchrony by employing an asynchrony by the real-time deadline to some extent.

Fabian Schär

Proof-of-work cryptocurrencies are heavily criticized for the alleged inefficiency of their mining mechanism. However, critics fail to distinguish between the resources that are used to secure the blockchain and those that are wasted. In this paper, we introduce a simple mining model and use this model to analyze the consensus protocol's efficiency, while accounting for the heterogeneity of the miners involved. We categorize the resources allocated by the miners as either useful or wasteful, and then use this to introduce a new measure of efficiency. We then demonstrate how this value depends on a set of potential miners and the variation of their marginal costs. Using this model, we then consider the existence of botnets and show how one could affect the security of the network. This analysis indicates that botnets can significantly change the mining landscape and, under certain circumstances, may lead to a dissipation ratio greater than one.

Tianmu Li, Yongjun Ren, Jinyue Xia

Blockchain technology has recently obtained widespread attention. And it is being regarded as potentially even more disruptive than the Internet, whose usage includes large areas of applications ranging from crypto currency, financial services, reputation system, Internet of Things, sharing economy to public and social services. The existing works of blockchain primarily are focused on key components and potential applications. However, in the existing blockchain systems, the waiting time of transactions is too long. Furthermore, it may produce serious consequences because many important transactions are not handled timely. To solve the problem, in the paper, the blockchain Queuing model with non-preemptive limited-priority is established, which considers the different transactions having different priority when being mined. There are two classes of transactions in the model, one is high-priority transaction with pay or with prior interest, the other is low-priority transaction without pay or without prior interest. And high-priority transactions can be mined preferentially when mining process is not occupied. If low-priority transaction is being mined, the arriving high-priority transaction will wait for the mining accomplishment. Through the analysis of the model, we compute average waiting time, average staying time and average length of queue. From simulation of the model, we find that transactions with pay or with prior interest and increase service rate of mining are effective for reducing waiting time. Besides, the two factors mutually reinforce to shorten waiting time. Finally, we conclude this paper and point out the direction of future research.

Sushil Mahavir Varma, Siva Theja Maguluri

Cryptocurrency networks, such as Bitcoin, have emerged as a distributed alternative to traditional centralized financial transaction networks. However, there are major challenges in scaling up the throughput of such networks. Lightning network and Spider network are alternates that build bidirectional payment channels on top of cryptocurrency networks using smart contracts, to enable fast transactions that bypass the Blockchain. In this article, we study the problem of routing transactions in such a payment processing network. We first propose a Stochastic model to study such a system, as opposed to a fluid model that is studied in the literature. Each link in such a model is a two-sided queue, and unlike classical queues, such queues are not stable unless there is an external control. We propose a notion of stability for the payment processing network consisting of such two-sided queues using the notion of on-chain rebalancing. We then characterize the capacity region and propose a throughput optimal algorithm that stabilizes the system under any load within the capacity region. The stochastic model enables us to study closed-loop policies, which typically have better queuing/delay performance than the open-loop policies (or static split rules) studied in the literature. We investigate this through simulations.

Jun Zhao, Jing Tang, Zengxiang Li, Huaxiong Wang · 6 authors

Formal analyses of blockchain protocols have received much attention recently. Consistency results of Nakamoto's blockchain protocol are often expressed in a quantity $c$, which denotes the expected number of network delays before some block is mined. With $μ$ (resp., $ν$) denoting the fraction of computational power controlled by benign miners (resp., the adversary), where $μ+ ν= 1$, we prove for the first time that to ensure the consistency property of Nakamoto's blockchain protocol in an asynchronous network, it suffices to have $c$ to be just slightly greater than $\frac{2μ}{\ln (μ/ν)}$. Such a result is both neater and stronger than existing ones. In the proof, we formulate novel Markov chains which characterize the numbers of mined blocks in different rounds.

Christopher King

Abstract A shared ledger is a record of transactions that can be updated by any member of a group of users. The notion of independent and consistent record-keeping in a shared ledger is important for blockchain and more generally for distributed ledger technologies. In this paper we analyze a stochastic model for the shared ledger known as the tangle, which was devised as the basis for the IOTA cryptocurrency. The model is a random directed acyclic graph, and its growth is described by a non-Markovian stochastic process. We first prove ergodicity of the stochastic process, and then derive a delay differential equation for the fluid model which describes the tangle at high arrival rate. We prove convergence in probability of the tangle process to the fluid model, and also prove global stability of the fluid model. The convergence proof relies on martingale techniques.

Yoshiaki Kawase, Shoji Kasahara

<p style='text-indent:20px;'>In Bitcoin system, a transaction is given a priority value according to its attributes such as the remittance amount and fee, and transactions with high priorities are likely to be confirmed faster than those with low priorities. In this paper, we analyze the transaction-confirmation time for Bitcoin system. We model the transaction-confirmation process as a queueing system with batch service, M/<inline-formula><tex-math id="M1">\begin{document}$ \mbox{G}^B $\end{document}</tex-math></inline-formula>/1. We consider the joint distribution of numbers of transactions in system and the elapsed service time, deriving the mean transaction-confirmation time. Using the result, we derive the recursive formulae of mean transaction-confirmation times of an M/<inline-formula><tex-math id="M2">\begin{document}$ \mbox{G}^B $\end{document}</tex-math></inline-formula>/1 queue with priority service discipline. In numerical examples, we show the effect of the maximum block size on the mean transaction-confirmation time, investigating the accuracy region of our queueing model. We also discuss how the increase in micropayments, which are likely to be given low priorities, affects the transaction-confirmation time.

Ashley S. McAbee, Murali Tummala, John McEachen

In this paper, the authors review documented problems in military intelligence that appear well suited for improvement via blockchain technology. We review guidance from the literature related to determining blockchain technology applicability and propose a decision aid tailored to military intelligence perspectives. We also propose applying batch queueing theory to enable initial feasibility studies and present analysis toward the first known case study of military intelligence incorporation of blockchain technology, a project reviewing blockchain applicability to an intelligence database that stores geographic locations of units of interest.

Daniel Fullmer, A. Stephen Morse

This paper presents a stochastic model for block arrival times based on the difficulty retargeting rule used in Bitcoin, as well as other proof-of-work blockchains. Unlike some previous work, this paper explicitly models the difficulty target as a random variable which is a function of the previous block arrival times and affecting the block times in the next retargeting period. An explicit marginal distribution is derived for the time between successive blocks (the blocktime), while allowing for randomly changing difficulty. This paper also aims to serve as an introduction to Bitcoin and proof-of-work blockchains for the controls community, focusing on the difficulty retargeting procedure used in Bitcoin.

Hyowoon Seo, Jihong Park, Mehdi Bennis, Wan Choi

This paper proposes Consensus-Before-Talk (CBT), a spectrum etiquette architecture leveraged by distributed ledger technology (DLT). In CBT, secondary users' spectrum access requests reach a consensus in a distributed way, thereby enabling collision-free distributed dynamic spectrum access. To achieve this consensus, the secondary users need to pay for the extra request exchanging delays. Incorporating the consensus delay, the end-to-end latency under CBT is investigated. Both the latency analysis and numerical evaluation validate that the proposed CBT achieves the lower end-to-end latency particularly under severe secondary user traffic, compared to the Listen-Before-Talk (LBT) benchmark scheme.

Quan‐Lin Li, Jing-Yu Ma, Yan-Xia Chang

Blockchain has many benefits including decentralization, availability, persistency, consistency, anonymity, auditability and accountability, and it also covers a wide spectrum of applications ranging from cryptocurrency, financial services, reputation system, Internet of Things, sharing economy to public and social services. Not only may blockchain be regarded as a by-product of Bitcoin cryptocurrency systems, but also it is a type of distributed ledger technology through using a trustworthy, decentralized log of totally ordered transactions. By summarizing the literature of blockchain, it is found that more papers focus on engineering implementation and realization, while little work has been done on basic theory, for example, mathematical models (Markov processes, queueing theory and game models), performance analysis and optimization of blockchain systems. In this paper, we develop queueing theory of blockchain systems and provide system performance evaluation. To do this, we design a Markovian batch-service queueing system with two different service stages, while the two stages are suitable to well express the mining process in the miners pool and the building of a new blockchain. By using the matrix-geometric solution, we obtain a system stable condition and express three key performance measures: (a) The number of transactions in the queue, (b) the number of transactions in a block, and (c) the transaction-confirmation time. Finally, We use numerical examples to verify computability of our theoretical results. Although our queueing model is simple under exponential or Poisson assumptions, our analytic method will open a series of potentially promising research in queueing theory of blockchain systems.

George Gui, Alı Hortaçsu, José Tudón

We analyze the economic incentives generated by the proof-of-stake mechanism discussed in the Ethereum Casper upgrade proposal. Compared with proof-of-work, proof-of-stake has a different cost structure for attackers. In Budish (2018), three equations characterize the limits of Bitcoin, which has a proof-of-work mechanism. We investigate their counterparts and evaluate the risk of double-spending attack and sabotage attack. We argue that PoS is safer than PoW agaisnt double-spending attack because of the tractability of attackers, which implies a large "stock" cost for the attacker. Compared to a PoW system whose mining equipments are repurposable, PoS is also safer against a sabotage attack.

Maria Frolkova, Michel Mandjes

The synchronization process inherent to the Bitcoin network gives rise to an infinite-server model with the unusual feature that customers interact. Among the closed-form characteristics that we derive for this model is the busy period distribution which, counterintuitively, does not depend on the arrival rate. We explain this by exploiting the equivalence between two specific service disciplines, which is also used to derive the model's stationary distribution. Next to these closed-form results, the second major contribution concerns an asymptotic result: a fluid limit in the presence of service delays. Since fluid limits arise under scalings of the law-of-large-numbers type, they are usually deterministic, but in the setting of the model discussed in this paper the fluid limit is random (more specifically, of growth-collapse type).

Cyril Grunspan, Ricardo Pérez-Marco

We correct the double spend race analysis given in Nakamoto’s foundational Bitcoin article and find the exact closed-form formula for the probability of success of a double spend attack using the regularized incomplete beta function. We give the first proof of its exponential decay on the number of confirmations, often cited in the literature, and find an asymptotic formula. Larger number of confirmations are required compared to those given by Nakamoto. We also compute this probability conditional to the knowledge of the time of the confirmations. This provides a finer risk analysis than the classical one.