# Vers: fully distributed Coded Computing System with Distributed Encoding

Nastaran Abadi Khooshemehr, Mohammad Ali Maddah-Ali
Sharif University of Technology, University of Minnesota
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
##  I Abstract

Coded computing has proved to be useful in distributed computing, and has
addressed challenges such as straggler workers. We have observed that almost
all coded computing systems studied so far consider a setup of one master and
some workers. However, recently emerging technologies such as blockchain,
internet of things, and federated learning introduce new requirements for
coded computing systems. In these systems, data is generated (and probably
stored) in a distributed manner, so central encoding/decoding by a master is
not feasible and scalable. This paper presents a fully distributed coded
computing system that consists of $k\in\mathbb{N}$ data owners and
$N\in\mathbb{N}$ workers, where data owners employ workers to do some
computations on their data, as specified by a target function $f$ of degree
$d\in\mathbb{N}$. As there is no central encoder, workers perform encoding
themselves, prior to computation phase. The challenge in this system is the
presence of adversarial data owners that do not know the data of honest data
owners but cause discrepancies by sending different versions of data to
different workers, which is detrimental to local encodings in workers. There
are at most $\beta\in\mathbb{N}$ adversarial data owners, and each distributes
at most $v\in\mathbb{N}$ different versions of data. Since the adversaries and
their possibly colluded behavior are not known to workers and honest data
owners, workers compute tags of their received data, in addition to their main
computational task, and send them to data owners in order to help them in
decoding. We introduce a tag function that allows data owners to partition
workers into sets that previously had received the same data from all data
owners. Then, we characterize the fundamental limit of this fully distributed
coded computing system, denoted by $t^{*}$, which is the minimum number of
workers whose work can be used to correctly calculate the desired function of
data of honest data owners. We show that $t^{*}=v^{\beta}d(K-1)+1$, and
present converse and achievable proofs.

##  II Introduction

Coded computing utilizes coding theory techniques to address the fundamental
challenges in distributed computing systems such as straggler mitigation,
security, and privacy preservation, and communication bandwidth issues [1].
The core idea in coded computing is to inject data or computation redundancy
in order to accomplish the mentioned goals. For instance, coded computing can
be used to accomplish a computation task by using the work of faster worker
nodes, and not being dependent on any specific set of workers (straggler
mitigation). This line of research has received so much attention, and many
aspects of it have been explored, see [2] for a survey on coded distributed
computing. However, almost all coded computing researches consider a setup of
one master (also called other names like parameter server) and several
workers, where the master encodes the data, distributes the data and
computation tasks among workers, collects the partial results from workers,
and constructs the final result. The following reasons motivate us to pursue a
different path from the centralized, single-master coded computing systems.

  * •

In a distributed computing system where a single master encodes the whole
initial data and then decodes all of the results, the master would be a
bottleneck for scalability. As the number of workers grows, the master should
get more powerful, in terms of computation and communication.

  * •

In some applications like federated learning [3], the data for computation
tasks are not congregated in one place, for reasons like the privacy of the
data owners, and/or the huge volume of data. Thus, one master does not have
access to the whole data.

  * •

Computation schemes that are specifically designed for distributed sources of
data are better suited for applications where the production of data is
distributed by nature, like sharded blockchains, federated learning, and
internet of things.

  * •

In practice, a cluster of servers that act as workers, would serve more than
one master, and do computation tasks for several masters in parallel. In this
way, the resources of workers would be efficiently utilized, and not left
idle.

A few works have studied masterless coded computing or coded computing with
several masters. In [4], a fully-decentralized and masterless setup,
consisting of only $N\in\mathbb{N}$ workers, has been considered. In such a
setup, decentralized coding strategies for two particular computation tasks,
matrix multiplication, and fast Fourier transform, have been introduced. In
matrix multiplication of two arbitrary matrices $\mathbf{A}$ and $\mathbf{B}$,
each worker has a portion of $\mathbf{A}$ and $\mathbf{B}$ initially. Then,
each worker performs local encoding on its initial data, communicates with
other workers, and then multiplies two matrices. At the end of the algorithm,
each worker has a portion of the calculated $\mathbf{AB}$. Note that the
encodings done by workers, are on their own initial data, and not on data
received from other workers. We will argue that distributed encoding of data
received from external sources introduces new challenges.

In [5], several masters, each with a matrix-vector multiplication task, share
some workers, and the workers have heterogeneous computing powers. The problem
is to assign computation tasks to workers such that the overall completion
time is minimum. Each worker either serves one master or several masters and
divides its computation power between them. In the latter case, each worker
simply performs the computation tasks of the masters separately, and no coding
is involved. In [6], there are $N\in\mathbb{N}$ workers, where each has a
piece of data, and wants to have a linear combination of all data. There is no
master and workers exchange messages with one another in a communication-
efficient way, to calculate their target linear combinations. [7] considers a
network graph of $N\in\mathbb{N}$ nodes each with an initial value, where a
subset of them wants to calculate some arbitrary functions of the initial
values. The target function of each node in that subset could be different. In
order to achieve this goal, an iterative linear strategy is deployed in which
nodes receive messages from their neighbours and obtain a linear combination
of the received values and their own value, without any leader. Given the
graph of nodes has some particular connectivity properties, a finite number of
rounds suffices for nodes to calculate the desired functions of initial
values, using the linear combinations obtained in the previous iterations. A
similar problem with the presence of adversaries is studied in [8], where
adversaries may calculate the linear combinations incorrectly and send
incorrect values to their neighbours. The adversaries do not send different
values to different neighbours, and may only deviate in calculating the linear
combination of the messages of their neighbours and their own message.

Coded computing can be designed to guarantee security in an adversarial
environment, as in [9, 10, 11, 12]. In the conventional setup of a single
master and many workers, the security of the coded computing scheme translates
to the resilience of the scheme against adversarial workers, because in such
setups, the master is assumed to be honest. Adversarial workers can freely
deviate from the protocol, e.g. return an arbitrary result, send different
data to different workers, refuse to send data, and so forth. However, when
there are several masters, it is reasonable to assume that some masters might
be adversarial as well.

In this paper, we study a coded computing system comprised of several masters
and workers, where masters employ workers to accomplish computational jobs for
them. We refer to masters as data owners, as each of them has a piece of data,
and aims to have a polynomial target function of that data by using workers.
Some of the data owners are adversarial and try to create discrepancies in the
system, in order to cause errors in the computation tasks of honest data
owners. There are communication links between data owners and workers, and
also between adversarial data owners, since they can collude with one another.
However, like many coded computing systems [1, 2], there is no communication
means between workers in our system. The system works as follows. The data
owners distribute their data among workers, but adversarial data owners may
distribute different contradictory data to different workers, to corrupt the
results. The adversarial data owners are free to cooperate in choosing what
they send to workers. Upon the reception of data, each worker encodes the
received data of all data owners, applies the target function on the encoded
data, and then returns the result back to data owners, along with a small tag
of the received data, to inform the honest data owners about the adversarial
data owners indirectly. Tags allow honest data owners to partition workers
into sets who have received the same message from the adversaries in the first
step, and enables honest data owners to decode the results. Finally, the
honest data owners can extract their required information from the returned
results of the workers.

We name the described system Vers, which is short for versatile. The reason
for this naming is that the workers are indeed versatile, and do a range of
different tasks: they encode the received data, calculate the target function
of the coded data, and calculate tags. We study the fundamental limit of Vers
in the case where Lagrange encoding is deployed in workers. This fundamental
limit, which we denote by $t^{*}$, is the minimum number such that honest data
owners can correctly and reliably extract their required information from the
results of any set of $t^{*}$ workers. In other words, for any adversarial
behavior, any set of $t^{*}$ workers should be enough for honest data owners
to calculate the target function of their data correctly. On the other hand,
for $t^{*}$ to be the minimum indeed, there should exist an adversarial
behavior and a set of $t^{*}-1$ workers whose results do not determine the
target of honest data owners uniquely. It is worth noting that in our previous
work [13], we have studied the fundamental limit of a system in which some
data owners want to store their data in some storage nodes, such that data can
be correctly retrieved later. In that system, some data owners are adversarial
and may send different data to different storage nodes.

The type of adversarial behavior in our problem, i.e. adversaries sending
inconsistent data to other nodes, has been explored from different points of
views in a wide range of distributed systems, such as byzantine agreement [14,
15, 16], byzantine broadcast [17, 18, 19], verifiable information dispersal
[20, 21, 22], and distributed key generation [23]. Even though the adversarial
behaviour has been previously known, addressing such behaviour in the context
of distributed computing systems like blockchain, federated learning and
internet of things is very underexplored. The distinction between this work
and the mentioned ones that consider a similar adversarial model is that we
deal with computation, rather than consensus. Our goal is to correctly
calculate functions of a subset of data, and this does not necessarily require
consensus on that data before calculation. Generally, inconsistencies caused
by the adversaries need to be resolved somehow, for which there are two main
approaches: nodes can either resolve the inconsistencies between themselves by
communicating with one another, or they can postpone dealing with
inconsistencies to subsequent steps such as decoding. The first approach is
pursued in many works such as [20], where nodes exchange enough information
with each other to extract consistent data and then use that consistent data
in their main task. Since in our model, there is no communication link between
workers, they cannot detect the adversarial data owners and then mitigate
their effect by exchanging information with one another. Therefore, the first
approach alone is not sufficient. In this work, we choose a combination of
these approaches for our particular model: we deal with inconsistencies in the
final step in decoding, with help of tags that workers had previously produced
and communicated to the data owners.

The structure of this paper is as follows. We formulate the problem in Section
III, and state the main result in Section VIII. Then, explain the concept of
tag functions in Section VI and introduce a good tag function. We define some
notions and analyze the system in Section VII. Finally, we state the
fundamental limit of the system in Section VIII.

##  III problem formulation

In this section, we formally introduce
$\textrm{Vers}(f,N,K,\beta,v,\textrm{Enc})$, a fully distributed linear coded
computing system with parameters $f,N,K,\beta,v$, and encoding algorithm Enc.
Consider a system of $K\in\mathbb{N}$ data owners and $N\in\mathbb{N}$ worker
nodes, indexed $1,\dots,K$, and $1,\dots,N$, where $K\leq N$. We denote the
set $\\{1,\dots,m\\},m\in\mathbb{N}$ with $[m]$, and $\\{0,1,\dots,m\\}$ with
$[m^{+}]$. The data owner $k\in[K]$ has $X_{k}\in\mathbb{U}$ and wants to have
$f(X_{k})$, where $f:\mathbb{U}\rightarrow\mathbb{V}$ is an arbitrary
polynomial function of degree $d\in\mathbb{N}$, called target function, and
$\mathbb{U},\mathbb{V}$ are vector spaces over a finite field $\mathbb{F}$.
Data owners employ workers to do the calculations for them, in a distributed
manner. Among the data owners, there are at most $\beta\in\mathbb{N}$
adversarial nodes, $\beta<K$. We denote the set of adversarial data owners by
$\mathcal{A}\in[K]$, and the set of honest data owners by
$\mathcal{H}=[K]\setminus\mathcal{A}$. The adversarial data owners try to
cause discrepancies in order to mislead honest data owners about the correct
values of $f(X_{k})$, $k\in\mathcal{H}$. The adversarial data owners sacrifice
their chance to use workers for their calculations, and hence, do not want any
specific correct computation at the end. The adversarial data owners are free
to cooperate with each other, but they do not know the data of the honest
nodes. We assume that all workers are honest. Moreover, honest data owners and
workers do not know the adversarial data owners.

We design Vers by using inspirations from [12]. In the following, we describe
the workflow of Vers in detail. The workflow is also shown in Algorithm 1. In
the first step, data owners transmit their data to the workers. Let $X_{k,n}$
be the message sent from data owner $k\in[K]$ to worker node $n\in[N]$. An
honest data owner $k\in\mathcal{H}$ sends $X_{k}$ to all workers, i.e.
$X_{k,n}=X_{k}$ for all $n\in[N]$. We assume that $X_{k},k\in\mathcal{H}$ are
chosen independently and uniformly at random from $\mathbb{U}$. An adversarial
data owner $k\in\mathcal{A}$ generates at most $v\in\mathbb{N}$ different
messages, which we denote by versions, $X_{k}^{(1)},\dots,X_{k}^{(v)}$, and
sends one of them to each worker. In other words,
$\\{X_{k,n},n\in[N]\\}=\\{X_{k}^{(1)},\dots,X_{k}^{(v)}\\}$, for
$k\in\mathcal{A}$. Adversarial data owners can generate up to $v$ messages of
their choice and can send any one of them to any worker they choose. The
adversarial data owners may also collude so that their aggregate adversarial
behavior is as detrimental as possible.

In the second step, worker node $n$ who has received $X_{1,n},\dots,X_{K,n}$
from data owners, computes a linear combination of the $K$ received messages,
denoted by $W_{n}\in\mathbb{U}$, using the encoding algorithm Enc. Let
$\gamma_{k,n}\in\mathbb{F},k\in[K]$ be the $K$ encoding coefficients of worker
$n$ that the encoding algorithm Enc determines. Therefore,

$\displaystyle W_{n}=\sum_{k\in[K]}\gamma_{k,n}X_{k,n},\quad n\in[N].$ (1)

We emphasize that encoding in Vers in done in a decentralized fashion, and
locally in each worker. This is the main idea of Vers that differentiates it
from other coded computing systems that incorporate a central encoder. After
local encoding of the received messages, in step 3, worker $n$ computes
$f(W_{n})$, where $f$ is the target function.

In addition to $W_{n}$, and $f(W_{n})$, worker node $n$ computes
$\mathsf{tag}_{n}=J(X_{1,n},\dots,X_{K,n})$ in step 4, where
$J:\mathbb{U}\rightarrow\mathbb{W}$ is a tag function, and $\mathbb{W}$ is a
vector space over $\mathbb{F}$. We will formally introduce tag function in
Section VI. Intuitively, a tag function compresses its $K$ inputs, and outputs
a fingerprint of inputs, so that outputs of two different sets of $K$ inputs
are almost always different.

In the fifth step, worker node $n$ sends $\mathsf{tag}_{n}$ and $f(W_{n})$ to
all data owners. Honest data owners can use tags to identify workers whose
received messages were the same in the first step, and therefore, their
returned computation results are consistent. In the sixth step, the honest
data owner $k\in[K]$ uses
$\\{f(W_{n}),n\in\mathcal{T}\\}\cup\\{\mathsf{tag}_{n},n\in\mathcal{T}\\}$,
where $\mathcal{T}$ is an arbitrary subset of $[N]$ of size $t\in\mathbb{N}$,
to recover $f(X_{k})$. An example
$\textrm{Vers}(f,N=5,K=3,\beta=1,v=2,\textrm{Enc})$ is shown in Fig 1.

Algorithm 1 The workflow of Vers

1:The honest data owner $k\in\mathcal{H}$ sends $X_{k}$ to all workers. The
adversarial data owner $k\in\mathcal{A}$ generates at most $v\in\mathbb{N}$
different messages $X_{k}^{(1)},\dots,X_{k}^{(v)}$, and sends one of them to
each worker.

2:Worker node $n\in[N]$ computes $W_{n}\in\mathbb{U}$ as a linear combination
of the $K$ received messages from data owners, using the encoding algorithm
Enc, and according to (1).

3:Worker node $n\in[N]$ computes $f(W_{n})$.

4:Worker node $n\in[N]$ computes $\mathsf{tag}_{n}=J(X_{1,n},\dots,X_{K,n})$,
where $J:\mathbb{U}\rightarrow\mathbb{W}$ is a tag function, and $\mathbb{W}$
is a vector space over $\mathbb{F}$.

5:Worker node $n\in[N]$ sends $\mathsf{tag}_{n}$ and $f(W_{n})$ to all data
owners.

6:An honest data owner $k$ recovers $f(X_{k})$ from
$\\{f(W_{n}),n\in\mathcal{T}\\}\cup\\{\mathsf{tag}_{n},n\in\mathcal{T}\\}$,
where $\mathcal{T}$ is an arbitrary subset of $[N]$ of size $t\in\mathbb{N}$.

$\displaystyle X_{1}^{(1)}$$\displaystyle X_{1}^{(1)}$$\displaystyle
X_{1}^{(2)}$$\displaystyle X_{1}^{(2)}$$\displaystyle X_{1}^{(2)}$ (a) The
orange nodes (top row) are data owners, and the red nodes (bottom row) are
workers. Data owners send their data to workers. Here, the first data owner is
an adversary and sends two different messages $X_{1}^{(1)}$ and $X_{1}^{(2)}$
to workers.

$\displaystyle\begin{array}[]{{>{\displaystyle}l}}f(W_{1})\\\
\text{tag}_{1}\end{array}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}{\color[rgb]{0.45,0.42,0.42}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.42,0.42}f(W_{3})}\\\
{\color[rgb]{0.45,0.42,0.42}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.42,0.42}\text{tag}_{3}}\end{array}$
(b) Workers apply $f$ on coded input, calculate tags, and return the results
to data owners.

Figure 1: $\textrm{Vers}(f,N=5,K=3,\beta=1,v=2,\textrm{Enc})$ is shown as an
example (only some of the messages between data owners and workers are shown).
The leftmost data owner is adversarial.

######  Remark 1.

Note that each worker node calculates a single tag in the fourth step of Vers.
Therefore, the total communication of Vers is $O(N)$, i.e. linear in $N$. Data
owners use the indirect information from these tags to partition workers into
sets that have received the same adversarial data from the adversarial data
owners. Another possible design is having each worker calculate $K$ tags, one
for each data received from the $K$ data owners. The direct information from
such tags reveals the identities of adversarial data owners for honest data
owners. However, such design results in $O(KN)$ communication load, and
hinders scalability when $K$ grows. As previously stated in Section II, one of
the main purposes of Vers is to compensate for scalability bottlenecks of
single master systems. Therefore, in Vers, we incorporate the communication
efficient single tag method, to allow $K$ to scale. Another intermediate
approach is to have each worker calculate a constant number of tags of the $K$
received messages. This method probably gives more information about the
adversarial behaviour to honest data owners. However, due to its complexity,
we do not address this approach in this paper, and leave it for future
research.

The formal definition of fundamental limit is as following.

######  Definition 1 (The fundamental limit of Vers).

The fundamental limit of $\textrm{Vers}(f,N,K,\beta,v,\textrm{Enc})$, which we
denote by $t^{*}(f,N,K,\beta,v,\textrm{Enc})$, is the minimum $t$ required
such that $f(X_{k}),k\in\mathcal{H}$ can be correctly computed from
$\\{f(W_{n}),n\in\mathcal{T}\\}$, and
$\\{\mathsf{tag}_{n},n\in\mathcal{T}\\}$, under any adversarial behavior,
where $\mathcal{T}$ is any arbitrary subset of $[N]$ of size $t$.

No matter how the adversaries choose and distribute their $v$ different
messages $X_{k}^{(1)},\dots,X_{k}^{(v)},k\in\mathcal{A}$ to workers,
$f(X_{k}),k\in\mathcal{H}$ should be correctly extractable from
$\\{f(W_{n}),n\in\mathcal{T}\\}$ and $\\{\mathsf{tag}_{n},n\in\mathcal{T}\\}$.
This should hold for any subset of workers of size
$t^{*}(f,N,K,\beta,v,\textrm{Enc})$, for the system to be robust against
stragglers and node failures which is common in distributed systems. Note that
we do not set any requirement on being able to find all or any of
$f(X_{k}^{(1)}),\dots,f(X_{k}^{(v)})$, $k\in\mathcal{A}$, from
$\\{f(W_{n}),n\in\mathcal{T}\\}$, and
$\\{\mathsf{tag}_{n},n\in\mathcal{T}\\}$. This is because the adversaries give
up their chance of using workers for computation, to cause inconsistency in
the system. In fact, there exist adversarial behaviors for which it is not
possible to find all of $f(X_{k}^{(1)}),\dots,f(X_{k}^{(v)})$. For example,
consider the case where all adversarial data owners $k\in\mathcal{A}$ send
$X_{k}^{(1)}$ to workers $1,\dots,N-1$, and $X_{k}^{(2)}$ to worker $N$. In
this case, there is not enough information to find
$f(X_{k}^{(2)}),k\in\mathcal{A}$ from any set of equations. Therefore, in
order to avoid complex scenarios, we define the fundamental limit based on the
requirement to find only $f(X_{k}),k\in\mathcal{H}$. In Section VIII, we
characterize the fundamental limit of
$\textrm{Vers}(f,N,K,\beta,v,\textrm{Lagrange})$. In other words, we choose
Lagrange encoding as Enc algorithm in
$\textrm{Vers}(f,N,K,\beta,v,\textrm{Enc})$, set $\gamma_{k,n}$ in (1)
accordingly, and then find $t^{*}(f,N,K,\beta,v,\textrm{Lagrange})$.

######  Remark 2.

The challenging part of Vers is the last step where the data owners decode the
results of workers because the adversarial data owners had injected
inconsistencies in the received data of workers. In this work, data owners
deal with inconsistencies in decoding and use tags to determine subsets of
workers whose results are consistent. Another approach is to resolve the
inconsistencies right in the first step, by using a reliable broadcast
algorithm, e.g. [24], for the message of each data owner, instead of having
data owners simply send messages to workers. This approach requires
communication between workers to help them reach a consensus on the received
data from each data owner.

##  IV Applications of Vers

The motivation for studying Vers is that we can use it to model a variety of
emerging computing systems in the presence of adversaries, such as internet of
things networks and blockchains. In this section, we elaborate on some
applications of Vers.

In an IoT network, since sensors and devices are resource-constrained, they
cannot process the data generated in them. Therefore, they need to offload the
computations to external nodes, i.e. workers in Vers, to calculate complex
target functions of their data. Thus, Vers can easily be used to model an IoT
network of resource-constrained devices. Data owners in Vers are equivalent to
devices in IoT network. Workers in Vers are equivalent to external
computational nodes in IoT network. The target function in Vers is equivalent
to any processing function that devices in IoT network require. For example,
suppose that in agriculture, IoT is used for smart irrigation. Some devices
need to know the efficient amount of water needed, which is a function of soil
moisture, weather conditions and ambient temperature, crop type, and possibly
more features. Such function can be modeled by target function in Vers.

The adversarial data owners in Vers are equivalent to adversarial IoT devices,
which include tampered and infected ones (e.g. see [25]). The adversarial
devices may deliberately send inconsistent data to computational nodes, in
order to mislead the decision making process of other devices. For example,
suppose that IoT is used to deploy smart home, and some devices have been
tampered with and try to affect the correct functionality of the smart lock on
the door. Since IoT devices are resource-constrained, the upper limit on the
different messages of adversarial data owners in Vers applies to them. The
fundamental limit of the Vers model of an IoT network specifies the number of
external computational nodes that are required for the system to be robust
against the adversarial devices.

Vers can also be used to model blockchains, and in particular, sharded
blockchains. In a blockchain network of $N\in\mathbb{N}$ nodes, nodes
collectively process transactions, produce blocks of transactions, distribute
the blocks, and also validate them. Blockchain is indeed the agreed-upon chain
of blocks, and whenever nodes reach consensus on a new block, that block is
appended to the chain. In a fully replicated blockchain system, such as
Bitcoin, each node repeats what other nodes do. Such decentralized approach
provides high security against adversaries, because no node relies on another
node, but its throughput (the number of confirmed transactions per second)
fails to scale due to its replication. Over the past few years, there has been
extensive research into how to make blockchains scalable [26, 27]. A notable
line of research in this regard, is sharding which is inspired by the idea of
parallel computing. Recently, Ethereum, the most popular blockchain platform,
introduced Danksharding [28], which is a novel sharding protocol, and is going
to deploy it in near future.

In vanilla sharding, e.g. [29, 30], blockchain nodes are divided into groups
called shards, say $M\in\mathbb{N}$ shards. shards run in parallel, such that
each shard of $\frac{N}{M}$ nodes has a local chain and produces its own
blocks. The allocation of nodes to shards can be random, or other methods. The
purpose of sharding is to increase the throughput by $M$ times. However, a
shard of $\frac{N}{M}$ nodes, and thus the whole sharded system, is more
vulnerable to security attacks in comparison to $N$ nodes. For example,
carrying out a 51% attack on a shard of $\frac{N}{M}$ nodes is easier for an
adversary, compared to a system of $N$ nodes. In order to preserve security
and scale the blockchain simultaneously, the concept of coded sharding was
first introduced in [31] and named PolyShard.

Unlike vanilla sharding where nodes in a shard work on their own blocks, in
Ployshard, all nodes in all shards work on coded blocks. Polyshard works as
following. In round $t\in\mathbb{N}$, each shard $m\in[M]$ needs to validate
its new block $B_{m}^{t}$. Shards broadcast their blocks to all nodes. Each
node $n$ calculates a coded block $\tilde{B}^{t}_{n}$ from the received blocks
$B_{1}^{t},\dots,B_{M}^{t}$, using Lagrange coding. To put it more clearly,
each node $n$ makes a Lagrange ploynomial whose coefficients are constructed
from $B_{1}^{t},\dots,B_{M}^{t}$, and then evaluate that in a point
$\alpha_{n}$ to obtain $\tilde{B}^{t}_{n}$. Then, nodes apply the block
verification function111Block verification function is determined by the
consensus algorithm of the blockchain system. $g$ on coded blocks that they
calculated previously, instead of applying that $M$ times on all $M$ blocks
separately. Validation of blocks in round $t$ requires data of blocks in
previous rounds $1,2,\dots,t-1$. Each node $n$ stores coded chain of blocks in
each round, evaluated at point $\alpha_{n}$, rather than only blocks of its
own shard. Therefore, it can use its stored coded local chain until round
$t-1$ when verifying its coded block in round $t$. Nodes broadcast their
results of verification in the network. In this step, adversaries may
broadcast arbitrary erroneous values. Nodes can obtain the verification of
$B_{1}^{t},\dots,B_{M}^{t}$ by decoding the verifications of coded blocks, and
the adversaries’ effect translates into errors in decoding data. The main
result of [31] is that the throughput and security222The number of adversarial
nodes that the system is resilient against. of this scheme scales linearly
with $N$, while the storage requirement of nodes does not need to scale.

The adversarial model in [31] is limited to adversaries that broadcast an
incorrect value instead of the verification result of their coded block. Even
in that case, the adversaries send the same incorrect value to all nodes, and
the consistency of the system is maintained. However, in a decentralized
system like blockchain, adversarial nodes can freely deviate from the
protocol. In [32], we introduced the discrepancy attack on PolyShard, in which
the adversaries take control of some shards and adversarial shards disseminate
different blocks to different nodes. This causes error in coded blocks of
nodes and disrupts the validation process, and breaks the scalability of
security in Polyshard.

Vers is a comprehensive system that can model a coded sharding blockchain in
the presence of adversaries as following. Data owner $k\in[K]$ in Vers is
equivalent to the representative of shard $k$ in blockchain that propagates
the new block of its shard in the network. Note that under the discrepancy
attack, the representative of shard $k$ may be adversarial. Data $X_{k}$ of
data owner $k$ in Vers is equivalent to block $B_{k}$ of shard $k$ in the
current round. Workers in Vers are equivalent to nodes of the network in
blockchain. The target function $f$ in Vers is equivalent to block
verification function $g$ in blockchain. In Vers, data owner $k$ needs
$f(X_{k})$, and in blockchain, nodes of shard $k$ need the result of the
verification function of $B_{k}$. The fundamental limit of the Vers model of a
coded sharding blockchain specifies the number of nodes that are required for
the system to be robust against the adversarial shards.

##  V Main result

The following theorem states the main result.

######  Theorem 1.

The fundamental limit of $\textrm{Vers}(f,N,K,\beta,v,\textrm{Lagrange})$ is
$t^{*}=v^{\beta}d(K-1)+1$.

This result implies that $N\geq v^{\beta}d(K-1)+1$ should hold. Otherwise,
even when there is no straggler or faulty worker, and all workers send their
computations back to data owners, data owners would not be able to recover
$f(X_{k}),k\in\mathcal{H}$.

Since the fundamental limit is the minimum number of workers whose results are
enough to correctly recover $f(X_{k}),k\in\mathcal{H}$, two proofs are needed
for Theorem 1. Firstly, in converse proof, we need to prove that $t^{*}$ is
truly the minimum, which means there should exist a particular adversarial
behaviour and a set of $t^{*}-1$ workers whose results do not determine
$f(X_{k}),k\in\mathcal{H}$ uniquely. But this is not as simple as showing a
system of equations is underdetermined. Note that the honest data owners do
not know the adversarial behaviour, so they do not know the correct way to
form equations from the results of workers, even with the help of tags.
Consequently, honest data owners need to consider every possible system of
equations from the results of workers. Moreover, since Lagrange coding is
used, $f(X_{k}),k\in\mathcal{H}$ are not directly the unknowns of the
equations of workers, rather, they are linear combinations of the unknowns. In
the converse proof, we show that there exists a possible interpretation of the
results of workers that leads to at least one incorrect output for
$f(X_{k}),k\in\mathcal{H}$. We provide the converse proof in Subsection
VIII-A.

Secondly, in the achievable proof, we need to prove that any set of $t^{*}$
workers is enough to correctly recover $f(X_{k}),k\in\mathcal{H}$. Again, this
should hold for any adversarial behavior, despite the existence of many
possible interpretations of the results of workers. We provide the achievable
proof in Subsection VIII-B.

######  Remark 3.

The fundamental limit of $\textrm{Vers}(f,N,K,\beta=0,v,\textrm{Enc})$, i.e.
when all data owners are honest, is not different from the fundamental limit
of a similar system in which a central entity encodes the data and sends the
encoded data to workers, because the encoded data in workers would be the
same. Indeed, the challenge in Vers is due to the adversarial data owners that
inject contradictory data in the system, and the resulting error that
propagates through local encodings in workers. The coded computing system
studied in [12] includes a central encoder, but it is essentially similar to
$\textrm{Vers}(f,N,K,\beta=0,v,\textrm{Lagrange})$, and its so called recovery
threshold is equivalent to the fundamental limit of
$\textrm{Vers}(f,N,K,\beta=0,v,\textrm{Lagrange})$. Therefore, using the
result of [12], we know that the fundamental limit of
$\textrm{Vers}(f,N,K,\beta=0,v,\textrm{Lagrange})$ is
$t^{*}(f,N,K,\beta=0,v,\textrm{Lagrange})=d(K-1)+1$, where $d$ is the degree
of the target polynomial function $f$.

##  VI Tag functions

In Algorithm 1, step 2, we explained that workers compute a tag of their
received messages. In this section, we introduce the concept of tags, and
prove the existence of a tag function that can be deployed in
$\textrm{Vers}(f,N,K,\beta,v,\textrm{Enc})$.

Recall that each adversarial data owner $k\in\mathcal{A}$ distributes
$X_{k}^{(1)},\dots,X_{k}^{(v)}$ among workers. The honest data owners that
receive $f(W_{n})$ from a worker $n\in[N]$ after step 5 of Algorithm 1, do not
know which one of the $v$ messages of the adversaries this worker has received
and has used in $W_{n}$. Therefore, honest data owners do not know which
workers have used the same set of input messages in their calculations. The
purpose of tag is to inform the honest data owners about the data used by
workers. Tags allow data owners to partition $[N]$ into some sets, at most
$v^{\beta}$ sets, where each set contains workers that have received the same
messages from all data owners in the first step.

Let us denote the concatenation of all $X_{k},k\in\mathcal{H}$, i.e. the data
of the honest data owners, with $X_{\mathcal{H}}$. Also let
$X_{\mathcal{A},n}$ be the concatenation of all $X_{k,n},k\in\mathcal{A}$,
i.e. the messages of the adversarial data owners received by worker $n\in[N]$.
Worker $n\in[N]$ applies the tag function $J$ on $X_{1,n},\dots,X_{K,n}$, but
since $\\{X_{1,n},\dots,X_{K,n}\\}=\\{X_{\mathcal{H}},X_{\mathcal{A},n}\\}$
for all $n\in[N]$, we exploit the notation and use
$J(X_{\mathcal{H}},X_{\mathcal{A},n})$. We define a tag function formally as
follows.

######  Definition 2 (Tag Function).

A function $J:\mathbb{U}^{K}\rightarrow\mathbb{U}^{l}$, $l<k$, is a tag
function if for two adversaries that choose two different $X_{A,n_{1}}$ and
$X_{A,n_{2}}$ independently from $X_{\mathcal{H}}$, and send them to workers
$n_{1},n_{2}\in[N]$,

$\displaystyle\textrm{Pr}\big{(}J(X_{\mathcal{H}},X_{\mathcal{A},n_{1}})=J(X_{\mathcal{H}},X_{\mathcal{A},n_{2}})\big{)}<\epsilon$
(2)

holds, where $\epsilon\in(0,1)$ is a negligible value.

There are some notable remarks about this definition.

  * •

The probability in (2) is over $X_{\mathcal{H}}$, because the data of honest
data owners come from an i.i.d uniform distribution on $\mathbb{U}$.

  * •

As mentioned in section III, adversaries are unaware of the data of the honest
data owners. Therefore, they can not choose $X_{A,n_{1}}$ and $X_{A,n_{2}}$
based on the knowledge of $X_{\mathcal{H}}$, and they have to choose
$X_{A,n_{1}}$ and $X_{A,n_{2}}$ independently from $X_{\mathcal{H}}$.

  * •

The condition $l<k$ is because we want the tag to be lightweight and
communication-efficient. If we do not impose such constraint, each worker $n$
could use the concatenation of all $X_{k,n}$, $k\in[K]$ as a tag, and data
owners could use such tag very easily to spot the inconsistencies between
workers. However, this trivial solution is not communication efficient at all.
We need a tag function that compresses the received $K$ messages in each
worker so that the discrepancies between workers caused by adversaries become
evident for honest data owners.

Suppose that we have a tag function $J$. Any data owner can compare tags of
two workers $n_{1},n_{2}\in[N]$,
$\mathsf{tag}_{n_{1}}=J(X_{\mathcal{H}},X_{\mathcal{A},n_{1}})$ and
$\mathsf{tag}_{n_{2}}=J(X_{\mathcal{H}},X_{\mathcal{A},n_{2}})$, and by
Definition 2, conclude that $\mathsf{tag}_{n_{1}}=\mathsf{tag}_{n_{2}}$ means
$n_{1}$ and $n_{2}$ had received the same data from all data owners with high
probability, i.e. $X_{k,n_{1}}=X_{k,n_{2}}$, for all $k\in[K]$. On the other
hand, when $\mathsf{tag}_{n_{1}}\neq\mathsf{tag}_{n_{2}}$, it is obvious for
data owners that $X_{k,n_{1}}\neq X_{k,n_{2}}$, for at least one
$k\in\mathcal{A}$ (this is simply because $J$ is a function). Therefore, tags
can be used by data owners to partition $\mathcal{T}$ into sets of workers who
had received the same data from data owners in the first step of Algorithm 1,
and have used the same initial data in their subsequent computations.

Tag functions are a type of the general fingerprinting functions.
Fingerprinting is used to map an arbitrarily large data into a small and fixed
length digest as its unique identifier, for many practical purposes like
avoiding the comparison of bulky data. According to [21], an
$\epsilon$-fingerprinting function
$fp:\mathcal{K}\times\mathbb{F}^{\delta}\rightarrow\mathbb{F}^{\gamma}$
satisfies

$\displaystyle\max_{\begin{subarray}{c}d,d^{\prime}\in\mathbb{F}^{\delta}\\\
d\neq
d^{\prime}\end{subarray}}\textrm{Pr}\left[fp(r,d)=fp(r,d^{\prime}):r\xleftarrow{R}\mathcal{K}\right]\leq\epsilon,$
(3)

where data is a length $\delta$ vector with elements in $\mathbb{F}$, and
$r\in\mathcal{K}$ is a random seed, $\mathcal{K}\subset\mathbb{R}$. One of the
well-known fingerprinting functions is Rabin’s fingerprint [33], and its
derivatives, that uses random polynomials in the finite field to generate the
fingerprint. Another class of fingerprinting functions are cryptographic hash
functions. We know that hash function $h$ is collision resistant if

$\displaystyle\textrm{Pr}\big{(}(x_{0},x_{1})\leftarrow A,x_{0}\neq
x_{1}:h(x_{0})=h(x_{1})\big{)}\leq\epsilon,$ (4)

where $A$ is a probabilistic polynomial adversary (This is just a rough
definition. For formal definition, refer to [34]). We cannot use a collision-
resistant hash function as a tag function for two reasons.

  * •

The probability of collision is small only when $x_{0}$ and $x_{1}$ are chosen
by a probabilistic polynomial adversary. However, tag function has to be
resilient against information theoretic adversary.

  * •

According to (2), inputs to tag function have a common part,
$X_{\mathcal{H}}$, but there is no such constraint on $x_{0}$ and $x_{1}$ in
(4). Even if collision resistance was defined as
$\textrm{Pr}\big{(}(x_{0},x_{1},x_{2})\leftarrow A:x_{1}\neq
x_{2},h(x_{0}||x_{1})=h(x_{0}||x_{2})\big{)}\leq\epsilon$, such $h$ could not
be used as tag, because adversaries could be any of the $\beta$ data owners
and not necessarily the last $\beta$ data owners. Note that
$J(X_{\mathcal{H}},X_{\mathcal{A},n})$ in (2) is just notation exploitation,
and in fact, worker $n\in\mathbb{N}$ calculates $J(X_{1,n},\dots,X_{K,n})$, in
which the $\beta$ adversarial messages could be dispersed in any positions.

In the following theorem, we prove that among all functions from
$\mathbb{U}^{K}$ to $\mathbb{U}$, there exists a tag function.

######  Theorem 2.

There exists a tag function $J^{*}:\mathbb{U}^{K}\rightarrow\mathbb{U}$ which
satisfies (2), given $|\mathbb{U}|$ is large enough.

The proof for this theorem is similar to Shannon’s achievability proof for the
capacity of discrete memoryless channels, and can be found in Appendix

######  Remark 4.

Tags help data owners partition workers, but they cannot resolve all the
ambiguity about the data that workers previously received from adversarial
data owners. For example, assume that

$\displaystyle\mathsf{tag}_{1}=J^{*}(X_{1},X_{2}^{(1)},X_{3}^{(1)}),$
$\displaystyle\mathsf{tag}_{2}=J^{*}(X_{1},X_{2}^{(1)},X_{3}^{(1)}),$
$\displaystyle\mathsf{tag}_{3}=J^{*}(X_{1},X_{2}^{(2)},X_{3}^{(1)}),$
$\displaystyle\mathsf{tag}_{4}=J^{*}(X_{1},X_{2}^{(2)},X_{3}^{(2)}),$

where $J^{*}$ is a tag function. An honest data owner compares these tags and
finds that $\mathsf{tag}_{1}=\mathsf{tag}_{2}$,
$\mathsf{tag}_{2}\neq\mathsf{tag}_{3}$,
$\mathsf{tag}_{2}\neq\mathsf{tag}_{4}$, and
$\mathsf{tag}_{3}\neq\mathsf{tag}_{4}$. So it concludes that with high
probability, workers $1$ and $2$ have received the same data from the
adversaries, while workers $3,4$ each have received different data. This
honest data owner has no way to find out that workers $3$ and $4$ have
received the same data from the second data owner, i.e.
$X_{2,3}=X_{2,4}=X_{2}^{(2)}$, or workers $2$ and $3$ have received the same
data from the third data owner, i.e. $X_{3,2}=X_{3,3}=X_{3}^{(1)}$.

##  VII Analysis of $\textrm{Vers}(f,N,K,\beta,v,\textrm{Lagrange})$

In this section, we introduce some tools and use them to analyze the system.
These tools help us understand the system better, and will be useful in the
next section when we study the fundamental limit of Vers. In the following, we
define the coefficient vector, monomial vector, characteristic matrix, and
relation matrix, and all of them are constructed from parts associated with
every possible adversarial behavior from the point of view of the workers. In
other words, the notions we introduce in this section are inclusive of all
adversarial behaviors. In the converse proof of the fundamental limit of the
system in the next section, we will show that in the worst-case scenario, all
adversarial behaviors from the point view of workers can be present in the
system, and therefore, need to be addressed.

Recall that there are at most $\beta$ adversarial data owners, and each of
them may send different messages to different workers, but honest data owners
send one single message to all workers. The version vector of a worker as we
define in the following, indicates which version of each adversarial message
that worker has received.

######  Definition 3 (version vector).

For worker $n\in[N]$, we define a version vector $\mathbf{v}\in[v^{+}]^{K}$ of
length $K$, whose $k$-th element, if $k\in\mathcal{A}$, is in $[v]$, and
denotes the version of the message of adversarial data owner $k\in\mathcal{A}$
received by worker $n$. Moreover, if $k\in\mathcal{H}$, the $k$-th element of
$\mathbf{v}$ is $0$, indicating that all workers receive the same message from
the honest data owner $k$.

In other words, worker node $n$ receives $X_{k}^{(\mathbf{v}[k])}$ from the
adversarial data owner $k$. Note that worker $n$ does not know $\mathbf{v}$,
because it neither knows the adversaries nor the versions of the adversarial
messages. Worker $n$ receives $K$ messages from data owners, without knowing
anything else about the adversarial or honest data owners, and performs some
computations on them. The version vector of worker $n$ is equivalent to the
adversarial behavior that this worker observes. Since there are at most $v$
different adversarial messages from each adversarial data owner, there exist
$v^{\beta}$ different version vectors. This brings us to the next definition.

It is worth noting that we did not include subscript $n$ for version vector of
worker $n$ in Definition 3 because we will not address version vectors by the
workers who received them. Rather, we use subscripts in version vectors to
enumerate them, as will be clear in the following definition.

######  Definition 4 (version vector set).

The version vector set denoted by
$\mathcal{V}\coloneqq\\{\mathbf{v}_{1},\mathbf{v}_{2},\dots,\mathbf{v}_{v^{\beta}}\\}\subset[v^{+}]^{K}$,
is the set of all the $v^{\beta}$ possible version vectors.

According to the system model described in Section III, each worker computes a
linear combination of the received messages, as in (1). Since we are studying
Vers with Lagrange encoding, each worker $n\in[N]$ whose version vector is
$\mathbf{v}$, forms the following Lagrange polynomial when encoding the
received data from data owners.

$\displaystyle
q^{(\mathbf{v})}(z)\coloneqq\sum_{k\in\mathcal{A}}X_{k}^{(\mathbf{v}[k])}\prod_{j\neq
k}\frac{z-\omega_{j}}{\omega_{i}-\omega_{j}}+\sum_{k\in\mathcal{H}}X_{k}\prod_{j\neq
k}\frac{z-\omega_{j}}{\omega_{i}-\omega_{j}},$ (5)

where $\omega_{k}\in\mathbb{F},k\in[K]$ are $K$ distinct elements assigned to
data owners. This can be rewritten as

$\displaystyle
q^{(\mathbf{v})}(z)=\sum_{i=0}^{K-1}L_{i}(X_{s},s\in\mathcal{H},X_{r}^{(\mathbf{v}[r])},r\in\mathcal{A},f(.))z^{i},$
(6)

where $L_{0},\dots,L_{K-1}:\mathbb{F}^{K}\rightarrow\mathbb{F}$ are linear
maps. Then, $f(q^{(\mathbf{v})}(z))$ can be rewritten as

$\displaystyle
f(q^{(\mathbf{v})}(z))=\sum_{i=0}^{d(K-1)}u_{i}(X_{s},s\in\mathcal{H},X_{r}^{(\mathbf{v}[r])},r\in\mathcal{A},f(.))z^{i},$
(7)

where $u_{0},\dots,u_{d(K-1)}:\mathbb{F}^{K}\rightarrow\mathbb{F}$ are
polynomials of degree $d$ of $X_{r}^{(\mathbf{v}[r])},r\in\mathcal{A}$ and
$X_{s},s\in\mathcal{H}$. Worker $n\in[N]$ evaluates $f(q^{(\mathbf{v})}(z))$
at $\alpha_{n}$, i.e. $f(W_{n})=f(q^{(\mathbf{v})}(\alpha_{n}))$, where
$\alpha_{n},n\in[N]$ are $n$ elements from $\mathbb{F}$, assigned to workers.
In the following, we define the coefficient vector and coefficient sub-vector,
so that we can express the computations of workers as multiplications of
matrices.

######  Definition 5 (coefficient vector).

Let the version vector set be
$\mathcal{V}=\\{\mathbf{v}_{1},\dots,\mathbf{v}_{v^{\beta}}\\}$. The
coefficient vector for a $\textrm{Vers}(f,N,K,\beta,v,\textrm{Lagrange})$
system is defined as

$\displaystyle\mathbf{U}\big{(}X_{s},s\in\mathcal{H},X_{r}^{(i)},r\in\mathcal{A},i\in[v],f(.)\big{)}\coloneqq\left[\begin{array}[]{c}\mathbf{u}_{\mathbf{v}_{1}}(X_{r}^{(\mathbf{v}_{1}[r])},X_{s},r\in\mathcal{A},s\in\mathcal{H},f)\\\
\hdashline\vdots\\\
\hdashline\mathbf{u}_{\mathbf{v}_{v^{\beta}}}(X_{r}^{(\mathbf{v}_{v^{\beta}}[r])},X_{s},r\in\mathcal{A},s\in\mathcal{H},f)\end{array}\right],$
(11)

where
$\mathbf{u}_{\mathbf{v}}\big{(}X_{s},s\in\mathcal{H},X_{r}^{(\mathbf{v}[r])},r\in\mathcal{A},f(.)\big{)},\mathbf{v}\in\mathcal{V}$
is a coefficient sub-vector defined as

$\displaystyle\mathbf{u}_{\mathbf{v}}\big{(}X_{s},s\in\mathcal{H},X_{r}^{(\mathbf{v}[r])},r\in\mathcal{A},f(.)\big{)}\coloneqq\left[\begin{array}[]{c}u_{d(K-1)}\big{(}X_{s},s\in\mathcal{H},X_{r}^{(\mathbf{v}[r])},r\in\mathcal{A},f(.)\big{)}\\\
\vdots\\\
u_{0}\big{(}X_{s},s\in\mathcal{H},X_{r}^{(\mathbf{v}[r])},r\in\mathcal{A},f(.)\big{)}\end{array}\right],\quad\mathbf{v}\in\mathcal{V}.$
(15)

The length of each coefficient sub-vector is $d(K-1)+1$, so the length of
coefficient vector $\mathbf{U}$ is $v^{\beta}(d(K-1)+1)$. As mentioned before,
the coefficient vector contains all of the $v^{\beta}$ possible adversarial
behaviors. Using the definition above, it is clear that for worker $n\in[N]$
whose version vector is $\mathbf{v}\in\mathcal{V}$,

$\displaystyle
f(W_{n})=\left[\alpha^{d(K-1)}~{}\dots~{}\alpha~{}1\right]\mathbf{u}_{\mathbf{v}}\big{(}X_{s},s\in\mathcal{H},X_{r}^{(\mathbf{v}[r])},r\in\mathcal{A},f(.)\big{)}.$
(16)

Therefore, the coefficient vector helps us express the computations of the
workers properly. This motivates us to study the coefficient vector more in-
depth. The following example clarifies the above definition.

######  Example 1.

Consider the following parameters.

$K$ | $N$ | $\beta$ | $v$ | $\mathcal{A}$ | $\mathcal{H}$ | $(\omega_{1},\omega_{2},\omega_{3})$ | $f(x)$
---|---|---|---|---|---|---|---
$3$ | $3$ | $1$ | $2$ | $\\{1,2\\}$ | $\\{3\\}$ | $(1,2,3)$ | $x^{2}$

Since $v=2$, the version vector set is
$\mathcal{V}=\\{[1,1,0],[1,2,0],[2,1,0],[2,2,0]\\}$. The Lagrange polynomial
for the version vector $[i_{1},i_{2},0]\in\mathcal{V}$ is

$\displaystyle q^{([i_{1},i_{2},0])}(z)$
$\displaystyle=\frac{(z-2)(z-3)}{2}X^{(i_{1})}_{1}+\frac{(z-1)(z-3)}{-1}X_{2}^{(i_{2})}+\frac{(z-1)(z-2)}{2}X_{3}=z^{2}(\frac{X_{1}^{(i_{1})}}{2}-X_{2}^{(i_{2})}+\frac{X_{3}}{2})$
$\displaystyle+z(-\frac{5X_{1}^{(i_{1})}}{2}+2X_{2}^{(i_{2})}-\frac{3X_{3}}{2})+(3X_{1}^{(i_{1})}-3X_{2}^{(i_{2})}+X_{3}),~{}[i_{1},i_{2},0]\in\mathcal{V}.$

Consequently,

$\displaystyle f(q^{([i_{1},i_{2},0])}(z))$
$\displaystyle=\bigg{(}\frac{(X_{1}^{(i_{1})})^{2}}{4}-X_{1}^{(i_{1})}X_{2}^{(i_{2})}+\frac{X_{1}^{(i_{1})}X_{3}}{2}+(X_{2}^{(i_{2})})^{2}-X_{2}^{(i_{2})}X_{3}+\frac{X_{3}^{2}}{4}\bigg{)}z^{4}+\bigg{(}\frac{-5(X_{1}^{(i_{1})})^{2}}{2}$
$\displaystyle+9X_{1}^{(i_{1})}X_{2}^{(i_{2})}-4X_{1}^{(i_{1})}X_{3}-8(X_{2}^{(i_{2})})^{2}+7X_{2}^{(i_{2})}X_{3}-\frac{3X_{3}^{2}}{2}\bigg{)}z^{3}+\bigg{(}\frac{37(X_{1}^{(i_{1})})^{2}}{4}-29X_{1}^{(i_{1})}X_{2}^{(i_{2})}$
$\displaystyle+\frac{23X_{1}^{(i_{1})}X_{3}}{2}+22(X_{2}^{(i_{2})})^{2}-17X_{2}^{(i_{2})}X_{3}+\frac{13X_{3}^{2}}{4}\bigg{)}z^{2}+\bigg{(}-15(X_{1}^{(i_{1})})^{2}+39X_{1}^{(i_{1})}X_{2}^{(i_{2})}$
$\displaystyle-14X_{1}^{(i_{1})}X_{3}-24(X_{2}^{(i_{2})})^{2}+17X_{2}^{(i_{2})}X_{3}-3X_{3}\bigg{)}z+\bigg{(}9(X_{1}^{(i_{1})})^{2}-18X_{1}^{(i_{1})}X_{2}^{(i_{2})}+6X_{1}^{(i_{1})}X_{3}$
$\displaystyle+9(X_{2}^{(i_{2})})^{2}-6X_{2}^{(i_{2})}X_{3}+X_{3}^{2}\bigg{)}.$
(17)

Therefore,

$\displaystyle\mathbf{u}_{[i_{1},i_{2},0]}(X_{1}^{(i_{1})},X_{2}^{(i_{2})},X_{3},f)=\left[\begin{array}[]{c}\frac{(X_{1}^{(i_{1})})^{2}}{4}-X_{1}^{(i_{1})}X_{2}^{(i_{2})}+\frac{X_{1}^{(i_{1})}X_{3}}{2}+(X_{2}^{(i_{2})})^{2}-X_{2}^{(i_{2})}X_{3}+\frac{X_{3}^{2}}{4}\\\
\frac{-5(X_{1}^{(i_{1})})^{2}}{2}+9X_{1}^{(i_{1})}X_{2}^{(i_{2})}-4X_{1}^{(i_{1})}X_{3}-8(X_{2}^{(i_{2})})^{2}+7X_{2}^{(i_{2})}X_{3}-\frac{3X_{3}^{2}}{2}\\\
\frac{37(X_{1}^{(i_{1})})^{2}}{4}-29X_{1}^{(i_{1})}X_{2}^{(i_{2})}+\frac{23X_{1}^{(i_{1})}X_{3}}{2}+22(X_{2}^{(i_{2})})^{2}-17X_{2}^{(i_{2})}X_{3}+\frac{13X_{3}^{2}}{4}\\\
-15(X_{1}^{(i_{1})})^{2}+39X_{1}^{(i_{1})}X_{2}^{(i_{2})}-14X_{1}^{(i_{1})}X_{3}-24(X_{2}^{(i_{2})})^{2}+17X_{2}^{(i_{2})}X_{3}-3X_{3}\\\
9(X_{1}^{(i_{1})})^{2}-18X_{1}^{(i_{1})}X_{2}^{(i_{2})}+6X_{1}^{(i_{1})}X_{3}+9(X_{2}^{(i_{2})})^{2}-6X_{2}^{(i_{2})}X_{3}+X_{3}^{2}\end{array}\right],$
(23)

and

$\displaystyle\mathbf{U}(X_{1}^{(i_{1})},X_{2}^{(i_{2})},i_{1},i_{2}\in[2],X_{3},f)=\left[\begin{array}[]{c}\mathbf{u}_{[1,1,0]}(X_{1}^{(1)},X_{2}^{(1)},X_{3},f)\\\
\mathbf{u}_{[1,2,0]}(X_{1}^{(1)},X_{2}^{(2)},X_{3},f)\\\
\mathbf{u}_{[2,1,0]}(X_{1}^{(2)},X_{2}^{(1)},X_{3},f)\\\
\mathbf{u}_{[2,2,0]}(X_{1}^{(2)},X_{2}^{(2)},X_{3},f)\end{array}\right]$ (28)

######  Remark 5.

In Definition 5, we implied a particular order on the coefficient sub-vectors
in (11). The first and topmost sub-vector in the coefficient vector is
$\mathbf{u}_{\mathbf{v}_{1}}$, the second is $\mathbf{u}_{\mathbf{v}_{2}}$,
and so forth, until $\mathbf{u}_{\mathbf{v}_{v^{\beta}}}$. In Example 1, we
chose $\mathbf{v}_{1}=[1,1,0]$, $\mathbf{v}_{2}=[1,2,0]$,
$\mathbf{v}_{3}=[2,1,0]$, and $\mathbf{v}_{4}=[2,2,0]$. We could have used
another assignment for
$\mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3},\mathbf{v}_{4}$, as different
assignments only lead to different permutations of the same coefficient
vector. Therefore, the order of coefficient sub-vectors in coefficient vector
is optional but fixed.

Every element of the coefficient vector is a summation of some monomials. For
example, in equation (23) from Example 1,
$\mathbf{u}_{[i_{1},i_{2},0]}(X_{1}^{(i_{1})},X_{2}^{(i_{2})},X_{3},f)$ shows
that elements of the coefficient vector are made of some monomials. Therefore,
in order to understand the coefficient vector better, we define a new vector
that contains the monomials that appear in the coefficient vector. Before
defining the monomial vector, we need to define the degree set of a function.
The degree set of a single variable function
$f:\mathbb{U}\rightarrow\mathbb{V}$, denoted by $\mathcal{D}(f)$, contains the
degrees of the monomials in $f$. For example, $\mathcal{D}(f)=\\{0,1,3\\}$ for
$f(x)=x^{3}+x+1$.

######  Definition 6 (monomial vector).

The monomial vector for a $\textrm{Vers}(f,N,K,\beta,v,\textrm{Lagrange})$
system contains all degree $e\in\mathcal{D}_{f}$ monomials of
$X_{k},k\in\mathcal{H}$ and $X_{k}^{(i)},k\in\mathcal{A},i\in[v]$, and is
defined as

$\displaystyle\mathbf{X}\big{(}X_{s},s\in\mathcal{H},X_{r}^{(i)},r\in\mathcal{A},i\in[v],f(.)\big{)}\coloneqq\left[\prod_{k\in\mathcal{A}}(X_{k}^{(\mathbf{v}[k])})^{i_{k}}\prod_{k\in\mathcal{H}}(X_{k})^{j_{k}},~{}\textrm{s.t.}\sum_{k\in\mathcal{A}}i_{k}+\sum_{k\in\mathcal{H}}j_{k}\in\mathcal{D}(f),\textrm{and}~{}\mathbf{v}\in\mathcal{V}\right]^{\intercal}.$
(29)

In the following example, we determine the monomial vector for Vers system
introduced in Example 1.

######  Example 2.

Recall that in Example 1, $f(x)=x^{2}$, and $\mathcal{D}(f)=\\{2\\}$.
Therefore, the monomial vector contains all degree $2$ monomials of
$X_{k},k\in\mathcal{H}$ and $X_{k}^{(i)},k\in\mathcal{A},i\in[v]$. In
particular,

  * •

for $i_{1}=2,i_{2}=0,i_{3}=0$, we get the monomials
$(X_{1}^{(1)})^{2},~{}(X_{1}^{(2)})^{2}$,

  * •

for $i_{1}=0,i_{2}=2,i_{3}=0$, we get the monomials
$(X_{2}^{(1)})^{2},~{}(X_{2}^{(2)})^{2}$,

  * •

for $i_{1}=0,i_{2}=0,i_{3}=2$, we get the monomial $(X_{3})^{2}$,

  * •

for $i_{1}=1,i_{2}=1,i_{3}=0$, we get the monomials
$X_{1}^{(1)}X_{2}^{(1)},~{}X_{1}^{(2)}X_{2}^{(1)},X_{1}^{(1)}X_{2}^{(2)},~{}X_{1}^{(2)}X_{2}^{(2)}$,

  * •

for $i_{1}=1,i_{2}=0,i_{3}=1$, we get the monomials
$X_{1}^{(1)}X_{3},~{}X_{1}^{(2)}X_{3}$,

  * •

for $i_{1}=0,i_{2}=1,i_{3}=1$, we get the monomials
$X_{2}^{(1)}X_{3},~{}X_{2}^{(2)}X_{3}$.

Therefore,

$\displaystyle\mathbf{X}\big{(}X_{1}^{(i_{1})},X_{2}^{(i_{2})},X_{3},i_{1},i_{2}\in[2],f(x)=x^{2}\big{)}=$
$\displaystyle\bigg{[}(X_{1}^{(1)})^{2},~{}(X_{1}^{(2)})^{2},~{}(X_{2}^{(1)})^{2},~{}(X_{2}^{(2)})^{2},~{}(X_{3})^{2},X_{1}^{(1)}X_{2}^{(1)},X_{1}^{(2)}X_{2}^{(1)},$
$\displaystyle
X_{1}^{(1)}X_{2}^{(2)},~{}X_{1}^{(2)}X_{2}^{(2)},X_{1}^{(1)}X_{3},~{}X_{1}^{(2)}X_{3},X_{2}^{(1)}X_{3},~{}X_{2}^{(2)}X_{3}\bigg{]}^{\intercal}.$
(30)

######  Remark 6.

Note that the order of the monomials in monomial vector is optional, but fixed
in all subsequent equations. For example, we could have formed
$\mathbf{X}\big{(}X_{1}^{(i_{1})},X_{2}^{(i_{2})},X_{3},i_{1},i_{2}\in[2],f(x)=x^{2}\big{)}$
in (2) as

$\displaystyle\biggr{[}(X_{1}^{(2)})^{2},~{}(X_{1}^{(1)})^{2},~{}(X_{2}^{(2)})^{2},~{}(X_{2}^{(1)})^{2},~{}(X_{3})^{2},$
$\displaystyle~{}X_{1}^{(2)}X_{2}^{(1)},~{}X_{1}^{(1)}X_{2}^{(1)},~{}X_{1}^{(2)}X_{2}^{(2)},X_{1}^{(1)}X_{2}^{(2)},$
$\displaystyle
X_{1}^{(1)}X_{3},~{}X_{1}^{(2)}X_{3},X_{2}^{(1)}X_{3},~{}X_{2}^{(2)}X_{3}\biggr{]}^{\intercal}.$

However, we chose the order in (2), and will keep using that in the follow-up
of Example 2.

######  Lemma 1.

The length of monomial vector
$\mathbf{X}\big{(}X_{r}^{(i)},X_{s},r\in\mathcal{A},s\in\mathcal{H},i\in[v]\big{)}$
in a $\textrm{Vers}(f,N,K,\beta,v,\textrm{Lagrange})$ system is

$\displaystyle\mathsf{Len}(\mathbf{X})\coloneqq\sum_{e\in\mathcal{D}(f)}\sum_{m=0}^{\min(e,\beta)}\binom{\beta}{m}\binom{K-\beta-1+e}{e-m}v^{m}$
(31)

###### Proof.

For each $e\in\mathcal{D}(f)$, we need to count the number of distinct
monomials
$\prod_{k\in\mathcal{A}}(X_{k}^{(\mathbf{v}[k])})^{i_{k}}\prod_{k\in\mathcal{H}}(X_{k})^{j_{k}}$,
that $\sum_{k\in\mathcal{A}}i_{k}+\sum_{k\in\mathcal{H}}j_{k}=e$ and
$\mathbf{v}\in\mathcal{V}$. We count as following:

  * •

We choose a subset $\mathcal{M}\in\mathcal{A}$, $|\mathcal{M}|=m$, of
adversarial messages to be in the monomial, so $m\leq\beta$ and $m\leq e$,
thus $0\leq m\leq\min(e,\beta)$. This makes the term $\binom{\beta}{m}$ in
(31).

  * •

There are $v^{m}$ different version values for the $m$ adversarial messages in
the monomial, which makes the term $v^{m}$ in (31).

  * •

We need to count the number of possible cases for the powers of the chosen $m$
adversarial messages and the $K-\beta$ honest messages. This is the number of
solutions for $\sum_{k\in\mathcal{M}}i_{k}+\sum_{k\in\mathcal{H}}j_{k}=e$,
where $1\leq i_{k}$, for $k\in\mathcal{M}$, and $0\leq j_{k}$, for
$k\in\mathcal{H}$. From combinatorics, we know that the number of such
solutions is $\binom{K-\beta-1+e}{e-m}$. This completes the proof.

∎

Now that the monomial vector is defined, we can express each element of the
coefficient vector as a linear combination of the monomials in the monomial
vector. We do so by defining the characteristic matrix.

######  Definition 7 (characteristic matrix).

The characteristic matrix of a
$\textrm{Vers}(f,N,K,\beta,v,\textrm{Lagrange})$ system, denoted by
$\mathbf{M}(\mathcal{H},\mathcal{A},v,f)$ illustrates the relation between the
coefficient vector and the monomial vector, i.e.

$\displaystyle\mathbf{U}\big{(}X_{s},s\in\mathcal{H},X_{r}^{(i)},r\in\mathcal{A},i\in[v],f(.)\big{)}=\mathbf{M}\big{(}\mathcal{H},\mathcal{A},v,f\big{)}\mathbf{X}\big{(}X_{s},s\in\mathcal{H},X_{r}^{(i)},r\in\mathcal{A},i\in[v],f(.)\big{)}.$
(32)

The dimension of the characteristic matrix is
$\big{(}v^{\beta}(d(K-1)+1)\big{)}\times\mathsf{Len}(\mathbf{X})$. It is worth
noting that similar to the coefficient vector, the characteristic matrix
contains all the $v^{\beta}$ adversarial behaviors.

######  Example 3.

For Vers system introduced in Example 1, we can easily form
$\mathbf{M}\big{(}\mathcal{H}=\\{3\\},\mathcal{A}=\\{1,2\\},v=2,f(x)=x^{2}\big{)}$
by using (23), (28), and also (2) from Example 2. The resulting characteristic
matrix is shown in (90).

We can decompose the characteristic matrix as

$\displaystyle\mathbf{M}\big{(}\mathcal{H},\mathcal{A},v,f\big{)}=\left[\begin{array}[]{c}\mathbf{M}_{\mathbf{v}_{1}}\big{(}\mathcal{H},\mathcal{A},f\big{)}\\\
\hdashline\vdots\\\
\hdashline\mathbf{M}_{\mathbf{v}_{v^{\beta}}}\big{(}\mathcal{H},\mathcal{A},f\big{)}\end{array}\right],$
(36)

where $\\{\mathbf{v}_{1},\dots,\mathbf{v}_{v^{\beta}}\\}=\mathcal{V}$. The
dimension of each sub-matrix
$\mathbf{M}_{\mathbf{v}}\big{(}\mathcal{H},\mathcal{A},f\big{)}$,
$\mathbf{v}\in\mathcal{V}$, is
$\big{(}d(K-1)+1\big{)}\times\mathsf{Len}(\mathbf{X})$. In fact, the sub-
matrix $\mathbf{M}_{\mathbf{v}}$ is dedicated to coefficient sub-vector
$\mathbf{u}_{\mathbf{v}}\big{(}X_{s},s\in\mathcal{H},X_{r}^{(\mathbf{v}[r])},r\in\mathcal{A},f(.)\big{)}$,
and expresses its elements as linear combinations of the element of the
monomial vector. Consequently, the order of the version vectors that we had
chosen in the coefficient vector, as discussed in Remark 5, determines the
order of the sub-matrices in the characteristic matrix. We emphasize that this
order is optional but fixed.

$\displaystyle\left[\begin{array}[]{c}u_{4}(X_{1}^{(1)},X_{2}^{(1)},X_{3})\\\
u_{3}(X_{1}^{(1)},X_{2}^{(1)},X_{3})\\\
u_{2}(X_{1}^{(1)},X_{2}^{(1)},X_{3})\\\
u_{1}(X_{1}^{(1)},X_{2}^{(1)},X_{3})\\\
u_{0}(X_{1}^{(1)},X_{2}^{(1)},X_{3})\\\ \hdashline
u_{4}(X_{1}^{(1)},X_{2}^{(2)},X_{3})\\\
u_{3}(X_{1}^{(1)},X_{2}^{(2)},X_{3})\\\
u_{2}(X_{1}^{(1)},X_{2}^{(2)},X_{3})\\\
u_{1}(X_{1}^{(1)},X_{2}^{(2)},X_{3})\\\
u_{0}(X_{1}^{(2)},X_{2}^{(2)},X_{3})\\\ \hdashline
u_{4}(X_{1}^{(2)},X_{2}^{(1)},X_{3})\\\
u_{3}(X_{1}^{(2)},X_{2}^{(1)},X_{3})\\\
u_{2}(X_{1}^{(2)},X_{2}^{(1)},X_{3})\\\
u_{1}(X_{1}^{(2)},X_{2}^{(1)},X_{3})\\\
u_{0}(X_{1}^{(2)},X_{2}^{(1)},X_{3})\\\ \hdashline
u_{4}(X_{1}^{(2)},X_{2}^{(2)},X_{3})\\\
u_{3}(X_{1}^{(2)},X_{2}^{(2)},X_{3})\\\
u_{2}(X_{1}^{(2)},X_{2}^{(2)},X_{3})\\\
u_{1}(X_{1}^{(2)},X_{2}^{(2)},X_{3})\\\
u_{0}(X_{1}^{(2)},X_{2}^{(2)},X_{3})\end{array}\right]=\left[\begin{array}[]{cc:cc:c:cccc:cc:cc}\frac{1}{4}&0&1&0&\frac{1}{4}&-1&0&0&0&\frac{1}{2}&0&-1&0\\\
-\frac{5}{2}&0&-8&0&-\frac{3}{2}&9&0&0&0&-4&0&7&0\\\
\frac{37}{4}&0&22&0&\frac{13}{4}&-29&0&0&0&\frac{23}{2}&0&-17&0\\\
-15&0&-24&0&-3&39&0&0&0&-14&0&-17&0\\\ 9&0&9&0&1&-18&0&0&0&6&0&-6&0\\\
\hdashline\frac{1}{4}&0&0&1&\frac{1}{4}&0&0&-1&0&\frac{1}{2}&0&0&-1\\\
-\frac{5}{2}&0&0&-8&-\frac{3}{2}&0&0&9&0&-4&0&0&7\\\
\frac{37}{4}&0&0&22&\frac{13}{4}&0&0&-29&0&\frac{23}{2}&0&0&-17\\\
-15&0&0&-24&-3&0&0&39&0&-14&0&0&17\\\ 9&0&0&9&1&0&0&-18&0&6&0&0&-6\\\
\hdashline 0&\frac{1}{4}&1&0&\frac{1}{4}&0&-1&0&0&0&\frac{1}{2}&-1&0\\\
0&-\frac{5}{2}&-8&0&-\frac{3}{2}&0&9&0&0&0&-4&7&0\\\
0&\frac{37}{4}&22&0&\frac{13}{4}&0&-29&0&0&0&\frac{23}{2}&-17&0\\\
0&-15&-24&0&-3&0&39&0&0&0&-14&17&0\\\ 0&9&9&0&1&0&-18&0&0&0&6&-6&0\\\
\hdashline 0&\frac{1}{4}&0&1&\frac{1}{4}&0&0&0&-1&0&\frac{1}{2}&0&-1\\\
0&-\frac{5}{2}&0&-8&-\frac{3}{2}&0&0&0&9&0&-4&0&7\\\
0&\frac{37}{4}&0&22&\frac{13}{4}&0&0&0&-29&0&\frac{23}{2}&0&-17\\\
0&-15&0&-24&-3&0&0&0&39&0&-14&0&17\\\
0&9&0&9&1&0&0&0&-18&0&6&0&-6\end{array}\right]\left[\begin{array}[]{c}(X_{1}^{(1)})^{2}\\\
(X_{1}^{(2)})^{2}\\\ \hdashline(X_{2}^{(1)})^{2}\\\ (X_{2}^{(2)})^{2}\\\
\hdashline(X_{3})^{2}\\\ \hdashline X_{1}^{(1)}X_{2}^{(1)}\\\
X_{1}^{(2)}X_{2}^{(1)}\\\ X_{1}^{(1)}X_{2}^{(2)}\\\ X_{1}^{(2)}X_{2}^{(2)}\\\
\hdashline X_{1}^{(1)}X_{3}\\\ X_{1}^{(2)}X_{3}\\\ \hdashline
X_{2}^{(1)}X_{3}\\\ X_{2}^{(2)}X_{3}\end{array}\right].$ (90)

######  Definition 8.

(relation matrix) The relation matrix in a
$\textrm{Vers}(f,N,K,\beta,v,\textrm{Lagrange})$ system, which we denote by
$\mathbf{P}\big{(}\mathcal{H},\mathcal{A},v,f\big{)}$, consists of basis of
the left null space of $\mathbf{M}\big{(}\mathcal{H},\mathcal{A},v,f\big{)}$,
i.e.

$\displaystyle\mathbf{P}\big{(}\mathcal{H},\mathcal{A},v,f\big{)}\mathbf{M}\big{(}\mathcal{H},\mathcal{A},v,f\big{)}=\mathbf{0}.$
(91)

The dimension of the relation matrix is
$\big{(}v^{\beta}(d(K-1)+1)-\textrm{rank}(\mathbf{M})\big{)}\times\big{(}v^{\beta}(d(K-1)+1)\big{)}$.
According to Definition 7,
$\mathbf{P}\big{(}\mathcal{H},\mathcal{A},v,f\big{)}\mathbf{M}\big{(}\mathcal{H},\mathcal{A},v,f\big{)}=\mathbf{0}$
is equivalent to

$\displaystyle\mathbf{P}\big{(}\mathcal{H},\mathcal{A},v,f\big{)}\mathbf{U}\big{(}X_{s},s\in\mathcal{H},X_{r}^{(i)},r\in\mathcal{A},i\in[v],f(.)\big{)}=\mathbf{0}.$
(92)

This is why we have named
$\mathbf{P}\big{(}\mathcal{H},\mathcal{A},v,f\big{)}$ as relation matrix,
because it reveals the linear relations of the elements of the coefficient
vector. Similar to the characteristic matrix, we can decompose the relation
matrix as

$\displaystyle\mathbf{P}\big{(}\mathcal{H},\mathcal{A},v,f\big{)}=\left[\begin{array}[]{c:c:c}\mathbf{P}_{\mathbf{v}_{1}}\big{(}\mathcal{H},\mathcal{A},f\big{)}&\dots&\mathbf{P}_{\mathbf{v}_{v^{\beta}}}\big{(}\mathcal{H},\mathcal{A},f\big{)}\end{array}\right],$
(94)

where $\\{\mathbf{v}_{1},\dots,\mathbf{v}_{v^{\beta}}\\}=\mathcal{V}$. The
dimension of each sub-matrix
$\mathbf{P}_{\mathbf{v}}\big{(}\mathcal{H},\mathcal{A},f\big{)}$,
$\mathbf{v}\in\mathcal{V}$, is
$\big{(}v^{\beta}(d(K-1)+1)-\textrm{rank}(\mathbf{M})\big{)}\times(d(K-1)+1)$.
Due to (36) and (91),

$\displaystyle\mathbf{P}_{\mathbf{v}_{1}}\mathbf{M}_{\mathbf{v}_{1}}+\dots+\mathbf{P}_{\mathbf{v}_{v^{\beta}}}\mathbf{M}_{\mathbf{v}_{v^{\beta}}}=\mathbf{0},$

and due to (7),

$\displaystyle\mathbf{P}_{\mathbf{v}_{1}}\mathbf{u}_{\mathbf{v}_{1}}+\dots+\mathbf{P}_{\mathbf{v}_{v^{\beta}}}\mathbf{u}_{\mathbf{v}_{v^{\beta}}}=\mathbf{0}.$

Now, we introduce effective and non-effective permutations of the relation
matrix.

######  Definition 9.

(effective permutations of the relation matrix) Suppose that

$\displaystyle\mathbf{P}\big{(}\mathcal{H},\mathcal{A},v,f\big{)}=\left[\begin{array}[]{c:c:c}\mathbf{P}_{\mathbf{v}_{1}}\big{(}\mathcal{H},\mathcal{A},f\big{)}&\dots&\mathbf{P}_{\mathbf{v}_{v^{\beta}}}\big{(}\mathcal{H},\mathcal{A},f\big{)}\end{array}\right]$

is the relation matrix of a $\textrm{Vers}(f,N,K,\beta,v,\textrm{Lagrange})$
system. A permutation $\Pi:[v^{\beta}]\rightarrow[v^{\beta}]$ of the relation
matrix is
$\mathbf{P}^{\Pi}\big{(}\mathcal{H},\mathcal{A},v,f\big{)}=\left[\begin{array}[]{c:c:c}\mathbf{P}_{\mathbf{v}_{\Pi(1)}}\big{(}\mathcal{H},\mathcal{A},f\big{)}&\dots&\mathbf{P}_{\mathbf{v}_{\Pi(v^{\beta})}}\big{(}\mathcal{H},\mathcal{A},f\big{)}\end{array}\right]$,
and is effective if $\mathbf{P}^{\Pi}\mathbf{M}\neq\mathbf{0}$, and non-
effective if $\mathbf{P}^{\Pi}\mathbf{M}=\mathbf{0}$.

The intuition behind this definition is the special structure of the
characteristic matrix, which is also evident in (90). This special structure
will get clear in the following example.

######  Example 4.

Recall that for Vers system introduced in Example (1), we had set
$\mathbf{v}_{1}=[1,1,0]$, $\mathbf{v}_{2}=[1,2,0]$,
$\mathbf{v}_{3}=[2,1,0],\mathbf{v}_{4}=[2,2,0]$, and
$\mathbf{P}\big{(}\mathcal{H}=\\{3\\},\mathcal{A}=\\{1,2\\},v=2,f(x)=x^{2}\big{)}=[\mathbf{P}_{\mathbf{v}_{1}}~{}\mathbf{P}_{\mathbf{v}_{2}}~{}\mathbf{P}_{\mathbf{v}_{3}}~{}\mathbf{P}_{\mathbf{v}_{4}}]$.
We show that in this Vers system, there are $3$ non-effective permutations of
$\mathbf{P}$, say $\Pi_{1},\Pi_{2},$ and $\Pi_{3}$, as following.

$\displaystyle\mathbf{P}^{\Pi_{1}}$
$\displaystyle=[\mathbf{P}_{\mathbf{v}_{4}}~{}\mathbf{P}_{\mathbf{v}_{3}}~{}\mathbf{P}_{\mathbf{v}_{2}}~{}\mathbf{P}_{\mathbf{v}_{1}}]$
(95) $\displaystyle\mathbf{P}^{\Pi_{2}}$
$\displaystyle=[\mathbf{P}_{\mathbf{v}_{3}}~{}\mathbf{P}_{\mathbf{v}_{4}}~{}\mathbf{P}_{\mathbf{v}_{1}}~{}\mathbf{P}_{\mathbf{v}_{2}}]$
(96) $\displaystyle\mathbf{P}^{\Pi_{3}}$
$\displaystyle=[\mathbf{P}_{\mathbf{v}_{2}}~{}\mathbf{P}_{\mathbf{v}_{1}}~{}\mathbf{P}_{\mathbf{v}_{4}}~{}\mathbf{P}_{\mathbf{v}_{3}}]$
(97)

In other words,
$\mathbf{P}^{\Pi_{1}}\mathbf{M}=\mathbf{P}^{\Pi_{2}}\mathbf{M}=\mathbf{P}^{\Pi_{3}}\mathbf{M}=\mathbf{0}$,
where $\mathbf{M}$ is given in (90). Let us consider $\Pi_{1}$ and show that
$\mathbf{P}^{\Pi_{1}}\mathbf{M}=\mathbf{0}$. The arguments for the other two
permutations are similar. We denote a column $i$, $1\leq i\leq 13$, of
$\mathbf{M}$ as
$\mathbf{c_{i}}=[c_{i,1}^{\intercal}~{}c_{i,2}^{\intercal}~{}c_{i,3}^{\intercal}~{}c_{i,4}^{\intercal}]^{\intercal}$,
where the length of $c_{i,1},c_{i,2},c_{i,3},c_{i,4}$ is $5$. We know that
$\mathbf{P}c_{i}=\mathbf{P}_{\mathbf{v}_{1}}c_{i,1}+\mathbf{P}_{\mathbf{v}_{2}}c_{i,2}+\mathbf{P}_{\mathbf{v}_{3}}c_{i,3}+\mathbf{P}_{\mathbf{v}_{4}}c_{i,4}=\mathbf{0}$.
We consider all $1\leq i\leq 13$ in the following.

  * •

$i=1,i=2$
A close look at the first two columns of $\mathbf{M}$ in (90) reveals that
$c_{1,1}=c_{1,2}=c_{2,3}=c_{2,4}\coloneqq c^{*}_{\\{1,2\\}}$, and
$c_{1,3}=c_{1,4}=c_{2,1}=c_{2,2}=\mathbf{0}$. Therefore

$\displaystyle\mathbf{P}\mathbf{c}_{1}=\mathbf{P}_{\mathbf{v}_{1}}c_{1,1}+\mathbf{P}_{\mathbf{v}_{2}}c_{1,2}+\mathbf{P}_{\mathbf{v}_{3}}c_{1,3}+\mathbf{P}_{\mathbf{v}_{4}}c_{1,4}=\mathbf{0},$

is equivalent to

$\displaystyle(\mathbf{P}_{\mathbf{v}_{1}}+\mathbf{P}_{\mathbf{v}_{2}})c^{*}_{\\{1,2\\}}=\mathbf{0},$
(98)

and

$\displaystyle\mathbf{P}\mathbf{c}_{2}=\mathbf{P}_{\mathbf{v}_{1}}c_{2,1}+\mathbf{P}_{\mathbf{v}_{2}}c_{2,2}+\mathbf{P}_{\mathbf{v}_{3}}c_{2,3}+\mathbf{P}_{\mathbf{v}_{4}}c_{2,4}=\mathbf{0},$

is equivalent to

$\displaystyle(\mathbf{P}_{\mathbf{v}_{3}}+\mathbf{P}_{\mathbf{v}_{4}})c^{*}_{\\{1,2\\}}=\mathbf{0}.$
(99)

Consequently, for the permuted relation matrix in (95),

$\displaystyle\mathbf{P}^{\Pi_{1}}\mathbf{c}_{1}=\mathbf{P}_{\mathbf{v}_{4}}c_{1,1}+\mathbf{P}_{\mathbf{v}_{3}}c_{1,2}+\mathbf{P}_{\mathbf{v}_{2}}c_{1,3}+\mathbf{P}_{\mathbf{v}_{1}}c_{1,4}=(\mathbf{P}_{\mathbf{v}_{4}}+\mathbf{P}_{\mathbf{v}_{3}})c^{*}_{\\{1,2\\}},$

and due to (99), we conclude that
$\mathbf{P}^{\Pi_{1}}\mathbf{c}_{1}=\mathbf{0}$. Similarly,

$\displaystyle\mathbf{P}^{\Pi_{1}}\mathbf{c}_{2}=\mathbf{P}_{\mathbf{v}_{4}}c_{2,1}+\mathbf{P}_{\mathbf{v}_{3}}c_{2,2}+\mathbf{P}_{\mathbf{v}_{2}}c_{2,3}+\mathbf{P}_{\mathbf{v}_{1}}c_{2,4}=(\mathbf{P}_{\mathbf{v}_{2}}+\mathbf{P}_{\mathbf{v}_{1}})c^{*}_{\\{1,2\\}},$

and due to (98), we conclude that
$\mathbf{P}^{\Pi_{1}}\mathbf{c}_{2}=\mathbf{0}$.

  * •

$i=3,i=4$
According to $\mathbf{M}$ in (90), $c_{3,1}=c_{3,3}=c_{4,2}=c_{4,4}\coloneqq
c^{*}_{\\{3,4\\}}$, and $c_{3,2}=c_{3,4}=c_{4,1}=c_{4,3}=\mathbf{0}$.
Therefore,

$\displaystyle\mathbf{P}\mathbf{c}_{3}=\mathbf{P}_{\mathbf{v}_{1}}c_{3,1}+\mathbf{P}_{\mathbf{v}_{2}}c_{3,2}+\mathbf{P}_{\mathbf{v}_{3}}c_{3,3}+\mathbf{P}_{\mathbf{v}_{4}}c_{3,4}=(\mathbf{P}_{\mathbf{v}_{1}}+\mathbf{P}_{\mathbf{v}_{3}})c^{*}_{\\{3,4\\}}=\mathbf{0},$
(100)

and

$\displaystyle\mathbf{P}\mathbf{c}_{4}=\mathbf{P}_{\mathbf{v}_{1}}c_{4,1}+\mathbf{P}_{\mathbf{v}_{2}}c_{4,2}+\mathbf{P}_{\mathbf{v}_{3}}c_{4,3}+\mathbf{P}_{\mathbf{v}_{4}}c_{4,4}=(\mathbf{P}_{\mathbf{v}_{2}}+\mathbf{P}_{\mathbf{v}_{4}})c^{*}_{\\{3,4\\}}=\mathbf{0}.$
(101)

As a result,

$\displaystyle\mathbf{P}^{\Pi_{1}}\mathbf{c}_{3}=\mathbf{P}_{\mathbf{v}_{4}}c_{3,1}+\mathbf{P}_{\mathbf{v}_{3}}c_{3,2}+\mathbf{P}_{\mathbf{v}_{2}}c_{3,3}+\mathbf{P}_{\mathbf{v}_{1}}c_{3,4}=(\mathbf{P}_{\mathbf{v}_{4}}+\mathbf{P}_{\mathbf{v}_{2}})c^{*}_{\\{3,4\\}},$

and due to (101), we conclude that
$\mathbf{P}^{\Pi_{1}}\mathbf{c}_{3}=\mathbf{0}$. Similarly,

$\displaystyle\mathbf{P}^{\Pi_{1}}\mathbf{c}_{4}=\mathbf{P}_{\mathbf{v}_{4}}c_{4,1}+\mathbf{P}_{\mathbf{v}_{3}}c_{4,2}+\mathbf{P}_{\mathbf{v}_{2}}c_{4,3}+\mathbf{P}_{\mathbf{v}_{1}}c_{4,4}=(\mathbf{P}_{\mathbf{v}_{3}}+\mathbf{P}_{\mathbf{v}_{1}})c^{*}_{\\{3,4\\}},$

and due to (100), we conclude that
$\mathbf{P}^{\Pi_{1}}\mathbf{c}_{4}=\mathbf{0}$.

  * •

$i=5$
Since $c_{5,1}=c_{5,2}=c_{5,3}=c_{5,4}\coloneqq c^{*}_{\\{5\\}}$ in the fifth
column of $\mathbf{M}$ according to (90),

$\displaystyle\mathbf{P}^{\Pi_{1}}\mathbf{c}_{5}=\mathbf{P}_{\mathbf{v}_{4}}c_{5,1}+\mathbf{P}_{\mathbf{v}_{3}}c_{5,2}+\mathbf{P}_{\mathbf{v}_{2}}c_{5,3}+\mathbf{P}_{\mathbf{v}_{1}}c_{5,4}$
$\displaystyle=(\mathbf{P}_{\mathbf{v}_{4}}+\mathbf{P}_{\mathbf{v}_{3}}+\mathbf{P}_{\mathbf{v}_{2}}+\mathbf{P}_{\mathbf{v}_{1}})c^{*}_{\\{5\\}}$
$\displaystyle=\mathbf{P}_{\mathbf{v}_{1}}c_{5,1}+\mathbf{P}_{\mathbf{v}_{2}}c_{5,2}+\mathbf{P}_{\mathbf{v}_{3}}c_{5,3}+\mathbf{P}_{\mathbf{v}_{4}}c_{5,4}=\mathbf{P}\mathbf{c}_{5}=\mathbf{0}.$

  * •

$i=6,i=7,i=8,i=9$
According to $\mathbf{M}$ in (90), $c_{6,1}=c_{7,3}=c_{8,2}=c_{9,4}\coloneqq
c^{*}_{\\{6,7,8,9\\}}$. Thus,

$\displaystyle\mathbf{P}^{\Pi_{1}}\mathbf{c}_{6}$
$\displaystyle=\mathbf{P}_{\mathbf{v}_{4}}c_{6,1}+\mathbf{P}_{\mathbf{v}_{3}}c_{6,2}+\mathbf{P}_{\mathbf{v}_{2}}c_{6,3}+\mathbf{P}_{\mathbf{v}_{1}}c_{6,4}=\mathbf{P}_{\mathbf{v}_{4}}c^{*}_{\\{6,7,8,9\\}}=\mathbf{P}\mathbf{c}_{9}=\mathbf{0},$
$\displaystyle\mathbf{P}^{\Pi_{1}}\mathbf{c}_{7}$
$\displaystyle=\mathbf{P}_{\mathbf{v}_{4}}c_{7,1}+\mathbf{P}_{\mathbf{v}_{3}}c_{7,2}+\mathbf{P}_{\mathbf{v}_{2}}c_{7,3}+\mathbf{P}_{\mathbf{v}_{1}}c_{7,4}=\mathbf{P}_{\mathbf{v}_{2}}c^{*}_{\\{6,7,8,9\\}}=\mathbf{P}\mathbf{c}_{8}=\mathbf{0},$
$\displaystyle\mathbf{P}^{\Pi_{1}}\mathbf{c}_{8}$
$\displaystyle=\mathbf{P}_{\mathbf{v}_{4}}c_{8,1}+\mathbf{P}_{\mathbf{v}_{3}}c_{8,2}+\mathbf{P}_{\mathbf{v}_{2}}c_{8,3}+\mathbf{P}_{\mathbf{v}_{1}}c_{8,4}=\mathbf{P}_{\mathbf{v}_{3}}c^{*}_{\\{6,7,8,9\\}}=\mathbf{P}\mathbf{c}_{7}=\mathbf{0},$
$\displaystyle\mathbf{P}^{\Pi_{1}}\mathbf{c}_{9}$
$\displaystyle=\mathbf{P}_{\mathbf{v}_{4}}c_{9,1}+\mathbf{P}_{\mathbf{v}_{3}}c_{9,2}+\mathbf{P}_{\mathbf{v}_{2}}c_{9,3}+\mathbf{P}_{\mathbf{v}_{1}}c_{9,4}=\mathbf{P}_{\mathbf{v}_{1}}c^{*}_{\\{6,7,8,9\\}}=\mathbf{P}\mathbf{c}_{6}=\mathbf{0}.$

  * •

$i=10,i=11$
This case is exactly like $i=1,i=2$.

  * •

$i=12,i=13$
This case is exactly like $i=3,i=4$.

We proved that in Example 1, $\mathbf{P}^{\Pi_{1}}$ in (95) is a non-effective
permutation of $\mathbf{P}$, i.e. $\mathbf{P}^{\Pi_{1}}\mathbf{M}=\mathbf{0}$.

######  Remark 7.

Any non-effective permutation
$\Pi:\\{1,\dots,v^{\beta}\\}\rightarrow\\{1,\dots,v^{\beta}\\}$ of the
relation matrix, $\mathbf{P}^{\Pi}$, is in the row span of the relation matrix
$\mathbf{P}$. Since $\mathbf{P}$ makes up the left null space of $\mathbf{M}$
by definition, $\mathbf{P}^{\Pi}\mathbf{M}=\mathbf{0}$ means
$\mathbf{P}^{\Pi}$ should be in the row span of $\mathbf{P}$. In other words,
any row of $\mathbf{P}^{\Pi}$ is a linear combination of the rows of
$\mathbf{P}$.

######  Lemma 2.

In a $\textrm{Vers}(f,N,K,\beta,v,\textrm{Lagrange})$ system, there are
$(v!)^{\beta}$ non-effective permutations of the relation matrix, out of all
$(v^{\beta})!$ permutations.

We know that the relation matrix has $v^{\beta}$ sub-matrices and hence, there
are $(v^{\beta})!$ possible permutations of relation matrix, including
effective and non-effective. Moreover, we know that each sub-matrix is
associated with a version vector that has $\beta$ elements from $[v]$. There
are $v!$ permutations for each of those $\beta$ elements, and $(v!)^{\beta}$
permutations in total. This lemma states that only those $(v!)^{\beta}$
permutations are non-effective. The proof of this lemma is in Appendix B.

##  VIII Fundamental Limit of $\textrm{Vers}(f,N,K,\beta,v,\textrm{Lagrange})$

In this section, we prove Theorem 1, and provide achievability and converse
proofs.

###  VIII-A Converse proof

In this proof, we show that there exists a particular adversarial behavior,
for which, $t=v^{\beta}d(K-1)$ messages from $t$ workers are not enough to
find $f(X_{k}),k\in\mathcal{H}$ correctly. In other words, we show that
$\\{f(W_{n}),\mathsf{tag}_{n},~{}n\in\mathcal{T}\\}$, where
$\mathcal{T}\subseteq[N]$, and $|\mathcal{T}|=v^{\beta}d(K-1)$, leads to more
that one possible value for at least one $f(X_{k}),k\in\mathcal{H}$.

Consider the adversarial behavior where the $\beta$ adversarial data owners
collude and distribute their messages to workers in $\mathcal{T}$ such that
for every $\mathbf{v}\in\mathcal{V}$, there exist exactly $d(K-1)$ workers in
$\mathcal{T}$ that receive adversarial messages whose versions are according
to $\mathbf{v}$.

For a set $\mathcal{S}\subseteq\mathbb{F}$, and an integer $D\in\mathbb{N}$,
let $\textrm{Van}_{\mathcal{S}}^{D}$ be a $|\mathcal{S}|\times(D+1)$
Vandermonde matrix that has $|\mathcal{S}|$ rows, and each row consists of
powers $0,1,\dots,D$ of an element of $\mathcal{S}$. For example,

$\displaystyle\textrm{Van}_{\\{\alpha_{1},\alpha_{2}\\}}^{3}=\begin{bmatrix}\alpha_{1}^{3}&\alpha_{1}^{2}&\alpha_{1}&1\\\
\alpha_{2}^{3}&\alpha_{2}^{2}&\alpha_{2}&1\end{bmatrix}.$

Step $1$. Suppose that an honest data owner $k\in\mathcal{H}$ receives
$y_{n}=f(W_{n})$, and $\mathsf{tag}_{n}$, from worker $n\in\mathcal{T}$. The
honest data owner uses tags from workers in $\mathcal{T}$ to make up
$v^{\beta}$ disjoint sets
$\mathcal{T}_{1},\dots,\mathcal{T}_{v^{\beta}}\subseteq\mathcal{T}$, such that
each set contains workers whose tags are equal, but different from tags of
workers in other sets. According to the adversarial behavior that we consider
in this proof, $N_{i}\coloneqq|\mathcal{T}_{i}|=d(K-1)$, $i\in[v^{\beta}]$.
The properties of the tag function ensure the honest data owner that the
$\beta$ adversarial messages used by workers $n\in\mathcal{T}_{i}$ and
$n^{\prime}\in\mathcal{T}_{j}$ from different sets are different in version of
at least one message. Recall that the honest data owner does not know the
adversarial data owners. Moreover, the honest data owner cannot know which
workers have previously received the same message from the adversarial data
owners, and thus have used the same messages in their computations, or, which
workers have previously received different messages from the adversarial data
owners, and thus have used different messages in their computations.
Step $2$. Let $\mathbf{y}_{i}=[y_{j}]_{j\in\mathcal{T}_{i}}$, and
$\mathbf{Q}_{i}=\textrm{Van}_{\\{\alpha_{n},n\in\mathcal{T}_{i}\\}}^{d(K-1)}$,
for $i\in[v^{\beta}]$. There is an underlying mapping
$\phi:[v^{\beta}]\rightarrow[v^{\beta}]$, that indicates the adversarial
messages that workers in $\mathcal{T}_{1},\dots,\mathcal{T}_{v^{\beta}}$ have
previously received from adversarial data owners. In particular, $\phi(i)=j$
means $\mathbf{y}_{i}=\mathbf{Q}_{i}\mathbf{u}_{\mathbf{v}_{j}}$, where
$i,j\in[v^{\beta}]$ and $u_{\mathbf{v}_{j}}$, $\mathbf{v}_{j}\in\mathcal{V}$
is a coefficient sub-vector defined in (15). In other words,
$\mathbf{y}_{i}=\mathbf{Q}_{i}\mathbf{u}_{\mathbf{v}_{j}}$ means that workers
$n\in\mathcal{T}_{i}$ have used adversarial messages whose versions are in
$\mathbf{v}_{j}$. Without loss of generality, assume that $\phi$ is the
identity permutation, i.e.
$\mathbf{y}_{i}=\mathbf{Q}_{i}\mathbf{u}_{\mathbf{v}_{i}}$, for all
$i\in[v^{\beta}]$.

The honest data owner $k$ considers a coefficient vector $\mathbf{U}^{\prime}$
as unknown, and tries to solve equations to find $\mathbf{U}^{\prime}$.
However, the honest data owner does not know $\phi$, so it needs to consider
all different possible cases for $\phi$, and make sure that all cases result
in a single $f(X_{k})$. Suppose that the honest data owner considers an
effective permutation $\Pi:[v^{\beta}]\rightarrow[v^{\beta}]$, and assumes
that $\mathbf{y}_{i}=\mathbf{Q}_{i}\mathbf{u}^{\prime}_{\mathbf{v}_{\Pi(i)}}$.
Therefore,

$\displaystyle\mathbf{Q}_{i}(\mathbf{u}_{\mathbf{v}_{i}}-\mathbf{u}^{\prime}_{\mathbf{v}_{\Pi(i)}})=\mathbf{0},\quad
i\in[v^{\beta}].$ (102)

Step $3$. Recall that $f(X_{k})=f(q^{(\mathbf{v})}(\omega_{k}))$,
$k\in\mathcal{H}$, for any $\mathbf{v}\in\mathcal{V}$, so

$\displaystyle\left[f(X_{k})\right]_{k\in\mathcal{H}}=\big{(}\textrm{Van}_{\\{\omega_{k},k\in\mathcal{H}\\}}^{d(K-1)+1}\big{)}\mathbf{u}_{\mathbf{v}_{i}},\quad
i\in[v^{\beta}]$ (103)

Consequently, all values of
$\textrm{Van}_{\\{\omega_{k},k\in\mathcal{H}\\}}^{d(K-1)+1}\mathbf{u}_{\mathbf{v}_{i}}$
for $i\in[v^{\beta}]$ are equal. Similarly, all values of
$\textrm{Van}_{\\{\omega_{k},k\in\mathcal{H}\\}}^{d(K-1)+1}\mathbf{u}^{\prime}_{\mathbf{v}_{\Pi(i)}}$,
for $i\in[v^{\beta}]$ are equal as well. We will show that any effective
permutation $\Pi$ results in different values for
$\textrm{Van}_{\\{\omega_{k},k\in\mathcal{H}\\}}^{d(K-1)+1}\mathbf{u}_{\mathbf{v}_{i}}$
and
$\textrm{Van}_{\\{\omega_{k},k\in\mathcal{H}\\}}^{d(K-1)+1}\mathbf{u}^{\prime}_{\mathbf{v}_{\Pi(i)}}$,
$i,j\in[v^{\beta}]$. If there exists one $i^{*}\in[v^{\beta}]$ such that

$\displaystyle\textrm{Van}_{\\{\omega_{k},k\in\mathcal{H}\\}}^{d(K-1)+1}(\mathbf{u}_{\mathbf{v}_{i^{*}}}-\mathbf{u}^{\prime}_{\mathbf{v}_{\Pi(i^{*})}})=\mathbf{0},$
(104)

then we can conclude that

$\displaystyle\left[f(X_{k})\right]_{k\in\mathcal{H}}=\big{(}\textrm{Van}_{\\{\omega_{k},k\in\mathcal{H}\\}}^{d(K-1)+1}\big{)}\mathbf{u}^{\prime}_{\mathbf{v}_{\Pi(i)}},\quad
i\in[v^{\beta}],$ (105)

because

$\displaystyle\left[f(X_{k})\right]_{k\in\mathcal{H}}=\big{(}\textrm{Van}_{\\{\omega_{k},k\in\mathcal{H}\\}}^{d(K-1)+1}\big{)}\mathbf{u}_{\mathbf{v}_{i^{*}}}$
(106)

and

$\displaystyle\big{(}\textrm{Van}_{\\{\omega_{k},k\in\mathcal{H}\\}}^{d(K-1)+1}\big{)}\mathbf{u}^{\prime}_{\mathbf{v}_{\Pi(i)}}=\big{(}\textrm{Van}_{\\{\omega_{k},k\in\mathcal{H}\\}}^{d(K-1)+1}\big{)}\mathbf{u}^{\prime}_{\mathbf{v}_{\Pi(i^{*})}},\quad
i\in[v^{\beta}].$ (107)

In other words, if there exists such $i^{*}$, permutation $\Pi$ results in
correct answer for $f(X_{k}),k\in\mathcal{H}$. By contradiction, we suppose
that there exists such $i^{*}$. Therefore,

$\displaystyle\begin{split}\mathbf{Q}_{i}(\mathbf{u}_{\mathbf{v}_{i}}-\mathbf{u}^{\prime}_{\mathbf{v}_{\Pi(i)}})&=\mathbf{0},\quad
i\in[v^{\beta}],\\\
\big{(}\textrm{Van}_{\\{\omega_{k},k\in\mathcal{H}\\}}^{d(K-1)+1}\big{)}(\mathbf{u}_{\mathbf{v}_{i}}-\mathbf{u}^{\prime}_{\mathbf{v}_{\Pi(i)}})&=\mathbf{0},\quad
i\in[v^{\beta}].\end{split}$ (108)

The matrix $\mathbf{Q}_{i}$ only contains powers of
$\alpha_{n},n\in\mathcal{T}_{i}$, and
$\textrm{Van}_{\\{\omega_{k},k\in\mathcal{H}\\}}^{d(K-1)+1}$ contains powers
of $\omega_{k},k\in\mathcal{H}$, and these elements are distinct and chosen
uniformly at random from $\mathbb{F}$. Therefore, the matrix

$\displaystyle\left[\begin{array}[]{c}\mathbf{Q}_{i}\\\
\hdashline\textrm{Van}_{\\{\omega_{k},k\in\mathcal{H}\\}}^{d(K-1)+1}\end{array}\right]$

is MDS, its dimension is $(d(K-1)+h)\times(d(K-1)+1)$, and its rank is
$d(K-1)+1$. The length of
$\mathbf{u}_{\mathbf{v}_{i}}-\mathbf{u}^{\prime}_{\mathbf{v}_{\Pi(i)}}$ is
$d(K-1)+1$, therefore any $d(K-1)+1$ equations of (108) result in

$\displaystyle\mathbf{u}_{\mathbf{v}_{i}}=\mathbf{u}^{\prime}_{\mathbf{v}_{\Pi(i)}},\quad
i\in[v^{\beta}].$ (109)

Step $4$. We know that $\mathbf{P}\mathbf{U}=0$ and
$\mathbf{P}\mathbf{U}^{\prime}=0$, thus,

$\displaystyle\mathbf{P}_{\mathbf{v}_{1}}\mathbf{u}_{\mathbf{v}_{1}}+\dots+\mathbf{P}_{\mathbf{v}_{v^{\beta}}}\mathbf{u}_{\mathbf{v}_{v^{\beta}}}$
$\displaystyle=\mathbf{0},$ (110)
$\displaystyle\mathbf{P}_{\mathbf{v}_{\Pi(1)}}\mathbf{u}^{\prime}_{\mathbf{v}_{\Pi(1)}}+\dots+\mathbf{P}_{\mathbf{v}_{\Pi(v^{\beta})}}\mathbf{u}^{\prime}_{\mathbf{v}_{\Pi(v^{\beta})}}$
$\displaystyle=\mathbf{0}.$ (111)

We substitute (109) in (111),

$\displaystyle\mathbf{P}_{\mathbf{v}_{\Pi(1)}}\mathbf{u}_{\mathbf{v}_{1}}+\dots+\mathbf{P}_{\mathbf{v}_{\Pi(v^{\beta})}}\mathbf{u}_{\mathbf{v}_{v^{\beta}}}$
$\displaystyle=\mathbf{0},$ (112)

Recall that $\Pi$ is an effective permutation, so according to definition,
$[\mathbf{P}_{\mathbf{v}_{\Pi(1)}}~{}\dots~{}\mathbf{P}_{\mathbf{v}_{\Pi(v^{\beta})}}]$
is not in row span of $\mathbf{P}$. Therefore, equation (112) exerts
additional constraint on $\mathbf{U}$ and consequently all messages of data
owners. However, messages of data owners, honest and adversarial, can have any
value and any constraint on them means contradiction. This concludes the
converse proof.

###  VIII-B Achievability Proof

In the achievability proof, we suppose that the honest data owner
$k\in\mathcal{H}$ receives $t^{*}=v^{\beta}d(K-1)+1$ messages from $t^{*}$
workers. The honest data owner uses the received tags to make up $v^{\beta}$
disjoint sets of workers, such that each set contains workers whose tags are
equal but different from tags of workers in other sets. Since
$t^{*}>v^{\beta}d(K-1)$, one of these sets definitely contains at least
$d(K-1)+1$ workers, which we call $\mathcal{T^{*}}$. There exists
$i^{*}\in[v^{\beta}]$ such that

$\displaystyle\big{(}\textrm{Van}_{\\{\alpha_{n},n\in\mathcal{T^{*}}\\}}^{d(K-1)}\big{)}\mathbf{u}_{\mathbf{v}_{i^{*}}}=[y_{j}]_{j\in\mathcal{T^{*}}}.$
(113)

This equation determines $\mathbf{u}_{\mathbf{v}_{i^{*}}}$ uniquely. Then, the
honest data owner can find
$f(X_{k})=\big{(}\textrm{Van}_{\omega_{k}}^{d(K-1)}\big{)}\mathbf{u}_{\mathbf{v}_{i^{*}}}$.
This completes the proof.

One of the assumptions in Theorem 1 is that workers are honest and send the
correct values of $f(W_{n}),\mathsf{tag}_{n},~{}n\in[N]$ to data owners.
Suppose that $a\in\mathbb{N},a\leq N$ workers are malicious and may send
incorrect $f(W_{n})$ or $\mathsf{tag}_{n}$ back to data owners. Incorrect tag
values are detrimental, because they mislead data owners in partitioning.
Following the notations in converse proof, assume that
$\mathbf{y}_{i}=\mathbf{Q}_{i}\mathbf{u}_{\mathbf{v}_{i}}+\mathbf{e}_{i}$ is
the truth, and
$\mathbf{y}_{i}=\mathbf{Q}_{i}\mathbf{u}^{\prime}_{\Pi(\mathbf{v}_{i})}+\mathbf{e}^{\prime}_{i}$
is an assumption that an honest data owner makes because of not knowing the
truth, and $\mathbf{e}_{i},\mathbf{e}^{\prime}_{i}$ are error vectors.
Therefore, in the presence of adversarial workers, equation (102) does not
hold anymore, and the approach used in the previous converse proof can not be
used here. However, we know from coding theory that results from
$t=v^{\beta}d(K-1)+1+2a$ workers are enough to decode
$f(X_{k}),k\in\mathcal{H}$ correctly.

##  Appendix A Proof of Theorem 2

In order to show that a tag function exists, we consider all $J$ functions
from $\mathbb{U}^{K}$ to $\mathbb{U}$ to be equiprobable and calculate the
average probability of the event that two arbitrary workers produce the same
tag. Consider two workers $n_{1},n_{2}\in[N]$ that receive different
$X_{\mathcal{A},n_{1}}$ and $X_{\mathcal{A},n_{2}}$ from adversarial data
owners, and $X_{\mathcal{H}}$ from honest data owners. We show that the
average probability of $\mathsf{tag}_{n_{1}}=\mathsf{tag}_{n_{2}}$, taken over
all $J$ functions, and the messages of honest data owners, is very small.
Then, we conclude that there exists a function, for which the average
probability of $\mathsf{tag}_{n_{1}}=\mathsf{tag}_{n_{2}}$, taken over the
messages of honest data owners, is very small, which means a tag function
exists.

Any function $J$ from $\mathbb{U}^{K}$ to $\mathbb{U}$, i.e. from a large
space to a small space, would map some different inputs to the same outputs.
For a function $J$, and two adversarial messages $X_{\mathcal{A},n_{1}}$ and
$X_{\mathcal{A},n_{2}}$, we define a function $g$ such that
$\mathcal{S}\coloneqq
g(J,X_{\mathcal{A},n_{1}},X_{\mathcal{A},n_{2}})\subseteq\mathbb{U}^{h}$ is
the set that

$\displaystyle
X_{\mathcal{H}}\in\mathcal{S}:J(X_{\mathcal{H}},X_{\mathcal{A},n_{1}})=J(X_{\mathcal{H}},X_{\mathcal{A},n_{2}}),$
$\displaystyle
X_{\mathcal{H}}\in\mathbb{U}^{h}\setminus\mathcal{S}:J(X_{\mathcal{H}},X_{\mathcal{A},n_{1}})\neq
J(X_{\mathcal{H}},X_{\mathcal{A},n_{2}}).$

Since the data of honest data owners are uniformly and independently chosen
from $\mathbb{U}^{h}$, and are independent of $X_{\mathcal{A},n_{1}}$ and
$X_{\mathcal{A},n_{2}}$,

$\displaystyle\textrm{Pr}\big{(}J(X_{\mathcal{H}},X_{\mathcal{A},n_{1}})=J(X_{\mathcal{H}},X_{\mathcal{A},n_{2}})\big{)}=\frac{|\mathcal{S}|}{\mathbb{U}^{h}},$
(114)

where
$\mathcal{S}=g(J,X_{\mathcal{A},n_{1}},X_{\mathcal{A},n_{2}})\subseteq\mathbb{U}^{h}$.
Since all $J$ functions are equiprobable, i.e.
$\textrm{Pr}(J)=\frac{1}{|\mathbb{U}|^{K}}$,

$\displaystyle\sum_{J:g(J,X_{\mathcal{A},n_{1}},X_{\mathcal{A},n_{2}})=\mathcal{S}}\textrm{Pr}(J)=(1-\frac{1}{|\mathbb{U}|})^{(|\mathbb{U}|^{h}-|\mathcal{S}|)}(\frac{1}{|\mathbb{U}|})^{|\mathcal{S}|}.$
(115)

Using (114) and (115),

$\displaystyle\textrm{Pr}(\mathsf{tag}_{n_{1}}=\mathsf{tag}_{n_{2}})$
$\displaystyle=\sum_{\mathcal{S}}\sum_{J:g(J,X_{\mathcal{A},n_{1}},X_{\mathcal{A},n_{2}})=\mathcal{S}}\textrm{Pr}(J)\textrm{Pr}\big{(}J(X_{\mathcal{H}},X_{\mathcal{A},n_{1}})=J(X_{\mathcal{H}},X_{\mathcal{A},n_{2}})\big{)}$
$\displaystyle=\sum_{\mathcal{S}}(1-\frac{1}{|\mathbb{U}|})^{(|\mathbb{U}|^{h}-|\mathcal{S}|)}(\frac{1}{|\mathbb{U}|})^{|\mathcal{S}|}\frac{|\mathcal{S}|}{\mathbb{U}^{h}}$
$\displaystyle=\sum_{s=1}^{|\mathbb{U}|^{h}}\binom{|\mathbb{U}|^{h}}{s}(1-\frac{1}{|\mathbb{U}|})^{(|\mathbb{U}|^{h}-s)}(\frac{1}{|\mathbb{U}|})^{s}\frac{s}{\mathbb{U}^{h}}$
$\displaystyle=\sum_{s=1}^{|\mathbb{U}|^{h}}\binom{|\mathbb{U}|^{h}-1}{s-1}(1-\frac{1}{|\mathbb{U}|})^{(|\mathbb{U}|^{h}-s)}(\frac{1}{|\mathbb{U}|})^{s}=\frac{1}{|\mathbb{U}|}$
(116)

If $\mathbb{U}$ is large enough that $\frac{1}{\epsilon}\leq|\mathbb{U}|$,
then $\textrm{Pr}(\mathsf{tag}_{n_{1}}=\mathsf{tag}_{n_{2}})\leq\epsilon$, and
the proof is complete.

##  Appendix B Proof of Lemma 2

In this appendix, we prove that there are $(v!)^{\beta}$ non-effective
permutations of the relation matrix. In Section VII, we examined an example,
and proved the non-effectiveness of a permutation of its relation matrix. The
understanding of that example is helpful for understanding the proof in this
section.

We show that all permutations of the relation matrix of the form
$\Pi=\pi_{1}\times\pi_{2}\times\dots\times\pi_{\beta}$ are non-effective, i.e.
$\mathbf{P}^{\Pi}\mathbf{M}=\mathbf{0}$, where $\pi_{i}:[v]\rightarrow[v]$,
$i\in[\beta]$ is a permutation on $[v]$. We parse the proof into the following
steps.

### Step 1

Consider column $i\in[L]$,
$\mathbf{c}_{i}=[c_{\mathbf{v}_{1},i}^{\intercal}~{}\dots~{}c_{\mathbf{v}_{v^{\beta}},i}^{\intercal}]^{\intercal}$
of $\mathbf{M}$, where the length of each so called sub-column
$c_{\mathbf{v}_{i}},i\in[v^{\beta}]$ is $d(K-1)+1$,
$\\{\mathbf{v}_{1},\dots,\mathbf{v}_{v^{\beta}}\\}=\mathcal{V}$, and $L$ is
the length of monomial vector $\mathbf{X}$.

The sub-column $c_{\mathbf{v},i}$, $\mathbf{v}\in\mathcal{V},i\in[L]$,
contains the coefficients of monomial $\mathbf{X}[i]$ in coefficient sub-
vector $\mathbf{u}_{\mathbf{v}}$. If coefficient sub-vector
$\mathbf{u}_{\mathbf{v}}$ does not have the monomial $\mathbf{X}[i]$, then
$c_{\mathbf{v},i}=\mathbf{0}$. For two coefficient sub-vectors
$\mathbf{u}_{\mathbf{v}}$ and $\mathbf{u}_{\mathbf{v^{\prime}}}$ that both
have $\mathbf{X}[i]$, $c_{\mathbf{v},i}=c_{\mathbf{v^{\prime}},i}\coloneqq
c^{*}_{i}$, because these coefficient sub-vectors only differ in adversarial
messages, and not the constant coefficients. Therefore, the nonzero sub-
columns in a column of $\mathbf{M}$ are the same. This is evident in
$\mathbf{M}$ of Example 1 in (90).

We define two neighbour columns of $\mathbf{M}$ as following. Consider two
columns $i,i^{\prime}\in[L]$, where the adversarial and honest messages in
monomials $\mathbf{X}[i]$ and $\mathbf{X}[i^{\prime}]$ are the same, but the
versions of adversarial messages in them are different. For example,
$i=6,i^{\prime}=7$ in (90) correspond to monomials $X_{1}^{(1)}X_{2}^{(1)}$
and $X_{1}^{(2)}X_{2}^{(1)}$, which differ in the version of $X_{1}$, but both
are made of the same messages $X_{1}$ and $X_{2}$. For two neighbour columns,
$c^{*}_{i}=c^{*}_{i^{\prime}}$, i.e. the nonzero sub-columns in two neighbour
columns are the same. For example, the nonzero sub-columns of columns $6$ and
$7$ in (90) are the same.

### Step 2

Let $\mathcal{V}_{\mathbf{c}_{i}}$, $i\in[L]$, be the set of version vectors
of coefficient sub-vectors that have the monomial $\mathbf{X}[i]$, or in other
words, version vectors that correspond to nonzero sub-columns of
$\mathbf{c}_{i}$. For instance, in Example 1, using (28) and (90), we find
that $\mathcal{V}_{\mathbf{c}_{1}}=\\{[1,1,0],[1,2,0]\\}$,
$\mathcal{V}_{\mathbf{c}_{2}}=\\{[2,1,0],[2,2,0]\\}$,
$\mathcal{V}_{\mathbf{c}_{3}}=\\{[1,1,0],[2,1,0]\\}$, and so forth. From the
previous step, we know that $c_{\mathbf{v},i}=c_{i}^{*}$ for
$\mathbf{v}\in\mathcal{V}_{\mathbf{c}_{i}}$. For each column $\mathbf{c}_{i}$
of $\mathbf{M}$, there are two possible cases.

  * •

Case 1. The monomial $\mathbf{X}[i]$ is comprised of honest messages only,
e.g. $(X_{3})^{2}$. In this case, all sub-columns of $\mathbf{c}_{i}$ are
equal and nonzero, i.e.
$c_{\mathbf{v}_{1},i}=\dots=c_{\mathbf{v}_{v^{\beta}},i}\coloneqq c^{*}_{i}$,
and $\mathcal{V}_{\mathbf{c}_{i}}=\mathcal{V}$. In Example 1, $\mathbf{c}_{5}$
of $\mathbf{M}$ in (90) is of this kind, as

$\displaystyle
c_{\mathbf{v}_{1},5}=c_{\mathbf{v}_{2},5}=c_{\mathbf{v}_{3},5}=c_{\mathbf{v}_{4},5}=\begin{bmatrix}\frac{1}{4}\\\
-\frac{3}{2}\\\ \frac{13}{4}\\\ -3\\\ 1\end{bmatrix}$ (117)

  * •

Case 2. The monomial $\mathbf{X}[i]$ contains adversarial messages, e.g.
$X[i]=(X^{(1)}_{1})^{2}$. In this case, version vectors
$\mathbf{v}\in\mathcal{V}_{\mathbf{c}_{i}}$ have the same version value for
the adversarial messages in $X[i]$. For example,
$\mathcal{V}_{\mathbf{c}_{1}}=\\{[1,1,0],[1,2,0]\\}$, and version vectors in
$\mathcal{V}_{\mathbf{c}_{1}}$ indicate version $(1)$ for $X_{1}$ because
$X[i]=(X^{(1)}_{1})^{2}$. As another example, for $X[11]=X_{1}^{(2)}X_{3}$ in
(90), $\mathcal{V}_{\mathbf{c}_{11}}=\\{[2,1,0],[2,2,0]\\}$, and version
vectors in $\mathcal{V}_{\mathbf{c}_{11}}$ indicate version $(2)$ for $X_{1}$.

### Step 3

We know $\mathbf{P}\mathbf{c}_{i}=\mathbf{0}$, $i\in[L]$. Recall that
$\mathbf{P}=[\mathbf{P}_{\mathbf{v}_{1}}\dots\mathbf{P}_{\mathbf{v}_{v^{\beta}}}]$,
where $\\{\mathbf{v}_{1},\dots,\mathbf{v}_{v^{\beta}}\\}=\mathcal{V}$.
Therefore,

$\displaystyle\mathbf{P}\mathbf{c}_{i}=\sum_{\mathbf{v}\in\mathcal{V}_{\mathbf{c}_{i}}}\mathbf{P}_{\mathbf{v}}c_{\mathbf{v},i}=\bigg{(}\sum_{\mathbf{v}\in\mathcal{V}_{\mathbf{c}_{i}}}\mathbf{P}_{\mathbf{v}}\bigg{)}c^{*}_{i}=\mathbf{0}$
(118)

Consider a permutation of form
$\Pi=\pi_{1}\times\pi_{2}\times\dots\times\pi_{\beta}$, where
$\pi_{i}:[v]\rightarrow[v]$, $i\in[\beta]$. Assume that this permutation is as
following.

  * •

For a particular adversarial message $X_{k},k\in\mathcal{A}$, and two
particular version values $m,m^{\prime}\in[v]$,

$\displaystyle\pi_{k}[m]$ $\displaystyle=m^{\prime},$
$\displaystyle\pi_{k}[m^{\prime}]$ $\displaystyle=m,$
$\displaystyle\pi_{k}[l]$ $\displaystyle=l,l\neq m,m^{\prime}.$

  * •

For all $j\in\mathcal{A},j\neq k$,

$\displaystyle\pi_{j}[l]=l,\quad l\in[v].$

It suffices to prove the non-effectiveness of this permutation, because any
other permutation is built from units of permutations like this. For each
column $\mathbf{c}_{i}$, there are two possible cases following the cases in
the previous step.

  * •

Case 1. If $\mathcal{V}_{\mathbf{c}_{i}}=\mathcal{V}$, then

$\displaystyle\mathbf{P}^{\Pi}\mathbf{c}_{i}=(\sum_{\mathbf{v}\in\mathcal{V}}\mathbf{P}_{\mathbf{v}})c^{*}_{i}=\mathbf{P}\mathbf{c}_{i}=\mathbf{0}.$
(119)

  * •

Case 2. Assume that monomial $\mathbf{X}[i]$ contains version $m$ of the
adversarial message $k$. There is a monomial $\mathbf{X}[i^{\prime}]$,
$i^{\prime}\in[L]$ that differs from $\mathbf{X}[i]$ only in the version of
$X_{k}$, which is $m^{\prime}$ in $\mathbf{X}[i^{\prime}]$. Clearly,

$\displaystyle\mathbf{P}\mathbf{c}_{i^{\prime}}=\sum_{\mathbf{v}\in\mathcal{V}_{\mathbf{c}_{i^{\prime}}}}\mathbf{P}_{\mathbf{v}}c_{\mathbf{v},{i^{\prime}}}=\bigg{(}\sum_{\mathbf{v}\in\mathcal{V}_{\mathbf{c}_{i^{\prime}}}}\mathbf{P}_{\mathbf{v}}\bigg{)}c^{*}_{i^{\prime}}=\mathbf{0}.$
(120)

It is easy to verify that for each
$\mathbf{v}^{\prime}\in\mathcal{V}_{\mathbf{c}_{i^{\prime}}}$, there is a
$\mathbf{v}\in\mathcal{V}_{\mathbf{c}_{i}}$, where
$\mathbf{v}^{\prime}[k]=m^{\prime}$ and $\mathbf{v}[k]=m$. From the definition
in Step 1, we know that columns $i$ and $i^{\prime}$ are neighbours and thus,
$c^{*}_{i}=c^{*}_{i^{\prime}}$. Therefore,

$\displaystyle\mathbf{P}^{\Pi}\mathbf{c}_{i}=\sum_{\begin{subarray}{c}\mathbf{v^{\prime}}\in\mathcal{V}_{\mathbf{c}_{i^{\prime}}}\\\
\mathbf{v}\in\mathcal{V}_{\mathbf{c}_{i}}\end{subarray}}\mathbf{P}_{\mathbf{v^{\prime}}}c_{\mathbf{v},{i}}=\bigg{(}\sum_{\mathbf{v}\in\mathcal{V}_{\mathbf{c}_{i^{\prime}}}}\mathbf{P}_{\mathbf{v}}\bigg{)}c^{*}_{i}=\bigg{(}\sum_{\mathbf{v}\in\mathcal{V}_{\mathbf{c}_{i^{\prime}}}}\mathbf{P}_{\mathbf{v}}\bigg{)}c^{*}_{i^{\prime}}=\mathbf{0},$
(121)

where the last equality is due to (120). In summary, we proved
$\mathbf{P}^{\Pi}\mathbf{c}_{i}=\mathbf{0}$ using
$\mathbf{P}\mathbf{c}_{i^{\prime}}=\mathbf{0}$.

## References

  * [1] S. Li and S. Avestimehr, “Coded computing,” _Foundations and Trends® in Communications and Information Theory_ , vol. 17, no. 1, 2020.
  * [2] J. S. Ng, W. Y. B. Lim, N. C. Luong, Z. Xiong, A. Asheralieva, D. Niyato, C. Leung, and C. Miao, “A comprehensive survey on coded distributed computing: Fundamentals, challenges, and networking applications,” _IEEE Communications Surveys & Tutorials_, 2021.
  * [3] Q. Yang, Y. Liu, Y. Cheng, Y. Kang, T. Chen, and H. Yu, “Federated learning,” _Synthesis Lectures on Artificial Intelligence and Machine Learning_ , vol. 13, no. 3, pp. 1–207, 2019.
  * [4] H. Jeong, “Fully-decentralized coded computing for reliable large-scale computing,” Ph.D. dissertation, Carnegie Mellon University, 2020.
  * [5] Y. Sun, F. Zhang, J. Zhao, S. Zhou, Z. Niu, and D. Gündüz, “Coded computation across shared heterogeneous workers with communication delay,” _arXiv preprint arXiv:2109.11246_ , 2021.
  * [6] C. Wang and N. Raviv, “All-to-all encode in synchronous systems,” _arXiv preprint arXiv:2205.05183_ , 2022.
  * [7] S. Sundaram and C. N. Hadjicostis, “Distributed function calculation and consensus using linear iterative strategies,” _IEEE journal on selected areas in communications_ , vol. 26, no. 4, pp. 650–660, 2008.
  * [8] ——, “Distributed function calculation via linear iterative strategies in the presence of malicious agents,” _IEEE Transactions on Automatic Control_ , vol. 56, no. 7, pp. 1495–1508, 2010.
  * [9] C.-S. Yang and A. S. Avestimehr, “Coded computing for secure boolean computations,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 1, pp. 326–337, 2021.
  * [10] M. Soleymani, R. E. Ali, H. Mahdavifar, and A. S. Avestimehr, “List-decodable coded computing: Breaking the adversarial toleration barrier,” _arXiv preprint arXiv:2101.11653_ , 2021.
  * [11] L. Chen, H. Wang, Z. Charles, and D. Papailiopoulos, “Draco: Byzantine-resilient distributed training via redundant gradients,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 903–912.
  * [12] Q. Yu, S. Li, N. Raviv, S. M. M. Kalan, M. Soltanolkotabi, and S. A. Avestimehr, “Lagrange coded computing: Optimal design for resiliency, security, and privacy,” in _The 22nd International Conference on Artificial Intelligence and Statistics_. PMLR, 2019, pp. 1215–1225.
  * [13] N. A. Khooshemehr and M. A. Maddah-Ali, “Fundamental limits of distributed linear encoding,” _IEEE Transactions on Information Theory_ , vol. 67, no. 12, pp. 7985–7998, 2021.
  * [14] M. Pease, R. Shostak, and L. Lamport, “Reaching agreement in the presence of faults,” _Journal of the ACM (JACM)_ , vol. 27, no. 2, pp. 228–234, 1980\.
  * [15] L. Lamport, R. Shostak, and M. Pease, “The byzantine generals problem,” in _Concurrency: the works of leslie lamport_ , 2019, pp. 203–226.
  * [16] R. Canetti and T. Rabin, “Fast asynchronous byzantine agreement with optimal resilience,” in _Proceedings of the twenty-fifth annual ACM symposium on Theory of computing_ , 1993, pp. 42–51.
  * [17] G. Bracha, “An asynchronous [(n-1)/3]-resilient consensus protocol,” in _Proceedings of the third annual ACM symposium on Principles of distributed computing_ , 1984, pp. 154–162.
  * [18] C. Cachin, K. Kursawe, F. Petzold, and V. Shoup, “Secure and efficient asynchronous broadcast protocols,” in _Annual International Cryptology Conference_. Springer, 2001, pp. 524–541.
  * [19] A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song, “The honey badger of bft protocols,” in _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , 2016, pp. 31–42.
  * [20] C. Cachin and S. Tessaro, “Asynchronous verifiable information dispersal,” in _24th IEEE Symposium on Reliable Distributed Systems (SRDS’05)_. IEEE, 2005, pp. 191–201.
  * [21] J. Hendricks, G. R. Ganger, and M. K. Reiter, “Verifying distributed erasure-coded data,” in _Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing_ , 2007, pp. 139–146.
  * [22] L. Yang, S. J. Park, M. Alizadeh, S. Kannan, and D. Tse, “$\\{$DispersedLedger$\\}$:$\\{$High-Throughput$\\}$ byzantine consensus on variable bandwidth networks,” in _19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22)_ , 2022, pp. 493–512.
  * [23] I. Abraham, P. Jovanovic, M. Maller, S. Meiklejohn, G. Stern, and A. Tomescu, “Reaching consensus for asynchronous distributed key generation,” in _Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing_ , 2021, pp. 363–373.
  * [24] G. Bracha, “Asynchronous byzantine agreement protocols,” _Information and Computation_ , vol. 75, no. 2, pp. 130–143, 1987.
  * [25] “Mirai botnet,” March 2023. [Online]. Available: https://www.cloudflare.com/learning/ddos/glossary/mirai-botnet/
  * [26] A. I. Sanka and R. C. Cheung, “A systematic review of blockchain scalability: Issues, solutions, analysis and future research,” _Journal of Network and Computer Applications_ , vol. 195, p. 103232, 2021.
  * [27] M. H. Nasir, J. Arshad, M. M. Khan, M. Fatima, K. Salah, and R. Jayaraman, “Scalable blockchains—a systematic review,” _Future generation computer systems_ , vol. 126, pp. 136–162, 2022.
  * [28] “Ethereum sharding,” Feb 2023. [Online]. Available: https://ethereum.org/en/upgrades/sharding/
  * [29] E. Kokoris-Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta, and B. Ford, “Omniledger: A secure, scale-out, decentralized ledger via sharding,” in _2018 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2018, pp. 583–598.
  * [30] M. Zamani, M. Movahedi, and M. Raykova, “Rapidchain: Scaling blockchain via full sharding,” in _Proceedings of the 2018 ACM SIGSAC conference on computer and communications security_ , 2018, pp. 931–948.
  * [31] S. Li, M. Yu, C.-S. Yang, A. S. Avestimehr, S. Kannan, and P. Viswanath, “Polyshard: Coded sharding achieves linearly scaling efficiency and security simultaneously,” _IEEE Transactions on Information Forensics and Security_ , vol. 16, pp. 249–261, 2020.
  * [32] N. A. Khooshemehr and M. A. Maddah-Ali, “The discrepancy attack on polyshard-ed blockchains,” in _2021 IEEE International Symposium on Information Theory (ISIT)_ , 2021, pp. 2672–2677.
  * [33] M. O. Rabin, “Fingerprinting by random polynomials,” _Technical report_ , 1981\.
  * [34] J. Katz and Y. Lindell, _Introduction to modern cryptography_. CRC press, 2020.