Distributed Download from an External Data Source in Byzantine Majority Settings

Almost 45 years ago, the Byzantine Generals Problem, which launched the study of Byzantine agreement, was posed as follows:

“We imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action.” [18]

One component of the problem is that each general $v$ must first evaluate the situation and make observations about the enemy that are used to guide its choice of action $x(v)$ (“attack” or “retreat”). The common formal definition of the agreement problem, as given in the literature, abstracts away the observation stage, and considers the action choice $x(v)$ of each general $v$ as its input bit (allowing those bits to differ even among the honest generals).

The Data Retrieval (DR) model [4] “zooms in” on the stage of collecting the observations. Suppose that there are $n$ questions of interest about the enemy, which the generals are required to answer to reach a correct action choice. Denote the answers to these questions (conveniently assumed to be Boolean) by the observation bits $b_1,\mathrm{\dots },b_n$. Making all $n$ observations and learning the entire observations vector $\overline{b}$ is possible but expensive for any single general $v$. The DR model addresses this by allowing the generals to collaborate in order to make all $n$ observations and share the bits $b_i$ correctly. Consequently, each general $v$ can compute its choice $x(v)$ based on the entire observations vector $\overline{b}$.

The original Byzantine Generals problem was introduced to model protocols that function correctly despite the failure of components of a computer system, where perhaps there is no external information that can be independently verified. In contrast, our modified variant of the Byzantine Generals problem can be thought of as a metaphor for scenarios (that are common these days) where there is a need to ascertain factual information that is spread across many sources, and the cost for an individual to validate every fact would be prohibitively expensive. This raises a need for a collaborative protocol to share these costs, where, as in the original Byzantine Generals Problem, there are untrustworthy peers who might communicate false findings.

Formally, our model represents the process of making observations as a trustworthy external “read-only” data source. Making observation $i$ is modeled as sending a query on $b_i$ to this data source. Note that in the DR model, making the right choice is always possible (albeit at a very high cost); each peer can learn each observation bit $b_i$ by querying the source directly. Hence, a significant advantage of this approach is that impossibility concerns are eliminated; reaching an agreement is always possible, for any number of corrupt peers. Instead, the focus shifts to efficiency: the peers must collaborate to share the cost of learning the observation bits from the source.

The DR model consists of a peer-to-peer network and an external data source in the form of an $n$-bit array X. There are $k$ peers, some of which may be Byzantine. They can query information from the array and communicate with each other through messages. The peers initially do not know the array’s contents, but are required to compute some function of the $n$ bits. The peers can learn information about the bits either by querying the data source directly or from other peers. The primary goal is to minimize the maximum number of queries by any honest peer.

The DR model gives rise to a natural class of problems, called retrieval problems. In a retrieval problem, each peer needs to output $f(\text{X})$ for some computable function $f$ of the input. In this work, we focus on the specific problem where $f$ is the identity function, hereafter referred to as the Download problem. We view this as the most fundamental retrieval problem since every computable function $f$ of the input can be computed by the peers by first running a Download protocol and then computing $f(\text{X})$ locally at no additional query, communication, or time cost. Hence, the query cost of the Download problem serves as a baseline against which to compare the costs of other specialized protocols for specific problems. Observe that a lower bound on query complexity for computing any Boolean function on X serves as a lower bound for Download as well.

The DR model was introduced in [4] and was inspired by distributed oracle networks (DONs) which are a part of blockchain systems. In such networks, peers are tasked with retrieving information from external data sources such as stock prices via well-defined Application Interfaces (APIs). Calls to these APIs incur a cost that increases with the oracle’s usage. Thus, reducing the number of API calls also reduces the overall cost of the DON.

The Download problem is easily solved in a query-balanced manner in the absence of failures. This problem becomes challenging in the presence of faults. We consider a synchronous¹¹1The companion paper [6] considers the asynchronous setting, which behaves rather differently. failure-prone setting where up to $\beta k$ peers are Byzantine and at least $\gamma \ge 1-\beta$ fraction are honest. For such systems, a tight bound on query complexity is established in [4] for deterministic Download, complemented by two randomized protocols that solve Download w.h.p.²²2Throughout this paper, we use the term “with high probability” to mean the following: with probability $\ge 1-n^{-c}$, for some constant $c\ge 1$. We often abbreviate the phrase “with high probability” as “whp” or “w.h.p.” The first can tolerate any constant fraction of Byzantine faults but has non-optimal query complexity of $O\left(\frac{n}{\gamma k}+\sqrt{n}\right)$, while the second has optimal query complexity of $\tilde{O}\left(\frac{n}{\gamma k}\right)$ but can only tolerate up to fraction of Byzantine faults³³3We use the $\tilde{O}(\cdot )$ notation to hide $\beta$ factors and polylogarithms in $n$ and $k$.. In this paper, we explore both the query and time complexity of the Download problem, with our main contribution being a novel randomized synchronous protocol that combines the best of both results, achieving optimal query complexity while tolerating any fraction of Byzantine faults.

In this section, we show how to optimize the query complexity of Download up to a factor of $\log n$, achieving $𝒬=O\left(\frac{n\log n}{\gamma k}\right)=\tilde{O}\left(\frac{n}{\gamma k}\right)$ for any . This provides an improvement over the best previously known results for Download [4], which either guaranteed a query complexity of $𝒬=\tilde{O}\left(\frac{n}{\gamma k}+\sqrt{n}\right)$ or imposed the additional restriction of .

The protocol described next works when $2\gamma k>2^{\delta }\cdot {\lg }^{2}n$, for some constant $\delta$⁶⁶6For any positive real number $x$, we use the notation $\lg x$ to denote ${\log }_{2}x$.. Note that, for smaller values of $k$, the desired bound of $\tilde{O}\left(\frac{n}{\gamma k}\right)$ on the query complexity holds trivially: when $k\le \left(\frac{2^{\delta }}{2\gamma }\right)\cdot {\lg }^{2}n$, this bound is $\tilde{O}\left(\frac{n}{\gamma k}\right)=\tilde{O}(n)$, which is attainable by the trivial protocol where every peer queries the entire input vector.

Our protocol runs in $n$ epochs. For $1\le i\le n$, an honest peer $\mu$ dedicates the $i^{\text{th}}$ epoch to learning the $i^{\text{th}}$ input bit. Furthermore, each epoch $i$ is divided into phases. During each phase $j$ of the epoch $i$, $\mu$ attempts to learn the $i^{\text{th}}$ input bit $b_i$ in one of two ways:

1. (i)

   based on messages received from the other peers in earlier phases, or

2. (ii)

   by querying the source directly (which happens with gradually increasing probability).

$\mu$ relies on the messages of its peers for learning $b_i=b$ in phase $j$ only if the number of peers who sent it the value $b$ exceeds a specified threshold (depending on $j$) and the number of peers who sent it the value $(1-b)$ is below that threshold. If $\mu$ fails to learn the bit in phase $j$, then it proceeds to phase $(j+1)$, in which it doubles its probability of querying. This is repeated until $\mu$ successfully learns $b_i$. (Note that a head is always thrown when $2^j$ exceeds $\frac{\gamma k}{\lg n}$).

Once $\mu$ learns $b_i$, it broadcasts it and blacklists any peers that sent contradictory values. In subsequent phases, $\mu$ never relies on bits sent by blacklisted peers. See Algorithm 1 for the pseudocode. Note that in each epoch $i$, $\mu$ learns the value of the $i^{\text{th}}$ bit either by gossip learning (i.e., receiving messages with a decisive majority, in line 9 of the protocol) or by query learning (in line 19). We name the epoch accordingly as a gossip epoch or as a query epoch. Furthermore, in every epoch $i$, $\mu$ performs a “learning step” in exactly one phase, hereafter referred to as the learning phase of epoch $i$ and denoted $\mathrm{\ell }(i)$.

Having established the existence of a query-optimal protocol for Download with an arbitrary bound on the fraction of Byzantine peers, we turn to the issue of time complexity and derive faster Download protocols. In this section, we first establish that any single-round protocol is inefficient, requiring $𝒬=n$. Then, we utilize information theory to show a lower bound on the trade-off between query complexity, time complexity and messages size.

Indistinguishability arguments typically require showing that two carefully constructed executions with different outputs “look the same” from the point of view of at least one peer $\mu$ that is honest in both of them. Hence, the peer $\mu$ will behave the same (and will output the same value) in both executions. In the well-studied Byzantine agreement context, the prover must show that a peer has the same input and will receive the same messages in both executions. In the case of randomized protocols, this becomes more complicated. Even under a fixed adversarial strategy, there is a probability space of executions over the random choices of all the peers. Therefore, we carefully construct probabilistic arguments over these execution spaces to show indistinguishability. In the DR model, these arguments are further complicated by the additional element of queries. Even if we show that the input of an honest peer and the messages it received are the same in both executions if the queries made by this peer in the different executions are not the same, then those executions do not “look the same” from its point of view and we can’t say that it will act the same in the different executions. We obtain the following lower bound.

Due to space considerations, readers interested in the proof details are referred to the full version of the paper [5].

In this section, we show how to reduce the time complexity to $O(\log n)$. Unlike the previous protocol, the protocols here do not use blacklisting and do not require fixed IDs from round to round; only that there is a known lower bound on the number of honest peers present in each round.

We first describe a key definition and a subroutine in these protocols. In a typical step of these protocols, we fix a parameter $\phi$ depending on the round, and the input vector X is partitioned into $𝒦=\lceil n/\phi \rceil$ contiguous subsets of size $\phi$, $\text{X}[\mathrm{\ell },\phi ]=(b_{(\mathrm{\ell }-1)\cdot \phi +1},b_{(\mathrm{\ell }-1)\cdot \phi +2},\mathrm{\dots },b_{\mathrm{\ell }\cdot \phi })$, for $\mathrm{\ell }\in [1,𝒦]$, with the last interval, $(b_{(𝒦-1)\cdot \phi +1},\mathrm{\dots },b_n)$), being possibly shorter. Each honest peer queries all the bits of some interval $\text{X}[\mathrm{\ell },\phi ]$ and broadcasts its findings to all other peers, in the form of a pair $⟨\mathrm{\ell },s⟩$, where $s$ is the bit string obtained from the queries. Hence at the end of a round, every peer receives a collection of strings for different intervals. Let $s[j]$ denotes the $j$-th bit of the string $s$. Note that a message $⟨\mathrm{\ell },s⟩$ can possibly be received in multiple copies, from different peers, and the protocol keeps all copies.

Let $S$ be a multiset of strings for a particular interval $\mathrm{\ell }$ received by peer $\mu$ at the current round. Define the set of $t$-frequent strings at a peer $\mu$ as

Note that the FS function gets a multiset and returns a set of $t$-frequent strings.

A decision-tree $T$ is a rooted ordered binary tree where leaves are labeled with strings and each internal node $v$ is labeled by an index $i$ of the input array such that all the strings $s$ in the left (respectively, right) sub-tree of $v$ has $s[i]=0$ (resp., $s[i]=1$). Given a set of strings FS of which one is consistent with the input array (i.e., it appears exactly in the input array at the specified indices), we can build a decision tree to determine which one of the strings in FS is consistent with the input array with a cost of $|\text{FS}|-1$ queries, by querying the indices associated with all the internal nodes of the decision tree at the same time. The path consistent with the results of these queries reaches a leaf that is labeled by the correct string for the interval. See Algorithm 2.

Byzantine fault tolerance was first introduced by Pease, Shostak, and Lamport [23, 19] in 1980 and has since played a pivotal role in distributed computing. Throughout the 80’s, the focus was on Byzantine Agreement [9, 19, 23, 24] along with some closely related problems like Byzantine Reliable Broadcast (BRB) [1, 14] and Collective Coin Tossing [11, 20]. Subsequently, Lamport introduced state machine replication (SMR) [17], which was extended to Byzantine resilience by Castro and Liskov [12]. SMR lies at the heart of distributed ledgers and blockchains, technologies that have gained popularity in the recent years.

In Byzantine Agreement, depending on the model assumptions and parameters, the Byzantine adversary can use various strategies to misrepresent or suppress critical information and foil agreement. In fact, even if communication is via broadcast, when $\beta \ge 1/2$, half of the input bits can be misrepresented, paving the way for a simple indistinguishability argument that shows that Byzantine Agreement is impossible. When communication is point-to-point (and cryptographic primitives are not used), the Byzantine peers can equivocate, i.e., send inconsistent messages. Exploiting equivocation, a more subtle argument (see Chapter 5 in [3]) can be used to prove that Byzantine Agreement is impossible when $\beta \ge 1/3$.

A natural question then is to ask whether there are reasonable circumstances under which any fixed can be tolerated. The answer is affirmative in a version of the Byzantine Resilient Broadcast [14] that allows peers to digitally sign messages. In the BRB problem, we have a designated leader, known to all peers, that has a message. All other peers must learn that message. The safety requirement of BRB, mandates that every honest peer outputs the same message, while the validity requirement demands that all honest peers must output the leader’s message when the leader is honest. This problem is challenging because the leader may be Byzantine and can try to trick peers into having different views of the input message. Without using cryptographic primitives, BRB can only be solved when . However, BRB can be solved for any when peers can digitally sign messages, a well-known result since the early days [14]. Intuitively, BRB with digital signatures makes it difficult for the Byzantine peers to suppress information or equivocate.

The Download problem first introduced in [4] also admits algorithms for any . The source is accessible to all nodes in the network, which makes it difficult for Byzantine nodes to suppress crucial information or equivocate without being caught. It is worth noting, however, that the Download problem is fundamentally different from BRB and other traditional problems. Unlike those problems, the Download problem admits a trivial protocol, tolerating any even without the use of cryptographic primitives. In fact, each peer can directly query all the bits, but spending that many queries is prohibitively wasteful. Moreover, BRB protocols require active engagement from the leader, for signing messages, applying error-correcting codes and collision resistant hash functions, etc. In contrast, the source in the DR model is a read-only data source with no computational power, and therefore cannot be expected to execute such primitives. Thus, solutions for traditional problems such as BRB do not translate to solutions for Download. Importantly, with impossibility a non-issue for Download, our focus shifts to ensuring optimal query complexity (and other complexities as well) without sacrificing fault tolerance. This work shows that one can achieve both the optimal query complexity (within log factors) and resilience of up to simultaneously. It is also worth noting that while using primitives like BRB for solving Download is possible, our solutions are significantly more efficient.

In this work, we studied the Data Retrieval model, introduced in [4], and improved the previous results on the Download problem by achieving both optimal query complexity and optimal resiliency of any fraction of Byzantine peers. In addition, we presented several new results, including a protocol with $O(\log n)$ time complexity and near-optimal expected query complexity in a model with a dynamic adaptive adversary, and, in the Broadcast model, near-optimal worst case time, query, and message complexity. We also established a lower bound for single-round protocols, demonstrating that it is necessary to query every bit to solve the Download problem within a single round.

Our work is useful in the context of blockchain oracles, specifically, as a sub-routine for data extraction from multiple data sources, where the data sources have some (possibly probabilistic) guarantee of being trustworthy. A relevant question in this context involves handling data that changes over time, such as stock prices or exchange rates. We leave this question open for future exploration, as these temporal changes must be formalized carefully and may require adjustments to the model.