Understanding Ergodicity in Markov Decision Processes

Table of Links

Abstract and 1. Introduction

1.1 Related Work

2. Preliminaries

   2.1 System Model

   2.2 Selfish Mining Objective

   2.3 Markov Decision Processes

3. Selfish Mining Attack

   3.1 Overview

   3.2 Formal Model

   3.3 Formal Analysis

   3.4 Key Features and Limitations

4. Experimental Evaluation

5. Conclusion, Acknowledgments, and References

A. NAS Mining Objectives

B. Efficient Proof Systems

C. Proof of Theorem 3.1

C PROOF OF THEOREM 3.1

Proof. Before we prove the theorem, we start by making several observations and introducing additional notation. The proof assumes familiarity with basic notions of Markov chains and MDPs, for which we refer the reader to [22, 26]. First, we observe that every strategy in the MDP M = (𝑆, 𝐴, 𝑃, 𝑠0) gives rise to an ergodic Markov chain. To see this, observe that the initial state 𝑠0 is reached with positive probability from any other state in the MDP, since honest miners with positive probability mine and add new blocks to the main chain for 𝑑 consecutive time steps upon which the MDP would return to the initial state 𝑠0.

Next, we define two auxiliary reward functions in the MDP M:

We are now ready to prove the theorem. To prove the first part of the theorem claim, observe that for each 𝛽 ∈ [0, 1] and for each strategy 𝜎 we have