PaperlayerView exact revision on arXiv

Source-linked AI summary

Astraea: A Decentralized Blockchain Oracle

John Adler, Ryan Berryhill, Andreas Veneris, Zissis Poulos, Neil Veira, Anastasia Kastania

arXiv:1808.00528v1cs.CR

TL;DR

Smart contracts cannot directly use external data, while existing oracles may lack blockchain-level security and create centralized points of failure. ASTRAEA addresses this with a public-ledger voting game involving low-risk voters and high-risk certifiers. Its analysis shows that bounded-fund manipulation can be made arbitrarily unlikely and that honest play forms a Nash equilibrium under stated conditions.

  • Problem

    Smart contracts cannot directly determine the validity of data outside the blockchain, while existing oracles may lack robust blockchain security and create centralized points of failure.

  • Method

    ASTRAEA uses a public-ledger voting game in which voters stake on randomly selected propositions and certifiers place larger stakes on propositions they choose.

  • Results

    The analysis shows that system parameters can make successful manipulation by bounded-fund adversaries arbitrarily unlikely and support an all-honest Nash equilibrium under the same conditions.

  • Takeaways & Limitations

    ASTRAEA provides a decentralized, trustless, and permissionless oracle design whose incentive structure is intended to make rational players behave honestly under stated assumptions.

Abstract

from arXiv · show

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.

I. INTRODUCTION

Blockchains support consensus over on-chain data and computations, but smart contracts cannot directly determine facts outside the blockchain. ASTRAEA proposes a voting-based decentralized oracle and analyzes its security and incentives.

  • Motivation: Smart contracts can operate only on data already stored on the blockchain, limiting their interaction with external facts.Ethereum can reach consensus on computations, but not on the validity of externally sourced data.
  • Motivation: Existing oracles may lack native blockchain security and can create centralized points of failure when external facts are not cryptographically or computationally verifiable.TLS-based attestations cannot guarantee that all visitors see identical information, and websites may manipulate outputs.
  • ASTRAEA: ASTRAEA uses a public-ledger voting game with submitters, low-risk voters, and high-risk certifiers to determine Boolean propositions.Voters stake small amounts on randomly selected propositions, while certifiers stake large amounts on propositions they choose.
  • ASTRAEA: Voting is designed to resist targeted manipulation through random proposition selection, while certification rewards agreement and penalizes disagreement with voter outcomes.Votes and certifications are sealed and revealed only after the process.
  • Analysis: The analysis shows that bounded-fund adversaries can be assigned an arbitrarily small manipulation probability, while honest play forms a Nash equilibrium under the same conditions.The paper also argues that certification avoids profitable constant-true or constant-false coordination strategies.

B. Oracles

Oracles connect smart contracts with external data, but existing approaches retain security, centralization, or trust limitations. ASTRAEA addresses the stated need for a decentralized, trustless, and permissionless oracle under explicit belief assumptions.

  • B. Oracles: Smart contracts cannot directly act on external data because deterministic execution requires publicly verifiable inputs stored on the blockchain.Oracles are therefore needed to connect blockchains with real-world information such as event outcomes.
  • System assumptions: ASTRAEA models Boolean propositions with truth values and player beliefs, assigning each player an accuracy probability.Player beliefs are assumed independent across players and propositions.
  • Existing proposals: Existing oracle proposals trade off centralization, performance, and scope, and several depend on centralized systems, token distribution, or trusted hardware.The cited examples include ChainLink, Oraclize.it, Gnosis, Delphi, and Town Crier.
  • Research gap: The paper identifies the absence of a truly decentralized, trustless, and permissionless oracle as the motivating gap.ASTRAEA is presented as a response to that gap.

IV. ASTRAEA

ASTRAEA organizes proposition validation into submitter, voter, and certifier roles within a decentralized voting-based oracle. Voters stake on random propositions, whereas certifiers choose propositions and accept larger risks.

  • Overview: ASTRAEA presents a decentralized voting-based oracle whose operation and game-theoretic properties are analyzed.The system description covers roles, voting, certification, and subsequent equilibrium analysis.
  • Roles: Submitters fund propositions, voters play a low-risk/low-reward random-assignment game, and certifiers play a high-risk/high-reward proposition-selection game.Voting and certification outcomes are computed from stake-weighted sums.
  • Voters: Voters stake before learning which uniformly random proposition they will evaluate, reducing targeted control over a particular proposition.The maximum voting deposit is a system parameter.
  • Certifiers: Certifiers choose available propositions and place large deposits to certify them as true or false.Not every proposition receives certification, and the minimum certification deposit should impose substantial risk.
  • Parameters: Parameter selection is central: a maximum voting deposit equal to 100% of a proposition’s stake gives an adversary total outcome control, whereas 1% makes control require repeated draws.The passage uses these values to illustrate the security tradeoff.

B. The Proposition List

ASTRAEA operates over an externally constructed proposition list with fixed size, hidden truth values, and associated bounties. Propositions are decided after sufficient voting stake, then removed and replaced.

  • B. The Proposition List: The proposition list P has fixed size |P|, and each proposition p_i has a hidden truth value t_i and bounty B_i.The list is constructed outside ASTRAEA.
  • B. The Proposition List: The proposition list may be populated through mechanisms such as an auction whose prices become proposition bounties.The construction procedure is outside the paper’s scope.
  • B. The Proposition List: After termination, a proposition is decided, rewards and penalties are administered, and the proposition is removed from the list.A new proposition may replace it through another auction.
  • B. The Proposition List: Voting and certification stakes are represented separately for each player, proposition, and truth value, with s_max and σ_min defining maximum voting and minimum certification stakes.These parameters distinguish the low-stake voting and high-stake certification mechanisms.
  • B. The Proposition List: Players may act as voters, certifiers, or both; voters follow a multistep random-assignment process, while certifiers submit one-step certifications to chosen propositions.The architecture depicts these differing interactions with propositions.

2) Certifying:

Astraea separates participation into voting and certifying, computes each outcome from stake-weighted totals, and uses majority rules to determine true, false, or unknown results.

  • 2) Certifying:: Certifiers submit a stake and a sealed certification of true or false for a proposition they choose.An honest certifier certifies according to their belief about the proposition.
  • 2) Certifying:: A proposition is decided after accumulating the system’s required voting stake Dv.The system then computes total voting and certifying stakes for both true and false positions.
  • 2) Certifying:: Simple majority determines both voting and certification outcomes, while ties produce an unknown outcome Ø.The system can alternatively require a super-majority, producing Ø when neither side reaches the threshold.
  • 2) Certifying:: The game and oracle outcomes are organized across the nine combinations of voting and certification results.Table III uses certification results as columns and voting results as rows.
  • 2) Certifying:: The game recognizes true, false, and unknown outcomes, while the oracle output may follow a suggested mapping or represent confidence in [0, 1].The suggested mapping follows voting when it agrees with certification or when certification is unknown.

D. Rewards and Penalties

Astraea converts voting and certification positions into rewards or penalties, with distinct incentives for correct positions and special treatment of unknown outcomes.

  • D. Rewards and Penalties: Participants are rewarded for positions matching true or false outcomes and penalized for opposing positions.In unknown outcomes, certifiers are penalized while voters receive neither rewards nor penalties.
  • D. Rewards and Penalties: Rewards and penalties are represented by rv for voting and rc for certification, with negative values denoting penalties.The resulting values are summarized in the paper’s reward table.
  • D. Rewards and Penalties: For a true outcome, a voter receives their share of true voting stake times the proposition bounty and loses their false-voting stake.The voting reward and penalty are described separately in the true-outcome case.
  • D. Rewards and Penalties: A certifier’s true-outcome reward equals their share of true certifying stake multiplied by RT and divided by the certification target τ.For example, RT = 1000 and τ = 10 distributes 100 monetary units to certifiers.
  • D. Rewards and Penalties: False outcomes use reward and penalty rules analogous to those for true outcomes.The paper states that the false-outcome rewards and penalties are similar.

2) Unknown Outcome:

ASTRAEA analyzes how voting accuracy, system parameters, and adversarial stake affect incorrect outcomes. Its reward structure penalizes certifiers in unknown outcomes and can make manipulation arbitrarily difficult under suitable conditions.

  • 2) Unknown Outcome:: Certifiers forfeit all stake in unknown outcomes, while voters receive neither rewards nor penalties because their propositions were selected randomly.This asymmetric treatment reflects certifiers’ choice to certify a proposition versus voters’ lack of choice.
  • 2) Unknown Outcome:: Reward pools are funded by unclaimed bounties and penalties, with the system expected to approach an incentive-balanced equilibrium.Initially empty certifier pools can make certification rare and leave most bounties unclaimed.
  • 2) Unknown Outcome:: Reward-pool transfers encourage certifiers to assess similar numbers of true and false propositions, discouraging constant T or F strategies.For true outcomes, funds are paid to certifiers when certification also yields T; otherwise they are added to the false pool, with the symmetric rule for false outcomes.
  • 2) Unknown Outcome:: The analysis relates system parameters to incorrect-voting probabilities, voter profitability, honest-play equilibrium, and resistance to constant-output strategies.The model first treats voting on one proposition as a sequence of smax-stake Bernoulli trials with honest-voter accuracy q.
  • 2) Unknown Outcome:: 99.7% is the approximate probability of a correct voting outcome when Dv = 20, smax = 1, and voter accuracy q = 0.8.This example models the outcome using a binomial random variable.
  • 2) Unknown Outcome:: Increasing both proposition-list size |P| and decision stake Dv makes adversarial manipulation more difficult.The passage states that both parameters appear in the denominator of the manipulation probability.
  • 2) Unknown Outcome:: 95% voter accuracy with Dv = 100 · smax makes manipulation effectively impossible even when an adversary controls 25% of votes.The analysis states that suitable parameters can make forced incorrect outcomes arbitrarily unlikely, and Table V reports probabilities across several conditions.

B. Minimum Voting Accuracy

This section derives how voter accuracy relates to profitability and shows how bounty caps can enforce a minimum accuracy threshold. The analysis explicitly notes that this threshold omits several voter costs.

  • B. Minimum Voting Accuracy: ASTRAEA quantifies the minimum voter accuracy needed for expected profitability as a function of the system parameters.The analysis assumes incorrect decisions are negligible and defines accuracy as the probability that a player’s belief matches the proposition’s truth value.
  • B. Minimum Voting Accuracy: A vote is profitable in expectation when its expected share of voting rewards exceeds its expected penalties.Unknown outcomes are excluded because voters receive neither rewards nor penalties in that case.
  • B. Minimum Voting Accuracy: Capping the bounty can make voting unprofitable below a selected accuracy threshold.The paper derives an upper bound on the bounty to enforce this threshold.
  • B. Minimum Voting Accuracy: For 80% desired accuracy with Dv = 1000, the bounty must be capped at 250 monetary units; for 50%, it must be capped at 1000.These thresholds are lower bounds because the analysis omits time, computing, and blockchain transaction costs.

C. Desirable Nash Equilibrium

ASTRAEA has a Nash equilibrium in which rational players behave honestly when voting outcomes are correct and honest voters are sufficiently accurate and numerous.

  • C. Desirable Nash Equilibrium: Honest play is an equilibrium when every voting outcome is correct and only feasible strategies are considered.Rewards go only to players agreeing with the voting outcome.
  • C. Desirable Nash Equilibrium: Independent beliefs prevent players from using correlated strategies to exceed their individual accuracy when voting or certifying honestly.Players cannot implement a perfect strategy because they do not know the underlying truth values.
  • C. Desirable Nash Equilibrium: Even an adversary controlling all certifying stake is incentivized to act honestly or abstain, because other strategies lose the entire stake.This conclusion applies under the stated correct-outcome and feasible-strategy conditions.

D. Proposition Bias and Reward Pools

ASTRAEA’s reward pools counter a lazy always-true voting strategy by shifting certification incentives as proposition bias drains one pool faster than the other.

  • D. Proposition Bias and Reward Pools: A lazy voter always votes true when true propositions are more common than false ones.This strategy agrees with correct outcomes on true propositions but disagrees on false propositions.
  • D. Proposition Bias and Reward Pools: Because certification is required for rewards, certifier incentives must be considered when evaluating whether lazy voting is profitable.Certifier incentives are tied to reward pools whose values fluctuate over time.
  • D. Proposition Bias and Reward Pools: When the true-proposition probability exceeds 0.5, the true-certification reward pool drains faster than the false-certification pool, which may grow.The changing pool values alter certifier incentives over time.
  • D. Proposition Bias and Reward Pools: At equilibrium, roughly equal certification of true and false propositions makes the lazy strategy unprofitable.Certifiers are not incentivized to label true propositions false because disagreement with voters incurs a penalty.

VI. EXTENSION TO UNKNOWN PROPOSITIONS AND DATA AVAILABILITY

ASTRAEA is extended to handle propositions without clear truth values and off-chain proposition storage while preserving protections against inappropriate player penalties.

  • VI. EXTENSION TO UNKNOWN PROPOSITIONS AND DATA AVAILABILITY: The extension addresses unclear propositions and data availability in practical ASTRAEA implementations.It is designed to handle two implementation issues simultaneously.
  • VI. EXTENSION TO UNKNOWN PROPOSITIONS AND DATA AVAILABILITY: Unknown propositions can arise when voters are randomly assigned questions whose truth is not established, such as whether P equals NP.Such propositions do not support a clear true-or-false vote for every voter.
  • VI. EXTENSION TO UNKNOWN PROPOSITIONS AND DATA AVAILABILITY: Off-chain proposition storage can identify propositions through an immutable public hash because blockchain storage is relatively expensive.The extension therefore accommodates data availability outside the blockchain.
  • VI. EXTENSION TO UNKNOWN PROPOSITIONS AND DATA AVAILABILITY: Voters who mark propositions unknown receive neither rewards nor punishments, while certifiers abstain from participating.The game’s reward structure otherwise remains unchanged.
  • VI. EXTENSION TO UNKNOWN PROPOSITIONS AND DATA AVAILABILITY: The extension protects players from penalization when submitters provide unclear propositions or withhold data.The analysis of the system’s desiderata follows straightforwardly from the original analysis.
Loading 1808.00528v1…