Incentive Attacks on DAG-Based Blockchains with Random Transaction Selection

Table of Links

Abstract and I. Introduction

II. Background

III. Problem Definition

IV. DAG-Oriented Solutions

V. Game Theoretical Analysis

VI. Simulation Model

VII. Evaluation

VIII. Countermeasures

IX. Discussion and Future Work

X. Related Work

XI. Conclusion and References

II. BACKGROUND

We establish preliminary terms and definitions that will be used throughout this work. The focus is put on Nakamoto’s consensus that is to be optimized by DAGs.

Blockchain. The blockchain is a tamper-resistant data structure in which data records (i.e., blocks) are linked using a cryptographic hash function. Each new block is agreed upon by consensus nodes running a consensus protocol.

Nakamoto Consensus (NC). NC [33] uses a single chain to link the blocks, while Proof of Work (PoW) algorithm is used to establish consensus among nodes (i.e., miners), which is a mathematical puzzle of cryptographic zero-knowledge hash proof, where one party proves to others that it has spent a certain computational effort and thus is entitled to be a leader of the round, producing a block. This effort represents finding a value below a threshold (determined by the difficulty parameter), which is computationally intensive. On the other hand, the correctness verification of the puzzle requires negligible effort. NC is used in Bitcoin, where the order of blocks was originally determined using the longest chain fork-choice rule (see Fig. 2). However, this rule was later replaced in favor of the strongest chain rule (see Fig. 3), which takes into account the accumulated difficulty of the PoW puzzle.

Fees & Rewards. Miners creating new blocks are rewarded with block rewards. Block rewards refer to new crypto tokens (e.g., BTC) awarded by the blockchain network. It is assumed that miners earn profits proportionally to their consensus (i.e., mining) power. Another source of income for miners is transaction fees, which are awarded to the miner who includes the corresponding transaction in a block. Transaction fees are paid by clients who deliberately choose the value of the fee based on the transaction’s priority. To maximize profit, miners use a transaction selection mechanism that prioritizes the transactions with the highest (per Byte)[3] fees.

Mempool. A mempool is a data structure of each miner and contains transactions that can potentially be included (i.e., mined) in a block produced by a miner. A new transaction is ‘gossiped’, i.e., sent from a client to its peers, who in turn forward the transaction to their peers, etc., until the transaction has propagated throughout the network. Due to a network propagation delay, transactions and new blocks are not immediately propagated throughout the network. Therefore, the mempool might slightly vary node per node, especially at the time a new block is mined.

Block Creation Time. In Bitcoin, there is a default block creation time λ set to create a new block every 10 minute on average. This parameter is derived directly from the network difficulty, which changes over time, and it is adjusted every 2016 block to fit the target value of 10 minutes (i.e., approximately every two weeks). According to Gervais et al., [15], the stale block rate of Bitcoin is 0.41%. Other sources [11], [18] state the values around 0.5 − 1%, which is considered negligible. We assume that the mathematical model corresponding to λ of Bitcoin is an exponentially distributed random variable with the time between two consecutive blocks given by

3. Note that since the Bitcoin block has limited capacity and transactions might have different sizes, miners consider fee normalized per Byte.