  Algorand is a recent, open-source public or permissionless blockchain system
that employs a novel proof-of-stake byzantine consensus protocol to efficiently
scale the distributed transaction agreement problem to billions of users. In
addition to being more democratic and energy-efficient, compared to popular
protocols such as Bitcoin, Algorand also touts a much high transaction
throughput. This paper is the first attempt in the literature to study and
address this problem. By carefully modeling the participation costs and rewards
received within a strategic interaction scenario, we first empirically show
that even a small number of nodes defecting to participate in the protocol
tasks due to insufficiency of the available incentives can result in the
Algorand network failing to compute and add new blocks of transactions. We
further show that this effect can be formalized by means of a mathematical
model of interaction in Algorand given its participation costs and the current
(or planned) reward distribution/sharing approach envisioned by the Algorand
Foundation. Specifically, on analyzing this game model we observed that mutual
cooperation under the currently proposed reward sharing approach is not a Nash
equilibrium. This is a significant result which could threaten the success of
an otherwise robust distributed consensus mechanism. We propose a novel reward
sharing approach for Algorand and formally show that it is
incentive-compatible, i.e., it can guarantee cooperation within a group of
selfish Algorand users. Extensive numerical and Algorand simulation results
further confirm our analytical findings. Moreover, these results show that for
a given distribution of stakes in the network, our reward sharing approach can
guarantee cooperation with a significantly smaller reward per round.
