论文标题
有效的MDP分析用于区块链中的自私开采
Efficient MDP Analysis for Selfish-Mining in Blockchains
论文作者
论文摘要
工作证明（POW）区块链协议根据其在总计算能力中所占的份额向其参与者（称为矿工）分发奖励。足够大的矿工可以进行自私的采矿 - 偏离协议以获得超过其公平份额。因此，如果所有矿工都小于阈值大小，则此类系统是安全的，因此他们的最佳响应遵循协议。 为了找到阈值，必须确定不同大小的矿工的最佳策略，即解决马尔可夫决策过程（MDP）。但是，由于POW难度调整机制，矿工的效用是非线性比率函数。因此，我们将其称为平均奖励比率（ARR）MDP。 Sapirshtein等人是第一个通过求解一系列收敛到ARR MDP解决方案的标准MDP来求解ARR MDP的人。 在这项工作中，我们提出了一种通过求解单个标准MDP来解决ARR MDP的新技术。我们方法的症结在于增加MDP，以便在预期的回合数量内随机终止。我们称此概率终止优化（PTO），该技术适用于其效用是比率函数的任何MDP。我们绑定了PTO的近似误差 - 它与终止前的预期回合数量成反比，这是我们控制的参数。从经验上讲，PTO的复杂性比艺术的状态低一个数量级。 PTO可以轻松地应用于不同的区块链。我们用它来收紧以太坊自私开采的阈值的界限。
A proof of work (PoW) blockchain protocol distributes rewards to its participants, called miners, according to their share of the total computational power. Sufficiently large miners can perform selfish mining - deviate from the protocol to gain more than their fair share. Such systems are thus secure if all miners are smaller than a threshold size so their best response is following the protocol. To find the threshold, one has to identify the optimal strategy for miners of different sizes, i.e., solve a Markov Decision Process (MDP). However, because of the PoW difficulty adjustment mechanism, the miners' utility is a non-linear ratio function. We therefore call this an Average Reward Ratio (ARR) MDP. Sapirshtein et al.\ were the first to solve ARR MDPs by solving a series of standard MDPs that converge to the ARR MDP solution. In this work, we present a novel technique for solving an ARR MDP by solving a single standard MDP. The crux of our approach is to augment the MDP such that it terminates randomly, within an expected number of rounds. We call this Probabilistic Termination Optimization (PTO), and the technique applies to any MDP whose utility is a ratio function. We bound the approximation error of PTO - it is inversely proportional to the expected number of rounds before termination, a parameter that we control. Empirically, PTO's complexity is an order of magnitude lower than the state of the art. PTO can be easily applied to different blockchains. We use it to tighten the bound on the threshold for selfish mining in Ethereum.
