  The public blockchain was originally conceived to process monetary
transactions in a peer-to-peer network while preventing double-spending. It has
since been extended to numerous other applications including execution of
programs that exist on the blockchain called "smart contracts." Smart contracts
have a major limitation, namely they only operate on data that is on the
blockchain. Trusted entities called oracles attest to external data in order to
bring it onto the blockchain but they do so without the robust security
guarantees that blockchains generally provide. This has the potential to turn
oracles into centralized points-of-failure. To address this concern, this paper
introduces Astraea, a decentralized oracle based on a voting game that decides
the truth or falsity of propositions. Players fall into two roles: voters and
certifiers. Voters play a low-risk/low-reward role that is resistant to
adversarial manipulation while certifiers play a high-risk/high-reward role so
they are required to play with a high degree of accuracy. This paper also
presents a formal analysis of the parameters behind the system to measure the
probability of an adversary with bounded funds being able to successfully
manipulate the oracle's decision, that shows that the same parameters can be
set to make manipulation arbitrarily difficult---a desirable feature for the
system. Further, this analysis demonstrates that under those conditions a Nash
equilibrium exists where all rational players are forced to behave honestly.
