text:
\section{Abstract}

Decentralized computation outsourcing should allow anyone to access the large amounts of computational power that exists in the Internet of Things. Unfortunately, when trusted third parties are removed to achieve this decentralization, ensuring an outsourced computation is performed correctly remains a significant challenge. In this paper, we provide a solution to this problem.

We outline $\text{Marvel DC}$, a fully decentralized blockchain-based distributed-computing protocol which formally guarantees that computers are strictly incentivized to correctly perform requested computations. Furthermore, $\text{Marvel DC}$ utilizes a reputation management protocol to ensure that, for any minority of computers not performing calculations correctly, these computers are identified and selected for computations with diminishing probability. We then outline Privacy $\text{Marvel DC}$, a privacy-enhanced version of $\text{Marvel DC}$ which decouples results from the computers which computed them, making the protocol suitable for computations such as Federated Learning, where results can reveal sensitive information about that computer that computed them.
We provide an implementation of $\text{Marvel DC}$ and analyses of both protocols, demonstrating that they are not only the first protocols to provide the aforementioned formal guarantees, but are also practical, competitive with prior attempts in the field, and ready to deploy.

\textbf{Keywords:} Distributed Computing, Decentralization, Blockchain, Incentives

\section{Introduction}

The distributing of computation among computers has beckoned a never-before-seen level of computing power available to average users with access to as little as a smart phone and an average internet connection. Distributed computations (DCs) have typically been outsourced directly to one of the few centralized Big Tech. providers such as Amazon Web Services, or Google Cloud. Unfortunately, centralized services like these have many drawbacks. Monopoly of resources, centralized trust, restricted access for certain clients, and in the case of Federated Learning (FL), lack of diverse data-sets make these centralized services unfit for many users and purposes. Full decentralization solves all of these issues. Unfortunately, decentralizing distributed-computing protocols brings many new challenges that are largely protected against in the centralized setting. A significant issue in many  existing decentralized DC implementations \cite{BlockchainDecentralisedFedLearningLi,FLChainBao,FLChainMajeed,FedLearningMeetsBlockchainMa,BlockFLKim,DeepChainWeng, BlockchainRepAwareFedLearningRehman,IncentiveMechFLBlockchainToyoda} is the accurate rewarding of computers to incentivize rational computers, computers who try to maximize their utility (e.g. in cryptocurrency tokens), to correctly perform outsourced computations. In decentralized settings such as blockchain protocols, players only follow an action(s) if that action(s) is(are) strong incentive compatible, resulting in strictly higher payoffs than the alternatives. One method to combat this is, for a given computation, to use zero-knowledge (ZK) tools to prove that a computer performed the actions as prescribed by the requester \cite{FairnessIntegrityPrivacyBlockchainBasedFLSystemRuckel}. Although theoretically any computation can be encoded in this way, the practicality of requiring requesters, typically with low computing power by the nature of outsourcing, to encode their computation as a ZK-circuit to allow for the proving of correct computation is an open question. Furthermore, the pre-computation work required by requesters in \cite{FairnessIntegrityPrivacyBlockchainBasedFLSystemRuckel} is itself intensive (3-40 minutes using 16 virtual CPU cores, and 64 GB RAM), and not appropriate for computationally-restricted requesters, defeating a significant purpose of DC protocols. In this paper, we address all of these issues.

\subsection{Our Contribution}

We present $\text{Marvel DC}$, a generic (can be adapted to any computational problem outputting results in Euclidean space) blockchain-based decentralized DC protocol which addresses the many gaps that exist in outsourcing computations without the use of a trusted third-party (TTP). Namely, $\text{Marvel DC}$ provides for the first time in literature a decentralized DC protocol which ensures rational computers are strongly incentivized to follow the protocol. This is a significant advancement in a field where existing claims of incentive compatibility do not account for computers trying to maximize their tokens, with no viable solution, to the best of our knowledge, for the distributing of tokenized rewards in a distributed and decentralized manner.

Furthermore, $\text{Marvel DC}$ utilizes reputations to isolate correctly-performing computers when selecting computers for computations. This allows $\text{Marvel DC}$ to efficiently remove adversarial computers from the protocol. As these reputations are maintained on the blockchain itself, through careful construction (Section \ref{sec:Reputation}) this reputation protocol neither affects the decentralisation or strong incentive compatibility of the protocol. When using a fixed number of computers per computation, our protocol shares all of the benefits of \cite{CoUtileP2PDecentralizedComputing}.
Our description of $\text{Marvel DC}$ can be adapted to run on any smart-contract enabled blockchain, and as such, can make use of the vast existing communities which exist on such blockchains. This is a further improvement on protocols which require the recruitment and constant participation of an independent network of computers. In a blockchain, where computers form a subset of users, computers can be dormant until required to perform a computation. By deploying on an existing blockchain, any player in that blockchain can also participate in $\text{Marvel DC}$ as a computer and/or requester. We summarize the main contributions of $\text{Marvel DC}$ as follows:

\begin{itemize}

    \item \textbf{Strong incentive compatibility in expectation}. In Section \ref{sec:SINCE}, we describe how to program rewards such that it is strong incentive compatible in expectation for every rational player (requesters, computers and/or block-producers) in the blockchain system to follow the protocol.

    \item \textbf{Handling of symmetric/asymmetric utilities}. By tokenising the protocol rewards, we are able to handle both symmetric (rational computers and requesters only want to produce good results) and asymmetric (rational computers want to be compensated financially) utilities.

    \item \textbf{Decentralization}. Encoding $\text{Marvel DC}$ in a generic manner for any tokenized smart-contract enabled blockchain, all players in such a  blockchain system are able to participate in $\text{Marvel DC}$. Furthermore, all of the tools used in $\text{Marvel DC}$ are already in use in smart-contract enabled decentralized systems such as Ethereum \footnote{\url{https://ethereum.org/en/}} and Harmony \footnote{\url{https://www.harmony.one/}} (our smart-contract encoding \cite{MarvelDCGithub} is written in Solidity \cite{MarvelDCGithub}, a programming language interpretable by both blockchains ), demonstrating our encoding can utilize the decentralisation of such blockchain ecosystems.

\end{itemize}

On top of these main contributions, $\text{Marvel DC}$ also retains additional desirable properties that should be present in any DC protocol:

\begin{itemize}

    \item \textbf{Fair selection}. Our protocol uses a decentralized pseudorandom function (such as a verifiable on-chain oracles\footnote{\url{https://docs.chain.link/docs/chainlink-vrf/}}, or those used in  \cite{ShieldedComputationsInSmartContractsOvercomingForksVisconti}) to provide a random seed used to select computers based on reputation. This removes the possibility of reputation-based manipulation by clusters of colluding computers who may try to prioritize the selection of computers in the colluding cluster, as is allowed in existing works \cite{CoUtileP2PDecentralizedComputing,CoUtileReputationProtocol, FairnessIntegrityPrivacyBlockchainBasedFLSystemRuckel}.

    \item \textbf{Proper management of new peers}. All new computers entering $\text{Marvel DC}$ are given the same initial reputation, which eventually becomes significantly lower than the average reputation of active honestly-behaving computers.

    \item \textbf{Low communication complexity $\&$ cost}. By utilising a blockchain, computers participating in $\text{Marvel DC}$ are only required to monitor the blockchain for computation requests, and respond when they themselves are selected to participate in the computation. Furthermore, by utilising cost-effective blockchains such as Harmony, the costs for participation in $\text{Marvel DC}$ are fractions of a US dollar, as shown in Section \ref{sec:Analysis}.

\end{itemize}

Given these properties of $\text{Marvel DC}$, we then outline a series of privacy-enhancing amendments, culminating in Privacy $\text{Marvel DC}$, a protocol in which results cannot be linked to the computer which provided the result, except with significant additional cost to the player who causes the revelation. Privacy $\text{Marvel DC}$ retains all of the decentralisation and incentive compatibility guarantees of $\text{Marvel DC}$, while also adding a layer of privacy which makes it appropriate for sensitive computations where knowing a certain computer computed a particular result can be used to infer private/unwanted information about the computer. This is particularly interesting in the case of FL, where computers are asked to use private data set.

To do this, we make use of existing ZK set-membership tools (described in Section \ref{sec:ZK}). These tools are used in protocols such as Zerocoin \cite{ZerocoinGreen} and Tornado Cash\footnote{\url{https://tornado.cash/}}, with the latter of which currently deployed and in use on the Ethereum blockchain. Computers encrypt results, and publish them anonymously to the blockchain through a network of relayers: blockchain participants who are incentivized to submit transactions on behalf of other players (explained in detail in Section \ref{sec:Relayers}). The set of good and bad results are published as in $\text{Marvel DC}$, and as results are not attached to the computer that sent them, computers prove membership among the set of computers submitting good/bad results using the aforementioned ZK set-membership tools.

Although our privacy techniques are not novel outside of DC, and in fact reduce privacy compared to DC protocols like \cite{FairnessIntegrityPrivacyBlockchainBasedFLSystemRuckel}, the combination of decentralisation, proven strong incentive compatibility and the ability to apply one smart-contract instance of Privacy $\text{Marvel DC}$ to any computational problem  with output in Euclidean space (summarized in Table \ref{table:RW}) stands as an additional novel contribution.

\section{Related Work}\label{sec:RW}

\begin{table}[H]
\begin{center}
\scalebox{0.7}{
  \begin{tabular}{ |l|c|c|c|c|}
    \toprule
    Protocol & \makecell{Tokenized \\ Rewards} & \makecell{Strong Incentive \\ Compatible} &  Computation-Independent & \makecell{Diminishing Adversarial \\ Selection Prob.}  \\
    \bottomrule
    \cite{BlockchainDecentralisedFedLearningLi,FLChainBao,FLChainMajeed,FedLearningMeetsBlockchainMa,BlockFLKim,DeepChainWeng, BlockchainRepAwareFedLearningRehman} & \textcolor{red}{\ding{55}} & \textcolor{red}{\ding{55}}   & \textcolor{green}{\ding{51}} & \textcolor{green}{\ding{51}} / \textcolor{red}{\ding{55}}  \\
    \midrule
    Toyoda et al. \cite{IncentiveMechFLBlockchainToyoda}  & \textcolor{green}{\ding{51}} & \textcolor{red}{\ding{55}}   & \textcolor{green}{\ding{51}} & \textcolor{red}{\ding{55}}  \\
    \midrule
    Ruckel et al. \cite{FairnessIntegrityPrivacyBlockchainBasedFLSystemRuckel}  & \textcolor{green}{\ding{51}} & \textcolor{green}{\ding{51}}   & \textcolor{red}{\ding{55}} * & \textcolor{red}{\ding{55}} \\
    \midrule
    Marvel DC & \textcolor{green}{\ding{51}} & \textcolor{green}{\ding{51}}  & \textcolor{green}{\ding{51}}  & \textcolor{green}{\ding{51}} \\
    \bottomrule
  \end{tabular}}
  \caption{Comparison of incentive-aware FL protocol designs. *Computation-independence refers to the ability of a particular smart-contract encoding to be re-used for many computations. The ZK circuit-encodings of \cite{FairnessIntegrityPrivacyBlockchainBasedFLSystemRuckel} must be generated anew for each type of computation, placing significant upfront costs on computation requesters. } \label{table:RW}
\end{center}
\end{table}

There are many intertwined areas of research regarding the decentralized outsourcing of computations to distributed sets of potentially untrusted peers. Strong advancements have been made with respect to single computer outsourcing, with \cite{BlockchainBasedDistributedComputingPaymentsZhang,OBFPLin,OptiSwapEckey} providing variations of such pairwise protocols.

These 2-player protocols involve several rounds of communication between the requester and computer. However, none discuss the problem of computer selection or rewarding in the presence of many competing computers. This limits their scope for outsourcing computations where the participation of many computers is required, such as in FL.

Blockchain-based DC protocols  \cite{BlockchainDecentralisedFedLearningLi,FLChainBao,FLChainMajeed,FedLearningMeetsBlockchainMa,BlockFLKim,DeepChainWeng, BlockchainRepAwareFedLearningRehman} have been well-studied also. Unfortunately, all of these papers consider a blockchain or distributed system in which all parties share one utility, that is, the ability to use/benefit from a well-trained shared  model, which gives correct behaviour by definition. Such an assumption makes these protocols and their resulting analyses inappropriate in the presence of untrusted peers and/or asymmetric utilities.

In \cite{IncentiveMechFLBlockchainToyoda}, a protocol and general framework for incentive mechanism design, within FL protocols where players measure utility tokenomically, are proposed. Computer registration and reward distribution must all be performed by players within the system. Computer registration is performed by an ``administrator", which prevents decentralization and encourages collusion. Furthermore, computation rewards are distributed based on votes of players within the system. The incentive compatibility of this choice is not considered, and is non-trivial to implement. In $\text{Marvel DC}$, rewards are distributed deterministically as part of the smart-contract execution on requester inputs. We prove that rational requesters always submit messages correctly to the blockchain, and thus, correct rewarding is strong incentive compatible. Moreover, \cite{IncentiveMechFLBlockchainToyoda} has no mechanism to identify Byzantine computers and diminish/remove their ability to participate in the protocol. In $\text{Marvel DC}$, this is achieved using reputations.

Recently, an extensive survey of existing attempts to construct privacy-preserving FL protocols\cite{privacyPreservingFLSurveyLiu} was published. Of the investigated works, the most promising for achieving an incentive-compatible decentralized protocol is \cite{FairnessIntegrityPrivacyBlockchainBasedFLSystemRuckel}.  In \cite{FairnessIntegrityPrivacyBlockchainBasedFLSystemRuckel}, ZK-proofs are used in the computing stage to prove that a computation was performed correctly. In a decentralized setting however, this raises many challenges, as each type of computation requires its own ZK circuit-generation/trusted set-up to generate the target function. In contrast, $\text{Marvel DC}$ can be implemented using existing, blockchain-deployed ZK-tools and generalised rewarding functions. Moreover, as acknowledged by the authors of \cite{FairnessIntegrityPrivacyBlockchainBasedFLSystemRuckel}, although their methodology ensures models were trained correctly, it does not guarantee the models were trained on appropriate data. A proposed solution is using ``certified sensors", equivalent to TTPs, a non-viable solution in a decentralized setting. As the rewarding functions in $\text{Marvel DC}$ reward players based on the relative quality of the results, and not just based on the fact that a series of computations has been performed correctly, independent of the data on which the computations are being performed, we are able to avoid this issue.

\section{Preliminaries}

\subsection{Blockchains}

In this paper, we are interested in a distributed set of $n$ players $\{\textit{P}_1,...,\textit{P}_\numPlayers\}$ interacting with one and other inside a blockchain protocol. These players send and receive stake among one another, along with the functionality to encode programs to run within the blockchain protocol in the form of \textit{smart contracts}. A foundational assumption for the functioning of blockchain protocols is that a majority of players in the protocol act \textit{rationally}, following the protocol if they are incentivized to do so. The non-rational players are known as \textit{Byzantine}, and are modelled as deviating from the protocol either maliciously or randomly, and being controlled by a single adversary. This player model is known as the ByRa model \cite{SMRwithoutHonestPlayers}, which we use in this paper. The ByRa model is a necessary improvement on the legacy BAR model \cite{BARGossip} for the true consideration of incentives in distributed systems, removing any dependencies on altruistic, honest-by-default players which cannot be assumed to exist in incentive-driven protocols like blockchain/DC protocols.

\begin{spacing}{1.5}
\begin{definition}\label{def:PlayerModel}
    The \textit{$\text{ByRa}$ model} consists of \textit{Byzantine} and \textit{Rational} players. A player is:
    \begin{itemize}
        \item \textit{Byzantine} if they deviate arbitrarily from a recommended protocol with unknown utility function. Byzantine players are chosen and controlled by an adversary $\mathcal{A}$.
        \item \textit{Rational} if they choose the strategy which maximizes their utility assuming all other players are rational.
    \end{itemize}

\end{definition}
\end{spacing}

It is the aim of this paper to construct a DC protocol that ensures rational players always follow the protocol, a property known as strong incentive compatibility in expectation. In this paper, rational players utility is measured in blockchain-based tokens.
Based on similar assumptions to \cite{Hawk}, the blockchain protocol acts conceptually as a public ledger managed by a TTP. In reality, it is the following of the blockchain protocol by some majority of players using the blockchain that replicates this TTP. The protocol provides availability and correctness of the programs being run through the protocol, but does not provide privacy. That is, any player can observe the current state of all programs being run on the blockchain, and can verify that this state has been reached through the correct running of these programs. However, player inputs to these programs must be committed publicly to the blockchain before they can be passed to the smart contract, and as such, it will be an important requirement of designing a protocol involving smart contract interaction, through transactions, that the blockchain will accept these transactions in a timely fashion. In our system, this is achieved using incentivization.

\ignore{
Smart contracts, like players, have an associated balance of stake. The sending of stake by a smart contract can only be done by satisfying specified logical conditions encoded in the smart contract. Examples of these conditions are the generation of small hash value by a player(Proof-of-work), the calling of the contract by members of a certain set of addresses, such as the contract writer, or the passing of a specified time/number of blocks (Time-lock). We consider smart contracts taking as input specifically-labelled transactions from players, containing payments and arbitrary textual data, and also the current height of the blockchain. The contract then produces some output, distributing, either to other contracts, players, or to burn, some amount of stake up to a maximum of the stake input to the contract. Only stake that is sent to a contract can be distributed by the contract.
}

\subsection{Zero-Knowledge Primitives}\label{sec:ZK}

The aim of this section is to outline existing \textit{non-interactive zero-knowledge} (NIZK) tools for set membership, such as those stemming from papers like \cite{ZerocoinGreen,ZCash,PairingBasedNIZKsGroth,ZKProofsSetMembershipBenarroch,SemaphoreWhitehat}, which are used in our privacy-enhanced DC protocol. We define these tools generically, allowing for the adoption of any secure NIZK set-membership protocol into $\text{Marvel DC}$, as we only require a common functionality that is shared by all of them.

In the rest of the paper, we let $*$ denote any value. Computers privately generate two bit strings, the \textit{serial number} $\textit{S}$ and \textit{randomness} $\textit{r}$, with $\textit{S}, \ \textit{r} \in \{0,1\}^{O(\kappa)}$ for some security parameter $\kappa$. Computers then commit to these values by generating a commitment $\textit{com} \leftarrow f_\textit{com}(\textit{S},\textit{r})$ where $f_\textit{com}(*)$ is some cryptographically-secure commitment function (such as a Pedersen Commitment \cite{PedersenCommitments}). This $\textit{com}$ is then published to the blockchain, with the set of all commitments denoted by $\textit{Com}$. With this in mind, we now define the key functions that allow us to reason about the NIZK proving of the membership of some commitment $\textit{com}$ in $\textit{Com}$:

\begin{itemize}
    \item Verify$(\pi)$: For a ZK proof $\pi$, returns 1 if and only if $\pi$ is a valid proof of knowledge.
    \item MemVerify$(\textit{Com},\textit{com}):$ Returns 1 if and only if $\textit{com} \in \textit{Com}$.
    \item NIZKPoK$\{(\textit{com}, \textit{r}):$ MemVerify($\textit{Com}, \textit{com} )=1 \, \And \textit{com}= f_\textit{com}(\textit{S},\textit{r}) $ $\} \rightarrow \pi $: Returns a NIZK proof of knowledge of a commitment $\textit{com}$ and randomness $\textit{r}$ which satisfies  MemVerify$(\textit{Com},\textit{com})$=1 and $\textit{com}= f_\textit{com}(\textit{S},\textit{r})$. The variables $(\textit{com}, \textit{r})$ are assumed to be known only by the prover, while all other variables and functions are know by the verifier. Specifically, this function depends on the serial number $\textit{S}$ being revealed. This revelation identifies to a verifier when a proof has previously been provided for a particular, albeit unknown, commitment as the prover must reproduce $\textit{S}$. This is used in conjunction with an escrow to enforce the correct participation of computers in our privacy-enhanced DC protocol.
    \item NIZKSoK($m$)$\{(\textit{com}, \textit{r}):$ MemVerify$(\textit{Com},\textit{com})=1 \, \And \textit{com}= f_\textit{com}(\textit{S},\textit{r}) $ $\} \rightarrow \pi$: for an arbitrary message $m$, this function returns an NIZK proof which proves that the person who chose $m$ can also produce NIZKPoK$\{ $ $(\textit{com}, $ $ \textit{r}):$ MemVerify$(\textit{Com},\textit{com})=1 \, \And \textit{com}= f_\textit{com}(\textit{S},\textit{r}) $ $\}$. As such, NIZKSoK($m$) acts as a \textit{signature of knowledge} on $m$, as coined in \cite{ZerocoinGreen}.
\end{itemize}

In this paper, we assume the public NIZK parameters are set-up in a trusted manner\footnote{Such as a Perpetual Powers of Tau ceremony, as used in Zcash \url{https://zkproof.org/2021/06/30/setup-ceremonies/}}.

\subsection{Relayers}\label{sec:Relayers}

A fundamental requirement for transaction submission in blockchains is the payment of some transaction fee to simultaneously incentivize block producers to include the transaction, and to prevent denial-of-service/spamming attacks. However, this allows for the linking of player transactions, balances, and their associated transaction patterns.
To counteract this, we utilize the concept of \textit{transaction relayers}\footnote{Ox \url{https://0x.org/docs/guides/v3-specification}, Open Gas Station Network \url{https://docs.opengsn.org/}, Rockside \url{https://rockside.io/}, Biconomy \url{https://www.biconomy.io/}}.

When a computer wishes to submit a transaction anonymously to the block- chain, the computer publishes a proof of membership to the relayer mempool, as well as the desired transaction and a signature-of-knowledge cryptographically binding the membership proof to the transaction, preventing tampering. As the relayer can verify the proof of membership, the relayer can also be sure that if the transaction is sent to certain smart-contracts (such as those used in our DC protocols), the relayer will receive a fee.  As such, a model in which players submit transactions to relayers, who then in turn submit those transactions to the blockchain for a guaranteed fee is a straightforward extension of a model in which players submit transactions directly to the blockchain themselves. Furthermore, if the transaction contains a proof of membership that is NIZK and the message is broadcast anonymously (using the onion routing (Tor) protocol\footnote{\url{https://www.torproject.org/}} for example), the relayer can only infer that the player sending the transaction is a member of a particular set.

\section{Constructing a Strong Incentive Compatible DC Protocol}\label{sec:SINCE}

For the sake of comprehensibility, we first describe an idealized protocol for the distribution of computation between a set of computers. We then demonstrate how to instantiate such a protocol using existing blockchain technology. In this description, we consider a requester who has a computation $\textit{calc}$ whose calculation the requester wishes to outsource to some subset of available computers $\textit{C}$. Furthermore, the requester is aware of a threshold ${n_{\psi}}$ such that for any random sample of ${n_{\psi}}$ computers without replacement from $\textit{C}$, a majority of those computers are rational.

We consider the output of all computations in this paper as a point in $l$-dimensional space. To reason about the goodness of a computation result, for every computation we assume the existence of a deterministic function which takes the set of computation responses, and given a majority of correctly computed results, outputs a target value $\tau$, which is computed correctly with probability $1- \epsilon$, for some $\epsilon<0.5$. For deterministic calculations, the mode is such a function. In FL where results are model gradients, the Krum function \cite{KrumMLwithAdversariesBlanchard} is such an aggregation function. We let $\textit{dist}(x,y)$ be the Euclidean distance function. For $x,y \in \mathbb{R}^l$, $\textit{dist}(x,y)=\sqrt{(x_1-y_1)^2 +...+(x_l-y_l)^2}$.

Consider the set of computation results $\{\textit{result}_1,...,\textit{result}_{n_{comp}} \}$. We require for any pair ($\textit{result}_{+}$, $\textit{result}_{-}$), with $\textit{result}_{+}$ a correctly computed result and $\textit{result}_{-}$ an incorrectly computed result the following holds for any $\sigma>0$:

\vspace{-0.5cm}

\begin{equation}\label{eq:BaseCase}
    P( \textit{dist}(\textit{result}_{+}, \tau) < \sigma) > P( \textit{dist}(\textit{result}_{-}, \tau) < \sigma).
\end{equation}
Given this, for any subset of computation results taken in ascending order using the function $\textit{dist}$, the expected number of these computations being correctly computed is greater than those being incorrectly computed. With respect to deterministic computations, letting $\tau$ be the median or mode, all correctly computed results will be distance 0 to $\tau$. For non-deterministic computations, it is less clear. The function used to compute $\tau$ must be chosen such that Equation \ref{eq:BaseCase} holds.

Now, consider the following DC protocol run by a trusted third party (TTP) who enforces the correct participation of all rational players. The proceeding sections then replace this TTP, in order to achieve full decentralization, through the use of a smart contract-enabled blockchain and a strong incentive compatible protocol ($\text{Marvel DC}$, described in Section \ref{sec:MarvelAlgos}) to be run therein.

\textbf{Idealized distributed computing protocol}. Requesters repeatedly enter the system with independent functions for computation. A requester wishing to avail of the distributed computation of some function $\textit{calc}$ submits $\textit{calc}$ to the TTP, as well as some number of computers ${n_{comp}}>{n_{\psi}}$. The TTP then selects ${n_{comp}}$ from the set of available computers $\textit{C}$. The computers respond to the TTP with their computation of $\textit{calc}$, who then sends all of the computation results to the requester.

\vspace{0.25cm}
In a distributed setting, such TTPs do not exist. Therefore, to enforce the correct participation of rational players we need to utilize a mixture of cryptography and incentivisation. With this in mind, we first describe how to generically construct a reward mechanism such that rational players are strongly incentivized to follow the protocol. We then outline a reputation management protocol which maintains this incentivisation, while reducing the probability that incorrectly performing computers are selected for computation.

\subsection{Reward Mechanism}

In this section, we provide a theoretical lower-bound on the per-computer reward required to strongly incentivize the correct participation of rational computers in our DC protocol. We describe this reward generically in terms of a cost to compute a particular computation,  fees required to post a transaction to the blockchain, and the probability of being rewarded for good and bad computations. We also describe an escrow amount to be deposited by the requester when submitting the computation, which is received back after correctly computing the set of computers to reward. Running computations such as sorting arrays or encryption/decryption on-chain is expensive, so we initially give the requester the opportunity to correctly submit the set of computers to reward. Computers have an opportunity to contest this by depositing a bounty on-chain, triggering the on-chain verification of the reward set. Note that verification is much cheaper than computation, but with respect to Privacy $\text{Marvel DC}$, this reveals some private information, which is why verification does not take place automatically. If the contest is valid, the requester loses the escrow. Otherwise, the computer loses the bounty. This is described in more detail in Section \ref{sec:MarvelAlgos}.

For a given computation $\textit{calc}$, we assume an accurate a-priori lower-bound on the cost to compute a particular computation $\textit{calc}$ of $\textit{cost}(\computation)$. This lower-bound is known by all players in the system (in reality this value can be enforced by the protocol smart-contract). Given that the payment of $\textit{Fee}(\textit{tx})$ per transaction guarantees timely inclusion in the blockchain, rational computers perform the calculation of $\textit{calc}$ if and only if:
\begin{equation} \label{eq:rewardsGreaterThanCosts}
    E(\textit{Reward}(\computation)) > \textit{cost}(\computation) + 2\textit{Fee}(\textit{tx}).
\end{equation}

To more accurately describe $\textit{Reward}(\computation)$, we introduce $0 \leq \omega,\gamma \leq 1$ with the probability of good computations being rewarded being $\omega$, and the probability of bad computations being rewarded being $\gamma$, such that WLOG $\omega>\gamma$. This gives an expected payoff of $\omega \textit{Reward}(\computation) - (\textit{cost}(\computation) +  2\textit{Fee}(\textit{tx}))>0$ for following the protocol, and an expected payoff of $\gamma \textit{Reward}(\computation) -  2\textit{Fee}(\textit{tx})$ for submitting a result but not performing the computation. Therefore, we require:
\begin{equation}
    \omega \textit{Reward}(\computation) - \textit{cost}(\computation)  -\gamma \textit{Reward}(\computation)  >0
\end{equation}

This reduces to
$\textit{Reward}(\computation)  > \frac{\textit{cost}(\computation)}{\omega -\gamma}.$
The exact values of $\omega$ and $\gamma$ depend on the computation, number of computers to be rewarded and the chosen target function. Exact values for  $\omega$ and $\gamma$ are difficult to predict a-priori. For deterministic computations $\omega \approx 1$, whereas for non-deterministic computations such as FL, $\omega$ will be smaller. Lower-bounding the possible value of $\omega -\gamma$ (although greater than 0) and using this value to compute $\textit{Reward}(\computation)$ ensures rational players follow the protocol.

Additionally, in a smart-contract blockchain, actions must be triggered by one or more players by sending transactions to the blockchain. In $\text{Marvel DC}$, the distribution of rewards is initially controlled by the requester (if the requester fails to trigger correct reward distribution, computers can eventually initiate the rewarding mechanism). To ensure a rational requester correctly submits the set of good computations to be rewarded, any positive escrow amount $\textit{escrow}_\textit{req}>\textit{Fee}(\textit{tx})$ suffices to strongly incentivize the requester. This can be seen as the payoff for submitting the correct set is $\textit{escrow}_\textit{req}-\textit{Fee}(\textit{tx})>0$, while the payoff for not submitting the set is 0. However, in the case of potential collusion of up to $k$ computers, setting $\textit{escrow}_\textit{req} \geq k\cdot \textit{Reward}(\computation)+\textit{Fee}(\textit{tx})$ guarantees that the requester correctly submits the set of good computations. If $k$ is set too small by the protocol/smart contract, not submitting the reward set, and rewarding all players may be positive expectancy for the requester. Setting $k$ equal to ${n_{comp}}$ conservatively achieves this.
With this lower bound on $\textit{escrow}_\textit{req}$, rational requesters always submit the correct set of good computations to the blockchain.

\subsection{Reputation Management Protocol}\label{sec:Reputation}

In the previous section, we identified that all rational players in the system follow the protocol given no changes to reputation. However, the use of a reputation-based selection process prioritizes good computers over bad computers, meaning both short- and long-term benefits for correctly behaving computers. Therefore, using reputation-based computer selection is desirable.
In this section we describe a reputation management protocol that maintains the incentive compatibility of a DC protocol with an incentive compatible reward mechanism.

We consider computations for which a rating mechanism rates results as either ``good" or ``bad" exists. Correctly performed computations are rated good with probability $\omega$, while incorrectly computations are rated good with probability $\gamma$. We construct a function from this rating mechanism, $\textit{rate}()$, which assigns good calculations a score of 1, and bad calculations a score of 0. For a player $\player_i$ taking part in computations for $\textit{calc}_{1}, \textit{calc}_2,..., \textit{calc}_k $, $\player_i$'s \textit{base reputation} is $\textit{baseRep}_i=\sum_{j=1}^k \textit{rate}(\textit{calc}_j)$.

Let $\textit{initRep}>0$ be the starting reputation for computers registering in the system. For a given computation, $\player_i$ is selected as computer for a computation in block at height $H$ in the blockchain in direct proportion to $\textit{baseRep}^{H-1}_i (\textit{initRep} -1)$ as a fraction of $\sum^{n}_{j=1} \textit{baseRep}^{H-1}_j - n \cdot (\textit{initRep} -1)$. We subtract ($\textit{initRep}$-1) from $\textit{baseRep}^{H-1}_i$ to normalize the base reputations for selection probability purposes, and so there is no benefit for computers rejoining, particularly in the case where base reputations are increasing over time. With this in mind, the number of computations a player $\player_i$ is selected for is directly proportional to:

\begin{equation}\label{eq:SelectionProb}
    \textit{probSelect}^H_i=\frac{\textit{baseRep}^{H-1}_i- (\textit{initRep} -1)}
    {\sum^{n}_{j=1} \textit{baseRep}^{H-1}_j - n\cdot (\textit{initRep} -1)}.
\end{equation}

Consider a player $\textit{P}_i$ who includes a good computation as block proposer for a computer. This increases that computers base reputation, and thus that computers $\textit{probSelect}$. This has long-term stake implications, as discussed at the beginning of Section \ref{sec:Reputation}. Although the computation result is encrypted, the expected change in $\textit{probSelect}$ for an included computer is positive, which negatively affects the $\textit{probSelect}$ of the block proposer. Therefore, we need to reward the proposer with an increase in base reputation to counteract the increase in the computers expected increase in base reputation. Let $E_\textit{repChange}>0$ be the expected change in base reputation for a computer whose computation gets included on the blockchain.

For $\player_i$ a proposer of a block that includes $k$ transactions containing computation results, we need the following equality to hold:
\vspace{-0.5cm}
\ignore{
\begin{equation}
\begin{split}
         \textit{probSelect}^H_i &= \frac{\textit{baseRep}^H_i-(\textit{initRep} -1)}{\textit{baseRep}^H_i+ \sum_{j \neq i} \textit{baseRep}^{H-1}_j + k\cdotE_\textit{repChange} - n\cdot (\textit{initRep} -1)}  \\
        &= \frac{\textit{baseRep}^{H-1}_i-(\textit{initRep} -1)}{\textit{baseRep}^{H-1}_i+\sum_{j \neq i} \textit{baseRep}^{H-1}_j - n \cdot (\textit{initRep} -1)} .
\end{split}
\end{equation}

Solving for $\textit{baseRep}^H_i$ in this equality gives:}

\begin{multline} \label{eq:reputationChange}
    \textit{baseRep}^H_i= \textit{baseRep}^{H-1}_i + \\  k\cdotE_\textit{repChange} \big(  \frac{\textit{baseRep}^{H-1}_i-(\textit{initRep} -1)}{\sum_{j \neq i} \textit{baseRep}^{H-1}_j - (n-1) \cdot (\textit{initRep} -1)} \big).
\end{multline}

This means we need to add $k\cdotE_\textit{repChange} \big(  \frac{\textit{baseRep}^{H-1}_i-(\textit{initRep} -1)}{\sum_{j \neq 1} \textit{baseRep}^{H-1}_j - (n-1) \cdot (\textit{initRep} -1)} \big)$ to $\textit{baseRep}^{H-1}_i$ in order to ensure the proposer is impartial, with respect to reputation and computer selection probability, to adding  transactions containing computation results to the blockchain.

For transactions from the requester finalising the rewards, we simply have to replace $E_\textit{repChange}$ with the actual mean change in reputation in Equation $\ref{eq:reputationChange}$, and the rest of the numbers stay the same.

\section{\texorpdfstring{$\text{Marvel DC}$}{TEXT}}\label{sec:MarvelAlgos}

The goal of this section is to take the ideal DC functionality of Section \ref{sec:SINCE}, and implement it as a set of algorithms encoded as smart-contracts that can be run by a decentralized (without a TTP) set of players with access to a blockchain. We call this protocol $\text{Marvel DC}$. In Section \ref{sec:SINCE}, we identified values for computer rewards, reputations changes and computer/requester escrows which ensure the participation of rational players if they can be enforced. In this section, we describe how all of these values can be enforced using a blockchain, and as such, that it is possible to implement the idealized DC protocol in a fully decentralized manner.

\subsection{Algorithmic Overview}\label{sec:AlgoOverview}

We outline the $\text{Marvel DC}$ protocol as a set of pseudo-code smart contracts encodings provided in Algorithms \ref{alg:SMRProgram} and \ref{alg:ComputerSelectionProtocol}. These contracts are labelled: \textit{Register}, \textit{Request}, \textit{Response} and \textit{Finalize}. A Solidity implementation of $\text{Marvel DC}$ has also been made publicly available on Github \cite{MarvelDCGithub}.

A $\text{Marvel DC}$ instance can spawn an indefinite number of computation instances, each initialized by calling the Request contract, and lasting at least $T$ blocks, where $T$ is the number of blocks required for players to observe an event on-chain, send a transaction and have that transaction committed on-chain given at least $\textit{Fee}(\textit{tx})$ is paid. We provide here the intuition to these encodings, including a graphic representation of the protocol flow in Figure \ref{fig:protocolFlow}. A privacy-enhancing implementation of $\text{Marvel DC}$ is then described in Section \ref{sec:PrivacyMarvel}.

\begin{figure}
	\includegraphics[width=1\textwidth]{MarvelFlow.JPG}
	\caption{$\text{Marvel DC}$ information and token flow. ${\bitcoin:}$ indicates the transfer of tokens.}
	\label{fig:protocolFlow}
\end{figure}

Each player $\player_i$ owns (has exclusive access to) a set of token balances $\textit{bal}_i$ which are stored as a globally accessible variable on the blockchain.
For a token $\bitcoin$, $\textit{bal}_i(\bitcoin)$ is the amount of token $\bitcoin$ that $\player_i$ owns.
Players in the underlying blockchain protocol can enter $\text{Marvel DC}$ as computers by calling the Register contract, which for a given computer deposits an escrow $\textit{escrow}_\textit{comp}$ (line \ref{line:depositEscrowComp}), granting that computer a reputation of $\textit{initRep}$ (line \ref{line:initialRep}).

Computation request instances are initialized by calling the Request contract, which specifies the computation details $\textit{calc}$, the number of computers to be selected for the computation ${n_{comp}}$, a deterministic function $\textit{f}_\target$ for selecting the target result $\tau$ from the set of results, the number of computers to reward ${n_{reward}}$, and the per-computer reward $\textit{Reward}_i$ received by a computer if included in the set of computers to reward. The requester deposits ${n_{reward}}\cdot\textit{Reward}_i +\textit{escrow}_\textit{req}$. The $\textit{compEncKey}$ is the public key corresponding to the temporary public/private key pair ($\textit{compEncKey}, \textit{compDecKey}$). This is a key pair generated by the requester specifically for $\textit{calc}$. A randomness beacon is called (line \ref{line:getComputers}), which provides a pseudo-random seed for selecting ${n_{comp}}$ computers to participate in the computation in direct proportion to computer reputations (line \ref{line:func:SelectComps}), with these computers listed in the set $\textit{calc}.I$.

Computers selected for a particular computation $\textit{calc}$, identified in $\textit{calc}.I$, can then submit results for $\textit{calc}$ to the blockchain by calling the Response contract for up to $T$ blocks after the computation is requested. These results should be encrypted using $\textit{calc}.\textit{compEncKey}$ (line \ref{line:SubmitResponse}). These encrypted results are decrypted in the Finalize phase (line \ref{line:decrypt}) for rewarding purposes. This encryption ensures no other computer can use another computer's result, and therefore must themselves perform the computation. Given a valid response is recorded, the block producer corresponding to the response is added to $\textit{calc}.\textit{proposers}$ (line \ref{line:addTXProposer}). This is used later to update reputations, in line with the analysis of Section \ref{sec:Reputation}.

Then, either after $T$ blocks from when the computation $\textit{calc}$ was requested, or when all computers in $\textit{calc}.I$ have responded, the requester of $\textit{calc}$ can complete the request by calling the Finalize contract. Calling the Finalize contract requires the requester to provide the decryption key $\textit{calc}.\textit{compDecKey}$ corresponding to $\textit{calc}.\textit{compEncKey}$. If these keys match up, the requester receives back her escrow $\textit{escrow}_\textit{req}$. The contract then uses $\textit{compDecKey}$ to decrypt the computer responses, and identify which computers are to be rewarded (line \ref{line:func:rateComputations}). This is done by applying the pre-specified target function to the computation results, and computing a target value $\tau$ (line \ref{line:setTargetResult}). The computers corresponding to the $\textit{calc}.{n_{reward}}$ results closest to $\tau$ using Euclidean distance are selected as the computers to reward, $I_{good}$ (line \ref{line:getBestResults}). The computers in $\textit{calc}.I_{good}$ each receive $\textit{calc}.\textit{Reward}_i$. Finally, all registered computers in $\textit{calc}.\textit{proposers}$ receive reputation increases of $\avgRepChange$ (line \ref{line:func:updateReps}), while computers in $\textit{calc}.I_{good}$ each receive an increase in reputation of 1 (line \ref{line:goodCompRepChange}).

\begin{algorithm}
\def\baselinestretch{1} \scriptsize \raggedright
\caption{\texorpdfstring{$\text{Marvel DC}$}{TEXT} smart contract pseudocode}
\label{alg:SMRProgram}
	\begin{algorithmic}[1]

	    \State $\textit{C} \leftarrow [] $ \Comment{Set of active computers}
	    \State $\textit{initRep} \leftarrow \textit{getInitialRep}()$
	    \State $\textit{Reps} \leftarrow [\textit{initRep} \ \textbf{for} \ i \in \textit{C}]$

	    \State $T \leftarrow \textit{getFinalizeDeadline}()$ \Comment{Globally-defined finalize deadline} \label{line:finalizeDeadline}
	    \State $\textit{escrow}_\textit{comp}, \textit{escrow}_\textit{req} \leftarrow \textit{getEscrows}()$ \Comment{Globally-defined escrow amounts, in line with Section \ref{sec:SINCE}}
	    \State ${n_{\psi}} \leftarrow \textit{getMinNumComputersPerComputation}()$ \Comment{Set ${n_{\psi}}$ in-line with requirements from Section \ref{sec:SINCE}}
	    \State $\textit{tFunctions} \leftarrow \textit{getTargetFunctions}()$ \Comment{Define allowable target functions. In reality, this can be updated during the protocol}

	    \vspace{3mm}

	    \State \textbf{Register}

	    \Upon{$\langle \textit{REGISTER} \rangle \ \From  \ \textit{P} \ \With \ \textit{P} \notin \textit{C} \  \textbf{and} \ \textit{P}\textit{.balance} > \textit{escrow}_\textit{comp} $}{}\label{func:Register}\Comment{add computer to the system}
	        \State $\textit{P}\textit{.transfer}(\textit{escrow}_\textit{comp} , \textit{contract})$ \Comment{Registration cost to prevent Sybil attacks} \label{line:depositEscrowComp}
		    \State $\textit{C}\textit{.append}(\textit{P})$
		    \State $\textit{Reps}\textit{.append}(\textit{initRep})$  \label{line:initialRep}
		\EndUpon

	    \vspace{3mm}

	    \State \textbf{Request}

		\Upon{$\langle \textit{REQUEST} , \textit{calc}, {n_{comp}}, {n_{reward}}, \textit{compEncKey}, \textit{Reward}_i, \textit{f}_\target \rangle \ \From  \ \textit{requester} \ \With \ {n_{comp}}> {n_{\psi}} \ \textbf{and} \  \textit{requester}\textit{.balance} >  (({n_{reward}},\cdot \textit{Reward}_i) + \textit{escrow}_\textit{req} ) $ $\textbf{and}$ $ \textit{f}_\target \in \textit{tFunctions} $}{}\label{func:Request}
		    \State $\textit{requester}\textit{.transfer}(({n_{reward}}, \cdot \textit{Reward}_i) + \textit{escrow}_\textit{req}, \textit{contract})$ \Comment{Transfer total reward plus requester escrow to contract}
		    \State $I \leftarrow \textit{selectComputers}(\textit{genRandom}(), {n_{comp}})$ \Comment{Select computers for computation} \label{line:getComputers}

		    \State $\textit{responses} \leftarrow []$
		    \State $\textit{proposers} \leftarrow []$ \Comment{Array of the players who recorded each $\langle \textit{RESPONSE}, * \rangle $ transaction}
		    \State $\textit{start} \leftarrow \textit{Blockchain}.\textit{height}$  \Comment{Record current height of blockchain}
		    \State $\textit{step}  \leftarrow \textit{computing}$
		\EndUpon

		\vspace{3mm}

		\State \textbf{Response}

		\Upon{$\textit{tx} \leftarrow \langle \textit{RESPONSE}, \textit{calc}, \textit{result} \rangle \ \From \ \textit{c} \in I $ $\ \With \  \textit{calc}.\textit{step} = \ \textit{computing} \ \textbf{and} \ \textit{Blockchain}.\textit{height} $ $ \ < \textit{calc}.\textit{start} + T  \  $  } \label{func:RESPONSE}
			\State $\textit{calc}.\textit{responses}\textit{.append}(\textit{result}) $ \Comment{$\textit{result}$ should be the computer $\textit{c}$'s result of computing $\textit{calc}$, encrypted using $\textit{calc}.\textit{compEncKey}$}
			\If{$\textit{tx}.blockProposer \in \textit{C}$}
			    \State $\textit{calc}.\textit{proposers}\textit{.append}(\textit{tx}.blockProposer)$ \label{line:addTXProposer}
			\EndIf
		\EndUpon

		\vspace{3mm}

		\State \textbf{Finalize}

		\Upon{$\textit{tx} \leftarrow \langle \textit{FINALIZE}, \textit{calc}, \textit{compDecKey} \rangle \ \From \ \textit{calc}.\textit{requester} $ $\ \With \ \textit{valid}(\textit{compDecKey}, \textit{calc}.\textit{compEncKey}) $ $ \ \textbf{and} \  \big( ( \textit{calc}.\textit{step} = \ \textit{computing} \ \textbf{and} \ \textit{Blockchain}.\textit{height} $ $ \ < \textit{calc}.\textit{start} + T  \ $ $\textbf{and} \ \textit{len}(\textit{calc}.\textit{responses})=\textit{calc}.{n_{comp}} ) $ $ \ \textbf{or} \ (\textit{calc}.\textit{step} = \ \textit{computing} \ $ $\textbf{and} \ \textit{Blockchain}.\textit{height}  \ \geq  \textit{calc}.\textit{start} + T) \big) $  } \label{func:FINALIZEsuccess}
		    \State $\textit{calc}\textit{.transfer}(\textit{escrow}, \textit{calc}.\textit{requester})$ \Comment{Returns the escrow to the requester} \label{line:requesterRefund}
		    \State $\textit{calc}.\textit{proposers}\textit{.append}(\textit{calc}.\textit{requester})$ \Comment{Required for SINCE of requester}
		    \If{$\textit{tx}.blockProposer \in \textit{C}$} \Comment{Required for SINCE of proposers}
			    \State $\textit{calc}.\textit{proposers}\textit{.append}(\textit{tx}.blockProposer)$
			\EndIf
			\State $\textit{calc}.\textit{step}  \leftarrow \textit{finalized}$

			\State $I_{good}, I_{bad} \leftarrow \textit{rateComputations}(\textit{calc}, \textit{calc}.{n_{reward}}, \textit{compDecKey}, \textit{calc}.\textit{f}_\target)$ \Comment{Function which deterministically evaluates the goodness of returned computations, returning the indices of good and bad computers}
			\State $\textit{calc}\textit{.transfer}(\textit{calc}.\textit{Reward}_i, I_{good})$ \label{line:payGoodComps}
			\State $\textit{updateReputations}(I_{good}, I_{bad}, \textit{calc}) $  \label{line:updateReps}

		\EndUpon

		\vspace{3mm}

	\end{algorithmic}

\end{algorithm}

\begin{algorithm}
\def\baselinestretch{1} \scriptsize \raggedright
\caption{Computer Selection Protocol}
\label{alg:ComputerSelectionProtocol}
	\begin{algorithmic}[1]

        \Function{$\textit{genProbSelect}()$}{} \label{line:func:generateSelctionProbabilities}
		\State $\textit{minRep} \leftarrow \textit{min}(\textit{Reps})$
		\State $\textit{denominator} \leftarrow \sum(\textit{Reps}) - \textit{len}(\textit{Reps})\cdot(\textit{minRep}-1)$
		\State \textbf{return} $[\big( (i- (\textit{minRep}-1))/ \textit{denominator} \big) \ \textit{for} \ i \in \textit{Reps}]$ \Comment{Probability formula from Section \ref{sec:Reputation}}
		\EndFunction

		\vspace{3mm}

		\Function{$\textit{selectComputers}(\textit{randomSeed},{n_{comp}})$}{} \label{line:func:SelectComps}
		\State $\textit{ctr} \leftarrow 0$
		\State $I \leftarrow []$
		\State $\textit{probSelect} \leftarrow \textit{genProbSelect}(\textit{Reps})$
		\State $\textit{randomSeed} \leftarrow \textit{SHA}(\textit{randomSeed})$
		\While{$\textit{ctr} < {n_{comp}}$} \label{line:drawfromUrn}
		    \State $i\leftarrow 0$
		    \State $\textit{sumReps} \leftarrow \textit{probSelect}[i]$
		    \While{$\textit{randomSeed} > \textit{sumReps}$} \label{line:findComputer}
		        \State $\textit{sumReps}\leftarrow \textit{sumReps} + (\textit{probSelect}[i++]*(2^256))$
		    \EndWhile
		    \If{$\textbf{not}(i \in I)$} \label{line:uniqueCompFound}
		        \State $I\textit{.append}(i)$
		        \State $\textit{ctr} \leftarrow \textit{ctr} +1 $
		    \EndIf
		    \State $\textit{randomSeed} \leftarrow \textit{SHA}(\textit{randomSeed})$
		\EndWhile
		\EndFunction

	\end{algorithmic}

\end{algorithm}

\begin{algorithm}
\def\baselinestretch{1} \scriptsize \raggedright
\caption{Reputation Management}
\label{alg:RepMgmtProtocol}
	\begin{algorithmic}[1]

		\Function{$\textit{rateComputations}(\textit{calc}, {n_{reward}},  \textit{compDecKey}, \textit{f}_\target)$}{} \label{line:func:rateComputations}
		\State $I_{good} \leftarrow []$
		\State $\textit{results} \leftarrow decrypt(\textit{calc}.\textit{responses}, \textit{compDecKey})$ \label{line:decrypt}
		\State $\tau \leftarrow \textit{f}_\target(\textit{results})$ \label{line:setTargetResult}
		\For{$ i \ \in \ [1,..., {n_{reward}}]$} \Comment{add the ${n_{reward}}$ closest results to $\tau$ to $I_{good}$} \label{line:getBestResults}
		  \State $I_{good}\textit{.append}(\textit{result}.\textit{c}) \textbf{and} \textit{results}.\textit{remove}(\textit{result})$ $\With \textit{dist}(\textit{result},\tau) = $ $ \textit{min}(\textit{dist}(\textit{results},\tau))$

		\EndFor
		\State $I_{bad} \leftarrow \textit{results}.\textit{c}$ \Comment{all results not already removed in the for loop are bad results, not to be rewarded}
		\State \textbf{return} $I_{good}, \ I_{bad}$
		\EndFunction

		\vspace{3mm}

		\Function{$\textit{updateReputations}(I_{good}, I_{bad}, \textit{calc})$}{}
		\State $\avgRepChange \leftarrow \textit{len}(I_{good})/(\textit{len}(I_{good})+\textit{len}(I_{bad}))$
		\State $\textit{denominator} \leftarrow \sum(\textit{Reps}) - (\textit{len}(\textit{Reps})-1)\cdot(\textit{initRep}-1)$
		\For{$blockProposer \ \in \ \textit{calc}.\textit{proposers}$} \label{line:func:updateReps} \Comment{in-line with the results from Section \ref{sec:Reputation}, block proposers rep. changes should be done before updating computers}
		    \State $\textit{Reps}[blockProposer] \leftarrow $ $\textit{Reps}[blockProposer]+ $ $ (\avgRepChange \cdot \big( (\textit{Reps}[blockProposer]-$ $ (\textit{initRep}-1))/ (\textit{denominator}-\textit{Reps}[blockProposer]) \big))$ \Comment{Necessary for SINCE of proposers/requester}
		\EndFor

		\State $\textit{Reps}[\textit{calc}.\textit{requester}] \leftarrow $ $\textit{Reps}[\textit{calc}.\textit{requester}] + $ $ (\avgRepChange \cdot \big( (\textit{Reps}[blockProposer]-$ $ (\textit{initRep}-1))/ (\textit{denominator}-\textit{Reps}[blockProposer]) \big))$ \Comment{Requester of successfully resolved computation must receive increase in reputation, in line with Section \ref{sec:Reputation}}
		\State $\textit{Reps}[\textit{tx}.blockProposer] \leftarrow $ $\textit{Reps}[\textit{tx}.blockProposer] + $ $ (\avgRepChange \cdot \big( (\textit{Reps}[blockProposer]-$ $ (\textit{initRep}-1))/ (\textit{denominator}-\textit{Reps}[blockProposer]) \big))$ \Comment{Proposer including the Finalize transaction must also receive increase in reputation, in line with Section \ref{sec:Reputation}}

		\State $\textit{Reps}[I_{good}] \leftarrow \textit{Reps}[I_{good}]+1$ \label{line:goodCompRepChange}

		\EndFunction

	\end{algorithmic}

\end{algorithm}

\begin{algorithm}
\def\baselinestretch{1} \scriptsize \raggedright
\caption{\texorpdfstring{$\text{Marvel DC}$}{TEXT} for player $\player_i$ as a Requester}
\label{alg:RequesterProtocol}
	\begin{algorithmic}[1]

	    \Function{$initialize(\textit{calc})$}{}\label{func:Initialise}
	        \State $\textit{compEncKey}, \textit{compDecKey} \leftarrow \textit{generateKeyPair}()$
	        \State $\textit{Reward}_i \leftarrow $ SINCE reward to guarantee participation of computers
	        \State ${n_{comp}} \leftarrow x \ \With x >  {n_{\psi}}$
	        \State $\textit{f}_\target \textit{getTargetFunction}(\textit{calc})$ \Comment{Select target function for computation}
	        \State \Broadcast $\langle \textit{REQUEST} , \textit{calc}, {n_{comp}}, {n_{reward}}, \textit{compEncKey}, \textit{Reward}_i, \textit{f}_\target \rangle$
		\EndFunction

		\vspace{3mm}
		\Upon {$ \textit{len}(\textit{calc}.\textit{responses})=\textit{calc}.{n_{comp}} \ \textbf{or} \ ( \textit{Blockchain}.\textit{height}  = \textit{calc}.\textit{start} + \textit{FD} ) $  } \label{func:RequesterFINALIZE}
			\State \Broadcast $\langle \textit{FINALIZE}, \textit{calc}, \textit{calc}.\textit{compDecKey} \rangle$
		\EndUpon

	\end{algorithmic}

\end{algorithm}

\begin{algorithm}
\def\baselinestretch{1} \scriptsize \raggedright
\caption{\texorpdfstring{$\text{Marvel DC}$}{TEXT} for player $\player_i$ as a computer}
\label{alg:ComputerProtocol}
	\begin{algorithmic}[1]

	    \State \Broadcast $ \langle \textit{REGISTER} \rangle $

		\Upon{$\langle \textit{REQUEST} , \textit{calc}, {n_{comp}}, {n_{reward}}, \textit{compEncKey}, \textit{Reward}_i, \textit{f}_\target \rangle \ \With \ i \in \textit{calc}.I$ }{}\label{func:ComputerAction}

		    \State \Broadcast $ \langle \textit{RESPONSE}, \textit{calc}, \textit{result} \leftarrow encrypt(\textit{compute}(\textit{calc}), \textit{calc}.\textit{compEncKey}) \rangle $ \label{line:SubmitResponse}
		\EndUpon

	\end{algorithmic}

\end{algorithm}

\subsection{Protocol Properties}\label{sec:properties}

In the following results, we make the assumption that rational requesters randomly enter the system, running unique instances of the Request contract. Under this assumption, we first show that rational computers and rational requesters are strongly incentivized to participate in the protocol.

\begin{spacing}{1.5}
\begin{theorem}\label{thm:SINCE}
    There is a strict Nash Equilibrium in which, for any computation with a per player reward $\textit{Reward}_i > \frac{\textit{cost}(\computation)}{\omega -\gamma}$, rational computers and requesters follow the protocol.
\end{theorem}

\begin{proof}
    Consider a Request( $\textit{requester}, *$) instance corresponding to a computation $\textit{calc}$, and computers selected for computation $I$. Based on ${n_{comp}}> {n_{\psi}}$, the majority of computers in $I$ are rational.

    First consider a rational requester. Correctly running Finalize ($ \textit{calc}, *$) allows the requester to receive back $\textit{calc}.\textit{escrow}_\textit{req}$, and as such, rational requesters follow the protocol.

    Consider now rational computers. If the requester correctly runs Finalize ($ \textit{calc}, *$), then $\textit{calc}.\tau$ and $\textit{calc}.I_{good}$ are generated correctly. Therefore, if all rational computers follow the protocol, the assumption under which we chose $\textit{Reward}_i$ in Section \ref{sec:SINCE}, for a given rational computer $\textit{c}_i$ correctly running Repsonse($ \textit{calc}, $ $ *$), $\textit{c}_i$ is included in $\textit{calc}.I_{good}$ with probability $\omega$. If $\textit{c}_i$ incorrectly runs Response($ \textit{calc}, $ $ *$), $\textit{c}_i$ is included in $\textit{calc}.I_{good}$ with probability of at most $\gamma$. By our choice of $\textit{Reward}_i$, we have seen in Section \ref{sec:SINCE}, given $\textit{calc}.I_{good}$ is generated correctly and computers included in $\textit{calc}.I_{good}$ receive this with probability 1, this is sufficient for rational computers to compute the result correctly, equivalent to calling Response($ \textit{calc}, *$).

    Therefore, rational computers and requesters follow the protocol if $\textit{Reward}_i > \frac{\textit{cost}(\computation)}{\omega -\gamma}$
\end{proof}
\end{spacing}

This result is enough to ensure rational players follow the $\text{Marvel DC}$ protocol. However, because of the use of the same reputation and computer-selection mechanism as described in Section \ref{sec:Reputation}, $\text{Marvel DC}$ also guarantees that Byzantine computers are selected with diminishing probability in the number of computations, converging to 0 for any minority of selected computers. This is stated formally in the following lemma.

\begin{spacing}{1.5}
\begin{lemma}\label{lem:diminishingProb}
    For a series of computations $[\textit{calc}_1, \textit{calc}_2, ..., \textit{calc}_i]$ with $\textit{Reward}_i > \frac{\textit{cost}(\computation)}{\omega -\gamma}$ and ${n_{comp}} >  {n_{\psi}}$, as the number of completed computations increases, the probability of selecting a Byzantine computer for a computation with ${n_{comp}} < \frac{|\textit{C}|}{2}$ is strictly decreasing in expectancy and converging to 0 as $i$ tends to infinity.
\end{lemma}

\begin{proof}
    As  $\textit{Reward}_i > \frac{\textit{cost}(\computation)}{\omega -\gamma}$, from Theorem \ref{thm:SINCE} rational computers follow the protocol. Let $\alpha$ be the share of computers that are Byzantine. We know a majority of computers selected are rational, as ${n_{comp}} >  {n_{\psi}}$. Therefore, Byzantine computers are rewarded with probability $\gamma < \omega$. For a given computation, the expected reputation increase of a selected Byzantine computer is $\gamma$, while the expected increase for a selected rational computer is $\omega$.
    Given ${n_{comp}}$ are selected for the computation, the expected number of these being rational computers is  $(1-\alpha) {n_{comp}}$, while the number of selected Byzantine computers is $\alpha {n_{comp}}$. Furthermore, this means the expected increase in reputation for rational computers is $(1-\alpha) {n_{comp}} \omega $, while the expected increase in reputation for Byzantine computers is $\alpha {n_{comp}}\gamma $. At the beginning of the protocol, the probability of selecting a Byzantine player from the set of all computers is in direct proportion to starting reputation. Given initial reputations of $\textit{initRep}$, after the first computation, the selection probability of a Byzantine computer reduces in expectancy to:
    \begin{equation}
        \frac{\alpha (|\textit{C}| \cdot \textit{initRep} + {n_{comp}}\gamma)}{|\textit{C}| \cdot \textit{initRep} + {n_{comp}} \big( (1-\alpha)\omega +\alpha\gamma \big)}.
    \end{equation}
    First it be can see that
    \begin{equation}
        \frac{\alpha (|\textit{C}| \cdot \textit{initRep} + {n_{comp}}\gamma)}{|\textit{C}|\cdot \textit{initRep} + {n_{comp}} \big( (1-\alpha)\omega +\alpha\gamma \big)}<\alpha
    \end{equation}
    meaning Byzantine selection probability is decreasing. To prove that Byzantine selection probability tends to 0 in the number of computations as described in the Lemma statements, let $\alpha_k$ be the Byzantine computer selection probability after $k$ computations. We have the expected Byzantine selection probability after $k+1$ computations, denoted , $\alpha_{k+1}$, is:
    \begin{equation}
    \begin{split}
        \frac{\alpha_k (|\textit{C}| \cdot \textit{initRep} + {n_{comp}}\gamma)}{|\textit{C}| \cdot \textit{initRep} + {n_{comp}} \big( (1-\alpha_k)\omega +\alpha_k\gamma \big)} \\
        = \frac{\alpha_k (|\textit{C}| \cdot \textit{initRep} + \gamma{n_{comp}})}{|\textit{C}| \cdot \textit{initRep} + {n_{comp}} \omega - \alpha_k {n_{comp}} (\omega-\gamma )}.
    \end{split}
    \end{equation}
    We have already seen $\alpha_{k+1}$ equals
    \begin{equation}
        \frac{\alpha_k (|\textit{C}| \cdot  \textit{initRep} + {n_{comp}}\gamma)}{|\textit{C}| \cdot \textit{initRep} + {n_{comp}} \omega - \alpha_k {n_{comp}} (\omega-\gamma )}< \alpha_k.
    \end{equation}
    which implies:
    \begin{equation}
        \frac{ (|\textit{C}| \cdot \textit{initRep} + {n_{comp}}\gamma)}{|\textit{C}| \cdot \textit{initRep} + {n_{comp}} \omega - \alpha_k {n_{comp}} (\omega-\gamma )}<1.
    \end{equation}
    Letting the term on the left be $r_k$, we can see $r_k$ is decreasing in $k$ as:
    \begin{itemize}
        \item ${n_{comp}} (\omega-\gamma )>0$ (because $\omega>\gamma$).
        \item $0<\alpha_{k+1}<\alpha_k$.
    \end{itemize}
    These together mean the negative term in the denominator of $r_k$, $\alpha_k {n_{comp}} (\omega-\gamma )$, is increasing (towards 0) and as such the denominator of $r_k$ is increasing. Therefore $\alpha_k< \alpha_0 r_{0}^k$, with $r_0 <1$. The result follows.
\end{proof}

\begin{remark}
    Lemma \ref{lem:diminishingProb} depends on the output of the on-chain randomness oracle being unpredictable when Request is called. Existing solutions, such as the Chainlink VRF \footnote{\url{https://docs.chain.link/docs/chainlink-vrf/}}, provide proofs that provided randomness was generated correctly. Analysis of the quality of this randomness is beyond the scope of this work.
\end{remark}
\end{spacing}

As a direct consequence of Lemma \ref{lem:diminishingProb}, with reasonable choices for rewarding functions and number of computers per-computation (explored in Table \ref{table:advShares}), both enforceable by the protocol, Byzantine players are eventually removed from the system. This improves the efficiency of the protocol over time, reducing the minimum requirements for computers, and as such, latency, transaction fees, and rewards.

\subsection{Privacy \texorpdfstring{$\text{Marvel DC}$}{TEXT}}\label{sec:PrivacyMarvel}

In this section we outline a privacy enhancement to $\text{Marvel DC}$ which we call Privacy $\text{Marvel DC}$. The motivation for this enhancement is to allow for an additional level of computer privacy which can be seen as necessary in computations such as those in FL protocols. The privacy provided is based on existing, well-known ZK techniques. However, this additional privacy on top of the novel contributions of being strong incentive compatible, generically applicable and fully decentralized further add to the applicability and utility of our work in an even larger set of DC problems.

We present Privacy $\text{Marvel DC}$ by describing it's key differences to $\text{Marvel DC}$ to ensure that in an optimistic scenario, only the requester and computers involved in a computation learn the results, and that players in the system can at most infer a computer submitted a good result (or bad result), but not which of the good results (bad results). In the pessimistic scenario, all players in the blockchain observe the results, but it still holds that any player in the system can at most infer a computer submitted a good result (or bad result), but not which of the good results (bad results). In Privacy \texorpdfstring{$\text{Marvel DC}$}{TEXT}, there is an additional contract, \textit{Reveal}, which is to be executed after the Response contract, and before rewards are finalized. The purpose of the Reveal contract is described later in this section.

During computer registration, computers in Privacy $\text{Marvel DC}$ privately generate $\textit{S}_1, \ $ $ \textit{r}_1 \in \{0,1\}^{O(\kappa)}$, and attach $\textit{regID}_1 \leftarrow $ $ f_\textit{com}(\textit{S}_1,\textit{r}_1)$ to the registration message, as described in Section \ref{sec:ZK}. Then, when a requester requests a computation, and the indices for computation $I$ are calculated, the requester now generates a Merkle Tree containing the indices as specified in $I$. This Merkle Tree is the structure to which only selected computers submitting results can prove membership in ZK. Results are therefore associated to a ZK set-membership proof which reveals nothing about the player that generated the proof. In Privacy $\text{Marvel DC}$, this separates result submission and player identity. To maintain this separation of identity from result, ZK set-membership proofs are required in the updated Finalize contract, described later in this section.

In addition to the deposits of $\text{Marvel DC}$, the requester must also deposit a pool of money necessary to incentivize relayers (as described in Section \ref{sec:Relayers}) to publish transactions on behalf of computers involved in the computation. Given the amount of money required by one relayer to include a blockchain transaction is $\textit{Fee}(\textit{relay})$, the additional required deposit is ${n_{comp}} \cdot \textit{Fee}(\textit{relay})$ for the relaying of computer messages during the Respnse phase.

In the Response contract for Privacy $\text{Marvel DC}$, computers selected in $I$ privately generate a ZK-proof proving their membership in $I$. Formally, given a computation result of $\textit{result}$, the computer sets $\textit{response} \leftarrow encrypt $ $(\textit{compute}(\textit{calc})$ $,\textit{calc}.\textit{compEncKey})$. The computer also generates a new $\textit{S}_2, \ $ $ \textit{r}_2 \in \{0,1\}^{O(\kappa)}$ pair, and computes $\textit{regID}_2 \leftarrow $ $ f_\textit{com}(\textit{S}_2,\textit{r}_2)$ . Setting $m \leftarrow \langle \textit{calc}, \textit{response}, \textit{r}_1, \textit{regID}_2 \rangle$, the computer generates a NIZKSoK  $\pi_1 \leftarrow $ \textit{NIZKSoK}[$m$]$\{(\textit{regID}_1,$ $\textit{r}_1):$ MemVerify ($I,$ $ \textit{regID}_1 )$ $=1 $ $ \And $ $ \textit{regID}_1=$ $ f_\textit{com}($ $\textit{S}_1, $ $\textit{r}_1) $ $\}$.
Finally, the computer then publishes $m$ and $\pi_1$ to the blockchain through a relayer, who receives $\textit{Fee}(\textit{relay})$ upon the transactions addition to the blockchain.

In the Reveal contract, the requester off-chain performs the same calculations that were done on-chain in $\text{Marvel DC}$ to calculate the results to be rewarded, but instead of adding computer indices to $\textit{responses}_{good}$, the requester adds the corresponding $\textit{regID}_2$s. The requester publishes $\textit{responses}_{good}$ and the encryption of $\textit{calc}.\textit{compDecKey}$ using each public key corresponding to computers in $\textit{calc}.I$ to the blockchain. However, rewards are not immediately distributed to computers in $\textit{responses}_{good}$.

In the Finalize contract, computers now have a chance to contest the computation of $\textit{responses}_{good}$ for up to $T$ blocks after the Reveal contract is called. If $\textit{responses}_{good}$ was computed incorrectly, any of the computers in $\textit{calc}.I$ can publish the decryption of all results and pass them into the $\textit{rateComputations}$ function of $\text{Marvel DC}$, proving the incorrect computation of $\textit{responses}_{good}$ by the requester. In this case, all computers are rewarded, and the requesters escrow is destroyed. To prevent malicious computers in $\textit{calc}.I$ from attempting this proof in order to reveal computation results, a further escrow is required, which is returned on the correct proving of miscomputation of $\textit{responses}_{good}$ by the requester.

If instead $\textit{responses}_{good}$ was computed correctly, any computer whose $\textit{regID}_2$ is included in $\textit{responses}_{good}$ can generate a proof of membership to $\textit{responses}_{good}$. Furthermore, as $\textit{regID}_1$ can no longer be used for future computations (using the same $\textit{regID}_1$ would reveal the same $\textit{r}_1$ in the next $\textit{calc}$), the computer generates a new $\textit{S}_3, \ $ $ \textit{r}_3 \in \{0,1\}^{O(\kappa)}$ pair and corresponding $\textit{regID}_3 \leftarrow $ $ f_\textit{com}(\textit{S}_3,\textit{r}_3)$. Setting $m\leftarrow\langle \textit{calc}, false, \textit{regID}_3 \rangle $, the computer with $\textit{regID}_2$ in $\textit{responses}_{good}$ then generates a NIZKSoK  $\pi_2 \leftarrow $ \textit{NIZKSoK}[$m$]$\{(\textit{regID}_2,$ $\textit{r}_2):$ MemVerify ($\textit{responses}_{good},$ $ \textit{regID}_2 )$ $=1 $ $ \And $ $ \textit{regID}_2=$ $ f_\textit{com}($ $\textit{S}_2, $ $\textit{r}_2) $ $\}$. Finally, the computer publishes $m$ and $\pi_2$ to the blockchain. In this variation of the protocol, computers not included in $\textit{responses}_{good}$ must also respond, updating there $\textit{regID}_1$. If this is not done, computers forfeit $\textit{escrow}_\textit{comp}$ and any reputation earned.

\begin{spacing}{1.5}
\begin{observation}

    As computers submit results through a relayer, and with an accompanying NIZKSoK $\pi$ proving membership in the selected indices for computation, all players in the blockchain protocol can be sure the player submitting the message must be a selected computer, but nothing else can be learned about the submitting player's identity. Similarly, when collecting rewards, or replacing $\textit{regID}_1$, the only thing learned when a computer submits a valid message during the Finalize phase is to which set, $\textit{responses}_{good}$ or $\textit{responses} \backslash \textit{responses}_{good}$, the computer belongs.
\end{observation}
\end{spacing}

\subsection{Further Privacy Enhancements}\label{sec:FurtherPrivacyRequirements}

There are further privacy enhancements possible for $\text{Marvel DC}$. One such enhancement is to detach reward collection/reputation updates from the computation. Given $\textit{responses}_{good}$ was calculated correctly, computers included in $\textit{responses}_{good}$ can instead delay their claiming of the reward and associated reputation increase arbitrarily. After a Finalize phase without arbitration, the set of $\textit{regID}_2$s corresponding to $\textit{responses}_{good}$ can be added to a pool of all recorded good responses throughout the protocol. These can then be immediately/periodically/sporadically claimed by computers, depending on the privacy requirements of the computer in question. This again uses the same NIZK set-membership techniques, except now with a larger set in which to diffuse.

\section{Implementation Analysis}\label{sec:Analysis}

In this section we analyse $\text{Marvel DC}$ and Privacy $\text{Marvel DC}$ as described in Sections \ref{sec:MarvelAlgos} and \ref{sec:PrivacyMarvel}. We show that on top of the unique formal guarantees of Section \ref{sec:properties}, both protocols are cost-effective and practical for both computers and requesters. Our reputation and computer selection mechanisms perform analogously to those graphed in \cite{CoUtileP2PDecentralizedComputing}. Crucially however, our protocols are proven to be strong incentive compatible in a fully decentralized setting, where computers an requesters have asymmetric utilities. The encoding of $\text{Marvel DC}$ is available here \cite{MarvelDCGithub}.

\subsection{Gas cost of running \texorpdfstring{$\text{Marvel DC}$}{TEXT} and Privacy \texorpdfstring{$\text{Marvel DC}$}{TEXT}}\label{sec:CostAnalysis}

\begin{table}[H]
\begin{center}

\scalebox{0.7}{
  \begin{tabular}{ |l|l|l|}
    \toprule
     & $\text{Marvel DC}$ & Privacy $\text{Marvel DC}$  \\
    \bottomrule
     Setup() & 2,000,000 & 2,450,000 + $h_\psi \cdot 150,000 ^{\dagger}$ \\
     \midrule
     Register() & 80,000 & 82,000 \\
     \midrule
     Request() & 500,000 + ${n_{comp}}$ $\cdot$ 31,000 + 0.25 LINK$^{\dagger \dagger}$ & \makecell{500,000 + ${n_{comp}}$ $\cdot$ 31,000 \\ + ${n_{comp}}$ $\cdot$ $h_\psi \cdot 51,000^{\dagger \dagger\dagger}$ + 0.25 LINK$^{\dagger \dagger}$} \\
     \midrule
     Response()& 60,000  & 63,000 +$300,000^{\dagger \dagger \dagger \dagger}$ \\
    \midrule
    Reveal() & N/A & 80,000 +${n_{reward}}$ $\cdot$ $h_\psi \cdot 51,000^{\dagger \dagger\dagger}$ \\
    \midrule
    Finalize() & - & - \\
    \midrule
     -No Arbitration & 80,000 +${n_{reward}}$ $\cdot$ 14,000 & (results not revealed) 83,000 + $300,000^{\dagger \dagger \dagger \dagger}$ \\
     \midrule
     -Arbitration & N/A & 80,000 +${n_{comp}}$ $\cdot$ 14,000 \\

    \bottomrule
  \end{tabular}}
  \caption{Gas costs of each contract call in $\text{Marvel DC}$ and Privacy $\text{Marvel DC}$. \footnotesize{$^\dagger$Cost of accessing Chainlink randomness. $^{\dagger\dagger}$Cost to generate a once-off Merkle Tree which can be reused for all computations. $^{\dagger\dagger\dagger}$ Cost to insert computer into copy of Merkle Tree. $^{\dagger\dagger\dagger\dagger}$ Cost to verify proof of membership on-chain.} } \label{table:gascosts}

\end{center}
\end{table}

There are several considerations when calculating the cost of running Marvel DC on a blockchain. In the case where a computation has a single 32 byte answer, the costs are significantly less than in the case of gradient estimation problem where answers contain thousands or millions of numbers. More concerning still is the prohibitive nature of messages in the order of MBs in many blockchain protocols. To counteract this, messages for the Response and Finalize contracts can be submitted to memory-efficient alternatives such as IPFS\footnote{\url{https://ipfs.io/}}, Layer-2 chains or even through an MPC protocol between computers and requesters (not necessarily the same entities involved in the computation). All of these suggestions require the use of checkpoints (such as those proposed in \cite{Casper}), pieces of summary information identifying permanent states in an off-chain protocol which are published to the main-chain, updating the state of the main-chain.

In Table \ref{table:gascosts} we present the approximate gas costs for $\text{Marvel DC}$ and Privacy $\text{Marvel DC}$ on an Ethereum-compatible blockchain of the main operations for a requester and computers in a computation, given ${n_{comp}}$ and a 256-bit result, with all messages published on-chain. This can be extended to $l$-dimensional results for any $l>1$. The set-membership tools described in Privacy $\text{Marvel DC}$ are pre-compiled, and currently being used in the Tornado Cash privacy protocol. We thus calculate the gas cost of the set-membership tools using the Tornado Cash library. All other operations are typical on-chain array manipulation, encryption/decryption, deposit, withdraw and writing to memory operations. We also include the cost of calling an on-chain randomness oracle in our calculation. This call needs to be made prior to the calculation of the indices for computation, and must be made when depositing rewards and escrow to ensure the requester cannot manipulate the selection of computers. To approximate the costs of running Privacy $\text{Marvel DC}$ described in Section \ref{sec:PrivacyMarvel}, we utilize ${n_{\psi}}$ the maximum number of computers required to select in order to guarantee a majority are rational. We let $h_\psi = \lceil\textit{log}_2({n_{\psi}})\rceil+1$. This is the required height of the Merkle Tree to be used in the ZK-proofs for set-membership.

As an example, using current gas costs of 32 GWEI/gas and 1 GWEI = $\$0.00000335$ \footnote{\url{https://etherscan.io/gastracker}, Accessed: 03/04/2022}, for ${n_{\psi}}=10$, and a computation with ${n_{comp}}=10$, for the basic protocol, this is a per computer cost of 140,000 gas, or $\$15$, while a requesters cost is 950,000 gas, or $\$102$ + $\$4.5$ for the LINK\footnote{\url{https://docs.chain.link/docs/vrf-contracts}, Accessed:03/04/2022 } required to access the on-chain randomness \footnote{\url{https://www.coingecko.com/en/coins/chainlink}, Accessed:03/04/2022}. Deploying on a cheaper protocol like Harmony with gas costs of
$\$0.00000005$ at the time of writing \footnote{\url{https://explorer.harmony.one/}, Accessed: 03/04/2022}, this is an approximate cost of $\$0.001$ and $\$4.505$ respectively.

For Privacy $\text{Marvel DC}$ on Harmony with ${n_{reward}}=5$, this gives $h_\psi=4$, and a gas cost of 950,000+ 2,040,000 for requesting, and 80,000+1,020,000 for revealing rewards, a total of 4,190,000 gas ($\$0.02$), plus the cost for accessing on-chain randomness ($\$4.5$), a total cost for the requester of $\$4.52$ . For computers, the cost is 746,000 gas ($\$0.004$) in the optimistic execution, and 503,000 ($\$0.0026$) in the pessimistic, but only for one computer. This means both implementations of $\text{Marvel DC}$ are suitable for immediate deployment on public blockchains.

\subsection{Latency and Throughput}

A direct comparison of our protocol to most existing distributed FL solutions with respect to throughput and latency is of limited benefit. This is because the the concept of time in decentralized systems (blocks in a blockchain) has no immediate parallel when centralized parties are required, as in \cite{BlockchainDecentralisedFedLearningLi,FLChainBao,FLChainMajeed,FedLearningMeetsBlockchainMa,BlockFLKim,DeepChainWeng, BlockchainRepAwareFedLearningRehman}.

Considering the protocols which allow for tokenized rewards in a decentralized setting (protocols which do not allow for tokenized rewarding have limited utility in a decentralized setting), this leaves only \cite{IncentiveMechFLBlockchainToyoda} and \cite{FairnessIntegrityPrivacyBlockchainBasedFLSystemRuckel}. Using the terminology of our paper, every protocol \textit{phase}, a period of time where an event occurs which requires a response, lasts up to $T$ blocks.  These $T$ blocks (as used in Section \ref{sec:AlgoOverview}) are equivalent to the time required to ensure players can submit transactions to the blockchain after a particular on-chain event, such as a computation request. $\text{Marvel DC}$ therefore lasts up to $2 T$ blocks, which covers the time for computers to respond to a request, and the time taken for the requester to reveal the decryption key. The protocol of \cite{IncentiveMechFLBlockchainToyoda} lasts at least $4 T$ blocks to ensure workers are incentivized to submit at least one correct model update (using the terminology of \cite{IncentiveMechFLBlockchainToyoda}, 2 model update rounds are needed for this to be the case). The additional costs are due to requesters and computers being required to respond twice each after the initial request. The protocol of \cite{FairnessIntegrityPrivacyBlockchainBasedFLSystemRuckel} requires at least $3 T$ blocks, as computers must commit to the data-set to be used, before submitting a computation result. All 3 protocols, including our own, are equipped to spawn arbitrarily many computations in parallel.

\subsection{Necessary bounds on the number of computers per-computation}

\begin{table}[H]
\begin{center}

\scalebox{0.83}{
  \begin{tabular}{ |r|r|r|r|r|r|r|r|}
    \toprule
     &${n_{comp}}=$\textbf{10}&\textbf{25}&\textbf{50}&\textbf{100}&\textbf{250}&\textbf{500}&\textbf{1000}\\
     \midrule
    $\alpha=$ \textbf{0.45}&0.504&0.694&0.716&0.817&0.936&0.986&0.999\\
    \midrule
    \textbf{0.4}&0.633&0.846&0.902&0.973&0.999&1&1\\
    \midrule
    \textbf{0.33}&0.787&0.958&0.989&1&1&1&1\\
    \midrule
    \textbf{0.25}&0.922&0.997&1&1&1&1&1\\
    \midrule
    \textbf{0.2}&0.967&1&1&1&1&1&1\\
    \midrule
    \textbf{0.1}&0.998&1&1&1&1&1&1\\
    \midrule
    \textbf{0.05}&1&1&1&1&1&1&1\\
    \midrule
    \textbf{0.01}&1&1&1&1&1&1&1\\
    \bottomrule
  \end{tabular}}
  \caption{The approximate probability, correct to 3 decimal places, of choosing a majority of rational computers given specific starting adversarial $\%$ of computers $\alpha$ (left column) and selected numbers of computers ${n_{comp}}$ (top row) from a sufficiently large population of computers such that adversarial share represents the per-selection probability of selecting an adversarial computer throughout sampling.} \label{table:advShares}

\end{center}
\end{table}

To estimate the required value of ${n_{\psi}}$ required to ensure a sufficiently probably majority of rational players, Table \ref{table:advShares} serves as a starting point. We recommend conservative choices of adversarial share and probability of rational majority. For example, given an adversarial share of $20\%$ of computers, any value of ${n_{\psi}}\geq 25$ suffices to ensure a majority of rational computers are chosen per-computation.

\section{Conclusion}

We present $\text{Marvel DC}$, a strong incentive compatible blockchain-based decentralized DC protocol which stands as a new standard in constructing fully decentralized DC protocols. This is achieved through a novel combination of strong incentivisation of rational computers in the presence of Byzantine computers, reputation-aware computer selection and privacy-enhancing techniques which can be bootstrapped to the core $\text{Marvel DC}$ protocol to allow for the use of $\text{Marvel DC}$ on computations revealing sensitive data about the computers participating in the protocol. Much work remains to ensure DC protocols remain incentive compatible and practical where computations produce large outputs, with storage being a limiting resources in mainstream blockchain protocols. $\text{Marvel DC}$ and Privacy $\text{Marvel DC}$ serve as key protocols with which to continue this research.

\section*{Declaration of Competing Interest}

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

\section*{Acknowledgements}

We thank IEEE Fellow Josep Domingo-Ferrer and his group at Universitat Rovira i Vigili for many interesting and motivating conversations related to this paper.

\section*{Vitaes}

\subsection*{Conor McMenamin}
\begin{figure}[H]
	\includegraphics[width=0.25\textwidth]{ConorProfile.jpg}
\end{figure}

Conor is a Marie Curie Fellow, working as researcher at Nokia-Bell Labs undertaking a PhD in Universitat Pompeu Fabra (UPF). He holds a Bachelor of Science degree in Computational Thinking (2015), and a Master of Science degree in Cryptography (2019). His research focuses on the game-theoretic aspects of blockchain technology, both at the consensus and the application layer.

\subsection*{Vanesa Daza}
\begin{figure}[H]
	\includegraphics[width=0.3\textwidth]{VanesaProfile.jpg}
\end{figure}

Vanesa is an Associate Professor at UPF. She holds a degree and a PhD in Mathematics.
Her research now focuses on designing cryptographic primitives and protocols to undertake  security and privacy challenges on blockchain technologies. She has co-authored over 40 papers and is the co-inventor of two international patents.
She has served as Associate Editor for two IEEE Transactions journals, several Program Committees and reviewer of international journals.
She currently coordinates two H2020 projects and collaborates with several companies. Likewise, she has served at UPF in several roles, including chairing the Department of Information and Communication Technologies.

\addcontentsline{toc}{section}{Bibliography}
\bibliographystyle{plain}

redpajama_set_name: RedPajamaArXiv


Here is the track list for "Aagye Mere Land Ka Tamsha Dekhene" we may collect and you can listen to and download. . Aagye Mere Land Ka . ka tamasha dekhne best .. Taqdeer Ka Tamasha Full Hindi Movie Govinda, Jeetendra, Mandakini, Kimi Katkar Full HD 1080p. . Taqdeer Ka Badshah - Full Hindi Bollywood Action Movie HD .
Download Housefull 2 movie Full HD Video Songs. You can download Housefull 2 720p & 1080p High Definition MP4 Blu-ray Quality Videos to your device for free.
Taqdeer Ka Tamasha: Taqdeer Ke . Download Songs Mp3 Songs,hindi movie Mp3 Songs of Songs download,download bollywood movie songs . Download full album of free .. Get Free Email, Chat, & Messaging.. Listen or download Meri Hatho Ki Lakiro Ka Tamasha Dekh Mp3 Song Dowenload music song for free. Please buy Meri Hatho Ki Lakiro Ka Tamasha . Download Full Album .


Samantha is a UK based writer, with short stories published in various magazines and anthologies both at home and abroad, including the new Edit Red anthology, Late Night River Lights.
Samantha's first novel, Despite Losing it on Finkle Street, was chosen as the launch title for the new imprint, Pioneer Readers, at Fygleaves Publishing, where the first chapter can be read online.
Samantha is the author of: "A Bad Winter", "Reliability of Rope", "Dreamers", and "Orange Balloon".
Her new novel, "Rose Villa" is coming soon from ASJ Publishing.


text:
Tag Archives: it
Does Anyone Remember 'Whose Line It Is' After all? Its Back!!!
May 30, 2013 vineetnov	2 Comments
Remember that show where 4 guys used to crack unthinkable and the funniest jokes that you could ever hear and instantaneously??? Well if you don't, then you seriously have missed out on a heck of show! And for the ones who have seen the show and been a fan like I have, here is a great news for you all! 'Whose Line Is It Anyway' is in for an entirely new run this July!!!
Best part about the show is that the original cast except for Drew Carey are back for the reboot! A short 5 mins clipping has been released from the upcoming season and trust me, it brings back the same feeling that the show had back in days, just that Drew Carey might be missed a little, with Aisha Tyler as the new host. But that can still be compromised having Wayne Brady, Ryan Stiles, and Colin Mochrie back doing what they do best! The theme of video revolves around a little something called '90210' fever.
Well… this will help in turning down the so-called Fever!!! I just hope that the other guys Charles Esten, Greg Proops and remaining gang also return to the show and create the magic they created last time!
The show will premier on the 16th of July! Excited??? I am!!!
2013anywayisitlinenewtvwhose
Linkin Park's New Single "Burn It Down" – Review!!!
April 16, 2012 vineetnov	2 Comments
The band had recently announced that they would be releasing a new single named "Burn It Down" and its finally out! The song is good! Not the "really awesome types" good that Linkin Park is actually capable of, but still good. The song has lots and lots of digital sounds in it, which at times makes sound like a pop song, but then the rock part comes in, which reminds us "oh yeah…Linkin Park…Rock…right!!". It mostly reminds me of their single for Transformers 2, "New Divide", the way Chester sings his part, the way the music goes and all.
Well there were quite a lot speculations going around about how the album would be, but this song makes me feel that they have stuck to there "A Thousand Suns" kind of style, i.e. with more meaning in the lyrics and lots of digital music in the background.
The song is all about how people try build up things and try live upto their own and other's expectations, but then eventually, they themselves end up destroying what they have built, as the lyrics go "We're building it up, to break it back down… we're building it up, to burn it down…we can't wait to burn it to the ground".
The music video to the song will be out soon, though the official lyric video got released on YouTube just today(16th April, 2012). Here is the lyric video…
The album is named "Living Things" and it would be coming out on the 26th of June, 2012. And here is the song for iTunes download.
And here is the track-list of the album:
1. LOST IN THE ECHO
2. IN MY REMAINS
3. BURN IT DOWN
4. LIES GREED MISERY
5. I'LL BE GONE
6. CASTLE OF GLASS
7. VICTIMIZED
8. ROADS UNTRAVELED
9. SKIN TO BONE
10. UNTIL IT BREAKS
11. TINFOIL
12. POWERLESS
So what are your thoughts on the song and expectations from the album???
burndownitlinkinparkreviewsingle
Enrique Likes How It Feels – New Single!!!
November 28, 2011 vineetnov	3 Comments
Enrique is back with his new single "I Like How It Feels" featuring Pitbull (again). The rapper had appeared in the first single off the last album "Euphoria" named "I Like It". Frankly… I felt that this song is way…way better than its two words younger brother.
The song came out last week and I know it's a bit late to review a week old song, but still, since I liked it, thought of writing a post. So, the song for a change is not about any girl who ditches Enrique or about how he likes a girl on top of him or about how he likes to see a sexy girl pole dancing in front of him. The song talks about Enrique's way to success and how great he feels to be where he is today. The song has fab music and effects to it, which actually makes us like how it feels to listen to it.
The video of the single is great. It has been directed by Enrique himself and features many celebs like Eva Longoria, George Lopez, Ken Jeong(the chinese guy from 'Hangover') and some others like them! The video is mainly dedicated to Enrique's fans. There are some behind the scenes videos merged in the music video itself, showing how crazy fans get at concerts and all the fun stuffs that Enrique and his friends do while in studio or out of studio. Well, watch the video right here and decide how much you like how Enrique feels! And oh… the chinese guy has done it again! See how he brings Hangover crazyness into the video!
So???
enriquefeelsft.howiitlikepitbullsingle
Bruno Mars says "It Will Rain"!!!
September 27, 2011 vineetnov	4 Comments
Just when I was wondering that I didn't get to listen anything new & "good" from any of my favorite artists, I get a mail from a subscription that I had made on the official Bruno Mars website saying "Listen To The NEW SINGLE – It Will Rain!" !!! And I go "Phew…Thank God!"
Yup! The "Grenade" hit maker is back with a new single named "It Will Rain". The song is going to feature in the highly anticipated upcoming movie "Twilight: Breaking Dawn"! Highly anticipated because people and media say so. Personally speaking, this song is the only thing that I'm excited or happy about! Not interested in movie at all. No offences meant! The song is subtle, sweet and wonderful. I don't know how the guy does it everytime. Every song by Bruno seems so wonderful in its own way. They should make a new genre of songs called "Bruno" especially for him. The lyrics, the music, the beats and off course, the singing are really good, though they don't match upto the standards of "Grenade", "Just the way you are" or "Liquor Store Blues", but still, like I said earlier, its beautiful in its own way!
Listen to the song right here!
You can download the song on iTunes here !
Update: Guys! The official video to this beautiful song is up now. The video is about Bruno, an up coming musician ( I guess) and a girl who are in love and are leading a happy life. But eventually things start to fall apart when Bruno is not able to find enough time to be with his girl, being busy making music throughout the day and all night long, which makes his girlfriend feel ignored and so on. It has scenes from "Twilight: Breaking Dawn Part I" movie as well. Watch the official video right here!
So…What are your thoughts???
breakingbrunodawnitmarsrainsingletwilightwill
AJ McLean New Video Single "Teenage Wildlife"
Oh yeah! The rockstar from the Backstreet Boys has finally released his first video single from his solo debut album "Have It All"!
The video has been picturised on the song named "Teenage Wildlife", which is an awesome dance song! The video starts as AJ with some of his friends looks for his love, and AJ's love happens to be someone who is in a wild creature's outfit (maybe that's why they have named the song "Teenage Wildlife")! So, in search of his love, AJ and his friends enter into a club which is full of people in suits of wild animals . AJ, after half of the song finally finds his love and to his surprise finds another 'wild creature' who also loves that same girl, with whom AJ is in love with and he challenges AJ to a dance battle!
Now, I think it would be better if you actually watch the video and see how the story ends. It is a different kind of music video but it always feels great to see AJ dance to awesome music and beets like in this song! So, get ready to get pumped up!
So, what do you think about it???
ajalbumallhaveitmcleansinglesoloteenagevideowildlife
So I decided to go premium on #Spotify ! Still pissed @spotifyindia since they don't have @linkinpark @GreenDay and… twitter.com/i/web/status/1… 10 hours ago
Yo @spotifyindia !!! I was already pissed with Spotify missing @linkinpark and @GreenDay here in India, now the fir… twitter.com/i/web/status/1… 1 day ago
A broad day light and an evening sun kissed view of the gothic Budapest Parliament House! . . . . . . . . . . . . .… twitter.com/i/web/status/1… 1 week ago
#SpiderManFarFromeHome is an awesome AWESOME movie! Loved what they did with #Mysterio . A more realistic and belie… twitter.com/i/web/status/1… 1 week ago
A broad day light and an evening sun kissed view of the gothic Budapest Parliament House! . . . . . . . . . . . . .… twitter.com/i/web/status/1… 2 weeks ago
Follow @vineetnove

redpajama_set_name: RedPajamaCommonCrawl


California Custom Coatings believes that only the highest quality, longest-lasting products should cover our customers' concrete. Starting with this important principle, we then give top priority to meeting the client's needs and desires, while designing the best possible flooring system for their budget. We back our work with a lifetime warranty, supported by premier materials from leading manufacturers.
California Custom Coatings also wants to live up to our name. To say we create "custom" coatings, we must offer a wide range of flooring colors mixed with color flakes, granites, and granules. The result is a nearly endless array of combinations. So where other companies offer limited patterns to cut costs, we offer a dazzling variety of products manufactured by companies known for quality supplies and proven success.
selecting the color. There was absolutely no pressure on which product to go with, but we did decide on the upgraded polyaspartic clear coat and are very happy we did so. The day of the install, Louis and Victor arrived on time and did an excellent job. They even helped us move the last heavy cabinet and refrigerator out. Louis also took the time to explain the time line for when we should move things back into the garage, as well as the best cleaning process. It was apparent that they cared about the customer's satisfaction and the quality of their work. We will be sure to recommend CCC to everyone we know.


How to Convert FLV to AAC using FLV to AAC Converter?
This step-by-step guide provide instruction for converting FLV to AAC file using Dicsoft Video Converter Platinum , It is as easy as 1-2-3.
Dicsoft Video Converter Platinum is a powerful and professional FLV AAC Converter which can convert FLV files to AAC perfectly. With super fast speed and an easy-to-use interface, it makes FLV to AAC conversion routine very simple. Enjoy your AAC video file made from an FLV file on your PC with such as an affordable FLV to AAC tool.
Dicsoft Video Converter Platinum makes your conversion task FLV to AAC a breeze, and easily converts FLV2 to other popular video formats like WMV, 3GP, FLV, etc. Moreover, it also can convert into AAC video from almost any popular video formats, such as MKV, WMV, FLV, MPG, etc.