Gaming the Blockchain System: Analyzing Optimal Selfish Mining and Reward Schemes in the Proof-of-Stake Protocol Algorand

Abstract

Cryptographic self-selection is a protocol that is used to select leaders for modern proof-of-stake blockchains such as Algorand. Each round \(r\) has a seed \(Q_r\), and in round \(r\) each account owner signs \(Q_r\), hashes their digital signature to produce a credential, and broadcasts this credential to the entire network. The credentials are scored in a way that matches the distribution of stake owned by each account, and the user who broadcasts the smallest-scoring credential becomes the leader for round \(r\), while their credential becomes the next seed \(Q_{r+1}\). The cryptographic self-selection protocol leaves open the possibility of a selfish mining attack, where a user who owns multiple accounts, each producing a low-scoring credential in round \(r\), can selectively choose which ones to broadcast in order to influence the seed for all future rounds \(r+k\), as \(k \rightarrow \infty\). Specifically, the user can pre-compute their credentials for all future rounds \(r+k\) for each potential seed, and broadcast the credential that produces the most favorable seed.

We reference a formalized model for cryptographic self-selection and the optimal strategy for the adversarial selfish miner, which inform the design of an optimal strategy for the selfish miner and the implementation of a simulation of the strategy's expected rewards. We introduce a new reward scheme that rewards each credential that is broadcasted and investigate its impact on the rewards of the adversary. Our simulations empirically show that that the optimal strategy consistently outperforms the honest strategy and strategies in previous work. We end by providing theoretical guarantees on the accuracy of the simulation's results.