Kaya Alpturer will present his General Exam "Optimal RANDAO Manipulation" on May 12, 2025 at 12:30pm in CS 301.

Committee: Matt Weinberg (adviser),  Mark Braverman, Pramod Viswanath

All are welcome to attend the talk.

Abstract:

It is well-known that RANDAO manipulation is possible in Ethereum if an adversary controls the proposers assigned to the last slots in an epoch. We provide a methodology to compute, for any fraction α of stake owned by an adversary, the maximum fraction f(α) of rounds that a strategic adversary can propose. We further implement our methodology and compute f(⋅) for all α. For example, we conclude that an optimal strategic participant with 5% of the stake can propose a 5.048% fraction of rounds, 10% of the stake can propose a 10.19% fraction of rounds, and 20% of the stake can propose a 20.68% fraction of rounds.



  • Roughgarden, Tim. Twenty lectures on algorithmic game theory. Cambridge University Press, 2016.

  • Dwork, Cynthia, Nancy Lynch, and Larry Stockmeyer. "Consensus in the presence of partial synchrony." Journal of the ACM (JACM) 35.2 (1988): 288-323.

  • Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. "Impossibility of distributed consensus with one faulty process." Journal of the ACM (JACM) 32.2 (1985): 374-382.

  • Yin, Maofan, et al. "HotStuff: BFT consensus with linearity and responsiveness." Proceedings of the 2019 ACM symposium on principles of distributed computing. 2019.

  • Cleve, Richard. "Limits on the security of coin flips when half the processors are faulty." Proceedings of the eighteenth annual ACM symposium on Theory of computing. 1986.

  • Eyal, Ittay, and Emin Gün Sirer. "Majority Is Not Enough: Bitcoin Mining Is Vulnerable." International Conference on Financial Cryptography and Data Security. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014.

  • Sapirshtein, Ayelet, Yonatan Sompolinsky, and Aviv Zohar. "Optimal selfish mining strategies in bitcoin." Financial Cryptography and Data Security: 20th International Conference, FC 2016, Christ Church, Barbados, February 22–26, 2016, Revised Selected Papers 20. Springer Berlin Heidelberg, 2017.

  • Cai, Yang, Nikhil R. Devanur, and S. Matthew Weinberg. "A duality based unified approach to bayesian mechanism design." Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. 2016.

  • Beyhaghi, Hedyeh, and S. Matthew Weinberg. "Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items." Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 2019.

  • Roughgarden, Tim. "Transaction Fee Mechanism Design." Journal of the ACM 71.4 (2024): 1-25.

  • Heilman, Ethan, et al. "Eclipse attacks on {Bitcoin’s}{peer-to-peer} network." 24th USENIX security symposium (USENIX security 15). 2015.

  • Matheus V. X. Ferreira, S. Matthew Weinberg. “Proof-of-Stake Mining Games with Perfect Randomness” EC 2021.