Table of Links
Abstract and 1. Introduction
1.1 Our Approach
1.2 Our Results & Roadmap
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
- A. Missing Proofs for Sections 2, 3
- B. Missing Proofs for Section 4
- C. Glossary
A: Missing Proofs for Sections 2, 3
We now note that a few facts that hold true for any n when x1 ≥ ℓ + ϵ:
We separate to several subcases:
B Missing Proofs for Section 4
We now compare ALG and ADV ’s performance in different steps along the adversary schedule, separating the steps before n and the last two steps.
Step i < n.
ALG expected performance:
Notice that this amortization of considering the i + 1 is only relevant for ADV, as ALG in such case necessarily has no transactions remaining to choose from at step i + 1.
where the last transition is since for any 0 ≤ λ ≤ 1, the expression
We now move on to analyze steps n, n + 1.
ALG expected performance at step n, n + 1:
As the base case, consider k = n. Then,
For the inductive step,
We thus need to show that
With this potential function, we can thus write at step i,
C Glossary
A summary of all symbols and acronyms used in the paper.
C.1 Symbols
ψ Transaction schedule function.
x Allocation function.
B Predefined maximal block-size, in bytes.
λ Miner discount factor.
ϕ Transaction fee of some transaction, in tokens.
T Miner planning horizon.
ℓ Immediacy ratio for our non-myopic allocation rule.
µ TTL of past transactions.
α Miner’s relative mining power, as a fraction. u Miner revenue.
t TTL of a transaction.
tx A transaction.
C.2 Acronyms
mempool memory pool
PoS Proof-of-Stake
PoW Proof-of-Work
QoS quality of service
TFM transaction fee mechanism
TTL time to live
:::info
Authors:
(1) Yotam Gafni, Weizmann Institute (yotam.gafni@gmail.com);
(2) Aviv Yaish, The Hebrew University, Jerusalem (aviv.yaish@mail.huji.ac.il).
:::
:::info
This paper is available on arxiv under CC BY 4.0 DEED license.
:::
[2] The argument of [CCFJST06] is done by showing conditions that hold for any fixed x ∈ [−1, 0], and so they hold for any fixed x ∈ [−λ, 0] as well.
