Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

Problem Statement

Oracle systems are used to bring real-world data to Blockchain. The most common example is reporting the asset price information, including the cryptocurrencies' prices.

Existing Work

Overview

The Oracul system is based on the SchellingCoin concept introduced by Vitalik. The values are reported in decentralized fashion. Every party reports a value and assigns a deposit to it. At the exersice time the median is computed and returned as the final value. Then the deposits are reassigned so that the reports that are far from median are penalized in favor of the ones whose reporting values were closer to the median.

Oracul Token

One of the criticisms of the SchellingCoin concept is the fact that a rich party can manipulate the system, forcing it to both return a wrong value and reassign the sincere reporters' deposits to the attacker. This is mitigated by the usage of system-specific tokens as deposits. The attacker should invest money in acquiring the 51% of the tokens, which will severely lose value after performing the 51% attack ("fake altruism").

In addition to the voting weight, the token owners are entitled to the proportional share of the system's comission.

Having domain-specific tokens encourages users not only to report similar values (to stay closer to the median), but also values that are actually true, because otherwise the Oracul won't be used as a data feed, hence less comission collected, which results in token depreciation.

Reporting

The introduction of domain-specific tokens makes it possible to report unobscured values, as strategy "report the same value as the first reporter" is suboptimal: if this value is not true, the tokens will depreciate in value. (this point should be validated)

Once the deadline passes, the median of all the reported values, weighted by deposit, is considered the final value and returned to the consumers.

The reporters of values that are far from the final median should be penalized to discourage wrong reports. Part of their deposit should be distributed among the other reporters.

We choose a fixed Δ that represents a spread tolerance range for the reported value. If Δ == 0, every report except the median is penalized proportinally to its distance from the median. If Δ > 0, all the reports within this range are considered valid and get share of penalties of the reports that fall outside of this range.

For the values that have a natural, exact true value we can choose a very low Δ. For others (e.g. ETH/USD that can be different depending on exchange), we can take a larger Δ. For example, for Δ == 0.05 and the true value (median) == 100, all the reports between 95 and 105 are considered valid and get their shares of the comission and the deposits of other reports. The closer the reported value is to the median, the bigger share of the penalty and comission collected it is eligible for.

Penalties

For the reports that fall outside of the spread tolerance range the penalty is computed as the difference between the reported value and the closest edge of the spread tolerance range relative to the median.

Rewards

Only the reports that fall within Median +- Δ are eligble for rewards. The rewards consist of the following:

  • Comission - fixed amount in ETH payed by the consumers
  • Penalties - the Oracul tokens that were confiscated from the reporters of values that are far from median. Can equal to zero if everyone's values are within Median +- Δ.

The rewards are distributed proportionally to the distance of their report to the median. First a reward multiplier is assigned to each report depending on this distance:

  • The reports that fall exactly on the median get maximum share of the reward pool (1x)
  • The other reports get lower share. The ones that are exactly in the middle between the median and edge of spread tolerance range only get half the rewards (0.5x)
  • The reports on the edges of the spread tolerance range don't get any rewards - 0x. Please note that they are also not penalized, as described above

Then the total reward pool is distributed among this reporters according to multipliers set.

In this example Δ == 0.05 and the final median is 100, so the spread tolerance range is [95,105]. The comission accumulated is 1.

deposit report penalty rewards (multiplier) deposit returned comission earned
1 105 0 0x 1 0
1 104 0 0.2x 1 + 0.57 / 3.2 * 0.2 = 1.035625 1 / 3.2 * 0.2 = 0.0625
1 102 0 0.6x 1.106875 0.1875
1 112 7% 0x 1 - 0.07 = 0.93 0
1 100 0 1x 1.178125 0.3125
1 99 0 0.8x 1.1425 0.25
1 98 0 0.6x 1.106875 0.1875
1 90 5% 0% 0.95 0
1 50 45% 0% 0.55 0

The total penalty is 1 * 0.07 + 1 * 0.05 + 1 * 0.45 = 0.57, the total multiplier is 0.2x + 0.6x + 1x + 0.8x + 0.6x = 3.2x. Thus, the total payout for the reporter with multiplier 0.2x is 0.57 / 3.2 * 0.2 = 0.035625.

Round Structure

  • Bets are placed along with the deposits in Oracul tokens;
  • median is resolved;
  • penalties and multipliers are computed for every participant;
  • once all of them are computed, they are distributed in accordance to the multipliers.
  • comission is also distributed along with the multipliers.

Implementation Considerations

Current Oracul implementation works entirely on-chain and it's crutial to keep the gas costs as low as possible, making sure that the block gas limit is never exceeded. To achieve that, all the operations in current implementation are at most o(ln(n)) where n is the number of different values reported in active round.

The round structure described above consists of a few actions, although they can be performed within at most two requests per reporter per round. This is achieved by performing the previous round finalization and repoting of a new value witinin a single smart contract invocation. To claim the comission and the penalties collected a new call is needed, as it can only be done when all the multipliers and comissions are finalized.

Data Structure

We need a data structure that stores the votes along with their weights. It should have the following properties:

  • The weighted median can be computed in o(ln(n))
  • New votes can be added in o(ln(n))

The proposed data structure is a Weighted Order Statistic Tree. A Red-Black tree is chosen as base data sctructure. It is implemented on-chain. in addition to the color, every node stores an addition value, which is the size of the subtree rooted in this node. In a classical Order Statistics Tree this number represents the number of nodes, but we use the sum of weights of nodes, so that we can efficiently compute the weighted median.

Let size[x] = size[left[x]] + size[right[x]] + weight[x], where size[nil] = 0 by definition. Then the select operation (find the i'th smallest element stored in the tree, where i indexes the weights, not the elements - so that select(totalWeight / 2) computes the weighted median) can be implemented as:

  function select(seekingIndex, node) {
    if (node.left.size < seekingIndex && node.left.size + node.weight >= seekingIndex) {
      return node.value;
    }

    if (node.left.size >= seekingIndex) {
      return select(seekingIndex, node.left);
    }

    return this.select(seekingIndex - (node.left.size + node.weight), node.right);
  }

Reporting Pools

An ordinary token holder is not supposed to have enough time and resources to report the price every round. We need a way to make it easy for the participants to report the price in a reliable and convinient way. To achieve that, we build a number of on-chain reporting pools. A reporting pool is a smart contract that reports values that are computed based on agreed in advance algorithm. There will be reporting pools linked to the major exchanges. The implementation is straightforward: the pool resolves the value from exchange API (e.g. with Oraclize) and reports it forward to Oracul. Token holders deposit their stakes to one or multiple reporting pools. Thereafter they can withdraw their stack along with their share of comission and the earned/lost tokens, in accordance to the pool's performance.

The reporting pools are expected to form the overwhelming majority of the voting power. In practice, there are normally not many sources of truth for the values reported. Therefore, there is no need to spend extra gas sending the same value multiple times. For the ETH/USD price oracle, it is the biggest exchanges who act as the source of truth. We build a reporting pool for every exchange and let token holders decide which exchange's price do they want to report. Token holders have to weigh how reliable their APIs are, and if some exchange experiences problems, they have to be proactive in removing their tokens from the corresponding reporting pool.

Some of the reporting pools might report aggregated values, like "Coinmarketcap" (it provides an average price from different exchanges, weighted by volume). Many token holders are likely to choose such a reporting pool, which is reasonable, but makes the corresponging website's API a single point of failure. Therefore, alternative reporting pools will be introduced: they should report the same (or very similar) value, but it should be computed without relying on the same website API.

Having reporting pools is also good for the transparancy: it will be clear which amount of the total voting power belongs to which pool (i.e. which exchange API / algorithm). If it's apparent that too much value is concentrated in a single reporting pool, the token holders are supposed to shift their tokens to another pool that reports perhaps same values but acquires them in a different way. Otherwise the holders risk the depreciation of their tokens.

Such reporting pools are not hard to buid on-chain so that they are trustless and every user is guaranteed to get their share of tokens back.

Comission

There must be comission collected to incentivise token holders to report every round. There is no point in charging everyone accessing the data, as once reported, data can be made accessible by a different contract for free. So, the comission should only be collected once per round. Consumers must agree on the comission share off-chain. (validate this point)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment