[논문 리뷰] DORA: Distributed Oracle Agreement with Simple Majority

Authors:

Prasanth Chakka, Saurabh Joshi, Aniket Kate, Joshua Tobkin, David Yang

Journal/Conference:

ICDCS '23

Source:

Abstract

Oracle networks feeding off-chain information to a blockchain are required to solve a distributed agreement problem since these networks receive information from multiple sources and at different times. We make a key observation that in most cases, the value obtained by oracle network nodes from multiple information sources are in close proximity. We define a notion of agreement distance and leverage the availability of a state machine replication (SMR) service to solve this distributed agreement problem with an honest simple majority of nodes instead of the conventional requirement of an honest super majority of nodes. Values from multiple nodes being in close proximity, therefore, forming a coherent cluster, is one of the keys to its efficiency. Our asynchronous protocol also embeds a fallback mechanism if the coherent cluster formation fails.
Through simulations using real-world exchange data from seven prominent exchanges, we show that even for very small agreement distance values, the protocol would be able to form coherent clusters and therefore, can safely tolerate up to 1/2 fraction of Byzantine nodes. We also show that, for a small statistical error, it is possible to choose the size of the oracle network to be significantly smaller than the entire system tolerating up to a 1/3 fraction of Byzantine failures. This allows the oracle network to operate much more efficiently and horizontally scale much better.

Introduction

DORA(Distributed Oracle Agreement) problem

Definition: ensuring that all the honest oracle nodes have the same output that is representative of all the honest datasources when all the honest nodes may have different outputs since they may be listening to different sets of data sources at slightly different times. (i.e., BTC prices from different exchanges, wind speed from different sensors, etc.)
Termination & agreement properties are required as same as Byzantine agreement (BA) problem.
Validity property for DORA is more generic: the output will be a value within a range defined by the minimum and maximum honest inputs, where as BA demands that the output be the same as an honest node’s input if all the honest nodes have the same input.
Thus, DORA problem can be considered as a generalized version of BA problem.

Comparison to ChainLink

Chainlink, which is one of the state-of-the-art oracle OCR protocol. (Fig. 1) / Proposed method, which is more scalable (Fig. 2)

One of the state-of-the-art oracle OCR protocol (ChainLink) works as the standard Byzantine agreement problem, while leaving the blockchain as a means to bradcast/publish the agreed-upon set to the world. (Fig. 1)
With the redefined notion of agreement, and utilizing ordering capabilities of the Blockchain, we reduce the number of oracle nodes required to 2f+1 instead of the usual requirement of 3f+1. (Fig. 2)

Contributions

Redefine the agreement notion by introducing a parameter called agreement distance.
Propose a novel protocol that achieves agreement with 2f+1 nodes.
Propose a multi-aggregator model in the protocol to ensure liveness without introducing extra latency of aggregator/leader change.
Demonstrate via empirical analysis of real-world data that most of the time the honest nodes would be able to provide values in very close proximity, therefore, the protocol can function with 2f+1 nodes with very small margins of potential error.
Probability analysis of effects of the size of the network of nodes and the size of the family of aggregators on the safety of the protocol is provided in SectionIV-B. It is evident that with a few hundred nodes in the entire system, and with 10−15 nodes in the family of aggregators, the protocol can function safely with very high probability.

Preliminaries

Property 1: Ideal Representative Value

$$ Ideal_Representative_Value = \sum_{{ds}_j \in DS} o(p_i, ds_j, \tau) / |DS| $$

with following notations,

datasource $ds_j$, the set of total datasources $DS$
honest oracle node $p_i$
observation value of $p_i$ on datasource $ds_j$ : $o(p_i, ds_j, \tau)$

Property 2: Honest Bounded Value

$$ H_{min} \le S \le H_{max} $$

As discussed in the literature*, the agreed value is in the convex hull of the non-faulty nodes’ inputs.

(* H.Mendes and M.Herlihy, “Multi dimensional approximate agreement in byzantine asynchronous systems,” in ACM STOC, 2013, pp.391–400.)

Oracle Protocol

1) Data Feed Collection

At the end of Algorithm 1, $H_{min}(Obs) \le O_{0.5}(Obs) \le H_{max}(Obs)$

2) DORA-CC problem

The requirement of an honest super-majority for DORA can be a scalability issue as the number of oracle nodes increases.
If we assume that inputs from all honest nodes form a coherent cluster within a reasonably small agreement distanced, then we can solve DORA requiring only an honest majority instead of an honest super majority.

3) DORA with Coherent Cluster Protocol

Evaluation

Impact of agreement distance

smaller values of agreement distance -> more frequent fallbacks
higher values of agreement distance -> higher deviation of $S$ from the ideal representative values of the mean of honest values

Impact of size of nodes

(a) Failrue probability decreases exponetially as the size of a family of aggregators increases.
(b) increasing the size of the tribe to a few hundred nodes would ensure that none of the 5 clans randomly drawn from the tribe would have a Byzantine majority with a very high probability.