提出伪MDP框架，高效解决以太坊链上最后揭示者攻击的优化难题。
Pseudo-MDPs: A Novel Framework for Efficiently Optimizing Last Revealer Seed Manipulations in Blockchains
- 构建伪MDP框架，将复杂博弈转化为可高效求解的标准MDP问题。
- 将攻击计算复杂度从$O(2^κκ^{2^{κ+2}})$降至$O(κ^4)$（κ=325时）。
- 适合资源受限设备部署，且支持快速收敛与策略提取。
本文针对一类受限问题中的马尔可夫决策过程（MDPs）求解计算挑战展开研究，其动机源于影响以太坊等权益证明（PoS）区块链公平性的“最后揭示者攻击”（LRA）。我们提出伪MDP（pMDPs）框架，自然建模此类问题，并提出两种到标准MDP的归约方法。其中一种归约提供新颖且反直觉的视角，结合两者可显著提升动态规划算法（如值迭代）性能。在以太坊场景下κ=325时，计算复杂度由$O(2^κκ^{2^{κ+2}})$降低至$O(κ^4)$（每轮迭代）。该方法还保证指数级收敛速度。双重视角也简化了策略提取，使方案适用于内存与算力受限的代理。进一步将结果推广至更广泛的MDP类，增强适用性。通过虚构卡牌游戏与以太坊随机种子共识协议上的两例验证，展示了框架对大规模问题的有效求解能力及对最优策略的洞见。本工作推动了MDP研究，并深化了对区块链安全漏洞的理解。
原文摘要 · Abstract (English)
This study tackles the computational challenges of solving Markov Decision Processes (MDPs) for a restricted class of problems. It is motivated by the Last Revealer Attack (LRA), which undermines fairness in some Proof-of-Stake (PoS) blockchains such as Ethereum (\$400B market capitalization). We introduce pseudo-MDPs (pMDPs) a framework that naturally models such problems and propose two distinct problem reductions to standard MDPs. One problem reduction provides a novel, counter-intuitive perspective, and combining the two problem reductions enables significant improvements in dynamic programming algorithms such as value iteration. In the case of the LRA which size is parameterized by $κ$ (in Ethereum's case $κ$= 325), we reduce the computational complexity from $O(2^κκ^{2^{κ+2}})$ to $O(κ^4)$ (per iteration). This solution also provide the usual benefits from Dynamic Programming solutions: exponentially fast convergence toward the optimal solution is guaranteed. The dual perspective also simplifies policy extraction, making the approach well-suited for resource-constrained agents who can operate with very limited memory and computation once the problem has been solved. Furthermore, we generalize those results to a broader class of MDPs, enhancing their applicability. The framework is validated through two case studies: a fictional card game and the LRA on the Ethereum random seed consensus protocol. These applications demonstrate the framework's ability to solve large-scale problems effectively while offering actionable insights into optimal strategies. This work advances the study of MDPs and contributes to understanding security vulnerabilities in blockchain systems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。