IEEEpubidpullup9Permission to freely reproduce all or part
of this paper for noncommercial purposes is granted provided that
copies bear this notice and the full citation on the first
page. Reproduction for commercial purposes is strictly prohibited
without the prior written consent of the Internet Society, the
first-named author (for reproduction of an entire paper only), and
the author's employer if the paper was prepared within the scope
of employment.

is a decentralized infrastructure, known as a distributed ledger, that supports user defined smart contracts and executes user-supplied transactions on their objects. The correct execution of smart contract transactions is verifiable by all. The system is scalable, by sharding state and the execution of transactions, and using , a distributed commit protocol, to guarantee consistency. is secure against subsets of nodes trying to compromise its integrity or availability properties through Byzantine Fault Tolerance (BFT), and extremely high-auditability, non-repudiation and `blockchain' techniques. Even when BFT fails, auditing mechanisms are in place to trace malicious participants. We present the design, rationale, and details of ; we argue through evaluating an implementation of the system about its scaling and other features; we illustrate a number of privacy-friendly smart contracts for smart metering, polling and banking and measure their performance.

§ INTRODUCTION

is a distributed ledger platform for high-integrity and transparent processing of transactions within a decentralized system. Unlike application specific distributed ledgers, such as Bitcoin [28] for a currency, or certificate transparency [21] for certificate verification, offers extensibility though smart contracts, like Ethereum [39]. However, users expose to enough information about contracts and transaction semantics, to provide higher scalability through sharding across infrastructure nodes: our modest testbed of 60 cores achieves 350 transactions per second, as compared with a peak rate of less than 7 transactions per second for over 6K full nodes. Etherium currently processes 4 transactions per second, out of theoretical maximum of 25. Furthermore, our platform is agnostic as to the smart contract language, or identity infrastructure, and supports privacy features through modern zero-knowledge techniques [1, 11].

Unlike other scalable but `permissioned' smart contract platforms, such as  [6] or  [27], aims to be an `open' system: it allows anyone to author a smart contract, anyone to provide infrastructure on which smart contract code and state runs, and any user to access calls to smart contracts. Further, it provides ecosystem features, by allowing composition of smart contracts from different authors. We integrate a value system, named , as a system smart contract to allow for accounting between those parties.

However, the security model of , is different from traditional unpermissioned blockchains, that rely on proof-of-work and global replication of state, such as Ethereum. In smart contract authors designate the parts of the infrastructure that are trusted to maintain the integrity of their contract—and only depend on their correctness, as well as the correctness of contract sub-calls. This provides fine grained control of which part of the infrastructure need to be trusted on a per-contract basis, and also allows for horizontal scalability.

This paper makes the following contributions:

* It presents , a system that can scale arbitrarily as the number of nodes increase, tolerates byzantine failures, and can be fully and publicly audited.

* It presents a novel distributed atomic commit protocol, called , for sharding generic smart contract transactions across multiple byzantine nodes, and correctly coordinating those nodes to ensure safety, liveness and security properties.

* It introduces a distinction between parts of the smart contract that execute a computation, and those that check the computation and discusses how that distinction is key to supporting privacy-friendly smart-contracts.

* It provides a full implementation and evaluates the performance of the byzantine distributed commit protocol, , on a real distributed set of nodes and under varying transaction loads.

* It presents a number of key system and application smart contracts and evaluates their performance. The contracts for privacy-friendly smart-metering and privacy-friendly polls illustrate and validate support for high-integrity and high-privacy applications.

Outline: <Ref> presents an overview of ; <Ref> presents the client-facing application interface; <Ref> presents the design of internal data structures guaranteeing integrity, the distributed architecture, the byzantine commit protocols, and smart contract definition and composition. <Ref> argues the correctness and security; specific smart contracts and their evaluations are presented in <Ref>; <Ref> presents an evaluation of the core protocols and smart contract performance; <Ref> presents limitation and <Ref> a comparison with related work; and <Ref> concludes.

§ SYSTEM OVERVIEW

allows applications developers to implement distributed ledger applications by defining and calling procedures of smart contracts operating on controlled objects, and abstracts the details of how the ledger works and scales. In this section, we first describe data model of , followed by an overview of the system design, its threat model and security properties.

§.§ Data Model: Objects, Contracts, Transactions.

applies aggressively the end-to-end principle [35] in relying on untrusted end-user applications to build transactions to be checked and executed. We describe below key concepts within the data model, that developers need to grasp to use the system.

Objects are atoms that hold state in the system. We usually refer to an object through the letter $o$, and a set of objects as $\csobject \in O$. All objects have a cryptographically derived unique identifier used to unambiguously refer to the object, that we denote $\id(\csobject)$. Objects also have a type, denoted as $\type(\csobject)$, that determines the unique identifier of the smart contract that defines them, and a type name. In object state is immutable. Objects may be in two meta-states, either active or inactive. Active objects are available to be operated on through smart contract procedures, while inactive ones are retained for the purposes of audit only.

Contracts are special types of objects, that contain executable information on how other objects of types defined by the contract may be manipulated. They define a set of initial objects that are created when the contract is first created within . A contract $\contract$ defines a namespace within which types (denoted as $\types(\contract)$) and a checker $\checker$ for procedures (denoted as $\procedures(\contract)$) are defined.

A procedure, $\csprocedure$, defines the logic by which a number of objects, that may be inputs or references, are processed by some logic and local parameters and local return values (denoted as $\lparams$ and $\lreturns$), to generate a number of object outputs. Notionally, input objects, denoted as a vector $\pinputs$, represent state that is invalidated by the procedure; references, denoted as $\preferences$ represent state that is only read; and outputs are objects, or $\poutputs$ are created by the procedure. Some of the local parameters or local returns may be secrets, and require confidentiality. We denote those as $\sparams$ and $\sreturns$ respectively.

We denote the execution of such a procedure as:

\begin{equation}\label{eq:procedure}
\contract.\csprocedure(\pinputs, \preferences, \lparams, \sparams) \rightarrow \poutputs, \lreturns, \sreturns
\end{equation}

for $\pinputs, \preferences, \poutputs \in O$ and $\csprocedure \in \procedures(\contract)$. We restrict the type of all objects (inputs $\pinputs$, outputs $\poutputs$ and references $\preferences$) to have types defined by the same contract $\contract$ as the procedure $\csprocedure$ (formally: $\forall \csobject \in \pinputs \cup \poutputs \cup \preferences . \type(\csobject) \in \types(\contract)$). However, public locals (both $\lparams$ and $\lreturns$) may refer to objects that are from different contracts through their identifiers. We further require a procedure that outputs an non empty set of objects $\poutputs$, to also take as parameters a non-empty set of input objects $\pinputs$. Transactions that create no outputs are allowed to just take locals and references $\preferences$.

Associated with each smart contract $\contract$, we define a checker denoted as $\checker$. Those checkers are pure functions (ie. deterministic, and have no side-effects), and return a Boolean value. A checker $\checker$ is defined by a contract, and takes as parameters a procedure $\csprocedure$, as well as inputs, outputs, references and locals.

\begin{equation}\label{eq:checker}
\contract.\checker(\csprocedure, \pinputs, \preferences, \lparams, \poutputs, \lreturns, \dependencies) \rightarrow \{\mathsf{true}, \mathsf{false}\}
\end{equation}

Note that checkers do not take any secret local parameters ($\sparams$ or $\sreturns$). A checker for a smart contract returns $\mathsf{true}$ only if there exist some secret parameters $\sparams$ or $\sreturns$, such that an execution of the contract procedure $\csprocedure$, with the parameters passed to the checker alongside $\sparams$ or $\sreturns$, is possible as defined in <Ref>.

The variable $\dependencies$ represent the context in which the procedure is called: namely information about other procedure executions. This supports composition, as we discuss in detail in the next section.

We note that procedures, unlike checkers, do not have to be pure functions, and may be randomized, keep state or have side effects. A smart contract defines explicitly the checker $\contract.\checker$, but does not have to define procedures per se. The system is oblivious to procedures, and relies merely on checkers. Yet, applications may use procedures to create valid transactions. The distinction between procedures and checkers—that do not take secrets—is key to implementing

privacy-friendly contracts.

Transactions represent the atomic application of one or more valid procedures to active input objects, and possibly some referenced objects, to create a number of new active output objects. The design of is user-centric, in that a user client executes all the computations necessary to determine the outputs of one or more procedures forming a transaction, and provides enough evidence to the system to check the validity of the execution and the new objects.

Once a transaction is accepted in the system it `consumes' the input objects, that become inactive, and brings to life all new output objects that start their life by being active. References on the other hand must be active for the transaction to succeed, and remain active once a transaction has been successfully committed.

An client packages enough information about the execution of those procedures to allow to safely serialize its execution, and atomically commit it only if all transactions are valid according to relevant smart contract checkers.

Design overview of system.

§.§ System Design, Threat Model and Security Properties

We provide an overview of the system design, illustrated in <Ref>. is comprised of a network of infrastructure nodes that manage valid objects, and ensure that only valid transactions are committed. A key design goal is to achieve scalability in terms of high transaction throughput and low latency. To this end, nodes are organized into shards that manage the state of objects, keep track of their validity, and record transactions aborted or committed. Within each shard all honest nodes ensure they consistently agree whether to accept or reject a transaction: whether an object is active or inactive at any point, and whether traces from contracts they know check. Across shards, nodes must ensure that transactions are committed if all shards are willing to commit the transaction, and rejected (or aborted) if any shards decide to abort the transaction—due to checkers returning  or objects being inactive. To satisfy these requirements, implements —a protocol that composes existing Byzantine agreement and atomic commit primitives in a novel way. Consensus on committing (or aborting) transactions takes place in parallel across different shards. For transparency and auditability, nodes in each shard periodically publish a signed hash chain of checkpoints: shards add a block (Merkle tree) of evidence including transactions processed in the current epoch, and signed promises from other nodes, to the hash chain.

supports security properties against two distinct types of adversaries, both polynomial time bounded:

* Honest Shards (HS). The first adversary may create arbitrary contracts, and input arbitrary transactions into , however they are bound to only control up to $\faulty$ faulty nodes in any shard. As a result, and to ensure the correctness and liveness properties of Byzantine consensus, each shard must have a size of at least $3\faulty + 1$ nodes.

* Dishonest Shards (DS). The second adversary has, additionally to HS, managed to gain control of one or more shards, meaning that they control over $\faulty$ nodes in those shards. Thus, its correctness or liveness may not be guaranteed.

Faulty nodes in shards may behave arbitrarily, and collude to violate any of the security, safely or liveness properties of the system. They may emit incorrect or contradictory messages, as well as not respond to any or some requests.

Given this threat model, supports the following security properties:

* Transparency. ensures that anyone in possession of the identity of a valid object may authenticate the full history of transactions and objects that led to the creation of the object. No transactions may be inserted, modified or deleted from that causal chain or tree. Objects may be used to self-authenticate its full history—this holds under both the HS and DS threat models.

* Integrity. Subject to the HS threat model, when one or more transactions are submitted only a set of valid non-conflicting transactions will be executed within the system. This includes resolving conflicts—in terms of multiple transactions using the same objects—ensuring the validity of the transactions, and also making sure that all new objects are registered as active. Ultimately, transactions are accepted, and the set of active objects changes, as if executed sequentially—however, unlike other systems such as Ethereum [39], this is merely an abstraction and high levels of concurrency are supported.

* Encapsulation. The smart contract checking system of enforces strict isolation between smart contracts and their state—thus prohibiting one smart contract from directly interfering with objects from other contracts. Under both the HS and DS threat models. However, cross-contract calls are supported but mediated by well defined interfaces providing encapsulation.

* Non-repudiation. In case conflicting or otherwise invalid transactions were to be accepted in honest shards (in the case of the DS threat model), then evidence exists to pinpoint the parties or shards in the system that allowed the inconsistency to occur. Thus, failures outside the HS threat model, are detectable; the guildy parties may be banned; and appropriate off-line recovery mechanisms could be deployed.

§ THE APPLICATION INTERFACE

$\alpha_0, \mathit{Valid}(t), \alpha'$
$\alpha', \mathit{Valid}(T'), \alpha_1$
$\alpha_0, \mathit{Valid}(T = t::T'), \alpha_1$

$\alpha_0, \mathit{Valid}(\dependencies), \alpha'$
$\alpha', \contract.\checker(\csprocedure, \pinputs, \preferences, \lparams, \poutputs, \lreturns, \dependencies), (\alpha' \setminus \pinputs) \cup \poutputs $

$\pinputs, \preferences \in \alpha' \land$
$(\poutputs \neq \emptyset) \rightarrow (\pinputs \neq \emptyset) \land$
$\forall \csobject \in \pinputs \cup \poutputs \cup \preferences . \type(\csobject) \in \types(\contract)$
$\alpha_0, \mathit{Valid}(t = [\contract, \csprocedure, \pinputs, \preferences, \poutputs, \lparams, \lreturns, \dependencies]), (\alpha' \setminus \pinputs) \cup \poutputs$

The sequencing and checking validity rules for transactions.

Smart Contract developers in register a smart contract $c$ into the distributed system managing , by defining a  checker for the contract and some initial objects. Users may then submit transactions to operate on those objects in ways allowed by the checkers.

Transactions represent the execution of one or more procedures from one or more smart contracts. It is necessary for all inputs to all procedures within the transaction to be active for a transaction to be executed and produce any output objects.

Transactions are atomic: either all their procedures run, and produce outputs, or none of them do. Transactions are also consistent: in case two transactions are submitted to the system using the same active object inputs, at most one of them will eventually be executed to produce outputs. Other transactions, called conflicting, will be aborted.

Representation of Transactions. A transaction within is represented by sequence of traces of the executions of the procedures that compose it, and their interdependencies. These are computed and packaged by end-user clients, and contain all the information  a checker needs to establish its correctness. A Transaction is a data structure such that:

\begin{align*}
\text{type}\ &\textit{Transaction}: \textit{Trace}\ \text{list}\\
\text{type}\ &\textit{Trace}: \text{Record}\ \{ \\
&\contract: \id(\csobject), \quad
\csprocedure: \text{string},\\
&\pinputs, \preferences, \poutputs: \id(\csobject)\ \text{list},\\
&\lparams, \lreturns: \text{arbitrary data}, \\
&\dependencies: \textit{Trace}\ \text{list} \}
\end{align*}

To generate a set of traces composing the transaction, a user executes on the client side all the smart contract procedures required on the input objects, references and local parameters, and generates the output objects and local returns for every procedure—potentially also using secret parameters and returns. Thus the actual computation behind the transactions is performed by the user, and the traces forming the transaction already contain the output objects and return parameters, and sufficient information to check their validity through smart contract checkers. This design pattern is related to traditional optimistic concurrency control.

Only valid transactions are eventually committed into the system, as specified by two validity rules sequencing and checking presented in <Ref>. Transactions are considered valid within a context of a set of active objects maintained by , denoted with $\alpha$. Valid transactions lead to a new context of active objects (eg. $\alpha'$). We denote this through the triplet ($\alpha, \textit{Valid}(T), \alpha'$), which is true if the execution of transaction $T$ is valid within the context of active objects $\alpha$ and generates a new context of active objects $\alpha'$. The two rules are as follows:

* (Sequence rule). A `Trace list' (within a `Transaction' or list of dependencies) is valid if each of the traces are valid in sequence (see <Ref> rule for sequencing). Further, the active objects set is updated in sequence before considering the validity of each trace.

* (Check rule).  A particular `Trace' is valid, if the sequence of its dependencies are valid, and then in the resulting active object context, the checker for it returns $\mathsf{true}$. A further three side conditions must hold: (1) inputs and references must be active; (2) if the trace produces any output objects it must also contain some input objects; and (3) all objects passed to the checker must be of types defined by the smart contract of this checker (see <Ref> rule for checking).

The ordering of active object sets in the validation rules result in a depth-first validation of all traces, which represents a depth-first execution and data flow dependency between them. It is also noteworthy that only the active set of objects needs to be tracked to determine the validity of new transactions, which is in the order of magnitude of active objects in the system. The much longer list of inactive objects, which grows to encompass the full history of every object in the system is not needed—which we leverage to enable better when validating transactions. It also results in a smaller amount of working memory to perform incremental audits.

A valid transaction is executed in a serialized manner, and committed or aborted atomically. If it is committed, the new set of active objects replaces the previous set; if not the set of active objects does not change. Determining whether a transaction may commit involves ensuring all the input objects are active, and all are consumed as a result of the transaction executing, as well as all new objects becoming available for processing (references however remain active). ensures this through the distributed atomic commit protocol, .

Smart contract composition. A contract procedure may call a transaction of another smart contract, with specific parameters and rely upon returned values. This is achieved through passing the $\dependencies$ variable to a smart contract checker, a validated list of traces of all the sub-calls performed. The checker can ensure that the parameters and return values are as expected, and those dependencies are checked for validity by .

Composition of smart contracts is a key feature of a transparent and auditable computation platform. It allows the creation of a library of smart contracts that act as utilities for other higher-level contracts: for example, a simple contract can implement a cryptographic currency, and other contracts—for e-commerce for example—can use this currency as part of their logic. Furthermore, we compose smart contracts, in order to build some of the functionality of itself as a set of `system' smart contracts, including management of shards mapping to nodes, key management of shard nodes, and governance.

also supports the atomic batch execution of multiple procedures for efficiency, that are not dependent on each other.

Reads. Besides executing transactions, clients, need to read the state of objects, if anything, to correctly form transactions. Reads, by themselves, cannot lead to inconsistent state being accepted into the system, even if they are used as inputs or references to transactions. This is a result of the system checking the validity rules before accepting a transaction, which will reject any stale state.

Thus, any mechanism may be used to expose the state of objects to clients, including traditional relational databases, or `no-SQL' alternatives. Additionally, any indexing mechanism may be used to allow clients to retrieve objects with specific characteristics faster. Decentralized, read-only stores have been extensively studied, so we do not address the question of reads further in this work.

Privacy by design. Defining smart contract logic as checkers allows to support privacy friendly-contracts by design. In such contracts some information in objects is not in the clear, but instead either encrypted using a public key, or committed using a secure commitment scheme as [29]. The transaction only contains a valid proof that the logic or invariants of the smart contract procedure were applied correctly or hold respectively, and can take the form of a zero-knowledge proof, or a Succinct Argument of Knowledge (SNARK). Then, generalizing the approach of [25], the checker runs the verifier part of the proof or SNARK that validates the invariants of the transactions, without revealing the secrets within the objects to the verifiers.

§ THE SYSTEM DESIGN

In a network of infrastructure nodes manages valid objects, and ensure key invariants: namely that only valid transactions are committed. We discuss the data structures nodes use collectively and locally to ensure high integrity; and the distributed protocols they employ to reach consensus on the accepted transactions.

§.§ High-Integrity Data Structures

employs a number of high-integrity data structures. They enable those in possession of a valid object or its identifier
to verify all operations that lead to its creation; they are also used to support non-equivocation—preventing nodes from providing a split view of the state they hold without detection.

Hash-DAG structure. Objects and transactions naturally form a directed acyclic graph (DAG): given an initial state of active objects a number of transactions render their inputs invalid, and create a new set of outputs as active objects. These may be represented as a directed graph between objects, transactions and new objects and so on. Each object may only be created by a single transaction trace, thus cycles between future transactions and previous objects never occur. We prove that output object identifiers resulting from valid transactions are fresh (see <Ref>). Hence, the graph of objects inputs, transactions and objects outputs form a DAG, that may be indexed by their identifiers.

We leverage this DAG structure, and augment it to provide a high-integrity data structure. Our principal aim is to ensure that given an object, and its identifier, it is possible to unambiguously and unequivocally check all transactions and previous (now inactive) objects and references that contribute to the existence of the object. To achieve this we define as an identifier for all objects and transactions a cryptographic hash that directly or indirectly depends on the identifiers of all state that contributed to the creation of the object.

Specifically, we define a function $\id(\mathit{Trace})$ as the identifier of a trace contained in transaction $T$. The identifier of a trace is a cryptographic hash function over the name of contract and the procedure producing the trace; as well as serialization of the input object identifiers, the reference object identifiers, and all local state of the transaction (but not the secret state of the procedures); the identifiers of the trace's dependencies are also included. Thus all information contributing to defining the Trace is included in the identifier, except the output object identifiers.

We also define the $\id(\csobject)$ as the identifier of an object $\csobject$. We derive this identifier through the application of a cryptographic hash function, to the identifier of the trace that created the object $\csobject$, as well as a unique name assigned by the procedures creating the trace, to this output object. (Unique in the context of the outputs of this procedure call, not globally, such as a local counter.)

An object identifier $\id(\csobject)$ is a high-integrity handle that may be used to authenticate the full history that led to the existence of the object $\csobject$. Due to the collision resistance properties of secure cryptographic hash functions an adversary is not able to forge a past set of objects or transactions that leads to an object with the same identifier. Thus, given  $\id(\csobject)$ anyone can verify the authenticity of a trace that led to the existence of $\csobject$.

A very important property of object identifiers is that future transactions cannot re-create an object that has already become inactive. Thus checking object validity only requires maintaining a list of active objects, and not a list of past inactive objects:

No sequence of valid transactions, by a polynomial time constrained adversary, may re-create an object with the same identifier with an object that has already been active in the system.

We argue this property by induction on the serialized application of valid transactions, and for each transaction by structural induction on the two validity rules. Assuming a history of $n-1$ transactions for which this property holds we consider transaction $n$. Within transaction $n$ we sequence all traces and their dependencies, and follow the data flow of the creation of new objects by the `check' rule. For two objects to have the same $\id(\csobject)$ there need to be two invocations of the check rule with the same contract, procedure, inputs and references. However, this leads to a contradiction: once the first trace is checked and considered valid the active input objects are removed from the active set, and the second invocation becomes invalid. Thus, as long as object creation procedures have at least one input (which is ensured by the side condition) the theorem holds, unless an adversary can produce a hash collision. The inductive base case involves assuming that no initial objects start with the same identifier – which we can ensure axiomatically.

We call this directed acyclic graph with identifiers derived using cryptographic functions a Hash-DAG, and we make extensive use of the identifiers of objects and their properties in .

Node Hash-Chains. Each node in , that is entrusted with preserving integrity, associates with its shard a hash chain. Periodically, peers within a shard consistently agree to seal a checkpoint, as a block of transactions into their hash chains. They each form a Merkle tree containing all transactions that have been accepted or rejected in sequence by the shard since the last checkpoint was sealed. Then, they extend their hash chain by hashing the root of this Merkle tree and a block sequence number, with the head hash of the chain so far, to create the new head of the hash chain. Each peer signs the new head of their chain, and shares it with all other peers in the shard, and anyone who requests it. For strong auditability additional information, besides committed or aborted transactions, has to be included in the Merkle tree: node should log any promise to either commit or abort a transaction from any other peer in any shard (the prepared(,*) statements explained in the next sections).

All honest nodes within a shard independently create the same chain for a checkpoint, and a signature on it—as long as the consensus protocols within the shards are correct. We say that a checkpoint represents the decision of a shard, for a specific sequence number, if at least $\faulty + 1$ signatures of shard nodes sign it. On the basis of these hash chains we define a partial audit and a full audit of the system.

In a partial audit a client is provided evidence that a transaction has been either committed or aborted by a shard. A client performing the partial audit may request from any node of the shard evidence for a transaction . The shard peer will present a block representing the decision of the shard, with $\faulty + 1$ signatures, and a proof of inclusion of a commit or abort for the transaction, or a signed statement the transaction is unknown. A partial audit provides evidence to a client of the fate of their transaction, and may be used to detect past of future violations of integrity. A partial audit is an efficient operation since the evidence has size $O(s + \log N)$ in $N$ the number of transactions in the checkpoint and $s$ the size of the shard—thanks to the efficiency of proving inclusion in a Merkle tree, and checking signatures.

A full audit involves replaying all transactions processed by the shard, and ensuring that (1) all transactions were valid according to the checkers the shard executed; (2) the objects input or references of all committed transactions were all active (see rules in <Ref>); and (3) the evidence received from other shards supports committing or aborting the transactions. To do so an auditor downloads the full hash-chain representing the decisions of the shard from the beginning of time, and re-executes all the transactions in sequence. This is possible, since—besides their secret signing keys—peers in shards have no secrets, and their execution is deterministic once the sequence of transactions is defined. Thus, an auditor can re-execute all transactions in sequence, and check that their decision to commit or abort them is consistent with the decision of the shard. Doing this, requires any inter-shard communication (namely the promises from other shards to commit or abort transactions) to be logged in the hash-chain, and used by the auditor to guide the re-execution of the transactions. A full audit needs to re-execute all transactions and requires evidence of size $O(N)$ in the number $N$ of transactions. This is costly, but may be done incrementally as new blocks of shard decisions are created.

§.§ Distributed Architecture & Consensus

A network of nodes manages the state of objects, keeps track of their validity, and record transactions that are seen or that are accepted as being committed.

uses sharding strategies to ensure scalability: a public function $\shard(\csobject)$ maps each object $\csobject$ to a set of nodes, we call a shard. These nodes collectively are entrusted to manage the state of the object, keep track of its validity, record transactions that involve the object, and eventually commit at most one transaction consuming the object as input and rendering it inactive. However, nodes must only record such a transaction as committed if they have certainty that all other nodes have, or will in the future, record the same transaction as consuming the object. We call this distributed algorithm the consensus algorithm within the shard.

For a transaction $\transaction$ we define a set of concerned nodes, $\Phi(\transaction)$ for a transaction structure $\transaction$. We first denote as $\zeta$ the set of all objects identifiers that are input into or referenced by any trace contained in $\transaction$. We also denote as $\xi$ the set of all objects that are output by any trace in $\transaction$. The function $\Phi(\transaction)$ represents the set of nodes that are managing objects that should exist, and be active, in the system for $\transaction$ to succeed. More mathematically, $\Phi(\transaction) = \bigcup \{ \phi(\csobject_i) | \csobject_i \in \zeta \setminus \xi \} $, where $\zeta \setminus \xi$ represents the set of objects input but not output by the transaction itself (its free variables). The set of concerned peers thus includes all shard nodes managing objects that already exist in that the transaction uses as references or inputs.

An important property of this set of nodes holds, that ensures that all smart contracts involved in a transaction will be mapped to some concerned nodes that manage state from this contract:

If a contract $\contract$ appears in any trace within a transaction $\transaction$, then the concerned nodes set $\Phi(\transaction)$ will contain nodes in a shard managing an object $\csobject$ of a type from contract $\contract$. I.e. $\exists o. \type(o) \in \types(\contract) \land \shard(o) \cap \Phi(\transaction) \neq \emptyset$.

Consider any trace $t$ within $\transaction$, from contract $c$. If the inputs or references to this trace are not in $\xi$—the set of objects that were created within $\transaction$—then their shards will be included within $\Phi(\transaction)$. Since those are of types within $\contract$ the theorem holds. If on the other hand the inputs or references are in $\xi$, it means that there exists another trace within $\transaction$ from the same contract $\contract$ that generated those outputs. We then recursively apply the case above to this trace from the same $\contract$. The process will terminate with some objects of types in $\contract$ and shard managing them within the concerned nodes set—and this is guarantee to terminate due to the Hash-DAG structure of the transactions (that may have no loops).

<Ref> ensures that the set of concerned nodes, includes nodes that manage objects from all contracts represented in a transaction. leverages this to distribute the process of rule validation across peers in two ways:

* For any existing object $\csobject$ in the system, used as a reference or input within a transaction $\transaction$, only the shard nodes managing it, namely in $\shard(\csobject)$, need to check that it is active (as part of the `check' rule in <Ref>).

* For any trace $t$ from contract $\contract$ within a transaction $\transaction$, only shards of concerned nodes that manage objects of types within $\contract$ need to run the checker of that contract to validate the trace (again as part of the `check' rule), and that all input, output and reference objects are of types within $\contract$.

However, all shards containing concerned nodes for $\transaction$ need to ensure that all others have performed the necessary checks before committing the transaction, and creating new objects.

Bano: shorten this by shifting anything you need to related work, and deleting. There are many options how to ensure that the shards of concerned nodes for a transaction do not have an inconsistent state for the accepted transactions:

* Centralization. Instead of relying on multiple peers, a centralized (possibly distributed) system is entrusted with accepting transactions, that do not conflict with each other.

* Proof-of-work. All peers manage all transactions, and each accepts a set of them they seal into blocks. They run a proof of work <cit.> scheme. The one that succeeds in completing a puzzle broadcasts the block to the others and after validation it is appended to the set of active transactions, as in the Bitcoin cryptographic currency [28]. The chain with the most work is considered valid.

* Coordinator. For each transaction there is a natural coordinator, that facilitates a two-phase commit protocol [20] across all concerned nodes to determine whether the next transaction is to be accepted.

* Paxos. Peers run a full 2-round Paxos protocol [18] to determine whether an incoming transaction can be accepted. Since the concerned peers for transactions with common inputs overlap, no inconsistent state can be reached. However, scalability suffers due to all nodes having to participate and order all actions.

* Byzantine Fault Tolerance. Paxos can only recover from crash-failures but not fully Byzantine participants. In order to tolerate some malicious peer a BFP consensus protocol, such as the recent xPaxos [19] may be used across the concerned peers to decide which transactions to accept. However, again this leads to a total ordering of all transactions though all nodes being part of the BFT session—which is not scalable.

The above list describes options going from the most centralized, but correct, option to the most decentralized one.

There are many options for ensuring that concerned nodes in each shards do not reach an inconsistent state for the accepted transactions, such as Nakamoto consensus through proof-of-work [28], two-phase commit protocols [20], and classical consensus protocols like Paxos [18], PBFT [8], or xPaxos [19]. However, these approaches lack in performance, scalability, and/or security. We design an open, scalable and decentralized mechanism to perform Sharded Byzantine Atomic Commit or .

§.§ Sharded Byzantine Atomic Commit ().

implements the previously described intra-shard consensus algorithm for transaction processing in the byzantine and asynchronous setting, through the Sharded Byzantine Atomic Commit () protocol, that combines two primitive protocols: Byzantine Agreement and atomic commit.

* Byzantine agreement ensures that all honest members of a shard of size $3 \faulty + 1$, agree on a specific common sequence of actions, despite
some $\faulty$ malicious nodes within the shard. It also guarantees that when agreement is sought, a decision or sequence will eventually be agreed upon. The agreement protocol is executed within each shard to coordinate all nodes. We use  [33] implementation of PBFT for state machine replication that provides an optimal number of communications steps (similar to PBFT [8]). This is achieved by replacing reliable broadcast with a special leader-driven Byzantine consensus primitive called Validated and Provable Consensus (VP-Consensus).

* Atomic commit is ran across all shards managing objects relied upon by a transaction. It ensures that each shard needs to accept to commit a transaction, for the transaction to be committed; even if a single shard rejects the transaction, then all agree it is rejected. We propose the use of a simple two-phase commit protocol [3], composed with an agreement protocol to achieve this—loosely inspired by Lamport and Gray [14]. This protocol was the first to reconcile the needs for distributed commit, and replicated consensus (but only in the non-byzantine setting).

[->,>=stealth',shorten >=1pt,auto,node distance=2.4cm,
every state=[fill=white,draw=black,text=black]

[initial,state] (A)                    None;
[state]         (B) [ right of=A] Active;
[state]         (C) [below right of=B,align=center] Locked
for $\transaction$;
[state]         (D) [ right of=C] Inactive;

(A) edge [align=center]     node All
(commit, T') (B)

(B) edge [in=30,out=60, loop,  align=center] node Local
(abort, T) (B)
edge             [align=center] node Local
(commit, T) (C)
(C) edge             [align=center] node [below] All
(commit, T) (D)
edge [bend left, align=center]  node Some
(Abort, T) (B)
edge [in=30,out=60, loop, align=center]  node *
(*, T”) (B)

The state machine representing the active, locked and inactive states for any object within . Each node in a shard replicates the state of the object, and participates in a consensus protocol that allows it to derive the invariants “Local prepared”, “All prepared”, and “Some prepared” to update the state of an object.

[shorten >=1pt]
dot/.style=circle,fill=#1,inner sep=0,minimum size=4pt

[draw, ->] (0, 3) – (13, 3) node[left, pos=-0.02] User with $T \{o_1, o_2\} \rightarrow o_3$
node[pos=0.05, dot=black,draw] (ustart)

node[pos=0.8, dot=black,draw] (ufinal) ;

[draw, ->] (0, 2.1) – (13, 2.1) node[left, pos=0] ;
[draw, ->] (0, 1.9) – (13, 1.9) node[left, pos=0] ;
[draw, ->] (0, 2) – (13, 2) node[left, pos=-0.02] Input shard $\shard(o_1)$
node[pos=0.1, dot=black,draw] (s1p1)
node[rectangle, fill=white, pos=0.2,draw] (s1bft) BFT
node[pos=0.3, dot=black,draw] (s1e1)
node[pos=0.4, dot=black,draw] (s1p2)
node[rectangle, fill=white, pos=0.5,draw] (s1bft2) BFT
node[pos=0.6, dot=black,draw] (s1e2)
node[pos=0.7, dot=black,draw] (s1ee) ;

[draw, ->] (0, 1.1) – (13, 1.1) node[left, pos=0] ;
[draw, ->] (0, 0.9) – (13, 0.9) node[left, pos=0] ;
[draw, ->] (0, 1) – (13, 1) node[left, pos=-0.02] Input shard $\shard(o_2)$
node[pos=0.1, dot=black,draw] (s2p1)
node[rectangle, fill=white, pos=0.2, draw] (s2bft) BFT
node[pos=0.3, dot=black,draw] (s2e1)
node[pos=0.4, dot=black,draw] (s2p2)
node[rectangle, fill=white, pos=0.5, draw] (s2bft2) BFT
node[pos=0.6, dot=black,draw] (s2e2)
node[pos=0.7, dot=black,draw] (s2ee) ;

[draw, ->] (0, 0.1) – (13, 0.1) node[left, pos=0] ;
[draw, ->] (0, -0.1) – (13, -0.1) node[left, pos=0] ;
[draw, ->] (0, 0) – (13, 0) node[left, pos=-0.02] Output shard $\shard(o_3)$
node[pos=0.7, dot=black,draw] (s3p2)
node[rectangle, fill=white, pos=0.8, draw] (s3bft2) BFT
node[pos=0.9] (s3e2) ;

[draw=none] (0, -0.5) – (13, -0.5) node[left, pos=0]
node[pos=0.05] (Lustart)

node[pos=0.2] (Le1)
node[pos=0.5] (Lp2)

node[pos=0.8] (Le2) ;

[below=0.1cm, align=center] at (Lustart) Initial

[below=0.1cm, align=center] at (Le1) Process
[below=0.1cm, align=center] at (Lp2) Process
[below=0.1cm, align=center] at (Le2) Process

[above=0.1cm, align=center] at (ustart) Send prepare($\transaction$);

[above=0.1cm, align=left] at (ufinal) Client Accept Confirmation;

[below=0.2cm] at (s3bft2) Create $o_3$;
[below=0.2cm] at (s1bft2) Inactive $o_1$;
[below=0.2cm] at (s2bft2) Inactive $o_2$;

[semithick, ->] (ustart) edge (s1p1);
[semithick, ->] (ustart) edge (s2p1);

[semithick, ->] (s1e1) edge (s2p2);
[semithick, ->] (s1e2) edge (s3p2);
[semithick, ->] (s1e2) edge (s2ee);

[semithick, ->] (s2e1) edge (s1p2);
[semithick, ->] (s2e2) edge (s3p2);
[semithick, ->] (s2e2) edge (s1ee);

[semithick, ->] (s2ee) edge (ufinal);
[semithick, ->] (s1ee) edge (ufinal);

for a transaction $T$ with two inputs ($o_1, o_2$) and one output object ($o_3$). The user sends the transaction to all nodes in shards managing $o_1$ and $o_2$. The takes the lead in sequencing $\transaction$, and emits 'prepared(accept, T)' or 'prepared(abort, T)' to all nodes within the shard. Next the of each shard assesses whether overall `All proposed(accept, T)' or `Some proposed(abort, T)' holds across shards, sequences the accept(T,*), and sends the decision to the user. All cross-shard arrows represent a multicast of all nodes in one shard to all nodes in another.

composes the above primitives in a novel way to ensure that shards process safely and consistently all transactions. <Ref> illustrates a simple example of the protocol to commit a single transaction with two inputs and one output that we may use as an example. The corresponding object state transitions have been illustrated in <Ref>. The combined protocol has been described below. For ease of understanding, in our description we state that all messages are sent and processed by shards. In reality, some of these are handled by a designated node in each shard—the —as we discuss at the end of this section.

Initial Broadcast (Prepare). A user acts as a transaction initiator, and sends `prepare(T)' to at least one honest concerned node for transaction $\transaction$.

To ensure at least one honest node receives it, the user may send the message to $\faulty+1$ nodes of a single shard, or $\faulty+1$ nodes in each concerned shard.

Sequence Prepare. Upon a message `prepare(T)' being received, nodes in each shard interpret it as the initiation of a two-phase commit protocol performed across the concerned shards.

The shard locally sequences `prepare(T)' message through the Byzantine consensus protocol.

Process Prepare. Upon the first action `prepare($T$)' being sequenced through BFT consensus in a shard, nodes of the shard implicitly decide whether it should be committed or aborted. Since all honest nodes in the shard have a consistent replica of the full sequence of actions, they will all decide the same consistent action following `prepare(T)'.

Transaction $\transaction$ is to be committed if it is valid according to the usual rules (see <Ref>), in brief: (1) the objects input or referenced by $\transaction$ in the shard are active, (2) there is no other instance of the two-phase commit protocol on-going concerning any of those objects (no locks held) and (3) if $\transaction$ is valid according to the validity rules, and the smart contract checkers in the shard. Only the checkers for types of objects held by the shard are checked by the shard.

If the decision is to commit, the shard broadcasts to all concerned nodes `prepared($T$,commit)', otherwise it broadcasts `prepared($T$, abort)'—along with sufficient signatures to convince any party of the collective shard decision (we denote this action as (*, T)). The objects used or referenced by $T$ are `locked' (<Ref>) in case of a `prepared commit' until an `accept' decision on the transaction is reached, and subsequent transactions concerning them will be aborted by the shard. Any subsequent `prepare($T''$)' actions in the sequence are ignored, until a matching accept($T$, abort) is reached to release locks, or forever if the transaction is committed.

Process Prepared (accept or abort).

Depending on the decision of `prepare($T$)', the shard sequences `accept($T$,commit)' or `accept($T$,abort)'  through the atomic commit protocol across all the concerned shards—along with all messages and signatures of the bundle of `prepared' messages relating to $T$ proving to other shards that the decision should be `accept($T$,commit)' or `accept($T$,abort)' according to its local consensus.
If it receives even a single `($T$,abort)' from another shard it instead will move to reach consensus on `accept($T$, abort)' (denoted as (abort,T)). Otherwise, if all the shards respond with `($T$,commit)' it will reach a consensus on (commit,T). The final decision is sent to the user, along with all messages and signatures of the bundle of `accept' messages relating to $T$ proving that the final decision should be to commit or abort according to responses from all concerned shards.

It is possible, that a shard hears a prepared message for $\transaction$ before a prepare message, due to unreliability, asynchrony or a malicious user. In that case the shard assumes that a `prepare(T)' message is implicit, and sequences it.

Process Accept. When a shard sequences an `accept($T$, commit)' decision, it sets all objects that are inputs to the transaction $T$ as being inactive (<Ref>). It also creates any output objects from $T$ via BFT consensus that are to be managed by the shard. If the output objects are not managed by the shard, the shard sends requests to the concerned shards to create the objects.
On the other hand if the shard decision is `accept($T$, abort)',  all nodes release locks held on inputs or references of transaction $T$. Thus those objects remain active and may be used by other transactions.

As previously mentioned, some of the messages in are handled by a designated node in each shard called the . Specifically, the drives the composed protocol by sending `prepare(T)' and then `accept($T$, *)' messages to reach BFT consensus within and across shards. It is also responsible for broadcasting consensus decisions to relevant parties. The protocol supports a two-phase process to recover from a malicious that suppresses transactions. As nodes in a shard hear all messages, they wait for the to act on it until they time out. They first send a reminder to the along with the original message to account for network losses. Next they proceed to wait; if they time out again, other nodes perform the action of which is idempotent.

§.§ Concurrency & Scalability

Each transaction $\transaction$ involves a fixed number of concerned nodes $\Phi(\transaction)$ within , corresponding to the shards managing its inputs and references. If two transactions $\transaction_0$ and $\transaction_1$ have disjoint sets of concerned nodes ($\Phi(T_0) \cap \Phi(T_1) = \emptyset$) they cannot conflict, and are executed in parallel or in any arbitrary order.
If however, two transactions have common input objects, only one of them is accepted by all nodes. This is achieved through the protocol. It is local, in that it concerns only nodes managing the conflicting transactions, and does not require a global consensus.

From the point of view of scalability, capacity grows linearly as more shards are added, subject to transactions having on average a constant, or sub-linear, number of inputs and references (see <Ref>). Furthermore, those inputs must be managed by different nodes within the system to ensure that load of accepting transactions is distributed across them.

§ SECURITY AND CORRECTNESS

§.§ A Clark-Wilson Security Policy

The system implements a platform that enforces a high-integrity security policy, by embodying a variant of a Clark-Wilson security policy [10].

In the language of the Clack-Wilson (CW) policy, objects represent constrained data items (CDI). Their creation implicitly ensures the integrity verification procedures (IVP) as defined by the smart contract checker. Transactions Procedures (TP) are defined through the procedures of smart contracts, and the checker of those procedures ensures CDI objects are consumed and valid new CDI objects are created. Thus the Clark-Wilson certification rules C1 and C2 are embodied in the rules ensuring validity of transactions.

The operations, namely nodes checking and executing valid client-submitted transactions, guarantees the Clark-Wilson enforcement rule CW-E1. Namely, only valid TPs takes CDIs from one valid state to another, as guaranteed by the checks nodes perform, and their acceptance of new transaction using a consensus protocol to avoid inconsistencies.

At its heart also enforces a very strong variant of certification rule CW-C4 relating to logging: through the distributed high-integrity data structures kept at each peer, a record of TPs applied, along with all their parameters, is kept. This log may be used to reconstruct the state of the system at any point; it may also be used to detect peer misbehaviour—through replication—and provides a strong form of non-equivocation.

Finally, certification rule CW-C5, relating to the admission of unconstrained data items into the system is also implemented by . procedures may be defined that take local parameters and generate output objects—and perform sanitization in the process. In that sense it acts as a gateway between data that is not currently in the system, and transforms it into constrained data items.

One aspect of the Clark-Wilson policy that purposefully omits relates to authentication and authorisation. Traditional Clark-Wilson presupposes all principals submitting transactions are authenticated (rule CW-E3), and all transaction submission authorised (rule E2) through an access control matrix. However, we make the choice for the system to be agnostic about identity and authorisation.

Instead, we entrust checkers to ensure proper authentication and authorization, where necessary. The objects in the system are supposed to carry enough information to facilitate access control by users performing transactions. Authenticators, such as valid signatures authorizing actions, may be passed to the local state of the transaction by the clients creating it.  This maximizes the flexibility afforded to smart contracts to implement any authentication or authorization process they prefer. Advanced designs are also possible, such as  privacy-friendly options using selective disclosure credentials, pseudonyms or succinct arguments of knowledge to authorize actions.

§.§ Security & Correctness of

The protocol guarantees a number of key properties, on which rest the security of , namely liveness consistency, and validity. Before proceeding with stating those properties in details, and proving them we note three key invariants, that nodes may decide:

* (commit / abort, T): A node considers that (commit / abort, T) for a shard holds, if it receives at least $\faulty + 1$ distinct signed messages from nodes in the shard, stating `prepared(commit, T)' or `prepared(abort, T)' respectively. As a special case a node automatically concludes (commit / abort, T) for a shard it is a member of, if all the preconditions necessary to provide that answer are present when an `prepare(T)' is sequenced.

* (commit, T): A node considers that `(commit, T)' holds if it believes that `(commit, T)' holds for all shards with concerned nodes for $T$. Note this may only be decided after reaching a conclusion (e.g. through receiving signed messages) about all shards.

* (abort, T): A node considers that `(abort, T)' holds if it believes that `(abort, T)' holds for at least one shard with concerned nodes for $T$. This may be concluded after only reaching a conclusion for a single shard, including the shard the node may be part of.

Liveness ensures that transactions make progress once proposed by a user, and no locks are held indefinitely on objects, preventing other transactions from making progress.

Liveness: Under the `honest shards' threat model, a transaction $\transaction$ that is proposed to at least one honest concerned node, will eventually result in either being committed or aborted, namely all parties deciding accept(commit, T) or accept(abort, T).

We rely on the liveness properties of the byzantine agreement (shards with only $\faulty$ nodes will reach a consensus on a sequence), and the broadcast from nodes of shards to all other nodes of shards, including the shards that manage transaction outputs. Assuming prepare(T) has been given to an honest node, it will be sequenced withing an honest shard BFT sequence, and thus a prepared(commit, T) or prepared(abort, T) will be sent from the $2\faulty+1$ honest nodes of this shard, to the $2\faulty+1$ nodes of the other concerned shards. Upon receiving these messages the honest nodes from other shards will schedule a prepare(T) message within their shards, and the BFT will eventually sequence it. Thus the user and all other honest concerned nodes will receive enough `prepared' messages to decide whether to proceed with `(commit, T)' or `(abort, T)' and proceed with sequencing them through BFT. Eventually, each shard will sequence those, and decide on the appropriate `accept'.

The second key property ensures that the execution of all transactions could be serialized, and thus is correct.

Consistency: Under the `honest shards' threat model, no two conflicting transactions, namely transactions sharing the same input will be committed. Furthermore, a sequential executions for all transactions exists.

A transaction is committed only if some nodes conclude that `(commit, T)', which presupposes all shards have provided enough evidence to conclude `(commit, T)' for each of them. Two conflicting transaction, sharing an input or reference, must share a shard of at least $3\faulty+1$ concerned nodes for the common object—with at most $\faulty$ of them being malicious. Without loss of generality upon receiving the prepare(T) message for the first transaction, this shard will sequence it, and the honest nodes will emit messages for all to conclude `(commit, T)'—and will lock this object until the two phase protocol concludes. Any subsequent attempt to prepare(T') for a conflicting T' will result in a (abort, T') and cannot yield a commit, if all other shards are honest majority too. After completion of the first `accept(commit, T)' the shard removes the object from the active set, and thus subsequent T' would also lead to (abort, T'). Thus there is no path in the chain of possible interleavings of the executions of two conflicting transactions that leads to them both being committed.

Validity: Under the `honest shards' threat model, a transaction may only be committed if it is valid according to the smart contract checkers matching the traces of the procedures it executes.

A transaction is committed only if some nodes conclude that `(commit, T)', which presupposes all shards have provided enough evidence to conclude `(commit, T)' for each of them. The concerned nodes include at least one shard per input or reference object for the transaction; for any contract $\contract$ represented in the transaction, at least one of those shards will be managing object from that contract. Each shard checks the validity rules for the objects they manage (ensuring they are active, and not locked) and the contracts those objects are part of (ensuring the calls to $\contract$ pass its checker) in order to (accept, T). Thus if all shards say (accept, T) to conclude that `(commit, T)', all object have been checked as active, and all the contract calls within the transaction have been checked by at least one shard—whose decision is honest due to at most $\faulty$ faulty nodes. If even a single object is inactive or locked, or a single trace for a contract fails to check, then the honest nodes in the shard will emit `prepared(abort, T)' upon sequencing `prepare(T)', and the final decision will be `(abort, T)'.

§.§ Auditability

In the previous sections we show that if each shard contains at most $\faulty$ faulty nodes (honest shard model), the protocol guarantees consistency and validity. In this section we argue that if this assumption is violated, i.e. one or more shards contain more than $\faulty$ byzantine nodes each, then honest shards can detect faulty shards. Namely, enough auditing information is maintained by honest nodes in to detect inconsistencies and attribute them to specific shards (or nodes within them).

The rules for transaction validity are summarized in <Ref>. Those rules are checked in a distributed manner: each shard keeps and checks the active or inactive state of objects assigned to it; and also only the contract checkers corresponding to the type of those objects. An honest shard emits a proposed(T, commit) for a transaction T only if those checks pass, and proposed(T, abort) otherwise or if there is a lock on a relevant object. A dishonest shard may emit proposed(T, *) messages arbitrarily without checking the validity rules. By definition, an invalid transaction is one that does not pass one or more of the checks defined in <Ref> at a shared, for which the shard has erroneously emitted a proposed(T, commit) message.

Auditability: A malicious shard (with more than  faulty nodes) that attempts to introduce an invalid transaction or object into the state of one or more honest shards, can be detected by an auditor performing a full audit of the system.

We consider two hash-chains from two distinct shards. We define the pair of them as being valid if (1) they are each valid under full audit, meaning that a re-execution of all their transactions under the messages received yields the same decisions to commit or abort all transactions; and (2) if all prepared(T,*) messages in one chain are compatible with all messages seen in the other chain. In this context `compatible' means that all prepared(T,*) statements received in one shard from the other represent the `correct' decision to commit or abort the transaction T in the other shard. An example of incompatible message would result in observing a proposed(T, commit) message being emitted from the first shard to the second, when in fact the first shard should have aborted the transaction, due to the checker showing it is invalid or an input being inactive.

Due to the property of digital signatures (unforgeability and non-repudiation), if two hash-chains are found to be `incompatible', one belonging to an honest shard and one belonging to a dishonest shard, it is possible for everyone to determine which shard is the dishonest one. To do so it suffices to isolate all statements that are signed by each shard (or a peer in the shard)—all of which should be self-consistent. It is then possible to show that within those statements there is an inconsistency—unambiguously implicating one of the two shards in the cheating. Thus, given two hash-chains it is possible to either establish their consistency, under a full audit, or determine which belongs to a malicious shard.

Note that the mechanism underlying tracing dishonest shards is an instance of the age-old double-entry book keeping[The first reported use is 1340AD [23].]: shards keep records of their operations as a non-repudiable signed hash-chain of checkpoints—with a view to prove the correctness of their operations. They also provide non-repudiable statements about their decisions in the form of signed proposed(T,*) statements to other shards. The two forms of evidence must be both correct and consistent—otherwise their misbehaviour is detected.

§ SYSTEM AND APPLICATIONS SMART CONTRACTS

§.§ System Contracts

The operation of a distributed ledger itself requires the maintenance of a number of high-integrity high-availability data structures. Instead of employing an ad-hoc mechanism, employs a number of system smart contracts to implement those.  Effectively, instantiation of is the combination of nodes running the basic protocol, as well as a set of system smart contracts providing flexible policies about managing shards, smart contract creation, auditing and accounting. This section provides an overview of system smart contracts.

Shard management. The discussion of so far, has assumed a function $\shard(\csobject)$ mapping an object $\csobject$ to nodes forming a shard. However, how those shards are constituted has been abstracted. A smart contract  is responsible for mapping nodes to shards.  initializes a singleton object of type  and provides three procedures:  takes as input a singleton object, and a list of node descriptors (names, network addresses and public verification keys), and creates a new singleton object and a  object representing a new shard;  takes an existing shard object, a new list of nodes, and $2\faulty+1$ signatures from nodes in the shard, and creates a new shard object representing the updated shard. Finally, the  procedure takes a shard object, and a non-repudiable record of malpractice from one of the nodes in the shard, and creates a new shard object omitting the malicious shard node—after validating the misbehaviour. Note that is `open' in the sense that any nodes may form a shard; and anyone may object to a malicious node and exclude it from a shard.

Smart-contract management. is also `open' in the sense that anyone may create a new smart contract, and this process is implemented using the  smart contract.  implements three types: ,  and . It also implements at least one procedure,  that takes a binary representing a checker for the contract, an initialization procedure name that creates initial objects for the contract, and the singleton token object. It then creates a number of outputs: one object of type  for use to create further contracts; an object of type  representing the contract, and containing the checker code, and a mapping object  encoding the mapping between objects of the contract and shards within the system. Furthermore, the procedure  calls the initialization function of the contract, with the contract itself as reference, and the singleton token, and creates the initial objects for the contract.

Note that this simple implementation for  does not allow for updating contracts. The semantics of such an update are delicate, particularly in relation to governance and backwards compatibility with existing objects. We leave the definitions of more complex, but correct, contracts for managing contracts as future work. In our first implementation we have hardcoded  and .

Payments for processing transactions. is an open system, and requires protection againt abuse resulting from overuse. To achieve this we implement a method for tracking value through a contract called .

The  contract creates a fixed initial supply of coins—a set of objects of type The  that may only be accessed by a user producing a signature verified by a public key denoted in the object. A  procedure allows a user to input a number of accounts, and transfer value between them, by producing the appropriate signature from incoming accounts. It produces a new version of each account object with updated balances. This contract has been implemented in Python with approximately 200 lines of code.

The  contract is designed to be composed with other procedures, to enable payments for processing transactions. The transfer procedure outputs a number of local returns with information about the value flows, that may be used in calling contracts to perform actions conditionally on those flows. Shards may advertise that they will only consider actions valid if some value of  is transferred to their constituent nodes. This may apply to system contracts and application contracts.

What we have:

* Nodes checkpoint every $s$ seconds.

* At each checkpoint, nodes compile all transactions committed during that checkpoint into a merkle tree. The root of this merkle tree is concatenated with the hash of the previous block header, to produce a new block header.

* Light audit: End clients can ask nodes for the transactions in the blockchain, and nodes should reply with a proof of inclusion of the transaction in the chain. This provides assurance to the end client that the transaction is auditable via a full audit.

* Full audit: An auditor that wants to audit the full blockchain can download all the ledgers from all the shards and manually validate every transaction to detect misbehaving shards (i.e. shards where 2f+1 nodes are dishonest).

* DISCUSS: During inter-shard transactions, the result of the first BFT round should be logged in the blockchain, and shards should provide other input shards with a proof of inclusion that this result is in the blockchain, before other shards commit the tranasction. This enables other shards to have assurance that the result from the first shard is publicly auditable. (Note: this would mean that transactions take two blocks to be committed.)

* Discussion: We do not use a blockchain for consensus, but for auditability. Our BFT consensus protocol provides assurances that the system works as long as 2f+1 nodes in all shards are honest. We use a auditable ledger to detect misbehaviour in the case where 2f+1 are dishonest.

§.§  Application level smart contracts

This section describes some examples of privacy-friendly smart contracts and showcases how smart contract creators may use to implement advanced privacy mechanisms.

Sensor—`Hello World' contract
To illustrate 's applications, we implement a simple 150 lines contract aggregating data from different sensors, called . This contract defines the types  and , and two procedures   and . The procedure  takes as input the singletone token (that is created upon contract creation), and outputs a fresh  object with initially no date. The  procedure is applied on a  object with some new sensor's data as parameter, and a new object  appending the list of new data to the previous ones is created.

Smart-Meter Private Billing.

We implement a basic private smart-meter billing mechanism [15, 31] using the contract : it implements three types ,  and ; and three procedures, , , and . The procedure  takes as input the singletone token and a public key and signature as local parameters, and it outputs a  object tied to this meter public key if the signature matches.  objects represent a collection of readings and some meta-data about the meter. Subsequently, the meter may invoke  on a  with a set of cryptographic commitments readings and a period identifier as local parameters, and a valid signature on them. A signature is also included and checked to ensure authenticity from the meter. A new object  is output appending the list of new readings to the previous ones. Finally, a procedure  is invoked with a  and local parameters a period identifier, a set of tariffs for each reading in the period, and a zero-knowledge proof of correctness of the bill computation. The procedure outputs a  object, representing the final bill in plain text and the meter and period information.

This proof of correctness is provided to the checker—rather than the secret readings—which proves that the readings matching the available commitments and the tariffs provided yield the bill object. The role of the checker, which checks public data, in both those cases is very different from the role of the procedure that is passed secrets not available to the checkers to protect privacy.

This contracts has been implemented in about 200 lines of Python code and is evaluated in section <Ref>.

A Platform for Decision Making.
An additional example of 's privacy-friendly application is a smart voting system. We implement the contract  with three types, ,  and ; and three procedures.

, consumes a singleton token and takes as local parameters the options, a list of all voter's public key, the tally's public key, and a signature on them from the tally. It outputs a fresh  object, representing the initial stage of the election (all candidates having a score of zero) along with a zero-knowledge proof asserting the correctness of the initial stage.

, is called on a  object and takes as local parameters a new vote to add, homomorphically encrypted and signed by the voter. In addition, the voter provides a zero-knowledge proof certifying that her vote is a binary value and that she voted for exactly one option. The voter's public key is then removed from the list of participants to ensure that she cannot vote more than once. If all proofs are verified by the checker and the voter's public key appears in the list, a new  object is created as the homomorphic addition of the previous votes with the new one. Note that the checker does not need to know the clear value of the votes to assert their correctness since it only has to verify the associated signatures and zero-knowledge proofs.

Finally, the procedure  is called to threshold decrypt the aggregated votes and provide a  object representing the final election's result in plain text, along with a proof of correct decryption from the tally. The  contract's size is approximately 400 lines.

§ IMPLEMENTATION & EVALUATION

We implemented a prototype of in $\sim$10K lines of Python and Java code. The implementation consists of two components: a Python contracts environment and a Java node. We have released the code as an open-source project on GitHub.[URL omitted for double-blind review.]

Python Contract Environment.
The Python contracts environment allows developers to write, deploy and test smart contracts. These are deployed on each node by running the Python script for the contract, which starts a local web service for the contract's checker. The contract's checker is then called though the web service. The environment provides a framework to allow developers to write smart contracts with little worry about the underlying implementation, and provides an auto-generated checker for simple contracts.

Java Node Implementation.
The Java node implements a shard replica that accepts incoming transactions from clients and initiates, and executes, the protocol. For BFT consensus, we use the  [4] Java library—one of the very few maintained open source libraries implementing byzantine consensus.

Diagram illustrating the implementation of a system with two shards managing four nodes each. The user submits the transaction to its local client through a built-in HTTP API (arrow 1). Then, this client sends the transaction to (arrow 2).

To communicate with , end users also run an –enabled client. First, she creates a transaction through the Python environments using one or many existing smart contracts.

She then submits the transaction to its client through the HTTP API as indicated in <Ref>, that sends the transaction to according to the protocol.

A node is composed of a server divided in two parts: the core and the checker. To communicate with other nodes, each node also contains an client. When a transaction is received, the core is in charge of verifying that the input objects and references are active (neither locked nor inactive).  Then, the node runs the checker associated with the contract, in an isolated container. (The checker is provided by the contract's creator when the node starts up, and interfaces with the node through an HTTP API.) When the client submits a transaction with dependencies, the core recursively checks each dependent transaction first, and the top-level transaction at last (similar to depth-first search algorithm).

Performance Measurements. We evaluated the performances and scalability of our implementation of , through deployments on Amazon EC2 containers. We launched up to 96 nodes on t2.medium virtual machines, each containing 8 GB of RAM on 2 virtual CPUs and running GNU/Linux Debian 8.1. We sent transactions to the network from a client running on a t2.xlarge virtual machine, containing 16 GB of RAM and 4 virtual CPUs, also running GNU/Linux Debian 8.1. In our tests, we map objects to shards randomly using the mapping function $\phi(o) = id(o) \mod K$ where $K$ is a constant representing the number of shards and $id(o)$ is the SHA256 hash of the object.

We first measure the effect of the number of shards on transaction throughput (<Ref>). The transaction throughput of scales linearly with the number of shards: with 4 nodes per shard, the number of transactions per second (t/s) increases on average by 22 for 1-input transactions for each shard added. This is because as inputs are randomly assigned to shards based on their hashes, the transaction processing load is spread out over a larger number of shards.

Next we investigate the effect of shard size (the number of nodes per shard) on transaction throughput (<Ref>). We fix the number of shards to 2, and increase the number of nodes per shard from 2 to 48. With configured for $3f+1$ fault tolerance, we observe an expected gracious decrease in transaction throughput: for each node added, the throughput reduces on average by 1.6 transactions per second. This is because in order for a node to realise consensus for a message, it must receive a result from at least $f+1$ nodes. Thus, the bottleneck is the latency of the $f+1$th node with the highest response time. ...

Another factor that can potentially affect transaction throughput is the number of inputs per transaction: the more shards touched by the transaction inputs, the longer it will take to run among all the concerned shards. In <Ref>, we study how the number of inputs per transaction affects transaction throughput. We measure this for 5 shards, varying the number of inputs per transaction from 1 to 10, and the inputs are randomly mapped to shards as previously stated. The transaction throughput decreases asymptotically until it becomes stable at around 40 transactions per second. This is because 's maximum time in processing transactions is capped at the time it takes to process transactions that touch all the 5 shards. Increasing the number of inputs does not further deteriorate the transaction throughput.

Finally, we measure the client-perceived latency—the time from when a client submits a transaction until it receives a decision about whether the transaction has been committed—under varying system loads expressed in terms of transactions received per second.
<Ref> shows the effect of transactions received by the system per second (all 1-input transactions) on client-perceived latency for 2 shards, each having 4 nodes. Recall from <Ref> that the average throughput for a system with similar configuration is 75 1-input transactions per second. Consequently, we observe in <Ref> that the increase in latency with varying system loads is smaller for 20 t/s–60 t/s (average 69 ms), but the values start to get bigger after 60 t/s (average 210 ms). This is when the system reaches its maximum transaction throughput, causing a backlog of transactions to be processed.

The effect of the number of shards on transaction throughput. (Shards: 2, nodes per shard: 4, input-to-shard mapping: random. Repeats: 20.)

The effect of the number of inputs per transaction on transaction throughput. (Shards: 2, nodes per shard: 4, input-to-shard mapping: random. Repeats: 20.)

The cumulative distribution function of delay for the client to receive a final commit or abort response, for varying system load. (Shards: 2, nodes per shard: 4, inputs per transaction: 1, input-to-shard mapping: random. Repeats: 5.)

The effect of the number of nodes per shard on transaction throughput. (Shards: 2, inputs per transaction: 1, input-to-shard mapping: random. Repeats: 20.)

Smart Contract Benchmarks.
We evaluate the cost and performance of some smart contracts described in <Ref>. We compute the mean ($\mu$) and standard deviation ($\sigma$) of the execution of each procedure (denoted as [g]) and checker (denoted as [c]) in the contracts. Each figure is the result of 10,000 measured on a dual-core Apple MacBook Pro 4.1, 2.7GHz Intel Core i7. The last column indicates the transaction's size resulting from executing the procedure. All cryptographic operations as digital signatures and zero-knowledge proofs have been implemented using the Python library petlib [30], wrapping OpenSSL.

to 0.47  X[1.5cm,r] X[c] X[c] X[c] X[r]
3l —Contract size: $\sim$150 lines

1lOperation         1c$\mu$ [ms]     1r$\sigma$ [ms]     1rsize [B]

[g]     0.139     $\pm$ 0.039     416

[c]     0.021     $\pm$ 0.008     -

[g]     0.105     $\pm$ 0.085     417

[c]     0.036     $\pm$ 0.015     -

The  contract is very cheap since it does not contain any cryptographic operation; the checker only has to verify the format of the transaction. The resulting micro benchmarks for  is therefore a good indication of just the overhead of the system—to execute a procedure or a checker.

to 0.47  X[1.4cm,r] X[c] X[c] X[r]
3l —Contract size: $\sim$200 lines

1lOperation     1c$\mu$ [ms]     1r$\sigma$ [ms]     1rsize [B]

[g]     4.845     $\pm$ 0.683     512

[c]     0.022     $\pm$ 0.005     -

[g]     4.986     $\pm$ 0.684     1114

[c]     5.750     $\pm$ 0.474     -

The user needs to generate a signing key pair to create an account in the  contract, which takes about 5 ms. However, verifying the account creation only requires to check the transaction's format, and it is therefore very fast. Transferring money is a little more expensive due to the need to sign the amount transferred and the beneficiary, and verifying the signature in the checker.

to 0.47  X[1.2cm,r] X[c] X[c] X[r]

3l —Contract size: $\sim$200 lines

1lOperation     1c$\mu$ [ms]     1c$\sigma$ [ms]     1rsize [B]

[g]     4.786     $\pm$ 0.480     $\sim$600

[c]     0.060     $\pm$ 0.003     -

[g]     5.286     $\pm$ 0.506     $\sim$1100

[c]     5.965     $\pm$ 0.697     -

[g]     5.043     $\pm$ 0.513     $\sim$1100

[c]     5.870     $\pm$ 0.603     -

Similarly to , creating a meter requires generating a cryptographic key pair which takes about 5 ms, while verifying the meter's creation is faster and only requires checking the transaction's format. Adding new readings takes about 5 ms, as the user needs to create a signed commitment of the readings which requires elliptic curve operations and an ECDSA signature. Computing the bill takes slightly longer (5.8 ms), and involves homomorphic additions, and verifying the bill involves checking a zero-knowledge proof of the billing calculation.

to 0.47  X[1.4cm,r] X[c] X[c] X[r]
3l —Contract size: $\sim$400 lines

1lOperation     1c$\mu$ [ms]     1r$\sigma$ [ms]     1rsize [B]

[g]     11.733     $\pm$ 1.028     $\sim$1227

[c]     11.327     $\pm$ 0.782     -

[g]     14.086     $\pm$ 1.043     $\sim$2758

[c]     28.178     $\pm$ 1.433     -

[g]     253.286     $\pm$ 7.793     $\sim$1264

[c]     11.589     $\pm$ 0.937     -

The  contract is more expensive than the others since it extensively uses zero-knowledge proofs and more advanced cryptography. For simplicity, this smart contract has been tested with three voters and two options. First of all, creating a new election event requires building a signed homomorphic encryption of the initial value for each option, and a zero-knowledge proof asserting that the encrypted value is zero; this takes roughly 11 ms to generate the transaction and to run the checker. Next, each time a vote is added, the user proves two zero-knowledge statements—one asserting that she votes for exactly one option and one proving that her vote is a binary value—and computes an ECDSA signature on her vote, which takes about 11 ms and generates a transaction of about 2.7 kB. Verifying the signature and the two zero-knowledge proofs are slower and takes about 30 ms. Finally, tallying is the slowest operation since it requires to decrypt the homomorphic encryption of the votes' sum.

§ LIMITATIONS

has a number of limitations, that are beyond the scope of this work to
tackle, and deferred to future work.

The integrity properties of rely on all shards managing objects being honest, namely containing at most $\faulty$  fault nodes each. We have chosen to let any set of nodes can create a shard. However, this means that the function $\phi(o)$ mapping objects to shards must avoid dishonest shards. Our isolation properties ensure that a dishonest shard can at worse affect state from contracts that have objects mapped to it. Thus, in , we opt to allow the contract creator to designate which shards manage objects from their contract. This embodies specific trust assumptions where users have to trust the contract creator both for the code (which is auditable) and also for the choice of shards to involve in transactions—which is also public.

In case one or more shards are malicious, we provide an auditing mechanism for honest nodes in honest shards to detect
the inconsistency and to trace the malicious shard. Through the Hash-DAG structure it is also possible to fully audit the histories of two objects, and to ensure that the validity rules hold jointly—in particular the double-use rules. However, it is not clear how to automatically recover from detecting such an inconsistency. Options include: forcing a fork into one or many consistent worlds; applying a rule to collectively agree the canonical version; patching past transactions to recover consistency; or agree on a minimal common consistent state. Which of those options is viable or best is left as future work.

Checkers involved in validating transactions can be costly. For this reason we allow peers in a shard to accept transactions subject to a  payment to the peers. However, this `flat' fee is not dependent on the cost or complexity of running the checker which might be more or less expensive. Etherium [39] instead charges `gas' according to the cost of executing the contract procedure—at the cost of implementing their own virtual machine and language.

Finally, the protocol ensures correctness in all cases. However, under high contention for the same object the rate of aborted transactions rises. This is expected, since the protocol in effect implements a variant of optimistic concurrency control, that is known to result in aborts under high contention. There are strategies for dealing with this in the distributed systems literature, such as locking objects in some conventional order—however none is immediately applicable to the byzantine setting.

§ COMPARISONS WITH RELATED WORK

Bitcoin's underlying blockchain technology suffers from scalability issues: with a current block size of 1MB and 10 minute inter-block interval, throughput is capped at about 7 transactions per second, and a client that creates a transaction has to wait for about 10 minutes to confirm. In contrast, mainstream payment processing companies like Visa confirm transactions within a few seconds, and have high throughput of 2000 transactions per second on average, peaking up to 56,000 transactions per second [38]. Reparametrization of —such as —can improve this to a limited extent up to 27 transactions per second and 12 second latency, respectively [7]. More significant improvement requires a fundamental redesign of the blockchain paradigm.

The most comparable system to is  [17]—that was developed concurrently—and provides a scalable distributed ledger for a cryptocurrency, and cannot support generic smart contracts. assigns nodes (selected using a Sybil-attack resistant mechanism) into shards among which state, representing coins, is split. The node-to-shard assignment is done every epoch using a bias-resistant decentralized randomness protocol [34] to prevent an adversary from compromising individual shards. A block-DAG (Directed Acyclic Graph) structure is maintained in each shard rather than a single blockchain, effectively creating multiple blockchains in which consensus of transactions can take place in parallel. Nodes within shards reach consensus through the Practical Byzantine Fault Tolerant (PBFT) protocol [8] with  [16]'s modifications that enable $O(n)$ messaging complexity. In contrast, uses 's PBFT implementation [33] as a black box, and inherits its $O(n^2)$ messaging complexity—however, can be replaced with any improved PBFT variant without breaking any security assumptions.

Similar to , uses an atomic commit protocol to process transactions across shards. However, it uses a different, client-driven approach to achieve it. To commit a transaction, the client first sends the transaction to the network. The leader of each shard that is responsible for the transaction inputs (input shard) validates the transaction and returns a proof-of-acceptance (or proof-of-rejection) to the client, and inputs are locked. To unlock those inputs, the client sends proof-of-accepts to the output shards, whose leaders add the transaction to the next block to be appended to the blockchain. In case the transaction fails the validation test, the client can send proof-of-rejection to the input shards to roll back the transaction and unlock the inputs. To avoid denial-of-service, the protocol assumes that clients are incentivized to proceed to the Unlock phase. Such incentives may exist in a cryptocurrency application, where coin owners only can spend them, but do not hold for a generalized platform like where objects may have shared ownership. Hence, 's atomic commit protocol has the entire shard—rather than a single untrusted client—act as a coordinator. Other related works include improvements to Byzantine consensus for reduced latency and decentralization [5, 24, 36], but these do not support sharding.

[22] scales by partitioning nodes in the network into a hierarchy of committees, where each committee is responsible for managing a subset (shard) of transactions consistently through PBFT. A final committee collates sets of transactions received from committees into a final block and then broadcasts it. At the end of each epoch, nodes are reassigned to committees through proof-of-work. The block throughput scales up almost linear to the size of the network. However, cannot process multi-shard transactions.

[12] is a permissioned blockchain. The central bank controls all monetary supply, while mintettes (nodes authorized by the bank) manage subsets of transactions and coins.

Like , communication between mintettes takes place indirectly, through the client—and also relies on the client to ensure completion of transactions. has low communication overhead, and the transaction throughput scales linearly with the number of mintettes, but cannot support generic smart contracts.

Some systems improve transaction latency by replacing its probabilistic guarantees with strong consistency.
[16] extends for high transaction throughput.

A consensus group is organized into a communication tree where the most recent miner (the leader) is at the root. The leader runs an $O(n)$ variant of PBFT (using CoSI) to get all members to agree on the next microblock. The outcome is a collective signature that proves that at least two-thirds of the consensus group members witnessed and attested the microblock. A node in the network can verify in $O(1)$ that a microblock has been validated by the consensus group. PeerConsensus [13] achieves strong consistency by allowing previous miners to vote on blocks. A Chain Agreement tracks the membership of identities in the system that can vote on new blocks.  [26] replaces proof-of-work with strong consistency by proposing a faster graded Byzantine fault tolerance protocol, that allows for a set of nodes to decide on the next block. A key aspect of Algorand is that these nodes are selected randomly using algorithimic randomness based on input from previously generated blocks. However, none of those systems are designed to support generic smart contracts.

Some recent systems provide a transparent platform based on blockchains for smart contracts.  Hyperledger Fabric [6] is a permissioned blockchain to setup private infrastructures for smart contracts. It is designed around the idea of a `consortium' blockchain, where a specific set of nodes are designated to validate transactions, rather than random nodes in a decentralized network. Each smart contract (called chaincode) has its own set of endorsers that re-execute submitted transactions to validate them. A consensus service then orders transactions and filters out those endorsed by too few. It uses modular consensus, which is replaceable depending on the requirements (e.g., Apache Kafka or SBFT).

Ethereum [39] provides a decentralized Turing-complete virtual machine, called EVM, able to execute smart-contracts. Its main scalability limitation results from every node having to process every transaction, as Bitcoin. On the other hand, 's sharded architecture allows for a ledger linearly scalable since only the nodes concerned by the transaction—that is, managing the transaction's inputs or references—have to process it. Ethereum plans to improve scalability through sharding techniques [2], but their work is still theoretical and does not provide any implementation or measurements. One major difference with is that Ethereum's smart contract are executed by the node, contrarily to the user providing the outputs of each transaction. also supports smart contracts written in any kind of language as long as checkers are pure functions, and there are no limitations for the code creating transactions. Some industrial systems [37, 32, 9] implement similar functionalities as , but without any empirical performance evaluation.

In terms of security policy, system implements a platform that enforces high-integrity by embodying a variant of the Clark-Wilson [10], proposed before smart contracts were heard of.

§ CONCLUSIONS

We presented the design of —an open, distributed ledger platform for high-integrity and transparent processing of transactions. offers extensibility though privacy-friendly smart contracts. We presented an instantiation of by parameterizing it with a number of `system' and `application' contracts, along with their evaluation. However, unlike existing smart-contract based systems such as Ethereum [39], it offers high scalability through sharding across nodes using a novel distributed atomic commit protocol called , while offering high auditability. We presented implementation and evaluation of on a real cloud-based testbed under varying transaction loads and showed that 's transaction throughput scales linearly with the number of shards by up to 22 transactions per second for each shard added, handling up to 350 transactions per second with 15 shards.  As such it offers a competitive alternative to both centralized and permissioned systems, as well as fully peer-to-peer, but unscalable systems like Ethereum.

Acknowledgements. George Danezis, Shehar Bano and Alberto Sonnino are supported in part by EPSRC Grant EP/M013286/1 and the EU H2020 DECODE project under grant agreement number 732546. Mustafa Al-Bassam is supported by a scholarship from The Alan Turing Institute. Many thanks to Daren McGuinness and Ramsey Khoury for discussions about the design.

[1]
Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, and Jens Groth.
Efficient zero-knowledge proof systems.
In Foundations of Security Analysis and Design VIII, pages
1–31. Springer, 2016.

[2]
Vitalik Buterin, Jeff Coleman, and Matthew Wampler-Doty.
Notes on scalable blockchain protocols (verson 0.3.2), 2015.

[3]
Philip A Bernstein, Vassos Hadzilacos, and Nathan Goodman.
CONCURRENCY CONTROL AND RECOVERY IN DATABASE SYSTEMS.
Addison- Wesley, 1987.

[4]
Alysson Bessani, João Sousa, and Eduardo E. P. Alchieri.
State machine replication for the masses with bft-smart.
In Proceedings of the 2014 44th Annual IEEE/IFIP International
Conference on Dependable Systems and Networks, DSN '14, pages 355–362,
Washington, DC, USA, 2014. IEEE Computer Society.

[5]
Ethan Buchman.
Tendermint: Byzantine fault tolerance in the age of blockchains.
Jun 2016.
Accessed: 2017-02-06.

[6]
Christian Cachin.
Architecture of the hyperledger blockchain fabric.
In Workshop on Distributed Cryptocurrencies and Consensus
Ledgers, 2016.

[7]
Kyle Croman, Christian Decker, Ittay Eyal, Adem Efe Gencer, Ari Juels, Ahmed
Kosba, Andrew Miller, Prateek Saxena, Elaine Shi, and Emin Gün.
On scaling decentralized blockchains.
In 3rd Workshop on Bitcoin and Blockchain Research, Financial
Cryptography 16, 2016.

[8]
Miguel Castro, Barbara Liskov, et al.
Practical byzantine fault tolerance.
In OSDI, volume 99, pages 173–186, 1999.

[9]
Corda: A distributed ledger.
2017 (visited August 9, 2017).

[10]
David D Clark and David R Wilson.
A comparison of commercial and military computer security policies.
In Security and Privacy, 1987 IEEE Symposium on, pages
184–184. IEEE, 1987.

[11]
George Danezis, Jens Groth, C Fournet, and Markulf Kohlweiss.
Square span programs with applications to succinct nizk arguments.
Springer Berlin Heidelberg, 2014.

[12]
George Danezis and Sarah Meiklejohn.
Centrally banked cryptocurrencies.
In Network and Distributed System Security. The Internet
Society, 2016.

[13]
Christian Decker, Jochen Seidel, and Roger Wattenhofer.
Bitcoin meets strong consistency.
In Proceedings of the 17th International Conference on
Distributed Computing and Networking, ICDCN '16, pages 13:1–13:10, New
York, NY, USA, 2016. ACM.

[14]
Jim Gray and Leslie Lamport.
Consensus on transaction commit.
ACM Transactions on Database Systems (TODS), 31(1):133–160,

[15]
Marek Jawurek, Martin Johns, and Florian Kerschbaum.
Plug-in privacy for smart metering billing.
In Privacy Enhancing Technologies - 11th International
Symposium, PETS 2011, Waterloo, ON, Canada, July 27-29, 2011. Proceedings,
pages 192–210, 2011.

[16]
Eleftherios Kokoris Kogias, Philipp Jovanovic, Nicolas Gailly, Ismail Khoffi,
Linus Gasser, and Bryan Ford.
Enhancing bitcoin security and performance with strong consistency
via collective signing.
In 25th USENIX Security Symposium (USENIX Security 16), pages
279–296, Austin, TX, 2016. USENIX Association.

[17]
Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly,
and Bryan Ford.
Omniledger: A secure, scale-out, decentralized ledger.
IACR Cryptology ePrint Archive, 2017:406, 2017.

[18]
Leslie Lamport et al.
Paxos made simple.
ACM Sigact News, 32(4):18–25, 2001.

[19]
Shengyun Liu, Christian Cachin, Vivien Quéma, and Marko Vukolic.
Xft: practical fault tolerance beyond crashes.
CoRR, abs/1502.05831, 2015.

[20]
Butler Lampson and David B Lomet.
Distributed transaction processing using two-phase commit protocol
with presumed-commit without log force, August 2 1994.
US Patent 5,335,343.

[21]
Ben Laurie, Adam Langley, and Emilia Kasper.
Certificate transparency.
Technical report, 2013.

[22]
Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, and
Prateek Saxena.
A secure sharding protocol for open blockchains.
In Proceedings of the 2016 ACM SIGSAC Conference on Computer and
Communications Security, CCS '16, pages 17–30, New York, NY, USA, 2016.

[23]
Luc Lauwers and Marleen Willekens.
Five hundred years of bookkeeping: a portrait of luca pacioli.
Tijdschrift voor Economie en Management, 39(3):289–304, 1994.

[24]
David Mazieres.
The stellar consensus protocol: A federated model for internet-level
Accessed: 2016-08-01.

[25]
Ian Miers, Christina Garman, Matthew Green, and Aviel D Rubin.
Zerocoin: Anonymous distributed e-cash from bitcoin.
In Security and Privacy (SP), 2013 IEEE Symposium on, pages
397–411. IEEE, 2013.

[26]
Silvio Micali.
Algorand: The efficient and democratic ledger.
http://arxiv.org/abs/1607.01341, 2016.
Accessed: 2017-02-09.

[27]
Trent McConaghy, Rodolphe Marques, Andreas Müller, Dimitri De Jonghe, Troy
McConaghy, Greg McMullen, Ryan Henderson, Sylvain Bellemare, and Alberto
Bigchaindb: a scalable blockchain database.
white paper, BigChainDB, 2016.

[28]
Satoshi Nakamoto.
Bitcoin: A peer-to-peer electronic cash system.

[29]
Torben P Pedersen et al.
Non-interactive and information-theoretic secure verifiable secret
In Crypto, volume 91, pages 129–140. Springer, 1991.

[30]
<https://github.com/gdanezis/petlib>, 2017 (version July 20,

[31]
Alfredo Rial and George Danezis.
Privacy-preserving smart metering.
In ISSE 2012 - Securing Electronic Business Processes,
Highlights of the Information Security Solutions Europe 2012 Conference,
Brussels, Belgium, October 23-24, 2012, pages 105–115, 2012.

[32]
<http://www.rsk.co>, 2017 (visited August 9, 2017).

[33]
João Sousa and Alysson Bessani.
From byzantine consensus to bft state machine replication: A
latency-optimal transformation.
In Proceedings of the 2012 Ninth European Dependable Computing
Conference, EDCC '12, pages 37–48, Washington, DC, USA, 2012. IEEE Computer

[34]
Ewa Syta, Philipp Jovanovic, Eleftherios Kokoris-Kogias, Nicolas Gailly,
Linus Gasser, Ismail Khoffi, Michael J. Fischer, and Bryan Ford.
Scalable bias-resistant distributed randomness.
IACR Cryptology ePrint Archive, 2016:1067, 2016.

[35]
Jerome H Saltzer, David P Reed, and David D Clark.
End-to-end arguments in system design.
ACM Transactions on Computer Systems (TOCS), 2(4):277–288,

[36]
David Schwartz, Noah Youngs, and Arthur Britto.
The ripple protocol consensus algorithm.
<https://ripple.com/files/ripple_consensus_whitepaper.pdf>, 2014.
Accessed: 2016-08-08.

[37]
Tezos – a self-amending crypto-ledger.
<https://www.tezos.com/static/papers/position_paper.pdf>, 2017
(visited August 9, 2017).

[38]
How a Visa transaction works.

[39]
Gavin Wood.
Ethereum: A secure decentralised generalised transaction ledger.
Ethereum Project Yellow Paper, 151, 2014.

The system supports user-defined smart contracts that encode the business logic of specific applications. Those smart contracts are represented as objects – with all rules around their valid status applying – that are managed within . They contain code defining data structures for objects associated with the contract, as well as procedures defining transactions associated with the contract.

Overall, each contract defines a name space, of object types and procedures defining transaction types, and associates with each transaction a `checker' that may be used to validate the transaction correctness. All objects and transactions that are part of a contract must have a reference to the contract object. Since new transactions need to point to have valid references, this also implies that the contract object must be active for new transactions within the contract to be valid. At the time of creation a contract may also create other initial state, in the form of objects, that is part of the contract. Those objects are outputs of the transaction that creates the contract within the system.

The logic of a contract is encoded in procedures defining transactions, and checkers for those transactions. Those checkers mirror the transaction procedures, in that they accept a list of objects, references, and calling arguments and a list of new objects generated by the transaction. They simply return a Boolean stating whether the transaction is valid, as part of the contract, or not. Therefore the smart contract defines checkers for each transaction within the contract, and it is the responsibility of the clients submitting the transaction to ensure all the inputs passed into the checker for a transaction would yield a valid execution according to the checker. The checkers for smart contracts must be pure functions, in that they are deterministic in their inputs, and do not cause any side effects. However, this assumption may be relaxed, if verification only needs to hold against a small subset of corrupt peers.

Special transactions may be provided as part of a contract that accept some calling parameters, and generate an object within the contract. Those may be used to generate new objects within the realm of a smart contract. However, for the purposes of ensuring all object identifiers are distinct we require all transactions to accept at least one object as an input.

Finally, smart contracts may call procedures in other smart contracts. However the objects of other smart contracts are opaque to them, and cannot be consumed or created directly by a smart contract within a different name space, but only through procedures defined in the original smart contract.

We briefly motivate the dichotomy between the definitions of smart contract procedures, that take inputs and references and generate outputs; and the associated checkers for those procedures, which take the procedure name, the inputs, references and outputs and simply return whether the transaction is valid. In the case all data necessary for the creation of a transaction is public, the checker associated with the transaction can simply be re-run the transaction procedure, and check that the outputs produced are those reported.

However, in case secrets are necessary to generate transactions, the checker needs to perform a fundamentally different operation then the procedure that generates a valid transaction. The simplest instance of this, is a procedure that relies on a digital signature scheme to generate valid signature authorizing the use of an object, on the basis of a secret signature key. The checker for such a procedure, instead of signing using a secret signature key, would simply verify the signatures using the signature verification function, and the associated verification key instead.

Defining smart contract logic as `checkers' also allows to support privacy friendly-contracts. In such contracts some information in objects is not in clear, but instead either encrypted using a public key, or committed using a secure commitment scheme <cit.>. Then the transaction may simply be valid proof that the logic or invariants of the smart contract procedure were applied correctly or hold respectively, and can take the form of a zero-knowledge (ZK) proof, or a Succinct Argument of Knowledge (SNARK). The checker then simply runs the verifier part of the ZK or SNARK protocol that validates the invariants of the transactions, without revealing the secrets within the objects to the verifiers.

§.§ Transaction Batching & Smart Contract Composition

supports the batching of multiple transactions, and their joint submission into the system. The batch of transactions is executed atomically – either all of them are accepted or none. Batching may be used to increase performance, by allowing clients to do a lot of work constructing transactions off-line, and committing them all at once. Batching also forms the basis for smart contract composition, which allows one smart contract checker to call with specific parameters, and rely upon returned values from transactions of other smart contracts.

Composition of smart contracts is a key feature of a transparent and auditable computation platform. It allows the creation of a library of smart contracts that act as utilities for other higher-level contracts: for example, a simple contract can implement a cryptographic currency, and other contracts – for e-commerce for example – can use this currency as part of their logic. Furthermore, we use the ability to compose smart contracts, in order to build some of the functionality of itself as a set of `system' smart contracts, including auditing, management of shards mapping to nodes, key management of shard nodes, and governance.

A batch of transactions $\bar{T}$ is composed by a sequence of atom transactions, each with their own checker function, input, references, outputs and local parameters. The usual rules apply for each of the transactions that form the batch: any input object may only be used once, and then becomes inactive; all transactions much take at least one input object; and on the basis of their individual parameters they must all by valid. In order to enable composition we provide the checker of each of the individual transactions, the full batch, and allow the checker to query whether a tuple representing a full transaction is in the batch, namely:

\begin{align}
(f, o_i \ldots o_{i'}, r_j \ldots r_{j'}, o_k \ldots o_{k'}, \mathsf{local},  o_k \ldots o_{k'}) \in \bar{T}
\end{align}

We note that this is the only operation a checker may perform on objects of a different contract. In particular inputs, references and output objects not belonging to the name space of the checker are opaque and not direct information about them may be gained. However, the information about local parameters and local returns in the $\mathsf{locals}$ can be accessed by other checkers – and this is the main vehicle by which contract may emulate calls to other contracts, and read information about objects of other contracts. Thus provides encapsulation of the object's state, that may only be mutated or read through well defined smart contract procedures, and verified by their checkers.

We need a final validity constraint on the set of transactions: namely that a transaction reference object, may only be used as part of a transaction if it was not an input to any previous transaction in the batch. Furthermore, a transaction output object in the batch may only be an input or a reference to a subsequent transaction in the batch (but not a previous one). This ensures a serializable execution of the transaction batch is possible, and provided by the creator of the batch – thus the need to order transactions in the batch.

We call a transaction batch Valid is all transactions that it is composed of are individually valid, on the basis of their inputs, references, outputs and local – and if the usual contrast describe above (single use of inputs, and at least one input per transaction, serializability) hold. It is the responsibility of each checker to ensure that `calls' to other transactions it relies on are included in the batch with the expected local parameters and returns.

When judging the validity of a batch not all shards involved in the validation of the batch need to check all transaction. Each shard only needs to check the transactions within the batch concerning procedures of contracts for which they manage objects. Thus is a shard manages object $o_1$ from contract $c$ that is an input or reference to the batch, it only needs to check the all the transactions in the batch from contract $c$. We note that there are always concerned shards that manage all contracts represented in a batch: since we restrict the contract calls to only takes objects of types defined with contracts, all transactions in a batch will be checked by at least one shard. This design choice allows for shards to be agnostic as to the logic of contracts relating to objects they do not manage – leading to locality and greater scalability.

As it is the case for single transactions, besides validity, all input and referenced objects relied upon by the batch must be active. However, to enable the batching of sequential transactions we need to define carefully what is the set of input objects of interest that need to be checked as active, and which should become inactive if the batch is processed by the system. We define the set $\bar{o}$ of batch inputs as the set defined by the union of all transaction inputs minus the set defined by the union of all transaction outputs. This ensures that the any objects relied upon by this transaction, that are not generated by the transaction itself, are active in order to execute it; and are turned inactive after its execution. Similarly, we define as the set $\bar{r}$ of batch references, the union of all references of transactions minus the set of all transaction outputs. This ensures all references that are not internal to the transaction need to be active to execute the transaction. Finally, we define as the output set of the batch the set $\bar{o}$ defined as the union of all outputs of all transactions minus the union of all inputs to all transactions. These are in effect the new objects created by the transaction, and not consumed by itself.

We note that objects that are internally created and also consumed by transactions in a batch are not materialized in any way in their respective shards, and thus no records are made of them being active, or inactive. This is safe due to the construction of the identifiers of objects as part of the Object-DAG, that ensures that all identifiers are fresh and collision resistant. It is also safe since shards managing objects of each contract represented in the batch have to be involved in the checking of the transaction, and thus can be relied upon to check and ensure the integrity and constraints relating to the intermediate objects.