Table of Links Abstract and 1. Introduction Abstract and 1. Introduction 1.1 Our Approach 1.1 Our Approach 1.2 Our Results & Roadmap 1.2 Our Results & Roadmap 1.3 Related Work 1.3 Related Work Model and Warmup and 2.1 Blockchain Model
2.2 The Miner
2.3 Game Model
2.4 Warm Up: The Greedy Allocation Function


The Deterministic Case and 3.1 Deterministic Upper Bound
3.2 The Immediacy-Biased Class Of Allocation Function


The Randomized Case


Discussion and References Model and Warmup and 2.1 Blockchain Model
2.2 The Miner
2.3 Game Model
2.4 Warm Up: The Greedy Allocation Function Model and Warmup and 2.1 Blockchain Model Model and Warmup and 2.1 Blockchain Model 2.2 The Miner 2.2 The Miner 2.3 Game Model 2.3 Game Model 2.4 Warm Up: The Greedy Allocation Function 2.4 Warm Up: The Greedy Allocation Function The Deterministic Case and 3.1 Deterministic Upper Bound
3.2 The Immediacy-Biased Class Of Allocation Function The Deterministic Case and 3.1 Deterministic Upper Bound The Deterministic Case and 3.1 Deterministic Upper Bound 3.2 The Immediacy-Biased Class Of Allocation Function 3.2 The Immediacy-Biased Class Of Allocation Function The Randomized Case The Randomized Case The Randomized Case Discussion and References Discussion and References Discussion and References A. Missing Proofs for Sections 2, 3
B. Missing Proofs for Section 4
C. Glossary A. Missing Proofs for Sections 2, 3 A. Missing Proofs for Sections 2, 3 B. Missing Proofs for Section 4 B. Missing Proofs for Section 4 C. Glossary C. Glossary 3 The Deterministic Case In this section, we focus on the discount model with miner ratio α ̸= 0 and some discount rate λ. Missing proofs are given in Appendix A. 3.1 Deterministic Upper Bound By combining Eqs. (5) and (6), the proof is concluded: 3.2 The Immediacy-Biased Class Of Allocation Function We proceed by introducing the immediacy-biased ratio class of allocation functions, and identify a regime of discount rates λ which we call the “semi-myopic” regime where it achieves the optimal deterministic competitive ratio. Given a parameter ℓ ∈ R, we denote the corresponding instance of this class as ρℓ and define it in the following manner Definition 3.3 (The ℓ-immediacy-biased ratio allocation function ρℓ). For a set S, let Definition 3.3 Before providing the lower and upper bound analysis, we comment on how our algorithm stands in comparison with another algorithm, MG [LSS05]. While the ℓ-immediacy-biased considers only the highest T T L = 1 transaction as a possible candidate to be scheduled instead of the highest-fee transaction, MG considers any earliest-deadline transaction. I.e., the algorithms differ in their behavior when no T T L = 1 transactions are available. However, in terms of competitive analysis, ℓ-immediacy-biased dominates ℓ-MG. That is because at any case that the ℓ-immediacy-biased allocation chooses a T T L = 1 transaction, ℓ-MG would do the same. But any case that ℓ-immediacy-biased allocation chooses the highest-fee transaction; we can force ℓ-MG to do the same by adding a (1, ϵ) with small enough ϵ to the adversary’s schedule at that step. Therefore, we can force ℓ-MG to make the same choices as ℓ-immediacy-biased allocation, without changing the optimal allocation performance. We bound the allocation function’s competitive ratio from below in Lemma 3.4. 4 The Randomized Case Next, Theorem 4.1 obtains an upper bound on the competitive ratio of any allocation function. 4.1 Randomized Upper Bound Theorem 4.1. Given α ̸= 0, for any (possibly randomized) allocation function ALG: Theorem 4.1. Given α ̸= 0, for any (possibly randomized) allocation function ALG: Similarly to the deterministic upper bound, the proof uses a recursive construction of adversaries where the transaction fees grow exponentially. The main technical choice is how to decide the base of the exponent. We guess it by the following equation: 4.2 The RMIXλ Randomized Allocation Function Next, we show that the best-known randomized allocation function known for the undiscounted case [CCFJST06], extends to the more general discount model. Notably, in the semi-myopic range that we identify in Section 3.2, our simple deterministic allocation achieves very similar performance to the above randomized allocation function. Our competitive ratio results are summarized in Fig. 5. Authors:
(1) Yotam Gafni, Weizmann Institute (yotam.gafni@gmail.com);
(2) Aviv Yaish, The Hebrew University, Jerusalem (aviv.yaish@mail.huji.ac.il). Authors: Authors: (1) Yotam Gafni, Weizmann Institute (yotam.gafni@gmail.com); (2) Aviv Yaish, The Hebrew University, Jerusalem (aviv.yaish@mail.huji.ac.il). 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

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

How the Greedy Algorithm Shapes Miner Rewards in Blockchain Networks

EScholar Technologies

Too Long; Didn't Read

Download free Tech Leaders Productivity Report!

Why “Immediacy Bias” Might Be the Secret to Faster, Smarter Blockchain Transactions

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

15 Common Types of Unethical Behavior Found in Open-Source Projects

Modeling Miner Incentives in Discounted Transaction Fee Mechanisms

The Algorithmic Evolution of Blockchain Fee Design

How Auction Theory Shapes Smarter Blockchain Transaction Fee Models

How the Greedy Algorithm Shapes Miner Rewards in Blockchain Networks

15 Common Types of Unethical Behavior Found in Open-Source Projects

Modeling Miner Incentives in Discounted Transaction Fee Mechanisms

The Algorithmic Evolution of Blockchain Fee Design

How Auction Theory Shapes Smarter Blockchain Transaction Fee Models

How the Greedy Algorithm Shapes Miner Rewards in Blockchain Networks

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps