Astraea: A Decentralized Blockchain Oracle

Ryan Berryhill and Andreas Veneris, University of Toronto

IEEE Blockchain Technical Briefs, March 2019

Discuss this topic on IEEE Collabratec

IEEE Collabratec

 

Introduction

The idea of a public blockchain was first conceived to prevent double-spending while processing monetary transactions in a peer-to-peer network [1]. In its original application, it allows a set of quasi-anonymous and mutually-distrusting parties to reach consensus on the ordering of monetary transactions. It has since been extended to other applications including execution of state machines (i.e., software programs) called “smart contracts” [2] in a decentralized fashion. Smart contracts have a major inherent limitation, as they can only operate on data that is on the blockchain. As a result, trusted entities called oracles attest to external data so as to bring it onto the blockchain. Existing oracles typically do not provide robust guarantees on the accuracy of this data. Trusted oracles are therefore at risk of becoming centralized points-of-failure for decentralized applications that depend on them. This isn't a major issue when the external data can be proven correct either cryptographically (such as data from another Proof-of-Work blockchain [3]), or computationally (such as the outcomes of computations that are infeasible to perform on  as Ethereum [4]).  However, most real-world facts present a challenge for existing oracles.

TLSnotary [5] and TownCrier [6] provide attestations regarding the content of websites accessed using the Hypertext Transfer Protocol Secure (HTTPS) protocol.  Such attestations can be checked cryptographically due to the use of Transport Layer Security (TLS), moving point-of-trust to the website itself. As such, these systems are only suitable in cases where one or more predefined entities are taken to be the arbiters of truth. Augur [7] is a prediction market with a built-in voting-based oracle to determine the outcome of events in order to pay out market participants. While offering greater decentralization by allowing anyone to participate in the oracle mechanism, Augur requires users to pre-register to report the outcomes of events at specific times. This is detrimental to the system’s usability from the perspective of the very users who make the system work.

System Architecture

To address the above-mentioned issues, we have developed Astraea [8] – a general-purpose decentralized oracle to determine the truth or falsity of Boolean propositions. Users of Astraea can participate in one or more of three roles: submitters, voters, and certifiers.  Submitters are clients who need to learn the outcome of Boolean propositions. As such, they provide propositions to the system and pay fees for doing so. Voters play a low-risk/low-reward game in which they are given the opportunity to vote on the truth or falsity of randomly-chosen propositions. Certifiers play a high-risk/high-reward game in which they certify propositions of their choosing as being either true or false. In general, participants may be rewarded when their vote or certification agrees with the majority outcome and may be penalized otherwise.

In Astraea, voters place a small monetary stake to earn the right to vote on a randomly-chosen proposition.  Subsequently, using a commit-reveal scheme, the voter submits a sealed vote of either true or false. A voter is rewarded for her vote on a particular proposition if it agrees with the majority of votes and certifications (explained below) for that proposition. Due to the random selection of propositions for voters, voting is resistant to manipulation by actors seeking to force an incorrect outcome for a particular proposition.

On its own the voting mechanism would be subject to a version of the verifier's dilemma [9] in which, rather than considering the actual propositions, voters simply always vote true or always vote false. To address this issue, Astraea also has a second set of participants called certifiers with different incentives designed to combat the verifier's dilemma. Unlike voters, certifiers place large monetary stakes in order to certify propositions of their choosing as either true or false. A certifier is rewarded for her certification on a proposition if it agrees with the majority of certifiers and the majority of voters and penalized otherwise. A high-level overview of the system’s architecture is shown in Figure 1.

Figure 1

Figure 1: High-level overview of Astraea's architecture.

However, rewards for certifying true and false may be asymmetric. In a situation where many propositions carry true certifications and few carry false certifications, the rewards for certifying propositions as false will be correspondingly higher. This creates a situation where certifiers are required to certify both true and false propositions in order to maximize their rewards. Ultimately, it can be argued that certifiers are incentivized to certify equal numbers of true and false propositions, and to do so honestly.

After a proposition has accumulated a certain number of votes, it is decided as either true or false based on the voting results, and rewards and penalties are administered to participating voters and certifiers. A proposition does not need to carry certifications in order to be decided. At this point, a voter is rewarded if her vote agrees with the majority of voters and certifiers, and penalized if it disagrees with both majorities. In other cases, including the case in which a proposition has no certifications, she receives no rewards or penalties.  By tying the voting rewards to certifier behavior, Astraea is able to avoid the degenerate equilibrium in which all voters always vote with a constant true or false without regard to the actual content of propositions. Since true and false certifications should occur equally often, voters cannot maximize their rewards by always voting true. As such, the equilibrium in which all participants behave honestly is expected to maximize rewards.

Conclusion and Future Work

Astraea is an oracle for blockchain applications built around a voting-based game. Two sets of participants called voters and certifiers work together to determine the truth or falsity of propositions. The mechanism driving voter incentives is resistant to adversarial manipulation. Conversely, the mechanism behind certifier incentives is intended to combat the verifier's dilemma. By combining these two mechanisms, Astraea can achieve a high degree of resistance to adversarial manipulation and degenerate equilibrium behavior. As future work, we intend to explore alternative approaches to solve the verifier’s dilemma and provide a more thorough formal analysis of the system.

 

References

[1] S. Nakamoto, "Bitcoin: A Peer-to-Peer Electronic Cash System," 2008.

[2] G. Wood, "Ethereum: a secure decentralised generalised transaction ledger," 2014.

[3] A. Kiayias, A. Miller and D. Zindros, "Non-interactive proofs of proof-of-work," Cryptology ePrint Archive, Report 2017/963, 2017.

[4] J. Teutsch and C. Reitwiessner, "A scalable verification solution for blockchains," 2017.

[5] "TLSnotary - a mechanism for independently audited https sessions," 2014. [Online]. Available: https://tlsnotary.org/TLSNotary.pdf.

[6] . Zhang, E. Cecchetti, K. Croman, A. Juels and E. Shi, "Town Crier: An Authenticated Data Feed for Smart Contracts," Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, 2016.

[7] J. Peterson, J. Krug, M. Zoltu, A. K. Williams and S. Alexander, "Augur: a Decentralized Oracle and Prediction Market Platform," 2018.

[8] J. Adler, R. Berryhill, A. Veneris, Z. Poulos, N. Veira and A. Kastania, "ASTRAEA: A Decentralized Blockchain Oracle," in IEEE Int'l Conference on Blockchain, Halifax, NS, Canada, 2018.

[9] L. Luu, J. Teutsch, K. Kulkarni and P. Saxena, "Demystifying incentives in the consensus computer," Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, 2015.

 


 

Ryan BerryhillRyan Berryhill (S’15) received the B.A.Sc. degree in computer engineering from the University of Waterloo, Waterloo, ON, Canada, in 2014, and the M.A.Sc. degree in computer engineering from the University of Toronto, Toronto, ON, Canada, in 2016, where he is currently pursuing the Ph.D. degree with the Department of Electrical and Computer Engineering. His current research interests include inductive formal verification and automated formal debugging of hardware and software.

 

Andreas VenerisAndreas Veneris (S’96-M’99-SM’05) received a Diploma in Computer Engineering and Informatics from the University of Patras in 1991, an M.S. degree in Computer Science from the University of Southern California, Los Angeles in 1992 and a Ph.D. degree in Computer Science from the University of Illinois at Urbana-Champaign in 1998. In 1998 he was a visiting faculty at the University of Illinois until 1999 when he joined the Department of Electrical and Computer Engineering and the Department of Computer Science at the University of Toronto where today he is a Professor. His research interests include CAD for debugging, verification, synthesis and test of digital circuits/systems, and combinatorics. He has received several teaching awards and a best paper award. He is the author of one book and he holds several patents. He is a member of IEEE, ACM, AMC, AAAS, Technical Chamber of Greece, Professionals Engineers of Ontario and The Planetary Society.

 

Editor:

Mohammed AtiquzzamanMohammed Atiquzzaman obtained his M.S. and Ph.D. in Electrical Engineering and Electronics from the University of Manchester (UK). He currently holds the Edith Kinney Gaylord Presidential professorship in the School of Computer Science at the University of Oklahoma and is a senior member of IEEE. Dr. Atiquzzaman is the Editor-in-Chief of Journal of Networks and Computer Applications and the founding Editor-in-Chief of Vehicular Communications and has served/serving on the editorial boards of IEEE Communications Magazine, IEEE Transactions on Mobile Computing, International Journal on Wireless and Optical Communications, Real Time Imaging Journal, Journal of Communication Systems, Communication Networks and Distributed Systems, and Journal of Sensor Networks. He also guest edited many special issues in various journals. He has served as the general chair of 4th International Conference on Internet of Vehicles and has served as symposium co-chairs for IEEE Globecom (2006, 2007, and 2014, 2016) and IEEE ICC (2007, 2009, 2011, and 2012, 2014, 2016 2017) conferences. He co-chaired ChinaComm (2008) served as general chair of 2017 International Conference on Smart Internet of Things (SmartIoT 2017) and the SPIE Quality of Service over Next Generation Data Networks conferences (2001, 2002, 2003, and 2005). He was the panels co-chair of INFOCOM’05 and is/has been in the program committee of numerous conferences such as INFOCOM, ICCCN, and Local Computer Networks. He serves on the review panels of funding agencies such as the National Science Foundation and National Research Council (Canada) and Australian Research Council (Australia).

Mohammed received from IEEE the 2018 Satellite and Space Communications Technical Recognition Award for valuable contributions to the Satellite and Space Communications scientific community. He also received the 2017 Distinguished Technical Achievement Award from IEEE Communications Society in recognition of outstanding technical contributions and services in the area of communications switching and routing. In recognition of his contribution to NASA research, he received the NASA Group Achievement Award for “outstanding work to further NASA Glenn Research Center’s effort in the area of Advanced Communications/Air Traffic Management’s Fiber Optic Signal Distribution for Aeronautical Communications” project. He is the co-author of the book “Performance of TCP/IP over ATM networks” and has over 270 refereed publications, which are accessible at www.cs.ou.edu/~atiq. His research interests are in communications switching , transport protocols, wireless and mobile networks, ad hoc networks, satellite networks, quality of service, and optical communications. His research has been funded by National Science Foundation (NSF), National Aeronautics and Space Administration (NASA), Us Air Force, Cisco, Honeywell, Oklahoma Department of Transportation, Oklahoma Highway Safety Office through grants totaling over $7M.

 


 

Subscribe to the IEEE Blockchain Technical Briefs

Join our Blockchain Technical Community and receive our Technical Briefs by email.

Subscribe Now


Article Contributions Welcomed

IEEE Blockchain Technical Briefs Editorial Guidelines for Authors (PDF, 115 KB)

If you wish to have an article considered for publication, please contact the Managing Editor at
blk-editor@ieee.org.


Best of IEEE Blockchain Technical Briefs

Read the top five most popular IEEE Blockchain Technical Briefs articles of 2018.
Read more (PDF, 731 KB)


Past Issues

March 2019

January 2019

December 2018

September 2018

July 2018


IEEE Blockchain Technical Briefs Editorial Board

Chonggang Wang, Editor-in-Chief
Olivia Choudhury, Managing Editor
Mohammed Atiquzzaman
Nathan Aw
Claire-Isabelle Carlier
Raymond Choo
Francisco Curbera
Mahmoud Daneshmand
Andy Lippman
Chengnian Long
Qinghua Lu
Ammar Rayes
Khaled Salah
Weisong Shi
Hong Wan
Honggang Wang
Jiang Xiao
Zheng Yan
Shucheng Yu
Yan Zhang