Daniele E Asoni

Chen Chen

David Barrera

Adrian Perrig

On Building Onion Routing into Future Internet Architectures

User privacy on the Internet has become a pressing concern in recent years largely due to the revelations of large scale network surveillance programs. Research initiatives around future Internet architectures (FIAs) offer a unique opportunity to integrate privacy protection measures into the architecture of the network itself. In this paper, we survey the main design challenges of network layer onion routing protocols in FIAs. We empirically investigate the requirements and trade-offs of different design choices. Our goal is to identify promising research directions and incentivize further exploration of the field.

Introduction

Recent revelations about global-scale pervasive surveillance [START_REF] Farrell | Pervasive Monitoring Is an Attack[END_REF] programs have demonstrated that Internet users' privacy is severely threatened. These revelations suggest massive amounts of private traffic, including web browsing activities, location information, and personal communications are being harvested in bulk by domestic and foreign intelligence agencies. In response to these threats, an increasing number of privacyconcerned users are resorting to anonymity tools and services. The state-of-the-art solutions today are onion routing systems (most notably Tor [START_REF] Dingledine | Tor: The Second-Generation Onion Router[END_REF]), which try to strike a balance between privacy and performance, enabling low-latency anonymous communication suitable for typical Internet activities (e.g., web browsing and instant messaging). Many of these systems work on top of the Internet as overlay networks: they rely on a number of servers, typically provided and run by volunteers, which anonymize user traffic by relaying it across the network a number of times. While these systems are gaining popularity, the active number of users still represents only a small fraction of the entire Internet population, partly because of these systems' limitations in terms of latency and scalability.

In recent years, to overcome the performance and scalability limitations of traditional anonymity systems, researchers have explored a new approach: building anonymity systems directly into the network architecture [START_REF] Hsu | LAP: Lightweight anonymity and privacy[END_REF][START_REF] Sankey | Dovetail: Stronger anonymity in next-generation internet routing[END_REF][START_REF] Dibenedetto | ANDaNA : Anonymous Named Data Networking Application[END_REF][START_REF] Liu | Tor instead of IP[END_REF][START_REF] Chen | HORNET: High-speed Onion Routing at the Network Layer[END_REF]. Instead of relying on volunteer-run servers, these proposals require Internet routers to perform traffic anonymization in addition to their typical packet forwarding operations. Current research in Future Internet Architectures (FIAs) [START_REF] Godfrey | Pathlet routing[END_REF][START_REF] Zhang | Named data networking[END_REF][START_REF] Zhang | SCION: Scalability, Control, and Isolation on Next-Generation Networks[END_REF] gives the opportunity to concretely plan for and evaluate this paradigm shift.

Research on network-layer anonymity systems is still in its infancy. Only a small fraction of the design space has been explored so far, and many of the important challenges and design decisions in the field have not been analyzed in detail. This paper aims to help fill this gap by identifying the main problems that arise when designing such systems, and by analyzing the trade-offs brought by those design choices.

The remainder is organized as follows. Section 2 gives background about traditional anonymity systems, FIAs, and recent network-layer anonymity systems based on FIAs. In Section 3, we discuss the necessary considerations when defining a threat model for onion routing systems at the network layer, showing how performance requirements and the network topology itself bound the privacy guarantees that such systems can provide. In Section 4 we present a set of design challenges and propose possible solutions as well as potential research directions. We conclude in Section 5.

Background and Related Work

Network-layer anonymity systems are usually an adaptation of traditional overlay anonymity systems. Thus, many of the fundamental concepts remain the same in both types of systems. For this reason we begin by presenting the traditional systems, in particular focusing on mix networks and onion routing. We then describe relevant FIA-based proposals, and finally present recent research on network-layer anonymity systems.

Traditional Anonymity Systems

The first system designed to enable anonymous communication over the Internet was proposed by Chaum in 1981 [START_REF] David | Untraceable electronic mail, return addresses, and digital pseudonyms[END_REF]. The main idea in this system is as follows: an end-host (the source) wishing to communicate anonymously with another end-host (the destination) chooses a sequence of servers (generically called nodes) that will relay the traffic. We call this sequence a path. Additionally, the source encrypts each message it sends multiple times in such a way that every node on the path will be able to remove one layer of encryption, until the final node (or the destination) obtains the original message. This technique is called onion encryption. Since messages look different (as a result of encryption or decryption) before and after being processed by a node, and under the assumption that many users will send messages through the system, it is nontrivial for the adversary to trace messages and thus to de-anonymize the communicating parties.

Chaum's design also includes batching and mixing of messages at every node, which increase the difficulty for an adversary to trace those messages across the network. For this reason Chaum's system, and others that are based on the same principles [START_REF] Gülcü | Mixing Email with Babel[END_REF][START_REF] Danezis | Mixminion: Design of a Type III Anonymous Remailer Protocol[END_REF][START_REF] Danezis | Sphinx: A Compact and Provably Secure Mix Format[END_REF], are called mix networks or mix-nets. These systems typically do on-thefly key establishment for every message using the long-term public keys of the nodes on the path. Key negotiations, together with batching and mixing, make mix-nets very slow, and thus suitable only for latency-tolerant applications like email.

The other important category of anonymity systems, which derives from mix-nets, is that of onion routing systems. The main examples are Tor [START_REF] Dingledine | Tor: The Second-Generation Onion Router[END_REF], I2P [START_REF] Zantout | I2P data communication system[END_REF] and Jon-Donym [22,[START_REF] Federrath | ON -Privacy protection on the Internet[END_REF]. These systems also use onion encryption, but they typically do not perform mixing or batching to avoid the performance penalty. They also create circuits (also called tunnels or sessions), i.e., they establish shared keys with each node on the path, and then use these keys to send many messages/packets over the same path. The overall speed of onion routing systems means that, unlike mix-nets, they can be used for applications like web browsing and instant messaging. The drawback of these systems is that they provide weaker security guarantees, which are typically expressed by considering threat models with more limited adversaries.

Likely due to their low latency, (circuit-based) onion routing systems are the most used anonymous networks today. Furthermore, the network-layer anonymity systems described in Section 2.3 are also mostly based on onion routing.

Future Internet Architectures

In response to the problems that the current Internet is facing, a number of research initiatives were started with the goal of defining new network architectures for the nextgeneration Internet [START_REF] Pan | A survey of the research on future internet architectures[END_REF]. As research in re-defining the Internet is still ongoing, there is an opportunity to integrate support for privacy-enhancing technologies into the network architecture itself. Some of the new architectures that have been proposed already include features which can be leveraged by anonymity networks (though the reason for their inclusion in the design lies strictly in networking aspects). In particular, some of these FIAs grant the end hosts a certain degree of control over the path that their traffic takes to traverse the network [START_REF] Yang | NIRA: a new inter-domain routing architecture[END_REF][START_REF] Godfrey | Pathlet routing[END_REF][START_REF] Zhang | SCION: Scalability, Control, and Isolation on Next-Generation Networks[END_REF]. Control, or at least knowlege of the path, is typically offered at the granularity of Autonomous Systems (ASes) or Internet Service Providers (ISPs). Control and visibility of network paths is a fundamental property leveraged by network-layer onion routing systems, with the main realization being that intermediate ISPs and/or ASes can act as nodes to perform traffic anonymization. Assuming that the ISPs and ASes have public cryptographic keys that can be obtained and verified by the source, it is even possible for the source to negotiate keys with the nodes on the path to perform cryptographic operations on packets, (e.g., onion encryption [START_REF] Chen | HORNET: High-speed Onion Routing at the Network Layer[END_REF]).

Network-Layer Anonymity Systems

The most practical and most used anonymity systems today are onion routing systems. However, application-layer overlay networks, on which today's onion routing systems are based, have inherent performance limitations. First, since each hop can traverse the entire network, the total propagation delay can be high. Second, the end hosts' network stacks add substantial processing and queuing delay [START_REF] Dingledine | Performance Improvements on Tor or, Why Tor is slow and what we're going to do about it[END_REF]. Finally, compared to ISP infrastructure, volunteer-run nodes typically offer only low to medium throughput [30].

Recent works have proposed to address the performance limitation of onion routing systems by building anonymity systems into the network layer [START_REF] Hsu | LAP: Lightweight anonymity and privacy[END_REF][START_REF] Sankey | Dovetail: Stronger anonymity in next-generation internet routing[END_REF][START_REF] Dibenedetto | ANDaNA : Anonymous Named Data Networking Application[END_REF][START_REF] Liu | Tor instead of IP[END_REF][START_REF] Chen | HORNET: High-speed Onion Routing at the Network Layer[END_REF]. LAP [START_REF] Hsu | LAP: Lightweight anonymity and privacy[END_REF] and Dovetail [START_REF] Sankey | Dovetail: Stronger anonymity in next-generation internet routing[END_REF] (so-called lightweight systems) hide end hosts' network locations by concealing routing information. However, in these two protocols, packets remain unchanged as they traverse the network, making both schemes vulnerable to trivial packet matching attacks. In contrast, Tor instead of IP [START_REF] Liu | Tor instead of IP[END_REF] and HORNET [START_REF] Chen | HORNET: High-speed Onion Routing at the Network Layer[END_REF] advocate performing onion routing at the network layer, where Internet Service Providers (ISPs) assume the role of onion relays and support per-hop high-speed onion encryption/decryption. We note that an important difference (and limitation) of network-layer anonymity system compared to overlay systems is that in the former the nodes typically only forward traffic to adjacent nodes. In overlay anonymity networks, on the other hand, it is assumed that each node can communicate with any other node. In Section 3 we show the limitations that this difference entails.

As discussed in Section 2.2, we assume that the network architecture provides end hosts with information about the network and the paths, which is a fundamental requirement of many of these network-layer anonymity systems. However, it is worth noting that LAP [START_REF] Hsu | LAP: Lightweight anonymity and privacy[END_REF] differs from the other proposed schemes in this respect, as it does not require path information to be known to the source. The reason LAP does not rely on this assumption is that its privacy guarantees are weak: the source has no control over whether its traffic is truly anonymized, and has to fully trust its ISP. We discuss anonymity guarantees in the next section.

Threat Model Considerations

Traditionally, high-latency mix systems [START_REF] David | Untraceable electronic mail, return addresses, and digital pseudonyms[END_REF] consider powerful Dolev-Yao adversaries (i.e., adversaries that control the entire network), and typically try to guarantee the highest degree of anonymity. Defining a threat model that is as clear for low-latency onion routing systems is generally more difficult. Low-latency schemes are unable to defend against Dolev-Yao adversaries, and almost any observation of the network increases the knowledge of the adversary, thereby affecting anonymity. This means that the definition of anonymity needs to be quantitative [START_REF] Backes | AnoA: A Framework For Analyzing Anonymous Communication Protocols[END_REF], and this is a challenging task as it requires an analysis of the actual network topology and the entities involved. For this reason even the most popular anonymity systems provide only some approximate notion of what an adversary is allowed to do, and what guarantees the system provides for its users [START_REF] Dingledine | Tor: The Second-Generation Onion Router[END_REF]. For network-layer anonymity systems these challenges remain, but additional elements must be considered.

Performance constraints. First, it is important to note that performance is a primary goal for network-layer low-latency anonymity systems. This implies, for example, that performing cryptographic operations on the packet should not constitute a bottleneck that limits a node's throughput. Some of the proposed lightweight schemes [START_REF] Hsu | LAP: Lightweight anonymity and privacy[END_REF][START_REF] Sankey | Dovetail: Stronger anonymity in next-generation internet routing[END_REF] lower the anonymity guarantees significantly in order to achieve better performance and scalability (see Figure 1), by considering a weak threat model in which at most one node can be compromised. HORNET [START_REF] Chen | HORNET: High-speed Onion Routing at the Network Layer[END_REF], an onion routing systems, tries to raise the bar, preserving user anonymity against more powerful adversaries, but has to sacrifice some performance. Unlike LAP and Dovetail, HORNET requires an initial circuit setup which involves expensive asymmetric cryptography operations, and data packets need to be fully onion encrypted/decrypted at each node. While the loss in performance is a clear downside of such a scheme, it appears to be unavoidable if the goal it to protect against stronger (and arguably more realistic) adversaries.

Topology constraints. Another important aspect of network-layer protocols is that they are constrained by the network topology and the business relations between network entities. This reduces the anonymity guarantees that such systems can provide [START_REF] Chen | HORNET: High-speed Onion Routing at the Network Layer[END_REF], as sources are not free to choose arbitrary paths traversing the network (a property explicitly enabled by overlay systems). For example, in the extreme case where the source and destination are in the same ISP, complete de-anonymization is trivial if the ISP is malicious. This shows one of the important challenges in the definition of the threat model: typically low-latency anonymity systems require that an adversary should not be able to observe both source and destination. However, for a variety of reasons a user many not trust its own ISP, so in such cases the system does not provide any guarantees. 1Trust assumptions. Traditional onion routing protocols typically use secure channels between nodes to protect against eavesdroppers. Tor, for instance, specifies TLS connections to transmit data between pairs of relays. At the network layer, an equivalent security mechanism would be some form of link encryption (e.g., IPsec [START_REF] Seo | Architecture for the Internet Protocol[END_REF]). In HOR-NET, the authors argue that link encryption may not be required under all network settings and for all adversaries. The reasoning is that if the threat model considers an adversary that can legally get access to the communication links, then the same adversary may be able to coerce ISPs into handing over all encryption keys, which would make link encryption pointless. However, should the threat model be different, it could be beneficial to use link encryption. One such case would be if multiple links between nodes, usually considered separate, all traverse a single Internet exchange Point (IXP) [START_REF] Johnson | Users get routed: traffic correlation on Tor by realistic adversaries[END_REF]. This example shows the importance of the threat model definition, which directly influences the design decisions.

Trade-offs and Challenges in the Design Space

We now analyze some of the main design questions and challenges that arise when building onion routing systems at the network layer. While most of the items below concern performance, some of these design decisions also depend on the chosen threat model (see Section 3) and expected security guarantees.

Stateful vs. Stateless Node Design

To process and forward a packet, onion routing relays require state including cryptographic keys and routing information. In Tor, each relay node maintains the state for all the circuits traversing the relay. Given the high throughput and the limited amount of high-speed memory on routers, a stateful relay-node design creates scalability problems. We estimate, based on packet traces of an edge router [START_REF]CAIDA UCSD Anonymized Internet Traces[END_REF], that a router with 100 Gb/s would need around 20 GB of state if all flows traversing through that router were Tor flows.

The ever decreasing costs of memory hardware might overcome the problem in the long term, but we note that to achieve high performance, routers need specialized highspeed memory, whose cost is higher than system memory. Furthermore, stored state is always a challenge for parallelization: if multiple cores need to access the same state, there are synchronization problems, and caching becomes less effective; if multiple machines need to access the same state, the state needs to be replicated. Hence, to mitigate such scalability problems in a stateful design, ISPs must either equip routers with a large high-speed memory, or carefully conduct load-balancing to delegate the state across multiple routers.

The diametrically opposed design choice is a stateless relay design, where each packet carries the necessary state embedded in its header [START_REF] Hsu | LAP: Lightweight anonymity and privacy[END_REF][START_REF] Sankey | Dovetail: Stronger anonymity in next-generation internet routing[END_REF][START_REF] Chen | HORNET: High-speed Onion Routing at the Network Layer[END_REF]. However, the stateless design requires large packet headers, reducing the effective throughput; it also requires cryptographic schemes that protect packet-carried state from tampering, and prevent it from leaking information about end hosts. This leads to more complex designs which require additional cryptographic operations and whose security is more difficult to analyze (cf. the simplicity of Tor [START_REF] Dingledine | Tor: The Second-Generation Onion Router[END_REF], which is stateful, with more complex design of HORNET [START_REF] Chen | HORNET: High-speed Onion Routing at the Network Layer[END_REF], which is stateless).

Transport Control

Tor guarantees lossless and in-order delivery of packets by using reliable transport between neighboring relays. Although this scheme (based on TLS) enables the detection of malicious packet modification, replay, or dropping, it introduces a high overhead due to additional processing and queuing2 [START_REF] Geddes | IMUX: Managing Tor connections from two to infinity, and beyond[END_REF]. In comparison, protocols without reliable per-hop transport control [START_REF] Hsu | LAP: Lightweight anonymity and privacy[END_REF][START_REF] Sankey | Dovetail: Stronger anonymity in next-generation internet routing[END_REF][START_REF] Chen | HORNET: High-speed Onion Routing at the Network Layer[END_REF] can reach lower latency and high throughput, but they consider different (usually weaker) threat models.

Another disadvantage of having only end-to-end transport control is that the transport layer of the network stack is exposed to the remote endpoint. This can, for instance, allow a malicious destination to perform network stack fingerprinting (e.g., learn what operating system is running). Note, however, that regardless of the design, some part of the network stack is always exposed. For example, in Tor it is still possible to obtain information about the host at the application layer (e.g., HTTP).

Circuit Setup

Low-latency onion routing systems need to set up circuits, a process which typically involves asymmetric cryptographic operations. The established circuits are then used to forward traffic efficiently (i.e., using only symmetric key cryptography). Existing onion routing systems adopt one of two strategies for the circuit setup: telescopic setup and direct setup. The telescopic setup [START_REF] Dingledine | Tor: The Second-Generation Onion Router[END_REF] consists in the extension of the circuit one hop at a time, so that the key exchange with the i-th node is completed before the (i + 1)-th node is contacted. The telescopic setup guarantees forward secrecy, but imposes high communication latency (O(N 2 ), where N is the number of nodes on the path). Furthermore, this type of setup requires that the underlying FIA allow traffic to flow in both direction on all links, which might not always be the case [START_REF] He | On routing asymmetry in the Internet[END_REF].

The direct setup [START_REF] Chen | HORNET: High-speed Onion Routing at the Network Layer[END_REF] does not suffer from these drawbacks. In particular, the communication latency is linear in N, but it cannot provide forward secrecy. Whether this is acceptable or not depends on the threat model: if it is assumed that the adversary will not be able to compromise certain nodes in the future, then a direct setup can be used. Otherwise it is still possible to mitigate the impact of a future compromise by changing circuit setup keys regularly. It can be challenging, however, to distribute the new keys if they are changed frequently. We note that direct setup does not preclude the end hosts from establishing an end to end channel that guarantees forward secrecy for the contents of the communication.

Bootstrapping Anonymous Communication

A difficult and still open problem is how to bootstrap anonymous communications in future Internet architectures. A source needs certain information to set up circuits, which usually at least includes the address of the intended destination, of a path to that destination 3 , and of the public keys of the nodes on that path. The challenge lies in retrieving this information in an anonymity-preserving way, while still providing the scalability and low latency properties of the main anonymity protocol (see Section 3).

Overlay anonymity systems (for instance, Tor) have an advantage in this case, because any sequence of mixes/onion relays can be used to reach any destination. This allows a source to construct a circuit without risking potential de-anonymization, as the circuit should give the attacker no information about the intended destination. Once the circuit is established, the source can ask the last mix/onion relay to perform the destination lookup through the established circuit. For onion routing protocols at the network layer this scheme cannot be directly applied, as the circuits are constructed on network paths which leak information about the source's location and the intended destination. We point out that this problem affects also the lightweight anonymity systems LAP [START_REF] Hsu | LAP: Lightweight anonymity and privacy[END_REF] and Dovetail [START_REF] Sankey | Dovetail: Stronger anonymity in next-generation internet routing[END_REF].

The simplest solution would be to use an overlay system only for bootstrapping, and then switch to a network layer onion routing system for the actual anonymous communication. The drawback of such a scheme would be a higher delay before the circuit is established, which is a problem for usability. Furthermore, the most popular anonymity systems today support a few million users a day [30], but if network anonymity protocols are used by a more significant fraction of the Internet population there might be scalability issues [START_REF] Chen | HORNET: High-speed Onion Routing at the Network Layer[END_REF], so this option's feasibility requires further investigation.

Another possibility is to implement a broadcast mechanism which pushes all topology information (or a large part of it) to all users. Pathlet routing [START_REF] Godfrey | Pathlet routing[END_REF] might be used to achieve such a broadcasting system, as proposed by Sankey and Wright for Dovetail [START_REF] Sankey | Dovetail: Stronger anonymity in next-generation internet routing[END_REF]. It is unclear whether such a system would scale to the size of the Internet, especially considering that public keys and certificates would also need to be broadcast. A more plausible scheme could be based on the idea of Federrath et al. [START_REF] Federrath | Privacy-preserving DNS: Analysis of broadcast, range queries and mix-based protection methods[END_REF], which combines a broadcasting mechanism for popular destinations with an overlay system for the rest.

For completeness we mention that there are systems that allow private information retrieval (PIR) [START_REF] Chor | Private information retrieval[END_REF], which means that a client is able to obtain information from a database without the database server knowing what piece of information is being accessed. Such systems could be used to solve certain parts of the problem, for example retrieval of the destinations address. However, such schemes impose high computational burden on servers, and while there have been some applications to anonymous communications [START_REF] Mittal | Scalable Anonymous Communication with Provable Security[END_REF], these do not appear to be well suited for our purposes.

Hybrids between Network-Layer and Overlay Anonymity Systems

To mitigate the problem of topology constraints (Section 3), Sankey and Wright [START_REF] Sankey | Dovetail: Stronger anonymity in next-generation internet routing[END_REF] suggest that ISPs could deviate from the standard valley-freeness constraint 4 to allow some redirection. It is unclear, however, whether such a scenario would be deployable in practice, since it requires ISPs to use resources to forward traffic that is neither originating from, nor destined to, one of their clients. A similar, but more radical approach is to assume that a number of end hosts could act as proxies, and thus add an additional global redirection that would eliminate the problem. This approach is an example of combining network layer anonymity protocols with overlay systems, albeit with the drawback of increased in communication latency.

It may be desirable to allow the user (or software acting on the user's behalf) to select from a range of protocols for a specific connection. Such flexibility would allow clients to dynamically trade off performance and privacy as needed for each particular case and adversary. More research is needed to accurately classify protocols and connection types based on their performance and privacy guarantees.

Legal Issues and Deployment Incentives

To date, the research community has focused on the technical aspects of anonymity systems while largely neglecting the legal aspects and economical incentives for the entities who should deploy those systems. We argue that it is important to consider, at least at a high level, what legal obstacles network entities might face when trying to deploy anonymity systems, and what incentives these entities have for making such systems available to their customers. Indeed, even the most secure and high-performing system is pointless if it cannot be used, so it is worth considering these issues during technical protocol design.

ISPs may benefit from offering anonymity as a service to both their immediate subscribers and to subscribers of other ISPs, but ISPs must simultaneously comply with legal requirements (e.g., state-mandated data retention laws) to facilitate the investigation of criminal activity. A naive solution here is to build anonymity systems with so called "master keys" that ISPs or entities with judicial power can use to de-anonymize communicating parties. This approach, however, is prone to abuse which could lead to pervasive de-anonymization of all users.

A perhaps better-suited solution may be for ISPs to keep logs of users generating anonymous traffic, while not allowing the immediate de-anonymization of traffic. If legally compelled to de-anonymize traffic, the ISP can assist in recording anonymous traffic, possibly cooperating with neighboring ISPs. De-anonymization attempts can then be performed for specific points on the path.

The recently proposed cMix [START_REF] Chaum | cMix: Anonymization by high-performance scalable mixing[END_REF] system consists of a fixed sequence of mix nodes, and the authors suggest that each node could be run by a different nation: such a distributed system would guarantee that several legal domains must be involved and must agree on sharing information to de-anonymize single communications.

But while the technical community can find various options with different tradeoffs, lawmakers should decide the correct balance between the right to privacy and free speech, as well clearly define the role played by law enforcement in cases where anonymous networks are used. Recent work [START_REF] Minarik | Tor does not stink: Use and abuse of the Tor anonymity network from the perspective of law[END_REF] points out the need for further research on the legal questions that arise around anonymous communications. The sooner there is clarity on these matters, the sooner ISPs and other parties can decide whether to and how to invest into these technologies.

Conclusion

This paper has given an overview of the design considerations, trade-offs, and challenges in deploying onion routing anonymity systems on future Internet architectures. Recent research has shown that network-level anonymous networks are not only feasible in practice, but can provide better performance and better privacy to any application. As deployment of future Internet architectures gains momentum, we expect that these theoretical anonymous network proposals will begin to see real-world adoption. While more research is needed to further investigate these and other aspects, we hope the discussion herein will guide exploration of the design space, ultimately leading to more efficient and more secure anonymous networks.

Fig. 1 .

 1 Fig.1. Conceptual representation of the performance-privacy trade-off for anonymity systems, according to the categories described in Section 2 (figure adapted from Hsiao et al.[START_REF] Hsu | LAP: Lightweight anonymity and privacy[END_REF]).

It is possible to mitigate these restrictions by adding redirection in the network (see Section 4.5).

Alternative transport designs have been studied to improve the performance of Tor in this respect[START_REF] Reardon | Improving Tor using a TCP-over-DTLS Tunnel[END_REF][START_REF] Alsabah | PCTCP: per-circuit TCP-over-IPsec transport for anonymous communication overlay networks[END_REF], but the fundamental problem of queuing remains.

A path is made of a sequence of nodes that can route traffic from the source to the destination.

Valley freeness is a routing property that derives from the fact that ISPs and ASes have an incentive to only forward traffic that either comes from, or is destined to, one of their customers. When this property holds, for example, no ISP reflects traffic arriving from outside the ISP back to where it originated.


Marko Vukolić
email: mvu@zurich.ibm.com

The Quest for Scalable Blockchain Fabric: Proof-of-Work vs. BFT Replication

Keywords: Bitcoin, blockchain, Byzantine fault tolerance, consensus, proof-of-work, scalability, state machine replication

Bitcoin cryptocurrency demonstrated the utility of global consensus across thousands of nodes, changing the world of digital transactions forever. In the early days of Bitcoin, the performance of its probabilistic proof-of-work (PoW) based consensus fabric, also known as blockchain, was not a major issue. Bitcoin became a success story, despite its consensus latencies on the order of an hour and the theoretical peak throughput of only up to 7 transactions per second. The situation today is radically different and the poor performance scalability of early PoW blockchains no longer makes sense. Specifically, the trend of modern cryptocurrency platforms, such as Ethereum, is to support execution of arbitrary distributed applications on blockchain fabric, needing much better performance. This approach, however, makes cryptocurrency platforms step away from their original purpose and enter the domain of database-replication protocols, notably, the classical state-machine replication, and in particular its Byzantine fault-tolerant (BFT) variants. In this paper, we contrast PoW-based blockchains to those based on BFT state machine replication, focusing on their scalability limits. We also discuss recent proposals to overcoming these scalability limits and outline key outstanding open problems in the quest for the "ultimate" blockchain fabric(s).

Introduction

Distributed consensus, infamous for its limited scalability, was for decades perceived as a synchronization primitive that is to be used only in applications in desperate need of consistency and only among few nodes (see e.g., [START_REF] Brewer | Towards robust distributed systems[END_REF][START_REF] Gilbert | Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services[END_REF]). However, Nakamoto's Bitcoin cryptocurrency [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF] demonstrated the utility of decentralized consensus across thousands of nodes, changing the world of digital transactions forever.

Although the Bitcoin protocol does not actually implement consensus in the traditional distributed computing sense, it comes very close to consensus with probabilistic agreement [START_REF] Garay | The Bitcoin backbone protocol: Analysis and applications[END_REF]. In a nutshell, the goal of a cryptocurrency such as Bitcoin, is to totally order transactions on a distributed ledger, also called a blockchain. The Bitcoin blockchain consists of a hashchain of blocks: every block contains an ordered set of transactions and a hash of the preceding block (starting from the initial, the so-called "genesis" block). The key part is the Proof-of-Work (PoW) aspect of the hashchain [START_REF] Dwork | Pricing via processing or combatting junk mail[END_REF]: a Bitcoin block contains nonces that a Bitcon miner (i.e., a node attempting to add a block to the chain) must set in such a way that the hash of the entire block is smaller than a known target, which is typically a very small number. In fact, in Bitcoin, the difficulty of mining, inversely proportional to the target, is adjusted dynamically throughout the lifetime of the system. The adjustment is made with respect to the block-mining rate and, indirectly, with respect to the computational power of nodes participating in the system, to maintain the expected block-mining rate at roughly one block every 10 min [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF]. This latency of 10 minutes (per block) is often referred to as the block frequency (see e.g., [START_REF] Eyal | Bitcoin-NG: A scalable blockchain protocol[END_REF]) and is one of the two critical "magic numbers" in Bitcoin, the other being the block size, which is set in Bitcoin to 1 MB.

In the early days of Bitcoin, the performance scalability of its probabilistic PoW-based blockchain was not a major issue. Even today, Bitcoin works with a consensus latency of about an hour (for the recommended 6-block transaction confirmation), and with up to 7 (seven) transactions per second peak throughput (with smallest 200-250 byte transactions). On top of this, the Bitcoin network uses a lot of power, which, in 2014, was roughly estimated to be in the ballpark of 0.1-10 GW [START_REF] O'dwyer | Bitcoin mining and its energy footprint[END_REF].

However, blockchain requirements change rapidly, with high latency and low throughput of Bitcoin-like blockchain becoming a major challenge [START_REF] Bonneau | Sok: Research perspectives and challenges for Bitcoin and cryptocurrencies[END_REF]. As a comparison, leading global credit-card payment companies serve roughly 2000 transactions per second on average [START_REF] Zohar | Bitcoin: under the hood[END_REF], with a peak capacity designed to sustain more than 10000 transactions per second. Moreover, the trend of modern cryptocurrency platforms, such as Ethereum [START_REF] Wood | Ethereum: A secure decentralised generalised transaction ledger[END_REF], is to support execution of Turing-complete code on blockchain fabric in the form of smart contracts, which are, roughly speaking, custom, self-executing programs (distributed applications) that automatically enforce properties of a digital contract. In fact, smart-contract blockchain is seen as a candidate technology for distributed ledgers in many industries. Clearly, in many of the intended smart-contract use cases, distributed applications require much better performance than that offered by Bitcoin. The banking industry is one prominent example, where potential blockchain use cases go well beyond digital payments [START_REF] Milkau | Digitalisation in payments: From interoperability to centralised models[END_REF] to, e.g., securities trade settlements and trade finance.

Smart-contract use cases take the blockchain well beyond its original cryptocurrency purpose, back to the domain of database replication protocols, notably, the classical state-machine replication [START_REF] Schneider | Implementing fault-tolerant services using the state machine approach: A tutorial[END_REF]. Indeed, a smart contract can be modeled as a state machine, and its consistent execution across multiple nodes in a distributed environment can be achieved using state machine replication. A family of state-machine replication protocols particularly interesting for blockchain is the family of Byzantine fault-tolerant (BFT) [START_REF] Lamport | The Byzantine generals problem[END_REF] state-machine replication protocols, which promise consensus despite participation of mali-cious (Byzantine) nodes. In more than three decades of research, BFT protocol prototypes have been shown to be practical [START_REF] Castro | Practical Byzantine fault tolerance and proactive recovery[END_REF], reaching practically minimal latencies allowed by the network, and supporting tens of thousands transactions per second (see e.g., [START_REF] Kotla | Zyzzyva: Speculative Byzantine fault tolerance[END_REF][START_REF] Aublin | The next 700 BFT protocols[END_REF]). However, BFT and state-machine replication protocols in general are often challenged for their scalability in terms of number of nodes (replicas) [START_REF] Brewer | Towards robust distributed systems[END_REF], and have not been throughly tested in this aspect critical to blockchain.

In summary, blockchain consensus technologies of today, PoW and BFT, sit at the two opposite ends of the scalability spectrum. Roughly speaking, PoWbased blockchain offers good node scalability with poor performance, whereas BFT-based blockchain offers good performance for small numbers of replicas, with not-well explored and intuitively very limited scalability. This current state of blockchain scalability is sketched in Figure 1. Given seemingly inherent tradeoffs between the number of replicas and performance, it is not clear today what the optimal blockchain solution is for the sweet spot relevant for many use cases in which the number of nodes n ranges from a few tens to 1000 (or perhaps few thousands). In this paper, we overview recent efforts towards improving scalability on both sides of the spectrum and highlight interesting directions and open problems in the quest for the "ultimate" blockchain fabric. First, in Section 2 we compare PoW-based blockchains to those based on BFT state-machine replication. Then, in Section 3, we overview novel promising approaches to scaling PoW and BFT protocols. We conclude in Section 4 with several open questions that will be interesting to tackle in the very near future.

PoW vs. BFT blockchains

Table 1 gives a high-level comparison between PoW consensus and BFT consensus for a set of important blockchain properties. These properties include node identity management, consensus finality (or, dually, the possibility of temporary forks in the blockchain), scalability in terms of number of consensus nodes and clients, performance (latency, throughput, power consumption), tolerated power of adversary, network synchrony assumptions, and, last but not least, existence of correctness proofs of protocols underlying blockchain. This set of properties is certainly not exhaustive, but we believe it is representative for comparing two blockchain families. In the rest of this section, we discuss Table 1 in more detail. Node identity management. How node identities are managed in PoW and BFT protocols is possibly their most fundamental difference. PoW blockchains feature an entirely decentralized identity management -for example, anybody can download the code for Bitcoin miner, and start participating in the protocol, knowing basically only a single peer to start with. This is a very powerful feature of PoW blockchains and the main reason why they are the blockchain family of choice when it comes to so-called "public" blockchains in which anybody is allowed to participate. Such public blockchains are sometimes also called "permissionless" blockchains -permissionless participation is made possible by PoW, as PoW inherently addresses the Sybil attack [START_REF] Douceur | The sybil attack. In Peer-to-Peer Systems[END_REF], infamous in anonymous networks. Specifically, in PoW-based blockchains, the ability of a node (resp., a pool of nodes) to influence the outcome of PoW consensus depends on computational power of a node (resp., a pool).

In contrast, the BFT approach to consensus typically requires every node to know the entire set of its peer nodes participating in consensus. This in turn calls for a (logically) centralized identity management in which a trusted party issues identities and cryptographic certificates to nodes. 1 Intuitively, this aspect of BFT-based blockchains puts it at a disadvantage with respect to PoW blockchains. That said, in a number of emerging blockchain applications (e.g., banking, finance, land and real-estate ownership ledgers) the requirement for known identity of nodes might anyway be imposed for legal and compliance reasons. This explains why BFT consensus protocols are the technology of choice for so-called "permissioned" blockchains, which require blockchain participants identity to be known.

Consensus finality.

Roughly speaking, what is often informally referred to as "consensus finality" (and sometimes as "forward security" [START_REF] Decker | Bitcoin meets strong consistency[END_REF]) is a property that mandates that a valid block, appended to the blockchain at some point in time, be never removed from the blockchain. In the standard distributed computing terminology, "consensus finality" follows from a combination of the total order and agreement properties of total order (atomic) broadcast [START_REF] Défago | Total order broadcast and multicast algorithms: Taxonomy and survey[END_REF], which is the primitive all state-machine replication protocols are built upon (total order broadcast is, in turn, equivalent to consensus). Translated to blockchain terminology, this property can be phrased as follows:

Definition 1 (Consensus Finality). If a correct node p appends block b to its copy of the blockchain before appending block b , then no correct node q appends block b before b to its copy of the blockchain.

Consensus finality is not satisfied by PoW-based blockchains. To see why, note that, besides obviating the need for identity management, PoW acts as a randomized concurrency control mechanism, in which the block frequency is adjusted such that block collisions (i.e., concurrent appends of different blocks to the blockchain) are rare. However, as concurrency control is only probabilistic and as block propagation over a network can take some time [START_REF] Decker | Information propagation in the Bitcoin network[END_REF], collisions do happen, resulting in temporary forks on the blockchain that PoW-based blockchains are prone to even if all nodes are honest. These temporary forks (see Fig. 2 for an illustration) are resolved by rules such as Bitcoin's longest (most difficult) fork rule [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF], or the GHOST rule [START_REF] Sompolinsky | Secure high-rate transaction processing in Bitcoin[END_REF], a variant of which is used in Ethereum. However, the very presence of temporary forks implies no consensus finality. As we discuss in more detail below, absence of consensus finality directly impacts the consensus latency of PoW blockchains as transactions need to be followed by several blocks to increase the probability that a transaction will not end up being pruned and removed from the blockchain (we speak of multi-block confirmation).

In contrast, consensus finality is satisfied by all BFT and state-machine replication protocols. 2 This gives BFT-based blockchains a clear advantage over PoW, as applications, users and smart contracts can have immediate confirmation of the final inclusion of a transaction into the blockchain.

Scalability. Although decoupling the issue of blockchain scalability (with the number of nodes and clients in the system) from that of blockchain performance (latency and throughput) is not entirely possible, we nevertheless first focus on the number of nodes and clients for which PoW and BFT technologies have been proven to work in practice.

On the one hand, the Bitcoin network features thousands of mining nodes, demonstrating node scalability of PoW-based blockchains in practice. That said, it is worth mentioning that grouping of miners into mining pools (with the goal of splitting mining rewards and making mining a financially more predictable endeavour) plagues Bitcoin, effectively centralizing the cryptocurrency [START_REF] Gervais | Is Bitcoin a decentralized currency[END_REF]. We note that mining pool centralization is not a specific trait of Bitcoin, but more a consequence of the popularity of a PoW blockchain, affecting also many altcoins (alternative Bitcoin-like cryptocurrencies) as well as popular blockchains, such as Ethereum.

On the other hand. BFT and state-machine replication are, in general, perceived as protocols with poor scalability (see, e.g., Brewer's CAP theorem [START_REF] Brewer | Towards robust distributed systems[END_REF]). However, having been invented in the context of replicating traditional applications, such as databases, for fault-tolerance, BFT protocols were never really tested thoroughly for their scalability beyond, say, n = 10 or n = 20 nodes, in particular in the light of the fairly modest performance targets of many blockchain applications. Intuitively, because of their intensive network communication which often involves as many as O(n 2 ) messages per block [START_REF] Castro | Practical Byzantine fault tolerance and proactive recovery[END_REF], BFT protocols are seen in the database and systems communities as not scalable (see also [START_REF] Mickens | The saddest moment[END_REF]). 3 This is true even for their crash-tolerant counterparts, i.e., replication protocols such as Paxos [START_REF] Lamport | The part-time parliament[END_REF], Zab [START_REF] Flavio | Zab: Highperformance broadcast for primary-backup systems[END_REF] and Raft [START_REF] Ongaro | In search of an understandable consensus algorithm[END_REF], which are used in many large scale systems but practically never across more than a handful of replicas (see e.g., [START_REF] Corbett | Spanner: Google's globally distributed database[END_REF]).

Finally, when it comes to scalability with the number of clients, both PoW and BFT protocols support thousands of clients and scale well.

Performance. Beyond the very limited performance of Bitcoin of up to 7 transactions per second (with the current block size) and 1-hour latency with 6-block confirmation, PoW-based blockchains face inherent performance challenges. As we already discussed, the two main performance-related parameters of a PoW blockchain are block size and block frequency. Increasing the block size with the goal of boosting throughput comes at the cost of increasing the latency, because of longer propagation delays of larger blocks across the Internet. These longer delays, in turn, have negative implications on blockchain security: longer delays may increase the number of forks and the possibilities for mounting doublespending attacks [START_REF] Ghassan | Misbehavior in Bitcoin: A study of double-spending and accountability[END_REF], because of the possibility of temporary chain forks and absence of consensus finality in PoW blockchains. Similar security challenges apply when the block frequency is increased, with the goal of reducing the latency of multi-block confirmation. The exact security implications of tuning the block frequency and the block size in PoW-based blockchain are in general rather involved (see e.g., [START_REF] Sompolinsky | Secure high-rate transaction processing in Bitcoin[END_REF] for an analysis) and should be handled with care. With this in mind, limited performance is seemingly inherent to PoW blockchains and not an artifact of a particular implementation.

In contrast, modern BFT protocols have been confirmed to sustain tens of thousands of transactions with practically network-speed latencies, not only as prototypes (e.g., [START_REF] Kotla | Zyzzyva: Speculative Byzantine fault tolerance[END_REF][START_REF] Clement | Making Byzantine fault tolerant systems tolerate Byzantine faults[END_REF][START_REF] Aublin | The next 700 BFT protocols[END_REF]) but also as practical systems [START_REF] Neves Bessani | State machine replication for the masses with BFT-SMART[END_REF].

Adversary. PoW and BFT consider different adversaries. In PoW blockchains, what matters is the total computational (hashing) power controlled by the adversary. Initially, Bitcoin was thought to be invulnerable so long as the adversary controls less than 50% of hashing power. Years later, it was shown that Bitcoin mining is actually vulnerable even if only 25% of the computing power is controlled by an adversary [START_REF] Eyal | Majority is not enough: Bitcoin mining is vulnerable[END_REF]. In contrast, BFT voting schemes are known to tolerate at most n/3 corrupted nodes [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF]. This bound holds only when the network is allowed to be (from time to time) fully asynchronous -strengthening synchrony assumptions makes it possible to raise this threshold. The classical n/3 threshold bound for BFT consensus can be generalized to general adversary structures, where an adversary can control different subsets of nodes [START_REF] Guerraoui | Refined quorum systems[END_REF][START_REF] Vukolić | Quorum Systems: With Applications to Storage and Consensus[END_REF].

Network synchrony. Bitcoin relies on the local time of a node to timestamp a block. Roughly speaking, a block is accepted as valid if its timestamp is greater than the median of the last 11 blocks. Additionally, timestamps play a major role in calculating the difficulty of mining and maintaining block frequency. Therefore, loose clock synchrony is needed for liveness. However, timestamp manipulation attacks that may also compromise the consistency of the blockchain are conceivable (see the "zeitgeist attack" [START_REF]The "Zeitgeist attack[END_REF]). Although such attacks are difficult to stage against major PoW blockchains such as Bitcoin, they have been successfully performed in the context of some PoW altcoins.

BFT protocols typically do not rely on any physical clock. 4 However, eventually synchronous communication is needed to ensure liveness, owing to the FLP consensus impossibility result, which states that consensus is impossible to achieve deterministically with potentially faulty nodes in a purely asynchronous system [START_REF] Michael | Impossibility of distributed consensus with one faulty process[END_REF]. The safety properties of consensus, including consensus finality, are maintained despite global communication outages and arbitrarily long asynchrony periods [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF].

Correctness proofs. Historically, state-machine replication protocols, and in particular their BFT variants, have been recognized as very challenging to design and implement [START_REF] Tushar | Paxos made live: an engineering perspective[END_REF][START_REF] Neves Bessani | State machine replication for the masses with BFT-SMART[END_REF][START_REF] Aublin | The next 700 BFT protocols[END_REF]. Consequently, new protocols are subject to detailed academic scrutiny and therefore come with (more or less) detailed proofs, sometimes even with formal proofs that take an entire PhD thesis (see [START_REF] De | On Building Blocks for Distributed Systems[END_REF][START_REF] Losa | Modularity in the design of robust distributed algorithms[END_REF]). Even if it may be understandable why Bitcoin was originally deployed without having been subjected to similar scrutiny, it is rather surprising that novel PoW blockchains are rarely accompanied by a detailed security and distributed protocol and security analysis.

Improving blockchain scalability

In this section we overview and discuss several recent efforts that focus on improving the scalability aspects of both PoW and BFT blockchains.

Improving the performance of PoW blockchains. Sompolinski and Zohar recently proposed the GHOST (Greedy Heaviest-Observed Sub-Tree) rule [START_REF] Sompolinsky | Secure high-rate transaction processing in Bitcoin[END_REF], which basically resolves conflicts in a PoW blockchain by weighing the subtrees rooted in blocks rather than the longest (sub)chain rooted in given blocks. Although GHOST is essentially a conflict-resolution strategy, it offers performance benefits over the standard longest (heaviest) chain rule of Bitcoin, as it provides more secure means of increasing the block frequency and the block size [START_REF] Sompolinsky | Secure high-rate transaction processing in Bitcoin[END_REF]. A variant of the GHOST rule is actually implemented in the Ethereum blockchain [START_REF] Wood | Ethereum: A secure decentralised generalised transaction ledger[END_REF], although the GHOST-PoW performance has not yet been adequately stresstested with high loads (in 2016, typical Ethereum throughput is fewer than 20,000 transactions per day, i.e., about 0.2 tx/s on average). 5Bitcoin-NG is a novel proposal by Eyal et al. [START_REF] Eyal | Bitcoin-NG: A scalable blockchain protocol[END_REF] that uses standard PoW for leader election, declaring a node which mines a block with standard difficulty (called a key block) to become a leader until a new key block is mined. In the meantime, the leader can append microblocks to the chain, which are not subject to PoW mining but are merely hashchained together. As such, microblocks considerably increase the throughput of the whole system and decrease the latency (that said, Bitcoin-NG is still to be stress-tested in practice). In a sense, Bitcoin-NG mixes leader election, often seen in BFT protocols, with a leader-centric protocol in between leader-election epochs. However, what is different in Bitcoin-NG from BFT protocols is that leader election is PoW-based. Consequently, forks are still possible in Bitcoin-NG and consensus finality is not ensured, which may lead to security implications such as asset double-spending, as discussed earlier.

Scaling blockchain through parallelization. Scaling blockchain by making it a blockDAG (directed acyclic graph) rather than a linear chain of blocks, was recently proposed by Lewenberg et al. in the context of PoW [START_REF] Lewenberg | Inclusive block chain protocols[END_REF]. The idea is to allow non-conflicting transactions (e.g., those transactions that do not constitute double-spending attempts) to be initially on different forks, but to eventually merge the forks by mining a block that would include them both in the ledger. 6The BFT and state-machine replication communities have also been intensively exploring the idea of parallel replication for a few years now, leveraging parallelization of execution of independent requests (transactions) (see, e.g., [START_REF] Kapritsos | All about Eve: execute-verify replication for multi-core servers[END_REF][START_REF] Parisa | Rethinking state-machine replication for parallelism[END_REF]).

Eliminating communication and resource overhead in BFT protocols. As we have already discussed, the major challenge for BFT protocols that prevents their wider adoption in blockchain is their scalability in terms of the number of nodes. Stellar [START_REF] Maziéres | The Stellar consensus protocol: A federated model for internetlevel consensus[END_REF] is an ongoing effort aimed at removing unanimously accepted membership lists from BFT protocols, while maintaining the other BFT advantages over PoW. Other approaches target the BFT scalability without changing membership assumptions. These include optimistic BFT protocols [START_REF] Harigovind | Parsimonious asynchronous byzantine-fault-tolerant atomic broadcast[END_REF][START_REF] Aublin | The next 700 BFT protocols[END_REF] which feature linear communication complexity in the "common case" and resort to expensive O(n 2 ) communication among nodes featured by classical protocols such as PBFT [START_REF] Castro | Practical Byzantine fault tolerance and proactive recovery[END_REF] only if the network and the process fault pattern are particularly infavorable. However, even optimistic BFT have a resource and communication overhead when compared to crash-tolerant replication protocols (e.g., [START_REF] Lamport | The part-time parliament[END_REF][START_REF] Flavio | Zab: Highperformance broadcast for primary-backup systems[END_REF][START_REF] Ongaro | In search of an understandable consensus algorithm[END_REF]), which are better proven in practice and may serve as a baseline for BFT.

To rectify this, Liu et al. recently proposed a novel network and node fault model called XFT [START_REF] Liu | XFT: practical fault tolerance beyond crashes[END_REF] that allows one to tolerate up to n/2 Byzantine nodes. At the same time, XFT features message patterns characteristic to crash-tolerant replication protocols, i.e., without the overhead pertaining to typical BFT message patterns. To this end, XFT ("cross" fault tolerance) challenges the established ability of a BFT adversary to control the network and Byzantine nodes simultaneously, decoupling network faults from Byzantine-node faults, treating them as largely independent. As such, XFT goes in the direction of a more realistic adversary model that resembles the one of PoW blockchains, which are not very concerned with the ability of the adversary to control the entire communication network.

Finally, another appealing direction for future BFT-based blockchain is BFT protocols that leverage small pieces of trusted hardware (e.g., [START_REF] Kapitza | CheapBFT: resource-efficient Byzantine fault tolerance[END_REF]) to improve communication and reduce resource cost.

Randomized BFT. Randomized BFT protocols (e.g., [START_REF] Bracha | An asynchronou [(n-1)/3]-resilient consensus protocol[END_REF][START_REF] Toueg | Randomized byzantine agreements[END_REF][START_REF] Cachin | Random oracles in constantipole: practical asynchronous byzantine agreement using cryptography (extended abstract)[END_REF]) are appealing alternative to standard, eventually synchronous [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF] BFT protocols such as PBFT. Specifically, randomized BFT protocols circumvent the FLP consensus impossibility result [START_REF] Michael | Impossibility of distributed consensus with one faulty process[END_REF] by guaranteeing correctness with very high probability (i.e., always, except with negligible probability), rather than deterministically. This allows randomized BFT protocols to be completely asynchronous [START_REF] Ben-Or | Another advantage of free choice: Completely asynchronous agreement protocols (extended abstract)[END_REF].

For many years, an issue with randomized BFT protocols has been their performance. Specifically, classical randomized BFT (e.g., [START_REF] Ben-Or | Another advantage of free choice: Completely asynchronous agreement protocols (extended abstract)[END_REF][START_REF] Bracha | An asynchronou [(n-1)/3]-resilient consensus protocol[END_REF][START_REF] Toueg | Randomized byzantine agreements[END_REF][START_REF] Cachin | Random oracles in constantipole: practical asynchronous byzantine agreement using cryptography (extended abstract)[END_REF]) are very inefficient compared to eventually synchronous, deterministic BFT protocols mostly due to overhead of cryptographic tools they use. However, this may be changing soon with novel randomized BFT protocols such as HoneyBadger [START_REF] Miller | The honey badger of BFT protocols[END_REF] showing promise for good practical performance (i.e., reasonably high throughput) with up to about 100 nodes, through cherry-picking best available cryptographic tools for randomization as well as processing requests in very large batches. Clearly, large batches negatively impact latency, but this could be addressed by Hybrid BFT protocols [START_REF] Kawazoe | Failure detection and randomization: A hybrid approach to solve consensus[END_REF] that may combine very efficient optimistic and deterministic BFT protocols (e.g., those described in [START_REF] Aublin | The next 700 BFT protocols[END_REF]) with practical randomized protocols such as HoneyBadger. Early examples of such Hybrid BFT protocols can be found in [START_REF] Kawazoe | Failure detection and randomization: A hybrid approach to solve consensus[END_REF][START_REF] Kursawe | Optimistic asynchronous atomic broadcast[END_REF][START_REF] Harigovind | Parsimonious asynchronous byzantine-fault-tolerant atomic broadcast[END_REF], but the development of future Hybrid BFT protocols can be facilitated by using the modular BFT design framework described in [START_REF] Aublin | The next 700 BFT protocols[END_REF].

Mixing PoW and BFT. Recently, Decker et al. [START_REF] Decker | Bitcoin meets strong consistency[END_REF] have proposed to enhance PoW blockchain with BFT (concretely, the PBFT protocol [START_REF] Castro | Practical Byzantine fault tolerance and proactive recovery[END_REF]), primarily to ensure consensus finality in a PoW blockchain by using BFT. SCP [START_REF] Luu | SCP: A computationally-scalable Byzantine consensus protocol for blockchains[END_REF] also proposes a hybrid PoW/BFT protocol, using PoW for identity management and (parallel and hierarchical) BFT consensus for agreement. Clearly, the above discussion on the importance of scaling BFT in terms of the number of nodes is also critical to such approaches that mix PoW and BFT.

Conclusion and open problems

We briefly overviewed state of the art as well as emerging directions towards scalable blockchain. We contrasted proof-of-work (PoW) and Byzantine faulttolerant (BFT) consensus protocols, highlighting their respective advantages.

Future work will be very dynamic and interesting. Making Figure 1 more precise, i.e., placing various protocols at the correct place with respect to their performance versus their node-scalability, entails a fair amount of research, but represents an immediate open problem that needs to be better understood to facilitate future blockchain scalability improvements. Furthermore, a lot of potential lies in synergies between PoW and BFT, both when it comes to combining protocol techniques and when it comes to refining the adversarial and network models.

Finally, for the most demanding blockchain applications, it would be interesting to move computationally expensive parts of BFT protocols (e.g., cryptography) closer to hardware. In general, implementing consensus in hardware is indeed very appealing and may yield impressive performance, as attested by recent proposals that explore this idea in the context of crash fault-tolerance [START_REF] Poke | DARE: high-performance state machine replication on RDMA networks[END_REF][START_REF] Istvan | Consensus in a box: Inexpensive coordination in hardware[END_REF].

Fig. 1 .

 1 Fig.1. Illustration of performance and scalability of different families of PoW and BFT protocols discussed in this paper. The actual, real-world performance of systems that touch upon the grey area is subject to further research. Hence, their positioning within the grey area is at the moment entirely speculative and for motivational purposes only.

  (a) Consensus finality violation resulting in a fork. (b) Eventually, one of the blocks must be pruned by a conflict resolution rule (e.g., Bitcoin's longest chain rule).

Fig. 2 .

 2 Fig. 2. Illustration of a violation of consensus finality, fork and conflict resolution.

Table 1 .

 1 High-level comparison between PoW and BFT blockchain consensus families for a set of important blockchain properties. Entries in bold suggest desirable features and highlight advantages of one consensus family over the other.

		PoW consensus	BFT consensus
	Node identity	open,	permissioned, nodes need
	management	entirely decentralized	to know IDs of all other nodes
	Consensus finality	no	yes
	Scalability	excellent	limited, not well explored
	(no. of nodes)	(thousands of nodes)	(tested only up to n ≤ 20 nodes)
	Scalability	excellent	excellent
	(no. of clients)	(thousands of clients)	(thousands of clients)
	Performance	limited	excellent
	(throughput)	(due to possible of chain forks)	(tens of thousands tx/sec)
	Performance	high latency	excellent
	(latency)	(due to multi-block confirmations) (matches network latency)
	Power	very poor	good
	consumption	(PoW wastes energy)
	Tolerated power	≤ 25% computing power	≤ 33% voting power
	of an adversary
	Network synchrony	physical clock timestamps	none for consensus safety
	assumptions	(e.g., for block validity)	(synchrony needed for liveness)
	Correctness	no	yes
	proofs

Here, it is important to note that after an initial bootstrap of a BFT-based blockchain, the nodes already on the blockchain could themselves act together as a distributed trusted party and help reconfigure the system[START_REF] Rodrigues | Automatic reconfiguration for large-scale reliable storage systems[END_REF][START_REF] Neves Bessani | State machine replication for the masses with BFT-SMART[END_REF].

Provided the assumptions about the power of the adversary hold.

That said, it is worth noting that there are optimistic BFT protocols with O(n) common-case (expected) message-complexity (see, e.g.,[START_REF] Harigovind | Parsimonious asynchronous byzantine-fault-tolerant atomic broadcast[END_REF][START_REF] Aublin | The next 700 BFT protocols[END_REF]) -we discuss these later in more detail.

Some state-machine replication protocols do use physical clock timestamps, but only to improve performance[START_REF] Du | Clock-RSM: Low-latency inter-datacenter state machine replication using loosely synchronized physical clocks[END_REF].

https://etherchain.org/statistics/basic.

BlockDAGs are conceptually similar to the notion of parallel sharded chains (sidechains) combined with merge mining.


Rachid Hba

Abdellah El Manouar

ICT Green Governance: new generation model based on Corporate Social Responsibility and Green IT

Keywords: Governance, Green IT, CSR, Information Technology, Sustainable Development

The strategy of sustainable development in the governance of information and communication technology (ICT) is a sector of advanced research that leads to rising challenges posed by social and environmental requirements in the implementation and establishment of the governance strategy. This paper offers new generation governance model that we call "ICT Green Governance". The proposed framework provides an original model based on the Corporate Social Responsibility (CSR) concept and Green IT strategy. Facing increasing pressure from stakeholders, the model offers a new vision of ICT governance to ensure effective and efficient use of ICT in enabling an enterprise to achieve its goals. We present here the relevance of our model, on the basis of a literature review, and provide guidelines and principles for effective ICT governance in the way of sustainable development, in order to improve the economic, social and environmental performance of companies.

INTRODUCTION

The ICT governancein the global ICT management of the companies is impacteddue to the technical and economic evolution. In consequence, on the socio-economic side, the results are substantial: oriented sustainable development models are completely open to the new forms of action, and potentially prepared to detect and put into action the good practices of ICT governance strategy. Several are the companies that recognize the potential of the Green IT (green information technologies), the Green IT make reference to ICT with low environmental impact through the reduction of carbon footprint, energy consumption and associated costs, throughout the life cycle of hardware, software and ICT related services, they also recognize the effect of Green IT on their organizations, on their overall ICT strategies, as well as, on the sustainable development or CSR strategies [8,9]. The big challenge is to associate the ICT strategy with Green IT to provide new managerial and organizational perspectives, and green market opportunities. Green IT and CSR activities are a recent concept which is seriously taken [3]; it is not perceived any more like fashion trend or a simple marketing label. In this context a new and great reflection is conducted on the CSR and Green IT management model, beyond marketing and environmental aspects [7]. In fact, the innovation activity associated with an ecological concern becomes a must to make the difference within a competitive and globalized environmental context. Thus, was born a new eco-responsible approach of ICT governance which is declined so much on the processes of the company, that on the comprehensive ICT strategy. This approach leads us to speak about the green governance that we can qualify as new generation managerial model, which aims at the alignment of CSR strategy and Green IT with the global ICT governance strategy to reach the sustainable ICT governance [2]. Thus, we postulate that the green governance based on Green IT and the CSR is an alternative of conventional governance that will address a new perspective of structuring of organization and deep changes in the practices of ICT management. To validate this assumption, our work will focus as well on two parties: we will first elucidate the concepts of green governance such as an agile model and horizontal managerial culture in the opposite of current models based on a hierarchically pyramidal relation and modes of subordinate collaboration, and we will outline the theoretical foundations of this research into sustainable management and eco-responsibility for the ICT governance. Secondly, we will expose the approach of the Corporate Sustainability and Responsibility (CSR) and the adoption of the Green IT practices like new model of good governance practices that proposes a 360 degree approach in terms of decision making criteria and offers a transverse dimension for ICT governance. This approach will invite us to develop the green governance as a new generation model of management thanks to the adoption of Green IT and CSR practices, this model has two dimensions: the Green IT and CSR, and governance, and how a strategy Green IT can give place to a strategy corporate and constitute the core of a total CSR strategy.

I LITERATURE REVIEW 1.1 Dominant approaches of ICT governance strategy

Face to dynamism to increase corporate policy and ICT governance strategy, several studies from the sixties have focused on aspects impactingglobal performancewithin companies with direct effect on strategic choice and competitive advantage. Further new processing logic, a deep technological and societal change has allowed researchers and engineers to rethink the conventional governance model by seeking innovation and the value creation in the organizations and business models in order to developefficiency and competitiveness through the ICT revolution that offers an innovation manner and growth opportunities. At the moment, ICT offers a continuous flow of knowledge creation and creative managerial practices of sensethrough their adaptability and their flexibility, and upgrade the flow of

ICT Governance

ICT Green Governance

New generation model

CSR Strategy

Green IT

Stakeholder Nedds

ICT Goals Value Creation

Figure 1. Synthesis of the problems information between various stakeholders (recipients) [15], in a many to many way, on the social and economic as well as environmental aspect. Owing to, their technological prowess and their extended and cross scope, ICT are able to bring a plus-value in the establishment of the managerial and strategic policies of the companies by taking into account the institutional requirements and taking care to conserve legitimacy via a socially constant control. by the establishment of BP Z67-320 repository of best practices; this repository provides a governance approach and practical recommendations on the eco-responsible information systems. Especially, reducing the energy consumption of ICT and minimizing their environmental impact. This contribution provides organizations best practices for creating green value and support innovation in the field of sustainable development.

The governance approach presented will integrate the concept of sustainability as a key decision-making criterion, and ensure alignment of the Green IT initiatives with the overall strategy of the company and also to identify areas for improvement to ensure continued innovation of ICT, using indicators for sustainable development [50,51].

Corporate Sustainability and Responsibility (CSR)

Corporate social responsibility (CSR) is a theme that was discussed by Henry Ford in 1920 and he wrote "If you try to run a business solely on profit, then it will also die because it will not have more reason to be". After several years the concept was defined in 1953 by Bowen and was enhanced following the Brundtland Report in 1987 and the Rio Summit in 1992, with an aim of looking further into the reflection on the regulation of the globalization phenomenon and multiplication of policies and economic interactions [13]. The "Global Compact" pact was concluded at the World Economic Forum in Davos on January 31st, 1999 following the suggestion from the Secretary-General of the United Nations Kofi Annan; this pact stipulates the stakes of the CSR based on sustainable development and common values which will enhance the investment of the human capital [17].

The CSR became an engine of transformation towards a new form of governance of the company (article 49, "Grenelle de l'environnement I" law). The United Nations, the Economic Co-operation and Development (OECD), the European commission and ISO consider "the CSR is the contribution of the companies to the stakes of sustainable development, and their responsibility towards the social and environmental impacts of their activities", this definition joined the representation into 1997 of John Elkington by Triple Bottom Line (TBL) which shows CSR stakes of sustainable development [22]:

The concept of the CSR is a strategic lever of action which fits in the sustainable and which includes all the elementsbeing able to create a plus-value of the business on the long term [8].

The progressive CSR approach is a sustained approach and controlled by a societal partnership contract which frames the interactions between the actors giving a new design to the organization [9] and the governance of the company.

Green IT

The biggest challenge facing the environment today is global warming, caused by carbon emissions. According to the Energy Information Administrationreport, About 98% of CO2emissions can be directly attributed to the energy consumption. Today, any companies are speaking openly about a need to operate in a greenmode, publishing sustainability principles for environmental practices on their corporate identity. In addition, many companies are now paying some kind of carbon duty for the resources they use and the environmental impact of services and the products they manufacture, thus, reducing the energy consumed can have a real financial recovery. The concept of Green IT was a great evolution from of an objective of reducing ICT impact on the company organization (organization footprint) and on the environment (carbon accounting) [16] to consideration of the impacts on the society and others stakeholders. Green IT was increasingly become a lever of CSR strategy providing strategic management and CSR reporting techniques [14], and for the causal relationship, the Green IT is the countenance of CSR [1]. The "Smart 2020" [34] study conducted by professionals of sustainable development has a focus on Green IT leverage on the company's processes thanks to its positive contribution to sustainable development. One of the key numbers presented by this study shows that Green IT will allow, by 2020, to make economies in terms of CO2 emission of about 7800 million tons.

With the publication of the ISO26000 standard and the "Grenelle de l'environnement II" law, the Green IT became more ambitious and thus offers a tool for strategic and operational management of CSR stakes, allowing reduction of the ecological footprint of ICT [3,16]. The evolution of green IT approach and its related fields that contribute to the company's involvement in CSR strategy, showed two levels or phases of Green IT maturity: we distinguish the Green IT 1.0 (Green For IT) and the Green IT 2.0 (IT For Green):

The purposes shared by these two types are generally, the energy effectiveness and saving, reduction of the company footprint and economic competitiveness. The Green IT 1.0 proposes good practices of use of computer material in order to minimize the environmental impact of ICT (eco-responsible ICT). On the other hand, the Green IT 2.0 takes an interest, through the ICT, in reduction of ecological footprint of the company (CSR stakes) it also allows the optimization of business processes and organization of the supply chain (Green Supply Chain).

Short Term Long Term ICT Strategy intergation

• Eco-design

•

Stakeholder theory

During last years, a very specific attention is drawn by the neo-institutionalists on the concepts of stakeholder's paradigm [34]. The researches carried out in the academic field have studied the company as being an organization or an institution, having potential and values towards all stakeholders [38,39]. The stake goes beyond concerns of shareholders benefits to the broader surrounding aspects. Few, are the studies which were made on this concept of stakeholders, the literature misses works exposing the related subject and theories. However, the stakeholder's theory is exposed according to a model of organizational relations between the company and its economic and environmental partners [40]. Its objective is to propose a tool for the improvement of the means of subsistence and durability [41]. Thus, it is regarded in certain cases as an obvious result of the social sciences evolution, in other cases; it is seen as a simple framework directed by the principles of morality [42].

With the emergence of Green IT and CSR, the research on the topic of stakeholders [43] provides a reference framework to theoretically develop the CSR which will incite us to explore the common axes that could lead us to a new theory or a new concept for use on many levels and for purposes of broadening the scope of its application.

II ICT GREEN GOVERNANCE: NEW GENERATION MODEL

ICTgovernance was introduced in companies in a context where from a point of view; the automation of activities and processes has become a key element within the company and from another point of view, where decision makers do not see how ICT can bring plus-value, effectiveness and performance in the organization. We can as well talk about ICT governance and therefore theoretical models and organizational and managerial practices. It is also in the interest of the transformation and innovation of techniques developed for the control and monitoring of ICT, to seek and explore new models for effective corporate governance, which requires strong management skills to make important decisions and provide leadership.The main objective is to propose a model for mastering ICT governance over time. This framework should be based on a set of "best practices" that are incorporated within the governance structure within the organization [35,36], and may take the form of changing the architecture of business processes [46]. As we explained in the introduction, with the appearance of the concept of sustainable development, the concerns and the engagement of the organizations in the business of ICT management are at the same time complex and improved and allowed to evolve missions and managerial competences of the decision makers [10,11]. Thus, environmental dimension and responsibility values endeavoured the companies to choose innovating practices in order to satisfy the sustainable development requirements.

Company

ICT governance includesthe principles and the procedures as well as the organizational management and structures which ensure that a firm's IT sustains and extends objectives and the organization's strategies, that the IT's resources are used in a responsible way, and that its risks are attenuated and controlled [37,38]. To reach the suggested outcomes, it is recommended to apply various mechanisms which, in this article, will be referred to as ICT green governance model. The following Frameworkhave been described in the literature: ICT strategy, ICT conformity and risk management, ICT compliance management, ICT performance management, ICT service management, IT sourcing management, ICT portfolio management.

Our model allows the sustainability of the resources (CSR impact on the human resources management and processes) [30,39]. It is, therefore, an effective and efficient organizational framework of the balance of the sustainable resources.

Given that ICT incorporates several actors in the production and the information processing and face to the difficulties to define a conceptual framework of these increasingly complex systems, the partnership (management of the stakeholders impact on the organization) and contractual approach (use of ICT for goal of organizational balances) of this model contribute to the enhancement of organizational and managerial architectures of the ICT business, as well on the creation of information as on its processing [11].

In our research we use the green governance as a model or management Framework to align conventional management to sustainable development concerns and the ICT Governance. Our major contribution is the use of a new strategy that combines governance and alignment as part of an integrated approach of Green IT and CSR. The Framework consists of two pillars or dimensions of good practices:

• Green IT and CSR Approach • ICT Governance

Our ICT green governance model offers to the managers two visions of decision making [13] to encourage desirable behavior in the use of ICT; an internal vision which consists in

ICT Green Governance

CSR Strategy

Green IT

ICT management

Green IT mangement

ICT Governance

Figure 5. ICT Green Governance model improving the efficiency and in minimizing the costs of the processes, and an external vision, when ICT is used in order to create a unique customer value [10] and this vision allows to reach goals of sustainable development towards various stakeholders thus to improve business competitiveness and the leadership of the company:

The ICTgreen governance model aims to the identification, with low costs [21], of sources of competitive advantage and thus aligns the internal vision of management with the external strategy which impacts other stakeholders. To achieve these objectives, our model offers an eco-responsible approach focused on two dimensions: Green IT and CSR, and ICT strategic governance. This helps to develop management strategies that can improve low-impact sustainability processes and business operations. The green governance provides a comprehensive framework that will help companies create optimal value thanks to the two mentioned dimensions, thus maintaining the balance between the goals of various internal and external [20] stakeholders and optimization levels of risk and the use of ICT.

To deliver value to stakeholders, the company needs good Green governance that evaluates and control, in a holistic manner, activities related to the use of ICT. This axis of our model is represented by the deployment of CSR type of governance authorities which provide indicators and dashboards management activities related to sustainable development for effective and sustainable management of ICT. The goal is to meet the requirements of lawful and contractual performance and conformity with respect to the other stakeholders and to make sure "that all the directives and internal and external regulations of conformity, are considered and treated in a suitable way". The Green IT and CSR approach in the context of the governance which is exposed on the model is conceptualized by a approach eco-responsible which obliges the managers to integrate durability in the instruments of governance, recommendation which must be applied in the various mechanisms of governance; ICT strategy, control risks and conformity, performance, resources management and economic and environmental intelligence, also "the infrastructure must be managed in the most effective manner, at the same time from the environmental and financial point of view" [4]. Thus, the integration of the notions of Green IT and CSR in the ICT governance implies necessarily a sustainable governance, "a sustainable IT strategy should be aligned on the sustainability strategy on the scale of the company" [5] This sustainable governance allows identifying and structuring the requests of the stakeholders by taking heed of the economic, environmental and societal concerns. Consequently, the methods and the criteria of conventional governance are reinforced by the CSR and Green IT factors.

Conclusion

Our work in this paper exposes the state of the art of the green governance, which we have qualified as new generation managerial model. The conceptual model, presented here, is a part of a research work which is in progress. It establishes a basis to pilot a reflection on the new generation ICT management systems based on CSR approach and Green IT strategy, and aims to enhance research in the field of responsible ICT management. Our major contribution is the use of a new strategy that incorporates governance as part of an integrated approach of Green IT and CSR strategy, which aims to ICT management differentiation based on sustainability-related value.

It is therefore too early to draw conclusions; however, the objective of our model is to contribute to the perception of an ICT responsible management, in order to provide to the companies a roadmap to create new models of green business, thought on sustainable resources.

Figure 3 .

 3 Figure 3. Evolution of Green IT

  Figure 4. Stakeholder theory diagram

Fig. 5 .

 5 Fig. 5.Internal and external vision of the ICT green governance

Social Economic Environmental CSR Figure

  2. Venn diagram of the Corporate Sustainability and ResponsibilityAfter the oil crisis baptized "First Oil Shock" in 1973 and the "Second Oil Shock" in 1979, the government of the United States launched in 1992 the "Energy Star" program for achieving energy saving in the ICT and data-processing field, this phase is also marked by the publication in 1993 of a first eco-label in the Green IT domain. The "Energy Star" program was initiated by the Environmental Protection Agency (EPA) after the Rio de Janeiro Earth Summit which joined together nearly 110 Heads of States and governments and represented by 178 countries. This summit was marked by the adoption of the "Rio Declaration on Environment and Development" consisted of 27 principles, thus concretizing the concept of sustainable development, an essential step in the birth of the Green IT concept.

Journal of Data Mining and Digital Humanities http://jdmdh.episciences.org

http://jdmdh.episciences.org