CS Theory at Northeastern

Home Courses Seminar

Computer Science Theory at Northeastern

Click here to subscribe to our mailing list.
Click here to subscribe to our Google Calendar.

Theory Seminar

This semester the theory seminar will be held in a hybrid format on Thursdays 11 AM - 12:30 PM at ISEC 655(map)/online video conference. Write to Anamay Chaturvedi with suggestions for speakers!

Spring Semester, 2022

April 28
ISEC 655 (in-person)/Zoom
Lucianna Kiffer
HaPPY-Mine: Designing a Mining Reward Function

In cryptocurrencies, the block reward is meant to serve as the incentive mechanism for miners to commit resources to create blocks and in effect secure the system. Existing systems primarily divide the reward in proportion to expended resources and follow one of two static models for total block reward: (i) a fixed reward for each block (e.g., Ethereum), or (ii) one where the block reward halves every set number of blocks (e.g., the Bitcoin model of halving roughly every 4 years) but otherwise remains fixed between halvings. In recent work, a game-theoretic analysis of the static model under asymmetric miner costs showed that an equilibrium always exists and is unique [1]. Their analysis also reveals how asymmetric costs can lead to large-scale centralization in blockchain mining, a phenomenon that has been observed in Bitcoin and Ethereum and highlighted by other studies including [2,3].

In this work we introduce a novel family of mining reward functions, HaPPY-Mine (HAsh-Pegged Proportional Yield), which peg the value of the reward to the hashrate of the system, decreasing the reward as the hashrate increases. HaPPY-Mine distributes rewards in proportion to expended hashrate and inherits the safety properties of the generalized proportional reward function established in [4]. We study HaPPY-Mine under a heterogeneous miner cost model and show that an equilibrium always exists with a unique set of miner participants and a unique total hashrate. Significantly, we prove that a HaPPY-Mine equilibrium is more decentralized than the static model equilibrium under a set of metrics including number of mining participants and hashrate distribution. Finally, we show that any HaPPY-Mine equilibrium is also safe against collusion and sybil attacks, and explore how the market value of the currency affects the equilibrium.

  1. Arnosti, N., Matthew Weinberg, S.: Bitcoin: A Natural Oligopoly. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
  2. Gervais, A., Karame, G.O., Capkun, V., Capkun, S.: Is bitcoin a decentralized currency?. IEEE Secur. Privacy 12(3), 54-60 (2014)
  3. Leonardos, N., Leonardos, S., Piliouras, G.: Oceanic Games: Centralization Risks and Incentives in Blockchain Mining. In: Pardalos, P., Kotsireas, I., Guo, Y., Knottenbelt, W. (eds.) Mathematical Research for Blockchain Economy. SPBE, pp. 183-199. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-37110-4_13
  4. Chen, X., Papadimitriou, C., Roughgarden, T.: An Axiomatic Approach to Block Rewards. In: Proceedings of the 1st ACM Conference on Advances in Financial Technologies, pp. 124-131 (2019)
March 31
ISEC 655 (in-person)/Zoom
LaKyah Tyner
Nearly Optimal Property Preserving Hashing
March 24
Zoom/ISEC 655 (screening)
Hongyang Zhang
Principled Methods for Robust Transfer and Generalization of Deep Neural Nets

Fall Semester, 2021

Spring Semester, 2020

Fall Semester, 2019

Spring Semester, 2019

Fall Semester, 2018

Spring Semester, 2018

Fall Semester, 2017

Spring Semester, 2017

Fall Semester, 2016

Spring Semester, 2016

Fall Semester, 2015

Prehistorical Theory Seminars