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 Authors:
(1) Martin Peresıni, Brno University of Technology, Faculty of Information Technology (iperesini@fit.vut.cz);
(2) Ivan Homoliak, Brno University of Technology, Faculty of Information Technology (ihomoliak@fit.vut);
(3) Federico Matteo Bencic, University of Zagreb, Faculty of Electrical Engineering and Computing (federico-matteo.bencic@fer.hr);
(4) Martin Hruby, Brno University of Technology, Faculty of Information Technology (hruby@fit.vut.cz);
(5) Kamil Malinka, Brno University of Technology, Faculty of Information Technology (malinka@fit.vut). This paper is available on arxiv under CC BY 4.0 DEED license. Note that since the Bitcoin block has limited capacity and transactions might have different sizes, miners consider fee normalized per Byte. Table of Links Abstract and I. Introduction Abstract and I. Introduction II. Background II. Background III. Problem Definition III. Problem Definition IV. DAG-Oriented Solutions IV. DAG-Oriented Solutions V. Game Theoretical Analysis V. Game Theoretical Analysis VI. Simulation Model VI. Simulation Model VII. Evaluation VII. Evaluation VIII. Countermeasures VIII. Countermeasures IX. Discussion and Future Work IX. Discussion and Future Work X. Related Work X. Related Work XI. Conclusion and References 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. Blockchain 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. Nakamoto Consensus (NC). difficulty 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. Fees & Rewards transaction 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. Mempool 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 Block Creation Time Authors: (1) Martin Peresıni, Brno University of Technology, Faculty of Information Technology (iperesini@fit.vut.cz); (2) Ivan Homoliak, Brno University of Technology, Faculty of Information Technology (ihomoliak@fit.vut); (3) Federico Matteo Bencic, University of Zagreb, Faculty of Electrical Engineering and Computing (federico-matteo.bencic@fer.hr); (4) Martin Hruby, Brno University of Technology, Faculty of Information Technology (hruby@fit.vut.cz); (5) Kamil Malinka, Brno University of Technology, Faculty of Information Technology (malinka@fit.vut). Authors: Authors: (1) Martin Peresıni, Brno University of Technology, Faculty of Information Technology (iperesini@fit.vut.cz); (2) Ivan Homoliak, Brno University of Technology, Faculty of Information Technology (ihomoliak@fit.vut); (3) Federico Matteo Bencic, University of Zagreb, Faculty of Electrical Engineering and Computing (federico-matteo.bencic@fer.hr); (4) Martin Hruby, Brno University of Technology, Faculty of Information Technology (hruby@fit.vut.cz); (5) Kamil Malinka, Brno University of Technology, Faculty of Information Technology (malinka@fit.vut). This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv available on arxiv Note that since the Bitcoin block has limited capacity and transactions might have different sizes, miners consider fee normalized per Byte. Note that since the Bitcoin block has limited capacity and transactions might have different sizes, miners consider fee normalized per Byte.

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Incentive Attacks on DAG-Based Blockchains with Random Transaction Selection

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Comparative Analysis of Crypto API Misuses Across Programming Languages

7 Consensus Mechanisms Developers Must Know to BUIDL for Web3

BFT Consensus: Will Your Car Full of Passengers Turn Right, Left, or Fly Over a Cliff?

Consensus Protocol in Blockchain

ConsensusPedia: An Encyclopedia of 30+ Consensus Algorithms

Could Block Proposals Be Fair and Efficient Without Proof of Work (PoW)?

A Comparative Analysis of Crypto API Misuses Across Programming Languages

7 Consensus Mechanisms Developers Must Know to BUIDL for Web3

BFT Consensus: Will Your Car Full of Passengers Turn Right, Left, or Fly Over a Cliff?

Consensus Protocol in Blockchain

ConsensusPedia: An Encyclopedia of 30+ Consensus Algorithms

Could Block Proposals Be Fair and Efficient Without Proof of Work (PoW)?

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps