Resilient Alerting Protocols for Blockchains

Smart contracts are stateful programs deployed on blockchains; they secure over a trillion dollars in transaction value per year. High-stakes smart contracts often rely on timely alerts about external events, but prior work has not analyzed their resilience to an attacker suppressing alerts via bribery. We formalize this challenge in a cryptoeconomic setting as the \emph{alerting problem}, giving rise to a game between a bribing adversary and~$n$ rational participants, who pay a penalty if they are caught deviating from the protocol. We establish a quadratic, i.e.,~$O(n^2)$, upper bound, whereas a straightforward alerting protocol only achieves~$O(n)$ bribery cost. We present a \emph{simultaneous game} that asymptotically achieves the quadratic upper bound and thus asymptotically-optimal bribery resistance. We then present two protocols that implement our simultaneous game: The first leverages a strong network synchrony assumption. The second relaxes this strong assumption and instead takes advantage of trusted hardware and blockchain proof-of-publication to establish a timed commitment scheme. These two protocols are constant-time but incur a linear storage overhead on the blockchain. We analyze a third, \emph{sequential alerting} protocol that optimistically incurs no on-chain storage overhead, at the expense of~$O(n)$ worst-case execution time. All three protocols achieve asymptotically-optimal bribery costs, but with different resource and performance tradeoffs. Together, they illuminate a rich design space for practical solutions to the alerting problem.