{'fraction_non_alphanumeric': 0.03196459711117691, 'fraction_numerical': 0.005988220971934327, 'mean_word_length': 4.72867778720196, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Fair Marketplace for Secure Outsourced Computations

The cloud computing paradigm offers clients ubiquitous and on demand access to a shared pool of computing resources, enabling the clients to provision scalable services with minimal management effort. Such a pool of resources, however, is typically owned and controlled by a single service provider, making it a single-point-of-failure. This paper presents Kosto - a framework that provisions a fair marketplace for secure outsourced computations, wherein the pool of computing resources aggregates resources offered by a large cohort of independent compute nodes. Kosto protects the confidentiality of clients' inputs as well as the integrity of the outsourced computations and their results using trusted hardware's enclave execution, in particular Intel SGX. Furthermore, Kosto warrants fair exchanges between the clients' payments for the execution of an outsourced computations and the compute nodes' work in servicing the clients' requests. Empirical evaluation on the prototype implementation of Kosto shows that performance overhead incurred by enclave execution is as small as 3% for computation-intensive operations, and 1.5x for IO-intensive operations.


INTRODUCTION
The cloud computing paradigm features a service provider offering its clients convenient and on-demand access to a shared pool of computing resources, enabling the latter to provision scalable services with minimal management effort. In such a model, clients typically entrust the cloud service provider to handle their data, to perform their outsourced computations, and to meter their cost footprint acurately (e.g., CPU-cycle, network bandwidth, storage) [50]. Although the clients may enjoy a wide range of cloud computing services, they are all offered by and at discretion of a few specific service providers.
Recent years have witnessed an emergence of online marketplaces that are in competition with traditional vendor-specific service providers. Examples include Airbnb [1] in lodging, Uber [15] in transportation, and Golem [2] in outsourced computations. In such marketplaces, the shared pool of resources is no longer owned, provisioned and controlled by a single party, but rather aggregates those that are offered by a large cohort of independent providers. Designing a fair marketplace for secure outsourced computations, however, faces various challenges.
The first challenge is in protecting the confidentiality of the clients' data and the integrity of the outsourced computations, for the resource providers (or compute nodes) may be untrustworthy. Solutions to protect the confidentiality and integrity of outsourced computations have been studied in the literature [28][29][30]57]. For examples, homomorphic encryption [29,57] and secure multi-party computation [30] are designed to protect data confidentiality, while verification by replications [2,13] and verifiable computation [28] aim to protect computation integrity. Nevertheless, these approaches either incur prohibitive overheads or support only a limited range of applications, hindering their adoption in practical systems.
Another challenge is in codifying fair exchanges between clients' payments for the execution of the outsourced computations and compute nodes' work in servicing the clients' requests. In the "payas-you-use" metering model where clients are billed based on the computing resources that their requested services consume, both clients and compute nodes have strong economic interests to falsify the resource metering (e.g., the compute nodes try to overcharge the clients, while the latter aim to be undercharged). One approach is to fix a remuneration for a task before hand, and let the compute node collect such reward once it returns a correct result for that task. To guarantee fairness, the remuneration might be deposited into an escrow held between the client and the compute node, which automatically and anomously releases the reward to the compute node upon successful task completion, or returns it to the client after a certain time-out. This approach, however, does not generalize. In particular, with micro tasks that yield very small remunerations, the transaction fee (i.e., the cost to conduct the payment transaction, which is often unproportional to the transaction value) becomes an overhead. In case of macro tasks, compute nodes may inadvertently abort the tasks midway (perhaps due to overly-extensive resource consumption), spending certain computational work but could not claim the reward. An ideal solution to enable fair exchanges between the clients and the compute nodes would require trusted metering of the latter's work and an self-enforcing or autonomous agent that is responsible for settling payments between the two parties based on the metering.
In this paper, we present Kosto -a framework that enables a fair marketplace for secure outsourced computations. Unlike in vendorspecific cloud services, a shared pool of computing resources in Kosto aggregates a large cohort of independent compute nodes each of which is capable of provisioning a Trusted Execution Environment (TEE) (e.g., using Intel SGX) for outsourced computations. The TEE provisioned by SGX, called an enclave, prevents other applications, the operating system and even the host owner of the compute node from tampering with the execution of application loaded within or observing its state, thus guaranteeing data confidentiality and computation integrity. A client in Kosto can request computational services from the compute nodes, while enjoying confidentiality protection on their data and integrity assurance on their outsourced computations. The compute nodes service the clients' requests by executing the outsourced computation inside an enclave that is attested to be correctly instantiated. Moreover, Kosto enables fair exchange between the clients and compute nodes via a novel hybrid architecture that combines TEE-based metering with blockchain micro payment channel [12,47]. More specifically, Kosto incorporates in each enclave that houses the outsourced computation an accounting logic that correctly meters the compute node's work. Such metering is then translated to a payment promise with which the compute node can settle the escrow and claim the corresponding reward. This allows the fair exchange between the client's payment and the compute node's work in executing the outsourced task, without incurring high overhead (i.e., transaction fee) or involving a trusted third party.
Besides, to facilitate the matching between clients and compute nodes, Kosto designates brokers to collect resource advertisements from available compute nodes as well as task requests from clients. The brokers then evaluate among the requests and offers it receives appropriate assignments of tasks to compute nodes. We devise a solution for maximum task assignment in a dynamic settings wherein the broker continuously receives new requests from the clients and resource offers from the compute nodes. To eliminate monopoly of broker and avoid single-point-of-failure, Kosto allows multiple brokers to co-exist, wherein a client or a compute node can also play a role of self-serving broker.
Empirical evaluations on the prototype implementation of Kosto reveals that the overhead incurred by enclave execution and the trusted metering is reasonable, which is as small as 3% for computation-intensive operations, and 1.5× for I/O-intensive operations. We remark that while Kosto is fully compatible with optimizations that enhance the efficiency of enclave execution [46,55,58], our prototype implementation does not include them. Thus, we expect the results reported in our evaluations (Section 6) to be an over-estimation of the real overhead that enclave execution incurs over unstrusted non-enclave execution, and the fully optimized implementation of Kosto to attain better efficiency.
In summary, this paper makes the following contributions.
• We propose Kosto -a framework enabling a fair marketplace for secure outsourced computations that protects confidentiality of clients' inputs and integrity of the outsourced computations. • We codify in Kosto a protocol that warrants fair exchanges between clients' payments for the execution of the outsourced computations and compute nodes' work in servicing the clients' requests. • We devise a task assignment mechanism that optimally matches pending requested tasks against available compute nodes in the system. • We conduct extensive experiments to demonstrate Kosto's practicality. The experiments shows that performance overhead incurred by enclave execution and trusted metering is as small as 3% for computation-intensive operations, and 1.5× for I/O-intensive operations.
The rest of the paper is organised as follows. We provide necessary backgrounds on Intel SGX, cryptocurrencies and their payment channels, as well as prior work on marketplace for outsourced computations in Section 2. Next, we give an overview of Kosto in Section 3, before presenting its design in Section 4. We then analyse its security in Section 5 and conduct empirical evaluation in Section 6. Finally, we survey the related works in Section 7 before concluding our work in Section 8.

PRELIMINARIES 2.1 Trusted Execution Environment
Kosto leverages Intel SGX [17,41] to provision a Trusted Execution Environment (TEE) that protects confidentiality and integrity of the clients' data and computations. Nonetheless, we remark that Kosto is compatible with any other mechanism featuring similar capabilities. In the following, we summarize key features of Intel SGX's TEEs.
Intel SGX [41] is a set of CPU extensions capable of providing hardware-protected TEE (or enclave) for generic computations. It enables a host to instantiate multiple enclaves at the same time. An enclave is isolated from other enclaves, from the operating system (OS), and from the host itself. Each enclave is associated with a protected address space. The trusted processor blocks any non-enclave code's attempt to access the enclave memory. Memory pages can be swapped out of the enclave memory, but it is encrypted using the processor's key prior to leaving the enclave.
Intel SGX provides attestation mechanisms that allows an attesting enclave to demonstrate to a validator that it has been properly instantiated with the correct code [17]. In addition, the attestation mechanism also enables the attesting enclave and the validator to establish a secure, authenticated channel via which they can securely communicate sensitive data.
If the validator is another enclave instantiated on the same platform with the attesting enclave, the two parties engage in a local attestation mechanism. Abstractly, once the code in question has been initiated inside the attesting enclave, the trusted processor computes a measurement of the initiated code (i.e., the hash of its initial state). Next, it produces a message authentication code (MAC) of such measurement using a key that is known only to the hardware and the validating enclave. Based on the measurement and the MAC, the validating enclave can verify if the attesting enclave has been instantiated correctly. Alternatively, if the validator is a remote party outside of the platform, the trusted processor creates a remote attestation by signing the attesting enclave's measurement with the hardware's private key under the Enhance Privacy ID (EPID) scheme [33] [17]. The remote party obtaining the attestation then requests Intel's Attestation Service (IAS) to verify the signature contained in the attestation on its behalf [6].
Recent attacks on Intel SGX show that enclave execution may be vulnerable to side-channel leakage [60], to which various defenses have been proposed [25,38,53,56]. Kosto is compatible with these side-channel leakage defenses.

Cryptocurrencies and Micro Payment Channel
Cryptocurrencies. Decentralised cryptocurrencies have gained considerable adoption since the introduction of Bitcoin [44]. They are typically administered on the public ledger that is secured and maintained by a set of independent peer-to-peer network operators (or miners). Cryptocurrencies allow any two willing parties to transact directly with one another without relying on any trusted third party. While our discussion focuses on the Ethereum blockchain [20] due to its popularity and the expressive capability of its ecosystem, payment in Kosto can be settled using any other currency that enables similar properties. Smart Contract and Payment Escrow. Ethereum enables smart contract (or contract for short), which is an "autonomous agent" stored in the blockchain. A contract is associated with a predefined executable code. Incentive and security mechanisms of the Ethereum ecosystem encourage miners to execute the contract's code faithfully [20]. While various works have shown that miners could be incentivized to deviate from the contract code, they only apply to contracts that require nontrivial computation effort [39]. Smart contract could be used to implement an escrow that enables fair exchange between two parties without relying on a trusted third party. The escrow enforces a payment from a payer to a payee once the payee has delivered some service to the payer, while keeping the payment inaccessible to the payee before such delivery. Kosto employs this capability to facilitate fair exchange between clients and compute nodes. Transaction Fee. The contract implementing the escrow can be invoked by a transaction in the Ethereum network. Each such transaction is associated with a transaction fee which is typically proportional to the execution complexity of the contract. In another words, the cost of settling the escrow does not necessarily depend on the monetary value that the escrow holds. Should the payment value is too small (i.e., micro transaction), the transaction fee becomes a significant overhead. Blockchain Scalability. The core component underlying cryptocurrencies is a consensus protocol which enables all (honest) peers in the network to "agree" on the same transaction history and to avoid double-spending. Consensus protocol in Ethereum's currently processes only a dozen of transactions per second 1 . Due to this limitations, Kosto's design has to restrict the number of on-chain transactions, while still offering fine-grained resource metering and payment. Payment Channel. Payment channel enables two parties to transact a large number of micro payments without incurring high transaction fee or overloading the blockchain with excessive number of transactions [12,47]. A payer establishes a channel to a payee by depositing a maximum amount of value that they wish to be transacted into an escrow on the blockchain. Subsequently, when a payer wants to make a micro payment to the payee, instead of posting the transaction to the blockchain, he issues a digitally signed and hash-locked transfer, called payment promise, and sends it offchain to the payee. The value contained in the payment promises should not exceed the on-chain deposit that was set up previously, otherwise it cannot be fully collateralized.
The escrow was programmed such that it can only be closed once using a single payment promise. The payment promises given to the payee have increasing value, where in each promise contains the sum of its immediate predecessor and the current micro payment. Let us assume the payer intends to make n micro payments whose values are ⟨v 1 , v 2 , · · · , v n ⟩. The i t h payment promise takes the value of i k =1 v k , invalidating all its predecessors. The payee can close the escrow at any time and claim the payment she has been promised so far by posting the last payment promise she received to the escrow. Upon receiving a closing payment promise, the escrow transfers the value indicated in the payment promise to the payee, and the remaining portion, if any, to the payer. This mechanism allows two parties to transact a very large number of micro payments using only two on-chain transactions (one for opening the channel, the other for closing it).

Prior Work on Marketplace for Outsourced Computations: Golem
The most closely related project to Kosto is Golem [2]. The Golem network connects computers in a peer-to-peer network, and allows application owners and individual users to rent computing resources from other users' machines (i.e., compute nodes) to execute their tasks. Golem incorporates a dedicated Ethereum-based transaction system to facilitate direct payments between involved parties. Nonetheless, the current architecture and system designs of Golem face several challenges that are left unresolved. First, Golem does not offer attested execution, allowing compute nodes to tamper with correct execution of outsourced tasks, or return bogus results. To verify the compute nodes' outputs, Golem has to repeat the same computation at different compute nodes, employing a majority voting principle to determine the correct result. This approach is not only subject to high overhead due to the redundant execution, but also susceptible to collusion wherein malicious compute nodes conspire to output the same incorrect result so as evade the voting.
Second, Golem does not feature trusted fine-grained metering. Compute nodes in Golem are only eligible to claim remuneration if they successfully finish the task and return correct results. If the assigned tasks are too large and they inadvertently have to abort midway (e.g., the task was ill-defined or consuming an unexpectedly large amount of resource), they cannot claim any reward despite having spent certain computation work. Further, a probabilistic nanopayment scheme in Golem 2 requires compute nodes to actively involve in the system for a potentially long period of time before being able to collect its reward [21].
Finally, Golem requires the outsourced task to adhere to certain templates as defined in their task and transaction framework. This adherence is necessary for Golem's task verification and remuneration mechanisms. Nonetheless, the expressiveness of Golem's task templates remains to be seen.

SYSTEM OVERVIEW
This section presents an overview of Kosto, focusing on its architecture and desired properties. We then state the threat model and assumptions that we make in designing Kosto. Finally, we introduce a strawman design that we shall convert step-by-step into Kosto.

Kosto overview
Kosto is a framework that enables a fair marketplace for secure outsourced general-purposed computations. Unlike vendor-specific cloud services, the pool of computing resources in Kosto aggregates those offered by a large cohort of independent compute nodes (which 2 The payment scheme essentially runs the lottery among n compute nodes ⟨C 1 , C 2 , . . . , C n ⟩, wherein C i expects a payment of v i . The lottery reward is V = n i =1 v i , and the winning probability of participant C i is v i /V . The winning node collects the whole sum V , while others receive nothing. we shall discuss in more details below). Computation and data that are executed and processed in Kosto enjoy strong confidentiality and integrity protections, thanks to the use of TEE on the compute nodes. Further, Kosto ensures fair exchange between the clients and compute nodes via a novel hybrid architecture that combines TEE-based metering with the Ethereum blockchain 3 . The Kosto architecture comprises three main parties: clients, compute nodes and brokers.
• Clients are end users of Kosto. A client would like to the execute a program Program on an input Input. The program Program can be written by the client, or an open-source software provided by a third party. In either case, the client outsources such computational task to a compute node. For practical usability reason, the clients are not expected to maintain constant connection with the compute node executing its program over the course of the outsourced computation. • Compute nodes are machines equipped with trusted processors (e.g., Intel SGX processors) that are capable of provisioning TEEs (or enclaves). A compute node services a client request by running its code in an enclave, and generating an attestation that proves the correctness of the code execution (and thus the result). In return, the compute node receives remuneration v proportional to computational work it has asserted in executing the outsourced task. • Brokers facilitate node discovery as well as load balancing. Moreover, the brokers assist the clients in attesting that the compute nodes have correctly instantiated the enclaves housing the outsourced computations. Brokers may charge clients and/or compute nodes certain commission fee in return to their services. Kosto eliminates broker monopoly and single-point-of-failure by allowing multiple brokers to coexist, thus enabling better brokering service for both clients and compute nodes. Work flow. Hereafter, we denote by P a client, by C a compute node, and by B a broker. To achieve desired properties (discussed in Section 3.2), Kosto requires Program to be instrumented into a program ProgKT that incorporates dynamic runtime checks over the execution of Program. P and C can post their requests and available resource offers, respectively, to a broker B of their choice, perhaps based on the broker's reputation or quality of service. B then evaluates among all requests and offers it has receives a suitable assignments of clients' requests to available compute nodes. Alternatively, the clients and the compute nodes can directly discover and connect to each other. In such an approach, the clients serve as their own broker, rendering the clients heavyweight. Once P and C are matched, P commits a payment v to an escrow on the Ethereum blockchain, and sends pkg = ⟨ProgKT, Enc(k P , Input), AuxData⟩ to C, wherein Enc() is a symantically secure symmetrickey encryption scheme [34], and AuxData contains auxiliary data that is needed for the execution (e.g., the proof that P has committed a payment v to the escrow). C then instantiates a ProgKT enclave, and attests that the enclave has been instantiated correctly. Upon successful attestation, a secret key k P is provisioned to the ProgKT 3 The Kostopayment mechanism can also be settled using other currencies that feature similar properties of the Ethereum blockchain. The key k C P is computed using a secret chosen by C and P's secret session key k P . Communication between P and C can be routed via B. The payment escrow (depicted in greenly shaded ellippse) is secured by the blockchain.
enclave, allowing it to process and compute on Input. Finally, the result of the computation, namely Output is sent to P. We note that Output is encrypted in such a way that its decryption by P ensures full payment of v to C. Figure 1 depicts a workflow and interactions between the three parties in Kosto.

System Goals
This section specifies primary desired properties that Kosto aims to achieve, with respect to security, scalability, and usability. These properties motivate and justify Kosto's design choices.
Data confidentiality: Kosto ensures that Input, and secret states of Program from an honest client remain encrypted outside the enclave memory, and thus are not known to any other party, including the compute node. The key to decrypt them resides only inside the enclave. We remark that Kosto does not attempt to eliminate Program's side-channel leakage. However, it is compatible with defense against these leakages [25,38,53].
Correct and attested execution: Kosto ensures that the output obtained by the client correctly reflects the faithful execution of Program on Input.
Fair exchange: Kosto assures that the work a compute node exhausts in executing the outsourced task is accurately metered and remunerated in fine granularity. At the same time, Kosto ensures that a compute node gets the full reward for the outsourced computation if and only if a client gets a correct result of such computation.
Limited interaction between client and compute node: Kosto unburdens clients from constantly maintaining a connection with their assigned compute nodes prior to and during execution of the outsourced computations.

Threat Model and Assumptions
We assume that an adversary is computationally bounded, and that cryptographic primitives employed in Kosto are secure. We further assume that trusted processors provisioniong the TEE, in particular Intel SGX processor, is implemented correctly and its protection mechanisms are not compromised. Although we do not consider side-channel attacks against the hardware [60], Kosto is fully compatible with defenses against these attacks [25,38].
We do not consider denial of service attack wherein an adversary denies service to honest clients, or blocks honest compute nodes from the system. As such, Kosto requires some compute nodes to behave correctly so as to guarantee the system's availability. We study a strong adversary that are capable of corrupting any number of clients and a majority (but not all) of the compute nodes.
An adversary compromising a compute node can control its operating system, schedule its processes, reorder and tamper with its network messages. However, it cannot tamper with the enclaves' execution, nor observe theirs internal state. Compromised components can deviate arbitrarily from the prescribed protocol.
Clients are mutually distrustful; i.e., they do not trust any other client. We assume that when a client delegates computation of the program Program, she trusts its code, and it is free of software bug. To enable fair exchange between clients and compute nodes, Kosto necessitates instrumenting Program into ProgKT that incorporates dynamic runtime checks over the execution of Program. We assume that all parties can verify such instrumentation which is simple enough to lend itself to formal verification and vetting.
As mentioned earlier, the clients can serve as their own broker, handling compute node discovery, and performing their own request-resource matching. As such, there will always be honest, self-serving brokers in the system. In another word, Kosto does not suffer from broker's single-point-of-failure problem.

Design Roadmap
This section introduces SimpleMarket which serves as an elementary solution of a marketplace for outsourced computations. Subsequently, we analyze SimpleMarket's shortcomings, based on which we outline design choices for Kosto.
SimpleMarket. We assume that there exists a registry to which clients can post requests and compute nodes advertise their resources. The client P and compute node C actively scan for their counterpart. Once they find a match, P and C update the status of their request and offer to being served and occupied, respectively.
Let v be the remuneration that P pays to C in exchange for executing Program on Input and delivering the result Output. P sets up an escrow on the Ethereum blockchain with a deposit v, intended recipient C, a time-out T , and a hash-lock h. This escrow holds the deposit v until being invoked with a settling transaction tx containing data such that H (data) = h, wherein H (·) is a secure hash function [34]. If tx arrives before the time-out T , the escrow sends v to C. Alternatively, if tx arrives after T has expired, v is refunded to P.
SimpleMarket provides a compiler that allows P to transform Program into a wrapper program Prog S M . In addition to Input, Prog S M also consumes h and data. It checks if data can indeed settle the escrow (i.e., H (data) = h) before executing Program on Input to obtain Output. If data cannot settle the escrow, Prog S M aborts the execution. We assume that P can formally verify the correctness of the compilation.
After setting up the escrow, P sends pkg = ⟨Prog S M , Enc(k P , Input), AuxData⟩ to C, wherein Enc() is a symantically secure symmetric-key encryption scheme [34], and AuxData contains Enc(k P , data) along with h. C then instantiates a Prog S M enclave. Next, P and the enclave engage in a remote attestation procedure [17] which convinces P that the code loaded within the enclave is indeed Prog S M . Furthermore, the remote attestation allows P to establish a secure authenticated channel with the enclave, via which they communicate the key k P . C supplies the enclave with Enc(k P , Input) and AuxData. The enclave checks the validity of data before executing Program on Input. Upon the completion of the computation, the Prog S M returns to C the encrypted output Enc(k P , Output) and data. C sends the encrypted output to P, and claims the reward v using data.
SimpleMarket's shortcomings. SimpleMarket protects the integrity of the outsourced computation, the confidentiality of the client's data, and guarantees remuneration for the compute nodes once they finish the outsourced task. Nonetheless, SimpleMarket still observes various shortcomings.
First, SimpleMarket rewards C based on task completion, which exposes the payment to various fairness issues. On the one hand, micro tasks yielding very small remunerations suffer from overhead incurred by the transaction fee. On the other hand, if C inadvertently aborts the computation midway due to its unexpectedly large resource consumption, it is not remunerated for the work it has completed prior to the abortion. Even worse, C could deny P of the computation result by dropping it after obtaining data, claiming the reward without delivering the encrypted output to P.
Second, SimpleMarket requires P to remain online until its request is accepted by a compute node C to carry out a remote attestation procedure and provision the key k P to the Prog S M enclave. The procedure requires P to contact IAS for verifying the attestation it obtains from C. This is clearly inconvenient for P, especially when the request demands uncommon resources or the IAS service is temporarily unavailable.
Finally, SimpleMarket assumes P and C could efficiently discover their counterparts. This assumption, however, may not hold true in practice, causing the system to be under-utilised when requests are not served despite there are available compute nodes.

KOSTO DESIGN
This section introduces Kosto's design to overcome SimpleMarket's shortcomings. In particular, Kosto enables fair exchange between P and C via a trusted work metering mechanism coupled with a scalable protocol for micro payments. Further, it unburdens P from remaining online and engaging in a remote attestation with C. Finally, Kosto entrusts B to match clients' requests with available compute nodes, maximizing the system's resource utilization.

Fair Exchange
Unlike SimpleMarket rewarding C based on task completion, Kosto splits the reward v of the outsourced computation into two portions, namely v c = αv and v d = (1 − α)v, where α is a parameter set by the client P, and agreed upon by C. The first portion (i.e., v c ) remunerates C for its work on a fine-grained basis, while the second portion (i.e., v d ) rewards the delivery of the result.
More specifically, C is entitled to v c upon the completion of the outsourced computation. In case C inadvertently aborts the computation midway, it is still remunerated with a fraction of v c according to its progress prior to the suspension. The remaining portion of v, namely v d , is only payable to C when the computation output is delivered to P. This discourages C from denying P of the result as it may in SimpleMarket. Additional mechanism that disincentivises result withholding (e.g., requiring C to make a security deposit which is forfeited should they repeatedly abort the computation [18,36]) can also be incorporated into Kosto.

TEE-based metering.
To enable a fair exchange described above, Kosto has to meter the compute node's work in a fine-grained and tamper-proof fashion. We follow REM [61] in implementing a reliable metering logic inside the enclave. More specifically, Kosto requires the client's program Program to be instrumented into a wrapper program ProgKT. The wrapper program reserves the logic of the original program (i.e., it executes Program's logic on Input), while keeping a counter of the number of instructions that has been executed. This is then used as a measurement of the compute node's effort.
ProgKT maintains the instruction counter in a reserved register which is inaccessiable to any other process. To prevent a malicious Program from manipulating the instruction counter, Kosto does not support Program that is multi-threaded or contains writeable code pages [5,61]. When the ProgKT enclave halts or exits, it returns a "proof of work" (i.e., the number of instruction executed) based on which Kosto settles the payment of v c (or a fraction of it). We remark that the restriction of single-threaded Program is not necessary a severe limitation, for threading in SGX enclave is much different compared to that of legacy software [3]. In particular, one cannot create or destroy an SGX thread on the fly, and an SGX thread is mapped directly to a logical processor. Consequently, a typical SGX-compliant program (i.e., a program that inherently supports SGX-enclave execution) is often single-threaded.
On the choice of instruction counting. One may argue that instructions are not the most accurate metric for CPU effort. Alternative metrics include CPU time and CPU cycles. Nevertheless, these metrics are subject to manipulation by the malicious OS. Even if they were not manipulated, they are incremented even when an enclave is swapped out [61]. Consequently, we believe that instruction counting is the most appropriate method for securely measuring the compute node's effort using available tools in SGX.

Micro Payments with Off-Chain Payment Channel.
One naive approach to settle the proof of work is for C to send it to P, who then responds with a transaction paying a corresponding amount of reward to C. This approach, however, does not ensure fairness in case P neglects her outsourced computation. Another approach is to have P commit a number of equally-valued micro transactions, each of which contains a fraction of v c , to a payment escrow on the blockchain, and to structure the proof such that it can be used to autonomously claim a subset or all of those micro transactions. Nonetheless, settling a large number of micro transactions on the blockchain incurs high overhead.
Kosto sidesteps this challenge by leveraging payment channel [12], allowing two parties to transact a large number of micro payments without incurring high transaction fee or overloading the blockchain with excessive number of transactions. It is assumed that a payer and a payee maintain a payment channel (discussed in section 2.2), and each micro payment is represented by a payment Enc(k C P , Output) rand P The key k C P is computed from rand C and the secret key k P .
promise to be communicated off-chain (i.e., off the blockchain) between the payer and the payee. To settle the payments, the payee posted the latest payment promise it has received, claiming the sum of all promises and thereby closing the channel. However, establishing a new channel for each pair of client and compute node is inefficient. Kosto, instead, makes use of multi-hop channels 4 to better utilize the channel capacity, requiring fewer channels to be established.
To this end, Kosto assumes that each client P maintains a payment channel with the broker B that, in turn, maintains a channel with each compute node C. The payment from P to C does not require the two parties to establish a channel. Instead, it could be securely routed via B, in a sense that if C collects a payment from B, it is guaranteed that B could also collect a corresponding payment from P 5 . We assume that each payment channel has sufficiently large capacity (i.e., the on-chain deposit that was set up at the beginning of the channel) to accommodate the payment of various outsourced computations during its lifetime. Figure 2 summarizes the fair exchange of the reward v and the outsourced computation of ProgKT. The payment of v is split over n + 1 micro payments, n of which summing up to v c , while the last one is worth v d . The protocol does not require any communication between P and C prior to or during the computation, nor a direct payment channel between the two parties. It, however, requires an off-chain communication between P and C in the final step to decrypt the output.
Payment of v c . Without loss of generality, let us assume that the payment of v c is divided into n equally-valued payment promises, which are routed via B. That is, P generates n payment promises to B, and B generates the corresponding n payments promises to C with the same value and claiming condition.
To generate the n payment promises ⟨m B 1 , m B 2 , . . . m B n ⟩ to B, P first picks n random strings ⟨s 1 , s 2 , . . . s n ⟩, and computes their hashes ⟨h 1 , h 2 , . . . h n ⟩ (i.e., h i = H (s i )). A digest h i is used to lock a promise m B i , such that B can only use m B i to close the channel if it is aware of s i such that H (s i ) = h i . The payment promise m B i is worth [debt P + (i × v c )/n] wherein debt P is the accumulated amount of unsettled payment for P's previous requests. Finally, P encrypts the random strings ⟨s 1 , s 2 , . . . s n ⟩ with k P , and attaches them as well as the payment promises to AuxData.
Similarly, B generates the corresponding promises ⟨m C 1 , m C 2 , . . . m C n ⟩ to C. Each promise m C i is locked by h i (i.e., the same hash-lock as m B i ), and worth [cred C + (i × v c )/n] wherein cred C is the accumulated unsettled credit that C is entitled to claim for its previous services. B includes these promises into the AuxData before forwarding pkg to C.
Payment of v d upon output delivery. To ensure that the remaining portion of v, namely v d , can only be collected upon the delivery of the output to P, ProgKT encrypts the output using a key k C P derived from k P and a secret rand C chosen and committed to by C. At the same time, the full payment of v is encumbered until the disclosure of rand C .
As shown in Figure 2, besides the n payment promises above, P generates another payment promise m B d to B that is worth [debt P +v] and is hash-locked by two digests h B and h P . Similarly, B also generate one more payment promise m C d to C that is worth [cred C + v], and hash-locked by h P and h C . The three hash-locks h P , h B and h C can be settled by three independent settling-data rand P , rand B and rand C chosen independently at random by the three parties P, B and C, respectively.
Dynamic Runtime Checks. The fair exchange requires the wrapper enclave ProgKT to perform some dynamic checks at runtime prior to executing Program's logic. More specifically, besides Input and AuxData, ProgKT also consumes the hash-lock h C and rand C . It first verifies the validity of the settling-data ⟨s 1 , s 2 , . . . s n ⟩ (i.e., h i = H (s i )∀⟨h i , s i ⟩ ∈ AuxData). Next, it checks if h C = H (rand C ). Only when the verification passes does it execute Program on Input, obtaining Output. It then encrypts Output with k C P = k P ⊕ rand C , producing an encrypted output Enc(k C P , Output). Finally, the enclave returns the appropriate settling-data s i based on the instruction counter and the encrypted output (if it successfully completes the computation) to C.
Payment settlement. The settling-data s i renders the promise m C i claimable, enabling C to collect (a portion of) v c according to its work. To obtain the settling-data necessary to claim m C d (i.e., the full reward v), C has to send the encrypted output to P, who then responds with rand P . If C chooses to settle the payment thereby closes the channel between C and B, it has to reveal both rand P and rand C . This allows P to compute k C P and obtain Output, and B to claim m B d . Alternatively, should C wish to maintain the channel, it has to back propagate the settling-data to B and P so that they PseudoCode 1 Attestation Manager Enclave procedure ReceiveKeyFromP(k P ) keyID ← Seal(k P ); // encrypts k P with the enclave's Seal Key for persistent storage to disk k P ← UnSeal(keyID); pk KH ← GetPK(Cert KH ); channelID ← EstablishSecureChannel(C, pk KH ); // inter-platform channel between B's AM and C's KH Send(channelID, k P ); can update cred C and debt P accordingly 6 . In a situation where P's response is invalid (i.e., its digest produced by the standard hash function H (·) does not match h P ), C can check this invalidity locally and use it as a evidence to accuse P of conducting mischief. In such situation, fairness property is still guaranteed; i.e., C does not claim v d from B, who in turn does not claim v d from P and P cannot decrypt Enc(k C P , Output) to obtain Output.

Delegated Attestation
Unlike SimpleMarket, Kosto relieves P from conducting a remote attestation with C at the beginning of every request execution by implementing a delegated attestation scheme. The scheme requires each broker B to run an attestation manager enclave AM (detailed in Algorithm 1), and each compute node C to run a key handler enclave KH (detailed in Algorithm 2). The execution of AM and KH are protected by Intel SGX. Without loss of generality, the delegated attestation builds a chain of trust that comprises three links. The first and second links are established via remote attestations between P as a validator and AM as an attesting enclave, and AM as a validator and KH as an attesting enclave. The final link entails ProgKT enclave to prove its correctness to KH via local attestation. Chaining all three links together, P gains confidence that the ProgKT enclave has been properly instantiated on the compute node C using the correct code, without contacting C or the IAS.
Each attestation manager enclave has its own (unique) public and private key pair ( pk AM , sk AM ) that are generated uniformly at random during the enclave instantiation. Upon successfully instantiating AM, B requests the trusted processor for its remote attestation π AM = ⟨M AM , pk AM ⟩ σ T E E , where M AM is the enclave's measurement, and σ T EE is a group signature signed by the processor's private key. The certificate π AM attests for the correctness of the AM enclave and its public key. Nonetheless, the only party that can verify π AM is the IAS acting as group manager [17]. Kosto converts π AM into a publicly verifiable certificate by having B obtain and store the IAS response Cert AM = ⟨π AM , validity⟩ σ I AS where σ I AS is the IAS's k P ← UnSeal(keyID); channelID ← EstablishLocalSecureChannel(ψ ProgKT ); // intra-platform channel, for both KH and ProgKT are instantiated on C Send(channelID, k P ); publicly verifiable signature on π AM and the validity flag. By examining Cert AM , the enclave code and its measurement M AM , any party can verify the correctness of and establish a secure connection to the AM enclave.
Likewise, every compute node C runs a key handler enclave KH . C obtains (from the IAS) and stores a publicly verifiable certificate Cert KH = ⟨π K H , valid⟩ σ I AS , where π K H is KH's remote attestation containing its measurement M K H and its unique public key pk KH . By examining Cert KH , any party can be assured of the correctness of KH and communicate securely with it.
Delegated Attestation Protocol. Figure 3 depicts the workflow of Kosto's delegated attestation. After instrumenting Program into ProgKT and verifying the correctness of the instrumentation, P initiates the delegated attestation by obtaining Cert AM from B and verifies its validity. It then establishes a secure and authenticated channel with AM using pk AM . P then sends pkg = ⟨ProgKT 7 , Enc(k P , Input), AuxData⟩ to B, and k P to AM via the secure channel. Once B finds a compute node C that is willing to match P's request, AM obtains Cert KH from C, verifies its validity, and establishes 7 Should P want to hide ProgKT from B, she could also encrypt it with k P , and sends Enc(k P , ProgKT) instead. a secure and authenticated connection with C's KH to communicate k P . B then sends pkg to C. The compute node instantiates an enclave to execute ProgKT, and performs a local attestation with KH to prove its correctness. Upon successfully attestation, KH sends the key k P to the ProgKT enclave. Once the ProgKT enclave completes the computation, it returns the encrypted output, which is then sent to P (perhaps being routed through B).
This mechanism only invokes IAS to obtain attestation certificates for AM and KH, instead of constantly involving IAS in every task execution as SimpleMarket does. Further, it allows P to post a request (along with the payment) and then go offline until the time she wishes to collect the output, as opposed to remaining online till her request is picked up by some computation node.

Task Assignment for Maximum Resource Utilization
Kosto designates to B the task of node discovery, load balancing and request-resource matching. More specifically, B collects requests from clients and advertise of available resource capacities from compute nodes, and to evaluate the optimal assignments of requests to compute nodes that maximises the resource utilization of compute nodes or number of requests that are served at every time instance. We assume that each request is associated with a resource specification requirement, and each resource offer indicates the compute node's available computational capacity. We further assume that there is no need for redundant execution (i.e., each request is assigned to one compute node), and a compute node serves only one request at a time. Let R = ⟨r 1 , r 2 , . . . , r p ⟩ be the set of pending requests, and O = ⟨C 1 , C 2 , . . . , C q ⟩ be the set of available compute nodes. The request assignment of R to O is the set A comprising tuples of form ⟨r i , C j ⟩, wherein a compute node C j has sufficient computational capacity to serve a request r i . The optimization goal is to maximize the number of such tuples (i.e., |A|).
The request assignment problem is reducible to a maximum bipartite matching problem [59]. A bipartite graph consists of vertices that can be divided into two independent sets such that there is no edge connecting vertices of same set. A maximum matching in a bipartite graph is a largest subset of the graph's edges such that no pair of edges in such a subset share an endpoint.
To reduce Kosto's request assignment problem to the maximum bipartite matching problem, we create a graph G = (V , E) wherein V is the set of vertices, and E is the set of edges. V contains two independent subsets, V 1 and V 2 , wherein |V 1 | = |R| and |V 2 | = |O |. We represent each request r i by a vertex v i ∈ V 1 , and a compute node C j by a vertex v |R |+j ∈ V 2 . We add an edge e i j that connects v i and v |R |+j if the compute node C j has sufficient computational capacity to satisfy the resource specification requirement of request r i . Since every edge in the graph G connects a vertex in V 1 to a vertex in V 2 , G is a bipartite graph. The maximum matching in G indicates the maximum request assignment of R to O, in which an edge e uv in the maximum matching suggests the request r u to be assigned to the compute node C v .
We expect that a typical request in Kosto can be served by a common compute node. This assumption renders the bipartite graph that represents all potential assignments of requests to compute nodes dense. The most efficient algorithm to find a maximum matching in a dense bipartite graph is the Mucha-Sankowski algorithm [43]. This algorithm is randomized, and operates based on the fast matrix multiplcation algorithm. As such, it attains a running time complexity of O(|V | ω ), where ω is the exponent of the best known matrix multiplication algorithm (the best known algorithm to date is Le Gall algorithm [37], with ω < 2.373).

SECURITY ANALYSIS 5.1 Fair exchange
TEE-based metering. To enable fair exchange between client's payment and compute node's computation, Kosto necessitates dynamic runtime checks incorporated within the enclave that houses the outsourced computation. We implement this by providing a compiler that instruments any SGX-compliant program Program into a wrapper program ProgKT. We believe that these additional steps and the overall instrumentation are simple enough to lend themselves to formal verification and vetting by Program writer, or by the client.
As we mentioned earlier, the original Program should not contain writable code pages, for they would allow the program to rewrite itself at runtime and thus evade the instrumentation. This could be enforced by requiring the code page to have either write or executable permission exclusively (i.e., it cannot have both permission at the same time). This practice has also been recommended by Intel to the enclave writers [5].
In addition, Kosto requires Program to be single-threaded. While the instruction counter is maintained in a reserved register which is inaccessible to any other processes (Section 4.1.1), it remains accessible by different threads of Program, should it be multi-threaded. Thus, a malicious program that has multiple threads could manipulate the instruction counter value by carefully crafting the interactions of its threads.
Payment of v c . Kosto builds on payment channel [12] to enable efficient micro payments and relies on the security of the Ethereum blockchain to ensure payment escrow is faithfully executed. To optimize for efficiency and avoid overloading the blockchain, Kosto securely routes payment from P to C via the broker B. A careful design of hash-lock payment promises, wherein promise from P to B, and that of B to C could be settled using the same settling-data, guarantees that B can always claim from P which he pays to C on behalf of P.
Ensuring Output Delivery. At the end of the computation, ProgKT enclave encrypts the Output using key k C P = k P ⊕ rand C . Since m C d is partially locked by rand C , the decryption of the output and the settling of m C d are bound together. Should C deny P of the output, it would have to forfeit v d . While this act weakens the availability of the system, it does not violate fairness guarantee.

Delegated Attestation
Kosto's delegated attestation relies on AM and KH enclaves to attest correct instantiation of ProgKT enclave. Therefore, their correct instantiations are of utter importance. Fortunately, these enclave are fixed (as opposed to the ProgKT enclave that houses client-defined program), and thus are easy to vet and verify.
Kosto's delegated attestation requires minimal involvement of P (i.e., examine the publicly verifiable certificates Cert AM = ⟨π AM , validity⟩ σ I AS ). By checking that π AM indeed contains the expected measurement M AM , that its validity flag indicates valid, and that the certificate has been properly certified (using Intel's published public key [11]), P can ascertain the correct instantiation of AM. Moreover, using the public key pk AM included in π AM , P can establish a secure and authenticated channel to AM via which the secret key k P is communicated. Likewise, AM can verify the correct instantiation of KH and securely communicate k P to the latter in the exact same manner. The security of the local attestation and communication between KH and ProgKT enclave follows directly from Intel SGX's specifications [17]. Therefore, provided that cryptographic primitives in use are secure, and SGX hardware protection mechanisms are not subverted, Kosto's delegated attestation is secure.

Attested Execution and Data Confidentiality
Kosto's relies on Intel SGX [41] to offer attested execution and data confidentiality to outsourced computations. In particular, SGX enables isolated execution [54] ensuring that code loaded and running inside the enclaves cannot be tampered with by any other processes including the operating system or hypervisor. This, in combination with attestation capabilities, allows Kosto to offer attested execution in which the computation correctness is guaranteed. Moreover, data (i.e., input, output) and secret states of the enclave execution always remain encrypted outside of the enclave memory, thus their confidentiality are guaranteed. Furthermore, SGX memory encryption engine is capable of protecting data integrity and preventing memory replay attacks [32,40]. Nonetheless, SGX's attested execution does not inherently offer protections against side-channel leakages [27,52,60]. The access pattern incurred by data (or code page) moving between the enclave and the non-enclave environment (e.g., page fault) could leak sensitive information about the code or data being processed within the enclave. Such side-channel leakage could be mitigated by ensuring that the enclave execution is data oblivious; i.e., the access pattern no longer depends on the input data [25]. While Kosto does not explicitly eliminate side-channel leakage, it could benefit from a vast amount of research on defenses against side-channel leakages [23,25,38,52,53], which we shall incorporate into Kosto in future work.

EVALUATION
This section reports empirical evaluation of our prototype implementation of Kosto. We are interested in quantifying the overhead of enclave over non-enclave (and thus untrusted) execution (Section 6.2) and the cost of task matching (Section 6.3).

Experimental Setup
All experiments are conducted on a system that is equipped with Intel i7-6820HQ 2.70GHz CPU, 16GB RAM, 2TB hard drive, and running Ubuntu 16.04 Xenial Xerus. We evaluate the overhead of Kosto's enclave execution using a number of computational tasks including five benchmarks (i.e., mcf, deepsjeng, leela, exchang2, and xz) selected from SPEC CPU2017 [14], and two standard cryptographic operations (i.e., SHA256 and AES Encryption). The enclave trusted codebases are implemented using Intel SGX SDK [4]. To quantify the cost of task matching in Kosto, we measure the runtime of the Mucha-Sankowski algorithm [43] that we implemented in C. All experiments are repeated over 10 runs, and the average results are reported.

Cost of Enclave Execution
Overhead in Execution Time. We evaluate the five SPEC CPU2017 benchmarks in three different execution modes, namely baseline, SGX-compliant and Kosto-compliant. The baseline mode compiles the benchmarks as-is and runs them in untrusted execution environment. SGX-compliant mode requires porting the benchmarks to support SGX-enclave execution. This entails replacing standard system calls and libraries in the original code with SGX-compliant ones supported in the SGX SDK [4]. Finally, the Kosto-compliant mode further instruments SGX-compliant code with dynamic runtime checks and TEE-based metering discussed in previous section. Figure 4 compares the running time of the five benchmarks in three modes, with the running time of each benchmark normalized against its own baseline. We observe that the SGX-compliant mode incurs from 1.5× to 3.7× overhead over the baseline. This overhead is mostly due to enclave's control switching. The instrumentations introduced in Kosto-compliant mode incur an extra 8% ∼ 14% overhead relative to the SGX-compliant mode.
We remark that our porting of the five benchmarks to SGX might not be optimized. Thus, the results reported in Figure 4 are likely an over-estimation of the real overhead that enclave execution incurs over unstrusted non-enclave execution. Various techniques have been proposed for minimizing the overhead of enclave execution, typically by reducing the control switching between the enclave code and the untrusted application that services OS-provided functions [46,55,58]. We leave the incorporation of such optimization into Kosto for future work.  Overhead in Throughput. Next, we measure the overhead in throughput incurred by enclave execution on computationintensive works. This set of experiments measure performances of SHA256 and AES-GCM encryption operations under OpenSSL [9] and Intel SGXSSL [7] implementations against exponentially increasing input size (ranging from 256B to 4MB). OpenSSL implementation runs in an untrusted non-enclave memory, whereas SGXSSL ports OpenSSL to support SGX enclave execution. Figure 5a shows a significant gap between the throughput of SGXSSL and OpenSSL implementations of SHA256 when a message size is small (e.g., OpenSSL's throughput is upto 5× for 1KB message). Nonetheless, such a gap reduces as the message size increases (e.g., as small as 1.5× for 4MB message). A similar trend is observed in throughput of AES-GCM encryption (the decryption throughput is similar), with the throughput overhead incurred by enclave execution reduces from 6.3× for 1KB message to 3% for 4MB message. We attribute this throughput gap to the I/O cost and context switching that enclave execution incurs. Fortunately, this overhead is amortized as the input size increases.

Cost of Task Matching
Finally, we evaluate the performance of Kosto task assignment by measuring the runtime of Mucha-Sankowski algorithm. The algorithm runs in O(|V | 2.38 ), where |V | is the total number of vertices in the graph. Table 1 reports running time of the Mucha-Sankowski algorithm on dense bipartite graphs whose densities (i.e., D = 2|V | |V |(|V |−1) ) range from 0.8 to 0.9. As expected, the running time grows quadratically with respect to the input size. This limits the task assignment algorithm to offer real-time performance only when the number of requests and compute nodes are small (e.g., 4000). To offer realtime performance at scale, Kosto expects a number of brokers offer competing services. Alternatively, a single broker can trade the optimality of the task assignment for lower cost of task matching by splitting requests and compute nodes into multiple batches, and evaluating the batches in parallel.

RELATED WORKS
Decentralised outsourced computation. Golem [2] also explores a marketplace for outsourced computation. Unlike Kosto, it does not feature the attested execution environment. Consequently, Golem needs to redundantly execute the same task on multiple compute nodes in order to verify the execution correctness.
Concurrent to our work, AirTNT [16] proposes the use of enclave execution for outsourced computations, and devises a protocol that allows fair exchange between the client and the compute nodes. Such protocol necessitates a separate payment channel for every pair of client and compute node, and requires constant communication between the two parties over the course of the outsourced computation (i.e., highly interactive). Kosto, in contrast, alleviates the client and the compute nodes from these inconveniences.
CryptoCurrency and Off-Chain Payment Channel. Cryptocurrencies allow two willing parties to transact directly via an open and decentralized blockchain [44]. Beyond a means of transacting, blockchain architectures have been developed for various purposes, such as enabling a Turing-complete smart contract platform [20] or enhancing transaction [8,48] privacy. We refer readers to [19] for a comprehensive overview of cryptocurrencies.
Current prominent cryptocurrencies can only support limited transaction throughputs. As a result, various off-chain payment solutions have been presented. Lighting network [47] and Raiden network [12] are earlier off-chain payment solutions proposed for Bitcoin and Ethereum, respectively. Sprites [42] and Revive [35] optimize the costs of indirect off-chain payments, while Bolt [31] allows privacy-preserving off-chain payment channels. Kosto design has thus far only tapped on a basic feature of payment channels, and can certainly benefit from their further developments.
Reliable Resource Accounting. Early approaches to resource accounting in the context of outsourced computations rely on nested virtualization and TPMs, or place a trusted resource observer underneath the service provider's software [22,51]. Alternatively, REM [61] instruments the client's program with dynamic runtime checks that maintain an instruction counter to self account its computational effort. The correctness and integrity of these runtime checks are enforced by the trusted hardware. Kosto adopts REM's approach in metering the compute nodes' work.
SGX-based systems. Trusted hardware, in particular Intel SGX processors, have been used to enhance security in various application domains, including data analytics [25,27,49], machine learning [45] and outsourced storage [23,26]. In addition, SGX has also been utilized to scale the blockchain [10,24]. To our knowledge, Kosto is the first solution to provision a full-fledged fair marketplace for secure outsourced computations using Intel SGX.